NodetteHQ/PureXML
1
0
Fork 0
Code Issues 5 Pull Requests Actions Packages Projects Releases 1 Wiki Activity

1 Release 12 Tags

RSS Feed
  • v0.4.8 d63218256c
    Compare

    PureXML 0.4.8 Stable

    Mihaela released this 2026-07-05 03:37:05 +00:00 | 22 commits to main since this release

    Changed

    • A generated-value facet differential against libxml2 (FacetValidationDifferentialTests, opt-in via FACET_DIFF and xmllint) exercises the datatype and facet value space, the largest correctness surface the determinism and instance-content differentials do not touch: for each generated simple type restricting a built-in (xs:int, decimal, double, string, token, boolean, date, dateTime, nonNegativeInteger) by a subset of its facets (min/maxInclusive/Exclusive, length/min/maxLength, totalDigits/fractionDigits, pattern, enumeration, whiteSpace), it validates a pool of values chosen at and around the facet boundaries with PureXML and with libxml2 and flags every disagreement, asserting the cardinal rule (zero values PureXML rejects that libxml2 accepts). Over about ten thousand values it found one false positive, the NaN enumeration fixed below, and otherwise zero; the residual false negatives are contested datatype readings (whitespace collapse, NaN against a range facet) where PureXML matches the XSD spec and this libxml2 build is stricter. Test-only.

    • Compiling a schema with a long <xs:simpleType> restriction chain (S0 restricting S1 restricting S2, and so on) is no longer near-cubic in the chain length, so a deep chain no longer stalls the compiler, a keystroke-time interactive-safety hang on hostile or generated input. Such a chain is flat in the document, so the same base type was resolved over and over: the named simple types were resolved by an N-pass fixpoint that re-resolved every type on every pass, and the facet-applicability variety check re-scanned the schema's children to find each base at every link of every type's chain. Named simple types are now resolved once in dependency order (base before derived), and the variety check resolves a base through a precomputed name map in constant time and memoizes each type's variety, so a chain is walked once rather than per type. A 600-link restriction chain that took about 4.4 seconds to compile now takes about 30 milliseconds. Behaviour-preserving: the resolved types and the emitted findings are identical, verified conformance-neutral over the full W3C XSTS corpus in release (all four buckets unchanged), the libxml2 determinism differential unchanged, and the full suite. The analogous repeated re-scan in attribute-group reference chains is milder and remains, tracked.

    • Compiling a schema with a long <xs:complexType> simpleContent extension chain (T0 extending T1 extending T2, and so on) is likewise no longer near-cubic. Each of the N types re-walked its whole base chain to resolve the simple type its simpleContent derives from, the same flat-document re-resolution. The resolved simple type of a complex type's simpleContent is now memoized by name (SimpleContentMemo, a reference type that survives the value-type context copies), so a chain is walked once rather than per type. A 400-link chain that took about 23 seconds to compile now takes about 1.2 seconds; past the content-model expansion-depth bound (512) such a chain is rejected with a located error as before. Behaviour-preserving: the resolved type is intrinsic to the name for an acyclic chain (a derivation cycle is rejected elsewhere), verified conformance-neutral over the full W3C XSTS corpus in release. The attribute flattening that accumulates each type's attributes along the chain is inherently quadratic in the bounded chain length and is tracked.

    • A generated-instance validation differential against libxml2 (InstanceValidationDifferentialTests, opt-in via INSTANCE_DIFF and xmllint) exercises 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. Where the schema-compile determinism check has its own differential, this characterises instance validation, 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. Test-only; no shipped behaviour change.

    • The graph-structured-stack content matcher's runtime resource use now has a proven, asserted bound: ContentRTNMatcher exposes peakLiveConfigurations (the largest live-configuration set in any closure) and gssNodeCount (the total graph-structured-stack nodes built), and ContentRTNDifferentialTests asserts they stay linear in a shared-group chain's depth (measured gss = K + 2, peak configurations = 3K + 3), where an explicit return stack would reach O(distinct stacks). The bound is checked by count, not by a machine-dependent wall-clock timeout, so a regression to super-linear fails the test rather than only slowing down. Test-and-metadata only; no shipped behaviour change.

    • A generated-schema determinism differential against libxml2 (DeterminismDifferentialTests, opt-in via DETERMINISM_DIFF and xmllint) fuzzes content models, elements, group references, choices, sequences, all groups, occurrences, and wildcards, and compares PureXML's Unique Particle Attribution accept/reject verdict to the reference's. The XSTS corpus is finite and did not exercise the multiply-referenced-group overlap that was a real gap; this characterises the UPA check over the open shape space instead, asserting the cardinal rule (zero schemas PureXML rejects as ambiguous that libxml2 accepts) and reporting false negatives for triage. It found zero false positives and a 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 gap before the enclosing repetition's loop edge, so the combined decision set is never checked. Test-only; no shipped behaviour change.

    • A model Group now carries an internal definitionID, a stable identity stamped on each <xs:group> expansion (from the existing per-compile memo key) and shared by every reference to it. It is metadata only (Group is not Equatable/Hashable, so it perturbs no comparison) and has no consumer yet: it is the first step of replacing the per-instance content-model build's per-reference group inlining (the 2^K doubling-chain hang) with the graph-structured-stack matcher designed in docs/design/counted-content-automaton.md. No behaviour change; the XSTS buckets are unchanged.

    • The counted content matcher gains a shared-group form: ContentRTNBuilder compiles a particle to a Recursive Transition Network in which each definitionID group is compiled once and reached by a call, and ContentRTNMatcher simulates it with a graph-structured stack (configurations are (state, counters, gssNode); a call saves the caller's counters on an interned GSS node and a return restores them, so a multiply-referenced group never mixes counter state across its callers). This replaces the inlining matcher's 2^K state and reset-action blow-up with an O(groups) build: a depth-24 doubling chain (2^24 inlined states) compiles to under 480 states in under a millisecond. The matcher exposes the full surface the content-model validator reads: matchesWhole, matchedParticles, and the streaming startStates/step/admissible/isComplete used for located diagnostics and the "expected a, b" hints. It is verified against the trusted inlining matcher (ContentNFA) as the oracle by a differential gate (ContentRTNDifferentialTests) that locks not only the accept verdict and the matched particle but the located rejection index, the admissible expectation set at every prefix, and isComplete, over: the hand-written 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 group references stamped the way the parser stamps them (a unique id per distinct group, a shared id only for genuinely shared structure, some anonymous inline groups). It is built alongside the inlining matcher and is not yet wired into validation, so there is no behaviour change and the XSTS buckets are unchanged; the switch-over is gated on this differential plus XSTS neutrality.

    • Content-model validation and completion now run on the graph-structured-stack matcher: the three call sites that built the inlining automaton per validated element, ComplexValidatorContentModel.sequenceStructureErrors (located structure errors), ComplexValidator.validateParticle (per-child particle attribution), and XSDCompletions (the acceptable-next labels), now build ContentRTNBuilder and run ContentRTNMatcher. This removes the last per-instance 2^K content-model blow-up: a schema whose nested <xs:group> references inlined 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 now built in O(groups). 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) and behaviour-identical on the located diagnostics and completions by the surface differential above. ContentNFABuilder/ContentNFA are retained as the differential oracle.

    • The schema-validity differential harness (XSTSDifferentialTests, the opt-in libxml2 characterisation for production-readiness stopper 3) now reports each disagreeing schema by its path relative to the corpus root, not its bare basename. The same basename recurs across subdirectories (Facets/Schemas/gMonth_maxInclusive001.xsd, which carries value="" and is correctly rejected, versus Facets/gMonth/gMonth_maxInclusive001.xsd, which carries the contested 2001-REC --MM-- form), so a basename-only entry hid which file actually disagrees. The header now also records the triage of the "libxml2 stricter" queue: it is dominated by libxml2 over-strictness (a maxOccurs like 999999999999999 is a valid unbounded-precision integer libxml2 rejects on its machine-int limit; an unresolvable include/import it fails to load) and contested datatype-version readings (gMonth --MM--, accepted to keep valid XSTS instances; anyURI strictness), not clean false negatives. Characterisation only; no shipped behaviour changes.

    Fixed

    • An unprefixed xsi:type value now resolves in the instance's namespace context rather than matching a namespaced type by local name alone. xsi:type 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. The resolver now keys an unprefixed xsi:type to the in-scope default namespace (none here), so xsi:type="Test" names no-namespace Test, which does not exist; the root element then has neither a declaration nor a usable type and the instance is invalid (W3C XSTS targetNS00101m; libxml2 rejects it identically). A prefixed xsi:type and an unprefixed one under a matching default namespace are unaffected. Verified over the full W3C XSTS corpus in release: invalid-instances-accepted 6 -> 5, valid-instances-rejected held at 0 across all 14383 groups, and the full suite passes.

    • An XSD key/keyref/unique field that selects a node whose declared type is not simple is now rejected (cvc-identity-constraint.3), rather than wrongly accepted. The XSD identity-constraint rule requires each 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 failing W3C XSTS case idZ010 nests anyType fields several levels deep). A compile-time pass (XSDParser.identityNonSimpleFieldKeys) now 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 (cvc reads the node's governing type, so a text-only anyType element with xsi:type="xsd:int" is still 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. 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 introduced), and the full suite passes.

    • The XSD regex escapes \i and \c now use the XML 1.0 Second Edition name classes (Appendix B), not the parser's Fifth Edition Name production. XSD 1.0 (Datatypes Appendix F) defines \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, which are the enumerated Unicode-2.0-era character classes of XML 1.0 Appendix B. \i/\c were wired to PureXML.Parsing.XMLCharacter, which correctly implements the Fifth Edition 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, for example the combining mark U+0346 (COMBINING BRIDGE ABOVE), which Appendix B's CombiningChar excludes (its first range ends at U+0345). A new XSDNameCharacter, transcribed clean-room from the Appendix B grammar (identical across editions one through four) and stored as sorted code-point ranges with binary-search membership, now backs both escapes; the parser's own name check is untouched. The two range tables are verified to reproduce the W3C XSTS \i/\c enumerations (reZ005, reZ006, 34516 and 35122 code points) exactly and in both directions, so 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), with both false-positive buckets at 0. 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.

    • The Ethiopic digits U+1369..U+1371 (ETHIOPIC DIGIT ONE..NINE) now match \d in an XSD pattern and not \D. XSD 1.0 fixes the regular-expression repertoire at Unicode 3.2 (Datatypes Appendix F), where these nine code points are general category Nd and each carries 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 override table was missing these nine, so \d used the modern No and rejected them. This was a two-directional bug: a valid instance whose \d-constrained value was an Ethiopic digit was wrongly rejected (the cardinal rule: never reject a valid value), and a \D-constrained value of one was wrongly accepted. They are now pinned to Nd, which is the complete set of code points that were Nd at 3.2 and are not today (the reverse direction is empty: every code point that became Nd later was unassigned at 3.2 and so already reports Cn, verified by diffing the 3.2 and current Unicode Nd sets), so \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), the matching \d valid cases (reS17, reS38, reZ004) no longer need their suspect-test exclusion and pass as ordinary agreements, and the two false-positive buckets stay 0. Found while triaging the invalid-instance tail against libxml2 (which rejects reT17/reT38, the reference-aligned reading) back to the authoritative UnicodeData-3.2.0; a prior note that had treated these as a disputed spec-divergence was the wrong call and is corrected.

    • A value of NaN is no longer wrongly rejected by an xs:double or xs:float enumeration that lists NaN. Value-space equality (OrderedValue.==) compared with IEEE equality, under which NaN != NaN, so a NaN value never matched a NaN enumeration member and was rejected, a false positive (the cardinal rule: never reject a valid value). The comparison now treats NaN as identical to itself, the value-space identity the reference (libxml2) and XSD 1.1 use throughout, so <v>NaN</v> validates against a type restricting xs:double by <xs:enumeration value="NaN"/>; INF/-INF already matched. This equality also backs the key/unique identity constraints and fixed, where the same identity holds (verified against xmllint): two NaN-valued unique fields collide as duplicates, and fixed="NaN" matches NaN. The ordering facets (minInclusive and friends) use the order relation, in which NaN stays incomparable, and are unaffected. Found by the new generated-value facet differential against libxml2, with the key/fixed behaviour confirmed after an adversarial critic flagged the shared comparison; the four W3C XSTS buckets held and the full suite passes, with regressions in SchemaDoubleEnumerationTests.

    • A long <xs:attributeGroup ref> chain (ag0 referencing ag1 referencing ag2, and so on) no longer overflows the stack or hangs the compiler. Such a chain is flat in the schema document, so flattening a complex type's attributes through it recursed once per link, overflowing the stack past about six thousand links and running near-cubic before that (about 17 seconds at three thousand links). The attribute-group reference depth is now bounded by maximumContentModelExpansionDepth (512, the same bound the content-model expansion uses), since the cycle-guard visited set already counts the chain depth: a chain past the bound is rejected with a located error (attribute group reference nesting exceeds the maximum depth of 512) rather than crashed. Behaviour-preserving for every schema within the bound, which no realistic schema or the XSTS corpus approaches; verified conformance-neutral over the full W3C XSTS corpus in release (all four buckets unchanged) and by the full suite. Disclosed residual: a schema with very many distinct over-bound attribute-group chains still rejects in time quadratic in the bounded depth per group, because the attribute flattening is re-done per group; memoizing it, as the simpleContent resolution now is, is the linear follow-up.

    • The schema compiler no longer overflows the stack on a content model whose expanded depth is unbounded. 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 (the group definitions are siblings, not nested) and a complexContent derivation chain (B0 extends B1 extends B2, and so on, the type definitions also siblings). The particle compiler inlines each group reference and composes each derivation once per link, so a long chain recursed once per link until the stack overflowed while compiling a legal, if hostile, schema, a keystroke-time interactive-safety crash. The expanded depth is now bounded by a single counter (XSDContext.expansionDepth, incremented at each compositor level, group-reference expansion, and derivation step) against maximumContentModelExpansionDepth (512, twice the element-nesting limit: room for a maximally nested model plus as much again for expansion). A model past the bound is rejected with a located error (content model nesting ... exceeds the maximum depth of 512, or the derivation form), not crashed: a bound, not a band-aid. The bound is on total expanded depth, so it covers both a long chain of shallow links and a short chain of internally deep ones. Together with the determinism-check fix below, this closes the group-reference-chain crash on every compiler pass that recursed on the chain. Verified conformance-neutral over the full W3C XSTS corpus in release (all four buckets unchanged; no valid schema newly rejected, the corpus's content models nesting far below the bound), the libxml2 determinism differential unchanged, and the full suite. An adversarial over-rejection critic confirmed the counter lives in a value-type context whose copies make it track depth, not width, so a wide-but-shallow model (hundreds of sibling particles) is never falsely rejected, and that the rejection is harvested into the schema's errors rather than silently truncating the model.

    • A deeply nested chain of <xs:group> references (g0 referencing g1 referencing g2, and so on) no longer overflows the stack in the Unique Particle Attribution determinism check. Such a chain is flat in the schema document, the group definitions being siblings rather than nested, so it is not bounded by the parser's maxDepth; the compositional check summarised each group lazily by recursing through the reference at its use site, so a long chain recursed once per link and overflowed the stack while compiling a legal (if hostile) schema, a keystroke-time interactive-safety crash on the primary platform. Group summaries form an acyclic graph (a circular group reference is rejected elsewhere), so they are now precomputed bottom-up in dependency order: every reachable group is summarised once, in an order where each group's own references are already cached, so the walk's group lookup is always a cache hit and recursion is bounded by a single group's model nesting (which maxDepth bounds), not by the chain length. A group summary is context-independent, so this only reorders the work; the set of decision sets it produces is identical and the accept/reject verdict does not depend on their order. Verified verdict-equivalent over the full W3C XSTS corpus in release (all four buckets unchanged: valid-schemas-rejected and valid-instances-rejected stay 0, invalid-schemas-accepted 8, invalid-instances-accepted 14), the generated-schema determinism differential against libxml2 unchanged (zero false positives, the same three named false negatives), and the full 1816-test suite. The particle-compiler pass that inlines a group reference, which this left recursing on the same chain, is now bounded as well (see the content-model expansion-depth entry above).

    • A repeating model whose optional trailing particle and leading particle share a name, (c, b?, c?)*, is now correctly rejected as a Unique Particle Attribution violation, 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 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) with 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.

    • Two references to the same <xs:group> that overlap ((g?, g?), (g | g), (g*, g)) are now correctly rejected as a Unique Particle Attribution violation, as the inline forms (x?, x?) / (x | x) already were 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 that two references are two expanded occurrences, and PureXML accepted these models (an invalid-schemas-accepted false negative). It also let the per-instance content matcher run on such a non-UPA model, where a multiply-referenced nullable group is exponential: a depth-18 optional doubling chain was accepted and then hung instance validation, a keystroke-time interactive-safety 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, while the repetition self-loop (a*, (a*)*) keeps its non-flagging dedupe so a single particle looping is not misread as two occurrences. This also bounds the check: the deduped first/follow sets stay O(labels) instead of 2^K, so the same depth-40 chain is now rejected at compile in 11 ms and no instance is ever matched against it. A redefine self-extension (<extension base="T"> inside the redefinition of T) lists a type's own content twice through effectiveModelNodes; that assembly artifact is deduped before the walk so it is not read as a conflict (addB094, schZ007). Verified over the full W3C XSTS corpus in release: valid-schemas-rejected and valid-instances-rejected stay 0 and invalid-*-accepted are unchanged (the corpus does not exercise this shape in its pinned buckets), with an adversarial over-rejection critic finding no valid schema newly rejected across the group-overlap shape space.

    • XSTS invalid-schemas-accepted (#145): a particle restriction whose restricting element has a union-typed base element now applies Type Derivation OK (Simple) (cos-st-derived-ok) rather than structural member subsetting. The NameAndTypeOK type clause (§3.9.6) requires the restricting element's type to be validly derived from the base element's type; PureXML accepted a separately declared union whenever its member types were a subset of the base union's members, which is not the spec's derivation relation. The restricting type is now valid over a union base only if it is the base type, derives from it through a declared restriction chain, or (clause 2.2.4) validly derives from one of the union's member types. Catches particlesIk011 (a fresh union(integer) is not a restriction of union(integer, string)): invalid-schemas-accepted 9 to 8, with valid-schemas-rejected held at 0 (verified over the full XSTS; the change is scoped to the element-restriction path, so no attribute or simple-type derivation check moved). Disclosed divergence: particlesIk025/Ik027, where the restricting type derives from a union member, are accepted per cos-st-derived-ok clause 2.2.4, a contested reading their XSTS invalid expectation does not share.

    Removed

    • Five unused internal schema-consistency wrappers (idAttributeErrors, consistencyErrors, postNamedTypeErrors, structureErrors, includeCompositionErrors) that returned [String] reason lists, along with the now-orphaned postCompileErrors(schema:context:containers:namedTypes:) overload and the SchemaCompileNamedTypes struct it consumed. None had callers; the XSDParser.consistencyErrors overload was shadowed by the distinct, still-live Validation.XSDSchema.consistencyErrors (a different signature returning ValidationError), which is why a name-only search first read it as used. The located-diagnostic API (the *Findings functions returning SchemaLocatedFinding, and Validation.XSDSchema returning ValidationError) superseded all of them. Removing them deletes dead code with no behavior change; the live *Findings and Validation.XSDSchema functions are unchanged. A stale doc-comment reference to the renamed userTypeValueConstraintErrors (now userTypeValueConstraintFindings) was corrected at the same time.

    • Two unused private helpers in XSLTNamespaceFixup (fixAttributeName and resolvedPrefix). The result-tree attribute fixup they implemented was inlined into fix(_ element:) and evolved past them (the inlined version additionally shadows a carried prefix through localPrefixes, which the helpers did not), leaving both with zero callers. Removing them deletes dead, diverged duplicate logic with no behavior change; the live inlined path is unchanged.

    • Three more dead file-scoped functions found by a private-scope sweep: selectNodes in XSLTTransformer (its sibling selectXPathNodes is the live one; a doc comment that referenced it was reworded), processingInstructionMatches in EvaluatorSteps, and parseExternalID in DoctypeScanner. All three are private/fileprivate with zero callers, so removing them is provably behavior-neutral (the compiler confirms).

    • Three more dead functions found by a repo-wide reference sweep: XSLTTransform.transformToNode (a transform-to-tree variant nothing called; the live transform returning a string is independent), and ComplexValidatorHelpers.matchesAll together with its now-orphaned helper label(of:). All had zero references; build and 1775 tests confirm behavior is unchanged.

    Fixed

    • The XSLT evaluator is now iterative, so template recursion and result-tree nesting no longer consume the native stack (#356). A recursive named template whose depth is driven by source data (for example <xsl:with-param name="n" select="count(//x)"/>) could previously recurse without bound and crash the process (SIGBUS) on attacker-controllable input; and even an identity transform of a deeply-nested source overflowed the stack on a small (Swift-concurrency Task) stack. The mutually-recursive instantiate/evaluate/applyTemplates engine is replaced by an explicit work-stack driver (XSLTDriver): each instruction appends its produced items to a sink or pushes sub-work, with the rest of the body pushed first so document order is preserved; template application, the built-in rule's source descent, and result-element nesting all run on the heap. Only stylesheet-bounded helper evaluation (a variable's or parameter's result-tree fragment, an attribute set, an xsl:message body) re-enters through a nested driver call, whose native depth is bounded by the stylesheet's own nesting. The result-tree serialization walks the engine now exposes at depth (the namespace fixup, the text and string-value extractions, and the content-type-meta and CDATA-section rewrites) were made iterative as well. Deep recursion now succeeds on any stack (a 5000-level recursive template builds and serializes on the test Task stack); maxTemplateDepth is retained as runaway protection (an unbounded result tree would otherwise exhaust memory), now defaulting to 40000 and tripping XSLTError.recursionLimitExceeded only past that. Behavior is otherwise unchanged: the full Apache Xalan XSLT 1.0 conformance corpus and the in-repo XSLT/XPath suites pass identically (one previously-failing Xalan case, mdocs07, now passes and was de-baselined). maxTemplateDepth and PureXML.XSLT.defaultMaxTemplateDepth (added for the earlier stack-based guard) keep their public shape.

    • Serializing a tree as HTML (PureXML.HTML.serialize, the html output method's serializer) no longer recurses on the tree's depth, so it no longer overflows the stack on a deeply-nested tree (as shallow as a couple of thousand deep on a Swift Task stack). The serializer now drives a deferred-close work stack (the same shape as the XML serializer and Canonicalizer): an element pushes a close step then its children reversed, and a raw-text element (script, style) flags its direct text children to emit verbatim. The output is byte-identical: the void-element, raw-text, comment, and escaping semantics are unchanged, with the HTML conformance corpus passing. A 50000-deep tree now serializes without crashing. (#350)

    • Processing xi:include elements (PureXML.XInclude.process) no longer recurses on the tree's depth, so it no longer overflows the stack on a deeply-nested document, even one with no includes (as shallow as a couple of thousand deep on a Swift Task stack). The pass now drives an explicit work stack: each branch gathers its processed children into a reference accumulator, then a deferred build step assembles the node, while the xml:base, inclusion-chain depth, and cycle-detection visited set thread down exactly as before. An include splices its (or its fallback's) content in place by pushing the loaded nodes back onto the stack. Behavior is unchanged: the XInclude/XPointer conformance corpus and the fallback, xpointer, cycle, and xml:base cases pass. A 50000-deep document, with or without an include at its base, now processes without crashing. (#350)

    • The two Canonical XML transforms that still recursed on a document's depth are now iterative, so they no longer overflow the stack on a deeply-nested tree (#350). The C14N 2.0 sequential prefix rewrite walks the tree twice (a document-order pass that assigns one canonical prefix per namespace, then a rebuild pass); both now drive explicit stacks, the assign pass a pre-order walk and the rebuild pass a child-gathering accumulator, with the in-scope declarations and the root flag threaded down per element. The node-subset serializer (canonicalize(_:including:), the C14N form over a selected subtree) now drives the same deferred-close work stack as the main serializer, threading each element's in-scope and rendered namespace context, with an omitted element still passing its declarations to descendants. The canonical bytes are unchanged: the C14N exclusive, 2.0, and node-subset corpora pass. A 50000-deep document now rewrites and subset-canonicalizes without crashing. (#350)

    • Canonicalizing a document (Canonicalizer, the C14N form used for XML signatures) no longer recurses on the document's depth, so it no longer overflows the stack on a deeply-nested document (it crashed around 5000 deep). The serializer now drives a deferred-close work stack that threads each element's namespace context to its children. The canonical bytes are unchanged: the C14N 1.0/1.1 and exclusive conformance corpora pass. (#350)

    • Applying DTD attribute defaults to a document (parseApplyingInternalDTDDefaults, and the defaults pass behind DTD validation) no longer recurses on the document's depth, so it no longer overflows the stack on a deeply-nested document. The tree is rebuilt bottom-up through a new shared iterative spine (Node.rebuildingBottomUp), which the other tree-to-tree transforms will adopt. (#350)

    • String-value extraction no longer recurses on a node's depth, so computing the string-value of a deeply-nested node no longer overflows the stack (it crashed as shallow as a couple of thousand deep on a Swift Task stack). TreeNode.textContent and the value-Node string-value behind XPath.Query.strings/Selection.stringValue now walk the subtree iteratively. (#350)

    • The value-Node string-value (behind XPath.Query.strings and Selection.stringValue) no longer includes the data of descendant comment and processing-instruction nodes in an element's string-value, matching XPath 1.0 (sections 5.1 and 5.5, where only text and CDATA contribute) and the tree-node path. A comment or PI node's own string-value is still its data (5.6, 5.7).

    • The value-returning XPath result API (PureXML.xpath, XPath.Query.evaluate/elements/strings) is now linear for results that nest within one another, not quadratic. Each result was rebuilt as an independent value Node subtree, so selecting a deep chain of nested elements materialized the sum of their subtrees. The projection now shares a per-result-set memo keyed by tree-node identity, so a result reuses the already-built value Node of a deeper one by reference (copy-on-write); each tree node is projected once. //a over a 8000-deep chain drops from about 19 s to about 0.04 s, and the result set is unchanged. (#348)

    • Sorting an XPath result into document order is now linear in the document, not quadratic in its depth. Each node's order key was its root path, an array as long as the node's depth, so ordering the descendants of a deeply-nested document was O(n log n x depth). The key is now a single O(1) index from a per-root pre-order numbering (built once per document and shared through the evaluation cache), with a band ordering an element before its namespace and attribute nodes and its children. A node-set spanning several documents is grouped by root. This linearizes the reference query path (Query.nodes, which XSLT and Schematron drive) on deep documents; the underlying subtree walk (appendSubtree) is now iterative too, so it no longer recurses. Document order is unchanged.

    • Parsing is now linear in nesting depth, not quadratic. Resolving each open element's name and attributes looked up namespace bindings by walking a scope stack as deep as the document, so a deeply-nested document was O(depth^2): a 40000-deep document took tens of seconds. The parser now maintains the current in-scope bindings incrementally (a single map plus a per-element undo list), so a lookup is O(1) and parsing is O(n). The same document parses in a fraction of a second, with no change to resolved namespaces. (#345)

    • The immutable value Model.Node tree type is now depth-safe. An Element previously stored its children inline (the enum was indirect), so a Node's recursive layout made building, comparing, hashing, and releasing a deeply-nested tree recurse one native frame per level and overflow the stack (on a constrained stack such as a Swift Task, as shallow as a few thousand deep). Element now holds its children behind a copy-on-write reference (ElementStorage): the Node enum is no longer indirect, so it is a fixed-size value, and ==, hashValue, and release all walk the tree iteratively through explicit work stacks. Release flattens only storage it solely owns, so a copy-on-write sibling keeps its subtree. Value semantics are unchanged (copying a node still copies its children, lazily) and Element/Node remain Equatable, Hashable, and Sendable. A 50000-deep tree now builds, compares, hashes, and releases in a fraction of a second with no crash. (Completes the value-Node half of #341.)

    • The mutable Model.TreeNode tree type is now depth-safe: building one from a value Node, projecting it back with node, and releasing it all run in bounded native stack instead of recursing one frame per level. Construction (TreeNode(_:)) and projection (node/projectedChildren) drive explicit post-order work stacks, and deinit flattens its subtree into a heap worklist before releasing, so a deeply-nested tree no longer overflows the stack through a recursive chain of child releases. The teardown only flattens nodes it solely owns (isKnownUniquelyReferenced), so a child still referenced elsewhere keeps its subtree. A 60000-deep tree releases in well under a tenth of a second; behaviour for ordinary trees is unchanged. The validator walk and the XPath descendant axis (AxisNavigation.appendDescendants) were made iterative for the same reason. (Part of #341. The immutable value Node's own recursive release, and XPath result ordering/dedup, are still depth-bounded and tracked there.)

    • Rejecting a billion-laughs document is no longer exponential in nesting depth. The "does this entity produce markup" check (splitAtMarkupEntity / producesMarkup) recursed into every reference of every replacement without memoizing, so a chain lol8 -> 10x lol7 -> 100x lol6 -> ... was traversed O(references^depth) times. The check is now memoized per entity name (the property depends only on the fixed entity graph), making it O(entities). A classic eight-level billion-laughs with DTD processing enabled drops from about 18 s to about 0.6 s (now bounded by the expansion budget, not the traversal), with no change to which documents are accepted; a cyclic entity is still rejected.

    • The No-Recursion check (checkRecursion) no longer re-traverses shared sub-chains. It validated the reference graph with only an in-progress (grey) set, so a billion-laughs graph was walked O(references^depth) times; a markup-producing eight-level document took about 31 s to reject. It is now a three-colour DFS that records each fully-verified entity (black set) and skips it on revisit, one pass over the distinct edges. The same document drops to about 11 s; cyclic entities are still rejected and no accepted document changes. (The residual cost is the re-injection re-read of the growing remainder on the markup-inclusion path, where Reader.inject re-maps the unconsumed tail each cycle; tracked in #339.)

    • Entity and content expansion is no longer quadratic in the size of a single expansion. The parser's lookahead buffer consumed from the front with Array.removeFirst() and re-injected entity replacement text with insert(at: 0), both O(buffer), so a large internal entity (or a long run pushed back by reference inclusion) was consumed in O(n^2). The buffer now advances a head index, so front-consume is O(1), and re-injection reuses the space the consumed prefix freed, so a single large expansion is linear. An 800000-character internal text entity that previously took quadratic time now parses in about 0.6 s. Behavior, characters, and limits are unchanged; guarded by the standing suite. (A separate quadratic in deeply-nested entity references, where the content scanner re-reads the un-expanded remainder, is tracked as its own issue.)

    • A complex type with simple content that restricts a base may no longer relax a base required attribute to optional (XSD 1.0 cos-ct-derived-ok / derivation-ok-restriction.2). The attribute-use restriction check ran only over complexContent restrictions, so a simpleContent restriction that relaxed a required attribute (or added a non-base attribute, or widened the attribute wildcard) was accepted; it now runs over both derivation roots. Closes XSTS particlesZ030_d, which libxml2 also rejects, so the fix aligns with the reference rather than exceeding it. XSTS invalid-schemas-accepted 10 -> 9 with valid-schemas-rejected held at 0 (full archive). Guarded by SimpleContentAttrRestrictionTests.

    • xpointer(string-range(...)) no longer uses a quadratic substring search. It matched the search string at every position of each node's value and re-allocated the whole needle-width window per position (O(text * needle), a denial-of-service vector on a long node value with a near-matching needle); it now uses a linear-time Knuth-Morris-Pratt search with the failure function built once. The matches are unchanged: same non-overlapping, left-to-right occurrences, same offset/length. A near-matching needle over a 16000-character node drops from about 0.18 s to about 0.002 s (~100x), and the cost is now linear. Guarded by the new non-overlapping and backtracking cases in XPointerRangeTests.

    • The XSLT id() function no longer scans the whole document ID index on every call. It filtered the entire index by tokens.contains(...) (O(index) per call), so a stylesheet calling id() across a wide document was quadratic; it now looks each requested token up directly (O(tokens)). The result is unchanged: the same elements in document order. A stylesheet resolving 4000 id() references against a 4000-entry index drops from about 0.34 s to about 0.03 s (~13x), and the cost is now linear. (key() already used direct lookups.)

    Verification

    • macOS: full gate (style, namespacing, forbidden patterns, validation
      coverage, changelog, roadmap, swiftformat, swiftlint strict, build, and
      1843 tests in 345 suites including the W3C XML, XSTS, Xalan, and RelaxNG
      conformance batteries).
    • Linux: build and 1843 tests in 345 suites, Swift 6.3.2 on aarch64.
    • WASM: debug and release library builds with the swift-6.3.2-RELEASE_wasm SDK.

    Known deferred issues

    • Windows build and test were NOT run for this release: the Windows CI
      workflow was hosted on GitHub and has no Codeberg runner equivalent yet.
    Downloads