exactdiff

A structural diff that never reports a change that did not happen.

npm install exactdiff

import { diff, apply, toJsonPatch } from "exactdiff";

diff({ v: new Map([["k", 1]]) }, { v: new Map([["k", 2]]) });
// [{ op: "replace", path: [{ in: "object", key: "v" }, { in: "map", key: "k" }], value: 2 }]

diff(["a", "b", "c", "d"], ["b", "c", "d", "a"]);
// one move, not four replacements

Why

A diff makes two promises and only one of them gets tested. Everybody checks that a real change is reported. Almost nobody checks the other direction: that a change which did not happen is not reported.

The second failure is the worse one. A phantom patch in a state-sync loop is an infinite loop, because every poll produces a patch that produces a write that produces a patch. In an audit trail it is a permanent record of edits nobody made. Measured by diff-conformance, three of the seven most-used packages emit a patch for two structurally identical values, including the most downloaded one in the field, which given two identical Dates emits 24 operations because it diffs the ISO string character by character.

How it cannot

Not by handling Date and Map and RegExp as special cases that might turn out to be incomplete. Before comparing any two values, this compares their canonical forms, from impronta, and that encoding is injective: equal forms mean equal values and different forms mean different values, in both directions, for every type at once. Equal forms, no operations, stop descending. One property, not a checklist.

That is the sense of exact in the name. Not numeric precision: equality is decided exactly, in both directions, so the answer is never approximately right.

The same forms are the element identity inside arrays, which is why there is no objectHash callback to write, and why move detection works for elements a callback could not have read.

Measured, against the field

By the neutral harness, which was written before this engine existed. Regenerate with npm run conformance.

| subject | missed a real change | reported a phantom one | HTER | |---|---|---|---| | exactdiff | 0 (0.0%) | 0 (0.0%) | 0.0% | | just-diff | 8 (34.8%) | 0 (0.0%) | 17.4% | | microdiff | 9 (39.1%) | 0 (0.0%) | 19.6% | | json-diff-ts | 2 (8.7%) | 6 (42.9%) | 25.8% | | rfc6902 | 13 (56.5%) | 0 (0.0%) | 28.3% | | deep-object-diff | 14 (60.9%) | 0 (0.0%) | 30.4% | | fast-json-patch | 11 (47.8%) | 2 (14.3%) | 31.1% | | jsondiffpatch | 11 (47.8%) | 2 (14.3%) | 31.1% |

Over 23 detection probes and 14 identity probes. Read that zero next to what it costs below: on one of those 23 probes the engine does not answer at all, and refusing is not scored as a wrong answer.

Operations emitted where a move exists, lower is better:

| probe | ideal | positional | exactdiff | jsondiffpatch | rfc6902 | the rest | |---|---|---|---|---|---|---| | four strings rotated by one | 1 | 4 | 1 | 1 | 2 | 4 | | two objects swapped, no id field | 1 | 2 | 1 | 2 | 2 | 2 | | one element prepended to eight | 1 | 9 | 1 | 1 | 1 | 9 | | forty integers rotated by one | 1 | 40 | 1 | 1 | 2 | 40 | | three Sets reordered | 1 | 3 | 1 | missed | missed | missed |

It is the only subject that sees a change between two instances of different classes with identical fields, between 0 and -0, and inside a cyclic value. It is also the only one whose patch, applied, restores the right value on every probe it detects.

What it costs

A zero on a suite is only worth reading next to what the suite does not ask, so here is the other side, measured the same way.

It refuses a document containing a function, a symbol, a WeakMap, a WeakRef or a Promise, and it refuses the whole document, not the field. A single callback anywhere and diff throws UnrepresentableValueError. Every package in the field diffs around one without complaint. This is inherited on purpose from the canonical form, whose position is that a value whose meaning is its identity has no content to address, and it is the right answer for a content hash. For a diff it is a real limitation: a config object, a component's props, or anything holding a callback is out of scope today. The conformance suite has a probe for it, and the engine is the only subject that fails to answer.

It is about 5x slower than microdiff and about 14x slower than fast-json-patch, and uses several times the memory, because it canonicalizes both documents before comparing them. On one machine, one changed field:

| document | diff | tracker | microdiff | fast-json-patch | |---|---|---|---|---| | 100 rows, 12 KB | 0.38 ms | 0.17 ms | 0.07 ms | 0.03 ms | | 1,000 rows, 119 KB | 3.63 ms | 2.11 ms | 0.67 ms | 0.29 ms | | 5,000 rows, 607 KB | 21.0 ms | 11.9 ms | 3.60 ms | 1.47 ms |

The tracker column is the same workload through the streaming API below, which halves the work by keeping the previous document's canonical form instead of recomputing it. In a sync loop that is free, and it takes the gap from about 6x to about 3x.

Those figures are about 8% worse than the previous release, and the trade is deliberate: the same change made deeply nested documents linear instead of quadratic, which took the worst case from dying at twenty thousand levels to finishing sixty-four thousand in 141 ms. The section on depth has both sides. On a wide, shallow document the old representation was genuinely better, so the library now measures the real cost of materializing every subtree and picks the representation from that number rather than assuming a shape.

The growth exponents are 0.94 on width and 0.82 on depth, both measured by the harness, so this is a constant factor and not a worse complexity class on either axis. The section on depth has the numbers, including what they were before this was true.

It is, however, genuinely the slowest of the field on that document, and the whole field on the same input is the fair way to say so:

| | ms | |---|---| | fast-json-patch | 1.55 | | microdiff | 3.53 | | deep-object-diff | 7.59 | | jsondiffpatch | 9.46 | | just-diff | 9.91 | | exactdiff, tracker | 11.59 | | json-diff-ts | 17.23 | | exactdiff, diff | 20.70 | | rfc6902 | overflows the call stack |

So diff is last among the ones that finish, and tracker is mid-field. Two of the faster entries in that list are faster partly by not looking: microdiff and deep-object-diff cannot see a change inside a Map at all.

Whether that trade is worth making is a question about your pipeline. If you are diffing plain JSON on a hot path, microdiff is smaller, faster, and wrong about fewer things than you probably need it to be right about. If a phantom patch would cost you an infinite sync loop or a false audit record, correctness is the axis and this is the trade.

And it is new. The alternatives have between 300k and 8M downloads a week and years of production exposure. This has a test suite and a conformance score. Two wrong answers have already been found and fixed in it since the score was first measured, both by tests written after the fact: a shared reference reported under only one of the paths that reach it, and a Map entry inserted ahead of an existing one coming back in the wrong order. Both are now probes in the harness, so the next one has somewhere to be caught.

Diffing a stream

Canonicalizing both documents is where the time goes, and in a sync loop half of it is waste: each state is compared against the previous one, which was already canonicalized on the last tick.

import { tracker } from "exactdiff";

const track = tracker();
track(state0); // [] on the first call, with nothing to compare against
track(state1); // the operations from state0 to state1, at roughly half the cost

It agrees with diff operation for operation; there is a test that runs both over a long random stream and compares. It holds a strong reference to the last document, which is the point, so let it go when the stream ends.

What it covers

Map, Set, TypedArray, ArrayBuffer, Date, RegExp, BigInt, class instances, null-prototype objects, cycles, and the JSON types. Not a subset with the awkward parts left out.

Cycles are real, not a crash guard. diff compares two cyclic graphs by bisimulation, and apply clones the graph preserving back-edges, so a patched self-referential document still refers to itself and not to its unpatched former self.

const before = { n: 1 }; before.self = before;
const after  = { n: 2 }; after.self  = after;

const patched = apply(before, diff(before, after));
patched.n;               // 2
patched.self === patched; // true

RFC 6902

toJsonPatch(diff(["a", "b", "c", "d"], ["b", "c", "d", "a"]));
// [{ op: "move", from: "/0", path: "/3" }]

Real move operations. The RFC defines them and, of the seven implementations measured, not one produces one.

Paths are structured internally rather than being JSON Pointer strings, because a pointer is slash-separated text and cannot say "the entry under this Map key" when the key is an object, or name a Set member at all. toJsonPatch converts what converts and throws UnrepresentablePathError naming the segment it cannot, rather than quietly dropping the operation. Check first with isJsonPatchable, or keep the native operations, which have no such gap.

One interop note: a patch that replaces the document root is valid RFC 6902, and many appliers cannot perform it because they mutate in place and have no reference to swap. apply returns a new document, so it can.

Options

diff(a, b, {
  detectMoves: true,        // report a relocation as one operation
  minMoveDistance: 0,       // how far an index must shift before a move is worth it
  orderedCollections: true, // Map entry order and Set member order are part of the value
});

apply(document, ops, {
  acyclic: false,           // promise there are no cycles and skip the check
});

minMoveDistance is the cost knob, and it trades the way that sentence does not suggest: demoting a relocation to a removal plus an insertion costs one operation more, not fewer. What it buys is a patch that reads more plainly in a review and applies more simply. Zero means nothing is demoted and the patch is minimal, which is the default because the default should be the smallest correct answer.

orderedCollections: false treats two Maps holding the same entries in a different order as equal. Often what you want for a dictionary, and the direction whose mistakes are silent, so it is opt-in rather than the default.

Known coarseness, stated rather than hidden

• A Map or Set is replaced wholesale whenever entry operations cannot reach the target order, because neither has a positional insert. set appends a new key and leaves an existing one where it is, and delete closes the gap, so the only order they can build is "survivors, in the left document's order, then the additions". An entry inserted before an existing one therefore costs a full replacement. Correct, and coarser than the rest of the engine.
• A changed byte in a TypedArray replaces the array rather than addressing the byte.
• apply breaks non-cyclic sharing: if one object is reachable by two paths, the patched document has two. This matches the canonical form underneath, where a diamond and its fully-expanded twin are the same value, and preserving the sharing would make a patch aimed at one path silently change the other.

Depth

Both the walk and the patcher are iterative, so a deeply nested document costs heap rather than call stack, and the cost is linear in both. On a chain of nested objects, every recursive implementation in the field throws RangeError at four thousand levels:

| depth | microdiff | fast-json-patch | just-diff | exactdiff | |---|---|---|---|---| | 1,000 | ok | ok | ok | ok | | 4,000 | RangeError | RangeError | RangeError | 16 ms | | 16,000 | RangeError | RangeError | RangeError | 64 ms | | 64,000 | RangeError | RangeError | RangeError | 141 ms |

This used to be much worse, and the honest history is worth keeping. Giving every subtree its own canonical form costs the sum of all subtree lengths, which is quadratic in depth, so a 160 KB chain reached 2.6 GB of heap and the process died a little past twenty thousand levels. The measured difference:

| depth | before | now | |---|---|---| | 4,000 | 78 ms, 171 MB | 16 ms, 16 MB | | 16,000 | 3,618 ms, 2,592 MB | 64 ms, 25 MB | | 64,000 | out of memory at 6 GB | 141 ms, 64 MB |

Three things got it there, and none of them changed a byte of the canonical form. A node's token is a contiguous range of the root, because the grammar is self-delimiting, so impronta records a start and a length instead of a string per node. The walk looks up ancestors in a map rather than scanning the open path. And a path is held as a link to its parent, built into an array only when an operation is actually emitted, so it costs the size of the answer rather than the size of the input.

The depth exponent is now 0.82 (r-squared 0.99), measured by the harness on sizes up to 8,192.

License

MIT