Computing Diffs

Two facts to hold at once: git stores whole snapshots (every blob is a complete file — you built this), yet git shows changes (git diff prints exactly what you edited). The resolution: diffs aren't stored anywhere. They're computed on demand, every time, from pairs of snapshots — and this lesson is that computation.

A diff is an edit script

Given old lines and new lines, a diff answers: what's the smallest set of line deletions and additions that turns old into new? Smallest matters — a legal-but-useless diff deletes every old line and adds every new one; the informative diff touches only what changed. The classical foundation is the longest common subsequence (LCS): lines in the LCS are the "unchanged" skeleton; old lines outside it are deletions; new lines outside it are additions.

old: A B C D          LCS: A B D
new: A B X D          diff: -C  +X   (C left the subsequence, X entered)

(Real git defaults to Myers' algorithm — an efficient way to find that minimal script — and offers alternatives like --patience that sometimes produce more human diffs. Your exercise fixes the algorithm or gives you inputs where the minimal script is unambiguous; the concept is the LCS skeleton.)

Why lines?

Nothing in the theory requires lines — you can diff characters or words. Lines win for code because they match how programmers edit and read: a changed line is a changed thought. It's a presentation choice, and a good default. (When you see git diff --word-diff produce something beautiful for prose, that's the same machinery at a different granularity.)

The unified format

The output format you'll produce (and have read a thousand times) is the unified diff:

@@ -2,3 +2,3 @@
 context line
-old line
+new line
 context line

The grammar: space-prefixed lines are context (unchanged, shown for orientation), - lines exist only in old, + lines only in new. The @@ hunk header gives positions: -2,3 = this hunk covers old-file lines 2–4 (start 2, count 3); +2,3 likewise for new. Changes near each other cluster into one hunk; distant changes get separate hunks with the unchanged middle elided. Every code review you've ever read was this format; producing it byte-exact is the exercise's fussiest part, so build the header arithmetic carefully — start line and count, both files, off-by-ones lurking.

Where diffs came from vs where they're stored

Keep the architecture straight, because it's a common git misconception: the object store never stores diffs — snapshots only, which is why checkout and log are fast (no replaying of changes). The one place git does store something diff-like is packfiles (chapter 0): delta compression between similar blobs, purely as a storage optimization, invisible above that layer. Diff-the-command and delta-the-storage share math but serve different masters. You're building the command.

Your exercise: Compute a Line Diff

Old text and new text in; edit script (in the spec's exact format) out. Test it against your intuition on the classics: a pure insertion (everything else is context), a pure deletion, a changed line (one - plus one + — not a "modify"; the format has no modify), and identical inputs (empty diff — no hunks at all, a case implementations love to get wrong by printing an empty header). When the format matches byte-for-byte, you've built the lens through which all code change is seen.