Designing Undo/Redo for a Text Editor

We’re designing an undo/redo mechanism for a single-user text editor with a linear edit history. Undo and redo must restore the document to exactly the previous logical state. It should support unlimited steps and behave the way developers expect from editors like VS Code or Notion.

To keep things focused, we’ll work within a small scope, It will be an in-memory document with sequential user actions and linear history. No collaboration (OT / CRDT) or persistence across restarts

The editor API is:

• insert(position, text)
• delete(position, length)
• replace(position, length, text)

At first glance, undo looks simple. Most initial designs fail once you push them slightly. It will make everything very complicated. Let’s look at some ideas

Full document snapshots

Store the entire document after each edit. This works functionally, but the trade-offs are bad:

• Memory usage grows with document size and edit count
• Undo latency increases for large documents
• Typing performance degrades over time
• It doesn’t scale beyond small documents.

Replay-only history

Store operations and recompute the document by replaying them. This introduces different problems:

• Undo time grows with history length
• Redo becomes fragile when operations depend on positions
• Earlier edits shift offsets, which can invalidate later operations
• It becomes hard to reason about and easy to break.

What must always be true

Before designing any data structures, it helps to state the rules that define correctness.

1. Undo followed by redo is identity - redo(undo(S)) == S
2. Redo history is cleared on new edits - Undo → new edit → redo must not be possible
3. Each user action is atomic - One intent maps to one undo step
4. Undo restores the exact previous document - Byte-for-byte equality
5. History order is preserved - The most recent edit is undone first

State model

Document

Holds the current text. The document is mutable and unaware of history.

Document
- content: str

Command

Represents a single user edit. A command applies a change to the document. It also stores enough information to undo that change. Each command owns the state required to reverse itself

Command
- apply(document)
- undo(document)

History

Tracks ordering and lifecycle. History does not understand edits. It only enforces ordering rules.

History
- undo_stack: List[Command]
- redo_stack: List[Command]

How state changes

New edit

• Apply the command
• Push it onto the undo stack
• Clear the redo stack

Before:
  undo = [A, B]
  redo = [C]

After:
  apply D
  undo = [A, B, D]
  redo = []

Undo

• Pop the undo stack
• Call undo
• Push the command onto the redo stack

Before:
  undo = [A, B, C]

After:
  undo C
  undo = [A, B]
  redo = [C]

Redo

• Pop the redo stack
• Call apply
• Push the command back onto the undo stack

Before:
  undo = [A, B]
  redo = [C]

After:
  apply C
  undo = [A, B, C]

Undo or redo on an empty stack is a no-op.

Edge cases

Replace is not primitive

Replace is logically a delete followed by an insert, but it must behave as a single undo step. This means replace is implemented as its own command that captures the replaced text during execution.

Design patterns

• Command pattern: each edit exposes apply and undo
• Memento (implicit): commands store prior state needed to undo, without snapshotting the entire document

Minimal class diagram

classDiagram
    class Document {
        content: str
    }

    class Command {
        <<abstract>>
        apply(doc: Document)
        undo(doc: Document)
    }

    class History {
        undo_stack: List~Command~
        redo_stack: List~Command~
        execute(cmd: Command, doc: Document)
        undo(doc: Document)
        redo(doc: Document)
    }

    History o-- Command : has
    Command ..> Document : uses

Implementation (Python)

The code below is a direct translation of the model above. There’s no extra abstraction.

from abc import ABC, abstractmethod


class Document:
    def __init__(self, content=""):
        self.content = content


class Command(ABC):
    @abstractmethod
    def apply(self, doc: Document):
        pass

    @abstractmethod
    def undo(self, doc: Document):
        pass


class Insert(Command):
    def __init__(self, pos: int, text: str):
        self.pos = pos
        self.text = text

    def apply(self, doc: Document):
        doc.content = (
            doc.content[:self.pos] +
            self.text +
            doc.content[self.pos:]
        )

    def undo(self, doc: Document):
        doc.content = (
            doc.content[:self.pos] +
            doc.content[self.pos + len(self.text):]
        )


class Delete(Command):
    def __init__(self, pos: int, length: int):
        self.pos = pos
        self.length = length
        self.deleted_text = ""

    def apply(self, doc: Document):
        self.deleted_text = doc.content[self.pos:self.pos + self.length]
        doc.content = (
            doc.content[:self.pos] +
            doc.content[self.pos + self.length:]
        )

    def undo(self, doc: Document):
        doc.content = (
            doc.content[:self.pos] +
            self.deleted_text +
            doc.content[self.pos:]
        )


class Replace(Command):
    def __init__(self, pos: int, length: int, text: str):
        self.pos = pos
        self.length = length
        self.text = text
        self.old_text = ""

    def apply(self, doc: Document):
        self.old_text = doc.content[self.pos:self.pos + self.length]
        doc.content = (
            doc.content[:self.pos] +
            self.text +
            doc.content[self.pos + self.length:]
        )

    def undo(self, doc: Document):
        doc.content = (
            doc.content[:self.pos] +
            self.old_text +
            doc.content[self.pos + len(self.text):]
        )


class History:
    def __init__(self):
        self.undo_stack = []
        self.redo_stack = []

    def execute(self, cmd: Command, doc: Document):
        cmd.apply(doc)
        self.undo_stack.append(cmd)
        self.redo_stack.clear()

    def undo(self, doc: Document):
        if not self.undo_stack:
            return
        cmd = self.undo_stack.pop()
        cmd.undo(doc)
        self.redo_stack.append(cmd)

    def redo(self, doc: Document):
        if not self.redo_stack:
            return
        cmd = self.redo_stack.pop()
        cmd.apply(doc)
        self.undo_stack.append(cmd)

Limits and extensions

This implementation is not efficient for very large documents. String slicing becomes expensive.

Real editors replace the underlying text structure with a rope or piece table. The undo/redo model stays the same.