reconcile.ts: the structural diff

1. The op vocabulary
2. Identity is the base case
3. Objects
4. Arrays: trim, then walk
5. applyPatch is pure
6. Budget

packages/core/src/reconcile.ts, with the JSON-pointer syntax in pointer.ts (its only import). Everything else in core sits on top of these two.

Two pure functions and an op vocabulary:

reconcile(prev: Json, next: Json): Patch    // diff
applyPatch(doc: Json, patch: Patch): Json   // apply, without mutating anything

The same patch travels three distances: to a local reader (the graph tests it against recorded read-paths), to the DOM (a region reconciles its children), and across a socket (the wire codec validates exactly these op shapes). There is one diff in the system, and this is it.

The op vocabulary

Paths are RFC 6901 JSON pointers (/items/3/done), with ~ escaped as ~0 and / as ~1. The root is the empty string. pointer.ts holds the syntax: escapeSegment for the diff, parsePath for the apply and the patch matcher, and arrayIndex, the index rule below; pointer.test.ts tables each.

This format differs from RFC 6902 JSON Patch by including splice, which lets a JSON Patch representation of "insert one row at the front of a 10,000-item list" is 10,000 index rewrites, while splice is one op whose size is the inserted slice. Since the wire carries these ops verbatim, the op set is a protocol decision rather than only an implementation detail. Changing it means changing packages/wire/spec/.

Identity is the base case

walk() opens with Object.is(prev, next) and returns immediately on a hit. Everything about the library's performance follows from that one line: if you build the next state by spreading and reusing the parts that didn't change, the diff never descends into the reused parts. Cost is proportional to what changed, not to the size of the state.

The mutate-then-clone anti-pattern defeats exactly this: a deep clone shares no identity, so every node is "changed" and the diff walks the whole tree. That is the ~4,900 µs row in concepts.md.

Path strings are built only along the changed spine. ${path}/${key} is constructed after the identity check fails, never for the untouched neighbours (measured ~5× on 10k items).

walk() stays one function, array and record cases inline: split into a function per kind it measured roughly 15% slower on the budget case below.

Objects

Keys present in prev but not next emit del. Keys in next are compared by identity; a changed key recurses if it existed before, and emits set if it is new.

The membership test is Object.hasOwn, never in. With in, a key like toString would find Object.prototype's method and the diff would conclude the key already existed, which would corrupt the patch for state that uses prototype-shadowing key names. applyPatch guards the mirror image by writing through Object.defineProperty rather than assignment, so a __proto__ key in the data cannot reach the prototype chain.

A key holding undefined counts as absent, because JSON has no undefined and the wire would drop it anyway. The diff never emits a set whose value is undefined, and a key that goes from a value to undefined emits del. On the apply side, a set of undefined on a record key removes the key. With the same rule on both sides, applyPatch(prev, reconcile(prev, next)) equals next once undefined keys are dropped, and so does anything decoded from the wire. reconcile.test.ts checks this with a property over records that carry undefined values.

Arrays: trim, then walk

The array case exists to keep list edits proportional to the edit. It trims the identity-shared prefix and suffix first, so a contiguous insertion or removal collapses into a single splice:

flowchart TD
    A["prev = [a, b, c, d, e]<br/>next = [a, b, X, d, e]"] --> B["trim prefix<br/>start = 2"]
    B --> C["trim suffix<br/>suffix = 2"]
    C --> D["windows: prev[2..3), next[2..3)<br/>both non-empty"]
    D --> E["walk the overlap per index<br/>→ ops under /2 only"]
    E --> F["lengths equal → no splice"]

Three outcomes after trimming, in the order the code tests them:

• Prefix window empty in prev (start === pEnd): pure insertion. One splice inserting the middle of next.
• Window empty in next (start === nEnd): pure removal. One splice removing that range.
• Both windows non-empty: indices agree in both coordinate systems across the overlap, so the overlap is walked per index, and one trailing splice accounts for any length difference.

When reading a patch, note that an edit and a length change in the same yield produce per-index ops plus one splice, not a single fused op. Minimality is asserted per-shape in reconcile.test.ts, not claimed in general.

applyPatch is pure

applyPatch copies every container it descends through and never touches the input document, the patch, or the values inside the patch. That purity is what makes it safe on the client, where the previous snapshot is still being read by live bindings while the next one is being built. This is the same structural-sharing discipline the docs ask of application code, applied internally.

A container is copied at most once per patch. applyPatch keeps the set of copies it has made during the call (fresh), and a later op that reaches one of them writes into it rather than copying again: nothing outside the call can hold a copy that the call itself created. Values that arrive in the patch are never in that set, so an op that descends into a value an earlier op set copies it first. That keeps a k-op patch into an array of n at O(n + k) rather than O(k × n); a reverse of 10,000 rows is 20,000 ops and one array copy (reconcile.test.ts, "copies each container once per patch").

It is strict about malformed input: a path that descends into a non-container or a missing key, a del of a missing key or of the root, a splice on a non-array, a splice range past the end, or an invalid ~ escape all throw. An array index (arrayIndex) must match RFC 6901's 0|[1-9][0-9]* and be in range: '01', '1e0', ' 1', '' and '-' are all rejected, although Number() would accept most of them. The wire vectors in packages/wire/spec/vectors/patches.json pin each of these cases. The wire's decoder does a structural pre-check of the same constraints (protocol.ts), so a hostile peer's patch is rejected at the codec rather than half-applied.

Round-tripping is the property test: for random prev/next pairs, applyPatch(prev, reconcile(prev, next)) must deep-equal next (reconcile.test.ts). Independent random pairs share no identity, so a second family of properties builds next from prev the way application code does: a few spine-copying edits that share every sibling. Those must round-trip too. When the edits keep array shapes, the patch has at most one op per edit, and a single edit of any kind, including an array insert or removal, is at most one op.

Budget

1 change in a 10,000-item list must diff in ≤ 100 µs, asserted in packages/core/test/reconcile.perf.test.ts. The figure is the best of five round medians of 200 runs each, which keeps it stable on shared CI runners without timing anything other than real runs. RECONCILE_BUDGET_US can tighten the budget but not loosen it. It is a CI assertion, not a guideline. Tighten it if you make the diff faster; do not loosen it to make a change fit.

Next: tracking.md explains how a reader records what it read so a patch can be matched against it.

This page's source on GitHub