In a two-stack undo/redo design, why must a new user action clear the redo stack?

## The model Undo/redo in a vector-graphics editor is the textbook two-stack pair, and it is worth stating the whole contract before the failure mode, because the failure mode is a consequence of it. The editor keeps a linear history of user actions. Two stacks divide it at the current position: - the **undo stack** holds everything already applied, most recent on top; - the **redo stack** holds everything that has been undone and could be re-applied, most recently undone on top. Three operations move entries between them: 1. **New action** — apply it, push it onto the undo stack, and clear the redo stack. 2. **Undo** — pop from the undo stack, apply the inverse, push the entry onto the redo stack. 3. **Redo** — pop from the redo stack, re-apply the entry, push it back onto the undo stack. Step 1's second half is the rule people forget, and it is the whole question. ## Why clearing is forced, not stylistic Every redo entry carries an unwritten precondition: *the document is in exactly the state this entry was undone from*. That is what makes re-applying it meaningful. Undo and redo are inverses only along one timeline. Suppose an illustrator draws a rectangle, applies a gradient to it, then undoes twice. The redo stack now holds "apply gradient" and above it nothing else; the canvas is empty. Instead of redoing, the illustrator draws a circle. The timeline has just **branched**: the past everyone agreed on ends at the empty canvas, and history now continues down a different path. The entry "apply gradient to the rectangle" still sits in the redo stack, but the rectangle it refers to no longer exists. If the redo entry is kept and later replayed, one of three things happens, in increasing order of nastiness: it fails cleanly because the target cannot be resolved; it does nothing and leaves the user's redo command silently inert; or — worst and most common — the identifier it stored has been reused by the new object, and the gradient lands on the circle. The user sees a change they never made, with no action of theirs to blame. This class of bug is hard to reproduce from a report because it requires the specific undo-then-diverge sequence. The deeper reason is representational. Two linear stacks can express exactly one sequence. A branch needs a tree, and if you keep the abandoned entries you have a data structure making a promise the model cannot keep. Clearing is the model telling the truth. ## The same shape elsewhere Back/forward navigation is this design under a different name: a back stack of visited locations and a forward stack of locations stepped back past. Going back moves an entry from one to the other; going forward moves it back. Following a **new** link while sitting several steps back empties the forward stack for exactly the reason above — the future you had stepped out of is no longer the future you are in. Users have internalised this so thoroughly that a product violating it feels broken, even though most could not state the rule. ## What entries should hold The stacks store actions, and there are two families: - **Snapshots** — a copy of the affected state before and after. Trivially correct, trivially reversible, and expensive: on a large document the undo stack becomes the biggest object in the process. Structural sharing between snapshots reclaims much of that. - **Commands** — a description of the change plus enough information to invert it ("moved these three shapes by this offset", "set fill from old value to new"). Compact, but every command type needs a correct inverse, and one wrong inverse corrupts the document in a way that only shows up several undos later. Most real editors mix them: commands for ordinary edits, a snapshot checkpoint for operations that are hard to invert, such as a filter over pixels. ## The judgment layer Three decisions come up in any real implementation and are worth raising unprompted. - **Granularity and coalescing.** One keystroke per undo entry is unusable; users expect a word, a drag gesture, or a burst of edits within a short window to undo as a unit. Coalescing happens when the entry is pushed, and it is a product decision as much as a technical one. - **Bounding.** An unbounded undo stack is an unbounded memory commitment. Capping depth, or capping total bytes and evicting the oldest entries from the bottom, keeps the ceiling predictable — note that this eviction is from the *bottom*, which a plain stack interface does not offer, so the underlying container usually needs access at both ends. - **Scope.** Not everything belongs in history. Selection changes, scroll position and view zoom generally should not be undoable, while document mutations must be. Getting this wrong produces the common complaint that undo "does nothing" — it undid a selection. ## Beyond two stacks If branch history genuinely matters, the honest answer is a different structure: a history tree or a persistent version graph where an undo followed by a new action creates a sibling branch rather than discarding one. It is strictly more powerful and strictly more expensive — in memory, in the interface needed to let a user navigate branches, and in the team's ongoing cost of maintaining it. The reason two stacks dominate is that the linear model matches what users already expect, and the branch they lost was one they had explicitly stepped away from.