Piece Table, in depth: immutable buffers, a tested implementation, cheap undo and the piece tree inside VS Code

The problem with storing text as one string

Start with the costs. A document of n characters held in a single array makes an insert at position k cost O(n - k) copying; typing at the top of a 50 MB log copies 50 MB per keystroke. A line array, one string per line, makes inserts cheap within a line but costs a separate object for every line, which dominates memory on files with millions of short lines.

Three structures solve this in different ways. A gap buffer keeps an empty gap at the cursor so local typing is O(1), but moving the cursor far away moves the gap, copying everything in between; Emacs is the classic user. A rope is a balanced tree of string chunks with O(log n) edits anywhere, at the cost of splitting and rebalancing text nodes. The piece table keeps the text itself immutable and puts all of the mutation into a small index of spans. That one decision is what makes its undo, memory and load-time behaviour so good.

Two buffers and a list of pieces

A piece table has three parts.

1. The original buffer: the file as loaded. It is read-only for the lifetime of the editing session.
2. The add buffer: every character the user ever types, appended in typing order. It only grows.
3. The piece list: an ordered sequence of descriptors, each naming a buffer, a start offset and a length. The document is the concatenation of the spans the pieces describe, in order.

A freshly opened file is one piece covering the whole original buffer. Inserting text appends it to the add buffer and splits the piece at the insertion point into a left part, a new piece pointing at the added text, and a right part. Deleting text never touches either buffer; it shrinks, splits or removes pieces so the deleted range is no longer referenced. Each edit changes a constant number of pieces, regardless of file size.

Worked example

Follow the diagram step by step. Load the quick fox (13 characters). The piece list is [orig 0..13].

Insert brown at position 10, just before fox. The six characters go to add-buffer offsets 0 to 5. Position 10 lands inside the only piece, at offset 10, so it splits: orig start 0 len 10 (the quick ), add start 0 len 6 (brown ), orig start 10 len 3 (fox). The document reads the quick brown fox.

Delete six characters at position 4, removing quick . The range [4, 10) falls entirely in the first piece, so that piece is trimmed to its head, orig start 0 len 4. The list becomes three pieces and the document reads the brown fox. Neither buffer changed during the delete. Our implementation below printed exactly these three pieces when run on this sequence.

A tested implementation

The implementation keeps pieces in a Python list, which makes locating a position O(pieces). That is the right first version: simple, easy to test, and fast enough for a few thousand pieces. It was fuzz-tested against a plain string over 300 random documents with 60 random inserts and deletes each, then undone back to the start.

from typing import NamedTuple

class Piece(NamedTuple):
    buf: str        # "orig" or "add"
    start: int
    length: int

class PieceTable:
    def __init__(self, text: str = ""):
        self.orig = text
        self.add = []                       # append-only
        self.pieces = [Piece("orig", 0, len(text))] if text else []
        self.undo_stack, self.redo_stack = [], []

    def _locate(self, pos):
        # piece index and offset inside it for a document position
        for i, pc in enumerate(self.pieces):
            if pos < pc.length:
                return i, pos
            pos -= pc.length
        return len(self.pieces), 0

    def _snapshot(self):
        self.undo_stack.append(list(self.pieces))
        self.redo_stack.clear()

    def insert(self, pos, text):
        if not text:
            return
        self._snapshot()
        new = Piece("add", len(self.add), len(text))
        self.add.extend(text)
        i, off = self._locate(pos)
        if off == 0:
            prev = self.pieces[i - 1] if i > 0 else None
            if prev and prev.buf == "add" and prev.start + prev.length == new.start:
                self.pieces[i - 1] = Piece("add", prev.start, prev.length + new.length)
            else:
                self.pieces.insert(i, new)
        else:
            pc = self.pieces[i]
            self.pieces[i:i + 1] = [Piece(pc.buf, pc.start, off), new,
                                    Piece(pc.buf, pc.start + off, pc.length - off)]

    def delete(self, pos, length):
        if length <= 0:
            return
        self._snapshot()
        out, cursor, end = [], 0, pos + length
        for pc in self.pieces:
            a, b = cursor, cursor + pc.length      # piece covers [a, b)
            cursor = b
            if b <= pos or a >= end:
                out.append(pc)
                continue
            if a < pos:                            # keep the head
                out.append(Piece(pc.buf, pc.start, pos - a))
            if b > end:                            # keep the tail
                out.append(Piece(pc.buf, pc.start + end - a, b - end))
        self.pieces = out

    def undo(self):
        if self.undo_stack:
            self.redo_stack.append(self.pieces)
            self.pieces = self.undo_stack.pop()

    def redo(self):
        if self.redo_stack:
            self.undo_stack.append(self.pieces)
            self.pieces = self.redo_stack.pop()

    def text(self):
        out = []
        for pc in self.pieces:
            src = self.orig if pc.buf == "orig" else self.add
            out.append("".join(src[pc.start:pc.start + pc.length]))
        return "".join(out)

Two details deserve attention. The insert path coalesces: when the user types characters one after another, each new character lands right after the previous one in the add buffer, so the code extends the last add piece instead of creating a new one. Without this, typing a paragraph would create one piece per keystroke. And delete handles ranges spanning many pieces in a single pass, keeping the head of the first affected piece and the tail of the last.

Undo comes almost free

Because the buffers never change, a past version of the document is fully described by its piece list. Undo is therefore just restoring an earlier list. The code above snapshots the whole list, which costs O(pieces) per edit; that is fine for small documents and a clear model of the idea. Production editors store the inverse operation instead (which pieces were removed and which were added at what index), making each undo record O(1) in size. Either way, no text is ever copied to support undo, unlike a design that saves deleted strings.

This is also why piece tables pair well with persistent data structures: if the piece index is itself an immutable tree, every version shares almost all of its nodes with the previous one, and keeping hundreds of versions costs little. See persistent data structures for the path-copying technique that makes this work.

From a list to a piece tree

The list version breaks down on large, heavily edited files. Finding a position walks the list, so after tens of thousands of edits each keystroke pays a linear scan. Editors also need to map between offsets and line numbers constantly, for rendering, go-to-line and diagnostics.

The fix is to store pieces in a balanced binary search tree ordered by document position, where each node caches the total text length of its left subtree. Locating offset k becomes a descent: if k is less than the left length, go left; if it falls inside this node, stop; otherwise subtract and go right. Insert and delete become O(log p) for p pieces, with rotations updating the cached sums. Cache the number of line breaks in the left subtree as well, and the same descent answers which line an offset is on, and where line L starts.

Visual Studio Code moved to exactly this design in release 1.21 (March 2018) and named it a piece tree. Its engineering blog describes a red-black tree of pieces in which each node tracks the left subtree length and line-feed count, multiple original buffers read in roughly 64 KB chunks rather than one, and per-buffer arrays of line-start offsets. The previous line-array model used about 600 MB to open a 35 MB file with 13.7 million lines; the piece tree brought memory close to the file size. The published trade-off is that looking up a line became O(log n) instead of O(1), which their measurements showed was negligible in rendering time.

Failure modes

The piece table moves complexity out of text storage and into bookkeeping, and the bookkeeping is where it goes wrong.

• Piece fragmentation. Scattered edits (multi-cursor replace, find and replace all) create many small pieces. A list implementation degrades linearly. Use a tree, or periodically rebuild the table into a single fresh buffer when the piece count passes a threshold.
• Unbounded add buffer. Deleted typed text is never reclaimed while undo history references it. A long-running session that pastes and deletes large blocks grows memory. Compact when history is trimmed.
• Offsets in the wrong unit. Bytes, UTF-16 code units and Unicode code points disagree for non-ASCII text. Pick one unit for piece offsets, convert at the API boundary, and never split a piece inside a multi-unit character or a CRLF pair, or line counts drift by one.
• The original file changes underneath. If the original buffer is memory-mapped rather than copied, another process rewriting the file corrupts the document. Copy on load, or detect modification and reload.
• Expensive full reads. Saving or searching walks every piece. Stream piece by piece to the output rather than building one giant string.

Comparison and trade-offs

Pick a gap buffer when edits are local and the code must be tiny. Pick a rope when you also need cheap concatenation and substring of large texts, as in collaborative or functional settings. Pick a piece table when large files, fast load and cheap undo dominate; move to the tree variant once documents can accumulate thousands of pieces. A doubly linked list of pieces is a middle step some editors use, making insertion O(1) once the position is found, with a cached cursor to make local edits fast.

What to do next

• Implement the list-based piece table above and fuzz it against a plain string, including undo back to the start.
• Add a line-start index: count line breaks per piece and answer offset-to-line queries.
• Measure piece counts after a find-and-replace-all on a large file, and add a compaction threshold.
• Replace the list with a balanced tree that caches left-subtree length and line-feed count; reuse your fuzz test.
• Store undo as inverse operations instead of whole snapshots and confirm memory stays flat over long sessions.
• Decide your offset unit (bytes, UTF-16 or code points) and add tests with emoji and CRLF line endings.