Commit Graph

9 Commits

Author SHA1 Message Date
b104723fed
perf(xpath): cache and fuse the following-sibling/preceding-sibling axes (#306)
siblingPosition(of:) located the context node with
parent.children.firstIndex { $0 === tree } on every call: a linear scan of the
parent's child list, independent of the result. Over a wide parent evaluated
from many context siblings (//x/following-sibling::y) that scan was quadratic,
and the axes then materialized every sibling before the node test filtered it.

Look the index up through the shared per-evaluation SiblingIndexCache (O(1)
after the per-parent table is built), and fuse the step's node test into the
walk so a rejected sibling is never wrapped (the same fusion the descendant and
following/preceding axes use). The selected siblings and their order are
unchanged.

The gratuitous per-context scan and the non-match wrapping are gone (the
remaining per-context iteration over the siblings is inherent to the axis); a
wide-parent following-sibling query is ~1.2-1.6x faster. The full suite, the
W3C XPath/XSLT and Apache Xalan corpora, and the WASM build stay green;
SiblingAxisTests pins the fused node test and document order.
2026-06-25 22:41:32 +02:00
ad289b0df1
perf(xpath): cache the document node list for following/preceding axes (#302)
following(of:) and preceding(of:) rebuilt the entire document node list and ran
a linear firstIndex search for the context node on every call. Evaluated over
many context nodes (//x/following::y), that rebuild-and-search was quadratic: a
200-context following:: query over a 20k-element document took ~16s.

Share a per-evaluation DocumentNavigationCache: each document's ordered node
list and a node-to-index map are built once (the document is immutable during
evaluation) and reused, so the position lookup is O(1). following:: also skips
the context's contiguous subtree by index arithmetic (start = index + 1 +
descendant count) instead of scanning the tail and filtering every descendant
out. The selected nodes and their document order are unchanged.

The 200-context query drops ~16s to ~9s; the residual is the produced
node-set's own size (materialization), which is inherent to the axis. The full
suite, the W3C XPath/XSLT and Apache Xalan corpora, and the WASM build stay
green; FollowingPrecedingAxisTests pins the subtree skip, ancestor exclusion,
and the shared-cache multi-context path.
2026-06-25 20:03:45 +02:00
68f6680a66
perf(xpath): share focus-independent state through an Environment reference (#288)
An EvaluationContext carried the variable bindings, the function library, the
namespace bindings, and the budget by value. Re-focusing the context onto each
node of a node-set (focused(on:position:size:), called once per node when a
predicate is applied) copied all three dictionaries every time, even though
none of them changes as the focus moves.

Bundle the focus-independent state in an Environment reference type. The
context now holds the node, position, size, and an Environment reference;
re-focusing copies the three integers and shares the environment by reference
instead of copying and reference-counting three dictionaries. The values and
behavior are identical.

Measured xpath ~16% faster on the 20k-item generated corpus via a same-state
A/B (count unchanged at 10000). The full XPath suite, the Apache Xalan XSLT
gold-output corpus, and the WASM build stay green.
2026-06-25 08:52:28 +02:00
ac85dd36de feat(xpath,xslt,wasm): evaluation budget, tailored collation, WASI runtime proof
PureXML.XPath.Budget is the configurable counterpart of libxml2's
fixed 10M node-set cap (libxml2Compatible preset included), thrown as
a located QueryError instead of a silent refusal, default unbounded.
xsl:sort honors lang with tailored alphabet orders for Polish and
Russian derived from the conformance golds, case-folded. The WASM
gate executes all 985 tests under wasmtime on an actual WASI runtime,
wired into CI; the first run caught a real wasm32 trap (Int is 32
bits there, so format-number's digit extraction trapped at 2^31
despite the 2^53 guard; internals are now Int64 and the xsl:number
bound is platform-correct). Xalan baseline 127 -> 125. Closes #143,
closes #144.
2026-06-11 06:26:13 +02:00
3d26db555f docs(xpath): note the strict unprefixed name-test rule on bindings 2026-06-10 15:03:19 +02:00
69678d31a1 feat(xpath): EXSLT common, math, and sets extension functions
Add the EXSLT common/math/sets modules, dispatched by resolving a function's
prefix to its namespace (FunctionTable.call falls back to namespace lookup),
so any prefix bound to an EXSLT namespace works. math:min/max/highest/lowest/
abs/sqrt (with the NaN rule), set:distinct/difference/intersection/
has-same-node/leading/trailing (by node identity and document order), and
exsl:object-type. math:power and the transcendentals are omitted (they need a
C math library the Foundation-free target excludes); exsl:node-set awaits
result-tree-fragment support.

Part of #105 (Tier 3)
2026-06-09 18:31:50 +02:00
2a77b56d2f feat(xpath): eval-time namespace context and XPointer xmlns()/xpath1() schemes
- Eval-time prefix bindings: Query.evaluate(over:namespaces:) and
  value(at:...:namespaces:) supply prefix to URI bindings, so a name test
  like q:item resolves q to a URI and matches by namespace regardless of
  the document's own prefix. The match is namespace-aware only when
  bindings are present, so existing unprefixed/prefix-string queries are
  unchanged.
- XPointer schemes: xpath1() evaluates an XPath expression (like
  xpointer()), and xmlns(p=uri) binds a prefix for the expression parts
  that follow it, threaded into the XPath evaluation.

The range() scheme (and so XInclude range inclusion) remains.

Part of #88
2026-06-08 16:00:15 +02:00
1286659c62 feat(xslt): add xsl:key/key(), format-number(), xsl:number, and document()
Reach full XSLT 1.0 key, numbering, and document parity:

- xsl:key declarations are compiled into an index over the source tree;
  the key() function looks nodes up by key name and value.
- format-number() renders a number against a picture string (digit places,
  decimal point, grouping, percent), Foundation-free.
- xsl:number generates the context node's position rendered as arabic,
  alphabetic, or roman numerals.
- document() resolves an external source through an injected loader so the
  transform never reaches the filesystem or network by default.

These hang off an XPath function-table injection mechanism: the evaluator
merges an engine-supplied FunctionTable, letting XSLT register current(),
key(), format-number(), and document() per evaluation.

Closes #63
2026-06-08 08:01:17 +02:00
d83e5a88ce feat(xpath): expression engine and the four-type model
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
2026-06-08 05:33:13 +02:00