use crate::ast::{Ast, BinaryOp, UnaryOp};
use crate::error::ExprError;
use crate::functions::Functions;
use crate::token::{tokenize, Tok, Token};
use crate::value::Value;
pub(crate) fn parse(src: &str, functions: &Functions) -> Result<Ast, ExprError> {
let toks = tokenize(src)?;
let mut p = Parser {
toks,
pos: 0,
functions,
};
let node = p.parse_ternary()?;
if p.peek() != &Tok::Eof {
return Err(p.error("unexpected trailing input"));
}
Ok(node)
}
struct Parser<'f> {
toks: Vec<Token>,
pos: usize,
functions: &'f Functions,
}
impl Parser<'_> {
fn peek(&self) -> &Tok {
&self.toks[self.pos].tok
}
fn here(&self) -> usize {
self.toks[self.pos].pos
}
fn error(&self, message: impl Into<String>) -> ExprError {
ExprError::syntax_at(message, self.here())
}
fn next(&mut self) -> Token {
let t = self.toks[self.pos].clone();
self.pos += 1;
t
}
fn is_punct(&self, v: &str) -> bool {
matches!(self.peek(), Tok::Punct(s) if *s == v)
}
fn eat(&mut self, v: &str) -> Result<(), ExprError> {
if !self.is_punct(v) {
return Err(self.error(format!("expected '{v}'")));
}
self.pos += 1;
Ok(())
}
fn take_op(&mut self, ops: &[(&str, BinaryOp)]) -> Option<BinaryOp> {
let found = match self.peek() {
Tok::Punct(s) => ops.iter().find(|(sym, _)| sym == s).map(|(_, op)| *op),
Tok::Id(s) if s == "in" => ops.iter().find(|(sym, _)| *sym == "in").map(|(_, op)| *op),
_ => None,
};
if found.is_some() {
self.pos += 1;
}
found
}
fn parse_ternary(&mut self) -> Result<Ast, ExprError> {
let cond = self.parse_or()?;
if !self.is_punct("?") {
return Ok(cond);
}
self.pos += 1;
let then = self.parse_ternary()?;
self.eat(":")?;
let els = self.parse_ternary()?;
Ok(Ast::Ternary(Box::new(cond), Box::new(then), Box::new(els)))
}
fn parse_or(&mut self) -> Result<Ast, ExprError> {
let mut left = self.parse_and()?;
while self.take_op(&[("||", BinaryOp::Or)]).is_some() {
let r = self.parse_and()?;
left = Ast::Binary(BinaryOp::Or, Box::new(left), Box::new(r));
}
Ok(left)
}
fn parse_and(&mut self) -> Result<Ast, ExprError> {
let mut left = self.parse_eq()?;
while self.take_op(&[("&&", BinaryOp::And)]).is_some() {
let r = self.parse_eq()?;
left = Ast::Binary(BinaryOp::And, Box::new(left), Box::new(r));
}
Ok(left)
}
fn parse_eq(&mut self) -> Result<Ast, ExprError> {
let mut left = self.parse_rel()?;
while let Some(op) = self.take_op(&[("==", BinaryOp::Eq), ("!=", BinaryOp::Ne), ("in", BinaryOp::In)]) {
let r = self.parse_rel()?;
left = Ast::Binary(op, Box::new(left), Box::new(r));
}
Ok(left)
}
fn parse_rel(&mut self) -> Result<Ast, ExprError> {
let mut left = self.parse_add()?;
while let Some(op) = self.take_op(&[
("<", BinaryOp::Lt),
("<=", BinaryOp::Le),
(">", BinaryOp::Gt),
(">=", BinaryOp::Ge),
]) {
let r = self.parse_add()?;
left = Ast::Binary(op, Box::new(left), Box::new(r));
}
Ok(left)
}
fn parse_add(&mut self) -> Result<Ast, ExprError> {
let mut left = self.parse_mul()?;
while let Some(op) = self.take_op(&[("+", BinaryOp::Add), ("-", BinaryOp::Sub)]) {
let r = self.parse_mul()?;
left = Ast::Binary(op, Box::new(left), Box::new(r));
}
Ok(left)
}
fn parse_mul(&mut self) -> Result<Ast, ExprError> {
let mut left = self.parse_unary()?;
while let Some(op) = self.take_op(&[("*", BinaryOp::Mul), ("/", BinaryOp::Div), ("%", BinaryOp::Rem)]) {
let r = self.parse_unary()?;
left = Ast::Binary(op, Box::new(left), Box::new(r));
}
Ok(left)
}
fn parse_unary(&mut self) -> Result<Ast, ExprError> {
if self.is_punct("!") {
self.pos += 1;
return Ok(Ast::Unary(UnaryOp::Not, Box::new(self.parse_unary()?)));
}
if self.is_punct("-") {
self.pos += 1;
return Ok(Ast::Unary(UnaryOp::Neg, Box::new(self.parse_unary()?)));
}
self.parse_postfix()
}
fn parse_postfix(&mut self) -> Result<Ast, ExprError> {
let mut node = self.parse_primary()?;
loop {
if self.is_punct(".") {
self.pos += 1;
match self.next().tok {
Tok::Id(name) => node = Ast::Member(Box::new(node), name),
_ => {
return Err(ExprError::syntax_at(
"expected a name after '.'",
self.toks[self.pos - 1].pos,
))
}
}
} else if self.is_punct("[") {
self.pos += 1;
let idx = self.parse_ternary()?;
self.eat("]")?;
node = Ast::Index(Box::new(node), Box::new(idx));
} else {
return Ok(node);
}
}
}
fn parse_args(&mut self) -> Result<Vec<Ast>, ExprError> {
self.eat("(")?;
let mut args = Vec::new();
if !self.is_punct(")") {
args.push(self.parse_ternary()?);
while self.is_punct(",") {
self.pos += 1;
args.push(self.parse_ternary()?);
}
}
self.eat(")")?;
Ok(args)
}
fn parse_primary(&mut self) -> Result<Ast, ExprError> {
let Token { tok, pos } = self.next();
match tok {
Tok::Num(v) => Ok(Ast::Lit(Value::Num(v))),
Tok::Str(s) => Ok(Ast::Lit(Value::Str(s))),
Tok::Id(name) => {
match name.as_str() {
"true" => return Ok(Ast::Lit(Value::Bool(true))),
"false" => return Ok(Ast::Lit(Value::Bool(false))),
"null" => return Ok(Ast::Lit(Value::Null)),
_ => {}
}
if self.is_punct("(") {
let Some(func) = self.functions.get(&name).cloned() else {
return Err(ExprError::UnknownFunction { name });
};
let args = self.parse_args()?;
if !func.accepts(args.len()) {
return Err(ExprError::Arity {
name,
min: func.min(),
max: func.max(),
given: args.len(),
});
}
Ok(Ast::Call(func, args))
} else {
Ok(Ast::Id(name))
}
}
Tok::Punct("(") => {
let e = self.parse_ternary()?;
self.eat(")")?;
Ok(e)
}
Tok::Punct("[") => {
let mut items = Vec::new();
if !self.is_punct("]") {
items.push(self.parse_ternary()?);
while self.is_punct(",") {
self.pos += 1;
items.push(self.parse_ternary()?);
}
}
self.eat("]")?;
Ok(Ast::List(items))
}
Tok::Eof => Err(ExprError::syntax_at("unexpected end of expression", pos)),
Tok::Punct(p) => Err(ExprError::syntax_at(format!("unexpected '{p}'"), pos)),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn p(src: &str) -> Result<Ast, ExprError> {
parse(src, &Functions::standard())
}
#[test]
fn precedence_ladder() {
let Ast::Binary(BinaryOp::And, l, r) = p("1 + 2 * 3 == 7 && !false").unwrap() else {
panic!()
};
assert!(matches!(*l, Ast::Binary(BinaryOp::Eq, _, _)));
assert!(matches!(*r, Ast::Unary(UnaryOp::Not, _)));
assert!(matches!(p("a ? b : c ? d : e").unwrap(), Ast::Ternary(..)));
assert!(matches!(p("x in [1, 2]").unwrap(), Ast::Binary(BinaryOp::In, _, _)));
assert!(matches!(p("a.b[0].c").unwrap(), Ast::Member(..)));
assert_eq!(p("a.b + c[d]").unwrap().identifiers(), vec!["a", "c", "d"]);
}
#[test]
fn compile_time_errors_are_typed_and_positioned() {
assert_eq!(
p("nope(1)").unwrap_err(),
ExprError::UnknownFunction { name: "nope".into() }
);
assert_eq!(
p("abs(1, 2)").unwrap_err(),
ExprError::Arity {
name: "abs".into(),
min: 1,
max: Some(1),
given: 2
}
);
assert_eq!(p("(1 + 2").unwrap_err(), ExprError::syntax_at("expected ')'", 6));
assert_eq!(
p("1 2").unwrap_err(),
ExprError::syntax_at("unexpected trailing input", 2)
);
assert_eq!(
p("a.").unwrap_err(),
ExprError::syntax_at("expected a name after '.'", 2)
);
assert_eq!(
p("").unwrap_err(),
ExprError::syntax_at("unexpected end of expression", 0)
);
assert_eq!(p("1 + )").unwrap_err(), ExprError::syntax_at("unexpected ')'", 4));
}
#[test]
fn unknown_function_depends_on_the_registry() {
let f = Functions::empty().with(crate::Function::fixed("only", 0, |_: &[Value]| Ok(Value::Null)));
assert!(parse("only()", &f).is_ok());
assert!(matches!(parse("abs(1)", &f), Err(ExprError::UnknownFunction { .. })));
}
}