Skip to main content

sheetkit_core/formula/
parser.rs

1//! nom-based parser for Excel formula strings.
2//!
3//! The formula string does NOT include the leading `=` sign.
4//!
5//! Operator precedence (lowest to highest):
6//! 1. Comparison (=, <>, <, <=, >, >=)
7//! 2. Concatenation (&)
8//! 3. Addition / Subtraction (+, -)
9//! 4. Multiplication / Division (*, /)
10//! 5. Exponentiation (^)
11//! 6. Unary (+, -, %)
12//! 7. Primary (literals, references, functions, parens)
13
14use nom::{
15    branch::alt,
16    bytes::complete::{tag, tag_no_case, take_while1},
17    character::complete::{alpha1, char, multispace0, one_of},
18    combinator::{map, opt, recognize, value},
19    error::{ErrorKind, ParseError},
20    sequence::{delimited, pair, preceded, terminated, tuple},
21    IResult, InputLength, Parser,
22};
23
24use super::ast::{BinaryOperator, CellReference, Expr, UnaryOperator};
25use super::budget::{FormulaBudget, FormulaLimits};
26use crate::error::{Error, Result};
27
28/// Parse an Excel formula string into an AST expression.
29///
30/// The input should NOT include the leading `=` sign.
31///
32/// # Errors
33///
34/// Returns an error if the formula string cannot be parsed.
35pub fn parse_formula(input: &str) -> Result<Expr> {
36    let budget = FormulaBudget::for_parse(FormulaLimits::secure_default())?;
37    parse_formula_with_budget(input, &budget)
38}
39
40/// Parse a formula while charging an existing operation budget.
41pub(crate) fn parse_formula_with_budget(input: &str, budget: &FormulaBudget) -> Result<Expr> {
42    let input_bytes = input.len() as u64;
43    budget.check_input(input_bytes)?;
44    let trimmed = input.trim();
45    if trimmed.is_empty() {
46        return Err(Error::Internal("empty formula".to_string()));
47    }
48    let (tokens, parenthesis_depth, unary_depth, binary_operators) = lexical_metrics(trimmed);
49    budget.check_nesting(parenthesis_depth.saturating_add(1))?;
50    budget.check_nesting(unary_depth.saturating_add(1))?;
51    budget.check_binary_chain(binary_operators)?;
52    budget.charge_lexical(input_bytes, tokens)?;
53
54    match parse_expr(trimmed) {
55        Ok(("", expr)) => {
56            let (nodes, depth, binary_chain) = expr.structural_metrics();
57            budget.charge_ast(nodes, depth, binary_chain)?;
58            Ok(expr)
59        }
60        Ok((remaining, _)) => Err(Error::Internal(format!(
61            "unexpected trailing input: {remaining}"
62        ))),
63        Err(e) => Err(Error::Internal(format!("formula parse error: {e}"))),
64    }
65}
66
67fn lexical_metrics(input: &str) -> (u64, u64, u64, u64) {
68    // ASCII bytes are exactly the chars they encode, so the byte iterator
69    // yields the same sequence without UTF-8 decoding.
70    if input.is_ascii() {
71        lexical_metrics_chars(input.bytes().map(char::from))
72    } else {
73        lexical_metrics_chars(input.chars())
74    }
75}
76
77fn lexical_metrics_chars(chars: impl Iterator<Item = char>) -> (u64, u64, u64, u64) {
78    let mut tokens = 0_u64;
79    let mut parenthesis_depth = 0_u64;
80    let mut max_parenthesis_depth = 0_u64;
81    let mut unary_run = 0_u64;
82    let mut max_unary_run = 0_u64;
83    let mut max_binary_chain = 0_u64;
84    let mut binary_chains = [0_u64; 129];
85    let mut expects_operand = [true; 129];
86    let mut frame = 0_usize;
87    let mut chars = chars.peekable();
88
89    while let Some(ch) = chars.next() {
90        if ch.is_whitespace() {
91            continue;
92        }
93        tokens = tokens.saturating_add(1);
94        match ch {
95            '"' => {
96                while let Some(current) = chars.next() {
97                    if current == '"' {
98                        if chars.peek().is_some_and(|next| *next == '"') {
99                            chars.next();
100                        } else {
101                            break;
102                        }
103                    }
104                }
105                unary_run = 0;
106                expects_operand[frame] = false;
107            }
108            '\'' => {
109                while let Some(current) = chars.next() {
110                    if current == '\'' {
111                        if chars.peek().is_some_and(|next| *next == '\'') {
112                            chars.next();
113                        } else {
114                            break;
115                        }
116                    }
117                }
118                if chars.peek().is_some_and(|next| *next == '!') {
119                    chars.next();
120                }
121                unary_run = 0;
122                expects_operand[frame] = false;
123            }
124            '(' => {
125                parenthesis_depth = parenthesis_depth.saturating_add(1);
126                max_parenthesis_depth = max_parenthesis_depth.max(parenthesis_depth);
127                if frame < 128 {
128                    frame += 1;
129                    binary_chains[frame] = 0;
130                    expects_operand[frame] = true;
131                }
132                unary_run = 0;
133            }
134            ')' => {
135                parenthesis_depth = parenthesis_depth.saturating_sub(1);
136                max_binary_chain = max_binary_chain.max(binary_chains[frame]);
137                frame = frame.saturating_sub(1);
138                expects_operand[frame] = false;
139                unary_run = 0;
140            }
141            '+' | '-' => {
142                if expects_operand[frame] {
143                    unary_run = unary_run.saturating_add(1);
144                    max_unary_run = max_unary_run.max(unary_run);
145                } else {
146                    binary_chains[frame] = binary_chains[frame].saturating_add(1);
147                    max_binary_chain = max_binary_chain.max(binary_chains[frame]);
148                    expects_operand[frame] = true;
149                    unary_run = 0;
150                }
151            }
152            '#' => {
153                while chars.peek().is_some_and(|next| {
154                    next.is_alphanumeric() || matches!(*next, '#' | '/' | '!' | '?')
155                }) {
156                    chars.next();
157                }
158                unary_run = 0;
159                expects_operand[frame] = false;
160            }
161            c if c.is_alphanumeric() || matches!(c, '_' | '$' | '.') => {
162                while chars.peek().is_some_and(|next| {
163                    next.is_alphanumeric()
164                        || matches!(*next, '_' | '$' | '.' | '\'' | '!' | '?' | '#')
165                }) {
166                    chars.next();
167                }
168                unary_run = 0;
169                expects_operand[frame] = false;
170            }
171            '<' | '>' => {
172                binary_chains[frame] = binary_chains[frame].saturating_add(1);
173                max_binary_chain = max_binary_chain.max(binary_chains[frame]);
174                if chars.peek().is_some_and(|next| matches!(*next, '=' | '>')) {
175                    chars.next();
176                }
177                unary_run = 0;
178                expects_operand[frame] = true;
179            }
180            '*' | '/' | '^' | '&' | '=' => {
181                binary_chains[frame] = binary_chains[frame].saturating_add(1);
182                max_binary_chain = max_binary_chain.max(binary_chains[frame]);
183                unary_run = 0;
184                expects_operand[frame] = true;
185            }
186            ',' => {
187                max_binary_chain = max_binary_chain.max(binary_chains[frame]);
188                binary_chains[frame] = 0;
189                expects_operand[frame] = true;
190                unary_run = 0;
191            }
192            ':' => {
193                expects_operand[frame] = true;
194                unary_run = 0;
195            }
196            '%' => {
197                expects_operand[frame] = false;
198                unary_run = unary_run.saturating_add(1);
199                max_unary_run = max_unary_run.max(unary_run);
200            }
201            _ => unary_run = 0,
202        }
203    }
204    max_binary_chain = max_binary_chain.max(binary_chains[frame]);
205
206    (
207        tokens,
208        max_parenthesis_depth,
209        max_unary_run,
210        max_binary_chain,
211    )
212}
213
214/// `nom::multi::many0` without the eager `Vec::with_capacity(4)`.
215///
216/// Every precedence level runs this once per operand and nearly always
217/// matches nothing, so deferring the allocation to the first match removes
218/// most per-operand heap traffic. Matching, error, and infinite-loop
219/// behavior are identical to nom's `many0`.
220fn many0<I, O, E, F>(mut f: F) -> impl FnMut(I) -> IResult<I, Vec<O>, E>
221where
222    I: Clone + InputLength,
223    F: Parser<I, O, E>,
224    E: ParseError<I>,
225{
226    move |mut i: I| {
227        let mut acc = Vec::new();
228        loop {
229            let len = i.input_len();
230            match f.parse(i.clone()) {
231                Err(nom::Err::Error(_)) => return Ok((i, acc)),
232                Err(e) => return Err(e),
233                Ok((i1, o)) => {
234                    if i1.input_len() == len {
235                        return Err(nom::Err::Error(E::from_error_kind(i, ErrorKind::Many0)));
236                    }
237                    i = i1;
238                    acc.push(o);
239                }
240            }
241        }
242    }
243}
244
245/// Wraps a parser to consume optional surrounding whitespace.
246fn ws<'a, F, O>(inner: F) -> impl FnMut(&'a str) -> IResult<&'a str, O>
247where
248    F: FnMut(&'a str) -> IResult<&'a str, O>,
249{
250    delimited(multispace0, inner, multispace0)
251}
252
253/// Top-level expression: comparison operators (lowest precedence).
254fn parse_expr(input: &str) -> IResult<&str, Expr> {
255    let (input, left) = parse_concat_expr(input)?;
256    let (input, rest) = many0(pair(ws(parse_comparison_op), parse_concat_expr))(input)?;
257    Ok((input, fold_binary(left, rest)))
258}
259
260fn parse_comparison_op(input: &str) -> IResult<&str, BinaryOperator> {
261    alt((
262        value(BinaryOperator::Le, tag("<=")),
263        value(BinaryOperator::Ge, tag(">=")),
264        value(BinaryOperator::Ne, tag("<>")),
265        value(BinaryOperator::Lt, tag("<")),
266        value(BinaryOperator::Gt, tag(">")),
267        value(BinaryOperator::Eq, tag("=")),
268    ))(input)
269}
270
271/// Concatenation (&).
272fn parse_concat_expr(input: &str) -> IResult<&str, Expr> {
273    let (input, left) = parse_additive(input)?;
274    let (input, rest) = many0(pair(
275        ws(value(BinaryOperator::Concat, tag("&"))),
276        parse_additive,
277    ))(input)?;
278    Ok((input, fold_binary(left, rest)))
279}
280
281/// Addition and subtraction.
282fn parse_additive(input: &str) -> IResult<&str, Expr> {
283    let (input, left) = parse_multiplicative(input)?;
284    let (input, rest) = many0(pair(ws(parse_add_sub_op), parse_multiplicative))(input)?;
285    Ok((input, fold_binary(left, rest)))
286}
287
288fn parse_add_sub_op(input: &str) -> IResult<&str, BinaryOperator> {
289    alt((
290        value(BinaryOperator::Add, tag("+")),
291        value(BinaryOperator::Sub, tag("-")),
292    ))(input)
293}
294
295/// Multiplication and division.
296fn parse_multiplicative(input: &str) -> IResult<&str, Expr> {
297    let (input, left) = parse_power(input)?;
298    let (input, rest) = many0(pair(ws(parse_mul_div_op), parse_power))(input)?;
299    Ok((input, fold_binary(left, rest)))
300}
301
302fn parse_mul_div_op(input: &str) -> IResult<&str, BinaryOperator> {
303    alt((
304        value(BinaryOperator::Mul, tag("*")),
305        value(BinaryOperator::Div, tag("/")),
306    ))(input)
307}
308
309/// Exponentiation (^).
310fn parse_power(input: &str) -> IResult<&str, Expr> {
311    let (input, left) = parse_unary(input)?;
312    let (input, rest) = many0(pair(ws(value(BinaryOperator::Pow, tag("^"))), parse_unary))(input)?;
313    Ok((input, fold_binary(left, rest)))
314}
315
316/// Unary +/- prefix and % postfix.
317fn parse_unary(input: &str) -> IResult<&str, Expr> {
318    let input = input.trim_start();
319    // Try unary minus
320    if let Ok((rest, _)) = tag::<&str, &str, nom::error::Error<&str>>("-")(input) {
321        let (rest, operand) = parse_unary(rest)?;
322        return Ok((
323            rest,
324            Expr::UnaryOp {
325                op: UnaryOperator::Neg,
326                operand: Box::new(operand),
327            },
328        ));
329    }
330    // Try unary plus
331    if let Ok((rest, _)) = tag::<&str, &str, nom::error::Error<&str>>("+")(input) {
332        let (rest, operand) = parse_unary(rest)?;
333        return Ok((
334            rest,
335            Expr::UnaryOp {
336                op: UnaryOperator::Pos,
337                operand: Box::new(operand),
338            },
339        ));
340    }
341    // Otherwise parse primary and check for postfix %
342    let (input, expr) = parse_primary(input)?;
343    let (input, pcts) = many0(ws(value(UnaryOperator::Percent, tag("%"))))(input)?;
344    let result = pcts.into_iter().fold(expr, |acc, op| Expr::UnaryOp {
345        op,
346        operand: Box::new(acc),
347    });
348    Ok((input, result))
349}
350
351/// Primary expressions: literals, references, function calls, parenthesized expressions.
352fn parse_primary(input: &str) -> IResult<&str, Expr> {
353    let input = input.trim_start();
354    alt((
355        parse_paren_expr,
356        parse_string_literal,
357        parse_error_literal,
358        parse_function_call,
359        parse_bool_literal,
360        parse_cell_ref_or_range,
361        parse_number_literal,
362    ))(input)
363}
364
365/// Parse a numeric literal (integer, decimal, or scientific notation).
366fn parse_number_literal(input: &str) -> IResult<&str, Expr> {
367    let (input, num_str) = recognize(pair(
368        take_while1(|c: char| c.is_ascii_digit()),
369        pair(
370            opt(pair(tag("."), take_while1(|c: char| c.is_ascii_digit()))),
371            opt(tuple((
372                one_of("eE"),
373                opt(one_of("+-")),
374                take_while1(|c: char| c.is_ascii_digit()),
375            ))),
376        ),
377    ))(input)?;
378    let n: f64 = num_str.parse().map_err(|_| {
379        nom::Err::Error(nom::error::Error::new(input, nom::error::ErrorKind::Float))
380    })?;
381    Ok((input, Expr::Number(n)))
382}
383
384/// Parse a string literal with `"` delimiters. `""` is an escaped quote (Excel convention).
385fn parse_string_literal(input: &str) -> IResult<&str, Expr> {
386    let (input, _) = tag("\"")(input)?;
387    let mut result = String::new();
388    let mut remaining = input;
389    loop {
390        if remaining.is_empty() {
391            return Err(nom::Err::Error(nom::error::Error::new(
392                remaining,
393                nom::error::ErrorKind::Tag,
394            )));
395        }
396        if remaining.starts_with("\"\"") {
397            result.push('"');
398            remaining = &remaining[2..];
399        } else if remaining.starts_with('"') {
400            remaining = &remaining[1..];
401            break;
402        } else {
403            let c = remaining.chars().next().unwrap();
404            result.push(c);
405            remaining = &remaining[c.len_utf8()..];
406        }
407    }
408    Ok((remaining, Expr::String(result)))
409}
410
411/// Parse a boolean literal: TRUE or FALSE (case-insensitive).
412fn parse_bool_literal(input: &str) -> IResult<&str, Expr> {
413    let (input, val) = alt((
414        value(
415            true,
416            terminated(tag_no_case("TRUE"), not_alnum_or_underscore),
417        ),
418        value(
419            false,
420            terminated(tag_no_case("FALSE"), not_alnum_or_underscore),
421        ),
422    ))(input)?;
423    Ok((input, Expr::Bool(val)))
424}
425
426/// Succeeds if the next character is NOT alphanumeric or underscore, or if at end of input.
427/// This prevents "TRUE1" from being parsed as Bool(true) with leftover "1".
428fn not_alnum_or_underscore(input: &str) -> IResult<&str, ()> {
429    if input.is_empty() {
430        return Ok((input, ()));
431    }
432    let c = input.chars().next().unwrap();
433    if c.is_alphanumeric() || c == '_' {
434        Err(nom::Err::Error(nom::error::Error::new(
435            input,
436            nom::error::ErrorKind::Alpha,
437        )))
438    } else {
439        Ok((input, ()))
440    }
441}
442
443/// Parse an Excel error literal (#DIV/0!, #VALUE!, etc.).
444fn parse_error_literal(input: &str) -> IResult<&str, Expr> {
445    let (input, err) = alt((
446        tag("#DIV/0!"),
447        tag("#VALUE!"),
448        tag("#REF!"),
449        tag("#NAME?"),
450        tag("#NUM!"),
451        tag("#NULL!"),
452        tag("#N/A"),
453    ))(input)?;
454    Ok((input, Expr::Error(err.to_string())))
455}
456
457/// Parse a cell reference (possibly with a sheet prefix) or a range (A1:B10).
458fn parse_cell_ref_or_range(input: &str) -> IResult<&str, Expr> {
459    let (input, first) = parse_single_cell_ref(input)?;
460    // Check for range operator ':'
461    if let Ok((input, _)) = tag::<&str, &str, nom::error::Error<&str>>(":")(input) {
462        let (input, second) = parse_single_cell_ref(input)?;
463        Ok((
464            input,
465            Expr::Range {
466                start: first,
467                end: second,
468            },
469        ))
470    } else {
471        Ok((input, Expr::CellRef(first)))
472    }
473}
474
475/// Parse a single cell reference, optionally prefixed with a sheet name.
476fn parse_single_cell_ref(input: &str) -> IResult<&str, CellReference> {
477    // Try to parse sheet prefix first
478    let (input, sheet) = opt(parse_sheet_prefix)(input)?;
479    // Parse optional $ for abs col
480    let (input, abs_col) = map(opt(tag("$")), |o| o.is_some())(input)?;
481    // Parse column letters
482    let (input, col) = alpha1(input)?;
483    // Make sure column letters are A-Z only
484    let col_upper = col.to_uppercase();
485    if !col_upper.chars().all(|c| c.is_ascii_uppercase()) {
486        return Err(nom::Err::Error(nom::error::Error::new(
487            input,
488            nom::error::ErrorKind::Alpha,
489        )));
490    }
491    // Parse optional $ for abs row
492    let (input, abs_row) = map(opt(tag("$")), |o| o.is_some())(input)?;
493    // Parse row digits
494    let (input, row_str) = take_while1(|c: char| c.is_ascii_digit())(input)?;
495    let row: u32 = row_str.parse().map_err(|_| {
496        nom::Err::Error(nom::error::Error::new(input, nom::error::ErrorKind::Digit))
497    })?;
498    Ok((
499        input,
500        CellReference {
501            col: col_upper,
502            row,
503            abs_col,
504            abs_row,
505            sheet,
506        },
507    ))
508}
509
510/// Parse a sheet prefix like `Sheet1!` or `'Sheet Name'!`.
511fn parse_sheet_prefix(input: &str) -> IResult<&str, String> {
512    alt((parse_quoted_sheet_prefix, parse_unquoted_sheet_prefix))(input)
513}
514
515/// Parse an unquoted sheet prefix: `SheetName!`
516fn parse_unquoted_sheet_prefix(input: &str) -> IResult<&str, String> {
517    let (input, name) = terminated(
518        recognize(pair(
519            take_while1(|c: char| c.is_alphanumeric() || c == '_'),
520            many0(take_while1(|c: char| c.is_alphanumeric() || c == '_')),
521        )),
522        tag("!"),
523    )(input)?;
524    Ok((input, name.to_string()))
525}
526
527/// Parse a quoted sheet prefix: `'Sheet Name'!`
528fn parse_quoted_sheet_prefix(input: &str) -> IResult<&str, String> {
529    let (input, _) = tag("'")(input)?;
530    let mut result = String::new();
531    let mut remaining = input;
532    loop {
533        if remaining.is_empty() {
534            return Err(nom::Err::Error(nom::error::Error::new(
535                remaining,
536                nom::error::ErrorKind::Tag,
537            )));
538        }
539        if remaining.starts_with("''") {
540            result.push('\'');
541            remaining = &remaining[2..];
542        } else if remaining.starts_with('\'') {
543            remaining = &remaining[1..];
544            break;
545        } else {
546            let c = remaining.chars().next().unwrap();
547            result.push(c);
548            remaining = &remaining[c.len_utf8()..];
549        }
550    }
551    let (remaining, _) = tag("!")(remaining)?;
552    Ok((remaining, result))
553}
554
555/// Parse a function call: `FUNCNAME(arg1, arg2, ...)`.
556fn parse_function_call(input: &str) -> IResult<&str, Expr> {
557    // Function name: letters, digits, underscores, dots (e.g., _xlfn.CONCAT)
558    let (input, name) = recognize(pair(
559        alt((alpha1, tag("_"))),
560        many0(alt((
561            take_while1(|c: char| c.is_alphanumeric() || c == '_'),
562            tag("."),
563        ))),
564    ))(input)?;
565    // Must be followed by '('
566    let (input, _) = preceded(multispace0, char('('))(input)?;
567    let (mut input, _) = multispace0(input)?;
568    if let Ok((remaining, _)) = char::<&str, nom::error::Error<&str>>(')')(input) {
569        return Ok((
570            remaining,
571            Expr::Function {
572                name: name.to_uppercase(),
573                args: vec![],
574            },
575        ));
576    }
577
578    let mut args = Vec::new();
579    let mut expecting_arg = true;
580    loop {
581        input = input.trim_start();
582        if let Ok((remaining, _)) = char::<&str, nom::error::Error<&str>>(')')(input) {
583            if expecting_arg {
584                args.push(Expr::Missing);
585            }
586            input = remaining;
587            break;
588        }
589
590        if let Ok((remaining, _)) = char::<&str, nom::error::Error<&str>>(',')(input) {
591            args.push(Expr::Missing);
592            input = remaining;
593            expecting_arg = true;
594            continue;
595        }
596
597        let (remaining, arg) = parse_expr(input)?;
598        args.push(arg);
599        input = remaining.trim_start();
600        if let Ok((remaining, _)) = char::<&str, nom::error::Error<&str>>(',')(input) {
601            input = remaining;
602            expecting_arg = true;
603        } else {
604            let (remaining, _) = char(')')(input)?;
605            input = remaining;
606            break;
607        }
608    }
609    Ok((
610        input,
611        Expr::Function {
612            name: name.to_uppercase(),
613            args,
614        },
615    ))
616}
617
618/// Parse a parenthesized expression.
619fn parse_paren_expr(input: &str) -> IResult<&str, Expr> {
620    let (input, _) = char('(')(input)?;
621    let (input, _) = multispace0(input)?;
622    let (input, expr) = parse_expr(input)?;
623    let (input, _) = preceded(multispace0, char(')'))(input)?;
624    Ok((input, Expr::Paren(Box::new(expr))))
625}
626
627/// Fold a left-associative chain of binary operations into a single AST node.
628fn fold_binary(first: Expr, rest: Vec<(BinaryOperator, Expr)>) -> Expr {
629    rest.into_iter()
630        .fold(first, |left, (op, right)| Expr::BinaryOp {
631            op,
632            left: Box::new(left),
633            right: Box::new(right),
634        })
635}
636
637#[cfg(test)]
638mod tests {
639    use super::*;
640    use crate::formula::ast::{BinaryOperator, CellReference, Expr, UnaryOperator};
641
642    /// Recursive reference for `Expr::structural_metrics`.
643    fn reference_metrics(expr: &Expr, depth: u64, chain: u64) -> (u64, u64, u64) {
644        let combine = |acc: (u64, u64, u64), child: (u64, u64, u64)| {
645            (acc.0 + child.0, acc.1.max(child.1), acc.2.max(child.2))
646        };
647        let own = (1, depth, 0);
648        match expr {
649            Expr::Function { args, .. } => args.iter().fold(own, |acc, arg| {
650                combine(acc, reference_metrics(arg, depth + 1, 0))
651            }),
652            Expr::BinaryOp { left, right, .. } => {
653                let chain = chain + 1;
654                let acc = combine((1, depth, chain), reference_metrics(left, depth, chain));
655                combine(acc, reference_metrics(right, depth, 0))
656            }
657            Expr::UnaryOp { operand, .. } | Expr::Paren(operand) => {
658                combine(own, reference_metrics(operand, depth + 1, 0))
659            }
660            _ => own,
661        }
662    }
663
664    #[test]
665    fn structural_metrics_match_reference_beyond_inline_stack() {
666        let wide = format!(
667            "SUM({})",
668            (1..=40)
669                .map(|n| n.to_string())
670                .collect::<Vec<_>>()
671                .join(",")
672        );
673        let chain = (1..=60)
674            .map(|n| format!("A{n}"))
675            .collect::<Vec<_>>()
676            .join("+");
677        let nested_wide = format!("IF(1>0,{wide},-({chain}))*ROUND(1.5,0)");
678        let deep = format!("{}1{}", "(".repeat(40), ")".repeat(40));
679        for formula in [
680            "1",
681            "SUM(1,2,3,4,5)",
682            "ABS(-42)+SQRT(81)",
683            wide.as_str(),
684            chain.as_str(),
685            nested_wide.as_str(),
686            deep.as_str(),
687        ] {
688            let expr = parse_formula(formula).unwrap();
689            assert_eq!(
690                expr.structural_metrics(),
691                reference_metrics(&expr, 1, 0),
692                "{formula}"
693            );
694        }
695    }
696
697    #[test]
698    fn lexical_metrics_ascii_fast_path_matches_char_path() {
699        for formula in [
700            "SUM(1,2,3)",
701            "IF(A1>=2,\"a\"\"b\",'My Sheet'!B2)&C3%",
702            "--+-1^2*3/4-5<>6",
703            "#N/A+#DIV/0!",
704            "((((1)))) , ((2))",
705            "\t1 +\r\n2\x0b+\x0c3",
706        ] {
707            assert!(formula.is_ascii());
708            assert_eq!(
709                lexical_metrics(formula),
710                lexical_metrics_chars(formula.chars()),
711                "{formula:?}"
712            );
713        }
714        // Non-ASCII input still uses the char path.
715        let unicode = "SUM(\u{3000}1,\"\u{d55c}\")";
716        assert_eq!(
717            lexical_metrics(unicode),
718            lexical_metrics_chars(unicode.chars())
719        );
720    }
721
722    #[test]
723    fn formula_limits_reject_deep_recursive_inputs_before_parsing() {
724        let exact = format!("{}1{}", "(".repeat(63), ")".repeat(63));
725        assert!(parse_formula(&exact).is_ok());
726
727        let over = format!("{}1{}", "(".repeat(64), ")".repeat(64));
728        let error = parse_formula(&over).unwrap_err();
729        assert_eq!(
730            error.resource_metadata().unwrap().dimension_code(),
731            "nesting_depth"
732        );
733
734        let unary_over = format!("{}1", "-".repeat(64));
735        let error = parse_formula(&unary_over).unwrap_err();
736        assert_eq!(
737            error.resource_metadata().unwrap().dimension_code(),
738            "nesting_depth"
739        );
740
741        let postfix_exact = format!("1{}", "%".repeat(63));
742        assert!(parse_formula(&postfix_exact).is_ok());
743        let postfix_over = format!("1{}", "%".repeat(64));
744        assert_eq!(
745            parse_formula(&postfix_over)
746                .unwrap_err()
747                .resource_metadata()
748                .unwrap()
749                .dimension_code(),
750            "nesting_depth"
751        );
752
753        let nested = |depth: usize| {
754            let mut formula = "'Odd)(Sheet'!A1".to_string();
755            for _ in 0..depth {
756                formula = format!("SUM({formula})");
757            }
758            formula
759        };
760        assert!(parse_formula(&nested(63)).is_ok());
761        assert_eq!(
762            parse_formula(&nested(64))
763                .unwrap_err()
764                .resource_metadata()
765                .unwrap()
766                .dimension_code(),
767            "nesting_depth"
768        );
769    }
770
771    #[test]
772    fn formula_input_and_binary_chain_boundaries_are_exact() {
773        let exact_input = format!("\"{}\"", "a".repeat(32_766));
774        assert!(parse_formula(&exact_input).is_ok());
775        let over_input = format!("\"{}\"", "a".repeat(32_767));
776        let error = parse_formula(&over_input).unwrap_err();
777        assert_eq!(
778            error.resource_metadata().unwrap().dimension_code(),
779            "input_bytes"
780        );
781        let padded = format!("{}1", " ".repeat(32_768));
782        assert_eq!(
783            parse_formula(&padded)
784                .unwrap_err()
785                .resource_metadata()
786                .unwrap()
787                .dimension_code(),
788            "input_bytes"
789        );
790
791        let exact_chain = std::iter::repeat_n("1", 513).collect::<Vec<_>>().join("+");
792        assert!(parse_formula(&exact_chain).is_ok());
793        let over_chain = std::iter::repeat_n("1", 514).collect::<Vec<_>>().join("+");
794        let error = parse_formula(&over_chain).unwrap_err();
795        assert_eq!(
796            error.resource_metadata().unwrap().dimension_code(),
797            "nesting_depth"
798        );
799
800        let independent_args = std::iter::repeat_n("1+1", 513)
801            .collect::<Vec<_>>()
802            .join(",");
803        assert!(parse_formula(&format!("F({independent_args})")).is_ok());
804    }
805
806    #[test]
807    fn token_and_ast_node_boundaries_are_exact() {
808        let exact = FormulaLimits {
809            per_formula_tokens: 3,
810            per_formula_ast_nodes: 3,
811            operation_tokens: 3,
812            operation_ast_nodes: 3,
813            ..FormulaLimits::secure_default()
814        };
815        let budget = FormulaBudget::for_parse(exact).unwrap();
816        assert!(parse_formula_with_budget("1+1", &budget).is_ok());
817
818        let token_over = FormulaLimits {
819            per_formula_tokens: 2,
820            ..FormulaLimits::secure_default()
821        };
822        let budget = FormulaBudget::for_parse(token_over).unwrap();
823        let error = parse_formula_with_budget("1+1", &budget).unwrap_err();
824        assert_eq!(
825            error.resource_metadata().unwrap().dimension_code(),
826            "token_count"
827        );
828        assert_eq!(error.resource_metadata().unwrap().observed(), 3);
829
830        let node_over = FormulaLimits {
831            per_formula_ast_nodes: 2,
832            ..FormulaLimits::secure_default()
833        };
834        let budget = FormulaBudget::for_parse(node_over).unwrap();
835        let error = parse_formula_with_budget("1+1", &budget).unwrap_err();
836        assert_eq!(
837            error.resource_metadata().unwrap().dimension_code(),
838            "node_count"
839        );
840        assert_eq!(error.resource_metadata().unwrap().observed(), 3);
841
842        let independent = FormulaLimits {
843            per_formula_nesting_depth: 1,
844            per_formula_binary_chain_depth: 1,
845            ..FormulaLimits::secure_default()
846        };
847        let budget = FormulaBudget::for_parse(independent).unwrap();
848        assert!(parse_formula_with_budget("1+2", &budget).is_ok());
849
850        let chain_over = FormulaLimits {
851            per_formula_binary_chain_depth: 0,
852            ..FormulaLimits::secure_default()
853        };
854        let budget = FormulaBudget::for_parse(chain_over).unwrap();
855        let error = parse_formula_with_budget("1+2", &budget).unwrap_err();
856        let metadata = error.resource_metadata().unwrap();
857        assert_eq!(metadata.dimension_code(), "nesting_depth");
858        assert_eq!((metadata.limit(), metadata.observed()), (0, 1));
859    }
860
861    #[test]
862    fn shared_parse_budget_cannot_be_reset_between_calls() {
863        let limits = FormulaLimits {
864            operation_input_bytes: 3,
865            ..FormulaLimits::secure_default()
866        };
867        let budget = FormulaBudget::for_parse(limits).unwrap();
868        assert!(parse_formula_with_budget("1", &budget).is_ok());
869        assert!(parse_formula_with_budget("22", &budget).is_ok());
870        let error = parse_formula_with_budget("3", &budget).unwrap_err();
871        let metadata = error.resource_metadata().unwrap();
872        assert_eq!(metadata.dimension_code(), "input_bytes");
873        assert_eq!((metadata.limit(), metadata.observed()), (3, 4));
874    }
875
876    #[test]
877    fn test_parse_integer() {
878        let result = parse_formula("42").unwrap();
879        assert_eq!(result, Expr::Number(42.0));
880    }
881
882    #[test]
883    fn test_parse_decimal() {
884        let result = parse_formula("3.15").unwrap();
885        assert_eq!(result, Expr::Number(3.15));
886    }
887
888    #[test]
889    fn test_parse_scientific_number_literals() {
890        for (formula, expected) in [
891            ("1E5", 100_000.0),
892            ("1e5", 100_000.0),
893            ("1.5E+2", 150.0),
894            ("2E-3", 0.002),
895        ] {
896            assert_eq!(parse_formula(formula).unwrap(), Expr::Number(expected));
897        }
898    }
899
900    #[test]
901    fn test_reject_incomplete_scientific_number_literals() {
902        for formula in ["1E", "1E+", "1E-"] {
903            assert!(parse_formula(formula).is_err(), "{formula} should fail");
904        }
905    }
906
907    #[test]
908    fn test_parse_negative_number() {
909        let result = parse_formula("-5").unwrap();
910        assert_eq!(
911            result,
912            Expr::UnaryOp {
913                op: UnaryOperator::Neg,
914                operand: Box::new(Expr::Number(5.0)),
915            }
916        );
917    }
918
919    #[test]
920    fn test_parse_string() {
921        let result = parse_formula("\"hello\"").unwrap();
922        assert_eq!(result, Expr::String("hello".to_string()));
923    }
924
925    #[test]
926    fn test_parse_empty_string() {
927        let result = parse_formula("\"\"").unwrap();
928        assert_eq!(result, Expr::String(String::new()));
929    }
930
931    #[test]
932    fn test_parse_true() {
933        let result = parse_formula("TRUE").unwrap();
934        assert_eq!(result, Expr::Bool(true));
935    }
936
937    #[test]
938    fn test_parse_false() {
939        let result = parse_formula("FALSE").unwrap();
940        assert_eq!(result, Expr::Bool(false));
941    }
942
943    #[test]
944    fn test_parse_error_div0() {
945        let result = parse_formula("#DIV/0!").unwrap();
946        assert_eq!(result, Expr::Error("#DIV/0!".to_string()));
947    }
948
949    #[test]
950    fn test_parse_error_na() {
951        let result = parse_formula("#N/A").unwrap();
952        assert_eq!(result, Expr::Error("#N/A".to_string()));
953    }
954
955    #[test]
956    fn test_parse_cell_ref() {
957        let result = parse_formula("A1").unwrap();
958        assert_eq!(
959            result,
960            Expr::CellRef(CellReference {
961                col: "A".to_string(),
962                row: 1,
963                abs_col: false,
964                abs_row: false,
965                sheet: None,
966            })
967        );
968    }
969
970    #[test]
971    fn test_parse_abs_cell_ref() {
972        let result = parse_formula("$A$1").unwrap();
973        assert_eq!(
974            result,
975            Expr::CellRef(CellReference {
976                col: "A".to_string(),
977                row: 1,
978                abs_col: true,
979                abs_row: true,
980                sheet: None,
981            })
982        );
983    }
984
985    #[test]
986    fn test_parse_mixed_cell_ref() {
987        let result = parse_formula("$A1").unwrap();
988        assert_eq!(
989            result,
990            Expr::CellRef(CellReference {
991                col: "A".to_string(),
992                row: 1,
993                abs_col: true,
994                abs_row: false,
995                sheet: None,
996            })
997        );
998    }
999
1000    #[test]
1001    fn test_parse_range() {
1002        let result = parse_formula("A1:B10").unwrap();
1003        assert_eq!(
1004            result,
1005            Expr::Range {
1006                start: CellReference {
1007                    col: "A".to_string(),
1008                    row: 1,
1009                    abs_col: false,
1010                    abs_row: false,
1011                    sheet: None,
1012                },
1013                end: CellReference {
1014                    col: "B".to_string(),
1015                    row: 10,
1016                    abs_col: false,
1017                    abs_row: false,
1018                    sheet: None,
1019                },
1020            }
1021        );
1022    }
1023
1024    #[test]
1025    fn test_parse_addition() {
1026        let result = parse_formula("1+2").unwrap();
1027        assert_eq!(
1028            result,
1029            Expr::BinaryOp {
1030                op: BinaryOperator::Add,
1031                left: Box::new(Expr::Number(1.0)),
1032                right: Box::new(Expr::Number(2.0)),
1033            }
1034        );
1035    }
1036
1037    #[test]
1038    fn test_parse_subtraction() {
1039        let result = parse_formula("5-3").unwrap();
1040        assert_eq!(
1041            result,
1042            Expr::BinaryOp {
1043                op: BinaryOperator::Sub,
1044                left: Box::new(Expr::Number(5.0)),
1045                right: Box::new(Expr::Number(3.0)),
1046            }
1047        );
1048    }
1049
1050    #[test]
1051    fn test_parse_multiplication() {
1052        let result = parse_formula("2*3").unwrap();
1053        assert_eq!(
1054            result,
1055            Expr::BinaryOp {
1056                op: BinaryOperator::Mul,
1057                left: Box::new(Expr::Number(2.0)),
1058                right: Box::new(Expr::Number(3.0)),
1059            }
1060        );
1061    }
1062
1063    #[test]
1064    fn test_parse_division() {
1065        let result = parse_formula("10/2").unwrap();
1066        assert_eq!(
1067            result,
1068            Expr::BinaryOp {
1069                op: BinaryOperator::Div,
1070                left: Box::new(Expr::Number(10.0)),
1071                right: Box::new(Expr::Number(2.0)),
1072            }
1073        );
1074    }
1075
1076    #[test]
1077    fn test_precedence_mul_over_add() {
1078        // "1+2*3" should parse as Add(1, Mul(2, 3))
1079        let result = parse_formula("1+2*3").unwrap();
1080        assert_eq!(
1081            result,
1082            Expr::BinaryOp {
1083                op: BinaryOperator::Add,
1084                left: Box::new(Expr::Number(1.0)),
1085                right: Box::new(Expr::BinaryOp {
1086                    op: BinaryOperator::Mul,
1087                    left: Box::new(Expr::Number(2.0)),
1088                    right: Box::new(Expr::Number(3.0)),
1089                }),
1090            }
1091        );
1092    }
1093
1094    #[test]
1095    fn test_precedence_parens() {
1096        // "(1+2)*3" should parse as Mul(Paren(Add(1, 2)), 3)
1097        let result = parse_formula("(1+2)*3").unwrap();
1098        assert_eq!(
1099            result,
1100            Expr::BinaryOp {
1101                op: BinaryOperator::Mul,
1102                left: Box::new(Expr::Paren(Box::new(Expr::BinaryOp {
1103                    op: BinaryOperator::Add,
1104                    left: Box::new(Expr::Number(1.0)),
1105                    right: Box::new(Expr::Number(2.0)),
1106                }))),
1107                right: Box::new(Expr::Number(3.0)),
1108            }
1109        );
1110    }
1111
1112    #[test]
1113    fn test_parse_function_no_args() {
1114        let result = parse_formula("NOW()").unwrap();
1115        assert_eq!(
1116            result,
1117            Expr::Function {
1118                name: "NOW".to_string(),
1119                args: vec![],
1120            }
1121        );
1122    }
1123
1124    #[test]
1125    fn test_parse_boolean_function_no_args() {
1126        assert_eq!(
1127            parse_formula("TRUE()").unwrap(),
1128            Expr::Function {
1129                name: "TRUE".to_string(),
1130                args: vec![],
1131            }
1132        );
1133        assert_eq!(
1134            parse_formula("FALSE()").unwrap(),
1135            Expr::Function {
1136                name: "FALSE".to_string(),
1137                args: vec![],
1138            }
1139        );
1140    }
1141
1142    #[test]
1143    fn test_parse_function_one_arg() {
1144        let result = parse_formula("ABS(-5)").unwrap();
1145        assert_eq!(
1146            result,
1147            Expr::Function {
1148                name: "ABS".to_string(),
1149                args: vec![Expr::UnaryOp {
1150                    op: UnaryOperator::Neg,
1151                    operand: Box::new(Expr::Number(5.0)),
1152                }],
1153            }
1154        );
1155    }
1156
1157    #[test]
1158    fn test_parse_function_multi_args() {
1159        let result = parse_formula("SUM(1,2,3)").unwrap();
1160        assert_eq!(
1161            result,
1162            Expr::Function {
1163                name: "SUM".to_string(),
1164                args: vec![Expr::Number(1.0), Expr::Number(2.0), Expr::Number(3.0),],
1165            }
1166        );
1167    }
1168
1169    #[test]
1170    fn test_parse_omitted_function_args() {
1171        for (formula, args) in [
1172            (
1173                "IF(A1,,1)",
1174                vec![
1175                    Expr::CellRef(CellReference {
1176                        col: "A".to_string(),
1177                        row: 1,
1178                        abs_col: false,
1179                        abs_row: false,
1180                        sheet: None,
1181                    }),
1182                    Expr::Missing,
1183                    Expr::Number(1.0),
1184                ],
1185            ),
1186            (
1187                "IF(,1,2)",
1188                vec![Expr::Missing, Expr::Number(1.0), Expr::Number(2.0)],
1189            ),
1190            (
1191                "IF(A1,1,)",
1192                vec![
1193                    Expr::CellRef(CellReference {
1194                        col: "A".to_string(),
1195                        row: 1,
1196                        abs_col: false,
1197                        abs_row: false,
1198                        sheet: None,
1199                    }),
1200                    Expr::Number(1.0),
1201                    Expr::Missing,
1202                ],
1203            ),
1204        ] {
1205            assert_eq!(
1206                parse_formula(formula).unwrap(),
1207                Expr::Function {
1208                    name: "IF".to_string(),
1209                    args,
1210                }
1211            );
1212        }
1213    }
1214
1215    #[test]
1216    fn test_parse_nested_function() {
1217        let result = parse_formula("SUM(A1:A10,MAX(B1:B10))").unwrap();
1218        assert_eq!(
1219            result,
1220            Expr::Function {
1221                name: "SUM".to_string(),
1222                args: vec![
1223                    Expr::Range {
1224                        start: CellReference {
1225                            col: "A".to_string(),
1226                            row: 1,
1227                            abs_col: false,
1228                            abs_row: false,
1229                            sheet: None,
1230                        },
1231                        end: CellReference {
1232                            col: "A".to_string(),
1233                            row: 10,
1234                            abs_col: false,
1235                            abs_row: false,
1236                            sheet: None,
1237                        },
1238                    },
1239                    Expr::Function {
1240                        name: "MAX".to_string(),
1241                        args: vec![Expr::Range {
1242                            start: CellReference {
1243                                col: "B".to_string(),
1244                                row: 1,
1245                                abs_col: false,
1246                                abs_row: false,
1247                                sheet: None,
1248                            },
1249                            end: CellReference {
1250                                col: "B".to_string(),
1251                                row: 10,
1252                                abs_col: false,
1253                                abs_row: false,
1254                                sheet: None,
1255                            },
1256                        }],
1257                    },
1258                ],
1259            }
1260        );
1261    }
1262
1263    #[test]
1264    fn test_parse_equal() {
1265        let result = parse_formula("A1=B1").unwrap();
1266        assert_eq!(
1267            result,
1268            Expr::BinaryOp {
1269                op: BinaryOperator::Eq,
1270                left: Box::new(Expr::CellRef(CellReference {
1271                    col: "A".to_string(),
1272                    row: 1,
1273                    abs_col: false,
1274                    abs_row: false,
1275                    sheet: None,
1276                })),
1277                right: Box::new(Expr::CellRef(CellReference {
1278                    col: "B".to_string(),
1279                    row: 1,
1280                    abs_col: false,
1281                    abs_row: false,
1282                    sheet: None,
1283                })),
1284            }
1285        );
1286    }
1287
1288    #[test]
1289    fn test_parse_not_equal() {
1290        let result = parse_formula("A1<>B1").unwrap();
1291        assert_eq!(
1292            result,
1293            Expr::BinaryOp {
1294                op: BinaryOperator::Ne,
1295                left: Box::new(Expr::CellRef(CellReference {
1296                    col: "A".to_string(),
1297                    row: 1,
1298                    abs_col: false,
1299                    abs_row: false,
1300                    sheet: None,
1301                })),
1302                right: Box::new(Expr::CellRef(CellReference {
1303                    col: "B".to_string(),
1304                    row: 1,
1305                    abs_col: false,
1306                    abs_row: false,
1307                    sheet: None,
1308                })),
1309            }
1310        );
1311    }
1312
1313    #[test]
1314    fn test_parse_less_than() {
1315        let result = parse_formula("A1<B1").unwrap();
1316        assert_eq!(
1317            result,
1318            Expr::BinaryOp {
1319                op: BinaryOperator::Lt,
1320                left: Box::new(Expr::CellRef(CellReference {
1321                    col: "A".to_string(),
1322                    row: 1,
1323                    abs_col: false,
1324                    abs_row: false,
1325                    sheet: None,
1326                })),
1327                right: Box::new(Expr::CellRef(CellReference {
1328                    col: "B".to_string(),
1329                    row: 1,
1330                    abs_col: false,
1331                    abs_row: false,
1332                    sheet: None,
1333                })),
1334            }
1335        );
1336    }
1337
1338    #[test]
1339    fn test_parse_concat() {
1340        let result = parse_formula("A1&B1").unwrap();
1341        assert_eq!(
1342            result,
1343            Expr::BinaryOp {
1344                op: BinaryOperator::Concat,
1345                left: Box::new(Expr::CellRef(CellReference {
1346                    col: "A".to_string(),
1347                    row: 1,
1348                    abs_col: false,
1349                    abs_row: false,
1350                    sheet: None,
1351                })),
1352                right: Box::new(Expr::CellRef(CellReference {
1353                    col: "B".to_string(),
1354                    row: 1,
1355                    abs_col: false,
1356                    abs_row: false,
1357                    sheet: None,
1358                })),
1359            }
1360        );
1361    }
1362
1363    #[test]
1364    fn test_parse_complex_formula() {
1365        // "SUM(A1:A10)+AVERAGE(B1:B10)*2"
1366        let result = parse_formula("SUM(A1:A10)+AVERAGE(B1:B10)*2").unwrap();
1367        assert_eq!(
1368            result,
1369            Expr::BinaryOp {
1370                op: BinaryOperator::Add,
1371                left: Box::new(Expr::Function {
1372                    name: "SUM".to_string(),
1373                    args: vec![Expr::Range {
1374                        start: CellReference {
1375                            col: "A".to_string(),
1376                            row: 1,
1377                            abs_col: false,
1378                            abs_row: false,
1379                            sheet: None,
1380                        },
1381                        end: CellReference {
1382                            col: "A".to_string(),
1383                            row: 10,
1384                            abs_col: false,
1385                            abs_row: false,
1386                            sheet: None,
1387                        },
1388                    }],
1389                }),
1390                right: Box::new(Expr::BinaryOp {
1391                    op: BinaryOperator::Mul,
1392                    left: Box::new(Expr::Function {
1393                        name: "AVERAGE".to_string(),
1394                        args: vec![Expr::Range {
1395                            start: CellReference {
1396                                col: "B".to_string(),
1397                                row: 1,
1398                                abs_col: false,
1399                                abs_row: false,
1400                                sheet: None,
1401                            },
1402                            end: CellReference {
1403                                col: "B".to_string(),
1404                                row: 10,
1405                                abs_col: false,
1406                                abs_row: false,
1407                                sheet: None,
1408                            },
1409                        }],
1410                    }),
1411                    right: Box::new(Expr::Number(2.0)),
1412                }),
1413            }
1414        );
1415    }
1416
1417    #[test]
1418    fn test_parse_sheet_ref() {
1419        let result = parse_formula("Sheet1!A1").unwrap();
1420        assert_eq!(
1421            result,
1422            Expr::CellRef(CellReference {
1423                col: "A".to_string(),
1424                row: 1,
1425                abs_col: false,
1426                abs_row: false,
1427                sheet: Some("Sheet1".to_string()),
1428            })
1429        );
1430    }
1431}