Mihaela Mihaljevic
380160cc2b
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.
291 lines
14 KiB
Swift
291 lines
14 KiB
Swift
/// The key under which a GSS node is interned during one match: a call's return
|
|
/// state, the caller's saved counters, and the input position at the call. Two
|
|
/// calls sharing all three share a node (the graph-structured-stack sharing).
|
|
private struct ContentRTNGSSKey: Hashable {
|
|
let returnState: Int
|
|
let savedCounters: [Int]
|
|
let position: Int
|
|
}
|
|
|
|
/// One graph-structured-stack node: a saved return context. `parents` are the
|
|
/// caller nodes (a set, so distinct callers sharing a return are merged); `popped`
|
|
/// records that a return has already fired through this node, so a parent added
|
|
/// afterward is served the replayed pop (the GLL completeness detail).
|
|
private struct ContentRTNGSSNode {
|
|
let returnState: Int
|
|
let savedCounters: [Int]
|
|
var parents: Set<Int>
|
|
var popped = false
|
|
}
|
|
|
|
/// A configuration: a program state, the live counter vector, and the GSS node
|
|
/// giving the return context. `gss == 0` is the empty stack. Internal (not private)
|
|
/// because it threads through the matcher's streaming surface, which the content-model
|
|
/// validator drives child by child.
|
|
struct ContentRTNConfiguration: Hashable {
|
|
var state: Int
|
|
var counters: [Int]
|
|
var gss: Int
|
|
}
|
|
|
|
extension PureXML.Schema {
|
|
/// Matches a child-name sequence against a ``ContentRTN`` using a
|
|
/// graph-structured stack, so a multiply-referenced group is traversed without
|
|
/// the inlining matcher's `2^K` state blow-up. Configurations are
|
|
/// `(state, counters, gssNode)`; a `call` saves the caller's counters on a GSS
|
|
/// node and a `return` restores them, so the shared callee fragment does not mix
|
|
/// counter state across its callers. GSS nodes are interned by
|
|
/// `(returnState, savedCounters, position)` with a parent set and a pop flag (the
|
|
/// GLL completeness detail: a parent added after the node was popped replays the
|
|
/// pop), which keeps the active set bounded by the program size, not by the
|
|
/// number of distinct return stacks.
|
|
final class ContentRTNMatcher {
|
|
private let rtn: ContentRTN
|
|
private var nodes: [ContentRTNGSSNode] = []
|
|
private var intern: [ContentRTNGSSKey: Int] = [:]
|
|
private var caps: [Int] = []
|
|
private var position = 0
|
|
/// Configurations produced by replaying a pop to a newly added parent during
|
|
/// closure; drained into the worklist.
|
|
private var pending: [ContentRTNConfiguration] = []
|
|
|
|
/// The matcher's observable resource bound for the last match: the largest live
|
|
/// configuration set across any single closure, and the total graph-structured
|
|
/// stack nodes built. The GSS shares stack suffixes, so on a model with `S` program
|
|
/// states and an input of length `N` both stay `O(S * N)` rather than the
|
|
/// `O(distinct-return-stacks)` an explicit stack grows to (the doubling chain that
|
|
/// gives an explicit stack ~3^depth configurations gives the GSS `O(depth)`).
|
|
/// Exposed so a test can assert the bound by counts, not by wall-clock.
|
|
private(set) var peakLiveConfigurations = 0
|
|
private(set) var gssNodeCount = 0
|
|
|
|
init(_ rtn: ContentRTN) {
|
|
self.rtn = rtn
|
|
}
|
|
|
|
// MARK: Public matching surface (mirrors ContentNFA)
|
|
|
|
func matchesWhole(_ names: [PureXML.Model.QualifiedName]) -> Bool {
|
|
var current = startStates(inputLength: names.count)
|
|
for name in names {
|
|
guard let next = step(current, over: name) else { return false }
|
|
current = next
|
|
}
|
|
return isComplete(current)
|
|
}
|
|
|
|
/// After consuming `names`, the labels the matcher can accept next and whether
|
|
/// the content may legally end here. Composes the streaming surface; mirrors
|
|
/// ``ContentNFA/follow(after:)``, used for completions. Returns an empty,
|
|
/// not-complete result when the prefix is already invalid.
|
|
func follow(after names: [PureXML.Model.QualifiedName]) -> (allowed: [TermLabel], complete: Bool) {
|
|
var current = startStates(inputLength: names.count)
|
|
for name in names {
|
|
guard let next = step(current, over: name) else { return ([], false) }
|
|
current = next
|
|
}
|
|
return (admissible(from: current), isComplete(current))
|
|
}
|
|
|
|
/// The active set before any child: resets this matcher's graph-structured
|
|
/// stack and returns the closure of the start configuration. `inputLength`
|
|
/// sizes the counter saturation caps. Mirrors ``ContentNFA/startStates``, but
|
|
/// is stateful (the GSS lives on the instance), so one matcher drives one
|
|
/// child scan: call this once, then ``step(_:over:)`` per child.
|
|
func startStates(inputLength: Int) -> Set<ContentRTNConfiguration> {
|
|
reset(inputLength: inputLength)
|
|
let seed = ContentRTNConfiguration(state: rtn.start, counters: Array(repeating: 0, count: rtn.counters.count), gss: 0)
|
|
return closure([seed])
|
|
}
|
|
|
|
/// Advances `current` by consuming one element `name`, or nil when `name` is
|
|
/// not admissible there. Mirrors ``ContentNFA/step(_:over:inputLength:)``; must
|
|
/// be called on the active set this matcher last produced (the GSS is stateful).
|
|
func step(_ current: Set<ContentRTNConfiguration>, over name: PureXML.Model.QualifiedName) -> Set<ContentRTNConfiguration>? {
|
|
var next: Set<ContentRTNConfiguration> = []
|
|
for configuration in current {
|
|
let state = configuration.state
|
|
if let label = rtn.states[state].label, let target = rtn.states[state].target, label.matches(name) {
|
|
next.insert(ContentRTNConfiguration(state: target, counters: configuration.counters, gss: configuration.gss))
|
|
}
|
|
}
|
|
if next.isEmpty {
|
|
return nil
|
|
}
|
|
position += 1
|
|
return closure(next)
|
|
}
|
|
|
|
/// The labels admissible from `current`, for diagnostics and completions. The
|
|
/// closure already expands `call` states into the callee's label states, so
|
|
/// this is the same shape as ``ContentNFA/admissible(from:)``: every active
|
|
/// configuration sitting on a labelled transition contributes its label.
|
|
func admissible(from current: Set<ContentRTNConfiguration>) -> [TermLabel] {
|
|
var labels: [TermLabel] = []
|
|
for configuration in current where rtn.states[configuration.state].target != nil {
|
|
if let label = rtn.states[configuration.state].label {
|
|
labels.append(label)
|
|
}
|
|
}
|
|
return labels
|
|
}
|
|
|
|
/// Whether the content may legally end at `current`: an active configuration at
|
|
/// the program accept with the empty stack (input consumed, all calls returned).
|
|
func isComplete(_ current: Set<ContentRTNConfiguration>) -> Bool {
|
|
current.contains { $0.state == rtn.accept && $0.gss == 0 }
|
|
}
|
|
|
|
/// The particle each child matched, in order (nil from the first rejected
|
|
/// child onward), with the inlining matcher's tie-breaking: a named particle
|
|
/// over a wildcard, then the lowest state index.
|
|
///
|
|
/// The lowest-state-index tie-break only distinguishes two same-kind particles
|
|
/// that both accept the child, which is a Unique Particle Attribution violation:
|
|
/// the schema compiler rejects such a model, so no instance is validated against
|
|
/// it. State numbering here differs from `ContentNFA`'s (the added call/return
|
|
/// states), so on such a (rejected) model the two matchers may pick different
|
|
/// competing particles; on a UPA-valid model at most one particle accepts each
|
|
/// child, so the pick, and the type/value metadata returned with it, is identical.
|
|
func matchedParticles(_ names: [PureXML.Model.QualifiedName]) -> [MatchedParticle?] {
|
|
var current = startStates(inputLength: names.count)
|
|
var result: [MatchedParticle?] = []
|
|
for name in names {
|
|
var next: Set<ContentRTNConfiguration> = []
|
|
var namedState: Int?
|
|
var anyState: Int?
|
|
for configuration in current {
|
|
let state = configuration.state
|
|
guard let label = rtn.states[state].label, let target = rtn.states[state].target, label.matches(name) else { continue }
|
|
next.insert(ContentRTNConfiguration(state: target, counters: configuration.counters, gss: configuration.gss))
|
|
if anyState.map({ state < $0 }) ?? true {
|
|
anyState = state
|
|
}
|
|
if case .name = label, namedState.map({ state < $0 }) ?? true {
|
|
namedState = state
|
|
}
|
|
}
|
|
guard let chosenState = namedState ?? anyState, !next.isEmpty else {
|
|
result.append(contentsOf: Array(repeating: nil, count: names.count - result.count))
|
|
return result
|
|
}
|
|
let matched = rtn.states[chosenState]
|
|
if case let .wildcard(wildcard) = matched.label {
|
|
result.append(.wildcard(wildcard))
|
|
} else {
|
|
result.append(.element(type: matched.elementType, valueConstraint: matched.valueConstraint))
|
|
}
|
|
position += 1
|
|
current = closure(next)
|
|
}
|
|
return result
|
|
}
|
|
|
|
// MARK: Simulation
|
|
|
|
private func reset(inputLength: Int) {
|
|
nodes = [ContentRTNGSSNode(returnState: -1, savedCounters: [], parents: [])] // node 0 = empty stack
|
|
intern = [:]
|
|
position = 0
|
|
caps = counterCaps(for: inputLength)
|
|
peakLiveConfigurations = 0
|
|
gssNodeCount = 0
|
|
}
|
|
|
|
private func closure(_ seed: Set<ContentRTNConfiguration>) -> Set<ContentRTNConfiguration> {
|
|
var seen = seed
|
|
var work = Array(seed)
|
|
while true {
|
|
if !pending.isEmpty {
|
|
let configuration = pending.removeLast()
|
|
if seen.insert(configuration).inserted {
|
|
work.append(configuration)
|
|
}
|
|
continue
|
|
}
|
|
guard let configuration = work.popLast() else { break }
|
|
let state = rtn.states[configuration.state]
|
|
for edge in state.epsilon {
|
|
if let nextConfiguration = apply(edge, to: configuration), seen.insert(nextConfiguration).inserted {
|
|
work.append(nextConfiguration)
|
|
}
|
|
}
|
|
for call in state.calls {
|
|
let node = internNode(returnState: call.returnTo, savedCounters: configuration.counters, parent: configuration.gss)
|
|
let nextConfiguration = ContentRTNConfiguration(state: call.calleeStart, counters: configuration.counters, gss: node)
|
|
if seen.insert(nextConfiguration).inserted {
|
|
work.append(nextConfiguration)
|
|
}
|
|
drainPending(into: &seen, work: &work)
|
|
}
|
|
if state.isReturn, configuration.gss != 0 {
|
|
popReturn(configuration.gss)
|
|
drainPending(into: &seen, work: &work)
|
|
}
|
|
}
|
|
peakLiveConfigurations = max(peakLiveConfigurations, seen.count)
|
|
gssNodeCount = nodes.count
|
|
return seen
|
|
}
|
|
|
|
private func drainPending(into seen: inout Set<ContentRTNConfiguration>, work: inout [ContentRTNConfiguration]) {
|
|
while let configuration = pending.popLast() {
|
|
if seen.insert(configuration).inserted {
|
|
work.append(configuration)
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Interns the GSS node for a call returning to `returnState` from the
|
|
/// caller's `savedCounters`, recording `parent`. If the node already exists
|
|
/// and was popped, replay the pop to the newly added parent (GLL).
|
|
private func internNode(returnState: Int, savedCounters: [Int], parent: Int) -> Int {
|
|
let key = ContentRTNGSSKey(returnState: returnState, savedCounters: savedCounters, position: position)
|
|
if let id = intern[key] {
|
|
if nodes[id].parents.insert(parent).inserted, nodes[id].popped {
|
|
pending.append(ContentRTNConfiguration(state: returnState, counters: savedCounters, gss: parent))
|
|
}
|
|
return id
|
|
}
|
|
let id = nodes.count
|
|
nodes.append(ContentRTNGSSNode(returnState: returnState, savedCounters: savedCounters, parents: [parent]))
|
|
intern[key] = id
|
|
return id
|
|
}
|
|
|
|
/// Returns from GSS node `id`: restore its saved counters and continue at its
|
|
/// return state for every parent. Mark it popped so a parent added later is
|
|
/// served too.
|
|
private func popReturn(_ id: Int) {
|
|
nodes[id].popped = true
|
|
let node = nodes[id]
|
|
for parent in node.parents {
|
|
pending.append(ContentRTNConfiguration(state: node.returnState, counters: node.savedCounters, gss: parent))
|
|
}
|
|
}
|
|
|
|
private func apply(_ edge: ContentEpsilonEdge, to configuration: ContentRTNConfiguration) -> ContentRTNConfiguration? {
|
|
for guardCondition in edge.guards where !guardCondition.accepts(configuration.counters) {
|
|
return nil
|
|
}
|
|
var values = configuration.counters
|
|
for action in edge.actions {
|
|
action.apply(to: &values, caps: caps)
|
|
}
|
|
return ContentRTNConfiguration(state: edge.target, counters: values, gss: configuration.gss)
|
|
}
|
|
|
|
private func counterCaps(for inputLength: Int) -> [Int] {
|
|
let reachable = inputLength == Int.max ? Int.max : inputLength + 1
|
|
return rtn.counters.map { scope in
|
|
guard let maximumCap = scope.range.maximum.clamped(to: reachable),
|
|
!scope.range.maximum.isGreaterThan(reachable)
|
|
else {
|
|
return scope.range.minimum.clamped(to: reachable)
|
|
}
|
|
return maximumCap
|
|
}
|
|
}
|
|
}
|
|
}
|