Rust · piece table text buffer
Edit big text
without rewriting it.
Quill is a dependency-free editable text buffer written from scratch in Rust, pure standard library. It is a piece table backed document with correct line and column indexing, a cursor and selection model, a coalescing undo and redo history, and substring search. Inserting near the front of a megabyte of text costs work proportional to the pieces it touches, not the size of the document. Type in the editor here and watch the piece table split, grow, and coalesce in real time.
Proven against a naive buffer
The pieces you see on the right are the real data model. Two immutable character stores exist: original holds the starting text and add is append-only. The document is an ordered list of pieces, each pointing at a range inside one store, so an insert appends to add and splices in at most one new piece, and nothing large is ever rewritten. That is the same PieceTable the Rust crate uses, and it is verified against a naive String reference on every single edit.
- Differential against a naive String. The same random stream of insert, delete, and replace operations runs on the piece table and on a plain
String; after every operation the full contents must match, and so must every line and column query.
- Undo and redo round-trip. A random op sequence is fully undone back to the exact initial state, then fully redone, with a mixed walk checked against a reference list of every state. Undo past the beginning stops cleanly and a new edit kills redo.
- Buffer invariants. Total length and line count stay correct, and no edit panics at a boundary: start, end, empty buffer, or a multibyte UTF-8 boundary.
- Multi-cursor and structured replace. Multi-cursor inserts, selection replacement, and selection deletion match the same edits as single-cursor splices, and piece count tracks the edit count rather than the document size.
# bounded for CI, op count tunable by env var; every op is compared to the reference
cargo test --release
Running tests/differential.rs test result: ok. 1 passed
Running tests/undo_redo.rs test result: ok. 7 passed
Running tests/invariants.rs test result: ok. 4 passed
Running tests/multi_cursor.rs test result: ok. 7 passed
Running tests/stress.rs test result: ok. 6 passed
# plus 17 lib unit tests and 1 doc test, all passing. QUILL_FUZZ_OPS scales the op counts.
The pieces of the design
Six ideas make the whole buffer. Each one is small enough to read in the source, and together they are why an edit never rewrites the document.
Two immutable stores original + add
The starting text lives in an immutable original store. Every insert appends to an add store that only ever grows. Neither store is edited in place.
Pieces ordered spans
The document is an ordered list of pieces, each pointing at a character range inside one store. Reading the document is walking the pieces in order.
Insert and delete by split insert / delete
An insert splits at most one piece and splices in a new one; a delete splits at both ends and drops the pieces between. Work is proportional to the pieces touched, not the document size.
Coalescing history undo / redo
Contiguous typing collapses into a single undo group, so one press of undo removes a whole typed run rather than one letter. A new edit clears the redo stack.
Line and column indexing line_col
Every character offset maps to a correct line and column, kept accurate across each edit, including at multibyte UTF-8 boundaries, since offsets count Unicode scalar values.
Search find_all
A direct substring scan over the document returns the character offset of every match, the same call the live editor uses to highlight and count matches.
Why a piece table
There are several ways to store an editable document. Quill picks the piece table and implements it from scratch, in the same family as the structures real editors ship.
Plain String or VecSimple and fine for small text. But inserting near the front rewrites the entire tail on every edit, which grows costly as the document and the number of edits grow.
Gap buffer (Emacs)Keeps a movable gap at the cursor so edits near it are cheap. Fast for local editing; jumping far means shifting the gap to the new position first.
Rope (used in many editors)A balanced tree of text chunks, strong for very large files and structural sharing. Powerful, and heavier to implement and to read than a piece table.
Piece table (VS Code)Two immutable stores and an ordered list of pieces. Existing text is never rewritten, undo falls out naturally, and the model stays small. This is the structure Quill implements.
QuillA from-scratch piece table you can read end to end, in pure Rust with no dependencies, with correct line and column indexing, coalescing undo and redo, and search, verified against a naive String on every edit.
See it run
The demo subcommand edits a line, types a second one, searches, replaces, walks undo and redo, and then prints the piece table it ended up with. Real output, straight from the release binary.
$ cargo build --release && ./target/release/quill demo
start: 2 lines, 20 chars, 1 pieces
after insert " jumps": "The quick brown fox jumps\n"
after typing line 2: "The quick brown fox jumps\nover the lazy dog"
now : 2 lines, 43 chars, 4 pieces
search "the" matched at char offsets [31]
after replace first "the" -> "THE": "The quick brown fox jumps\nover THE lazy dog"
after undo (replace): "The quick brown fox jumps\nover the lazy dog"
after undo (typed line):"The quick brown fox jumps\n"
after redo (typed line):"The quick brown fox jumps\nover the lazy dog"
after redo (replace): "The quick brown fox jumps\nover THE lazy dog"
piece table structure (6 pieces):
[0] original bytes 0..19 = "The quick brown fox"
[1] add bytes 0..6 = " jumps"
[2] original bytes 19..20 = "\n"
[3] add bytes 29..34 = "over "
[4] add bytes 46..49 = "THE"
[5] add bytes 37..46 = " lazy dog"
final: 2 lines, 43 chars, 6 pieces
Use it
# build, run the correctness gates, try the binary
cargo build --release
cargo test
./target/release/quill demo
./target/release/quill path/to/file.txt --region 0 10
# or drop the library into your own project
use quill::TextEditor;
let mut ed = TextEditor::new("hello");
ed.insert(5, " world"); // "hello world"
ed.replace(0, 5, "HELLO"); // "HELLO world"
ed.undo(); // back to "hello world"
let hits = ed.find_all("o"); // char offsets of every "o"