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