> ## Documentation Index
> Fetch the complete documentation index at: https://differens.ossl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# Tree Matching

> How the GumTree algorithm finds structural matches between two code trees

# 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`:

```ts theme={null}
function greet(name: string): string {
  return `hello ${name}`;
}
```

`b.ts`:

```ts theme={null}
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:

```text theme={null}
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:

```text theme={null}
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%.

<Info>
  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](/guides/machine-outputs).
</Info>

## 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.