The Diff Keeps a Furthest Frontier
A file diff is easy to use and surprisingly easy to misunderstand.
When it says:
- cache = off
+ cache = on
it is not claiming to understand configuration semantics. It is producing a small script that turns one sequence of tokens into another sequence of tokens. The tokens might be lines, words, characters, AST nodes, or something else. The classic problem is narrower still:
delete tokens from A
insert tokens from B
keep equal tokens in order
No substitution operation is needed. A replacement is just a delete followed by an insert.
Myers’ 1986 paper frames this as the dual of longest common subsequence: finding a shortest edit script and finding a longest common subsequence are two views of the same path through an edit graph.1 The algorithm is famous because it is fast when the two sequences are similar. If:
\[N = |A| + |B| \quad\text{and}\quad D = \text{length of the shortest insert/delete script},\]then the frontier algorithm runs in \(O(ND)\) time. Small change, small \(D\), small search.
That is exactly the workload a file comparison tool hopes for.
The Edit Graph Is The Ledger
Put the old sequence on the horizontal axis and the new sequence on the vertical axis. A point \((x, y)\) means:
we have consumed A[0..x)
we have consumed B[0..y)
From that point there are three possible kinds of edge:
right delete A[x]
down insert B[y]
diagonal keep A[x] == B[y]
The diagonal edge is available only when the next tokens are equal. It costs zero edit operations because keeping an equal token does not appear in the patch. Horizontal and vertical edges cost one.
So a shortest diff is a path from \((0,0)\) to \((|A|, |B|)\) with the fewest non-diagonal edges.
If a path keeps \(L\) diagonal tokens, then it spends:
\[D = |A| + |B| - 2L\]insert/delete edits. This is the LCS connection: maximizing the number of kept diagonal edges is the same as minimizing the number of horizontal and vertical edges.
A full dynamic-programming table can compute that. Myers’ algorithm asks for less.
Store The Furthest Point Per Diagonal
Number a diagonal by:
\[k = x - y.\]Every delete moves to diagonal \(k+1\). Every insert moves to diagonal \(k-1\). Every run of equal tokens stays on the same diagonal. Myers calls such a maximal run of diagonal edges a snake.
Now fix an edit budget \(d\). Instead of storing every reachable point, store only this:
V[k] = the largest x coordinate reachable on diagonal k
using exactly d insert/delete edits,
after greedily following equal-token diagonals
For the next layer, each diagonal can be reached from one of two neighbors:
from k-1: delete one old token, then snake
from k+1: insert one new token, then snake
Keep whichever reaches the larger \(x\) coordinate. If it reaches farther along the same diagonal, it dominates the shorter prefix because the future choices on that diagonal see the same suffixes with more input already consumed.
This gives the search loop:
for d = 0, 1, 2, ...
for k = -d, -d+2, ..., d
arrive from k-1 or k+1
follow the diagonal snake while tokens match
remember the furthest x on diagonal k
stop if the frontier reaches (|A|, |B|)
The first \(d\) that reaches the lower-right corner is the shortest edit script length. Earlier layers have tried every path with fewer edits.
The implementation below stores the whole frontier trace so it can reconstruct and draw one shortest path. A production implementation can use less memory when it only needs the distance, and Myers also gives a divide-and-conquer variation based on middle snakes.2
The Browser Lab
The lab builds the furthest-reaching frontier, reconstructs a shortest script, and checks the result against an ordinary dynamic-programming LCS oracle. The orange points are the selected frontier layer. Purple segments are snakes. Green is the final kept-token path; red and blue are deletes and inserts.
The tie break changes which shortest script is drawn when two predecessors reach the same furthest point. It should not change the edit distance.
In the default example, the old sequence has 7 tokens and the new sequence has
- The LCS keeps 7 tokens, so the shortest script has:
edit. The frontier reaches the lower-right corner at layer 1.
Switch to moved block. The example has no semantic move operation. It is a pure insert/delete diff, so reordering a pair of lines appears as deletions plus insertions. The oracle reports edit distance 4 and LCS length 5. That is not a bug; it is the cost model.
Switch to config file. The tokens look like key-value updates, but exact line equality only keeps two lines. The shortest insert/delete script length is
- A configuration-aware diff could do better for human review, but it would be solving a different problem.
Reproducibility Check
The browser file is also a CommonJS module:
node - <<'NODE'
const lab = require("./assets/js/myers-diff-lab.js");
const EXPECTED_CHECKS = [
{ name: "distance-matches-dp", passed: true },
{ name: "lcs-matches-dp", passed: true },
{ name: "script-replays-new-sequence", passed: true },
{ name: "edit-count-equals-distance", passed: true },
{ name: "equal-count-equals-lcs", passed: true },
{ name: "path-starts-at-origin", passed: true },
{ name: "path-ends-at-target", passed: true },
{ name: "path-steps-monotone", passed: true },
{ name: "equal-ops-match-tokens", passed: true }
];
const EXPECTED_TOTALS = {
namedRows: 10,
exhaustiveBinaryCases: 3969,
passed: 11,
total: 11,
passedChecks: 35811,
totalChecks: 35811
};
const EXPECTED_BY_TIE = [
"delete:5 cases:maxD=8:5/5 passed:45/45 checks",
"insert:5 cases:maxD=8:5/5 passed:45/45 checks"
];
const EXPECTED_EXHAUSTIVE = {
checked: 3969,
failedChecks: 0,
passed: true,
passedChecks: 35721,
totalChecks: 35721
};
const EXPECTED_CASE_ROWS = [
"refactor/delete:small refactor:7->8:d=1:lcs=7:layers=2:ops=8:9/9:true",
"refactor/insert:small refactor:7->8:d=1:lcs=7:layers=2:ops=8:9/9:true",
"moved/delete:moved block:7->7:d=4:lcs=5:layers=5:ops=9:9/9:true",
"moved/insert:moved block:7->7:d=4:lcs=5:layers=5:ops=9:9/9:true",
"repeated/delete:repeated tokens:8->7:d=3:lcs=6:layers=4:ops=9:9/9:true",
"repeated/insert:repeated tokens:8->7:d=3:lcs=6:layers=4:ops=9:9/9:true",
"sentence/delete:sentence edit:8->8:d=4:lcs=6:layers=5:ops=10:9/9:true",
"sentence/insert:sentence edit:8->8:d=4:lcs=6:layers=5:ops=10:9/9:true",
"config/delete:config file:6->6:d=8:lcs=2:layers=9:ops=10:9/9:true",
"config/insert:config file:6->6:d=8:lcs=2:layers=9:ops=10:9/9:true"
];
function sameJson(actual, expected) {
return JSON.stringify(actual) === JSON.stringify(expected);
}
function rowDrifts(actualRows, expectedRows) {
const drifts = [];
const rows = Math.max(actualRows.length, expectedRows.length);
for (let index = 0; index < rows; index += 1) {
const actual = index < actualRows.length ? actualRows[index] : null;
const expected = index < expectedRows.length ? expectedRows[index] : null;
if (!sameJson(actual, expected)) {
drifts.push({ index, actual, expected });
}
}
return drifts;
}
const audit = lab.auditMyersDiff();
const auditShape = {
namedRows: audit.cases.length,
exhaustiveBinaryCases: audit.exhaustiveBinaryCases,
passed: audit.passed,
total: audit.total,
passedChecks: audit.passedChecks,
totalChecks: audit.totalChecks
};
const byTieRows = audit.byTie.map((row) =>
`${row.tie}:${row.cases} cases:maxD=${row.maxDistance}:` +
`${row.passed}/${row.cases} passed:${row.passedChecks}/${row.totalChecks} checks`
);
const exhaustiveShape = {
checked: audit.exhaustive.checked,
failedChecks: audit.exhaustive.failedChecks.length,
passed: audit.exhaustive.passed,
passedChecks: audit.exhaustive.passedChecks,
totalChecks: audit.exhaustive.totalChecks
};
const caseRows = audit.cases.map((row) =>
`${row.example}/${row.tie}:${row.label}:${row.oldLength}->${row.newLength}:` +
`d=${row.distance}:lcs=${row.lcsLength}:layers=${row.layers}:` +
`ops=${row.operations}:${row.passedChecks}/${row.totalChecks}:${row.passed}`
);
const checkRows = audit.cases.map((row) => ({
example: `${row.example}/${row.tie}`,
checks: row.checks.map((check) => ({
name: check.name,
passed: check.passed
}))
}));
const expectedCheckRows = EXPECTED_CASE_ROWS.map((row) => ({
example: row.split(":")[0],
checks: EXPECTED_CHECKS
}));
const byTieDrifts = rowDrifts(byTieRows, EXPECTED_BY_TIE);
const caseRowDrifts = rowDrifts(caseRows, EXPECTED_CASE_ROWS);
const checkRowDrifts = rowDrifts(checkRows, expectedCheckRows);
const driftShape = {
auditShape,
exhaustiveShape,
byTieDrifts,
caseRowDrifts,
checkRowDrifts
};
const shapeErrors = [
sameJson(auditShape, EXPECTED_TOTALS) ? null : "totals",
byTieDrifts.length === 0 ? null : "byTieRows",
sameJson(exhaustiveShape, EXPECTED_EXHAUSTIVE) ? null : "exhaustiveShape",
caseRowDrifts.length === 0 ? null : "caseRows",
checkRowDrifts.length === 0 ? null : "checkRows"
].filter(Boolean);
if (shapeErrors.length) {
throw new Error(
`Myers diff audit shape drifted in ${shapeErrors.join(", ")}:\n` +
JSON.stringify(driftShape, null, 2)
);
}
console.log(audit.exhaustiveBinaryCases + " exhaustive binary pairs checked");
console.table(audit.byTie);
console.table(audit.cases.map((row) => ({
example: row.label,
tie: row.tie,
distance: row.distance,
lcs: row.lcsLength,
layers: row.layers,
checks: `${row.passedChecks}/${row.totalChecks}`,
passed: row.passed
})));
const summary =
`${audit.passed}/${audit.total} audit groups and ` +
`${audit.passedChecks}/${audit.totalChecks} checks passed`;
const failedCases = audit.cases.filter(
(row) => !row.passed || row.passedChecks !== row.totalChecks
);
const exhaustiveFailures = audit.exhaustive.failedChecks.slice(0, 10);
if (!audit.ok || failedCases.length || !audit.exhaustive.passed ||
audit.passed !== audit.total || audit.passedChecks !== audit.totalChecks) {
throw new Error(JSON.stringify({
issues: audit.issues.slice(0, 10),
failedCases,
exhaustiveFailures,
auditShape
}, null, 2));
}
console.log(summary);
NODE
The audit checks all included examples under both tie-break rules, then checks every pair of binary sequences of length 0 through 5. That is 3,969 exhaustive small cases and 35,811 named checks. For each case it verifies:
- the Myers edit distance equals the dynamic-programming LCS distance;
- the reconstructed script replays from the old sequence to the new sequence;
- the number of insert/delete operations equals \(D\);
- the number of equal operations equals the LCS length;
- equal operations join equal tokens; and
-
the drawn path is monotone from \((0,0)\) to $$( A , B )$$.
The implementation is intentionally inspectable:
assets/js/myers-diff-lab.js.
What A Diff Does Not Know
Myers’ model is about sequence equality and order. It does not know that two lines share a key, that a function was renamed, or that a block moved intact. That is why real review tools often layer heuristics around the core problem: tokenization choices, unique-line anchors, whitespace handling, syntax-aware preprocessing, histogram or patience-style matching, and output cleanup.
Those layers can improve human readability. They also change the promise. A shortest insert/delete script is an optimization problem with a clear certificate. A readable patch is partly a user-interface problem.
Tie-breaking is the smallest example of that distinction. When two predecessor diagonals reach the same furthest point, preferring deletes or inserts gives a different script with the same length. The edit graph proves both are shortest. Only the reader can say which one is clearer.
Miller and Myers’ earlier file-comparison paper described computing a shortest sequence of insertion and deletion commands for one file to another, especially when the files are similar.3 The enduring engineering lesson is not that this is the only way to show changes. It is that a good diff keeps its mathematical core small:
tokens define equality
the edit graph defines legality
the frontier proves shortestness
the renderer decides how humans see it
The algorithm does not understand your code. It does something narrower and more auditable: it walks the furthest frontier until no shorter script could have arrived first.
-
Eugene W. Myers, “An O(ND) Difference Algorithm and Its Variations”, Algorithmica 1, 251-266, 1986. A public PDF copy is available from the Max Planck Institute of Molecular Cell Biology and Genetics publications server. ↩
-
Myers’ paper also gives variations, including a linear-space refinement for reconstructing scripts. The lab here deliberately stores the trace so the frontier can be visualized. ↩
-
Webb Miller and Eugene W. Myers, “A File Comparison Program”, Software: Practice and Experience 15(11), 1025-1040, 1985. A PDF copy is indexed by SciSpace. ↩