Module dfa 

Deterministic finite automaton for content-model matching.

Built once at schema-compile time from a ContentModel. At validation time the validator just walks the DFA: O(1) state lookup per child element instead of tree-walking the particle list.

Coverage

Sequence, choice, single elements, nested groups (flattened in), and wildcards all compile to DFA transitions. xs:all does not — its semantics (each particle in any order) require either subset construction (worst-case 2ⁿ states) or runtime bitset tracking. We keep the existing particle-walk matcher for all-groups; the DFA path is opt-in per ComplexType via ContentMatcher.

Determinism

XSD §3.8.6 requires content models to satisfy Unique Particle Attribution: each child must match at most one particle without lookahead. This means the resulting state machine is naturally deterministic. The compiler enforces UPA — any duplicate transition out of the same state is a compile error.

Substitution groups

When a transition matches an element with substitutes, the substitutes are pre-expanded into separate transitions. Lookup at validation time stays a linear scan (small N typical), no per-validate substitution-group lookup needed.

Structs

Dfa

DfaState

ElementTransition

WildcardTransition

Enums

ContentMatcher

What a ComplexType uses to validate its content at runtime. The Builder picks one based on the content-model shape.

DfaTransition

Functions

build_matcher

build_matcher_with_target_ns

Type Aliases

StateId