FoundationalProblem 15 of 20
FoundationalIntermediate
Undo/Redo Manager
Command PatternMemento PatternComposite Pattern
Two stacks and a Command interface. Every user action becomes an object that knows how to do and undo itself — the rest is just stack discipline.
Key Abstractions
Command
Interface with execute and undo. Every user action is a command object.
HistoryManager
Two stacks (undo/redo), capacity cap, and a map of named checkpoints
CompositeCommand
Macro: a list of commands that execute and undo atomically
DocumentMemento
Snapshot of document state used by named checkpoints
RestoreCommand
Swaps the document to a memento's content; its undo swaps back — so restore is itself undoable
Class Diagram
The Key Insight
Every user action is an object, not a mutation. That's the whole idea. Once an "action" is a Command with execute() and undo(), the manager becomes trivial: push on execute, pop-and-invoke-undo on undo, pop-and-invoke-execute on redo. No special cases, no knowledge of what the action did.
The subtle invariant is that a new action clears the redo stack. If someone undoes twice, then types something new, the two things they undid are gone — the timeline branched. Keeping them around would mean "redo" replays commands that depended on the state before the new edit, which is now inconsistent.
The second insight is scope. The naive approach snapshots the document before every command. That's fine for a calculator, fatal for a text editor. Each command should be small enough to compute its own inverse. An InsertCommand undoes by deleting exactly what it inserted. A DeleteCommand undoes by re-inserting what it captured. No full-document snapshots.
Requirements
Functional
- Execute an action and record it for undo
- Undo returns to the prior state; redo moves forward
- A new action after undo invalidates the redo path
- Support macro/composite commands that undo atomically
- Bounded history so long sessions don't leak memory
Non-Functional
- O(1) per undo/redo
- Commands must be self-contained (no external references to transient UI state)
- Composite failures must roll back partial execution
Design Decisions
Why two stacks?
A single "pointer into a list" works too, but it wastes memory once undone commands are overwritten. Two stacks make the invariant explicit — "everything I can undo" vs "everything I can redo" — and execute() is the only place that clears redo. Easier to reason about and matches the way command-line shells handle history.
Why capture state in the command rather than outside?
Putting the "what got deleted" into DeleteCommand._removed means the command is self-sufficient. Moving it to a separate undo-log means every undo has to match by ID and look up the log. The command already exists on the stack — attach the data there.
Why composite command instead of manual batch undo?
Without composites, "find and replace all" pushes 47 separate commands. One undo press reverts one replacement — infuriating. Wrapping 47 commands in a CompositeCommand makes one undo revert all 47 as the user expects.
Why partial-rollback inside CompositeCommand.execute?
If step 5 of a 10-step macro fails, the document is already half-changed. The manager doesn't know to undo. Rolling back locally inside the composite keeps the document consistent and lets the caller see the failure as if nothing happened.
Interview Follow-ups
- "How would you handle huge documents?" Use diff-based commands — store the minimal delta (inserted text, deleted range) instead of snapshots. Already the design here.
- "What about collaborative editing?" Each user has their own history stack but operations must be transformed against concurrent edits (Operational Transformation) or use CRDTs. Far more complex — separate design problem.
- "How would you persist undo across sessions?" Serialize commands to disk as a log. On load, replay or keep the log for undo. Commands must be serializable (no live doc references — use IDs).
- "How does this scale to the Photoshop history panel?" Same model plus visual previews per command. The panel reads
describe()from each command for its label.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from collections import deque
4
5
6 class Command(ABC):
7 @abstractmethod
8 def execute(self) -> None: ...
9
10 @abstractmethod
11 def undo(self) -> None: ...
12
13 def describe(self) -> str:
14 return self.__class__.__name__
15
16
17 class Document:
18 """Mutable text model. Commands operate on this."""
19
20 def __init__(self, text: str = ""):
21 self._buf = list(text)
22
23 def insert(self, pos: int, text: str) -> None:
24 if not 0 <= pos <= len(self._buf):
25 raise IndexError("insert position out of range")
26 self._buf[pos:pos] = list(text)
27
28 def delete(self, pos: int, length: int) -> str:
29 if pos < 0 or pos + length > len(self._buf):
30 raise IndexError("delete range out of bounds")
31 removed = "".join(self._buf[pos:pos + length])
32 del self._buf[pos:pos + length]
33 return removed
34
35 def content(self) -> str:
36 return "".join(self._buf)
37
38
39 class InsertCommand(Command):
40 def __init__(self, doc: Document, pos: int, text: str):
41 self._doc = doc
42 self._pos = pos
43 self._text = text
44
45 def execute(self) -> None:
46 self._doc.insert(self._pos, self._text)
47
48 def undo(self) -> None:
49 self._doc.delete(self._pos, len(self._text))
50
51 def describe(self) -> str:
52 preview = self._text if len(self._text) <= 10 else self._text[:10] + "..."
53 return f"Insert({preview!r} at {self._pos})"
54
55
56 class DeleteCommand(Command):
57 def __init__(self, doc: Document, pos: int, length: int):
58 self._doc = doc
59 self._pos = pos
60 self._length = length
61 self._removed: str | None = None # captured on execute, replayed on undo
62
63 def execute(self) -> None:
64 self._removed = self._doc.delete(self._pos, self._length)
65
66 def undo(self) -> None:
67 if self._removed is None:
68 raise RuntimeError("Cannot undo — execute was not called")
69 self._doc.insert(self._pos, self._removed)
70
71 def describe(self) -> str:
72 return f"Delete({self._length} chars at {self._pos})"
73
74
75 class CompositeCommand(Command):
76 """Atomic group — multiple commands that undo together."""
77
78 def __init__(self, children: list[Command], label: str = "Macro"):
79 self._children = children
80 self._label = label
81
82 def execute(self) -> None:
83 done: list[Command] = []
84 try:
85 for cmd in self._children:
86 cmd.execute()
87 done.append(cmd)
88 except Exception:
89 # Partial failure: roll back what we did. This keeps the doc consistent.
90 for cmd in reversed(done):
91 try:
92 cmd.undo()
93 except Exception:
94 pass
95 raise
96
97 def undo(self) -> None:
98 for cmd in reversed(self._children):
99 cmd.undo()
100
101 def describe(self) -> str:
102 return f"Macro({self._label}, {len(self._children)} steps)"
103
104
105 class DocumentMemento:
106 """Opaque snapshot of a Document's content. The Document is the 'originator',
107 Memento captures just enough state to restore it."""
108
109 __slots__ = ("_content",)
110
111 def __init__(self, content: str):
112 self._content = content
113
114 def content(self) -> str:
115 return self._content
116
117
118 class RestoreCommand(Command):
119 """Rewrites the document to a memento's content. Undoable like any command —
120 its inverse restores whatever the document held before the restore ran."""
121
122 def __init__(self, doc: Document, memento: DocumentMemento, label: str = ""):
123 self._doc = doc
124 self._memento = memento
125 self._label = label
126 self._prev: DocumentMemento | None = None
127
128 def execute(self) -> None:
129 self._prev = DocumentMemento(self._doc.content())
130 current_len = len(self._doc.content())
131 if current_len > 0:
132 self._doc.delete(0, current_len)
133 self._doc.insert(0, self._memento.content())
134
135 def undo(self) -> None:
136 if self._prev is None:
137 raise RuntimeError("Cannot undo — execute was not called")
138 current_len = len(self._doc.content())
139 if current_len > 0:
140 self._doc.delete(0, current_len)
141 self._doc.insert(0, self._prev.content())
142
143 def describe(self) -> str:
144 return f"Restore({self._label or 'checkpoint'})"
145
146
147 class HistoryManager:
148 """Bounded undo/redo via two stacks and a capacity cap. Named checkpoints
149 snapshot the document and restore is itself undoable."""
150
151 def __init__(self, capacity: int = 100):
152 if capacity <= 0:
153 raise ValueError("capacity must be positive")
154 self._capacity = capacity
155 self._undo: deque[Command] = deque()
156 self._redo: deque[Command] = deque()
157 self._checkpoints: dict[str, DocumentMemento] = {}
158
159 def execute(self, cmd: Command) -> None:
160 cmd.execute()
161 self._undo.append(cmd)
162 # New action invalidates any redo path — the future branched.
163 self._redo.clear()
164 # Enforce capacity by dropping the oldest undoable command.
165 if len(self._undo) > self._capacity:
166 self._undo.popleft()
167
168 def checkpoint(self, doc: Document, name: str) -> None:
169 """Save the document's current state under `name`. Overwrites an existing label."""
170 if not name:
171 raise ValueError("checkpoint needs a non-empty name")
172 self._checkpoints[name] = DocumentMemento(doc.content())
173
174 def restore_to(self, doc: Document, name: str) -> None:
175 """Restore via a Command so the restore itself is undoable."""
176 memento = self._checkpoints.get(name)
177 if memento is None:
178 raise KeyError(f"no checkpoint named {name!r}")
179 self.execute(RestoreCommand(doc, memento, label=name))
180
181 def checkpoint_names(self) -> list[str]:
182 return list(self._checkpoints.keys())
183
184 def undo(self) -> bool:
185 if not self._undo:
186 return False
187 cmd = self._undo.pop()
188 cmd.undo()
189 self._redo.append(cmd)
190 return True
191
192 def redo(self) -> bool:
193 if not self._redo:
194 return False
195 cmd = self._redo.pop()
196 cmd.execute()
197 self._undo.append(cmd)
198 return True
199
200 def can_undo(self) -> bool: return bool(self._undo)
201 def can_redo(self) -> bool: return bool(self._redo)
202
203 def describe_undo_stack(self) -> list[str]:
204 return [c.describe() for c in self._undo]
205
206
207 if __name__ == "__main__":
208 doc = Document("Hello ")
209 history = HistoryManager(capacity=100)
210
211 history.execute(InsertCommand(doc, 6, "world"))
212 history.execute(InsertCommand(doc, 11, "!"))
213 print(f"After edits: {doc.content()!r}") # 'Hello world!'
214
215 history.undo()
216 print(f"After one undo: {doc.content()!r}") # 'Hello world'
217
218 history.undo()
219 print(f"After two undos: {doc.content()!r}") # 'Hello '
220
221 history.redo()
222 print(f"After redo: {doc.content()!r}") # 'Hello world'
223
224 # New action kills redo — the timeline branched.
225 history.execute(InsertCommand(doc, 11, " there"))
226 print(f"After branching edit: {doc.content()!r}") # 'Hello world there'
227 assert not history.can_redo()
228
229 # Macro: replace "Hello" with "Goodbye" as one atomic undo.
230 macro = CompositeCommand([
231 DeleteCommand(doc, 0, 5),
232 InsertCommand(doc, 0, "Goodbye"),
233 ], label="Replace greeting")
234 history.execute(macro)
235 print(f"After macro: {doc.content()!r}") # 'Goodbye world there'
236
237 history.undo()
238 print(f"After undo macro: {doc.content()!r}") # 'Hello world there'
239
240 # Checkpoint → edits → restore_to → undo the restore.
241 history.checkpoint(doc, "v1")
242 saved = doc.content()
243 history.execute(InsertCommand(doc, len(doc.content()), " — draft 2"))
244 print(f"After draft-2 edit: {doc.content()!r}")
245 history.restore_to(doc, "v1")
246 print(f"After restore_to('v1'): {doc.content()!r}")
247 assert doc.content() == saved
248 history.undo()
249 print(f"After undo of restore: {doc.content()!r}")
250 assert doc.content().endswith("— draft 2")
251 print("All operations succeeded.")Common Mistakes
- ✗Keeping the redo stack alive after a new command. Now 'redo' replays a command from an obsolete branch.
- ✗Storing before/after snapshots for every command. A 10MB document times 1000 commands eats 10GB. Compute inverses or diff.
- ✗Mutating the document inside undo() without restoring side effects — cursor position, scroll, selection.
- ✗Letting commands hold references to stale UI state. The command must hold data, not widgets.
Key Points
- ✓Two stacks, not one. Executing a new command clears the redo stack — branching invalidates the future.
- ✓Commands capture everything needed to redo in their constructor. No hidden dependence on current state.
- ✓Composite commands let macros (replace-all, multi-edit) undo as one click.
- ✓Capacity bounded with a deque from the bottom so long sessions don't blow memory.
- ✓Named checkpoints use the Memento pattern. restoreTo runs through execute(), so restoring to v1 can itself be undone.