Piece Tables, Gap Buffers, and Ropes in Editor Buffers

The editing model of an editor is the component that holds the document as characters and answers two families of question: which character lives at offset N, and what text lies between offset A and offset B. Almost everything else in the window is derived from those answers. Syntax highlighting, folding, the minimap, the outline, and the text sent to a language server are all produced by reading the buffer, usually from a thread that is not the one accepting keystrokes.

Two workloads pull in opposite directions. Typing is a stream of small edits that cluster near the caret, and each one has to be reflected on screen before the next frame. Rendering asks for line counts, line start offsets, and slices of a few dozen lines scattered across the entire document, far more often than edits arrive. A contiguous character array answers the rendering queries at pointer arithmetic speed but costs a memmove of the whole tail for every insertion. A linked list of one-character nodes makes insertion cheap and makes everything else impractical. The three structures that editors actually use are attempts to find a different point on that curve.

The operations the buffer has to make cheap

A buffer interface in a real editor is small, and its complexity requirements are specific. Insertion and deletion happen at an arbitrary offset, not only at the end. Offset lookup returns the character or the bytes at a given position. Line lookup converts in both directions: given a line number, find its first offset; given an offset, find its line. Range slicing extracts text, and equality comparison decides whether a saving pass can skip writing a file at all.

The cost of each operation is usually stated per edit or per query, but the number that matters is the interaction between them. A source file of 100 KiB with 10,000 recorded edits is a different object from the same file freshly loaded, even though both contain the same 100 KiB of text, because the representation now carries metadata proportional to the edit history rather than to the content. A common table of what each structure gives:

Structure	Insert/delete	Offset lookup	Slice	Snapshot
Contiguous array	O(n)	O(1)	O(k)	O(n) copy
Gap buffer	O(1) at gap, O(n) elsewhere	O(1)	O(k)	O(n) copy
Piece table	O(log p) with a tree of p pieces	O(log p)	O(log p + k)	O(1) if persistent
Rope	O(log n)	O(log n)	O(log n + k)	O(1) if persistent

The last column is often the one that decides the design. Background parsing, incremental synchronization to a language server, and asynchronous save all want a stable view of the document while the user keeps typing.

Gap buffers: one contiguous array with a hole in it

The gap buffer keeps a single array with a reserved empty region, the gap, positioned at the caret. Characters before the gap and after the gap are the document’s prefix and suffix. Inserting at the caret writes into the front of the gap and advances its start; deleting before the caret retracts it. Both are constant-time and touch one element.

The cost appears the moment an edit lands anywhere else, because the gap has to move: characters between the old gap position and the new one must be shifted one by one. Moving the gap a distance of d over an array of capacity c costs d byte moves, so a burst of edits at one place is nearly free while alternating edits at the top and bottom of a large file degenerate to linear work per keystroke.

/* Gap buffer: buf holds prefix ++ gap ++ suffix. */
struct gapbuf { char *buf; size_t cap, gap_start, gap_end; };

static void gap_move(struct gapbuf *g, size_t pos) {
    while (g->gap_start > pos) {           /* shift prefix right */
        g->buf[--g->gap_end] = g->buf[--g->gap_start];
    }
    while (g->gap_end < g->cap && g->gap_start < pos) { /* shift suffix left */
        g->buf[g->gap_start++] = g->buf[g->gap_end++];
    }
}

static void gap_insert(struct gapbuf *g, size_t pos, char c) {
    if (g->gap_start == g->gap_end) {      /* gap exhausted: grow and re-hole */
        size_t new_cap = g->cap ? g->cap * 2 : 64;
        char *nb = realloc(g->buf, new_cap);
        size_t suffix = g->cap - g->gap_end;
        memmove(nb + new_cap - suffix, nb + g->gap_end, suffix);
        g->buf = nb;
        g->gap_end = new_cap - suffix;
        g->cap = new_cap;
    }
    gap_move(g, pos);
    g->buf[g->gap_start++] = c;
}

The consequence is a rule that shows up in editor behaviour rather than in code: the gap’s inertia is why a search that walks the document in steps costs far more than a search that jumps directly, and why the representation stays popular for interactive buffers whose edits are local. GNU Emacs has long used gap buffers for buffer text, which is a reasonable choice at its scale; the structure was described in detail in Finseth’s book on text editing.

Piece tables: keep the original immutable

The piece table removes the memmove entirely by never modifying stored text. It maintains two character stores: the original file content, which is treated as read-only, and an append-only add buffer that only ever grows at its end. The document is a sequence of pieces, each a triple of a source, a start offset in that source, and a length. The pieces in order, concatenated, are the document.

Inserting text appends it to the add buffer and splices a new piece into the piece list, splitting the piece that contained the insertion point into a prefix and a suffix. Deleting text splits pieces and drops the middle, or adjusts lengths when a deletion falls inside a single piece. Nothing is copied, so an edit costs the allocation of a small descriptor plus a splice in the piece list.

If the piece list is a plain array, splicing is O(p) for p pieces and the structure degrades exactly where a gap buffer degrades, only for a different reason: a long editing session turns one piece into thousands. Storing the pieces in a balanced binary search tree, weighted by the number of characters in each subtree, restores O(log p) for splicing and O(log p) for offset lookup. The weight is not the node count but the character count, which is what makes “find the piece containing offset N” a descent rather than a scan.

The original-plus-add split has a second benefit that only becomes visible later: the original store can be left memory-mapped on disk or kept uncompressed for random access, while the add buffer holds only what the user typed. Memory use is roughly the file size plus the bytes typed, plus a descriptor per piece — small, but multiplied by every edit. This is the model that the editing core behind Visual Studio Code uses, and it is the reason the editor can hand a background thread a consistent view of a large file without copying it.

Ropes: split strings and share them

A rope is a binary tree whose leaves hold short strings and whose internal nodes hold a concatenation. Each internal node also stores the total character count of its left subtree; a lookup at offset N compares N against that weight and descends left or right, so indexing is O(log n) where n is the number of leaves. Insertion is a split followed by a concatenate, deletion a split followed by a join, both O(log n) if the tree is kept balanced. The structure was introduced by Boehm, Atkinson, and Plass as an alternative to flat strings for very large text.

class Node:
    __slots__ = ("text", "left", "right", "weight")

def weight(n):
    return 0 if n is None else (len(n.text) if n.text is not None
                                else n.weight)

def char_at(node, i):
    while node.text is None:               # internal node: descend by weight
        w = weight(node.left)
        if i < w:
            node = node.left
        else:
            i -= w
            node = node.right
    return node.text[i]

The property that distinguishes ropes from the other two structures is sharing. Because concatenation and splitting never mutate the nodes below them, two ropes can share most of their subtrees, and an edit produces a new root that reuses the old structure. That is exactly the semantics of a persistent tree in the sense of Okasaki’s work, and it makes a snapshot of the whole document O(1) in the number of nodes rather than O(n) in characters. Undo becomes a stack of old roots, and a background parser can hold an immutable view while the foreground edits a different root. The price is constant factors: pointer chasing, poorer cache locality, and rebalancing logic that has to be correct.

Finding line N without walking the document

None of the three structures answers line queries directly, so editors layer a second index on top. The naive line index is an array of line start offsets, which answers “first offset of line k” in O(1) and “which line contains offset N” in O(log lines) by binary search. It fails the moment an edit inserts or removes a newline, because every subsequent entry shifts by one and the update is O(lines) — acceptable per keystroke only for small files.

The fix is to make the index a balanced tree keyed by line number but weighted by the number of newlines and characters in each subtree, so that an edit touches O(log lines) nodes. Such an index is usually maintained alongside the text structure rather than derived from it, and it stores, for each subtree, both the newline count and the character count; conversions between offsets and line/column positions then cost O(log lines) each. A long line is the degenerate case: a single 10 MiB minified line makes per-line work proportional to the whole file, which is why line-based operations and byte-based operations must remain distinct in the API even where they coincide in practice.

Line indexing is also where the buffer’s unit becomes a visible problem rather than an internal detail. Positions in the editor’s public interfaces are not always byte offsets, and the conversion between what a language server counts and what the buffer counts has its own cost model, examined in Byte Offsets, UTF-16 Code Units, and Editor Positions.

Where each structure breaks

Gap buffers are the simplest to implement and the fastest for local typing, and they fail on two inputs: alternating edits far apart, which force repeated long moves, and any attempt to snapshot cheaply, which requires a full copy. A single gap also means a single writer; concurrent readers need a lock or a copy.

Piece tables degrade as the number of pieces grows, since the descriptor list becomes the dominant cost if it is not a balanced tree; a session with a million tiny edits accumulates a million descriptors, and periodically flattening the piece list back into a contiguous file buffer is a real maintenance operation rather than an optimisation. The add buffer also never shrinks on its own after deletions, so a long session can hold memory proportional to everything typed, not to what remains.

Ropes pay for their sharing in locality. Pointer-chasing a tree of small chunks is slower than scanning one array, and choosing the leaf size is a trade: large leaves make scans fast and splits coarse, small leaves give fine-grained edits at the cost of more nodes. Ropes are also memory-hungry per character at small document sizes, which is why implementations that use them typically set a threshold below which the document is a flat string.

All three structures assume the document is one buffer of bytes or code units. None of them says what a position means when the document is UTF-8 and the consumer counts UTF-16 code units, and none of them constrains how edits are batched before they leave the process. Those two subjects carry the rest of the editing model, along with incremental parsing and tree reuse, which consumes these buffers to produce syntax structure.