qualia_core_db/sparql_library/sparql_grammar/
tokenizer.rs

1//! SPARQL tokenizer.
2//!
3//! Turns a SPARQL fragment (a FILTER/BIND expression, or a group graph pattern)
4//! into a flat `Vec<Token>` that the expression and pattern parsers consume by
5//! recursive descent. This is the front-end the old string-slicing parser never
6//! had — the AST, planner, and executor already support the full algebra, so a
7//! real tokenizer + parser is all that stands between a query string and the
8//! engine.
9//!
10//! Not zero-heap: parsing is a cold, one-shot path per query (unlike execution),
11//! so a `Vec<Token>` + `String` interning is the right trade for correctness and
12//! clarity. Execution stays on the zero-heap `SparqlQueryContext` arenas.
13
14/// A lexical token.
15#[derive(Debug, Clone, PartialEq)]
16pub enum Token {
17    /// `?x` or `$x` — the leading sigil is kept (the full `?x` text) so it
18    /// matches `ctx.register_variable`'s convention.
19    Var(String),
20    /// `<http://…>` — the inner IRI text (angle brackets stripped).
21    Iri(String),
22    /// `prefix:local` — kept split so the parser can expand against the prefix map.
23    Prefixed(String, String),
24    /// A quoted string literal (quotes stripped, `\"`/`\\` unescaped). An
25    /// optional `@lang` or `^^<datatype>` is carried alongside.
26    Str {
27        value: String,
28        lang: Option<String>,
29        datatype: Option<String>,
30    },
31    /// A numeric literal (integer or decimal/double) — kept as text so the
32    /// parser can choose the inline tag.
33    Num(String),
34    /// `true` / `false`.
35    Bool(bool),
36    /// An unquoted word: a keyword (FILTER, OPTIONAL, …), a function name, or
37    /// the Turtle `a` shorthand. Case is preserved; callers upper-case to match.
38    Word(String),
39    /// `(` `)` `{` `}` `,` `;` `.` `[` `]`
40    Punct(char),
41    /// A multi-char or single-char operator: `||`, `&&`, `=`, `!=`, `<`, `<=`,
42    /// `>`, `>=`, `+`, `-`, `*`, `/`, `!`.
43    Op(&'static str),
44    /// `<<` — opens an RDF-Star quoted triple.
45    StarOpen,
46    /// `>>` — closes an RDF-Star quoted triple.
47    StarClose,
48}
49
50/// Tokenize a SPARQL fragment. Returns an error string on a malformed literal
51/// or an unterminated IRI/string.
52pub fn tokenize(input: &str) -> Result<Vec<Token>, String> {
53    let bytes = input.as_bytes();
54    let n = bytes.len();
55    let mut i = 0usize;
56    let mut out = Vec::new();
57
58    while i < n {
59        let (c, w) = decode_char(bytes, i);
60
61        // Whitespace (Unicode-aware, not just ASCII).
62        if c.is_whitespace() {
63            i += w;
64            continue;
65        }
66
67        // Comment to end of line (`# …`).
68        if c == '#' {
69            while i < n && bytes[i] != b'\n' {
70                i += 1;
71            }
72            continue;
73        }
74
75        // `<<` / `>>` (RDF-Star) must be checked before `<`/`>` operators and IRIs.
76        if c == '<' && i + 1 < n && bytes[i + 1] == b'<' {
77            out.push(Token::StarOpen);
78            i += 2;
79            continue;
80        }
81        if c == '>' && i + 1 < n && bytes[i + 1] == b'>' {
82            out.push(Token::StarClose);
83            i += 2;
84            continue;
85        }
86
87        // IRI `<...>`. A `<` starts an IRI only when it looks like one (no spaces
88        // and a closing `>`); otherwise it is the `<`/`<=` operator. SPARQL IRIs
89        // contain no whitespace and no `<`, so we scan to the next `>`.
90        if c == '<' {
91            if let Some(close) = find_iri_close(bytes, i + 1) {
92                let iri = std::str::from_utf8(&bytes[i + 1..close])
93                    .map_err(|_| "non-utf8 IRI".to_string())?
94                    .to_string();
95                out.push(Token::Iri(iri));
96                i = close + 1;
97                continue;
98            }
99            // Fall through to operator handling.
100        }
101
102        // Variables `?x` / `$x` — SPARQL 1.1 allows Unicode in variable names.
103        if c == '?' || c == '$' {
104            let start = i;
105            i += 1; // consume sigil
106            while i < n {
107                let (ch, cw) = decode_char(bytes, i);
108                if is_varname_char(ch) {
109                    i += cw;
110                } else {
111                    break;
112                }
113            }
114            out.push(Token::Var(input[start..i].to_string()));
115            continue;
116        }
117
118        // String literals `"..."` or `'...'`, with optional @lang / ^^datatype.
119        if c == '"' || c == '\'' {
120            let (tok, next) = lex_string(input, bytes, i, c as u8)?;
121            out.push(tok);
122            i = next;
123            continue;
124        }
125
126        // Numeric literals: an optional sign is handled by the parser as a unary
127        // op, so here a number starts with a digit or a `.` followed by a digit.
128        if c.is_ascii_digit() || (c == '.' && i + 1 < n && (bytes[i + 1] as char).is_ascii_digit())
129        {
130            let start = i;
131            i += 1;
132            while i < n && {
133                let b = bytes[i] as char;
134                b.is_ascii_digit() || b == '.' || b == 'e' || b == 'E' || b == '+' || b == '-'
135            } {
136                // Only consume +/- as part of an exponent.
137                if (bytes[i] == b'+' || bytes[i] == b'-')
138                    && !(i > start && (bytes[i - 1] == b'e' || bytes[i - 1] == b'E'))
139                {
140                    break;
141                }
142                i += 1;
143            }
144            out.push(Token::Num(input[start..i].to_string()));
145            continue;
146        }
147
148        // Multi-char operators.
149        if let Some(op) = match_two_char_op(bytes, i) {
150            out.push(Token::Op(op));
151            i += 2;
152            continue;
153        }
154
155        // Single-char operators and punctuation.
156        match c {
157            '=' | '<' | '>' | '+' | '-' | '*' | '/' | '!' => {
158                out.push(Token::Op(single_char_op(c)));
159                i += 1;
160                continue;
161            }
162            '(' | ')' | '{' | '}' | ',' | ';' | '.' | '[' | ']' => {
163                out.push(Token::Punct(c));
164                i += 1;
165                continue;
166            }
167            _ => {}
168        }
169
170        // Words: keywords, function names, prefixed names, `a`, `true`/`false`.
171        // SPARQL 1.1 allows Unicode in PN_CHARS_U and PN_CHARS.
172        if is_word_start_char(c) {
173            let start = i;
174            i += w;
175            while i < n {
176                let (ch, cw) = decode_char(bytes, i);
177                if is_word_char(ch) {
178                    i += cw;
179                } else {
180                    break;
181                }
182            }
183            let word = &input[start..i];
184            // Prefixed name `prefix:local` (but not `::` or a lone trailing `:`).
185            if i < n && bytes[i] == b':' {
186                let prefix = word.to_string();
187                i += 1; // consume ':'
188                let local_start = i;
189                while i < n {
190                    let (ch, cw) = decode_char(bytes, i);
191                    if is_word_char(ch) {
192                        i += cw;
193                    } else {
194                        break;
195                    }
196                }
197                let local = input[local_start..i].to_string();
198                out.push(Token::Prefixed(prefix, local));
199                continue;
200            }
201            match word {
202                "true" => out.push(Token::Bool(true)),
203                "false" => out.push(Token::Bool(false)),
204                _ => out.push(Token::Word(word.to_string())),
205            }
206            continue;
207        }
208
209        // A bare `:local` (empty prefix) prefixed name.
210        if c == ':' {
211            let local_start = i + 1;
212            let mut j = local_start;
213            while j < n {
214                let (ch, cw) = decode_char(bytes, j);
215                if is_word_char(ch) {
216                    j += cw;
217                } else {
218                    break;
219                }
220            }
221            out.push(Token::Prefixed(
222                String::new(),
223                input[local_start..j].to_string(),
224            ));
225            i = j;
226            continue;
227        }
228
229        return Err(format!("unexpected character '{c}' at byte {i}"));
230    }
231
232    Ok(out)
233}
234
235fn find_iri_close(bytes: &[u8], from: usize) -> Option<usize> {
236    let mut i = from;
237    while i < bytes.len() {
238        match bytes[i] {
239            b'>' => return Some(i),
240            // Whitespace or `<` inside `<...>` means this wasn't an IRI.
241            b'<' | b' ' | b'\t' | b'\n' | b'\r' | b'"' | b'{' | b'}' | b'|' => return None,
242            _ => i += 1,
243        }
244    }
245    None
246}
247
248fn lex_string(
249    input: &str,
250    bytes: &[u8],
251    start: usize,
252    quote: u8,
253) -> Result<(Token, usize), String> {
254    let n = bytes.len();
255    let mut i = start + 1;
256    let mut value = String::new();
257    while i < n {
258        let b = bytes[i];
259        if b == b'\\' && i + 1 < n {
260            let esc = bytes[i + 1];
261            value.push(match esc {
262                b'n' => '\n',
263                b't' => '\t',
264                b'r' => '\r',
265                b'"' => '"',
266                b'\'' => '\'',
267                b'\\' => '\\',
268                other => other as char,
269            });
270            i += 2;
271            continue;
272        }
273        if b == quote {
274            i += 1; // consume closing quote
275                    // Optional language tag `@en` or datatype `^^<iri>` / `^^prefix:local`.
276            let mut lang = None;
277            let mut datatype = None;
278            if i < n && bytes[i] == b'@' {
279                let ls = i + 1;
280                let mut j = ls;
281                while j < n {
282                    let (ch, cw) = decode_char(bytes, j);
283                    if is_word_char(ch) || ch == '-' {
284                        j += cw;
285                    } else {
286                        break;
287                    }
288                }
289                lang = Some(input[ls..j].to_string());
290                i = j;
291            } else if i + 1 < n && bytes[i] == b'^' && bytes[i + 1] == b'^' {
292                i += 2;
293                if i < n && bytes[i] == b'<' {
294                    if let Some(close) = find_iri_close(bytes, i + 1) {
295                        datatype = Some(input[i + 1..close].to_string());
296                        i = close + 1;
297                    }
298                } else {
299                    let ds = i;
300                    while i < n {
301                        let (ch, cw) = decode_char(bytes, i);
302                        if is_word_char(ch) || ch == ':' {
303                            i += cw;
304                        } else {
305                            break;
306                        }
307                    }
308                    datatype = Some(input[ds..i].to_string());
309                }
310            }
311            return Ok((
312                Token::Str {
313                    value,
314                    lang,
315                    datatype,
316                },
317                i,
318            ));
319        }
320        // Push the decoded Unicode character, not the raw byte.
321        let (ch, cw) = decode_char(bytes, i);
322        value.push(ch);
323        i += cw;
324    }
325    Err("unterminated string literal".to_string())
326}
327
328fn match_two_char_op(bytes: &[u8], i: usize) -> Option<&'static str> {
329    if i + 1 >= bytes.len() {
330        return None;
331    }
332    match (bytes[i], bytes[i + 1]) {
333        (b'|', b'|') => Some("||"),
334        (b'&', b'&') => Some("&&"),
335        (b'!', b'=') => Some("!="),
336        (b'<', b'=') => Some("<="),
337        (b'>', b'=') => Some(">="),
338        _ => None,
339    }
340}
341
342fn single_char_op(c: char) -> &'static str {
343    match c {
344        '=' => "=",
345        '<' => "<",
346        '>' => ">",
347        '+' => "+",
348        '-' => "-",
349        '*' => "*",
350        '/' => "/",
351        '!' => "!",
352        _ => unreachable!(),
353    }
354}
355
356/// Decode one UTF-8 character at byte offset `i`, returning (char, byte_width).
357/// Falls back to the raw byte for invalid UTF-8 (never panics).
358#[inline]
359fn decode_char(bytes: &[u8], i: usize) -> (char, usize) {
360    let b = bytes[i];
361    if b < 0x80 {
362        return (b as char, 1);
363    }
364    // Multi-byte: use str slicing for safe decode.
365    let remaining = &bytes[i..];
366    match std::str::from_utf8(remaining) {
367        Ok(s) => {
368            let c = s.chars().next().unwrap_or(b as char);
369            (c, c.len_utf8())
370        }
371        Err(e) => {
372            // Use the valid prefix length, then decode the next char.
373            let valid_len = e.valid_up_to();
374            if valid_len > 0 {
375                let s = std::str::from_utf8(&remaining[..valid_len]).unwrap();
376                let c = s.chars().next().unwrap();
377                (c, c.len_utf8())
378            } else {
379                // Invalid byte — emit as replacement, advance 1.
380                (b as char, 1)
381            }
382        }
383    }
384}
385
386/// SPARQL 1.1 variable names allow Unicode (PN_CHARS_U + PN_CHARS).
387fn is_varname_char(c: char) -> bool {
388    c.is_alphanumeric() || c == '_'
389}
390
391/// Word start: letters, underscore, and Unicode letters (SPARQL PN_CHARS_U).
392fn is_word_start_char(c: char) -> bool {
393    c.is_alphabetic() || c == '_'
394}
395
396/// Word continuation: alphanumeric, underscore, hyphen, dot (SPARQL PN_CHARS).
397fn is_word_char(c: char) -> bool {
398    c.is_alphanumeric() || c == '_' || c == '-' || c == '.'
399}
400
401#[cfg(test)]
402mod tests {
403    use super::*;
404
405    #[test]
406    fn tokenize_filter_expression() {
407        let toks = tokenize("?age >= 18 && ?name = \"Alice\"").unwrap();
408        assert_eq!(
409            toks,
410            vec![
411                Token::Var("?age".into()),
412                Token::Op(">="),
413                Token::Num("18".into()),
414                Token::Op("&&"),
415                Token::Var("?name".into()),
416                Token::Op("="),
417                Token::Str {
418                    value: "Alice".into(),
419                    lang: None,
420                    datatype: None
421                },
422            ]
423        );
424    }
425
426    #[test]
427    fn tokenize_iri_and_prefixed() {
428        let toks = tokenize("?s <http://example.org/p> foaf:name").unwrap();
429        assert_eq!(toks[0], Token::Var("?s".into()));
430        assert_eq!(toks[1], Token::Iri("http://example.org/p".into()));
431        assert_eq!(toks[2], Token::Prefixed("foaf".into(), "name".into()));
432    }
433
434    #[test]
435    fn tokenize_star_triple() {
436        let toks = tokenize("<< ?s ?p ?o >>").unwrap();
437        assert_eq!(toks[0], Token::StarOpen);
438        assert_eq!(toks[4], Token::StarClose);
439    }
440
441    #[test]
442    fn tokenize_function_call_and_punct() {
443        let toks = tokenize("REGEX(?x, \"^a\")").unwrap();
444        assert_eq!(toks[0], Token::Word("REGEX".into()));
445        assert_eq!(toks[1], Token::Punct('('));
446        assert_eq!(toks[2], Token::Var("?x".into()));
447        assert_eq!(toks[3], Token::Punct(','));
448        assert_eq!(
449            toks[4],
450            Token::Str {
451                value: "^a".into(),
452                lang: None,
453                datatype: None
454            }
455        );
456        assert_eq!(toks[5], Token::Punct(')'));
457    }
458
459    #[test]
460    fn tokenize_lt_operator_vs_iri() {
461        // A `<` not forming an IRI is the less-than operator.
462        let toks = tokenize("?a < ?b").unwrap();
463        assert_eq!(
464            toks,
465            vec![
466                Token::Var("?a".into()),
467                Token::Op("<"),
468                Token::Var("?b".into())
469            ]
470        );
471    }
472
473    #[test]
474    fn tokenize_typed_literal() {
475        let toks = tokenize("\"5\"^^<http://www.w3.org/2001/XMLSchema#integer>").unwrap();
476        assert_eq!(
477            toks[0],
478            Token::Str {
479                value: "5".into(),
480                lang: None,
481                datatype: Some("http://www.w3.org/2001/XMLSchema#integer".into())
482            }
483        );
484    }
485
486    #[test]
487    fn tokenize_lang_literal() {
488        let toks = tokenize("\"chat\"@fr").unwrap();
489        assert_eq!(
490            toks[0],
491            Token::Str {
492                value: "chat".into(),
493                lang: Some("fr".into()),
494                datatype: None
495            }
496        );
497    }
498
499    #[test]
500    fn tokenize_unicode_variable_name() {
501        let toks = tokenize("?名前").unwrap();
502        assert_eq!(toks[0], Token::Var("?名前".into()));
503    }
504
505    #[test]
506    fn tokenize_unicode_prefixed_name() {
507        let toks = tokenize("日本:東京").unwrap();
508        assert_eq!(toks[0], Token::Prefixed("日本".into(), "東京".into()));
509    }
510
511    #[test]
512    fn tokenize_unicode_string_literal() {
513        let toks = tokenize("\"你好世界\"").unwrap();
514        assert_eq!(
515            toks[0],
516            Token::Str {
517                value: "你好世界".into(),
518                lang: None,
519                datatype: None
520            }
521        );
522    }
523
524    #[test]
525    fn tokenize_unicode_whitespace() {
526        // U+3000 (ideographic space) should be treated as whitespace.
527        let toks = tokenize("?x\u{3000}?y").unwrap();
528        assert_eq!(toks[0], Token::Var("?x".into()));
529        assert_eq!(toks[1], Token::Var("?y".into()));
530    }
531}
qualia_core_db/sparql_library/sparql_grammar/tokenizer.rs

qualia_core_db/sparql_library/sparql_grammar/
tokenizer.rs
