Diff two sequences of lines as finding the shortest edit script of inserts and deletes - equivalently the longest common subsequence - and pin every value exactly: the LCS length, the Myers edit distance D (5 for ABCABBA vs CBABAC), the V array evolution, the recovered keep/insert/delete script, the @@ -1,5 +1,5 @@ hunk header, and the round-trip where applying your own diff reproduces the target byte for byte. Every lesson is one concrete spec: an exact edit script, an exact D, or an exact block of unified-diff text.
Over 28 lessons you build a working line-based diff library from scratch - the core of what git diff, patch, and code review tools do every day. You model diffing two documents as finding a shortest edit script of insertions and deletions, which is the same thing as finding their longest common subsequence, and you build it twice: first a correct dynamic-programming baseline so you always have a known-good answer, then Eugene Myers' greedy O(ND) algorithm - the edit graph, the k-diagonals, the snakes, and the furthest-reaching V array that finds the minimal edit distance and lets you backtrack a concrete edit script.
On top of that engine you produce real output: group the edit script into hunks with context lines, emit the unified diff format (the @@ -start,len +start,len @@ headers and the space, minus, and plus line prefixes), merge nearby hunks, and handle the awkward edges - a change on the first or last line, a missing trailing newline, an empty file. Then you build a patch applier that parses a unified diff and reconstructs the target, rejecting a hunk whose context does not match, and the capstone proves the round-trip: applying your own diff of two real documents reproduces the target exactly.
This is a teaching-grade but genuinely correct diff library, built around the classic Myers design. It works on lines (not words or characters), uses the greedy forward algorithm with a recorded trace to recover the script, and emits and applies standard unified diffs. It is honest about what it stops short of: it does not do the linear-space middle-snake refinement, word-level or syntax-aware diffing, fuzzy patch application, rename or copy detection, or binary files - exactly the extensions that tools like git and GNU diffutils layer on top of this same core. The finalize pass adds a runnable diff CLI that diffs two files (or a built-in demo) with a configurable context, and applies a patch back.
A diff tool compares two documents line by line, so the very first thing we need is a way to turn a blob of text into a sequence of lines. Today you build that splitter - the input to everything that follows.
Split a text string into a sequence of lines, dropping the empty trailing element a final newline leaves behind.
Every diff you have ever read is line-based: it talks about lines added, lines removed, lines kept. So the atom of our whole library is the line, and the first job is to chop a document into an ordered sequence of them. From here on, “a document” means a []string of lines, and every algorithm we build compares two such sequences.
The one subtlety is the trailing newline. A well-formed text file usually ends with \n, and naively splitting "a\nb\nc\n" on \n yields a phantom empty string at the end. We drop that trailing empty element so "a\nb\nc\n" is three lines, not four. A document that does not end in a newline (like "a\nb") keeps its last line as-is. We are throwing away the information about whether the file ended in a newline for now - a later lesson brings it back when it matters for output.
func Lines(text string) []string {if text == "" {return []string{}}parts := strings.Split(text, "\n")// a trailing newline leaves a final "" element - drop itif len(parts) > 0 && parts[len(parts)-1] == "" {parts = parts[:len(parts)-1]}return parts}
A genuinely working, standards-matching line diff - Myers O(ND) edit scripts (cross-checked against an LCS baseline), unified-diff output with context lines, hunk merging, the no-newline marker, and a context-checking patch applier that proves apply(a, diff(a, b)) == b, plus a runnable diff CLI (file diff, -U context, -demo, and -apply) - but it diffs whole lines only (not words or characters), uses the greedy forward Myers pass with a recorded trace rather than the linear-space middle-snake, applies patches by exact context match with no fuzzy offset search, handles one file per patch, and drops the no-final-newline marker on parse so a re-applied patch always ends in a newline.
The 1986 paper this whole project implements. It frames diffing as a shortest path through an edit graph and derives the greedy O(ND) algorithm, the V array of furthest-reaching paths, and the linear-space middle-snake refinement. Dense but foundational - read it alongside the lessons.
A three-part blog series that walks Myers' paper into working code step by step - the edit graph, the forward pass, storing the trace, and backtracking to build the diff. The clearest modern explanation of exactly what these lessons build.
The authoritative description of the unified diff format your output must match: the ---/+++ file header, the @@ -start,count +start,count @@ hunk header (and when the count is omitted), the line prefixes, and the "no newline at end of file" marker.
The 1990 follow-up that sharpens Myers to O(NP) where P is the number of deletions - the refinement most production diff libraries (including git's xdiff) actually use once you have the O(ND) core down.
A practical survey from the author of diff-match-patch: pre- and post-processing tricks, choosing granularity (line vs word vs character), and cleanup heuristics that turn a mathematically minimal diff into a human-readable one.