diffkit
Myers O(ND), patience and table LCS — unified diff that matches GNU, right in your browser.
1 Two texts, three algorithms
Paste old and new. Algorithms share one edit-script type: equal / delete / insert. Myers walks diagonals of the edit graph at O((N+M)D); the table fills (N+1)×(M+1) — same distance, far more memory.
2 Why Myers over the table
The dynamic-programming LCS everyone is taught fills an (N+1)×(M+1) table of integers — 1,601,200 cells for two 4,000-line files whether they differ by 11 edits or 11,000. Myers keeps the furthest point reached for each number of edits D, at O((N+M)D).
| lines | Myers | table |
|---|---|---|
| 100 | 57 µs, 54 KB | 135 µs, 101 KB |
| 1,000 | 271 µs, 524 KB | 9.1 ms, 8.3 MB |
| 4,000 | 962 µs, 2.1 MB | 110 ms, 131 MB |
Measured on two 4,000-line files differing by 11 edits: Myers 1.25ms / 2MB, table 197ms / 128MB — 158× slower and 59× the memory for the same eleven edits. The table stays in the test suite because it computes a true LCS: TestMyersIsMinimal checks Myers against it on 3,000 random inputs.
3 Patch refuses to lie
Every context and deleted line is checked against the target before anything is written. A patch that does not fit is refused with the line number that disagreed — because a patch applied without checking silently corrupts a file that has moved on.
Hunk headers number an empty range from the line before it — the line patch inserts after. Getting it wrong produces a patch that applies cleanly and corrupts the file. Output is compared against diff -U0/1/3 byte for byte in CI.
4 3-way merge playground
Diff3 in the browser: hunks from base→left and base→right are merged over the shared ancestor. Non-overlapping edits combine cleanly; edits to the same region produce conflict markers.
5 Myers edit path visualizer
The O(ND) edit graph: diagonals are free matches, vertical/horizontal steps cost one edit. The animated path is the shortest path Myers finds — its length minus the diagonal equals D, the edit distance.
6 Apply patch & export
Every context and deleted line is checked against the target before anything is written — same rule the Go CLI enforces. Export the current unified diff, tweak it, then simulate applying it to OLD.