use crate::ast::{col_number, BinaryOp, CellRef, Expr, UnaryOp, MAX_COL, MAX_ROW};
use crate::error::FormulaError;
use crate::lexer::tokenize;
use crate::token::{Token, TokenKind};
use alloc::boxed::Box;
use alloc::string::String;
use alloc::vec::Vec;
pub const MAX_DEPTH: usize = 512;
pub fn parse(input: &str) -> Result<Expr, FormulaError> {
let toks = tokenize(input)?;
let mut p = Parser {
toks: &toks,
pos: 0,
depth: 0,
};
if p.pos == 0 && matches!(p.peek().kind, TokenKind::Eq) {
p.pos += 1;
}
let e = p.parse_expr(0)?;
if p.peek().kind != TokenKind::Eof {
return Err(p.err_here("end of formula"));
}
Ok(e)
}
struct Parser<'t, 'i> {
toks: &'t [Token<'i>],
pos: usize,
depth: usize,
}
impl<'i> Parser<'_, 'i> {
fn peek(&self) -> Token<'i> {
*self
.toks
.get(self.pos)
.unwrap_or(self.toks.last().unwrap_or(&Token {
kind: TokenKind::Eof,
pos: 0,
}))
}
fn err_here(&self, expected: &'static str) -> FormulaError {
let tok = self.peek();
FormulaError::Parse {
pos: tok.pos,
expected,
got: tok.kind.describe(),
}
}
fn enter(&mut self) -> Result<(), FormulaError> {
self.depth += 1;
if self.depth > MAX_DEPTH {
return Err(FormulaError::RecursionLimit);
}
Ok(())
}
fn leave(&mut self) {
self.depth -= 1;
}
fn parse_expr(&mut self, min_bp: usize) -> Result<Expr, FormulaError> {
self.enter()?;
let mut lhs = self.parse_unary()?;
while let Some((lbp, rbp, op)) = self.peek_infix() {
if lbp < min_bp {
break;
}
self.pos += 1; let rhs = self.parse_expr(rbp)?;
lhs = Expr::Binary {
op,
left: Box::new(lhs),
right: Box::new(rhs),
};
}
self.leave();
Ok(lhs)
}
fn peek_infix(&self) -> Option<(usize, usize, BinaryOp)> {
let op = match self.peek().kind {
TokenKind::Plus => BinaryOp::Add,
TokenKind::Minus => BinaryOp::Sub,
TokenKind::Star => BinaryOp::Mul,
TokenKind::Slash => BinaryOp::Div,
TokenKind::Caret => BinaryOp::Pow,
TokenKind::Amp => BinaryOp::Concat,
TokenKind::Eq => BinaryOp::Eq,
TokenKind::Ne => BinaryOp::Ne,
TokenKind::Lt => BinaryOp::Lt,
TokenKind::Gt => BinaryOp::Gt,
TokenKind::Le => BinaryOp::Le,
TokenKind::Ge => BinaryOp::Ge,
_ => return None,
};
let (lbp, rbp) = op.binding_power();
Some((lbp, rbp, op))
}
fn parse_unary(&mut self) -> Result<Expr, FormulaError> {
self.enter()?;
let e = match self.peek().kind {
TokenKind::Minus => {
self.pos += 1;
Expr::Unary {
op: UnaryOp::Neg,
expr: Box::new(self.parse_unary()?),
}
}
TokenKind::Plus => {
self.pos += 1;
Expr::Unary {
op: UnaryOp::Pos,
expr: Box::new(self.parse_unary()?),
}
}
_ => self.parse_postfix()?,
};
self.leave();
Ok(e)
}
fn parse_postfix(&mut self) -> Result<Expr, FormulaError> {
let mut e = self.parse_primary()?;
while self.peek().kind == TokenKind::Percent {
self.pos += 1;
e = Expr::Unary {
op: UnaryOp::Percent,
expr: Box::new(e),
};
}
Ok(e)
}
fn parse_primary(&mut self) -> Result<Expr, FormulaError> {
let tok = self.peek();
match tok.kind {
TokenKind::Number(n) => {
self.pos += 1;
Ok(Expr::Number(n))
}
TokenKind::Str(raw) => {
self.pos += 1;
Ok(Expr::Text(unescape(raw)))
}
TokenKind::ErrLit(e) => {
self.pos += 1;
Ok(Expr::Error(e))
}
TokenKind::Cell { .. } => {
self.pos += 1;
let r = self.finish_celllike(tok, None)?;
self.maybe_range(r)
}
TokenKind::Ident(word) => {
self.pos += 1;
if self.peek().kind == TokenKind::LParen {
self.pos += 1;
let args = self.parse_args()?;
return Ok(Expr::Function {
name: word.to_ascii_uppercase(),
args,
});
}
if word.eq_ignore_ascii_case("TRUE") {
return Ok(Expr::Boolean(true));
}
if word.eq_ignore_ascii_case("FALSE") {
return Ok(Expr::Boolean(false));
}
let cr = match self.bare_word_ref(word) {
Ok(cr) => cr,
Err(expected) => return Err(self.err_here(expected)),
};
let r = self.finish_celllike(tok, Some(cr))?;
self.maybe_range(r)
}
TokenKind::LParen => {
self.pos += 1;
self.enter()?;
let e = self.parse_expr(0)?;
if self.peek().kind != TokenKind::RParen {
return Err(self.err_here("')'"));
}
self.pos += 1;
self.leave();
Ok(e)
}
_ => Err(self.err_here("expression")),
}
}
fn finish_celllike(
&mut self,
tok: Token<'_>,
word: Option<(u32, u32)>,
) -> Result<CellRef, FormulaError> {
let (col, row, col_abs, row_abs) = match tok.kind {
TokenKind::Cell {
col,
row,
col_abs,
row_abs,
} => (col, row, col_abs, row_abs),
TokenKind::Ident(_) => {
let (col, row) = word.unwrap_or((0, 0));
(col, row, false, false)
}
_ => (0, 0, false, false),
};
if col == 0 || col > MAX_COL || row == 0 || row > MAX_ROW {
return Err(FormulaError::Parse {
pos: tok.pos,
expected: "cell reference within A1:XFD1048576",
got: tok.kind.describe(),
});
}
Ok(CellRef {
col,
row,
col_abs,
row_abs,
})
}
fn bare_word_ref(&self, word: &str) -> Result<(u32, u32), &'static str> {
let b = word.as_bytes();
let letters = b.iter().take_while(|c| c.is_ascii_alphabetic()).count();
let digits = b
.get(letters..)
.map_or(0, |rest| rest.iter().filter(|c| c.is_ascii_digit()).count());
let ref_shaped =
letters > 0 && letters <= 3 && digits > 0 && letters + digits == b.len() && digits <= 7;
if !ref_shaped {
return Err("cell reference, TRUE/FALSE, or function call");
}
let col = col_number(&word[..letters]).ok_or("cell reference within A1:XFD1048576")?;
let row: u32 = word[letters..]
.parse()
.map_err(|_| "cell reference within A1:XFD1048576")?;
if row > MAX_ROW {
return Err("cell reference within A1:XFD1048576");
}
Ok((col, row))
}
fn maybe_range(&mut self, start: CellRef) -> Result<Expr, FormulaError> {
if self.peek().kind != TokenKind::Colon {
return Ok(Expr::CellRef {
col: start.col,
row: start.row,
col_abs: start.col_abs,
row_abs: start.row_abs,
});
}
self.pos += 1;
let tok = self.peek();
let end = match tok.kind {
TokenKind::Cell { .. } => {
self.pos += 1;
self.finish_celllike(tok, None)?
}
TokenKind::Ident(word) => {
self.pos += 1;
let (c, r) = self.bare_word_ref(word).map_err(|_| FormulaError::Parse {
pos: tok.pos,
expected: "cell reference after ':'",
got: tok.kind.describe(),
})?;
self.finish_celllike(tok, Some((c, r)))?
}
_ => return Err(self.err_here("cell reference after ':'")),
};
if self.peek().kind == TokenKind::Colon {
return Err(self.err_here("end of range (single ':' only)"));
}
Ok(Expr::Range { start, end })
}
fn parse_args(&mut self) -> Result<Vec<Expr>, FormulaError> {
self.enter()?;
let mut args = Vec::new();
if self.peek().kind == TokenKind::RParen {
self.pos += 1;
self.leave();
return Ok(args);
}
loop {
if matches!(self.peek().kind, TokenKind::Comma | TokenKind::RParen) {
args.push(Expr::Error(crate::error::ExcelError::Null));
} else {
args.push(self.parse_expr(0)?);
}
match self.peek().kind {
TokenKind::Comma => self.pos += 1, TokenKind::RParen => {
self.pos += 1;
break;
}
_ => return Err(self.err_here("',' or ')'")),
}
}
self.leave();
Ok(args)
}
}
fn unescape(raw: &str) -> String {
if !raw.contains('"') {
return String::from(raw);
}
let mut out = String::with_capacity(raw.len());
let mut chars = raw.chars();
while let Some(c) = chars.next() {
if c == '"' {
if chars.next() == Some('"') {
out.push('"');
}
} else {
out.push(c);
}
}
out
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::indexing_slicing
)]
use super::*;
use crate::token::Token;
use alloc::format;
use alloc::vec;
use alloc::vec::Vec;
fn toks(input: &str) -> Vec<Token<'_>> {
tokenize(input).unwrap()
}
#[test]
fn leading_eq_positions() {
assert_eq!(parse("=1+1"), parse("1+1"));
assert!(parse("1=1").is_ok());
assert!(parse("==1").is_err()); }
#[test]
fn eof_sentinel_keeps_peek_in_bounds() {
let t = toks("1");
assert!(matches!(t.last().unwrap().kind, TokenKind::Eof));
}
#[test]
fn unclosed_function_call() {
assert!(matches!(
parse("SUM(1,2"),
Err(FormulaError::Parse { expected: "',' or ')'", got, .. }) if got == "end of formula"
));
}
#[test]
fn empty_vs_omitted_args() {
let e = parse("F()").unwrap();
let Expr::Function { args, .. } = &e else {
panic!()
};
assert_eq!(args.len(), 0);
let e = parse("F(1)").unwrap();
let Expr::Function { args, .. } = &e else {
panic!()
};
assert_eq!(args.len(), 1);
let e = parse("F(,)").unwrap();
let Expr::Function { args, .. } = &e else {
panic!()
};
assert_eq!(args.len(), 2);
}
#[test]
fn function_names_normalize_and_reject_bad_words() {
assert_eq!(
parse("min(1)").unwrap(),
Expr::Function {
name: "MIN".into(),
args: vec![Expr::Number(1.0)]
}
);
assert!(matches!(
parse("_xlfn.SUM(1)").unwrap(),
Expr::Function { ref name, .. } if name == "_XLFN.SUM"
));
}
#[test]
fn mixed_case_refs_and_ranges() {
assert_eq!(parse("Ab12").unwrap(), parse("aB12").unwrap());
assert_eq!(parse("ab12:CD34").unwrap(), parse("AB12:cd34").unwrap());
}
#[test]
fn unary_percent_chains() {
let deep = format!("{}1", "+".repeat(MAX_DEPTH + 5));
assert_eq!(parse(&deep), Err(FormulaError::RecursionLimit));
let near = format!("{}1", "+".repeat(MAX_DEPTH - 2));
assert!(parse(&near).is_ok());
}
#[test]
fn unescape_doubled_quotes() {
assert_eq!(unescape("plain"), "plain");
assert_eq!(unescape("a\"\"b"), "a\"b");
assert_eq!(unescape("\"\"\"\""), "\"\"");
assert_eq!(unescape(""), "");
}
#[test]
fn trailing_percent_after_ref() {
assert!(parse("A1%").is_ok());
assert!(parse("SUM(1)%").is_ok());
assert!(parse("A1:B2%").is_ok());
}
#[test]
fn parens_do_not_make_calls() {
assert!(matches!(
parse("(A1)(B1)"),
Err(FormulaError::Parse {
expected: "end of formula",
..
})
));
}
}