English | 中文

lightweight, stb-style single-header C89 libraries for building high-performance text editor buffers:

• piecetab.h — a byte-level piece table backed by a B+ tree, with copy-on-write snapshots, transactional editing, and zero-copy reads.
• linecache.h — a metric B+ tree mapping byte offsets to line numbers, maintaining a line-number cache under heavy edits.
• undotree.h — a version tree + edit journal + diff service based on interval algebra, riding on top of pt_Buffer COW snapshots.

These libraries are independent and composable: piecetab stores bytes ("clean octets" — no line or encoding awareness), linecache tracks line breaks, undotree manages the version graph and computes diffs between any two versions. Combine them to get a full editor buffer with O(log n) offset ↔ line navigation and undo/redo.

Peripheral libraries extend the core toward a full editor:

• cellgrid.h — a screen buffer with a diff layer: grid cells, scroll/move/fill primitives, and a redraw-diff driver for efficient screen updates.
• termfeed.h — a libtermkey-style terminal input state machine: raw bytes to decoded keys (CSI/SS3, UTF-8, alt keys, mouse, OSC52).

All of them follow the same stb-style layout: single-header C89 implementation, a Lua binding in lua/, and a test file in tests/.

AI Usage

• All implements (stb header) are written by hand, AI used to find solutions, help with design, and generate documentation.
• All tests are written by AI, reviewed by human, used to verify the correctness of the implementation, and to ensure that the code meets the requirements and specifications.
• editor.lua is written by AI, used to demonstrate the usage of the library, and to provide a reference for developers who want to use the library in their own projects.

Motivation

This project is driven by the need for a high-performance, low-latency text buffer that remains predictable under heavy edits, large files, and complex content:

• Stable performance under insert/delete workloads
• Cheap snapshots for undo/redo and asynchronous consumers
• A compact, single-header implementation suitable for embedding

Features

piecetab.h

• Immutable buffers + COW: pt_Buffer is a refcounted snapshot; the first edit on a cursor forks a private transient tree, pt_commit freezes it into a new buffer, pt_rollback discards it and returns the source buffer (retained for the caller). Both detach the cursor (C->tree = NULL); re-attach with pt_seek on the returned buffer
• Compacting freeze: pt_commit merges physically adjacent literals produced by freezing contiguous holes and rebalances the tree, so long typing runs collapse into single pieces instead of fragmenting the tree
• Two piece kinds: zero-copy literal pieces referencing user memory, and pooled mutable hole pieces absorbing small edits in place
• Transactional OOM safety: edits pre-reserve pool objects; on PT_ERRMEM the structure stays consistent and the cursor stays valid
• Arena-backed literals: pt_reserve / pt_scratch / pt_literal write bytes directly into the tree's arena without an extra copy
• Generational compaction: each edit generation owns its arena; pt_compact produces a fresh standalone buffer — bytes owned by the old generations are copied into a compact new arena, external memory (e.g. a large mmap) is referenced as-is, and releasing the old chain reclaims all of its memory

linecache.h

• Metric B+ tree: byte offsets and line breaks are double-counted per subtree, enabling O(log n) navigation in both directions
• Bulk loading: lc_scan builds the tree bottom-up from a scanner callback, far cheaper than per-line insertion
• Full editing: single break insert (lc_markbreak), range delete (lc_remove), splice (lc_splice), and mid-tree text insertion (lc_insert / lc_append) with full OOM rollback

undotree.h

• Version graph: tree of immutable snapshots (ut_Node), each carrying a changeset (hunk list) from its parent and an opaque payload (e.g. pt_Buffer)
• Edit journal: uncommitted edits stored as (off, del, ins) triples, normalised into a hunk list on commit
• Hunk algebra: compose (X→Y ∘ Y→Z → X→Z), invert, and normalise operations on interval-change hunks
• Fresh-vid protocol: ut_freshvid(S) sentinel represents the uncommitted state; ut_diff(from, to) handles any combination of committed versions + fresh endpoints via four-phase compose

Quick Start

All headers are stb-style: include the header anywhere, define the *_IMPLEMENTATION macro in exactly one translation unit.

piecetab.h

#define PT_IMPLEMENTATION
#include "piecetab.h"

int main(void) {
    pt_State *S = pt_open(NULL, NULL);        /* default allocator */
    pt_Buffer src, out;
    pt_Cursor C;
    char      buf[32];
    size_t    n;

    src = pt_from(S, "hello world", 11);      /* zero-copy buffer */
    pt_seek(&C, src, 5);
    pt_insert(&C, ",", 1);                    /* reference semantics */
    out = pt_commit(&C);                      /* freeze into new buffer */

    pt_seek(&C, out, 0);
    n = pt_read(&C, buf, sizeof(buf));        /* "hello, world" */

    pt_release(src);
    pt_release(out);
    pt_close(S);
    return (int)n;
}

linecache.h

#define LC_IMPLEMENTATION
#include "linecache.h"
#include <string.h>

/* scanner returns the length of the next line (incl. '\n'), 0 to stop */
static unsigned scan(void *ud, size_t pos) {
    const char **s = (const char **)ud;
    const char  *nl = strchr(*s, '\n');
    unsigned     len;
    (void)pos;
    if (nl == NULL) return 0;
    len = (unsigned)(nl - *s) + 1;
    *s += len;
    return len;
}

int main(void) {
    const char *text = "one\ntwo\nthree\n";
    lc_State *S = lc_open(NULL, NULL);
    lc_Cache *c = lc_newcache(S);
    lc_Cursor C;

    lc_scan(c, scan, &text);           /* bulk-load line breaks */
    lc_seekline(&C, c, 2);             /* line 2 starts at ...   */
    /* lc_offset(&C) == 8, lc_breaks(c) == 3 */

    lc_close(S);                       /* frees all caches */
    return 0;
}

editor.lua

editor.lua is an AI-written modal editor demo that wires the libraries together: a piecetab/linecache buffer (pt.doc), a cellgrid screen buffer, and termfeed terminal input. Ed.new(content?, term?, grid?) builds an editor from a string; Ed.open(filename, term?, grid?) loads a file; both accept injected term/grid objects (tests use fakes). It also serves as a C-module incubation ground — helpers marked TODO(C) (char motion, column math) are candidates for promotion into C.

Syntax highlighting: files opened with a .c/.h/.lua extension get tree-sitter highlighting (keyword/string/comment/function styles) via the treesitter Lua binding (see lua/treesitter.c). Ed:open_language(lang) enables it manually. Editing updates highlights incrementally.

local Ed = require("editor")

local e = Ed.open("file.txt")            -- or Ed.new("hello\nworld")
e:keymap("normal", "G", function(self)
  self.doc:seek("line", self.doc:breaks() - 1)
end)
e:command("hello", function(self, arg, bang)
  self.msg = "hello, " .. arg
end)

Custom keys/commands hook into the per-mode registries (mode is "normal" / "insert" / "command"). Built-in keys: h/j/k/l, w/b, 0/$, gg/G, x, dd, i/a/o/O, u/<C-r>, :; commands: :w, :q, :wq, :e.

Run the tests with just lua/ed; smoke-test interactively with lua editor.lua [file].

API Overview

piecetab.h

Category	Functions
Lifecycle	pt_open, pt_close, pt_reset, pt_getallocf
Buffer	pt_empty, pt_from, pt_compact, pt_retain, pt_release
Query	pt_bytes, pt_version
Cursor	pt_seek, pt_locate, pt_advance, pt_offset
Read	pt_read, pt_piece, pt_next, pt_prev
Edit	pt_edit (copy), pt_insert / pt_append / pt_splice / pt_remove (reference)
Txn	pt_commit, pt_rollback
Arena	pt_reserve, pt_scratch, pt_literal

Reference-semantics edits (pt_insert etc.) do not copy input bytes — the caller must keep the memory alive while any buffer references it. pt_edit copies into hole pieces (len <= PT_MAX_HOLESIZE per call).

linecache.h

Category	Functions
Lifecycle	lc_open, lc_close, lc_reset
Cache	lc_newcache, lc_delcache
Bulk	lc_scan
Query	lc_breaks, lc_bytes
Cursor	lc_seek, lc_seekline, lc_locate, lc_locline, lc_advance, lc_advline
Query	lc_offset, lc_line, lc_col, lc_lineoffset, lc_linelen
Edit	lc_markbreak, lc_clearbreaks, lc_remove, lc_splice, lc_insert, lc_append

undotree.h

Category	Functions
Lifecycle	ut_open, ut_close, ut_setcleaner
Tree	ut_newtree, ut_deltree
Journal	ut_record, ut_unrecord, ut_freshcount, ut_discard
Version	ut_commit, ut_switch
Navigate	ut_root, ut_current, ut_parent, ut_payload, ut_childcount
Navigate	ut_firstchild, ut_lastchild, ut_nextsib, ut_younger, ut_older
Navigate	ut_ancestor
Diff	ut_freshvid, ut_diff, ut_freshdiff, ut_hunks, ut_mapoffset

See docs/piecetab.md, docs/linecache.md, and docs/undotree.md for the full API references.

Configuration

Override before including the implementation:

Macro	Default	Meaning
PT_FANOUT / LC_FANOUT	62	max children per node
LC_LEAF_FANOUT	62	max lines per leaf
PT_MAX_HOLESIZE	64	hole piece capacity
PT_MAX_LEVEL / LC_MAX_LEVEL	16	max tree depth
PT_PAGE_SIZE / LC_PAGE_SIZE / UT_PAGE_SIZE	65536	pool allocator page size
PT_ARENA_SIZE	1024	arena block minimum size
PT_COMPACT_RANGES	64	compact range array initial capacity

All libraries accept a custom allocator (lc_Alloc / pt_Alloc / ut_Alloc, Lua-style realloc signature) at *_open.

Repository Layout

• *.h — stb-style single-header libraries (pure C89, self-contained): piecetab.h, linecache.h, undotree.h, cellgrid.h, termfeed.h
• lua/ — Lua side: one binding name.c + API declaration name.d.lua per library, the editor.lua demo, and tests/ with Lua tests. Bindings build to lua/*.so (Lua 5.5, primary) and lua/luajit/*.so (LuaJIT, compat)
• tests/ — C tests: one *_test.c per library; tests.h (shared runner + asserts), gen_entries.lua (test-entry generator), lc_tests.h (linecache-specific helpers shared by both fanout variants)
• docs/, notes/ — API reference docs and design records

Documentation

• docs/piecetab.md — piecetab API reference & implementation notes (中文)
• docs/linecache.md — linecache API reference & implementation notes (中文)
• docs/undotree.md — undotree API reference & integration guide (中文)

Peripheral libraries (cellgrid.h, termfeed.h) have no API docs yet — see their lua/*.d.lua declarations and notes/design_cellgrid.md, notes/design_termfeed.md.

• notes/ — design documents: architecture overviews (brief_*.md), algorithm designs (design_*.md), and the range-delete algorithm evolution history

Testing

Tests run with tiny fanout (4) under ASan/UBSan to force tree splits, plus coverage builds via lcov. All libraries maintain 100% line / function coverage and ~90% branch coverage.

# C tests (one runner per lib)
just lc     # linecache tests
just pt     # piecetab tests
just ut     # undotree tests
just cg     # cellgrid tests
just tf     # termfeed tests
just cov    # coverage report

# Lua binding tests — just lua/<recipe> runs lua/justfile
just lua/pt  # piecetab binding (also lua/cg, lua/tf, lua/ed)
just lua/ts  # treesitter binding tests
just lua/ts-cov  # treesitter binding coverage
just lua/ts-lines  # treesitter uncovered lines

Dependencies: libtree-sitter (homebrew tree-sitter) for the treesitter binding; grammars are fetched and compiled by misc/fetch_grammars.sh (run by just lua/ts-grammars).

See CONTRIBUTING.md for coding conventions.

License

MIT, same as Lua.