Skip to main content

sheetkit_core/formula/
eval.rs

1//! Formula evaluation engine.
2//!
3//! Evaluates parsed formula ASTs against cell data provided through the
4//! [`CellDataProvider`] trait. Supports arithmetic, comparison, string
5//! concatenation, cell/range references, and built-in function calls.
6
7use 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
17/// Provides cell data for formula evaluation.
18pub trait CellDataProvider {
19    /// Return the cell value at the given (1-based) column and row on `sheet`.
20    fn get_cell(&self, sheet: &str, col: u32, row: u32) -> CellValue;
21    /// Return the name of the sheet that owns the formula being evaluated.
22    fn current_sheet(&self) -> &str;
23}
24
25/// In-memory snapshot of cell data, decoupled from any Workbook borrow.
26pub struct CellSnapshot {
27    cells: std::collections::HashMap<(String, u32, u32), CellValue>,
28    current_sheet: String,
29}
30
31impl CellSnapshot {
32    /// Create a new empty snapshot with the given current-sheet context.
33    pub fn new(current_sheet: String) -> Self {
34        Self {
35            cells: std::collections::HashMap::new(),
36            current_sheet,
37        }
38    }
39
40    /// Insert a cell value into the snapshot.
41    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    /// Change the current-sheet context used for unqualified cell references.
46    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
64/// Evaluate a parsed formula expression against the given cell data provider.
65pub fn evaluate(expr: &Expr, provider: &dyn CellDataProvider) -> Result<CellValue> {
66    let mut evaluator = Evaluator::new(provider);
67    evaluator.eval_expr(expr)
68}
69
70/// Stateful evaluator that tracks recursion depth and circular references.
71///
72/// Unqualified references resolve against the evaluator's current sheet. That
73/// is the provider's sheet for the top-level formula and the owning sheet of
74/// any referenced formula cell while that cell's formula is being evaluated.
75pub 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    /// Create a new evaluator backed by the given data provider.
86    pub fn new(provider: &'a dyn CellDataProvider) -> Self {
87        Self::with_budget(provider, FormulaBudget::secure_calculation())
88    }
89
90    /// Create an evaluator that shares an existing calculation budget.
91    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    /// Set the 1-based `(column, row)` coordinate of the formula being evaluated.
103    pub fn set_position(&mut self, col: u32, row: u32) {
104        self.position = (col, row);
105    }
106
107    /// Return the 1-based `(column, row)` coordinate of the formula being evaluated.
108    pub fn position(&self) -> (u32, u32) {
109        self.position
110    }
111
112    /// Evaluate an AST expression node.
113    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    /// Evaluate a single argument expression at `index`, returning an error if
137    /// the index is out of bounds.
138    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    /// Collect numeric values for aggregate functions such as SUM or AVERAGE.
148    ///
149    /// Reference arguments (ranges and single-cell references) contribute only
150    /// numeric cells (see [`reference_number`]); empty, boolean, and text cells
151    /// are skipped, and an error cell aborts with that error. Other arguments
152    /// are direct values and use [`coerce_to_number`], so `TRUE` counts as 1
153    /// and numeric text is parsed.
154    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    /// Flatten all arguments into a Vec of CellValues, expanding ranges.
188    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    /// Expand a rectangular cell range into individual CellValues (row-major).
204    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    /// Return the sheet that unqualified references currently resolve against.
244    pub fn current_sheet(&self) -> &str {
245        self.sheet_override
246            .as_deref()
247            .unwrap_or_else(|| self.provider.current_sheet())
248    }
249
250    /// Charge wildcard or criteria matching work before performing it.
251    pub fn charge_match_work(&self, amount: u64) -> Result<()> {
252        self.budget.charge_match_work(amount)
253    }
254
255    /// Charge analytically known loop or helper work before executing it.
256    pub fn charge_evaluation_work(&self, amount: u64) -> Result<()> {
257        self.budget.charge_evaluation_steps(amount)
258    }
259
260    /// Check analytically known string output before reserving it.
261    pub fn check_output_bytes(&self, amount: u64) -> Result<()> {
262        self.budget.check_output_bytes(amount)
263    }
264
265    // -- Private helpers --
266
267    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                // When a range appears in a scalar context, return the first cell.
277                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    /// Resolve a single cell, following formula values and detecting cycles.
299    ///
300    /// A referenced formula is evaluated with the referenced cell's sheet and
301    /// position as context; the caller's context is restored afterwards on
302    /// both success and error. Cycle keys are sheet-qualified.
303    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        // Propagate errors.
333        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
417// -- Type coercion helpers (pub for use by function implementations) --
418
419/// Select the numeric value of a cell reached through a reference.
420///
421/// Aggregates over references use only numeric cells: numbers and dates yield
422/// `Some`, and a cached formula result is inspected recursively. Empty,
423/// boolean, text, and error cells yield `None`; callers decide whether an
424/// error cell propagates.
425pub 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
436/// Coerce a CellValue to f64. Booleans become 0/1, empty becomes 0,
437/// numeric strings are parsed. Non-numeric strings yield an error.
438pub 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
464/// Coerce a CellValue to a string.
465pub 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
496/// Coerce a CellValue to a boolean. Numbers: 0 is false, nonzero is true.
497/// Strings "TRUE"/"FALSE" are recognized. Empty is false.
498pub 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
532/// Compare two CellValues for ordering. Uses Excel comparison semantics:
533/// numbers compare numerically, strings compare case-insensitively,
534/// mixed types rank as: empty < number < string < bool.
535pub 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/// A cell coordinate used as a node in the dependency graph.
580#[derive(Debug, Clone, PartialEq, Eq, Hash)]
581pub struct CellCoord {
582    pub sheet: String,
583    pub col: u32,
584    pub row: u32,
585}
586
587/// Build a dependency graph from formula cells.
588/// Returns a map from each formula cell to the cells it depends on.
589pub 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
603/// Build a dependency graph from formula cells that have already been parsed.
604/// Returns a map from each formula cell to the cells it depends on.
605pub 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
612/// Build a dependency graph while charging an existing calculation budget.
613pub(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
627/// Extract all cell references from a parsed expression.
628fn 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
706/// Topological sort of formula cells based on dependencies.
707/// Returns cells in evaluation order (dependencies first).
708/// Detects cycles and returns an error if found.
709pub 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
717/// Deterministically sort formula cells while charging queue operations.
718pub(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    // Kahn's algorithm
757    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    // -- Literal evaluation --
983
984    #[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    // -- Binary operations --
1026
1027    #[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    // -- Unary operations --
1188
1189    #[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    // -- Cell reference resolution --
1220
1221    #[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    // -- Range expansion --
1266
1267    #[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    // -- Type coercion --
1366
1367    #[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    // -- Circular reference detection --
1410
1411    #[test]
1412    fn eval_circular_reference() {
1413        let mut snap = make_snapshot();
1414        // A1 references itself.
1415        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        // A1 = B1, B1 = A1
1444        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    // -- Max depth --
1478
1479    #[test]
1480    fn eval_max_depth_exceeded() {
1481        let snap = make_snapshot();
1482        // Build a deeply nested expression: ((((... (1) ...))))
1483        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    // -- Function evaluation --
1494
1495    #[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        // C1 = A1 + B1
1552        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        // A1 = B1 + C1
1639        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))); // B1
1643        assert!(a1_deps.contains(&coord("Sheet1", 3, 1))); // C1
1644        assert_eq!(a1_deps.len(), 2);
1645    }
1646
1647    #[test]
1648    fn test_build_dependency_graph_range() {
1649        // A1 = SUM(B1:B5)
1650        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        // Sheet1!A1 = Sheet2!B1
1662        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))); // A1
1675        assert!(refs.contains(&coord("Sheet1", 2, 1))); // B1
1676        assert!(refs.contains(&coord("Sheet1", 2, 2))); // B2
1677        assert!(refs.contains(&coord("Sheet1", 2, 3))); // B3
1678        assert!(refs.contains(&coord("Sheet1", 3, 1))); // C1
1679        assert_eq!(refs.len(), 5);
1680    }
1681
1682    #[test]
1683    fn test_topological_sort_linear_chain() {
1684        // A2 = A1 + 1, A3 = A2 + 1 (A1 is a value, not a formula)
1685        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)]); // A2 depends on A1 (value)
1688        deps.insert(
1689            coord("Sheet1", 1, 3),
1690            vec![coord("Sheet1", 1, 2)], // A3 depends on A2 (formula)
1691        );
1692        let sorted = topological_sort(&formula_cells, &deps).unwrap();
1693        assert_eq!(sorted.len(), 2);
1694        // A2 must come before A3
1695        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        // A1 = B1 + C1, B1 = D1, C1 = D1
1709        // D1 is a value, so formula_cells = [A1, B1, C1]
1710        let formula_cells = vec![
1711            coord("Sheet1", 1, 1), // A1
1712            coord("Sheet1", 2, 1), // B1
1713            coord("Sheet1", 3, 1), // C1
1714        ];
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)]); // D1 value
1721        deps.insert(coord("Sheet1", 3, 1), vec![coord("Sheet1", 4, 1)]); // D1 value
1722
1723        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        // B1 and C1 must come before A1
1738        assert!(pos_b1 < pos_a1);
1739        assert!(pos_c1 < pos_a1);
1740    }
1741
1742    #[test]
1743    fn test_topological_sort_cycle_detection() {
1744        // A1 = B1, B1 = A1
1745        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}