Skip to main content

sheetkit_core/formula/
ast.rs

1//! AST types for parsed Excel formulas.
2
3/// A parsed Excel formula expression.
4#[derive(Debug, Clone, PartialEq)]
5pub enum Expr {
6    /// Numeric literal (e.g., 42, 3.14)
7    Number(f64),
8    /// String literal (e.g., "hello")
9    String(String),
10    /// Boolean literal (TRUE/FALSE)
11    Bool(bool),
12    /// Error literal (#N/A, #VALUE!, #REF!, #DIV/0!, #NUM!, #NAME?, #NULL!)
13    Error(String),
14    /// Omitted function argument (e.g., the second argument in `IF(A1,,1)`)
15    Missing,
16    /// Cell reference (e.g., A1, $B$2)
17    CellRef(CellReference),
18    /// Range reference (e.g., A1:B10)
19    Range {
20        start: CellReference,
21        end: CellReference,
22    },
23    /// Function call (e.g., SUM(A1:A10))
24    Function { name: String, args: Vec<Expr> },
25    /// Binary operation (e.g., A1 + B1)
26    BinaryOp {
27        op: BinaryOperator,
28        left: Box<Expr>,
29        right: Box<Expr>,
30    },
31    /// Unary operation (e.g., -A1, +5)
32    UnaryOp {
33        op: UnaryOperator,
34        operand: Box<Expr>,
35    },
36    /// Parenthesized expression
37    Paren(Box<Expr>),
38}
39
40impl Expr {
41    /// Return `(nodes, recursive nesting, binary-chain depth)` iteratively.
42    ///
43    /// Binary branches are tracked independently because the parser builds
44    /// them iteratively; function, unary, and parenthesized nodes consume the
45    /// recursive-parser nesting budget.
46    pub(crate) fn structural_metrics(&self) -> (u64, u64, u64) {
47        let mut nodes = 0_u64;
48        let mut max_depth = 0_u64;
49        let mut max_binary_chain = 0_u64;
50        let mut stack = MetricStack::new(self);
51        stack.push((self, 1_u64, 0_u64));
52
53        while let Some((expr, depth, parent_binary_chain)) = stack.pop() {
54            nodes = nodes.saturating_add(1);
55            max_depth = max_depth.max(depth);
56            match expr {
57                Self::Function { args, .. } => {
58                    for arg in args.iter().rev() {
59                        stack.push((arg, depth.saturating_add(1), 0));
60                    }
61                }
62                Self::BinaryOp { left, right, .. } => {
63                    let chain = parent_binary_chain.saturating_add(1);
64                    max_binary_chain = max_binary_chain.max(chain);
65                    stack.push((right, depth, 0));
66                    stack.push((left, depth, chain));
67                }
68                Self::UnaryOp { operand, .. } | Self::Paren(operand) => {
69                    stack.push((operand, depth.saturating_add(1), 0));
70                }
71                _ => {}
72            }
73        }
74
75        (nodes, max_depth, max_binary_chain)
76    }
77}
78
79/// LIFO work stack for [`Expr::structural_metrics`] that keeps typical
80/// formulas off the heap and spills deeper traversals to a `Vec`.
81struct MetricStack<'a> {
82    inline: [(&'a Expr, u64, u64); MetricStack::INLINE],
83    len: usize,
84    spill: Vec<(&'a Expr, u64, u64)>,
85}
86
87impl<'a> MetricStack<'a> {
88    const INLINE: usize = 16;
89
90    fn new(filler: &'a Expr) -> Self {
91        Self {
92            inline: [(filler, 0, 0); Self::INLINE],
93            len: 0,
94            spill: Vec::new(),
95        }
96    }
97
98    fn push(&mut self, entry: (&'a Expr, u64, u64)) {
99        if self.spill.is_empty() && self.len < Self::INLINE {
100            self.inline[self.len] = entry;
101            self.len += 1;
102        } else {
103            self.spill.push(entry);
104        }
105    }
106
107    fn pop(&mut self) -> Option<(&'a Expr, u64, u64)> {
108        if let Some(entry) = self.spill.pop() {
109            return Some(entry);
110        }
111        if self.len == 0 {
112            return None;
113        }
114        self.len -= 1;
115        Some(self.inline[self.len])
116    }
117}
118
119/// A cell reference with optional absolute markers.
120#[derive(Debug, Clone, PartialEq)]
121pub struct CellReference {
122    /// Column name (e.g., "A", "AB")
123    pub col: String,
124    /// Row number (1-based)
125    pub row: u32,
126    /// True if column is absolute ($A)
127    pub abs_col: bool,
128    /// True if row is absolute ($1)
129    pub abs_row: bool,
130    /// Optional sheet name (e.g., Sheet1!A1)
131    pub sheet: Option<String>,
132}
133
134/// Binary operators.
135#[derive(Debug, Clone, Copy, PartialEq, Eq)]
136pub enum BinaryOperator {
137    /// Addition (+)
138    Add,
139    /// Subtraction (-)
140    Sub,
141    /// Multiplication (*)
142    Mul,
143    /// Division (/)
144    Div,
145    /// Exponentiation (^)
146    Pow,
147    /// Concatenation (&)
148    Concat,
149    /// Equal (=)
150    Eq,
151    /// Not equal (<>)
152    Ne,
153    /// Less than (<)
154    Lt,
155    /// Less than or equal (<=)
156    Le,
157    /// Greater than (>)
158    Gt,
159    /// Greater than or equal (>=)
160    Ge,
161}
162
163/// Unary operators.
164#[derive(Debug, Clone, Copy, PartialEq, Eq)]
165pub enum UnaryOperator {
166    /// Negation (-)
167    Neg,
168    /// Positive (+)
169    Pos,
170    /// Percent (%)
171    Percent,
172}