Semantic Diff: Comparing Two Versions of a Function by Meaning, Not Text

A diff is a claim about how much changed, and reviewers spend attention in proportion to it. Line-based diffs make that claim badly in both directions, and the two failures need different tools.

A large diff that changes nothing

Rename a parameter and reflow the argument list. Here is the before and after of a small function:

- def compute(o, r, d=False):
-     total = sum(i.price * i.qty for i in o.items)
-     if d:
-         total = total * (1 - r)
-     return round(total, 2)

+ def compute(
+     order,
+     discount_rate,
+     apply_discount=False,
+ ):
+     total = sum(
+         item.price * item.qty for item in order.items
+     )
+     if apply_discount:
+         total = total * (1 - discount_rate)
+     return round(total, 2)

Ten lines removed, thirteen added: by every line-based measure this is a complete rewrite of the function. By behaviour it is a no-op. The abstract syntax trees are identical up to the names of the identifiers and the positions of the tokens, and no execution of this function can distinguish the two versions.

The reverse failure is worse. Change 1 - discount_rate to 1 + discount_rate and the diff is one character on one line — the smallest possible visual footprint for a change that inverts what the function computes. A reviewer scanning by diff size has exactly inverted priorities on these two commits.

Why line diff behaves this way

Unix diff and git’s default solve a longest-common- subsequence problem over lines. A line is the unit, so any change anywhere in a line replaces the whole line, and reflowing a statement across four lines replaces four. The algorithm has no notion of a token, a name or a scope, and it is not trying to have one — it is a general text algorithm applied to a file that happens to contain code.

Git’s built-in mitigations help at the edges and are worth knowing. --word-diff changes the unit from a line to a whitespace- delimited word, which collapses the reflow half of the example above but not the rename half. -w ignores whitespace changes entirely. The --patience and --histogram diff algorithms produce better-aligned hunks when a block moves, which reduces spurious “deleted here, added there” pairs. None of them understands that o and order are the same variable, because that is a question about scope, and scope requires a parser.

It is worth knowing that this asymmetry has a cost beyond review attention. Line-based diffs are what merge algorithms operate on, so two developers who reflow the same function in different ways produce a conflict over code that is semantically identical in both branches — and resolving it by hand is exactly the situation in which a real logic change on a nearby line gets discarded by accident. Reflow and rename in their own commits, separately from behaviour changes, and the tooling stops fighting you. That convention is worth more in practice than any diff algorithm.

Tree diff and edit scripts

The structural approach parses both versions and computes an edit script between the two trees: a sequence of insert, delete, update and move operations on nodes. The reference work here is GumTree, published by Falleri, Morandat, Blanc, Martinez and Monperrus at ASE 2014 (“Fine-grained and Accurate Source Code Differencing”), which matches nodes between the trees in two phases — a top-down pass finding identical subtrees, then a bottom-up pass matching containers whose children mostly matched — and derives the edit script from the resulting mapping.

On the example above, a tree diff reports what actually happened: three update operations on identifier nodes, and nothing else. The move operation is the one line diff cannot express at all; it is what turns “40 lines deleted, 40 lines added” into “one function moved between classes”.

The costs are real. You need a grammar per language, both versions must parse — which excludes diffs against a broken intermediate commit unless your parser recovers from errors — and tree matching is heuristic, so two structurally different but behaviourally identical rewrites still look large. Tree diff fixes the representation, not the semantics.

One property of tree diff surprises people the first time: the size of the edit script depends on the grammar, not only on the change. A grammar that models a binary expression as a node with two children and an operator field produces a one-node update when the operator changes. A grammar that models it as a flat sequence of tokens produces an insert and a delete. Two tools can therefore report honestly different magnitudes for the same commit, and neither is wrong. Compare edit-script sizes only within one tool and one language.

Canonical renaming

For the specific and common case of “is this only a rename”, there is a cheap exact test. Parse, resolve each identifier to its binding, and rewrite every local name to a positional placeholder — the first parameter becomes v0, the second v1, the first local v2. Then compare the token streams.

before -> def compute(v0, v1, v2=False):
              v3 = sum(v4.price * v4.qty for v4 in v0.items)
              if v2: v3 = v3 * (1 - v1)
              return round(v3, 2)

after  -> def compute(v0, v1, v2=False):
              v3 = sum(v4.price * v4.qty for v4 in v0.items)
              if v2: v3 = v3 * (1 - v1)
              return round(v3, 2)

identical -> report "renamed only", not a 23-line diff

This is decidable and exact within its scope: it proves the two versions differ only by the choice of local names, which is alpha-equivalence in the lambda-calculus sense. It says nothing about renamed globals or changed method names on other objects, both of which can alter behaviour, so scope the placeholder rewriting to bindings you can see. Used as a review filter, it moves a meaningful fraction of refactoring commits out of the queue that needs careful reading.

Where embeddings fit, and do not

It is tempting to compute the cosine similarity of the two versions and call the result a semantic diff. Do not present it as one. The similarity between a function and its renamed self will be high, and the similarity between 1 - rate and 1 + rate will also be high — very high, because they differ by one token out of forty. Precisely the change you most need to catch is the one an embedding is least able to see.

Embeddings are useful here for a different question: finding which function in the new version corresponds to which in the old, when a file was reorganised and names changed so that neither path nor symbol matching works. Match candidates by vector similarity, then run the exact structural comparison on each matched pair. The embedding solves the correspondence problem, which is a search problem it is good at, and the parser answers the equivalence question, which it is not. The same division of labour runs through clone detection, and the parsing side is covered in the AST page.