LOW LEVEL DESIGN · MACHINE CODING · HARD · 19 OF 42

Design Undo/Redo and Version History (Command, Memento, Mini Git) in Java

Undo, redo and version history designed and coded in layers: edits as Commands on an undo and a redo stack, Mementos as immutable snapshots, a tiny git with commits that point to parents, branches, checkout, log and merge base, branch tips moved by compare-and-set, and the calculator whose last five operations can be edited, with the follow-ups and full Java 17 code.

Patterns usedMementoCommandComposite

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 18

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 317 lines, with a small main() demo. Save it as VersionControl.java, then run javac VersionControl.java && java VersionControl.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.LongBinaryOperator;

/**
 * Undo/redo and version history in three layers: an editor whose edits are Commands on two stacks,
 * Mementos (snapshots) of the document, and a tiny git-like repository of immutable commits with branches,
 * checkout, log and merge base. Plus the calculator that lets you edit its last five operations.
 */
public final class VersionControl {

    // ---------- layer 1: commands with undo and redo ----------
    static final class Document {
        private final StringBuilder text = new StringBuilder();

        String text() { return text.toString(); }
    }

    /** Command: each edit knows how to apply itself and how to reverse itself. */
    interface Command {
        void execute(Document d);

        void undo(Document d);
    }

    record Insert(int pos, String s) implements Command {
        public void execute(Document d) { d.text.insert(pos, s); }

        public void undo(Document d) { d.text.delete(pos, pos + s.length()); }
    }

    /** Delete must remember what it removed, so undo can put it back. */
    static final class Delete implements Command {
        private final int pos, len;
        private String removed = "";

        Delete(int pos, int len) {
            this.pos = pos;
            this.len = len;
        }

        public void execute(Document d) {
            removed = d.text.substring(pos, pos + len);
            d.text.delete(pos, pos + len);
        }

        public void undo(Document d) { d.text.insert(pos, removed); }
    }

    /** Memento: an immutable snapshot of the document that the document itself can restore from. */
    record Snapshot(String text) {}

    static final class Editor {
        private final Document doc = new Document();
        private final Deque<Command> undo = new ArrayDeque<>(), redo = new ArrayDeque<>();
        private final int historyLimit;

        Editor(int historyLimit) { this.historyLimit = historyLimit; }

        void apply(Command c) {
            c.execute(doc);
            undo.push(c);
            if (undo.size() > historyLimit) undo.removeLast(); // forget the oldest edit
            redo.clear(); // a new edit after undo starts a new future
        }

        boolean undo() {
            Command c = undo.poll();
            if (c == null) return false;
            c.undo(doc);
            redo.push(c);
            return true;
        }

        boolean redo() {
            Command c = redo.poll();
            if (c == null) return false;
            c.execute(doc);
            undo.push(c);
            return true;
        }

        Snapshot save() { return new Snapshot(doc.text()); }

        /** Restoring a version replaces the text; old commands no longer line up, so history resets. */
        void restore(Snapshot s) {
            doc.text.setLength(0);
            doc.text.append(s.text());
            undo.clear();
            redo.clear();
        }

        String text() { return doc.text(); }
    }

    // ---------- layer 2: a tiny git ----------
    record Commit(String id, String parent, String message, Snapshot snapshot) {}

    static final class StaleBranchException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        StaleBranchException(String msg) { super(msg); }
    }

    static final class Repository {
        private final Map<String, Commit> commits = new ConcurrentHashMap<>(); // immutable, never removed
        private final Map<String, String> branches = new ConcurrentHashMap<>(); // branch -> tip commit id
        private final AtomicInteger ids = new AtomicInteger();
        private volatile String head = "main"; // the checked-out branch

        Repository() {
            Commit root = new Commit("c0", null, "initial", new Snapshot(""));
            commits.put(root.id(), root);
            branches.put("main", root.id());
        }

        /** Commits on top of the branch tip. The tip moves by compare-and-set, like git's ref lock. */
        String commit(String branch, String expectedTip, Snapshot snap, String message) {
            Commit c = new Commit("c" + ids.incrementAndGet(), expectedTip, message, snap);
            commits.put(c.id(), c);
            if (!branches.replace(branch, expectedTip, c.id()))
                throw new StaleBranchException(branch + " moved past " + expectedTip + ": pull and retry");
            return c.id();
        }

        String commit(Snapshot snap, String message) { return commit(head, tip(head), snap, message); }

        String tip(String branch) {
            String id = branches.get(branch);
            if (id == null) throw new IllegalArgumentException("no branch " + branch);
            return id;
        }

        void branch(String name) {
            if (branches.putIfAbsent(name, tip(head)) != null)
                throw new IllegalArgumentException(name + " exists");
        }

        /** Switches HEAD and returns the snapshot to load into the editor. */
        Snapshot checkout(String branch) {
            Snapshot s = commits.get(tip(branch)).snapshot();
            head = branch;
            return s;
        }

        String head() { return head; }

        List<String> log(String branch) {
            List<String> out = new ArrayList<>();
            for (String id = tip(branch); id != null; id = commits.get(id).parent())
                out.add(id + " " + commits.get(id).message());
            return out;
        }

        int depth(String branch) {
            int n = 0;
            for (String id = tip(branch); id != null; id = commits.get(id).parent()) n++;
            return n;
        }

        /** Merge base: the nearest commit both branches share; a three-way merge diffs both sides from it. */
        String mergeBase(String a, String b) {
            Set<String> seen = new HashSet<>();
            for (String id = tip(a); id != null; id = commits.get(id).parent()) seen.add(id);
            for (String id = tip(b); id != null; id = commits.get(id).parent())
                if (seen.contains(id)) return id;
            throw new IllegalStateException("no common ancestor");
        }
    }

    // ---------- the variant: a calculator whose last five operations can be edited ----------
    record Op(char symbol, long operand) {
        long apply(long x) {
            LongBinaryOperator f = switch (symbol) {
                case '+' -> Long::sum;
                case '-' -> (p, q) -> p - q;
                case '*' -> (p, q) -> p * q;
                default -> throw new IllegalArgumentException("unknown op " + symbol);
            };
            return f.applyAsLong(x, operand);
        }

        @Override
        public String toString() { return symbol + "" + operand; }
    }

    /** Older operations are folded into a checkpoint; only the last N stay editable. Every op is O(N). */
    static final class Calculator {
        private final int editable;
        private long checkpoint; // value after every operation that can no longer be edited
        private final List<Op> recent = new ArrayList<>();

        Calculator(long start, int editable) {
            this.checkpoint = start;
            this.editable = editable;
        }

        void apply(Op op) {
            recent.add(op);
            if (recent.size() > editable) checkpoint = recent.remove(0).apply(checkpoint);
        }

        /** k = 1 is the most recent operation. */
        void edit(int k, Op replacement) {
            if (k < 1 || k > recent.size()) throw new IllegalArgumentException("only the last " + editable);
            recent.set(recent.size() - k, replacement);
        }

        void undo() { if (!recent.isEmpty()) recent.remove(recent.size() - 1); }

        long value() {
            long v = checkpoint;
            for (Op op : recent) v = op.apply(v); // replay at most five
            return v;
        }

        List<Op> recent() { return List.copyOf(recent); }
    }

    // ---------- demo ----------
    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) throws InterruptedException {
        Editor ed = new Editor(100);
        ed.apply(new Insert(0, "Hello"));
        ed.apply(new Insert(5, " world"));
        ed.apply(new Insert(5, ","));
        System.out.println("Typed:   " + ed.text());
        ed.undo();
        System.out.println("Undo:    " + ed.text());
        ed.redo();
        System.out.println("Redo:    " + ed.text());
        ed.apply(new Delete(0, 7));
        System.out.println("Delete:  " + ed.text());
        ed.undo();
        ed.undo();
        ed.apply(new Insert(11, "!")); // a new edit clears the redo stack
        System.out.println("Branch:  " + ed.text() + " (redo possible? " + ed.redo() + ")");
        check(ed.text().equals("Hello world!"), "undo/redo");

        Repository repo = new Repository();
        String c1 = repo.commit(ed.save(), "greeting");
        repo.branch("feature");
        ed.restore(repo.checkout("feature"));
        ed.apply(new Insert(ed.text().length(), " Bye."));
        repo.commit(ed.save(), "add farewell");
        ed.restore(repo.checkout("main"));
        ed.apply(new Insert(0, ">> "));
        repo.commit(ed.save(), "add prompt");
        System.out.println("main:    " + ed.text() + "   log " + repo.log("main"));
        System.out.println("feature: " + repo.checkout("feature").text() + "   log " + repo.log("feature"));
        System.out.println("Merge base of main and feature: " + repo.mergeBase("main", "feature"));
        check(repo.mergeBase("main", "feature").equals(c1), "merge base");

        try {
            repo.commit("main", "c0", new Snapshot("old"), "stale"); // someone committed since c0
            throw new AssertionError("stale commit accepted");
        } catch (StaleBranchException e) {
            System.out.println("Rejected: " + e.getMessage());
        }

        // Four threads commit 100 times each to one branch; CAS + retry keeps history a single line.
        repo.checkout("main");
        int before = repo.depth("main");
        ExecutorService pool = Executors.newFixedThreadPool(4);
        CountDownLatch done = new CountDownLatch(4);
        AtomicInteger retries = new AtomicInteger();
        for (int t = 0; t < 4; t++) {
            int author = t;
            pool.submit(() -> {
                for (int i = 0; i < 100; i++) {
                    while (true) {
                        try {
                            String tip = repo.tip("main");
                            repo.commit("main", tip, new Snapshot("w" + author + "-" + i), "edit " + i);
                            break;
                        } catch (StaleBranchException e) {
                            retries.incrementAndGet();
                        }
                    }
                }
                done.countDown();
            });
        }
        done.await();
        pool.shutdown();
        System.out.println("400 concurrent commits: history depth " + before + " -> " + repo.depth("main")
                + ", retries " + (retries.get() > 0 ? "> 0" : "0"));
        check(repo.depth("main") == before + 400, "no lost commits");

        Calculator calc = new Calculator(0, 5);
        for (Op op : List.of(new Op('+', 5), new Op('*', 3), new Op('-', 2), new Op('+', 10), new Op('*', 2),
                new Op('+', 1))) calc.apply(op);
        System.out.println("Calculator: " + calc.recent() + " = " + calc.value());
        check(calc.value() == ((5 * 3 - 2 + 10) * 2 + 1), "calc");
        calc.edit(4, new Op('+', 2)); // change "-2" (4th from last) to "+2"
        System.out.println("Edit 4th from last to +2: " + calc.recent() + " = " + calc.value());
        check(calc.value() == ((5 * 3 + 2 + 10) * 2 + 1), "edit");
        calc.undo();
        System.out.println("Undo last: " + calc.value());
        try {
            calc.edit(6, new Op('+', 0));
        } catch (IllegalArgumentException e) {
            System.out.println("Edit 6th from last: " + e.getMessage());
        }
    }
}

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.

Requirements
  • 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
Clarify first
  • 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.

Command
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.

Editor
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.

Trace
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 vs Command
  • 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.

Repository
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.

Two branches from c1
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() and mergeBase()
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.

Calculator(start, editable = 5)
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.

Moving a branch safely
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.

Extension points
  • 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.

Run it
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.

Follow-ups to expect
  • 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.

In the interview
  • "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."

Interview questions

How do you implement undo and redo?

Model each edit as a Command with execute and undo. Keep an undo stack and a redo stack: applying pushes on undo and clears redo, undo moves a command from undo to redo after reversing it, and redo moves it back after executing it again.

Why does a new edit clear the redo stack?

Redo commands were recorded against a document state that the new edit has replaced, so replaying them could corrupt the text. Clearing them starts a new future; an undo tree is the extension that keeps the abandoned branch reachable.

What is the difference between Command and Memento for undo?

Command stores each change and how to reverse it, which is compact but must replay exactly. Memento stores a snapshot of the whole state, which is simple and robust but uses more memory. Editors often use commands for keystrokes and snapshots for saved versions.

How would you model git-like commits and branches?

A commit is an immutable record with an id, a parent id, a message and a snapshot. A branch is a name mapped to a tip commit id, and head names the current branch. Committing creates a new commit whose parent is the tip, then moves the branch pointer.

How do you find the merge base of two branches?

Collect all ancestors of one tip into a set by following parent pointers, then walk back from the other tip and return the first commit found in the set. A three-way merge then compares both sides against that base.

How do you stop two concurrent commits from losing one?

Commits are immutable, so only the branch pointer is contended. Move it with compare-and-set from the expected tip to the new commit; if it fails, someone else committed first, so re-read the tip, rebuild on it and retry.

How do you build a calculator whose last five operations can be edited?

Keep a checkpoint value and a list of the last five operations. A sixth operation folds the oldest into the checkpoint. Editing replaces one entry, and the value is the checkpoint with the five operations replayed, so every step is constant time.

How do you keep undo history from using too much memory?

Cap the number of commands and drop the oldest from the bottom of a deque, merge consecutive small edits such as typed characters into one command, or keep periodic snapshots plus only the commands since the last one.