extension PureXML.XPath.Evaluator { typealias Node = PureXML.XPath.Node typealias Step = PureXML.XPath.Step typealias NodeTest = PureXML.XPath.NodeTest typealias Axis = PureXML.XPath.Axis typealias Expression = PureXML.XPath.Expression typealias EvaluationContext = PureXML.XPath.EvaluationContext typealias Value = PureXML.XPath.Value typealias PrincipalKind = PureXML.XPath.PrincipalKind /// Walks the steps from a starting node-set, threading each step's result into /// the next. Predicates run with proximity position within each context node's /// axis result. static func evaluateSteps(_ steps: [Step], from start: [Node], _ context: EvaluationContext) throws -> [Node] { var current = start for step in steps { var result: [Node] = [] // Cross-context de-duplication is needed only when two distinct // context nodes can reach the same node. With at most one context, or // on an axis whose results are disjoint per context (child, attribute, // namespace, self), no duplicate can arise, so accumulate directly: // the `Set` path below produces the identical sequence (every insert // succeeds) at the cost of hashing and copying every node. if current.count <= 1 || step.axis.yieldsDisjointResults { for contextNode in current { try result.append(contentsOf: stepNodes(step, from: contextNode, context)) try context.checkBudget(result.count) } } else { var seen: Set = [] for contextNode in current { for node in try stepNodes(step, from: contextNode, context) where seen.insert(node).inserted { result.append(node) } try context.checkBudget(result.count) } } current = result } return current } /// The nodes a single `step` selects from one `contextNode`: the axis nodes /// that pass the node test, then the step's predicates (applied per context, /// as XPath proximity position requires). private static func stepNodes(_ step: Step, from contextNode: Node, _ context: EvaluationContext) throws -> [Node] { let matched = matchedAxisNodes(step, from: contextNode, context) return try applyPredicates(step.predicates, to: matched, context) } /// The axis nodes that pass the step's node test. For the descendant family /// over a tree context the test is fused into the traversal so a node the /// test rejects is never wrapped (and so never retained); every other axis /// builds the axis node list and filters it. private static func matchedAxisNodes(_ step: Step, from contextNode: Node, _ context: EvaluationContext) -> [Node] { if case let .tree(tree) = contextNode { switch step.axis { case .descendant: let keep = compiledTreeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.descendants(of: tree, where: keep) case .descendantOrSelf: let keep = compiledTreeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.descendantsOrSelf(of: tree, where: keep) case .attribute: let keep = compiledAttributeTest(step.test, context.namespaces) return PureXML.XPath.AxisNavigation.attributes(of: tree, where: keep) default: break } } let cache = context.environment.documentNavigation let siblingCache = context.environment.siblingIndex // The following/preceding and following-sibling/preceding-sibling axes // fuse the node test into the walk so a rejected node is never wrapped or // copied out; the other axes build their node list and filter it. switch step.axis { case .following: let keep = compiledNodeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.following(of: contextNode, cache: cache, where: keep) case .preceding: let keep = compiledNodeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.preceding(of: contextNode, cache: cache, where: keep) case .followingSibling: let keep = compiledTreeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.followingSiblings(of: contextNode, siblingCache: siblingCache, where: keep) case .precedingSibling: let keep = compiledTreeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.precedingSiblings(of: contextNode, siblingCache: siblingCache, where: keep) default: let keep = compiledNodeTest(step.test, on: step.axis, context.namespaces) return PureXML.XPath.AxisNavigation.nodes(on: step.axis, from: contextNode, cache: cache).filter(keep) } } /// Filters nodes through each predicate in turn. A numeric predicate is a /// position test; any other is taken as a boolean. static func applyPredicates( _ predicates: [Expression], to nodes: [Node], _ context: EvaluationContext, ) throws -> [Node] { var current = nodes for predicate in predicates { var kept: [Node] = [] let size = current.count for (offset, node) in current.enumerated() { let focused = context.focused(on: node, position: offset + 1, size: size) if try keeps(predicate, focused, position: offset + 1) { kept.append(node) } } current = kept } return current } private static func keeps(_ predicate: Expression, _ context: EvaluationContext, position: Int) throws -> Bool { let value = try eval(predicate, context) if case let .number(number) = value { return Int(number) == position } return value.boolean } // MARK: Node tests static func matches(_ node: Node, _ test: NodeTest, on axis: Axis, namespaces: [String: String] = [:]) -> Bool { if case let .tree(tree) = node { return matchesTree(tree, test, on: axis, namespaces) } // Attribute and namespace nodes: a name or wildcard test selects them // (by the axis's principal kind), `node()` matches anything, and the // kind tests (text/comment/processing-instruction) never match a node // that is not a tree node. switch test { case let .name(name): return nameMatches(node, name, axis.principalKind, namespaces) case .wildcard: return wildcardMatches(node, axis.principalKind) case .node: return true case .text, .comment, .processingInstruction: return false } } /// The node test applied directly to an attribute, the single-node core of /// ``matches`` for an `.attribute` node on the attribute axis (whose /// principal kind is always attribute). Taking the raw ``Attribute`` lets the /// attribute axis test a candidate without wrapping (and so retaining) it, so /// an attribute the test rejects is never materialized. A name test matches /// by qualified name; a wildcard or `node()` matches any attribute; the kind /// tests never match an attribute. static func matchesAttribute(_ attribute: PureXML.Model.Attribute, _ test: NodeTest, _ namespaces: [String: String]) -> Bool { switch test { case let .name(name): qualifiedMatches(attribute.name, name, namespaces) case .wildcard, .node: true case .text, .comment, .processingInstruction: false } } /// Compiles a tree-node test into a per-node predicate, resolving everything /// that is invariant across a traversal (the axis principal kind, whether /// namespace bindings are in effect, the prefix-wildcard shape of the test /// name) exactly once instead of on every node. A descendant walk over a /// wide subtree applies the returned closure tens of thousands of times, so /// hoisting the test's fixed structure out of the per-node path is the bulk /// of the saving. The closure is equivalent to ``matchesTree`` for the same /// arguments, the one source of truth it specializes. static func compiledTreeTest( _ test: NodeTest, on axis: Axis, _ namespaces: [String: String], ) -> (PureXML.Model.TreeNode) -> Bool { switch test { case let .name(name): guard axis.principalKind == .element else { return { _ in false } } // No eval-time bindings and no prefix wildcard: the match is the // plain in-document-string comparison, with no per-node namespace or // suffix work. if namespaces.isEmpty, !name.hasSuffix(":*") { return { tree in tree.kind == .element && tree.name.map { $0.description == name || $0.localName == name } == true } } return { tree in tree.kind == .element && tree.name.map { qualifiedMatches($0, name, namespaces) } == true } case .wildcard: guard axis.principalKind == .element else { return { _ in false } } return { $0.kind == .element } case .text: return { $0.kind == .text || $0.kind == .cdata } case .node: return { _ in true } case .comment: return { $0.kind == .comment } case let .processingInstruction(target): return { tree in tree.kind == .processingInstruction && (target == nil || tree.name?.description == target) } } } /// Compiles an attribute-node test into a per-attribute predicate, hoisting /// the same invariants as ``compiledTreeTest`` (the binding state and the /// prefix-wildcard shape) out of the per-attribute path. Equivalent to /// ``matchesAttribute`` for the same arguments. static func compiledAttributeTest( _ test: NodeTest, _ namespaces: [String: String], ) -> (PureXML.Model.Attribute) -> Bool { switch test { case let .name(name): if namespaces.isEmpty, !name.hasSuffix(":*") { return { $0.name.description == name || $0.name.localName == name } } return { qualifiedMatches($0.name, name, namespaces) } case .wildcard, .node: return { _ in true } case .text, .comment, .processingInstruction: return { _ in false } } } /// Compiles a general node test (any node kind) into a per-node predicate, /// for the axes that build a node list and filter it. A tree node is tested /// by the compiled tree test; an attribute or namespace node keeps the /// ``matches`` behavior. Equivalent to ``matches`` for the same arguments. static func compiledNodeTest( _ test: NodeTest, on axis: Axis, _ namespaces: [String: String], ) -> (Node) -> Bool { let treeTest = compiledTreeTest(test, on: axis, namespaces) switch test { case let .name(name): let kind = axis.principalKind return { node in if case let .tree(tree) = node { return treeTest(tree) } return nameMatches(node, name, kind, namespaces) } case .wildcard: let kind = axis.principalKind return { node in if case let .tree(tree) = node { return treeTest(tree) } return wildcardMatches(node, kind) } case .node: return { _ in true } case .text, .comment, .processingInstruction: return { node in if case let .tree(tree) = node { return treeTest(tree) } return false } } } /// The node test applied directly to a tree node, the single-node core of /// ``matches`` for a `.tree` node. Taking the ``TreeNode`` rather than a /// wrapped ``Node`` lets the descendant traversal test a candidate without /// first wrapping (and so retaining) it, so a node the test rejects is never /// retained. ``matches`` delegates here for every tree node, keeping one /// source of truth. static func matchesTree(_ tree: PureXML.Model.TreeNode, _ test: NodeTest, on axis: Axis, _ namespaces: [String: String]) -> Bool { switch test { case let .name(name): guard axis.principalKind == .element, tree.kind == .element, let qualified = tree.name else { return false } return qualifiedMatches(qualified, name, namespaces) case .wildcard: return axis.principalKind == .element && tree.kind == .element case .text: return tree.kind == .text || tree.kind == .cdata case .node: return true case .comment: return tree.kind == .comment case let .processingInstruction(target): guard tree.kind == .processingInstruction else { return false } return target == nil || tree.name?.description == target } } private static func nameMatches(_ node: Node, _ name: String, _ kind: PrincipalKind, _ namespaces: [String: String]) -> Bool { switch kind { case .element: guard case let .tree(tree) = node, tree.kind == .element, let qualified = tree.name else { return false } return qualifiedMatches(qualified, name, namespaces) case .attribute: guard case let .attribute(_, attribute) = node else { return false } return qualifiedMatches(attribute.name, name, namespaces) case .namespace: guard case let .namespace(_, prefix, _) = node else { return false } return prefix == name } } /// Matches a node's qualified name against a test name. When an eval-time /// prefix binding covers the test's prefix, the match is by namespace URI and /// local name; otherwise it falls back to the in-document prefix string (the /// behavior when no bindings are supplied). private static func qualifiedMatches(_ qualified: PureXML.Model.QualifiedName, _ name: String, _ namespaces: [String: String]) -> Bool { if !namespaces.isEmpty { if let colon = name.firstIndex(of: ":") { let prefix = String(name[.. Bool { switch kind { case .element: return isTreeKind(node, in: [.element]) case .attribute: if case .attribute = node { return true } return false case .namespace: if case .namespace = node { return true } return false } } private static func isTreeKind(_ node: Node, in kinds: [PureXML.Model.TreeNodeKind]) -> Bool { guard case let .tree(tree) = node else { return false } return kinds.contains(tree.kind) } }