A diff is not a comparison. Lay the old file along one axis and the new file along the other: moving right deletes a line, moving down inserts one, and wherever the lines match you move diagonally for free. The best diff is the cheapest path, and Myers finds it by iterating over the edit count rather than over position — can I get there in 0 edits, in 1, in 2 — so the first arrival at the corner is minimal by construction. Nothing checks it afterwards.
Which is the problem, because nothing downstream notices when it stops being minimal either.
Seven algorithms, live, on files you can edit: https://dev48.infy.uk/design/day68-diff-viewer.html
The property everybody tests
assert(applyPatch(oldFile, diff(oldFile, newFile)) === newFile);
A real property, and it catches real bugs. It is also satisfied by this:
function diff(a, b){
return [...a.map(deleteLine), ...b.map(insertLine)]; // "everything changed"
}
Over 6,000 pairs that null diff applies cleanly on 100% of them and puts 10.86× as many changed lines in front of a reviewer as the minimal answer. Six of the seven implementations round-trip perfectly; only the one comparing 32-bit hashes without confirming them fails, on 3.3%. A diff has two jobs — reconstruct the file, and be short — and the suite covers the first.
The oracle that only works on fixtures
Where every line is distinct the minimum has a closed form, minEdits = deletions + insertions, so 6,000 large pairs cost nothing. Then pay a full O(n·m) LCS table on 4,000 pairs of source code. Same algorithms, same oracle logic:
| algorithm | distinct lines, above the minimum | source code, above the minimum |
|---|---|---|
| Myers | 0.0% | 0.0% |
| scan ahead for the next match | 0.0% | 37.1% |
| unique-line anchors | 0.0% | 42.6% |
| delete all, insert all | 100% | 100% |
Nothing changed but the corpus. Real files repeat themselves — a } every few lines, a blank line between functions — and a generated fixture never does. Delete a function header and it stops occurring exactly once on both sides, so it stops being an anchor, and the region it pinned falls back to the crude path: eight edits for a two-line deletion.
The hash version is the one row where "below the minimum" is not blank: 645 of 4,000. No correct diff can report fewer edits than a proven minimum, so it is the cheapest signature there is that two different lines are being treated as the same line. Under a checksum that adds character codes, a + b and b + a are a perfect anagram.
The off-by-one that renders identically
Hunks merge when the gap is small enough, and the threshold is gap > 2 * context: at exactly 2·context the trailing context of one hunk and the leading context of the next meet with nothing left over. Write >= and it splits there. Across 4,000 documents that changes the hunk count on 29.7% of them and the rendered output on none — same lines, same order, each exactly once, and the same 115,234 context lines. Every assertion about what appears on screen passes. The difference is one @@ header.
What the measurement contradicted
My companion claim was that the neighbouring rule — split whenever the gap exceeds one context — is the loud one, hunks overlapping and printing lines twice. It is, 5,975 times over the same documents. But the assertion failed on my exhibit, and the engine was right: at a gap of exactly 2·context every splitting rule lands its hunks adjacent, so the loud bug is invisible at precisely the boundary built to expose the quiet one. Duplication needs ctx < gap < 2·ctx. A fixture tuned for one off-by-one is the worst possible fixture for its neighbour.
7,074,354 assertions on load, 144 more in the verifier. The load-bearing one is the one that has to keep passing:
assert(nuke.applyFail === 0); // <- the point of the whole page
If that ever starts failing, the harness has drifted, not the bug.
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)