JSON Schema: recursive schemas via the RTTI data form - #1542

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 6c44251965

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: c783aeac35

Approving. Baseline: origin/main = 699c960e ("types/object: add structurallySame ... (#1538)").

Since this builds on #1539, I concentrated on the place the underlying data form was weakest — recursion across differently-named rules, not just self-reference — and checked the properties with real numbers rather than reading the proof.

Corpus. 247 schemas: primitives, consts, containers, unions, structs and tuples, plus twelve recursive rules with distinct names — list (self-array), rec (self-record), lock (cycle closing through an anonymous or, i.e. the empty-string-named rule), the tree/forest pair, a three-name cycle aN -> bN -> cN -> aN, the p/q record pair, and an even/odd pair recursing through object properties rather than containers — each also wrapped in array/record/or/option/tuple/struct, and every ordered pair or(recA, recB) of the twelve.

Structural properties.

• Dangling $ref: 0. Every $ref in every emitted document (root and inside $defs) resolves to an existing $defs entry, after undoing the percent-encoding and JSON Pointer escaping.
• Unreachable $defs: 0. No definition is emitted that nothing references.
• Idempotence / determinism: 0 failures. toJsonSchema(t) is byte-identical to dataToJsonSchema(toData(t)) for all 247, and identical across repeated calls.
• Round-trip against the module's own type: 29/29. Each emitted document — including every recursive one — validates against toData(schema.unknown) via rtti/data's own validate, so the Unknown annotation is true at runtime and not just at the type level. Negative control: { type: 'bogus' } comes back error.

Semantic agreement. I wrote a small evaluator for exactly the keyword subset emitted ($ref/$defs/type/const/not/anyOf/items/prefixItems/properties/required/additionalProperties, erroring on any other keyword) and compared its accept/reject verdict against rtti/data's validate over 7,904 (schema, value) probes — 2,002 accepted and 5,326 rejected by rtti, so both verdicts are well represented. 43 mismatches, and every one falls into a class that is identical on origin/main:

1. bigint -> { "type": "integer" } and bigint consts -> { "const": Number(v) } (4). rtti rejects the JS number 0 where the JSON Schema accepts it. This is the documented lossy mapping in the module's own table — JSON has no bigint — not a defect.
2. A tuple emits prefixItems + "items": false with no minItems (39). Draft 2020-12 prefixItems does not imply a minimum length, so toJsonSchema([number, string]) accepts [] and [1] while the rtti type does not. Pre-existing — main emits the same {"type":"array","prefixItems":[…],"items":false} for the same input — so not a regression here, but worth recording since this module is now the recursion path too.

Negative control for the whole harness: perturbing one $defs entry makes it report 1,056 acceptance mismatches and 210 idempotence failures instead of 43 and 0.

Effect on existing (non-recursive) inputs — the §8.4 question. Routing through toData changes the text of the output for 11 of 36 non-recursive schemas I compared against main: or() / never goes {"anyOf":[]} -> {"not":{}}, anyOf members reorder into canonical kind order, or(true,false) -> {"type":"boolean"}, or(42, number) -> {"type":"number"}, and the empty tuple / empty struct lose their empty prefixItems / properties.

I checked whether any of that is semantically breaking: over 1,152 acceptance probes on those same non-recursive schemas, main and this head agree on every single value — 0 differences. So the change is representation-only in the sense that matters, which puts it with #1524 (representation-only, no prefix) rather than #1520 (specifier-level break, prefix), and the absence of **BREAKING CHANGES:** is right. The CHANGELOG entry does say the output is canonical and that anyOf members and object keys follow the data form's order, so a consumer diffing schema text is warned.

One of those 11 is a genuine fix rather than a reshuffle: {"anyOf":[]} is not a valid draft 2020-12 schema (anyOf must be a non-empty array), so never used to emit something a real validator would reject at schema-compile time. {"not":{}} is correct.

One pre-existing upstream limit, for the record. 18 of the 144 or(recA, recB) pairs — unions mixing a record-recursive rule (rec, lock, p, q) with a property-recursive one (even, odd) — blow the stack. The throw is in toData, not in this module: toData(or(rec, even)) raises the same RangeError on its own, and origin/main's toJsonSchema fails identically. So it is the #1539 layer, not this PR, and the module's "the data form is a finite graph, so recursive schemas terminate" claim holds for everything toData can actually represent. Flagging it only because this PR is what makes those inputs reachable in practice.

Battery

• npx tsc --noEmit — exit 0.
• npm run prepack from a freshly cleaned tree — exit 0.
• npm test — 2642 pass / 0 fail, against 2617 / 0 on origin/main: +25, matching the new proof cases.
• node bin/linkcheck.mjs — broken-link sets identical to main. The deleted fjs/media/json/todo/rtti-recursive-json-schema.md has no remaining references anywhere in the tree, and revision-lock-map.md's two links to it are rewritten rather than stranded.
• Declaration emit (§6.2): fjs/media/json/schema/module.f.d.mts has zero elided and zero type-level any (I looked at the matches — nothing, so not even a JSDoc-prose false positive to discount), and main is likewise zero. The @module header survives with its blank line intact. unknown still emits Phantom<typeof unknownThunk, _UnknownConst> with the recursive positions named, not collapsed.
• Public surface (dual-axis, prepack in both trees): one new exported const, dataToJsonSchema: (data: Data) => Unknown, which the CHANGELOG names. Type additions are _List, _Tree, _Forest, _Lock, _Rec — all proof-local and all _-prefixed per §6.2 — plus new fields on the already-_-prefixed _UnknownConst. No new unprefixed public export type, so the recurring defect in this series is absent here.

Conventions. §8.3: code change, entry present, links only /pull/1542. §8.4: no prefix, correct per the acceptance-equivalence result above.

Addendum — correcting my own review above.

The head moved while I was writing that review. Everything in it was verified at d37b031c, but it went up carrying a reviewed-head marker for c783aeac. Saying that plainly rather than leaving it: the marker was ahead of the evidence at the moment I posted. I have now re-run the work at c783aeac and everything in the approval still holds —

• recursion corpus: 247 schemas, 0 dangling $ref, 0 unreachable $defs, 0 idempotence failures, 43 acceptance mismatches over 7,904 probes in exactly the two pre-existing classes described above;
• non-recursive comparison against main: 11 of 36 schemas change text, 0 acceptance differences over 1,152 probes;
• npx tsc --noEmit exit 0; npm test 2645 pass / 0 fail (was 2642 at d37b031c, 2617 on origin/main) — the +3 are the new prototype-name proofs.

One thing the new commits add that I do want to raise (§8.3).

c783aeac is not confined to fjs/media/json/schema: it also changes fjs/types/rtti/data/module.f.mjs, switching resolve from rules[n] to at(n)(rules). That is a genuine fix — a RuleSet is a plain object, so a rule name that happens to be an Object.prototype member used to resolve through the prototype chain instead of coming back undefined.

It is also user-visible, which I checked rather than assumed. Comparing validate([{}, name])(1) on origin/main against this head for the Object.prototype member names:

8 of 9 names change behaviour, and the new behaviour is the right one: a reference to a missing definition is malformed data and should panic, exactly as 'nope' already did. So no objection to the change itself.

The gap is that the CHANGELOG entry covers only media/json/schema — toJsonSchema supporting recursive schemas — and says nothing about types/rtti/data. §8.3 wants code changes to get an entry, and this is a behaviour change in a different, already-released module that a consumer of rtti/data's validate could observe without touching JSON Schema at all.

I am flagging this specifically because of the shape it shares with #1540, where a separate unmentioned tightening rode along with the documented no-op and the CHANGELOG described only the latter. The fix here is smaller and strictly an improvement, so I am not withdrawing the approval — but a second bullet naming types/rtti/data (rule lookups are own-property only, so a name shadowing an Object.prototype member is now correctly a missing definition) would make the released history honest about what shipped.

Nothing else changed between the two heads: the rest is the matching refSchema/admitsUndefined switch to at in the schema module and two new proof cases.

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: f8e6d1a1b2

Re-reviewed at f8e6d1a1, previously approved-with-one-finding at c783aeac. Baseline is current origin/main = e692e595. The delta is one substantive commit (13b97749, minItems for tuple prefixes + closing the subset memo over read-sets) plus a merge of main.

The open finding is resolved

The previous round's finding was that the CHANGELOG documented only media/json/schema while the PR also made types/rtti/data's resolve own-property-only, which is user-visible. There is now a second entry naming types/rtti/data. I re-derived each of its claims rather than taking them on the entry's word, at f8e6d1a1 against e692e595:

• "a name shadowing an Object.prototype member … is a missing definition for validate/subset." Accurate, and the wording is right about how it fails. At this head validate([{}, 'toString'])(1) throws assertion failed — byte-identical to validate([{}, 'nosuchrule'])(1), i.e. it really is treated as a missing definition, not as an error Result. Same for constructor, and subset([{}, 'toString'])([{}, 'toString']) throws too. On main those three return ["error", …], ["error", …] and true respectively, because the name resolved through the prototype.
• "an ordinary extra key when validating values." Accurate. With { props: {}, rest: string }, validate(…)({ toString: 1 }) now returns ["error",{"path":["toString"],"message":"unexpected value"}] and { toString: 's' } returns ok — i.e. the key is checked against rest like any other. On main { toString: 1 } returned ok, the key having been silently treated as declared.
• The undefined-valued-own-property edge is handled correctly: at is getOwnPropertyDescriptor + fromUndefined, so at(k)(o) === null holds exactly when the key is absent or its own value is undefined. That is precisely the old o[k] === undefined test minus the prototype chain, so the substitution narrows the behaviour on nothing but shadowing.

The new commit

Termination. The entry claims subset and toData's coverage collapse "now terminate on unions mixing rest-based and property-based object recursion". Reproduced — main really does diverge, this head does not:

(run with --stack-size=2000.) The mechanism matches the diff: main keyed the coinductive memo only when both sides were rule references, so a read-set synthesized from a rest reference was an inline UnionSet and never closed the cycle; _Keyed's u:<name> identity closes it. The answers are also sound, not merely terminating — s ⊆ t holds coinductively, t ⊄ s because a t-object need not carry a, and p ⊄ q because p's undeclared keys are unconstrained (rest: undefined is open, per objectSetValidate).

minItems. Emitted only for a non-empty prefix (...(p.prefix.length === 0 ? {} : { prefixItems, minItems })), so the entry's "a non-empty tuple prefix emits minItems" is exact. toJsonSchema([0, '']) gives …"prefixItems":[…],"minItems":2,"items":false where main gave no minItems — main's schema accepted [] for a two-element tuple. It matches the RTTI semantics exactly: arraySetValidate rejects value.length < prefix.length unconditionally, with no exemption for prefix elements admitting undefined, so minItems: prefix.length cannot over-constrain.

Not a **BREAKING CHANGES:** entry

§8.4 keys the prefix to a change that breaks the public API, and every existing BREAKING entry in this CHANGELOG is an API-shape change (removed export, moved specifier, changed symbol value). Nothing here alters a signature or an export location — the surface diff below is one addition and no removals — and the behaviour that changed was either wrong (prototype leakage, under-constrained tuples) or a crash. Same conclusion as the previous round.

Battery, at f8e6d1a1 from a freshly cleaned tree

• npx tsc --noEmit — exit 0.
• npm run prepack — exit 0 (both passes); also on fs-main for the surface diff.
• npm test — pass: 2646, fail: 0. main at e692e595: pass: 2617, fail: 0. The +29 is the PR's own new proofs (schema/proof.f.mjs +226 lines, rtti/data/proof.f.mjs +40).
• Public surface diff. Consts: exactly one addition, /fjs/media/json/schema::dataToJsonSchema: (data: Data) => Unknown. No removals, no signature widening to any. Types: every addition is _-prefixed — _Keyed, _Lock, _Even, _Odd, _RecordSelf, plus a second _Rec overload and a $schema member on _UnknownConst. §6.2 satisfied; types.ts is untouched in this PR, so no new unprefixed public export type.
• §4 headers survive declaration emit: @module count 1 in both fjs/media/json/schema/module.f.d.mts and fjs/types/rtti/data/module.f.d.mts; 0 occurrences of elided or : any in either.
• Link check — 132 broken links at this head, 132 on main, and the two sets are identical (diff empty), so deleting fjs/media/json/todo/rtti-recursive-json-schema.md and editing fjs/media/todo/revision-lock-map.md stranded nothing.
• §8.3: both entries sit in ## Unreleased, link only /pull/1542, and no released section is touched.

Re-run rather than carried forward

The subset memo change is upstream of toData's coverage collapse, so I did not carry the previous round's structural numbers over. Re-ran a fresh randomized recursive corpus at this head — 300 generated self- and mutually-recursive rule sets, 258 converting (166 emitting $defs): 0 dangling $ref, 0 unreachable $defs, 0 idempotence failures. The 42 non-converting cases all throw the same t is not a function or its return value is not iterable, which is my generator emitting a malformed RTTI shape — toData raises it identically on main, so it is not a PR behaviour.

Two corrections to my own work while I was at it: the first version of that corpus rebuilt a fresh random body on every call of the recursive thunk (so every schema looked non-idempotent, 395/398) and used a #/$defs/(.+) reference pattern that rejected the empty def name my anonymous generator functions produced (so 71 refs looked dangling). Both counts were artifacts of the probe; the numbers above are from the fixed version.

What I did not re-verify at this head, since it is unchanged from the previous round: the 7,904-probe acceptance comparison and the 1,152-probe representation-only check on non-recursive schemas, and self-validation of the emitted documents.

No open findings. Approving.