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 structure hashes match exactly: same kind, same children, same shape, with labels and values ignored. 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.

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 the 250,000-node cap, the chance of any two nodes colliding is about 0.0003%.

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 is inherently super-linear, so the core enforces two bounds:

maxNodes = 250,000: trees larger than this make diffTrees return a lines fallback, and the caller falls back to a line diff, which keeps the birthday bound quoted above honest.
O(n²) bottom-up matching: the bottom-up phase is bounded to quadratic worst-case work; candidate pairs are only considered inside already-matched parents, which keeps typical runs far below the bound.

The valves fail soft: exceeding a bound triggers a line-diff fallback instead of aborting.

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