Mihaela Mihaljevic
5bd4b77305
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.
269 lines
15 KiB
Swift
269 lines
15 KiB
Swift
import Testing
|
|
@testable import PureXML
|
|
|
|
/// Locks the graph-structured-stack content matcher (`ContentRTNMatcher`, which
|
|
/// shares each `<xs:group>` definition) to the trusted inlining matcher
|
|
/// (`ContentNFA`) as the oracle: they must agree on the verdict and the matched
|
|
/// particle for every child sequence, and the RTN build must stay polynomial where
|
|
/// the inlining build is `2^K`. The differential gate from the GSS-matcher design.
|
|
@Suite("RTN/GSS vs inlining content-matcher differential")
|
|
struct ContentRTNDifferentialTests {
|
|
private func element(_ name: String, min: Int = 1, max: Int? = 1) -> PureXML.Schema.Particle {
|
|
// A per-name fixed value constraint so the matched-particle comparison sees the
|
|
// metadata `matchedParticles` carries (type/valueConstraint), not only the
|
|
// element/wildcard kind. A name maps to one constraint (as a real schema's
|
|
// element declaration does), so whichever particle of a given name is picked, its
|
|
// constraint is the same: the comparison stays meaningful without depending on the
|
|
// lowest-state-index tie-break, which only distinguishes same-name particles, and
|
|
// same-name particles with differing metadata are a UPA violation the schema
|
|
// compiler rejects before any instance is validated.
|
|
.init(minOccurs: min, maxOccurs: max, term: .element(name: .init(name), type: nil, typeName: nil, valueConstraint: .fixed("v-\(name)")))
|
|
}
|
|
|
|
private func group(_ compositor: PureXML.Schema.Compositor, _ particles: [PureXML.Schema.Particle], min: Int = 1, max: Int? = 1, id: Int? = nil) -> PureXML.Schema.Particle {
|
|
.init(minOccurs: min, maxOccurs: max, term: .group(.init(compositor: compositor, particles: particles, definitionID: id)))
|
|
}
|
|
|
|
/// A `##any` wildcard, which admits every child; paired with a named element it
|
|
/// exercises the named-over-wildcard tie-break the matched-particle path must
|
|
/// reproduce.
|
|
private func wildcard(min: Int = 1, max: Int? = 1) -> PureXML.Schema.Particle {
|
|
.init(minOccurs: min, maxOccurs: max, term: .wildcard(.init()))
|
|
}
|
|
|
|
private func names(_ list: [String]) -> [PureXML.Model.QualifiedName] {
|
|
list.map { PureXML.Model.QualifiedName($0) }
|
|
}
|
|
|
|
/// Both matchers' accept verdict, and the kind (nil/element/wildcard) each child
|
|
/// was matched to, must agree.
|
|
private func assertAgree(_ particle: PureXML.Schema.Particle, _ sequence: [String], _ context: @autoclosure () -> String) {
|
|
let qnames = names(sequence)
|
|
let nfa = PureXML.Schema.ContentNFABuilder.build(particle)
|
|
let rtn = PureXML.Schema.ContentRTNBuilder.build(particle)
|
|
let nfaWhole = nfa.matchesWhole(qnames)
|
|
let rtnWhole = PureXML.Schema.ContentRTNMatcher(rtn).matchesWhole(qnames)
|
|
#expect(nfaWhole == rtnWhole, "verdict disagree on \(context()) for \(sequence): nfa=\(nfaWhole) rtn=\(rtnWhole)")
|
|
let nfaAttribution = nfa.matchedParticles(qnames).map(attribution)
|
|
let rtnAttribution = PureXML.Schema.ContentRTNMatcher(rtn).matchedParticles(qnames).map(attribution)
|
|
#expect(nfaAttribution == rtnAttribution, "attribution disagree on \(context()) for \(sequence): \(nfaAttribution) vs \(rtnAttribution)")
|
|
assertStreamingAgree(nfa, rtn, qnames, context())
|
|
}
|
|
|
|
/// Locks the located-diagnostic surface, not just the accept verdict: driving
|
|
/// both matchers child by child, the first child either rejects (`step` is nil)
|
|
/// in both or neither, the `admissible` expectation set agrees at the start and
|
|
/// after every accepted child, and `isComplete` agrees once the whole sequence is
|
|
/// consumed. This is what `sequenceStructureErrors` actually reads, so the
|
|
/// switch-over keeps the placed errors and the "expected a, b" hints identical.
|
|
private func assertStreamingAgree(
|
|
_ nfa: PureXML.Schema.ContentNFA,
|
|
_ rtn: PureXML.Schema.ContentRTN,
|
|
_ qnames: [PureXML.Model.QualifiedName],
|
|
_ context: @autoclosure () -> String,
|
|
) {
|
|
let matcher = PureXML.Schema.ContentRTNMatcher(rtn)
|
|
var nfaCurrent = nfa.startStates(inputLength: qnames.count)
|
|
var rtnCurrent = matcher.startStates(inputLength: qnames.count)
|
|
#expect(labelSet(nfa.admissible(from: nfaCurrent)) == labelSet(matcher.admissible(from: rtnCurrent)), "admissible@start disagree on \(context())")
|
|
var consumedAll = true
|
|
for (index, name) in qnames.enumerated() {
|
|
let nfaNext = nfa.step(nfaCurrent, over: name, inputLength: qnames.count)
|
|
let rtnNext = matcher.step(rtnCurrent, over: name)
|
|
#expect((nfaNext == nil) == (rtnNext == nil), "rejection-index disagree at child \(index) on \(context())")
|
|
guard let nfaStepped = nfaNext, let rtnStepped = rtnNext else { consumedAll = false
|
|
break
|
|
}
|
|
nfaCurrent = nfaStepped
|
|
rtnCurrent = rtnStepped
|
|
#expect(labelSet(nfa.admissible(from: nfaCurrent)) == labelSet(matcher.admissible(from: rtnCurrent)), "admissible@\(index) disagree on \(context())")
|
|
}
|
|
if consumedAll {
|
|
#expect(nfa.isComplete(nfaCurrent) == matcher.isComplete(rtnCurrent), "isComplete disagree on \(context())")
|
|
}
|
|
// The composed follow(after:) the completion path reads must agree too.
|
|
let nfaFollow = nfa.follow(after: qnames)
|
|
let rtnFollow = PureXML.Schema.ContentRTNMatcher(rtn).follow(after: qnames)
|
|
#expect(labelSet(nfaFollow.allowed) == labelSet(rtnFollow.allowed), "follow.allowed disagree on \(context())")
|
|
#expect(nfaFollow.complete == rtnFollow.complete, "follow.complete disagree on \(context())")
|
|
}
|
|
|
|
/// The full matched-particle attribution as a comparable string: the kind plus the
|
|
/// carried value constraint for a named element, so the comparison catches the
|
|
/// matcher dropping or swapping the metadata `matchedParticles` returns, not only a
|
|
/// kind flip. (`MatchedParticle` is not `Equatable` because `ElementType?` is not, so
|
|
/// project the observable fields.)
|
|
private func attribution(_ matched: PureXML.Schema.MatchedParticle?) -> String {
|
|
switch matched {
|
|
case .none: "nil"
|
|
case let .element(_, valueConstraint): "element:\(valueConstraint?.value ?? "-")"
|
|
case .wildcard: "wildcard"
|
|
}
|
|
}
|
|
|
|
/// The admissible labels as a set of comparable keys (the "expected" hint
|
|
/// de-duplicates, so set equality is the meaningful comparison). Wildcards are
|
|
/// all `##any` here, so one key suffices.
|
|
private func labelSet(_ labels: [PureXML.Schema.TermLabel]) -> Set<String> {
|
|
Set(labels.map { label in
|
|
switch label {
|
|
case let .name(qualified): "n:\(qualified.localName)|\(qualified.namespaceURI ?? "")"
|
|
case .wildcard: "w"
|
|
}
|
|
})
|
|
}
|
|
|
|
@Test("agree on the hand-written model cases (inline groups, no calls)")
|
|
func test_inlineCases() {
|
|
let cases: [(PureXML.Schema.Particle, [[String]])] = [
|
|
(group(.sequence, [element("a"), element("b")]), [["a", "b"], ["b", "a"], ["a"], []]),
|
|
(group(.choice, [element("a"), element("b")]), [["a"], ["b"], ["a", "b"], []]),
|
|
(group(.sequence, [element("a")], min: 0, max: nil), [[], ["a"], ["a", "a", "a"], ["b"]]),
|
|
(group(.sequence, [element("a")], min: 1, max: nil), [[], ["a"], ["a", "a"]]),
|
|
(group(.sequence, [element("a")], min: 0, max: 1), [[], ["a"], ["a", "a"]]),
|
|
(group(.choice, [group(.sequence, [element("a"), element("b")]), element("c")]), [["a", "b"], ["c"], ["a", "c"], ["a", "b", "c"]]),
|
|
(group(.sequence, [element("a", min: 0, max: 2), element("b", min: 1, max: 3)]), [["b"], ["a", "b"], ["a", "a", "b", "b", "b"], ["a", "a", "a", "b"]]),
|
|
// Named-over-wildcard tie-break: "a" matches both, the named particle wins;
|
|
// "b"/"c" match only the wildcard.
|
|
(group(.choice, [element("a"), wildcard()]), [["a"], ["b"], ["c"], []]),
|
|
(group(.sequence, [element("a"), wildcard(min: 0, max: nil)]), [["a"], ["a", "b", "c"], ["b"], []]),
|
|
]
|
|
for (particle, sequences) in cases {
|
|
for sequence in sequences {
|
|
assertAgree(particle, sequence, "inline")
|
|
}
|
|
}
|
|
}
|
|
|
|
/// `g0=(g1,g1), …, g_{K-1}=(gK,gK), gK=x`: the model is `x` repeated `2^K` times.
|
|
private func doubling(depth: Int) -> PureXML.Schema.Particle {
|
|
var current = element("x")
|
|
for level in stride(from: depth - 1, through: 0, by: -1) {
|
|
current = group(.sequence, [current, current], id: level)
|
|
}
|
|
return current
|
|
}
|
|
|
|
@Test("agree on shared-group doubling chains, exercising call/return")
|
|
func test_doublingCallReturn() {
|
|
for depth in 1 ... 5 {
|
|
let required = 1 << depth // 2^depth occurrences of x
|
|
let particle = doubling(depth: depth)
|
|
for count in [0, required - 1, required, required + 1] where count >= 0 {
|
|
assertAgree(particle, Array(repeating: "x", count: count), "doubling depth=\(depth)")
|
|
}
|
|
}
|
|
}
|
|
|
|
@Test("the RTN build is polynomial where the inlining build is 2^K")
|
|
func test_buildBound() {
|
|
// Depth 24 is 2^24 inlined states (infeasible to inline); the shared build
|
|
// must stay linear in the depth.
|
|
let rtn = PureXML.Schema.ContentRTNBuilder.build(doubling(depth: 24))
|
|
#expect(rtn.states.count < 24 * 20, "shared build is not linear in depth: \(rtn.states.count) states")
|
|
}
|
|
|
|
// The matcher's runtime resource use, asserted by COUNT not wall-clock (a timeout is
|
|
// machine-dependent): on a depth-K shared-group chain the live-configuration set and
|
|
// the graph-structured-stack node count stay linear in K (measured gss = K + 2, peak
|
|
// configurations = 3K + 3), where an explicit return stack would reach O(distinct
|
|
// stacks). A generous linear ceiling separates it from any super-linear regression.
|
|
// Native-only: the depth-80 RTN build recurses on nesting depth and overflows WASI's
|
|
// small single-threaded stack (the builder's deeper WASI depth-safety is separate).
|
|
#if !os(WASI)
|
|
@Test("the matcher's runtime resource use is linear in the depth, not exponential")
|
|
func test_runtimeBoundIsLinear() {
|
|
for depth in [20, 80] {
|
|
let rtn = PureXML.Schema.ContentRTNBuilder.build(doubling(depth: depth))
|
|
let matcher = PureXML.Schema.ContentRTNMatcher(rtn)
|
|
_ = matcher.matchesWhole(names(["x", "x", "x"]))
|
|
#expect(matcher.gssNodeCount < depth + 16, "GSS nodes not linear at depth \(depth): \(matcher.gssNodeCount)")
|
|
#expect(matcher.peakLiveConfigurations < 3 * depth + 16, "live configs not linear at depth \(depth): \(matcher.peakLiveConfigurations)")
|
|
}
|
|
}
|
|
#endif
|
|
|
|
@Test("agree on a fuzz of nested models with occurrences and shared groups")
|
|
func test_fuzz() {
|
|
var rng = SeededRNG(seed: 0x5EED_1234)
|
|
var nextID = 0
|
|
for _ in 0 ..< 4000 {
|
|
let particle = randomParticle(depth: 3, rng: &rng, nextID: &nextID)
|
|
let length = Int.random(in: 0 ... 6, using: &rng)
|
|
let sequence = (0 ..< length).map { _ in letter(&rng) }
|
|
assertAgree(particle, sequence, "fuzz")
|
|
}
|
|
}
|
|
|
|
/// `nextID` hands out a unique `definitionID` per distinct group, so a shared id
|
|
/// only ever marks genuinely-shared (structurally identical) groups; a monotonic
|
|
/// counter avoids the collision a random id risks. Most groups are stamped (the
|
|
/// production shape, where every `<xs:group ref>` is memoized and called, singly
|
|
/// or shared), some are left anonymous (inline, no call) to keep that path live.
|
|
private func randomParticle(depth: Int, rng: inout SeededRNG, nextID: inout Int) -> PureXML.Schema.Particle {
|
|
let (min, max): (Int, Int?) = switch Int.random(in: 0 ..< 5, using: &rng) {
|
|
case 0: (1, 1)
|
|
case 1: (0, 1)
|
|
case 2: (0, nil)
|
|
case 3: (1, nil)
|
|
default: (Int.random(in: 0 ... 2, using: &rng), Int.random(in: 2 ... 3, using: &rng))
|
|
}
|
|
if depth == 0 || Bool.random(using: &rng) {
|
|
// One leaf in four is a wildcard, so the named-over-wildcard tie-break and
|
|
// the wildcard match path are exercised inside shared groups too.
|
|
if Int.random(in: 0 ..< 4, using: &rng) == 0 {
|
|
return wildcard(min: min, max: max)
|
|
}
|
|
return element(letter(&rng), min: min, max: max)
|
|
}
|
|
let compositor: PureXML.Schema.Compositor = Bool.random(using: &rng) ? .sequence : .choice
|
|
let count = Int.random(in: 1 ... 3, using: &rng)
|
|
// Sometimes make the children a shared group (same id, same structure) to
|
|
// exercise the call/return sharing: build one child and reference it twice.
|
|
if compositor == .sequence, count >= 2, Bool.random(using: &rng) {
|
|
let shared = randomParticle(depth: depth - 1, rng: &rng, nextID: &nextID)
|
|
let id = allocate(&nextID)
|
|
let stamped = withID(shared, id)
|
|
return group(.sequence, [stamped, stamped], min: min, max: max)
|
|
}
|
|
let children = (0 ..< count).map { _ in randomParticle(depth: depth - 1, rng: &rng, nextID: &nextID) }
|
|
// Three groups in four are a named-group reference (a unique id, so a single
|
|
// call into a once-used fragment); the rest are anonymous inline groups.
|
|
let id = Int.random(in: 0 ..< 4, using: &rng) == 0 ? nil : allocate(&nextID)
|
|
return group(compositor, children, min: min, max: max, id: id)
|
|
}
|
|
|
|
private func allocate(_ nextID: inout Int) -> Int {
|
|
defer { nextID += 1 }
|
|
return nextID
|
|
}
|
|
|
|
private func withID(_ particle: PureXML.Schema.Particle, _ id: Int) -> PureXML.Schema.Particle {
|
|
guard case let .group(inner) = particle.term else { return particle }
|
|
var stamped = inner
|
|
stamped.definitionID = id
|
|
return .init(occurrenceRange: particle.occurrenceRange, term: .group(stamped))
|
|
}
|
|
|
|
/// One letter from the three-symbol alphabet, without a force unwrap.
|
|
private func letter(_ rng: inout SeededRNG) -> String {
|
|
["a", "b", "c"][Int.random(in: 0 ..< 3, using: &rng)]
|
|
}
|
|
}
|
|
|
|
/// A tiny deterministic RNG so the fuzz is reproducible.
|
|
private struct SeededRNG: RandomNumberGenerator {
|
|
private var state: UInt64
|
|
init(seed: UInt64) {
|
|
state = seed
|
|
}
|
|
|
|
mutating func next() -> UInt64 {
|
|
state = state &* 6_364_136_223_846_793_005 &+ 1_442_695_040_888_963_407
|
|
var mixed = state
|
|
mixed = (mixed ^ (mixed >> 30)) &* 0xBF58_476D_1CE4_E5B9
|
|
mixed = (mixed ^ (mixed >> 27)) &* 0x94D0_49BB_1331_11EB
|
|
return mixed ^ (mixed >> 31)
|
|
}
|
|
}
|