exactdiff

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

What this is

You have two versions of the same value: the document as it was, and the document as it is now. A structural diff is the list of changes that turns the first into the second, written as operations over the structure itself (set this key, remove this element, replace this value, move this row) rather than as changed lines of text. A text diff is the right tool for prose and source files. A structural diff is the right tool for the objects a program holds in memory, the row it is about to write, the state it is about to send to a client.

That list is worth having as data rather than as a rendering. JSON Patch, RFC 6902, is the standard way to write one down: a JSON array of operations, each carrying an op and a path such as /users/3/email. Because it is plain data it travels. You can log it, keep it as a revision, send it over a socket, and apply it at the other end to arrive at the same document without shipping the document.

The hard part is not the list. It is the equality test underneath it, because JavaScript does not hand you one. === on two objects asks whether they are the same object, not whether they hold the same thing. JSON.stringify builds a string you can compare, and it cannot see inside a Map or a Set, drops undefined, refuses a BigInt, throws on a cycle, and prints 0 and -0 the same way. So implementations do the only thing left: walk both values and handle the types they thought of. Whatever was not on that list is where the wrong answers come from, in both directions.

And a diff makes two promises, of which only one 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, four 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.

Install

npm install exactdiff

Use

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

diff(a, b) returns the operations that turn a into b, in order, each one applying to the document as the previous one left it. apply(document, ops) returns a new document with them applied and never mutates the one you handed it. toJsonPatch(ops) converts to RFC 6902 for every path a JSON Pointer can address, and says so by name when a path is outside the format.

Where this earns its place

The shape to look for is always the same: two versions of a value richer than JSON, where acting on a difference costs something. The cost is what makes exactness matter. If a spurious operation only makes a log line slightly wrong, any library in this field will do. If it triggers a write, a rerender, a webhook or a permanent record, the second promise is the one you are buying.

Deciding whether to write at all. Persist when the document changed, skip when it did not. A phantom operation here means a write on every tick: a version bump, an invalidated cache, replication traffic, a webhook fan-out, and an updatedAt that has stopped telling anyone anything. The answer that path depends on is the empty patch, and an empty patch is what equal values produce here for every type at once rather than for the types somebody remembered.

Audit trails and revision history. Keep the operations between successive states and you can replay any version from a base, with each entry standing as a claim about what somebody did. A change reported that nobody made is a false record, and a real change missed is a gap no later reader can detect from the log itself. Real move operations also matter for reading: "this row went from position 0 to position 3" is what happened, where four replacements describe the array rather than the edit.

Optimistic UI and state reconciliation. The client applies its own change immediately, the server answers with authoritative state, and you reconcile by patching the local tree instead of replacing it, so component identity, focus and scroll position survive. Both failure directions bite here: a phantom patch is the poll, write, poll loop, and a missed change is an interface that silently disagrees with the server. A list reorder arriving as one move also keeps the churn down to the elements that actually moved.

Sync protocols, where you send the patch and not the document. Use toJsonPatch on the wire when the state is JSON-shaped, and the native operations when it is not, because a JSON Pointer cannot address an entry under a Map key that is itself an object, and cannot name a Set member at all. apply returns a new document rather than mutating in place, so a patch that replaces the root works, which is valid RFC 6902 and something many appliers cannot perform.

Test assertions and review of two snapshots. "What changed between these two values" as a short list beats two printed objects side by side. This one reports the differences a JSON round trip erases on the way: a Map entry, a Set member, a byte in a TypedArray, 0 against -0, and two instances of different classes whose fields line up exactly.

Routing on what changed. Every operation carries a structured path, so "the shipping address changed" is a predicate over paths rather than a second comparison of the subtree. Because a segment holds a Map key as a value rather than as text, that predicate can name locations a pointer string cannot spell.

Where it does not fit needs the measurements first, so it comes after them.

Measured, against the field

By diff-conformance, a harness written before this engine existed. I wrote that one too, so the zero below is a score I gave myself, and you should read it knowing that. What stands against the conflict: the harness is a separate package with fixed public probes, it ships adapters for the field and none for this library, and you can install it and score any subject yourself rather than taking my word for a row.

Regenerate with npm run conformance. Only rfc6902 is a devDependency here, so a fresh clone scores two subjects and the report names the six it did not measure. Install the rest of the field for all eight rows:

npm i -D fast-json-patch just-diff deep-object-diff jsondiffpatch microdiff json-diff-ts

One asymmetry inside that run: each built-in subject is scored in a child process and this one cannot be, because a subject defined in the repository is a closure and a closure does not cross a process boundary. It is scored in process, on the same probes.

| 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 | 8 (34.8%) | 1 (7.1%) | 21.0% | | 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 score next to what it costs below: on one of those detection 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, with no field a caller could nominate as a key | 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, where an objectHash callback has nothing to read | 1 | 3 | 1 | missed | missed | missed, 3 |

One of the 23 detection probes is answered by this library and by nothing else in the field: same fields, different class.

Of the 5 subjects that ship an applier, it is the only one whose patch, applied, restores the right value on every probe it detects: 0 failures over 21, against 2 to 5 for the rest. The other 3 do not ship one, which is a legitimate scope decision and is not scored against them.

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 WeakSet, 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 9.2x 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. One changed field in a list of rows:

| document | diff | tracker | microdiff | fast-json-patch | |---|---|---|---|---| | 100 rows, 17 KB | 0.293 ms | 0.162 ms | 0.046 ms | 0.030 ms | | 1,000 rows, 170 KB | 3.93 ms | 2.12 ms | 0.459 ms | 0.324 ms | | 5,000 rows, 849 KB | 21.1 ms | 11.6 ms | 2.28 ms | 1.56 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 on the largest document here it runs about 1.8x faster than diff.

Every millisecond in this README comes from npm run bench, which writes bench/results.json; every probe count and error rate comes from npm run conformance, which writes bench/conformance.json. Both tables are then written into this file by npm run bench:render, and prepublishOnly refuses to publish a README that disagrees with either file. No figure here was typed by hand.

The run behind them: 9 replicates, each a separate process, 7 interleaved trials inside each, on Apple M4 / 10 cores / Node v22.14.0. Two subjects are ordered only when every replicate agreed on the direction, which under the null that they are equally fast has p = 2^(1-9) = 0.0039 per pair; a pair the replicates split is reported as unordered rather than rounded into a winner. Re-running the whole thing moves a cell by up to 23.2% of its own value, so read the order and the magnitude, not the digits.

Rivals: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected].

Inside that number there is one knob worth knowing about, because it is the whole trade between a wide document and a deep one. A node is identified either by its own canonical token or by an interned id, chosen on the length of the token. Both routes are exact and the threshold only decides which is cheaper: materializing a short token and comparing it as a string is what a wide, shallow document wants, and materializing a long one is the quadratic that would make a deep document impossible. The length is a property of the node, which both sides of a comparison share whenever they are equal, so two equal values are never identified by different routes.

The growth exponents are 0.96 (r-squared 0.98) on width and 0.84 (r-squared 0.99) on depth, so this is a constant factor and not a worse complexity class on either axis. Each is a fit through 5 points on one machine and it moves between runs at the second digit, which is what the harness says about that column too: read the order, not the digits.

It is near the bottom of the field on that document, 7 of 8 that finish, with jsondiffpatch behind it, and the whole field on the same input is the fair way to say so:

| | ms | |---|---| | fast-json-patch | 1.56 | | microdiff | 2.28 | | deep-object-diff | 3.36 | | just-diff | 9.56 | | exactdiff, tracker | 11.6 | | json-diff-ts | 13.5 | | exactdiff, diff | 21.1 | | jsondiffpatch | 45.4 | | rfc6902 | overflows the call stack |

tracker is 5 of 8. Two of the entries above it 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.

When not to use this

Both ends, because a package that only names where it wins is advertising.

Your documents carry functions, symbols, WeakMaps, WeakSets, WeakRefs or Promises. The refusal above is total, so a component's props, a config object with a handler in it, or a container holding a factory is simply outside this library today. microdiff and deep-object-diff diff around such a value without complaint, and if that is the shape you have, use one of them.

Speed is the axis and the values are plain JSON. On the 5,000-row document fast-json-patch finishes in 1.56 ms and microdiff in 2.28 ms where diff takes 21.1 ms, and both have years of production exposure behind them. If a diff runs on every keystroke or every request, weigh that against how many of the harness probes involve types your documents cannot contain in the first place.

What you want is a text diff. Two strings are equal or they are not, and an unequal pair is one replace of the whole string. Nothing here looks inside one. For prose, for source code, for anything whose interesting unit is a line or a character, use a text diff and keep this for the structure around it.

The patch has to be as small as physically possible. A changed string is replaced whole, and two containers are deliberately coarse for the reasons in known coarseness: a changed byte replaces the whole TypedArray, and a Map or Set whose target order entry operations cannot build is replaced wholesale. If you are paying by the byte on the wire, those three are where the bytes go.

You need merge, inversion or conflict resolution. This computes the operations from one state to another and applies them. There is no inverse patch, no three-way merge and no conflict model, so an undo stack has to keep the states themselves, or the operations in both directions. jsondiffpatch ships reverse and unpatch if an invertible delta is the thing you actually want, and if two people can edit the same document at the same time the honest answer is not a diff at all: use a CRDT such as yjs or @automerge/automerge, which are built for exactly the case a patch between two states cannot express.

You would rather have mileage than a score. It is new. The alternatives have between 300k and 8M downloads a week and years of production exposure, which no test suite substitutes for; this has a test suite and a conformance score. Every wrong answer found here becomes a probe in the harness, so the next one has somewhere to be caught, and that is a process rather than a track record.

What is left, and what this is for: values richer than JSON, in a pipeline where a change reported wrongly costs a write, a record or a loop.

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.

API

diff(a: unknown, b: unknown, options?: DiffOptions): Operation[]
tracker(options?: DiffOptions): (next: unknown) => Operation[]
apply(document: unknown, ops: ReadonlyArray<Operation>,
      options?: { acyclic?: boolean }): unknown

toJsonPatch(ops: ReadonlyArray<Operation>): JsonPatchOperation[]
isJsonPatchable(ops: ReadonlyArray<Operation>): boolean
toPointer(path: Path): string

planSequence(keysA: ReadonlyArray<string>, keysB: ReadonlyArray<string>,
             options?: { detectMoves?: boolean; minMoveDistance?: number }): SequencePlan
longestIncreasingRun(values: ReadonlyArray<number>): number[]

type Segment =
  | { in: "object"; key: string }
  | { in: "array"; index: number }
  | { in: "map"; key: unknown }      // the key itself, not a rendering of it
  | { in: "set"; member: unknown }

type Path = ReadonlyArray<Segment>

type Operation =
  | { op: "add"; path: Path; value: unknown }
  | { op: "remove"; path: Path }
  | { op: "replace"; path: Path; value: unknown }
  | { op: "move"; from: Path; path: Path }

type JsonPatchOperation   // the same four, with a JSON Pointer string for each Path

interface DiffOptions {
  detectMoves?: boolean         // default true
  minMoveDistance?: number      // default 0
  orderedCollections?: boolean  // default true
}

interface SequencePlan {
  removed: number[]                      // indices into A that are not in B
  added: number[]                        // indices into B that are not in A
  kept: Array<{ a: number; b: number }>  // matched, relative order unchanged
  moved: Array<{ a: number; b: number }> // matched, has to be relocated
}

apply returns unknown, so a typed caller casts at that boundary. It never mutates what it is given, and with an empty patch it returns the same document rather than a copy, which is the fast path a sync loop hits on every unchanged tick.

Three errors, each exported as a class so you can catch it by name rather than by matching a message:

• UnrepresentableValueError, from diff and tracker, when either document holds a function, a symbol, a WeakMap, a WeakSet, a WeakRef or a Promise. It carries a path string pointing at the value. Raised inside impronta and re-exported here, so the name the documentation gives you is a name this package has.
• UnrepresentablePathError, from toJsonPatch and toPointer, for a Map or Set segment that no JSON Pointer can address. It carries the segment it choked on. Call isJsonPatchable first to ask without catching.
• PatchError, from apply, when an operation does not fit the document it is handed: a path that leaves it, a descent into a non-container, a replace aimed at a Set member, a remove of the root.

planSequence and longestIncreasingRun are the move detector, exported because they are the part most likely to be useful on their own. planSequence takes two arrays of content keys, already computed by the caller, and classifies every element; longestIncreasingRun is the patience-sorting longest increasing subsequence it decides on, returning the positions rather than only the length.

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. Every subject below was given a chain of nested objects with one changed leaf and asked for a diff, climbing until it broke. cold is the first call in a fresh process; warm is the same ladder after 140 calls at 1,000 levels, in a process that has done nothing else either way:

| subject | deepest that works, cold | warm | |---|---|---| | exactdiff, diff | no ceiling up to 250,000 | same | | exactdiff, tracker | no ceiling up to 250,000 | same | | fast-json-patch | 2,000 (RangeError at 4,000) | 4,000 | | microdiff | 2,000 (RangeError at 4,000) | 2,000 | | deep-object-diff | 1,000 (RangeError at 2,000) | 4,000 | | just-diff | 1,000 (RangeError at 2,000) | 4,000 | | jsondiffpatch | no ceiling up to 250,000 | same | | json-diff-ts | 1,000 (RangeError at 2,000) | 2,000 | | rfc6902 | 1,000 (RangeError at 2,000) | 4,000 |

Depth is therefore not this library's ground. jsondiffpatch handles the same chain without a stack limit either, and does it on the first call. At 64,000 levels it is also faster than this library: 41.9 ms against 80.5 ms for tracker. If nesting is the only thing pushing you here, that is the cheaper answer.

The 6 that overflow do it between 2,000 and 4,000 levels, and the two columns are why that is a range and not a number. A recursive function reaches deeper once V8 has optimized it, because an optimized frame is smaller than an interpreted one, so a stack ceiling is a property of the library and how warm it is, together: 5 of the 6 climb further once warm, by up to 4x. Quote the cold column if you want the reproducible end and the answer a first call gets; quote neither as a guarantee.

Three things keep the cost linear here, and none of them touches 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 rather than a string per node; giving every subtree its own materialized form would cost the sum of all subtree lengths, which is quadratic in depth. 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.

License

MIT