basalt/sql/
parser.rs

1/// Recursive-descent SQL parser with operator precedence.
2use super::ast::*;
3use super::lexer::{Token, TokenSpan};
4use crate::types::{ColumnType, Value};
5
6#[derive(Debug)]
7pub struct ParseError {
8    pub message: String,
9    pub offset: usize,
10}
11
12pub struct Parser {
13    tokens: Vec<TokenSpan>,
14    pos: usize,
15    expression_depth: usize,
16    statement_depth: usize,
17}
18
19pub fn parse(input: &str) -> Result<Vec<Statement>, ParseError> {
20    let tokens = super::lexer::lex(input).map_err(|e| ParseError {
21        message: e.message,
22        offset: e.offset,
23    })?;
24    let mut p = Parser {
25        tokens,
26        pos: 0,
27        expression_depth: 0,
28        statement_depth: 0,
29    };
30    let mut stmts = Vec::new();
31    while !p.at_eof() {
32        stmts.push(p.parse_statement()?);
33        p.expect_semi_or_eof()?;
34    }
35    Ok(stmts)
36}
37
38impl Parser {
39    fn cur(&self) -> &Token {
40        &self.tokens[self.pos].token
41    }
42    fn cur_offset(&self) -> usize {
43        self.tokens[self.pos].offset
44    }
45    fn at_eof(&self) -> bool {
46        matches!(self.cur(), Token::Eof)
47    }
48
49    fn advance(&mut self) -> Token {
50        let t = self.tokens[self.pos].token.clone();
51        if !matches!(t, Token::Eof) {
52            self.pos += 1;
53        }
54        t
55    }
56
57    fn err<T>(&self, msg: impl Into<String>) -> Result<T, ParseError> {
58        Err(ParseError {
59            message: msg.into(),
60            offset: self.cur_offset(),
61        })
62    }
63
64    fn accept_keyword(&mut self, kw: &str) -> bool {
65        if let Token::Ident(s) = self.cur()
66            && s.eq_ignore_ascii_case(kw)
67        {
68            self.advance();
69            return true;
70        }
71        false
72    }
73
74    fn expect_keyword(&mut self, kw: &str) -> Result<(), ParseError> {
75        if self.accept_keyword(kw) {
76            Ok(())
77        } else {
78            self.err(format!("expected {kw}"))
79        }
80    }
81
82    fn accept(&mut self, t: &Token) -> bool {
83        if self.cur() == t {
84            self.advance();
85            true
86        } else {
87            false
88        }
89    }
90
91    fn expect(&mut self, t: &Token) -> Result<(), ParseError> {
92        if self.accept(t) {
93            Ok(())
94        } else {
95            self.err(format!("expected {t:?}"))
96        }
97    }
98
99    fn expect_ident(&mut self) -> Result<String, ParseError> {
100        match self.cur().clone() {
101            Token::Ident(s) => {
102                self.advance();
103                Ok(s)
104            }
105            Token::QuotedIdent(s) => {
106                self.advance();
107                Ok(s)
108            }
109            _ => self.err("expected identifier"),
110        }
111    }
112
113    fn expect_semi_or_eof(&mut self) -> Result<(), ParseError> {
114        if self.at_eof() {
115            return Ok(());
116        }
117        self.expect(&Token::Semi)
118    }
119
120    fn parse_statement(&mut self) -> Result<Statement, ParseError> {
121        if self.statement_depth >= MAX_STATEMENT_DEPTH {
122            return self.err(format!(
123                "SQL statement nesting exceeds the {MAX_STATEMENT_DEPTH}-level limit"
124            ));
125        }
126        self.statement_depth += 1;
127        let result = self.parse_statement_inner();
128        self.statement_depth -= 1;
129        result
130    }
131
132    fn parse_statement_inner(&mut self) -> Result<Statement, ParseError> {
133        match self.cur().clone() {
134            Token::Ident(kw) if kw.eq_ignore_ascii_case("CREATE") => self.parse_create(),
135            Token::Ident(kw) if kw.eq_ignore_ascii_case("DROP") => self.parse_drop(),
136            Token::Ident(kw) if kw.eq_ignore_ascii_case("INSERT") => self.parse_insert(),
137            Token::Ident(kw) if kw.eq_ignore_ascii_case("SELECT") => self.parse_select(),
138            Token::Ident(kw) if kw.eq_ignore_ascii_case("UPDATE") => self.parse_update(),
139            Token::Ident(kw) if kw.eq_ignore_ascii_case("DELETE") => self.parse_delete(),
140            Token::Ident(kw) if kw.eq_ignore_ascii_case("BEGIN") => {
141                self.advance();
142                Ok(Statement::Begin)
143            }
144            Token::Ident(kw) if kw.eq_ignore_ascii_case("COMMIT") => {
145                self.advance();
146                Ok(Statement::Commit)
147            }
148            Token::Ident(kw) if kw.eq_ignore_ascii_case("ROLLBACK") => {
149                self.advance();
150                Ok(Statement::Rollback)
151            }
152            Token::Ident(kw) if kw.eq_ignore_ascii_case("CHECKPOINT") => {
153                self.advance();
154                Ok(Statement::Checkpoint)
155            }
156            Token::Ident(kw) if kw.eq_ignore_ascii_case("EXPLAIN") => {
157                self.advance();
158                Ok(Statement::Explain(Box::new(self.parse_statement()?)))
159            }
160            _ => self.err("expected a SQL statement"),
161        }
162    }
163
164    fn parse_create(&mut self) -> Result<Statement, ParseError> {
165        self.expect_keyword("CREATE")?;
166        if self.accept_keyword("TABLE") {
167            return self.parse_create_table_tail();
168        }
169        let unique = self.accept_keyword("UNIQUE");
170        self.expect_keyword("INDEX")?;
171        let if_not_exists = if self.accept_keyword("IF") {
172            self.expect_keyword("NOT")?;
173            self.expect_keyword("EXISTS")?;
174            true
175        } else {
176            false
177        };
178        let name = self.expect_ident()?;
179        self.expect_keyword("ON")?;
180        let table = self.expect_ident()?;
181        self.expect(&Token::LParen)?;
182        let column = self.expect_ident()?;
183        self.expect(&Token::RParen)?;
184        Ok(Statement::CreateIndex {
185            name,
186            table,
187            column,
188            unique,
189            if_not_exists,
190        })
191    }
192
193    fn parse_create_table_tail(&mut self) -> Result<Statement, ParseError> {
194        let if_not_exists = if self.accept_keyword("IF") {
195            self.expect_keyword("NOT")?;
196            self.expect_keyword("EXISTS")?;
197            true
198        } else {
199            false
200        };
201        let name = self.expect_ident()?;
202        self.expect(&Token::LParen)?;
203        let mut columns = Vec::new();
204        loop {
205            let cname = self.expect_ident()?;
206            let tyname = self.expect_ident()?;
207            let ty = ColumnType::parse(&tyname).ok_or_else(|| ParseError {
208                message: format!("unknown type {tyname}"),
209                offset: self.cur_offset(),
210            })?;
211            let mut primary_key = false;
212            let mut not_null = false;
213            let mut unique = false;
214            loop {
215                if self.accept_keyword("PRIMARY") {
216                    self.expect_keyword("KEY")?;
217                    primary_key = true;
218                    not_null = true;
219                } else if self.accept_keyword("NOT") {
220                    self.expect_keyword("NULL")?;
221                    not_null = true;
222                } else if self.accept_keyword("UNIQUE") {
223                    unique = true;
224                } else {
225                    break;
226                }
227            }
228            columns.push(ColumnDef {
229                name: cname,
230                ty,
231                primary_key,
232                not_null,
233                unique,
234            });
235            if self.accept(&Token::Comma) {
236                continue;
237            }
238            break;
239        }
240        self.expect(&Token::RParen)?;
241        Ok(Statement::CreateTable {
242            name,
243            if_not_exists,
244            columns,
245        })
246    }
247
248    fn parse_drop(&mut self) -> Result<Statement, ParseError> {
249        self.expect_keyword("DROP")?;
250        if self.accept_keyword("INDEX") {
251            let if_exists = if self.accept_keyword("IF") {
252                self.expect_keyword("EXISTS")?;
253                true
254            } else {
255                false
256            };
257            let name = self.expect_ident()?;
258            return Ok(Statement::DropIndex { name, if_exists });
259        }
260        self.expect_keyword("TABLE")?;
261        let if_exists = if self.accept_keyword("IF") {
262            self.expect_keyword("EXISTS")?;
263            true
264        } else {
265            false
266        };
267        let name = self.expect_ident()?;
268        Ok(Statement::DropTable { name, if_exists })
269    }
270
271    fn parse_insert(&mut self) -> Result<Statement, ParseError> {
272        self.expect_keyword("INSERT")?;
273        self.expect_keyword("INTO")?;
274        let table = self.expect_ident()?;
275        let columns = if self.accept(&Token::LParen) {
276            let mut cols = Vec::new();
277            loop {
278                cols.push(self.expect_ident()?);
279                if self.accept(&Token::Comma) {
280                    continue;
281                }
282                break;
283            }
284            self.expect(&Token::RParen)?;
285            Some(cols)
286        } else {
287            None
288        };
289        if matches!(self.cur(), Token::Ident(keyword) if keyword.eq_ignore_ascii_case("SELECT")) {
290            let query = self.parse_select()?;
291            return Ok(Statement::InsertSelect {
292                table,
293                columns,
294                query: Box::new(query),
295            });
296        }
297        self.expect_keyword("VALUES")?;
298        let mut rows = Vec::new();
299        loop {
300            self.expect(&Token::LParen)?;
301            let mut row = Vec::new();
302            loop {
303                row.push(self.parse_expr(0)?);
304                if self.accept(&Token::Comma) {
305                    continue;
306                }
307                break;
308            }
309            self.expect(&Token::RParen)?;
310            rows.push(row);
311            if self.accept(&Token::Comma) {
312                continue;
313            }
314            break;
315        }
316        Ok(Statement::Insert {
317            table,
318            columns,
319            rows,
320        })
321    }
322
323    fn parse_select(&mut self) -> Result<Statement, ParseError> {
324        self.expect_keyword("SELECT")?;
325        let distinct = self.accept_keyword("DISTINCT");
326        let columns = if self.accept(&Token::Star) {
327            SelectItems::Star
328        } else {
329            let mut items = Vec::new();
330            loop {
331                items.push(self.parse_select_item()?);
332                if self.accept(&Token::Comma) {
333                    continue;
334                }
335                break;
336            }
337            SelectItems::List(items)
338        };
339        let (from, from_alias) = if self.accept_keyword("FROM") {
340            let from = self.expect_ident()?;
341            let alias = self.parse_optional_alias()?;
342            (from, alias)
343        } else {
344            (String::new(), None)
345        };
346        let mut joins = Vec::new();
347        loop {
348            let kind = if self.accept_keyword("JOIN") {
349                Some(crate::sql::ast::JoinKind::Inner)
350            } else if self.accept_keyword("INNER") {
351                self.expect_keyword("JOIN")?;
352                Some(crate::sql::ast::JoinKind::Inner)
353            } else if self.accept_keyword("LEFT") {
354                let _ = self.accept_keyword("OUTER");
355                self.expect_keyword("JOIN")?;
356                Some(crate::sql::ast::JoinKind::Left)
357            } else if self.accept_keyword("RIGHT") {
358                let _ = self.accept_keyword("OUTER");
359                self.expect_keyword("JOIN")?;
360                Some(crate::sql::ast::JoinKind::Right)
361            } else if self.accept_keyword("FULL") {
362                let _ = self.accept_keyword("OUTER");
363                self.expect_keyword("JOIN")?;
364                Some(crate::sql::ast::JoinKind::Full)
365            } else if self.accept_keyword("CROSS") {
366                self.expect_keyword("JOIN")?;
367                Some(crate::sql::ast::JoinKind::Cross)
368            } else {
369                None
370            };
371            let Some(kind) = kind else { break };
372            let table = self.expect_ident()?;
373            let alias = self.parse_optional_alias()?;
374            let on = if self.accept_keyword("ON") {
375                if kind == crate::sql::ast::JoinKind::Cross {
376                    return self.err("CROSS JOIN cannot have an ON condition");
377                }
378                Some(self.parse_expr(0)?)
379            } else if kind == crate::sql::ast::JoinKind::Cross {
380                None
381            } else {
382                return self.err("JOIN expects an ON condition");
383            };
384            joins.push(crate::sql::ast::JoinClause {
385                kind,
386                table,
387                alias,
388                on,
389            });
390        }
391        let where_clause = if self.accept_keyword("WHERE") {
392            Some(self.parse_expr(0)?)
393        } else {
394            None
395        };
396        let mut group_by = Vec::new();
397        if self.accept_keyword("GROUP") {
398            self.expect_keyword("BY")?;
399            loop {
400                group_by.push(self.parse_expr(0)?);
401                if self.accept(&Token::Comma) {
402                    continue;
403                }
404                break;
405            }
406        }
407        let having = if self.accept_keyword("HAVING") {
408            Some(self.parse_expr(0)?)
409        } else {
410            None
411        };
412        let mut order_by = Vec::new();
413        let mut order_by_exprs = Vec::new();
414        if self.accept_keyword("ORDER") {
415            self.expect_keyword("BY")?;
416            loop {
417                let expression = self.parse_expr(0)?;
418                let col = order_label(&expression);
419                let asc = if self.accept_keyword("DESC") {
420                    false
421                } else {
422                    self.accept_keyword("ASC");
423                    true
424                };
425                order_by.push((col, asc));
426                order_by_exprs.push((expression, asc));
427                if self.accept(&Token::Comma) {
428                    continue;
429                }
430                break;
431            }
432        }
433        let limit = if self.accept_keyword("LIMIT") {
434            match self.advance() {
435                Token::Integer(n) if n >= 0 => Some(u64::try_from(n).map_err(|_| ParseError {
436                    message: "LIMIT is out of range".into(),
437                    offset: self.cur_offset(),
438                })?),
439                _ => return self.err("LIMIT expects an integer"),
440            }
441        } else {
442            None
443        };
444        let offset = if self.accept_keyword("OFFSET") {
445            match self.advance() {
446                Token::Integer(n) if n >= 0 => Some(u64::try_from(n).map_err(|_| ParseError {
447                    message: "OFFSET is out of range".into(),
448                    offset: self.cur_offset(),
449                })?),
450                _ => return self.err("OFFSET expects a non-negative integer"),
451            }
452        } else {
453            None
454        };
455        Ok(Statement::Select {
456            distinct,
457            columns,
458            from,
459            from_alias,
460            joins,
461            where_clause,
462            group_by,
463            having,
464            order_by,
465            order_by_exprs,
466            limit,
467            offset,
468        })
469    }
470
471    fn parse_update(&mut self) -> Result<Statement, ParseError> {
472        self.expect_keyword("UPDATE")?;
473        let table = self.expect_ident()?;
474        self.expect_keyword("SET")?;
475        let mut assignments = Vec::new();
476        loop {
477            let col = self.expect_ident()?;
478            self.expect(&Token::Eq)?;
479            let val = self.parse_expr(0)?;
480            assignments.push((col, val));
481            if self.accept(&Token::Comma) {
482                continue;
483            }
484            break;
485        }
486        let where_clause = if self.accept_keyword("WHERE") {
487            Some(self.parse_expr(0)?)
488        } else {
489            None
490        };
491        Ok(Statement::Update {
492            table,
493            assignments,
494            where_clause,
495        })
496    }
497
498    fn parse_delete(&mut self) -> Result<Statement, ParseError> {
499        self.expect_keyword("DELETE")?;
500        self.expect_keyword("FROM")?;
501        let table = self.expect_ident()?;
502        let where_clause = if self.accept_keyword("WHERE") {
503            Some(self.parse_expr(0)?)
504        } else {
505            None
506        };
507        Ok(Statement::Delete {
508            table,
509            where_clause,
510        })
511    }
512
513    fn parse_select_item(&mut self) -> Result<Expr, ParseError> {
514        let expr = self.parse_expr(0)?;
515        let alias = if self.accept_keyword("AS") {
516            Some(self.expect_ident()?)
517        } else if let Token::Ident(name) = self.cur() {
518            if !is_clause_keyword(name) {
519                Some(self.expect_ident()?)
520            } else {
521                None
522            }
523        } else if matches!(self.cur(), Token::QuotedIdent(_)) {
524            Some(self.expect_ident()?)
525        } else {
526            None
527        };
528        Ok(match alias {
529            Some(alias) => Expr::Alias {
530                expr: Box::new(expr),
531                alias,
532            },
533            None => expr,
534        })
535    }
536
537    fn parse_optional_alias(&mut self) -> Result<Option<String>, ParseError> {
538        if self.accept_keyword("AS") {
539            return Ok(Some(self.expect_ident()?));
540        }
541        match self.cur() {
542            Token::Ident(name) if !is_clause_keyword(name) => Ok(Some(self.expect_ident()?)),
543            Token::QuotedIdent(_) => Ok(Some(self.expect_ident()?)),
544            _ => Ok(None),
545        }
546    }
547
548    // ---- expressions (precedence climbing) ----
549
550    pub fn parse_expr(&mut self, min_prec: u8) -> Result<Expr, ParseError> {
551        if self.expression_depth >= MAX_EXPRESSION_DEPTH {
552            return self.err(format!(
553                "SQL expression nesting exceeds the {MAX_EXPRESSION_DEPTH}-level limit"
554            ));
555        }
556        self.expression_depth += 1;
557        let result = self.parse_expr_inner(min_prec);
558        self.expression_depth -= 1;
559        result
560    }
561
562    fn parse_expr_inner(&mut self, min_prec: u8) -> Result<Expr, ParseError> {
563        let mut left = self.parse_unary()?;
564        loop {
565            let op = match self.cur() {
566                Token::Eq => BinOp::Eq,
567                Token::NotEq => BinOp::NotEq,
568                Token::Lt => BinOp::Lt,
569                Token::LtEq => BinOp::LtEq,
570                Token::Gt => BinOp::Gt,
571                Token::GtEq => BinOp::GtEq,
572                Token::Plus => BinOp::Add,
573                Token::Minus => BinOp::Sub,
574                Token::Star => BinOp::Mul,
575                Token::Slash => BinOp::Div,
576                Token::Percent => BinOp::Mod,
577                Token::Ident(s) if s.eq_ignore_ascii_case("AND") => BinOp::And,
578                Token::Ident(s) if s.eq_ignore_ascii_case("OR") => BinOp::Or,
579                _ => break,
580            };
581            let prec = bin_prec(op);
582            if prec < min_prec {
583                break;
584            }
585            self.advance();
586            // comparison ops are non-associative: parse right side at prec+1
587            let right = self.parse_expr(prec + 1)?;
588            left = Expr::Binary {
589                left: Box::new(left),
590                op,
591                right: Box::new(right),
592            };
593        }
594        Ok(left)
595    }
596
597    fn parse_unary(&mut self) -> Result<Expr, ParseError> {
598        if self.accept_keyword("NOT") {
599            let e = self.parse_expr(NOT_PREC)?;
600            return Ok(Expr::Unary {
601                op: UnaryOp::Not,
602                expr: Box::new(e),
603            });
604        }
605        if self.accept(&Token::Minus) {
606            if let Token::Integer(value) = self.cur()
607                && *value == i64::MAX as i128 + 1
608            {
609                self.advance();
610                return Ok(Expr::Literal(Value::Integer(i64::MIN)));
611            }
612            let e = self.parse_expr(UNARY_PREC)?;
613            return Ok(Expr::Unary {
614                op: UnaryOp::Neg,
615                expr: Box::new(e),
616            });
617        }
618        let atom = self.parse_atom()?;
619        if self.accept_keyword("IS") {
620            let negated = self.accept_keyword("NOT");
621            self.expect_keyword("NULL")?;
622            return Ok(Expr::IsNull {
623                expr: Box::new(atom),
624                negated,
625            });
626        }
627        Ok(atom)
628    }
629
630    fn parse_atom(&mut self) -> Result<Expr, ParseError> {
631        match self.cur().clone() {
632            Token::Integer(n) => {
633                self.advance();
634                let value = i64::try_from(n).map_err(|_| ParseError {
635                    message: "integer out of range".into(),
636                    offset: self.cur_offset(),
637                })?;
638                Ok(Expr::Literal(Value::Integer(value)))
639            }
640            Token::Real(f) => {
641                self.advance();
642                Ok(Expr::Literal(Value::Real(f)))
643            }
644            Token::Str(s) => {
645                self.advance();
646                Ok(Expr::Literal(Value::Text(s)))
647            }
648            Token::LParen => {
649                self.advance();
650                let e = self.parse_expr(0)?;
651                self.expect(&Token::RParen)?;
652                Ok(e)
653            }
654            Token::Minus => {
655                self.advance();
656                let e = self.parse_expr(UNARY_PREC)?;
657                Ok(Expr::Unary {
658                    op: UnaryOp::Neg,
659                    expr: Box::new(e),
660                })
661            }
662            Token::Ident(s) => {
663                self.advance();
664                match s.to_uppercase().as_str() {
665                    "NULL" => Ok(Expr::Literal(Value::Null)),
666                    "TRUE" => Ok(Expr::Literal(Value::Boolean(true))),
667                    "FALSE" => Ok(Expr::Literal(Value::Boolean(false))),
668                    _ if self.accept(&Token::LParen) => {
669                        let distinct = self.accept_keyword("DISTINCT");
670                        let mut args = Vec::new();
671                        if !self.accept(&Token::RParen) {
672                            if self.accept(&Token::Star) {
673                                args.push(Expr::Column("*".into()));
674                            } else {
675                                loop {
676                                    args.push(self.parse_expr(0)?);
677                                    if self.accept(&Token::Comma) {
678                                        continue;
679                                    }
680                                    break;
681                                }
682                            }
683                            self.expect(&Token::RParen)?;
684                        }
685                        Ok(Expr::Function {
686                            name: s,
687                            args,
688                            distinct,
689                        })
690                    }
691                    _ if self.accept(&Token::Dot) => {
692                        if self.accept(&Token::Star) {
693                            Ok(Expr::QualifiedWildcard(s))
694                        } else {
695                            let column = self.expect_ident()?;
696                            Ok(Expr::ColumnRef {
697                                relation: s,
698                                column,
699                            })
700                        }
701                    }
702                    _ => Ok(Expr::Column(s)),
703                }
704            }
705            Token::QuotedIdent(s) => {
706                self.advance();
707                if self.accept(&Token::Dot) {
708                    if self.accept(&Token::Star) {
709                        Ok(Expr::QualifiedWildcard(s))
710                    } else {
711                        let column = self.expect_ident()?;
712                        Ok(Expr::ColumnRef {
713                            relation: s,
714                            column,
715                        })
716                    }
717                } else {
718                    Ok(Expr::Column(s))
719                }
720            }
721            _ => self.err("expected expression"),
722        }
723    }
724}
725
726const NOT_PREC: u8 = 3;
727const UNARY_PREC: u8 = 6;
728const MAX_EXPRESSION_DEPTH: usize = 128;
729const MAX_STATEMENT_DEPTH: usize = 64;
730
731fn bin_prec(op: BinOp) -> u8 {
732    match op {
733        BinOp::Or => 1,
734        BinOp::And => 2,
735        BinOp::Eq | BinOp::NotEq | BinOp::Lt | BinOp::LtEq | BinOp::Gt | BinOp::GtEq => 3,
736        BinOp::Add | BinOp::Sub => 4,
737        BinOp::Mul | BinOp::Div | BinOp::Mod => 5,
738    }
739}
740
741fn is_clause_keyword(value: &str) -> bool {
742    matches!(
743        value.to_ascii_uppercase().as_str(),
744        "FROM"
745            | "WHERE"
746            | "GROUP"
747            | "HAVING"
748            | "ORDER"
749            | "LIMIT"
750            | "OFFSET"
751            | "JOIN"
752            | "INNER"
753            | "LEFT"
754            | "RIGHT"
755            | "FULL"
756            | "OUTER"
757            | "CROSS"
758            | "ON"
759            | "ASC"
760            | "DESC"
761            | "AND"
762            | "OR"
763    )
764}
765
766fn order_label(expr: &Expr) -> String {
767    match expr {
768        Expr::Column(name) => name.clone(),
769        Expr::ColumnRef { relation, column } => format!("{relation}.{column}"),
770        Expr::Function { name, .. } => name.clone(),
771        _ => "expr".into(),
772    }
773}
774
775#[cfg(test)]
776mod tests {
777    use super::*;
778
779    fn one(input: &str) -> Statement {
780        let mut stmts = parse(input).expect("parse failed");
781        assert_eq!(stmts.len(), 1);
782        stmts.pop().unwrap()
783    }
784
785    #[test]
786    fn parses_create_table() {
787        let s = one(
788            "CREATE TABLE IF NOT EXISTS users (id INTEGER PRIMARY KEY, name TEXT NOT NULL, score REAL, active BOOLEAN)",
789        );
790        match s {
791            Statement::CreateTable {
792                name,
793                if_not_exists,
794                columns,
795            } => {
796                assert_eq!(name, "users");
797                assert!(if_not_exists);
798                assert_eq!(columns.len(), 4);
799                assert!(columns[0].primary_key);
800                assert!(columns[1].not_null);
801                assert_eq!(columns[2].ty, ColumnType::Real);
802            }
803            _ => panic!("wrong statement"),
804        }
805    }
806
807    #[test]
808    fn rejects_deep_expression_nesting_without_recursing_forever() {
809        let input = format!(
810            "SELECT {}1{}",
811            "(".repeat(MAX_EXPRESSION_DEPTH + 1),
812            ")".repeat(MAX_EXPRESSION_DEPTH + 1)
813        );
814
815        let error = parse(&input).unwrap_err();
816
817        assert!(error.message.contains("expression nesting"));
818    }
819
820    #[test]
821    fn rejects_deep_statement_nesting_without_recursing_forever() {
822        let input = format!("{}SELECT 1", "EXPLAIN ".repeat(MAX_STATEMENT_DEPTH + 1));
823
824        let error = parse(&input).unwrap_err();
825
826        assert!(error.message.contains("statement nesting"));
827    }
828
829    #[test]
830    fn parses_insert_multi_row() {
831        let s = one("INSERT INTO t (a, b) VALUES (1, 'x'), (2, 'y''s')");
832        match s {
833            Statement::Insert {
834                table,
835                columns,
836                rows,
837            } => {
838                assert_eq!(table, "t");
839                assert_eq!(columns.unwrap(), vec!["a".to_string(), "b".to_string()]);
840                assert_eq!(rows.len(), 2);
841                assert_eq!(rows[1][1], Expr::Literal(Value::Text("y's".into())));
842            }
843            _ => panic!("wrong statement"),
844        }
845    }
846
847    #[test]
848    fn operator_precedence_is_correct() {
849        // 1 + 2 * 3 == 1 + (2*3), and a AND b OR c == (a AND b) OR c
850        let s = one("SELECT * FROM t WHERE a = 1 + 2 * 3 AND b OR c");
851        match s {
852            Statement::Select {
853                where_clause:
854                    Some(Expr::Binary {
855                        op: BinOp::Or,
856                        left,
857                        right,
858                    }),
859                ..
860            } => {
861                assert!(matches!(*left, Expr::Binary { op: BinOp::And, .. }));
862                assert_eq!(*right, Expr::Column("c".into()));
863            }
864            other => panic!("unexpected: {other:?}"),
865        }
866    }
867
868    #[test]
869    fn comparison_binds_tighter_than_and() {
870        let s = one("SELECT * FROM t WHERE x < 10 AND y > 2");
871        match s {
872            Statement::Select {
873                where_clause: Some(Expr::Binary { op: BinOp::And, .. }),
874                ..
875            } => {}
876            other => panic!("unexpected: {other:?}"),
877        }
878    }
879
880    #[test]
881    fn parses_full_select_shape() {
882        let s = one(
883            "SELECT DISTINCT name, score * 2 FROM users WHERE active IS NOT NULL ORDER BY score DESC, name LIMIT 10",
884        );
885        match s {
886            Statement::Select {
887                distinct,
888                columns,
889                order_by,
890                limit,
891                ..
892            } => {
893                assert!(distinct);
894                match columns {
895                    SelectItems::List(items) => assert_eq!(items.len(), 2),
896                    _ => panic!("expected list"),
897                }
898                assert_eq!(
899                    order_by,
900                    vec![("score".to_string(), false), ("name".to_string(), true)]
901                );
902                assert_eq!(limit, Some(10));
903            }
904            _ => panic!("wrong statement"),
905        }
906    }
907
908    #[test]
909    fn parses_update_delete_txn() {
910        assert_eq!(
911            one("UPDATE t SET a = 1, b = 'x' WHERE id = 3"),
912            Statement::Update {
913                table: "t".into(),
914                assignments: vec![
915                    ("a".into(), Expr::Literal(Value::Integer(1))),
916                    ("b".into(), Expr::Literal(Value::Text("x".into())))
917                ],
918                where_clause: Some(Expr::Binary {
919                    left: Box::new(Expr::Column("id".into())),
920                    op: BinOp::Eq,
921                    right: Box::new(Expr::Literal(Value::Integer(3)))
922                }),
923            }
924        );
925        assert!(matches!(
926            one("DELETE FROM t"),
927            Statement::Delete {
928                where_clause: None,
929                ..
930            }
931        ));
932        assert_eq!(one("BEGIN"), Statement::Begin);
933        assert_eq!(one("ROLLBACK"), Statement::Rollback);
934    }
935
936    #[test]
937    fn rejects_garbage() {
938        assert!(parse("SELEC * FROM t").is_err());
939        assert!(parse("INSERT INTO t VALUES (").is_err());
940        assert!(parse("SELECT * FROM t WHERE x = 'unterminated").is_err());
941        assert!(parse("CREATE TABLE t (a BOGUS)").is_err());
942        assert!(parse("SELECT * FROM t WHERE 1 = 1 == 2").is_err()); // dangling ==
943    }
944
945    #[test]
946    fn multiple_statements_and_comments() {
947        let stmts = parse("-- hello\nBEGIN; /* block */ SELECT * FROM t; COMMIT;").unwrap();
948        assert_eq!(stmts.len(), 3);
949    }
950
951    #[test]
952    fn quoted_and_unicode_identifiers() {
953        let s = one("SELECT * FROM \"my table\"");
954        match s {
955            Statement::Select { from, .. } => assert_eq!(from, "my table"),
956            _ => panic!("wrong statement"),
957        }
958        let s = one("SELECT \"u\".\"display name\" \"friendly name\" FROM \"my table\" \"u\"");
959        match s {
960            Statement::Select {
961                columns: SelectItems::List(items),
962                from,
963                from_alias,
964                ..
965            } => {
966                assert_eq!(from, "my table");
967                assert_eq!(from_alias, Some("u".into()));
968                assert!(matches!(
969                    &items[0],
970                    Expr::Alias { alias, expr }
971                        if alias == "friendly name"
972                            && matches!(expr.as_ref(), Expr::ColumnRef { relation, column } if relation == "u" && column == "display name")
973                ));
974            }
975            _ => panic!("wrong statement shape"),
976        }
977        assert!(parse("SELECT * FROM 表").is_ok());
978    }
979
980    #[test]
981    fn null_true_false_and_is_null() {
982        let s = one("SELECT * FROM t WHERE a IS NULL AND b IS NOT NULL AND c = NULL");
983        assert!(matches!(s, Statement::Select { .. }));
984    }
985
986    #[test]
987    fn accepts_the_minimum_integer_literal() {
988        assert!(matches!(
989            one("SELECT -9223372036854775808"),
990            Statement::Select {
991                columns: SelectItems::List(items),
992                ..
993            } if items == vec![Expr::Literal(Value::Integer(i64::MIN))]
994        ));
995        assert!(parse("SELECT 9223372036854775808").is_err());
996        assert!(parse("SELECT -9223372036854775809").is_err());
997    }
998
999    #[test]
1000    fn rejects_out_of_range_limits() {
1001        assert!(parse("SELECT 1 LIMIT 18446744073709551616").is_err());
1002        assert!(parse("SELECT 1 OFFSET 18446744073709551616").is_err());
1003    }
1004
1005    #[test]
1006    fn parses_indexes_joins_groups_and_functions() {
1007        assert!(matches!(
1008            one("CREATE UNIQUE INDEX IF NOT EXISTS ix ON users (email)"),
1009            Statement::CreateIndex {
1010                unique: true,
1011                if_not_exists: true,
1012                ..
1013            }
1014        ));
1015        assert!(matches!(
1016            one("DROP INDEX IF EXISTS ix"),
1017            Statement::DropIndex {
1018                if_exists: true,
1019                ..
1020            }
1021        ));
1022        let statement = one(
1023            "SELECT u.name AS user_name, COUNT(DISTINCT p.id) AS posts FROM users u LEFT JOIN posts p ON u.id = p.user_id GROUP BY u.name HAVING COUNT(*) > 0 ORDER BY u.name LIMIT 5 OFFSET 2",
1024        );
1025        let Statement::Select {
1026            from_alias,
1027            joins,
1028            group_by,
1029            having,
1030            limit,
1031            offset,
1032            ..
1033        } = statement
1034        else {
1035            panic!()
1036        };
1037        assert_eq!(from_alias, Some("u".into()));
1038        assert_eq!(joins.len(), 1);
1039        assert_eq!(group_by.len(), 1);
1040        assert!(having.is_some());
1041        assert_eq!(limit, Some(5));
1042        assert_eq!(offset, Some(2));
1043    }
1044
1045    #[test]
1046    fn not_binds_around_comparison() {
1047        let statement = one("SELECT * FROM t WHERE NOT id = 1 AND id = 2");
1048        let Statement::Select {
1049            where_clause:
1050                Some(Expr::Binary {
1051                    left,
1052                    op: BinOp::And,
1053                    ..
1054                }),
1055            ..
1056        } = statement
1057        else {
1058            panic!()
1059        };
1060        assert!(matches!(
1061            *left,
1062            Expr::Unary {
1063                op: UnaryOp::Not,
1064                expr
1065            } if matches!(*expr, Expr::Binary { op: BinOp::Eq, .. })
1066        ));
1067    }
1068}
basalt/sql/parser.rs

basalt/sql/
parser.rs
