Text Editor
Undo and redo through state snapshots and command objects. The Memento saves what the document looked like, the Command knows how to get there and back.
Key Abstractions
Originator that creates and restores state snapshots on every operation
Immutable memento capturing text content and cursor position at a point in time
Underlying text storage with insert and delete at arbitrary positions
Interface for executable and undoable editor operations like type and delete
Caretaker managing undo and redo stacks of EditorState snapshots
Class Diagram
The Key Insight
A text editor's undo system needs to answer two questions: what did the user do, and what did things look like before they did it? These are fundamentally different concerns. The Command pattern answers the first question. Each operation (type, delete, bold) becomes an object with execute() and undo() methods. The Memento pattern answers the second. Before any command runs, you snapshot the entire editor state into an immutable object and push it onto a stack.
You could technically build undo with just commands. Reverse each operation to go back. But some operations are hard to reverse perfectly. What if a delete removes text that spans a formatting boundary? Reconstructing the exact prior state from the inverse operation gets messy fast. Memento sidesteps that problem entirely. You just restore the snapshot. O(1), no reconstruction logic, no edge cases.
The History class ties it all together as the caretaker. It holds two stacks of EditorState snapshots. Undo pops from the undo stack, redo pops from the redo stack. When the user performs a new action after undoing, the redo stack clears. That forking behavior is what users expect, and forgetting to implement it is a common source of bugs.
Requirements
Functional
- Insert text at any cursor position
- Delete characters before the cursor (backspace behavior)
- Undo the last operation, restoring the editor to its previous state
- Redo a previously undone operation
- Track cursor position through all operations
Non-Functional
- O(1) for undo and redo via direct state restoration
- Bounded memory usage with a configurable history cap
- EditorState must be truly immutable so snapshots cannot be corrupted
- Commands should be self-contained and store enough context to reverse themselves
Design Decisions
Why Memento over just storing diffs?
Diffs are smaller in memory. That is their one advantage. But rebuilding the full editor state from a chain of diffs is O(n) where n is the number of operations since the snapshot you need. For a text editor where users hit Ctrl+Z constantly, that latency adds up. Memento gives you O(1) restore every time. You pay more in memory, but you bound that cost with a history cap. The tradeoff is worth it for any interactive application where responsiveness matters more than storage.
Why Command + Memento instead of just one?
Command tells you what happened: "typed 'hello' at position 5." Memento tells you what things looked like before that happened. You could do undo with just commands by reversing each one. But some operations are genuinely hard to reverse. A delete that spans multiple words, a paste that overwrites a selection. Getting the inverse exactly right for every edge case is a bug factory. Memento gives you a reliable fallback. The command executes the action, the memento guarantees you can always get back.
Why is EditorState immutable?
This is the most common mistake people make. If your memento holds a mutable reference to the editor's text buffer, then when the editor changes, your "snapshot" changes with it. The undo stack silently corrupts. By making EditorState a frozen dataclass (Python) or a class with only final fields and getters (Java), each snapshot is a copy, not a reference. It is frozen at the moment it was created. No amount of subsequent editing can touch it.
Why cap the history size?
An editor session can run for hours. Without a cap, every single keystroke adds a snapshot to the undo stack. That is linear memory growth with no upper bound. A user typing a 10,000-word document would accumulate tens of thousands of snapshots, each holding a full copy of the text. Set a reasonable maximum (100 is a good default), drop the oldest entries when you hit the limit, and memory stays predictable.
Interview Follow-ups
- "How would you handle collaborative editing with multiple users?" Each user gets their own command stream. You need Operational Transformation (OT) or CRDTs to merge concurrent edits. The memento approach breaks down because one user's undo might conflict with another user's concurrent change. This is a fundamentally different problem.
- "What if you want to undo specific operations out of order, not just the most recent one?" That moves you from a stack-based model to a tree-based one. Each state becomes a node in a version tree, and users can jump to any node. The memento snapshots still work, but the History class needs to become a tree structure instead of two stacks.
- "How would you reduce memory usage for large documents?" Instead of storing the full text in every snapshot, store a combination of the base text plus a compact diff. Or use a rope data structure for the text buffer, which shares unchanged segments across snapshots through structural sharing.
- "What about grouping multiple keystrokes into a single undo step?" Batch commands by time window. If the user types five characters within 500ms, group those into a single CompoundCommand. When they hit undo, all five characters disappear at once. Most real editors do this because undoing one character at a time is tedious.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from dataclasses import dataclass
4
5
6 @dataclass(frozen=True)
7 class EditorState:
8 """Immutable memento. Frozen dataclass means no field can be changed after creation."""
9 text: str
10 cursor_position: int
11
12
13 class TextBuffer:
14 """Raw text storage. Handles inserts and deletes at arbitrary positions."""
15
16 def __init__(self):
17 self._content = ""
18
19 def insert(self, position: int, text: str) -> None:
20 self._content = self._content[:position] + text + self._content[position:]
21
22 def delete(self, position: int, length: int) -> str:
23 start = position - length
24 if start < 0:
25 start = 0
26 deleted = self._content[start:position]
27 self._content = self._content[:start] + self._content[position:]
28 return deleted
29
30 def get_text(self) -> str:
31 return self._content
32
33 def length(self) -> int:
34 return len(self._content)
35
36
37 class History:
38 """Caretaker. Manages undo/redo stacks of EditorState snapshots."""
39
40 def __init__(self, max_size: int = 100):
41 self._undo_stack: list[EditorState] = []
42 self._redo_stack: list[EditorState] = []
43 self._max_size = max_size
44
45 def push(self, state: EditorState) -> None:
46 if len(self._undo_stack) >= self._max_size:
47 self._undo_stack.pop(0)
48 self._undo_stack.append(state)
49 self._redo_stack.clear()
50
51 def undo(self, current_state: EditorState) -> EditorState | None:
52 if not self._undo_stack:
53 return None
54 self._redo_stack.append(current_state)
55 return self._undo_stack.pop()
56
57 def redo(self, current_state: EditorState) -> EditorState | None:
58 if not self._redo_stack:
59 return None
60 self._undo_stack.append(current_state)
61 return self._redo_stack.pop()
62
63 @property
64 def can_undo(self) -> bool:
65 return len(self._undo_stack) > 0
66
67 @property
68 def can_redo(self) -> bool:
69 return len(self._redo_stack) > 0
70
71
72 class Command(ABC):
73 @abstractmethod
74 def execute(self) -> None: ...
75
76 @abstractmethod
77 def undo(self) -> None: ...
78
79
80 class Editor:
81 """Originator. Creates and restores mementos around every operation."""
82
83 def __init__(self):
84 self.text_buffer = TextBuffer()
85 self.cursor_position = 0
86 self._history = History()
87
88 def create_memento(self) -> EditorState:
89 return EditorState(
90 text=self.text_buffer.get_text(),
91 cursor_position=self.cursor_position,
92 )
93
94 def restore_memento(self, state: EditorState) -> None:
95 self.text_buffer = TextBuffer()
96 self.text_buffer.insert(0, state.text)
97 self.cursor_position = state.cursor_position
98
99 def execute(self, command: Command) -> None:
100 self._history.push(self.create_memento())
101 command.execute()
102
103 def undo(self) -> bool:
104 state = self._history.undo(self.create_memento())
105 if state is None:
106 return False
107 self.restore_memento(state)
108 return True
109
110 def redo(self) -> bool:
111 state = self._history.redo(self.create_memento())
112 if state is None:
113 return False
114 self.restore_memento(state)
115 return True
116
117 def __str__(self) -> str:
118 text = self.text_buffer.get_text()
119 return f"'{text}' (cursor at {self.cursor_position})"
120
121
122 class TypeCommand(Command):
123 """Inserts text at the editor's current cursor position."""
124
125 def __init__(self, editor: Editor, text: str):
126 self._editor = editor
127 self._text = text
128
129 def execute(self) -> None:
130 self._editor.text_buffer.insert(self._editor.cursor_position, self._text)
131 self._editor.cursor_position += len(self._text)
132
133 def undo(self) -> None:
134 pos = self._editor.cursor_position
135 self._editor.text_buffer.delete(pos, len(self._text))
136 self._editor.cursor_position -= len(self._text)
137
138
139 class DeleteCommand(Command):
140 """Deletes characters before the cursor. Stores deleted text for undo."""
141
142 def __init__(self, editor: Editor, length: int):
143 self._editor = editor
144 self._length = length
145 self._deleted_text = ""
146
147 def execute(self) -> None:
148 self._deleted_text = self._editor.text_buffer.delete(
149 self._editor.cursor_position, self._length
150 )
151 self._editor.cursor_position -= len(self._deleted_text)
152
153 def undo(self) -> None:
154 self._editor.text_buffer.insert(
155 self._editor.cursor_position, self._deleted_text
156 )
157 self._editor.cursor_position += len(self._deleted_text)
158
159
160 if __name__ == "__main__":
161 editor = Editor()
162
163 # Type "Hello"
164 editor.execute(TypeCommand(editor, "Hello"))
165 print(f"After typing 'Hello': {editor}")
166
167 # Type " World"
168 editor.execute(TypeCommand(editor, " World"))
169 print(f"After typing ' World': {editor}")
170
171 # Move cursor to position 5 and type " Beautiful"
172 editor.cursor_position = 5
173 editor.execute(TypeCommand(editor, " Beautiful"))
174 print(f"After inserting ' Beautiful' at pos 5: {editor}")
175
176 # Undo the insert
177 editor.undo()
178 print(f"After first undo: {editor}")
179
180 # Undo " World"
181 editor.undo()
182 print(f"After second undo: {editor}")
183
184 # Redo " World"
185 editor.redo()
186 print(f"After redo: {editor}")
187
188 # Move cursor to end and delete 3 chars
189 editor.cursor_position = editor.text_buffer.length()
190 editor.execute(DeleteCommand(editor, 3))
191 print(f"After deleting 3 chars from end: {editor}")
192
193 # Undo the delete
194 editor.undo()
195 print(f"After undoing delete: {editor}")
196
197 print("All operations completed successfully.")Common Mistakes
- ✗Storing mutable references in the memento. If the editor state changes, your snapshot changes too.
- ✗Unbounded undo history. A user editing for hours will eat all your memory without a cap.
- ✗Coupling the memento to the editor's internal structure. The memento should be opaque to everyone except the originator.
- ✗Forgetting to clear the redo stack when a new action happens after an undo.
Key Points
- ✓Memento captures state, Command captures action. Together they give you full undo/redo.
- ✓EditorState is immutable. Once created, it never changes. This makes the undo stack reliable.
- ✓History limits stack depth to prevent unbounded memory growth in long editing sessions.
- ✓Commands store just enough to reverse themselves. DeleteCommand saves the deleted text.