uqa_graph/cypher/
lexer.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Cypher tokenizer. Produces a flat [`Token`] vector consumed by the
8//! recursive-descent parser. Keywords are case-insensitive — they
9//! arrive as `Identifier` tokens whose uppercased text the parser
10//! matches against keyword strings.
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum TokenKind {
14    Integer,
15    Float,
16    String,
17    Identifier,
18    LParen,
19    RParen,
20    LBracket,
21    RBracket,
22    LBrace,
23    RBrace,
24    Colon,
25    Comma,
26    Dot,
27    DotDot,
28    Pipe,
29    Dollar,
30    Plus,
31    Minus,
32    Star,
33    Slash,
34    Percent,
35    Caret,
36    Eq,
37    Neq,
38    Lt,
39    Gt,
40    Lte,
41    Gte,
42    PlusEq,
43    /// `=~` regular-expression match operator.
44    RegexMatch,
45    ArrowRight,
46    ArrowLeft,
47    Eof,
48}
49
50#[derive(Debug, Clone)]
51pub struct Token {
52    pub kind: TokenKind,
53    pub value: String,
54    pub pos: usize,
55}
56
57#[derive(Debug, thiserror::Error, PartialEq, Eq)]
58pub enum LexError {
59    #[error("unexpected character {ch:?} at position {position}")]
60    UnexpectedChar { ch: char, position: usize },
61    #[error("unterminated string starting at position {position}")]
62    UnterminatedString { position: usize },
63    #[error("unterminated backtick identifier at position {position}")]
64    UnterminatedBacktick { position: usize },
65}
66
67pub fn tokenize(source: &str) -> Result<Vec<Token>, LexError> {
68    let bytes = source.as_bytes();
69    let n = bytes.len();
70    let mut tokens = Vec::new();
71    let mut i = 0;
72    while i < n {
73        let ch = bytes[i] as char;
74        if ch.is_ascii_whitespace() {
75            i += 1;
76            continue;
77        }
78        if let Some(next) = skip_comment(bytes, i) {
79            i = next;
80            continue;
81        }
82        if ch == '\'' || ch == '"' {
83            let (tok, next) = scan_string(source, i, ch)?;
84            tokens.push(tok);
85            i = next;
86            continue;
87        }
88        if ch.is_ascii_digit()
89            || (ch == '.' && i + 1 < n && (bytes[i + 1] as char).is_ascii_digit())
90        {
91            let (tok, next) = scan_number(source, i);
92            tokens.push(tok);
93            i = next;
94            continue;
95        }
96        if ch.is_ascii_alphabetic() || ch == '_' {
97            let (tok, next) = scan_ident(source, i);
98            tokens.push(tok);
99            i = next;
100            continue;
101        }
102        if ch == '`' {
103            let (tok, next) = scan_backtick_ident(source, i)?;
104            tokens.push(tok);
105            i = next;
106            continue;
107        }
108        if let Some((tok, next)) = scan_two_char_symbol(source, i) {
109            tokens.push(tok);
110            i = next;
111            continue;
112        }
113        let kind = single_char_kind(ch).ok_or(LexError::UnexpectedChar { ch, position: i })?;
114        tokens.push(Token {
115            kind,
116            value: ch.to_string(),
117            pos: i,
118        });
119        i += 1;
120    }
121    tokens.push(Token {
122        kind: TokenKind::Eof,
123        value: String::new(),
124        pos: n,
125    });
126    Ok(tokens)
127}
128
129/// If `bytes[i..]` starts a `//` or `/* */` comment, return the index
130/// just past the comment; otherwise `None`.
131fn skip_comment(bytes: &[u8], i: usize) -> Option<usize> {
132    let n = bytes.len();
133    if !(i + 1 < n && bytes[i] == b'/') {
134        return None;
135    }
136    match bytes[i + 1] {
137        b'/' => {
138            let mut j = i;
139            while j < n && bytes[j] != b'\n' {
140                j += 1;
141            }
142            Some(j)
143        }
144        b'*' => {
145            let mut j = i + 2;
146            while j + 1 < n && !(bytes[j] == b'*' && bytes[j + 1] == b'/') {
147                j += 1;
148            }
149            Some((j + 2).min(n))
150        }
151        _ => None,
152    }
153}
154
155fn scan_two_char_symbol(source: &str, i: usize) -> Option<(Token, usize)> {
156    if i + 2 > source.len() {
157        return None;
158    }
159    let bytes = source.as_bytes();
160    let pair = (bytes[i], bytes[i + 1]);
161    let kind = match pair {
162        (b'<', b'>') => TokenKind::Neq,
163        (b'<', b'=') => TokenKind::Lte,
164        (b'>', b'=') => TokenKind::Gte,
165        (b'-', b'>') => TokenKind::ArrowRight,
166        (b'<', b'-') => TokenKind::ArrowLeft,
167        (b'+', b'=') => TokenKind::PlusEq,
168        (b'=', b'~') => TokenKind::RegexMatch,
169        (b'.', b'.') => TokenKind::DotDot,
170        _ => return None,
171    };
172    // The match above only succeeds when both bytes are ASCII, so
173    // building a 2-char ASCII string from them is safe.
174    let value = String::from_iter([char::from(pair.0), char::from(pair.1)]);
175    Some((
176        Token {
177            kind,
178            value,
179            pos: i,
180        },
181        i + 2,
182    ))
183}
184
185fn single_char_kind(ch: char) -> Option<TokenKind> {
186    Some(match ch {
187        '(' => TokenKind::LParen,
188        ')' => TokenKind::RParen,
189        '[' => TokenKind::LBracket,
190        ']' => TokenKind::RBracket,
191        '{' => TokenKind::LBrace,
192        '}' => TokenKind::RBrace,
193        ':' => TokenKind::Colon,
194        ',' => TokenKind::Comma,
195        '.' => TokenKind::Dot,
196        '|' => TokenKind::Pipe,
197        '$' => TokenKind::Dollar,
198        '+' => TokenKind::Plus,
199        '-' => TokenKind::Minus,
200        '*' => TokenKind::Star,
201        '/' => TokenKind::Slash,
202        '%' => TokenKind::Percent,
203        '^' => TokenKind::Caret,
204        '=' => TokenKind::Eq,
205        '<' => TokenKind::Lt,
206        '>' => TokenKind::Gt,
207        _ => return None,
208    })
209}
210
211fn scan_string(source: &str, start: usize, quote: char) -> Result<(Token, usize), LexError> {
212    // Iterate proper UTF-8 chars over the body of the string literal,
213    // not raw bytes — a previous bytewise loop silently corrupted any
214    // non-ASCII codepoint by reinterpreting each byte as Latin-1.
215    let body_start = start + quote.len_utf8();
216    let mut buf = String::new();
217    let mut iter = source[body_start..].char_indices().peekable();
218    while let Some((rel, ch)) = iter.next() {
219        let abs = body_start + rel;
220        if ch == '\\' {
221            if let Some((_, esc)) = iter.next() {
222                let mapped = match esc {
223                    'n' => '\n',
224                    't' => '\t',
225                    'r' => '\r',
226                    '\\' => '\\',
227                    _ if esc == quote => quote,
228                    _ => esc,
229                };
230                buf.push(mapped);
231                continue;
232            }
233            return Err(LexError::UnterminatedString { position: start });
234        }
235        if ch == quote {
236            // Doubled quote escapes the quote inside the same quote.
237            if let Some((_, next)) = iter.peek() {
238                if *next == quote {
239                    iter.next();
240                    buf.push(quote);
241                    continue;
242                }
243            }
244            return Ok((
245                Token {
246                    kind: TokenKind::String,
247                    value: buf,
248                    pos: start,
249                },
250                abs + ch.len_utf8(),
251            ));
252        }
253        buf.push(ch);
254    }
255    Err(LexError::UnterminatedString { position: start })
256}
257
258fn scan_number(source: &str, start: usize) -> (Token, usize) {
259    let bytes = source.as_bytes();
260    let n = bytes.len();
261    let mut i = start;
262    let mut has_dot = false;
263    while i < n {
264        let ch = bytes[i] as char;
265        if ch.is_ascii_digit() {
266            i += 1;
267            continue;
268        }
269        if ch == '.' {
270            if has_dot {
271                break;
272            }
273            // Stop on `..` (range) or `.<non-digit>` (method/property access).
274            if i + 1 < n && bytes[i + 1] as char == '.' {
275                break;
276            }
277            if i + 1 < n && !(bytes[i + 1] as char).is_ascii_digit() {
278                break;
279            }
280            has_dot = true;
281            i += 1;
282            continue;
283        }
284        break;
285    }
286    if i < n && (bytes[i] as char == 'e' || bytes[i] as char == 'E') {
287        i += 1;
288        if i < n && (bytes[i] as char == '+' || bytes[i] as char == '-') {
289            i += 1;
290        }
291        while i < n && (bytes[i] as char).is_ascii_digit() {
292            i += 1;
293        }
294        has_dot = true;
295    }
296    let text = &source[start..i];
297    let kind = if has_dot {
298        TokenKind::Float
299    } else {
300        TokenKind::Integer
301    };
302    (
303        Token {
304            kind,
305            value: text.to_string(),
306            pos: start,
307        },
308        i,
309    )
310}
311
312fn scan_ident(source: &str, start: usize) -> (Token, usize) {
313    let bytes = source.as_bytes();
314    let n = bytes.len();
315    let mut i = start;
316    while i < n {
317        let ch = bytes[i] as char;
318        if ch.is_ascii_alphanumeric() || ch == '_' {
319            i += 1;
320        } else {
321            break;
322        }
323    }
324    let text = &source[start..i];
325    (
326        Token {
327            kind: TokenKind::Identifier,
328            value: text.to_string(),
329            pos: start,
330        },
331        i,
332    )
333}
334
335fn scan_backtick_ident(source: &str, start: usize) -> Result<(Token, usize), LexError> {
336    let bytes = source.as_bytes();
337    let n = bytes.len();
338    let mut i = start + 1;
339    while i < n && bytes[i] as char != '`' {
340        i += 1;
341    }
342    if i >= n {
343        return Err(LexError::UnterminatedBacktick { position: start });
344    }
345    let text = &source[start + 1..i];
346    Ok((
347        Token {
348            kind: TokenKind::Identifier,
349            value: text.to_string(),
350            pos: start,
351        },
352        i + 1,
353    ))
354}
355
356/// `true` if the token is an identifier whose uppercased text matches.
357pub fn is_keyword(token: &Token, keyword: &str) -> bool {
358    token.kind == TokenKind::Identifier && token.value.eq_ignore_ascii_case(keyword)
359}
360
361#[cfg(test)]
362mod tests {
363    use super::*;
364
365    fn kinds(src: &str) -> Vec<TokenKind> {
366        tokenize(src).unwrap().iter().map(|t| t.kind).collect()
367    }
368
369    #[test]
370    fn tokenize_basic_query() {
371        let ks = kinds("MATCH (n:Person) RETURN n.name");
372        assert_eq!(
373            ks,
374            vec![
375                TokenKind::Identifier,
376                TokenKind::LParen,
377                TokenKind::Identifier,
378                TokenKind::Colon,
379                TokenKind::Identifier,
380                TokenKind::RParen,
381                TokenKind::Identifier,
382                TokenKind::Identifier,
383                TokenKind::Dot,
384                TokenKind::Identifier,
385                TokenKind::Eof,
386            ]
387        );
388    }
389
390    #[test]
391    fn tokenize_arrow_and_range() {
392        let toks = tokenize("[*1..3]->").unwrap();
393        let kinds: Vec<TokenKind> = toks.iter().map(|t| t.kind).collect();
394        assert_eq!(
395            kinds,
396            vec![
397                TokenKind::LBracket,
398                TokenKind::Star,
399                TokenKind::Integer,
400                TokenKind::DotDot,
401                TokenKind::Integer,
402                TokenKind::RBracket,
403                TokenKind::ArrowRight,
404                TokenKind::Eof,
405            ]
406        );
407    }
408
409    #[test]
410    fn tokenize_strings_and_escapes() {
411        let toks = tokenize(r#"'a''b' "c\n""#).unwrap();
412        assert_eq!(toks[0].kind, TokenKind::String);
413        assert_eq!(toks[0].value, "a'b");
414        assert_eq!(toks[1].kind, TokenKind::String);
415        assert_eq!(toks[1].value, "c\n");
416    }
417
418    #[test]
419    fn tokenize_numbers() {
420        let toks = tokenize("1 2.5 1e3 1.2e-4").unwrap();
421        assert_eq!(toks[0].kind, TokenKind::Integer);
422        assert_eq!(toks[1].kind, TokenKind::Float);
423        assert_eq!(toks[2].kind, TokenKind::Float);
424        assert_eq!(toks[3].kind, TokenKind::Float);
425    }
426
427    #[test]
428    fn tokenize_skips_comments() {
429        let toks = tokenize("MATCH // comment\n n /* block */ RETURN n").unwrap();
430        let kinds: Vec<TokenKind> = toks.iter().map(|t| t.kind).collect();
431        assert!(kinds.iter().all(|k| !matches!(k, TokenKind::Slash)));
432    }
433
434    #[test]
435    fn keyword_match_case_insensitive() {
436        let toks = tokenize("match").unwrap();
437        assert!(is_keyword(&toks[0], "MATCH"));
438    }
439
440    #[test]
441    fn backtick_identifier_preserves_inner_text() {
442        let toks = tokenize("`spaced name`").unwrap();
443        assert_eq!(toks[0].kind, TokenKind::Identifier);
444        assert_eq!(toks[0].value, "spaced name");
445    }
446}
uqa_graph/cypher/lexer.rs

uqa_graph/cypher/
lexer.rs
