Computing Diffs

Two facts to hold at once: git stores whole snapshots (every blob is a complete file, as you built), yet git shows changes (git diff prints what you edited). The resolution is that diffs are stored nowhere. They are computed on demand, from a pair of snapshots, every time. After this lesson your program computes a line diff and prints it as git diff does: the shortest edit script, and the unified format with its @@ hunk headers.

A diff is an edit script

Given old lines and new lines, a diff answers: what is the smallest set of line deletions and additions that turns old into new? The classical foundation is the longest common subsequence (LCS). Lines in the LCS are the unchanged skeleton; old lines outside it are deletions and new lines outside it are additions.

old:  A B C D          LCS: A B D
new:  A B X D          script:  =A  =B  -C  +X  =D

Build a table L[i][j] holding the LCS length of old lines i.. and new lines j.., filling it from the end. Then walk from the start: if the two current lines are equal, keep them (matching is always safe); otherwise take the step that keeps the LCS length, and when removing and adding are equally good, remove first. That tie rule matters: several shortest scripts often exist, and the output must be one specific script. (Git uses Myers' algorithm, which finds a shortest script faster but may choose differently when there are ties. Where the shortest script is unique, both agree.)

The unified format

A line starting with a space is context (unchanged), - exists only in old, + only in new. A change is never "modified", it is one - and one +. Changes are grouped into hunks, each with a header:

@@ -start,count +start,count @@

-3,4 means the hunk covers 4 old lines starting at line 3; +3,5 covers 5 new lines starting at new line 3. Worked example with 2 lines of context around the single change in a 12-line file whose line 7 was replaced by two lines:

@@ -5,5 +5,6 @@
 line 5
 line 6
-line 7
+line 7, edited
+line 7b
 line 8
 line 9

The old side has 5 lines (5, 6, 7, 8, 9) and the new side has 6. Details that decide byte-exact output:

• A count of 1 is written as just the number: @@ -4 +4,2 @@.
• A count of 0 uses the line before the hunk as its start, so adding two lines at the very top of a file reads @@ -0,0 +1,2 @@.
• Each change gets up to n lines of context on both sides. Two changes belong to the same hunk when the unchanged gap between them is at most 2n lines, because their contexts then touch or overlap; a longer gap starts a new hunk. With n = 0 every separate change is its own hunk.
• Real git appends the name of the enclosing function after the closing @@. This exercise omits it.

Where diffs live

The object store never stores diffs, only snapshots. That is why checkout and log are fast: nothing is replayed. The one place git stores something diff-like is packfiles, which delta-compress similar blobs purely as a storage optimisation underneath all of this.

Common mistakes

• Printing a modified line as one line. There is no "modify"; it is - then +.
• Emitting + before - inside a change when both are possible.
• Writing -3,1 instead of -3, or -4,0 with the wrong start for an empty side.
• Starting a new hunk too early or too late: the rule is a gap of more than 2n unchanged lines.
• Forgetting that identical inputs produce context lines (full mode) or nothing at all (hunk mode).

Your exercise

The starter reads the two files and prints your output. You write edit_script, the LCS-based script, and hunks, which turns a script into unified hunks. The tests include diffs checked against real git diff wherever the shortest script is unique.