Diff Checker

The mistake almost every diff tool makes

Comparing two documents looks like it should be easy. Walk both at once, compare line one with line one, line two with line two, mark them different where they differ. Many online comparison tools do exactly that, and it works right up until the first insertion.

Add one line at the top of a hundred-line file and every line below it shifts down by one. The lockstep comparison now finds line two of the first document against line three of the second, and they do not match. Nor does anything after them. The tool reports ninety-nine changed lines when one line was added, which is not a rounding error but a complete failure to describe the edit, and it fails hardest on precisely the change you most wanted to inspect.

The correct question is not which lines sit at the same position but which lines the two documents have in common, in order. That is the longest common subsequence, and everything not in it is an insertion or a deletion. Once you frame it that way, one added line is one added line no matter what follows.

How Myers' algorithm finds the shortest answer

Eugene Myers published the standard method in 1986, in a paper called An O(ND) Difference Algorithm and Its Variations. Its central move is to stop thinking about text and start thinking about a grid.

Lay the first document down the left edge and the second across the top. A path from the top-left corner to the bottom-right corner is one way of turning the first into the second. Moving right deletes a line, moving down inserts one, and moving diagonally means the two lines match, so it costs nothing. The best diff is the shortest path, and shortest here means fewest non-diagonal moves.

Searching that grid exhaustively would be far too slow. The insight is that for a given number of edits D, you only need to know, for each diagonal of the grid, the furthest point any D-edit path has reached. Everything else can be discarded. So the search proceeds one edit at a time, tracking a single array of furthest-reaching points, and stops the moment one of them arrives at the far corner.

The consequence is that the running time depends on how different the documents are rather than on how large they are. Two thousand-line files with three changed lines are compared almost instantly; two thousand-line files with nothing in common are the slow case. That is the right way round, since similar documents are what people actually compare.

Why an edited line is not a delete and an insert

The algorithm produces a flat list of deletions and insertions. That is mathematically complete and awkward to read: a line where one word changed appears as a removed line in one place and an added line in another, and you are left comparing two long strings by eye to find the actual difference.

So a run of deletions immediately followed by a run of insertions is paired up into replacements, and each replacement is compared again at the word level with the same algorithm. Only the words that actually changed get marked, which turns a wall of red and green into a sentence with two highlighted words in it.

The tokenising for that second pass matters more than it sounds. Whitespace is kept as its own token rather than thrown away, so the pieces reassemble into the original line without anybody having to guess where the spaces were. Punctuation is separated from words, so changing a full stop to a comma highlights the mark rather than repainting the whole word around it.

Unified diffs, and why the format is worth producing

The unified format is the one you see in a git commit or an emailed patch: a hunk header giving the line ranges, then the context and changes with a space, minus or plus at the front of each line. Three lines of context either side is the convention, and long runs of unchanged text between hunks are simply omitted, which is what keeps the output readable on a large file.

Producing it properly means the output is not just something to look at but something to apply. Copy it, add the file headers your workflow expects, and patch or git apply will turn the first document into the second.

That claim is easy to make and easy to get subtly wrong, since a hunk header with the wrong line count is accepted by some tools and rejected by others. So it is checked by generating a patch, handing it to git, and confirming git both accepts it and produces the expected file. Testing the output against my own parser would only have proved the two agreed with each other.