extension PureXML.Schema.XSDParser {
    /// The lookups a simple-type variety walk needs, bundled so the walk's base resolution
    /// is O(1) (the name map) and threadable without a long parameter list.
    struct VarietyLookup {
        let byName: [String: XSDTree]
        let bindings: [String: String]
        let target: String?

        /// Built from a schema element: its global `simpleType` definitions keyed by name
        /// (first declaration wins, matching the prior first-match scan), so the variety
        /// walk looks a base up in O(1) instead of re-scanning the schema's children at
        /// every link of a `restriction` chain (the former O(n^3) on a long, hostile chain).
        init(schema: XSDTree, bindings: [String: String], target: String?) {
            var byName: [String: XSDTree] = [:]
            for child in PureXML.Schema.XSDNode.elementChildren(schema) where PureXML.Schema.XSDNode.localName(child) == "simpleType" {
                if let name = PureXML.Schema.XSDNode.attribute(child, "name"), byName[name] == nil {
                    byName[name] = child
                }
            }
            self.byName = byName
            self.bindings = bindings
            self.target = target
        }
    }

    /// The variety (`"list"`, `"union"`, or nil for atomic/unknown) a `restriction`
    /// derives from: an inline `simpleType` base wins, otherwise the `base` QName.
    /// `cache` memoizes each named type's variety, so a chain is walked once, not per type.
    static func restrictionBaseVariety(_ restriction: XSDTree, _ lookup: VarietyLookup, _ visited: Set<String>, _ cache: inout [String: String?]) -> String? {
        if let inlineBase = PureXML.Schema.XSDNode.firstChild(restriction, named: "simpleType") {
            return simpleTypeVariety(inlineBase, lookup, visited, &cache)
        }
        guard let base = PureXML.Schema.XSDNode.attribute(restriction, "base") else { return nil }
        return namedTypeVariety(base, lookup, visited, &cache)
    }

    private static func simpleTypeVariety(_ simpleType: XSDTree, _ lookup: VarietyLookup, _ visited: Set<String>, _ cache: inout [String: String?]) -> String? {
        if PureXML.Schema.XSDNode.firstChild(simpleType, named: "list") != nil {
            return "list"
        }
        if PureXML.Schema.XSDNode.firstChild(simpleType, named: "union") != nil {
            return "union"
        }
        if let restriction = PureXML.Schema.XSDNode.firstChild(simpleType, named: "restriction") {
            return restrictionBaseVariety(restriction, lookup, visited, &cache)
        }
        return nil
    }

    /// The variety of a named base, resolved namespace-aware so a same-local-name
    /// collision never flips the variety: a base in the XSD namespace is a built-in
    /// (only the list datatypes are list-variety; the rest atomic, nil); a base in
    /// the schema's own target namespace resolves to a declared global `simpleType`
    /// (cycle-guarded); a base in any other namespace is external and skipped (nil).
    private static func namedTypeVariety(_ base: String, _ lookup: VarietyLookup, _ visited: Set<String>, _ cache: inout [String: String?]) -> String? {
        let (prefix, local) = splitQName(base)
        let uri = prefix.map { lookup.bindings[$0] } ?? lookup.bindings[""]
        if uri == xsdNamespace {
            return builtinListTypes.contains(local) ? "list" : nil
        }
        if let cached = cache[local] {
            return cached
        }
        guard uri == lookup.target, !visited.contains(local), let declared = lookup.byName[local] else { return nil }
        let variety = simpleTypeVariety(declared, lookup, visited.union([local]), &cache)
        cache[local] = variety
        return variety
    }
}