Skip to main content

parsec_xpath/
eval.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! Evaluating an XPath expression tree against a document.
5
6use std::borrow::Cow;
7use std::cell::{Cell, RefCell};
8use std::collections::{HashMap, HashSet};
9
10use parsec::{self as html, NodeId};
11
12use crate::index::{CDATA, COMMENT, ELEMENT, PI, TEXT};
13use crate::parser::{Axis, Expr, NodeTest, Op, Step};
14use crate::{Doc, Extensions, Item, Value, XML_NS, XValue};
15
16/// How much work one run may do before it gives up: nodes looked at on
17/// axes and by `lang()`, predicate tests, and nodes and every 16 bytes of
18/// text read for string-values. Some queries are quadratic on any engine
19/// (`//p[following::p]`), and a hostile page can make them run for hours.
20/// A unit takes one to twenty-odd nanoseconds, so this is a few seconds
21/// at most: still over ten times what the slowest query of the benchmark
22/// pages needs.
23pub const WORK_LIMIT: u64 = 1 << 27;
24
25struct Context<'a, 'v> {
26    item: Item,
27    position: usize,
28    size: usize,
29    doc: Doc<'a>,
30    root: NodeId,
31    vars: &'v [(String, XValue)],
32    namespaces: &'v [(String, String)],
33    kept: &'v RefCell<Kept>,
34    ext: &'v dyn Extensions,
35    /// Work done so far, and the most allowed (see [`WORK_LIMIT`]).
36    spent: &'v Cell<u64>,
37    limit: u64,
38    /// Inside a predicate, where the same node can be tested many times.
39    nested: bool,
40}
41
42/// Values of a run's [`Expr::Memo`] expressions, by slot and node key. Only
43/// a number or a yes or no is ever needed from them.
44type Kept = HashMap<(usize, (u32, u32)), Scalar>;
45
46#[derive(Debug, Clone, Copy)]
47enum Scalar {
48    Num(f64),
49    Bool(bool),
50}
51
52type Result<T> = std::result::Result<T, String>;
53
54fn text<'a>(s: String) -> Value<'a> {
55    Value::Str(Cow::Owned(s))
56}
57
58/// Evaluates `expr` with `scope` as the context node.
59pub(crate) fn run<'a>(
60    expr: &Expr,
61    doc: Doc<'a>,
62    scope: NodeId,
63    vars: &[(String, XValue)],
64    namespaces: &[(String, String)],
65    ext: &dyn Extensions,
66    limit: u64,
67) -> Result<Value<'a>> {
68    // `/` is the top of the scope's tree: the document, or for a node
69    // removed from it, the top of what was removed (as lxml has it).
70    let mut root = scope;
71    while let Some(up) = doc.tree.parent(root) {
72        root = up;
73    }
74    if doc.index.order(root) == u32::MAX {
75        return Err(format!(
76            "the top of node {scope}'s tree, node {root}, isn't in the index"
77        ));
78    }
79    let kept = RefCell::default();
80    let spent = Cell::new(0);
81    let ctx = Context {
82        item: Item::Node(scope),
83        position: 1,
84        size: 1,
85        doc,
86        root,
87        vars,
88        namespaces,
89        kept: &kept,
90        ext,
91        spent: &spent,
92        limit,
93        nested: false,
94    };
95    eval(expr, &ctx)
96}
97
98impl<'a> Context<'a, '_> {
99    /// Counts `units` of work, failing once the run has done too much.
100    fn spend(&self, units: usize) -> Result<()> {
101        let spent = self.spent.get().saturating_add(units as u64);
102        self.spent.set(spent);
103        if spent > self.limit {
104            return Err(format!(
105                "the query needs more than {} steps on this document, so it was stopped",
106                self.limit
107            ));
108        }
109        Ok(())
110    }
111
112    /// Counts a string-value's text, which [`Context::spend`] then sees.
113    fn charge_text(&self, bytes: usize) {
114        let units = (bytes / 16) as u64;
115        self.spent.set(self.spent.get().saturating_add(units));
116    }
117
118    fn order(&self, n: NodeId) -> u32 {
119        self.doc.index.order(n)
120    }
121
122    /// Position in document order. An element's attributes come after the
123    /// element and before its children, whose order is higher.
124    fn key(&self, item: &Item) -> (u32, u32) {
125        match item {
126            Item::Node(n) => (self.order(*n), 0),
127            Item::Attr { owner, index, .. } => (self.order(*owner), index + 1),
128        }
129    }
130
131    fn kind(&self, n: NodeId) -> u8 {
132        self.doc.index.kind_at(self.order(n))
133    }
134
135    /// A text, comment or processing instruction node's own text.
136    fn data(&self, n: NodeId) -> &'a str {
137        match self.doc.tree.kind(n) {
138            html::Kind::Text(t) | html::Kind::Cdata(t) | html::Kind::Comment(t) => t,
139            html::Kind::ProcessingInstruction { data, .. } => data,
140            _ => "",
141        }
142    }
143
144    fn string_value(&self, item: &Item) -> Cow<'a, str> {
145        let n = match item {
146            Item::Attr { owner, index, .. } => {
147                return Cow::Borrowed(self.doc.attr_at(*owner, *index).1);
148            }
149            Item::Node(n) => *n,
150        };
151        let index = self.doc.index;
152        let at = self.order(n);
153        match index.kind_at(at) {
154            TEXT | CDATA | COMMENT | PI => {
155                let data = self.data(n);
156                self.charge_text(data.len());
157                Cow::Borrowed(data)
158            }
159            _ => {
160                // Every text node below, read off the index's range.
161                let end = index.end_of(at);
162                self.spent
163                    .set(self.spent.get().saturating_add((end - at) as u64));
164                // Borrowed while there is only one piece, as in `<p>x</p>`.
165                let mut out = Cow::Borrowed("");
166                for j in at + 1..end {
167                    if matches!(index.kind_at(j), TEXT | CDATA) {
168                        let piece = self.data(index.node_at(j));
169                        // What's done with it (compared, searched) is in
170                        // proportion to its length.
171                        self.charge_text(piece.len());
172                        if out.is_empty() {
173                            out = Cow::Borrowed(piece);
174                        } else {
175                            out.to_mut().push_str(piece);
176                        }
177                    }
178                }
179                out
180            }
181        }
182    }
183
184    /// An element's name with its prefix, as written; lowercase in HTML.
185    fn qualified_name(&self, n: NodeId) -> &'a str {
186        self.doc.tree.lower_name(n).unwrap_or("")
187    }
188
189    /// An element's name without an XML prefix.
190    fn tag(&self, n: NodeId) -> Option<&'a str> {
191        let name = self.doc.tree.lower_name(n)?;
192        if self.doc.is_xml() {
193            return Some(name.split_once(':').map_or(name, |(_, local)| local));
194        }
195        Some(name)
196    }
197
198    fn ns_id(&self, n: NodeId) -> u32 {
199        self.doc.names.map_or(0, |names| names.ns_of(n))
200    }
201
202    fn pi_target(&self, n: NodeId) -> Option<&'a str> {
203        match self.doc.tree.kind(n) {
204            html::Kind::ProcessingInstruction { target, .. } => Some(target),
205            _ => None,
206        }
207    }
208
209    /// The name with its prefix, as `name()` gives it.
210    fn name(&self, item: &Item) -> &'a str {
211        match item {
212            Item::Node(n) => match self.pi_target(*n) {
213                Some(target) => target,
214                None => self.qualified_name(*n),
215            },
216            Item::Attr { owner, index, .. } => self.doc.attr_at(*owner, *index).0,
217        }
218    }
219
220    /// The name without its prefix, as `local-name()` gives it.
221    fn local_name(&self, item: &Item) -> &'a str {
222        let name = self.name(item);
223        // In HTML a colon is just part of a name (`fb:like`), as in lxml.
224        match name.split_once(':') {
225            Some((_, local)) if self.doc.is_xml() => local,
226            _ => name,
227        }
228    }
229
230    fn namespace_uri(&self, item: &Item) -> &'a str {
231        let Some(names) = self.doc.names else {
232            return "";
233        };
234        match item {
235            Item::Node(n) => names.uri(names.ns_of(*n)),
236            Item::Attr { ns, .. } => names.uri(*ns),
237        }
238    }
239
240    /// The position of the top of the tree being queried, and one past its
241    /// last node.
242    fn tree_range(&self) -> (u32, u32) {
243        let top = self.order(self.root);
244        (top, self.doc.index.end_of(top))
245    }
246}
247
248/// Stack kept free before recursing, and the size of each extra segment.
249/// The parser caps nesting, but debug builds use large frames and callers
250/// may run on small thread stacks.
251const RED_ZONE: usize = 64 * 1024;
252const GROW: usize = 1024 * 1024;
253
254fn eval<'a>(expr: &Expr, ctx: &Context<'a, '_>) -> Result<Value<'a>> {
255    stacker::maybe_grow(RED_ZONE, GROW, || eval_here(expr, ctx))
256}
257
258fn eval_here<'a>(expr: &Expr, ctx: &Context<'a, '_>) -> Result<Value<'a>> {
259    Ok(match expr {
260        Expr::Literal(s) => text(s.clone()),
261        Expr::Number(n) => Value::Num(*n),
262        Expr::Variable(name) => match ctx.vars.iter().find(|(k, _)| k == name) {
263            Some((_, XValue::Str(s))) => text(s.clone()),
264            Some((_, XValue::Num(n))) => Value::Num(*n),
265            Some((_, XValue::Bool(b))) => Value::Bool(*b),
266            None => return Err(format!("no value given for ${name}")),
267        },
268        Expr::Negate(e) => Value::Num(-number(eval(e, ctx)?, ctx)),
269        Expr::Binary(op, l, r) => binary(*op, l, r, ctx)?,
270        Expr::Union(l, r) => {
271            let (Value::Nodes(mut a), Value::Nodes(b)) = (eval(l, ctx)?, eval(r, ctx)?) else {
272                return Err("both sides of | must be node-sets".into());
273            };
274            a.extend(b);
275            Value::Nodes(in_document_order(a, ctx))
276        }
277        Expr::Call(name, args) => call(name, args, ctx)?,
278        Expr::Memo(e, slot) => {
279            let key = (*slot, ctx.key(&ctx.item));
280            // Not borrowed while evaluating: slots inside `e` fill too.
281            let known = ctx.kept.borrow().get(&key).copied();
282            let scalar = match known {
283                Some(s) => s,
284                None => {
285                    let s = match eval(e, ctx)? {
286                        Value::Num(n) => Scalar::Num(n),
287                        other => Scalar::Bool(boolean(&other)),
288                    };
289                    ctx.kept.borrow_mut().insert(key, s);
290                    s
291                }
292            };
293            match scalar {
294                Scalar::Num(n) => Value::Num(n),
295                Scalar::Bool(b) => Value::Bool(b),
296            }
297        }
298        Expr::Path { absolute, steps } => {
299            let start = if *absolute {
300                Item::Node(ctx.root)
301            } else {
302                ctx.item
303            };
304            Value::Nodes(walk(vec![start], steps, ctx)?)
305        }
306        Expr::Filter {
307            primary,
308            predicates,
309            steps,
310        } => {
311            let Value::Nodes(mut items) = eval(primary, ctx)? else {
312                return Err("predicates and paths can only follow a node-set".into());
313            };
314            for p in predicates {
315                items = filter(items, p, ctx)?;
316            }
317            Value::Nodes(walk(items, steps, ctx)?)
318        }
319    })
320}
321
322fn in_document_order<'a>(items: Vec<Item>, ctx: &Context<'a, '_>) -> Vec<Item> {
323    // Often they already are, and sorting a copy would double the memory.
324    if items.windows(2).all(|w| ctx.key(&w[0]) < ctx.key(&w[1])) {
325        return items;
326    }
327    // A key costs an index lookup, so each is read once.
328    let mut keyed: Vec<_> = items.into_iter().map(|i| (ctx.key(&i), i)).collect();
329    keyed.sort_unstable_by_key(|(k, _)| *k);
330    keyed.dedup_by_key(|(k, _)| *k);
331    keyed.into_iter().map(|(_, i)| i).collect()
332}
333
334fn walk<'a>(mut items: Vec<Item>, steps: &[Step], ctx: &Context<'a, '_>) -> Result<Vec<Item>> {
335    let index = ctx.doc.index;
336    let mut candidates = Vec::new();
337    let mut scanned = Vec::new();
338    let mut i = 0;
339    while i < steps.len() {
340        let step = &steps[i];
341        i += 1;
342        // "//x[pred]" is descendant-or-self::node()/child::x[pred]: run it
343        // as one descendant scan for x, with positions counted among each
344        // match's siblings, instead of a child scan from every node.
345        if let Some(next) = steps.get(i)
346            && step.axis == Axis::DescendantOrSelf
347            && step.test == NodeTest::Node
348            && step.predicates.is_empty()
349            && next.axis == Axis::Child
350            && !next.predicates.is_empty()
351            && let Some(grouped) = descendants_by_parent(&items, next, ctx)
352        {
353            items = grouped?;
354            i += 1;
355            continue;
356        }
357        let test = Test::resolve(&step.test, step.axis, ctx)?;
358        // Without predicates, a step's result is a set, whichever context
359        // node each member came from: work it out for the set at once, so
360        // nested or neighbouring context nodes don't each walk the same
361        // nodes again (`//div//div` on nested divs was quadratic).
362        if step.predicates.is_empty()
363            && items.len() > 1
364            && let Some(found) = whole_set(&items, step.axis, &test, ctx)?
365        {
366            items = found;
367            continue;
368        }
369        // A leading `[k]` with k a whole number from 1 up.
370        let nth = match step.predicates.first() {
371            Some(Expr::Number(k)) if *k >= 1.0 && k.fract() == 0.0 && *k < usize::MAX as f64 => {
372                Some(*k as usize)
373            }
374            _ => None,
375        };
376        let mut next = Vec::new();
377        for item in &items {
378            candidates.clear();
379            // Predicates already applied while collecting candidates.
380            let mut done = 0;
381            match (item, test.indexable()) {
382                // Child and descendant steps on names, *, text() and node()
383                // scan the document index instead of walking the tree.
384                (Item::Node(n), true)
385                    if matches!(
386                        step.axis,
387                        Axis::Child | Axis::Descendant | Axis::DescendantOrSelf
388                    ) =>
389                {
390                    let at = ctx.order(*n);
391                    let keep = |kind, tag| test.keeps(kind, tag);
392                    scanned.clear();
393                    match step.axis {
394                        Axis::Child => index.children(at, keep, &mut scanned),
395                        axis => {
396                            ctx.spend((index.end_of(at) - at) as usize)?;
397                            index.descendants(
398                                at,
399                                axis == Axis::DescendantOrSelf,
400                                keep,
401                                &mut scanned,
402                            )
403                        }
404                    }
405                    candidates.extend(
406                        scanned
407                            .iter()
408                            .copied()
409                            .map(Item::Node)
410                            .filter(|i| !test.exact() || test.matches(i, ctx)),
411                    );
412                }
413                _ => {
414                    let looked = Cell::new(0usize);
415                    let mut on_axis = axis(*item, step.axis, ctx)
416                        .inspect(|_| looked.set(looked.get() + 1))
417                        .filter(|c| test.matches(c, ctx));
418                    if nth.is_some() {
419                        done = 1;
420                    }
421                    match nth {
422                        // `[k]` first: stop at the kth node instead of
423                        // collecting the whole axis (following-sibling::dd[1]).
424                        Some(k) => candidates.extend(on_axis.nth(k - 1)),
425                        None => candidates.extend(on_axis),
426                    }
427                    ctx.spend(looked.get())?;
428                }
429            }
430            ctx.spend(candidates.len() + 1)?;
431            let mut kept = std::mem::take(&mut candidates);
432            for p in &step.predicates[done..] {
433                kept = filter(kept, p, ctx)?;
434            }
435            next.extend_from_slice(&kept);
436            candidates = kept;
437        }
438        // One context node's results are already in order; several need
439        // merging. Skipping the sort for one keeps `//x` a single scan.
440        items = if items.len() == 1 && !step.axis.is_reverse() {
441            next
442        } else {
443            in_document_order(next, ctx)
444        };
445    }
446    Ok(items)
447}
448
449/// A step without predicates from every one of `items` (in document
450/// order) at once, in document order: None for the axes that gain nothing
451/// from it.
452fn whole_set<'a>(
453    items: &[Item],
454    axis: Axis,
455    test: &Test<'_>,
456    ctx: &Context<'a, '_>,
457) -> Result<Option<Vec<Item>>> {
458    let index = ctx.doc.index;
459    let (_, tree_end) = ctx.tree_range();
460    let keep = |j: u32| {
461        let item = Item::Node(index.node_at(j));
462        if test.indexable() {
463            test.keeps(index.kind_at(j), index.tag_at(j))
464                && (!test.exact() || test.matches(&item, ctx))
465        } else {
466            test.matches(&item, ctx)
467        }
468    };
469    let mut out = Vec::new();
470    match axis {
471        Axis::Descendant | Axis::DescendantOrSelf => {
472            // A node inside an earlier item's subtree was scanned with it.
473            let mut covered_to = 0;
474            for item in items {
475                match item {
476                    Item::Node(n) => {
477                        let at = ctx.order(*n);
478                        if at < covered_to {
479                            continue;
480                        }
481                        covered_to = index.end_of(at);
482                        let from = if axis == Axis::DescendantOrSelf {
483                            at
484                        } else {
485                            at + 1
486                        };
487                        ctx.spend((covered_to - from) as usize)?;
488                        out.extend(
489                            (from..covered_to)
490                                .filter(|&j| keep(j))
491                                .map(|j| Item::Node(index.node_at(j))),
492                        );
493                    }
494                    // An attribute has no descendants, only itself.
495                    attr if axis == Axis::DescendantOrSelf && test.matches(attr, ctx) => {
496                        out.push(*attr)
497                    }
498                    _ => {}
499                }
500            }
501            return Ok(Some(in_document_order(out, ctx)));
502        }
503        Axis::Following => {
504            // Everything after the subtree that ends first: an attribute's
505            // following nodes start with its element's children.
506            let Some(from) = items
507                .iter()
508                .map(|i| match i {
509                    Item::Node(n) => index.end_of(ctx.order(*n)),
510                    Item::Attr { owner, .. } => ctx.order(*owner) + 1,
511                })
512                .min()
513            else {
514                return Ok(Some(out));
515            };
516            ctx.spend(tree_end.saturating_sub(from) as usize)?;
517            out.extend(
518                (from..tree_end)
519                    .filter(|&j| keep(j))
520                    .map(|j| Item::Node(index.node_at(j))),
521            );
522        }
523        Axis::Preceding => {
524            // The last item's preceding nodes hold every other item's.
525            let Some(last) = items.iter().map(|i| ctx.key(i).0).max() else {
526                return Ok(Some(out));
527            };
528            let (top, _) = ctx.tree_range();
529            ctx.spend(last.saturating_sub(top) as usize)?;
530            // Not its ancestors, whose subtrees reach past it.
531            out.extend(
532                (top..last)
533                    .filter(|&j| index.end_of(j) <= last && keep(j))
534                    .map(|j| Item::Node(index.node_at(j))),
535            );
536        }
537        Axis::Ancestor | Axis::AncestorOrSelf => {
538            // Climb from each item until reaching a node already climbed.
539            let mut seen = HashSet::new();
540            for item in items {
541                let start = match item {
542                    Item::Node(n) if axis == Axis::Ancestor => index.parent_of(ctx.order(*n)),
543                    Item::Node(n) => ctx.order(*n),
544                    Item::Attr { owner, .. } => {
545                        if axis == Axis::AncestorOrSelf && test.matches(item, ctx) {
546                            out.push(*item);
547                        }
548                        ctx.order(*owner)
549                    }
550                };
551                let mut at = start;
552                while at != u32::MAX && seen.insert(at) {
553                    ctx.spend(1)?;
554                    if keep(at) {
555                        out.push(Item::Node(index.node_at(at)));
556                    }
557                    at = index.parent_of(at);
558                }
559            }
560            return Ok(Some(in_document_order(out, ctx)));
561        }
562        Axis::FollowingSibling | Axis::PrecedingSibling => {
563            // Per parent, only the siblings of its first item (following)
564            // or its last (preceding) count. Attributes have no siblings.
565            let tree = ctx.doc.tree;
566            let mut from: HashMap<NodeId, NodeId> = HashMap::new();
567            for item in items {
568                if let Item::Node(n) = item
569                    && let Some(p) = tree.parent(*n)
570                {
571                    if axis == Axis::FollowingSibling {
572                        from.entry(p).or_insert(*n);
573                    } else {
574                        from.insert(p, *n);
575                    }
576                }
577            }
578            for &n in from.values() {
579                let step = |&s: &NodeId| match axis {
580                    Axis::FollowingSibling => tree.next_sibling(s),
581                    _ => tree.prev_sibling(s),
582                };
583                for s in std::iter::successors(step(&n), step) {
584                    ctx.spend(1)?;
585                    if keep(ctx.order(s)) {
586                        out.push(Item::Node(s));
587                    }
588                }
589            }
590            return Ok(Some(in_document_order(out, ctx)));
591        }
592        _ => return Ok(None),
593    }
594    Ok(Some(out))
595}
596
597/// `//x[pred]` from each item in `items`: every descendant passing `step`'s
598/// test, grouped by parent so predicate positions count siblings, in
599/// document order. None when the test can't be read from the index.
600fn descendants_by_parent<'a>(
601    items: &[Item],
602    step: &Step,
603    ctx: &Context<'a, '_>,
604) -> Option<Result<Vec<Item>>> {
605    let test = match Test::resolve(&step.test, step.axis, ctx) {
606        Ok(test) => test,
607        Err(e) => return Some(Err(e)),
608    };
609    if !test.indexable() {
610        return None;
611    }
612    let index = ctx.doc.index;
613    let mut found = Vec::new();
614    // Items come in document order. One inside an earlier item's subtree
615    // was scanned with it, and scanning it again would count its
616    // descendants twice.
617    let mut covered_to = 0;
618    for item in items {
619        // An attribute has no children.
620        let Item::Node(n) = item else { continue };
621        let at = ctx.order(*n);
622        if at < covered_to {
623            continue;
624        }
625        covered_to = index.end_of(at);
626        if let Err(e) = ctx.spend((covered_to - at) as usize) {
627            return Some(Err(e));
628        }
629        index.descendants(at, false, |k, t| test.keeps(k, t), &mut found);
630    }
631    if test.exact() {
632        found.retain(|&n| test.matches(&Item::Node(n), ctx));
633    }
634    // Predicates blind to the position need no sibling groups: the matches
635    // are in document order already. Each is tested once, so outside
636    // another predicate, keeping their answers would only take memory.
637    if !step.predicates.iter().any(Expr::positional) {
638        let mut items: Vec<Item> = found.into_iter().map(Item::Node).collect();
639        for p in &step.predicates {
640            let p = match p {
641                Expr::Memo(inner, _) if !ctx.nested => inner,
642                p => p,
643            };
644            items = match filter(items, p, ctx) {
645                Ok(items) => items,
646                Err(e) => return Some(Err(e)),
647            };
648        }
649        return Some(Ok(items));
650    }
651    // Group by parent, keeping each group in document order.
652    let mut groups: Vec<(u32, Vec<Item>)> = Vec::new();
653    let mut slot: HashMap<u32, usize> = HashMap::new();
654    for node in found {
655        let parent = index.parent_of(ctx.order(node));
656        let at = *slot.entry(parent).or_insert_with(|| {
657            groups.push((parent, Vec::new()));
658            groups.len() - 1
659        });
660        groups[at].1.push(Item::Node(node));
661    }
662    let run = || -> Result<Vec<Item>> {
663        let mut out = Vec::new();
664        for (_, mut group) in groups {
665            for p in &step.predicates {
666                group = filter(group, p, ctx)?;
667            }
668            out.extend(group);
669        }
670        Ok(in_document_order(out, ctx))
671    };
672    Some(run())
673}
674
675/// `[@name = 'value']`, `['value' = @name]` and `[@name]`: answered from
676/// the element directly, without building its attribute list. None for any
677/// other predicate.
678fn quick_predicate(pred: &Expr, item: &Item, doc: Doc<'_>) -> Option<bool> {
679    let attr_name = |e: &Expr| match e {
680        Expr::Path {
681            absolute: false,
682            steps,
683        } => match steps.as_slice() {
684            [
685                Step {
686                    axis: Axis::Attribute,
687                    test: NodeTest::Name(n),
688                    predicates,
689                },
690                // Doc::attr folds case when looking an attribute up, but
691                // XPath names are case-sensitive and HTML attribute names are
692                // stored lowercase: leave capitals to the general path.
693            ] if predicates.is_empty() && !n.bytes().any(|b| b.is_ascii_uppercase()) => {
694                Some(n.clone())
695            }
696            _ => None,
697        },
698        _ => None,
699    };
700    let Item::Node(node) = item else { return None };
701    match pred {
702        Expr::Binary(Op::Eq, l, r) => {
703            let (name, value) = match (attr_name(l), attr_name(r), &**l, &**r) {
704                (Some(n), None, _, Expr::Literal(v)) | (None, Some(n), Expr::Literal(v), _) => {
705                    (n, v)
706                }
707                _ => return None,
708            };
709            Some(doc.attr(*node, &name) == Some(value.as_str()))
710        }
711        other => attr_name(other).map(|n| doc.attr(*node, &n).is_some()),
712    }
713}
714
715/// Keeps the items for which `pred` holds, numbering them in the order
716/// given (axis order inside a step, document order in a filter).
717fn filter<'a>(items: Vec<Item>, pred: &Expr, ctx: &Context<'a, '_>) -> Result<Vec<Item>> {
718    let size = items.len();
719    ctx.spend(size)?;
720    // Kept in place: a second set as large would double the memory.
721    let mut kept = items;
722    let mut len = 0;
723    for i in 0..size {
724        let item = kept[i];
725        if let Some(keep) = quick_predicate(pred, &item, ctx.doc) {
726            if keep {
727                kept[len] = item;
728                len += 1;
729            }
730            continue;
731        }
732        let inner = Context {
733            item,
734            position: i + 1,
735            size,
736            nested: true,
737            ..*ctx
738        };
739        let keep = match eval(pred, &inner)? {
740            Value::Num(n) => n == (i + 1) as f64,
741            other => boolean(&other),
742        };
743        if keep {
744            kept[len] = item;
745            len += 1;
746        }
747    }
748    kept.truncate(len);
749    Ok(kept)
750}
751
752/// The URI `prefix` is bound to for this run.
753fn namespace<'c>(prefix: &str, ctx: &'c Context<'_, '_>) -> Result<&'c str> {
754    if let Some((_, uri)) = ctx.namespaces.iter().rev().find(|(p, _)| p == prefix) {
755        return Ok(uri);
756    }
757    if prefix == "xml" {
758        return Ok(XML_NS);
759    }
760    Err(format!("undefined namespace prefix {prefix:?}"))
761}
762
763/// A node test made ready for one document: names become tag ids,
764/// so matching an element is one integer comparison.
765enum Test<'t> {
766    Node,
767    Text,
768    Comment,
769    /// `processing-instruction()`, with the target if one is given.
770    Pi(Option<&'t str>),
771    Never,
772    /// `*` on the axis's principal node type.
773    AnyElement,
774    AnyAttribute,
775    ElementId(usize),
776    /// A name with capitals: no HTML element has one (the parser lowercases
777    /// them), but SVG and MathML elements can, so compare the text.
778    ElementName(&'t str),
779    AttributeName(&'t str),
780    /// An XML element by namespace and local name. `id` is the index's id
781    /// for the lowercased name, which the index can check first; the case
782    /// and namespace are checked after.
783    XmlElement {
784        id: usize,
785        local: &'t str,
786        ns: u32,
787    },
788    /// Any XML element in a namespace.
789    XmlElementIn(u32),
790    XmlAttribute {
791        local: &'t str,
792        ns: u32,
793    },
794    XmlAttributeIn(u32),
795}
796
797impl<'t> Test<'t> {
798    fn resolve(test: &'t NodeTest, axis: Axis, ctx: &Context<'_, '_>) -> Result<Test<'t>> {
799        let attr = axis == Axis::Attribute;
800        let index = ctx.doc.index;
801        if let Some(names) = ctx.doc.names {
802            // The namespace id a prefix stands for here; None if nothing in
803            // the document is in it.
804            let ns =
805                |prefix: &str| -> Result<Option<u32>> { Ok(names.id_of(namespace(prefix, ctx)?)) };
806            return Ok(match test {
807                NodeTest::Name(local) if attr => Test::XmlAttribute { local, ns: 0 },
808                NodeTest::Prefixed(p, local) if attr => match ns(p)? {
809                    Some(ns) => Test::XmlAttribute { local, ns },
810                    None => Test::Never,
811                },
812                NodeTest::AnyIn(p) if attr => ns(p)?.map_or(Test::Never, Test::XmlAttributeIn),
813                NodeTest::Name(local) => match index.tag_id_named(local) {
814                    Some(id) => Test::XmlElement { id, local, ns: 0 },
815                    None => Test::Never,
816                },
817                NodeTest::Prefixed(p, local) => match (ns(p)?, index.tag_id_named(local)) {
818                    (Some(ns), Some(id)) => Test::XmlElement { id, local, ns },
819                    _ => Test::Never,
820                },
821                NodeTest::AnyIn(p) => ns(p)?.map_or(Test::Never, Test::XmlElementIn),
822                other => Test::resolve_html(other, attr, ctx),
823            });
824        }
825        if let NodeTest::Prefixed(p, _) | NodeTest::AnyIn(p) = test {
826            // Checked, so a typo is still an error; but HTML has no
827            // namespaces, so nothing matches.
828            namespace(p, ctx)?;
829            return Ok(Test::Never);
830        }
831        Ok(Test::resolve_html(test, attr, ctx))
832    }
833
834    fn resolve_html(test: &'t NodeTest, attr: bool, ctx: &Context<'_, '_>) -> Test<'t> {
835        match test {
836            NodeTest::Node => Test::Node,
837            NodeTest::Text if attr => Test::Never,
838            NodeTest::Text => Test::Text,
839            NodeTest::Comment if attr => Test::Never,
840            NodeTest::Comment => Test::Comment,
841            // HTML5 parsing turns processing instructions into comments;
842            // XML keeps them.
843            NodeTest::ProcessingInstruction(_) if attr => Test::Never,
844            NodeTest::ProcessingInstruction(target) => Test::Pi(target.as_deref()),
845            NodeTest::Any if attr => Test::AnyAttribute,
846            NodeTest::Any => Test::AnyElement,
847            NodeTest::Name(name) if attr => Test::AttributeName(name),
848            NodeTest::Name(name) if name.bytes().any(|b| b.is_ascii_uppercase()) => {
849                Test::ElementName(name)
850            }
851            NodeTest::Name(name) => ctx
852                .doc
853                .index
854                .tag_id_named(name)
855                .map_or(Test::Never, Test::ElementId),
856            NodeTest::Prefixed(..) | NodeTest::AnyIn(_) => Test::Never,
857        }
858    }
859
860    /// Whether `keeps` can decide this test from the index alone, or (for
861    /// an `exact` one) narrow it down.
862    fn indexable(&self) -> bool {
863        matches!(
864            self,
865            Test::Node
866                | Test::Text
867                | Test::Comment
868                | Test::Pi(None)
869                | Test::AnyElement
870                | Test::ElementId(_)
871                | Test::XmlElement { .. }
872                | Test::Never
873        )
874    }
875
876    /// Whether what `keeps` lets through still needs `matches`.
877    fn exact(&self) -> bool {
878        matches!(self, Test::XmlElement { .. })
879    }
880
881    /// The test, from a node's kind and tag id.
882    fn keeps(&self, kind: u8, tag: usize) -> bool {
883        match self {
884            Test::Node => true,
885            Test::Text => kind == TEXT || kind == CDATA,
886            Test::Comment => kind == COMMENT,
887            Test::Pi(None) => kind == PI,
888            Test::AnyElement => kind == ELEMENT,
889            Test::ElementId(id) | Test::XmlElement { id, .. } => kind == ELEMENT && tag == *id,
890            _ => false,
891        }
892    }
893
894    fn matches(&self, item: &Item, ctx: &Context<'_, '_>) -> bool {
895        let kind = |n: &NodeId| ctx.kind(*n);
896        match (self, item) {
897            (Test::Node, _) => true,
898            (Test::Never, _) => false,
899            (Test::ElementId(id), Item::Node(n)) => {
900                let at = ctx.order(*n);
901                ctx.doc.index.tag_at(at) == *id && ctx.doc.index.kind_at(at) == ELEMENT
902            }
903            (Test::ElementName(name), Item::Node(n)) => ctx.tag(*n) == Some(name),
904            (Test::AnyElement, Item::Node(n)) => kind(n) == ELEMENT,
905            (Test::Text, Item::Node(n)) => matches!(kind(n), TEXT | CDATA),
906            (Test::Comment, Item::Node(n)) => kind(n) == COMMENT,
907            (Test::Pi(target), Item::Node(n)) => {
908                kind(n) == PI && target.is_none_or(|t| ctx.pi_target(*n) == Some(t))
909            }
910            (Test::AnyAttribute, Item::Attr { .. }) => true,
911            (Test::AttributeName(name), Item::Attr { owner, index, .. }) => {
912                ctx.doc.attr_at(*owner, *index).0 == *name
913            }
914            (Test::XmlElement { local, ns, .. }, Item::Node(n)) => {
915                kind(n) == ELEMENT && ctx.tag(*n) == Some(local) && ctx.ns_id(*n) == *ns
916            }
917            (Test::XmlElementIn(ns), Item::Node(n)) => kind(n) == ELEMENT && ctx.ns_id(*n) == *ns,
918            (Test::XmlAttribute { local, ns }, i @ Item::Attr { ns: a, .. }) => {
919                a == ns && ctx.local_name(i) == *local
920            }
921            (Test::XmlAttributeIn(ns), Item::Attr { ns: a, .. }) => a == ns,
922            _ => false,
923        }
924    }
925}
926
927fn attributes<'a>(n: NodeId, doc: Doc<'a>) -> impl Iterator<Item = Item> + 'a {
928    doc.tree
929        .attrs(n)
930        .enumerate()
931        .map(move |(i, (ns, _, _))| Item::Attr {
932            owner: n,
933            index: i as u32,
934            ns: match ns {
935                html::AttrNs::Host(id) => id,
936                _ => 0,
937            },
938        })
939}
940
941/// The nodes on `axis` from `item`, in axis order (nearest first for
942/// reverse axes), produced lazily.
943fn axis<'a>(item: Item, axis: Axis, ctx: &Context<'a, '_>) -> Box<dyn Iterator<Item = Item> + 'a> {
944    let doc = ctx.doc;
945    let (tree, index) = (doc.tree, doc.index);
946    let (top, tree_end) = ctx.tree_range();
947    let node_at = move |j: u32| Item::Node(index.node_at(j));
948    let ancestors =
949        move |n: NodeId| std::iter::successors(tree.parent(n), move |&p| tree.parent(p));
950    // Everything after `n` in document order that isn't its descendant.
951    let following = move |n: NodeId| (index.end_of(index.order(n))..tree_end).map(node_at);
952    // Everything before `n` that isn't its ancestor, nearest first.
953    let preceding = move |n: NodeId| {
954        let at = index.order(n);
955        (top..at)
956            .rev()
957            .filter(move |&j| index.end_of(j) <= at)
958            .map(node_at)
959    };
960    let descendants = move |n: NodeId| {
961        let at = index.order(n);
962        (at + 1..index.end_of(at)).map(node_at)
963    };
964    match item {
965        Item::Node(n) => match axis {
966            Axis::Child => Box::new(tree.children(n).map(Item::Node)),
967            Axis::Descendant => Box::new(descendants(n)),
968            Axis::DescendantOrSelf => Box::new(std::iter::once(item).chain(descendants(n))),
969            Axis::Parent => Box::new(tree.parent(n).map(Item::Node).into_iter()),
970            Axis::Ancestor => Box::new(ancestors(n).map(Item::Node)),
971            Axis::AncestorOrSelf => {
972                Box::new(std::iter::once(n).chain(ancestors(n)).map(Item::Node))
973            }
974            Axis::FollowingSibling => Box::new(
975                std::iter::successors(tree.next_sibling(n), move |&s| tree.next_sibling(s))
976                    .map(Item::Node),
977            ),
978            Axis::PrecedingSibling => Box::new(
979                std::iter::successors(tree.prev_sibling(n), move |&s| tree.prev_sibling(s))
980                    .map(Item::Node),
981            ),
982            Axis::Following => Box::new(following(n)),
983            Axis::Preceding => Box::new(preceding(n)),
984            Axis::Attribute if ctx.kind(n) == ELEMENT => Box::new(attributes(n, doc)),
985            Axis::Attribute | Axis::Namespace => Box::new(std::iter::empty()),
986            Axis::Itself => Box::new(std::iter::once(item)),
987        },
988        Item::Attr { owner, .. } => match axis {
989            Axis::Parent => Box::new(std::iter::once(Item::Node(owner))),
990            Axis::Ancestor => Box::new(
991                std::iter::once(owner)
992                    .chain(ancestors(owner))
993                    .map(Item::Node),
994            ),
995            Axis::AncestorOrSelf => Box::new(
996                std::iter::once(item).chain(
997                    std::iter::once(owner)
998                        .chain(ancestors(owner))
999                        .map(Item::Node),
1000                ),
1001            ),
1002            Axis::Itself | Axis::DescendantOrSelf => Box::new(std::iter::once(item)),
1003            Axis::Following => Box::new(descendants(owner).chain(following(owner))),
1004            Axis::Preceding => Box::new(preceding(owner)),
1005            _ => Box::new(std::iter::empty()),
1006        },
1007    }
1008}
1009
1010// --- conversions (section 4) ----------------------------------------------
1011
1012fn string<'a>(v: &Value<'a>, ctx: &Context<'a, '_>) -> String {
1013    match v {
1014        Value::Str(s) => s.to_string(),
1015        Value::Num(n) => number_to_string(*n),
1016        Value::Bool(b) => b.to_string(),
1017        Value::Nodes(items) => items
1018            .first()
1019            .map(|i| ctx.string_value(i).into_owned())
1020            .unwrap_or_default(),
1021    }
1022}
1023
1024fn number_to_string(n: f64) -> String {
1025    if n.is_nan() {
1026        "NaN".into()
1027    } else if n.is_infinite() {
1028        if n > 0.0 { "Infinity" } else { "-Infinity" }.into()
1029    } else if n == 0.0 {
1030        "0".into()
1031    } else {
1032        // Rust prints f64 without an exponent and without a trailing ".0",
1033        // as XPath requires.
1034        format!("{n}")
1035    }
1036}
1037
1038fn number<'a>(v: Value<'a>, ctx: &Context<'a, '_>) -> f64 {
1039    match v {
1040        Value::Num(n) => n,
1041        Value::Bool(b) => b as u8 as f64,
1042        Value::Str(s) => parse_number(&s),
1043        nodes @ Value::Nodes(_) => parse_number(&string(&nodes, ctx)),
1044    }
1045}
1046
1047/// XPath's Number grammar: optional minus, digits with an optional
1048/// fraction, and XML whitespace around. Anything else is NaN.
1049fn parse_number(s: &str) -> f64 {
1050    let t = s.trim_matches(|c| matches!(c, ' ' | '\t' | '\n' | '\r'));
1051    let digits = t.strip_prefix('-').unwrap_or(t);
1052    let valid = !digits.is_empty()
1053        && digits.chars().all(|c| c.is_ascii_digit() || c == '.')
1054        && digits.matches('.').count() <= 1
1055        && digits != ".";
1056    if valid {
1057        t.parse().unwrap_or(f64::NAN)
1058    } else {
1059        f64::NAN
1060    }
1061}
1062
1063fn boolean(v: &Value<'_>) -> bool {
1064    match v {
1065        Value::Bool(b) => *b,
1066        Value::Num(n) => *n != 0.0 && !n.is_nan(),
1067        Value::Str(s) => !s.is_empty(),
1068        Value::Nodes(items) => !items.is_empty(),
1069    }
1070}
1071
1072// --- operators (section 3.4, 3.5) -----------------------------------------
1073
1074fn binary<'a>(op: Op, l: &Expr, r: &Expr, ctx: &Context<'a, '_>) -> Result<Value<'a>> {
1075    Ok(match op {
1076        Op::Or => Value::Bool(boolean(&eval(l, ctx)?) || boolean(&eval(r, ctx)?)),
1077        Op::And => Value::Bool(boolean(&eval(l, ctx)?) && boolean(&eval(r, ctx)?)),
1078        Op::Add | Op::Sub | Op::Mul | Op::Div | Op::Mod => {
1079            let (a, b) = (number(eval(l, ctx)?, ctx), number(eval(r, ctx)?, ctx));
1080            Value::Num(match op {
1081                Op::Add => a + b,
1082                Op::Sub => a - b,
1083                Op::Mul => a * b,
1084                Op::Div => a / b,
1085                // Truncating remainder, which is what Rust's % does on f64.
1086                _ => a % b,
1087            })
1088        }
1089        _ => Value::Bool(compare(op, eval(l, ctx)?, eval(r, ctx)?, ctx)),
1090    })
1091}
1092
1093fn compare_atoms<'a>(op: Op, a: &Value<'a>, b: &Value<'a>, ctx: &Context<'a, '_>) -> bool {
1094    if matches!(op, Op::Eq | Op::Neq) {
1095        let equal = if matches!(a, Value::Bool(_)) || matches!(b, Value::Bool(_)) {
1096            boolean(a) == boolean(b)
1097        } else if matches!(a, Value::Num(_)) || matches!(b, Value::Num(_)) {
1098            number(a.clone(), ctx) == number(b.clone(), ctx)
1099        } else {
1100            // Without copying strings: a node-set compared with a string
1101            // compares every member.
1102            fn text<'v, 'a>(v: &'v Value<'a>, ctx: &Context<'a, '_>) -> Cow<'v, str> {
1103                match v {
1104                    Value::Str(s) => Cow::Borrowed(s),
1105                    other => Cow::Owned(string(other, ctx)),
1106                }
1107            }
1108            text(a, ctx) == text(b, ctx)
1109        };
1110        return equal == (op == Op::Eq);
1111    }
1112    let (x, y) = (number(a.clone(), ctx), number(b.clone(), ctx));
1113    match op {
1114        Op::Lt => x < y,
1115        Op::Le => x <= y,
1116        Op::Gt => x > y,
1117        _ => x >= y,
1118    }
1119}
1120
1121/// Comparisons involving node-sets are true if any member makes them true.
1122fn compare<'a>(op: Op, a: Value<'a>, b: Value<'a>, ctx: &Context<'a, '_>) -> bool {
1123    match (&a, &b) {
1124        (Value::Nodes(xs), Value::Nodes(ys)) => {
1125            let ys: Vec<Value<'_>> = ys.iter().map(|y| Value::Str(ctx.string_value(y))).collect();
1126            xs.iter().any(|x| {
1127                let x = Value::Str(ctx.string_value(x));
1128                ys.iter().any(|y| compare_atoms(op, &x, y, ctx))
1129            })
1130        }
1131        (Value::Nodes(_), Value::Bool(_)) | (Value::Bool(_), Value::Nodes(_)) => compare_atoms(
1132            op,
1133            &Value::Bool(boolean(&a)),
1134            &Value::Bool(boolean(&b)),
1135            ctx,
1136        ),
1137        (Value::Nodes(xs), other) => xs
1138            .iter()
1139            .any(|x| compare_atoms(op, &atom_like(x, other, ctx), other, ctx)),
1140        (other, Value::Nodes(ys)) => ys
1141            .iter()
1142            .any(|y| compare_atoms(op, other, &atom_like(y, other, ctx), ctx)),
1143        _ => compare_atoms(op, &a, &b, ctx),
1144    }
1145}
1146
1147/// A node's value as the type it is compared with.
1148fn atom_like<'a>(item: &Item, other: &Value<'_>, ctx: &Context<'a, '_>) -> Value<'a> {
1149    match other {
1150        Value::Num(_) => Value::Num(parse_number(&ctx.string_value(item))),
1151        _ => Value::Str(ctx.string_value(item)),
1152    }
1153}
1154
1155// --- functions (section 4) -------------------------------------------------
1156
1157/// The arguments of a call to an extension function, worked out when
1158/// asked for, as the core library's are.
1159pub struct Args<'c, 'a> {
1160    name: &'c str,
1161    exprs: &'c [Expr],
1162    ctx: &'c Context<'a, 'c>,
1163}
1164
1165impl<'a> Args<'_, 'a> {
1166    pub fn len(&self) -> usize {
1167        self.exprs.len()
1168    }
1169
1170    pub fn is_empty(&self) -> bool {
1171        self.exprs.is_empty()
1172    }
1173
1174    /// An error unless there are `min` to `max` arguments.
1175    pub fn arity(&self, min: usize, max: usize) -> Result<()> {
1176        arity(self.name, self.exprs.len(), min, max)
1177    }
1178
1179    /// Argument `i`, evaluated.
1180    pub fn value(&self, i: usize) -> Result<Value<'a>> {
1181        eval(&self.exprs[i], self.ctx)
1182    }
1183
1184    /// Argument `i`, converted as `string()` converts it.
1185    pub fn string(&self, i: usize) -> Result<String> {
1186        Ok(string(&self.value(i)?, self.ctx))
1187    }
1188
1189    /// The context node.
1190    pub fn context(&self) -> Item {
1191        self.ctx.item
1192    }
1193
1194    pub fn doc(&self) -> Doc<'a> {
1195        self.ctx.doc
1196    }
1197}
1198
1199fn arity(name: &str, got: usize, min: usize, max: usize) -> Result<()> {
1200    if got < min || got > max {
1201        let expected = if min == max {
1202            format!("{min}")
1203        } else if max == usize::MAX {
1204            format!("at least {min}")
1205        } else {
1206            format!("{min} to {max}")
1207        };
1208        return Err(format!("{name}() takes {expected} arguments, got {got}"));
1209    }
1210    Ok(())
1211}
1212
1213fn call<'a>(name: &str, args: &[Expr], ctx: &Context<'a, '_>) -> Result<Value<'a>> {
1214    let arity = |min: usize, max: usize| arity(name, args.len(), min, max);
1215    let arg = |i: usize| eval(&args[i], ctx);
1216    let str_arg = |i: usize| -> Result<String> { Ok(string(&eval(&args[i], ctx)?, ctx)) };
1217    let nodes_arg = |i: usize| -> Result<Vec<Item>> {
1218        match eval(&args[i], ctx)? {
1219            Value::Nodes(n) => Ok(n),
1220            _ => Err(format!("{name}() needs a node-set argument")),
1221        }
1222    };
1223    // The context node as a one-item node-set, for functions whose
1224    // argument defaults to it.
1225    let context_or = |i: usize| -> Result<Vec<Item>> {
1226        if args.len() > i {
1227            nodes_arg(i)
1228        } else {
1229            Ok(vec![ctx.item])
1230        }
1231    };
1232    Ok(match name {
1233        "last" => {
1234            arity(0, 0)?;
1235            Value::Num(ctx.size as f64)
1236        }
1237        "position" => {
1238            arity(0, 0)?;
1239            Value::Num(ctx.position as f64)
1240        }
1241        "count" => {
1242            arity(1, 1)?;
1243            Value::Num(nodes_arg(0)?.len() as f64)
1244        }
1245        "id" => {
1246            arity(1, 1)?;
1247            let wanted: Vec<String> = match arg(0)? {
1248                Value::Nodes(items) => items
1249                    .iter()
1250                    .map(|i| ctx.string_value(i).into_owned())
1251                    .collect(),
1252                other => vec![string(&other, ctx)],
1253            };
1254            let index = ctx.doc.index;
1255            let doc = ctx.doc;
1256            let (top, end) = ctx.tree_range();
1257            let found = wanted
1258                .iter()
1259                .flat_map(|s| s.split_whitespace())
1260                .flat_map(|id| index.with_id(id, |n| doc.attr(n, "id")))
1261                .filter(|&n| (top..end).contains(&ctx.order(n)))
1262                .map(Item::Node)
1263                .collect();
1264            Value::Nodes(in_document_order(found, ctx))
1265        }
1266        "local-name" | "name" | "namespace-uri" => {
1267            arity(0, 1)?;
1268            let first = in_document_order(context_or(0)?, ctx).into_iter().next();
1269            text(
1270                first
1271                    .map(|i| match name {
1272                        "name" => ctx.name(&i),
1273                        "local-name" => ctx.local_name(&i),
1274                        _ => ctx.namespace_uri(&i),
1275                    })
1276                    .unwrap_or_default()
1277                    .to_string(),
1278            )
1279        }
1280        "string" => {
1281            arity(0, 1)?;
1282            text(if args.is_empty() {
1283                ctx.string_value(&ctx.item).into_owned()
1284            } else {
1285                str_arg(0)?
1286            })
1287        }
1288        "concat" => {
1289            arity(2, usize::MAX)?;
1290            let mut out = String::new();
1291            for i in 0..args.len() {
1292                out.push_str(&str_arg(i)?);
1293            }
1294            text(out)
1295        }
1296        "starts-with" => {
1297            arity(2, 2)?;
1298            Value::Bool(str_arg(0)?.starts_with(&str_arg(1)?))
1299        }
1300        "contains" => {
1301            arity(2, 2)?;
1302            Value::Bool(str_arg(0)?.contains(&str_arg(1)?))
1303        }
1304        "substring-before" => {
1305            arity(2, 2)?;
1306            let (s, t) = (str_arg(0)?, str_arg(1)?);
1307            text(s.find(&t).map(|i| s[..i].to_string()).unwrap_or_default())
1308        }
1309        "substring-after" => {
1310            arity(2, 2)?;
1311            let (s, t) = (str_arg(0)?, str_arg(1)?);
1312            text(
1313                s.find(&t)
1314                    .map(|i| s[i + t.len()..].to_string())
1315                    .unwrap_or_default(),
1316            )
1317        }
1318        "substring" => {
1319            arity(2, 3)?;
1320            let s = str_arg(0)?;
1321            let start = round(number(arg(1)?, ctx));
1322            let end = if args.len() == 3 {
1323                start + round(number(arg(2)?, ctx))
1324            } else {
1325                f64::INFINITY
1326            };
1327            // Characters are numbered from 1; comparisons with NaN are false.
1328            text(
1329                s.chars()
1330                    .enumerate()
1331                    .filter(|(i, _)| {
1332                        let p = (*i + 1) as f64;
1333                        p >= start && p < end
1334                    })
1335                    .map(|(_, c)| c)
1336                    .collect(),
1337            )
1338        }
1339        "string-length" => {
1340            arity(0, 1)?;
1341            let s = if args.is_empty() {
1342                ctx.string_value(&ctx.item).into_owned()
1343            } else {
1344                str_arg(0)?
1345            };
1346            Value::Num(s.chars().count() as f64)
1347        }
1348        "normalize-space" => {
1349            arity(0, 1)?;
1350            let s = if args.is_empty() {
1351                ctx.string_value(&ctx.item).into_owned()
1352            } else {
1353                str_arg(0)?
1354            };
1355            text(
1356                s.split([' ', '\t', '\n', '\r'])
1357                    .filter(|w| !w.is_empty())
1358                    .collect::<Vec<_>>()
1359                    .join(" "),
1360            )
1361        }
1362        "translate" => {
1363            arity(3, 3)?;
1364            let (s, from, to) = (str_arg(0)?, str_arg(1)?, str_arg(2)?);
1365            let from: Vec<char> = from.chars().collect();
1366            let to: Vec<char> = to.chars().collect();
1367            text(
1368                s.chars()
1369                    .filter_map(|c| match from.iter().position(|&f| f == c) {
1370                        Some(i) => to.get(i).copied(),
1371                        None => Some(c),
1372                    })
1373                    .collect(),
1374            )
1375        }
1376        "boolean" => {
1377            arity(1, 1)?;
1378            Value::Bool(boolean(&arg(0)?))
1379        }
1380        "not" => {
1381            arity(1, 1)?;
1382            Value::Bool(!boolean(&arg(0)?))
1383        }
1384        "true" => {
1385            arity(0, 0)?;
1386            Value::Bool(true)
1387        }
1388        "false" => {
1389            arity(0, 0)?;
1390            Value::Bool(false)
1391        }
1392        "lang" => {
1393            arity(1, 1)?;
1394            let want = str_arg(0)?.to_ascii_lowercase();
1395            let node = match ctx.item {
1396                Item::Node(n) => n,
1397                Item::Attr { owner, .. } => owner,
1398            };
1399            let tree = ctx.doc.tree;
1400            // A climb per call: counted, as an ancestor axis is.
1401            let mut declared = None;
1402            let mut at = Some(node);
1403            while let Some(n) = at {
1404                ctx.spend(1)?;
1405                declared = ctx
1406                    .doc
1407                    .attr(n, "xml:lang")
1408                    .or_else(|| ctx.doc.attr(n, "lang"));
1409                if declared.is_some() {
1410                    break;
1411                }
1412                at = tree.parent(n);
1413            }
1414            let declared = declared.map(str::to_ascii_lowercase);
1415            Value::Bool(declared.is_some_and(|l| l == want || l.starts_with(&format!("{want}-"))))
1416        }
1417        "number" => {
1418            arity(0, 1)?;
1419            Value::Num(if args.is_empty() {
1420                parse_number(&ctx.string_value(&ctx.item))
1421            } else {
1422                number(arg(0)?, ctx)
1423            })
1424        }
1425        "sum" => {
1426            arity(1, 1)?;
1427            // Fold from 0.0: Rust's f64 sum() of nothing is -0.0.
1428            Value::Num(
1429                nodes_arg(0)?
1430                    .iter()
1431                    .map(|i| parse_number(&ctx.string_value(i)))
1432                    .fold(0.0, |a, b| a + b),
1433            )
1434        }
1435        "floor" => {
1436            arity(1, 1)?;
1437            Value::Num(number(arg(0)?, ctx).floor())
1438        }
1439        "ceiling" => {
1440            arity(1, 1)?;
1441            Value::Num(number(arg(0)?, ctx).ceil())
1442        }
1443        "round" => {
1444            arity(1, 1)?;
1445            Value::Num(round(number(arg(0)?, ctx)))
1446        }
1447        _ => {
1448            let args = Args {
1449                name,
1450                exprs: args,
1451                ctx,
1452            };
1453            return ctx
1454                .ext
1455                .call(name, &args)
1456                .unwrap_or_else(|| Err(format!("unknown function {name}()")));
1457        }
1458    })
1459}
1460
1461/// XPath's round: halves go up, and -0.5 <= x < 0 rounds to -0.
1462fn round(x: f64) -> f64 {
1463    if x.is_nan() || x.is_infinite() {
1464        x
1465    } else if (-0.5..0.0).contains(&x) {
1466        -0.0
1467    } else {
1468        // Not (x + 0.5).floor(): the addition rounds, which turns
1469        // 0.49999999999999994 into 1 and moves odd integers above 2^52.
1470        let f = x.floor();
1471        if x - f >= 0.5 { f + 1.0 } else { f }
1472    }
1473}
1474
1475#[cfg(test)]
1476mod tests {
1477    use super::*;
1478
1479    #[test]
1480    fn xpath_number_grammar() {
1481        assert_eq!(parse_number(" 12.5\n"), 12.5);
1482        assert_eq!(parse_number("-.5"), -0.5);
1483        assert_eq!(parse_number("5."), 5.0);
1484        for bad in ["", ".", "1e3", "+1", "0x10", "1.2.3", "inf", "NaN", "- 1"] {
1485            assert!(parse_number(bad).is_nan(), "{bad:?}");
1486        }
1487    }
1488}