9.7.12 — Text Editor: The Buffer and Undo

"Design a text editor. It needs insert, delete, and unlimited undo and redo."

Two decisions carry this whole problem, and both are usually made badly.

The first is how the text is stored, which decides whether editing a large file is instant or unusable. The second is how undo is represented, which decides whether "unlimited undo" costs kilobytes or gigabytes. Get both right and everything else is small.

1. The questions to ask first

How large can a document be? A chat message is not a two-hundred-megabyte log file. The buffer choice below only matters at size, and asking tells the interviewer you know that.

What is one undo step, from the user's point of view? This is the question nobody asks and everybody gets wrong. Typing "hello" is five insertions and exactly one undo. Getting this right is section 5.

Is it collaborative? If two people edit at once, this becomes a completely different problem and belongs in 11.13. Confirm it is out of scope, or you will design the wrong thing.

What else can edit the document? Find-and-replace, auto-formatting, a spell-check fix. Each must go through the same path as typing, or undo will not cover it.

State the contract: "I will design the buffer for large documents, insert and delete, and undo and redo with sensible grouping. Collaboration is out of scope. Find-and-replace goes through the same command path so it is undoable."

2. The buffer: how the text is stored

A single string is the obvious choice and it is quadratic. Inserting one character in the middle of a two-hundred-megabyte document copies two hundred megabytes. Type a sentence and you have copied several gigabytes. It is fine up to a few thousand characters and unusable beyond.

There are three real answers, and knowing why each exists is the point.

A gap buffer. Keep the text in one array with a gap of free space at the cursor. Typing writes into the gap, which is O(1). Moving the cursor moves the gap, which costs the distance moved. This is what a classic editor uses, and it is beautifully matched to how people actually edit — you type many characters in one place, then move.

Its weakness is exactly its assumption: an operation that jumps around the document constantly, like a find-and-replace across a large file, moves the gap on every edit and becomes O(n) each time.

A rope. A balanced tree whose leaves hold pieces of text. Insert and delete are O(log n) anywhere, and concatenating two large documents is O(log n) rather than a copy. The cost is that reading a range means walking the tree, and the implementation is genuinely fiddly.

A piece table, which is what most modern editors actually use, and which is worth understanding properly because it makes undo almost free.

Figure 1 — A piece table stores no text, only where to find it. Both buffers are append-only, so every version of the document that ever existed is still readable; only the piece list changed.

interface Piece {
  readonly buffer: "original" | "add";       // (1) which buffer this text lives in
  readonly start: number;
  readonly length: number;
}

class PieceTable {
  #original: string;                          // (2) never modified
  #add = "";                                  // (3) only ever appended
  #pieces: Piece[] = [];

  insert(at: number, text: string): void {
    const addStart = this.#add.length;
    this.#add += text;                        // (4) O(text length), never O(document)
    const { index, offset } = this.#locate(at);
    const newPiece: Piece = { buffer: "add", start: addStart, length: text.length };
    this.#pieces = splitAndInsert(this.#pieces, index, offset, newPiece);   // (5)
  }

  delete(at: number, length: number): void {
    this.#pieces = removeRange(this.#pieces, at, length);   // (6) no text deleted anywhere
  }
}

(1) A piece says where the text is, never what it is.

(2) and (3) Both buffers are immutable or append-only. Nothing is ever overwritten.

(4) Typing appends to the add buffer, which is cheap regardless of document size.

(5) The edit is a change to the piece list: split the piece the cursor is inside, and insert one. Three list entries changed, no text moved.

(6) Deletion removes or trims pieces. The characters remain in the buffers, unreferenced.

Three properties fall out, and the third is why this page pairs the buffer with undo.

Insert and delete cost nothing proportional to document size.

Loading is instant — the original buffer can even be memory-mapped, so a huge file opens without reading it all.

Every past version is still expressible, because no text was ever destroyed. Undo becomes "restore the previous piece list", which is a small array rather than a copy of the document.

The trade to state: an index lookup means walking the piece list to find which piece covers position n, which is O(pieces). After thousands of scattered edits the list grows, so real implementations keep the pieces in a balanced tree keyed by cumulative length, making lookup O(log pieces).

Buffer	Insert at cursor	Insert anywhere	Random read	Good for
String	O(n)	O(n)	O(1)	Small documents
Gap buffer	O(1)	O(distance)	O(1)	Typing in one place
Rope	O(log n)	O(log n)	O(log n)	Huge documents, big splices
Piece table	O(pieces)	O(pieces)	O(pieces)	Large files, cheap undo

3. Undo: the two representations

The memento approach stores a copy of the document before each change. Undo is restoring a copy. It is trivially correct and it costs the document size per undo step, so "unlimited undo" on a large file is unusable.

The command approach stores what changed, along with enough information to reverse it. Undo runs the reverse. Memory is proportional to the size of the edits rather than the size of the document, which is smaller by orders of magnitude.

interface EditCommand {
  apply(doc: Document): void;
  invert(): EditCommand;                       // (1) returns the command that undoes this one
  readonly selectionBefore: Selection;         // (2)
  readonly selectionAfter: Selection;
}

class InsertText implements EditCommand {
  constructor(
    readonly at: number,
    readonly text: string,
    readonly selectionBefore: Selection,
    readonly selectionAfter: Selection,
  ) {}

  apply(doc: Document): void { doc.buffer.insert(this.at, this.text); }

  invert(): EditCommand {
    return new DeleteText(this.at, this.text, this.selectionAfter, this.selectionBefore);  // (3)
  }
}

class DeleteText implements EditCommand {
  constructor(
    readonly at: number,
    readonly removed: string,                  // (4) the deleted text is kept
    readonly selectionBefore: Selection,
    readonly selectionAfter: Selection,
  ) {}

  apply(doc: Document): void { doc.buffer.delete(this.at, this.removed.length); }
  invert(): EditCommand {
    return new InsertText(this.at, this.removed, this.selectionAfter, this.selectionBefore);
  }
}

(1) Each command knows its own inverse, so the undo stack holds edits rather than special-cased reversal logic. This is the Command pattern (9.4.15).

(2) The selection before and after. Section 6 is about why this is not optional.

(3) Inverting swaps the selections too, so undoing an insert restores the cursor to where it was before the insert.

(4) A delete command must store the text it removed, or it cannot be undone. This is the one place where memory is unavoidable, and it is proportional to what was deleted rather than to the document.

With a piece table you get a third option that is better than both. Since no text is ever destroyed, an undo step can be just the previous piece list — an array of small records. It is memento-shaped, so it is trivially correct, and it is command-sized, because a piece list is tiny compared with the document. This is the real reason modern editors use piece tables, and saying it connects the two halves of this page.

4. The two stacks

class History {
  #undo: EditCommand[] = [];
  #redo: EditCommand[] = [];

  record(cmd: EditCommand): void {
    this.#undo.push(cmd);
    this.#redo.length = 0;                     // (1) a new edit invalidates the redo branch
  }

  undo(doc: Document): void {
    const cmd = this.#undo.pop();
    if (!cmd) return;                          // (2) nothing to undo is normal, not an error
    const inverse = cmd.invert();
    inverse.apply(doc);
    doc.selection = cmd.selectionBefore;       // (3)
    this.#redo.push(cmd);
  }

  redo(doc: Document): void {
    const cmd = this.#redo.pop();
    if (!cmd) return;
    cmd.apply(doc);
    doc.selection = cmd.selectionAfter;
    this.#undo.push(cmd);
  }
}

(1) The rule people forget. After undoing three times and then typing something new, the three redo steps are gone — they belonged to a future that no longer exists. Keeping them would let a user redo into a document state that never followed from the current one.

(2) Empty stacks are ordinary. Undo at the start of a session does nothing.

(3) Restoring the selection is part of undo, not decoration. Section 6.

Bounding the history. "Unlimited undo" is a lie in a memory-limited process. Cap it by total bytes rather than by step count, because one step can be a hundred-megabyte paste while another is a single character. Drop from the oldest end.

5. Grouping: what counts as one undo

Typing "hello" generates five insert commands. Pressing undo once must remove all five, not one letter. A user who has to press undo five times to delete a word considers the editor broken.

The rule is to merge a new command into the previous one when all of these hold:

• it is the same kind of operation, insert with insert or delete with delete;
• it is contiguous — the new insert starts exactly where the previous one ended;
• it happened within a short time of the previous one, typically under a second;
• nothing broke the run in between.

And the events that must break a run, because these are what people miss:

• moving the cursor, including by clicking — typing "hel", clicking elsewhere, then typing "lo" must be two undo steps;
• saving the file, so undo can take you back to exactly the saved state;
• typing a word boundary, which many editors use so undo removes one word at a time;
• any non-typing command such as find-and-replace or a formatting action.

function shouldMerge(prev: EditCommand, next: EditCommand, now: Instant): boolean {
  return prev instanceof InsertText
      && next instanceof InsertText
      && next.at === prev.at + prev.text.length            // (1) contiguous
      && now.minus(prev.at) < Duration.millis(700)          // (2) recent
      && !next.text.includes("\n");                         // (3) a newline ends the group
}

(1) Contiguity is what makes it one logical action. (2) The time window keeps a pause from merging two separate thoughts into one undo. (3) A newline is a natural boundary and matches user expectation.

Find-and-replace is the reverse case: replacing forty occurrences is forty edits and must be one undo step. So grouping works in both directions — merging many small commands into one, and wrapping many deliberate commands into one composite:

class CompositeEdit implements EditCommand {
  constructor(private readonly parts: EditCommand[], ...) {}
  apply(doc: Document): void { for (const p of this.parts) p.apply(doc); }
  invert(): EditCommand {
    return new CompositeEdit([...this.parts].reverse().map(p => p.invert()), ...);   // (1)
  }
}

(1) Reversing the order matters. Undoing three edits means undoing the last one first, because each edit's positions were computed against the document as it stood after the previous one.

6. The detail that separates answers: restoring the selection

Undo must restore where the cursor was, not just what the text was.

Consider: the user selects a paragraph, presses delete, then presses undo. If undo restores the text and leaves the cursor at the start of the document, the user has to find their place again. If it restores the text and the selection, they are exactly where they were and can carry on.

This is why every command carries selectionBefore and selectionAfter, and why inverting swaps them. It costs two small fields per command and it is the single most noticeable quality difference between a good editor and a bad one.

The related detail: after an undo, the document should be scrolled so the restored text is visible. An undo that changes text off-screen looks to the user like nothing happened, and they will press it again — undoing something they wanted to keep.

7. Where this connects

Every mutation goes through a command. Typing, pasting, find-and-replace, auto-formatting, a spell-check fix, a plugin's edit. If any path writes to the buffer directly, that change is invisible to undo, and the user will find it — usually by losing work. This is the same rule as 9.7.10's ledger: one door in, and everything that changes state goes through it.

Save state is a marker in the history, not a flag. Record which history position was last saved, and the document is modified exactly when the current position differs from it. Then undoing back to the saved point correctly reports the document as unmodified — a flag cannot do that, and a flag is why some editors ask you to save a file you have already undone back to its original state.

Collaboration is a different problem. Two people editing simultaneously means positions computed against different versions of the document, and reconciling them needs operational transformation or a conflict-free replicated type (11.13). Naming it as out of scope and knowing why it is hard — position 40 means different things to two clients — is the right answer here.

8. What the interviewer will push on

"How do you store the text?" They want to hear that a single string makes every insert O(n), and then a real alternative with its trade. Gap buffer for typing in one place, rope for huge documents and big splices, piece table for large files plus cheap undo. Name the piece table's cost too: locating a position walks the piece list, so real implementations index the pieces in a balanced tree.

"How much memory does unlimited undo take?" The question separating memento from command. Storing document copies costs the document size per step; storing commands costs the size of each edit. Then the observation that ties the page together: with a piece table, an undo step can be the previous piece list, which is memento-simple and command-small at the same time.

"The user types 'hello'. How many undo steps?" One. Then the merge rule — same operation, contiguous, within a short time window — and, more importantly, the events that must break a run: cursor movement, saving, a word boundary, and any non-typing command. Candidates who only describe merging usually forget that clicking elsewhere ends the group.

"The user undoes three times and then types. What happens to redo?" The redo stack is cleared. Those steps belonged to a future that no longer exists, and keeping them would let a user redo into a state that does not follow from the current document.

"Find-and-replace changes forty occurrences. How many undos?" One, via a composite command — and inverting it applies the parts in reverse order, because each edit's positions were computed against the document as it stood after the previous one.

"What does undo restore besides the text?" The selection. This is the detail most candidates miss and every user notices. Each command carries the selection before and after, inverting swaps them, and the view scrolls to make the restored region visible.

The thing to volunteer that nobody asks for: track the saved position as a marker in the history, not as a dirty flag. Then undoing back to the last save correctly reports the document as unmodified, and the editor stops asking people to save a file they have already returned to its original state. It is three lines and it removes a small daily annoyance that most editors still have.

Next: 9.7.13 — four prompts that turn out to be one problem, and the two questions that tell them apart.

Recall

• A single string makes every insert O(n) — typing a sentence into a large document copies gigabytes. Real answers: gap buffer (O(1) at the cursor, O(distance) to move it), rope (O(log n) anywhere), piece table (append-only buffers plus a list of pieces).
• A piece table stores no text, only where to find it. Both buffers are append-only, so every past version is still expressible — which makes an undo step the previous piece list, small and trivially correct.
• Memento stores document copies (document-sized per step). Command stores the edit plus its inverse (edit-sized). A delete command must keep the removed text.
• A new edit clears the redo stack — those steps belonged to a future that no longer exists.
• Grouping: merge when the operation is the same, contiguous, and recent. Break the run on cursor movement, save, word boundary, or any non-typing command.
• Find-and-replace is one composite command, and inverting it applies the parts in reverse order.
• Undo restores the selection, not just the text, and scrolls it into view. Two fields per command, and the most noticeable quality difference there is.
• Every mutation goes through a command, or it is invisible to undo. Track the saved position as a history marker, not a dirty flag.
• Bound the history by bytes, not by step count — one step can be a huge paste.

Self-test: Why is a string the wrong buffer, and what does a piece table cost instead? Why does a piece table make undo cheap? What must break an undo group? What happens to redo after a new edit? Why must a composite invert in reverse order? What else does undo restore?

Quiz Bank

FoundationalCompare the buffer representations and say which you would pick and why.

A single string is what everyone writes first. Strings are immutable in most languages, so inserting one character in the middle allocates a new string and copies the whole thing. Typing a sentence into a two-hundred-megabyte document copies gigabytes. It is correct, it is simple, and it is unusable above a few thousand characters.

A gap buffer keeps the text in one array with a region of free space sitting at the cursor. Typing writes into the gap at O(1). Moving the cursor moves the gap, costing the distance moved.

Its virtue is that it matches how people edit — many characters typed in one place, then a jump. Its weakness is the same assumption inverted: an operation that edits all over the document, such as find-and-replace across a large file, moves the gap on every edit and becomes O(n) each time.

A rope is a balanced tree whose leaves hold text fragments. Insert and delete anywhere are O(log n), and splicing two large documents together is O(log n) rather than a full copy. The cost is that reading a character range means walking the tree, and the implementation — keeping the tree balanced across arbitrary edits — is genuinely intricate.

A piece table keeps two buffers: the original file, loaded once and never modified, and an add buffer that is only ever appended to. The document is a list of pieces, each saying which buffer, where it starts, and how long it is. Editing changes the list, never the text.

I would pick the piece table for a general editor, for three reasons.

Editing cost is independent of document size. Typing appends to the add buffer and splits one piece.

Loading is instant, because the original buffer can be read lazily or memory-mapped rather than parsed up front.

Undo becomes almost free, and this is the decisive one. Since no text is ever destroyed, a previous version of the document is fully described by a previous piece list — a small array of records rather than a copy of the content. That gives you the simplicity of storing snapshots with the memory cost of storing edits.

And its cost, stated so the answer is not one-sided: finding which piece covers character position n walks the list, so after thousands of scattered edits lookups degrade. Real implementations hold the pieces in a balanced tree keyed by cumulative length, making it O(log pieces) — which is the same fix ropes use, applied to a coarser unit.

The choice would change for a small-document editor, where a plain string is right and simpler, and for an editor whose main job is enormous single-place edits, where a rope's splice performance dominates.

AppliedImplement undo and redo, and explain the three rules that make it feel correct to a user.

The structure is two stacks and a command that knows its own inverse.

Each edit is a command carrying enough to reverse itself. An insert knows its position and text; its inverse is a delete of that range. A delete knows its position and — crucially — the text it removed; its inverse is an insert of that text. Storing the removed text is the one unavoidable memory cost, and it is proportional to what was deleted rather than to the document.

Undo pops from the undo stack, applies the inverse, and pushes the original onto the redo stack. Redo does the reverse. Empty stacks are an ordinary no-op, not an error.

Rule one: a new edit clears the redo stack. The user undoes three times, then types something. Those three redo steps described a future that no longer exists — redoing into them would produce a document state that does not follow from the current one. Clearing is the only coherent behaviour, and forgetting it produces corruption that is very hard to reason about after the fact.

Rule two: undo restores the selection, not just the text. Each command records where the selection was before it and after it, and inverting swaps the two. Undoing a paragraph deletion should put the text back and re-select it, so the user is exactly where they were. Without this, every undo forces the user to find their place again, and it is the single most noticeable difference between an editor that feels good and one that does not. The view should also scroll the restored region into view — an undo whose effect is off-screen looks like nothing happened, so the user presses it again and loses something they wanted.

Rule three: grouping matches user intent, not implementation events. Typing "hello" is five insert commands and exactly one undo. Merge a new command into the previous one when it is the same kind of operation, contiguous with it, and within a short time window — around 700 milliseconds.

Equally important is what must break a group: moving the cursor (including by clicking), saving the file, a word boundary in some editors, and any non-typing command such as find-and-replace. Typing "hel", clicking somewhere else, and typing "lo" must be two undo steps, and candidates who describe only the merging half usually miss this.

Grouping runs the other way too. Find-and-replace across forty occurrences is one undo step, expressed as a composite command holding the forty parts. Inverting it applies the inverted parts in reverse order, because each edit's positions were computed against the document as it stood after the previous one — reversing them in forward order corrupts the positions.

And one bound worth adding: cap the history by total bytes rather than step count, since a single step can be a hundred-megabyte paste while another is one character, and drop from the oldest end.

InterviewWhy does a piece table make undo cheap, and what does that tell you about the relationship between the two design decisions?

Because a piece table never destroys anything. The original buffer is immutable and the add buffer is append-only, so every character that has ever been part of the document is still sitting in one of them. Editing only changes the piece list — the ordered set of references describing which spans, from which buffer, in what order, make up the current document.

That means a past version of the document is completely described by a past piece list. Not a copy of the text: a small array of records, each holding a buffer name, a start and a length. A document of two hundred megabytes with a few hundred edits has a piece list of a few hundred entries, measured in kilobytes.

So undo becomes: replace the piece list with the previous one. That is memento-shaped — you store a whole state, so it is trivially correct with no inverse logic to get wrong — while costing what a command-based approach costs, because the state you store is tiny.

What this tells you is the general point of the question: the buffer choice and the undo choice are not independent decisions that happen to sit on the same page. The data structure determines what undo costs.

With a mutable string, the text is destroyed as you edit, so an undo step must either carry a copy of the document (memento, document-sized) or carry an inverse operation (command, correct but requiring careful inverse logic for every operation type).

With a piece table, history is inherent in the representation. You are not building an undo system on top of a data structure; you are reading a property the data structure already has.

Two further consequences worth naming.

Redo is symmetric and free, because a redo step is just the piece list you moved away from.

The same property is what makes snapshots and versioning cheap. Keeping the piece lists from every save gives you a document history at almost no cost, which is why editors built this way tend to grow features like "revert to this morning" without a redesign. It is the same insight as copy-on-write in 9.7.11: when nothing is ever overwritten, old versions cost only the references that describe them.

And the honest caveat: the buffers grow forever, including text the user deleted long ago. A long editing session accumulates add-buffer content that is no longer referenced by any live piece list. Real implementations compact on save — writing out the current document as a fresh original buffer and resetting the piece list — which discards the history in exchange for reclaiming the memory, and is a decision to make explicitly rather than by accident.

StaffA plugin system lets third parties modify the document. Design it so undo still works and the editor stays responsive.

The core rule is that there is exactly one way to change the document, and plugins use it. Nothing gets direct access to the buffer. A plugin proposes edits as commands, the editor applies them through the same path as typing, and they land on the history like everything else. The moment one code path can write to the buffer directly, that change becomes invisible to undo, and the user loses work in a way they cannot explain.

Give plugins a transaction, not a mutation API.

editor.edit(tx => {
  tx.replace(range, "new text");     // recorded, not applied yet
  tx.insert(at, "more");
});

Everything inside one edit call becomes a single composite command, so a plugin that changes forty places is one undo step. It also means the plugin cannot leave the document half-modified: if it throws partway through, nothing is applied at all. And because positions inside the transaction are resolved against the document as it was at the start, the plugin does not have to track how its own earlier edits shifted later positions — which is the single most common source of plugin bugs.

Responsiveness needs the work off the main path. A plugin doing something expensive — reformatting, analysing, calling a service — must not block typing. So the pattern is: the plugin computes on a copy or on a snapshot, and returns a set of edits; the editor applies them on the main thread, which is fast because applying is just piece-list manipulation.

That creates the interesting problem: the document may have changed while the plugin was thinking. A plugin given a snapshot at version 12 returns edits for positions that were valid then, and the document is now at version 15 because the user kept typing. Applying those positions blindly corrupts the text.

Three options, and the choice is a product decision rather than a technical one.

Reject and retry. Tag each returned edit set with the version it was computed against, and if the document has moved on, discard it and ask the plugin to run again. Simple, always correct, and it can starve on a fast typist — the plugin never finishes before the document changes again.

Rebase the edits. Translate the plugin's positions through the edits that happened in the meantime, which is exactly the transformation machinery from collaborative editing (11.13). Powerful, and a large amount of work to get right.

Anchor to content rather than to offsets. Have the plugin return edits expressed against markers that the editor maintains and moves as the document changes, rather than against raw character positions. This is what most real editors do, and it handles the common cases — a marker whose surrounding text was deleted simply becomes invalid and that edit is dropped.

I would start with reject-and-retry because it is correct and cheap, measure how often it starves, and move to anchors for the plugins where it does.

Two safeguards worth designing in from the start.

Bound what a plugin may do. A time limit on producing edits and a cap on their total size, so a badly written plugin degrades into "that plugin did not run" rather than freezing the editor or exhausting memory.

Make plugin edits attributable. Record which plugin produced each command, so the undo entry can say "undo auto-format" rather than "undo", and so a plugin that keeps making unwanted changes can be identified from the history rather than by guesswork. This costs one field and it is the difference between a support burden and a support answer.

Flashcards

FlashBuffer choices

String: O(n) per insert, small documents only. Gap buffer: O(1) at the cursor, O(distance) to move. Rope: O(log n) anywhere. Piece table: append-only buffers plus a piece list, and cheap undo.

FlashWhy a piece table makes undo cheap

Nothing is ever destroyed, so a past version is fully described by a past piece list — kilobytes, not the document. Memento-simple at command-sized cost.

FlashUndo grouping

Merge when same operation, contiguous, and recent. Break on cursor movement, save, word boundary, or any non-typing command. Find-and-replace is one composite, inverted in reverse order.

FlashA new edit clears redo

Those steps described a future that no longer exists. Keeping them lets a user redo into a state that does not follow from the current document.

FlashUndo restores the selection

Each command carries selection before and after; inverting swaps them. Also scroll the restored region into view, or the user thinks nothing happened and presses undo again.

FlashSaved state

A marker at a history position, not a dirty flag. Undoing back to the marker correctly reports the document as unmodified.