1use std::cmp::Reverse;
8use std::collections::{BinaryHeap, HashMap, HashSet};
9
10use crate::cell::CellValue;
11use crate::error::{Error, Result};
12use crate::formula::ast::{BinaryOperator, CellReference, Expr, UnaryOperator};
13use crate::formula::budget::FormulaBudget;
14use crate::formula::functions;
15use crate::utils::cell_ref::{column_name_to_number, column_number_to_name};
16
17pub trait CellDataProvider {
19 fn get_cell(&self, sheet: &str, col: u32, row: u32) -> CellValue;
21 fn current_sheet(&self) -> &str;
23}
24
25pub struct CellSnapshot {
27 cells: std::collections::HashMap<(String, u32, u32), CellValue>,
28 current_sheet: String,
29}
30
31impl CellSnapshot {
32 pub fn new(current_sheet: String) -> Self {
34 Self {
35 cells: std::collections::HashMap::new(),
36 current_sheet,
37 }
38 }
39
40 pub fn set_cell(&mut self, sheet: &str, col: u32, row: u32, value: CellValue) {
42 self.cells.insert((sheet.to_string(), col, row), value);
43 }
44
45 pub fn set_current_sheet(&mut self, sheet: &str) {
47 self.current_sheet = sheet.to_string();
48 }
49}
50
51impl CellDataProvider for CellSnapshot {
52 fn get_cell(&self, sheet: &str, col: u32, row: u32) -> CellValue {
53 self.cells
54 .get(&(sheet.to_string(), col, row))
55 .cloned()
56 .unwrap_or(CellValue::Empty)
57 }
58
59 fn current_sheet(&self) -> &str {
60 &self.current_sheet
61 }
62}
63
64pub fn evaluate(expr: &Expr, provider: &dyn CellDataProvider) -> Result<CellValue> {
66 let mut evaluator = Evaluator::new(provider);
67 evaluator.eval_expr(expr)
68}
69
70pub struct Evaluator<'a> {
76 provider: &'a dyn CellDataProvider,
77 eval_stack: HashSet<(String, u32, u32)>,
78 depth: usize,
79 position: (u32, u32),
80 sheet_override: Option<String>,
81 budget: FormulaBudget,
82}
83
84impl<'a> Evaluator<'a> {
85 pub fn new(provider: &'a dyn CellDataProvider) -> Self {
87 Self::with_budget(provider, FormulaBudget::secure_calculation())
88 }
89
90 pub fn with_budget(provider: &'a dyn CellDataProvider, budget: FormulaBudget) -> Self {
92 Self {
93 provider,
94 eval_stack: HashSet::new(),
95 depth: 0,
96 position: (1, 1),
97 sheet_override: None,
98 budget,
99 }
100 }
101
102 pub fn set_position(&mut self, col: u32, row: u32) {
104 self.position = (col, row);
105 }
106
107 pub fn position(&self) -> (u32, u32) {
109 self.position
110 }
111
112 pub fn eval_expr(&mut self, expr: &Expr) -> Result<CellValue> {
114 self.budget.charge_evaluation_steps(1)?;
115 self.depth += 1;
116 if let Err(error) = self.budget.check_evaluation_depth(self.depth as u64) {
117 self.depth -= 1;
118 return Err(error);
119 }
120 let result = self.eval_inner(expr).and_then(|value| {
121 let output_bytes = match &value {
122 CellValue::String(value) | CellValue::Error(value) => value.len() as u64,
123 CellValue::RichString(runs) => runs
124 .iter()
125 .map(|run| run.text.len() as u64)
126 .fold(0_u64, u64::saturating_add),
127 _ => 0,
128 };
129 self.budget.charge_output_bytes(output_bytes)?;
130 Ok(value)
131 });
132 self.depth -= 1;
133 result
134 }
135
136 pub fn eval_arg(&mut self, args: &[Expr], index: usize) -> Result<CellValue> {
139 if index >= args.len() {
140 return Err(Error::FormulaError(format!(
141 "missing argument at index {index}"
142 )));
143 }
144 self.eval_expr(&args[index])
145 }
146
147 pub fn collect_numbers(&mut self, args: &[Expr]) -> Result<Vec<f64>> {
155 let mut nums = Vec::new();
156 for arg in args {
157 match arg {
158 Expr::Range { start, end } => {
159 let values = self.expand_range(start, end)?;
160 for v in values {
161 if let CellValue::Error(error) = v {
162 return Err(Error::FormulaError(error));
163 }
164 if let Some(n) = reference_number(&v) {
165 nums.push(n);
166 }
167 }
168 }
169 Expr::CellRef(_) => {
170 let v = self.eval_expr(arg)?;
171 if let CellValue::Error(error) = v {
172 return Err(Error::FormulaError(error));
173 }
174 if let Some(n) = reference_number(&v) {
175 nums.push(n);
176 }
177 }
178 _ => {
179 let v = self.eval_expr(arg)?;
180 nums.push(coerce_to_number(&v)?);
181 }
182 }
183 }
184 Ok(nums)
185 }
186
187 pub fn flatten_args_to_values(&mut self, args: &[Expr]) -> Result<Vec<CellValue>> {
189 let mut values = Vec::new();
190 for arg in args {
191 match arg {
192 Expr::Range { start, end } => {
193 values.extend(self.expand_range(start, end)?);
194 }
195 _ => {
196 values.push(self.eval_expr(arg)?);
197 }
198 }
199 }
200 Ok(values)
201 }
202
203 pub fn expand_range(
205 &mut self,
206 start: &CellReference,
207 end: &CellReference,
208 ) -> Result<Vec<CellValue>> {
209 let sheet = match start.sheet.as_deref() {
210 Some(sheet) => sheet.to_string(),
211 None => self.current_sheet().to_string(),
212 };
213 let start_col = column_name_to_number(&start.col)?;
214 let end_col = column_name_to_number(&end.col)?;
215 let start_row = start.row;
216 let end_row = end.row;
217 let min_col = start_col.min(end_col);
218 let max_col = start_col.max(end_col);
219 let min_row = start_row.min(end_row);
220 let max_row = start_row.max(end_row);
221 let width = u64::from(max_col - min_col)
222 .checked_add(1)
223 .ok_or_else(|| Error::Internal("formula range width overflow".to_string()))?;
224 let height = u64::from(max_row - min_row)
225 .checked_add(1)
226 .ok_or_else(|| Error::Internal("formula range height overflow".to_string()))?;
227 let area = width.saturating_mul(height);
228 self.budget.charge_range_cells(area)?;
229 let mut values = Vec::new();
230 let capacity = usize::try_from(area)
231 .map_err(|_| Error::Internal("formula range capacity overflow".to_string()))?;
232 values
233 .try_reserve_exact(capacity)
234 .map_err(|_| Error::Internal("formula range allocation failed".to_string()))?;
235 for r in min_row..=max_row {
236 for c in min_col..=max_col {
237 values.push(self.resolve_cell(&sheet, c, r)?);
238 }
239 }
240 Ok(values)
241 }
242
243 pub fn current_sheet(&self) -> &str {
245 self.sheet_override
246 .as_deref()
247 .unwrap_or_else(|| self.provider.current_sheet())
248 }
249
250 pub fn charge_match_work(&self, amount: u64) -> Result<()> {
252 self.budget.charge_match_work(amount)
253 }
254
255 pub fn charge_evaluation_work(&self, amount: u64) -> Result<()> {
257 self.budget.charge_evaluation_steps(amount)
258 }
259
260 pub fn check_output_bytes(&self, amount: u64) -> Result<()> {
262 self.budget.check_output_bytes(amount)
263 }
264
265 fn eval_inner(&mut self, expr: &Expr) -> Result<CellValue> {
268 match expr {
269 Expr::Number(n) => Ok(CellValue::Number(*n)),
270 Expr::String(s) => Ok(CellValue::String(s.clone())),
271 Expr::Bool(b) => Ok(CellValue::Bool(*b)),
272 Expr::Error(e) => Ok(CellValue::Error(e.clone())),
273 Expr::Missing => Ok(CellValue::Empty),
274 Expr::CellRef(cell_ref) => self.eval_cell_ref(cell_ref),
275 Expr::Range { start, end } => {
276 let vals = self.expand_range(start, end)?;
278 Ok(vals.into_iter().next().unwrap_or(CellValue::Empty))
279 }
280 Expr::Paren(inner) => self.eval_expr(inner),
281 Expr::BinaryOp { op, left, right } => self.eval_binary(*op, left, right),
282 Expr::UnaryOp { op, operand } => self.eval_unary(*op, operand),
283 Expr::Function { name, args } => self.eval_function(name, args),
284 }
285 }
286
287 fn eval_cell_ref(&mut self, cell_ref: &CellReference) -> Result<CellValue> {
288 let sheet = cell_ref
289 .sheet
290 .as_deref()
291 .unwrap_or_else(|| self.current_sheet())
292 .to_string();
293 let col = column_name_to_number(&cell_ref.col)?;
294 let row = cell_ref.row;
295 self.resolve_cell(&sheet, col, row)
296 }
297
298 fn resolve_cell(&mut self, sheet: &str, col: u32, row: u32) -> Result<CellValue> {
304 let key = (sheet.to_string(), col, row);
305 if self.eval_stack.contains(&key) {
306 let col_name = column_number_to_name(col)?;
307 return Err(Error::CircularReference {
308 cell: format!("{col_name}{row}"),
309 });
310 }
311 let cell_value = self.provider.get_cell(sheet, col, row);
312 match cell_value {
313 CellValue::Formula { ref expr, .. } => {
314 self.eval_stack.insert(key.clone());
315 let saved_sheet = self.sheet_override.replace(sheet.to_string());
316 let saved_position = std::mem::replace(&mut self.position, (col, row));
317 let result = crate::formula::parser::parse_formula_with_budget(expr, &self.budget)
318 .and_then(|parsed| self.eval_expr(&parsed));
319 self.sheet_override = saved_sheet;
320 self.position = saved_position;
321 self.eval_stack.remove(&key);
322 result
323 }
324 other => Ok(other),
325 }
326 }
327
328 fn eval_binary(&mut self, op: BinaryOperator, left: &Expr, right: &Expr) -> Result<CellValue> {
329 let lhs = self.eval_expr(left)?;
330 let rhs = self.eval_expr(right)?;
331
332 if let CellValue::Error(ref e) = lhs {
334 return Ok(CellValue::Error(e.clone()));
335 }
336 if let CellValue::Error(ref e) = rhs {
337 return Ok(CellValue::Error(e.clone()));
338 }
339
340 match op {
341 BinaryOperator::Concat => {
342 let ls = coerce_to_string(&lhs);
343 let rs = coerce_to_string(&rhs);
344 Ok(CellValue::String(format!("{ls}{rs}")))
345 }
346 BinaryOperator::Add
347 | BinaryOperator::Sub
348 | BinaryOperator::Mul
349 | BinaryOperator::Div
350 | BinaryOperator::Pow => {
351 let ln = coerce_to_number(&lhs)?;
352 let rn = coerce_to_number(&rhs)?;
353 let result = match op {
354 BinaryOperator::Add => ln + rn,
355 BinaryOperator::Sub => ln - rn,
356 BinaryOperator::Mul => ln * rn,
357 BinaryOperator::Div => {
358 if rn == 0.0 {
359 return Ok(CellValue::Error("#DIV/0!".to_string()));
360 }
361 ln / rn
362 }
363 BinaryOperator::Pow => ln.powf(rn),
364 _ => unreachable!(),
365 };
366 if !result.is_finite() {
367 return Ok(CellValue::Error("#NUM!".to_string()));
368 }
369 Ok(CellValue::Number(result))
370 }
371 BinaryOperator::Eq
372 | BinaryOperator::Ne
373 | BinaryOperator::Lt
374 | BinaryOperator::Le
375 | BinaryOperator::Gt
376 | BinaryOperator::Ge => {
377 let ord = compare_values(&lhs, &rhs);
378 let result = match op {
379 BinaryOperator::Eq => ord == std::cmp::Ordering::Equal,
380 BinaryOperator::Ne => ord != std::cmp::Ordering::Equal,
381 BinaryOperator::Lt => ord == std::cmp::Ordering::Less,
382 BinaryOperator::Le => {
383 ord == std::cmp::Ordering::Less || ord == std::cmp::Ordering::Equal
384 }
385 BinaryOperator::Gt => ord == std::cmp::Ordering::Greater,
386 BinaryOperator::Ge => {
387 ord == std::cmp::Ordering::Greater || ord == std::cmp::Ordering::Equal
388 }
389 _ => unreachable!(),
390 };
391 Ok(CellValue::Bool(result))
392 }
393 }
394 }
395
396 fn eval_unary(&mut self, op: UnaryOperator, operand: &Expr) -> Result<CellValue> {
397 let val = self.eval_expr(operand)?;
398 if let CellValue::Error(ref e) = val {
399 return Ok(CellValue::Error(e.clone()));
400 }
401 let n = coerce_to_number(&val)?;
402 match op {
403 UnaryOperator::Neg => Ok(CellValue::Number(-n)),
404 UnaryOperator::Pos => Ok(CellValue::Number(n)),
405 UnaryOperator::Percent => Ok(CellValue::Number(n / 100.0)),
406 }
407 }
408
409 fn eval_function(&mut self, name: &str, args: &[Expr]) -> Result<CellValue> {
410 let func = functions::lookup_function(name).ok_or_else(|| Error::UnknownFunction {
411 name: name.to_string(),
412 })?;
413 func(args, self)
414 }
415}
416
417pub fn reference_number(value: &CellValue) -> Option<f64> {
426 match value {
427 CellValue::Number(n) | CellValue::Date(n) => Some(*n),
428 CellValue::Formula {
429 result: Some(inner),
430 ..
431 } => reference_number(inner),
432 _ => None,
433 }
434}
435
436pub fn coerce_to_number(value: &CellValue) -> Result<f64> {
439 match value {
440 CellValue::Number(n) => Ok(*n),
441 CellValue::Date(n) => Ok(*n),
442 CellValue::Bool(b) => Ok(if *b { 1.0 } else { 0.0 }),
443 CellValue::Empty => Ok(0.0),
444 CellValue::String(s) => s
445 .parse::<f64>()
446 .map_err(|_| Error::FormulaError(format!("cannot convert \"{s}\" to number"))),
447 CellValue::Error(e) => Err(Error::FormulaError(e.clone())),
448 CellValue::Formula { result, .. } => {
449 if let Some(ref inner) = result {
450 coerce_to_number(inner)
451 } else {
452 Ok(0.0)
453 }
454 }
455 CellValue::RichString(runs) => {
456 let plain = crate::rich_text::rich_text_to_plain(runs);
457 plain
458 .parse::<f64>()
459 .map_err(|_| Error::FormulaError(format!("cannot convert \"{plain}\" to number")))
460 }
461 }
462}
463
464pub fn coerce_to_string(value: &CellValue) -> String {
466 match value {
467 CellValue::String(s) => s.clone(),
468 CellValue::Number(n) => {
469 if n.fract() == 0.0 && n.is_finite() {
470 format!("{}", *n as i64)
471 } else {
472 format!("{n}")
473 }
474 }
475 CellValue::Bool(b) => {
476 if *b {
477 "TRUE".to_string()
478 } else {
479 "FALSE".to_string()
480 }
481 }
482 CellValue::Empty => String::new(),
483 CellValue::Error(e) => e.clone(),
484 CellValue::Date(n) => format!("{n}"),
485 CellValue::Formula { result, .. } => {
486 if let Some(ref inner) = result {
487 coerce_to_string(inner)
488 } else {
489 String::new()
490 }
491 }
492 CellValue::RichString(runs) => crate::rich_text::rich_text_to_plain(runs),
493 }
494}
495
496pub fn coerce_to_bool(value: &CellValue) -> Result<bool> {
499 match value {
500 CellValue::Bool(b) => Ok(*b),
501 CellValue::Number(n) => Ok(*n != 0.0),
502 CellValue::Date(n) => Ok(*n != 0.0),
503 CellValue::Empty => Ok(false),
504 CellValue::String(s) => match s.to_ascii_uppercase().as_str() {
505 "TRUE" => Ok(true),
506 "FALSE" => Ok(false),
507 _ => Err(Error::FormulaError(format!(
508 "cannot convert \"{s}\" to boolean"
509 ))),
510 },
511 CellValue::Error(e) => Err(Error::FormulaError(e.clone())),
512 CellValue::Formula { result, .. } => {
513 if let Some(ref inner) = result {
514 coerce_to_bool(inner)
515 } else {
516 Ok(false)
517 }
518 }
519 CellValue::RichString(runs) => {
520 let plain = crate::rich_text::rich_text_to_plain(runs);
521 match plain.to_ascii_uppercase().as_str() {
522 "TRUE" => Ok(true),
523 "FALSE" => Ok(false),
524 _ => Err(Error::FormulaError(format!(
525 "cannot convert \"{plain}\" to boolean"
526 ))),
527 }
528 }
529 }
530}
531
532pub fn compare_values(lhs: &CellValue, rhs: &CellValue) -> std::cmp::Ordering {
536 use std::cmp::Ordering;
537
538 match (lhs, rhs) {
539 (CellValue::Empty, CellValue::Number(n) | CellValue::Date(n)) => {
540 return 0.0_f64.partial_cmp(n).unwrap_or(Ordering::Equal);
541 }
542 (CellValue::Number(n) | CellValue::Date(n), CellValue::Empty) => {
543 return n.partial_cmp(&0.0).unwrap_or(Ordering::Equal);
544 }
545 _ => {}
546 }
547
548 fn type_rank(v: &CellValue) -> u8 {
549 match v {
550 CellValue::Empty => 0,
551 CellValue::Number(_) | CellValue::Date(_) => 1,
552 CellValue::String(_) | CellValue::RichString(_) => 2,
553 CellValue::Bool(_) => 3,
554 CellValue::Error(_) => 4,
555 CellValue::Formula { .. } => 5,
556 }
557 }
558
559 let lr = type_rank(lhs);
560 let rr = type_rank(rhs);
561 if lr != rr {
562 return lr.cmp(&rr);
563 }
564
565 match (lhs, rhs) {
566 (CellValue::Empty, CellValue::Empty) => Ordering::Equal,
567 (CellValue::Number(a), CellValue::Number(b))
568 | (CellValue::Date(a), CellValue::Date(b))
569 | (CellValue::Number(a), CellValue::Date(b))
570 | (CellValue::Date(a), CellValue::Number(b)) => a.partial_cmp(b).unwrap_or(Ordering::Equal),
571 (CellValue::String(a), CellValue::String(b)) => {
572 a.to_ascii_lowercase().cmp(&b.to_ascii_lowercase())
573 }
574 (CellValue::Bool(a), CellValue::Bool(b)) => a.cmp(b),
575 _ => Ordering::Equal,
576 }
577}
578
579#[derive(Debug, Clone, PartialEq, Eq, Hash)]
581pub struct CellCoord {
582 pub sheet: String,
583 pub col: u32,
584 pub row: u32,
585}
586
587pub fn build_dependency_graph(
590 formula_cells: &[(CellCoord, String)],
591) -> Result<HashMap<CellCoord, Vec<CellCoord>>> {
592 let budget = FormulaBudget::secure_calculation();
593 let parsed_cells = formula_cells
594 .iter()
595 .map(|(coord, formula_str)| {
596 crate::formula::parser::parse_formula_with_budget(formula_str, &budget)
597 .map(|expr| (coord.clone(), expr))
598 })
599 .collect::<Result<Vec<_>>>()?;
600 build_dependency_graph_from_parsed_with_budget(&parsed_cells, &budget)
601}
602
603pub fn build_dependency_graph_from_parsed(
606 formula_cells: &[(CellCoord, Expr)],
607) -> Result<HashMap<CellCoord, Vec<CellCoord>>> {
608 let budget = FormulaBudget::secure_calculation();
609 build_dependency_graph_from_parsed_with_budget(formula_cells, &budget)
610}
611
612pub(crate) fn build_dependency_graph_from_parsed_with_budget(
614 formula_cells: &[(CellCoord, Expr)],
615 budget: &FormulaBudget,
616) -> Result<HashMap<CellCoord, Vec<CellCoord>>> {
617 let mut deps: HashMap<CellCoord, Vec<CellCoord>> = HashMap::new();
618 deps.try_reserve(formula_cells.len())
619 .map_err(|_| Error::Internal("formula graph allocation failed".to_string()))?;
620 for (coord, expr) in formula_cells {
621 let refs = extract_cell_refs(expr, &coord.sheet, budget)?;
622 deps.insert(coord.clone(), refs);
623 }
624 Ok(deps)
625}
626
627fn extract_cell_refs(
629 expr: &Expr,
630 current_sheet: &str,
631 budget: &FormulaBudget,
632) -> Result<Vec<CellCoord>> {
633 let mut refs = Vec::new();
634 let mut stack = vec![expr];
635 while let Some(expr) = stack.pop() {
636 match expr {
637 Expr::CellRef(cell_ref) => {
638 let sheet = cell_ref
639 .sheet
640 .as_deref()
641 .unwrap_or(current_sheet)
642 .to_string();
643 if let Ok(col) = column_name_to_number(&cell_ref.col) {
644 budget.charge_dependency_edges(1)?;
645 refs.try_reserve(1).map_err(|_| {
646 Error::Internal("formula graph allocation failed".to_string())
647 })?;
648 refs.push(CellCoord {
649 sheet,
650 col,
651 row: cell_ref.row,
652 });
653 }
654 }
655 Expr::Range { start, end } => {
656 let sheet = start.sheet.as_deref().unwrap_or(current_sheet).to_string();
657 if let (Ok(start_col), Ok(end_col)) = (
658 column_name_to_number(&start.col),
659 column_name_to_number(&end.col),
660 ) {
661 let min_col = start_col.min(end_col);
662 let max_col = start_col.max(end_col);
663 let min_row = start.row.min(end.row);
664 let max_row = start.row.max(end.row);
665 let width = u64::from(max_col - min_col).checked_add(1).ok_or_else(|| {
666 Error::Internal("formula range width overflow".to_string())
667 })?;
668 let height = u64::from(max_row - min_row).checked_add(1).ok_or_else(|| {
669 Error::Internal("formula range height overflow".to_string())
670 })?;
671 let area = width.saturating_mul(height);
672 budget.charge_dependency_edges(area)?;
673 let capacity = usize::try_from(area).map_err(|_| {
674 Error::Internal("formula graph capacity overflow".to_string())
675 })?;
676 refs.try_reserve(capacity).map_err(|_| {
677 Error::Internal("formula graph allocation failed".to_string())
678 })?;
679 for r in min_row..=max_row {
680 for c in min_col..=max_col {
681 refs.push(CellCoord {
682 sheet: sheet.clone(),
683 col: c,
684 row: r,
685 });
686 }
687 }
688 }
689 }
690 Expr::Function { args, .. } => {
691 for arg in args.iter().rev() {
692 stack.push(arg);
693 }
694 }
695 Expr::BinaryOp { left, right, .. } => {
696 stack.push(right);
697 stack.push(left);
698 }
699 Expr::UnaryOp { operand, .. } | Expr::Paren(operand) => stack.push(operand),
700 _ => {}
701 }
702 }
703 Ok(refs)
704}
705
706pub fn topological_sort(
710 formula_cells: &[CellCoord],
711 deps: &HashMap<CellCoord, Vec<CellCoord>>,
712) -> Result<Vec<CellCoord>> {
713 let budget = FormulaBudget::secure_calculation();
714 topological_sort_with_budget(formula_cells, deps, &budget)
715}
716
717pub(crate) fn topological_sort_with_budget(
719 formula_cells: &[CellCoord],
720 deps: &HashMap<CellCoord, Vec<CellCoord>>,
721 budget: &FormulaBudget,
722) -> Result<Vec<CellCoord>> {
723 let mut formula_set: HashSet<CellCoord> = HashSet::new();
724 formula_set
725 .try_reserve(formula_cells.len())
726 .map_err(|_| Error::Internal("formula ordering allocation failed".to_string()))?;
727 formula_set.extend(formula_cells.iter().cloned());
728
729 let mut in_degree: HashMap<CellCoord, usize> = HashMap::new();
730 let mut dependents: HashMap<CellCoord, Vec<CellCoord>> = HashMap::new();
731 in_degree
732 .try_reserve(formula_cells.len())
733 .map_err(|_| Error::Internal("formula ordering allocation failed".to_string()))?;
734 dependents
735 .try_reserve(formula_cells.len())
736 .map_err(|_| Error::Internal("formula ordering allocation failed".to_string()))?;
737
738 for cell in formula_cells {
739 in_degree.entry(cell.clone()).or_insert(0);
740 }
741
742 for (cell, cell_deps) in deps {
743 let dep_count = cell_deps.iter().filter(|d| formula_set.contains(d)).count();
744 in_degree.insert(cell.clone(), dep_count);
745 for dep in cell_deps {
746 if formula_set.contains(dep) {
747 let entries = dependents.entry(dep.clone()).or_default();
748 entries.try_reserve(1).map_err(|_| {
749 Error::Internal("formula ordering allocation failed".to_string())
750 })?;
751 entries.push(cell.clone());
752 }
753 }
754 }
755
756 let mut queue: BinaryHeap<Reverse<(String, u32, u32)>> = BinaryHeap::new();
758 queue
759 .try_reserve(formula_cells.len())
760 .map_err(|_| Error::Internal("formula ordering allocation failed".to_string()))?;
761 for (cell, degree) in &in_degree {
762 if *degree == 0 {
763 budget.charge_ready_queue_ops(1)?;
764 queue.push(Reverse((cell.sheet.clone(), cell.row, cell.col)));
765 }
766 }
767
768 let mut sorted = Vec::new();
769 sorted
770 .try_reserve_exact(formula_cells.len())
771 .map_err(|_| Error::Internal("formula ordering allocation failed".to_string()))?;
772 let mut visited = 0;
773
774 while let Some(Reverse((sheet, row, col))) = queue.pop() {
775 budget.charge_ready_queue_ops(1)?;
776 let cell = CellCoord { sheet, col, row };
777 sorted.push(cell.clone());
778 visited += 1;
779 if let Some(cell_dependents) = dependents.get(&cell) {
780 for dep in cell_dependents {
781 if let Some(deg) = in_degree.get_mut(dep) {
782 *deg -= 1;
783 if *deg == 0 {
784 budget.charge_ready_queue_ops(1)?;
785 queue.push(Reverse((dep.sheet.clone(), dep.row, dep.col)));
786 }
787 }
788 }
789 }
790 }
791
792 if visited != formula_cells.len() {
793 return Err(Error::CircularReference {
794 cell: "multiple cells".to_string(),
795 });
796 }
797
798 Ok(sorted)
799}
800
801#[cfg(test)]
802mod tests {
803 use super::*;
804 use crate::formula::ast::{BinaryOperator, CellReference, Expr, UnaryOperator};
805 use crate::formula::budget::{FormulaBudget, FormulaLimits};
806 use crate::formula::parser::parse_formula;
807
808 fn make_snapshot() -> CellSnapshot {
809 CellSnapshot::new("Sheet1".to_string())
810 }
811
812 struct CountingProvider(std::cell::Cell<u64>);
813
814 impl CellDataProvider for CountingProvider {
815 fn get_cell(&self, _sheet: &str, _col: u32, _row: u32) -> CellValue {
816 self.0.set(self.0.get() + 1);
817 CellValue::Empty
818 }
819
820 fn current_sheet(&self) -> &str {
821 "Sheet1"
822 }
823 }
824
825 #[test]
826 fn range_budget_is_checked_before_provider_calls() {
827 let provider = CountingProvider(std::cell::Cell::new(0));
828 let limits = FormulaLimits {
829 operation_range_cells: 4,
830 ..FormulaLimits::secure_default()
831 };
832 let budget = FormulaBudget::for_calculation(limits).unwrap();
833 let mut evaluator = Evaluator::with_budget(&provider, budget);
834 let start = CellReference {
835 col: "A".to_string(),
836 row: 1,
837 abs_col: false,
838 abs_row: false,
839 sheet: None,
840 };
841 let end = CellReference {
842 col: "B".to_string(),
843 row: 2,
844 abs_col: false,
845 abs_row: false,
846 sheet: None,
847 };
848
849 assert_eq!(evaluator.expand_range(&start, &end).unwrap().len(), 4);
850 assert_eq!(provider.0.get(), 4);
851 let error = evaluator.expand_range(&start, &start).unwrap_err();
852 assert_eq!(
853 error.resource_metadata().unwrap().dimension_code(),
854 "range_cell_count"
855 );
856 assert_eq!(provider.0.get(), 4);
857 }
858
859 #[test]
860 fn ready_queue_budget_is_cumulative_and_deterministic() {
861 let a = CellCoord {
862 sheet: "Sheet1".to_string(),
863 col: 1,
864 row: 1,
865 };
866 let b = CellCoord {
867 sheet: "Sheet1".to_string(),
868 col: 2,
869 row: 1,
870 };
871 let deps = HashMap::from([(a.clone(), vec![]), (b.clone(), vec![])]);
872 let limits = FormulaLimits {
873 operation_ready_queue_ops: 4,
874 ..FormulaLimits::secure_default()
875 };
876 let budget = FormulaBudget::for_calculation(limits).unwrap();
877 assert_eq!(
878 topological_sort_with_budget(&[b.clone(), a.clone()], &deps, &budget).unwrap(),
879 vec![a.clone(), b.clone()]
880 );
881
882 let limits = FormulaLimits {
883 operation_ready_queue_ops: 3,
884 ..FormulaLimits::secure_default()
885 };
886 let budget = FormulaBudget::for_calculation(limits).unwrap();
887 let error = topological_sort_with_budget(&[a, b], &deps, &budget).unwrap_err();
888 assert_eq!(
889 error.resource_metadata().unwrap().dimension_code(),
890 "operation_count"
891 );
892 }
893
894 #[test]
895 fn large_independent_graph_has_exact_bounded_queue_work() {
896 let cells: Vec<CellCoord> = (1..=1_024)
897 .rev()
898 .map(|row| CellCoord {
899 sheet: "Sheet1".to_string(),
900 col: 1,
901 row,
902 })
903 .collect();
904 let deps: HashMap<CellCoord, Vec<CellCoord>> = cells
905 .iter()
906 .cloned()
907 .map(|cell| (cell, Vec::new()))
908 .collect();
909 let limits = FormulaLimits {
910 operation_ready_queue_ops: 2_048,
911 ..FormulaLimits::secure_default()
912 };
913 let budget = FormulaBudget::for_calculation(limits).unwrap();
914 let sorted = topological_sort_with_budget(&cells, &deps, &budget).unwrap();
915 assert_eq!((sorted[0].row, sorted[1_023].row), (1, 1_024));
916
917 let limits = FormulaLimits {
918 operation_ready_queue_ops: 2_047,
919 ..FormulaLimits::secure_default()
920 };
921 let budget = FormulaBudget::for_calculation(limits).unwrap();
922 let error = topological_sort_with_budget(&cells, &deps, &budget).unwrap_err();
923 let metadata = error.resource_metadata().unwrap();
924 assert_eq!((metadata.limit(), metadata.observed()), (2_047, 2_048));
925 }
926
927 #[test]
928 fn dependency_edge_boundaries_are_exact() {
929 let coord = CellCoord {
930 sheet: "Sheet1".to_string(),
931 col: 1,
932 row: 1,
933 };
934 let expression = parse_formula("SUM(A1,B1,C1,D1)").unwrap();
935 let limits = FormulaLimits {
936 operation_dependency_edges: 4,
937 ..FormulaLimits::secure_default()
938 };
939 let budget = FormulaBudget::for_calculation(limits).unwrap();
940 let graph = build_dependency_graph_from_parsed_with_budget(
941 &[(coord.clone(), expression.clone())],
942 &budget,
943 )
944 .unwrap();
945 assert_eq!(graph[&coord].len(), 4);
946
947 let limits = FormulaLimits {
948 operation_dependency_edges: 3,
949 ..FormulaLimits::secure_default()
950 };
951 let budget = FormulaBudget::for_calculation(limits).unwrap();
952 let error = build_dependency_graph_from_parsed_with_budget(&[(coord, expression)], &budget)
953 .unwrap_err();
954 let metadata = error.resource_metadata().unwrap();
955 assert_eq!((metadata.limit(), metadata.observed()), (3, 4));
956 assert_eq!(metadata.dimension_code(), "dependency_edge_count");
957 }
958
959 #[test]
960 fn dependency_range_is_rejected_before_materialization() {
961 let limits = FormulaLimits {
962 operation_range_cells: 0,
963 operation_dependency_edges: 4,
964 ..FormulaLimits::secure_default()
965 };
966 let budget = FormulaBudget::for_calculation(limits).unwrap();
967 let coord = CellCoord {
968 sheet: "Sheet1".to_string(),
969 col: 1,
970 row: 1,
971 };
972 let expression = parse_formula("A1:C2").unwrap();
973
974 let error = build_dependency_graph_from_parsed_with_budget(&[(coord, expression)], &budget)
975 .unwrap_err();
976
977 let metadata = error.resource_metadata().unwrap();
978 assert_eq!(metadata.dimension_code(), "dependency_edge_count");
979 assert_eq!((metadata.limit(), metadata.observed()), (4, 6));
980 }
981
982 #[test]
985 fn eval_number_literal() {
986 let snap = make_snapshot();
987 let result = evaluate(&Expr::Number(42.0), &snap).unwrap();
988 assert_eq!(result, CellValue::Number(42.0));
989 }
990
991 #[test]
992 fn eval_string_literal() {
993 let snap = make_snapshot();
994 let result = evaluate(&Expr::String("hello".to_string()), &snap).unwrap();
995 assert_eq!(result, CellValue::String("hello".to_string()));
996 }
997
998 #[test]
999 fn eval_bool_literal() {
1000 let snap = make_snapshot();
1001 assert_eq!(
1002 evaluate(&Expr::Bool(true), &snap).unwrap(),
1003 CellValue::Bool(true)
1004 );
1005 assert_eq!(
1006 evaluate(&Expr::Bool(false), &snap).unwrap(),
1007 CellValue::Bool(false)
1008 );
1009 }
1010
1011 #[test]
1012 fn eval_error_literal() {
1013 let snap = make_snapshot();
1014 let result = evaluate(&Expr::Error("#N/A".to_string()), &snap).unwrap();
1015 assert_eq!(result, CellValue::Error("#N/A".to_string()));
1016 }
1017
1018 #[test]
1019 fn eval_missing_argument_as_empty() {
1020 let snap = make_snapshot();
1021 let expr = parse_formula("IF(TRUE,,1)").unwrap();
1022 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Empty);
1023 }
1024
1025 #[test]
1028 fn eval_add() {
1029 let snap = make_snapshot();
1030 let expr = Expr::BinaryOp {
1031 op: BinaryOperator::Add,
1032 left: Box::new(Expr::Number(10.0)),
1033 right: Box::new(Expr::Number(5.0)),
1034 };
1035 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(15.0));
1036 }
1037
1038 #[test]
1039 fn eval_sub() {
1040 let snap = make_snapshot();
1041 let expr = Expr::BinaryOp {
1042 op: BinaryOperator::Sub,
1043 left: Box::new(Expr::Number(10.0)),
1044 right: Box::new(Expr::Number(3.0)),
1045 };
1046 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(7.0));
1047 }
1048
1049 #[test]
1050 fn eval_mul() {
1051 let snap = make_snapshot();
1052 let expr = Expr::BinaryOp {
1053 op: BinaryOperator::Mul,
1054 left: Box::new(Expr::Number(4.0)),
1055 right: Box::new(Expr::Number(3.0)),
1056 };
1057 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(12.0));
1058 }
1059
1060 #[test]
1061 fn eval_div() {
1062 let snap = make_snapshot();
1063 let expr = Expr::BinaryOp {
1064 op: BinaryOperator::Div,
1065 left: Box::new(Expr::Number(10.0)),
1066 right: Box::new(Expr::Number(4.0)),
1067 };
1068 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(2.5));
1069 }
1070
1071 #[test]
1072 fn eval_div_by_zero() {
1073 let snap = make_snapshot();
1074 let expr = Expr::BinaryOp {
1075 op: BinaryOperator::Div,
1076 left: Box::new(Expr::Number(1.0)),
1077 right: Box::new(Expr::Number(0.0)),
1078 };
1079 assert_eq!(
1080 evaluate(&expr, &snap).unwrap(),
1081 CellValue::Error("#DIV/0!".to_string())
1082 );
1083 }
1084
1085 #[test]
1086 fn eval_pow() {
1087 let snap = make_snapshot();
1088 let expr = Expr::BinaryOp {
1089 op: BinaryOperator::Pow,
1090 left: Box::new(Expr::Number(2.0)),
1091 right: Box::new(Expr::Number(10.0)),
1092 };
1093 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(1024.0));
1094 }
1095
1096 #[test]
1097 fn eval_negative_fractional_power_returns_num_error() {
1098 let snap = make_snapshot();
1099 let expr = parse_formula("(-8)^0.5").unwrap();
1100
1101 assert_eq!(
1102 evaluate(&expr, &snap).unwrap(),
1103 CellValue::Error("#NUM!".to_string())
1104 );
1105 }
1106
1107 #[test]
1108 fn eval_concat() {
1109 let snap = make_snapshot();
1110 let expr = Expr::BinaryOp {
1111 op: BinaryOperator::Concat,
1112 left: Box::new(Expr::String("hello".to_string())),
1113 right: Box::new(Expr::String(" world".to_string())),
1114 };
1115 assert_eq!(
1116 evaluate(&expr, &snap).unwrap(),
1117 CellValue::String("hello world".to_string())
1118 );
1119 }
1120
1121 #[test]
1122 fn eval_eq() {
1123 let snap = make_snapshot();
1124 let expr = Expr::BinaryOp {
1125 op: BinaryOperator::Eq,
1126 left: Box::new(Expr::Number(5.0)),
1127 right: Box::new(Expr::Number(5.0)),
1128 };
1129 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1130 }
1131
1132 #[test]
1133 fn eval_ne() {
1134 let snap = make_snapshot();
1135 let expr = Expr::BinaryOp {
1136 op: BinaryOperator::Ne,
1137 left: Box::new(Expr::Number(5.0)),
1138 right: Box::new(Expr::Number(3.0)),
1139 };
1140 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1141 }
1142
1143 #[test]
1144 fn eval_lt() {
1145 let snap = make_snapshot();
1146 let expr = Expr::BinaryOp {
1147 op: BinaryOperator::Lt,
1148 left: Box::new(Expr::Number(3.0)),
1149 right: Box::new(Expr::Number(5.0)),
1150 };
1151 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1152 }
1153
1154 #[test]
1155 fn eval_le() {
1156 let snap = make_snapshot();
1157 let expr = Expr::BinaryOp {
1158 op: BinaryOperator::Le,
1159 left: Box::new(Expr::Number(5.0)),
1160 right: Box::new(Expr::Number(5.0)),
1161 };
1162 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1163 }
1164
1165 #[test]
1166 fn eval_gt() {
1167 let snap = make_snapshot();
1168 let expr = Expr::BinaryOp {
1169 op: BinaryOperator::Gt,
1170 left: Box::new(Expr::Number(5.0)),
1171 right: Box::new(Expr::Number(3.0)),
1172 };
1173 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1174 }
1175
1176 #[test]
1177 fn eval_ge() {
1178 let snap = make_snapshot();
1179 let expr = Expr::BinaryOp {
1180 op: BinaryOperator::Ge,
1181 left: Box::new(Expr::Number(5.0)),
1182 right: Box::new(Expr::Number(5.0)),
1183 };
1184 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1185 }
1186
1187 #[test]
1190 fn eval_unary_neg() {
1191 let snap = make_snapshot();
1192 let expr = Expr::UnaryOp {
1193 op: UnaryOperator::Neg,
1194 operand: Box::new(Expr::Number(7.0)),
1195 };
1196 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(-7.0));
1197 }
1198
1199 #[test]
1200 fn eval_unary_pos() {
1201 let snap = make_snapshot();
1202 let expr = Expr::UnaryOp {
1203 op: UnaryOperator::Pos,
1204 operand: Box::new(Expr::Number(7.0)),
1205 };
1206 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(7.0));
1207 }
1208
1209 #[test]
1210 fn eval_unary_percent() {
1211 let snap = make_snapshot();
1212 let expr = Expr::UnaryOp {
1213 op: UnaryOperator::Percent,
1214 operand: Box::new(Expr::Number(50.0)),
1215 };
1216 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(0.5));
1217 }
1218
1219 #[test]
1222 fn eval_cell_ref() {
1223 let mut snap = make_snapshot();
1224 snap.set_cell("Sheet1", 1, 1, CellValue::Number(42.0));
1225 let expr = Expr::CellRef(CellReference {
1226 col: "A".to_string(),
1227 row: 1,
1228 abs_col: false,
1229 abs_row: false,
1230 sheet: None,
1231 });
1232 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(42.0));
1233 }
1234
1235 #[test]
1236 fn eval_cell_ref_empty() {
1237 let snap = make_snapshot();
1238 let expr = Expr::CellRef(CellReference {
1239 col: "Z".to_string(),
1240 row: 99,
1241 abs_col: false,
1242 abs_row: false,
1243 sheet: None,
1244 });
1245 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Empty);
1246 }
1247
1248 #[test]
1249 fn eval_cell_ref_cross_sheet() {
1250 let mut snap = make_snapshot();
1251 snap.set_cell("Sheet2", 2, 3, CellValue::String("remote".to_string()));
1252 let expr = Expr::CellRef(CellReference {
1253 col: "B".to_string(),
1254 row: 3,
1255 abs_col: false,
1256 abs_row: false,
1257 sheet: Some("Sheet2".to_string()),
1258 });
1259 assert_eq!(
1260 evaluate(&expr, &snap).unwrap(),
1261 CellValue::String("remote".to_string())
1262 );
1263 }
1264
1265 #[test]
1268 fn eval_range_expansion() {
1269 let mut snap = make_snapshot();
1270 snap.set_cell("Sheet1", 1, 1, CellValue::Number(1.0));
1271 snap.set_cell("Sheet1", 1, 2, CellValue::Number(2.0));
1272 snap.set_cell("Sheet1", 1, 3, CellValue::Number(3.0));
1273 let expr = parse_formula("SUM(A1:A3)").unwrap();
1274 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(6.0));
1275 }
1276
1277 #[test]
1278 fn eval_range_2d() {
1279 let mut snap = make_snapshot();
1280 snap.set_cell("Sheet1", 1, 1, CellValue::Number(1.0));
1281 snap.set_cell("Sheet1", 2, 1, CellValue::Number(2.0));
1282 snap.set_cell("Sheet1", 1, 2, CellValue::Number(3.0));
1283 snap.set_cell("Sheet1", 2, 2, CellValue::Number(4.0));
1284 let expr = parse_formula("SUM(A1:B2)").unwrap();
1285 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(10.0));
1286 }
1287
1288 #[test]
1289 fn eval_sum_range_propagates_cell_errors() {
1290 let mut snap = make_snapshot();
1291 snap.set_cell("Sheet1", 1, 1, CellValue::Number(1.0));
1292 snap.set_cell("Sheet1", 1, 2, CellValue::Error("#DIV/0!".to_string()));
1293 let expr = parse_formula("SUM(A1:A2)").unwrap();
1294
1295 let error = evaluate(&expr, &snap).unwrap_err();
1296 assert!(error.to_string().contains("#DIV/0!"));
1297 }
1298
1299 #[test]
1300 fn eval_sum_range_skips_non_numeric_text() {
1301 let mut snap = make_snapshot();
1302 snap.set_cell("Sheet1", 1, 1, CellValue::Number(1.0));
1303 snap.set_cell("Sheet1", 1, 2, CellValue::String("text".to_string()));
1304 let expr = parse_formula("SUM(A1:A2)").unwrap();
1305
1306 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(1.0));
1307 }
1308
1309 #[test]
1310 fn eval_blank_cell_compares_as_zero_against_numbers() {
1311 let snap = make_snapshot();
1312
1313 assert_eq!(
1314 evaluate(&parse_formula("A1=0").unwrap(), &snap).unwrap(),
1315 CellValue::Bool(true)
1316 );
1317 assert_eq!(
1318 evaluate(&parse_formula("A1<>0").unwrap(), &snap).unwrap(),
1319 CellValue::Bool(false)
1320 );
1321 assert_eq!(
1322 evaluate(&parse_formula("A1<1").unwrap(), &snap).unwrap(),
1323 CellValue::Bool(true)
1324 );
1325 }
1326
1327 #[test]
1328 fn eval_row_and_column_without_reference_use_evaluator_position() {
1329 let snap = make_snapshot();
1330 let mut evaluator = Evaluator::new(&snap);
1331 evaluator.set_position(3, 5);
1332
1333 assert_eq!(
1334 evaluator
1335 .eval_expr(&parse_formula("ROW()").unwrap())
1336 .unwrap(),
1337 CellValue::Number(5.0)
1338 );
1339 assert_eq!(
1340 evaluator
1341 .eval_expr(&parse_formula("COLUMN()").unwrap())
1342 .unwrap(),
1343 CellValue::Number(3.0)
1344 );
1345 }
1346
1347 #[test]
1348 fn eval_row_and_column_preserve_default_and_explicit_references() {
1349 let snap = make_snapshot();
1350
1351 assert_eq!(
1352 evaluate(&parse_formula("ROW()").unwrap(), &snap).unwrap(),
1353 CellValue::Number(1.0)
1354 );
1355 assert_eq!(
1356 evaluate(&parse_formula("ROW(A7)").unwrap(), &snap).unwrap(),
1357 CellValue::Number(7.0)
1358 );
1359 assert_eq!(
1360 evaluate(&parse_formula("COLUMN(C7)").unwrap(), &snap).unwrap(),
1361 CellValue::Number(3.0)
1362 );
1363 }
1364
1365 #[test]
1368 fn coerce_bool_to_number() {
1369 assert_eq!(coerce_to_number(&CellValue::Bool(true)).unwrap(), 1.0);
1370 assert_eq!(coerce_to_number(&CellValue::Bool(false)).unwrap(), 0.0);
1371 }
1372
1373 #[test]
1374 fn coerce_empty_to_number() {
1375 assert_eq!(coerce_to_number(&CellValue::Empty).unwrap(), 0.0);
1376 }
1377
1378 #[test]
1379 fn coerce_string_to_number_success() {
1380 assert_eq!(
1381 coerce_to_number(&CellValue::String("3.15".to_string())).unwrap(),
1382 3.15
1383 );
1384 }
1385
1386 #[test]
1387 fn coerce_string_to_number_fail() {
1388 assert!(coerce_to_number(&CellValue::String("abc".to_string())).is_err());
1389 }
1390
1391 #[test]
1392 fn coerce_number_to_string() {
1393 assert_eq!(coerce_to_string(&CellValue::Number(42.0)), "42");
1394 assert_eq!(coerce_to_string(&CellValue::Number(3.15)), "3.15");
1395 }
1396
1397 #[test]
1398 fn coerce_bool_to_string() {
1399 assert_eq!(coerce_to_string(&CellValue::Bool(true)), "TRUE");
1400 assert_eq!(coerce_to_string(&CellValue::Bool(false)), "FALSE");
1401 }
1402
1403 #[test]
1404 fn coerce_number_to_bool() {
1405 assert!(coerce_to_bool(&CellValue::Number(1.0)).unwrap());
1406 assert!(!coerce_to_bool(&CellValue::Number(0.0)).unwrap());
1407 }
1408
1409 #[test]
1412 fn eval_circular_reference() {
1413 let mut snap = make_snapshot();
1414 snap.set_cell(
1416 "Sheet1",
1417 1,
1418 1,
1419 CellValue::Formula {
1420 expr: "A1".to_string(),
1421 result: None,
1422 },
1423 );
1424 let expr = Expr::CellRef(CellReference {
1425 col: "A".to_string(),
1426 row: 1,
1427 abs_col: false,
1428 abs_row: false,
1429 sheet: None,
1430 });
1431 let result = evaluate(&expr, &snap);
1432 assert!(result.is_err());
1433 let err_str = result.unwrap_err().to_string();
1434 assert!(
1435 err_str.contains("circular reference"),
1436 "expected circular reference error, got: {err_str}"
1437 );
1438 }
1439
1440 #[test]
1441 fn eval_indirect_circular_reference() {
1442 let mut snap = make_snapshot();
1443 snap.set_cell(
1445 "Sheet1",
1446 1,
1447 1,
1448 CellValue::Formula {
1449 expr: "B1".to_string(),
1450 result: None,
1451 },
1452 );
1453 snap.set_cell(
1454 "Sheet1",
1455 2,
1456 1,
1457 CellValue::Formula {
1458 expr: "A1".to_string(),
1459 result: None,
1460 },
1461 );
1462 let expr = Expr::CellRef(CellReference {
1463 col: "A".to_string(),
1464 row: 1,
1465 abs_col: false,
1466 abs_row: false,
1467 sheet: None,
1468 });
1469 let result = evaluate(&expr, &snap);
1470 assert!(result.is_err());
1471 assert!(result
1472 .unwrap_err()
1473 .to_string()
1474 .contains("circular reference"));
1475 }
1476
1477 #[test]
1480 fn eval_max_depth_exceeded() {
1481 let snap = make_snapshot();
1482 let mut expr = Expr::Number(1.0);
1484 for _ in 0..1_025 {
1485 expr = Expr::Paren(Box::new(expr));
1486 }
1487 let error = evaluate(&expr, &snap).unwrap_err();
1488 let metadata = error.resource_metadata().unwrap();
1489 assert_eq!(metadata.dimension_code(), "nesting_depth");
1490 assert_eq!((metadata.limit(), metadata.observed()), (1_024, 1_025));
1491 }
1492
1493 #[test]
1496 fn eval_sum_function() {
1497 let snap = make_snapshot();
1498 let expr = parse_formula("SUM(1,2,3)").unwrap();
1499 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(6.0));
1500 }
1501
1502 #[test]
1503 fn eval_average_function() {
1504 let snap = make_snapshot();
1505 let expr = parse_formula("AVERAGE(10,20,30)").unwrap();
1506 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(20.0));
1507 }
1508
1509 #[test]
1510 fn eval_if_true_branch() {
1511 let snap = make_snapshot();
1512 let expr = parse_formula("IF(TRUE,10,20)").unwrap();
1513 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(10.0));
1514 }
1515
1516 #[test]
1517 fn eval_if_false_branch() {
1518 let snap = make_snapshot();
1519 let expr = parse_formula("IF(FALSE,10,20)").unwrap();
1520 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(20.0));
1521 }
1522
1523 #[test]
1524 fn eval_unknown_function() {
1525 let snap = make_snapshot();
1526 let expr = parse_formula("NONEXISTENT(1)").unwrap();
1527 let result = evaluate(&expr, &snap);
1528 assert!(result.is_err());
1529 assert!(result.unwrap_err().to_string().contains("unknown function"));
1530 }
1531
1532 #[test]
1533 fn eval_nested_functions() {
1534 let snap = make_snapshot();
1535 let expr = parse_formula("SUM(1,MAX(2,3))").unwrap();
1536 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(4.0));
1537 }
1538
1539 #[test]
1540 fn eval_abs_function() {
1541 let snap = make_snapshot();
1542 let expr = parse_formula("ABS(-42)").unwrap();
1543 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(42.0));
1544 }
1545
1546 #[test]
1547 fn eval_formula_cell_chain() {
1548 let mut snap = make_snapshot();
1549 snap.set_cell("Sheet1", 1, 1, CellValue::Number(10.0));
1550 snap.set_cell("Sheet1", 2, 1, CellValue::Number(20.0));
1551 snap.set_cell(
1553 "Sheet1",
1554 3,
1555 1,
1556 CellValue::Formula {
1557 expr: "A1+B1".to_string(),
1558 result: None,
1559 },
1560 );
1561 let expr = Expr::CellRef(CellReference {
1562 col: "C".to_string(),
1563 row: 1,
1564 abs_col: false,
1565 abs_row: false,
1566 sheet: None,
1567 });
1568 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(30.0));
1569 }
1570
1571 #[test]
1572 fn eval_error_propagation_in_binary() {
1573 let snap = make_snapshot();
1574 let expr = Expr::BinaryOp {
1575 op: BinaryOperator::Add,
1576 left: Box::new(Expr::Error("#VALUE!".to_string())),
1577 right: Box::new(Expr::Number(1.0)),
1578 };
1579 assert_eq!(
1580 evaluate(&expr, &snap).unwrap(),
1581 CellValue::Error("#VALUE!".to_string())
1582 );
1583 }
1584
1585 #[test]
1586 fn eval_parsed_expression() {
1587 let mut snap = make_snapshot();
1588 snap.set_cell("Sheet1", 1, 1, CellValue::Number(5.0));
1589 snap.set_cell("Sheet1", 2, 1, CellValue::Number(3.0));
1590 let expr = parse_formula("A1*B1+2").unwrap();
1591 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(17.0));
1592 }
1593
1594 #[test]
1595 fn eval_comparison_strings() {
1596 let snap = make_snapshot();
1597 let expr = Expr::BinaryOp {
1598 op: BinaryOperator::Lt,
1599 left: Box::new(Expr::String("abc".to_string())),
1600 right: Box::new(Expr::String("def".to_string())),
1601 };
1602 assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1603 }
1604
1605 #[test]
1606 fn eval_wrong_arg_count() {
1607 let snap = make_snapshot();
1608 let expr = parse_formula("ABS(1,2)").unwrap();
1609 let result = evaluate(&expr, &snap);
1610 assert!(result.is_err());
1611 assert!(result.unwrap_err().to_string().contains("expects"));
1612 }
1613
1614 #[test]
1615 fn eval_concat_number_and_string() {
1616 let snap = make_snapshot();
1617 let expr = Expr::BinaryOp {
1618 op: BinaryOperator::Concat,
1619 left: Box::new(Expr::Number(42.0)),
1620 right: Box::new(Expr::String(" items".to_string())),
1621 };
1622 assert_eq!(
1623 evaluate(&expr, &snap).unwrap(),
1624 CellValue::String("42 items".to_string())
1625 );
1626 }
1627
1628 fn coord(sheet: &str, col: u32, row: u32) -> CellCoord {
1629 CellCoord {
1630 sheet: sheet.to_string(),
1631 col,
1632 row,
1633 }
1634 }
1635
1636 #[test]
1637 fn test_build_dependency_graph_simple() {
1638 let formula_cells = vec![(coord("Sheet1", 1, 1), "B1+C1".to_string())];
1640 let deps = build_dependency_graph(&formula_cells).unwrap();
1641 let a1_deps = deps.get(&coord("Sheet1", 1, 1)).unwrap();
1642 assert!(a1_deps.contains(&coord("Sheet1", 2, 1))); assert!(a1_deps.contains(&coord("Sheet1", 3, 1))); assert_eq!(a1_deps.len(), 2);
1645 }
1646
1647 #[test]
1648 fn test_build_dependency_graph_range() {
1649 let formula_cells = vec![(coord("Sheet1", 1, 1), "SUM(B1:B5)".to_string())];
1651 let deps = build_dependency_graph(&formula_cells).unwrap();
1652 let a1_deps = deps.get(&coord("Sheet1", 1, 1)).unwrap();
1653 assert_eq!(a1_deps.len(), 5);
1654 for r in 1..=5 {
1655 assert!(a1_deps.contains(&coord("Sheet1", 2, r)));
1656 }
1657 }
1658
1659 #[test]
1660 fn test_build_dependency_graph_cross_sheet() {
1661 let formula_cells = vec![(coord("Sheet1", 1, 1), "Sheet2!B1".to_string())];
1663 let deps = build_dependency_graph(&formula_cells).unwrap();
1664 let a1_deps = deps.get(&coord("Sheet1", 1, 1)).unwrap();
1665 assert_eq!(a1_deps.len(), 1);
1666 assert_eq!(a1_deps[0], coord("Sheet2", 2, 1));
1667 }
1668
1669 #[test]
1670 fn test_extract_cell_refs_from_nested_expr() {
1671 let expr = parse_formula("A1+SUM(B1:B3,C1)").unwrap();
1672 let budget = FormulaBudget::secure_calculation();
1673 let refs = extract_cell_refs(&expr, "Sheet1", &budget).unwrap();
1674 assert!(refs.contains(&coord("Sheet1", 1, 1))); assert!(refs.contains(&coord("Sheet1", 2, 1))); assert!(refs.contains(&coord("Sheet1", 2, 2))); assert!(refs.contains(&coord("Sheet1", 2, 3))); assert!(refs.contains(&coord("Sheet1", 3, 1))); assert_eq!(refs.len(), 5);
1680 }
1681
1682 #[test]
1683 fn test_topological_sort_linear_chain() {
1684 let formula_cells = vec![coord("Sheet1", 1, 2), coord("Sheet1", 1, 3)];
1686 let mut deps = HashMap::new();
1687 deps.insert(coord("Sheet1", 1, 2), vec![coord("Sheet1", 1, 1)]); deps.insert(
1689 coord("Sheet1", 1, 3),
1690 vec![coord("Sheet1", 1, 2)], );
1692 let sorted = topological_sort(&formula_cells, &deps).unwrap();
1693 assert_eq!(sorted.len(), 2);
1694 let pos_a2 = sorted
1696 .iter()
1697 .position(|c| *c == coord("Sheet1", 1, 2))
1698 .unwrap();
1699 let pos_a3 = sorted
1700 .iter()
1701 .position(|c| *c == coord("Sheet1", 1, 3))
1702 .unwrap();
1703 assert!(pos_a2 < pos_a3);
1704 }
1705
1706 #[test]
1707 fn test_topological_sort_diamond() {
1708 let formula_cells = vec![
1711 coord("Sheet1", 1, 1), coord("Sheet1", 2, 1), coord("Sheet1", 3, 1), ];
1715 let mut deps = HashMap::new();
1716 deps.insert(
1717 coord("Sheet1", 1, 1),
1718 vec![coord("Sheet1", 2, 1), coord("Sheet1", 3, 1)],
1719 );
1720 deps.insert(coord("Sheet1", 2, 1), vec![coord("Sheet1", 4, 1)]); deps.insert(coord("Sheet1", 3, 1), vec![coord("Sheet1", 4, 1)]); let sorted = topological_sort(&formula_cells, &deps).unwrap();
1724 assert_eq!(sorted.len(), 3);
1725 let pos_a1 = sorted
1726 .iter()
1727 .position(|c| *c == coord("Sheet1", 1, 1))
1728 .unwrap();
1729 let pos_b1 = sorted
1730 .iter()
1731 .position(|c| *c == coord("Sheet1", 2, 1))
1732 .unwrap();
1733 let pos_c1 = sorted
1734 .iter()
1735 .position(|c| *c == coord("Sheet1", 3, 1))
1736 .unwrap();
1737 assert!(pos_b1 < pos_a1);
1739 assert!(pos_c1 < pos_a1);
1740 }
1741
1742 #[test]
1743 fn test_topological_sort_cycle_detection() {
1744 let formula_cells = vec![coord("Sheet1", 1, 1), coord("Sheet1", 2, 1)];
1746 let mut deps = HashMap::new();
1747 deps.insert(coord("Sheet1", 1, 1), vec![coord("Sheet1", 2, 1)]);
1748 deps.insert(coord("Sheet1", 2, 1), vec![coord("Sheet1", 1, 1)]);
1749
1750 let result = topological_sort(&formula_cells, &deps);
1751 assert!(result.is_err());
1752 let err_str = result.unwrap_err().to_string();
1753 assert!(
1754 err_str.contains("circular reference"),
1755 "expected circular reference error, got: {err_str}"
1756 );
1757 }
1758
1759 #[test]
1760 fn test_topological_sort_no_formulas() {
1761 let formula_cells: Vec<CellCoord> = vec![];
1762 let deps: HashMap<CellCoord, Vec<CellCoord>> = HashMap::new();
1763 let sorted = topological_sort(&formula_cells, &deps).unwrap();
1764 assert!(sorted.is_empty());
1765 }
1766
1767 #[test]
1768 fn test_set_current_sheet() {
1769 let mut snap = CellSnapshot::new("Sheet1".to_string());
1770 assert_eq!(snap.current_sheet(), "Sheet1");
1771 snap.set_current_sheet("Sheet2");
1772 assert_eq!(snap.current_sheet(), "Sheet2");
1773 }
1774}