radixdb_sql/lexer/
mod.rs

1// Copyright 2026 RadixDB Contributors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! SQL Lexer (Tokenizer)
16//!
17//! This module provides the lexer for tokenizing SQL input strings.
18
19mod cursor;
20mod identifier;
21mod literal;
22mod trivia;
23
24use super::token::{
25    is_keyword, is_operator, is_operator_char, is_punctuator, punctuator_str, Position, Token,
26    TokenType,
27};
28use radixdb_core::SmartString;
29
30/// SQL Lexer for tokenizing input
31///
32/// Uses byte-based indexing for efficiency. SQL is predominantly ASCII,
33/// so we can work with bytes directly and only decode UTF-8 when needed.
34pub struct Lexer {
35    /// Input string as bytes (avoids `Vec<char>` allocation)
36    input: Box<[u8]>,
37    /// Current byte position in input
38    position: usize,
39    /// Next byte position in input (after current char)
40    read_position: usize,
41    /// Current character under examination
42    ch: char,
43    /// Whether `ch` is the synthetic end-of-input marker rather than U+0000
44    eof: bool,
45    /// Current position tracking
46    pos: Position,
47    /// Last error encountered
48    last_error: Option<String>,
49}
50
51impl Lexer {
52    /// Create a new lexer for the given input
53    pub fn new(input: &str) -> Self {
54        // Store as bytes - much more memory efficient than Vec<char>
55        let bytes: Box<[u8]> = input.as_bytes().into();
56        let mut lexer = Self {
57            input: bytes,
58            position: 0,
59            read_position: 0,
60            ch: '\0',
61            eof: true,
62            pos: Position::new(0, 1, 1),
63            last_error: None,
64        };
65        lexer.read_char();
66        lexer
67    }
68
69    /// Get the next token
70    pub fn next_token(&mut self) -> Token {
71        self.skip_whitespace();
72
73        let pos = self.pos;
74
75        match self.ch {
76            '\0' if self.eof => Token::eof(pos),
77
78            '\0' => {
79                self.read_char();
80                Token::error("NULL byte (0x00) is not allowed in SQL input", "", pos)
81            }
82
83            // String literal (single quotes)
84            '\'' => {
85                let literal = self.read_string_literal();
86                if let Some(err) = self.last_error.take() {
87                    return Token::error(err, "", pos);
88                }
89                Token::new(TokenType::String, literal, pos)
90            }
91
92            // Double-quoted identifier (identifier with string fallback)
93            '"' => {
94                let literal = self.read_quoted_identifier('"');
95                if let Some(err) = self.last_error.take() {
96                    return Token::error(err, "", pos);
97                }
98                Token::new_quoted(TokenType::Identifier, literal, pos)
99            }
100
101            // Backtick-quoted identifier (MySQL style)
102            '`' => {
103                let literal = self.read_quoted_identifier('`');
104                if let Some(err) = self.last_error.take() {
105                    return Token::error(err, "", pos);
106                }
107                Token::new_quoted(TokenType::Identifier, literal, pos)
108            }
109
110            // Negative numbers: parser handles unary minus, not the lexer.
111
112            // Number literal
113            c if c.is_ascii_digit() => {
114                let literal = self.read_number();
115                if literal.contains('.') || literal.contains('e') || literal.contains('E') {
116                    Token::new(TokenType::Float, literal, pos)
117                } else {
118                    Token::new(TokenType::Integer, literal, pos)
119                }
120            }
121
122            // Single line comment (#)
123            '#' => {
124                let literal = self.read_line_comment();
125                if let Some(err) = self.last_error.take() {
126                    return Token::error(err, "", pos);
127                }
128                Token::new(TokenType::Comment, literal, pos)
129            }
130
131            // Single line comment (--) per SQL standard (SQL:2023 section 5.2)
132            // Double negation should be written as `- -val` or `- (-val)`
133            '-' if self.peek_char() == '-' => {
134                let literal = self.read_line_comment();
135                if let Some(err) = self.last_error.take() {
136                    return Token::error(err, "", pos);
137                }
138                Token::new(TokenType::Comment, literal, pos)
139            }
140
141            // Multi-line comment
142            '/' if self.peek_char() == '*' => {
143                let literal = self.read_block_comment();
144                if let Some(err) = self.last_error.take() {
145                    return Token::error(err, "", pos);
146                }
147                Token::new(TokenType::Comment, literal, pos)
148            }
149
150            // Parameter ($1, $2, etc.)
151            '$' if self.peek_char().is_ascii_digit() => {
152                let literal = self.read_parameter();
153                Token::new(TokenType::Parameter, literal, pos)
154            }
155
156            // Parameter (?)
157            '?' => {
158                self.read_char();
159                Token::new(TokenType::Parameter, "?", pos)
160            }
161
162            // Named parameter (:name)
163            ':' if self.peek_char().is_alphabetic() || self.peek_char() == '_' => {
164                let literal = self.read_named_parameter();
165                Token::new(TokenType::Parameter, literal, pos)
166            }
167
168            // Procedural assignment. This must precede punctuator handling so
169            // longest-match keeps `:=` atomic while bare `:` remains intact.
170            ':' if self.peek_char() == '=' => {
171                let literal = self.read_operator();
172                Token::new(TokenType::Operator, literal, pos)
173            }
174
175            // Star is always an operator (SELECT * handled by parser)
176            '*' => {
177                self.read_char();
178                Token::new(TokenType::Operator, "*", pos)
179            }
180
181            // Regular punctuator - use static string to avoid allocation
182            c if is_punctuator(c) => {
183                self.read_char();
184                // SAFETY: We already checked is_punctuator(c), so punctuator_str always returns Some
185                Token::new(TokenType::Punctuator, punctuator_str(c).unwrap(), pos)
186            }
187
188            // Operator
189            c if is_operator_char(c) => {
190                let literal = self.read_operator();
191                Token::new(TokenType::Operator, literal, pos)
192            }
193
194            // Identifier or keyword
195            c if c.is_alphabetic() || c == '_' => {
196                let literal = self.read_identifier();
197                if is_keyword(&literal) {
198                    Token::new(TokenType::Keyword, literal.to_uppercase(), pos)
199                } else {
200                    Token::new(TokenType::Identifier, literal, pos)
201                }
202            }
203
204            // Unrecognized character
205            c => {
206                self.read_char();
207                Token::error(
208                    format!("unrecognized character: {:?}", c),
209                    c.to_string(),
210                    pos,
211                )
212            }
213        }
214    }
215
216    /// Read an operator
217    fn read_operator(&mut self) -> SmartString {
218        let mut result = SmartString::new("");
219        let first_char = self.ch;
220        result.push(first_char);
221        self.read_char();
222
223        // Check for multi-character operators
224        if !self.eof {
225            let two_chars: SmartString =
226                SmartString::from_iter([first_char, self.ch].iter().copied());
227            if is_operator(&two_chars) {
228                result.push(self.ch);
229                self.read_char();
230
231                // Check for three-character operators
232                if !self.eof {
233                    let mut three_chars = two_chars.clone();
234                    three_chars.push(self.ch);
235                    if is_operator(&three_chars) {
236                        result.push(self.ch);
237                        self.read_char();
238                    }
239                }
240            }
241        }
242
243        result
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use super::*;
250
251    #[test]
252    fn test_simple_select() {
253        let mut lexer = Lexer::new("SELECT * FROM users");
254
255        let token = lexer.next_token();
256        assert_eq!(token.token_type, TokenType::Keyword);
257        assert_eq!(token.literal, "SELECT");
258
259        let token = lexer.next_token();
260        assert_eq!(token.token_type, TokenType::Operator);
261        assert_eq!(token.literal, "*");
262
263        let token = lexer.next_token();
264        assert_eq!(token.token_type, TokenType::Keyword);
265        assert_eq!(token.literal, "FROM");
266
267        let token = lexer.next_token();
268        assert_eq!(token.token_type, TokenType::Identifier);
269        assert_eq!(token.literal, "users");
270
271        let token = lexer.next_token();
272        assert!(token.is_eof());
273    }
274
275    #[test]
276    fn test_numbers() {
277        let mut lexer = Lexer::new("123 45.67 -89 3.14e10 1.5E-3");
278
279        let token = lexer.next_token();
280        assert_eq!(token.token_type, TokenType::Integer);
281        assert_eq!(token.literal, "123");
282
283        let token = lexer.next_token();
284        assert_eq!(token.token_type, TokenType::Float);
285        assert_eq!(token.literal, "45.67");
286
287        // Negative numbers are tokenized as operator + number (parser handles unary minus)
288        let token = lexer.next_token();
289        assert_eq!(token.token_type, TokenType::Operator);
290        assert_eq!(token.literal, "-");
291
292        let token = lexer.next_token();
293        assert_eq!(token.token_type, TokenType::Integer);
294        assert_eq!(token.literal, "89");
295
296        let token = lexer.next_token();
297        assert_eq!(token.token_type, TokenType::Float);
298        assert_eq!(token.literal, "3.14e10");
299
300        let token = lexer.next_token();
301        assert_eq!(token.token_type, TokenType::Float);
302        assert_eq!(token.literal, "1.5E-3");
303    }
304
305    #[test]
306    fn test_string_literals() {
307        let mut lexer = Lexer::new("'hello' 'world''s' 'escaped\\ntext'");
308
309        let token = lexer.next_token();
310        assert_eq!(token.token_type, TokenType::String);
311        assert_eq!(token.literal, "'hello'");
312
313        let token = lexer.next_token();
314        assert_eq!(token.token_type, TokenType::String);
315        assert_eq!(token.literal, "'world's'");
316
317        let token = lexer.next_token();
318        assert_eq!(token.token_type, TokenType::String);
319        assert_eq!(token.literal, "'escaped\\ntext'");
320    }
321
322    #[test]
323    fn test_quoted_identifiers() {
324        let mut lexer = Lexer::new("\"table name\" `column`");
325
326        let token = lexer.next_token();
327        assert_eq!(token.token_type, TokenType::Identifier);
328        assert_eq!(token.literal, "table name");
329
330        let token = lexer.next_token();
331        assert_eq!(token.token_type, TokenType::Identifier);
332        assert_eq!(token.literal, "column");
333    }
334
335    #[test]
336    fn test_operators() {
337        let mut lexer = Lexer::new("= <> >= <= != + - * / || -> ->>");
338
339        let expected = vec![
340            "=", "<>", ">=", "<=", "!=", "+", "-", "*", "/", "||", "->", "->>",
341        ];
342
343        for exp in expected {
344            let token = lexer.next_token();
345            assert_eq!(token.token_type, TokenType::Operator);
346            assert_eq!(token.literal, exp);
347        }
348    }
349
350    #[test]
351    fn test_punctuators() {
352        let mut lexer = Lexer::new("( ) , ; . [ ]");
353
354        let expected = vec!["(", ")", ",", ";", ".", "[", "]"];
355
356        for exp in expected {
357            let token = lexer.next_token();
358            assert_eq!(token.token_type, TokenType::Punctuator);
359            assert_eq!(token.literal, exp);
360        }
361    }
362
363    #[test]
364    fn test_comments() {
365        let mut lexer = Lexer::new("-- line comment\nSELECT /* block */ 1");
366
367        let token = lexer.next_token();
368        assert_eq!(token.token_type, TokenType::Comment);
369        assert!(token.literal.contains("line comment"));
370
371        let token = lexer.next_token();
372        assert_eq!(token.token_type, TokenType::Keyword);
373        assert_eq!(token.literal, "SELECT");
374
375        let token = lexer.next_token();
376        assert_eq!(token.token_type, TokenType::Comment);
377        assert!(token.literal.contains("block"));
378
379        let token = lexer.next_token();
380        assert_eq!(token.token_type, TokenType::Integer);
381        assert_eq!(token.literal, "1");
382    }
383
384    #[test]
385    fn test_double_dash_is_always_comment() {
386        // Per SQL standard (SQL:2023 5.2), -- always starts a line comment
387        // regardless of what follows the dashes.
388
389        // --5 is a comment, not double negation
390        let mut lexer = Lexer::new("SELECT --5");
391        let token = lexer.next_token();
392        assert_eq!(token.token_type, TokenType::Keyword);
393        assert_eq!(token.literal, "SELECT");
394        let token = lexer.next_token();
395        assert_eq!(token.token_type, TokenType::Comment);
396
397        // --val is a comment, not double negation
398        let mut lexer = Lexer::new("SELECT --val");
399        let token = lexer.next_token();
400        assert_eq!(token.token_type, TokenType::Keyword);
401        let token = lexer.next_token();
402        assert_eq!(token.token_type, TokenType::Comment);
403
404        // --comment at start of input is a comment
405        let mut lexer = Lexer::new("--comment\nSELECT 1");
406        let token = lexer.next_token();
407        assert_eq!(token.token_type, TokenType::Comment);
408        let token = lexer.next_token();
409        assert_eq!(token.token_type, TokenType::Keyword);
410        assert_eq!(token.literal, "SELECT");
411
412        // -- with space is still a comment
413        let mut lexer = Lexer::new("SELECT -- comment");
414        let token = lexer.next_token();
415        assert_eq!(token.token_type, TokenType::Keyword);
416        let token = lexer.next_token();
417        assert_eq!(token.token_type, TokenType::Comment);
418
419        // Double negation must use `- -` with a space
420        let mut lexer = Lexer::new("SELECT - -5");
421        let token = lexer.next_token();
422        assert_eq!(token.token_type, TokenType::Keyword);
423        let token = lexer.next_token();
424        assert_eq!(token.token_type, TokenType::Operator);
425        assert_eq!(token.literal, "-");
426        let token = lexer.next_token();
427        assert_eq!(token.token_type, TokenType::Operator);
428        assert_eq!(token.literal, "-");
429        let token = lexer.next_token();
430        assert_eq!(token.token_type, TokenType::Integer);
431        assert_eq!(token.literal, "5");
432    }
433
434    #[test]
435    fn test_parameters() {
436        let mut lexer = Lexer::new("$1 $23 ? :name :user_id :_private");
437
438        let token = lexer.next_token();
439        assert_eq!(token.token_type, TokenType::Parameter);
440        assert_eq!(token.literal, "$1");
441
442        let token = lexer.next_token();
443        assert_eq!(token.token_type, TokenType::Parameter);
444        assert_eq!(token.literal, "$23");
445
446        let token = lexer.next_token();
447        assert_eq!(token.token_type, TokenType::Parameter);
448        assert_eq!(token.literal, "?");
449
450        let token = lexer.next_token();
451        assert_eq!(token.token_type, TokenType::Parameter);
452        assert_eq!(token.literal, ":name");
453
454        let token = lexer.next_token();
455        assert_eq!(token.token_type, TokenType::Parameter);
456        assert_eq!(token.literal, ":user_id");
457
458        let token = lexer.next_token();
459        assert_eq!(token.token_type, TokenType::Parameter);
460        assert_eq!(token.literal, ":_private");
461    }
462
463    #[test]
464    fn test_keywords_case_insensitive() {
465        let mut lexer = Lexer::new("select SELECT Select");
466
467        for _ in 0..3 {
468            let token = lexer.next_token();
469            assert_eq!(token.token_type, TokenType::Keyword);
470            assert_eq!(token.literal, "SELECT");
471        }
472    }
473
474    #[test]
475    fn test_position_tracking() {
476        let mut lexer = Lexer::new("SELECT\nFROM");
477
478        let token = lexer.next_token();
479        assert_eq!(token.position.line, 1);
480        assert_eq!(token.position.column, 1);
481
482        let token = lexer.next_token();
483        assert_eq!(token.position.line, 2);
484        assert_eq!(token.position.column, 1);
485    }
486
487    #[test]
488    fn test_complex_query() {
489        let query = r#"
490            SELECT u.id, u.name, COUNT(o.id) as order_count
491            FROM users u
492            LEFT JOIN orders o ON u.id = o.user_id
493            WHERE u.active = TRUE AND o.amount >= 100.50
494            GROUP BY u.id, u.name
495            HAVING COUNT(o.id) > 0
496            ORDER BY order_count DESC
497            LIMIT 10
498        "#;
499
500        let mut lexer = Lexer::new(query);
501        let mut tokens = Vec::new();
502
503        loop {
504            let token = lexer.next_token();
505            if token.is_eof() {
506                break;
507            }
508            tokens.push(token);
509        }
510
511        // Verify we got reasonable tokens
512        assert!(tokens.len() > 30);
513        assert!(tokens.iter().any(|t| t.is_keyword("SELECT")));
514        assert!(tokens.iter().any(|t| t.is_keyword("FROM")));
515        assert!(tokens.iter().any(|t| t.is_keyword("JOIN")));
516        assert!(tokens.iter().any(|t| t.is_keyword("WHERE")));
517        assert!(tokens.iter().any(|t| t.is_keyword("GROUP")));
518        assert!(tokens.iter().any(|t| t.is_keyword("HAVING")));
519        assert!(tokens.iter().any(|t| t.is_keyword("ORDER")));
520        assert!(tokens.iter().any(|t| t.is_keyword("LIMIT")));
521    }
522
523    #[test]
524    fn test_error_token() {
525        let mut lexer = Lexer::new("SELECT © FROM");
526
527        let token = lexer.next_token();
528        assert_eq!(token.token_type, TokenType::Keyword);
529
530        let token = lexer.next_token();
531        assert_eq!(token.token_type, TokenType::Error);
532        // Error message is stored in literal field
533        assert!(!token.literal.is_empty());
534    }
535}
radixdb_sql/lexer/mod.rs

radixdb_sql/lexer/
mod.rs
