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::collections::{HashMap, HashSet};
8
9use crate::cell::CellValue;
10use crate::error::{Error, Result};
11use crate::formula::ast::{BinaryOperator, CellReference, Expr, UnaryOperator};
12use crate::formula::functions;
13use crate::utils::cell_ref::{column_name_to_number, column_number_to_name};
14
15/// Maximum recursion depth for nested formula evaluation.
16const MAX_EVAL_DEPTH: usize = 256;
17
18/// Provides cell data for formula evaluation.
19pub trait CellDataProvider {
20    /// Return the cell value at the given (1-based) column and row on `sheet`.
21    fn get_cell(&self, sheet: &str, col: u32, row: u32) -> CellValue;
22    /// Return the name of the sheet that owns the formula being evaluated.
23    fn current_sheet(&self) -> &str;
24}
25
26/// In-memory snapshot of cell data, decoupled from any Workbook borrow.
27pub struct CellSnapshot {
28    cells: std::collections::HashMap<(String, u32, u32), CellValue>,
29    current_sheet: String,
30}
31
32impl CellSnapshot {
33    /// Create a new empty snapshot with the given current-sheet context.
34    pub fn new(current_sheet: String) -> Self {
35        Self {
36            cells: std::collections::HashMap::new(),
37            current_sheet,
38        }
39    }
40
41    /// Insert a cell value into the snapshot.
42    pub fn set_cell(&mut self, sheet: &str, col: u32, row: u32, value: CellValue) {
43        self.cells.insert((sheet.to_string(), col, row), value);
44    }
45
46    /// Change the current-sheet context used for unqualified cell references.
47    pub fn set_current_sheet(&mut self, sheet: &str) {
48        self.current_sheet = sheet.to_string();
49    }
50}
51
52impl CellDataProvider for CellSnapshot {
53    fn get_cell(&self, sheet: &str, col: u32, row: u32) -> CellValue {
54        self.cells
55            .get(&(sheet.to_string(), col, row))
56            .cloned()
57            .unwrap_or(CellValue::Empty)
58    }
59
60    fn current_sheet(&self) -> &str {
61        &self.current_sheet
62    }
63}
64
65/// Evaluate a parsed formula expression against the given cell data provider.
66pub fn evaluate(expr: &Expr, provider: &dyn CellDataProvider) -> Result<CellValue> {
67    let mut evaluator = Evaluator::new(provider);
68    evaluator.eval_expr(expr)
69}
70
71/// Stateful evaluator that tracks recursion depth and circular references.
72pub struct Evaluator<'a> {
73    provider: &'a dyn CellDataProvider,
74    eval_stack: HashSet<(String, u32, u32)>,
75    depth: usize,
76}
77
78impl<'a> Evaluator<'a> {
79    /// Create a new evaluator backed by the given data provider.
80    pub fn new(provider: &'a dyn CellDataProvider) -> Self {
81        Self {
82            provider,
83            eval_stack: HashSet::new(),
84            depth: 0,
85        }
86    }
87
88    /// Evaluate an AST expression node.
89    pub fn eval_expr(&mut self, expr: &Expr) -> Result<CellValue> {
90        self.depth += 1;
91        if self.depth > MAX_EVAL_DEPTH {
92            self.depth -= 1;
93            return Err(Error::FormulaError(
94                "maximum evaluation depth exceeded".to_string(),
95            ));
96        }
97        let result = self.eval_inner(expr);
98        self.depth -= 1;
99        result
100    }
101
102    /// Evaluate a single argument expression at `index`, returning an error if
103    /// the index is out of bounds.
104    pub fn eval_arg(&mut self, args: &[Expr], index: usize) -> Result<CellValue> {
105        if index >= args.len() {
106            return Err(Error::FormulaError(format!(
107                "missing argument at index {index}"
108            )));
109        }
110        self.eval_expr(&args[index])
111    }
112
113    /// Collect all numeric values from the argument list, expanding ranges.
114    /// Non-numeric values inside ranges are silently skipped (Excel semantics).
115    pub fn collect_numbers(&mut self, args: &[Expr]) -> Result<Vec<f64>> {
116        let mut nums = Vec::new();
117        for arg in args {
118            match arg {
119                Expr::Range { start, end } => {
120                    let values = self.expand_range(start, end)?;
121                    for v in values {
122                        if let Ok(n) = coerce_to_number(&v) {
123                            nums.push(n);
124                        }
125                    }
126                }
127                _ => {
128                    let v = self.eval_expr(arg)?;
129                    nums.push(coerce_to_number(&v)?);
130                }
131            }
132        }
133        Ok(nums)
134    }
135
136    /// Flatten all arguments into a Vec of CellValues, expanding ranges.
137    pub fn flatten_args_to_values(&mut self, args: &[Expr]) -> Result<Vec<CellValue>> {
138        let mut values = Vec::new();
139        for arg in args {
140            match arg {
141                Expr::Range { start, end } => {
142                    values.extend(self.expand_range(start, end)?);
143                }
144                _ => {
145                    values.push(self.eval_expr(arg)?);
146                }
147            }
148        }
149        Ok(values)
150    }
151
152    /// Expand a rectangular cell range into individual CellValues (row-major).
153    pub fn expand_range(
154        &mut self,
155        start: &CellReference,
156        end: &CellReference,
157    ) -> Result<Vec<CellValue>> {
158        let sheet = start
159            .sheet
160            .as_deref()
161            .unwrap_or_else(|| self.provider.current_sheet());
162        let start_col = column_name_to_number(&start.col)?;
163        let end_col = column_name_to_number(&end.col)?;
164        let start_row = start.row;
165        let end_row = end.row;
166        let min_col = start_col.min(end_col);
167        let max_col = start_col.max(end_col);
168        let min_row = start_row.min(end_row);
169        let max_row = start_row.max(end_row);
170        let mut values = Vec::new();
171        for r in min_row..=max_row {
172            for c in min_col..=max_col {
173                values.push(self.resolve_cell(sheet, c, r)?);
174            }
175        }
176        Ok(values)
177    }
178
179    /// Return the current sheet name from the provider.
180    pub fn current_sheet(&self) -> &str {
181        self.provider.current_sheet()
182    }
183
184    // -- Private helpers --
185
186    fn eval_inner(&mut self, expr: &Expr) -> Result<CellValue> {
187        match expr {
188            Expr::Number(n) => Ok(CellValue::Number(*n)),
189            Expr::String(s) => Ok(CellValue::String(s.clone())),
190            Expr::Bool(b) => Ok(CellValue::Bool(*b)),
191            Expr::Error(e) => Ok(CellValue::Error(e.clone())),
192            Expr::CellRef(cell_ref) => self.eval_cell_ref(cell_ref),
193            Expr::Range { start, end } => {
194                // When a range appears in a scalar context, return the first cell.
195                let vals = self.expand_range(start, end)?;
196                Ok(vals.into_iter().next().unwrap_or(CellValue::Empty))
197            }
198            Expr::Paren(inner) => self.eval_expr(inner),
199            Expr::BinaryOp { op, left, right } => self.eval_binary(*op, left, right),
200            Expr::UnaryOp { op, operand } => self.eval_unary(*op, operand),
201            Expr::Function { name, args } => self.eval_function(name, args),
202        }
203    }
204
205    fn eval_cell_ref(&mut self, cell_ref: &CellReference) -> Result<CellValue> {
206        let sheet = cell_ref
207            .sheet
208            .as_deref()
209            .unwrap_or_else(|| self.provider.current_sheet())
210            .to_string();
211        let col = column_name_to_number(&cell_ref.col)?;
212        let row = cell_ref.row;
213        self.resolve_cell(&sheet, col, row)
214    }
215
216    /// Resolve a single cell, following formula values and detecting cycles.
217    fn resolve_cell(&mut self, sheet: &str, col: u32, row: u32) -> Result<CellValue> {
218        let key = (sheet.to_string(), col, row);
219        if self.eval_stack.contains(&key) {
220            let col_name = column_number_to_name(col)?;
221            return Err(Error::CircularReference {
222                cell: format!("{col_name}{row}"),
223            });
224        }
225        let cell_value = self.provider.get_cell(sheet, col, row);
226        match cell_value {
227            CellValue::Formula { ref expr, .. } => {
228                self.eval_stack.insert(key.clone());
229                let parsed = crate::formula::parser::parse_formula(expr)?;
230                let result = self.eval_expr(&parsed);
231                self.eval_stack.remove(&key);
232                result
233            }
234            other => Ok(other),
235        }
236    }
237
238    fn eval_binary(&mut self, op: BinaryOperator, left: &Expr, right: &Expr) -> Result<CellValue> {
239        let lhs = self.eval_expr(left)?;
240        let rhs = self.eval_expr(right)?;
241
242        // Propagate errors.
243        if let CellValue::Error(ref e) = lhs {
244            return Ok(CellValue::Error(e.clone()));
245        }
246        if let CellValue::Error(ref e) = rhs {
247            return Ok(CellValue::Error(e.clone()));
248        }
249
250        match op {
251            BinaryOperator::Concat => {
252                let ls = coerce_to_string(&lhs);
253                let rs = coerce_to_string(&rhs);
254                Ok(CellValue::String(format!("{ls}{rs}")))
255            }
256            BinaryOperator::Add
257            | BinaryOperator::Sub
258            | BinaryOperator::Mul
259            | BinaryOperator::Div
260            | BinaryOperator::Pow => {
261                let ln = coerce_to_number(&lhs)?;
262                let rn = coerce_to_number(&rhs)?;
263                let result = match op {
264                    BinaryOperator::Add => ln + rn,
265                    BinaryOperator::Sub => ln - rn,
266                    BinaryOperator::Mul => ln * rn,
267                    BinaryOperator::Div => {
268                        if rn == 0.0 {
269                            return Ok(CellValue::Error("#DIV/0!".to_string()));
270                        }
271                        ln / rn
272                    }
273                    BinaryOperator::Pow => ln.powf(rn),
274                    _ => unreachable!(),
275                };
276                Ok(CellValue::Number(result))
277            }
278            BinaryOperator::Eq
279            | BinaryOperator::Ne
280            | BinaryOperator::Lt
281            | BinaryOperator::Le
282            | BinaryOperator::Gt
283            | BinaryOperator::Ge => {
284                let ord = compare_values(&lhs, &rhs);
285                let result = match op {
286                    BinaryOperator::Eq => ord == std::cmp::Ordering::Equal,
287                    BinaryOperator::Ne => ord != std::cmp::Ordering::Equal,
288                    BinaryOperator::Lt => ord == std::cmp::Ordering::Less,
289                    BinaryOperator::Le => {
290                        ord == std::cmp::Ordering::Less || ord == std::cmp::Ordering::Equal
291                    }
292                    BinaryOperator::Gt => ord == std::cmp::Ordering::Greater,
293                    BinaryOperator::Ge => {
294                        ord == std::cmp::Ordering::Greater || ord == std::cmp::Ordering::Equal
295                    }
296                    _ => unreachable!(),
297                };
298                Ok(CellValue::Bool(result))
299            }
300        }
301    }
302
303    fn eval_unary(&mut self, op: UnaryOperator, operand: &Expr) -> Result<CellValue> {
304        let val = self.eval_expr(operand)?;
305        if let CellValue::Error(ref e) = val {
306            return Ok(CellValue::Error(e.clone()));
307        }
308        let n = coerce_to_number(&val)?;
309        match op {
310            UnaryOperator::Neg => Ok(CellValue::Number(-n)),
311            UnaryOperator::Pos => Ok(CellValue::Number(n)),
312            UnaryOperator::Percent => Ok(CellValue::Number(n / 100.0)),
313        }
314    }
315
316    fn eval_function(&mut self, name: &str, args: &[Expr]) -> Result<CellValue> {
317        let func = functions::lookup_function(name).ok_or_else(|| Error::UnknownFunction {
318            name: name.to_string(),
319        })?;
320        func(args, self)
321    }
322}
323
324// -- Type coercion helpers (pub for use by function implementations) --
325
326/// Coerce a CellValue to f64. Booleans become 0/1, empty becomes 0,
327/// numeric strings are parsed. Non-numeric strings yield an error.
328pub fn coerce_to_number(value: &CellValue) -> Result<f64> {
329    match value {
330        CellValue::Number(n) => Ok(*n),
331        CellValue::Date(n) => Ok(*n),
332        CellValue::Bool(b) => Ok(if *b { 1.0 } else { 0.0 }),
333        CellValue::Empty => Ok(0.0),
334        CellValue::String(s) => s
335            .parse::<f64>()
336            .map_err(|_| Error::FormulaError(format!("cannot convert \"{s}\" to number"))),
337        CellValue::Error(e) => Err(Error::FormulaError(e.clone())),
338        CellValue::Formula { result, .. } => {
339            if let Some(ref inner) = result {
340                coerce_to_number(inner)
341            } else {
342                Ok(0.0)
343            }
344        }
345        CellValue::RichString(runs) => {
346            let plain = crate::rich_text::rich_text_to_plain(runs);
347            plain
348                .parse::<f64>()
349                .map_err(|_| Error::FormulaError(format!("cannot convert \"{plain}\" to number")))
350        }
351    }
352}
353
354/// Coerce a CellValue to a string.
355pub fn coerce_to_string(value: &CellValue) -> String {
356    match value {
357        CellValue::String(s) => s.clone(),
358        CellValue::Number(n) => {
359            if n.fract() == 0.0 && n.is_finite() {
360                format!("{}", *n as i64)
361            } else {
362                format!("{n}")
363            }
364        }
365        CellValue::Bool(b) => {
366            if *b {
367                "TRUE".to_string()
368            } else {
369                "FALSE".to_string()
370            }
371        }
372        CellValue::Empty => String::new(),
373        CellValue::Error(e) => e.clone(),
374        CellValue::Date(n) => format!("{n}"),
375        CellValue::Formula { result, .. } => {
376            if let Some(ref inner) = result {
377                coerce_to_string(inner)
378            } else {
379                String::new()
380            }
381        }
382        CellValue::RichString(runs) => crate::rich_text::rich_text_to_plain(runs),
383    }
384}
385
386/// Coerce a CellValue to a boolean. Numbers: 0 is false, nonzero is true.
387/// Strings "TRUE"/"FALSE" are recognized. Empty is false.
388pub fn coerce_to_bool(value: &CellValue) -> Result<bool> {
389    match value {
390        CellValue::Bool(b) => Ok(*b),
391        CellValue::Number(n) => Ok(*n != 0.0),
392        CellValue::Date(n) => Ok(*n != 0.0),
393        CellValue::Empty => Ok(false),
394        CellValue::String(s) => match s.to_ascii_uppercase().as_str() {
395            "TRUE" => Ok(true),
396            "FALSE" => Ok(false),
397            _ => Err(Error::FormulaError(format!(
398                "cannot convert \"{s}\" to boolean"
399            ))),
400        },
401        CellValue::Error(e) => Err(Error::FormulaError(e.clone())),
402        CellValue::Formula { result, .. } => {
403            if let Some(ref inner) = result {
404                coerce_to_bool(inner)
405            } else {
406                Ok(false)
407            }
408        }
409        CellValue::RichString(runs) => {
410            let plain = crate::rich_text::rich_text_to_plain(runs);
411            match plain.to_ascii_uppercase().as_str() {
412                "TRUE" => Ok(true),
413                "FALSE" => Ok(false),
414                _ => Err(Error::FormulaError(format!(
415                    "cannot convert \"{plain}\" to boolean"
416                ))),
417            }
418        }
419    }
420}
421
422/// Compare two CellValues for ordering. Uses Excel comparison semantics:
423/// numbers compare numerically, strings compare case-insensitively,
424/// mixed types rank as: empty < number < string < bool.
425pub fn compare_values(lhs: &CellValue, rhs: &CellValue) -> std::cmp::Ordering {
426    use std::cmp::Ordering;
427
428    fn type_rank(v: &CellValue) -> u8 {
429        match v {
430            CellValue::Empty => 0,
431            CellValue::Number(_) | CellValue::Date(_) => 1,
432            CellValue::String(_) | CellValue::RichString(_) => 2,
433            CellValue::Bool(_) => 3,
434            CellValue::Error(_) => 4,
435            CellValue::Formula { .. } => 5,
436        }
437    }
438
439    let lr = type_rank(lhs);
440    let rr = type_rank(rhs);
441    if lr != rr {
442        return lr.cmp(&rr);
443    }
444
445    match (lhs, rhs) {
446        (CellValue::Empty, CellValue::Empty) => Ordering::Equal,
447        (CellValue::Number(a), CellValue::Number(b))
448        | (CellValue::Date(a), CellValue::Date(b))
449        | (CellValue::Number(a), CellValue::Date(b))
450        | (CellValue::Date(a), CellValue::Number(b)) => a.partial_cmp(b).unwrap_or(Ordering::Equal),
451        (CellValue::String(a), CellValue::String(b)) => {
452            a.to_ascii_lowercase().cmp(&b.to_ascii_lowercase())
453        }
454        (CellValue::Bool(a), CellValue::Bool(b)) => a.cmp(b),
455        _ => Ordering::Equal,
456    }
457}
458
459/// A cell coordinate used as a node in the dependency graph.
460#[derive(Debug, Clone, PartialEq, Eq, Hash)]
461pub struct CellCoord {
462    pub sheet: String,
463    pub col: u32,
464    pub row: u32,
465}
466
467/// Build a dependency graph from formula cells.
468/// Returns a map from each formula cell to the cells it depends on.
469pub fn build_dependency_graph(
470    formula_cells: &[(CellCoord, String)],
471) -> Result<HashMap<CellCoord, Vec<CellCoord>>> {
472    let mut deps: HashMap<CellCoord, Vec<CellCoord>> = HashMap::new();
473    for (coord, formula_str) in formula_cells {
474        let expr = crate::formula::parser::parse_formula(formula_str)?;
475        let refs = extract_cell_refs(&expr, &coord.sheet);
476        deps.insert(coord.clone(), refs);
477    }
478    Ok(deps)
479}
480
481/// Extract all cell references from a parsed expression.
482fn extract_cell_refs(expr: &Expr, current_sheet: &str) -> Vec<CellCoord> {
483    let mut refs = Vec::new();
484    collect_refs(expr, current_sheet, &mut refs);
485    refs
486}
487
488fn collect_refs(expr: &Expr, current_sheet: &str, refs: &mut Vec<CellCoord>) {
489    match expr {
490        Expr::CellRef(cell_ref) => {
491            let sheet = cell_ref
492                .sheet
493                .as_deref()
494                .unwrap_or(current_sheet)
495                .to_string();
496            if let Ok(col) = column_name_to_number(&cell_ref.col) {
497                refs.push(CellCoord {
498                    sheet,
499                    col,
500                    row: cell_ref.row,
501                });
502            }
503        }
504        Expr::Range { start, end } => {
505            let sheet = start.sheet.as_deref().unwrap_or(current_sheet).to_string();
506            if let (Ok(start_col), Ok(end_col)) = (
507                column_name_to_number(&start.col),
508                column_name_to_number(&end.col),
509            ) {
510                let min_col = start_col.min(end_col);
511                let max_col = start_col.max(end_col);
512                let min_row = start.row.min(end.row);
513                let max_row = start.row.max(end.row);
514                for r in min_row..=max_row {
515                    for c in min_col..=max_col {
516                        refs.push(CellCoord {
517                            sheet: sheet.clone(),
518                            col: c,
519                            row: r,
520                        });
521                    }
522                }
523            }
524        }
525        Expr::Function { args, .. } => {
526            for arg in args {
527                collect_refs(arg, current_sheet, refs);
528            }
529        }
530        Expr::BinaryOp { left, right, .. } => {
531            collect_refs(left, current_sheet, refs);
532            collect_refs(right, current_sheet, refs);
533        }
534        Expr::UnaryOp { operand, .. } => {
535            collect_refs(operand, current_sheet, refs);
536        }
537        Expr::Paren(inner) => {
538            collect_refs(inner, current_sheet, refs);
539        }
540        _ => {}
541    }
542}
543
544/// Topological sort of formula cells based on dependencies.
545/// Returns cells in evaluation order (dependencies first).
546/// Detects cycles and returns an error if found.
547pub fn topological_sort(
548    formula_cells: &[CellCoord],
549    deps: &HashMap<CellCoord, Vec<CellCoord>>,
550) -> Result<Vec<CellCoord>> {
551    let formula_set: HashSet<CellCoord> = formula_cells.iter().cloned().collect();
552
553    let mut in_degree: HashMap<CellCoord, usize> = HashMap::new();
554    let mut dependents: HashMap<CellCoord, Vec<CellCoord>> = HashMap::new();
555
556    for cell in formula_cells {
557        in_degree.entry(cell.clone()).or_insert(0);
558    }
559
560    for (cell, cell_deps) in deps {
561        let dep_count = cell_deps.iter().filter(|d| formula_set.contains(d)).count();
562        in_degree.insert(cell.clone(), dep_count);
563        for dep in cell_deps {
564            if formula_set.contains(dep) {
565                dependents
566                    .entry(dep.clone())
567                    .or_default()
568                    .push(cell.clone());
569            }
570        }
571    }
572
573    // Kahn's algorithm
574    let mut queue: Vec<CellCoord> = in_degree
575        .iter()
576        .filter(|(_, &deg)| deg == 0)
577        .map(|(cell, _)| cell.clone())
578        .collect();
579    queue.sort_by(|a, b| (&a.sheet, a.row, a.col).cmp(&(&b.sheet, b.row, b.col)));
580
581    let mut sorted = Vec::new();
582    let mut visited = 0;
583
584    while let Some(cell) = queue.pop() {
585        sorted.push(cell.clone());
586        visited += 1;
587        if let Some(cell_dependents) = dependents.get(&cell) {
588            for dep in cell_dependents {
589                if let Some(deg) = in_degree.get_mut(dep) {
590                    *deg -= 1;
591                    if *deg == 0 {
592                        queue.push(dep.clone());
593                    }
594                }
595            }
596        }
597        queue.sort_by(|a, b| (&b.sheet, b.row, b.col).cmp(&(&a.sheet, a.row, a.col)));
598    }
599
600    if visited != formula_cells.len() {
601        return Err(Error::CircularReference {
602            cell: "multiple cells".to_string(),
603        });
604    }
605
606    Ok(sorted)
607}
608
609#[cfg(test)]
610mod tests {
611    use super::*;
612    use crate::formula::ast::{BinaryOperator, CellReference, Expr, UnaryOperator};
613    use crate::formula::parser::parse_formula;
614
615    fn make_snapshot() -> CellSnapshot {
616        CellSnapshot::new("Sheet1".to_string())
617    }
618
619    // -- Literal evaluation --
620
621    #[test]
622    fn eval_number_literal() {
623        let snap = make_snapshot();
624        let result = evaluate(&Expr::Number(42.0), &snap).unwrap();
625        assert_eq!(result, CellValue::Number(42.0));
626    }
627
628    #[test]
629    fn eval_string_literal() {
630        let snap = make_snapshot();
631        let result = evaluate(&Expr::String("hello".to_string()), &snap).unwrap();
632        assert_eq!(result, CellValue::String("hello".to_string()));
633    }
634
635    #[test]
636    fn eval_bool_literal() {
637        let snap = make_snapshot();
638        assert_eq!(
639            evaluate(&Expr::Bool(true), &snap).unwrap(),
640            CellValue::Bool(true)
641        );
642        assert_eq!(
643            evaluate(&Expr::Bool(false), &snap).unwrap(),
644            CellValue::Bool(false)
645        );
646    }
647
648    #[test]
649    fn eval_error_literal() {
650        let snap = make_snapshot();
651        let result = evaluate(&Expr::Error("#N/A".to_string()), &snap).unwrap();
652        assert_eq!(result, CellValue::Error("#N/A".to_string()));
653    }
654
655    // -- Binary operations --
656
657    #[test]
658    fn eval_add() {
659        let snap = make_snapshot();
660        let expr = Expr::BinaryOp {
661            op: BinaryOperator::Add,
662            left: Box::new(Expr::Number(10.0)),
663            right: Box::new(Expr::Number(5.0)),
664        };
665        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(15.0));
666    }
667
668    #[test]
669    fn eval_sub() {
670        let snap = make_snapshot();
671        let expr = Expr::BinaryOp {
672            op: BinaryOperator::Sub,
673            left: Box::new(Expr::Number(10.0)),
674            right: Box::new(Expr::Number(3.0)),
675        };
676        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(7.0));
677    }
678
679    #[test]
680    fn eval_mul() {
681        let snap = make_snapshot();
682        let expr = Expr::BinaryOp {
683            op: BinaryOperator::Mul,
684            left: Box::new(Expr::Number(4.0)),
685            right: Box::new(Expr::Number(3.0)),
686        };
687        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(12.0));
688    }
689
690    #[test]
691    fn eval_div() {
692        let snap = make_snapshot();
693        let expr = Expr::BinaryOp {
694            op: BinaryOperator::Div,
695            left: Box::new(Expr::Number(10.0)),
696            right: Box::new(Expr::Number(4.0)),
697        };
698        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(2.5));
699    }
700
701    #[test]
702    fn eval_div_by_zero() {
703        let snap = make_snapshot();
704        let expr = Expr::BinaryOp {
705            op: BinaryOperator::Div,
706            left: Box::new(Expr::Number(1.0)),
707            right: Box::new(Expr::Number(0.0)),
708        };
709        assert_eq!(
710            evaluate(&expr, &snap).unwrap(),
711            CellValue::Error("#DIV/0!".to_string())
712        );
713    }
714
715    #[test]
716    fn eval_pow() {
717        let snap = make_snapshot();
718        let expr = Expr::BinaryOp {
719            op: BinaryOperator::Pow,
720            left: Box::new(Expr::Number(2.0)),
721            right: Box::new(Expr::Number(10.0)),
722        };
723        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(1024.0));
724    }
725
726    #[test]
727    fn eval_concat() {
728        let snap = make_snapshot();
729        let expr = Expr::BinaryOp {
730            op: BinaryOperator::Concat,
731            left: Box::new(Expr::String("hello".to_string())),
732            right: Box::new(Expr::String(" world".to_string())),
733        };
734        assert_eq!(
735            evaluate(&expr, &snap).unwrap(),
736            CellValue::String("hello world".to_string())
737        );
738    }
739
740    #[test]
741    fn eval_eq() {
742        let snap = make_snapshot();
743        let expr = Expr::BinaryOp {
744            op: BinaryOperator::Eq,
745            left: Box::new(Expr::Number(5.0)),
746            right: Box::new(Expr::Number(5.0)),
747        };
748        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
749    }
750
751    #[test]
752    fn eval_ne() {
753        let snap = make_snapshot();
754        let expr = Expr::BinaryOp {
755            op: BinaryOperator::Ne,
756            left: Box::new(Expr::Number(5.0)),
757            right: Box::new(Expr::Number(3.0)),
758        };
759        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
760    }
761
762    #[test]
763    fn eval_lt() {
764        let snap = make_snapshot();
765        let expr = Expr::BinaryOp {
766            op: BinaryOperator::Lt,
767            left: Box::new(Expr::Number(3.0)),
768            right: Box::new(Expr::Number(5.0)),
769        };
770        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
771    }
772
773    #[test]
774    fn eval_le() {
775        let snap = make_snapshot();
776        let expr = Expr::BinaryOp {
777            op: BinaryOperator::Le,
778            left: Box::new(Expr::Number(5.0)),
779            right: Box::new(Expr::Number(5.0)),
780        };
781        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
782    }
783
784    #[test]
785    fn eval_gt() {
786        let snap = make_snapshot();
787        let expr = Expr::BinaryOp {
788            op: BinaryOperator::Gt,
789            left: Box::new(Expr::Number(5.0)),
790            right: Box::new(Expr::Number(3.0)),
791        };
792        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
793    }
794
795    #[test]
796    fn eval_ge() {
797        let snap = make_snapshot();
798        let expr = Expr::BinaryOp {
799            op: BinaryOperator::Ge,
800            left: Box::new(Expr::Number(5.0)),
801            right: Box::new(Expr::Number(5.0)),
802        };
803        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
804    }
805
806    // -- Unary operations --
807
808    #[test]
809    fn eval_unary_neg() {
810        let snap = make_snapshot();
811        let expr = Expr::UnaryOp {
812            op: UnaryOperator::Neg,
813            operand: Box::new(Expr::Number(7.0)),
814        };
815        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(-7.0));
816    }
817
818    #[test]
819    fn eval_unary_pos() {
820        let snap = make_snapshot();
821        let expr = Expr::UnaryOp {
822            op: UnaryOperator::Pos,
823            operand: Box::new(Expr::Number(7.0)),
824        };
825        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(7.0));
826    }
827
828    #[test]
829    fn eval_unary_percent() {
830        let snap = make_snapshot();
831        let expr = Expr::UnaryOp {
832            op: UnaryOperator::Percent,
833            operand: Box::new(Expr::Number(50.0)),
834        };
835        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(0.5));
836    }
837
838    // -- Cell reference resolution --
839
840    #[test]
841    fn eval_cell_ref() {
842        let mut snap = make_snapshot();
843        snap.set_cell("Sheet1", 1, 1, CellValue::Number(42.0));
844        let expr = Expr::CellRef(CellReference {
845            col: "A".to_string(),
846            row: 1,
847            abs_col: false,
848            abs_row: false,
849            sheet: None,
850        });
851        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(42.0));
852    }
853
854    #[test]
855    fn eval_cell_ref_empty() {
856        let snap = make_snapshot();
857        let expr = Expr::CellRef(CellReference {
858            col: "Z".to_string(),
859            row: 99,
860            abs_col: false,
861            abs_row: false,
862            sheet: None,
863        });
864        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Empty);
865    }
866
867    #[test]
868    fn eval_cell_ref_cross_sheet() {
869        let mut snap = make_snapshot();
870        snap.set_cell("Sheet2", 2, 3, CellValue::String("remote".to_string()));
871        let expr = Expr::CellRef(CellReference {
872            col: "B".to_string(),
873            row: 3,
874            abs_col: false,
875            abs_row: false,
876            sheet: Some("Sheet2".to_string()),
877        });
878        assert_eq!(
879            evaluate(&expr, &snap).unwrap(),
880            CellValue::String("remote".to_string())
881        );
882    }
883
884    // -- Range expansion --
885
886    #[test]
887    fn eval_range_expansion() {
888        let mut snap = make_snapshot();
889        snap.set_cell("Sheet1", 1, 1, CellValue::Number(1.0));
890        snap.set_cell("Sheet1", 1, 2, CellValue::Number(2.0));
891        snap.set_cell("Sheet1", 1, 3, CellValue::Number(3.0));
892        let expr = parse_formula("SUM(A1:A3)").unwrap();
893        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(6.0));
894    }
895
896    #[test]
897    fn eval_range_2d() {
898        let mut snap = make_snapshot();
899        snap.set_cell("Sheet1", 1, 1, CellValue::Number(1.0));
900        snap.set_cell("Sheet1", 2, 1, CellValue::Number(2.0));
901        snap.set_cell("Sheet1", 1, 2, CellValue::Number(3.0));
902        snap.set_cell("Sheet1", 2, 2, CellValue::Number(4.0));
903        let expr = parse_formula("SUM(A1:B2)").unwrap();
904        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(10.0));
905    }
906
907    // -- Type coercion --
908
909    #[test]
910    fn coerce_bool_to_number() {
911        assert_eq!(coerce_to_number(&CellValue::Bool(true)).unwrap(), 1.0);
912        assert_eq!(coerce_to_number(&CellValue::Bool(false)).unwrap(), 0.0);
913    }
914
915    #[test]
916    fn coerce_empty_to_number() {
917        assert_eq!(coerce_to_number(&CellValue::Empty).unwrap(), 0.0);
918    }
919
920    #[test]
921    fn coerce_string_to_number_success() {
922        assert_eq!(
923            coerce_to_number(&CellValue::String("3.14".to_string())).unwrap(),
924            3.14
925        );
926    }
927
928    #[test]
929    fn coerce_string_to_number_fail() {
930        assert!(coerce_to_number(&CellValue::String("abc".to_string())).is_err());
931    }
932
933    #[test]
934    fn coerce_number_to_string() {
935        assert_eq!(coerce_to_string(&CellValue::Number(42.0)), "42");
936        assert_eq!(coerce_to_string(&CellValue::Number(3.14)), "3.14");
937    }
938
939    #[test]
940    fn coerce_bool_to_string() {
941        assert_eq!(coerce_to_string(&CellValue::Bool(true)), "TRUE");
942        assert_eq!(coerce_to_string(&CellValue::Bool(false)), "FALSE");
943    }
944
945    #[test]
946    fn coerce_number_to_bool() {
947        assert!(coerce_to_bool(&CellValue::Number(1.0)).unwrap());
948        assert!(!coerce_to_bool(&CellValue::Number(0.0)).unwrap());
949    }
950
951    // -- Circular reference detection --
952
953    #[test]
954    fn eval_circular_reference() {
955        let mut snap = make_snapshot();
956        // A1 references itself.
957        snap.set_cell(
958            "Sheet1",
959            1,
960            1,
961            CellValue::Formula {
962                expr: "A1".to_string(),
963                result: None,
964            },
965        );
966        let expr = Expr::CellRef(CellReference {
967            col: "A".to_string(),
968            row: 1,
969            abs_col: false,
970            abs_row: false,
971            sheet: None,
972        });
973        let result = evaluate(&expr, &snap);
974        assert!(result.is_err());
975        let err_str = result.unwrap_err().to_string();
976        assert!(
977            err_str.contains("circular reference"),
978            "expected circular reference error, got: {err_str}"
979        );
980    }
981
982    #[test]
983    fn eval_indirect_circular_reference() {
984        let mut snap = make_snapshot();
985        // A1 = B1, B1 = A1
986        snap.set_cell(
987            "Sheet1",
988            1,
989            1,
990            CellValue::Formula {
991                expr: "B1".to_string(),
992                result: None,
993            },
994        );
995        snap.set_cell(
996            "Sheet1",
997            2,
998            1,
999            CellValue::Formula {
1000                expr: "A1".to_string(),
1001                result: None,
1002            },
1003        );
1004        let expr = Expr::CellRef(CellReference {
1005            col: "A".to_string(),
1006            row: 1,
1007            abs_col: false,
1008            abs_row: false,
1009            sheet: None,
1010        });
1011        let result = evaluate(&expr, &snap);
1012        assert!(result.is_err());
1013        assert!(result
1014            .unwrap_err()
1015            .to_string()
1016            .contains("circular reference"));
1017    }
1018
1019    // -- Max depth --
1020
1021    #[test]
1022    fn eval_max_depth_exceeded() {
1023        let snap = make_snapshot();
1024        // Build a deeply nested expression: ((((... (1) ...))))
1025        let mut expr = Expr::Number(1.0);
1026        for _ in 0..300 {
1027            expr = Expr::Paren(Box::new(expr));
1028        }
1029        let result = evaluate(&expr, &snap);
1030        assert!(result.is_err());
1031        assert!(result
1032            .unwrap_err()
1033            .to_string()
1034            .contains("maximum evaluation depth"));
1035    }
1036
1037    // -- Function evaluation --
1038
1039    #[test]
1040    fn eval_sum_function() {
1041        let snap = make_snapshot();
1042        let expr = parse_formula("SUM(1,2,3)").unwrap();
1043        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(6.0));
1044    }
1045
1046    #[test]
1047    fn eval_average_function() {
1048        let snap = make_snapshot();
1049        let expr = parse_formula("AVERAGE(10,20,30)").unwrap();
1050        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(20.0));
1051    }
1052
1053    #[test]
1054    fn eval_if_true_branch() {
1055        let snap = make_snapshot();
1056        let expr = parse_formula("IF(TRUE,10,20)").unwrap();
1057        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(10.0));
1058    }
1059
1060    #[test]
1061    fn eval_if_false_branch() {
1062        let snap = make_snapshot();
1063        let expr = parse_formula("IF(FALSE,10,20)").unwrap();
1064        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(20.0));
1065    }
1066
1067    #[test]
1068    fn eval_unknown_function() {
1069        let snap = make_snapshot();
1070        let expr = parse_formula("NONEXISTENT(1)").unwrap();
1071        let result = evaluate(&expr, &snap);
1072        assert!(result.is_err());
1073        assert!(result.unwrap_err().to_string().contains("unknown function"));
1074    }
1075
1076    #[test]
1077    fn eval_nested_functions() {
1078        let snap = make_snapshot();
1079        let expr = parse_formula("SUM(1,MAX(2,3))").unwrap();
1080        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(4.0));
1081    }
1082
1083    #[test]
1084    fn eval_abs_function() {
1085        let snap = make_snapshot();
1086        let expr = parse_formula("ABS(-42)").unwrap();
1087        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(42.0));
1088    }
1089
1090    #[test]
1091    fn eval_formula_cell_chain() {
1092        let mut snap = make_snapshot();
1093        snap.set_cell("Sheet1", 1, 1, CellValue::Number(10.0));
1094        snap.set_cell("Sheet1", 2, 1, CellValue::Number(20.0));
1095        // C1 = A1 + B1
1096        snap.set_cell(
1097            "Sheet1",
1098            3,
1099            1,
1100            CellValue::Formula {
1101                expr: "A1+B1".to_string(),
1102                result: None,
1103            },
1104        );
1105        let expr = Expr::CellRef(CellReference {
1106            col: "C".to_string(),
1107            row: 1,
1108            abs_col: false,
1109            abs_row: false,
1110            sheet: None,
1111        });
1112        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(30.0));
1113    }
1114
1115    #[test]
1116    fn eval_error_propagation_in_binary() {
1117        let snap = make_snapshot();
1118        let expr = Expr::BinaryOp {
1119            op: BinaryOperator::Add,
1120            left: Box::new(Expr::Error("#VALUE!".to_string())),
1121            right: Box::new(Expr::Number(1.0)),
1122        };
1123        assert_eq!(
1124            evaluate(&expr, &snap).unwrap(),
1125            CellValue::Error("#VALUE!".to_string())
1126        );
1127    }
1128
1129    #[test]
1130    fn eval_parsed_expression() {
1131        let mut snap = make_snapshot();
1132        snap.set_cell("Sheet1", 1, 1, CellValue::Number(5.0));
1133        snap.set_cell("Sheet1", 2, 1, CellValue::Number(3.0));
1134        let expr = parse_formula("A1*B1+2").unwrap();
1135        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Number(17.0));
1136    }
1137
1138    #[test]
1139    fn eval_comparison_strings() {
1140        let snap = make_snapshot();
1141        let expr = Expr::BinaryOp {
1142            op: BinaryOperator::Lt,
1143            left: Box::new(Expr::String("abc".to_string())),
1144            right: Box::new(Expr::String("def".to_string())),
1145        };
1146        assert_eq!(evaluate(&expr, &snap).unwrap(), CellValue::Bool(true));
1147    }
1148
1149    #[test]
1150    fn eval_wrong_arg_count() {
1151        let snap = make_snapshot();
1152        let expr = parse_formula("ABS(1,2)").unwrap();
1153        let result = evaluate(&expr, &snap);
1154        assert!(result.is_err());
1155        assert!(result.unwrap_err().to_string().contains("expects"));
1156    }
1157
1158    #[test]
1159    fn eval_concat_number_and_string() {
1160        let snap = make_snapshot();
1161        let expr = Expr::BinaryOp {
1162            op: BinaryOperator::Concat,
1163            left: Box::new(Expr::Number(42.0)),
1164            right: Box::new(Expr::String(" items".to_string())),
1165        };
1166        assert_eq!(
1167            evaluate(&expr, &snap).unwrap(),
1168            CellValue::String("42 items".to_string())
1169        );
1170    }
1171
1172    fn coord(sheet: &str, col: u32, row: u32) -> CellCoord {
1173        CellCoord {
1174            sheet: sheet.to_string(),
1175            col,
1176            row,
1177        }
1178    }
1179
1180    #[test]
1181    fn test_build_dependency_graph_simple() {
1182        // A1 = B1 + C1
1183        let formula_cells = vec![(coord("Sheet1", 1, 1), "B1+C1".to_string())];
1184        let deps = build_dependency_graph(&formula_cells).unwrap();
1185        let a1_deps = deps.get(&coord("Sheet1", 1, 1)).unwrap();
1186        assert!(a1_deps.contains(&coord("Sheet1", 2, 1))); // B1
1187        assert!(a1_deps.contains(&coord("Sheet1", 3, 1))); // C1
1188        assert_eq!(a1_deps.len(), 2);
1189    }
1190
1191    #[test]
1192    fn test_build_dependency_graph_range() {
1193        // A1 = SUM(B1:B5)
1194        let formula_cells = vec![(coord("Sheet1", 1, 1), "SUM(B1:B5)".to_string())];
1195        let deps = build_dependency_graph(&formula_cells).unwrap();
1196        let a1_deps = deps.get(&coord("Sheet1", 1, 1)).unwrap();
1197        assert_eq!(a1_deps.len(), 5);
1198        for r in 1..=5 {
1199            assert!(a1_deps.contains(&coord("Sheet1", 2, r)));
1200        }
1201    }
1202
1203    #[test]
1204    fn test_build_dependency_graph_cross_sheet() {
1205        // Sheet1!A1 = Sheet2!B1
1206        let formula_cells = vec![(coord("Sheet1", 1, 1), "Sheet2!B1".to_string())];
1207        let deps = build_dependency_graph(&formula_cells).unwrap();
1208        let a1_deps = deps.get(&coord("Sheet1", 1, 1)).unwrap();
1209        assert_eq!(a1_deps.len(), 1);
1210        assert_eq!(a1_deps[0], coord("Sheet2", 2, 1));
1211    }
1212
1213    #[test]
1214    fn test_extract_cell_refs_from_nested_expr() {
1215        let expr = parse_formula("A1+SUM(B1:B3,C1)").unwrap();
1216        let refs = extract_cell_refs(&expr, "Sheet1");
1217        assert!(refs.contains(&coord("Sheet1", 1, 1))); // A1
1218        assert!(refs.contains(&coord("Sheet1", 2, 1))); // B1
1219        assert!(refs.contains(&coord("Sheet1", 2, 2))); // B2
1220        assert!(refs.contains(&coord("Sheet1", 2, 3))); // B3
1221        assert!(refs.contains(&coord("Sheet1", 3, 1))); // C1
1222        assert_eq!(refs.len(), 5);
1223    }
1224
1225    #[test]
1226    fn test_topological_sort_linear_chain() {
1227        // A2 = A1 + 1, A3 = A2 + 1 (A1 is a value, not a formula)
1228        let formula_cells = vec![coord("Sheet1", 1, 2), coord("Sheet1", 1, 3)];
1229        let mut deps = HashMap::new();
1230        deps.insert(coord("Sheet1", 1, 2), vec![coord("Sheet1", 1, 1)]); // A2 depends on A1 (value)
1231        deps.insert(
1232            coord("Sheet1", 1, 3),
1233            vec![coord("Sheet1", 1, 2)], // A3 depends on A2 (formula)
1234        );
1235        let sorted = topological_sort(&formula_cells, &deps).unwrap();
1236        assert_eq!(sorted.len(), 2);
1237        // A2 must come before A3
1238        let pos_a2 = sorted
1239            .iter()
1240            .position(|c| *c == coord("Sheet1", 1, 2))
1241            .unwrap();
1242        let pos_a3 = sorted
1243            .iter()
1244            .position(|c| *c == coord("Sheet1", 1, 3))
1245            .unwrap();
1246        assert!(pos_a2 < pos_a3);
1247    }
1248
1249    #[test]
1250    fn test_topological_sort_diamond() {
1251        // A1 = B1 + C1, B1 = D1, C1 = D1
1252        // D1 is a value, so formula_cells = [A1, B1, C1]
1253        let formula_cells = vec![
1254            coord("Sheet1", 1, 1), // A1
1255            coord("Sheet1", 2, 1), // B1
1256            coord("Sheet1", 3, 1), // C1
1257        ];
1258        let mut deps = HashMap::new();
1259        deps.insert(
1260            coord("Sheet1", 1, 1),
1261            vec![coord("Sheet1", 2, 1), coord("Sheet1", 3, 1)],
1262        );
1263        deps.insert(coord("Sheet1", 2, 1), vec![coord("Sheet1", 4, 1)]); // D1 value
1264        deps.insert(coord("Sheet1", 3, 1), vec![coord("Sheet1", 4, 1)]); // D1 value
1265
1266        let sorted = topological_sort(&formula_cells, &deps).unwrap();
1267        assert_eq!(sorted.len(), 3);
1268        let pos_a1 = sorted
1269            .iter()
1270            .position(|c| *c == coord("Sheet1", 1, 1))
1271            .unwrap();
1272        let pos_b1 = sorted
1273            .iter()
1274            .position(|c| *c == coord("Sheet1", 2, 1))
1275            .unwrap();
1276        let pos_c1 = sorted
1277            .iter()
1278            .position(|c| *c == coord("Sheet1", 3, 1))
1279            .unwrap();
1280        // B1 and C1 must come before A1
1281        assert!(pos_b1 < pos_a1);
1282        assert!(pos_c1 < pos_a1);
1283    }
1284
1285    #[test]
1286    fn test_topological_sort_cycle_detection() {
1287        // A1 = B1, B1 = A1
1288        let formula_cells = vec![coord("Sheet1", 1, 1), coord("Sheet1", 2, 1)];
1289        let mut deps = HashMap::new();
1290        deps.insert(coord("Sheet1", 1, 1), vec![coord("Sheet1", 2, 1)]);
1291        deps.insert(coord("Sheet1", 2, 1), vec![coord("Sheet1", 1, 1)]);
1292
1293        let result = topological_sort(&formula_cells, &deps);
1294        assert!(result.is_err());
1295        let err_str = result.unwrap_err().to_string();
1296        assert!(
1297            err_str.contains("circular reference"),
1298            "expected circular reference error, got: {err_str}"
1299        );
1300    }
1301
1302    #[test]
1303    fn test_topological_sort_no_formulas() {
1304        let formula_cells: Vec<CellCoord> = vec![];
1305        let deps: HashMap<CellCoord, Vec<CellCoord>> = HashMap::new();
1306        let sorted = topological_sort(&formula_cells, &deps).unwrap();
1307        assert!(sorted.is_empty());
1308    }
1309
1310    #[test]
1311    fn test_set_current_sheet() {
1312        let mut snap = CellSnapshot::new("Sheet1".to_string());
1313        assert_eq!(snap.current_sheet(), "Sheet1");
1314        snap.set_current_sheet("Sheet2");
1315        assert_eq!(snap.current_sheet(), "Sheet2");
1316    }
1317}
sheetkit_core/formula/eval.rs

sheetkit_core/formula/
eval.rs
