Code weight: one type dispatch for hashing and equality#

Reviewed executable revision: 3b8412f4 (base 0122da80, the fetched origin/main at review time). This record follows in a documentation-only commit. Work started on 8283f2e8. f4c390a6 merges 0122da80, which does not change packages/db-ivm.

• c0182397 adds the hash identity oracle and the work-cap tests on unchanged production code.
• d1fa5a9a is the refactor.
• b7455952 extends the oracle after mutants on the refactor found three grammar gaps.
• 6073cb13 applies review fixes. It fixes one performance regression and one behavior change, and it closes three more grammar gaps.
• 33603a2f compares type markers by object identity, after an external review found that equality used random numbers as type identity.
• 3b8412f4 runs every oracle law in a module copy whose type markers all collide, generates any value as a Map key, and aims half of the mutations at container nodes.

Each version of the new tests also passes on the base code. The documentation commit that follows also adds comments to the oracle file, with no executable change.

Change#

hashObject and equalHashValues in packages/db-ivm/src/hashing/hash.ts each had a six-way type dispatch: Date, binary, Temporal, RegExp, and the Map/Set/array/object shapes. Each branch had its own hasher or its own comparison. One objectParts(input) function now returns a [marker, header, body?] view that both use. Each marker is a private object that holds a random hash number. Hashing writes the number, and equality compares the objects by identity.

Also removed:

• the four per-type hashers (hashDate, hashUint8Array, hashTemporal, hashPlainObject) and structuralShape.
• the duplicate root and nested paths in getCachedHash.
• the unreachable typeof default: warning in updateHasher. The switch already covers all eight typeof results.

referenceValues moved into isReferenceHashedObject, which both functions already call.

The change is intended to preserve behavior. Hash values change because the binary header is now a string. Hash values were never stable: the markers are random for each process, and nothing persists them.

All numbers come from an esbuild bundle of the public entry, minified.

What earlier versions changed, and what this change keeps#

The audit prototype (ledger IVM-01) and the first port of it changed the behaviors below. This change keeps each one as the base code had it:

1. Work cap. The prototype wrote every header value directly to the hasher. Array lengths and RegExp fields then stopped counting toward MAX_STRUCTURAL_HASH_WORK, so a 1,000,000-element array was accepted instead of rejected. Now header values of a type that has a body go through updateHasher, as before. Date, binary, and Temporal headers still cost nothing.
2. Pair memo. The prototype entered the equality pair memo before it compared headers. That allocated memo entries for every Date, binary, and Temporal pair, and binary equality took 2.3 times as long. The first port moved the whole memo after objectParts, which copies Map and Set entries. Each revisit of a shared or cyclic Map then cost O(entries): 100 revisits of one pair made 200 entry copies instead of 2. Now the lookup comes before objectParts, and the insert comes after the markers and headers match, only for types with a body. That is the base order.
3. Arrays from another realm. instanceof Array is false for an array from another realm, so both versions give it the object marker. The base equality also compared lengths with Array.isArray. The prototype dropped that check. This change keeps it.
4. Header comparison. The first port compared headers with the NaN rule, so a RegExp whose lastIndex is NaN equaled its copy. The base code compared RegExp fields with !==. Headers now compare with ===, and the header of an invalid Date is invalid, so all invalid dates stay equal.
5. Type identity. The base code told types apart with instanceof. The first port compared the random marker numbers, so two types whose numbers collided compared equal, for example an empty Map and an empty Set. Map and array then also gave different results in each argument order. Markers are now objects, compared by identity.

Why a new owner#

Before this change, equalHashValues had no direct test. topKBatch uses it to cancel a retraction against its replacement, and only tests/operators/topk-batch-contract.test.ts reached it. The hash-values owner (hash.property.test.ts) checks pairwise hash laws on flat values. It has no model of equality, and it does not generate Temporal values, RegExp fields, holes, symbol keys, registered handles, File, or Map/Set order.

The new owner, packages/db-ivm/tests/hash-identity-oracle.property.test.ts, checks both functions against one identity model.

Contract, path, and limits#

Authority: the method comments in src/hashing/hash.ts, and the behavior at 8283f2e8.

1. Primitives compare by value. -0 equals 0, NaN equals NaN, and a bigint differs from the equal number. Symbols compare by identity.
2. Functions, registered handles, File values, and binary values over 128 bytes compare by identity.
3. Dates compare by timestamp. All invalid dates are equal.
4. Binary values of at most 128 bytes compare by bytes. Buffer and Uint8Array do not differ.
5. Temporal values compare by type tag and string form.
6. Regular expressions compare by source, flags, lastIndex, and enumerable own properties. The fields compare with ===, so a NaN lastIndex never equals itself.
7. Arrays compare by length and enumerable own properties. A hole differs from undefined.
8. Maps and Sets compare by entries or values in insertion order. Other properties on a Map or Set do not count.
9. Other objects compare by enumerable own string and symbol properties, in any order. The prototype and non-enumerable properties do not count.

The model is a canonical encoding of a value spec, which is plain data. It never reads a production object. The driver builds both sides of a pair as fresh objects from their specs. A seed varies property order, prototypes ({}, Object.create(null), a class instance), hidden non-enumerable properties, Buffer or Uint8Array, extra Map/Set properties, -0 for 0, and sharing or copying of a repeated subtree. None of these changes the identity.

Every law also runs in a second copy of the module, loaded with a captureHashSession tape whose initialization draws are all equal. Every random constant, including every type marker, then has the same number, in any declaration order. A pinned case checks that precondition. In that copy, only the sampled distinct-hash control is skipped.

For each acyclic pair, the check asserts:

• equalHashValues in both argument orders equals the model verdict.
• Equal identities have equal hashes.
• Distinct identities have distinct hashes. This is a sampled control, because a 32-bit hash can collide.

Cyclic values are chains of arrays, Map values, Sets, or plain objects with a back edge to an ancestor. For each one, the check asserts that equalHashValues accepts a second build of the same spec and rejects a build where one leaf holds a text that no pool value has. It also asserts that hash throws Cannot hash cyclic structural values. These verdicts come from construction, so the model needs no bisimulation rule.

hash-work.test.ts pins seven work-cap boundaries. Each case names the largest input that fits, and the next size must throw. One more law counts Map entry copies: equality on 100 revisits of one shared Map pair copies entries twice, once for each side.

Limits:

• Arrays from another realm are outside the grammar. One pinned case holds equality's length check. Hashing gives such an array the object marker, so [1, <hole>] and [1] from another realm hash equal but compare unequal. This mismatch is present on the base revision too.
• Map and Set order sensitivity, and ignored Map/Set properties, are pinned current behavior. No contract promises them.
• Getters and proxies are outside the grammar.
• A RegExp with a NaN lastIndex is outside the grammar. One pinned case holds strict comparison. Hashing normalizes NaN, so that pair hashes equal but compares unequal. This mismatch is present on the base revision too.
• Cycles through a RegExp property, a Map key, or a symbol-keyed property are outside the grammar. So are pairs that differ only in where a back edge points, such as a = [a] against b = [[b]]. Those need a bisimulation model.
• hash and equalHashValues still list enumerable own keys in two ways (Object.keys plus symbols, and Reflect.ownKeys). The oracle's hidden non-enumerable properties catch drift between them: mutant N16 fails.
• Real Temporal types print distinct formats. Only a polyfill-shaped value can share text across types, so one pinned case holds the type tag.

Grammar controls and calibration#

Specs cover every kind in the contract, nested to a small depth. Map keys are any generated value. The model merges primitive keys and shared references that are equal under SameValueZero, as Map and Set do: the first position stays and the last value wins. A pair is either the same spec (30%) or the spec with one near-miss mutation. Half of the mutations target a container node, because leaves outnumber containers:

• Reconstruction: 22 pinned pairs hold one rule each, in both module copies. Six more pinned cases hold the Temporal tag, strict RegExp field comparison, a shared child against two different copies, the cross-realm length check, the colliding-marker precondition, and a topKBatch Map-to-Set replacement with colliding markers. One case builds the same shared/copied spec with 39 seed pairs.
• Ablation and exclusion: the mutants below.
• Range: the positive execution witness requires the fixed campaign (seed 2026930, 300 pairs) to reach all 20 value kinds and all eight mutation classes, to give a false verdict for header, hole, retype, replace, and split mutations, and to give only true for unmutated pairs. It also requires Map keys that are numbers, symbols, references, and containers, and at least one merged Map key.

Each run executes a fixed campaign and a random campaign of 300 pairs for acyclic values, and the same for cyclic values. TANSTACK_DB_IVM_HASH_IDENTITY_SEED and TANSTACK_DB_IVM_HASH_IDENTITY_PATH select a direct replay.

Source mutants on unchanged production (8283f2e8 sources)#

All rows use the tests at 3b8412f4. The columns count failures:

• Identity oracle: hash-identity-oracle.property.test.ts (34 cases).
• Work-cap pins: the seven boundary cases in hash-work.test.ts.
• Pre-existing: every other db-ivm test, with hash-work.test.ts at its origin/main version (589 tests).

A first mutant for W11, "Date equality accepts a non-Date", survived every test. It is equivalent in this domain: the earlier typeof guard rejects a Date compared with a primitive, and no generated object has getTime.

Source mutants on the refactor (3b8412f4)#

N15 changes only work, not identity. The entry-copy law in hash-work.test.ts rejects it with an assertion failure (1 case). The production code before 33603a2f, which compared marker numbers, fails the same 9 oracle cases as N17, including both generated pair campaigns.

History of the grammar gaps:

• N1, N8, N9, and N11 survived the first oracle (c0182397). b7455952 adds Sets of generated values, a Map key rename, a Map-to-Set retype, and two pinned cases.
• N12, N13, N14, and N15 came from review of b7455952. 6073cb13 adds the split mutation, mutations of values under symbol keys, the strict RegExp pin, and the entry-copy law.
• N17 came from an external review of f4c390a6. 33603a2f added a pinned collision at fixed draw positions. 3b8412f4 replaces it with the colliding module copy, which does not depend on declaration order.

Fourteen mutants pass every pre-existing db-ivm test: W5, W8, W11, N1, N5, N7, N9, N11, N12, N13, N14, N15, N16, and N17.

Performance#

hash runs for structural keys and unkeyed consolidation. equalHashValues runs only in topKBatch, for a key with more than one entry in one batch.

Each timing process loads one implementation and runs every workload five times after two warm-up passes. Most workloads use 20,000 values. Processes alternate, and each ratio is the median of 15 processes of each implementation. The machine had a load average of 4.5 to 10 during the run.

Each ratio is new time over base time. The A/A control compares two copies of the base code. Its noise reached ±7% in this run and ±10% in earlier runs.

• Hashing is neutral or faster, except binary values, which are about 10% slower. The murmur stream writes two bytes for each string character, and the base code wrote each byte once.
• Equality on small distinct pairs is 1.3 to 1.4 times slower for join keys and binary values. Each side now builds a parts tuple and a header array. equalHashValues runs only in topKBatch for a key with more than one entry in one batch, so this cost stays on a rare path.
• Equality over a shared Map is faster than the base, and it copies entries once for each distinct pair.

The harness is not checked in. These timings predate 33603a2f, which adds one property read for each hashed object and compares marker objects instead of numbers. They were not rerun for that change.

ORC-001 through ORC-012#

Verification#

On 3b8412f4, the following passed:

• packages/db-ivm Vitest: 42 files, 631 tests, no type errors.
• packages/db-ivm tsc --noEmit: no errors.
• packages/db Vitest, typecheck off: 193 files, 7,162 tests.
• pnpm test:oracles: 49 @tanstack/db files with 2,845 tests, and 16 @tanstack/query-db-collection files with 454 tests and 1 todo.
• pnpm test:minified-db: error names, index metadata, query rows, and live updates.

The environment was Node v24.19.0 and Vitest 3.2.4 on Darwin arm64.

External review follow-up at 33603a2f and 3b8412f4#

The executable fix at 33603a2f follows reviewed PR head f4c390a6 and base 0122da80. An external review found that the refactor used independent 31-bit random hash numbers as equality type discriminators. Those numbers can collide even though the value types differ. With a fresh module and controlled Math.random draws, making only the Map and Set marker numbers equal made equalHashValues(new Map(), new Set()) and its reverse return true on f4c390a6. Both returned false on the base. Making the Map and array numbers equal made Map-to-array return true and array-to-Map return false on the PR. Both directions returned false on the base. Each probe observed 19 draws.

The new pinned oracle first failed on the unmodified PR at the Map/Set assertion (expected true to be false). Each type marker now carries its original random hash number in a distinct private object. Hashing writes that number. Equality compares the marker objects by identity. This keeps the shared type dispatch and its random hash values while separating equality from numeric marker collisions. The same controlled probes then returned false for both pairs in both argument orders. The oracle also checks that topKBatch retains one Map retraction and one Set addition for the same key. The full db-ivm suite passed 625 tests in 42 files. tsc --noEmit -p packages/db-ivm/tsconfig.json, Prettier, and git diff --check passed.

The test checks equality type separation for empty Map/Set and Map/array pairs under forced collisions, plus the corresponding topKBatch output. Distinct marker objects cover the other supported carrier types by the same invariant. The test does not prove hash collision freedom or all live-query histories. 3b8412f4 closes both gaps. The pinned draw-position test is replaced by the colliding module copy, which runs every generated and pinned law with all type markers equal. Generated Map keys now include numbers, symbols, references, and containers, with SameValueZero merging in the model.

Three other external suggestions remain optional. The if (body) test in the header loop is invariant, but runs at most three times for a RegExp and once for an array. Distinct object comparisons allocate two parts tuples. A Map/Set mismatch copied one entries iterator on both the PR and base, while a binary/Date mismatch newly calls String.fromCharCode once. A direct type short-circuit would duplicate the shared dispatch without an established hot path need. For a fresh 16-byte binary value, a deterministic counter observed 56 writeByte calls on the PR and 40 on the base. The earlier review's 10% binary timing and 1.3–1.4× small-pair equality timing were not rerun for this fix. Reintroducing specialized binary hashing remains a conditional performance follow-up, not part of this correctness fix.