reifydb_sql/

parser.rs

// SPDX-License-Identifier: AGPL-3.0-or-later
// Copyright (c) 2026 ReifyDB

use crate::{
	Error,
	ast::*,
	token::{Keyword, Token},
};

pub struct Parser {
	tokens: Vec<Token>,
	pos: usize,
}

impl Parser {
	pub fn new(tokens: Vec<Token>) -> Self {
		Self {
			tokens,
			pos: 0,
		}
	}

	pub fn parse(&mut self) -> Result<Statement, Error> {
		let stmt = match self.peek()? {
			Token::Keyword(Keyword::With) => self.parse_select()?,
			Token::Keyword(Keyword::Select) => self.parse_select()?,
			Token::Keyword(Keyword::Insert) => self.parse_insert()?,
			Token::Keyword(Keyword::Update) => self.parse_update()?,
			Token::Keyword(Keyword::Delete) => self.parse_delete()?,
			Token::Keyword(Keyword::Create) => self.parse_create()?,
			Token::Keyword(Keyword::Drop) => self.parse_drop()?,
			other => return Err(Error(format!("unexpected token: {other:?}"))),
		};

		if self.pos < self.tokens.len() && self.tokens[self.pos] == Token::Semicolon {
			self.pos += 1;
		}
		Ok(stmt)
	}

	fn peek(&self) -> Result<&Token, Error> {
		self.tokens.get(self.pos).ok_or_else(|| Error("unexpected end of input".into()))
	}

	fn advance(&mut self) -> Result<Token, Error> {
		if self.pos < self.tokens.len() {
			let tok = self.tokens[self.pos].clone();
			self.pos += 1;
			Ok(tok)
		} else {
			Err(Error("unexpected end of input".into()))
		}
	}

	fn expect_keyword(&mut self, kw: Keyword) -> Result<(), Error> {
		let tok = self.advance()?;
		if tok == Token::Keyword(kw.clone()) {
			Ok(())
		} else {
			Err(Error(format!("expected {kw:?}, got {tok:?}")))
		}
	}

	fn expect_token(&mut self, expected: Token) -> Result<(), Error> {
		let tok = self.advance()?;
		if tok == expected {
			Ok(())
		} else {
			Err(Error(format!("expected {expected:?}, got {tok:?}")))
		}
	}

	fn at_keyword(&self, kw: &Keyword) -> bool {
		matches!(self.tokens.get(self.pos), Some(Token::Keyword(k)) if k == kw)
	}

	fn at_token(&self, t: &Token) -> bool {
		matches!(self.tokens.get(self.pos), Some(tok) if tok == t)
	}

	fn is_eof(&self) -> bool {
		self.pos >= self.tokens.len()
	}

	fn expect_ident(&mut self) -> Result<String, Error> {
		let tok = self.advance()?;
		match tok {
			Token::Ident(name) => Ok(name),

			Token::Keyword(kw) => Ok(keyword_to_string(&kw)),
			_ => Err(Error(format!("expected identifier, got {tok:?}"))),
		}
	}

	fn is_ident_like(&self) -> bool {
		match self.tokens.get(self.pos) {
			Some(Token::Ident(_)) => true,
			Some(Token::Keyword(kw)) => !is_structural_keyword(kw),
			_ => false,
		}
	}

	fn parse_select(&mut self) -> Result<Statement, Error> {
		let sel = self.parse_select_statement()?;
		Ok(Statement::Select(Box::new(sel)))
	}

	fn parse_select_statement(&mut self) -> Result<SelectStatement, Error> {
		let ctes = if self.at_keyword(&Keyword::With) {
			self.parse_cte_list()?
		} else {
			vec![]
		};

		self.expect_keyword(Keyword::Select)?;

		let distinct = if self.at_keyword(&Keyword::Distinct) {
			self.advance()?;
			true
		} else {
			false
		};

		let columns = self.parse_select_columns()?;

		let mut from = None;
		let mut joins = Vec::new();

		if self.at_keyword(&Keyword::From) {
			self.advance()?;
			let (first_from, _first_alias) = self.parse_from_item()?;
			from = Some(first_from);

			while self.at_token(&Token::Comma) {
				self.advance()?;
				let (extra_from, extra_alias) = self.parse_from_item()?;
				let alias = extra_alias.or_else(|| match &extra_from {
					FromClause::Table {
						name,
						..
					} => Some(name.clone()),
					_ => None,
				});
				joins.push(JoinClause {
					join_type: JoinType::Cross,
					table: extra_from,
					table_alias: alias,
					on: Expr::BoolLiteral(true),
				});
			}
		}
		while self.parse_join_if_present()? {
			let join = self.finish_parse_join()?;
			joins.push(join);
		}

		let where_clause = if self.at_keyword(&Keyword::Where) {
			self.advance()?;
			Some(self.parse_expr()?)
		} else {
			None
		};

		let group_by = if self.at_keyword(&Keyword::Group) {
			self.advance()?;
			self.expect_keyword(Keyword::By)?;
			self.parse_expr_list()?
		} else {
			vec![]
		};

		let having = if self.at_keyword(&Keyword::Having) {
			self.advance()?;
			Some(self.parse_expr()?)
		} else {
			None
		};

		let order_by = if self.at_keyword(&Keyword::Order) {
			self.advance()?;
			self.expect_keyword(Keyword::By)?;
			self.parse_order_by_list()?
		} else {
			vec![]
		};

		let limit = if self.at_keyword(&Keyword::Limit) {
			self.advance()?;
			Some(self.parse_u64()?)
		} else {
			None
		};

		let offset = if self.at_keyword(&Keyword::Offset) {
			self.advance()?;
			Some(self.parse_u64()?)
		} else {
			None
		};

		let set_op = if self.at_keyword(&Keyword::Union) {
			self.advance()?;
			let op = if self.at_keyword(&Keyword::All) {
				self.advance()?;
				SetOp::UnionAll
			} else {
				SetOp::Union
			};
			let right = self.parse_select_statement()?;
			Some((op, Box::new(right)))
		} else if self.at_keyword(&Keyword::Intersect) {
			self.advance()?;
			let right = self.parse_select_statement()?;
			Some((SetOp::Intersect, Box::new(right)))
		} else if self.at_keyword(&Keyword::Except) {
			self.advance()?;
			let right = self.parse_select_statement()?;
			Some((SetOp::Except, Box::new(right)))
		} else {
			None
		};

		Ok(SelectStatement {
			ctes,
			distinct,
			columns,
			from,
			joins,
			where_clause,
			group_by,
			having,
			order_by,
			limit,
			offset,
			set_op,
		})
	}

	fn parse_from_item(&mut self) -> Result<(FromClause, Option<String>), Error> {
		let from = if self.at_token(&Token::OpenParen) {
			self.advance()?;
			if self.at_keyword(&Keyword::Select) {
				let sel = self.parse_select_statement()?;
				self.expect_token(Token::CloseParen)?;
				FromClause::Subquery(Box::new(sel))
			} else {
				return Err(Error("expected subquery after '('".into()));
			}
		} else {
			let name = self.expect_ident()?;
			if self.at_token(&Token::Dot) {
				self.advance()?;
				let table = self.expect_ident()?;
				FromClause::Table {
					shape: Some(name),
					name: table,
					alias: None,
				}
			} else {
				FromClause::Table {
					name,
					shape: None,
					alias: None,
				}
			}
		};

		let alias = if self.at_keyword(&Keyword::As) {
			self.advance()?;
			Some(self.expect_ident()?)
		} else if !self.is_eof() && self.is_ident_like() {
			Some(self.expect_ident()?)
		} else {
			None
		};

		if let Some(alias) = alias {
			match from {
				FromClause::Table {
					name,
					shape,
					..
				} => Ok((
					FromClause::Table {
						name,
						shape,
						alias: Some(alias),
					},
					None,
				)),
				other => Ok((other, Some(alias))),
			}
		} else {
			Ok((from, None))
		}
	}

	fn parse_cte_list(&mut self) -> Result<Vec<CteDefinition>, Error> {
		self.expect_keyword(Keyword::With)?;
		if self.at_keyword(&Keyword::Recursive) {
			return Err(Error("recursive CTEs are not supported".into()));
		}
		let mut ctes = Vec::new();
		loop {
			let name = self.expect_ident()?;
			self.expect_keyword(Keyword::As)?;
			self.expect_token(Token::OpenParen)?;
			let query = self.parse_select_statement()?;
			self.expect_token(Token::CloseParen)?;
			ctes.push(CteDefinition {
				name,
				query,
			});
			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}
		Ok(ctes)
	}

	fn parse_select_columns(&mut self) -> Result<Vec<SelectColumn>, Error> {
		let mut cols = Vec::new();
		loop {
			if self.at_token(&Token::Asterisk) {
				self.advance()?;
				cols.push(SelectColumn::AllColumns);
			} else if self.is_eof()
				|| self.at_keyword(&Keyword::From)
				|| self.at_keyword(&Keyword::Where)
				|| self.at_keyword(&Keyword::Order)
				|| self.at_keyword(&Keyword::Limit)
				|| self.at_keyword(&Keyword::Group)
				|| self.at_keyword(&Keyword::Having)
				|| self.at_keyword(&Keyword::Union)
				|| self.at_keyword(&Keyword::Intersect)
				|| self.at_keyword(&Keyword::Except)
				|| self.at_token(&Token::Semicolon)
				|| self.at_token(&Token::CloseParen)
			{
				break;
			} else {
				let expr = self.parse_expr()?;
				let alias = if self.at_keyword(&Keyword::As) {
					self.advance()?;
					Some(self.expect_ident()?)
				} else {
					None
				};
				cols.push(SelectColumn::Expr {
					expr,
					alias,
				});
			}

			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}
		Ok(cols)
	}

	fn parse_from_clause(&mut self) -> Result<FromClause, Error> {
		let (from, _alias) = self.parse_from_item()?;
		Ok(from)
	}

	fn parse_join_if_present(&mut self) -> Result<bool, Error> {
		if self.is_eof() {
			return Ok(false);
		}

		if self.at_keyword(&Keyword::Join) {
			return Ok(true);
		}

		if self.at_keyword(&Keyword::Inner)
			|| self.at_keyword(&Keyword::Left)
			|| self.at_keyword(&Keyword::Right)
			|| self.at_keyword(&Keyword::Cross)
			|| self.at_keyword(&Keyword::Natural)
			|| self.at_keyword(&Keyword::Full)
		{
			let mut look = self.pos + 1;
			if look < self.tokens.len() && self.tokens[look] == Token::Keyword(Keyword::Outer) {
				look += 1;
			}
			if look < self.tokens.len() && self.tokens[look] == Token::Keyword(Keyword::Join) {
				return Ok(true);
			}
		}
		Ok(false)
	}

	fn finish_parse_join(&mut self) -> Result<JoinClause, Error> {
		let join_type = if self.at_keyword(&Keyword::Left) {
			self.advance()?;
			if self.at_keyword(&Keyword::Outer) {
				self.advance()?;
			}
			self.expect_keyword(Keyword::Join)?;
			JoinType::Left
		} else if self.at_keyword(&Keyword::Inner) {
			self.advance()?;
			self.expect_keyword(Keyword::Join)?;
			JoinType::Inner
		} else if self.at_keyword(&Keyword::Cross) {
			self.advance()?;
			self.expect_keyword(Keyword::Join)?;
			JoinType::Cross
		} else if self.at_keyword(&Keyword::Natural) {
			self.advance()?;
			self.expect_keyword(Keyword::Join)?;
			JoinType::Inner
		} else if self.at_keyword(&Keyword::Right) || self.at_keyword(&Keyword::Full) {
			self.advance()?;
			if self.at_keyword(&Keyword::Outer) {
				self.advance()?;
			}
			self.expect_keyword(Keyword::Join)?;
			JoinType::Inner
		} else {
			self.expect_keyword(Keyword::Join)?;
			JoinType::Inner
		};

		let table = self.parse_from_clause()?;
		let table_alias = if self.at_keyword(&Keyword::As) {
			self.advance()?;
			Some(self.expect_ident()?)
		} else if !self.is_eof() && self.is_ident_like() && !self.at_keyword(&Keyword::On) {
			Some(self.expect_ident()?)
		} else {
			match &table {
				FromClause::Table {
					alias,
					..
				} => alias.clone(),
				_ => None,
			}
		};

		let on = if self.at_keyword(&Keyword::On) {
			self.advance()?;
			self.parse_expr()?
		} else {
			Expr::BoolLiteral(true)
		};

		Ok(JoinClause {
			join_type,
			table,
			table_alias,
			on,
		})
	}

	fn parse_insert(&mut self) -> Result<Statement, Error> {
		self.expect_keyword(Keyword::Insert)?;
		self.expect_keyword(Keyword::Into)?;

		let (shape, table) = self.parse_table_name()?;

		let columns = if self.at_token(&Token::OpenParen) {
			self.advance()?;
			let cols = self.parse_ident_list()?;
			self.expect_token(Token::CloseParen)?;
			cols
		} else {
			vec![]
		};

		if self.at_keyword(&Keyword::Select) || self.at_keyword(&Keyword::With) {
			let sel = self.parse_select_statement()?;
			return Ok(Statement::Insert(InsertStatement {
				table,
				shape,
				columns,
				source: InsertSource::Select(Box::new(sel)),
			}));
		}

		self.expect_keyword(Keyword::Values)?;

		let mut values = Vec::new();
		loop {
			self.expect_token(Token::OpenParen)?;
			let row = self.parse_expr_list()?;
			self.expect_token(Token::CloseParen)?;
			values.push(row);
			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}

		Ok(Statement::Insert(InsertStatement {
			table,
			shape,
			columns,
			source: InsertSource::Values(values),
		}))
	}

	fn parse_update(&mut self) -> Result<Statement, Error> {
		self.expect_keyword(Keyword::Update)?;
		let (shape, table) = self.parse_table_name()?;
		self.expect_keyword(Keyword::Set)?;

		let mut assignments = Vec::new();
		loop {
			let col = self.expect_ident()?;
			self.expect_token(Token::Eq)?;
			let val = self.parse_expr()?;
			assignments.push((col, val));
			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}

		let where_clause = if self.at_keyword(&Keyword::Where) {
			self.advance()?;
			Some(self.parse_expr()?)
		} else {
			None
		};

		Ok(Statement::Update(UpdateStatement {
			table,
			shape,
			assignments,
			where_clause,
		}))
	}

	fn parse_delete(&mut self) -> Result<Statement, Error> {
		self.expect_keyword(Keyword::Delete)?;
		self.expect_keyword(Keyword::From)?;
		let (shape, table) = self.parse_table_name()?;

		let where_clause = if self.at_keyword(&Keyword::Where) {
			self.advance()?;
			Some(self.parse_expr()?)
		} else {
			None
		};

		Ok(Statement::Delete(DeleteStatement {
			table,
			shape,
			where_clause,
		}))
	}

	fn parse_create(&mut self) -> Result<Statement, Error> {
		self.expect_keyword(Keyword::Create)?;

		if self.at_keyword(&Keyword::Unique) {
			self.advance()?;
			self.expect_keyword(Keyword::Index)?;
			return self.parse_create_index(true);
		}

		if self.at_keyword(&Keyword::Index) {
			self.advance()?;
			return self.parse_create_index(false);
		}

		self.expect_keyword(Keyword::Table)?;

		let if_not_exists = if self.at_keyword(&Keyword::If) {
			self.advance()?;
			self.expect_keyword(Keyword::Not)?;
			self.expect_keyword(Keyword::Exists)?;
			true
		} else {
			false
		};

		let (shape, table) = self.parse_table_name()?;

		self.expect_token(Token::OpenParen)?;
		let mut columns = Vec::new();
		let mut primary_key = Vec::new();
		loop {
			if self.at_token(&Token::CloseParen) {
				break;
			}

			if self.at_keyword(&Keyword::Primary) {
				self.advance()?;
				self.expect_keyword(Keyword::Key)?;
				self.expect_token(Token::OpenParen)?;
				primary_key = self.parse_ident_list()?;
				self.expect_token(Token::CloseParen)?;
				if self.at_token(&Token::Comma) {
					self.advance()?;
				}
				continue;
			}

			if self.at_keyword(&Keyword::Unique) {
				self.advance()?;
				self.expect_token(Token::OpenParen)?;
				let _cols = self.parse_ident_list()?;
				self.expect_token(Token::CloseParen)?;
				if self.at_token(&Token::Comma) {
					self.advance()?;
				}
				continue;
			}
			let name = self.expect_ident()?;
			let data_type = self.parse_sql_type()?;
			let mut nullable = true;
			if self.at_keyword(&Keyword::Not) {
				self.advance()?;
				self.expect_keyword(Keyword::Null)?;
				nullable = false;
			} else if self.at_keyword(&Keyword::Null) {
				self.advance()?;
				nullable = true;
			}

			if self.at_keyword(&Keyword::Primary) {
				self.advance()?;
				self.expect_keyword(Keyword::Key)?;
				primary_key.push(name.clone());
				nullable = false;
			}

			if self.at_keyword(&Keyword::Unique) {
				self.advance()?;
			}

			columns.push(Column {
				name,
				data_type,
				nullable,
			});
			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}
		self.expect_token(Token::CloseParen)?;

		Ok(Statement::CreateTable(CreateTableStatement {
			table,
			shape,
			columns,
			primary_key,
			if_not_exists,
		}))
	}

	fn parse_create_index(&mut self, unique: bool) -> Result<Statement, Error> {
		if self.at_keyword(&Keyword::If) {
			self.advance()?;
			self.expect_keyword(Keyword::Not)?;
			self.expect_keyword(Keyword::Exists)?;
		}

		let index_name = self.expect_ident()?;
		self.expect_keyword(Keyword::On)?;
		let (shape, table) = self.parse_table_name()?;

		self.expect_token(Token::OpenParen)?;
		let mut columns = Vec::new();
		loop {
			let name = self.expect_ident()?;
			let direction = if self.at_keyword(&Keyword::Asc) {
				self.advance()?;
				Some(OrderDirection::Asc)
			} else if self.at_keyword(&Keyword::Desc) {
				self.advance()?;
				Some(OrderDirection::Desc)
			} else {
				None
			};
			columns.push(IndexColumn {
				name,
				direction,
			});
			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}
		self.expect_token(Token::CloseParen)?;

		if self.at_keyword(&Keyword::Where) {
			self.advance()?;
			let _ = self.parse_expr()?;
		}

		Ok(Statement::CreateIndex(CreateIndexStatement {
			unique,
			index_name,
			table,
			shape,
			columns,
		}))
	}

	fn parse_drop(&mut self) -> Result<Statement, Error> {
		self.expect_keyword(Keyword::Drop)?;

		if self.at_keyword(&Keyword::Index) {
			self.advance()?;

			let _if_exists = if self.at_keyword(&Keyword::If) {
				self.advance()?;
				self.expect_keyword(Keyword::Exists)?;
				true
			} else {
				false
			};
			let index_name = self.expect_ident()?;

			return Ok(Statement::DropTable(DropTableStatement {
				table: index_name,
				shape: None,
				if_exists: _if_exists,
			}));
		}

		self.expect_keyword(Keyword::Table)?;

		let if_exists = if self.at_keyword(&Keyword::If) {
			self.advance()?;
			self.expect_keyword(Keyword::Exists)?;
			true
		} else {
			false
		};

		let (shape, table) = self.parse_table_name()?;

		Ok(Statement::DropTable(DropTableStatement {
			table,
			shape,
			if_exists,
		}))
	}

	fn parse_sql_type(&mut self) -> Result<SqlType, Error> {
		let tok = self.advance()?;
		match tok {
			Token::Keyword(Keyword::Int) => Ok(SqlType::Int),
			Token::Keyword(Keyword::Int2) => Ok(SqlType::Int2),
			Token::Keyword(Keyword::Int4) => Ok(SqlType::Int4),
			Token::Keyword(Keyword::Int8) => Ok(SqlType::Int8),
			Token::Keyword(Keyword::Smallint) => Ok(SqlType::Smallint),
			Token::Keyword(Keyword::Integer) => Ok(SqlType::Integer),
			Token::Keyword(Keyword::Bigint) => Ok(SqlType::Bigint),
			Token::Keyword(Keyword::Float4) => Ok(SqlType::Float4),
			Token::Keyword(Keyword::Float8) => Ok(SqlType::Float8),
			Token::Keyword(Keyword::FloatKw) => Ok(SqlType::FloatType),
			Token::Keyword(Keyword::Numeric) => Ok(SqlType::Numeric),
			Token::Keyword(Keyword::Real) => Ok(SqlType::Real),
			Token::Keyword(Keyword::Double) => {
				if self.at_keyword(&Keyword::Precision) {
					self.advance()?;
				}
				Ok(SqlType::Double)
			}
			Token::Keyword(Keyword::Boolean) => Ok(SqlType::Boolean),
			Token::Keyword(Keyword::Bool) => Ok(SqlType::Bool),
			Token::Keyword(Keyword::Text) => Ok(SqlType::Text),
			Token::Keyword(Keyword::Utf8) => Ok(SqlType::Utf8),
			Token::Keyword(Keyword::Blob) => Ok(SqlType::Blob),
			Token::Keyword(Keyword::Varchar) => {
				let len = if self.at_token(&Token::OpenParen) {
					self.advance()?;
					let n = self.parse_u64()?;
					self.expect_token(Token::CloseParen)?;
					Some(n)
				} else {
					None
				};
				Ok(SqlType::Varchar(len))
			}
			Token::Keyword(Keyword::Char) => {
				let len = if self.at_token(&Token::OpenParen) {
					self.advance()?;
					let n = self.parse_u64()?;
					self.expect_token(Token::CloseParen)?;
					Some(n)
				} else {
					None
				};
				Ok(SqlType::Char(len))
			}
			_ => Err(Error(format!("expected SQL type, got {tok:?}"))),
		}
	}

	fn parse_expr(&mut self) -> Result<Expr, Error> {
		self.parse_or()
	}

	fn parse_or(&mut self) -> Result<Expr, Error> {
		let mut left = self.parse_and()?;
		while self.at_keyword(&Keyword::Or) {
			self.advance()?;
			let right = self.parse_and()?;
			left = Expr::BinaryOp {
				left: Box::new(left),
				op: BinaryOp::Or,
				right: Box::new(right),
			};
		}
		Ok(left)
	}

	fn parse_and(&mut self) -> Result<Expr, Error> {
		let mut left = self.parse_not()?;
		while self.at_keyword(&Keyword::And) {
			self.advance()?;
			let right = self.parse_not()?;
			left = Expr::BinaryOp {
				left: Box::new(left),
				op: BinaryOp::And,
				right: Box::new(right),
			};
		}
		Ok(left)
	}

	fn parse_not(&mut self) -> Result<Expr, Error> {
		if self.at_keyword(&Keyword::Not) {
			if matches!(self.tokens.get(self.pos + 1), Some(Token::Keyword(Keyword::Exists))) {
				self.advance()?;
				self.advance()?;
				self.expect_token(Token::OpenParen)?;
				let sel = self.parse_select_statement()?;
				self.expect_token(Token::CloseParen)?;
				return Ok(Expr::UnaryOp {
					op: UnaryOp::Not,
					expr: Box::new(Expr::Exists(Box::new(sel))),
				});
			}
			self.advance()?;
			let expr = self.parse_not()?;
			Ok(Expr::UnaryOp {
				op: UnaryOp::Not,
				expr: Box::new(expr),
			})
		} else {
			self.parse_comparison()
		}
	}

	fn parse_comparison(&mut self) -> Result<Expr, Error> {
		let mut left = self.parse_addition()?;

		if self.at_keyword(&Keyword::Is) {
			self.advance()?;
			if self.at_keyword(&Keyword::Not) {
				self.advance()?;
				self.expect_keyword(Keyword::Null)?;
				return Ok(Expr::IsNull {
					expr: Box::new(left),
					negated: true,
				});
			} else {
				self.expect_keyword(Keyword::Null)?;
				return Ok(Expr::IsNull {
					expr: Box::new(left),
					negated: false,
				});
			}
		}

		if self.at_keyword(&Keyword::Not)
			&& matches!(self.tokens.get(self.pos + 1), Some(Token::Keyword(Keyword::Between)))
		{
			self.advance()?;
			self.advance()?;
			let low = self.parse_addition()?;
			self.expect_keyword(Keyword::And)?;
			let high = self.parse_addition()?;
			return Ok(Expr::Between {
				expr: Box::new(left),
				low: Box::new(low),
				high: Box::new(high),
				negated: true,
			});
		}

		if self.at_keyword(&Keyword::Between) {
			self.advance()?;
			let low = self.parse_addition()?;
			self.expect_keyword(Keyword::And)?;
			let high = self.parse_addition()?;
			return Ok(Expr::Between {
				expr: Box::new(left),
				low: Box::new(low),
				high: Box::new(high),
				negated: false,
			});
		}

		if self.at_keyword(&Keyword::Not)
			&& matches!(self.tokens.get(self.pos + 1), Some(Token::Keyword(Keyword::Like)))
		{
			self.advance()?;
			self.advance()?;
			let pattern = self.parse_addition()?;
			return Ok(Expr::Like {
				expr: Box::new(left),
				pattern: Box::new(pattern),
				negated: true,
			});
		}

		if self.at_keyword(&Keyword::Like) {
			self.advance()?;
			let pattern = self.parse_addition()?;
			return Ok(Expr::Like {
				expr: Box::new(left),
				pattern: Box::new(pattern),
				negated: false,
			});
		}

		if self.at_keyword(&Keyword::Not)
			&& matches!(self.tokens.get(self.pos + 1), Some(Token::Keyword(Keyword::Glob)))
		{
			self.advance()?;
			self.advance()?;
			let pattern = self.parse_addition()?;
			return Ok(Expr::Like {
				expr: Box::new(left),
				pattern: Box::new(pattern),
				negated: true,
			});
		}

		if self.at_keyword(&Keyword::Glob) {
			self.advance()?;
			let pattern = self.parse_addition()?;
			return Ok(Expr::Like {
				expr: Box::new(left),
				pattern: Box::new(pattern),
				negated: false,
			});
		}

		if self.at_keyword(&Keyword::Not)
			&& matches!(self.tokens.get(self.pos + 1), Some(Token::Keyword(Keyword::In)))
		{
			self.advance()?;
			self.advance()?;
			self.expect_token(Token::OpenParen)?;

			if self.at_keyword(&Keyword::Select) || self.at_keyword(&Keyword::With) {
				let sel = self.parse_select_statement()?;
				self.expect_token(Token::CloseParen)?;
				return Ok(Expr::InSelect {
					expr: Box::new(left),
					subquery: Box::new(sel),
					negated: true,
				});
			}
			let list = self.parse_expr_list()?;
			self.expect_token(Token::CloseParen)?;
			return Ok(Expr::InList {
				expr: Box::new(left),
				list,
				negated: true,
			});
		}

		if self.at_keyword(&Keyword::In) {
			self.advance()?;
			self.expect_token(Token::OpenParen)?;

			if self.at_keyword(&Keyword::Select) || self.at_keyword(&Keyword::With) {
				let sel = self.parse_select_statement()?;
				self.expect_token(Token::CloseParen)?;
				return Ok(Expr::InSelect {
					expr: Box::new(left),
					subquery: Box::new(sel),
					negated: false,
				});
			}
			let list = self.parse_expr_list()?;
			self.expect_token(Token::CloseParen)?;
			return Ok(Expr::InList {
				expr: Box::new(left),
				list,
				negated: false,
			});
		}

		let op = match self.tokens.get(self.pos) {
			Some(Token::Eq) => Some(BinaryOp::Eq),
			Some(Token::NotEq) => Some(BinaryOp::NotEq),
			Some(Token::Lt) => Some(BinaryOp::Lt),
			Some(Token::Gt) => Some(BinaryOp::Gt),
			Some(Token::LtEq) => Some(BinaryOp::LtEq),
			Some(Token::GtEq) => Some(BinaryOp::GtEq),
			_ => None,
		};
		if let Some(op) = op {
			self.advance()?;
			let right = self.parse_addition()?;
			left = Expr::BinaryOp {
				left: Box::new(left),
				op,
				right: Box::new(right),
			};
		}

		Ok(left)
	}

	fn parse_addition(&mut self) -> Result<Expr, Error> {
		let mut left = self.parse_multiplication()?;
		loop {
			let op = match self.tokens.get(self.pos) {
				Some(Token::Plus) => Some(BinaryOp::Add),
				Some(Token::Minus) => Some(BinaryOp::Sub),
				Some(Token::Concat) => Some(BinaryOp::Concat),
				_ => None,
			};
			if let Some(op) = op {
				self.advance()?;
				let right = self.parse_multiplication()?;
				left = Expr::BinaryOp {
					left: Box::new(left),
					op,
					right: Box::new(right),
				};
			} else {
				break;
			}
		}
		Ok(left)
	}

	fn parse_multiplication(&mut self) -> Result<Expr, Error> {
		let mut left = self.parse_unary()?;
		loop {
			let op = match self.tokens.get(self.pos) {
				Some(Token::Asterisk) => Some(BinaryOp::Mul),
				Some(Token::Slash) => Some(BinaryOp::Div),
				Some(Token::Percent) => Some(BinaryOp::Mod),
				_ => None,
			};
			if let Some(op) = op {
				self.advance()?;
				let right = self.parse_unary()?;
				left = Expr::BinaryOp {
					left: Box::new(left),
					op,
					right: Box::new(right),
				};
			} else {
				break;
			}
		}
		Ok(left)
	}

	fn parse_unary(&mut self) -> Result<Expr, Error> {
		if self.at_token(&Token::Minus) {
			self.advance()?;
			let expr = self.parse_unary()?;
			return Ok(Expr::UnaryOp {
				op: UnaryOp::Neg,
				expr: Box::new(expr),
			});
		}

		if self.at_token(&Token::Plus) {
			self.advance()?;
			return self.parse_unary();
		}
		self.parse_primary()
	}

	fn parse_primary(&mut self) -> Result<Expr, Error> {
		let tok = self.peek()?.clone();
		match tok {
			Token::Integer(n) => {
				self.advance()?;
				Ok(Expr::IntegerLiteral(n))
			}
			Token::Float(f) => {
				self.advance()?;
				Ok(Expr::FloatLiteral(f))
			}
			Token::StringLit(s) => {
				self.advance()?;
				Ok(Expr::StringLiteral(s))
			}
			Token::Keyword(Keyword::True) => {
				self.advance()?;
				Ok(Expr::BoolLiteral(true))
			}
			Token::Keyword(Keyword::False) => {
				self.advance()?;
				Ok(Expr::BoolLiteral(false))
			}
			Token::Keyword(Keyword::Null) => {
				self.advance()?;
				Ok(Expr::Null)
			}
			Token::Keyword(Keyword::Cast) => self.parse_cast_expr(),
			Token::Keyword(Keyword::Case) => self.parse_case_expr(),
			Token::Keyword(Keyword::Exists) => {
				self.advance()?;
				self.expect_token(Token::OpenParen)?;
				let sel = self.parse_select_statement()?;
				self.expect_token(Token::CloseParen)?;
				Ok(Expr::Exists(Box::new(sel)))
			}
			Token::Keyword(Keyword::Not) => {
				if matches!(self.tokens.get(self.pos + 1), Some(Token::Keyword(Keyword::Exists))) {
					self.advance()?;
					self.advance()?;
					self.expect_token(Token::OpenParen)?;
					let sel = self.parse_select_statement()?;
					self.expect_token(Token::CloseParen)?;
					Ok(Expr::UnaryOp {
						op: UnaryOp::Not,
						expr: Box::new(Expr::Exists(Box::new(sel))),
					})
				} else {
					Err(Error(format!("unexpected token in expression: {tok:?}")))
				}
			}

			Token::Keyword(Keyword::Count)
			| Token::Keyword(Keyword::Sum)
			| Token::Keyword(Keyword::Avg)
			| Token::Keyword(Keyword::Min)
			| Token::Keyword(Keyword::Max) => {
				let name = keyword_to_string(match &self.advance()? {
					Token::Keyword(kw) => kw,
					_ => unreachable!(),
				});
				self.expect_token(Token::OpenParen)?;

				let distinct_prefix = if self.at_keyword(&Keyword::Distinct) {
					self.advance()?;
					true
				} else {
					false
				};
				let args = if self.at_token(&Token::Asterisk) {
					self.advance()?;
					vec![Expr::Identifier("*".into())]
				} else {
					self.parse_expr_list()?
				};
				self.expect_token(Token::CloseParen)?;
				if distinct_prefix {
					Ok(Expr::FunctionCall {
						name: format!("{name}_DISTINCT"),
						args,
					})
				} else {
					Ok(Expr::FunctionCall {
						name,
						args,
					})
				}
			}
			Token::OpenParen => {
				self.advance()?;

				if self.at_keyword(&Keyword::Select) || self.at_keyword(&Keyword::With) {
					let sel = self.parse_select_statement()?;
					self.expect_token(Token::CloseParen)?;
					return Ok(Expr::Subquery(Box::new(sel)));
				}
				let expr = self.parse_expr()?;
				self.expect_token(Token::CloseParen)?;
				Ok(Expr::Nested(Box::new(expr)))
			}
			Token::Ident(_) => {
				let name = self.expect_ident()?;

				if self.at_token(&Token::Dot) {
					self.advance()?;
					let col = self.expect_ident()?;

					if self.at_token(&Token::OpenParen) {
						self.advance()?;
						let args = if self.at_token(&Token::CloseParen) {
							vec![]
						} else if self.at_token(&Token::Asterisk) {
							self.advance()?;
							vec![Expr::Identifier("*".into())]
						} else {
							self.parse_expr_list()?
						};
						self.expect_token(Token::CloseParen)?;
						Ok(Expr::FunctionCall {
							name: format!("{name}.{col}"),
							args,
						})
					} else {
						Ok(Expr::QualifiedIdentifier(name, col))
					}
				} else if self.at_token(&Token::OpenParen) {
					self.advance()?;
					let args = if self.at_token(&Token::CloseParen) {
						vec![]
					} else if self.at_token(&Token::Asterisk) {
						self.advance()?;
						vec![Expr::Identifier("*".into())]
					} else {
						self.parse_expr_list()?
					};
					self.expect_token(Token::CloseParen)?;
					Ok(Expr::FunctionCall {
						name,
						args,
					})
				} else {
					Ok(Expr::Identifier(name))
				}
			}
			_ => Err(Error(format!("unexpected token in expression: {tok:?}"))),
		}
	}

	fn parse_cast_expr(&mut self) -> Result<Expr, Error> {
		self.expect_keyword(Keyword::Cast)?;
		self.expect_token(Token::OpenParen)?;
		let expr = self.parse_expr()?;
		self.expect_keyword(Keyword::As)?;
		let data_type = self.parse_sql_type()?;
		self.expect_token(Token::CloseParen)?;
		Ok(Expr::Cast {
			expr: Box::new(expr),
			data_type,
		})
	}

	fn parse_case_expr(&mut self) -> Result<Expr, Error> {
		self.expect_keyword(Keyword::Case)?;

		let operand = if !self.at_keyword(&Keyword::When) {
			Some(Box::new(self.parse_expr()?))
		} else {
			None
		};

		let mut when_clauses = Vec::new();
		while self.at_keyword(&Keyword::When) {
			self.advance()?;
			let condition = self.parse_expr()?;
			self.expect_keyword(Keyword::Then)?;
			let result = self.parse_expr()?;
			when_clauses.push((condition, result));
		}

		let else_clause = if self.at_keyword(&Keyword::Else) {
			self.advance()?;
			Some(Box::new(self.parse_expr()?))
		} else {
			None
		};

		self.expect_keyword(Keyword::End)?;

		Ok(Expr::Case {
			operand,
			when_clauses,
			else_clause,
		})
	}

	fn parse_expr_list(&mut self) -> Result<Vec<Expr>, Error> {
		let mut exprs = Vec::new();
		exprs.push(self.parse_expr()?);
		while self.at_token(&Token::Comma) {
			self.advance()?;
			exprs.push(self.parse_expr()?);
		}
		Ok(exprs)
	}

	fn parse_ident_list(&mut self) -> Result<Vec<String>, Error> {
		let mut names = Vec::new();
		names.push(self.expect_ident()?);
		while self.at_token(&Token::Comma) {
			self.advance()?;
			names.push(self.expect_ident()?);
		}
		Ok(names)
	}

	fn parse_order_by_list(&mut self) -> Result<Vec<OrderByItem>, Error> {
		let mut items = Vec::new();
		loop {
			let expr = self.parse_expr()?;
			let direction = if self.at_keyword(&Keyword::Desc) {
				self.advance()?;
				OrderDirection::Desc
			} else {
				if self.at_keyword(&Keyword::Asc) {
					self.advance()?;
				}
				OrderDirection::Asc
			};
			items.push(OrderByItem {
				expr,
				direction,
			});
			if self.at_token(&Token::Comma) {
				self.advance()?;
			} else {
				break;
			}
		}
		Ok(items)
	}

	fn parse_u64(&mut self) -> Result<u64, Error> {
		let tok = self.advance()?;
		match tok {
			Token::Integer(n) if n >= 0 => Ok(n as u64),
			_ => Err(Error(format!("expected positive integer, got {tok:?}"))),
		}
	}

	fn parse_table_name(&mut self) -> Result<(Option<String>, String), Error> {
		let name = self.expect_ident()?;
		if self.at_token(&Token::Dot) {
			self.advance()?;
			let table = self.expect_ident()?;
			Ok((Some(name), table))
		} else {
			Ok((None, name))
		}
	}
}

fn is_structural_keyword(kw: &Keyword) -> bool {
	matches!(
		kw,
		Keyword::Where
			| Keyword::Order | Keyword::Group
			| Keyword::Having | Keyword::Limit
			| Keyword::Offset | Keyword::Join
			| Keyword::Inner | Keyword::Left
			| Keyword::Right | Keyword::Cross
			| Keyword::Outer | Keyword::Full
			| Keyword::Natural | Keyword::On
			| Keyword::Set | Keyword::Values
			| Keyword::Select | Keyword::From
			| Keyword::Union | Keyword::Intersect
			| Keyword::Except | Keyword::When
			| Keyword::Then | Keyword::Else
			| Keyword::End | Keyword::And
			| Keyword::Or | Keyword::Not
	)
}

fn keyword_to_string(kw: &Keyword) -> String {
	match kw {
		Keyword::Select => "SELECT",
		Keyword::From => "FROM",
		Keyword::Where => "WHERE",
		Keyword::And => "AND",
		Keyword::Or => "OR",
		Keyword::Not => "NOT",
		Keyword::As => "AS",
		Keyword::Order => "ORDER",
		Keyword::By => "BY",
		Keyword::Asc => "ASC",
		Keyword::Desc => "DESC",
		Keyword::Limit => "LIMIT",
		Keyword::Offset => "OFFSET",
		Keyword::Group => "GROUP",
		Keyword::Having => "HAVING",
		Keyword::Distinct => "DISTINCT",
		Keyword::Insert => "INSERT",
		Keyword::Into => "INTO",
		Keyword::Values => "VALUES",
		Keyword::Update => "UPDATE",
		Keyword::Set => "SET",
		Keyword::Delete => "DELETE",
		Keyword::Create => "CREATE",
		Keyword::Table => "TABLE",
		Keyword::Join => "JOIN",
		Keyword::Inner => "INNER",
		Keyword::Left => "LEFT",
		Keyword::Right => "RIGHT",
		Keyword::On => "ON",
		Keyword::Null => "NULL",
		Keyword::True => "true",
		Keyword::False => "false",
		Keyword::Is => "IS",
		Keyword::In => "IN",
		Keyword::Between => "BETWEEN",
		Keyword::Cast => "CAST",
		Keyword::Count => "COUNT",
		Keyword::Sum => "SUM",
		Keyword::Avg => "AVG",
		Keyword::Min => "MIN",
		Keyword::Max => "MAX",
		Keyword::Int => "INT",
		Keyword::Int2 => "INT2",
		Keyword::Int4 => "INT4",
		Keyword::Int8 => "INT8",
		Keyword::Smallint => "SMALLINT",
		Keyword::Integer => "INTEGER",
		Keyword::Bigint => "BIGINT",
		Keyword::Float4 => "FLOAT4",
		Keyword::Float8 => "FLOAT8",
		Keyword::Real => "REAL",
		Keyword::Double => "DOUBLE",
		Keyword::Precision => "PRECISION",
		Keyword::Boolean => "BOOLEAN",
		Keyword::Bool => "BOOL",
		Keyword::Varchar => "VARCHAR",
		Keyword::Text => "TEXT",
		Keyword::Char => "CHAR",
		Keyword::Utf8 => "UTF8",
		Keyword::Blob => "BLOB",
		Keyword::Primary => "PRIMARY",
		Keyword::Key => "KEY",
		Keyword::With => "WITH",
		Keyword::Recursive => "RECURSIVE",
		Keyword::Case => "CASE",
		Keyword::When => "WHEN",
		Keyword::Then => "THEN",
		Keyword::Else => "ELSE",
		Keyword::End => "END",
		Keyword::Exists => "EXISTS",
		Keyword::Union => "UNION",
		Keyword::All => "ALL",
		Keyword::Intersect => "INTERSECT",
		Keyword::Except => "EXCEPT",
		Keyword::Like => "LIKE",
		Keyword::Glob => "GLOB",
		Keyword::If => "IF",
		Keyword::FloatKw => "FLOAT",
		Keyword::Index => "INDEX",
		Keyword::Unique => "UNIQUE",
		Keyword::Drop => "DROP",
		Keyword::Cross => "CROSS",
		Keyword::Outer => "OUTER",
		Keyword::Full => "FULL",
		Keyword::Natural => "NATURAL",
		Keyword::Numeric => "NUMERIC",
	}
	.into()
}

#[cfg(test)]
mod tests {
	use super::*;
	use crate::token::tokenize;

	#[test]
	fn test_parse_simple_select() {
		let tokens = tokenize("SELECT id, name FROM users").unwrap();
		let stmt = Parser::new(tokens).parse().unwrap();
		match stmt {
			Statement::Select(sel) => {
				assert_eq!(sel.columns.len(), 2);
				assert!(sel.from.is_some());
			}
			_ => panic!("expected select"),
		}
	}

	#[test]
	fn test_parse_select_star() {
		let tokens = tokenize("SELECT * FROM users").unwrap();
		let stmt = Parser::new(tokens).parse().unwrap();
		match stmt {
			Statement::Select(sel) => {
				assert!(matches!(sel.columns[0], SelectColumn::AllColumns));
			}
			_ => panic!("expected select"),
		}
	}

	#[test]
	fn test_parse_where() {
		let tokens = tokenize("SELECT * FROM users WHERE age > 18").unwrap();
		let stmt = Parser::new(tokens).parse().unwrap();
		match stmt {
			Statement::Select(sel) => {
				assert!(sel.where_clause.is_some());
			}
			_ => panic!("expected select"),
		}
	}

	#[test]
	fn test_parse_insert() {
		let tokens = tokenize("INSERT INTO users (id, name) VALUES (1, 'Alice')").unwrap();
		let stmt = Parser::new(tokens).parse().unwrap();
		match stmt {
			Statement::Insert(ins) => {
				assert_eq!(ins.table, "users");
				assert_eq!(ins.columns.len(), 2);
				match &ins.source {
					InsertSource::Values(v) => assert_eq!(v.len(), 1),
					_ => panic!("expected values"),
				}
			}
			_ => panic!("expected insert"),
		}
	}
}