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

libxml_rs/xml/xpath/
lexer.rs
