Tree Matching

The diff core runs one algorithm, in the GumTree lineage, across three phases: top-down isomorphic matching, bottom-up container matching, and a Chawathe edit script over the matched pairs. All six tiers feed the same algorithm; only the trees differ.

Phase 1: top-down isomorphic matching

The algorithm walks both trees top-down and pairs subtrees that are structurally identical. Two subtrees are isomorphic when their content hashes match exactly: same kind, same children, same shape. The hash is a candidate, not a verdict: before a pair is trusted, the matcher walks the subtree and compares every kind, label, and value directly, so even a forged hash collision cannot weld two different subtrees together. Take these two small ASTs. a.ts:

function greet(name: string): string {
  return `hello ${name}`;
}

b.ts:

function greet(name: string): string {
  const greeting = `hello ${name}`;
  return greeting;
}

The return node in a.ts and the return node in b.ts differ, but the parameter list, name: string, is identical in both. Top-down matching anchors on those identical subtrees first:

old: function_declaration
       └── formal_parameters
             └── required_parameter "name"        ← matched (structure hash equal)
new: function_declaration
       └── formal_parameters
             └── required_parameter "name"        ← matched (structure hash equal)

Isomorphic anchors are cheap to find: one hash comparison per candidate. They seed the rest of the algorithm with high-confidence pairs.

Phase 2: bottom-up container matching

Most changes don’t preserve isomorphism. In the example above the bodies differ, so no body node matched top-down. Bottom-up matching propagates matches upward: a container matches if most of its children already matched, even when the container’s own shape changed. The function declarations have identical parameter lists (matched in phase 1) and the return statements differ. The function_declaration nodes share a matched child, so they pair up:

old: function_declaration  ← matched in phase 2 (1 of 2 children matched)
       ├── name "greet"
       ├── formal_parameters     ← matched in phase 1
       └── body
             └── return
new: function_declaration  ← matched in phase 2 (1 of 2 children matched)
       ├── name "greet"
       ├── formal_parameters     ← matched in phase 1
       └── body
             ├── local_var "greeting"
             └── return

The matcher only compares candidates whose parents already match. A node can never match against something in a different subtree, and that pruning is what keeps the phase tractable.

Chawathe edit scripts

Once the match sets exist, the algorithm computes the minimal edit script that transforms the old tree into the new one, in the style of Chawathe’s tree-diff work:

Action	Meaning	Example
`Insert`	A node exists only in the new tree	the `local_var "greeting"` declaration
`Delete`	A node exists only in the old tree	a removed import
`Update`	A matched node changed label or value	`greet` renamed to `greetUser`
`Move`	A matched node changed parents	an extracted helper moved to module scope
`Reorder`	Matched siblings changed order	two imports swapped

The script is minimal: one action per affected node, and a rename is one Update, never a delete plus an insert.

Content hash vs structure hash

Every node carries two hashes, 53-bit-safe folds of two 32-bit FNV-1a streams, both computed bottom-up (Merkle-style):

Content hash: kind + label + value + the children’s content hashes. Two nodes with the same content hash are the same code. Renaming greet changes the label and therefore the content hash.
Structure hash: kind + the children’s structure hashes. Labels and values are ignored, so function greet(...) and function farewell(...) with identical bodies share a structure hash. This is what phase 1 matches on.

Structure hashes find where things are; content hashes find what things are. The correlator uses both, and it verifies exact content matches with the same full-subtree comparison as the matcher.

FNV-1a hashing

Hashes use FNV-1a over two independent 32-bit streams, folded into one 53-bit-safe JavaScript number. Each node’s hash combines its own fields with its children’s hashes, so a change anywhere in a subtree changes every ancestor’s hash. That Merkle property makes subtree equality a single comparison. The collision bound follows from the birthday problem: at one million nodes the chance of any two nodes colliding is about 0.006%, and at ten million about 0.6%. That bound now describes wasted comparisons, not wrong matches: every hash-equal pair is verified against the real subtree content, so a collision degrades to “no match” and the change still gets reported through the next matching phase. There is no node-count cap, so this applies at every realistic tree size.

Hashes are JavaScript numbers, not full 64-bit integers, so no BigInt handling is involved. The JSON formatter serializes them as regular integers. See Output.

Safety valves

Tree matching runs on flat typed arrays and is linear in node count, so there is no node-count cap: every tree size is matched for real. Two bounds keep the worst case sane without rejecting any input:

maxNodes (opt-in): embedders may set a node count beyond which diffTrees returns a lines fallback instead of matching. The default is Infinity.
Bottom-up candidate caps: the bottom-up phase compares a container against at most four candidates and zips leaf alignments past 64 siblings by position. Candidate pairs are only considered inside already-matched parents, which keeps typical runs far below the quadratic worst case.

Getting Started

How It Works

Guides

Tree Matching

Tree Matching

Phase 1: top-down isomorphic matching

Phase 2: bottom-up container matching

Chawathe edit scripts

Content hash vs structure hash

FNV-1a hashing

Safety valves

​Tree Matching

​Phase 1: top-down isomorphic matching

​Phase 2: bottom-up container matching

​Chawathe edit scripts

​Content hash vs structure hash

​FNV-1a hashing

​Safety valves

Tree Matching

Phase 1: top-down isomorphic matching

Phase 2: bottom-up container matching

Chawathe edit scripts

Content hash vs structure hash

FNV-1a hashing

Safety valves