Mihaela Mihaljevic
fa3552876a
The counted content-model automaton represents its active set as (state, counter-vector) configurations bounded by states times the product of the per-counter saturation caps. An unbounded counter already saturates at its minimum (every higher count is matching-equivalent). A finite maximum the input cannot reach is equivalent: the active set increments a counter at most to its cap, the cap is at most inputLength+1, so when maximum > inputLength+1 the value can never reach maximum, belowMaximum is always satisfied, and every value at or above the minimum is indistinguishable. Saturate such a counter at its minimum too, so a huge but finite maxOccurs on a nested counter no longer multiplies the active set by an inputLength factor per nesting level. A document that did not terminate within a minute against the Z035 worst case (nested sequences/choices with maxOccurs up to 1e11) now validates in linear time. No accept/reject decision changes: the full XSTS suite holds at 0/35/0/26, and an adversarial no-caps reference-matcher differential found no false positive or false negative, including the nullable-body case (where the builder makes canExit unconditional, so the counter value is matching-irrelevant) and the occurrence boundary. Guarded by ContentMatcherWorstCaseTests. Partial: a model with several moderate (input-reachable) maxOccurs nested deeply still enumerates a large active set; the general polynomial bound (a position- indexed DP over the counting automaton) remains under #192.
42 lines
2.2 KiB
Swift
42 lines
2.2 KiB
Swift
import Testing
|
|
@testable import PureXML
|
|
|
|
/// #192 worst-case guard. A content model with nested huge-`maxOccurs` counters (the
|
|
/// Z035-class adversarial shape) must validate a large document in bounded work, not
|
|
/// blow up the active-configuration set. Before effectively-unbounded finite counters
|
|
/// were saturated at their minimum, an 800-child document against this model did not
|
|
/// terminate within a minute (the active set grew like `inputLength` raised to the
|
|
/// nesting depth); it is now linear. The time limit turns a regression back to the
|
|
/// super-linear blowup into a test failure rather than a silent interactive hang.
|
|
///
|
|
/// This covers the huge-`maxOccurs` case (a maximum the input cannot reach). A model
|
|
/// with several MODERATE `maxOccurs` (reachable by the document) nested deeply is not
|
|
/// yet bounded to a small constant and remains tracked in #192.
|
|
@Suite("XSD content-matcher worst case (#192)")
|
|
struct ContentMatcherWorstCaseTests {
|
|
private let hugeMaxOccursModel = """
|
|
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
|
|
<xs:element name="root"><xs:complexType>
|
|
<xs:sequence maxOccurs="100000"><xs:sequence maxOccurs="100000">
|
|
<xs:choice maxOccurs="100000"><xs:element name="a" type="xs:string" maxOccurs="100000"/></xs:choice>
|
|
</xs:sequence></xs:sequence>
|
|
</xs:complexType></xs:element>
|
|
</xs:schema>
|
|
"""
|
|
|
|
#if os(WASI)
|
|
@Test("a huge-maxOccurs nested content model validates a large document in bounded work")
|
|
#else
|
|
@Test("a huge-maxOccurs nested content model validates a large document in bounded work", .timeLimit(.minutes(1)))
|
|
#endif
|
|
func test_hugeMaxOccursBounded() throws {
|
|
let document = try PureXML.Schema.Document(hugeMaxOccursModel)
|
|
let valid = "<root>" + String(repeating: "<a>x</a>", count: 10000) + "</root>"
|
|
#expect(try document.validate(valid).isEmpty)
|
|
// A child the model does not admit is still correctly rejected (the saturation
|
|
// does not widen what is accepted), and that decision is also bounded.
|
|
let invalid = "<root>" + String(repeating: "<a>x</a>", count: 5000) + "<b/></root>"
|
|
#expect(try !document.validate(invalid).isEmpty)
|
|
}
|
|
}
|