PureXML/Sources/Schema/ContentModelDeterminismCompositional.swift

/// One distinct particle occurrence in a content model: its source-node identity
/// and label. A particle never conflicts with a repetition of itself, so identity,
/// not label alone, decides conflict (per the UPA semantics). Module-internal so the
/// conflict tests (``CompConflict``) can live in their own file.
struct CompItem: Hashable {
    let particle: ObjectIdentifier
    let label: PureXML.Schema.TermLabel

    static func == (lhs: CompItem, rhs: CompItem) -> Bool {
        lhs.particle == rhs.particle
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(particle)
    }
}

/// The context-independent summary of a sub-model: nullability, the items that can
/// start it (`first`), and, for each item that can END it, the items that follow
/// that end-item INTERNALLY (`followlast`, e.g. the loop-back of a repetition or
/// the cross-edges of an `all`). The parent forms a gap's decision set by combining
/// a child's `followlast` with the first of what comes next.
private struct CompSummary {
    var nullable: Bool
    var first: [CompItem]
    /// Each end-item paired with its internal follow set.
    var lastFollow: [(item: CompItem, follow: [CompItem])]
}

extension PureXML.Schema {
    /// A compositional Unique Particle Attribution (1-unambiguity) check that does
    /// NOT inline `<xs:group ref>`: each group is summarized once, so a
    /// multiply-referenced nested group cannot blow up to `2^K` positions (which is
    /// why the former inlining Glushkov automaton needed a `positionCap` skip).
    /// Cross-boundary decision sets are formed at each reference site, so two
    /// reference contexts never merge (that merge would be a false positive).
    ///
    /// This is the authoritative determinism check (`ContentModelDeterminism`
    /// delegates to it). It was proven verdict-equivalent to the prior inlining
    /// automaton by a differential over the whole XSTS corpus (zero divergences)
    /// before replacing it. See docs/design/counted-content-automaton.md.
    enum CompositionalDeterminism {
        /// A UPA-violation message for the content model formed by `models` in
        /// sequence (a complexContent extension's effective content), or nil.
        static func violation(_ models: [XSDTree], _ bindings: [String: String], _ context: XSDContext) -> String? {
            var walk = CompWalk(bindings: bindings, context: context)
            // Dedupe the effective-model nodes by identity. A redefine self-extension
            // (`<extension base="T">` inside the redefinition of `T`) resolves its base to
            // the redefinition itself, so `effectiveModelNodes` lists this type's own
            // content twice: an assembly artifact, not two real occurrences. Counting the
            // same node once keeps the genuine two-reference detection (a group referenced
            // twice WITHIN a model) while not inventing a conflict from the duplication
            // (addB094, schZ007).
            var seenModel: Set<ObjectIdentifier> = []
            let uniqueModels = models.filter { seenModel.insert(ObjectIdentifier($0)).inserted }
            // Summarize every reachable group up front, in dependency order, so the walk
            // below never recurses through a `<group ref>` chain (which is flat in the
            // document and so unbounded by `maxDepth`); see `precomputeGroupSummaries`.
            walk.precomputeGroupSummaries(uniqueModels)
            let summary = walk.sequence(uniqueModels.map { walk.summarize($0, visiting: []) })
            // The root's entry decision set, plus the followpos of each item that can
            // end the whole model (nothing follows the root, so its followpos is just
            // its internal follow).
            walk.emit(summary.first)
            for entry in summary.lastFollow {
                walk.emit(entry.follow)
            }
            // A same-particle collision (two references to one group) found during the
            // walk, then the distinct-identity, same-label overlaps.
            if let conflict = walk.identityConflict {
                return "ambiguous content model: '\(conflict)' can be matched by more than one particle"
            }
            for set in walk.decisionSets {
                if let conflict = CompConflict.overlap(set) {
                    return "ambiguous content model: '\(conflict)' can be matched by more than one particle"
                }
            }
            return nil
        }
    }
}

/// The mutable walk state, so the recursive helpers take few parameters and the
/// group cache / decision-set accumulator are threaded without inout chains.
private struct CompWalk {
    let bindings: [String: String]
    let context: PureXML.Schema.XSDContext
    var decisionSets: [[CompItem]] = []
    var groupCache: [String: CompSummary] = [:]
    /// A conflict label found because the SAME particle reaches one decision point from
    /// two distinct contributions. A `<xs:group ref>` is summarized once and its items
    /// reuse the group's node identity across references, so two references to the same
    /// group (the `(g?, g?)` / `(g | g)` overlap) would otherwise be invisible to the
    /// distinct-identity `overlap` check, even though XSD expands each reference into a
    /// separate occurrence. Detecting the collision here both reports that conflict and,
    /// because the merge dedupes, keeps a multiply-referenced nullable group's first and
    /// follow sets `O(labels)` instead of `2^K`.
    var identityConflict: String?

    mutating func emit(_ set: [CompItem]) {
        if set.count > 1 {
            decisionSets.append(set)
        }
    }

    /// Dedupe a decision set (first set or follow set) by particle identity. A repeated
    /// identity means the same particle reaches this point from two contributions, which
    /// XSD treats as two expanded occurrences: record it as a conflict. The deduped set
    /// is still handed to `overlap` for the distinct-identity, same-label case.
    mutating func merge(_ lists: [CompItem]...) -> [CompItem] {
        mergeList(lists)
    }

    mutating func mergeList(_ lists: [[CompItem]]) -> [CompItem] {
        var seen: Set<ObjectIdentifier> = []
        var result: [CompItem] = []
        for item in lists.joined() {
            if seen.insert(item.particle).inserted {
                result.append(item)
            } else if identityConflict == nil {
                identityConflict = labelName(item.label)
            }
        }
        return result
    }

    /// Dedupe by particle identity WITHOUT flagging a conflict, for combinations where a
    /// repeated identity is one particle looping back on itself, not two occurrences: a
    /// repetition's loop edge (`a*`, and nesting like `(a*)*`) folds the body's first
    /// into its own follow, which is legitimate. Only combinations of DISTINCT child
    /// particles (first sets, sequence gaps, `all` cross-follows) use the flagging merge.
    func dedupOnly(_ lists: [[CompItem]]) -> [CompItem] {
        var seen: Set<ObjectIdentifier> = []
        var result: [CompItem] = []
        for item in lists.joined() where seen.insert(item.particle).inserted {
            result.append(item)
        }
        return result
    }

    /// Dedupe `lastFollow` end-items by particle, unioning their follow sets, so a
    /// multiply-referenced nullable group does not double the carried follow list at
    /// every level. End-item identity collision is not itself a conflict (the overlap of
    /// the two references is decided where they START, in a merged first set), so this
    /// does not flag `identityConflict`.
    mutating func mergeLastFollow(_ entries: [(item: CompItem, follow: [CompItem])]) -> [(item: CompItem, follow: [CompItem])] {
        var indexByParticle: [ObjectIdentifier: Int] = [:]
        var result: [(item: CompItem, follow: [CompItem])] = []
        for entry in entries {
            if let index = indexByParticle[entry.item.particle] {
                result[index].follow = dedupOnly([result[index].follow, entry.follow])
            } else {
                indexByParticle[entry.item.particle] = result.count
                result.append((entry.item, dedupOnly([entry.follow])))
            }
        }
        return result
    }

    private func labelName(_ label: PureXML.Schema.TermLabel) -> String {
        if case let .name(qname) = label {
            return qname.localName
        }
        return "any"
    }

    mutating func summarize(_ node: PureXML.Model.TreeNode, visiting: Set<String>) -> CompSummary {
        let (minimum, maximum) = PureXML.Schema.XSDNode.occurrence(node)
        if let maximum, maximum <= 0 {
            return CompSummary(nullable: true, first: [], lastFollow: [])
        }
        var body = bodySummary(node, visiting: visiting)
        // A repeat edge folds the body's first into every end-item's follow. Kept in a
        // separate method, not inline: `summarize` recurses on nesting depth, so any
        // locals it holds multiply the per-level stack frame, and a deep group chain
        // already overflows a small (WASI) stack. The repeat-edge work runs as the
        // recursion unwinds, so its frame is not on the deepest descent path.
        body.lastFollow = withRepeatEdge(body, minimum: minimum, maximum: maximum)
        return CompSummary(nullable: minimum == 0 || body.nullable, first: body.first, lastFollow: body.lastFollow)
    }

    /// Adds the repetition loop edge (`last -> first`) for a true repetition (max
    /// unbounded or `>= 2`, with `min < max`). A fixed `{n,n}` clamps to copies sharing
    /// the body's particle identities (no new conflict); `{0,1}` is optional, not a
    /// repetition. The loop fold uses the non-flagging dedupe: a single particle looping
    /// is not two occurrences.
    private mutating func withRepeatEdge(_ body: CompSummary, minimum: Int, maximum: Int?) -> [(item: CompItem, follow: [CompItem])] {
        guard minimum != maximum, maximum == nil || (maximum ?? 0) > 1 else { return body.lastFollow }
        var looped: [(item: CompItem, follow: [CompItem])] = []
        for entry in body.lastFollow {
            looped.append((entry.item, dedupOnly([entry.follow, body.first])))
        }
        return looped
    }

    private mutating func bodySummary(_ node: PureXML.Model.TreeNode, visiting: Set<String>) -> CompSummary {
        switch PureXML.Schema.XSDNode.localName(node) {
        case "element":
            let item = CompItem(particle: ObjectIdentifier(node), label: .name(elementQName(node)))
            return CompSummary(nullable: false, first: [item], lastFollow: [(item, [])])
        case "any":
            let item = CompItem(particle: ObjectIdentifier(node), label: .wildcard(PureXML.Schema.XSDParser.wildcard(node, context)))
            return CompSummary(nullable: false, first: [item], lastFollow: [(item, [])])
        case "sequence":
            return sequence(children(node, visiting: visiting))
        case "choice":
            return choice(children(node, visiting: visiting))
        case "all":
            return all(children(node, visiting: visiting))
        case "group":
            return group(node, visiting: visiting)
        default:
            return CompSummary(nullable: true, first: [], lastFollow: [])
        }
    }

    private mutating func children(_ node: PureXML.Model.TreeNode, visiting: Set<String>) -> [CompSummary] {
        PureXML.Schema.XSDNode.elementChildren(node)
            .filter { ["element", "sequence", "choice", "all", "group", "any"].contains(PureXML.Schema.XSDNode.localName($0) ?? "") }
            .map { summarize($0, visiting: visiting) }
    }

    /// A `sequence`: at each gap, every item that can end the preceding nullable run
    /// has its internal follow combined with the first of the following nullable run
    /// into one decision set (the real `followpos` of that end-item inside the
    /// sequence). The sequence's own `lastFollow` is its trailing nullable suffix's
    /// end-items, carried up for the parent to combine with whatever follows.
    mutating func sequence(_ parts: [CompSummary]) -> CompSummary {
        // `suffixFirst[index]` is the first of the nullable run starting after `index`,
        // i.e. what can follow an end-item of `parts[index]` WITHIN this sequence.
        var suffixFirst: [[CompItem]] = Array(repeating: [], count: parts.count)
        for index in parts.indices {
            var suffix: [CompItem] = []
            for next in parts[(index + 1)...] {
                suffix.append(contentsOf: next.first)
                if !next.nullable {
                    break
                }
            }
            suffixFirst[index] = suffix
        }
        for index in parts.indices where !suffixFirst[index].isEmpty {
            for entry in parts[index].lastFollow {
                emit(merge(entry.follow, suffixFirst[index]))
            }
        }
        var prefixFirsts: [[CompItem]] = []
        for part in parts {
            prefixFirsts.append(part.first)
            if !part.nullable {
                break
            }
        }
        // Each trailing end-item carries its internal follow PLUS the suffix that follows
        // it inside the sequence. Otherwise an end-item that is also followed internally
        // (an optional element after it) loses that continuation in `lastFollow`, so a
        // parent gap, or an enclosing repetition's loop edge, forms only a partial
        // followpos: a repeating `(c, b?, c?)` would not see that after `b` both the
        // trailing `c` and the looped leading `c` are reachable. The gap loop already
        // flagged the internal followpos, so dedupe without re-flagging here.
        var trailing: [(item: CompItem, follow: [CompItem])] = []
        for index in parts.indices.reversed() {
            for entry in parts[index].lastFollow {
                trailing.append((entry.item, dedupOnly([entry.follow, suffixFirst[index]])))
            }
            if !parts[index].nullable {
                break
            }
        }
        return CompSummary(nullable: parts.allSatisfy(\.nullable), first: mergeList(prefixFirsts), lastFollow: mergeLastFollow(trailing))
    }

    private mutating func choice(_ parts: [CompSummary]) -> CompSummary {
        let first = mergeList(parts.map(\.first))
        emit(first)
        return CompSummary(
            nullable: parts.isEmpty || parts.contains(where: \.nullable),
            first: first,
            lastFollow: mergeLastFollow(parts.flatMap(\.lastFollow)),
        )
    }

    /// `all`: members are order-independent, so each may follow every other. Each
    /// member's end-items therefore follow (internally) every OTHER member's first,
    /// and the union of member firsts is one decision set (the entry). The cross
    /// follow is recorded in `followlast` so a parent gap combines it with the suffix
    /// (mirrors `ContentModelDeterminism.all`).
    private mutating func all(_ parts: [CompSummary]) -> CompSummary {
        let first = mergeList(parts.map(\.first))
        emit(first)
        var lastFollow: [(item: CompItem, follow: [CompItem])] = []
        for (index, part) in parts.enumerated() {
            let others = parts.enumerated().filter { $0.offset != index }.flatMap(\.element.first)
            for entry in part.lastFollow {
                lastFollow.append((entry.item, merge(entry.follow, others)))
            }
        }
        return CompSummary(
            nullable: parts.isEmpty || parts.allSatisfy(\.nullable),
            first: first,
            lastFollow: mergeLastFollow(lastFollow),
        )
    }

    private mutating func group(_ node: PureXML.Model.TreeNode, visiting: Set<String>) -> CompSummary {
        guard let ref = PureXML.Schema.XSDNode.attribute(node, "ref") else { return CompSummary(nullable: true, first: [], lastFollow: []) }
        let name = PureXML.Schema.XSDNode.stripPrefix(ref)
        if visiting.contains(name) {
            return redefineSelfReference(name, visiting: visiting)
        }
        if let cached = groupCache[name] {
            return cached
        }
        guard let definition = context.groups[name], let model = modelChild(definition)
        else { return CompSummary(nullable: true, first: [], lastFollow: []) }
        // Summarize the group once: its internal decision sets are context-independent
        // and emitted here; its cross-boundary follow is formed by each reference site.
        let summary = summarize(model, visiting: visiting.union([name]))
        groupCache[name] = summary
        return summary
    }

    /// A `<group ref>` to the name currently being summarized is a src-redefine
    /// self-reference: in the compiled (instance) content model it expands to the
    /// ORIGINAL group it redefines (XSDParserParticles.groupReferenceParticle), not
    /// to itself. The determinism check must see that same expanded model, else the
    /// original's particles are invisible and a real UPA ambiguity goes unreported
    /// (the redefine chain in XSTS schN10: an inner c-g2 contributes a `c24` that
    /// overlaps the redefinition's own direct `c24`). Expand one level to the base; a
    /// mark stops a redefine CHAIN from re-expanding the same name, so it terminates.
    /// Every item this surfaces is genuinely reachable in the real model, so the
    /// decision sets stay a SUBSET of the true ones: it can catch a real ambiguity,
    /// never invent one (no false positive). A non-redefined recursive reference has
    /// no base, so it still contributes nothing, exactly as before.
    private mutating func redefineSelfReference(_ name: String, visiting: Set<String>) -> CompSummary {
        let empty = CompSummary(nullable: true, first: [], lastFollow: [])
        let mark = "\u{1}redefined:\(name)"
        guard !visiting.contains(mark), context.redefinedGroups.contains(name),
              let base = context.baseGroups[name], let model = modelChild(base)
        else { return empty }
        return summarize(model, visiting: visiting.union([mark]))
    }

    /// The `sequence`/`choice`/`all` model child of a group definition, if any.
    private func modelChild(_ definition: PureXML.Model.TreeNode) -> PureXML.Model.TreeNode? {
        PureXML.Schema.XSDNode.elementChildren(definition)
            .first { ["sequence", "choice", "all"].contains(PureXML.Schema.XSDNode.localName($0) ?? "") }
    }

    // MARK: Helpers (mirror ContentModelDeterminism)

    private func elementQName(_ node: PureXML.Model.TreeNode) -> PureXML.Model.QualifiedName {
        if let ref = PureXML.Schema.XSDNode.attribute(node, "ref") {
            return resolveQName(ref)
        }
        let name = PureXML.Schema.XSDNode.attribute(node, "name") ?? ""
        let form = PureXML.Schema.XSDNode.attribute(node, "form")
        let qualified = form == "qualified" || (form == nil && context.elementFormQualified)
        return PureXML.Model.QualifiedName(localName: name, namespaceURI: qualified ? context.targetNamespace : nil)
    }

    private func resolveQName(_ qname: String) -> PureXML.Model.QualifiedName {
        let parts = qname.split(separator: ":", maxSplits: 1).map(String.init)
        if parts.count == 2 {
            return PureXML.Model.QualifiedName(localName: parts[1], namespaceURI: bindings[parts[0]] ?? parts[0])
        }
        return PureXML.Model.QualifiedName(localName: qname, namespaceURI: bindings[""])
    }

    // MARK: Group summaries (depth-safe precomputation)

    /// Summarizes every group reachable from `models`, in dependency order, into
    /// `groupCache`, so the main walk's `group(_:)` is always a cache hit and
    /// `summarize` never recurses through a `<group ref>` chain. A group reference
    /// chain is FLAT in the schema document (the definitions are siblings, not
    /// nested), so it is NOT bounded by the parser's `maxDepth`; summarizing lazily
    /// through references therefore recursed on the chain length and overflowed the
    /// stack on a long (hostile but legal) chain. Each group's own model nesting is
    /// document structure, so it stays `maxDepth`-bounded. The cached summary is the
    /// SAME object the lazy walk would have produced (a group summary is
    /// context-independent), so this only reorders the work; the decision sets it
    /// emits are identical as a set, and the verdict does not depend on their order.
    mutating func precomputeGroupSummaries(_ models: [PureXML.Model.TreeNode]) {
        for name in GroupDependencyOrder.reachable(from: models, context: context) where groupCache[name] == nil {
            guard let definition = context.groups[name], let model = modelChild(definition) else { continue }
            groupCache[name] = summarize(model, visiting: [name])
        }
    }
}