How Text Diffs Actually Work

A diff tool gets two versions of a text and no other information. It doesn't know what you typed, moved, or renamed — it has to infer a plausible set of edits from the before and after alone. Everything a diff shows you, including the parts that look wrong, follows from how that inference works.

The core idea: longest common subsequence

The standard framing is the longest common subsequence (LCS): find the longest sequence of lines that appears in both versions in the same order — not necessarily contiguously. Those lines are the "unchanged" backbone of the diff. Every line in the old version that isn't part of it is a deletion; every line in the new version that isn't is an insertion.

Why the longest one? Because maximizing what's kept is the same as minimizing what changed. A diff that keeps more lines in common needs fewer delete/insert markers, and a minimal edit script is the version most likely to match what a human actually did.

Myers: the shortest edit script, efficiently

Computing the LCS naively takes time proportional to the product of the two file lengths, which is too slow for large files. The algorithm used by git and most modern diff tools is Eugene Myers' 1986 algorithm, which reframes the problem as pathfinding through an edit graph: from any position, stepping one way means "delete a line from the old file," stepping the other means "insert a line from the new file," and a diagonal step — allowed only where the lines match — is free. The shortest path through this graph is the shortest edit script.

Myers' key property is that its cost grows with the size of the difference, not the size of the files. Comparing two 10,000-line files that differ by five lines is nearly instant; that's the common case in practice, and it's why diffing feels free even in large repositories.

Lines first, then words and characters

Running the algorithm on individual characters would be slow and produce noisy, meaningless matches. So practical tools work in two passes. First, a line-level diff: each line is hashed, and the algorithm compares hashes, which makes each line one cheap unit. Then, for each block where a group of removed lines sits opposite a group of added lines, the tool re-runs the same algorithm at word or character level inside just that block. That second pass is what produces the fine-grained highlighting — the diff engine showing that only one word changed inside an otherwise identical line. A text diff tool that highlights intraline changes is doing exactly this two-level refinement.

Why moved code shows as delete + add

The edit model has only two operations: delete and insert. There is no "move." So a paragraph relocated from the top of a document to the bottom appears as a deletion up top and an unrelated-looking insertion below — the algorithm has no concept linking them, because delete-here-plus-insert-there is the shortest edit script for a move. Some tools bolt on move detection afterward as a heuristic (git's --color-moved re-scans the output for deleted blocks whose content matches inserted blocks and recolors them), but that's presentation-layer pattern matching on the finished diff, not part of the algorithm.

The same limitation explains another familiar annoyance: when you insert a function between two similar-looking ones, the diff sometimes attributes the "wrong" lines to the change — say, matching a closing brace from the old code with a closing brace from your new code. Both interpretations are equally minimal edit scripts; the algorithm just picked one, and heuristics like git's "indent heuristic" exist purely to nudge it toward the boundary a human would choose.

Why whitespace options exist

The algorithm compares lines for exact equality — a line reindented by one space is, to the algorithm, a completely different line. Reformat a file and the diff reports every line changed, drowning the real edit. That's why diff tools offer normalization options: ignore trailing whitespace, ignore all whitespace changes, normalize CRLF vs LF line endings, ignore case. Each option redefines what "equal" means before the comparison runs, which can radically change the resulting diff — same algorithm, different notion of sameness.

That's the right mental model for reading any diff: it isn't a recording of what happened, it's the smallest story consistent with the evidence. Usually that story matches reality — and when it doesn't, it's because two different histories can leave behind exactly the same pair of files.