ravenrs_sheet/formula/
ast.rs

1//! Formula syntax tree.
2
3use std::sync::Arc;
4
5use crate::base::{CellError, CellRef, MAX_COLS, MAX_ROWS, RangeRef};
6use serde::{Deserialize, Serialize};
7
8/// One end of a reference, with `$` anchors.
9#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
10pub struct Anchor {
11    pub row: u32,
12    pub col: u32,
13    pub row_abs: bool,
14    pub col_abs: bool,
15}
16
17impl Anchor {
18    pub fn cell(&self) -> CellRef {
19        CellRef::new(self.row, self.col)
20    }
21}
22
23#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
24pub enum RefKind {
25    Cell(Anchor),
26    Range(Anchor, Anchor),
27    /// Whole rows `3:5` (row, abs) pairs.
28    Rows(u32, bool, u32, bool),
29    /// Whole columns `A:C`.
30    Cols(u32, bool, u32, bool),
31}
32
33#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
34pub enum SheetSel {
35    /// Unqualified: the formula's own sheet.
36    Current,
37    Named(String),
38    /// 3-D span `Sheet1:Sheet3`.
39    Span(String, String),
40}
41
42#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
43pub struct Reference {
44    pub sheet: SheetSel,
45    pub kind: RefKind,
46}
47
48impl Reference {
49    pub fn range(&self) -> RangeRef {
50        match &self.kind {
51            RefKind::Cell(a) => RangeRef::cell(a.cell()),
52            RefKind::Range(a, b) => RangeRef::new(a.cell(), b.cell()),
53            RefKind::Rows(r0, _, r1, _) => RangeRef::rows((*r0).min(*r1), (*r0).max(*r1)),
54            RefKind::Cols(c0, _, c1, _) => RangeRef::cols((*c0).min(*c1), (*c0).max(*c1)),
55        }
56    }
57    pub fn sheet_name(&self) -> Option<&str> {
58        match &self.sheet {
59            SheetSel::Named(s) => Some(s),
60            _ => None,
61        }
62    }
63}
64
65/// Structured reference `Table1[[#Headers],[Col1]:[Col3]]`, `[@Col]`.
66#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
67pub struct StructRef {
68    /// Empty for `[@Col]` inside the table itself.
69    pub table: String,
70    pub specifiers: Vec<StructItem>,
71    pub col_start: Option<String>,
72    pub col_end: Option<String>,
73}
74
75#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
76pub enum StructItem {
77    All,
78    Data,
79    Headers,
80    Totals,
81    ThisRow,
82}
83
84#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
85pub enum UnOp {
86    Neg,
87    Plus,
88    Percent,
89    /// Implicit intersection `@`.
90    At,
91    /// Spill range operator `A1#`: the whole spill range of the dynamic array anchored at the
92    /// cell (`ANCHORARRAY` in files).
93    Spill,
94    /// Trim reference `A1.:E10` / `A1:.E10` / `A1.:.E10` around a range: the range without its
95    /// blank leading, trailing or outer rows and columns (`TRIMRANGE` with both trim codes set).
96    Trim(TrimMode),
97}
98
99/// Which blank edges a trim reference drops.
100#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
101pub enum TrimMode {
102    /// `.:` — leading blank rows and columns.
103    Leading,
104    /// `:.` — trailing blank rows and columns.
105    Trailing,
106    /// `.:.` — both.
107    All,
108}
109
110impl TrimMode {
111    pub fn symbol(self) -> &'static str {
112        match self {
113            TrimMode::Leading => ".:",
114            TrimMode::Trailing => ":.",
115            TrimMode::All => ".:.",
116        }
117    }
118    /// The equivalent `TRIMRANGE` trim_rows / trim_cols code.
119    pub fn code(self) -> u8 {
120        match self {
121            TrimMode::Leading => 1,
122            TrimMode::Trailing => 2,
123            TrimMode::All => 3,
124        }
125    }
126}
127
128#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
129pub enum BinOp {
130    Add,
131    Sub,
132    Mul,
133    Div,
134    Pow,
135    Concat,
136    Eq,
137    Ne,
138    Lt,
139    Gt,
140    Le,
141    Ge,
142    /// `:` between two references.
143    Range,
144    /// `,` inside parentheses.
145    Union,
146    /// space between two references.
147    Intersect,
148}
149
150impl BinOp {
151    pub fn symbol(&self) -> &'static str {
152        match self {
153            BinOp::Add => "+",
154            BinOp::Sub => "-",
155            BinOp::Mul => "*",
156            BinOp::Div => "/",
157            BinOp::Pow => "^",
158            BinOp::Concat => "&",
159            BinOp::Eq => "=",
160            BinOp::Ne => "<>",
161            BinOp::Lt => "<",
162            BinOp::Gt => ">",
163            BinOp::Le => "<=",
164            BinOp::Ge => ">=",
165            BinOp::Range => ":",
166            BinOp::Union => ",",
167            BinOp::Intersect => " ",
168        }
169    }
170    /// Binding power (higher binds tighter).
171    pub fn precedence(&self) -> u8 {
172        match self {
173            BinOp::Range => 90,
174            BinOp::Intersect => 85,
175            BinOp::Union => 80,
176            BinOp::Pow => 50,
177            BinOp::Mul | BinOp::Div => 40,
178            BinOp::Add | BinOp::Sub => 30,
179            BinOp::Concat => 20,
180            BinOp::Eq | BinOp::Ne | BinOp::Lt | BinOp::Gt | BinOp::Le | BinOp::Ge => 10,
181        }
182    }
183}
184
185/// A formula's syntax tree.
186///
187/// A flat operator chain such as `=A1+A2+…` nests one [`Expr::Binary`] per operator on its
188/// left, so a formula as long as Excel allows (8,192 characters) is about 4,000 levels deep.
189/// `Clone`, `PartialEq`, [`Expr::walk`] and [`Expr::map`] therefore follow that left spine in a
190/// loop and recurse only into right-hand operands and real nesting, which the parser bounds.
191#[derive(Debug, Serialize, Deserialize)]
192pub enum Expr {
193    Number(f64),
194    Text(Arc<str>),
195    Bool(bool),
196    Error(CellError),
197    /// Array constant `{1,2;3,4}` (rows of literal expressions).
198    Array(Vec<Vec<Expr>>),
199    Ref(Reference),
200    /// Defined name, table name or LET/LAMBDA parameter.
201    Name(String),
202    Struct(StructRef),
203    Unary(UnOp, Box<Expr>),
204    Binary(BinOp, Box<Expr>, Box<Expr>),
205    /// Function call; the name is upper-case without `_xlfn.`.
206    Call(String, Vec<Expr>),
207    /// Calling the result of an expression, e.g. `LAMBDA(x,x+1)(2)`.
208    Invoke(Box<Expr>, Vec<Expr>),
209    /// An omitted argument `F(1,,3)`.
210    Missing,
211    Paren(Box<Expr>),
212}
213
214impl Expr {
215    /// Visits every node depth-first, parents before children, left to right.
216    pub fn walk<'a>(&'a self, f: &mut dyn FnMut(&'a Expr)) {
217        // An explicit stack: a long operator chain must not recurse once per operand.
218        let mut pending = vec![self];
219        while let Some(e) = pending.pop() {
220            f(e);
221            match e {
222                Expr::Array(rows) => pending.extend(rows.iter().flatten().rev()),
223                Expr::Unary(_, e) | Expr::Paren(e) => pending.push(e),
224                Expr::Binary(_, a, b) => {
225                    pending.push(b);
226                    pending.push(a);
227                }
228                Expr::Call(_, args) => pending.extend(args.iter().rev()),
229                Expr::Invoke(c, args) => {
230                    pending.extend(args.iter().rev());
231                    pending.push(c);
232                }
233                _ => {}
234            }
235        }
236    }
237    /// Rewrites every node bottom-up, children left to right before their parent.
238    pub fn map(self, f: &mut dyn FnMut(Expr) -> Expr) -> Expr {
239        // Unwind the left spine of a long operator chain into a list, then rebuild it from the
240        // innermost operand outwards, in the order a recursive rewrite would visit the nodes.
241        let mut spine = Vec::new();
242        let mut node = self;
243        while let Expr::Binary(op, a, b) = node {
244            spine.push((op, b));
245            node = *a;
246        }
247        let e = match node {
248            Expr::Array(rows) => Expr::Array(rows.into_iter().map(|r| r.into_iter().map(|e| e.map(f)).collect()).collect()),
249            Expr::Unary(op, e) => Expr::Unary(op, Box::new(e.map(f))),
250            Expr::Paren(e) => Expr::Paren(Box::new(e.map(f))),
251            Expr::Call(n, args) => Expr::Call(n, args.into_iter().map(|e| e.map(f)).collect()),
252            Expr::Invoke(c, args) => Expr::Invoke(Box::new(c.map(f)), args.into_iter().map(|e| e.map(f)).collect()),
253            other => other,
254        };
255        let mut acc = f(e);
256        while let Some((op, b)) = spine.pop() {
257            let b = b.map(f);
258            acc = f(Expr::Binary(op, Box::new(acc), Box::new(b)));
259        }
260        acc
261    }
262    /// All references in the formula.
263    pub fn references(&self) -> Vec<&Reference> {
264        let mut v = Vec::new();
265        self.walk(&mut |e| {
266            if let Expr::Ref(r) = e {
267                v.push(r);
268            }
269        });
270        v
271    }
272    /// Function names used (upper-case).
273    pub fn functions(&self) -> Vec<&str> {
274        let mut v = Vec::new();
275        self.walk(&mut |e| {
276            if let Expr::Call(n, _) = e {
277                v.push(n.as_str());
278            }
279        });
280        v
281    }
282}
283
284impl Clone for Expr {
285    fn clone(&self) -> Self {
286        // Copy the left spine of an operator chain in a loop (see [`Expr`]).
287        let mut spine = Vec::new();
288        let mut node = self;
289        while let Expr::Binary(op, a, b) = node {
290            spine.push((*op, b));
291            node = a;
292        }
293        let mut acc = match node {
294            Expr::Number(n) => Expr::Number(*n),
295            Expr::Text(t) => Expr::Text(t.clone()),
296            Expr::Bool(b) => Expr::Bool(*b),
297            Expr::Error(e) => Expr::Error(*e),
298            Expr::Array(rows) => Expr::Array(rows.clone()),
299            Expr::Ref(r) => Expr::Ref(r.clone()),
300            Expr::Name(n) => Expr::Name(n.clone()),
301            Expr::Struct(s) => Expr::Struct(s.clone()),
302            Expr::Unary(op, e) => Expr::Unary(*op, e.clone()),
303            Expr::Binary(op, a, b) => Expr::Binary(*op, a.clone(), b.clone()),
304            Expr::Call(n, args) => Expr::Call(n.clone(), args.clone()),
305            Expr::Invoke(c, args) => Expr::Invoke(c.clone(), args.clone()),
306            Expr::Missing => Expr::Missing,
307            Expr::Paren(e) => Expr::Paren(e.clone()),
308        };
309        while let Some((op, b)) = spine.pop() {
310            acc = Expr::Binary(op, Box::new(acc), b.clone());
311        }
312        acc
313    }
314}
315
316impl PartialEq for Expr {
317    fn eq(&self, other: &Self) -> bool {
318        // Compare the left spines of operator chains in a loop (see [`Expr`]). The right-hand
319        // operands are compared only once the whole spine matches, so a mismatch on the left
320        // returns before any (possibly deep) right operand is walked.
321        let (mut x, mut y) = (self, other);
322        let mut right_operands = Vec::new();
323        let equal = loop {
324            match (x, y) {
325                (Expr::Binary(o1, a1, b1), Expr::Binary(o2, a2, b2)) => {
326                    if o1 != o2 {
327                        return false;
328                    }
329                    right_operands.push((b1, b2));
330                    x = a1;
331                    y = a2;
332                }
333                (Expr::Number(a), Expr::Number(b)) => break a == b,
334                (Expr::Text(a), Expr::Text(b)) => break a == b,
335                (Expr::Bool(a), Expr::Bool(b)) => break a == b,
336                (Expr::Error(a), Expr::Error(b)) => break a == b,
337                (Expr::Array(a), Expr::Array(b)) => break a == b,
338                (Expr::Ref(a), Expr::Ref(b)) => break a == b,
339                (Expr::Name(a), Expr::Name(b)) => break a == b,
340                (Expr::Struct(a), Expr::Struct(b)) => break a == b,
341                (Expr::Unary(o1, a), Expr::Unary(o2, b)) => break o1 == o2 && a == b,
342                (Expr::Call(n1, a), Expr::Call(n2, b)) => break n1 == n2 && a == b,
343                (Expr::Invoke(c1, a), Expr::Invoke(c2, b)) => break c1 == c2 && a == b,
344                (Expr::Missing, Expr::Missing) => break true,
345                (Expr::Paren(a), Expr::Paren(b)) => break a == b,
346                _ => break false,
347            }
348        };
349        equal && right_operands.into_iter().rev().all(|(b1, b2)| b1 == b2)
350    }
351}
352
353pub(crate) fn clamp_anchor(row: i64, col: i64) -> Option<(u32, u32)> {
354    if (0..MAX_ROWS as i64).contains(&row) && (0..MAX_COLS as i64).contains(&col) { Some((row as u32, col as u32)) } else { None }
355}
ravenrs_sheet/formula/ast.rs

ravenrs_sheet/formula/
ast.rs
