Undo / redo and command pattern

coreCommon atAnthropicGoogleMicrosoftMetaRead firstStacksClass design and invariantsPractise in the Sandbox →

Keep two stacks. Every edit is pushed onto undo. Undo pops it, reverses it, and pushes it onto redo; redo does the opposite. Any new edit clears redo, because the future it held no longer follows from the present. Each entry is either a command (a small object that can do and undo itself) or a memento (a copy of the state before the edit). Both make undo and redo O(1) stack operations plus the cost of applying the entry.

The idea in plain words

Think of a trail of breadcrumbs. Each step forward drops a crumb (push to undo). Walking back picks crumbs up and puts them in your pocket (move to redo), so you can walk forward again the same way. But if you walk back three steps and then take a different path, the crumbs in your pocket describe a path you’re no longer on. You throw them away. That’s the redo-clearing rule, and it’s the part people forget.

What goes in each entry is the real design choice:

• A command records what was done: “moved shape 7 by (+5, +2)”. To undo, apply the inverse: move by (−5, −2). Small, but every command needs a correct inverse, and some inverses need extra saved data (“delete line 3” must remember the line’s text).
• A memento records what it looked like before: a copy of the state. To undo, put the copy back. No inverse logic to get wrong, but each entry costs as much as the state.

The names come from the Gang of Four Design Patterns book: Command and Memento.

See it

Make a few edits, undo twice, then make a different edit: the redo stack empties. Switch between storing commands and mementos and compare the memory meter after the same edits. Notice that Clear is the one command that is as big as a memento: undoing it needs everything it removed.

Undo and redo with two stacks

sandbox

history storescommands (deltas)mementos (copies)

add “Drift”remove firstmove last → topclear all

↶ undo↷ redo↺ reset

undo stack0

empty

playlist (the document)2 tracks

0 Intro1 Blue

redo stack0

empty

history size (fields)

0

can_undofalse

can_redofalse

modecommand

Each entry is a small object that knows how to do and undo itself. Most are one field. Clear is the exception: to undo it, it must remember everything it removed.

Make a few edits, undo twice, then make a new edit. Watch what happens to the redo stack.

When to reach for it

The problem says…	What to build
“undo reverts the most recent edit; redo re-applies it”	Two stacks of edits.
“any new edit clears the redo history”	redo.clear() inside the method that records an edit.
“these operations can’t be undone” (cursor moves, selection, reads)	Don’t push them. Decide per method, and write it down.
“after undo, X returns to where it was before the edit”	The entry must also save that X (a cursor, a selection, a timestamp).
“this compound action counts as one edit”	One entry holding several changes: a macro command with sub-commands.
“roll back everything since checkpoint / begin”	The undo stack as a transaction log: undo until the marker.

How it works

1. Pick the entry type. Commands if state is large and edits are small. Mementos if state is small, or inverses are hard to get right.
2. Route every edit through one method (run(cmd) or record()). It applies the edit, pushes the entry onto undo, and clears redo.
3. Undo: pop from undo; reverse it (run the inverse, or restore the memento); push onto redo. Return False or do nothing if empty, as the spec says.
4. Redo: pop from redo; re-apply it; push onto undo. Redo must not clear the redo stack.
5. Edits that change nothing (deleting from an empty document) usually shouldn’t be recorded. Otherwise the user has to press undo for nothing. Check the spec.

Commands, on a canvas of shapes:

Python

history.py

from typing import Protocol

Canvas = dict[str, tuple[int, int]]  # shape id -> (x, y)


class Command(Protocol):
    def do(self, c: Canvas) -> None: ...
    def undo(self, c: Canvas) -> None: ...


class AddShape:
    def __init__(self, sid: str, x: int, y: int) -> None:
        self.sid, self.pos = sid, (x, y)

    def do(self, c: Canvas) -> None:
        c[self.sid] = self.pos

    def undo(self, c: Canvas) -> None:
        del c[self.sid]


class MoveShape:
    def __init__(self, sid: str, dx: int, dy: int) -> None:
        self.sid, self.dx, self.dy = sid, dx, dy  # 1. a delta: tiny, and exactly invertible

    def do(self, c: Canvas) -> None:
        x, y = c[self.sid]
        c[self.sid] = (x + self.dx, y + self.dy)

    def undo(self, c: Canvas) -> None:
        x, y = c[self.sid]
        c[self.sid] = (x - self.dx, y - self.dy)


class History:
    def __init__(self, canvas: Canvas) -> None:
        self.canvas = canvas
        self.undos: list[Command] = []
        self.redos: list[Command] = []

    def run(self, cmd: Command) -> None:
        cmd.do(self.canvas)  # 2. do it, then remember it
        self.undos.append(cmd)
        self.redos.clear()  # 3. a new edit forks history: the old future is gone

    def undo(self) -> bool:
        if not self.undos:
            return False
        cmd = self.undos.pop()
        cmd.undo(self.canvas)  # 4. invert, and keep it for redo
        self.redos.append(cmd)
        return True

    def redo(self) -> bool:
        if not self.redos:
            return False
        cmd = self.redos.pop()
        cmd.do(self.canvas)  # 5. replay, and make it undoable again
        self.undos.append(cmd)
        return True


if __name__ == "__main__":
    h = History({})
    h.run(AddShape("sq", 0, 0))
    h.run(MoveShape("sq", 5, 2))
    assert h.canvas == {"sq": (5, 2)}
    assert h.undo() and h.canvas == {"sq": (0, 0)}
    assert h.redo() and h.canvas == {"sq": (5, 2)}
    h.undo()
    h.run(MoveShape("sq", 0, 9))  # new edit: the undone move can no longer be redone
    assert not h.redo() and h.canvas == {"sq": (0, 9)}
    assert h.undo() and h.undo() and h.canvas == {} and not h.undo()
    print("ok")

TypeScript

history.ts

import assert from "node:assert/strict";

type Canvas = Map<string, [number, number]>; // shape id -> [x, y]

interface Command { do(c: Canvas): void; undo(c: Canvas): void }

class AddShape implements Command {
  constructor(private readonly id: string, private readonly x: number, private readonly y: number) {}
  do(c: Canvas): void { c.set(this.id, [this.x, this.y]); }
  undo(c: Canvas): void { c.delete(this.id); }
}

class MoveShape implements Command { // 1. a delta: tiny, and exactly invertible
  constructor(private readonly id: string, private readonly dx: number, private readonly dy: number) {}
  do(c: Canvas): void { const [x, y] = c.get(this.id)!; c.set(this.id, [x + this.dx, y + this.dy]); }
  undo(c: Canvas): void { const [x, y] = c.get(this.id)!; c.set(this.id, [x - this.dx, y - this.dy]); }
}

class History {
  private readonly undos: Command[] = [];
  private readonly redos: Command[] = [];
  constructor(readonly canvas: Canvas) {}

  run(cmd: Command): void {
    cmd.do(this.canvas); // 2. do it, then remember it
    this.undos.push(cmd);
    this.redos.length = 0; // 3. a new edit forks history: the old future is gone
  }

  undo(): boolean {
    const cmd = this.undos.pop();
    if (!cmd) return false;
    cmd.undo(this.canvas); // 4. invert, and keep it for redo
    this.redos.push(cmd);
    return true;
  }

  redo(): boolean {
    const cmd = this.redos.pop();
    if (!cmd) return false;
    cmd.do(this.canvas); // 5. replay, and make it undoable again
    this.undos.push(cmd);
    return true;
  }
}

const h = new History(new Map());
h.run(new AddShape("sq", 0, 0));
h.run(new MoveShape("sq", 5, 2));
assert.deepEqual(h.canvas.get("sq"), [5, 2]);
assert.ok(h.undo()); assert.deepEqual(h.canvas.get("sq"), [0, 0]);
assert.ok(h.redo()); assert.deepEqual(h.canvas.get("sq"), [5, 2]);
h.undo();
h.run(new MoveShape("sq", 0, 9)); // new edit: the undone move can no longer be redone
assert.ok(!h.redo()); assert.deepEqual(h.canvas.get("sq"), [0, 9]);
assert.ok(h.undo() && h.undo() && h.canvas.size === 0 && !h.undo());
console.log("ok");

C#

history.cs

var h = new History(new Dictionary<string, (int X, int Y)>());
h.Run(new AddShape("sq", 0, 0));
h.Run(new MoveShape("sq", 5, 2));
if (h.Canvas["sq"] != (5, 2)) throw new Exception("move");
if (!h.Undo() || h.Canvas["sq"] != (0, 0)) throw new Exception("undo");
if (!h.Redo() || h.Canvas["sq"] != (5, 2)) throw new Exception("redo");
h.Undo();
h.Run(new MoveShape("sq", 0, 9)); // new edit: the undone move can no longer be redone
if (h.Redo() || h.Canvas["sq"] != (0, 9)) throw new Exception("redo should be cleared");
if (!(h.Undo() && h.Undo() && h.Canvas.Count == 0 && !h.Undo())) throw new Exception("undo to empty");
Console.WriteLine("ok");

interface ICommand { void Do(Dictionary<string, (int X, int Y)> c); void Undo(Dictionary<string, (int X, int Y)> c); }

record AddShape(string Id, int X, int Y) : ICommand
{
    public void Do(Dictionary<string, (int X, int Y)> c) => c[Id] = (X, Y);
    public void Undo(Dictionary<string, (int X, int Y)> c) => c.Remove(Id);
}

record MoveShape(string Id, int Dx, int Dy) : ICommand // 1. a delta: tiny, and exactly invertible
{
    public void Do(Dictionary<string, (int X, int Y)> c) => c[Id] = (c[Id].X + Dx, c[Id].Y + Dy);
    public void Undo(Dictionary<string, (int X, int Y)> c) => c[Id] = (c[Id].X - Dx, c[Id].Y - Dy);
}

class History(Dictionary<string, (int X, int Y)> canvas)
{
    readonly Stack<ICommand> undos = new(), redos = new();
    public Dictionary<string, (int X, int Y)> Canvas => canvas;

    public void Run(ICommand cmd)
    {
        cmd.Do(canvas);  // 2. do it, then remember it
        undos.Push(cmd);
        redos.Clear();   // 3. a new edit forks history: the old future is gone
    }

    public bool Undo()
    {
        if (!undos.TryPop(out var cmd)) return false;
        cmd.Undo(canvas); // 4. invert, and keep it for redo
        redos.Push(cmd);
        return true;
    }

    public bool Redo()
    {
        if (!redos.TryPop(out var cmd)) return false;
        cmd.Do(canvas);   // 5. replay, and make it undoable again
        undos.Push(cmd);
        return true;
    }
}

Mementos, on a small settings object, with a history limit:

Python

settings.py

from collections import deque


class Settings:
    """Undo by snapshot: save a copy of the whole state before each change."""

    def __init__(self, limit: int = 3) -> None:
        self.state: dict[str, str] = {"theme": "light", "font": "serif"}
        self.past: deque[dict[str, str]] = deque(maxlen=limit)  # 1. bounded: oldest drop off

    def change(self, key: str, value: str) -> None:
        self.past.append(dict(self.state))  # 2. memento = a copy, taken *before* the change
        self.state[key] = value

    def undo(self) -> bool:
        if not self.past:
            return False
        self.state = self.past.pop()  # 3. restore wholesale: no inverse logic needed
        return True


if __name__ == "__main__":
    s = Settings(limit=3)
    for v in ["dark", "solar", "night", "dawn"]:
        s.change("theme", v)
    assert s.state["theme"] == "dawn" and len(s.past) == 3  # the first memento was dropped
    assert s.undo() and s.undo() and s.undo()
    assert s.state["theme"] == "dark"  # can't go back to "light": history limit
    assert not s.undo()
    print("ok")

TypeScript

settings.ts

import assert from "node:assert/strict";

type State = Readonly<Record<string, string>>;

/** Undo by snapshot: save a copy of the whole state before each change. */
class Settings {
  state: State = { theme: "light", font: "serif" };
  readonly past: State[] = [];
  constructor(private readonly limit = 3) {}

  change(key: string, value: string): void {
    this.past.push(this.state); // 2. memento: state is replaced, never mutated, so the old object is safe
    if (this.past.length > this.limit) this.past.shift(); // 1. bounded: oldest drop off
    this.state = { ...this.state, [key]: value };
  }

  undo(): boolean {
    const prev = this.past.pop();
    if (!prev) return false;
    this.state = prev; // 3. restore wholesale: no inverse logic needed
    return true;
  }
}

const s = new Settings(3);
for (const v of ["dark", "solar", "night", "dawn"]) s.change("theme", v);
assert.equal(s.state.theme, "dawn");
assert.equal(s.past.length, 3); // the first memento was dropped
assert.ok(s.undo() && s.undo() && s.undo());
assert.equal(s.state.theme, "dark"); // can't go back to "light": history limit
assert.ok(!s.undo());
console.log("ok");

C#

settings.cs

var s = new Settings(limit: 3);
foreach (var v in new[] { "dark", "solar", "night", "dawn" }) s.Change("theme", v);
if (s.State["theme"] != "dawn" || s.PastCount != 3) throw new Exception("first memento should drop");
if (!(s.Undo() && s.Undo() && s.Undo())) throw new Exception("three undos");
if (s.State["theme"] != "dark") throw new Exception("history limit reached at 'dark'");
if (s.Undo()) throw new Exception("nothing left");
Console.WriteLine("ok");

// Undo by snapshot: save a copy of the whole state before each change.
class Settings(int limit)
{
    public Dictionary<string, string> State { get; private set; } = new() { ["theme"] = "light", ["font"] = "serif" };
    readonly LinkedList<Dictionary<string, string>> past = new(); // 1. bounded deque
    public int PastCount => past.Count;

    public void Change(string key, string value)
    {
        past.AddLast(new Dictionary<string, string>(State)); // 2. memento = a copy, taken before
        if (past.Count > limit) past.RemoveFirst();         // oldest drops off
        State[key] = value;
    }

    public bool Undo()
    {
        if (past.Last is not { } last) return false;
        past.RemoveLast();
        State = last.Value; // 3. restore wholesale: no inverse logic needed
        return true;
    }
}

A memento must not share mutable state

If a memento is a reference to the same dict the app keeps editing, every saved “copy” changes along with it and undo restores nothing. Copy on save (Python dict(state), C# new Dictionary<,>(state)), or make the state immutable and replace it instead of mutating it (the TypeScript version above).

What it costs

With state size S and an edit that touches d items:

	Record an edit	Undo / redo	Memory per entry	Risk
Command (delta)	O(d)	O(d) to apply the inverse	O(d)	a wrong inverse silently corrupts state
Memento (full copy)	O(S) to copy	O(1) swap, or O(S) if copied again	O(S)	none in the logic; memory blows up
Memento of the touched part	O(d)	O(d)	O(d)	must know exactly what’s touched
Persistent / immutable state	O(log S) path copy	O(1) pointer swap	O(log S)	needs persistent structures

The stacks themselves are O(1) per push and pop. Everything interesting is in the entry.

For a text editor with a 1 MB document and 1,000 history entries, full mementos are a gigabyte. Commands such as “insert ‘abc’ at 120” are bytes. That is why real editors store commands, sometimes merged (“typing ‘hello’ is one undo step, not five”).

Variations you’ll meet

• Macro commands. A list of commands that undo in reverse order. “Duplicate and move” = add + move.
• Coalescing. Merge consecutive small edits (typed characters, drags) into one entry if they’re close in time or position.
• Bounded history. Keep the last N entries. A deque or ring buffer drops the oldest.
• Transactions. begin pushes a marker; rollback undoes until the marker; commit drops the marker (and with it the ability to roll back). Nested transactions are nested markers, or a stack of per-level change logs.
• Undo tree. Instead of clearing redo, keep the abandoned branch so the user can reach it later (Vim’s undo tree, Emacs’s undo ring).
• Collaborative undo. With several users, “undo my last edit” must transform it against everyone else’s later edits (operational transformation, CRDTs). Well beyond an interview, but worth naming.

Pitfalls

• Forgetting to clear redo on a new edit. Redo then re-applies an edit to a state it was never meant for.
• Clearing redo on redo. Redo is not a “new edit”. Only route genuinely new edits through the clearing path.
• Inverse that loses information. “Remove shape 7” can’t be undone without shape 7’s data. Save it in the command when it runs, not when it’s created (the data isn’t known until then).
• Recording no-op edits. A delete at position 0 changes nothing. Pushing it means one undo press does nothing visible.
• Undoing the wrong side state. If the spec says the cursor returns to where it was before the edit, the entry must store that cursor position. The document alone isn’t enough.
• Mutable mementos (see the caution above).

In the interview

• Ask: “Which operations are undoable? Does a no-op count as an edit? Where does the cursor (or other side state) go after undo and after redo? Is there a history limit?”
• Say: “Two stacks. Every edit goes through one method that pushes onto undo and clears redo. Undo moves an entry from undo to redo; redo moves it back.”
• Justify the entry type with numbers: “The document can be large and edits are small, so I’ll store commands with their inverse data rather than full copies.”
• Test the sequence that catches most bugs: edit, edit, undo, undo, redo, new edit, redo (should do nothing), undo, undo.
• Expect follow-ups: group edits into one undo step, bounded history, transactions with rollback, and “make this work for two users”.

Check yourself

Check yourself

pick one

Edits A, B, C. Then undo, undo. Then a new edit D. What's on the undo and redo stacks (bottom to top)?

Aundo: A, D. redo: emptyBundo: A, D. redo: C, BCundo: A, B, C, D. redo: emptyDundo: D. redo: B, C

Check yourself

pick one

A 'remove shape' command stores only the shape id. Why can't it be undone correctly?

ABecause deletes can never be undoneBBecause the inverse needs the deleted text, which the command never savedCBecause the id might not exist

Check yourself

pick one

State is a 5-field settings object; edits are rare; correctness matters most. Which entry type is the better default?

ACommands with hand-written inversesBMementos: a copy of the 5 fields before each editCNo history; recompute from defaults

Practice on your own

These are classic exercises, not gym questions:

• A drawing app: add, move, recolor and delete shapes, with undo/redo. Make “delete” undoable without mementos.
• A calculator with a running total and undo of the last N operations, including a non-invertible one (multiply by zero). How do you undo it?
• Group consecutive “type a character” commands into one undo step when they are within 1 second of each other.
• Implement begin / rollback / commit on top of an undo stack using a marker.

Go deeper

• Gamma, Helm, Johnson, Vlissides, Design Patterns (1994): Command and Memento. Readable summaries: Command and Memento on refactoring.guru.
• Python collections.deque with maxlen for bounded history; .NET Stack<T>.TryPop.
• Vim help, :help undo-tree: branching history instead of discarding redo.

Related

StacksThe data structure doing all the work.

Snapshots, backup and restoreMementos at the scale of a whole store.

State machinesReplaying events to rebuild state.

Designing for the next requirementUndo is a classic level-3 add-on.