When Undo/Redo Stops Scaling: Transactional History for Object Graphs
Full-document snapshots are a valid undo/redo boundary—until a large, shared object graph makes every small edit pay for the whole document. Transactional copy-on-write history narrows that work, but introduces a real management cost.
- .NET
- Undo/Redo
- Object Graphs
- Copy-on-Write
- Transactions
- Performance
Snapshots were a correct first boundary
A snapshot-based undo system has an important property: it is easy to reason about. Capture the document before or after a successful edit, place that state in history, and restore it when the user moves backward or forward. New editing commands do not need a custom inverse operation, and it is difficult to omit one changed field when the entire persisted state is the boundary.
For small documents, infrequent edits, or models that serialize cheaply, that simplicity can be the right design. Replacing snapshots only because command objects look more sophisticated would exchange a compact, reliable mechanism for unnecessary architecture.
The decision changed in a production-oriented desktop editor because document size and graph complexity changed the economics. A small interaction could force the application to copy, purge, serialize, compress, hash, retain, and later reconstruct a much larger scene. The approach remained logically correct; the unit of work had become too broad.
The scaling question is N versus K
Let N represent the size of the document graph and K the part affected by one operation. A full snapshot performs work proportional to N even when K is one node. A copy-on-write transaction aims to perform history work proportional to K, plus the bookkeeping required to preserve graph invariants.
That difference becomes meaningful when N is large, edits are frequent, and most operations touch a narrow subset. It becomes less compelling when edits replace most of the document, snapshots are structurally shared already, or the graph is small enough that broad copying is not visible to the user.
The public teaching model makes this boundary measurable without claiming a universal speedup. For a synthetic 10,000-node document and twenty single-node edits, its snapshot implementation records 210,000 node copies: the initial state plus one complete state per edit. Its transactional implementation records twenty working-node copies. These are deterministic copy counts for the sample, not wall-clock production benchmarks.
History records operations and deltas instead of complete worlds
The replacement architecture keeps the familiar undo and redo stacks, but changes what each entry owns. An entry can represent added nodes, removed nodes, replacements, collection changes, layer-property changes, or a composite of several commands that must behave as one user action.
A command does not need to know about the complete application. It needs enough before-and-after state to reverse and reapply its own boundary. Collection operations can retain placement indexes. Property operations can retain compact value objects. A composite entry can preserve ordering when one interaction changes several related surfaces.
csharp
IHistoryCommand.cs
A neutral contract: the stack remains simple while each command owns the state required for its mutation boundary.
public interface IHistoryCommand<TDocument>
{
void Undo(TDocument document);
void Redo(TDocument document);
}
public sealed class CompositeCommand<TDocument>(
IReadOnlyList<IHistoryCommand<TDocument>> commands)
: IHistoryCommand<TDocument>
{
public void Undo(TDocument document)
{
for (int index = commands.Count - 1; index >= 0; index--)
commands[index].Undo(document);
}
public void Redo(TDocument document)
{
foreach (var command in commands)
command.Redo(document);
}
}Copy-on-write protects the original graph until commit
Command objects solve storage granularity, but a shared object graph adds another problem. Mutating an original node in place can leak a half-completed edit into aliases held elsewhere. Deep-copying the whole graph avoids that leak but recreates the original cost.
A graph-mutation transaction takes a middle path. The caller declares the affected roots, the transaction creates mapped working copies for that boundary, and editing code changes only those mapped objects. Commit turns the before-and-after states into one history entry. Closing without commit restores the original state.
The affected set is part of the contract. If an operation can change three roots but declares only two, the history entry is incomplete. Making mutation go through Map is therefore more than an optimization API: it makes an otherwise implicit ownership rule visible and testable.
csharp
MoveSelection.cs
Public-safe shape of the transaction. The production model, types, and resource rules are deliberately omitted.
using var change = history.BeginMutation(affectedNodeIds);
foreach (Guid id in affectedNodeIds)
{
CanvasNode editable = change.Map(id);
editable.X += offsetX;
editable.Y += offsetY;
}
bool isValid = affectedNodeIds.All(id => change.Map(id).X >= 0);
if (!isValid)
return; // Dispose restores the original nodes.
change.Commit();A transaction defines failure semantics
The transaction boundary aligns history with the user's intent rather than with individual property assignments. A drag may update coordinates many times, but it should normally become one undo step. A multi-part edit may change geometry, metadata, layers, and derived state, but it should either commit as one coherent entry or restore the original graph.
This is also why opening a history transaction on every mouse-move event is the wrong granularity. Begin once when the interaction starts, mutate mapped working copies while it continues, and commit once when the operation becomes valid. Cancellation and exceptions must leave no partial history entry behind.
The management cost is the price of narrower work
Snapshot history centralizes complexity inside capture and restore. Transactional history distributes responsibility across the history engine and every editing workflow. That is the main disadvantage, and it should be treated as a lifecycle cost rather than a one-time refactor.
- Every operation must declare all affected roots, including indirect graph changes.
- Editing code must mutate mapped working copies instead of stale original references.
- New command types need correct inverse ordering and redo behavior.
- Shared resources need retention, cleanup, and identity rules across the whole history window.
- Long interactions need one transaction rather than a stream of accidental history entries.
- Asynchronous work must update or cancel the intended entry without corrupting stack order.
- Derived data, visual caches, selection state, and domain state need an explicit post-restore refresh policy.
- Every new editor feature must be reviewed for undo, redo, rollback, and graph-identity coverage.
Asynchronous completion makes history temporal
Some operations add a placeholder immediately and finish expensive work later. If history records only the placeholder, redo may restore an incomplete object. If the completion creates a second entry, one user action becomes two unrelated steps. If the user undoes before completion, a late callback can update an entry that no longer belongs to the current timeline.
One solution is for the initial commit to return a narrow update token. Successful completion replaces the after-state owned by that exact command. Cancellation removes or invalidates it. The token becomes single-use, and the history manager verifies that the target entry still belongs to the active branch before accepting an update.
This mechanism is powerful but adds another management contract. If the product does not have asynchronous edits, do not add it preemptively. If it does, make temporal ownership explicit instead of letting callbacks reach into a global stack by index.
Choose the simpler boundary until scale disproves it
Snapshot history and command-based history are not competing ideologies. They optimize different constraints. Snapshots favor implementation simplicity and broad correctness. Commands, deltas, and copy-on-write transactions favor narrow work and control over large graphs, while demanding more design discipline from every mutation path.
Start with the simplest boundary that is correct for the document. Measure capture cost, allocation pressure, history size, restore latency, edit frequency, and typical mutation size. Move to a narrower architecture when those measurements show that the document—not the user's edit—has become the dominant unit of work.
The important architectural change is not replacing one stack implementation with another. It is accepting that performance and management move in opposite directions: the less state history copies automatically, the more precisely the application must describe what changed and who owns it.
Share