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 number literal.
272    fn read_number(&mut self) -> f64 {
273        let start = self.pos;
274        // Integer part
275        while self.ch != 0 && self.ch.is_ascii_digit() {
276            self.advance();
277        }
278        // Fractional part
279        if self.ch == b'.' && self.peek().is_ascii_digit() {
280            self.advance(); // consume '.'
281            while self.ch != 0 && self.ch.is_ascii_digit() {
282                self.advance();
283            }
284        }
285        let s = String::from_utf8_lossy(&self.input[start..self.pos]).to_string();
286        s.parse::<f64>().unwrap_or(0.0)
287    }
288
289    /// Read a string literal.
290    fn read_string(&mut self, quote: u8) -> String {
291        self.advance(); // consume opening quote
292        let start = self.pos;
293        while self.ch != 0 && self.ch != quote {
294            self.advance();
295        }
296        let s = String::from_utf8_lossy(&self.input[start..self.pos]).to_string();
297        if self.ch == quote {
298            self.advance(); // consume closing quote
299        }
300        s
301    }
302
303    /// Get the next token.
304    pub fn next_token(&mut self) -> Token {
305        self.skip_ws();
306
307        if self.ch == 0 {
308            return Token::Eof;
309        }
310
311        // Save at_start for unary minus detection
312        let was_at_start = self.at_start;
313        self.at_start = false;
314
315        // ── Single-char tokens ────────────────────────────────────────────
316        match self.ch {
317            b'(' => {
318                self.advance();
319                return Token::LParen;
320            }
321            b')' => {
322                self.advance();
323                return Token::RParen;
324            }
325            b'[' => {
326                self.advance();
327                return Token::LBracket;
328            }
329            b']' => {
330                self.advance();
331                return Token::RBracket;
332            }
333            b'{' => {
334                self.advance();
335                return Token::LBrace;
336            }
337            b'}' => {
338                self.advance();
339                return Token::RBrace;
340            }
341            b',' => {
342                self.advance();
343                return Token::Comma;
344            }
345            b'$' => {
346                self.advance();
347                return Token::Dollar;
348            }
349            b'|' => {
350                self.advance();
351                return Token::Pipe;
352            }
353            b'+' => {
354                self.advance();
355                return Token::Plus;
356            }
357            b'@' => {
358                self.advance();
359                return Token::At;
360            }
361            b'.' => {
362                if self.peek() == b'.' {
363                    self.advance();
364                    self.advance();
365                    return Token::DotDot;
366                }
367                // Check if it's a number starting with '.'
368                if self.peek().is_ascii_digit() {
369                    return Token::NumberLiteral(self.read_number());
370                }
371                self.advance();
372                return Token::Dot;
373            }
374            b'-' => {
375                self.advance();
376                // If at start or after operator, this is unary minus
377                // We handle this at the parser level, just return Minus
378                return Token::Minus;
379            }
380            b'=' => {
381                self.advance();
382                return Token::Eq;
383            }
384            b'!' => {
385                if self.peek() == b'=' {
386                    self.advance();
387                    self.advance();
388                    return Token::Ne;
389                }
390                // Invalid character, skip
391                self.advance();
392                return self.next_token();
393            }
394            b'<' => {
395                self.advance();
396                if self.ch == b'=' {
397                    self.advance();
398                    return Token::Le;
399                }
400                return Token::Lt;
401            }
402            b'>' => {
403                self.advance();
404                if self.ch == b'=' {
405                    self.advance();
406                    return Token::Ge;
407                }
408                return Token::Gt;
409            }
410            b'/' => {
411                self.advance();
412                if self.ch == b'/' {
413                    self.advance();
414                    return Token::DoubleSlash;
415                }
416                return Token::Slash;
417            }
418            b'*' => {
419                self.advance();
420                return Token::Star; // lexer returns Star; parser disambiguates
421            }
422            b':' => {
423                if self.peek() == b':' {
424                    self.advance();
425                    self.advance();
426                    return Token::DoubleColon;
427                }
428                // Single colon is part of a QName, handled below
429                // Actually, if we see a colon, it should be part of a name
430                // This case handles axis::name or prefix:name
431                // Since we read the full name first, this shouldn't normally happen alone
432                self.advance();
433                return self.next_token();
434            }
435            b'\'' | b'"' => {
436                let quote = self.ch;
437                let s = self.read_string(quote);
438                return Token::StringLiteral(s);
439            }
440            _ => {}
441        }
442
443        // ── Number ───────────────────────────────────────────────────────
444        if self.ch.is_ascii_digit() {
445            return Token::NumberLiteral(self.read_number());
446        }
447
448        // ── Name ─────────────────────────────────────────────────────────
449        if self.ch.is_ascii_alphabetic() || self.ch == b'_' {
450            let name = self.read_name();
451
452            // Check for QName (prefix:local)
453            if self.ch == b':' && self.peek() != b':' {
454                self.advance(); // consume ':'
455                if self.ch.is_ascii_alphabetic() || self.ch == b'_' || self.ch == b'*' {
456                    if self.ch == b'*' {
457                        self.advance();
458                        let full = format!("{}:*", name);
459                        return Token::Name(full);
460                    }
461                    let local = self.read_name();
462                    return Token::Name(format!("{}:{}", name, local));
463                }
464                // If the colon is not followed by a valid name character,
465                // it might be an axis separator that got split. Push back?
466                // Actually in well-formed XPath, `name:` is followed by `:`
467                // for axis:: or by a local name for QName.
468                // We already checked peek != ':', so this is a QName prefix.
469                // If the local part is missing, treat the whole thing as a name.
470                return Token::Name(name);
471            }
472
473            // Check for axis separator: name::
474            // We DON'T consume the :: here — we return just the axis keyword token.
475            // The :: will be tokenized as DoubleColon on the next call to next_token().
476            if self.ch == b':' && self.peek() == b':' {
477                if let Some(axis) = self.try_keyword_or_axis(&name) {
478                    return axis;
479                }
480                // Not an axis keyword — could be a QName prefix followed by ::?
481                // Treat it as a regular name and let the :: be consumed separately.
482                return Token::Name(name);
483            }
484
485            // Check for keyword or axis
486            if let Some(keyword) = self.try_keyword_or_axis(&name) {
487                return keyword;
488            }
489
490            return Token::Name(name);
491        }
492
493        // Unknown character, skip
494        self.advance();
495        self.next_token()
496    }
497}
498
499// ═══════════════════════════════════════════════════════════════════════════════
500// Tests
501// ═══════════════════════════════════════════════════════════════════════════════
502
503#[cfg(test)]
504mod tests {
505    use super::*;
506
507    fn tokenize(s: &str) -> Vec<Token> {
508        let mut lexer = Lexer::new(s);
509        let mut tokens = Vec::new();
510        loop {
511            let tok = lexer.next_token();
512            let is_eof = matches!(tok, Token::Eof);
513            tokens.push(tok);
514            if is_eof {
515                break;
516            }
517        }
518        tokens
519    }
520
521    #[test]
522    fn test_empty() {
523        let tokens = tokenize("");
524        assert_eq!(tokens.len(), 1);
525        assert_eq!(tokens[0], Token::Eof);
526    }
527
528    #[test]
529    fn test_simple_path() {
530        let tokens = tokenize("child::para");
531        assert_eq!(
532            tokens,
533            vec![
534                Token::Child,
535                Token::DoubleColon,
536                Token::Name("para".into()),
537                Token::Eof,
538            ]
539        );
540    }
541
542    #[test]
543    fn test_absolute_path() {
544        let tokens = tokenize("/child::para");
545        assert_eq!(
546            tokens,
547            vec![
548                Token::Slash,
549                Token::Child,
550                Token::DoubleColon,
551                Token::Name("para".into()),
552                Token::Eof,
553            ]
554        );
555    }
556
557    #[test]
558    fn test_short_form() {
559        let tokens = tokenize("para");
560        assert_eq!(tokens, vec![Token::Name("para".into()), Token::Eof]);
561    }
562
563    #[test]
564    fn test_attribute() {
565        let tokens = tokenize("@attr");
566        assert_eq!(
567            tokens,
568            vec![Token::At, Token::Name("attr".into()), Token::Eof]
569        );
570    }
571
572    #[test]
573    fn test_predicate() {
574        let tokens = tokenize("para[1]");
575        assert_eq!(
576            tokens,
577            vec![
578                Token::Name("para".into()),
579                Token::LBracket,
580                Token::NumberLiteral(1.0),
581                Token::RBracket,
582                Token::Eof,
583            ]
584        );
585    }
586
587    #[test]
588    fn test_function_call() {
589        let tokens = tokenize("position()");
590        assert_eq!(
591            tokens,
592            vec![
593                Token::Name("position".into()),
594                Token::LParen,
595                Token::RParen,
596                Token::Eof,
597            ]
598        );
599    }
600
601    #[test]
602    fn test_string_literal() {
603        let tokens = tokenize("'hello'");
604        assert_eq!(
605            tokens,
606            vec![Token::StringLiteral("hello".into()), Token::Eof]
607        );
608    }
609
610    #[test]
611    fn test_number() {
612        let tokens = tokenize("42");
613        assert_eq!(tokens, vec![Token::NumberLiteral(42.0), Token::Eof]);
614    }
615
616    #[test]
617    fn test_decimal() {
618        let tokens = tokenize("3.14");
619        assert_eq!(tokens, vec![Token::NumberLiteral(3.14), Token::Eof]);
620    }
621
622    #[test]
623    fn test_operators() {
624        let tokens = tokenize("a = b and c != d or e < f");
625        assert!(tokens.contains(&Token::Eq));
626        assert!(tokens.contains(&Token::And));
627        assert!(tokens.contains(&Token::Ne));
628        assert!(tokens.contains(&Token::Or));
629        assert!(tokens.contains(&Token::Lt));
630    }
631
632    #[test]
633    fn test_union() {
634        let tokens = tokenize("a | b");
635        assert_eq!(
636            tokens,
637            vec![
638                Token::Name("a".into()),
639                Token::Pipe,
640                Token::Name("b".into()),
641                Token::Eof,
642            ]
643        );
644    }
645
646    #[test]
647    fn test_double_slash() {
648        let tokens = tokenize("//para");
649        assert_eq!(
650            tokens,
651            vec![Token::DoubleSlash, Token::Name("para".into()), Token::Eof]
652        );
653    }
654
655    #[test]
656    fn test_qname() {
657        let tokens = tokenize("xslt:template");
658        assert_eq!(
659            tokens,
660            vec![Token::Name("xslt:template".into()), Token::Eof]
661        );
662    }
663
664    #[test]
665    fn test_wildcard() {
666        let tokens = tokenize("*");
667        assert_eq!(tokens, vec![Token::Star, Token::Eof]);
668    }
669
670    #[test]
671    fn test_ns_wildcard() {
672        let tokens = tokenize("ns:*");
673        assert_eq!(tokens, vec![Token::Name("ns:*".into()), Token::Eof]);
674    }
675
676    #[test]
677    fn test_dot_dot() {
678        let tokens = tokenize("..");
679        assert_eq!(tokens, vec![Token::DotDot, Token::Eof]);
680    }
681
682    #[test]
683    fn test_axis_keyword() {
684        let tokens = tokenize("ancestor-or-self::node()");
685        assert_eq!(
686            tokens,
687            vec![
688                Token::AncestorOrSelf,
689                Token::DoubleColon,
690                Token::Name("node".into()),
691                Token::LParen,
692                Token::RParen,
693                Token::Eof,
694            ]
695        );
696    }
697
698    #[test]
699    fn test_complex_expression() {
700        let tokens = tokenize("/html/body//div[@class='main']/p[1]");
701        // Collect name-like tokens (including keyword tokens that can be element names)
702        let names: Vec<String> = tokens
703            .iter()
704            .filter_map(|t| match t {
705                Token::Name(n) => Some(n.clone()),
706                Token::Div => Some("div".to_string()),
707                Token::Mod => Some("mod".to_string()),
708                Token::And => Some("and".to_string()),
709                Token::Or => Some("or".to_string()),
710                _ => None,
711            })
712            .collect();
713        assert_eq!(names, vec!["html", "body", "div", "class", "p"]);
714    }
715
716    #[test]
717    fn test_variable() {
718        let tokens = tokenize("$var");
719        assert_eq!(
720            tokens,
721            vec![Token::Dollar, Token::Name("var".into()), Token::Eof]
722        );
723    }
724}
libxml_rs/xml/xpath/lexer.rs

libxml_rs/xml/xpath/
lexer.rs
