Skip to main content

arb/
xpath_syntax.rs

1//! XPath 1.0 lexer, AST and parser.
2//!
3//! Grammar and section numbers throughout are from the W3C Recommendation of
4//! 16 November 1999, <https://www.w3.org/TR/1999/REC-xpath-19991116/>.
5//!
6//! This replaces a translator that compiled XPath-shaped syntax to a CSS
7//! selector. That approach could not carry axes, functions, positional
8//! predicates or anything else CSS has no spelling for — and worse, it made
9//! `/li/text()` mean "descendant li", so a ROOTED path answered with a
10//! non-empty node set where XPath selects nothing. A real parser plus a real
11//! evaluator ([`crate::xpath_eval`]) removes that whole class of answer.
12
13use std::fmt;
14
15// ── AST ─────────────────────────────────────────────────────────────────────
16
17/// The 13 axes of §2.2.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum Axis {
20    Ancestor,
21    AncestorOrSelf,
22    Attribute,
23    Child,
24    Descendant,
25    DescendantOrSelf,
26    Following,
27    FollowingSibling,
28    Namespace,
29    Parent,
30    Preceding,
31    PrecedingSibling,
32    SelfAxis,
33}
34
35impl Axis {
36    fn from_name(s: &str) -> Option<Axis> {
37        Some(match s {
38            "ancestor" => Axis::Ancestor,
39            "ancestor-or-self" => Axis::AncestorOrSelf,
40            "attribute" => Axis::Attribute,
41            "child" => Axis::Child,
42            "descendant" => Axis::Descendant,
43            "descendant-or-self" => Axis::DescendantOrSelf,
44            "following" => Axis::Following,
45            "following-sibling" => Axis::FollowingSibling,
46            "namespace" => Axis::Namespace,
47            "parent" => Axis::Parent,
48            "preceding" => Axis::Preceding,
49            "preceding-sibling" => Axis::PrecedingSibling,
50            "self" => Axis::SelfAxis,
51            _ => return None,
52        })
53    }
54
55    /// §2.2: "the ancestor, ancestor-or-self, preceding, and preceding-sibling
56    /// axes are reverse axes; all other axes are forward axes."
57    ///
58    /// This decides the PROXIMITY POSITION a predicate sees (§2.4): on a reverse
59    /// axis the first node is the one nearest the context node in REVERSE
60    /// document order, so `preceding-sibling::li[1]` is the immediately
61    /// preceding sibling, not the first one in the document.
62    pub fn is_reverse(self) -> bool {
63        matches!(
64            self,
65            Axis::Ancestor | Axis::AncestorOrSelf | Axis::Preceding | Axis::PrecedingSibling
66        )
67    }
68
69    /// §2.3: "every axis has a principal node type … For the attribute axis, the
70    /// principal node type is attribute. For the namespace axis, the principal
71    /// node type is namespace. For other axes, the principal node type is
72    /// element." This is what a name test or `*` selects.
73    pub fn principal(self) -> Principal {
74        match self {
75            Axis::Attribute => Principal::Attribute,
76            Axis::Namespace => Principal::Namespace,
77            _ => Principal::Element,
78        }
79    }
80}
81
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub enum Principal {
84    Element,
85    Attribute,
86    Namespace,
87}
88
89/// §2.3 NodeTest.
90#[derive(Debug, Clone, PartialEq, Eq)]
91pub enum NodeTest {
92    /// `*` — any node of the axis's principal type.
93    Any,
94    /// `prefix:*`.
95    AnyInPrefix(String),
96    /// A QName. HTML has no namespaces to speak of, so the whole QName is
97    /// matched against the node's name, which is also what libxml2 does for
98    /// HTML input.
99    Name(String),
100    /// `node()`.
101    Node,
102    /// `text()`.
103    Text,
104    /// `comment()`.
105    Comment,
106    /// `processing-instruction()` or `processing-instruction('target')`.
107    Pi(Option<String>),
108}
109
110#[derive(Debug, Clone, PartialEq)]
111pub struct Step {
112    pub axis: Axis,
113    pub test: NodeTest,
114    pub preds: Vec<Expr>,
115}
116
117/// Where a path's step list starts.
118#[derive(Debug, Clone, PartialEq)]
119pub enum PathStart {
120    /// `/…` — the root node of the document (§2).
121    Root,
122    /// `a/b` — the context node.
123    Relative,
124    /// §3.3 PathExpr: a FilterExpr followed by `/` or `//` steps.
125    Filter(Box<Expr>, Vec<Expr>),
126}
127
128#[derive(Debug, Clone, Copy, PartialEq, Eq)]
129pub enum RelOp {
130    Lt,
131    Gt,
132    Le,
133    Ge,
134}
135
136#[derive(Debug, Clone, PartialEq)]
137pub enum Expr {
138    Or(Box<Expr>, Box<Expr>),
139    And(Box<Expr>, Box<Expr>),
140    Eq(Box<Expr>, Box<Expr>),
141    Ne(Box<Expr>, Box<Expr>),
142    Rel(RelOp, Box<Expr>, Box<Expr>),
143    Add(Box<Expr>, Box<Expr>),
144    Sub(Box<Expr>, Box<Expr>),
145    Mul(Box<Expr>, Box<Expr>),
146    Div(Box<Expr>, Box<Expr>),
147    Mod(Box<Expr>, Box<Expr>),
148    Neg(Box<Expr>),
149    Union(Box<Expr>, Box<Expr>),
150    Path(PathStart, Vec<Step>),
151    Number(f64),
152    Literal(String),
153    Call(String, Vec<Expr>),
154}
155
156// ── lexer (§3.7) ────────────────────────────────────────────────────────────
157
158#[derive(Debug, Clone, PartialEq)]
159pub enum Tok {
160    Slash,
161    DblSlash,
162    LParen,
163    RParen,
164    LBracket,
165    RBracket,
166    Dot,
167    DblDot,
168    At,
169    Comma,
170    DblColon,
171    Star,
172    Pipe,
173    Plus,
174    Minus,
175    Eq,
176    Ne,
177    Lt,
178    Gt,
179    Le,
180    Ge,
181    /// `and` / `or` / `mod` / `div` recognized as an operator by §3.7's rule.
182    Op(&'static str),
183    Num(f64),
184    Str(String),
185    /// An NCName or QName. `is_fn` records that a `(` follows (a NodeType or
186    /// FunctionName), `is_axis` that a `::` follows.
187    Name {
188        text: String,
189        is_fn: bool,
190        is_axis: bool,
191    },
192}
193
194impl fmt::Display for Tok {
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        match self {
197            Tok::Slash => f.write_str("/"),
198            Tok::DblSlash => f.write_str("//"),
199            Tok::LParen => f.write_str("("),
200            Tok::RParen => f.write_str(")"),
201            Tok::LBracket => f.write_str("["),
202            Tok::RBracket => f.write_str("]"),
203            Tok::Dot => f.write_str("."),
204            Tok::DblDot => f.write_str(".."),
205            Tok::At => f.write_str("@"),
206            Tok::Comma => f.write_str(","),
207            Tok::DblColon => f.write_str("::"),
208            Tok::Star => f.write_str("*"),
209            Tok::Pipe => f.write_str("|"),
210            Tok::Plus => f.write_str("+"),
211            Tok::Minus => f.write_str("-"),
212            Tok::Eq => f.write_str("="),
213            Tok::Ne => f.write_str("!="),
214            Tok::Lt => f.write_str("<"),
215            Tok::Gt => f.write_str(">"),
216            Tok::Le => f.write_str("<="),
217            Tok::Ge => f.write_str(">="),
218            Tok::Op(s) => f.write_str(s),
219            Tok::Num(n) => write!(f, "{n}"),
220            Tok::Str(s) => write!(f, "'{s}'"),
221            Tok::Name { text, .. } => f.write_str(text),
222        }
223    }
224}
225
226/// Is `c` allowed to start an XML Name? XPath 1.0 defers to XML's `NameStartChar`
227/// via NCName; HTML tag and attribute names are ASCII in practice, and `_`/`:`
228/// are the only non-alphabetic starters worth carrying. Non-ASCII letters are
229/// accepted wholesale rather than table-driven — refusing a valid name would be
230/// a worse error than accepting an exotic one no HTML document contains.
231fn is_name_start(c: char) -> bool {
232    c.is_alphabetic() || c == '_' || !c.is_ascii()
233}
234
235fn is_name_char(c: char) -> bool {
236    is_name_start(c) || c.is_ascii_digit() || c == '-' || c == '.'
237}
238
239/// Tokenize an XPath expression.
240///
241/// §3.7's disambiguation rules are the whole reason this cannot be a naive
242/// scanner, and both are implemented here:
243///
244/// * "If there is a preceding token and the preceding token is not one of `@`,
245///   `::`, `(`, `[`, `,` or an Operator, then a `*` must be recognized as a
246///   MultiplyOperator and an NCName must be recognized as an OperatorName." That
247///   is what keeps `//div` (a name test) apart from `4 div 2` (an operator), and
248///   `//*` (a name test) apart from `2 * 3`.
249/// * "If the character following an NCName (possibly after intervening
250///   ExprWhitespace) is `(`, then the token must be recognized as a NodeType or
251///   a FunctionName" — and as an AxisName if followed by `::`.
252pub fn lex(src: &str) -> Result<Vec<Tok>, String> {
253    let cs: Vec<char> = src.chars().collect();
254    let mut i = 0;
255    let mut out: Vec<Tok> = Vec::new();
256    while i < cs.len() {
257        let c = cs[i];
258        if c.is_whitespace() {
259            i += 1;
260            continue;
261        }
262        // The §3.7 predicate: does the PREVIOUS token allow an operator here?
263        let after_operand = matches!(
264            out.last(),
265            Some(
266                Tok::RParen
267                    | Tok::RBracket
268                    | Tok::Num(_)
269                    | Tok::Str(_)
270                    | Tok::Star
271                    | Tok::Dot
272                    | Tok::DblDot
273                    | Tok::Name { .. }
274            )
275        );
276        match c {
277            '(' => {
278                out.push(Tok::LParen);
279                i += 1;
280            }
281            ')' => {
282                out.push(Tok::RParen);
283                i += 1;
284            }
285            '[' => {
286                out.push(Tok::LBracket);
287                i += 1;
288            }
289            ']' => {
290                out.push(Tok::RBracket);
291                i += 1;
292            }
293            '@' => {
294                out.push(Tok::At);
295                i += 1;
296            }
297            ',' => {
298                out.push(Tok::Comma);
299                i += 1;
300            }
301            '|' => {
302                out.push(Tok::Pipe);
303                i += 1;
304            }
305            '+' => {
306                out.push(Tok::Plus);
307                i += 1;
308            }
309            '-' => {
310                out.push(Tok::Minus);
311                i += 1;
312            }
313            '*' => {
314                // Both readings are the same token; the PARSER decides, using the
315                // same "is an operator legal here" state. Recording it as `Star`
316                // keeps the lexer from needing the grammar.
317                out.push(Tok::Star);
318                i += 1;
319            }
320            '=' => {
321                out.push(Tok::Eq);
322                i += 1;
323            }
324            '!' if cs.get(i + 1) == Some(&'=') => {
325                out.push(Tok::Ne);
326                i += 2;
327            }
328            '!' => return Err("`!` must be part of `!=`".into()),
329            '<' if cs.get(i + 1) == Some(&'=') => {
330                out.push(Tok::Le);
331                i += 2;
332            }
333            '<' => {
334                out.push(Tok::Lt);
335                i += 1;
336            }
337            '>' if cs.get(i + 1) == Some(&'=') => {
338                out.push(Tok::Ge);
339                i += 2;
340            }
341            '>' => {
342                out.push(Tok::Gt);
343                i += 1;
344            }
345            '/' if cs.get(i + 1) == Some(&'/') => {
346                out.push(Tok::DblSlash);
347                i += 2;
348            }
349            '/' => {
350                out.push(Tok::Slash);
351                i += 1;
352            }
353            ':' if cs.get(i + 1) == Some(&':') => {
354                out.push(Tok::DblColon);
355                i += 2;
356            }
357            '\'' | '"' => {
358                // §3.7 Literal. Both quote characters are legal and neither
359                // escapes: a literal delimited by `'` may contain `"` and vice
360                // versa. An UNTERMINATED literal is an error, never a silently
361                // truncated string.
362                let quote = c;
363                i += 1;
364                let start = i;
365                while i < cs.len() && cs[i] != quote {
366                    i += 1;
367                }
368                if i >= cs.len() {
369                    return Err(format!("unterminated string literal ({quote}…)"));
370                }
371                out.push(Tok::Str(cs[start..i].iter().collect()));
372                i += 1;
373            }
374            '.' if cs.get(i + 1) == Some(&'.') => {
375                out.push(Tok::DblDot);
376                i += 2;
377            }
378            // §3.7 Number ::= Digits ('.' Digits?)? | '.' Digits. A `.` that
379            // begins a number is only a number when a digit follows it.
380            '.' if cs.get(i + 1).is_some_and(char::is_ascii_digit) => {
381                let start = i;
382                i += 1;
383                while i < cs.len() && cs[i].is_ascii_digit() {
384                    i += 1;
385                }
386                out.push(Tok::Num(num(&cs[start..i])?));
387            }
388            '.' => {
389                out.push(Tok::Dot);
390                i += 1;
391            }
392            c if c.is_ascii_digit() => {
393                let start = i;
394                while i < cs.len() && cs[i].is_ascii_digit() {
395                    i += 1;
396                }
397                if cs.get(i) == Some(&'.') {
398                    i += 1;
399                    while i < cs.len() && cs[i].is_ascii_digit() {
400                        i += 1;
401                    }
402                }
403                out.push(Tok::Num(num(&cs[start..i])?));
404            }
405            c if is_name_start(c) => {
406                let start = i;
407                while i < cs.len() && is_name_char(cs[i]) {
408                    i += 1;
409                }
410                // A QName's single `:` joins two NCNames. `::` is the axis
411                // separator and must NOT be eaten here.
412                if cs.get(i) == Some(&':') && cs.get(i + 1).is_some_and(|c| is_name_start(*c)) {
413                    i += 1;
414                    while i < cs.len() && is_name_char(cs[i]) {
415                        i += 1;
416                    }
417                } else if cs.get(i) == Some(&':') && cs.get(i + 1) == Some(&'*') {
418                    i += 2;
419                }
420                let text: String = cs[start..i].iter().collect();
421                // Look ahead past whitespace for `(` and `::`.
422                let mut j = i;
423                while j < cs.len() && cs[j].is_whitespace() {
424                    j += 1;
425                }
426                let is_fn = cs.get(j) == Some(&'(');
427                let is_axis = cs.get(j) == Some(&':') && cs.get(j + 1) == Some(&':');
428                // The OperatorName rule: only when an operator is legal here and
429                // the name is not itself being used as a function or an axis.
430                if after_operand && !is_fn && !is_axis {
431                    match text.as_str() {
432                        "and" | "or" | "mod" | "div" => {
433                            out.push(Tok::Op(match text.as_str() {
434                                "and" => "and",
435                                "or" => "or",
436                                "mod" => "mod",
437                                _ => "div",
438                            }));
439                            continue;
440                        }
441                        _ => {}
442                    }
443                }
444                out.push(Tok::Name {
445                    text,
446                    is_fn,
447                    is_axis,
448                });
449            }
450            other => return Err(format!("unexpected character `{other}`")),
451        }
452    }
453    Ok(out)
454}
455
456fn num(cs: &[char]) -> Result<f64, String> {
457    let s: String = cs.iter().collect();
458    s.parse::<f64>().map_err(|_| format!("bad number `{s}`"))
459}
460
461// ── parser (§3.1–§3.5, §2) ──────────────────────────────────────────────────
462
463struct P {
464    toks: Vec<Tok>,
465    i: usize,
466}
467
468/// Parse a complete XPath 1.0 expression, or report why it is not one.
469///
470/// Trailing junk is an ERROR rather than being ignored: an expression this
471/// parser only half-understands must never reach the evaluator, because a
472/// half-understood path is exactly how the old translator produced answers that
473/// looked right and were not.
474pub fn parse(src: &str) -> Result<Expr, String> {
475    let toks = lex(src)?;
476    if toks.is_empty() {
477        return Err("empty expression".into());
478    }
479    let mut p = P { toks, i: 0 };
480    let e = p.expr()?;
481    if p.i != p.toks.len() {
482        return Err(format!(
483            "unexpected `{}` after a complete expression",
484            p.toks[p.i]
485        ));
486    }
487    Ok(e)
488}
489
490impl P {
491    fn peek(&self) -> Option<&Tok> {
492        self.toks.get(self.i)
493    }
494
495    fn eat(&mut self, t: &Tok) -> bool {
496        if self.peek() == Some(t) {
497            self.i += 1;
498            true
499        } else {
500            false
501        }
502    }
503
504    fn expect(&mut self, t: &Tok) -> Result<(), String> {
505        if self.eat(t) {
506            Ok(())
507        } else {
508            Err(match self.peek() {
509                Some(g) => format!("expected `{t}`, found `{g}`"),
510                None => format!("expected `{t}`, found end of expression"),
511            })
512        }
513    }
514
515    // §3.4 OrExpr ::= AndExpr | OrExpr 'or' AndExpr
516    fn expr(&mut self) -> Result<Expr, String> {
517        let mut l = self.and_expr()?;
518        while self.eat(&Tok::Op("or")) {
519            l = Expr::Or(Box::new(l), Box::new(self.and_expr()?));
520        }
521        Ok(l)
522    }
523
524    fn and_expr(&mut self) -> Result<Expr, String> {
525        let mut l = self.eq_expr()?;
526        while self.eat(&Tok::Op("and")) {
527            l = Expr::And(Box::new(l), Box::new(self.eq_expr()?));
528        }
529        Ok(l)
530    }
531
532    fn eq_expr(&mut self) -> Result<Expr, String> {
533        let mut l = self.rel_expr()?;
534        loop {
535            if self.eat(&Tok::Eq) {
536                l = Expr::Eq(Box::new(l), Box::new(self.rel_expr()?));
537            } else if self.eat(&Tok::Ne) {
538                l = Expr::Ne(Box::new(l), Box::new(self.rel_expr()?));
539            } else {
540                return Ok(l);
541            }
542        }
543    }
544
545    fn rel_expr(&mut self) -> Result<Expr, String> {
546        let mut l = self.add_expr()?;
547        loop {
548            let op = match self.peek() {
549                Some(Tok::Lt) => RelOp::Lt,
550                Some(Tok::Gt) => RelOp::Gt,
551                Some(Tok::Le) => RelOp::Le,
552                Some(Tok::Ge) => RelOp::Ge,
553                _ => return Ok(l),
554            };
555            self.i += 1;
556            l = Expr::Rel(op, Box::new(l), Box::new(self.add_expr()?));
557        }
558    }
559
560    fn add_expr(&mut self) -> Result<Expr, String> {
561        let mut l = self.mul_expr()?;
562        loop {
563            if self.eat(&Tok::Plus) {
564                l = Expr::Add(Box::new(l), Box::new(self.mul_expr()?));
565            } else if self.eat(&Tok::Minus) {
566                l = Expr::Sub(Box::new(l), Box::new(self.mul_expr()?));
567            } else {
568                return Ok(l);
569            }
570        }
571    }
572
573    fn mul_expr(&mut self) -> Result<Expr, String> {
574        let mut l = self.unary_expr()?;
575        loop {
576            // A `*` here is the MultiplyOperator: the parser is in a position
577            // where an operand has just been read, which is §3.7's own rule.
578            if self.eat(&Tok::Star) {
579                l = Expr::Mul(Box::new(l), Box::new(self.unary_expr()?));
580            } else if self.eat(&Tok::Op("div")) {
581                l = Expr::Div(Box::new(l), Box::new(self.unary_expr()?));
582            } else if self.eat(&Tok::Op("mod")) {
583                l = Expr::Mod(Box::new(l), Box::new(self.unary_expr()?));
584            } else {
585                return Ok(l);
586            }
587        }
588    }
589
590    // §3.5 UnaryExpr ::= UnionExpr | '-' UnaryExpr
591    fn unary_expr(&mut self) -> Result<Expr, String> {
592        if self.eat(&Tok::Minus) {
593            return Ok(Expr::Neg(Box::new(self.unary_expr()?)));
594        }
595        self.union_expr()
596    }
597
598    fn union_expr(&mut self) -> Result<Expr, String> {
599        let mut l = self.path_expr()?;
600        while self.eat(&Tok::Pipe) {
601            l = Expr::Union(Box::new(l), Box::new(self.path_expr()?));
602        }
603        Ok(l)
604    }
605
606    /// §3.3 PathExpr ::= LocationPath
607    ///                 | FilterExpr
608    ///                 | FilterExpr '/' RelativeLocationPath
609    ///                 | FilterExpr '//' RelativeLocationPath
610    fn path_expr(&mut self) -> Result<Expr, String> {
611        // A PrimaryExpr start means this is a FilterExpr, not a LocationPath.
612        // §2.3's four NodeTypes are spelled like function calls and are not
613        // ones: `text()` starting an expression is a location STEP
614        // (`child::text()`), which is what `//a[text()="X"]` means. Reading it as
615        // a FunctionCall made that predicate a hard error on a path xmllint
616        // answers.
617        let node_type_ahead = matches!(
618            self.peek(),
619            Some(Tok::Name { text, is_fn: true, .. })
620                if matches!(text.as_str(), "node" | "text" | "comment" | "processing-instruction")
621        );
622        let is_filter = !node_type_ahead
623            && (matches!(
624                self.peek(),
625                Some(Tok::Num(_)) | Some(Tok::Str(_)) | Some(Tok::LParen)
626            ) || matches!(self.peek(), Some(Tok::Name { is_fn: true, .. })));
627        if is_filter {
628            let base = self.primary_expr()?;
629            let mut preds = Vec::new();
630            while self.eat(&Tok::LBracket) {
631                preds.push(self.expr()?);
632                self.expect(&Tok::RBracket)?;
633            }
634            let mut steps = Vec::new();
635            if self.eat(&Tok::DblSlash) {
636                steps.push(descendant_or_self());
637                steps.extend(self.relative_path()?);
638            } else if self.eat(&Tok::Slash) {
639                steps.extend(self.relative_path()?);
640            }
641            // §3.3: a bare FilterExpr IS a PathExpr, and its value is the
642            // primary expression's own — `'/x'` is the string `/x` and
643            // `last()` is a number. Wrapping those in a Path would demand a
644            // node-set from a value that is not one, which is how
645            // `//a[@href='/x']` came back as an error instead of a match.
646            if preds.is_empty() && steps.is_empty() {
647                return Ok(base);
648            }
649            return Ok(Expr::Path(PathStart::Filter(Box::new(base), preds), steps));
650        }
651        self.location_path()
652    }
653
654    // §2 LocationPath ::= RelativeLocationPath | AbsoluteLocationPath
655    fn location_path(&mut self) -> Result<Expr, String> {
656        if self.eat(&Tok::DblSlash) {
657            // §2.5: `//x` abbreviates `/descendant-or-self::node()/x`.
658            let mut steps = vec![descendant_or_self()];
659            steps.extend(self.relative_path()?);
660            return Ok(Expr::Path(PathStart::Root, steps));
661        }
662        if self.eat(&Tok::Slash) {
663            // A lone `/` is the root node itself. `/` followed by a step is a
664            // path FROM the root — which is what makes `/li` select nothing on a
665            // document whose root child is `html`, the bug this engine exists to
666            // fix.
667            if self.starts_step() {
668                let steps = self.relative_path()?;
669                return Ok(Expr::Path(PathStart::Root, steps));
670            }
671            return Ok(Expr::Path(PathStart::Root, Vec::new()));
672        }
673        let steps = self.relative_path()?;
674        Ok(Expr::Path(PathStart::Relative, steps))
675    }
676
677    /// Can the current token begin a Step?
678    fn starts_step(&self) -> bool {
679        matches!(
680            self.peek(),
681            Some(Tok::At | Tok::Dot | Tok::DblDot | Tok::Star | Tok::Name { .. })
682        )
683    }
684
685    fn relative_path(&mut self) -> Result<Vec<Step>, String> {
686        let mut steps = vec![self.step()?];
687        loop {
688            if self.eat(&Tok::DblSlash) {
689                steps.push(descendant_or_self());
690                steps.push(self.step()?);
691            } else if self.eat(&Tok::Slash) {
692                steps.push(self.step()?);
693            } else {
694                return Ok(steps);
695            }
696        }
697    }
698
699    // §2.1 Step ::= AxisSpecifier NodeTest Predicate* | AbbreviatedStep
700    fn step(&mut self) -> Result<Step, String> {
701        // §2.5 AbbreviatedStep: `.` is `self::node()`, `..` is `parent::node()`.
702        if self.eat(&Tok::Dot) {
703            return Ok(Step {
704                axis: Axis::SelfAxis,
705                test: NodeTest::Node,
706                preds: Vec::new(),
707            });
708        }
709        if self.eat(&Tok::DblDot) {
710            return Ok(Step {
711                axis: Axis::Parent,
712                test: NodeTest::Node,
713                preds: Vec::new(),
714            });
715        }
716        // §2.5: `@` abbreviates `attribute::`.
717        let axis = if self.eat(&Tok::At) {
718            Axis::Attribute
719        } else if let Some(Tok::Name {
720            text,
721            is_axis: true,
722            ..
723        }) = self.peek()
724        {
725            let name = text.clone();
726            let a =
727                Axis::from_name(&name).ok_or_else(|| format!("`{name}` is not an XPath axis"))?;
728            self.i += 1;
729            self.expect(&Tok::DblColon)?;
730            a
731        } else {
732            Axis::Child
733        };
734        let test = self.node_test()?;
735        let mut preds = Vec::new();
736        while self.eat(&Tok::LBracket) {
737            preds.push(self.expr()?);
738            self.expect(&Tok::RBracket)?;
739        }
740        Ok(Step { axis, test, preds })
741    }
742
743    // §2.3 NodeTest ::= NameTest | NodeType '(' ')' | 'processing-instruction' '(' Literal ')'
744    fn node_test(&mut self) -> Result<NodeTest, String> {
745        if self.eat(&Tok::Star) {
746            return Ok(NodeTest::Any);
747        }
748        let (text, is_fn) = match self.peek() {
749            Some(Tok::Name { text, is_fn, .. }) => (text.clone(), *is_fn),
750            Some(t) => return Err(format!("expected a node test, found `{t}`")),
751            None => return Err("expected a node test, found end of expression".into()),
752        };
753        self.i += 1;
754        if is_fn {
755            self.expect(&Tok::LParen)?;
756            let t = match text.as_str() {
757                "node" => NodeTest::Node,
758                "text" => NodeTest::Text,
759                "comment" => NodeTest::Comment,
760                "processing-instruction" => {
761                    if let Some(Tok::Str(s)) = self.peek() {
762                        let s = s.clone();
763                        self.i += 1;
764                        NodeTest::Pi(Some(s))
765                    } else {
766                        NodeTest::Pi(None)
767                    }
768                }
769                other => {
770                    return Err(format!(
771                        "`{other}()` is not a node type (expected node, text, comment or \
772                         processing-instruction)"
773                    ))
774                }
775            };
776            self.expect(&Tok::RParen)?;
777            return Ok(t);
778        }
779        if let Some(prefix) = text.strip_suffix(":*") {
780            return Ok(NodeTest::AnyInPrefix(prefix.to_string()));
781        }
782        Ok(NodeTest::Name(text))
783    }
784
785    // §3.1 PrimaryExpr ::= VariableReference | '(' Expr ')' | Literal | Number | FunctionCall
786    fn primary_expr(&mut self) -> Result<Expr, String> {
787        match self.peek().cloned() {
788            Some(Tok::Num(n)) => {
789                self.i += 1;
790                Ok(Expr::Number(n))
791            }
792            Some(Tok::Str(s)) => {
793                self.i += 1;
794                Ok(Expr::Literal(s))
795            }
796            Some(Tok::LParen) => {
797                self.i += 1;
798                let e = self.expr()?;
799                self.expect(&Tok::RParen)?;
800                Ok(e)
801            }
802            Some(Tok::Name {
803                text, is_fn: true, ..
804            }) => {
805                self.i += 1;
806                self.expect(&Tok::LParen)?;
807                let mut args = Vec::new();
808                if !self.eat(&Tok::RParen) {
809                    loop {
810                        args.push(self.expr()?);
811                        if self.eat(&Tok::Comma) {
812                            continue;
813                        }
814                        self.expect(&Tok::RParen)?;
815                        break;
816                    }
817                }
818                Ok(Expr::Call(text, args))
819            }
820            Some(t) => Err(format!("expected an expression, found `{t}`")),
821            None => Err("expected an expression, found end of expression".into()),
822        }
823    }
824}
825
826/// The step `//` abbreviates (§2.5): `descendant-or-self::node()`.
827fn descendant_or_self() -> Step {
828    Step {
829        axis: Axis::DescendantOrSelf,
830        test: NodeTest::Node,
831        preds: Vec::new(),
832    }
833}