inillucent_sql/
lexer.rs

1//! The zero-copy lexer: SQL bytes in, tokens with spans out.
2//!
3//! Invariant: every input byte belongs to exactly one token or trivia span,
4//! spans are ordered, non-overlapping and inside the source, and no token owns
5//! a byte. Token text is always a slice of the original SQL, which is what
6//! makes `prepare` free of identifier allocation and what lets an error point
7//! at an exact offset in the caller's own string.
8//!
9//! An unterminated quote or comment reports the offset of the byte that opened
10//! it, not the end of input. That is the difference between "there is a problem
11//! at character 4093" and "there is a problem somewhere", and it is the reason
12//! the opening offset is carried down rather than recomputed.
13
14use crate::keyword::{self, Keyword};
15
16/// A half-open byte range in the source SQL.
17#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
18pub struct Span {
19    /// The first byte of the span.
20    pub start: u32,
21    /// One past the last byte of the span.
22    pub end: u32,
23}
24
25impl Span {
26    /// Returns a span covering `start..end`.
27    pub fn new(start: usize, end: usize) -> Span {
28        Span {
29            start: start.min(u32::MAX as usize) as u32,
30            end: end.min(u32::MAX as usize) as u32,
31        }
32    }
33
34    /// Returns an empty span at one offset, used for end-of-input.
35    pub fn at(offset: usize) -> Span {
36        Span::new(offset, offset)
37    }
38
39    /// Returns the span covering both spans and everything between them.
40    pub fn to(self, other: Span) -> Span {
41        Span {
42            start: self.start.min(other.start),
43            end: self.end.max(other.end),
44        }
45    }
46
47    /// Returns the length of the span in bytes.
48    pub fn len(self) -> usize {
49        self.end.saturating_sub(self.start) as usize
50    }
51
52    /// Returns whether the span covers no bytes.
53    pub fn is_empty(self) -> bool {
54        self.end <= self.start
55    }
56
57    /// Returns the source bytes the span covers.
58    pub fn slice(self, source: &[u8]) -> &[u8] {
59        source
60            .get(self.start as usize..self.end as usize)
61            .unwrap_or(&[])
62    }
63}
64
65/// The quoting form an identifier was written with.
66///
67/// SQLite treats the four forms differently once semantics begin: a
68/// double-quoted word falls back to a string literal when it resolves to no
69/// name and the connection permits it, and the other three never do.
70#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
71pub enum QuoteForm {
72    /// `plain`, with no quoting at all.
73    Bare,
74    /// `"quoted"`, which may fall back to a string literal.
75    Double,
76    /// `[quoted]`, the MS-Access form.
77    Bracket,
78    /// `` `quoted` ``, the MySQL form.
79    Backtick,
80}
81
82/// The kind of a token.
83#[derive(Clone, Copy, Debug, PartialEq, Eq)]
84pub enum TokenKind {
85    /// A word: a keyword when `keyword` is set, otherwise an identifier.
86    Identifier {
87        /// The keyword this word spells, when it spells one.
88        keyword: Option<Keyword>,
89        /// How the identifier was quoted.
90        quote: QuoteForm,
91    },
92    /// A `'string'` literal.
93    String,
94    /// An `x'..'` blob literal.
95    Blob,
96    /// An integer literal, in decimal or hexadecimal.
97    Integer,
98    /// A floating-point literal.
99    Float,
100    /// A bound parameter.
101    Parameter,
102    /// Punctuation or an operator.
103    Punctuator(Punctuator),
104    /// End of input.
105    EndOfInput,
106}
107
108/// Every punctuation and operator token the pinned release accepts.
109#[derive(Clone, Copy, Debug, PartialEq, Eq)]
110pub enum Punctuator {
111    /// `(`
112    LeftParen,
113    /// `)`
114    RightParen,
115    /// `,`
116    Comma,
117    /// `;`
118    Semicolon,
119    /// `.`
120    Dot,
121    /// `+`
122    Plus,
123    /// `-`
124    Minus,
125    /// `*`
126    Star,
127    /// `/`
128    Slash,
129    /// `%`
130    Percent,
131    /// `=` or `==`
132    Equal,
133    /// `<>` or `!=`
134    NotEqual,
135    /// `<`
136    Less,
137    /// `<=`
138    LessEqual,
139    /// `>`
140    Greater,
141    /// `>=`
142    GreaterEqual,
143    /// `<<`
144    ShiftLeft,
145    /// `>>`
146    ShiftRight,
147    /// `&`
148    BitAnd,
149    /// `|`
150    BitOr,
151    /// `~`
152    BitNot,
153    /// `||`
154    Concat,
155    /// `->`
156    Arrow,
157    /// `->>`
158    DoubleArrow,
159    /// `<->`, pgvector's Euclidean distance.
160    L2Distance,
161    /// `<=>`, pgvector's cosine distance.
162    CosineDistance,
163    /// `<#>`, pgvector's negative inner product.
164    NegativeInnerProduct,
165    /// `<+>`, pgvector's taxicab distance.
166    L1Distance,
167    /// `<~>`, pgvector's Hamming distance.
168    HammingDistance,
169    /// `<%>`, pgvector's Jaccard distance.
170    JaccardDistance,
171}
172
173impl Punctuator {
174    /// Returns the canonical spelling, for diagnostics.
175    pub fn as_str(self) -> &'static str {
176        match self {
177            Punctuator::LeftParen => "(",
178            Punctuator::RightParen => ")",
179            Punctuator::Comma => ",",
180            Punctuator::Semicolon => ";",
181            Punctuator::Dot => ".",
182            Punctuator::Plus => "+",
183            Punctuator::Minus => "-",
184            Punctuator::Star => "*",
185            Punctuator::Slash => "/",
186            Punctuator::Percent => "%",
187            Punctuator::Equal => "=",
188            Punctuator::NotEqual => "<>",
189            Punctuator::Less => "<",
190            Punctuator::LessEqual => "<=",
191            Punctuator::Greater => ">",
192            Punctuator::GreaterEqual => ">=",
193            Punctuator::ShiftLeft => "<<",
194            Punctuator::ShiftRight => ">>",
195            Punctuator::BitAnd => "&",
196            Punctuator::BitOr => "|",
197            Punctuator::BitNot => "~",
198            Punctuator::Concat => "||",
199            Punctuator::Arrow => "->",
200            Punctuator::L2Distance => "<->",
201            Punctuator::CosineDistance => "<=>",
202            Punctuator::NegativeInnerProduct => "<#>",
203            Punctuator::L1Distance => "<+>",
204            Punctuator::HammingDistance => "<~>",
205            Punctuator::JaccardDistance => "<%>",
206            Punctuator::DoubleArrow => "->>",
207        }
208    }
209}
210
211/// One token: what it is and where it came from.
212#[derive(Clone, Copy, Debug, PartialEq, Eq)]
213pub struct Token {
214    /// What kind of token this is.
215    pub kind: TokenKind,
216    /// The bytes of the source it covers.
217    pub span: Span,
218}
219
220impl Token {
221    /// Returns the source text of the token.
222    pub fn text(self, source: &[u8]) -> &[u8] {
223        self.span.slice(source)
224    }
225
226    /// Returns the keyword this token spells, if it spells one.
227    pub fn keyword(self) -> Option<Keyword> {
228        match self.kind {
229            TokenKind::Identifier { keyword, .. } => keyword,
230            _ => None,
231        }
232    }
233
234    /// Returns whether the token is a punctuator of the given kind.
235    pub fn is(self, punctuator: Punctuator) -> bool {
236        self.kind == TokenKind::Punctuator(punctuator)
237    }
238}
239
240/// Why lexing stopped.
241#[derive(Clone, Copy, Debug, PartialEq, Eq)]
242pub enum LexErrorKind {
243    /// A quote or bracket was opened and never closed.
244    UnterminatedQuote,
245    /// A block comment was opened and never closed.
246    UnterminatedComment,
247    /// A byte that begins no token.
248    UnrecognisedByte,
249    /// A blob literal whose body is not an even number of hex digits.
250    MalformedBlob,
251    /// A numeric literal SQLite does not accept in this form.
252    MalformedNumber,
253    /// A parameter name that is empty or out of range.
254    MalformedParameter,
255}
256
257impl LexErrorKind {
258    /// Returns a stable one-line description.
259    pub fn message(self) -> &'static str {
260        match self {
261            LexErrorKind::UnterminatedQuote => "unrecognized token: unterminated quoted name",
262            LexErrorKind::UnterminatedComment => "unrecognized token: unterminated comment",
263            LexErrorKind::UnrecognisedByte => "unrecognized token",
264            LexErrorKind::MalformedBlob => "unrecognized token: malformed blob literal",
265            LexErrorKind::MalformedNumber => "unrecognized token: malformed numeric literal",
266            LexErrorKind::MalformedParameter => "unrecognized token: malformed parameter",
267        }
268    }
269}
270
271/// A lexing failure, with the offset of the byte that caused it.
272#[derive(Clone, Copy, Debug, PartialEq, Eq)]
273pub struct LexError {
274    /// Why it failed.
275    pub kind: LexErrorKind,
276    /// The offset the diagnostic points at.
277    pub offset: u32,
278}
279
280/// The scanner. It holds the source and a cursor and nothing else.
281#[derive(Clone, Debug)]
282pub struct Lexer<'a> {
283    source: &'a [u8],
284    offset: usize,
285}
286
287impl<'a> Lexer<'a> {
288    /// Returns a lexer positioned at the start of the source.
289    pub fn new(source: &'a [u8]) -> Lexer<'a> {
290        Lexer { source, offset: 0 }
291    }
292
293    /// Returns a lexer positioned at a byte offset in the source.
294    pub fn at(source: &'a [u8], offset: usize) -> Lexer<'a> {
295        Lexer {
296            source,
297            offset: offset.min(source.len()),
298        }
299    }
300
301    /// Returns the current byte offset.
302    pub fn offset(&self) -> usize {
303        self.offset
304    }
305
306    /// Returns the source being scanned.
307    pub fn source(&self) -> &'a [u8] {
308        self.source
309    }
310
311    /// Returns the byte at an offset, if there is one.
312    fn byte(&self, offset: usize) -> Option<u8> {
313        self.source.get(offset).copied()
314    }
315
316    /// Skips whitespace and both comment forms, returning an error for an
317    /// unterminated block comment at the offset that opened it.
318    fn skip_trivia(&mut self) -> Result<(), LexError> {
319        loop {
320            match self.byte(self.offset) {
321                Some(byte) if is_space(byte) => self.offset += 1,
322                Some(b'-') if self.byte(self.offset + 1) == Some(b'-') => {
323                    self.offset += 2;
324                    while let Some(byte) = self.byte(self.offset) {
325                        self.offset += 1;
326                        if byte == b'\n' {
327                            break;
328                        }
329                    }
330                }
331                Some(b'/') if self.byte(self.offset + 1) == Some(b'*') => {
332                    let opened = self.offset;
333                    self.offset += 2;
334                    loop {
335                        match self.byte(self.offset) {
336                            None => {
337                                // SQLite accepts an unterminated block comment
338                                // at the very end of input, treating it as
339                                // closed. It is the one place a missing
340                                // terminator is not an error.
341                                return Ok(());
342                            }
343                            Some(b'*') if self.byte(self.offset + 1) == Some(b'/') => {
344                                self.offset += 2;
345                                break;
346                            }
347                            Some(_) => self.offset += 1,
348                        }
349                    }
350                    let _ = opened;
351                }
352                _ => return Ok(()),
353            }
354        }
355    }
356
357    /// Scans and returns the next token, skipping trivia first.
358    pub fn next_token(&mut self) -> Result<Token, LexError> {
359        self.skip_trivia()?;
360        let start = self.offset;
361        let Some(byte) = self.byte(start) else {
362            return Ok(Token {
363                kind: TokenKind::EndOfInput,
364                span: Span::at(start),
365            });
366        };
367        match byte {
368            b'\'' => self.scan_quoted(start, b'\'', TokenKind::String),
369            b'"' => self.scan_quoted(
370                start,
371                b'"',
372                TokenKind::Identifier {
373                    keyword: None,
374                    quote: QuoteForm::Double,
375                },
376            ),
377            b'`' => self.scan_quoted(
378                start,
379                b'`',
380                TokenKind::Identifier {
381                    keyword: None,
382                    quote: QuoteForm::Backtick,
383                },
384            ),
385            b'[' => self.scan_bracket(start),
386            b'0'..=b'9' => self.scan_number(start),
387            b'.' if self.byte(start + 1).is_some_and(is_digit) => self.scan_number(start),
388            b'?' | b':' | b'@' | b'$' => self.scan_parameter(start),
389            byte if is_identifier_start(byte) => self.scan_word(start),
390            _ => self.scan_punctuator(start),
391        }
392    }
393
394    /// Scans a `'`, `"` or backtick delimited run, where the delimiter is
395    /// escaped by doubling it.
396    fn scan_quoted(
397        &mut self,
398        start: usize,
399        delimiter: u8,
400        kind: TokenKind,
401    ) -> Result<Token, LexError> {
402        let mut cursor = start + 1;
403        loop {
404            match self.byte(cursor) {
405                None => {
406                    return Err(LexError {
407                        kind: LexErrorKind::UnterminatedQuote,
408                        offset: start as u32,
409                    })
410                }
411                Some(byte) if byte == delimiter => {
412                    if self.byte(cursor + 1) == Some(delimiter) {
413                        cursor += 2;
414                        continue;
415                    }
416                    cursor += 1;
417                    break;
418                }
419                Some(_) => cursor += 1,
420            }
421        }
422        self.offset = cursor;
423        Ok(Token {
424            kind,
425            span: Span::new(start, cursor),
426        })
427    }
428
429    /// Scans a `[bracketed]` identifier, which has no escape at all.
430    fn scan_bracket(&mut self, start: usize) -> Result<Token, LexError> {
431        let mut cursor = start + 1;
432        loop {
433            match self.byte(cursor) {
434                None => {
435                    return Err(LexError {
436                        kind: LexErrorKind::UnterminatedQuote,
437                        offset: start as u32,
438                    })
439                }
440                Some(b']') => {
441                    cursor += 1;
442                    break;
443                }
444                Some(_) => cursor += 1,
445            }
446        }
447        self.offset = cursor;
448        Ok(Token {
449            kind: TokenKind::Identifier {
450                keyword: None,
451                quote: QuoteForm::Bracket,
452            },
453            span: Span::new(start, cursor),
454        })
455    }
456
457    /// Scans a bare word, which may be a keyword or the `x'..'` blob prefix.
458    fn scan_word(&mut self, start: usize) -> Result<Token, LexError> {
459        let mut cursor = start;
460        while self.byte(cursor).is_some_and(is_identifier_part) {
461            cursor += 1;
462        }
463        let word = self.source.get(start..cursor).unwrap_or(&[]);
464        if word.len() == 1
465            && word
466                .first()
467                .is_some_and(|byte| byte.eq_ignore_ascii_case(&b'x'))
468            && self.byte(cursor) == Some(b'\'')
469        {
470            return self.scan_blob(start, cursor);
471        }
472        self.offset = cursor;
473        Ok(Token {
474            kind: TokenKind::Identifier {
475                keyword: keyword::lookup(word),
476                quote: QuoteForm::Bare,
477            },
478            span: Span::new(start, cursor),
479        })
480    }
481
482    /// Scans the `'..'` body of a blob literal, which must be an even number of
483    /// hexadecimal digits.
484    fn scan_blob(&mut self, start: usize, quote: usize) -> Result<Token, LexError> {
485        let mut cursor = quote + 1;
486        let body = cursor;
487        loop {
488            match self.byte(cursor) {
489                None => {
490                    return Err(LexError {
491                        kind: LexErrorKind::UnterminatedQuote,
492                        offset: start as u32,
493                    })
494                }
495                Some(b'\'') => break,
496                Some(byte) if byte.is_ascii_hexdigit() => cursor += 1,
497                Some(_) => {
498                    return Err(LexError {
499                        kind: LexErrorKind::MalformedBlob,
500                        offset: start as u32,
501                    })
502                }
503            }
504        }
505        if !(cursor - body).is_multiple_of(2) {
506            return Err(LexError {
507                kind: LexErrorKind::MalformedBlob,
508                offset: start as u32,
509            });
510        }
511        self.offset = cursor + 1;
512        Ok(Token {
513            kind: TokenKind::Blob,
514            span: Span::new(start, cursor + 1),
515        })
516    }
517
518    /// Scans a numeric literal in every form the pinned release accepts.
519    fn scan_number(&mut self, start: usize) -> Result<Token, LexError> {
520        if self.byte(start) == Some(b'0')
521            && self
522                .byte(start + 1)
523                .is_some_and(|byte| byte.eq_ignore_ascii_case(&b'x'))
524        {
525            return self.scan_hex_number(start);
526        }
527        let mut cursor = start;
528        let mut float = false;
529        cursor = self.scan_digits(cursor);
530        if self.byte(cursor) == Some(b'.') {
531            float = true;
532            cursor = self.scan_digits(cursor + 1);
533        }
534        if self
535            .byte(cursor)
536            .is_some_and(|byte| byte.eq_ignore_ascii_case(&b'e'))
537        {
538            let mut lookahead = cursor + 1;
539            if matches!(self.byte(lookahead), Some(b'+') | Some(b'-')) {
540                lookahead += 1;
541            }
542            if self.byte(lookahead).is_some_and(is_digit) {
543                float = true;
544                cursor = self.scan_digits(lookahead);
545            }
546        }
547        // A digit run that runs straight into a word is not two tokens; SQLite
548        // rejects `123abc` rather than lexing an integer and an identifier.
549        if self.byte(cursor).is_some_and(is_identifier_part) {
550            return Err(LexError {
551                kind: LexErrorKind::MalformedNumber,
552                offset: start as u32,
553            });
554        }
555        self.offset = cursor;
556        Ok(Token {
557            kind: if float {
558                TokenKind::Float
559            } else {
560                TokenKind::Integer
561            },
562            span: Span::new(start, cursor),
563        })
564    }
565
566    /// Scans a `0x` literal, which has no fractional or exponent part.
567    fn scan_hex_number(&mut self, start: usize) -> Result<Token, LexError> {
568        let mut cursor = start + 2;
569        let digits = cursor;
570        while self
571            .byte(cursor)
572            .is_some_and(|byte| byte.is_ascii_hexdigit())
573        {
574            cursor += 1;
575        }
576        if cursor == digits || self.byte(cursor).is_some_and(is_identifier_part) {
577            return Err(LexError {
578                kind: LexErrorKind::MalformedNumber,
579                offset: start as u32,
580            });
581        }
582        self.offset = cursor;
583        Ok(Token {
584            kind: TokenKind::Integer,
585            span: Span::new(start, cursor),
586        })
587    }
588
589    /// Advances over a run of decimal digits, allowing SQLite's `_` separators.
590    fn scan_digits(&mut self, from: usize) -> usize {
591        let mut cursor = from;
592        while let Some(byte) = self.byte(cursor) {
593            if is_digit(byte) {
594                cursor += 1;
595                continue;
596            }
597            // A separator is only a separator between two digits.
598            if byte == b'_'
599                && cursor > from
600                && self.byte(cursor + 1).is_some_and(is_digit)
601                && self.byte(cursor.wrapping_sub(1)).is_some_and(is_digit)
602            {
603                cursor += 1;
604                continue;
605            }
606            break;
607        }
608        cursor
609    }
610
611    /// Scans `?`, `?NNN`, `:name`, `@name` and `$name`.
612    fn scan_parameter(&mut self, start: usize) -> Result<Token, LexError> {
613        let sigil = self.byte(start).unwrap_or(b'?');
614        let mut cursor = start + 1;
615        if sigil == b'?' {
616            cursor = self.scan_digits(cursor);
617            self.offset = cursor;
618            return Ok(Token {
619                kind: TokenKind::Parameter,
620                span: Span::new(start, cursor),
621            });
622        }
623        while self.byte(cursor).is_some_and(is_identifier_part) {
624            cursor += 1;
625        }
626        // `$name` accepts a bracketed or quoted suffix in SQLite's TCL variable
627        // syntax; the parenthesised form is the one that reaches SQL.
628        if sigil == b'$' && self.byte(cursor) == Some(b'(') {
629            while let Some(byte) = self.byte(cursor) {
630                cursor += 1;
631                if byte == b')' {
632                    break;
633                }
634            }
635        }
636        if cursor == start + 1 {
637            // A bare `:` or `@` is not a parameter. `:` is punctuation SQLite
638            // has no use for, so the byte is unrecognised.
639            return Err(LexError {
640                kind: LexErrorKind::MalformedParameter,
641                offset: start as u32,
642            });
643        }
644        self.offset = cursor;
645        Ok(Token {
646            kind: TokenKind::Parameter,
647            span: Span::new(start, cursor),
648        })
649    }
650
651    /// Scans punctuation and operators, longest form first.
652    fn scan_punctuator(&mut self, start: usize) -> Result<Token, LexError> {
653        let one = self.byte(start).unwrap_or(0);
654        let two = self.byte(start + 1);
655        let three = self.byte(start + 2);
656        let (punctuator, length) = match (one, two, three) {
657            (b'-', Some(b'>'), Some(b'>')) => (Punctuator::DoubleArrow, 3),
658            // **Before the two-byte forms, because `<=>` starts with `<=`.**
659            // These are pgvector's distance operators, and the longest-form-
660            // first rule is the only thing that keeps `v <=> q` from lexing as
661            // `v <= (> q)`.
662            (b'<', Some(b'-'), Some(b'>')) => (Punctuator::L2Distance, 3),
663            (b'<', Some(b'='), Some(b'>')) => (Punctuator::CosineDistance, 3),
664            (b'<', Some(b'#'), Some(b'>')) => (Punctuator::NegativeInnerProduct, 3),
665            (b'<', Some(b'+'), Some(b'>')) => (Punctuator::L1Distance, 3),
666            (b'<', Some(b'~'), Some(b'>')) => (Punctuator::HammingDistance, 3),
667            (b'<', Some(b'%'), Some(b'>')) => (Punctuator::JaccardDistance, 3),
668            (b'-', Some(b'>'), _) => (Punctuator::Arrow, 2),
669            (b'|', Some(b'|'), _) => (Punctuator::Concat, 2),
670            (b'<', Some(b'<'), _) => (Punctuator::ShiftLeft, 2),
671            (b'>', Some(b'>'), _) => (Punctuator::ShiftRight, 2),
672            (b'<', Some(b'='), _) => (Punctuator::LessEqual, 2),
673            (b'>', Some(b'='), _) => (Punctuator::GreaterEqual, 2),
674            (b'<', Some(b'>'), _) => (Punctuator::NotEqual, 2),
675            (b'!', Some(b'='), _) => (Punctuator::NotEqual, 2),
676            (b'=', Some(b'='), _) => (Punctuator::Equal, 2),
677            (b'(', _, _) => (Punctuator::LeftParen, 1),
678            (b')', _, _) => (Punctuator::RightParen, 1),
679            (b',', _, _) => (Punctuator::Comma, 1),
680            (b';', _, _) => (Punctuator::Semicolon, 1),
681            (b'.', _, _) => (Punctuator::Dot, 1),
682            (b'+', _, _) => (Punctuator::Plus, 1),
683            (b'-', _, _) => (Punctuator::Minus, 1),
684            (b'*', _, _) => (Punctuator::Star, 1),
685            (b'/', _, _) => (Punctuator::Slash, 1),
686            (b'%', _, _) => (Punctuator::Percent, 1),
687            (b'=', _, _) => (Punctuator::Equal, 1),
688            (b'<', _, _) => (Punctuator::Less, 1),
689            (b'>', _, _) => (Punctuator::Greater, 1),
690            (b'&', _, _) => (Punctuator::BitAnd, 1),
691            (b'|', _, _) => (Punctuator::BitOr, 1),
692            (b'~', _, _) => (Punctuator::BitNot, 1),
693            _ => {
694                return Err(LexError {
695                    kind: LexErrorKind::UnrecognisedByte,
696                    offset: start as u32,
697                })
698            }
699        };
700        self.offset = start + length;
701        Ok(Token {
702            kind: TokenKind::Punctuator(punctuator),
703            span: Span::new(start, start + length),
704        })
705    }
706}
707
708/// Returns whether the byte is SQL whitespace.
709pub fn is_space(byte: u8) -> bool {
710    matches!(byte, b' ' | b'\t' | b'\n' | b'\r' | 0x0b | 0x0c)
711}
712
713/// Returns whether the byte is an ASCII decimal digit.
714pub fn is_digit(byte: u8) -> bool {
715    byte.is_ascii_digit()
716}
717
718/// Returns whether the byte may begin a bare identifier.
719///
720/// SQLite treats every byte at or above 0x80 as an identifier character, which
721/// is how it accepts UTF-8 names without decoding them.
722pub fn is_identifier_start(byte: u8) -> bool {
723    byte.is_ascii_alphabetic() || byte == b'_' || byte >= 0x80
724}
725
726/// Returns whether the byte may continue a bare identifier.
727pub fn is_identifier_part(byte: u8) -> bool {
728    is_identifier_start(byte) || byte.is_ascii_digit() || byte == b'$'
729}
730
731/// Returns the unquoted text of an identifier token, undoubling escapes.
732///
733/// The common case is a bare word, which borrows. Only a quoted name that
734/// actually contains a doubled delimiter has to allocate.
735pub fn identifier_text<'a>(source: &'a [u8], token: Token) -> std::borrow::Cow<'a, [u8]> {
736    let raw = token.text(source);
737    let TokenKind::Identifier { quote, .. } = token.kind else {
738        return std::borrow::Cow::Borrowed(raw);
739    };
740    match quote {
741        QuoteForm::Bare => std::borrow::Cow::Borrowed(raw),
742        QuoteForm::Bracket => {
743            std::borrow::Cow::Borrowed(raw.get(1..raw.len().saturating_sub(1)).unwrap_or(&[]))
744        }
745        QuoteForm::Double => unquote(raw, b'"'),
746        QuoteForm::Backtick => unquote(raw, b'`'),
747    }
748}
749
750/// Returns the body of a `'string'` token with doubled quotes undoubled.
751pub fn string_text(source: &[u8], token: Token) -> std::borrow::Cow<'_, [u8]> {
752    unquote(token.text(source), b'\'')
753}
754
755/// Strips the delimiters and undoubles the escapes of a quoted run.
756fn unquote(raw: &[u8], delimiter: u8) -> std::borrow::Cow<'_, [u8]> {
757    let body = raw.get(1..raw.len().saturating_sub(1)).unwrap_or(&[]);
758    if !body.contains(&delimiter) {
759        return std::borrow::Cow::Borrowed(body);
760    }
761    let mut out = Vec::with_capacity(body.len());
762    let mut index = 0;
763    while let Some(byte) = body.get(index).copied() {
764        out.push(byte);
765        index += if byte == delimiter && body.get(index + 1) == Some(&delimiter) {
766            2
767        } else {
768            1
769        };
770    }
771    std::borrow::Cow::Owned(out)
772}
773
774/// Returns the bytes of a blob literal token, decoded from its hex digits.
775pub fn blob_bytes(source: &[u8], token: Token) -> Vec<u8> {
776    let raw = token.text(source);
777    let body = raw.get(2..raw.len().saturating_sub(1)).unwrap_or(&[]);
778    let mut out = Vec::with_capacity(body.len() / 2);
779    let mut index = 0;
780    while let (Some(high), Some(low)) = (body.get(index), body.get(index + 1)) {
781        let high = (*high as char).to_digit(16).unwrap_or(0) as u8;
782        let low = (*low as char).to_digit(16).unwrap_or(0) as u8;
783        out.push((high << 4) | low);
784        index += 2;
785    }
786    out
787}
788
789/// Converts a byte offset into a one-based line and column, scanning lazily.
790pub fn line_and_column(source: &[u8], offset: u32) -> (u32, u32) {
791    let limit = (offset as usize).min(source.len());
792    let mut line = 1u32;
793    let mut column = 1u32;
794    for byte in source.get(..limit).unwrap_or(&[]) {
795        if *byte == b'\n' {
796            line = line.saturating_add(1);
797            column = 1;
798        } else {
799            column = column.saturating_add(1);
800        }
801    }
802    (line, column)
803}
804
805#[cfg(test)]
806mod tests {
807    use super::*;
808
809    /// Collects every token of a source, for the tests below.
810    fn tokens(source: &str) -> Result<Vec<Token>, LexError> {
811        let bytes = source.as_bytes();
812        let mut lexer = Lexer::new(bytes);
813        let mut out = Vec::new();
814        loop {
815            let token = lexer.next_token()?;
816            if token.kind == TokenKind::EndOfInput {
817                return Ok(out);
818            }
819            out.push(token);
820        }
821    }
822
823    /// Every byte of the source belongs to exactly one token or to trivia, and
824    /// the spans are ordered and inside the source. This is the lexer's first
825    /// invariant and it is checkable directly.
826    #[test]
827    fn spans_are_ordered_disjoint_and_inside_the_source() {
828        let source = "SELECT a, 'x' /* c */ FROM t -- tail\nWHERE b=1;";
829        let found = tokens(source).expect("it lexes");
830        let mut previous_end = 0u32;
831        for token in &found {
832            assert!(token.span.start >= previous_end, "{token:?}");
833            assert!(token.span.end <= source.len() as u32, "{token:?}");
834            assert!(token.span.end > token.span.start, "{token:?}");
835            previous_end = token.span.end;
836        }
837    }
838
839    /// A keyword is an identifier token carrying a keyword, so the parser can
840    /// choose per position whether to accept it as a name.
841    #[test]
842    fn a_keyword_is_an_identifier_carrying_a_keyword() {
843        let found = tokens("select key").expect("it lexes");
844        assert_eq!(
845            found.first().and_then(|t| t.keyword()),
846            Some(Keyword::SELECT)
847        );
848        assert_eq!(found.get(1).and_then(|t| t.keyword()), Some(Keyword::KEY));
849        assert!(found
850            .get(1)
851            .and_then(|t| t.keyword())
852            .is_some_and(Keyword::may_fall_back));
853    }
854
855    /// The four quoting forms are distinguished, because only one of them may
856    /// later become a string literal.
857    #[test]
858    fn the_four_identifier_quote_forms_are_distinguished() {
859        let found = tokens("a \"b\" [c] `d`").expect("it lexes");
860        let forms: Vec<QuoteForm> = found
861            .iter()
862            .filter_map(|token| match token.kind {
863                TokenKind::Identifier { quote, .. } => Some(quote),
864                _ => None,
865            })
866            .collect();
867        assert_eq!(
868            forms,
869            vec![
870                QuoteForm::Bare,
871                QuoteForm::Double,
872                QuoteForm::Bracket,
873                QuoteForm::Backtick
874            ]
875        );
876    }
877
878    /// A doubled quote inside a string is one quote, and the borrow is only
879    /// given up when there is one.
880    #[test]
881    fn doubled_quotes_are_undoubled() {
882        let source = b"'it''s'";
883        let mut lexer = Lexer::new(source);
884        let token = lexer.next_token().expect("it lexes");
885        assert_eq!(token.kind, TokenKind::String);
886        assert_eq!(string_text(source, token).as_ref(), b"it's");
887
888        let plain = b"'plain'";
889        let mut lexer = Lexer::new(plain);
890        let token = lexer.next_token().expect("it lexes");
891        assert!(matches!(
892            string_text(plain, token),
893            std::borrow::Cow::Borrowed(_)
894        ));
895    }
896
897    /// An unterminated quote reports the byte that opened it, not the end of
898    /// input, because that is the offset a caller can act on.
899    #[test]
900    fn an_unterminated_quote_reports_its_opening_byte() {
901        let mut lexer = Lexer::new(b"SELECT 'abc");
902        assert_eq!(
903            lexer.next_token().map(|t| t.kind),
904            Ok(TokenKind::Identifier {
905                keyword: Some(Keyword::SELECT),
906                quote: QuoteForm::Bare
907            })
908        );
909        assert_eq!(
910            lexer.next_token(),
911            Err(LexError {
912                kind: LexErrorKind::UnterminatedQuote,
913                offset: 7
914            })
915        );
916    }
917
918    /// Numeric forms: decimal, leading dot, exponent, hexadecimal, and the
919    /// underscore separators the pinned release accepts.
920    #[test]
921    fn every_numeric_form_lexes() {
922        for (source, kind) in [
923            ("1", TokenKind::Integer),
924            ("1_000", TokenKind::Integer),
925            ("0x1f", TokenKind::Integer),
926            ("0XFF", TokenKind::Integer),
927            ("1.5", TokenKind::Float),
928            (".5", TokenKind::Float),
929            ("1.", TokenKind::Float),
930            ("1e10", TokenKind::Float),
931            ("1E+10", TokenKind::Float),
932            ("1.5e-3", TokenKind::Float),
933        ] {
934            let found = tokens(source).expect(source);
935            assert_eq!(found.first().map(|t| t.kind), Some(kind), "{source}");
936            assert_eq!(found.len(), 1, "{source}");
937        }
938    }
939
940    /// A number that runs into a word is one bad token, not two good ones.
941    #[test]
942    fn a_number_glued_to_a_word_is_rejected() {
943        assert_eq!(
944            tokens("123abc").map(|_| ()),
945            Err(LexError {
946                kind: LexErrorKind::MalformedNumber,
947                offset: 0
948            })
949        );
950    }
951
952    /// Blob literals must be an even number of hex digits, and the prefix is
953    /// case-insensitive.
954    #[test]
955    fn blob_literals_decode() {
956        let source = b"X'48690a'";
957        let mut lexer = Lexer::new(source);
958        let token = lexer.next_token().expect("it lexes");
959        assert_eq!(token.kind, TokenKind::Blob);
960        assert_eq!(blob_bytes(source, token), vec![0x48, 0x69, 0x0a]);
961        assert!(tokens("x'abc'").is_err());
962        assert!(tokens("x'zz'").is_err());
963    }
964
965    /// Every parameter form lexes as one token.
966    #[test]
967    fn every_parameter_form_lexes() {
968        for source in ["?", "?12", ":name", "@name", "$name"] {
969            let found = tokens(source).expect(source);
970            assert_eq!(found.len(), 1, "{source}");
971            assert_eq!(found.first().map(|t| t.kind), Some(TokenKind::Parameter));
972        }
973        assert!(tokens(":").is_err());
974    }
975
976    /// Both comment forms are trivia, and a line comment ends at the newline.
977    #[test]
978    fn comments_are_trivia() {
979        let found = tokens("1 -- comment\n+ /* block */ 2").expect("it lexes");
980        assert_eq!(found.len(), 3);
981        assert!(found.get(1).is_some_and(|t| t.is(Punctuator::Plus)));
982    }
983
984    /// An unterminated block comment at end of input is accepted, which is what
985    /// the pinned release does.
986    #[test]
987    fn an_unterminated_block_comment_at_end_of_input_is_accepted() {
988        let found = tokens("SELECT 1 /* trailing").expect("it lexes");
989        assert_eq!(found.len(), 2);
990    }
991
992    /// Operators lex longest-first, so `->>` never becomes `->` and `>`.
993    #[test]
994    fn operators_lex_longest_first() {
995        let found = tokens("a->>b->c||d<<e").expect("it lexes");
996        let punctuators: Vec<&'static str> = found
997            .iter()
998            .filter_map(|token| match token.kind {
999                TokenKind::Punctuator(punctuator) => Some(punctuator.as_str()),
1000                _ => None,
1001            })
1002            .collect();
1003        assert_eq!(punctuators, vec!["->>", "->", "||", "<<"]);
1004    }
1005
1006    /// Line and column are derived from an offset only when asked for, and
1007    /// count from one.
1008    #[test]
1009    fn line_and_column_count_from_one() {
1010        let source = b"SELECT\n  1";
1011        assert_eq!(line_and_column(source, 0), (1, 1));
1012        assert_eq!(line_and_column(source, 9), (2, 3));
1013    }
1014
1015    /// Bytes above 0x7f are identifier characters, so a UTF-8 name lexes as one
1016    /// token without the lexer decoding anything.
1017    #[test]
1018    fn high_bytes_are_identifier_characters() {
1019        let found = tokens("naïve").expect("it lexes");
1020        assert_eq!(found.len(), 1);
1021    }
1022}
inillucent_sql/lexer.rs

inillucent_sql/
lexer.rs
