PureXML/Tests/ContentModelDeterminismGroupReferenceTests.swift

import Testing
@testable import PureXML

/// Two references to the same `<xs:group>` are two expanded occurrences for Unique
/// Particle Attribution, so when they overlap (`(g?, g?)`, `(g | g)`) the model is
/// ambiguous, exactly as the inline `(x?, x?)` / `(x | x)` is. The compositional
/// determinism check summarizes a group once and reused its node identity across
/// references, so the distinct-identity overlap test could not see the conflict and
/// PureXML accepted these where libxml2/Xerces reject them. That also let the per-
/// instance content matcher run on a non-UPA model, where a multiply-referenced
/// nullable group is exponential, a keystroke-time hang on an accepted schema. The
/// fix (dedup decision sets by identity, treat a same-identity collision as the
/// conflict) closes the gap and bounds the check.
@Suite("UPA on multiply-referenced group overlap")
struct DeterminismGroupReferenceTests {
    private let header = "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\">"
    private let groupG = "<xs:group name=\"g\"><xs:sequence><xs:element name=\"x\"/></xs:sequence></xs:group>"

    private func accepts(_ body: String) -> Bool {
        (try? PureXML.Schema.Document(header + body + "</xs:schema>")) != nil
    }

    private func model(_ content: String, withGroup: Bool = true) -> String {
        (withGroup ? groupG : "") + "<xs:element name=\"d\"><xs:complexType>\(content)</xs:complexType></xs:element>"
    }

    @Test("two overlapping references to one group are rejected as ambiguous")
    func test_overlappingGroupReferencesRejected() {
        // (g?, g?): a leading element of g matches the first or the second reference.
        #expect(!accepts(model("<xs:sequence><xs:group ref=\"g\" minOccurs=\"0\"/><xs:group ref=\"g\" minOccurs=\"0\"/></xs:sequence>")))
        // (g | g): a leading element of g matches either branch.
        #expect(!accepts(model("<xs:choice><xs:group ref=\"g\"/><xs:group ref=\"g\"/></xs:choice>")))
        // (g*, g): after a run of g, the next could be the repeat or the trailing g.
        #expect(!accepts(model("<xs:sequence><xs:group ref=\"g\" maxOccurs=\"unbounded\"/><xs:group ref=\"g\"/></xs:sequence>")))
    }

    @Test("references to one group that do NOT overlap stay valid (no over-rejection)")
    func test_nonOverlappingGroupReferencesAccepted() {
        // (g, g): a required g then a required g is a deterministic two-element sequence.
        #expect(accepts(model("<xs:sequence><xs:group ref=\"g\"/><xs:group ref=\"g\"/></xs:sequence>")))
        // (g, g*): g then zero-or-more g is g repeated, unambiguous (the a+ shape).
        #expect(accepts(model("<xs:sequence><xs:group ref=\"g\"/><xs:group ref=\"g\" maxOccurs=\"unbounded\"/></xs:sequence>")))
        // A single group reference, repeated, is one particle looping: valid.
        #expect(accepts(model("<xs:sequence><xs:group ref=\"g\" minOccurs=\"0\" maxOccurs=\"unbounded\"/></xs:sequence>")))
    }

    @Test("nested repetition of a single element is not a same-particle conflict")
    func test_nestedSingleElementRepetitionAccepted() {
        // ((a{0,M}){0,M}){0,M}: one element 'a' nested in repetitions is a*, unambiguous.
        // The repeat-edge self-loop must not be read as two occurrences (#192 shape).
        let content = "<xs:sequence maxOccurs=\"100\"><xs:sequence maxOccurs=\"100\">"
            + "<xs:choice maxOccurs=\"100\"><xs:element name=\"a\" maxOccurs=\"100\"/></xs:choice>"
            + "</xs:sequence></xs:sequence>"
        #expect(accepts(model(content, withGroup: false)))
    }

    /// `g0=(g1?,g1?) … g{K-1}=(gK?,gK?), gK=(x?)`: every level optional and referenced
    /// twice. Inlined this is the `2^K` overlap that hung the matcher; the determinism
    /// check now rejects it in work linear in the depth, so no instance is ever matched
    /// against it (the interactive-safety payoff).
    private func optionalDoublingSchema(depth: Int) -> String {
        var parts = [header]
        for level in 0 ..< depth {
            parts.append("<xs:group name=\"g\(level)\"><xs:sequence>"
                + "<xs:group ref=\"g\(level + 1)\" minOccurs=\"0\"/><xs:group ref=\"g\(level + 1)\" minOccurs=\"0\"/>"
                + "</xs:sequence></xs:group>")
        }
        parts.append("<xs:group name=\"g\(depth)\"><xs:sequence><xs:element name=\"x\" minOccurs=\"0\"/></xs:sequence></xs:group>")
        parts.append("<xs:complexType name=\"T\"><xs:sequence><xs:group ref=\"g0\"/></xs:sequence></xs:complexType>")
        parts.append("<xs:element name=\"doc\" type=\"T\"/></xs:schema>")
        return parts.joined()
    }

    // The determinism check is the linear-in-depth rejection's home, but it recurses on
    // nesting depth, so a depth-40 chain overflows WASI's small single-threaded stack
    // (the recursive check/builder depth-safety on WASI is tracked separately). The bound
    // is platform-independent, so this runs on the large-stack hosts (macOS, Linux); the
    // shallow correctness tests above cover the fix on WASI too.
    #if !os(WASI)
        @Test("a deep multiply-referenced nullable group chain is rejected in bounded work", .timeLimit(.minutes(1)))
        func test_deepOptionalDoublingRejectedBounded() {
            // 2^40 inlined occurrences: it must be rejected by the linear-in-depth check,
            // not explored. Reaching this test's end at all is the bound (the time limit
            // turns a regression to the exponential back into a failure, not a hang).
            #expect((try? PureXML.Schema.Document(optionalDoublingSchema(depth: 40))) == nil)
        }
    #endif
}