How Diff Produces Hunks: Myers, Patience, and Hunk Sliding

Given two versions of a file, there are usually many correct ways to describe the difference. Delete a block here and add an equivalent block there, or leave it in place and adjust the lines around it; both produce the same second file from the first. A diff tool has to choose one, and the choice determines whether a reviewer sees a coherent change or a scatter of unrelated edits. The algorithms involved are solving a well-defined optimisation problem, and most of the engineering around them exists because the optimal answer is frequently the wrong one to display.

An edit script is a path through a grid

Model the two files as sequences of lines. A diff is a sequence of operations: keep a line from both files, delete a line from the first, or insert a line from the second. Laying one file along the horizontal axis and the other along the vertical turns any such script into a monotone path from the top-left corner to the bottom-right, moving diagonally on a match, right on a deletion, and down on an insertion.

The length of the shortest such path is the edit distance under insertions and deletions, and it is related to the longest common subsequence by a fixed identity: the number of edits equals the sum of the two lengths minus twice the length of the longest common subsequence. Computing the LCS by dynamic programming takes time and space proportional to the product of the lengths. For two versions of a source file with a few thousand lines each, that is millions of cells per file, and a commit that touches hundreds of files multiplies it.

Myers and the furthest-reaching path

The 1986 algorithm by Eugene Myers avoids the quadratic table by searching over the number of edits rather than over the grid. It proceeds in rounds indexed by an edit distance D. After round D, it knows, for each diagonal k of the grid, the furthest point reachable using at most D edits, where a diagonal is the set of cells with x minus y equal to k. Extending a point means sliding along its diagonal as long as the lines match, which costs nothing.

Each round only has to consider the diagonals of the right parity, and each diagonal’s new value comes from one of two neighbours: the one above, which corresponds to an insertion, or the one to the left, which corresponds to a deletion. The first round in which the bottom-right corner is reached gives the edit distance, and the choices recorded along the way give the script.

The running time is proportional to N times D, where N is the sum of the file lengths and D is the number of edits. Files that differ in a few places are cheap regardless of size; files with nothing in common degenerate to D equal to N, which is the quadratic case again. The classic formulation keeps the whole trace to recover the path, which costs memory proportional to D squared; the linear-space refinement finds a middle snake by running the search from both ends and recursing on the two halves, reducing memory to O(N) at the cost of a constant factor in time.

def myers_distance(a, b):
    n, m = len(a), len(b)
    v = {1: 0}                      # v[k] = furthest x reached on diagonal k
    for d in range(n + m + 1):
        for k in range(-d, d + 1, 2):
            if k == -d or (k != d and v[k - 1] < v[k + 1]):
                x = v[k + 1]        # came from above: inserted a line of b
            else:
                x = v[k - 1] + 1    # came from the left: deleted a line of a
            y = x - k
            while x < n and y < m and a[x] == b[y]:
                x, y = x + 1, y + 1
            v[k] = x
            if x >= n and y >= m:
                return d

Anchoring on lines that occur once

Myers optimises a global count. It has no notion of which lines are meaningful, so a run of identical braces is as good a place to split a hunk as a function signature. Patience diff takes a different route: it finds lines that occur exactly once in each file, pairs them by position, computes the longest increasing subsequence of those pairs to keep the anchors in order, and then recurses on the regions between anchors. Regions with no unique lines fall back to a conventional algorithm.

The effect on readability is large for source code, where braces, blank lines, and common statements occur many times but identifiers, signatures, and comments usually occur once. Anchoring on those makes a moved function appear as a move of its body rather than as a delete and insert in unrelated places. The cost is that the algorithm gives up on minimality: it can emit more edits than necessary, and it degrades to the fallback when a file has no unique lines at all, which happens with generated files and with files consisting of repeated records.

Histogram diff generalises the idea. Instead of requiring uniqueness, it selects the line with the lowest occurrence count in the region, uses its occurrences as anchors, and recurses, which handles files where every line is duplicated while still preferring rare lines. It also avoids the quadratic matching that patience performs when a line occurs many times, since the occurrence counts are computed once per region.

Why the minimal diff reads badly

The shortest edit script is a poor description of intent because intent is not part of the input. Moving a block of ten lines downward by three positions can be expressed minimally as three deletions at the top and three insertions at the bottom, which is also the minimal description of deleting three lines and adding three different ones. A human reading the patch sees two unrelated changes.

The same effect appears at a smaller scale with repeated punctuation. A minimal script may choose to align a closing brace in the old file with a different closing brace in the new file, producing a hunk that starts mid-expression. The algorithm is not wrong; it is optimising a metric that does not measure comprehension.

There is also a pathological cost case. Because Myers explores by increasing edit distance, files that share almost nothing require exploring nearly the whole grid, and a large generated file with one changed line in the middle can still be expensive if the change shifts a long repeated pattern. Implementations impose heuristics and, in some cases, a cap on the effort spent before falling back to a cheaper answer.

Sliding hunks after the fact

The chosen script is not the final output. A hunk boundary can often be moved up or down without changing the number of edits, because the lines at its edges are identical on both sides. Git’s diff machinery slides each hunk as far as it can in either direction and then picks a position using a heuristic.

The default heuristic scores candidate positions by the indentation of the surrounding context, preferring a boundary where the hunk begins at a lower indentation level than the lines it contains. That tends to place hunks at the start of a block rather than in the middle of an expression. An alternative heuristic prefers boundaries adjacent to blank lines, and the choice is configurable per invocation or per repository. Sliding is a post-pass, so it applies to every algorithm equally and costs time proportional to the size of the hunk.

Whitespace handling sits outside the algorithm as well. Trailing whitespace can be ignored at comparison time, which changes what counts as a match and therefore changes the script. Line endings are normalised before comparison in some configurations and not others, so the same commit can produce different patches on different machines.

What the output cannot express

Line-based diffing has structural limits that no algorithm choice fixes. A file without a trailing newline is a single line, so a change anywhere in it is a whole-file replacement. A file containing a NUL byte in its first few kilobytes is treated as binary and shown as “Binary files differ” rather than as a patch, a heuristic that misclassifies some text formats. Rename detection is a separate pass that pairs deleted and added paths by content similarity and is not part of the diff at all; the same similarity score is what a merge consults when it has to decide whether a path survived.

The output format also fixes the granularity. Unified hunks carry three lines of context by default, and a hunk header gives the starting line and length on each side; changing the context changes the hunks without changing the edit script. Adjacent hunks merge when their context regions overlap, so a file with many small changes produces fewer, larger hunks than the edit count suggests.

The same diff machinery feeds the merge engine, where it is run twice against a common ancestor rather than once between two files. That use exposes a different failure: a hunk that is minimal between two versions may not align with the region a second version changed, which is one source of the conflicts described in three-way merge.