Notes
Requirements
The requirements come in three layers. First, edits: insert and delete text, with undo and redo many levels deep, and a new edit after an undo drops the redo history. Second, versions: commit the current text with a message. Third, branches: create one, check it out, show the log, and find where two branches split. Concurrent commits must never be lost. And the variant: a calculator that lets you change any of its last five operations.
Clarify. Undo history is bounded, dropping the oldest edit when full. Checking out another version resets the undo history, because old edits no longer line up with the new text. A version stores a full snapshot first; storing only differences is an optimisation for later. Full merging with conflicts is out of scope, but finding the merge base is in. And several people may commit to the same branch at the same moment.
- insert and delete text
- undo and redo, many levels
- a new edit after undo:
- redo history is dropped
- commit a version with a message
- branch, checkout, log
- find where two branches split
- concurrent commits: none lost
- variant: calculator, edit any
- of its last five operations
- how many undo levels?
- bounded: drop the oldest
- undo across a checkout?
- no: checkout resets history
- store diffs or full copies?
- full snapshots first, then
- diffs as an optimisation
- merge with conflicts?
- merge base only, merge later
- one user or many?
- many may commit at once
Entities
The entities. The editor owns a document and two stacks of commands, undo and redo. Saving the document produces a snapshot, an immutable copy of the text. The repository stores commits, each holding a snapshot and the id of its parent, and a small map of branch names to their tip commits. Commands handle the fine-grained steps, snapshots handle whole versions, and commits chain those versions into history.
Command pattern
Each edit is a Command object with two methods, execute and undo. Insert is a record: undo deletes the same number of characters at the same position. Delete is the interesting one: it cannot know what to restore until it runs, so execute saves the removed text in a field, and undo inserts it back. That is the rule for any command: capture whatever undo will need at the moment you execute.
interface Command {
void execute(Document d);
void undo(Document d);
}
record Insert(int pos, String s)
undo: delete(pos, pos + s.length())
class Delete(int pos, int len)
execute: removed = substring(..)
undo: insert(pos, removed) Undo and redo stacks
Two stacks do everything. Applying an edit executes it, pushes it on the undo stack and clears the redo stack. Undo pops from undo, reverses the command and pushes it on redo. Redo pops from redo, executes again and pushes back on undo. A deque lets us cap history cheaply by dropping the oldest from the bottom. And clearing redo on a new edit is the rule people forget: after undoing, typing something new starts a new future.
apply(c): c.execute(doc) undo.push(c) if over limit: undo.removeLast() redo.clear() undo(): c = undo.poll() c.undo(doc); redo.push(c) redo(): c = redo.poll() c.execute(doc); undo.push(c) Deque: push/poll at the top, removeLast drops the oldest
Flow: undo and redo
Trace it. Type hello, then world, then a comma: hello comma world. Undo removes the comma, redo brings it back. Delete the first seven characters, leaving world. Undo twice, which restores hello and then removes the comma again. Now type an exclamation mark. That new edit clears the redo stack, so redo reports false. The document is hello world with an exclamation mark, exactly as the demo asserts.
Typed: Hello, world Undo: Hello world Redo: Hello, world Delete: world undo, undo, then type "!" Branch: Hello world! (redo possible? false)
Memento
The Memento pattern is the other way to remember the past: save a frozen copy of the whole state. The editor creates a snapshot and can restore from one, without anyone else seeing its internals. Mementos are simple and always correct, but cost memory per version. Commands are tiny but must replay exactly. Real editors use both: commands for keystroke undo, snapshots for saved versions. Git stores full snapshots too, and saves space by sharing identical content.
- Memento: store the whole state
- simple, always correct
- costs memory per version
- Command: store each change
- tiny, but replay must be exact
- editors: commands for undo,
- snapshots for saved versions
- git: full snapshots, deduped
- by content hash
Class diagram: mini git
The tiny git. A commit is an immutable record: an id, the parent's id, a message and a snapshot. Commits are never changed or removed, so history is a chain of parent pointers, and with branches, a tree. A branch is nothing but a name pointing at its tip commit, and head names the checked-out branch. That is the insight that makes git simple: branching is cheap because it only writes one small pointer.
record Commit(String id, String parent,
String message, Snapshot snapshot)
Map<String, Commit> commits
// immutable, never removed
Map<String, String> branches
// "main" -> "c3"
volatile String head = "main"
history = follow parent pointers Flow: branch and commit
Follow the flow. Commit the greeting as c1 on main. Branching feature just copies main's tip, c1, under a new name. Check out feature: load its snapshot into the editor, which resets undo history. Edit, then commit c2, whose parent is c1, and move feature's pointer to c2. Check out main, edit, and commit c3, also with parent c1. History has forked: main is c3, c1, c0, and feature is c2, c1, c0.
commit "greeting" -> c1 (main) branch feature -> at c1 checkout feature, edit commit "add farewell" -> c2 checkout main, edit commit "add prompt" -> c3 main: c3, c1, c0 feature: c2, c1, c0
Log and merge base
Log is a walk along parent pointers from the tip until there is no parent. The merge base is the nearest commit both branches share: collect every ancestor of one tip in a set, then walk back from the other tip until you hit one. For main and feature that is c1. A real merge diffs each side against the merge base, combines changes that do not overlap, and flags the ones that do as conflicts.
log(b): for (id = tip(b); id != null;
id = parent(id)) add(id)
mergeBase(a, b):
seen = all ancestors of a
walk b back; first in seen wins
main vs feature -> c1
three-way merge: diff base->main,
base->feature, combine, flag clashes Variant: calculator
The calculator variant. Keep a checkpoint value and a list of the last five operations. When a sixth arrives, fold the oldest into the checkpoint, since it can never be edited again. Editing replaces one operation in the list, and the value is the checkpoint with the five recent operations replayed, so every step is constant time. Plus five, times three, minus two, plus ten, times two, plus one gives forty-seven; changing the minus two to plus two gives fifty-five.
apply(op): recent.add(op)
if (recent.size() > 5)
checkpoint = remove(0).apply(..)
edit(k, op): recent.set(size - k, op)
value(): replay recent on checkpoint
+5 *3 -2 +10 *2 +1 = 47
checkpoint 5, recent [*3 .. +1]
edit 4th from last to +2 = 55
edit 6th from last: rejected Concurrency
Concurrency. Commits are immutable and written once to a concurrent map, so they need no lock. The only shared thing that changes is a branch pointer, and it moves by compare-and-set: replace main's tip only if it is still the commit I built on. If someone else got there first, the commit is rejected as stale, just like a rejected push, and the caller re-reads the tip and retries. Four threads making a hundred commits each leave a single line four hundred commits longer.
commits: ConcurrentHashMap, write once branches.replace(branch, expected, id) fails if someone moved the tip -> StaleBranchException -> re-read tip, retry 4 threads x 100 commits: depth 3 -> 403, nothing lost the editor: one owner thread
Extensibility
Extensions. A macro, such as find and replace all, is a composite command that undoes its parts in reverse order. An undo tree keeps the redo branch you abandoned instead of clearing it, so nothing typed is ever lost. Store differences between snapshots to save memory. Use a hash of the content as the commit id, so identical content is stored once. Merge commits get two parents. And real-time collaborative editing needs operational transforms or CRDTs.
- macro: a CompositeCommand
- undoes its parts in reverse
- undo tree: keep abandoned redo
- branches instead of clearing
- store diffs between snapshots
- content-hash ids: equal text,
- equal id, stored once
- merge commits: two parents
- collaborative editing:
- operational transform, CRDTs
Testing
The full code is below the player. The demo traces undo and redo and checks that a new edit kills redo. It forks main and feature from one commit, prints both logs and checks the merge base. A commit built on an old tip is rejected. Four threads commit concurrently and the history depth grows by exactly four hundred. And the calculator gives forty-seven, fifty-five after the edit, and refuses to edit a sixth-from-last operation.
Typed: Hello, world Undo: Hello world Branch: Hello world! (redo? false) main: >> Hello world! log [c3, c1, c0] feature: Hello world! Bye. Merge base of main and feature: c1 Rejected: main moved past c0 depth 3 -> 403 Calculator ... = 47, edited = 55
Follow-ups
Expect follow-ups. In a shared document, undo should reverse only my own operations, transformed past everyone else's. A million edits? Cap the history, or snapshot every N commands and keep only commands since then. Why immutable commits? They can be shared, cached and read without locks. And to edit any past calculator step, not just the last five, keep a checkpoint every k operations and replay from the nearest one.
- undo in a multi-user doc?
- undo only my own operations
- memory for 1 million edits?
- cap, or snapshot every N +
- commands since the snapshot
- why immutable commits?
- sharing, caching, no locks
- calculator: edit any op?
- snapshot every k ops: O(k)
- how does git find changes? diff
Say it like this
The short version. Each edit is a command with execute and undo, kept on an undo stack and a redo stack, and a new edit clears redo. Saved versions are mementos inside immutable commits that point to their parent. A branch is just a name for a tip commit, moved by compare-and-set so concurrent commits are never lost. Log walks parents, and the merge base is the first shared ancestor.
- "Edits are Commands with execute
- and undo on two stacks; a new
- edit clears redo. Versions are
- Mementos inside immutable
- commits that point to a parent.
- A branch is a name for a tip,
- moved by compare-and-set. Merge
- base: first shared ancestor."