libxml_rs/xml/xpath/
lexer.rs

1//! XPath 1.0 Expression Lexer/Tokenizer (§25).
2//!
3//! Tokenizes XPath expression strings into a stream of tokens
4//! for the parser to consume.
5//!
6//! # UPSTREAM-PARITY
7//!
8//! Covers all XPath 1.0 token types: names, numbers, strings, operators,
9//! axes, function names, variable references, punctuation.
10//!
11//! # Courts
12//!
13//! XPATH-LEXER-*
14
15use std::fmt;
16
17// ═══════════════════════════════════════════════════════════════════════════════
18// Token Types
19// ═══════════════════════════════════════════════════════════════════════════════
20
21/// A token in an XPath expression.
22#[derive(Debug, Clone, PartialEq)]
23pub enum Token {
24    // ── Names ────────────────────────────────────────────────────────────
25    /// Name (NCName or QName)
26    Name(String),
27    /// `*` wildcard
28    Star,
29    /// `.` (self)
30    Dot,
31    /// `..` (parent)
32    DotDot,
33
34    // ── Operators ────────────────────────────────────────────────────────
35    /// `@` (attribute axis)
36    At,
37    /// `::` (axis separator)
38    DoubleColon,
39    /// `/`
40    Slash,
41    /// `//`
42    DoubleSlash,
43    /// `|`
44    Pipe,
45    /// `+`
46    Plus,
47    /// `-`
48    Minus,
49    /// `=`
50    Eq,
51    /// `!=`
52    Ne,
53    /// `<`
54    Lt,
55    /// `>`
56    Gt,
57    /// `<=`
58    Le,
59    /// `>=`
60    Ge,
61    /// `*` (multiplication operator, distinct from wildcard)
62    Multiply,
63
64    // ── Keywords ─────────────────────────────────────────────────────────
65    /// `or`
66    Or,
67    /// `and`
68    And,
69    /// `mod`
70    Mod,
71    /// `div`
72    Div,
73    /// `ancestor`
74    Ancestor,
75    /// `ancestor-or-self`
76    AncestorOrSelf,
77    /// `attribute`
78    Attribute,
79    /// `child`
80    Child,
81    /// `descendant`
82    Descendant,
83    /// `descendant-or-self`
84    DescendantOrSelf,
85    /// `following`
86    Following,
87    /// `following-sibling`
88    FollowingSibling,
89    /// `namespace`
90    Namespace,
91    /// `parent`
92    Parent,
93    /// `preceding`
94    Preceding,
95    /// `preceding-sibling`
96    PrecedingSibling,
97    /// `self`
98    Self_,
99
100    // ── Literals ─────────────────────────────────────────────────────────
101    /// String literal (without quotes)
102    StringLiteral(String),
103    /// Numeric literal
104    NumberLiteral(f64),
105
106    // ── Punctuation ──────────────────────────────────────────────────────
107    /// `(` — left parenthesis (groups sub-expressions, opens function calls)
108    LParen,
109    /// `)` — right parenthesis
110    RParen,
111    /// `[` — left bracket (opens a predicate)
112    LBracket,
113    /// `]` — right bracket (closes a predicate)
114    RBracket,
115    /// `{` — left brace (for XSLT attribute value templates; rare in XPath)
116    LBrace,
117    /// `}` — right brace
118    RBrace,
119    /// `,` — separates function call arguments
120    Comma,
121    /// `$` (variable reference)
122    Dollar,
123
124    // ── Special ──────────────────────────────────────────────────────────
125    /// End of expression
126    Eof,
127}
128
129impl fmt::Display for Token {
130    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
131        match self {
132            Token::Name(n) => write!(f, "{}", n),
133            Token::Star => write!(f, "*"),
134            Token::Dot => write!(f, "."),
135            Token::DotDot => write!(f, ".."),
136            Token::At => write!(f, "@"),
137            Token::DoubleColon => write!(f, "::"),
138            Token::Slash => write!(f, "/"),
139            Token::DoubleSlash => write!(f, "//"),
140            Token::Pipe => write!(f, "|"),
141            Token::Plus => write!(f, "+"),
142            Token::Minus => write!(f, "-"),
143            Token::Eq => write!(f, "="),
144            Token::Ne => write!(f, "!="),
145            Token::Lt => write!(f, "<"),
146            Token::Gt => write!(f, ">"),
147            Token::Le => write!(f, "<="),
148            Token::Ge => write!(f, ">="),
149            Token::Multiply => write!(f, "*"),
150            Token::Or => write!(f, "or"),
151            Token::And => write!(f, "and"),
152            Token::Mod => write!(f, "mod"),
153            Token::Div => write!(f, "div"),
154            Token::Ancestor => write!(f, "ancestor"),
155            Token::AncestorOrSelf => write!(f, "ancestor-or-self"),
156            Token::Attribute => write!(f, "attribute"),
157            Token::Child => write!(f, "child"),
158            Token::Descendant => write!(f, "descendant"),
159            Token::DescendantOrSelf => write!(f, "descendant-or-self"),
160            Token::Following => write!(f, "following"),
161            Token::FollowingSibling => write!(f, "following-sibling"),
162            Token::Namespace => write!(f, "namespace"),
163            Token::Parent => write!(f, "parent"),
164            Token::Preceding => write!(f, "preceding"),
165            Token::PrecedingSibling => write!(f, "preceding-sibling"),
166            Token::Self_ => write!(f, "self"),
167            Token::StringLiteral(s) => write!(f, "'{}'", s),
168            Token::NumberLiteral(n) => write!(f, "{}", n),
169            Token::LParen => write!(f, "("),
170            Token::RParen => write!(f, ")"),
171            Token::LBracket => write!(f, "["),
172            Token::RBracket => write!(f, "]"),
173            Token::LBrace => write!(f, "{{"),
174            Token::RBrace => write!(f, "}}"),
175            Token::Comma => write!(f, ","),
176            Token::Dollar => write!(f, "$"),
177            Token::Eof => write!(f, "<EOF>"),
178        }
179    }
180}
181
182// ═══════════════════════════════════════════════════════════════════════════════
183// Lexer
184// ═══════════════════════════════════════════════════════════════════════════════
185
186/// XPath expression lexer.
187///
188/// Produces a stream of tokens from an XPath expression string.
189#[derive(Debug, Clone)]
190pub struct Lexer {
191    /// Input bytes
192    input: Vec<u8>,
193    /// Current position
194    pos: usize,
195    /// Look-ahead character (0 if EOF)
196    ch: u8,
197    /// Whether we're at the start of an expression (helps with `-` vs `-`)
198    at_start: bool,
199}
200
201impl Lexer {
202    /// Create a lexer for the given XPath expression string.
203    pub fn new(input: &str) -> Self {
204        let bytes = input.as_bytes().to_vec();
205        let ch = if bytes.is_empty() { 0 } else { bytes[0] };
206        Self {
207            input: bytes,
208            pos: 0,
209            ch,
210            at_start: true,
211        }
212    }
213
214    /// Advance to the next character.
215    fn advance(&mut self) {
216        self.pos += 1;
217        self.ch = if self.pos < self.input.len() {
218            self.input[self.pos]
219        } else {
220            0
221        };
222    }
223
224    /// Peek at the next character without consuming it.
225    fn peek(&self) -> u8 {
226        if self.pos + 1 < self.input.len() {
227            self.input[self.pos + 1]
228        } else {
229            0
230        }
231    }
232
233    /// Skip whitespace.
234    fn skip_ws(&mut self) {
235        while self.ch != 0
236            && (self.ch == b' ' || self.ch == b'\t' || self.ch == b'\n' || self.ch == b'\r')
237        {
238            self.advance();
239        }
240    }
241
242    /// Read a name token (NCName).
243    fn read_name(&mut self) -> String {
244        let start = self.pos;
245        while self.ch != 0
246            && (self.ch.is_ascii_alphanumeric()
247                || self.ch == b'_'
248                || self.ch == b'-'
249                || self.ch == b'.')
250        {
251            self.advance();
252        }
253        String::from_utf8_lossy(&self.input[start..self.pos]).to_string()
254    }
255
256    /// Try to match an axis name or keyword.
257    fn try_keyword_or_axis(&self, name: &str) -> Option<Token> {
258        match name {
259            "or" => Some(Token::Or),
260            "and" => Some(Token::And),
261            "mod" => Some(Token::Mod),
262            "div" => Some(Token::Div),
263            "ancestor" => Some(Token::Ancestor),
264            "ancestor-or-self" => Some(Token::AncestorOrSelf),
265            "attribute" => Some(Token::Attribute),
266            "child" => Some(Token::Child),
267            "descendant" => Some(Token::Descendant),
268            "descendant-or-self" => Some(Token::DescendantOrSelf),
269            "following" => Some(Token::Following),
270            "following-sibling" => Some(Token::FollowingSibling),
271            "namespace" => Some(Token::Namespace),
272            "parent" => Some(Token::Parent),
273            "preceding" => Some(Token::Preceding),
274            "preceding-sibling" => Some(Token::PrecedingSibling),
275            "self" => Some(Token::Self_),
276            _ => None,
277        }
278    }
279
280    /// Read a numeric literal — a faithful port of upstream xpath.c
281    /// `xmlXPathCompNumber` (R-000166). The oracle accumulates digits
282    /// directly (`ret = ret * 10 + d`), caps the fraction at MAX_FRAC=20
283    /// digits after any leading zeros, and applies the exponent with
284    /// `pow(10.0, exp)` — which underflows to 0 for exponents below the
285    /// smallest subnormal (e.g. `5e-324`). Rust's correctly-rounded
286    /// `strtod`-style parse differs in those edge cases, so the accumulation
287    /// is reproduced exactly.
288    fn read_number(&mut self) -> f64 {
289        let input = &self.input;
290        let len = input.len();
291        let mut cur = self.pos;
292
293        // Integer part.
294        let mut ret = 0.0f64;
295        while cur < len && input[cur].is_ascii_digit() {
296            ret = ret * 10.0 + (input[cur] - b'0') as f64;
297            cur += 1;
298        }
299
300        // Fractional part (upstream consumes a trailing '.' even without
301        // digits, so `5.` is a single number literal).
302        let mut frac: i32 = 0;
303        if cur < len && input[cur] == b'.' {
304            cur += 1;
305            while cur < len && input[cur] == b'0' {
306                frac += 1;
307                cur += 1;
308            }
309            let max = frac + 20; // MAX_FRAC
310            let mut fraction = 0.0f64;
311            while cur < len && input[cur].is_ascii_digit() && frac < max {
312                let v = (input[cur] - b'0') as f64;
313                fraction = fraction * 10.0 + v;
314                frac += 1;
315                cur += 1;
316            }
317            fraction /= 10f64.powf(frac as f64);
318            ret += fraction;
319            while cur < len && input[cur].is_ascii_digit() {
320                cur += 1;
321            }
322        }
323
324        // Exponent part (upstream xmlXPathCompNumber consumes 'e'/'E'
325        // unconditionally, then an optional sign, then digits — greedily
326        // even when malformed).
327        let mut exponent: i32 = 0;
328        let mut is_exponent_negative = false;
329        if cur < len && (input[cur] == b'e' || input[cur] == b'E') {
330            cur += 1;
331            if cur < len && input[cur] == b'-' {
332                is_exponent_negative = true;
333                cur += 1;
334            } else if cur < len && input[cur] == b'+' {
335                cur += 1;
336            }
337            while cur < len && input[cur].is_ascii_digit() {
338                if exponent < 1000000 {
339                    exponent = exponent * 10 + (input[cur] - b'0') as i32;
340                }
341                cur += 1;
342            }
343        }
344        if is_exponent_negative {
345            exponent = -exponent;
346        }
347        ret *= 10f64.powf(exponent as f64);
348
349        self.pos = cur;
350        self.ch = if cur < len { input[cur] } else { 0 };
351        ret
352    }
353
354    /// Read a string literal.
355    fn read_string(&mut self, quote: u8) -> String {
356        self.advance(); // consume opening quote
357        let start = self.pos;
358        while self.ch != 0 && self.ch != quote {
359            self.advance();
360        }
361        let s = String::from_utf8_lossy(&self.input[start..self.pos]).to_string();
362        if self.ch == quote {
363            self.advance(); // consume closing quote
364        }
365        s
366    }
367
368    /// Get the next token.
369    pub fn next_token(&mut self) -> Token {
370        self.skip_ws();
371
372        if self.ch == 0 {
373            return Token::Eof;
374        }
375
376        // Save at_start for unary minus detection
377        let _was_at_start = self.at_start;
378        self.at_start = false;
379
380        // ── Single-char tokens ────────────────────────────────────────────
381        match self.ch {
382            b'(' => {
383                self.advance();
384                return Token::LParen;
385            }
386            b')' => {
387                self.advance();
388                return Token::RParen;
389            }
390            b'[' => {
391                self.advance();
392                return Token::LBracket;
393            }
394            b']' => {
395                self.advance();
396                return Token::RBracket;
397            }
398            b'{' => {
399                self.advance();
400                return Token::LBrace;
401            }
402            b'}' => {
403                self.advance();
404                return Token::RBrace;
405            }
406            b',' => {
407                self.advance();
408                return Token::Comma;
409            }
410            b'$' => {
411                self.advance();
412                return Token::Dollar;
413            }
414            b'|' => {
415                self.advance();
416                return Token::Pipe;
417            }
418            b'+' => {
419                self.advance();
420                return Token::Plus;
421            }
422            b'@' => {
423                self.advance();
424                return Token::At;
425            }
426            b'.' => {
427                if self.peek() == b'.' {
428                    self.advance();
429                    self.advance();
430                    return Token::DotDot;
431                }
432                // Check if it's a number starting with '.'
433                if self.peek().is_ascii_digit() {
434                    return Token::NumberLiteral(self.read_number());
435                }
436                self.advance();
437                return Token::Dot;
438            }
439            b'-' => {
440                self.advance();
441                // If at start or after operator, this is unary minus
442                // We handle this at the parser level, just return Minus
443                return Token::Minus;
444            }
445            b'=' => {
446                self.advance();
447                return Token::Eq;
448            }
449            b'!' => {
450                if self.peek() == b'=' {
451                    self.advance();
452                    self.advance();
453                    return Token::Ne;
454                }
455                // Invalid character, skip
456                self.advance();
457                return self.next_token();
458            }
459            b'<' => {
460                self.advance();
461                if self.ch == b'=' {
462                    self.advance();
463                    return Token::Le;
464                }
465                return Token::Lt;
466            }
467            b'>' => {
468                self.advance();
469                if self.ch == b'=' {
470                    self.advance();
471                    return Token::Ge;
472                }
473                return Token::Gt;
474            }
475            b'/' => {
476                self.advance();
477                if self.ch == b'/' {
478                    self.advance();
479                    return Token::DoubleSlash;
480                }
481                return Token::Slash;
482            }
483            b'*' => {
484                self.advance();
485                return Token::Star; // lexer returns Star; parser disambiguates
486            }
487            b':' => {
488                if self.peek() == b':' {
489                    self.advance();
490                    self.advance();
491                    return Token::DoubleColon;
492                }
493                // Single colon is part of a QName, handled below
494                // Actually, if we see a colon, it should be part of a name
495                // This case handles axis::name or prefix:name
496                // Since we read the full name first, this shouldn't normally happen alone
497                self.advance();
498                return self.next_token();
499            }
500            b'\'' | b'"' => {
501                let quote = self.ch;
502                let s = self.read_string(quote);
503                return Token::StringLiteral(s);
504            }
505            _ => {}
506        }
507
508        // ── Number ───────────────────────────────────────────────────────
509        if self.ch.is_ascii_digit() {
510            return Token::NumberLiteral(self.read_number());
511        }
512
513        // ── Name ─────────────────────────────────────────────────────────
514        if self.ch.is_ascii_alphabetic() || self.ch == b'_' {
515            let name = self.read_name();
516
517            // Check for QName (prefix:local)
518            if self.ch == b':' && self.peek() != b':' {
519                self.advance(); // consume ':'
520                if self.ch.is_ascii_alphabetic() || self.ch == b'_' || self.ch == b'*' {
521                    if self.ch == b'*' {
522                        self.advance();
523                        let full = format!("{}:*", name);
524                        return Token::Name(full);
525                    }
526                    let local = self.read_name();
527                    return Token::Name(format!("{}:{}", name, local));
528                }
529                // If the colon is not followed by a valid name character,
530                // it might be an axis separator that got split. Push back?
531                // Actually in well-formed XPath, `name:` is followed by `:`
532                // for axis:: or by a local name for QName.
533                // We already checked peek != ':', so this is a QName prefix.
534                // If the local part is missing, treat the whole thing as a name.
535                return Token::Name(name);
536            }
537
538            // Check for axis separator: name::
539            // We DON'T consume the :: here — we return just the axis keyword token.
540            // The :: will be tokenized as DoubleColon on the next call to next_token().
541            if self.ch == b':' && self.peek() == b':' {
542                if let Some(axis) = self.try_keyword_or_axis(&name) {
543                    return axis;
544                }
545                // Not an axis keyword — could be a QName prefix followed by ::?
546                // Treat it as a regular name and let the :: be consumed separately.
547                return Token::Name(name);
548            }
549
550            // Check for keyword or axis
551            if let Some(keyword) = self.try_keyword_or_axis(&name) {
552                return keyword;
553            }
554
555            return Token::Name(name);
556        }
557
558        // Unknown character, skip
559        self.advance();
560        self.next_token()
561    }
562}
563
564// ═══════════════════════════════════════════════════════════════════════════════
565// Tests
566// ═══════════════════════════════════════════════════════════════════════════════
567
568#[cfg(test)]
569mod tests {
570    use super::*;
571
572    fn tokenize(s: &str) -> Vec<Token> {
573        let mut lexer = Lexer::new(s);
574        let mut tokens = Vec::new();
575        loop {
576            let tok = lexer.next_token();
577            let is_eof = matches!(tok, Token::Eof);
578            tokens.push(tok);
579            if is_eof {
580                break;
581            }
582        }
583        tokens
584    }
585
586    #[test]
587    fn test_empty() {
588        let tokens = tokenize("");
589        assert_eq!(tokens.len(), 1);
590        assert_eq!(tokens[0], Token::Eof);
591    }
592
593    #[test]
594    fn test_simple_path() {
595        let tokens = tokenize("child::para");
596        assert_eq!(
597            tokens,
598            vec![
599                Token::Child,
600                Token::DoubleColon,
601                Token::Name("para".into()),
602                Token::Eof,
603            ]
604        );
605    }
606
607    #[test]
608    fn test_absolute_path() {
609        let tokens = tokenize("/child::para");
610        assert_eq!(
611            tokens,
612            vec![
613                Token::Slash,
614                Token::Child,
615                Token::DoubleColon,
616                Token::Name("para".into()),
617                Token::Eof,
618            ]
619        );
620    }
621
622    #[test]
623    fn test_short_form() {
624        let tokens = tokenize("para");
625        assert_eq!(tokens, vec![Token::Name("para".into()), Token::Eof]);
626    }
627
628    #[test]
629    fn test_attribute() {
630        let tokens = tokenize("@attr");
631        assert_eq!(
632            tokens,
633            vec![Token::At, Token::Name("attr".into()), Token::Eof]
634        );
635    }
636
637    #[test]
638    fn test_predicate() {
639        let tokens = tokenize("para[1]");
640        assert_eq!(
641            tokens,
642            vec![
643                Token::Name("para".into()),
644                Token::LBracket,
645                Token::NumberLiteral(1.0),
646                Token::RBracket,
647                Token::Eof,
648            ]
649        );
650    }
651
652    #[test]
653    fn test_function_call() {
654        let tokens = tokenize("position()");
655        assert_eq!(
656            tokens,
657            vec![
658                Token::Name("position".into()),
659                Token::LParen,
660                Token::RParen,
661                Token::Eof,
662            ]
663        );
664    }
665
666    #[test]
667    fn test_string_literal() {
668        let tokens = tokenize("'hello'");
669        assert_eq!(
670            tokens,
671            vec![Token::StringLiteral("hello".into()), Token::Eof]
672        );
673    }
674
675    #[test]
676    fn test_number() {
677        let tokens = tokenize("42");
678        assert_eq!(tokens, vec![Token::NumberLiteral(42.0), Token::Eof]);
679    }
680    #[allow(clippy::approx_constant)]
681    #[test]
682    fn test_decimal() {
683        let tokens = tokenize("3.14");
684        assert_eq!(tokens, vec![Token::NumberLiteral(3.14), Token::Eof]);
685    }
686
687    #[test]
688    fn test_operators() {
689        let tokens = tokenize("a = b and c != d or e < f");
690        assert!(tokens.contains(&Token::Eq));
691        assert!(tokens.contains(&Token::And));
692        assert!(tokens.contains(&Token::Ne));
693        assert!(tokens.contains(&Token::Or));
694        assert!(tokens.contains(&Token::Lt));
695    }
696
697    #[test]
698    fn test_union() {
699        let tokens = tokenize("a | b");
700        assert_eq!(
701            tokens,
702            vec![
703                Token::Name("a".into()),
704                Token::Pipe,
705                Token::Name("b".into()),
706                Token::Eof,
707            ]
708        );
709    }
710
711    #[test]
712    fn test_double_slash() {
713        let tokens = tokenize("//para");
714        assert_eq!(
715            tokens,
716            vec![Token::DoubleSlash, Token::Name("para".into()), Token::Eof]
717        );
718    }
719
720    #[test]
721    fn test_qname() {
722        let tokens = tokenize("xslt:template");
723        assert_eq!(
724            tokens,
725            vec![Token::Name("xslt:template".into()), Token::Eof]
726        );
727    }
728
729    #[test]
730    fn test_wildcard() {
731        let tokens = tokenize("*");
732        assert_eq!(tokens, vec![Token::Star, Token::Eof]);
733    }
734
735    #[test]
736    fn test_ns_wildcard() {
737        let tokens = tokenize("ns:*");
738        assert_eq!(tokens, vec![Token::Name("ns:*".into()), Token::Eof]);
739    }
740
741    #[test]
742    fn test_dot_dot() {
743        let tokens = tokenize("..");
744        assert_eq!(tokens, vec![Token::DotDot, Token::Eof]);
745    }
746
747    #[test]
748    fn test_axis_keyword() {
749        let tokens = tokenize("ancestor-or-self::node()");
750        assert_eq!(
751            tokens,
752            vec![
753                Token::AncestorOrSelf,
754                Token::DoubleColon,
755                Token::Name("node".into()),
756                Token::LParen,
757                Token::RParen,
758                Token::Eof,
759            ]
760        );
761    }
762
763    #[test]
764    fn test_complex_expression() {
765        let tokens = tokenize("/html/body//div[@class='main']/p[1]");
766        // Collect name-like tokens (including keyword tokens that can be element names)
767        let names: Vec<String> = tokens
768            .iter()
769            .filter_map(|t| match t {
770                Token::Name(n) => Some(n.clone()),
771                Token::Div => Some("div".to_string()),
772                Token::Mod => Some("mod".to_string()),
773                Token::And => Some("and".to_string()),
774                Token::Or => Some("or".to_string()),
775                _ => None,
776            })
777            .collect();
778        assert_eq!(names, vec!["html", "body", "div", "class", "p"]);
779    }
780
781    #[test]
782    fn test_variable() {
783        let tokens = tokenize("$var");
784        assert_eq!(
785            tokens,
786            vec![Token::Dollar, Token::Name("var".into()), Token::Eof]
787        );
788    }
789}
libxml_rs/xml/xpath/lexer.rs

libxml_rs/xml/xpath/
lexer.rs
