Two-stack inverse Undo/Redo

Definition

This is the history (edit record) model to use when you want Ctrl+Z (undo) and Ctrl+Shift+Z (redo) in an editor. Instead of storing each edit whole, you record only a pair — "the operation going forward" and "the opposite operation that reverses it" — and then you can shuttle state back and forth between two stacks (one for undo, one for redo).

More precisely, two-stack inverse undo/redo is a history model that records an edit as a pair of a forward operation (do) and a backward operation (undo/inverse), and moves that pair between two stacks, the undo stack and the redo stack. The inverse means the opposite edit that exactly reverses some edit — e.g., the inverse of "insert 'a' at position 3" is "delete the 'a' at position 3." You shuttle state via the inverse of commands (events) rather than stacking full state snapshots (a whole copy of the document at that instant). It's the same lineage as execute / unexecute in the GoF Command pattern (a classic design pattern that treats an edit as a single "command object" that can be executed/undone).

Why it matters

For large state like a document · canvas · form, copying the whole document per edit and stacking it is costly and easily breaks the structural-sharing · memoization (an optimization that caches values to avoid recomputation) contract. If every edit is already expressed as a "patch (a change fragment that partially modifies state) / command," then computing the inverse alongside it at that single apply gateway (the one apply function every edit must pass through) makes undo nearly free. Without a gateway, you have to build the recording gateway before the undo UI.

How it works

1. When a user edit passes the apply gateway, compute do and inverse simultaneously.
2. Push the entry { undo: inverse, redo: do } onto the undo stack and empty the redo stack (a new branch invalidates the future).
3. Undo: pop from the undo stack → apply undo → push the same entry onto the redo stack.
4. Redo: pop from the redo stack → apply redo → push it back onto the undo stack.
5. During history replay, don't record again, and also turn off automatic normalizers (logic that auto-corrects the document to the rules after an edit) like the trailing node (a rule such as always keeping the document ending with an empty paragraph). Break this and the stack pollutes itself, or normalization after undo changes the state so redo diverges.

Practical application

type Entry = { undo: Patch[]; redo: Patch[] };

const undoStack: Entry[] = [];
const redoStack: Entry[] = [];

function applyUserEdit(patches: Patch[]) {
  const inverse = computeInverse(patches);
  applyRaw(patches); // normalizer on, record path
  undoStack.push({ undo: inverse, redo: patches });
  redoStack.length = 0;
}

function undo() {
  const entry = undoStack.pop();
  if (!entry) return;
  applyRaw(entry.undo, { record: false, normalize: false });
  redoStack.push(entry);
}

function redo() {
  const entry = redoStack.pop();
  if (!entry) return;
  applyRaw(entry.redo, { record: false, normalize: false });
  undoStack.push(entry);
}

When an inline editor (session history) and a document-tree history coexist, if the lower keymap (a mapping that ties key input to a specific action) has nothing to handle, return false to bubble (an event propagating from lower to upper) the event to the upper handler.

Tradeoffs

• Smaller and faster in memory than a snapshot stack, but it needs a correct inverse for every operation. If the inverse is wrong, state breaks silently.
• Invariants (always ending with an empty paragraph, etc.) and history must be mutually exclusive. If you run the invariant on the history path too, redo diverges from the computed state.

When not to use

• When edits mutate state directly without a gateway — the inverse can't be trusted.
• When multi-user concurrent editing is the main thing, as with OT/CRDT (collaborative algorithms that merge multiple users' concurrent edits without conflict) — a local two-stack alone has different composition rules from remote operations.
• When state is small and a snapshot is simpler (a few settings toggles) — a snapshot stack is enough.

Common mistakes

• Record stays on during the undo path too, so the stack re-stacks itself.
• A normalizer like trailing-block changes the state after undo, collapsing redo.
• Not emptying the redo stack after a new edit, leaving a "future" behind.
• An inline editor and the document history contend over the same key (e.g., Mod-z) and overwrite each other.

Related concepts

• focused-guest-editor — the typical backdrop for layering an inline guest session history and a document host history.