rudb_parse/
token.rs

1//! What the tokenizer produces and what the matcher consumes.
2//!
3//! A token is twelve bytes and holds no string. The text stays in the query, the token holds a
4//! span into it, and nothing is decoded here: a string keeps its quotes and its escapes, a number
5//! keeps its underscores, an identifier keeps its case. Decoding is the transformer's job, and
6//! leaving it there is what keeps the whole token vector in cache for a query of any sane size.
7//!
8//! `spec/20-the-grammar.md` section 7 is the behaviour this has to match and why matching it is
9//! the largest single compatibility risk in the front end.
10
11use rudb_common::Span;
12
13/// A word is not a keyword.
14///
15/// `u16::MAX` rather than an `Option<u16>`, which would be four bytes and would put a branch on
16/// the path that reads the keyword out. There are 514 keywords and there is no prospect of 65,535.
17pub const NOT_A_KEYWORD: u16 = u16::MAX;
18
19/// What a token is.
20///
21/// DuckDB has one `IDENTIFIER` type covering both a bare word and a quoted one, and recovers the
22/// difference by looking at the first byte where it matters. We split them, because the grammar
23/// has a `QuotedIdentifier` rule and asking the token is cheaper and harder to get wrong than
24/// asking the source text. The two are otherwise treated alike everywhere upstream treats them
25/// alike, which is nearly everywhere.
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
27#[repr(u8)]
28pub enum Kind {
29    /// A bare word that is in no keyword class. `foo`, and also `ascending`, which is spelled by
30    /// a rule and is in no class, so it is a perfectly good column name.
31    Identifier,
32    /// A word in double quotes. Still an identifier, never a keyword, and case preserving in
33    /// exactly the same way a bare one is.
34    QuotedIdentifier,
35    /// A bare word that is in at least one keyword class. `keyword` on this token says which.
36    Keyword,
37    /// A numeric literal, with its underscores, its exponent and its decimal point as written.
38    Number,
39    /// A string literal, with its quotes. Single quoted, dollar quoted, or one of the four
40    /// prefixed forms, all of which arrive here as one token.
41    String,
42    /// Punctuation or an operator run. `(`, `,`, `::`, `!~~*` and `+` are all this.
43    Operator,
44    /// A `;`. Its own kind because `Program <- TopLevelStatement*` consumes it as one, and
45    /// because a statement boundary that the tokenizer decided would be a statement boundary the
46    /// grammar cannot change.
47    Terminator,
48    /// The sentinel at the end. Always present, always last, always exactly one.
49    EndOfInput,
50}
51
52impl Kind {
53    /// Whether this is a name, either spelling.
54    pub const fn is_identifier(self) -> bool {
55        matches!(self, Kind::Identifier | Kind::QuotedIdentifier)
56    }
57}
58
59/// Facts about the gap before a token, which the grammar cannot see and two rules need.
60///
61/// A bitfield rather than three `bool`s so that a token stays twelve bytes.
62#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
63pub struct Flags(u8);
64
65impl Flags {
66    /// There was a line break between the end of the previous token and the start of this one.
67    pub const NEWLINE: Flags = Flags(1 << 0);
68    /// A block comment ended in the gap before this token.
69    pub const BLOCK_COMMENT: Flags = Flags(1 << 1);
70    /// The token ran to the end of the input without its closing delimiter. Only a dollar quoted
71    /// string reaches the matcher this way; the other unterminated forms are errors.
72    pub const UNTERMINATED: Flags = Flags(1 << 2);
73
74    /// Whether every flag in `other` is set here.
75    pub const fn has(self, other: Flags) -> bool {
76        self.0 & other.0 == other.0
77    }
78
79    /// This set with `other` added.
80    pub const fn with(self, other: Flags) -> Flags {
81        Flags(self.0 | other.0)
82    }
83}
84
85/// One token. Twelve bytes, no allocation, no owned text.
86#[derive(Debug, Clone, Copy, PartialEq, Eq)]
87pub struct Token {
88    /// What it is.
89    pub kind: Kind,
90    /// What was in the gap before it.
91    pub flags: Flags,
92    /// The index into `generated::keywords::KEYWORDS`, or `NOT_A_KEYWORD`.
93    ///
94    /// Resolved once here rather than at every position the matcher considers the token, because
95    /// the matcher considers most tokens many times and the fold plus binary search is the
96    /// expensive part of asking.
97    pub keyword: u16,
98    /// Where it starts, as a byte offset into the query.
99    pub start: u32,
100    /// One past where it ends.
101    pub end: u32,
102}
103
104impl Token {
105    /// The span this token covers.
106    pub const fn span(self) -> Span {
107        Span::new(self.start, self.end)
108    }
109
110    /// The text of this token, given the query it came from.
111    ///
112    /// Both bounds came from a scan over the same string and always land on a character boundary,
113    /// so this cannot panic on well formed input. It is written as a slice rather than a checked
114    /// `get` because a token whose bounds are not on a boundary is a bug in the tokenizer and
115    /// silently returning nothing would hide it.
116    pub fn text(self, query: &str) -> &str {
117        &query[self.start as usize..self.end as usize]
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use super::{Flags, Kind, Token};
124
125    #[test]
126    fn a_token_is_twelve_bytes() {
127        // Not a style preference. A hundred token query is one cache line per ten tokens, and the
128        // matcher walks the vector many times over. If this ever fails, something grew a field
129        // that should have been computed instead.
130        assert_eq!(size_of::<Token>(), 12);
131    }
132
133    #[test]
134    fn the_flags_combine_and_read_back() {
135        let flags = Flags::default().with(Flags::NEWLINE).with(Flags::BLOCK_COMMENT);
136        assert!(flags.has(Flags::NEWLINE));
137        assert!(flags.has(Flags::BLOCK_COMMENT));
138        assert!(!flags.has(Flags::UNTERMINATED));
139        assert!(!Flags::default().has(Flags::NEWLINE));
140    }
141
142    #[test]
143    fn both_spellings_of_a_name_are_identifiers() {
144        assert!(Kind::Identifier.is_identifier());
145        assert!(Kind::QuotedIdentifier.is_identifier());
146        assert!(!Kind::Keyword.is_identifier());
147        assert!(!Kind::String.is_identifier());
148    }
149}
rudb_parse/token.rs

rudb_parse/
token.rs
