The attribute axis built an XPath node for every attribute of the element
and then filtered by the step's node test. A predicate like [@name='value']
runs that per matched element, so for a wide document it wrapped many
attributes only to discard all but one, and each wrap retains the owner
element and copies the attribute's qualified name and value.
Apply the same fusion the descendant axes use: test the raw attribute during
the walk and wrap only the ones that pass. matches delegates, for an
attribute node, to a new matchesAttribute (the attribute axis always carries
the attribute principal kind, so the reduction is exact), and the attribute
walk applies it as a keep filter. The node-set, declaration order, and
uniqueness are identical to build-then-filter.
Measured xpath ~20% faster on the 20k-item generated corpus via a same-state
A/B (count unchanged at 10000); xpath is now ~2x libxml2, down from ~13x at
the start of this work. XPathFusedAttributeTests covers every node-test kind
through the fused path, and an adversarial equivalence review found no query
whose result changes. Full suite, Apache Xalan XSLT gold output, and the WASM
build stay green.
The descendant and descendant-or-self axes built the full subtree node list
and then filtered it by the step's node test. For a //name query over a wide
document most of the wrapped nodes were discarded immediately, and each wrap
retains a tree node whose weak parent forces the slow reference-counting path.
Run the node test against the raw tree node during the walk, so a rejected
node is never wrapped. matches(_:_:on:namespaces:) now delegates, for a tree
node, to a new tree-node matchesTree (one source of truth, exercised by the
full XPath suite), and the descendant walk applies it as a keep filter. The
node-set, document order, and uniqueness are identical to build-then-filter;
only non-matching nodes are no longer materialized.
Measured xpath ~11% faster on the 20k-item generated corpus via a same-state
A/B (count unchanged at 10000). XPathFusedDescendantTests covers every
node-test kind through the fused path, and an adversarial equivalence review
found no query whose result changes. Full suite, Apache Xalan XSLT gold
output, and the WASM build stay green.
`descendants(of:)` recursed on wrapped XPath nodes and, at every node, built
a fresh array for that node's subtree and concatenated it
(`result.append(contentsOf: descendants(of: child))`). That is an array
allocation and copy per node, roughly O(n x depth) work over the subtree, and
the parse profile showed it dominating XPath evaluation for a `//`-style query
over a wide document.
Recurse on the raw tree node instead, appending into one shared inout
accumulator. The result is the identical node-set in the identical document
order; only the way the array is built changes, from O(n x depth) to O(n).
Measured xpath ~46% faster on the 20k-item generated corpus via a same-state
A/B (count unchanged at 10000). Full suite, the Apache Xalan XSLT gold-output
corpus, and the WASM build stay green.
The following and preceding axes work from attribute and namespace
starts, anchored at the owner element per XPath 1.0 document order:
an attribute follows its element, precedes the element's children,
and has no descendants of its own. Xalan baseline 182 -> 174
(axes 16 -> 8).
Rebuild the XPath engine on the parent-aware tree. Add an XPath node
abstraction (tree, attribute, namespace) with document order, and navigate
all thirteen axes: child, descendant, parent, ancestor, following-sibling,
preceding-sibling, following, preceding, attribute, namespace, self,
descendant-or-self, ancestor-or-self. Support the ./../@/// abbreviations
and processing-instruction() node tests. Reverse axes number nearest-first
for positional predicates; results return de-duplicated in document order.
The attribute axis excludes xmlns declarations; the namespace axis surfaces
in-scope namespace nodes.
Closes#40
