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.
221 lines
11 KiB
Swift
221 lines
11 KiB
Swift
import Foundation
|
|
import Testing
|
|
@testable import PureXML
|
|
|
|
/// A generated-schema differential for the Unique Particle Attribution (content-model
|
|
/// determinism) check against libxml2 (`xmllint --schema`), the reference. The XSTS
|
|
/// corpus is finite and did not exercise the multiply-referenced-group overlap that was
|
|
/// a real determinism gap; this fuzzes content models, elements, group references,
|
|
/// choices, sequences, `all` groups, occurrences, and wildcards, and flags every schema
|
|
/// where PureXML's determinism accept/reject verdict disagrees with libxml2's.
|
|
///
|
|
/// Opt-in (needs `/usr/bin/xmllint`, set `DETERMINISM_DIFF=1`); never runs in plain
|
|
/// `swift test` or CI. A PureXML-rejects / libxml2-accepts determinism disagreement is a
|
|
/// FALSE POSITIVE (the cardinal-rule blocker); a PureXML-accepts / libxml2-rejects is a
|
|
/// false negative to triage. Non-determinism rejections are skipped so the comparison
|
|
/// isolates the UPA check.
|
|
///
|
|
/// The test asserts only the cardinal rule (zero false positives); it found zero over
|
|
/// this generator, the same shape space that earlier hid the multiply-referenced-group
|
|
/// overlap (now fixed). The false negatives it surfaces are NAMED here rather than left
|
|
/// silent, and triaged genuine vs contested:
|
|
/// - FIXED: a repeating model whose optional trailing particle and leading particle share
|
|
/// a name, `(c, b?, c?)*`. Distinct particles that both match at the loop point; the
|
|
/// sequence now carries each end-item's internal suffix in `lastFollow` so the loop edge
|
|
/// forms the combined `{trailing, leading}` followpos (`DeterminismSequenceFollowposTests`).
|
|
/// - GENUINE but unfixed (a fundamental compositional limitation): the SAME shape through
|
|
/// two references to ONE group in a repeating sequence (`(g+, c, g?)+`). The trailing
|
|
/// and looped occurrences share the cached group identity, so the loop fold's
|
|
/// non-flagging dedupe cannot tell them from a single particle looping (`(a*)*`) without
|
|
/// over-rejecting; distinguishing them needs per-occurrence tracking the summarize-once
|
|
/// design omits.
|
|
/// - CONTESTED, libxml2 the stricter party: an UNUSED group definition with an ambiguous
|
|
/// model (`all(b, b)`) (XSD's UPA constrains the effective content type of complex
|
|
/// types, and an unreferenced group is never one), and `(a?)+`, a nullable body
|
|
/// repeated (one particle, so unambiguous by particle uniqueness; libxml2 rejects the
|
|
/// epsilon loop). PureXML is arguably the more-correct, lenient party on both.
|
|
@Suite("Determinism differential vs libxml2 (opt-in via DETERMINISM_DIFF)")
|
|
struct DeterminismDifferentialTests {
|
|
private var enabled: Bool {
|
|
ProcessInfo.processInfo.environment["DETERMINISM_DIFF"] != nil
|
|
}
|
|
|
|
private var xmllint: String? {
|
|
let path = ProcessInfo.processInfo.environment["XMLLINT"].flatMap { $0.isEmpty ? nil : $0 } ?? "/usr/bin/xmllint"
|
|
return FileManager.default.isExecutableFile(atPath: path) ? path : nil
|
|
}
|
|
|
|
/// Each side's determinism-relevant verdict: accepts the schema, rejects it
|
|
/// specifically for non-determinism, or rejects it for some other reason (skipped).
|
|
private enum Verdict: Equatable { case accepts, notDeterminist, otherReject }
|
|
|
|
private func pureXMLVerdict(_ source: String) -> Verdict {
|
|
do {
|
|
_ = try PureXML.Schema.Document(source)
|
|
return .accepts
|
|
} catch {
|
|
return "\(error)".contains("ambiguous content model") ? .notDeterminist : .otherReject
|
|
}
|
|
}
|
|
|
|
private func libxml2Verdict(_ source: String, xmllint: String) -> Verdict? {
|
|
// WASI has no subprocess, so the libxml2 oracle is unavailable there. The whole
|
|
// differential is opt-in and a host-only tool, so stand down to nil (the test is
|
|
// a no-op on WASI); guarding here keeps the file compiling without `Process`.
|
|
#if os(WASI)
|
|
return nil
|
|
#else
|
|
let directory = NSTemporaryDirectory()
|
|
let file = directory + "det-diff-\(abs(source.hashValue)).xsd"
|
|
guard (try? source.write(toFile: file, atomically: true, encoding: .utf8)) != nil else { return nil }
|
|
defer { try? FileManager.default.removeItem(atPath: file) }
|
|
let process = Process()
|
|
process.executableURL = URL(fileURLWithPath: xmllint)
|
|
process.arguments = ["--noout", "--schema", file, file]
|
|
let pipe = Pipe()
|
|
process.standardError = pipe
|
|
process.standardOutput = pipe
|
|
guard (try? process.run()) != nil else { return nil }
|
|
let data = pipe.fileHandleForReading.readDataToEndOfFile()
|
|
process.waitUntilExit()
|
|
let output = String(decoding: data, as: UTF8.self)
|
|
if process.terminationStatus == 0 {
|
|
return .accepts
|
|
}
|
|
return output.contains("not determinist") ? .notDeterminist : .otherReject
|
|
#endif
|
|
}
|
|
|
|
@Test("PureXML's UPA verdict agrees with libxml2 over generated content models")
|
|
func test_determinismDifferential() {
|
|
guard enabled, let xmllint else { return }
|
|
let seed = ProcessInfo.processInfo.environment["DIFF_SEED"].flatMap { UInt64($0) } ?? 0xDE7E_5A11_C0DE_F00D
|
|
var generator = DeterminismSchemaGenerator(seed: seed)
|
|
var falsePositives: [String] = []
|
|
var falseNegatives: [String] = []
|
|
var compared = 0
|
|
for _ in 0 ..< 5000 {
|
|
let source = generator.schema()
|
|
let pureXML = pureXMLVerdict(source)
|
|
guard let reference = libxml2Verdict(source, xmllint: xmllint) else { continue }
|
|
// Only the determinism dimension: skip when either side rejects for an
|
|
// unrelated reason (a structural error the other may or may not share).
|
|
if pureXML == .otherReject || reference == .otherReject {
|
|
continue
|
|
}
|
|
compared += 1
|
|
if pureXML == .notDeterminist, reference == .accepts {
|
|
if falsePositives.count < 20 {
|
|
falsePositives.append(source)
|
|
}
|
|
} else if pureXML == .accepts, reference == .notDeterminist {
|
|
if falseNegatives.count < 20 {
|
|
falseNegatives.append(source)
|
|
}
|
|
}
|
|
}
|
|
let report = "compared \(compared) schemas; false positives \(falsePositives.count), false negatives \(falseNegatives.count)"
|
|
FileHandle.standardError.write(Data("determinism-diff: \(report)\n".utf8))
|
|
try? (falsePositives + ["--- false negatives ---"] + falseNegatives).joined(separator: "\n\n")
|
|
.write(toFile: NSTemporaryDirectory() + "determinism-diff.txt", atomically: true, encoding: .utf8)
|
|
// The cardinal rule: PureXML must never reject (as ambiguous) a content model
|
|
// libxml2 accepts. False negatives are reported for triage, not asserted to 0
|
|
// (libxml2 can be lenient on contested shapes).
|
|
#expect(falsePositives.isEmpty, "\(falsePositives.count) determinism false positives (see \(NSTemporaryDirectory())determinism-diff.txt): \(falsePositives.first ?? "")")
|
|
}
|
|
}
|
|
|
|
/// Generates well-formed XSD schemas whose only open question is content-model
|
|
/// determinism: a small element alphabet (so two particles often share a name), group
|
|
/// definitions referenced more than once, choices and sequences and element-only `all`
|
|
/// groups, optional/repeated occurrences (the overlap-prone shapes), and `##any`
|
|
/// wildcards. Kept structurally valid so a rejection is a determinism rejection, not a
|
|
/// schema error.
|
|
private struct DeterminismSchemaGenerator {
|
|
private var rng: GeneratorRNG
|
|
private var groupNames: [String] = []
|
|
|
|
init(seed: UInt64) {
|
|
rng = GeneratorRNG(seed: seed)
|
|
}
|
|
|
|
private mutating func pick<T>(_ options: [T]) -> T {
|
|
options[Int.random(in: 0 ..< options.count, using: &rng)]
|
|
}
|
|
|
|
private mutating func chance(_ bound: Int) -> Bool {
|
|
Int.random(in: 0 ..< bound, using: &rng) == 0
|
|
}
|
|
|
|
private mutating func occurrence() -> String {
|
|
switch Int.random(in: 0 ..< 5, using: &rng) {
|
|
case 0: ""
|
|
case 1: " minOccurs=\"0\""
|
|
case 2: " maxOccurs=\"unbounded\""
|
|
case 3: " minOccurs=\"0\" maxOccurs=\"unbounded\""
|
|
default: " minOccurs=\"0\" maxOccurs=\"2\""
|
|
}
|
|
}
|
|
|
|
private mutating func particle(depth: Int) -> String {
|
|
// Leaf: an element of a small alphabet, or a wildcard.
|
|
if depth == 0 || chance(2) {
|
|
if chance(4) {
|
|
return "<xs:any processContents=\"skip\"\(occurrence())/>"
|
|
}
|
|
return "<xs:element name=\"\(pick(["a", "b", "c"]))\" type=\"xs:string\"\(occurrence())/>"
|
|
}
|
|
// A reference to one of the defined groups (the multiply-referenced overlap).
|
|
if !groupNames.isEmpty, chance(2) {
|
|
return "<xs:group ref=\"\(pick(groupNames))\"\(occurrence())/>"
|
|
}
|
|
let compositor = pick(["sequence", "choice", "all"])
|
|
let count = Int.random(in: 1 ... 3, using: &rng)
|
|
// `all` is structurally restricted: element-only members, no occurrence on it or
|
|
// its members beyond 0..1, so keep it simple to avoid a non-determinism error.
|
|
if compositor == "all" {
|
|
let members = (0 ..< count).map { _ in "<xs:element name=\"\(pick(["a", "b", "c"]))\"\(chance(2) ? " minOccurs=\"0\"" : "")/>" }
|
|
return "<xs:all>\(members.joined())</xs:all>"
|
|
}
|
|
let members = (0 ..< count).map { _ in particle(depth: depth - 1) }.joined()
|
|
return "<xs:\(compositor)\(occurrence())>\(members)</xs:\(compositor)>"
|
|
}
|
|
|
|
mutating func schema() -> String {
|
|
groupNames = []
|
|
var groups = ""
|
|
// 0..2 group definitions, each a small content model, referenced from the body.
|
|
for index in 0 ..< Int.random(in: 0 ... 2, using: &rng) {
|
|
let name = "g\(index)"
|
|
groupNames.append(name)
|
|
groups += "<xs:group name=\"\(name)\">\(wrapModel(particle(depth: 1)))</xs:group>"
|
|
}
|
|
let body = wrapModel(particle(depth: 3))
|
|
return "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\">\(groups)"
|
|
+ "<xs:element name=\"doc\"><xs:complexType>\(body)</xs:complexType></xs:element></xs:schema>"
|
|
}
|
|
|
|
/// A group/complexType content model must be a single model group; wrap a bare
|
|
/// element or wildcard (or `all`) in a sequence when it is not already a compositor.
|
|
private func wrapModel(_ particle: String) -> String {
|
|
if particle.hasPrefix("<xs:sequence") || particle.hasPrefix("<xs:choice") || particle.hasPrefix("<xs:all") {
|
|
return particle
|
|
}
|
|
return "<xs:sequence>\(particle)</xs:sequence>"
|
|
}
|
|
}
|
|
|
|
private struct GeneratorRNG: RandomNumberGenerator {
|
|
private var state: UInt64
|
|
init(seed: UInt64) {
|
|
state = seed == 0 ? 0x9E37_79B9_7F4A_7C15 : seed
|
|
}
|
|
|
|
mutating func next() -> UInt64 {
|
|
state ^= state >> 12
|
|
state ^= state << 25
|
|
state ^= state >> 27
|
|
return state &* 0x2545_F491_4F6C_DD1D
|
|
}
|
|
}
|