main
8 Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
|
5d38f0c82f
|
perf(schema): graph-structured-stack content matcher, killing the last 2^K content-model hang (#364)
* perf(schema): graph-structured-stack content matcher, sharing each xs:group (alongside)
The per-instance content-model build inlines every xs:group reference, so a
multiply-referenced nested group (g0=(g1,g1), g1=(g2,g2), ...) explodes to 2^K
states and reset actions: a depth-16 doubling chain already takes seconds, depth
20+ hangs. This compiles the same particle to a counted Recursive Transition
Network instead, where each definitionID group is compiled once and reached by a
call, and simulates it with a graph-structured stack.
ContentRTNBuilder mirrors ContentNFABuilder exactly except that a group with a
definitionID becomes a call into its shared, compiled-once fragment (memoized by
id; the fragment's accept is a return). The callee's counters are deliberately not
propagated to the caller: every counter is reset on its own particle's entry edge,
which is on the path from the callee's start, so a shared fragment resets itself on
every re-entry without the caller re-listing it. Re-listing was the residual
blow-up: it nested the reset-action lists to 2^K even when the states stayed O(K).
ContentRTNMatcher runs configurations (state, counters, gssNode): a call saves the
caller's counters on a GSS node interned by (returnState, savedCounters, position)
and a return restores them, so the shared callee never mixes counter state across
its callers; parents are a set and a popped node replays its pop to a parent added
later (the GLL completeness detail). The build drops to O(groups): a depth-24
doubling chain (2^24 inlined states) compiles to under 480 states in under a
millisecond.
It is gated by a differential (ContentRTNDifferentialTests) against the trusted
inlining matcher ContentNFA as the oracle: the two agree on the accept verdict and
the matched particle over the hand model cases, the named-over-wildcard tie-break,
the shared-group doubling chains that exercise call and return, and a 4000-case
fuzz of nested models with occurrences, wildcards, and shared groups, plus a bound
assertion. Built alongside the inlining matcher and not yet wired into validation,
so no behaviour change and the XSTS buckets are unchanged; the switch-over is gated
on this differential.
* perf(schema): add the streaming/located surface to the GSS matcher, lock it differentially
The content-model validator reads two things off the inlining matcher: matchedParticles
for per-child attribution, and the streaming startStates/step/admissible/isComplete for
located diagnostics (which child breaks the model, and the "expected a, b" hint). The GSS
matcher only had matchesWhole/matchedParticles, so it could not yet replace the inlining
matcher. This adds the streaming surface: admissible works because the closure already
expands call states into the callee's label states, so the follow set has the same shape
as ContentNFA's.
The differential gate now locks the whole surface, not just the accept verdict: driving
both matchers child by child, the first rejected child (step is nil) agrees, the
admissible expectation set agrees at the start and after every accepted child, and
isComplete agrees once the sequence is consumed. The fuzz now stamps group references the
way the parser does, a unique definitionID per distinct group (so a singly-referenced
named group also takes the call path, not only doubled groups), a shared id only for
genuinely shared structure, and some anonymous inline groups, over occurrences and
wildcards. Still alongside, not wired; no behaviour change, XSTS buckets unchanged.
* perf(schema): complete the GSS matcher surface with follow(after:), verified
follow(after:) is the last ContentNFA method the GSS matcher lacked: the completion
path (XSDCompletions) reads it for the acceptable-next labels and whether the content
may end. It composes the streaming surface, and the differential now locks its allowed
set and complete flag to ContentNFA too. The RTN matcher is now a complete drop-in for
the ContentNFA surface the validator and completions read, so the switch-over is a
mechanical builder swap gated on XSTS neutrality. Still alongside; no behaviour change.
* docs(design): record GSS Steps 1-3 done, the switch as a corpus-gated mechanical swap
Updates the counted-content-automaton Step 4 to the current state: the GSS matcher and
its full differential gate are built and green in-repo, and the production switch is now
a three-site builder swap blocked only on the XSTS neutrality measurement, which must run
on a machine that has the corpus. Records the exact swap sites and the gate so the corpus
machine can execute it mechanically.
* perf(schema): validate and complete on the GSS matcher, killing the last 2^K content-model hang
The three call sites that built the inlining content automaton once per validated
element, ComplexValidatorContentModel.sequenceStructureErrors (located structure
errors), ComplexValidator.validateParticle (per-child particle attribution), and
XSDCompletions (acceptable-next labels), now build ContentRTNBuilder and run
ContentRTNMatcher. A schema whose nested <xs:group> references inline to 2^K positions
(the g{i}=(g{i+1},g{i+1}) doubling shape) no longer makes each keystroke-time validation
of an element exponential in the nesting depth: the automaton is built in O(groups).
Validating a short instance against a depth-40 doubling schema (2^40 inlined positions),
the shape an editor sees mid-typing, now completes in milliseconds with a located error
instead of hanging; a new end-to-end test pins it.
Verified conformance-neutral on the full W3C XSTS corpus in release: valid-schemas-rejected
and valid-instances-rejected stay 0, invalid-schemas-accepted and invalid-instances-accepted
unchanged at 8 and 14. The located diagnostics, per-child attribution, and completions are
behaviour-identical by the surface differential (ContentRTNDifferentialTests), which locks
the verdict, matched particle, rejection index, admissible set, isComplete, and follow to
the inlining ContentNFA. ContentNFABuilder/ContentNFA are retained as that oracle.
* docs(design): mark GSS content-matcher Step 4 done, XSTS-neutral in production
Records that the three production sites are switched to the graph-structured-stack
matcher and the switch was measured conformance-neutral on the full W3C XSTS corpus in
release (all four buckets held). Notes the local corpus path and that ContentNFABuilder
is kept as the differential oracle rather than deleted.
* test(schema): compare full matched-particle attribution; bound a cyclic group id
From the adversarial review of the GSS matcher:
- The differential compared only the matched-particle kind (element/wildcard), so it
could not observe the type/value metadata matchedParticles carries. Every fuzz and
hand element now carries a per-name fixed value constraint and the comparison projects
it, so the gate verifies the metadata is carried identically through call/return, not
only that the kind agrees. A name maps to one constraint, so the comparison does not
depend on the lowest-state-index tie-break (which only distinguishes same-name
particles, a UPA violation the compiler rejects before instance validation); the
matchedParticles doc now records that caveat.
- ContentRTNBuilder.groupFragment memoizes after compiling, so a (malformed) cyclic
definitionID would recur without bound, the interactive-safety hazard this matcher
removes. definitionID groups are acyclic by construction (the parser breaks cycles at
element boundaries, the inlining builder relies on the same), but bound it anyway:
a cycle degrades to a terminating empty fragment instead of recurring.
No production behaviour change; the differential, full suite, and the full XSTS corpus
in release (16/16, all four buckets held) stay green.
|
|||
|
116b260149
|
docs(design): add the code-level implementation blueprint for the GSS matcher (#362)
The previous section settled the algorithm and the bound proof; this makes the build turnkey rather than exploratory. It is the full scope of the reverted RTN attempt (whose group sharing was correct) with the explicit return stack replaced by the graph-structured stack: - Step 1: a group-definition identity (`Group.definitionID`, stamped from the existing `GroupParticleMemoKey` in `XSDParserParticles`), FP-neutral on its own. - Step 2: a `ContentRTNBuilder` alongside the trusted inlining `ContentNFABuilder`, compiling each definition once via `call`/`return` epsilon edges, counters still per-configuration and reset on entry so a shared fragment does not alias. - Step 3: the GSS simulation: a node `(returnState, parents-set)` interned per `(returnState, inputPosition)`, configuration `(state, counters, gssNode)`, with call interning and pop fan-out, deduplicated on the configuration key. - Step 4: the differential gate against the inlining oracle (XSTS + a nullable-nested-group fuzz, verdict AND matched-particle equal), then the switch and a perf assertion on GSS/configuration COUNTS (not a wall-clock timeout, the reverted attempt's lesson). Each step is its own PR; steps 1-2 keep the oracle authoritative, step 4 is the only behaviour change and is gated to equivalence before it lands. Design only. |
|||
|
1057fc19d0
|
docs(design): derive the graph-structured-stack bound for the content matcher (#361)
Closes the proof gap that sank the reverted RTN matcher. The counted automaton removed the occurrence-magnitude blow-up and the compositional determinism check removed the determinism group-sharing blow-up, but the per-instance matcher build (ContentNFABuilder.group) still expands a multiply-referenced group once per reference, so a doubling chain g0=(g1,g1)... builds 2^K states and hangs on the first validate. That is the last place stopper 4 is a hang, not a proven bound. The reverted pushdown rewrite compiled the group DAG to call/return edges (O(groups) program) but kept EXPLICIT return stacks, so a nullable doubling chain made the start epsilon-closure reach ~3^depth distinct stacks: the exponential moved from the build to the per-keystroke closure. It was verdict-correct yet bounded nothing, and was reverted. This section derives the fix: a graph-structured stack (the GLL/Earley device). A GSS node (returnState, parents-set) shares stack suffixes, so configurations are keyed on (state, counters, gssNode) and the live set is bounded by O(states), not by the number of distinct stacks. The nullable doubling chain that produced 3^depth explicit stacks produces O(K) GSS nodes. The section states the size and termination bounds (counters clamped to N+1, non-recursive group DAG), the deterministic-model O(N*S*D) match, and the same alongside-then-differential-gated rollout that made the compositional-determinism change FP-safe, with a perf ASSERTION on configuration/GSS counts rather than a wall-clock limit (the reverted attempt's lesson). Design only; no code change. Status: DESIGNED, not implemented. |
|||
|
330e827262
|
docs(design): derive the exact Particle Valid (Restriction) procedure (#252)
* docs(design): derive the exact Particle Valid (Restriction) procedure The false-negative tail (particles*/elemZ) routes through one approximate oracle, ParticleRestriction.violation. Rather than patch cases, derive the exact XSD 1.0 3.9.6 decision procedure once, clean-room from the spec and the Xerces reference algorithm, with the soundness (no-false-positive) argument for each clause: normalization, substitution-group expansion, effective total range, the compositor dispatch table, and the rcases. Identifies the closeable gaps (subst-group expansion for elemZ026/V020, MapAndSum effective-total-range, NameAndTypeOK union-member derivation) and names the genuine spec limitations (Ha161/Z001 contradiction, mgO013 contested, union-member by-name derivation) as bounded, not bugs. Sets the implementation order, each clause gated by the proof plus the XSTS valid-rejected=0 gate and an adversarial over-rejection critic. No behaviour change. * docs(design): record the empirical finding -- particle-restriction tail is contested Probing the actual cases overturned the first hypothesis. elemZ026 and particlesV020 are the same pattern (a derived ref to a substitution-group MEMBER restricting a base ref to the HEAD), and PureXML already accepts them because its content model expands a head ref to admit members (for instance validation), which the restriction oracle inherits -- the Xerces-lenient reading. They are CONTESTED (Xerces/PureXML accept, XSTS rejects under strict NameAndTypeOK), so the keystone (adding expansion) would entrench the acceptance, not close them; closing them risks a false positive. Every remaining particle case is contested or FP-delicate, so the exact-oracle keystone yields no clean conformance win. The remaining lever toward the full bar is the proven resource bound (pushdown matcher), not this oracle. Proof first earned its keep: it prevented shipping against contested targets. |
|||
| 6f8222a840 |
feat(schema): compositional UPA determinism, delete positionCap
The Unique Particle Attribution check no longer inlines group references or caps. A new CompositionalDeterminism engine computes first/followlast over particle identities and summarizes each xs:group once, so a multiply-referenced nested group whose inlined Glushkov automaton would be 2^K positions is checked in O(nodes * particles^2) time. ContentModelDeterminism now delegates to it and the inlining position automaton plus positionCap are deleted, closing the last named interactive-safety resource-bound blocker (production-readiness stopper #4) and the silent under-rejection the cap caused (stopper #3). The compositional engine was proven verdict-equivalent to the prior inlining automaton by a differential over the entire XSTS corpus (zero divergences) before replacing it. The followlast detail was essential: a first attempt that emitted a repeating end-item's loop-back and the suffix-first as separate decision sets under-detected 13 XSTS content models; the differential caught every one. Verification: XSTS gate unchanged (invalid-schemas-accepted 15, valid-schemas- rejected 0, instance buckets held); SchemaDeterminismGroupBlowupTests compiles a 2^20-position model without hanging and rejects an ambiguous one the old cap would have skipped (WASI uses a smaller depth, native time limits gated off WASI); full suite, style, namespacing, and WASM all pass. The per-particle model and QName-only overlap are preserved, so the false-positive direction stays at zero. |
|||
| ba69d716fa |
docs(design): specify the compositional UPA algorithm to delete positionCap
Turns the 'blocked design frontier' for ContentModelDeterminism.positionCap into a ready-to-implement, FP-safe plan derived from the current engine. Documents the root cause (group-ref inlining gives 2^K positions), why naive position dedup/sharing is unsound (cross-context followpos merge = false positive), the sound compositional algorithm (per-group memoized nullable/firstParticles/ lastParticles/followlast over particle identities, cross-boundary conflicts computed per reference-site by the parent, the star condition for repetition, bounded O(nodes x particles^2)), and the differential-gated rollout (build alongside the inlining oracle, prove verdict-equality on XSTS + a group-ref fuzz, only then switch and delete the cap) with acceptance criteria. |
|||
| b73384bc2e | fix(schema): count content-model occurrences | |||
| 47c3a230e4 | docs(schema): design counted content automaton |
