Fifth serialize-path pass (#139, docs/benchmarks.md pass 31). textNeedsEscaping,
attributeNeedsEscaping, and the comment/processingInstruction existence checks
run unconditionally on every text node, attribute value, comment, and PI in a
document, scanning through UTF8View's default Collection iteration. Profiling
a new deeply-nested, attribute-dense corpus (the standard flat catalog corpus
has no density to indict this) put the two needsEscaping functions as the
largest PureXML-specific frames in the sample. A standalone micro-benchmark
confirmed withContiguousStorageIfAvailable's raw buffer scan measures ~2-2.75x
faster than the Collection-based scan, with a Collection fallback kept for a
non-contiguous (foreign/bridged) string.
Two abstraction attempts were tried and rejected before landing this shape: a
shared generic helper taking a predicate closure recovered most but not all of
the win, and calling a separate small function from inside the buffer loop (to
dodge a cyclomatic-complexity violation) erased nearly the entire win even
though it isn't a closure value. The violation is instead resolved by splitting
each function into a contiguous/collection pair, moving the call boundary
outside the loop rather than inside it.
Output is byte-identical by construction; full local suite (1925 tests) and
full lint unchanged. Measured with interleaved same-state A/B under real
concurrent machine load: clean with zero overlap across 5 pairs at the nested
corpus (~9%), noisier at the standard corpus but the means still separate
clearly (~4%).
Two profile-guided serialize passes (#139, docs/benchmarks.md passes 29-30).
The attribute writer now precomputes the quote character as a String once
per element instead of interpolating a Character into every attribute,
avoiding the grapheme-breadcrumb machinery that repeats twice per attribute
for a value that never changes within an element. Escaping.comment and
processingInstruction's escaping fallback (taken whenever a comment has a
hyphen or PI data has a '?', a case pass 8 could skip past but not speed up)
is rewritten in the same byte-scan bulk-copy shape as passes 23-24, so a
value with one rare trigger no longer pays a full character-by-character
rebuild.
Both are same-observable-behavior changes. The quote change is byte-
identical by construction. The comment/PI rewrite is verified against a new
differential suite that reimplements the original character-loop as an
independent oracle and checks adjacency/trailing/combining-mark cases plus
two 20000-case seeded fuzzes, since a byte match inside a combining-mark
cluster is not, on its own, the bare trigger character. Full local suite
(1925 tests) unchanged.
Measured with interleaved same-state A/B: pass 29 ~1.5% at a 100k-item
corpus; pass 30 ~2x on a dedicated comment/PI micro-benchmark (the standard
corpus has no comment/PI content, so real documents with copyright banners
or hyphenated comment prose see this, not the headline ratio). A same-
session multi-append restructuring attempt measured a clear ~6% regression
and was reverted; a suspected hasInlineContent double-scan was profiled at
~0.2% of samples and not worth a pass. Both outcomes are recorded in
docs/benchmarks.md rather than dropped.
The two monolithic XSD content/identity rules only satisfied the OpenAPIKit
validation idiom at the wrong granularity: no per-constraint removability,
no isolable failing/near-miss tests. Split them into 32 named rules, each
finding tagged at its origin and cached per XSDContext so the walk still
runs once per document (the #101 decision against duplicating XSD's
recursive type resolution still holds). Wired the streaming path's ID/IDREF
and identity checks through the same framework instead of calling the
validators imperatively, and added the unwrapAndLookup combinator the rule
already named as required.
Also includes the mandated repo-wide swiftformat/swiftlint pass.
The byte-path close-quote consume candidate measured NEUTRAL in an
interleaved A/B despite the sampler attributing ~4% of parse to the
advance() chain it replaced: decoding one ASCII scalar into a
small-string-backed Character costs about the same as consume's
literal-matching path. Recorded under Known structure of the gap so no
future round redoes it, with the meta-lesson that sample attribution
overstates single-character round trips and only the interleaved A/B
verdict counts.
Also records the #8 decision: the TreeNode weak-parent side-table cost
(~9% of parse) is accepted for now. unowned is rejected outright since a
trap after release contradicts the never-crash posture and the documented
nil-after-release behavior; the arena/index-based tree remains the
designed future path, sequenced after the scanning-architecture work,
which carries ~47% of parse to this finding's ~9%.
Fourth profile-guided pass (#139, docs/benchmarks.md pass 28). scanAttributes
allocated a fresh Set<String>'s native storage on every element with
attributes, just to check a handful of names for duplicates; the set is now a
stored EventReader scratch property cleared with removeAll(keepingCapacity:)
per element, so each element's check reuses the previous element's storage.
Safe because scanAttributes cannot re-enter itself (nothing inside an
attribute scan starts another start-tag scan), so the shared storage never
sees two interleaved scans; duplicate detection, recovering-mode behavior,
and thrown errors are unchanged.
Verified in an isolated worktree at the previous commit: full local suite
(1858 tests) and full W3C XSTS suite (14383 groups) pass unchanged. Measured
with an interleaved same-state A/B, baseline/patched/baseline/patched each
best-of-5, because the machine carried concurrent load this session: both
patched runs (0.1073s, 0.1067s) beat both baseline runs (0.1091s, 0.1117s),
~2-4% on parse.
Recorded alongside, per the benchmarks log's discipline: a sibling candidate
(reserving each tree frame's children capacity on first append) measured
neutral under the same protocol and was reverted rather than landed, and the
TreeNode weak-parent side-table cost (~9% of parse, swift_weakAssign per
child plus a runtime side table per parent) is documented under Known
structure of the gap as needing a design decision, since parent's
nil-after-release semantics are documented public API. Touched lines carry
repo-standard swiftformat rewraps applied by a concurrent formatter run.
Third profile-guided pass (#139, docs/benchmarks.md pass 27), targeting
scanContentMarkup(), which inlines the start-tag/attribute/namespace scanners
and carries ~46% of parse time.
scanAttributeValue's opening and closing quote checks ran on the Character
path (peek + advance, buffering the quote as a Character only to compare and
discard it) on every attribute value in the document; both now check the raw
byte first, reaching the byte fast path with no Character buffering, with the
Character path kept as the off-fast-path fallback for streaming sources. The
quote bytes are ASCII and non-CR/LF, so the raw byte and the normalized
stream agree, the same reasoning peekByte's other callers already rely on.
NamespaceContext.checkExpandedNames allocated a Set's native storage and
built a concatenated URI+local key string per element even when at most one
attribute carries a namespace URI, where no duplicate is possible (the
default namespace never applies to attributes, and xmlns declarations carry
no URI). Counting URI-bearing attributes first, with no allocation, and
returning early below two skips all of it on the overwhelming majority of
elements; for xml:* attributes specifically the key exceeded the small-string
limit, so this also removes a real per-element heap allocation.
EntityDecoder.decode/decodeLenient guarded with raw.contains("&"), a
grapheme-by-grapheme walk to find one ASCII byte, once per ampersand-bearing
text node or attribute value; raw.utf8.contains(0x26) finds the same byte
without decoding graphemes, the same shape as checkNameShape's colon check.
The quote-handling extraction into two helpers also resolves the cyclomatic
complexity the inline version tripped. Six new regression tests pin the
quote edge cases (empty value, single-quoted, a quote kind nested inside the
other, unterminated at end of input) plus byte/Character-path agreement for
each in the parser path differential.
Verified: full local suite (1858 tests) and full W3C XSTS suite (14383
groups) pass unchanged. Parse ~6.00x -> ~4.75x versus libxml2 at the
20000-item corpus, best of 5.
Two profile-guided passes (#139), found by sample-profiling a 42MB generated
corpus after re-measuring the parse/libxml2 ratio fresh:
scanAttributeValue's closing-quote check re-derived an already-known answer
through Reader.consume's general String-iteration path, which allocates a
fresh String(quote) and iterates it via Character machinery twice, on every
single attribute value in the document. The content loop's own break
condition already guarantees the buffered peek is either the quote or end of
input, so checking it directly and advancing once is the same behavior for
less work.
NamespaceContext.enterElement, called once per element: checkNameShape's
name.localName.contains(":") resolved to Sequence.contains(_:), walking
extended grapheme clusters to find one ASCII byte; utf8.contains(0x3A) finds
the same colon via the UTF-8 byte view. Separately, attributes.map{
resolveAttribute } allocated a fresh backing array on every element even
though resolveAttribute returns its argument unchanged whenever the attribute
has no prefix or the xmlns prefix (the common case); checking first with no
allocation and reusing the input array when nothing would change gives the
identical result without it.
Both are same-observable-behavior changes, verified against the full local
suite (1852 tests) and the full W3C XSTS conformance suite (14383 groups),
both unchanged. Measured parse ~6.59x -> ~6.00x versus libxml2 at the
20000-item/4.2MB corpus, best of 5; see docs/benchmarks.md passes 25-26.
An element restricting a base choice was always checked by the
effective-total-range approximation, which exists for one reason: the
literal section 3.9.6 pairing has no allowance for occurrence counts
accumulated across the choice's own repetitions and over-rejects
W3C-read-valid schemas (particlesZ001, whose manifest calls the rule
ambiguous). That ambiguity is impossible when the choice cannot repeat:
at {max occurs} = 1 every accepted child comes from one traversal of one
branch, so the literal rule governs. elementRestrictsChoice now applies
the literal pairing (the derived element, with its own occurrence range,
must validly restrict some non-pointless branch) when base maxOccurs is
1, and keeps the effective-range reading only for repeating choices.
Closes XSTS particlesHa161 (a derived a{0,1} is not a pointwise
NameAndTypeOK restriction of a required branch a{1,1}) and particlesM034
(a derived d1+ cannot map into the branch (d1*, d2+): the required d2 is
unmapped and not emptiable). The settled-valid neighbors that pin the
boundary from the other side all still pass: Ha160, M002, M003, M035,
and the Z001 shape, each now a regression test in
XSDParticleChoiceRestrictionTests. invalid-schemas-accepted 6 -> 4.
particlesIg004 is reclassified as spec-divergent (4 -> 3): section 3.3.2
maps block="#all" and the explicit substitution/extension/restriction
list to the SAME {disallowed substitutions} set, so NameAndTypeOK clause
5's superset requirement holds and the invalid expectation has no spec
path; it is jointly unsatisfiable with the settled Ig001/002/003 (equal
sets, valid) and Ig005 (#all covers the triple, valid).
The remaining three schema deviations are documented divergences, not
open bugs: Ik025/Ik027 (cos-st-derived-ok 2.2.4 reading) and schN12,
newly adjudicated in docs/xsts-deviations.md: its chameleon redefine
fails src-redefine 6.2.2 on NameAndTypeOK clause 1 (no-namespace locals
vs qualified locals), but 6.2.2 cannot be enforced uniformly because
mgO013's settled-VALID schema also violates it; any uniform enforcement
trades a false negative for a valid-schema-rejected false positive.
Also corrects the stale deviations-doc row that listed the already-closed
particlesIk011 and omitted schN12; the failures file is the authority.
Gates: full XSTS release suite green at 0/3/0/4 (valid buckets unchanged
at zero), libxml2 differential green at 244 pinned entries (Ha161 and
M034 newly pinned, both compile under libxml2), full local gate green.
NameAndTypeOK clause 1 (XSD 1.0 section 3.9.6, Elt:Elt) pairs the declared
element declarations and requires the same {name} and {target namespace};
no clause grants substitution an allowance. The substitution-group
expansion rewrites the compiled term (an abstract head is dropped, members
join a synthetic choice), so the checker previously compared the expanded
names and a head-for-member swap looked name-identical.
Particle.declaredReference now preserves the pre-expansion identity of an
element-ref particle, and the restriction check pairs the declared
references before the structural pairing table (extracted as
structuralValid). Closes XSTS elemZ026 and particlesV020:
invalid-schemas-accepted 8 -> 6, valid buckets unchanged at zero.
Stricter than libxml2, which does not implement this edge; elemZ026 is
pinned in the differential baseline accordingly.
particlesZ008, byte-for-byte the same construct as elemZ026 but carrying
a settled valid expectation contradicting elemZ026's settled invalid, is
reclassified as a spec-divergent schema test with the adjudication
recorded in the suite (exclusion tables split into
Tests/XSTSSuiteExclusions.swift for file length).
Separately attributed: the differential baseline gains ten further pinned
entries (addB070a, addB108, addB177, attO025, elemZ027_c, errC008,
groupH021v, notatB005, notatE002, particlesEb040) that reproduce with
this change stashed. They are pre-existing drift from earlier main-line
fixes, not effects of this commit. Baseline 231 -> 242, differential
green.
The roadmap and README cited issue numbers from the deleted GitHub
tracker and carried stale XSTS figures (0/39/0/26 and 0/43/0/31 against
the enforced 0/8/0/4). Recreate the load-bearing issues on Codeberg
(#3 production-readiness epic, #4 and #5 gate trackers, #6 performance,
#7 Xalan burn-down), cite them, correct every baseline figure to the
test ratchet, mark shipped work (located diagnostics, the differential
harness) as done, and note that pre-migration numbers in the historical
narrative refer to the lost tracker.
Closes#2
Every unique commit on the branch (the changelog stamp, the Codeberg
repoint, and the rules-baseline stamps) was re-applied on main before
tagging v0.4.8, so the merge records the supersession without content
changes.
The earlier release/0.4.8 branch stamped the changelog but the tag was
never cut, and main moved 60 commits past it. Fold the accumulated
unreleased entries into the still-unpublished 0.4.8 section, redate it,
repoint every remaining github.com/mihaelamj reference (badges, support
links, roadmap, the XSLT vendor-url system property), and track the
shared-rules baseline v1.1.2.
Adopt the rules-swift pin-and-codify strategy in snapshot mode (third_party/rules-swift
@97dc70f + sha256), add codified gates, a conformance audit ledger, and
.github/workflows/rules-swift.yml (corpus-pin integrity required, full gate report mode).
Remove the docs/rules mirror it supersedes (repo-specific files kept under docs/). Style
and leak gates exclude the vendored corpus.
The rules-swift concurrency rule's acceptance check requires every `@unchecked
Sendable` and `nonisolated(unsafe)` to carry an adjacent comment explaining why
the race is acceptable; an unjustified one is a violation. An audit found six
escape hatches whose comment explained the type but not the race:
- The four XPath `FunctionTable` statics (`CoreFunctions`, `StringFunctions`,
`NodeFunctions`, `Evaluator.library`): each is an immutable, build-once lookup
table never mutated after initialization, so concurrent reads race on nothing;
`FunctionTable` is un-`Sendable` only because it stores closures.
- `Validation.Validator`: immutable after `init` (every stored validation list is
a `let`); the erased `AnyValidation` closures are simply not provably `Sendable`.
- The test `ResultBox`: written once by the worker thread before its semaphore
signals and read only after the wait, so the write happens-before the read.
Comments only; no behaviour change. `LoaderBox` and `ElementStorage` were already
justified. swiftformat/swiftlint --strict and the full suite stay green.
The instance-validation differential treated "PureXML rejects, libxml2 accepts"
as a PureXML false positive. That is unsound: libxml2's own content validation is
lenient and accepts some INVALID instances. A DIFF_SEED sweep surfaced exactly
such a case (seed 13371337): the model ( (a*|c*){1,3}, b? ){1,3} and the instance
<doc><b/><b/><a/><b/><c/><a/></doc>. libxml2 accepts it, but it is genuinely
INVALID (the three b's anchor three (choice,b?) segments, leaving the trailing
'ca' with no fourth segment), so PureXML's rejection is correct, not a false
positive. Verified against an external regex engine and exhaustive enumeration.
Add ContentModelOracle, an independent brute-force membership matcher over element
names, implemented separately from PureXML's matcher. The generated instances are
empty xs:string elements, so an instance is valid iff its element-name sequence is
in the model's language, which this oracle decides exactly. The generator now
emits the structured ContentModel alongside the schema string (group references
inlined), and the differential classifies a false positive / false negative
against the ORACLE as ground truth; libxml2 is kept as a secondary cross-check
whose disagreements with the oracle are counted (its leniency) but never charged
to PureXML.
The oracle is unit-tested (ContentModelOracleTests), including the libxml2-leniency
case it exists to catch. Over a sweep of seeds the differential now reports zero
oracle-adjudicated false positives and zero false negatives, so PureXML's content
matcher agrees with the independent oracle on every generated case; the default
seed is unchanged. Test-only; no library behaviour change.
The three generated-vs-libxml2 differentials (instance, facet, determinism) each
ran a single hardcoded seed, so they characterised one fixed slice of the open
input space rather than sampling it. Each now reads an optional DIFF_SEED
environment override (defaulting to its existing seed, so the default run is
unchanged), turning the fixed smoke test into an open-space fuzzer: a sweep over
many seeds explores far more of the unbounded schema/instance space than the
finite XSTS corpus, which is the production-readiness "uncharacterized
correctness" stopper.
A 12-seed sweep of the instance differential immediately surfaced a genuine
content-matcher false positive (cardinal-rule violation) at DIFF_SEED=13371337:
the model `( (choice(a*|(c*)+)){1,3}, b? ){1,3}` rejects `<doc><b/><b/><a/><b/>
<c/><a/></doc>` ("element 'c' is not allowed here") though libxml2 accepts it. A
nested nullable-repetition edge in the graph-structured-stack matcher, captured
for a focused fix; the default seed and every other swept seed hold false
positives at 0.
particlesZ001 declares Derived as a complexContent restriction of Base and an
instance whose <elem> (type Derived) content is annotation + four elements. The
suite pairs a valid schemaTest with an invalid instanceTest, but the two are
mutually exclusive for a consistent conformant processor, and the manifest's own
documentation labels the governing rule, Particle Derivation OK (RecurseAsIfGroup),
ambiguous.
cvc-complex-type (§3.4.4) validates an instance against the element's own
{content type}: for <elem> that is Derived = sequence(annotation?, element*),
which the instance satisfies, so the instance is valid. Particle Valid
(Restriction) / RecurseAsIfGroup (§3.9.6) is a schema-assembly constraint that is
never re-run during instance validation, so there is no path from an accepted
schema to an invalid instance. The only way to reach the suite's invalid is to
reject the schema as an invalid restriction, which is a valid-schema-rejected
false positive and would still fail the suite's own valid schemaTest. libxml2
accepts both schema and instance, agreeing with PureXML.
Exclude particlesZ001.i via specDivergentInstances with the spec-grounded
justification in code and docs/xsts-deviations.md. invalid-instances-accepted
5 -> 4; full XSTS in release now 0/8/0/4, both false-positive buckets at 0. No
library behaviour change. Confirmed by an adversarial analysis that found no
spec-coherent reading yielding valid-schema + invalid-instance.
An xsi:type value is a QName: a prefix binds through that prefix, an unprefixed
name through the in-scope default namespace, and with no default namespace an
unprefixed name is in no namespace. PureXML stores each named type under both its
namespaced key and a bare local-name alias (for lenient lookup), so an unprefixed
xsi:type="Test" matched a {targetNS}Test through the alias even when the instance
had no default namespace, wrongly typing an otherwise-undeclared root and
accepting the document (W3C XSTS targetNS00101m; libxml2 rejects it identically).
xsiTypeReference now keys an unprefixed xsi:type to the in-scope default namespace
(none here) rather than returning the bare local name, so xsi:type="Test" names
no-namespace Test, which does not exist; the root then has neither a declaration
nor a usable type and the instance is invalid. A prefixed xsi:type and an
unprefixed one under a default namespace equal to the target namespace are
unaffected, and the child-element builtin-substitution path keeps its bare-name
fallback (xsiTypeName), so an unprefixed builtin still substitutes where valid.
Verified over the full W3C XSTS corpus in release: invalid-instances-accepted
6 -> 5, valid-instances-rejected held at 0 across all 14383 groups, full suite
(1840 tests) and wasm green. An adversarial critic traced every resolveNamedType
branch, including the unprefixed-builtin-via-key case, and confirmed the only
path that no longer resolves corresponds to a spec-invalid reference, so no valid
instance is newly rejected.
mgO013 redefines a model group `group` to `all{e1(1,1)}`, redefining a base
`all{e1(0,0)}` (e1 forbidden) without referencing itself. The suite pairs a
`valid` schemaTest with an `invalid` instanceTest, but the two are mutually
exclusive for a consistent conformant processor.
src-redefine clause 6.2.2 makes a no-self-reference group redefine a restriction
obligation: the redefined group must be a valid restriction of the original.
`all{e1(1,1)}` is not a valid restriction of `all{e1(0,0)}` (Particle Valid
(Restriction), Occurrence Range OK: derived max 1 > base max 0), so enforcing
6.2.2 rejects the schema, a valid-schema-rejected false positive against the
schemaTest's own `valid` verdict. Yet §4.2.2 makes the referencing type's group
reference resolve to the redefined `all{e1(1,1)}`, against which the single-e1
instance is valid. There is no third path: reaching instance-invalid requires
rejecting the schema. libxml2 accepts both, agreeing with PureXML and the
schemaTest. An adversarial analysis confirmed no reading yields valid-schema +
invalid-instance.
Exclude mgO013.i via specDivergentInstances with the spec-grounded justification
in code and docs/xsts-deviations.md. invalid-instances-accepted 7 -> 6; full XSTS
in release now 0/8/0/6, both false-positive buckets at 0. No library behaviour
change: matching the suite would introduce the false positive the production bar
forbids.
XSD 1.0 §3.11.4 (cvc-identity-constraint.3) requires each key/keyref/unique
field to identify a node of simple type. A field that reaches an element
declared with no type (the ur-type anyType) or an inline complex type without
simple content does not, so the instance is invalid; the reference (libxml2)
rejects it identically. PureXML accepted such instances because its identity
validator could resolve a field target's type only for a global element reached
by a direct-child name, not for a local element reached through a path (the W3C
XSTS case idZ010 nests anyType fields several levels deep, e.g. a key field
./b/c where c has no type).
A compile-time pass (XSDParser.identityNonSimpleFieldKeys) resolves each field's
target element through its selector and field paths, by element-name steps, and
records the fields whose declared target is provably non-simple. The validator
rejects those at runtime unless the instance gives the node a simple type
through xsi:type, since cvc reads the node's governing type (a text-only anyType
element with xsi:type="xsd:int" is a valid field). The resolution is
conservative: any wildcard, descendant axis, predicate, ref, or named
non-builtin type leaves the field unflagged, so a valid field is never rejected.
The one residual divergence path, two same-name child elements of differing
simplicity in one inline model, is an Element-Declarations-Consistent violation
the compiler already rejects.
Verified over the full W3C XSTS corpus in release: invalid-instances-accepted
8 -> 7 (idZ010 now rejects), valid-instances-rejected held at 0 across all 14383
groups (no false positive), full suite (1837 tests), wasm, and lint all green.
An adversarial critic that read every file and probed for a false positive could
not construct one; the failure mode is under-rejection, the safe direction.
The sch* schema-location cluster, dissected per case rather than swept. An
adversarial analysis separated the contested tests from the genuine deviations.
schA2.i and schA5.i are contested and now excluded (invalid-instances-accepted
10 -> 8). Each group's own documentation states the inline xsi:schemaLocation
hint "is ignored" and the instance "must conform to" the collection schema, but
under exactly that prescribed behavior the instances are valid: libxml2 validates
schA2.xml against its a.xsd and schA5.xml against its a.xsd+b.xsd collection. So
the suite's invalid expectation contradicts its own documentation. Reaching
invalid requires letting the instance's hint override a schema already loaded for
that namespace, which XSD 1.0 §4.3.2 makes optional (strategy 1: do nothing when a
schema for the namespace is already known) and which would be a direct false
positive for an IDE: an instance file forcing rejection against the project's own
schema. PureXML's policy (honor hints but keep the collection's declarations on
conflict) is conformant.
schA7.i is NOT excluded. The adversarial pass showed its invalid IS spec-grounded:
with hints ignored, the instance's b:e1 (namespace ns-b) has no declaration in the
a.xsd-only collection and is demanded by root's default-strict ##any wildcard, so
§3.10.4 makes it invalid. PureXML accepts it only by honoring the ns-b hint to
gap-fill, the other conformant §4.3.2 strategy. A genuine policy-dependent
deviation, left in the count and documented.
schU3.i/schU4.i/schU5.i are also left in the count, documented as a deferred
under-rejection in an underspecified area: circular redefine chains where an
attribute group is redefined to conflicting types across an include/redefine
cycle. The suite expects the int reading (so c1="a" is invalid); PureXML resolves
the laxer type and accepts. libxml2 does not support the construct at all (rejects
the schema: multiple redefinition not supported), so matching the suite means
out-resolving the reference on a construct whose cyclic composition order the spec
does not pin down.
Full XSTS in release now 0/8/0/8, both false-positive buckets at 0. No library
behavior change; reasoning recorded in code and docs/xsts-deviations.md.
The W3C XSTS group anyURI_a004_1339 pairs a `valid` schemaTest with an `invalid`
instanceTest, but the two expectations are mutually inconsistent, so PureXML's
acceptance of the instance is spec-correct rather than an under-rejection.
The schema's include, import, and redefine carry unresolvable schemaLocations
(ftp://, gopher://, mailto:). XSD 1.0 §4.2.1 makes an unresolvable include "not
an error" (no inclusion performed), the import likewise, and the empty redefine
imposes no resolution requirement (src-redefine clause 1 gates that on
non-annotation children), so the schema is conformantly valid, agreeing with the
schemaTest. The only components the instance exercises (root, bar, st, att) are
fully locally defined, and every instance value is byte-identical to one of the
type's six anyURI enumeration members, so a strict assessment of the document
element is valid. There is no spec path to valid-schema + invalid-instance.
libxml2 is no authority here: it non-conformantly fails to compile the schema on
the unresolvable include, so it disagrees with the suite's valid-schema verdict
too. Matching the suite's invalid-instance expectation would mean rejecting a
valid instance whenever an include cannot be resolved, a false positive an IDE
editing loop hits constantly, which the production bar forbids.
Exclude it from the counts via specDivergentInstances, mirroring how the suite's
own status="queried" entries are skipped, with the spec-grounded justification
recorded in code and docs/xsts-deviations.md. invalid-instances-accepted 11 -> 10;
full XSTS in release now 0/8/0/10, both false-positive buckets at 0. Two
independent adversarial analyses failed to refute the instance's validity.
XSD 1.0 (Datatypes Appendix F) defines the regex escape \i as the characters
that may begin an XML Name (Letter | '_' | ':') and \c as the characters that
may appear in one (NameChar), citing the XML 1.0 Second Edition productions:
the enumerated, Unicode-2.0-era character classes of XML 1.0 Appendix B
(BaseChar, Ideographic, CombiningChar, Digit, Extender). \i and \c were wired
to PureXML.Parsing.XMLCharacter, which correctly implements the Fifth Edition
Name production used to parse live XML, but the two genuinely differ: the Fifth
Edition admits whole blocks where the Second Edition has gaps, so \c
over-accepted, e.g. the combining mark U+0346 (COMBINING BRIDGE ABOVE), which
Appendix B's CombiningChar excludes (its first range ends at U+0345).
Add XSDNameCharacter, transcribed clean-room from the Appendix B grammar
(identical across editions one through four) and stored as sorted, non-
overlapping code-point ranges with binary-search membership; the parser's own
name check is untouched. The two tables reproduce the W3C XSTS \i/\c
enumerations (reZ005, reZ006: 34516 and 35122 code points) exactly and in both
directions, so the more restrictive definition rejects no spec-valid input:
there is no false-positive surface.
Verified over the full W3C XSTS corpus in release: invalid-instances-accepted
12 -> 11 (reZ006i, whose value is U+0346, now rejects), both false-positive
buckets at 0. Full suite (1834 tests) green; an adversarial critic brute-forced
the binary search over the whole code-point space (0 mismatches), confirmed the
tables are sorted and non-overlapping and equal the oracle sets, and that the
parser's Fifth Edition path is left intact. Found by triaging the invalid-
instance tail to a single boundary code point (U+0345 valid vs U+0346 invalid)
and reading the XML 1.0 Appendix B grammar.
XSD 1.0 fixes the regular-expression repertoire at Unicode 3.2 (Datatypes
Appendix F), where U+1369..U+1371 (ETHIOPIC DIGIT ONE..NINE) are general
category Nd, each carrying a decimal value; a later Unicode reclassified them
to No. XSDCategory derives \d (== \p{Nd}) from the running platform's category,
pinned to 3.2 by an assigned-in-3.2 gate plus a per-code-point override table,
but the table omitted these nine, so \d used the modern No: a valid \d-constrained
Ethiopic digit was wrongly rejected (cardinal-rule false positive) and a
\D-constrained one wrongly accepted.
Pin the nine to Nd. This is the complete set of code points that were Nd at 3.2
and are not today; the reverse direction is empty (every later-Nd point was
unassigned at 3.2 and already reports Cn), verified by diffing the 3.2 and current
Unicode Nd sets. \w is unaffected: an Ethiopic numeral is category N either way,
neither punctuation, separator, nor other.
Verified over the full W3C XSTS corpus in release: invalid-instances-accepted
14 -> 12 (reT17, reT38, the \D cases, now reject), and the matching \d-valid cases
reS17/reS38/reZ004 no longer need a suspect-test exclusion and pass as ordinary
agreements, with both false-positive buckets at 0. Full suite (1830 tests) green;
an adversarial over-rejection critic re-derived the Nd delta bidirectionally and
confirmed no false-positive surface. A regression-pinning test exercises the
production regex path, including the boundary that U+1372 (No even at 3.2) is
not \d.
OrderedValue.== compared doubles with IEEE equality (NaN != NaN), so a NaN value never matched a NaN enumeration member and was rejected: <v>NaN</v> against xs:double restricted by <xs:enumeration value="NaN"/> is valid, and PureXML rejected it (a cardinal-rule false positive). NaN is now treated as identical to itself in value-space equality, the identity the reference (libxml2) and XSD 1.1 use throughout; an adversarial critic flagged the shared comparison (also used by key/unique and fixed), so the key/fixed behaviour was verified against xmllint: libxml2 collides two NaN unique keys and matches fixed="NaN", i.e. the same identity, so one identity == matches the reference everywhere. Ordering (<) keeps NaN incomparable, so range facets are unaffected. Found by a new generated-value facet differential (FacetValidationDifferentialTests, opt-in via FACET_DIFF) over ~10000 datatype/facet values: one FP found, zero after; the four W3C XSTS buckets held, full suite passes, SchemaDoubleEnumerationTests locks all three relations.
A long <xs:attributeGroup ref> chain (ag0 refs ag1 refs ag2 ...) is flat in the document, so flattening a complex type's attributes through it recursed once per link: the stack overflowed past ~6000 links and it was near-cubic before that (~17s at 3000). attributeUses already threads a visited cycle-guard set whose count is the chain depth, so bound it against maximumContentModelExpansionDepth (512): a chain past the bound is rejected with a located error rather than crashed. Behaviour-preserving within the bound, which no realistic schema or the XSTS corpus approaches; verified conformance-neutral over the full W3C XSTS corpus and the full suite. Residual: many distinct over-bound chains still reject in O(n^2) per group (attribute flattening re-done per group); a memo is the linear follow-up.
A long <xs:complexType> simpleContent extension chain (T0 extends T1 extends T2 ...) is flat in the document, so each of the N complex types re-walked its whole base chain to resolve the simple type its simpleContent derives from (an O(n^3) compile; a 400-link chain took ~23s). The resolved simple type is now memoized by complex-type name (SimpleContentMemo, a reference type surviving the value-type context copies, mirroring GroupParticleMemo); the same chain compiles in ~1.2s, and past the 512 expansion-depth bound it is rejected with a located error as before. Behaviour-preserving (an acyclic resolution is intrinsic to the name; a derivation cycle is rejected elsewhere), verified conformance-neutral over the full W3C XSTS corpus, the determinism differential, and the full suite. The attribute flattening along the chain is inherently quadratic in the bounded length and is tracked.
A long <xs:simpleType> restriction chain is flat in the document, so the same base was resolved repeatedly: the named simple types were resolved by an N-pass fixpoint, and the facet-applicability variety check re-scanned the schema's children to find each base at every link of every type's chain (compiling a 600-link chain took ~4.4s). Named simple types are now resolved once in dependency order (XSDSimpleTypeOrder), and the variety check uses an O(1) name map and memoizes each type's variety (SchemaSimpleTypeVariety); the same chain now compiles in ~30ms. Behaviour-preserving, verified conformance-neutral over the full W3C XSTS corpus, the determinism differential, and the full suite.
Two constructs are flat in the schema document, so they escape the parser's element-nesting maxDepth (256) yet make a content model arbitrarily deep once compiled: a <xs:group ref> chain and a complexContent derivation chain (the definitions are siblings). The particle compiler inlines each group reference and composes each derivation once per link, overflowing the stack on a long chain. The expanded depth is now bounded by one counter (XSDContext.expansionDepth, incremented at each compositor level, group-reference expansion, and derivation step) against maximumContentModelExpansionDepth (512); a model past the bound is rejected with a located error, not crashed. The counter lives in a value-type context so it tracks depth not width (no width false positive), and the rejection is harvested into the schema's errors (no silent truncation). Verified conformance-neutral over the full W3C XSTS corpus (all four buckets unchanged), the libxml2 determinism differential unchanged, and the full suite; an adversarial critic found the derivation-chain gap, which this fixes with the same counter.
A flat chain of <xs:group> references is not bounded by the parser's maxDepth (the definitions are siblings, not nested), so the compositional UPA determinism check's lazy per-reference recursion overflowed the native 8 MB stack while compiling a legal schema. Group summaries form an acyclic graph, so they are now precomputed bottom-up in dependency order (GroupDependencyOrder): the walk's group lookup is a cache hit and recursion is bounded by a single group's own model nesting. The precomputed reachable set is identical to the lazy walk's, so the verdict is unchanged. Verified verdict-equivalent over the full W3C XSTS corpus, the libxml2 determinism differential (0 FP, same 3 FN), the full suite, and an adversarial critic. Residual, tracked: the particle compiler that inlines a group reference still overflows on a far longer chain; closing it needs a content-model nesting-depth limit with a located error.
The schema-compile determinism check has a generated-schema differential; this adds the
counterpart for the instance-validation path, exercising the per-instance content matcher
(the graph-structured-stack ContentRTNMatcher now in production) over the open input space.
For every generated, both-engines-compile schema it validates many generated <doc>
instances with PureXML and with libxml2 and compares the verdicts, characterising the
cardinal rule's instance half beyond the finite XSTS corpus.
It asserts the cardinal rule (PureXML never rejects an instance libxml2 accepts) and
reports false negatives for triage. Over 6568 generated validations (1357 both-valid, 5211
both-invalid) across sequences, choices, all groups, group references, occurrences, and
wildcards it found zero false positives and zero false negatives: independent confirmation
that the matcher agrees with libxml2. Opt-in via INSTANCE_DIFF and xmllint, a no-op in
plain swift test and CI; the libxml2 subprocess is guarded for WASI. No behaviour change.
The interactive-safety bar wants a proven worst-case bound, not a cap or a timeout. The
graph-structured-stack matcher shares stack suffixes, so on a model with S program states
and an input of length N the live-configuration set and the GSS node count stay O(S*N)
where an explicit return stack reaches O(distinct stacks): a nullable doubling chain that
gives an explicit stack ~3^depth configurations gives the GSS O(depth).
ContentRTNMatcher now exposes peakLiveConfigurations and gssNodeCount, and the differential
asserts they stay linear in the chain depth (measured gss = K + 2, peak configs = 3K + 3),
by count rather than a machine-dependent wall-clock timeout, so a regression to super-linear
fails the test. Native-only (the depth-80 RTN build recurses on nesting depth and overflows
WASI's small stack; that builder depth-safety is tracked separately). No behaviour change.
A repeating model whose optional trailing particle and leading particle share a name,
(c, b?, c?)*, is ambiguous, as libxml2/Xerces reject it: after b the next c could be the
trailing c? or the looped leading c, two distinct particles. The compositional determinism
check formed the internal sequence gap before the enclosing repetition's loop edge was
added, so the combined {trailing, leading} followpos was never checked, an invalid-schemas-
accepted false negative the finite XSTS corpus did not contain.
The sequence now carries each trailing end-item's internal suffix in its lastFollow, so a
parent gap or the loop edge (withRepeatEdge) forms the end-item's full followpos. The
carried suffix is always a subset of the true followpos, so the check only catches more
genuine conflicts and never over-rejects: the non-repeated (c, b?, c?) and disjoint shapes
like (a, b?)* stay valid.
Found by the new generated-schema determinism differential against libxml2. Verified over
the full W3C XSTS corpus in release (valid-schemas-rejected/valid-instances-rejected stay
0, invalid-*-accepted unchanged at 8/14), full suite on macOS/Linux/WASI, and an
adversarial over-rejection critic finding no valid schema newly rejected over 47 shapes.
The related ambiguity through two references to one group in a repeating sequence stays an
under-rejection (the cached group identity cannot distinguish a looped from a trailing
occurrence without per-occurrence tracking), named in DeterminismDifferentialTests.
The XSTS corpus is finite and did not exercise the multiply-referenced-group overlap that
was a real UPA gap (it was found by reasoning, not the corpus). This adds the systematic
characterisation the production-readiness bar calls for: a generated-schema differential
that fuzzes content models (elements, group references, choices, sequences, all groups,
occurrences, wildcards) and compares PureXML's Unique Particle Attribution accept/reject
verdict to libxml2's. Opt-in via DETERMINISM_DIFF and xmllint, isolated to the determinism
dimension (non-determinism rejections are skipped).
It asserts the cardinal rule, zero schemas PureXML rejects as ambiguous that libxml2
accepts, and reports false negatives for triage rather than leaving them silent. Over this
generator it found zero false positives and one genuine, named under-rejection: a repeating
model whose optional trailing particle and leading particle share a name, (c, b?, c?)*,
where the compositional check forms the internal sequence gap before the enclosing
repetition's loop edge is added, so the combined decision set is never checked. The other
disagreements are contested (unused-group checking; (a?)+ epsilon loop) with PureXML the
more-correct lenient party. The genuine gap is tracked as a follow-up, its own FP-critical
fix.
Two references to the same <xs:group> are two expanded occurrences for Unique Particle
Attribution, so when they overlap, (g?, g?), (g | g), (g*, g), the model is ambiguous,
exactly as inline (x?, x?) / (x | x) is, and as libxml2/Xerces reject them. The
compositional determinism check summarises each group once and reused the group's node
identity across references, so the distinct-identity overlap test could not see the
conflict: PureXML accepted these (an invalid-schemas-accepted false negative). It also let
the per-instance content matcher run on a non-UPA model, where a multiply-referenced
nullable group is exponential, so a depth-18 optional doubling chain was accepted and then
hung instance validation: a keystroke-time hang on a schema PureXML itself accepted.
The fix dedupes each decision set (first set, sequence gap, all cross-follow) by particle
identity and treats a same-identity collision as the conflict; the repetition self-loop
(a*, (a*)*) keeps a non-flagging dedupe so one particle looping is not misread as two
occurrences. This also bounds the check, the deduped first/follow sets stay O(labels) not
2^K, so the depth-40 chain is now rejected at compile in 11 ms and no instance is matched
against it. A redefine self-extension lists a type's own content twice through
effectiveModelNodes; that artifact is deduped before the walk so it is not a false
conflict (addB094, schZ007).
The repeat-edge fold is kept in a separate method, not inline in summarize: summarize
recurses on nesting depth, so a local it holds multiplies the per-level stack frame and a
deep group chain overflows WASI's small stack (the recursive check's deeper WASI depth-
safety is tracked separately).
Verified over the full W3C XSTS corpus in release: valid-schemas-rejected and
valid-instances-rejected stay 0, invalid-*-accepted unchanged at 8 and 14; an adversarial
over-rejection critic found no valid schema newly rejected; the full suite passes on
macOS, Linux, and WASI (run locally under wasmtime).
When swiftly is absent, check-wasm.sh fell back to the active `swift`. The Xcode-bundled
Apple toolchain has no WebAssembly LLVM codegen backend, so a wasm cross-compile through
it does not fail cleanly: it aborts deep inside LLVM (clang module build, "No available
targets are compatible with triple wasm32-...") with a multi-megabyte stack dump that
reads like a code bug. The SDK-presence check passed (the SDK is installed) and the build
crashed anyway, so the real cause, the wrong host toolchain, was invisible.
Detect it up front and exit 2 with an actionable message. Discriminate by the compiler's
self-reported build tag, not its path: both toolchains print "Apple Swift version X", but
the Xcode/Apple build tags it "(swiftlang-...)" while a swift.org toolchain tags it
"(swift-...-RELEASE/SNAPSHOT)". The self-report is authoritative however `swift` is
symlinked or shimmed, which a path-string match would miss. `swift -print-target-info
-target wasm32-...` is not a usable probe: it succeeds even without the backend, because
the frontend knows the triple and only codegen is missing.
* 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.
Step 1 of the GSS content-matcher build (docs/design/counted-content-automaton.md).
A multiply-referenced `<xs:group>` expands to one copy-on-write-shared `Particle`
(GroupParticleMemo), but `Group`/`Term` are value types with no exposed identity,
so a content-model compiler cannot tell two references apart and inlines the group
per reference (the 2^K build the GSS matcher will close).
Group now carries a `definitionID: Int?`, stamped from a per-compile counter on
GroupParticleMemo when an expansion is first compiled, so every reference sharing
the memo key reuses the same stamped term and distinct definitions differ. It is
metadata only: Group is not Equatable/Hashable, so it perturbs no determinism or
restriction comparison, and it is nil for an inline group.
FP-neutral by construction (no consumer yet). Full in-repo suite green; the XSTS
buckets are unchanged (valid-schemas-rejected 0, invalid-schemas-accepted 8,
valid-instances-rejected 0, invalid-instances-accepted 14); swiftformat/swiftlint
clean. Step 2 (a call/return content-model build keyed on this id, alongside the
inlining oracle) consumes it.
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.
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.
