The Piece Table

Rendering is half an editor. The other half is the document model: the data structure holding the text being edited. It has to absorb millions of tiny edits — one keystroke each — anywhere in a file that might be 500 MB of logs, while supporting undo, and never blocking the paint loop.

The naive model is a single std::string. Every insertion in the middle shifts everything after it — O(n) per keystroke — and worse, every edit destroys information: after str.insert(...) the old text is gone, so undo needs you to have copied something somewhere first. Editors have produced a whole zoo of better structures. The gap buffer keeps a hole at the cursor so local typing is O(1) (Emacs; our sibling terminal-editor course builds one, along with its heavier cousin the rope). This course builds the structure used by Bravo — the first WYSIWYG editor, at Xerox PARC — then Microsoft Word, AbiWord, and (in tree-refined form) VS Code: the piece table. Charles Crowley's paper "Data Structures for Text Sequences" surveys the field and comes down firmly in its favor; the VS Code team's 2018 write-up of reboarding onto a piece tree is the modern sequel, and both are in this course's extended reading.

Two buffers, never edited

The piece table's move is to declare that text, once written, is immutable. It keeps exactly two byte buffers:

• the original buffer — the file as loaded. Read-only, forever.
• the add buffer — every byte the user has ever typed, appended in arrival order. Append-only: nothing in it moves or dies either.

Neither buffer is the document. The document is a third thing: a list of pieces, each saying "take len bytes from buffer B starting at offset start". Read the pieces in order, concatenating their spans, and the document appears:

struct Piece {
    bool add;       // which buffer: false = original, true = add
    size_t start;   // offset into that buffer
    size_t len;     // bytes
};

Load "the quick fox": one piece, {original, 0, 13}. Type "brown " at offset 10: the six bytes go to the end of the add buffer — wherever the cursor is — and the piece list becomes:

{original, 0, 10}   "the quick "
{add,      0,  6}   "brown "
{original, 10, 3}   "fox"

Every edit is span surgery: an insertion splits at most one piece and adds one; a deletion trims or removes pieces without touching a single byte of text. The costs follow: insertion copies s.size() bytes into the add buffer plus O(pieces) list work — never O(document). A 500 MB file with one typo fixed is two buffers and three pieces.

The design rewards you three more times downstream:

• Undo is nearly free. Since buffers never change, any prior document state is fully described by a prior piece list — a handful of structs. Snapshot the list (or just the changed slice of it), restore it later; the bytes are still there. Compare that with string-model undo, which must squirrel away every overwritten span.
• Loading is instant. "Read-only original buffer" fits mmap exactly: the OS pages the file in as pieces get read, and the editor shows a gigabyte file before having read most of it.
• Sharing is safe. A std::string_view into either buffer stays valid across edits (only the piece list changes) — which is why our reading APIs can hand out cheap views instead of copies.

The cost, honestly stated: the piece list grows by O(1) pieces per noncontiguous edit, and reading offset pos means walking pieces to find which one covers it — O(pieces). Long editing sessions on huge files are why VS Code turned the list into a balanced tree with subtree-length counts (O(log pieces) lookup). The flat std::vector version you'll build is the same algorithm with a linear index; upgrading the container later changes nothing about the surgery.

The one optimization that matters: coalescing

Typing "hello" naively appends five pieces. But notice what typing looks like in the table: each new char lands at the end of the add buffer, and each insertion point is exactly the end of the piece created by the previous keystroke. So before splitting, check: is the insertion point the end of an add-buffer piece whose span ends exactly where the add buffer used to end? If so, the new bytes continue that span — extend len, done. One piece per typing burst instead of one per keystroke. This check is what keeps the piece list short in practice, and the tests count pieces to make sure you implemented it.

For deletion there's a symmetric subtlety: deleting a range that starts mid-piece and ends mid-another means the first piece keeps its head, the last keeps its tail, and everything between vanishes. Deleting from the middle of one piece splits it in two — the table grows on delete, which surprises people once and never again.