use crate::ast::*;
use crate::error::{BqlError, BqlResult};
use crate::lexer::{self, Token, TokenKind};
use std::borrow::Cow;
const MAX_DEPTH: usize = 128;
pub struct Parser<'a> {
tokens: Vec<Token<'a>>,
pos: usize,
depth: usize,
}
impl<'a> Parser<'a> {
fn new(tokens: Vec<Token<'a>>) -> Self {
Self {
tokens,
pos: 0,
depth: 0,
}
}
fn kind(&self) -> &TokenKind<'a> {
&self.tokens[self.pos].kind
}
fn descend(&mut self) -> BqlResult<()> {
self.depth += 1;
if self.depth > MAX_DEPTH {
Err(self.err_here("expression nested too deeply"))
} else {
Ok(())
}
}
fn ascend(&mut self) {
self.depth -= 1;
}
fn offset(&self) -> usize {
self.tokens[self.pos].offset
}
fn peek_word_at(&self, ahead: usize) -> Option<&str> {
let idx = (self.pos + ahead).min(self.tokens.len() - 1);
match &self.tokens[idx].kind {
TokenKind::Word(w) => Some(w),
_ => None,
}
}
fn peek_kind_at(&self, ahead: usize) -> &TokenKind<'a> {
let idx = (self.pos + ahead).min(self.tokens.len() - 1);
&self.tokens[idx].kind
}
fn word_eq(&self, kw: &str) -> bool {
matches!(&self.tokens[self.pos].kind, TokenKind::Word(w) if w.eq_ignore_ascii_case(kw))
}
fn advance(&mut self) {
if self.pos + 1 < self.tokens.len() {
self.pos += 1;
}
}
fn err_here(&self, msg: impl Into<String>) -> BqlError {
BqlError::new(self.offset(), msg)
}
fn expect_keyword(&mut self, kw: &str) -> BqlResult<()> {
if self.word_eq(kw) {
self.advance();
Ok(())
} else {
Err(self.err_here(format!("expected `{kw}`")))
}
}
}
pub fn parse<'a>(input: &'a str) -> BqlResult<Option<Expr<'a>>> {
let tokens = lexer::lex(input)?;
let mut p = Parser::new(tokens);
if matches!(p.kind(), TokenKind::Eof) {
return Ok(None);
}
let node = p.parse_expr()?;
if !matches!(p.kind(), TokenKind::Eof) {
return Err(p.err_here("expected end of input"));
}
Ok(Some(node))
}
impl<'a> Parser<'a> {
fn parse_expr(&mut self) -> BqlResult<Expr<'a>> {
self.parse_or()
}
fn parse_or(&mut self) -> BqlResult<Expr<'a>> {
let first = self.parse_and()?;
if !self.word_eq("or") {
return Ok(first);
}
let mut operands = vec![Box::new(first)];
while self.word_eq("or") {
self.advance();
operands.push(Box::new(self.parse_and()?));
}
Ok(Expr::Or(Box::new(Or { operands })))
}
fn parse_and(&mut self) -> BqlResult<Expr<'a>> {
let first = self.parse_not()?;
if !self.word_eq("and") {
return Ok(first);
}
let mut operands = vec![Box::new(first)];
while self.word_eq("and") {
self.advance();
operands.push(Box::new(self.parse_not()?));
}
Ok(Expr::And(Box::new(And { operands })))
}
fn parse_not(&mut self) -> BqlResult<Expr<'a>> {
if self.word_eq("not") {
self.advance();
self.descend()?;
let operand = self.parse_not()?;
self.ascend();
return Ok(Expr::Not(Box::new(operand)));
}
self.parse_primary()
}
fn parse_primary(&mut self) -> BqlResult<Expr<'a>> {
if matches!(self.kind(), TokenKind::LParen) {
self.advance();
self.descend()?;
let inner = self.parse_expr()?;
self.ascend();
if !matches!(self.kind(), TokenKind::RParen) {
return Err(self.err_here("expected `)`"));
}
self.advance();
return Ok(inner);
}
let field = match self.kind().clone() {
TokenKind::Word(w) => {
if is_reserved(w) {
return Err(self.err_here(format!(
"`{w}` is a reserved keyword and cannot be used here"
)));
}
self.advance();
Cow::Borrowed(w)
}
TokenKind::Str(s) => {
self.advance();
Cow::Borrowed(s)
}
other => {
return Err(self.err_here(format!("expected a field, found {other:?}")));
}
};
if matches!(self.kind(), TokenKind::Op(_)) {
return self.parse_compare(field);
}
if self.word_eq("between")
|| (self.word_eq("not")
&& matches!(self.peek_word_at(1), Some(w) if w.eq_ignore_ascii_case("between")))
{
return self.parse_between(field);
}
if self.word_eq("in")
|| (self.word_eq("not")
&& matches!(self.peek_word_at(1), Some(w) if w.eq_ignore_ascii_case("in")))
{
return self.parse_in(field);
}
if self.word_eq("is") {
return self.parse_empty(field);
}
Err(self.err_here("expected an operator, `[NOT] BETWEEN`, `[NOT] IN`, `IS`"))
}
}
impl<'a> Parser<'a> {
fn parse_compare(&mut self, field: Cow<'a, str>) -> BqlResult<Expr<'a>> {
let op = if let TokenKind::Op(op) = self.kind() {
let op = *op;
self.advance();
op
} else {
return Err(self.err_here("expected an operator"));
};
let value = self.parse_value()?;
let payload = Compare { field, op, value };
Ok(Expr::Compare(payload))
}
}
impl<'a> Parser<'a> {
fn parse_between(&mut self, field: Cow<'a, str>) -> BqlResult<Expr<'a>> {
let negated = if self.word_eq("not") {
self.advance();
true
} else {
false
};
self.expect_keyword("between")?;
let lo = self.parse_value()?;
self.expect_keyword("and")?;
let hi = self.parse_value()?;
let payload = Between { field, lo, hi };
Ok(match negated {
false => Expr::Between(payload),
true => Expr::NotBetween(payload),
})
}
}
impl<'a> Parser<'a> {
fn parse_in(&mut self, field: Cow<'a, str>) -> BqlResult<Expr<'a>> {
let negated = if self.word_eq("not") {
self.advance();
true
} else {
false
};
self.expect_keyword("in")?;
if !matches!(self.kind(), TokenKind::LParen) {
return Err(self.err_here("expected `(`"));
}
self.advance();
let mut values = Vec::new();
values.push(self.parse_value()?);
while matches!(self.kind(), TokenKind::Comma) {
self.advance();
values.push(self.parse_value()?);
}
if !matches!(self.kind(), TokenKind::RParen) {
return Err(self.err_here("expected `)`"));
}
self.advance();
let payload = In { field, values };
Ok(match negated {
false => Expr::In(payload),
true => Expr::NotIn(payload),
})
}
}
impl<'a> Parser<'a> {
fn parse_empty(&mut self, field: Cow<'a, str>) -> BqlResult<Expr<'a>> {
self.expect_keyword("is")?;
let negated = if self.word_eq("not") {
self.advance();
true
} else {
false
};
let kind = self.parse_empty_kind()?;
let payload = Empty { field };
Ok(match (negated, kind) {
(false, EmptyKind::Empty) => Expr::IsEmpty(payload),
(false, EmptyKind::Null) => Expr::IsNull(payload),
(true, EmptyKind::Empty) => Expr::IsNotEmpty(payload),
(true, EmptyKind::Null) => Expr::IsNotNull(payload),
})
}
}
impl<'a> Parser<'a> {
fn parse_empty_kind(&mut self) -> BqlResult<EmptyKind> {
if self.word_eq("empty") {
self.advance();
return Ok(EmptyKind::Empty);
}
if self.word_eq("null") {
self.advance();
return Ok(EmptyKind::Null);
}
Err(self.err_here("expected `EMPTY` or `NULL`"))
}
}
impl<'a> Parser<'a> {
fn parse_value(&mut self) -> BqlResult<Value<'a>> {
match self.kind().clone() {
TokenKind::Str(s) => {
self.advance();
Ok(Value::String(Cow::Borrowed(s)))
}
TokenKind::Word(w) => {
if w.eq_ignore_ascii_case("now")
&& matches!(self.peek_kind_at(1), TokenKind::LParen)
{
self.advance();
if !matches!(self.kind(), TokenKind::LParen) {
return Err(self.err_here("expected `(`"));
}
self.advance();
if !matches!(self.kind(), TokenKind::RParen) {
return Err(self.err_here("expected `)`"));
}
self.advance();
return Ok(Value::Now(Now {}));
}
let off = self.offset();
self.advance();
classify_word(w, off)
}
other => Err(self.err_here(format!("expected a value, found {other:?}"))),
}
}
}
pub(crate) fn classify_word<'a>(w: &'a str, offset: usize) -> BqlResult<Value<'a>> {
if is_reserved(w) {
return Err(BqlError::new(
offset,
format!("`{w}` is a reserved keyword and cannot be used as a value"),
));
}
if w.eq_ignore_ascii_case("true") {
return Ok(Value::Boolean(Boolean::True));
}
if w.eq_ignore_ascii_case("false") {
return Ok(Value::Boolean(Boolean::False));
}
if is_integer_shape(w) {
if w.parse::<i32>().is_err() {
return Err(BqlError::new(offset, "integer literal out of range"));
}
return Ok(Value::Integer(Cow::Borrowed(w)));
}
if is_float_shape(w) {
return Ok(Value::Float(Cow::Borrowed(w)));
}
if is_date_shape(w) {
return Ok(Value::Date(Cow::Borrowed(w)));
}
if is_datetime_shape(w) {
return Ok(Value::DateTime(Cow::Borrowed(w)));
}
if let Some((prefix, rest)) = w.split_once(':')
&& is_participant_prefix(prefix)
&& !rest.is_empty()
{
return Ok(Value::Participant(Participant {
r#type: Cow::Borrowed(prefix),
id: Cow::Borrowed(rest),
}));
}
Ok(Value::Enum(Cow::Borrowed(w)))
}
fn is_reserved(w: &str) -> bool {
matches!(
w.to_ascii_lowercase().as_str(),
"and" | "or" | "not" | "in" | "is" | "between" | "empty" | "null"
)
}
fn is_integer_shape(w: &str) -> bool {
let b = w.as_bytes();
let mut i = 0;
if let Some(c) = b.first()
&& matches!(c, b'+' | b'-')
{
i += 1;
}
i < b.len() && b[i..].iter().all(u8::is_ascii_digit)
}
fn is_float_shape(w: &str) -> bool {
let b = w.as_bytes();
let mut i = 0;
if let Some(c) = b.first()
&& matches!(c, b'+' | b'-')
{
i += 1;
}
if b.get(i) == Some(&b'.') {
i += 1;
let ds = i;
while i < b.len() && b[i].is_ascii_digit() {
i += 1;
}
if i == ds {
return false;
}
} else {
let ds = i;
while i < b.len() && b[i].is_ascii_digit() {
i += 1;
}
if i == ds {
return false;
}
if b.get(i) == Some(&b'.') {
i += 1;
while i < b.len() && b[i].is_ascii_digit() {
i += 1;
}
}
}
if b.get(i).is_some_and(|c| matches!(c, b'e' | b'E')) {
i += 1;
if b.get(i).is_some_and(|c| matches!(c, b'+' | b'-')) {
i += 1;
}
let es = i;
while i < b.len() && b[i].is_ascii_digit() {
i += 1;
}
if i == es {
return false;
}
}
i == b.len()
}
fn is_date_shape(w: &str) -> bool {
let b = w.as_bytes();
b.len() == 10
&& b[4] == b'-'
&& b[7] == b'-'
&& b[..4].iter().all(u8::is_ascii_digit)
&& b[5..7].iter().all(u8::is_ascii_digit)
&& b[8..10].iter().all(u8::is_ascii_digit)
}
fn is_datetime_shape(w: &str) -> bool {
let b = w.as_bytes();
b.len() > 10
&& b[4] == b'-'
&& b[7] == b'-'
&& b[..4].iter().all(u8::is_ascii_digit)
&& b[5..7].iter().all(u8::is_ascii_digit)
&& b[8..10].iter().all(u8::is_ascii_digit)
&& matches!(b[10], b'T' | b't' | b' ')
}
fn is_participant_prefix(p: &str) -> bool {
matches!(
p,
"agent" | "customer" | "user" | "guest" | "service_account" | "serviceaccount"
)
}