ravenrs_sheet/engine/
pivot_calc.rs

1//! Calculated PivotTable fields: a formula over other fields (`=Sales*0.1`,
2//! `='Unit Price'*Units`, `=IF(Units>0,Sales/Units,0)`).
3//!
4//! As Microsoft documents for Excel, the formula operates on the *sums* of the fields it names
5//! for each report cell (items, subtotals and grand totals alike), not record by record: for
6//! `=Sales*1.2` a cell shows 1.2 × the sum of Sales of that cell's records. Fields are written
7//! bare (`Sales`) or in single quotes (`'Unit Price'`); cell references and defined names are not
8//! allowed. A calculated field may use other calculated fields; a cycle evaluates to `#REF!`.
9
10use crate::base::{CellError, CellRef, Value};
11use crate::formula::Expr;
12use crate::model::{PivotTable, Workbook};
13
14/// Longest formula accepted.
15pub const MAX_FORMULA_LEN: usize = 8_192;
16/// Most calculated fields per PivotTable.
17pub const MAX_CALC_FIELDS: usize = 256;
18/// Deepest chain of calculated fields using calculated fields.
19const MAX_DEPTH: usize = 64;
20const PREFIX: &str = "__pcf";
21
22fn placeholder(i: usize) -> String {
23    format!("{PREFIX}{i}")
24}
25
26/// A parsed formula: field names replaced by placeholder names `__pcf0`, `__pcf1`, … in the
27/// order of `refs`.
28#[derive(Clone, Debug)]
29pub struct Compiled {
30    pub body: Expr,
31    /// Canonical names of the fields used.
32    pub refs: Vec<String>,
33}
34
35/// Parses a calculated-field formula. `field` maps a written name to the canonical name of a
36/// source or calculated field.
37pub fn compile(formula: &str, field: &dyn Fn(&str) -> Option<String>) -> Result<Compiled, String> {
38    let text = formula.trim();
39    let text = text.strip_prefix('=').unwrap_or(text).trim();
40    if text.is_empty() {
41        return Err("The formula is empty.".into());
42    }
43    if text.len() > MAX_FORMULA_LEN {
44        return Err("The formula is too long.".into());
45    }
46    let chars: Vec<char> = text.chars().collect();
47    let at = |i: usize| chars.get(i).copied();
48    let mut out = String::with_capacity(text.len() + 16);
49    let mut refs: Vec<String> = Vec::new();
50    let slot = |name: String, refs: &mut Vec<String>| -> String {
51        let i = refs.iter().position(|r| r.eq_ignore_ascii_case(&name)).unwrap_or_else(|| {
52            refs.push(name);
53            refs.len() - 1
54        });
55        placeholder(i)
56    };
57    let mut i = 0;
58    while let Some(c) = at(i) {
59        match c {
60            '"' => {
61                out.push('"');
62                i += 1;
63                loop {
64                    match at(i) {
65                        None => return Err("The formula has an unterminated text value.".into()),
66                        Some('"') if at(i + 1) == Some('"') => {
67                            out.push_str("\"\"");
68                            i += 2;
69                        }
70                        Some('"') => {
71                            out.push('"');
72                            i += 1;
73                            break;
74                        }
75                        Some(x) => {
76                            out.push(x);
77                            i += 1;
78                        }
79                    }
80                }
81            }
82            '\'' => {
83                let mut name = String::new();
84                i += 1;
85                loop {
86                    match at(i) {
87                        None => return Err("The formula has an unterminated field name.".into()),
88                        Some('\'') if at(i + 1) == Some('\'') => {
89                            name.push('\'');
90                            i += 2;
91                        }
92                        Some('\'') => {
93                            i += 1;
94                            break;
95                        }
96                        Some(x) => {
97                            name.push(x);
98                            i += 1;
99                        }
100                    }
101                }
102                let canon = field(&name).ok_or_else(|| format!("There's no field named '{name}'."))?;
103                out.push_str(&slot(canon, &mut refs));
104            }
105            c if c.is_ascii_digit() || (c == '.' && at(i + 1).is_some_and(|d| d.is_ascii_digit())) => {
106                while at(i).is_some_and(|d| d.is_ascii_digit() || d == '.') {
107                    out.push(at(i).unwrap_or('0'));
108                    i += 1;
109                }
110                if matches!(at(i), Some('e' | 'E')) {
111                    let sign = usize::from(matches!(at(i + 1), Some('+' | '-')));
112                    if at(i + 1 + sign).is_some_and(|d| d.is_ascii_digit()) {
113                        for _ in 0..=sign {
114                            out.push(at(i).unwrap_or('0'));
115                            i += 1;
116                        }
117                        while at(i).is_some_and(|d| d.is_ascii_digit()) {
118                            out.push(at(i).unwrap_or('0'));
119                            i += 1;
120                        }
121                    }
122                }
123            }
124            c if c.is_alphabetic() || c == '_' => {
125                let start = i;
126                while at(i).is_some_and(|d| d.is_alphanumeric() || d == '_' || d == '.') {
127                    i += 1;
128                }
129                let word: String = chars.get(start..i).map(|w| w.iter().collect()).unwrap_or_default();
130                let mut j = i;
131                while at(j).is_some_and(char::is_whitespace) {
132                    j += 1;
133                }
134                let is_call = at(j) == Some('(');
135                match field(&word) {
136                    Some(canon) if !is_call => out.push_str(&slot(canon, &mut refs)),
137                    _ => out.push_str(&word),
138                }
139            }
140            c => {
141                out.push(c);
142                i += 1;
143            }
144        }
145    }
146    let body = crate::formula::parse(&out).map_err(|_| "The formula contains an error.".to_string())?;
147    let mut problem: Option<String> = None;
148    body.walk(&mut |e| {
149        if problem.is_some() {
150            return;
151        }
152        match e {
153            Expr::Name(n) if n.starts_with(PREFIX) => {}
154            Expr::Name(n) => problem = Some(format!("There's no field named '{n}'.")),
155            Expr::Ref(_) | Expr::Struct(_) => problem = Some("A calculated field can't refer to cells or tables; use field names.".into()),
156            _ => {}
157        }
158    });
159    match problem {
160        Some(p) => Err(p),
161        None => Ok(Compiled { body, refs }),
162    }
163}
164
165fn literal(v: &Value) -> Expr {
166    match v {
167        Value::Number(n) => Expr::Number(*n),
168        Value::Error(e) => Expr::Error(*e),
169        Value::Text(t) => Expr::Text(t.clone()),
170        Value::Bool(b) => Expr::Bool(*b),
171        Value::Empty => Expr::Number(0.0),
172        Value::Array(_) => literal(&v.scalar()),
173    }
174}
175
176/// Evaluates a compiled formula with the given field values (in `refs` order).
177pub fn eval(wb: &Workbook, c: &Compiled, args: &[Value]) -> Value {
178    let expr = if c.refs.is_empty() {
179        c.body.clone()
180    } else {
181        let mut call = Vec::with_capacity(c.refs.len() * 2 + 1);
182        for i in 0..c.refs.len() {
183            call.push(Expr::Name(placeholder(i)));
184            call.push(literal(args.get(i).unwrap_or(&Value::Empty)));
185        }
186        call.push(c.body.clone());
187        Expr::Call("LET".into(), call)
188    };
189    match crate::calc::recalc::evaluate_expr(wb, 0, CellRef::default(), &expr).scalar() {
190        Value::Empty => Value::Number(0.0),
191        v => v,
192    }
193}
194
195/// A PivotTable's calculated fields, compiled against its source headers.
196pub struct CalcSet {
197    names: Vec<String>,
198    compiled: Vec<Result<Compiled, String>>,
199}
200
201impl CalcSet {
202    pub fn new(pt: &PivotTable, headers: &[String]) -> CalcSet {
203        let names: Vec<String> = pt.calculated_fields.iter().take(MAX_CALC_FIELDS).map(|c| c.name.clone()).collect();
204        let lookup = |n: &str| -> Option<String> {
205            let n = n.trim();
206            headers.iter().chain(names.iter()).find(|h| h.trim().eq_ignore_ascii_case(n)).cloned()
207        };
208        let compiled = pt.calculated_fields.iter().take(MAX_CALC_FIELDS).map(|c| compile(&c.formula, &lookup)).collect();
209        CalcSet { names, compiled }
210    }
211
212    pub fn index(&self, name: &str) -> Option<usize> {
213        self.names.iter().position(|n| n.eq_ignore_ascii_case(name.trim()))
214    }
215
216    /// The compile error of a calculated field, if any.
217    pub fn error(&self, i: usize) -> Option<&str> {
218        self.compiled.get(i).and_then(|c| c.as_ref().err()).map(String::as_str)
219    }
220
221    /// Source fields a calculated field needs, directly or through other calculated fields.
222    pub fn source_refs(&self, i: usize) -> Vec<String> {
223        let mut out: Vec<String> = Vec::new();
224        let mut seen = vec![false; self.names.len()];
225        let mut stack = vec![i];
226        while let Some(j) = stack.pop() {
227            if !seen.get(j).copied().unwrap_or(true) {
228                if let Some(s) = seen.get_mut(j) {
229                    *s = true;
230                }
231                if let Some(Ok(c)) = self.compiled.get(j) {
232                    for r in &c.refs {
233                        match self.index(r) {
234                            Some(k) => stack.push(k),
235                            None => {
236                                if !out.iter().any(|o| o.eq_ignore_ascii_case(r)) {
237                                    out.push(r.clone());
238                                }
239                            }
240                        }
241                    }
242                }
243            }
244        }
245        out
246    }
247
248    /// Whether a calculated field reaches itself through the fields it uses.
249    pub fn is_cyclic(&self, i: usize) -> bool {
250        let mut seen = vec![false; self.names.len()];
251        let mut stack: Vec<usize> = match self.compiled.get(i) {
252            Some(Ok(c)) => c.refs.iter().filter_map(|r| self.index(r)).collect(),
253            _ => vec![],
254        };
255        while let Some(j) = stack.pop() {
256            if j == i {
257                return true;
258            }
259            if seen.get(j).copied().unwrap_or(true) {
260                continue;
261            }
262            if let Some(s) = seen.get_mut(j) {
263                *s = true;
264            }
265            if let Some(Ok(c)) = self.compiled.get(j) {
266                stack.extend(c.refs.iter().filter_map(|r| self.index(r)));
267            }
268        }
269        false
270    }
271
272    /// The value of calculated field `i` for one report cell; `sum` gives a source field's sum
273    /// over that cell's records.
274    pub fn value(&self, wb: &Workbook, i: usize, sum: &dyn Fn(&str) -> Value) -> Value {
275        let mut memo: Vec<Option<Value>> = vec![None; self.names.len()];
276        let mut active = vec![false; self.names.len()];
277        self.value_in(wb, i, sum, &mut memo, &mut active, 0)
278    }
279
280    fn value_in(&self, wb: &Workbook, i: usize, sum: &dyn Fn(&str) -> Value, memo: &mut [Option<Value>], active: &mut [bool], depth: usize) -> Value {
281        if let Some(Some(v)) = memo.get(i) {
282            return v.clone();
283        }
284        if depth > MAX_DEPTH || active.get(i).copied().unwrap_or(true) {
285            return Value::Error(CellError::Ref);
286        }
287        let Some(Ok(c)) = self.compiled.get(i) else { return Value::Error(CellError::Name) };
288        if let Some(a) = active.get_mut(i) {
289            *a = true;
290        }
291        let args: Vec<Value> = c
292            .refs
293            .iter()
294            .map(|r| match self.index(r) {
295                Some(j) => self.value_in(wb, j, sum, memo, active, depth + 1),
296                None => sum(r),
297            })
298            .collect();
299        let v = eval(wb, c, &args);
300        if let Some(a) = active.get_mut(i) {
301            *a = false;
302        }
303        if let Some(m) = memo.get_mut(i) {
304            *m = Some(v.clone());
305        }
306        v
307    }
308}
309
310#[cfg(test)]
311mod tests {
312    use super::*;
313
314    fn fields(n: &str) -> Option<String> {
315        ["Sales", "Units", "Unit Price", "Q1"].iter().find(|f| f.eq_ignore_ascii_case(n)).map(|f| f.to_string())
316    }
317
318    #[test]
319    fn compiles_field_names() {
320        let c = compile("= Sales*0.1 + 'Unit Price'/units - Sales", &fields).unwrap();
321        assert_eq!(c.refs, vec!["Sales", "Unit Price", "Units"]);
322        // A field named like a cell reference is still a field; functions stay functions.
323        let c = compile("=ROUND(Q1*1.5E2,0)", &fields).unwrap();
324        assert_eq!(c.refs, vec!["Q1"]);
325        let wb = Workbook::new();
326        assert_eq!(eval(&wb, &c, &[Value::Number(2.0)]), Value::Number(300.0));
327        assert!(compile("=Sales*Bogus", &fields).unwrap_err().contains("Bogus"));
328        assert!(compile("=A1*2", &fields).is_err());
329        assert!(compile("='Nope'*2", &fields).is_err());
330        assert!(compile("=Sales*(", &fields).is_err());
331        assert!(compile("=", &fields).is_err());
332        assert!(compile(&format!("={}", "1+".repeat(MAX_FORMULA_LEN)), &fields).is_err());
333    }
334
335    #[test]
336    fn deep_and_cyclic_chains_are_bounded() {
337        // 300 calculated fields, each using the previous one, and a two-field cycle.
338        let mut pt = PivotTable::default();
339        pt.calculated_fields.push(crate::model::PivotCalcField { name: "C0".into(), formula: "=Sales+1".into() });
340        for i in 1..300 {
341            pt.calculated_fields.push(crate::model::PivotCalcField { name: format!("C{i}"), formula: format!("=C{}+1", i - 1) });
342        }
343        pt.calculated_fields.push(crate::model::PivotCalcField { name: "P".into(), formula: "=Q".into() });
344        pt.calculated_fields.push(crate::model::PivotCalcField { name: "Q".into(), formula: "=P*2".into() });
345        let set = CalcSet::new(&pt, &["Sales".to_string()]);
346        let wb = Workbook::new();
347        let sum = |_: &str| Value::Number(10.0);
348        assert_eq!(set.value(&wb, 0, &sum), Value::Number(11.0));
349        assert_eq!(set.value(&wb, 10, &sum), Value::Number(21.0));
350        // Past the depth bound (the list itself is capped at MAX_CALC_FIELDS).
351        assert_eq!(set.value(&wb, 200, &sum), Value::Error(CellError::Ref));
352        assert_eq!(set.index("P"), None, "P is past the cap of {MAX_CALC_FIELDS} fields");
353        // A small cycle within the cap.
354        let mut small = PivotTable::default();
355        small.calculated_fields.push(crate::model::PivotCalcField { name: "P".into(), formula: "=Q".into() });
356        small.calculated_fields.push(crate::model::PivotCalcField { name: "Q".into(), formula: "=P*2".into() });
357        let set = CalcSet::new(&small, &["Sales".to_string()]);
358        assert!(set.is_cyclic(0));
359        assert_eq!(set.value(&wb, 0, &sum), Value::Error(CellError::Ref));
360        assert_eq!(set.source_refs(0), Vec::<String>::new());
361    }
362}
ravenrs_sheet/engine/pivot_calc.rs

ravenrs_sheet/engine/
pivot_calc.rs
