Undo looks like a stack of documents. It cannot be one: a snapshot costs a whole document, so sixty edits in a twenty-thousand-character file is 1.2 MB of history for 2.5 KB of actual change, and the ratio gets worse the longer you work. A real history stores inverse patches on two stacks.
Then one predicate is left, and every complaint anybody has had about an undo implementation is that predicate: does this keystroke join the entry on top of the stack, or start a new one? Five clauses answer it.
if (top.kind !== e.kind) return false; // (1) same kind of edit
if (H.moved) return false; // (2) the caret was moved by hand
if (e.t0 - top.t1 > H.idle) return false; // (3) the run went quiet
if (e.inserted.indexOf('\n') >= 0) return false; // (5) a newline
return e.from === top.from + top.inserted.length; // (4) contiguity
Eight machines, one clause each, replayed side by side: https://dev48.infy.uk/design/day71-undo-history.html
The property every undo test asserts is nearly a tautology
Undo until nothing happens, redo the same number of times, assert the text. It is satisfied by 8 of 8 implementations on 100.0% of 700 generated cases — near-tautologically, because on two stacks k pops followed by k pushes is a permutation that has to return, whatever nonsense the entries contain.
Assert the identical round trip on the caret instead and it separates one machine on 700 of 700.
| assertion, on the generated corpus | what it separates |
|---|---|
| undo k, redo k, the text is back | 0 of 8 machines |
| the same round trip, on the caret | 1 of 8, on 700/700 sessions |
canRedo after every operation |
one machine, wrong on 74.5% of ops |
Day 70's lesson was that a realistic corpus is not a concentrated one. This page inverts it. Here the blind corpus is the generated one, blind four separate ways: it never branches, every operation is one clock tick apart, the caret never moves on its own, and a test case is too short to reach a cap. A stale redo branch hands back documents no edit ever produced — caught not by any text comparison but by canRedo, one boolean, wrong on three quarters of a realistic session.
What the measurement contradicted
I drafted contiguity as the core of the merge rule. It is dead code. Counting all the reasons for every refusal rather than only the first, across four corpora and 179,243 operations, contiguity was a reason 11,989 times and the sole reason 0 times. A machine with the clause deleted diverges on nothing, anywhere: 0 differences in text, caret, canUndo or canRedo, in any corpus.
The reason is structural. If the caret is where the last edit left it, the next keystroke is contiguous by construction, and the only things that can move the caret have already tripped a different clause. For one person at a keyboard, contiguity is implied by the other four.
It stops being implied the moment a change does not come from that keyboard. Type abc, let a collaborator insert XY at the top, type d, press undo once. With the clause you get XYabc. Without it you get cd — it deleted the collaborator's text and half of yours. The clause is not there for your keystrokes. It is there for everybody else's.
6,179,960 assertions on load against a snapshot-and-pointer oracle sharing no line with the implementation. One file, inline CSS, no external asset of any kind.
Part of a from-scratch series — one component a day, vanilla JS, one file, dependency-free engine: https://dev48.infy.uk/designfromzero.php
Top comments (0)