Code a text editor with undo and redo

In one minute

• A text editor is a sequence of small, reversible edits applied to a buffer. Undo is not a feature bolted on at the end; it is the reason every edit is recorded as data (a position, the text removed and the text inserted) instead of being applied and forgotten.
• Keep the buffer and the history separate. The buffer (a gap buffer or a piece table) answers "what is the text?" cheaply. The history (command objects on an undo stack and a redo stack) answers "how do I get back?".
• Store deltas, not snapshots. A Memento that copies the whole document per keystroke costs O(document) memory per step; a command that stores the changed span costs O(edit). Snapshots still win in narrow cases, such as cheap immutable structures.
• Grouping decides what "one undo" means to a human. Coalesce typing by time and contiguity, break the group when the cursor jumps, and let callers wrap multi-step operations such as replace-all in an explicit group.
• The shape is multi-step consistency: a batch of changes must appear to happen, and be reversed, as one unit. The same design reappears in database savepoints, saga compensation and "revert this commit" in version control.

Requirements

Functional:

• Insert text at the cursor; delete with backspace; replace the current selection when one exists.
• Move the cursor and set a selection range.
• Undo and redo any number of steps. A new edit after an undo discards the redo history.
• Typing a word is one undo step, not one per character; a caller can also group several edits explicitly.
• Undo restores the text and puts the cursor or selection back where the user had it.

Non-functional:

• Typing at the cursor is amortised O(1) per character; undo and redo cost O(size of the edit), not O(size of the document).
• Deterministic: the grouping rule uses an injected clock, never the system time.
• Memory for history is bounded by the amount of text changed, and can be capped.

Out of scope: rich text and styles, multiple cursors, collaborative editing, persistence of the history across sessions, Unicode grapheme handling. Mention them, park them in Extensibility, and move on.

Entities and relationships

• Buffer holds the characters. It offers insert(pos, s), delete(pos, n) and slice(a, b) and knows nothing about undo. Two classic implementations are a gap buffer and a piece table.
• Editor is the receiver and façade. It owns the buffer, the cursor, an optional selection anchor, and the two stacks.
• Edit is the command: position, removed text, inserted text, the selection before, the cursor after and a timestamp. It has apply and revert.
• Step is one entry on a stack: a single edit or a group of edits that undo together. This is the Composite idea in its smallest form.
• Clock supplies time for the coalescing rule.

Relationships: the editor is composed of one buffer and two stacks; a step aggregates edits; an edit references no object other than the buffer it is applied to, which is what makes it replayable.

Class diagram

classDiagram
    class Editor {
      -buf: Buffer
      -cur: int
      -anchor: int
      -undoStack: Step[]
      -redoStack: Step[]
      +insert(s)
      +backspace()
      +move(pos)
      +select(a, b)
      +beginGroup()
      +endGroup()
      +undo() bool
      +redo() bool
    }
    class Buffer {
      <<interface>>
      +insert(pos, s)
      +delete(pos, n)
      +slice(a, b) string
      +text() string
    }
    class GapBuffer
    class PieceTable
    class Step {
      +edits: Edit[]
      +grouped: bool
    }
    class Edit {
      +pos: int
      +removed: string
      +inserted: string
      +selBefore: pair
      +cursorAfter: int
      +time: int
      +apply(buf)
      +revert(buf)
    }
    class Clock {
      <<interface>>
      +now() int
    }
    Buffer <|.. GapBuffer
    Buffer <|.. PieceTable
    Editor *-- Buffer
    Editor o-- Step
    Step o-- Edit
    Editor ..> Clock

Key flows

Typing three letters quickly, pausing, then undoing twice shows the coalescing rule and the stack movement.

sequenceDiagram
    participant U as User
    participant E as Editor
    participant B as Buffer
    participant S as UndoStack
    U->>E: insert "a" (t=0)
    E->>B: insert(0, "a")
    E->>S: push Edit("a")
    U->>E: insert "b" (t=400)
    E->>B: insert(1, "b")
    E->>S: merge into top: "ab"
    U->>E: insert "c" (t=5000)
    E->>B: insert(2, "c")
    E->>S: push new Edit("c")
    U->>E: undo
    E->>S: pop Edit("c")
    E->>B: delete(2, 1)
    E->>E: push to redo stack

Undo pops a step, reverts its edits in reverse order, restores the selection that existed before the step, and pushes the step on the redo stack. Redo does the mirror image. Any fresh edit empties the redo stack, because the future it described no longer follows from the present.

Design patterns used and why

• Command. Each edit is an object that knows how to apply and revert itself, which is the pattern's textbook use for undoable operations (Refactoring.Guru: Command). The history is just two lists of commands, and the editor never needs to know what kind of edit it is replaying.
• Memento. A memento saves a snapshot of an object's state so it can be restored later (Refactoring.Guru: Memento). We use it in miniature: each edit keeps the pre-edit selection, and the removed text is a snapshot of just the span that changed. Snapshotting the whole buffer would work but costs memory proportional to the document for every step.
• Composite. A step holds one edit or many, and undo treats both the same way. That is how explicit grouping and replace-all fit without a second code path.
• Strategy (or just an interface). The buffer sits behind a small interface so a gap buffer can be swapped for a piece table when files get large.
• Dependency injection. The clock is passed in. Without it, the coalescing rule cannot be tested.

Command versus Memento, decided. Command stores what changed and needs both directions of every edit. It is small and fast, but every new kind of mutation must supply a correct inverse. Memento stores what the state was and needs nothing from the mutation, but costs memory per step and is slow for large state. A good rule is to use commands when edits are small and well understood, and snapshots when the state is small, immutable or the inverse is hard to write. Some editors do both: commands for typing, a snapshot for rare "transform the whole file" actions.

Concurrency and edge cases

• Single-threaded by design. An editor receives events from one UI thread. Do not add locks to the buffer; instead, make long operations such as replace-all run on a snapshot or inside one group on that thread. If background features (a formatter, a linter) need to edit, they should submit edits through the same queue.
• Positions shift. An edit stores an absolute position, which is valid only against the exact text it was recorded on. That is why undo must pop in strict last-in first-out order, and why the redo stack must be cleared on any new edit. Apply an old edit to a changed text and the position points at the wrong characters.
• Merging must not lose information. Only merge pure insertions that are contiguous with the previous one (pos == prev.pos + len(prev.inserted)), inside the time window, with no cursor movement or undo between them. Deletions, replacements and newlines start a new step in this implementation.
• Selection replace. Typing over a selection is one edit with both removed and inserted text, so one undo brings the old text and the selection back together.
• Group left open. If a caller begins a group and forgets to end it, history stops growing. Use a try/finally or a scoped helper in real code, and refuse undo while a group is open as this implementation does.
• Unbounded history. Cap the stack by count or by total bytes of removed and inserted text, and drop the oldest steps. A single 50 MB paste is a step that costs 50 MB; budget by bytes, not entries.
• Out-of-range positions. Validate cursor and selection against the buffer length and fail loudly; a silent clamp hides bugs in the caller.

In the wild

• Visual Studio Code, 2018: replacing the line array with a piece table. The old text buffer kept an object per line at roughly 40 to 60 bytes each. A 35 MB file with 13.7 million lines needed about 600 MB and crashed the editor with out-of-memory errors. The team moved to a piece table whose nodes point into immutable original and added buffers, then stored the nodes in a balanced tree with cached line-break counts so line lookup stays logarithmic. The write-up also notes that a V8 string length limit forced a list of chunked buffers rather than one big string (VS Code blog).
• CKEditor 5, 2018: undo that works with collaboration. The authors list undo and redo among the features that had to be made collaboration-aware. Undo must be selective: a user may reverse only their own changes, even after other people have edited the same text, so a plain "pop the last operation" stack is not enough. They describe adding operation types and a graveyard for removed nodes to make this work (CKEditor blog).
• Google Docs, 2010: the document as a revision log. The rebuilt editor represents a document as a log of changes (insert text, delete text, apply style) that are replayed to display it, and concurrent changes are transformed against each other before they are applied (Google Drive blog). The same idea scales down to this lesson: if every edit is data with a clear inverse, history, replay and undo all come from one representation.

Down the stack

Extensibility

• Large files. Swap the buffer for a piece table behind the same interface. Edits and history do not change, because they only call insert, delete and slice.
• Undo tree. Keep the abandoned redo branch as a child node instead of discarding it, as Vim does. The stacks become a tree with a current pointer; undo moves to the parent, redo to a chosen child.
• Multiple cursors. An edit becomes a list of non-overlapping sub-edits applied together; the Composite step already reverts them as one.
• Collaboration. Local absolute positions are no longer valid after a remote edit. Transform them (operational transformation) or use identifiers instead of offsets, and make undo selective so that a user reverses only their own steps.
• Persisted history. Serialise the edits; because they are plain data, saving and loading is a few lines.
• Memory cap. Evict the oldest steps once the total bytes in history pass a budget, and mark the document as having lost deep undo.

Leadership lens

• Decide the user-visible rule for "one undo" before coding, and write it down. Time windows, newline breaks and word boundaries are product decisions; engineers should not discover them by accident.
• Ask in review: what is the inverse of every new mutation? If a feature changes state outside the buffer (formatting, metadata), it must produce an edit or its changes will survive an undo and corrupt the document.
• Plan the data-structure upgrade path. A gap buffer is fine for files up to tens of megabytes; set a size threshold and a test with a file at 10 times that size before users find it.
• Own the test strategy: a property test that applies a random sequence of edits, then undoes all of them, and checks the text equals the original catches most history bugs in one go.
• Cost is mostly memory and correctness, not CPU. Budget history in bytes, expose it in diagnostics, and decide who is on call for "my document lost my changes" reports.

Check yourself

1. Why must the redo stack be cleared when the user makes a new edit after an undo?

   Show answer

   Each edit stores absolute positions that are valid only for the text it was recorded against. After a new edit the text differs, so replaying the old redo steps would modify the wrong characters.

2. When would you pick snapshots (Memento) over commands for undo?

   Show answer

   When state is small or immutable so copying is cheap, or when writing a correct inverse for a mutation is hard. For large documents with small edits, commands that store only the changed span use far less memory.

3. A user types "hello", clicks elsewhere in the text, and types "x". How many undo steps exist, and why?

   Show answer

   Two. Moving the cursor seals the first group, and the next insertion is not contiguous with the previous one, so it starts a new step.

4. A gap buffer holds a 100 MB file and the user jumps from the start to the end. What does it cost, and how would you reduce it?

   Show answer

   The gap must slide across the whole file, a copy of about 100 MB, around ten milliseconds or more. A piece table avoids the copy because it changes only its piece list; so would a rope or a tree of chunks.

Watch

• Command Pattern, Design Patterns ep 7 (Christopher Okhravi): invoker, receiver and command, including undo.
• Memento Design Pattern (Derek Banas): originator, memento and caretaker roles built step by step.

Sources and further study

Primary

• Text Buffer Reimplementation (VS Code blog): why a line array failed on large files and how a piece table with a balanced tree replaced it.
• Lessons learned from creating a rich text editor with real-time collaboration (CKEditor): selective undo and the operation set needed for a tree model.
• What's different about the new Google Docs (Google Drive blog): the document as a replayable log of changes.

Systems docs

• Vim documentation: undo.txt: undo blocks, :undojoin and undo branches in a production editor.
• Gap buffer (Wikipedia): the structure, its costs and where it is used.
• Piece table (Wikipedia): original and added buffers plus a piece list.
• Event Sourcing (Martin Fowler): state as a log of events, the same idea as an edit history.

Books

• Design Patterns: Elements of Reusable Object-Oriented Software, Gamma, Helm, Johnson and Vlissides: chapter 2 "A Case Study: Designing a Document Editor", then the Command and Memento entries in chapter 5.
• Head First Design Patterns, Freeman and Robson: the Command chapter, which builds an undoable remote control.

Other curricula

• Refactoring.Guru: Command: presents undo as a stack of command objects with saved backups of state.

Free resources

• Memento (Refactoring.Guru): the three roles and how snapshots are kept opaque.
• Implementing Undo History (Redux docs): past, present and future arrays, the snapshot approach with immutable state.
• Operational transformation (Wikipedia): how concurrent edits are reconciled, the next step beyond this lesson.
• Rope (data structure) (Wikipedia)): another tree-based alternative for very large text.