Menu
Public repository / ee7487eee78cd52cdafdcb22b6ff4bf57093d6e9
AkurAI-Framework / crates/sql/src/parser.rs
Latest change fa37e2544d31a1199954a395f9e5b3ebb237b17f - feat(sql): aggregates (COUNT/SUM/AVG/MIN/MAX) + GROUP BY (gpt-5.5) by Ólafur Búi Ólafsson
//! Recursive-descent parser: [`SpannedToken`]s in, a [`Statement`] out.
//!
//! Each statement kind has its own routine. `WHERE` expressions are parsed by
//! precedence climbing so `AND` binds tighter than `OR`
//! (`a=1 AND b=2 OR c=3` ⇒ `(a=1 AND b=2) OR c=3`). Any malformed input returns
//! a positioned [`SqlError`]; the parser never panics.
use crate::ast::{
AggregateArg, AggregateExpr, AggregateFunction, ColumnDef, CompareOp, CreateTableStmt,
DataType, DeleteStmt, Direction, Expr, InsertStmt, Literal, OrderBy, SelectColumn, SelectStmt,
Statement, UpdateStmt,
};
use crate::error::SqlError;
use crate::lexer::tokenize;
use crate::token::{Keyword, SpannedToken, Token};
/// Parse a single SQL statement. A trailing `;` is allowed; anything after the
/// statement (or a second statement) is an error.
pub fn parse(sql: &str) -> Result<Statement, SqlError> {
let tokens = tokenize(sql)?;
let end = sql.chars().count();
let mut parser = Parser {
tokens,
pos: 0,
end,
};
let stmt = parser.parse_statement()?;
parser.consume_optional(&Token::Semicolon);
if let Some(tok) = parser.peek() {
return Err(SqlError::new("unexpected token after statement", tok.pos));
}
Ok(stmt)
}
struct Parser {
tokens: Vec<SpannedToken>,
pos: usize,
/// Character offset just past the input — used for "unexpected end" errors.
end: usize,
}
impl Parser {
fn peek(&self) -> Option<&SpannedToken> {
self.tokens.get(self.pos)
}
fn peek_token(&self) -> Option<&Token> {
self.peek().map(|t| &t.token)
}
/// Position to attach to an "unexpected end of input" error.
fn eof_pos(&self) -> usize {
self.tokens.last().map_or(self.end, |t| t.pos)
}
fn bump(&mut self) -> Option<SpannedToken> {
let tok = self.tokens.get(self.pos).cloned();
if tok.is_some() {
self.pos += 1;
}
tok
}
/// Advance past `token` if it is next; report whether it was there.
fn consume_optional(&mut self, token: &Token) -> bool {
if self.peek_token() == Some(token) {
self.pos += 1;
true
} else {
false
}
}
/// Require exactly `token` next, else a positioned error.
fn expect(&mut self, token: &Token, what: &str) -> Result<(), SqlError> {
match self.peek() {
Some(t) if &t.token == token => {
self.pos += 1;
Ok(())
}
Some(t) => Err(SqlError::new(format!("expected {what}"), t.pos)),
None => Err(SqlError::new(
format!("expected {what} but reached end of input"),
self.eof_pos(),
)),
}
}
fn expect_keyword(&mut self, kw: Keyword, what: &str) -> Result<(), SqlError> {
self.expect(&Token::Keyword(kw), what)
}
/// Require an identifier next and return its name.
fn expect_ident(&mut self, what: &str) -> Result<String, SqlError> {
match self.peek() {
Some(SpannedToken {
token: Token::Ident(name),
..
}) => {
let name = name.clone();
self.pos += 1;
Ok(name)
}
Some(t) => Err(SqlError::new(format!("expected {what}"), t.pos)),
None => Err(SqlError::new(
format!("expected {what} but reached end of input"),
self.eof_pos(),
)),
}
}
fn parse_statement(&mut self) -> Result<Statement, SqlError> {
match self.peek() {
Some(SpannedToken {
token: Token::Keyword(kw),
..
}) => match kw {
Keyword::Select => self.parse_select().map(Statement::Select),
Keyword::Insert => self.parse_insert().map(Statement::Insert),
Keyword::Update => self.parse_update().map(Statement::Update),
Keyword::Delete => self.parse_delete().map(Statement::Delete),
Keyword::Create => self.parse_create_table().map(Statement::CreateTable),
_ => Err(SqlError::new(
"expected SELECT, INSERT, UPDATE, DELETE, or CREATE",
self.peek().unwrap().pos,
)),
},
Some(t) => Err(SqlError::new(
"expected SELECT, INSERT, UPDATE, DELETE, or CREATE",
t.pos,
)),
None => Err(SqlError::new("empty statement", self.eof_pos())),
}
}
// ---- SELECT ----------------------------------------------------------
fn parse_select(&mut self) -> Result<SelectStmt, SqlError> {
self.expect_keyword(Keyword::Select, "SELECT")?;
let columns = self.parse_select_columns()?;
self.expect_keyword(Keyword::From, "FROM")?;
let table = self.expect_ident("table name")?;
let where_clause = if self.consume_optional(&Token::Keyword(Keyword::Where)) {
Some(self.parse_expr()?)
} else {
None
};
let group_by = if self.consume_optional(&Token::Keyword(Keyword::Group)) {
self.expect_keyword(Keyword::By, "BY after GROUP")?;
Some(self.expect_ident("column name in GROUP BY")?)
} else {
None
};
let order_by = if self.consume_optional(&Token::Keyword(Keyword::Order)) {
self.expect_keyword(Keyword::By, "BY after ORDER")?;
let column = self.expect_ident("column name in ORDER BY")?;
let direction = if self.consume_optional(&Token::Keyword(Keyword::Asc)) {
Direction::Asc
} else if self.consume_optional(&Token::Keyword(Keyword::Desc)) {
Direction::Desc
} else {
Direction::Asc
};
Some(OrderBy { column, direction })
} else {
None
};
let limit = if self.consume_optional(&Token::Keyword(Keyword::Limit)) {
Some(self.expect_int("a number after LIMIT")?)
} else {
None
};
Ok(SelectStmt {
columns,
table,
where_clause,
group_by,
order_by,
limit,
})
}
fn parse_select_columns(&mut self) -> Result<Vec<SelectColumn>, SqlError> {
let mut columns = vec![self.parse_select_column()?];
while self.consume_optional(&Token::Comma) {
columns.push(self.parse_select_column()?);
}
Ok(columns)
}
fn parse_select_column(&mut self) -> Result<SelectColumn, SqlError> {
if self.consume_optional(&Token::Star) {
return Ok(SelectColumn::All);
}
let pos = self.peek().map_or(self.eof_pos(), |t| t.pos);
let name = self.expect_ident("column name")?;
if self.consume_optional(&Token::LParen) {
self.parse_aggregate(name, pos)
} else {
Ok(SelectColumn::Named(name))
}
}
fn parse_aggregate(&mut self, name: String, pos: usize) -> Result<SelectColumn, SqlError> {
let func = match name.to_ascii_uppercase().as_str() {
"COUNT" => AggregateFunction::Count,
"SUM" => AggregateFunction::Sum,
"AVG" => AggregateFunction::Avg,
"MIN" => AggregateFunction::Min,
"MAX" => AggregateFunction::Max,
_ => return Err(SqlError::new("unsupported function in SELECT list", pos)),
};
let arg = if self.consume_optional(&Token::Star) {
if func != AggregateFunction::Count {
return Err(SqlError::new("only COUNT accepts '*'", pos));
}
AggregateArg::All
} else {
AggregateArg::Column(self.expect_ident("aggregate column name")?)
};
self.expect(&Token::RParen, "')' after aggregate argument")?;
Ok(SelectColumn::Aggregate(AggregateExpr { func, arg }))
}
fn expect_int(&mut self, what: &str) -> Result<i64, SqlError> {
match self.peek() {
Some(SpannedToken {
token: Token::Int(n),
..
}) => {
let n = *n;
self.pos += 1;
Ok(n)
}
Some(t) => Err(SqlError::new(format!("expected {what}"), t.pos)),
None => Err(SqlError::new(
format!("expected {what} but reached end of input"),
self.eof_pos(),
)),
}
}
// ---- INSERT ----------------------------------------------------------
fn parse_insert(&mut self) -> Result<InsertStmt, SqlError> {
self.expect_keyword(Keyword::Insert, "INSERT")?;
self.expect_keyword(Keyword::Into, "INTO")?;
let table = self.expect_ident("table name")?;
self.expect(&Token::LParen, "'(' before column list")?;
let mut columns = vec![self.expect_ident("column name")?];
while self.consume_optional(&Token::Comma) {
columns.push(self.expect_ident("column name")?);
}
self.expect(&Token::RParen, "')' after column list")?;
self.expect_keyword(Keyword::Values, "VALUES")?;
self.expect(&Token::LParen, "'(' before value list")?;
let mut values = vec![self.parse_literal()?];
while self.consume_optional(&Token::Comma) {
values.push(self.parse_literal()?);
}
self.expect(&Token::RParen, "')' after value list")?;
Ok(InsertStmt {
table,
columns,
values,
})
}
// ---- UPDATE ----------------------------------------------------------
fn parse_update(&mut self) -> Result<UpdateStmt, SqlError> {
self.expect_keyword(Keyword::Update, "UPDATE")?;
let table = self.expect_ident("table name")?;
self.expect_keyword(Keyword::Set, "SET")?;
let mut assignments = vec![self.parse_assignment()?];
while self.consume_optional(&Token::Comma) {
assignments.push(self.parse_assignment()?);
}
let where_clause = if self.consume_optional(&Token::Keyword(Keyword::Where)) {
Some(self.parse_expr()?)
} else {
None
};
Ok(UpdateStmt {
table,
assignments,
where_clause,
})
}
/// One `<col> = <value>` pair in a `SET` list.
fn parse_assignment(&mut self) -> Result<(String, Literal), SqlError> {
let column = self.expect_ident("column name in SET")?;
self.expect(&Token::Eq, "'=' in assignment")?;
let value = self.parse_literal()?;
Ok((column, value))
}
// ---- DELETE ----------------------------------------------------------
fn parse_delete(&mut self) -> Result<DeleteStmt, SqlError> {
self.expect_keyword(Keyword::Delete, "DELETE")?;
self.expect_keyword(Keyword::From, "FROM")?;
let table = self.expect_ident("table name")?;
let where_clause = if self.consume_optional(&Token::Keyword(Keyword::Where)) {
Some(self.parse_expr()?)
} else {
None
};
Ok(DeleteStmt {
table,
where_clause,
})
}
// ---- CREATE TABLE ----------------------------------------------------
fn parse_create_table(&mut self) -> Result<CreateTableStmt, SqlError> {
self.expect_keyword(Keyword::Create, "CREATE")?;
self.expect_keyword(Keyword::Table, "TABLE")?;
let table = self.expect_ident("table name")?;
self.expect(&Token::LParen, "'(' before column definitions")?;
let mut columns = vec![self.parse_column_def()?];
while self.consume_optional(&Token::Comma) {
columns.push(self.parse_column_def()?);
}
self.expect(&Token::RParen, "')' after column definitions")?;
Ok(CreateTableStmt { table, columns })
}
fn parse_column_def(&mut self) -> Result<ColumnDef, SqlError> {
let name = self.expect_ident("column name")?;
let ty = self.parse_data_type()?;
let not_null = if self.consume_optional(&Token::Keyword(Keyword::Not)) {
self.expect_keyword(Keyword::Null, "NULL after NOT")?;
true
} else {
false
};
Ok(ColumnDef { name, ty, not_null })
}
fn parse_data_type(&mut self) -> Result<DataType, SqlError> {
match self.peek() {
Some(SpannedToken {
token: Token::Keyword(kw),
..
}) => {
let ty = match kw {
Keyword::Integer => DataType::Integer,
Keyword::Text => DataType::Text,
Keyword::Real => DataType::Real,
_ => {
return Err(SqlError::new(
"expected a column type (INTEGER, TEXT, or REAL)",
self.peek().unwrap().pos,
))
}
};
self.pos += 1;
Ok(ty)
}
Some(t) => Err(SqlError::new(
"expected a column type (INTEGER, TEXT, or REAL)",
t.pos,
)),
None => Err(SqlError::new(
"expected a column type but reached end of input",
self.eof_pos(),
)),
}
}
// ---- WHERE expressions (precedence climbing) -------------------------
fn parse_expr(&mut self) -> Result<Expr, SqlError> {
self.parse_or()
}
fn parse_or(&mut self) -> Result<Expr, SqlError> {
let mut left = self.parse_and()?;
while self.consume_optional(&Token::Keyword(Keyword::Or)) {
let right = self.parse_and()?;
left = Expr::Or(Box::new(left), Box::new(right));
}
Ok(left)
}
fn parse_and(&mut self) -> Result<Expr, SqlError> {
let mut left = self.parse_not()?;
while self.consume_optional(&Token::Keyword(Keyword::And)) {
let right = self.parse_not()?;
left = Expr::And(Box::new(left), Box::new(right));
}
Ok(left)
}
fn parse_not(&mut self) -> Result<Expr, SqlError> {
if self.consume_optional(&Token::Keyword(Keyword::Not)) {
let operand = self.parse_not()?;
Ok(Expr::Not(Box::new(operand)))
} else {
self.parse_comparison()
}
}
fn parse_comparison(&mut self) -> Result<Expr, SqlError> {
let left = self.parse_primary()?;
if let Some(op) = self.peek_compare_op() {
self.pos += 1;
let right = self.parse_primary()?;
Ok(Expr::Comparison {
left: Box::new(left),
op,
right: Box::new(right),
})
} else {
Ok(left)
}
}
fn peek_compare_op(&self) -> Option<CompareOp> {
Some(match self.peek_token()? {
Token::Eq => CompareOp::Eq,
Token::NotEq => CompareOp::NotEq,
Token::Lt => CompareOp::Lt,
Token::LtEq => CompareOp::LtEq,
Token::Gt => CompareOp::Gt,
Token::GtEq => CompareOp::GtEq,
_ => return None,
})
}
fn parse_primary(&mut self) -> Result<Expr, SqlError> {
match self.peek() {
Some(SpannedToken {
token: Token::LParen,
..
}) => {
self.pos += 1;
let inner = self.parse_expr()?;
self.expect(&Token::RParen, "')' to close expression")?;
Ok(inner)
}
Some(SpannedToken {
token: Token::Ident(name),
..
}) => {
let name = name.clone();
self.pos += 1;
Ok(Expr::Column(name))
}
Some(SpannedToken {
token:
Token::Keyword(Keyword::Null) | Token::Str(_) | Token::Int(_) | Token::Float(_),
..
}) => Ok(Expr::Literal(self.parse_literal()?)),
Some(t) => Err(SqlError::new(
"expected a column, literal, or '(' in expression",
t.pos,
)),
None => Err(SqlError::new(
"expected an expression but reached end of input",
self.eof_pos(),
)),
}
}
fn parse_literal(&mut self) -> Result<Literal, SqlError> {
match self.bump() {
Some(SpannedToken {
token: Token::Keyword(Keyword::Null),
..
}) => Ok(Literal::Null),
Some(SpannedToken {
token: Token::Int(n),
..
}) => Ok(Literal::Int(n)),
Some(SpannedToken {
token: Token::Float(n),
..
}) => Ok(Literal::Float(n)),
Some(SpannedToken {
token: Token::Str(s),
..
}) => Ok(Literal::Str(s)),
Some(t) => Err(SqlError::new("expected a literal value", t.pos)),
None => Err(SqlError::new(
"expected a literal value but reached end of input",
self.eof_pos(),
)),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn parses_select_star() {
let stmt = parse("SELECT * FROM users").unwrap();
assert_eq!(
stmt,
Statement::Select(SelectStmt {
columns: vec![SelectColumn::All],
table: "users".into(),
where_clause: None,
group_by: None,
order_by: None,
limit: None,
})
);
}
#[test]
fn parses_select_with_all_clauses() {
let stmt = parse("SELECT id, name FROM users WHERE age >= 18 ORDER BY name DESC LIMIT 10;")
.unwrap();
let select = match stmt {
Statement::Select(s) => s,
_ => panic!("expected select"),
};
assert_eq!(
select.columns,
vec![
SelectColumn::Named("id".into()),
SelectColumn::Named("name".into())
]
);
assert_eq!(select.table, "users");
assert_eq!(
select.where_clause,
Some(Expr::Comparison {
left: Box::new(Expr::Column("age".into())),
op: CompareOp::GtEq,
right: Box::new(Expr::Literal(Literal::Int(18))),
})
);
assert_eq!(
select.order_by,
Some(OrderBy {
column: "name".into(),
direction: Direction::Desc,
})
);
assert_eq!(select.group_by, None);
assert_eq!(select.limit, Some(10));
}
#[test]
fn parses_aggregates_and_group_by() {
let select = match parse(
"SELECT dept, COUNT(*), COUNT(score), SUM(score), AVG(score), MIN(name), MAX(score) \
FROM users WHERE active = 1 GROUP BY dept ORDER BY dept LIMIT 5",
)
.unwrap()
{
Statement::Select(s) => s,
_ => panic!("expected select"),
};
assert_eq!(
select.columns,
vec![
SelectColumn::Named("dept".into()),
SelectColumn::Aggregate(AggregateExpr {
func: AggregateFunction::Count,
arg: AggregateArg::All,
}),
SelectColumn::Aggregate(AggregateExpr {
func: AggregateFunction::Count,
arg: AggregateArg::Column("score".into()),
}),
SelectColumn::Aggregate(AggregateExpr {
func: AggregateFunction::Sum,
arg: AggregateArg::Column("score".into()),
}),
SelectColumn::Aggregate(AggregateExpr {
func: AggregateFunction::Avg,
arg: AggregateArg::Column("score".into()),
}),
SelectColumn::Aggregate(AggregateExpr {
func: AggregateFunction::Min,
arg: AggregateArg::Column("name".into()),
}),
SelectColumn::Aggregate(AggregateExpr {
func: AggregateFunction::Max,
arg: AggregateArg::Column("score".into()),
}),
]
);
assert_eq!(select.group_by, Some("dept".into()));
assert_eq!(select.limit, Some(5));
}
#[test]
fn aggregate_malformed_are_errors() {
assert!(parse("SELECT SUM(*) FROM t").is_err());
assert!(parse("SELECT COUNT( FROM t").is_err());
assert!(parse("SELECT MEDIAN(v) FROM t").is_err());
assert!(parse("SELECT COUNT(v FROM t").is_err());
assert!(parse("SELECT COUNT(*) FROM t GROUP v").is_err());
}
#[test]
fn order_by_defaults_to_asc() {
let select = match parse("SELECT * FROM t ORDER BY x").unwrap() {
Statement::Select(s) => s,
_ => panic!(),
};
assert_eq!(select.order_by.unwrap().direction, Direction::Asc);
}
#[test]
fn and_binds_tighter_than_or() {
// a=1 AND b=2 OR c=3 ⇒ (a=1 AND b=2) OR c=3
let select = match parse("SELECT * FROM t WHERE a=1 AND b=2 OR c=3").unwrap() {
Statement::Select(s) => s,
_ => panic!(),
};
let cmp = |col: &str, n: i64| Expr::Comparison {
left: Box::new(Expr::Column(col.into())),
op: CompareOp::Eq,
right: Box::new(Expr::Literal(Literal::Int(n))),
};
assert_eq!(
select.where_clause,
Some(Expr::Or(
Box::new(Expr::And(Box::new(cmp("a", 1)), Box::new(cmp("b", 2)))),
Box::new(cmp("c", 3)),
))
);
}
#[test]
fn parentheses_override_precedence() {
let select = match parse("SELECT * FROM t WHERE a=1 AND (b=2 OR c=3)").unwrap() {
Statement::Select(s) => s,
_ => panic!(),
};
// Top node must be AND, not OR.
match select.where_clause.unwrap() {
Expr::And(_, right) => assert!(matches!(*right, Expr::Or(_, _))),
other => panic!("expected AND at top, got {other:?}"),
}
}
#[test]
fn parses_not() {
let select = match parse("SELECT * FROM t WHERE NOT a = 1").unwrap() {
Statement::Select(s) => s,
_ => panic!(),
};
assert!(matches!(select.where_clause, Some(Expr::Not(_))));
}
#[test]
fn parses_insert() {
let stmt = parse("INSERT INTO users (id, name) VALUES (1, 'Ann')").unwrap();
assert_eq!(
stmt,
Statement::Insert(InsertStmt {
table: "users".into(),
columns: vec!["id".into(), "name".into()],
values: vec![Literal::Int(1), Literal::Str("Ann".into())],
})
);
}
#[test]
fn parses_update_with_multiple_assignments_and_where() {
let stmt = parse("UPDATE t SET a = 1, b = 'x' WHERE id = 2").unwrap();
assert_eq!(
stmt,
Statement::Update(UpdateStmt {
table: "t".into(),
assignments: vec![
("a".into(), Literal::Int(1)),
("b".into(), Literal::Str("x".into())),
],
where_clause: Some(Expr::Comparison {
left: Box::new(Expr::Column("id".into())),
op: CompareOp::Eq,
right: Box::new(Expr::Literal(Literal::Int(2))),
}),
})
);
}
#[test]
fn parses_update_without_where() {
let stmt = parse("UPDATE t SET a = NULL").unwrap();
assert_eq!(
stmt,
Statement::Update(UpdateStmt {
table: "t".into(),
assignments: vec![("a".into(), Literal::Null)],
where_clause: None,
})
);
}
#[test]
fn parses_delete_with_where() {
let stmt = parse("DELETE FROM t WHERE a > 3").unwrap();
assert_eq!(
stmt,
Statement::Delete(DeleteStmt {
table: "t".into(),
where_clause: Some(Expr::Comparison {
left: Box::new(Expr::Column("a".into())),
op: CompareOp::Gt,
right: Box::new(Expr::Literal(Literal::Int(3))),
}),
})
);
}
#[test]
fn parses_delete_without_where() {
let stmt = parse("DELETE FROM t").unwrap();
assert_eq!(
stmt,
Statement::Delete(DeleteStmt {
table: "t".into(),
where_clause: None,
})
);
}
#[test]
fn update_delete_malformed_are_errors() {
assert!(parse("UPDATE t a = 1").is_err()); // missing SET
assert!(parse("UPDATE t SET a 1").is_err()); // missing '='
assert!(parse("UPDATE t SET").is_err()); // truncated
assert!(parse("DELETE t WHERE a = 1").is_err()); // missing FROM
assert!(parse("DELETE FROM").is_err()); // missing table
}
#[test]
fn parses_create_table() {
let stmt =
parse("CREATE TABLE users (id INTEGER NOT NULL, name TEXT, score REAL)").unwrap();
assert_eq!(
stmt,
Statement::CreateTable(CreateTableStmt {
table: "users".into(),
columns: vec![
ColumnDef {
name: "id".into(),
ty: DataType::Integer,
not_null: true,
},
ColumnDef {
name: "name".into(),
ty: DataType::Text,
not_null: false,
},
ColumnDef {
name: "score".into(),
ty: DataType::Real,
not_null: false,
},
],
})
);
}
#[test]
fn null_literal_in_where_and_values() {
let select = match parse("SELECT * FROM t WHERE a = NULL").unwrap() {
Statement::Select(s) => s,
_ => panic!(),
};
assert_eq!(
select.where_clause,
Some(Expr::Comparison {
left: Box::new(Expr::Column("a".into())),
op: CompareOp::Eq,
right: Box::new(Expr::Literal(Literal::Null)),
})
);
}
#[test]
fn errors_are_results_not_panics() {
assert!(parse("SELECT * users").is_err()); // missing FROM
assert!(parse("SELECT * FROM t WHERE (a = 1").is_err()); // unclosed paren
assert!(parse("SELECT * FROM").is_err()); // missing table
assert!(parse("INSERT INTO t (a) VALUES (").is_err()); // truncated
assert!(parse("").is_err()); // empty
assert!(parse("DROP TABLE t").is_err()); // unsupported statement
assert!(parse("SELECT * FROM t; SELECT * FROM u").is_err()); // two statements
assert!(parse("SELECT * FROM t WHERE 1 #").is_err()); // bad token (lex error)
}
#[test]
fn error_carries_position() {
// The bad token here is `users`, which starts at offset 9.
let err = parse("SELECT * users").unwrap_err();
assert_eq!(err.position, 9);
}
}