Sorting a node-set into document order keyed each node by its root path, an
array as long as the node's depth, computed with a per-node ancestor walk.
Ordering the descendants of a deeply-nested document was therefore
O(n log n x depth): `//a` over an 8000-deep document took ~19s through the
reference query path.
The key is now a single O(1) pre-order index from a per-root numbering,
built once per document and shared through the evaluation's navigation
cache, with a band ordering an element before its namespace nodes, its
attribute nodes, and its children. A node-set spanning several documents
(an XSLT document() result) is grouped by root, ranked by first appearance,
so only a foreign node walks its ancestors. `appendSubtree` (the numbering
walk) is now iterative, so it no longer recurses on depth either.
Document order is unchanged: 1786 tests pass, including the XPath, XSLT,
XPointer, and Schematron conformance corpora. `Query.nodes` over a
50000-deep document now orders in a fraction of a second.
An attribute node's document-order key bands by the attribute's index among its
owner's attributes, found with owner.attributes.firstIndex { $0.name == name }.
That linear scan ran for every attribute node, so sorting an element's K
attributes into document order was O(K^2): an 8000-attribute element took ~0.18s
and grew quadratically.
Cache a per-owner attribute-name-to-index map in SiblingIndexCache, built once
on the second lookup (a single lookup still scans), exactly as the sibling-index
cache already does for child positions. The index is the same first-occurrence
position; only its cost changes.
The 8000-attribute sort drops to ~0.01s (~16x) and is now linear. The full
suite, the W3C XPath and Apache Xalan corpora, the C14N suite (which orders
attributes byte-exactly), and the WASM build stay green; AttributeDocumentOrderTests
pins declaration order through the cached sort.
firstInDocumentOrder() computed a document-order key even for a zero- or
one-node set. The key walks a node up to the root, taking its index among each
parent's children, which is a linear scan of a wide parent. string(@x) and
value-of take the string-value of a (usually single) node-set through this
path, so an XSLT transform over a wide flat fan-out rescanned the wide parent
once per extraction, turning the transform quadratic.
For a set of zero or one node the document order is irrelevant: the node is
trivially first. Return it directly without computing the key, the same
count <= 1 early-out sortedByDocumentOrder() already has.
A transform reading a couple of attributes and child values per element over a
20k-element document drops from ~2.3s to ~0.65s (~3.5x). The output is
unchanged: the full suite, the Apache Xalan XSLT gold-output corpus, the W3C
XPath/XSLT/EXSLT tests, and the WASM build stay green, and FirstInDocumentOrderTests
pins the single-node fast path and the multi-node document-first selection.
EventReader.next(), both initializers, and the Event alias are public
(an internal typealias in a split file had been shadowing the public
Parsing.Event); a new PureXMLPublicAPITests target compiles without
testable import so facade gaps fail CI. The large-corpus benchmarks
exposed document-order sorting as quadratic on flat fan-outs; the fix's
first attempt was itself worse (an eager sibling table built per
predicate evaluation), caught by sampling the live run, and replaced
with a lazy table: single-node sets never touch order keys and a
parent's table builds on its second lookup. XPath at 42 MB drops
27.1 s to 1.57 s (190x to 11.7x); at 210 MB PureXML completes in 9.4 s
the query libxml2 refuses at its 10M node-set cap (#143 tracks our
configurable budget). Benchmark harness: size series to 210 MB, CORPUS
mode for real files (NASA, SwissProt measured), SAX stage,
refusal-aware table, NULL-safe C driver. All conformance suites,
Linux, and WASM verified. Closes#142.
Node-set ordering previously recomputed both nodes' root paths on every
precedes comparison (treePath is O(depth x siblings), so sorts were
O(n log n x depth)). Add decorate-sort-undecorate helpers,
sortedByDocumentOrder() and firstInDocumentOrder(), that compute each node's
order key once, and switch the evaluator's order-and-dedup, the EXSLT set
functions, string-value coercion, and NodeFunctions' target lookup to them.
set:leading/trailing also decorate once, reusing the keys for the pivot
filter and the final sort. precedes stays for pairwise use, sharing the
key comparator (Node.ordered). Behavior unchanged, all suites green.
Closes#113
Compile and evaluate full XPath 1.0 expressions, not just location paths.
Add the four-type Value (node-set, boolean, number, string) with the spec's
coercion rules and canonical number formatting, a recursive-descent parser
for the operator grammar (or/and, equality, relational, additive,
multiplicative, unary minus, union) whose grammatical position disambiguates
* and the operator keywords, function calls, variable references, and filter
expressions. Predicates are now arbitrary expressions (a numeric predicate
is a position test). Comparison follows the node-set quantification rules.
Query gains value/number/string/boolean accessors and a $variable binding
map; the core functions last, position, count, not, true, false, boolean,
number, and string ship with it.
Closes#42
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
