Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Piece tables: edit text through source spans

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A piece table stores text in two logical sources: the original document and an append-only addition buffer. The visible document is an ordered sequence of pieces, each naming a source, start offset, and length. Insertion finds a visible position, splits a piece if needed, appends the new fragment to the addition source, and inserts one descriptor. Deletion splits both boundaries and removes descriptors between them. Neither operation rewrites the original source. This Python model uses a list of pieces and a string for the addition source; those concrete choices matter for cost. An empty insertion changes nothing, and deleting an empty interval preserves the text.

Operational case

Start with Depot D-19 cleared. Insert north followed by a space after Depot, then delete the D-19 segment. Rendering the resulting pieces prints Depot north cleared, length 19, across three pieces. The original source still contains its old words; visibility comes only from descriptors. A delete can leave text in either source that no live piece references. Keeping history can help an undo design, but this example does not implement undo, snapshots, compaction, or file persistence. Its positions count Python string code points, not grapheme clusters seen by a user interface.

Working Python program

python
"""Text editor using immutable source buffers and a mutable piece sequence."""

from dataclasses import dataclass


@dataclass(frozen=True)
class Piece:
    source: int
    start: int
    length: int


class IncidentNote:
    def __init__(self, original: str):
        self.buffers = [original, ""]
        self.pieces = [Piece(0, 0, len(original))] if original else []
        self.length = len(original)

    def _split_at(self, position: int) -> int:
        if not 0 <= position <= self.length:
            raise IndexError(position)
        offset = 0
        for piece_index, piece in enumerate(self.pieces):
            next_offset = offset + piece.length
            if position == offset:
                return piece_index
            if offset < position < next_offset:
                left_length = position - offset
                self.pieces[piece_index:piece_index + 1] = [
                    Piece(piece.source, piece.start, left_length),
                    Piece(piece.source, piece.start + left_length, piece.length - left_length),
                ]
                return piece_index + 1
            offset = next_offset
        return len(self.pieces)

    def insert(self, position: int, text: str) -> None:
        piece_index = self._split_at(position)
        if not text:
            return
        start = len(self.buffers[1])
        self.buffers[1] += text
        self.pieces.insert(piece_index, Piece(1, start, len(text)))
        self.length += len(text)

    def delete(self, start: int, stop: int) -> None:
        if not 0 <= start <= stop <= self.length:
            raise IndexError((start, stop))
        first = self._split_at(start)
        last = self._split_at(stop)
        del self.pieces[first:last]
        self.length -= stop - start

    def text(self) -> str:
        return "".join(self.buffers[piece.source][piece.start:piece.start + piece.length]
                       for piece in self.pieces)


note = IncidentNote("Depot D-19 cleared")
note.insert(6, "north ")
note.delete(12, 17)
print(note.text())
print(note.length)
print(len(note.pieces))

Output

Output
Depot north cleared
19
3

Time, space, and tradeoff

Let P be the number of pieces, A the current addition-buffer length, F the inserted fragment length, and N the visible length. Finding each split point scans O(P) pieces; Python list insertion and deletion may shift O(P) descriptors. Python string concatenation copies the addition buffer and fragment, costing O(A + F) time and fresh temporary string space for an insertion here. Rendering slices and joins the visible pieces in O(N + P) time and O(N) output space. Retained source text and descriptors consume O(original length + A + P) space. A production editor can use chunked append storage and a balanced piece tree for better edit scaling, but this runnable model deliberately does not claim those bounds.

Common Mistakes

  • Do not mutate the original source when inserting or deleting visible text.
  • Do not treat a descriptor index as a character offset.
  • Do not promise logarithmic edits from a Python list of pieces.
  • Do not confuse code-point positions with user-perceived grapheme boundaries.

Connected lessons

Apply the invariant in the depot forest and notes project, then check the operations quiz.

Gap buffers: pay when the edit cursor crosses text adds a related sequence operation contract.

Ropes: share text chunks across immutable revisions adds a related sequence operation contract.

data structures
range-query-structures
Storage details