How undo and redo work: the command pattern, step by step
Build undo and redo the way editors do: edits as reversible commands, an undo and a redo stack, merging typing into words, grouping edits into one step, and a capped history.
Undo looks like magic until you see the trick: every change is an object that knows how to reverse itself, kept on a stack.
Edits as commands
Instead of changing the text directly, describe each change:
Insert { position: 42, text: "hello" } inverse: Delete { position: 42, length: 5 }
Delete { position: 10, text: "old" } inverse: Insert { position: 10, text: "old" }Note that a delete must remember the text it removed; without it, it can't be undone. Fill it in when the command is applied, not when it's created.
Validate before applying: inserting at position 500 of a 100-character document must be refused and leave both the document and the history unchanged.
Two stacks
apply(cmd): cmd.do(doc); undo.push(cmd); redo.clear()
undo(): cmd = undo.pop(); cmd.undo(doc); redo.push(cmd)
redo(): cmd = redo.pop(); cmd.do(doc); undo.push(cmd)undo() with an empty stack does nothing (and says so, with a false return value or similar).
Why new edits clear redo
Type "cat", undo it, type "dog". Redo would now try to re-insert "cat" into a document it was never part of. Clearing the redo stack on every new edit is what keeps every command on the stacks valid for the state it will be applied to.
Merging small steps
Nobody wants to press undo once per letter. Editors merge a new command into the previous one when they continue each other:
top of undo = Insert{pos 10, "hel"}; new = Insert{pos 13, "l"} -> merge: Insert{pos 10, "hell"}Typical rules: merge consecutive inserts at the end of the previous one, but start a new step at a space or newline (so undo removes one word), after a pause, or after the cursor moved. Write the rules from the ticket down as a list before coding, and turn each into a test.
Grouping several edits into one step
Some actions make several changes at once: "replace all" or "indent 5 lines". Undo must reverse them together. A composite command holds a list of commands:
group.do(): for cmd in commands: cmd.do()
group.undo(): for cmd in reverse(commands): cmd.undo() # reverse order mattersUndo in reverse order: positions in later edits depend on the earlier ones.
Bounded history
Memory isn't infinite. Cap the undo stack at N steps by dropping the oldest command when a new
one would exceed the cap. A double-ended queue (std::deque) makes dropping from the bottom O(1).
Decide whether a merged step counts as one or several towards the cap (usually one).
Build all of it in undo and redo for Draftboard.
Questions and answers
- Should undo store snapshots or commands?
- Commands, for anything large. A snapshot of a 1 MB document per keystroke uses a gigabyte after a thousand edits; a command stores only what changed (insert 'x' at 42). Snapshots are fine for small state and are simpler to get right.
- Why does a new edit clear the redo stack?
- Redo replays edits on top of the state they were undone from. After a new edit, that state no longer exists, so the old redo history no longer applies. Editors that keep it build a tree of histories instead of two stacks.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Draftboard
Undo and redo for Draftboard
Give Draftboard's editor an undo history that behaves the way writers expect: reversible commands, typing that undoes a word at a time, grouped edits and a bounded history.
- command pattern
- stacks
- inverse operations
- bounded history
Shipwright
Order lifecycle for Shipwright
Replace Shipwright's tangle of status flags with an explicit state machine: one transition table, guards, an audit history and replay from an event log.
- finite state machines
- transition tables
- guards
- event replay
Read next
- State machines in practice: transition tables, guards and event logs
Model order statuses, CSV quoting and regex matching as state machines: one transition table, guards for business rules, event logs you can replay, and NFAs that track several states.