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. Your exercise stops one step short of it: you emit the prefixed edit-script lines ( , -, +) for the whole file, with no @@ headers and no hunk grouping — the header arithmetic is what a real git diff layers on top of exactly this output.

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 (every line comes back as context, prefixed with a space — not an empty output). When every line carries the right prefix and the script you emit is the shortest one, you've built the lens through which all code change is seen.