Undo/Redo & Structural Sharing
Deep-cloning a 5 MB document on every edit (structuredClone) crashes tabs with Out-of-Memory errors. Structural sharing clones only the ancestor spine from the mutated leaf up to the root, letting past, present, and future stacks share 99% of unchanged objects by reference.
Undo/Redo Stacks with Structural Sharing
Trace copy-on-write path cloning, future-stack truncation, and reference reuse across history.
Document has nodes A (4MB mesh) and B (text). Present points to Root#1.
const history = { past: [], present: root1, future: [] };- pastLen
- 0
- presentRef
- Root#1
- futureLen
- 0
- heapMb
- 4.1
Under the Hood
Structural sharing works like Git commits: editing one file creates new tree nodes only along its parent folders, while sibling folders share the exact same pointers. Keeping unchanged subtrees === identical lets Virtual DOM bail out in $O(1)$ and preserves V8 Hidden Classes.
- Store history as
{ past: State[], present: State, future: State[] }. - On edit, copy only the modified path (
{ ...state, nodes: { ...state.nodes, [id]: nextNode } }), pushpresentontopast, and resetfuture = []. - On
undo(), poppastintopresentand push oldpresentontofuture, zero object cloning required.
function commitEdit(history, nextPresent) {
return {
past: [...history.past.slice(-99), history.present], // Cap stack at 100
present: nextPresent,
future: [], // Clear redo branch on new timeline
};
}Problem Genealogy
- 1990s (Command Pattern
execute()/unexecute()): Saved memory by storing inverse deltas, but writing bug-freeunexecute()methods for every action was notoriously fragile. - 2015 (Persistent Data Structures, Immutable.js): Brought Clojure-style HAMT structural sharing to JS, at the cost of non-plain
.getIn()APIs. - 2018+ (ES6 Proxy Copy-on-Write, Immer): Let developers write plain mutations inside a
produce()draft while emitting structurally shared immutable trees or compact JSON patches.
Production Pitfalls
- Pushing every
mousemoveor keystroke: Recording 60 undo steps per second during a drag floods the stack and forces users to hitCmd+Z60 times to undo one drag; commit only onpointerupor debounce typing bursts. - Forgetting to cap
past.length: An unbounded undo array leaks memory over hours-long editor sessions; slice to a fixed ring buffer (e.g., 100 entries) or switch to inverse JSON patches.
- When not to use Structural Sharing: For 2D pixel buffers or 100k-row typed arrays, copy-on-write still duplicates large
Uint8Arraychunks, store compact inverse command deltas instead.
Connections & Logical Next Steps
Structural sharing snapshots let command logs rewind state in O(1) without cloning the full document.
Structural sharing keeps unchanged subtrees === equal so memoized components skip re-diffing.
Consistent object shapes in cloned path nodes preserve V8 hidden-class inline caches.
Optimistic rollback reverts failed pending mutations, whereas undo/redo tracks user-confirmed history via structural sharing.