1use 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
28pub 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
40pub(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 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
214fn 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
245fn 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
253fn 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
271fn 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
281fn 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
295fn 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
309fn 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
316fn parse_unary(input: &str) -> IResult<&str, Expr> {
318 let input = input.trim_start();
319 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 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 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
351fn 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
365fn 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
384fn 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
411fn 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
426fn 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
443fn 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
457fn parse_cell_ref_or_range(input: &str) -> IResult<&str, Expr> {
459 let (input, first) = parse_single_cell_ref(input)?;
460 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
475fn parse_single_cell_ref(input: &str) -> IResult<&str, CellReference> {
477 let (input, sheet) = opt(parse_sheet_prefix)(input)?;
479 let (input, abs_col) = map(opt(tag("$")), |o| o.is_some())(input)?;
481 let (input, col) = alpha1(input)?;
483 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 let (input, abs_row) = map(opt(tag("$")), |o| o.is_some())(input)?;
493 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
510fn parse_sheet_prefix(input: &str) -> IResult<&str, String> {
512 alt((parse_quoted_sheet_prefix, parse_unquoted_sheet_prefix))(input)
513}
514
515fn 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
527fn 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
555fn parse_function_call(input: &str) -> IResult<&str, Expr> {
557 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 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
618fn 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
627fn 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 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 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 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 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 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}