rupg_sql/
parser.rs

1//! The LR parser that runs the generated tables.
2//!
3//! Lifted from `crates/rudb-pgparse/src/parser.rs` of tamnd/rudb at f5f7065a (spec/04 section 4.9).
4
5use std::vec::Drain;
6
7use crate::actions::Parser;
8use crate::error::{Error, Notice};
9use crate::filter::Tokens;
10use crate::generated::keywords::{self, Keyword};
11use crate::generated::tables::{
12    ACTION_BASE, CHARACTER, CHECK, DEFAULT_GOTO, DEFAULT_REDUCTION, ENTRIES, ERROR, FINAL,
13    GOTO_BASE, NO_BASE, RULE_LENGTH, RULE_LHS, RULE_NAME, SYMBOL_NAME,
14};
15use crate::lexer::Lexer;
16
17/// The token of an ASCII character that is a token by itself, such as `;` or `+`.
18pub fn character(c: u8) -> Option<u16> {
19    let token = *CHARACTER.get(usize::from(c))?;
20    (token != 0).then_some(token)
21}
22
23/// The keyword that a word spells, with ASCII letters in any case, as `kwlist.h` has it.
24pub fn keyword(word: &str) -> Option<&'static Keyword> {
25    keywords::lookup(word.as_bytes())
26}
27
28/// Every keyword, in the order of `kwlist.h`.
29pub fn keywords() -> &'static [Keyword] {
30    &keywords::KEYWORDS
31}
32
33/// The place where the grammar stops accepting the input.
34#[derive(Clone, Copy, PartialEq, Eq, Debug)]
35pub struct SyntaxError {
36    /// The index of the token that the grammar does not accept. It is the number of tokens when the input ends too early.
37    pub token: usize,
38}
39
40/// The name of a rule as `productions.txt` has it, for example `a_expr.17`, or `None` when there is no such rule.
41pub fn rule_name(rule: usize) -> Option<&'static str> {
42    RULE_NAME.get(rule).copied()
43}
44
45/// The name of a symbol as `gram.y` has it, for example `IDENT`, `'+'` or `a_expr`, or `None` when there is no such symbol. The tokens come first.
46pub fn symbol_name(symbol: usize) -> Option<&'static str> {
47    SYMBOL_NAME.get(symbol).copied()
48}
49
50/// The entry of the action row of a state for a token, or the default of the state.
51fn action(state: usize, token: u16) -> i16 {
52    let base = ACTION_BASE[state];
53    if base != NO_BASE {
54        let at = base + i32::from(token);
55        if let Ok(at) = usize::try_from(at)
56            && CHECK.get(at) == Some(&(token as i16))
57        {
58            return ENTRIES[at];
59        }
60    }
61    match DEFAULT_REDUCTION[state] {
62        0 => ERROR,
63        rule => -(rule as i16),
64    }
65}
66
67/// The state that a nonterminal goes to from a state.
68fn goto(state: usize, nonterminal: usize) -> usize {
69    let base = GOTO_BASE[nonterminal];
70    if base != NO_BASE {
71        let at = base + state as i32;
72        if let Ok(at) = usize::try_from(at)
73            && CHECK.get(at) == Some(&(state as i16))
74        {
75            return ENTRIES[at] as usize;
76        }
77    }
78    usize::from(DEFAULT_GOTO[nonterminal])
79}
80
81/// What the parser does with the tokens and the rules: [`run`] asks it for the tokens and gives it each reduction.
82pub(crate) trait Machine {
83    /// The value of a symbol.
84    type Value;
85    /// The error of the lexer or of an action.
86    type Error;
87
88    /// The next token, its value and its location. The end of the input is token 0.
89    fn token(&mut self) -> Result<(u16, Self::Value, i32), Self::Error>;
90
91    /// Runs the action of `rule` on the values of its right side, with their locations and the location of the rule, and gives the value of the rule.
92    fn reduce(
93        &mut self,
94        rule: usize,
95        rhs: Drain<'_, Self::Value>,
96        at: &[i32],
97        here: i32,
98    ) -> Result<Self::Value, Self::Error>;
99}
100
101/// Runs the grammar. The parser asks for a token only when the state needs one, as the parser of bison does, so an error of the lexer after a syntax error does not come first. Gives the value of the start symbol, or `None` at a syntax error, which is at the last token that the machine gave.
102pub(crate) fn run<M: Machine>(machine: &mut M) -> Result<Option<M::Value>, M::Error> {
103    let mut stack: Vec<usize> = vec![0];
104    // The value and the location of each symbol on the stack. The first state has no symbol.
105    let mut values: Vec<M::Value> = Vec::new();
106    let mut locations: Vec<i32> = Vec::new();
107    let mut ahead: Option<(u16, M::Value, i32)> = None;
108    loop {
109        // The stack is never empty: a reduction pops the symbols of its right side, and the first state is under all of them.
110        let state = stack[stack.len() - 1];
111        let entry = if ACTION_BASE[state] == NO_BASE {
112            match DEFAULT_REDUCTION[state] {
113                0 => ERROR,
114                rule => -(rule as i16),
115            }
116        } else {
117            let token = match &ahead {
118                Some((token, _, _)) => *token,
119                None => ahead.insert(machine.token()?).0,
120            };
121            action(state, token)
122        };
123        if entry == ERROR {
124            if ahead.is_none() {
125                machine.token()?;
126            }
127            return Ok(None);
128        }
129        if entry > 0 {
130            if entry == FINAL {
131                return Ok(values.pop());
132            }
133            let Some((_, value, location)) = ahead.take() else {
134                // A shift is only in a state that reads a token, so there is a token.
135                return Ok(None);
136            };
137            stack.push(entry as usize);
138            values.push(value);
139            locations.push(location);
140            continue;
141        }
142        let rule = usize::from(entry.unsigned_abs());
143        let from = stack.len() - 1 - usize::from(RULE_LENGTH[rule]);
144        let at = &locations[from..];
145        // `YYLLOC_DEFAULT` of `gram.y`: the first location of the right side that is known.
146        let here = at.iter().copied().find(|&location| location >= 0).unwrap_or(-1);
147        let value = machine.reduce(rule, values.drain(from..), at, here)?;
148        locations.truncate(from);
149        values.push(value);
150        locations.push(here);
151        stack.truncate(from + 1);
152        let state = stack[stack.len() - 1];
153        stack.push(goto(state, usize::from(RULE_LHS[rule])));
154    }
155}
156
157/// The machine of [`recognize`]: a list of tokens and no actions.
158struct List<'a> {
159    tokens: &'a [u16],
160    at: usize,
161}
162
163impl Machine for List<'_> {
164    type Value = ();
165    type Error = std::convert::Infallible;
166
167    fn token(&mut self) -> Result<(u16, (), i32), Self::Error> {
168        self.at += 1;
169        Ok((self.tokens.get(self.at - 1).copied().unwrap_or(0), (), -1))
170    }
171
172    fn reduce(&mut self, _: usize, _: Drain<'_, ()>, _: &[i32], _: i32) -> Result<(), Self::Error> {
173        Ok(())
174    }
175}
176
177/// Runs the grammar over a list of tokens. The list does not end with the end token; the end of the slice is the end of the input.
178pub fn recognize(tokens: &[u16]) -> Result<(), SyntaxError> {
179    let mut list = List { tokens, at: 0 };
180    match run(&mut list) {
181        Ok(Some(())) => Ok(()),
182        Ok(None) | Err(_) => Err(SyntaxError { token: list.at - 1 }),
183    }
184}
185
186/// The machine of [`check`]: the tokens of a text and no actions.
187struct Check<'a> {
188    tokens: Tokens<'a>,
189    last: (usize, usize),
190}
191
192impl Machine for Check<'_> {
193    type Value = ();
194    type Error = Error;
195
196    fn token(&mut self) -> Result<(u16, (), i32), Error> {
197        let token = self.tokens.next_token()?;
198        self.last = (token.start, token.end);
199        Ok((token.kind, (), -1))
200    }
201
202    fn reduce(&mut self, _: usize, _: Drain<'_, ()>, _: &[i32], _: i32) -> Result<(), Error> {
203        Ok(())
204    }
205}
206
207/// Lexes and parses `text` as PostgreSQL does, and gives the first error of the lexer or the grammar, or the notices when there is no error.
208pub fn check(text: &str) -> Result<Vec<Notice>, Error> {
209    let mut check = Check { tokens: Tokens::new(text), last: (0, 0) };
210    if run(&mut check)?.is_some() {
211        Ok(check.tokens.take_notices())
212    } else {
213        let text = Lexer::new(text).text().as_bytes();
214        Err(Error::syntax(text, "syntax error", check.last.0, check.last.1))
215    }
216}
217
218/// The raw parse tree of `text` and the notices of the parse, as `raw_parser` of PostgreSQL gives them: a list with a `RawStmt` for each statement. An error is the first error of the lexer, the grammar or an action.
219pub fn parse(text: &str) -> Result<(crate::nodes::List, Vec<Notice>), Error> {
220    let mut parser = Parser::new(text);
221    if run(&mut parser)?.is_none() {
222        return Err(parser.yyerror("syntax error"));
223    }
224    Ok(parser.finish())
225}
226
227/// `typeStringToTypeName` without its checks: the `TypeName` of `text`, as `raw_parser` gives it in the mode `RAW_PARSE_TYPE_NAME`. An error is the first error of the lexer, the grammar or an action, at a byte offset in `text`.
228pub fn parse_type_name(text: &str) -> Result<crate::nodes::TypeName, Error> {
229    let mut parser = Parser::with_mode(text, Some(crate::token::MODE_TYPE_NAME));
230    if run(&mut parser)?.is_none() {
231        return Err(parser.yyerror("syntax error"));
232    }
233    match parser.finish().0.pop() {
234        Some(Some(crate::nodes::Node::TypeName(name))) => Ok(*name),
235        _ => Err(Error::internal("the mode of a type name gave no TypeName")),
236    }
237}
238
239/// The `SelectStmt` of a PL/pgSQL expression `text`, as `raw_parser` gives it in the mode `RAW_PARSE_PLPGSQL_EXPR`: the targets and the clauses of a `SELECT` without the word `SELECT`. An error is the first error of the lexer, the grammar or an action, at a byte offset in `text`.
240pub fn parse_plpgsql_expr(text: &str) -> Result<crate::nodes::Node, Error> {
241    let mut parser = Parser::with_mode(text, Some(crate::token::MODE_PLPGSQL_EXPR));
242    if run(&mut parser)?.is_none() {
243        return Err(parser.yyerror("syntax error"));
244    }
245    match parser.finish().0.pop() {
246        Some(Some(crate::nodes::Node::RawStmt(raw))) => {
247            raw.stmt.ok_or_else(|| Error::internal("the mode of an expression gave no statement"))
248        }
249        _ => Err(Error::internal("the mode of an expression gave no RawStmt")),
250    }
251}
252
253/// The `PLAssignStmt` of a PL/pgSQL assignment `text`, as `raw_parser` gives it in the modes `RAW_PARSE_PLPGSQL_ASSIGN1` to `RAW_PARSE_PLPGSQL_ASSIGN3`: the target with `names` names, which is 1, 2 or 3, its indirection, `:=` and the value. An error is the first error of the lexer, the grammar or an action, at a byte offset in `text`.
254pub fn parse_plpgsql_assign(text: &str, names: usize) -> Result<crate::nodes::Node, Error> {
255    let mode = match names {
256        1 => crate::token::MODE_PLPGSQL_ASSIGN1,
257        2 => crate::token::MODE_PLPGSQL_ASSIGN2,
258        _ => crate::token::MODE_PLPGSQL_ASSIGN3,
259    };
260    let mut parser = Parser::with_mode(text, Some(mode));
261    if run(&mut parser)?.is_none() {
262        return Err(parser.yyerror("syntax error"));
263    }
264    match parser.finish().0.pop() {
265        Some(Some(crate::nodes::Node::RawStmt(raw))) => {
266            raw.stmt.ok_or_else(|| Error::internal("the mode of an assignment gave no statement"))
267        }
268        _ => Err(Error::internal("the mode of an assignment gave no RawStmt")),
269    }
270}
271
272#[cfg(test)]
273mod tests {
274    use super::*;
275    use crate::token::*;
276
277    fn c(ch: u8) -> u16 {
278        character(ch).unwrap()
279    }
280
281    #[test]
282    fn statements() {
283        assert_eq!(recognize(&[]), Ok(()));
284        assert_eq!(recognize(&[SELECT, ICONST]), Ok(()));
285        assert_eq!(recognize(&[SELECT, ICONST, c(b'+'), ICONST, c(b';'), SELECT]), Ok(()));
286        assert_eq!(recognize(&[SELECT, FROM, IDENT]), Ok(()));
287        let create = [CREATE, TABLE, IDENT, c(b'('), IDENT, INT_P, c(b','), IDENT, IDENT, c(b')')];
288        assert_eq!(recognize(&create), Ok(()));
289        let not_in = [SELECT, IDENT, NOT_LA, IN_P, c(b'('), ICONST, c(b')')];
290        assert_eq!(recognize(&not_in), Ok(()));
291    }
292
293    #[test]
294    fn names() {
295        assert_eq!(rule_name(1), Some("parse_toplevel.1"));
296        assert_eq!(rule_name(crate::RULES), None);
297        assert_eq!(symbol_name(usize::from(SELECT)), Some("SELECT"));
298        assert_eq!(symbol_name(usize::from(c(b'+'))), Some("'+'"));
299        assert_eq!(symbol_name(crate::TOKENS), Some("$accept"));
300    }
301
302    #[test]
303    fn errors() {
304        assert_eq!(recognize(&[SELECT, ICONST, c(b'+')]), Err(SyntaxError { token: 3 }));
305        assert_eq!(recognize(&[SELECT, ICONST, ICONST]), Err(SyntaxError { token: 2 }));
306        assert_eq!(recognize(&[CREATE, SELECT]), Err(SyntaxError { token: 1 }));
307        // `a = b = c` is an error because `=` does not associate.
308        let chain = [SELECT, IDENT, c(b'='), IDENT, c(b'='), IDENT];
309        assert_eq!(recognize(&chain), Err(SyntaxError { token: 4 }));
310    }
311
312    #[test]
313    fn keywords() {
314        use crate::Category;
315        use crate::generated::keywords::KEYWORDS;
316        assert_eq!(
317            keyword("SELECT").map(|k| (k.token, k.category)),
318            Some((SELECT, Category::Reserved))
319        );
320        assert_eq!(keyword("abort").map(|k| k.token), Some(ABORT_P));
321        assert_eq!(keyword("zone").map(|k| k.bare_label), Some(true));
322        assert!(keyword("selectx").is_none());
323        assert!(keyword("").is_none());
324        for k in &KEYWORDS {
325            assert!(std::ptr::eq(keyword(k.name).unwrap(), k));
326            assert!(std::ptr::eq(keyword(&k.name.to_uppercase()).unwrap(), k));
327        }
328    }
329
330    /// The first error of each text, as the PostgreSQL 19 server gives it: the SQLSTATE, the position and the message.
331    #[test]
332    fn check_errors() {
333        let cases = [
334            ("SELEC 1", "42601", 1, "syntax error at or near \"SELEC\""),
335            ("SELECT 1 +", "42601", 11, "syntax error at end of input"),
336            ("SELECT 'abc", "42601", 8, "unterminated quoted string at or near \"'abc\""),
337            (
338                "SELECT /* x /* y */",
339                "42601",
340                8,
341                "unterminated /* comment at or near \"/* x /* y */\"",
342            ),
343            ("SELECT 1abc", "42601", 8, "trailing junk after numeric literal at or near \"1abc\""),
344            ("SELECT 0x", "42601", 8, "invalid hexadecimal integer at or near \"0x\""),
345            ("SELECT 0b2", "42601", 8, "trailing junk after numeric literal at or near \"0b2\""),
346            (
347                "SELECT 1_000$1",
348                "42601",
349                8,
350                "trailing junk after numeric literal at or near \"1_000$1\"",
351            ),
352            ("SELECT $1a", "42601", 8, "trailing junk after parameter at or near \"$1a\""),
353            ("SELECT \"\"", "42601", 8, "zero-length delimited identifier at or near \"\"\"\""),
354            ("SELECT E'\\u12'", "22025", 10, "invalid Unicode escape"),
355            ("SELECT E'\\0'", "22021", 0, "invalid byte sequence for encoding \"UTF8\": 0x00"),
356            ("SELECT E'\\xff'", "22021", 0, "invalid byte sequence for encoding \"UTF8\": 0xff"),
357            ("SELECT U&'\\0000'", "42601", 11, "invalid Unicode escape value"),
358            (
359                "SELECT U&'x' UESCAPE 'ab'",
360                "42601",
361                22,
362                "invalid Unicode escape character at or near \"'ab'\"",
363            ),
364            (
365                "SELECT U&'x' UESCAPE 1",
366                "42601",
367                22,
368                "UESCAPE must be followed by a simple string literal at or near \"1\"",
369            ),
370            (
371                "SELECT U&'x' UESCAPE",
372                "42601",
373                21,
374                "UESCAPE must be followed by a simple string literal at end of input",
375            ),
376            (
377                "SELECT $99999999999",
378                "42601",
379                8,
380                "parameter number too large at or near \"$99999999999\"",
381            ),
382            ("SELECT 'a' 'b'", "42601", 12, "syntax error at or near \"'b'\""),
383            (
384                "SELECT $a$abc$b$",
385                "42601",
386                8,
387                "unterminated dollar-quoted string at or near \"$a$abc$b$\"",
388            ),
389            ("SELECT B'01", "42601", 8, "unterminated bit string literal at or near \"B'01\""),
390            (
391                "SELECT X'0f",
392                "42601",
393                8,
394                "unterminated hexadecimal string literal at or near \"X'0f\"",
395            ),
396            ("SELECT E'\\ud83d'", "42601", 16, "invalid Unicode surrogate pair at or near \"'\""),
397            (
398                "SELECT E'\\ud83d\\u0041'",
399                "42601",
400                16,
401                "invalid Unicode surrogate pair at or near \"\\u0041\"",
402            ),
403            (
404                "SELECT E'\\udc00'",
405                "42601",
406                10,
407                "invalid Unicode surrogate pair at or near \"\\udc00\"",
408            ),
409            (
410                "SELECT E'\\U00110000'",
411                "42601",
412                10,
413                "invalid Unicode escape value at or near \"\\U00110000\"",
414            ),
415            ("SELECT U&'\\D83Dx'", "42601", 16, "invalid Unicode surrogate pair"),
416            ("SELECT U&'\\12'", "42601", 11, "invalid Unicode escape"),
417            ("SELECT U&'!0041' UESCAPE '!' 1", "42601", 30, "syntax error at or near \"1\""),
418            ("SELECT 1e+", "42601", 8, "trailing junk after numeric literal at or near \"1e+\""),
419            ("SELECT 1..2", "42601", 9, "syntax error at or near \"..\""),
420            ("SELECT é FROM 1", "42601", 15, "syntax error at or near \"1\""),
421            ("SELECT 'a'\n-- c\n'b' 1", "42601", 21, "syntax error at or near \"1\""),
422            ("SELECT 1 =- 1 1", "42601", 15, "syntax error at or near \"1\""),
423            ("SELECT 1 <=> 1 1", "42601", 16, "syntax error at or near \"1\""),
424            ("SELECT 0x_", "42601", 8, "invalid hexadecimal integer at or near \"0x_\""),
425            ("SELECT E'\\", "42601", 8, "unterminated quoted string at or near \"E'\\\""),
426            ("SELECT 1 WITH ORDINALITY", "42601", 10, "syntax error at or near \"WITH\""),
427            ("SELECT 1 /* a */ /* b", "42601", 18, "unterminated /* comment at or near \"/* b\""),
428            ("SELECT $1 $2", "42601", 11, "syntax error at or near \"$2\""),
429        ];
430        for (text, code, position, message) in cases {
431            let error = check(text).unwrap_err();
432            let got =
433                (error.code.as_str(), error.position(text).unwrap_or(0), error.message.as_str());
434            assert_eq!(got, (code, position, message), "{text}");
435        }
436        assert_eq!(check("SELECT 1 NOT IN (1); SELECT 'a'\n'b'"), Ok(Vec::new()));
437        // The lexer does not read past a syntax error, so the open string after it is no error.
438        assert_eq!(check("SELEC 1 'abc").unwrap_err().message, "syntax error at or near \"SELEC\"");
439        assert_eq!(check(&"a".repeat(64)).unwrap_err().code.as_str(), "42601");
440        let notices = check(&format!("SELECT {}", "a".repeat(64))).unwrap();
441        assert_eq!(notices[0].code.as_str(), "42622");
442    }
443}
rupg_sql/parser.rs

rupg_sql/
parser.rs
