types/object: add structurallySame and assertStructurallySame #1538
There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,107 @@ | ||
| ## Replace serialized proof expectations with structural ones | ||
|
|
||
| **Priority:** P4 | ||
| **Status:** open | ||
|
|
||
| ### Problem | ||
|
|
||
| Roughly 105 proof assertions compare `JSON.stringify(value)` against a JSON | ||
| **string literal** instead of stating the expected value directly: | ||
|
|
||
| | File | sites | | ||
| | ---- | ----- | | ||
| | `fjs/djs/tokenizer/proof.f.mjs` | ~14 | | ||
| | `fjs/bnf/ll1/proof.f.mjs` | 34 | | ||
| | `fjs/bnf/descent/proof.f.mjs` | 27 | | ||
| | `fjs/bnf/data/proof.f.mjs` | 4 | | ||
| | `fjs/media/json/serializer/proof.f.mjs` | 11 (serialization **is** the contract — leave alone) | | ||
|
|
||
| ```js | ||
| const result = JSON.stringify(dm) | ||
| if (result !== '{"":{"rangeMap":[[null,64],[{"rules":[]},70]]}}') { throw result } | ||
| ``` | ||
|
|
||
| Serialization is incidental here — the proof wants "is this the dispatch map I | ||
| expect?", not "does it serialize to this text". The string form makes property | ||
| order observable, drops `undefined`-valued properties, and forces the reader to | ||
| parse JSON in their head to see what is being claimed. | ||
|
|
||
| `structurallySame` / `assertStructurallySame` (added in the PR that filed this | ||
| issue, see `fjs/types/object/structurally_same/README.md`) is the comparison | ||
| these sites want. The two sites where serialization was *only* a comparison | ||
| mechanism — `fjs/cas/evo/proof.f.mjs` and `fjs/bnf/proof.f.mjs:105`, both | ||
| `stringify(actual)` vs `stringify(expected)` — were converted there. These | ||
| remaining ones were not, for the reason below. | ||
|
|
||
| ### The obstacle: `undefined`-valued properties | ||
|
|
||
| A mechanical rewrite of the string literal into the equivalent JavaScript | ||
| literal **does not pass**, and this is not a typo-level problem. The BNF | ||
| dispatch entries carry optional properties as *present with value | ||
| `undefined`*, which `JSON.stringify` silently drops: | ||
|
|
||
| ```js | ||
| const dm = dispatchMap(toData(range('AF'))[0]) | ||
| Object.keys(dm['']) // ['emptyTag', 'rangeMap'] — emptyTag is present, and undefined | ||
| ``` | ||
|
|
||
| So `{"":{"rangeMap":[…]}}` is a *lossy projection* of the real value. Under | ||
| `structurallySame`, `{ a: undefined }` and `{}` deliberately differ (a property | ||
| is a property), so the honest literal is | ||
| `{ '': { emptyTag: undefined, rangeMap: […] } }` — every expectation gains | ||
| `emptyTag: undefined` / `tag: undefined` noise that says nothing about the | ||
| grammar under test. That is not obviously an improvement over the JSON string, | ||
| which is why this needs a design decision rather than a mechanical pass. | ||
|
|
||
| A second, smaller loss: `fjs/bnf/data/proof.f.mjs`'s `emptyTagMap` expectations | ||
| (`'{"5":true,"":"e"}'`) are order-sensitive today purely because they are | ||
| strings. `structurallySame` ignores property order by design, so converting | ||
| them silently drops an assertion nobody wrote on purpose — fine if intended, | ||
| but it should be intended. | ||
|
|
||
| ### Proposal | ||
|
|
||
| Decide which of these is true, then apply it uniformly: | ||
|
|
||
| 1. **The `undefined` properties are the defect.** `dispatchMap` and friends | ||
| should not emit `emptyTag: undefined` / `tag: undefined` at all — omit the | ||
| key instead. Then the mechanical rewrite works, the expectations read | ||
| cleanly, and the data structures stop carrying properties that mean | ||
| "absent". Check what consumes `emptyTag` before changing its shape. | ||
| 2. **The `undefined` properties are intended**, and the proofs should spell | ||
| them out. Verbose but honest; the expectation then documents the real value. | ||
| 3. **`structurallySame` should treat an `undefined`-valued property as | ||
| absent.** This would match how the repo already treats `StringMap<T>` — | ||
| `{readonly[k in string]?: T}`, iterated with `definedEntries` / | ||
| `definedValues` precisely because an `undefined` value is not an entry | ||
| (AGENTS.md §6.2). It contradicts the semantics `structurallySame` shipped | ||
| with, so it is a breaking change to that helper and needs its own argument, | ||
| not a drive-by flip. Note that option 3 also removes the reason option 1 | ||
| exists, so pick one, not both. | ||
|
|
||
| Option 1 is the most likely right answer — it fixes the data rather than the | ||
| comparison — but it is a change to `fjs/bnf`, not to the proofs, and should be | ||
| measured against what reads `emptyTag`. | ||
|
|
||
| ### Tasks | ||
|
|
||
| - [ ] Decide between the three options above; record the reasoning in | ||
| `fjs/bnf/README.md` (option 1/2) or | ||
| `fjs/types/object/structurally_same/README.md` (option 3). | ||
| - [ ] Convert the `fjs/bnf/ll1`, `fjs/bnf/descent`, `fjs/bnf/data` and | ||
| `fjs/djs/tokenizer` expectations accordingly. | ||
| - [ ] Confirm the `emptyTagMap` expectations do not depend on property order, | ||
| or keep those specific ones as strings and say why. | ||
| - [ ] Leave `fjs/media/json/serializer/proof.f.mjs` as string comparisons — | ||
| serialized text is that module's contract. | ||
| - [ ] `npx tsc`, `fjs test`. | ||
|
|
||
| ### Related | ||
|
|
||
| - `fjs/types/object/structurally_same/README.md` — the comparison these sites | ||
| should use, and what it does and does not promise. | ||
| - `fjs/cas/evo/proof.f.mjs`, `fjs/bnf/proof.f.mjs` — the two sites already | ||
| converted; both compared two *values*, so neither hit the `undefined` | ||
| problem. | ||
| - AGENTS.md §6.2 (`StringMap` / `definedEntries`) — the precedent option 3 | ||
| would be aligning with. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,65 @@ | ||
| # Structurally same | ||
|
|
||
| ## Why this is its own module | ||
|
|
||
| `structurallySame` is the comparison behind `assertStructurallySame` in | ||
| [`fjs/asserts`](../../../asserts/module.f.mjs), and it is also an ordinary | ||
| object helper that belongs on [`fjs/types/object`](../module.f.mjs). Those two | ||
| homes cannot both be the implementation: the object module imports | ||
| `types/nullable`, which imports `fjs/asserts`, so an assertion module importing | ||
| the object module would close the runtime cycle | ||
| `asserts -> object -> nullable -> asserts`. | ||
|
|
||
| So the implementation lives here, in a leaf that imports **nothing**, and the | ||
| two consumers reach it from opposite directions — `fjs/asserts` imports it | ||
| directly, and `fjs/types/object` re-exports it as part of its public API. Adding | ||
| any import to this module re-opens the cycle; keep it a leaf. | ||
|
|
||
| ## What it compares, and what it does not | ||
|
|
||
| The contract is FunctionalScript data — primitives, arrays, and record-like | ||
| objects: | ||
|
|
||
| - `Object.is` decides first, so `NaN` is the same as `NaN`, `0` and `-0` differ, | ||
| and a value is trivially the same as itself. | ||
| - Arrays match arrays of equal length, elementwise. An array never matches a | ||
| non-array. | ||
| - Other objects match on their own enumerable string properties as a *set* — | ||
| order is not part of the structure — with every value compared recursively. | ||
| A property whose value is `undefined` is a property, so `{ a: undefined }` and | ||
| `{}` differ. | ||
|
|
||
| The signature takes `unknown` because assertion and parsing boundaries have | ||
| nothing narrower to offer, but a wide input type is not a promise of wide | ||
| semantics. A date, map, set, or typed array is compared **only** by its own | ||
| enumerable string properties, which for most of them is no properties at all — | ||
| two different `Date`s read as the same. Prototypes, property descriptors, | ||
| symbol keys, and getters are all invisible here. A caller needing any of those | ||
| needs a different comparison, not a flag on this one. | ||
|
|
||
| There is no cycle detection: a self-referential value recurses until the stack | ||
| runs out. FunctionalScript data is acyclic, so a seen-set would tax every real | ||
| comparison to catch a case that cannot occur. | ||
|
|
||
| Array comparison likewise assumes **dense** arrays. `Array.prototype.every` | ||
| skips a sparse array's holes, so a hole-bearing first operand would compare | ||
| vacuously equal in one direction and not the other. That asymmetry is | ||
| unreachable rather than handled: FunctionalScript has no way to build a sparse | ||
| array — `new Array(n)` is not part of the language — so the input cannot occur, | ||
| and spreading every array into a dense copy to defend against it would cost an | ||
| allocation per comparison for a value that cannot exist. Callers reaching this | ||
| from plain JavaScript with a hand-built sparse array are outside the contract, | ||
| like the host objects above. | ||
|
|
||
| ## Why proofs should prefer it to `JSON.stringify` | ||
|
|
||
| Proofs reached for `assertEq(JSON.stringify(a), JSON.stringify(b))` because no | ||
| structural comparison existed. Serialization answers a different question and | ||
| drags in semantics the proof did not ask for: property order becomes | ||
| observable, `undefined`-valued properties vanish, `NaN` and the infinities | ||
| collapse to `null`, `-0` becomes `0`, `bigint` throws, and both sides allocate | ||
| strings only to be thrown away. | ||
|
|
||
| Keep a string comparison where the serialized text *is* the contract — a | ||
| serializer's own proofs, or an API that returns text. Everywhere else, state the | ||
| expected value directly and compare it with `assertStructurallySame`. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,59 @@ | ||
| /** | ||
| * Structural comparison for FunctionalScript data. | ||
| * | ||
| * `structurallySame` answers "do these two independently constructed values | ||
| * have the same shape and the same leaves?" — the question proofs really ask | ||
| * when they compare a computed value against an expected one. It is scoped to | ||
| * FunctionalScript data (primitives, arrays, and record-like objects) and | ||
| * deliberately says nothing about dates, maps, sets, typed arrays, prototypes, | ||
| * or property descriptors; see the README for what it does *not* promise. | ||
| * | ||
| * This module is a dependency-free leaf on purpose. `fjs/asserts` needs the | ||
| * comparison for `assertStructurallySame`, and the public object module | ||
| * (`../module.f.mjs`) reaches `fjs/asserts` through `types/nullable`, so | ||
| * importing anything here would close the cycle | ||
| * `asserts -> object -> nullable -> asserts`. Keep it importing nothing. | ||
| * | ||
| * @module | ||
| */ | ||
|
|
||
| const { entries, is } = Object | ||
|
|
||
| /** | ||
| * Compares two values structurally. | ||
| * | ||
| * - `Object.is` decides first, so `NaN` equals itself, `0` and `-0` differ, and | ||
| * an object is trivially the same as itself. | ||
| * - Anything else that is not a non-null object differs. | ||
| * - Arrays match arrays of the same length whose elements match pairwise; an | ||
| * array never matches a non-array. Arrays are assumed dense — FunctionalScript | ||
| * cannot build a sparse one; see the README. | ||
| * - Other objects match when their own enumerable string properties form the | ||
| * same set — order is irrelevant — and every property's value matches. A | ||
| * property whose value is `undefined` is a property: `{ a: undefined }` and | ||
| * `{}` differ. | ||
| * | ||
| * There is no cycle detection: a self-referential value recurses until the | ||
| * stack runs out. FunctionalScript data is acyclic, and adding a seen-set would | ||
| * cost every ordinary comparison for a case that cannot arise. | ||
| * | ||
| * @type {(a: unknown, b: unknown) => boolean} | ||
| */ | ||
| export const structurallySame = (a, b) => { | ||
| if (is(a, b)) { return true } | ||
| if ( | ||
| typeof a !== 'object' || a === null || | ||
| typeof b !== 'object' || b === null | ||
| ) { return false } | ||
| if (a instanceof Array) { | ||
| return b instanceof Array | ||
| && a.length === b.length | ||
| && a.every((v, i) => structurallySame(v, b[i])) | ||
|
There was a problem hiding this comment.
When the first operand is sparse, Useful? React with 👍 / 👎.
Contributor
Author
There was a problem hiding this comment. FunctionalScript doesn't allow
Contributor
Author
There was a problem hiding this comment. Agreed, and thanks — I'd started down the wrong path here. I had pushed a The asymmetry is now recorded as out of scope rather than silently dropped, in
Generated by Claude Code There was a problem hiding this comment.
When two distinct but equal values contain a few thousand nested arrays, this recursive call throws Useful? React with 👍 / 👎. There was a problem hiding this comment.
When independently constructed acyclic values share substructure, this traversal re-compares the same object pair once per incoming reference. For example, repeatedly forming Useful? React with 👍 / 👎. |
||
| } | ||
| if (b instanceof Array) { return false } | ||
| const ae = entries(a) | ||
| /** @type {ReadonlyMap<string, unknown>} */ | ||
| const bm = new Map(entries(b)) | ||
| return ae.length === bm.size | ||
| && ae.every(([k, v]) => bm.has(k) && structurallySame(v, bm.get(k))) | ||
| } | ||
Oops, something went wrong.
Oops, something went wrong.
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This code change exports
structurallySameandassertStructurallySameas new public APIs, but the commit has no entry underCHANGELOG.md'sUnreleasedsection. That omits the feature from release notes and from the changelog-driven versioning process; add the required short entry with the real PR number.AGENTS.md reference: AGENTS.md:L1194-L1203
Useful? React with 👍 / 👎.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Already done — the entry landed in 025acec, one commit after the 8723489 this review ran against. AGENTS.md §8.3 has the entry created after the PR exists so it can cite the real number, so the gap between the two commits is expected.
Generated by Claude Code