Type "Hello world", press Ctrl+Z, and the word "world" disappears, not the letter "d" and not the whole line. That one keystroke is the design: edits as commands, two stacks, and a rule for which keystrokes belong together.
"Design a text editor with undo" is the standard machine-coding prompt for the Command pattern, and nearly every candidate knows the pattern's name. The marks are in what comes after. Does a new edit clear redo? Does undo restore the cursor? Is typing over a selection one step or two? Does undoing a sentence take forty presses? And when asked "why not save a copy before each edit?", can you put a number on why not?
This lesson builds a small editor core: a document, a cursor and selection, insert and delete commands that carry their own inverse, a compound command, coalescing, and a memento for comparison.
How the round runs#
"Build the core of a text editor: a cursor, typing, backspace, selecting text and typing over it, and unlimited undo and redo. Well, not unlimited: keep the last 100 steps. Undo should feel like a real editor's. No rendering, no files. 90 minutes, working code."
- 0–10 min — clarify: what one undo step is, cursor after undo, redo after a new edit, history limit, selection behaviour
- 10–25 min — the document, the cursor, and the command interface:
do,undo,absorb - 25–45 min —
Insert,DeleteandCompound, each exactly reversible - 45–60 min — the editor: two stacks, the history limit, sealing groups
- 60–75 min — coalescing rules, then a demo that types, undoes, redoes and replaces a selection
- 75–90 min — the memento comparison and the follow-ups: big documents, collaboration
Requirements and clarifying questions#
| You ask | They answer | What it changes |
|---|---|---|
| What does one undo remove? | Roughly a word of typing, or a burst of backspaces. | Commands coalesce into groups |
| When does a group end? | A pause, a cursor move, a new word, or an undo. | A time gap, a "sealed" flag, a word-boundary rule |
| Typing over a selection? | One undo step brings the old text back. | A Compound of a delete and an insert |
| Undo, then type something new? | The redo history is gone, as in every editor. | A new edit clears the redo stack |
| Where's the cursor after undo? | Where the edit happened. | Each command returns the cursor position |
| How much history? | The last 100 steps. | A deque(maxlen=100) |
| Paste? | Its own step, never merged with typing. | Only single keystrokes coalesce |
Snapshots or commands?
One way to get undo is to save a copy of the whole document before every edit, and restore the copy on undo. Another is to record each edit and how to reverse it. For a 50,000-character document and 100 steps of history, roughly how much does each keep?
One strong answer
Snapshots keep 100 copies of the document: about 5 million characters, even if every edit was one keystroke. Commands keep only what changed: about 100 characters plus a few integers per step. Snapshots (the Memento pattern) are simpler and can't get an inverse wrong, so they're right for small state or rare checkpoints, such as autosave. For keystroke-level undo on real documents, the Command pattern with an exact inverse wins by orders of magnitude. The demo below measures both.
The classes#
%% title: Text editor: the classes
classDiagram
class Document {
+text str
+insert(pos, s)
+delete(pos, n) str
}
class Command {
<<abstract>>
+do(doc) int
+undo(doc) int
+absorb(next) bool
}
class Insert {
+pos int
+text str
+at float
+keystroke bool
}
class Delete {
+pos int
+text str
+at float
+keystroke bool
}
class Compound {
+parts tuple
}
class Snapshot {
+text str
+cursor int
}
class Editor {
+cursor int
+anchor int
-undo_stack deque
-redo_stack list
+type(text, now)
+backspace(now)
+move(pos, select)
+select(start, end)
+undo() bool
+redo() bool
+save() Snapshot
+restore(snapshot)
}
Command <|-- Insert
Command <|-- Delete
Command <|-- Compound
Compound "1" o-- "many" Command
Editor --> Document
Editor "1" o-- "many" Command
Editor ..> SnapshotThree roles, kept apart. The Document only stores text and knows nothing about history. The commands know how to apply and exactly reverse one edit, and whether they can swallow the next one. The Editor owns the cursor, the selection and the two stacks, and is the only thing the UI calls. The selection is two numbers: the cursor and an anchor, the end where the selection started.
The interfaces#
Every command answers three questions: how to apply it, how to reverse it, and whether the next edit belongs to the same undo step. do and undo return the cursor position, so undo puts the cursor back where the edit was:
# editor.py, part 1: the document, and edits as commands
from __future__ import annotations
import threading
from abc import ABC, abstractmethod
from collections import deque
from dataclasses import dataclass
GROUP_GAP_S = 1.0 # a pause longer than this ends an undo group
class Document:
"""Just the text. A str is fine for the round; real editors use a gap buffer, piece table or rope."""
def __init__(self, text: str = "") -> None:
self.text = text
def insert(self, pos: int, s: str) -> None:
self.text = self.text[:pos] + s + self.text[pos:]
def delete(self, pos: int, n: int) -> str:
gone = self.text[pos : pos + n]
self.text = self.text[:pos] + self.text[pos + n :]
return gone
class Command(ABC):
@abstractmethod
def do(self, doc: Document) -> int: ... # apply the edit; return where the cursor goes
@abstractmethod
def undo(self, doc: Document) -> int: ... # exactly reverse it; return where the cursor goes
def absorb(self, nxt: Command) -> bool: # coalescing: may this group swallow the next edit?
return False
@dataclass
class Insert(Command):
pos: int
text: str
at: float # time of the latest keystroke in the group
keystroke: bool = True # False for a paste: a paste is always its own undo step
def do(self, doc: Document) -> int:
doc.insert(self.pos, self.text)
return self.pos + len(self.text)
def undo(self, doc: Document) -> int:
doc.delete(self.pos, len(self.text))
return self.pos
def absorb(self, nxt: Command) -> bool:
if not (isinstance(nxt, Insert) and self.keystroke and nxt.keystroke):
return False
new_word = self.text[-1].isspace() and not nxt.text.isspace()
if nxt.pos != self.pos + len(self.text) or nxt.at - self.at > GROUP_GAP_S or new_word:
return False
self.text, self.at = self.text + nxt.text, nxt.at
return True
@dataclass
class Delete(Command):
pos: int
text: str # what was removed: the command carries what it needs to undo itself
at: float
keystroke: bool = True # False when a whole selection was deleted
def do(self, doc: Document) -> int:
doc.delete(self.pos, len(self.text))
return self.pos
def undo(self, doc: Document) -> int:
doc.insert(self.pos, self.text)
return self.pos + len(self.text)
def absorb(self, nxt: Command) -> bool: # backspace, backspace, backspace -> one group
if not (isinstance(nxt, Delete) and self.keystroke and nxt.keystroke):
return False
if nxt.pos + len(nxt.text) != self.pos or nxt.at - self.at > GROUP_GAP_S:
return False
self.pos, self.text, self.at = nxt.pos, nxt.text + self.text, nxt.at
return True
class Compound(Command):
"""Several commands as one undo step: typing over a selection is a delete then an insert."""
def __init__(self, *parts: Command) -> None:
self.parts = parts
def do(self, doc: Document) -> int:
return [p.do(doc) for p in self.parts][-1]
def undo(self, doc: Document) -> int:
return [p.undo(doc) for p in reversed(self.parts)][-1]
@dataclass(frozen=True)
class Snapshot: # the memento: the whole state, opaque to everyone but the editor
text: str
cursor: intThat is the whole trick of the Command pattern for undo: a command carries exactly what it needs to reverse itself. An insert needs its position and text; a delete needs the text it took away, because once it's gone, nothing else remembers it.
Grouping: when keystrokes become one step#
Without grouping, typing a 40-character sentence leaves 40 undo steps. With it, consecutive keystrokes merge into the command on top of the stack, until something ends the group:
- Not adjacent: the new character isn't right after the group's last one (the cursor moved).
- A pause: more than 1 second since the group's last keystroke.
- A new word: the group ends in whitespace and the new character isn't whitespace, so "Hello world" is two steps, "Hello " and "world".
- Not a keystroke: a paste or a typed-over selection is always its own step.
- Sealed: after an undo, a redo or a cursor move, the next edit starts fresh even if it happens to be adjacent.
Backspaces group the same way, growing the group leftwards: each new delete must end exactly where the group begins. Merging happens after the new command has been applied, so absorbing only updates the group's bookkeeping (its position, text and timestamp); undoing the merged group reverses all of it at once.
The patterns, and why#
| Pattern | Where | Why it earns its place |
|---|---|---|
| Command | Insert, Delete |
Each edit is an object with do and an exact undo; the history is a stack of them. |
| Composite | Compound |
Typing over a selection is a delete then an insert, undone as one step, in reverse order. |
| Memento | Snapshot, save(), restore() |
Whole-state capture, opaque to everyone but the editor. Right for autosave and crash recovery; too heavy for keystroke undo. |
| Bounded history | deque(maxlen=100) |
Memory stays fixed however long the session runs; the oldest step falls off silently. |
Concurrency and edge cases#
An editor has one UI thread, and every edit happens on it. The concurrency is around it: an autosave timer reading the text, a spell-checker reading a paragraph, a sync client sending changes. The editor takes a re-entrant lock in every public method, so a reader sees the text either before or after an edit, never halfway through a compound one. Readers that take a while (autosave writing to disk) should save() a snapshot under the lock and do the slow work outside it; a Snapshot is immutable, so that's safe.
Two people editing the same document is a different problem, and the interviewer may ask: the local undo stack no longer describes the document, because the other person's edits shifted every position. That needs operational transformation or a CRDT (see the follow-ups); say so rather than trying to lock your way out of it.
- Backspace at position 0: does nothing and records nothing; no empty commands on the stack
- Undo with an empty stack, redo after a new edit: return
False, don't raise - Typing over a selection: one
Compound; undo restores the old text and puts the cursor after it - Backspace with a selection: deletes the selection, not one character before it
- A cursor position past the end: clamp it, so a stale position from another component can't corrupt the text
- History full: the 101st step drops the oldest; the user can still undo 100 times
The code#
The editor: cursor, selection, the two stacks, and the memento methods for comparison:
# part 2: the editor: cursor, selection, and two stacks
class Editor:
def __init__(self, text: str = "", history: int = 100) -> None:
self.doc = Document(text)
self.cursor, self.anchor = len(text), None # anchor is the other end of a selection
self._undo_stack: deque[Command] = deque(maxlen=history) # the oldest step falls off the bottom
self._redo_stack: list[Command] = []
self._sealed = True # True: the next edit starts a new group
self._lock = threading.RLock() # autosave and spell-check read while the UI thread writes
@property
def text(self) -> str:
with self._lock:
return self.doc.text
def move(self, pos: int, select: bool = False) -> None:
with self._lock:
if select and self.anchor is None:
self.anchor = self.cursor
elif not select:
self.anchor = None
self.cursor = max(0, min(pos, len(self.doc.text)))
self._sealed = True # typing somewhere else is a new group
def select(self, start: int, end: int) -> None:
self.move(start)
self.move(end, select=True)
def selection(self) -> tuple[int, int] | None:
if self.anchor is None or self.anchor == self.cursor:
return None
return min(self.anchor, self.cursor), max(self.anchor, self.cursor)
def _cut(self, now: float) -> Delete | None:
if (sel := self.selection()) is None:
return None
s, e = sel
return Delete(s, self.doc.text[s:e], now, keystroke=False)
def type(self, text: str, now: float) -> None:
with self._lock:
cut = self._cut(now)
ins = Insert(cut.pos if cut else self.cursor, text, now, keystroke=len(text) == 1 and cut is None)
self._run(Compound(cut, ins) if cut else ins)
def backspace(self, now: float) -> None:
with self._lock:
cmd = self._cut(now)
if cmd is None and self.cursor > 0:
cmd = Delete(self.cursor - 1, self.doc.text[self.cursor - 1], now)
if cmd:
self._run(cmd)
def _run(self, cmd: Command) -> None:
self.cursor, self.anchor = cmd.do(self.doc), None
if self._sealed or not self._undo_stack or not self._undo_stack[-1].absorb(cmd):
self._undo_stack.append(cmd)
self._sealed = False
self._redo_stack.clear() # a new edit forks history: the old future is gone
def undo(self) -> bool:
with self._lock:
if not self._undo_stack:
return False
cmd = self._undo_stack.pop()
self.cursor, self.anchor, self._sealed = cmd.undo(self.doc), None, True
self._redo_stack.append(cmd)
return True
def redo(self) -> bool:
with self._lock:
if not self._redo_stack:
return False
cmd = self._redo_stack.pop()
self.cursor, self.anchor, self._sealed = cmd.do(self.doc), None, True
self._undo_stack.append(cmd)
return True
def save(self) -> Snapshot:
with self._lock:
return Snapshot(self.doc.text, self.cursor)
def restore(self, s: Snapshot) -> None:
with self._lock:
self.doc.text, self.cursor, self.anchor = s.text, s.cursor, None_run is the one place where history changes: apply the command, try to merge it into the group on top of the stack (unless the group is sealed), and clear the redo stack. Any edit that skipped _run would break undo, which is why type and backspace both go through it.
A short session, then 200 edits on a large document with both kinds of history:
# part 3: type, undo, redo, replace a selection, and the cost of snapshots
if __name__ == "__main__":
ed = Editor()
for i, ch in enumerate("Hello world"):
ed.type(ch, now=i * 0.2) # five keystrokes a second
print(repr(ed.text), "| undo steps:", len(ed._undo_stack))
ed.undo()
print("undo ->", repr(ed.text), "cursor", ed.cursor)
ed.redo()
print("redo ->", repr(ed.text), "cursor", ed.cursor)
ed.select(6, 11)
ed.type("there", now=5.0) # typing over a selection: delete + insert, one step
for k in range(3):
ed.backspace(now=8.0 + k * 0.1)
print("typed over 'world', 3 backspaces ->", repr(ed.text))
ed.undo()
print("undo ->", repr(ed.text), "(3 backspaces, 1 step)")
ed.undo()
print("undo ->", repr(ed.text), "cursor", ed.cursor)
ed.type("!", now=12.0)
print("type '!' ->", repr(ed.text), "| redo available:", ed.redo())
ed.type(" Bye.", now=12.3) # a paste: never merged with the '!'
ed.undo()
print("undo the paste ->", repr(ed.text))
big, snaps = Editor("x" * 50_000), deque(maxlen=100)
for i in range(200):
snaps.append(big.save()) # the memento way: copy everything before each edit
big.move(i * 250)
big.type("y", now=i * 10.0)
cmd_chars = sum(len(c.text) for c in big._undo_stack)
snap_chars = sum(len(s.text) for s in snaps)
print(f"200 edits on 50,000 chars, last 100 kept: commands hold {cmd_chars} chars, snapshots {snap_chars:,}")
big.restore(snaps[0])
print("restore the oldest snapshot ->", len(big.text), "chars")'Hello world' | undo steps: 2
undo -> 'Hello ' cursor 6
redo -> 'Hello world' cursor 11
typed over 'world', 3 backspaces -> 'Hello th'
undo -> 'Hello there' (3 backspaces, 1 step)
undo -> 'Hello world' cursor 11
type '!' -> 'Hello world!' | redo available: False
undo the paste -> 'Hello world!'
200 edits on 50,000 chars, last 100 kept: commands hold 100 chars, snapshots 5,014,950
restore the oldest snapshot -> 50100 chars"Hello world" typed in one go is two undo steps, split at the word boundary. Undo takes away "world" and leaves the cursor after "Hello "; redo puts it back. Typing "there" over the selected "world" and then pressing backspace three times gives "Hello th", and one undo restores all three characters. The next undo reverses the replacement as a single step. Typing "!" clears the redo stack, so redo returns False, and the pasted " Bye." is its own step. On the 50,000-character document, the last 100 edits cost 100 characters as commands and over 5 million as snapshots: about 50,000 times more.
Extending it: the follow-ups#
- "Make it fast on a 50 MB file." Replace the string with a gap buffer (cheap edits near the cursor), a piece table (the original file plus an append-only buffer of insertions, used by several well-known editors) or a rope (a balanced tree of string chunks, O(log n) edits anywhere). Commands don't change; only
Documentdoes. - "Two people editing at once." Each edit becomes an operation that can be transformed against concurrent ones (operational transformation), or the document becomes a CRDT whose characters have stable ids instead of positions. Undo then means "undo my last operation", transformed against everything since.
- "Undo survives a restart." Serialise commands, not snapshots: each is a small record of position and text. Replay them against the saved document.
- "Never lose a branch." An undo tree: a new edit after undo starts a branch instead of clearing redo, and the user can walk back to any earlier state.
- "Multiple cursors." Each command holds a list of positions; applying it from the last position to the first keeps the earlier positions valid.
Common mistakes#
- Snapshots of the whole document on every keystroke, with no idea what they cost
- A delete command that doesn't store the deleted text, so it can't be undone
- Forgetting to clear the redo stack on a new edit, so redo applies an edit to text it no longer fits
- Every keystroke as its own undo step, or the opposite: merging a paste into typing
- Undo that restores text but leaves the cursor wherever it was
- Editing the document directly in
type()instead of through a command, so some edits never reach the history
Text editor
Q1/3 The user undoes two steps, then types a letter. What should happen to the redo stack?
Answer & explanation
Answer: B
The redone commands were recorded against a document that no longer exists at those positions. A linear history clears redo; keeping both futures is what an undo tree is for.
Q2/3 What must a Delete command store so that it can be undone?
Answer & explanation
Answer: C
Once the text is gone, nothing else remembers it. Position plus removed text is the smallest exact inverse; a full copy works but is the memento cost the demo measures.
Q3/3 "Hello world" is typed at a steady five keys a second. With these grouping rules, how many undo steps is it?
Answer & explanation
Answer: C
Keystrokes merge while they're adjacent, quick and inside one word. The space joins the first group; the "w" after it starts a new one.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.