ravenrs_sheet/calc/eval/
array.rs

1use super::{Array, BinOp, CellError, MAX_CELLS, Value, compare};
2
3/// The aggregates that can fold a reference without building an array.
4#[derive(Clone, Copy, PartialEq, Eq)]
5pub(super) enum Agg {
6    Sum,
7    Count,
8    Average,
9}
10
11impl Agg {
12    pub(super) fn of(name: &str) -> Option<Agg> {
13        match name {
14            "SUM" => Some(Agg::Sum),
15            "COUNT" => Some(Agg::Count),
16            "AVERAGE" => Some(Agg::Average),
17            _ => None,
18        }
19    }
20}
21
22/// What a folded aggregate carries from one value to the next.
23#[derive(Default)]
24pub(super) struct Acc {
25    pub(super) sum: f64,
26    pub(super) count: u64,
27}
28
29impl Acc {
30    /// Takes a value found inside a reference: only numbers count. `Err` is an error value that
31    /// ends `SUM` and `AVERAGE`; `COUNT` skips errors.
32    pub(super) fn add_cell(&mut self, kind: Agg, v: &Value) -> Result<(), CellError> {
33        match v {
34            Value::Number(n) => {
35                self.sum += n;
36                self.count = self.count.saturating_add(1);
37                Ok(())
38            }
39            Value::Error(e) if kind != Agg::Count => Err(*e),
40            _ => Ok(()),
41        }
42    }
43
44    pub(super) fn finish(&self, kind: Agg) -> Value {
45        match kind {
46            Agg::Sum => Value::number(self.sum),
47            Agg::Count => Value::number(self.count as f64),
48            Agg::Average if self.count == 0 => Value::Error(CellError::Div0),
49            Agg::Average => Value::number(self.sum / self.count as f64),
50        }
51    }
52}
53
54// ---------------------------------------------------------------- operators
55
56pub(super) fn map_unary(v: &Value, f: &dyn Fn(f64) -> Value, plus: bool, sys: crate::base::DateSystem) -> Value {
57    match v {
58        Value::Array(a) => Value::from(Array { rows: a.rows, cols: a.cols, data: a.data.iter().map(|x| map_unary(x, f, plus, sys)).collect() }),
59        Value::Error(e) => Value::Error(*e),
60        Value::Text(_) if plus => v.clone(),
61        other => match other.to_number_in(sys) {
62            Ok(n) => f(n),
63            Err(e) => Value::Error(e),
64        },
65    }
66}
67
68/// Element-wise combination with Excel's broadcasting.
69pub fn zip2(a: &Value, b: &Value, f: impl Fn(&Value, &Value) -> Value) -> Value {
70    match (a, b) {
71        (Value::Array(x), Value::Array(y)) => {
72            let rows = broadcast_dim(x.rows, y.rows);
73            let cols = broadcast_dim(x.cols, y.cols);
74            let Some(n) = broadcast_len(rows, cols) else { return Value::Error(CellError::Num) };
75            let mut data = Vec::with_capacity(n);
76            for r in 0..rows {
77                for c in 0..cols {
78                    data.push(f(&x.get_broadcast(r, c), &y.get_broadcast(r, c)));
79                }
80            }
81            Value::from(Array { rows, cols, data })
82        }
83        (Value::Array(x), s) => Value::from(Array { rows: x.rows, cols: x.cols, data: x.data.iter().map(|v| f(v, s)).collect() }),
84        (s, Value::Array(y)) => Value::from(Array { rows: y.rows, cols: y.cols, data: y.data.iter().map(|v| f(s, v)).collect() }),
85        (x, y) => f(x, y),
86    }
87}
88
89/// [`zip2`] that stops at the first cell `f` refuses (`None`), before the rest is built: the
90/// result grows as cells are made rather than being reserved for the whole broadcast up front.
91fn try_zip2(a: &Value, b: &Value, mut f: impl FnMut(&Value, &Value) -> Option<Value>) -> Option<Value> {
92    Some(match (a, b) {
93        (Value::Array(x), Value::Array(y)) => {
94            let rows = broadcast_dim(x.rows, y.rows);
95            let cols = broadcast_dim(x.cols, y.cols);
96            if broadcast_len(rows, cols).is_none() {
97                return Some(Value::Error(CellError::Num));
98            }
99            let mut data = Vec::new();
100            for r in 0..rows {
101                for c in 0..cols {
102                    data.push(f(&x.get_broadcast(r, c), &y.get_broadcast(r, c))?);
103                }
104            }
105            Value::from(Array { rows, cols, data })
106        }
107        (Value::Array(x), s) => Value::from(Array { rows: x.rows, cols: x.cols, data: x.data.iter().map(|v| f(v, s)).collect::<Option<_>>()? }),
108        (s, Value::Array(y)) => Value::from(Array { rows: y.rows, cols: y.cols, data: y.data.iter().map(|v| f(s, v)).collect::<Option<_>>()? }),
109        (x, y) => f(x, y)?,
110    })
111}
112
113/// Cell count of a `rows`×`cols` broadcast result, or `None` when it would exceed [`MAX_CELLS`].
114/// Each operand passes its own size cap, but their broadcast product can be far larger
115/// (`SEQUENCE(1048576)*SEQUENCE(1,16384)` is 17 billion cells), so it is checked before allocating.
116/// The product is formed in `u64`: on wasm32 `usize` is 32 bits, where a `usize` product above
117/// `u32::MAX` would wrap (2^32 cells → 0) and slip past the cap.
118pub(super) fn broadcast_len(rows: usize, cols: usize) -> Option<usize> {
119    let cells = u64::try_from(rows).ok()?.checked_mul(u64::try_from(cols).ok()?)?;
120    if cells > MAX_CELLS {
121        return None;
122    }
123    usize::try_from(cells).ok()
124}
125
126fn broadcast_dim(a: usize, b: usize) -> usize {
127    if a == 1 {
128        b
129    } else if b == 1 {
130        a
131    } else {
132        a.max(b)
133    }
134}
135
136pub(super) fn zip3(c: &Array, t: &Value, f: &Value, g: impl Fn(&Value, &Value, &Value) -> Value) -> Value {
137    let dims = |v: &Value| if let Value::Array(a) = v { (a.rows, a.cols) } else { (1, 1) };
138    let (tr, tc) = dims(t);
139    let (fr, fc) = dims(f);
140    let rows = broadcast_dim(broadcast_dim(c.rows, tr), fr);
141    let cols = broadcast_dim(broadcast_dim(c.cols, tc), fc);
142    let Some(n) = broadcast_len(rows, cols) else { return Value::Error(CellError::Num) };
143    let get = |v: &Value, r: usize, col: usize| if let Value::Array(a) = v { a.get_broadcast(r, col) } else { v.clone() };
144    let mut data = Vec::with_capacity(n);
145    for r in 0..rows {
146        for col in 0..cols {
147            data.push(g(&c.get_broadcast(r, col), &get(t, r, col), &get(f, r, col)));
148        }
149    }
150    Value::from(Array { rows, cols, data })
151}
152
153/// One cell of a LAMBDA helper's result, or `None` for an array of more than one value: arrays
154/// can't nest, so the whole helper gives `#CALC!`, as in Excel.
155pub(super) fn single(v: Value) -> Option<Value> {
156    match v {
157        Value::Array(a) if a.data.len() > 1 => None,
158        v => Some(v.scalar()),
159    }
160}
161
162/// Text bytes that one `&` over arrays may produce in all. Each piece is capped on its own, but a
163/// compact formula can broadcast a long text across millions of cells
164/// (`SEQUENCE(4000,4000)&REPT("x",30000)` is 480 GB): past this the whole result is `#NUM!`, the
165/// error for a result too large to hold, before the rest is built.
166pub(super) const MAX_CONCAT_ARRAY_BYTES: usize = 512 * 1024 * 1024;
167
168pub fn binary_values(op: BinOp, x: &Value, y: &Value, sys: crate::base::DateSystem) -> Value {
169    if op == BinOp::Concat && (matches!(x, Value::Array(_)) || matches!(y, Value::Array(_))) {
170        return concat_arrays(x, y, sys, MAX_CONCAT_ARRAY_BYTES);
171    }
172    zip2(x, y, |a, b| binary_scalar(op, a, b, sys))
173}
174
175/// `x & y` with at least one array operand, giving `#NUM!` once the texts built so far pass `budget`
176/// bytes.
177fn concat_arrays(x: &Value, y: &Value, sys: crate::base::DateSystem, budget: usize) -> Value {
178    let mut used = 0usize;
179    try_zip2(x, y, |a, b| {
180        let v = binary_scalar(BinOp::Concat, a, b, sys);
181        if let Value::Text(t) = &v {
182            used = used.saturating_add(t.len());
183            if used > budget {
184                return None;
185            }
186        }
187        Some(v)
188    })
189    .unwrap_or(Value::Error(CellError::Num))
190}
191
192fn binary_scalar(op: BinOp, a: &Value, b: &Value, sys: crate::base::DateSystem) -> Value {
193    if let Value::Error(e) = a {
194        return Value::Error(*e);
195    }
196    if let Value::Error(e) = b {
197        return Value::Error(*e);
198    }
199    let num = |f: fn(f64, f64) -> Value| match (a.to_number_in(sys), b.to_number_in(sys)) {
200        (Ok(x), Ok(y)) => f(x, y),
201        (Err(e), _) | (_, Err(e)) => Value::Error(e),
202    };
203    use std::cmp::Ordering::*;
204    match op {
205        BinOp::Add => num(|x, y| Value::number(x + y)),
206        BinOp::Sub => num(|x, y| Value::number(x - y)),
207        BinOp::Mul => num(|x, y| Value::number(x * y)),
208        BinOp::Div => num(|x, y| if y == 0.0 { Value::Error(CellError::Div0) } else { Value::number(x / y) }),
209        BinOp::Pow => num(|x, y| {
210            if x == 0.0 && y == 0.0 {
211                Value::Error(CellError::Num)
212            } else if x == 0.0 && y < 0.0 {
213                Value::Error(CellError::Div0)
214            } else {
215                Value::number(x.powf(y))
216            }
217        }),
218        BinOp::Concat => match (a.to_text(), b.to_text()) {
219            (Ok(x), Ok(y)) => {
220                if x.len() + y.len() > 32767 * 4 {
221                    Value::Error(CellError::Value)
222                } else {
223                    Value::text(x + &y)
224                }
225            }
226            (Err(e), _) | (_, Err(e)) => Value::Error(e),
227        },
228        BinOp::Eq => Value::Bool(compare(a, b) == Equal),
229        BinOp::Ne => Value::Bool(compare(a, b) != Equal),
230        BinOp::Lt => Value::Bool(compare(a, b) == Less),
231        BinOp::Gt => Value::Bool(compare(a, b) == Greater),
232        BinOp::Le => Value::Bool(compare(a, b) != Greater),
233        BinOp::Ge => Value::Bool(compare(a, b) != Less),
234        BinOp::Range | BinOp::Union | BinOp::Intersect => Value::Error(CellError::Value),
235    }
236}
237
238#[cfg(test)]
239mod tests {
240    use super::{Array, BinOp, CellError, MAX_CELLS, Value, broadcast_len, concat_arrays, try_zip2};
241
242    /// The broadcast stops at the first refused cell: nothing after it is visited.
243    #[test]
244    fn a_refused_cell_stops_the_broadcast() {
245        let col = Value::from(Array::column((0..4_000).map(|i| Value::number(i as f64)).collect()));
246        let row = Value::from(Array { rows: 1, cols: 4_000, data: (0..4_000).map(|i| Value::number(i as f64)).collect() });
247        let mut calls = 0;
248        let r = try_zip2(&col, &row, |a, _| {
249            calls += 1;
250            (calls <= 10).then(|| a.clone())
251        });
252        assert_eq!((r, calls), (None, 11));
253    }
254
255    #[test]
256    fn concatenating_arrays_stops_at_the_byte_budget() {
257        let sys = crate::base::DateSystem::default();
258        let col = Value::from(Array::column((0..100).map(|i| Value::number(i as f64)).collect()));
259        let long = Value::text("x".repeat(100));
260        // 100 cells of 101 or 102 bytes each: about 10 KB in all.
261        let r = concat_arrays(&col, &long, sys, 20_000);
262        assert!(matches!(&r, Value::Array(a) if a.data.len() == 100), "{r:?}");
263        assert_eq!(concat_arrays(&col, &long, sys, 5_000), Value::Error(CellError::Num));
264        assert_eq!(concat_arrays(&long, &col, sys, 5_000), Value::Error(CellError::Num));
265        // Through the operator, a small result is unaffected.
266        let r = super::binary_values(BinOp::Concat, &col, &Value::text("a"), sys);
267        assert!(matches!(&r, Value::Array(a) if a.data.first() == Some(&Value::text("0a"))), "{r:?}");
268    }
269
270    #[test]
271    fn broadcast_len_caps_at_max_cells() {
272        assert_eq!(broadcast_len(4_000, 4_000), Some(MAX_CELLS as usize));
273        assert_eq!(broadcast_len(4_000, 4_001), None);
274        assert_eq!(broadcast_len(1, MAX_CELLS as usize), Some(MAX_CELLS as usize));
275    }
276
277    /// `65_536 * 65_536` is 2^32. Multiplied as `usize` on wasm32 it wraps to 0, which a
278    /// `> MAX_CELLS` test would let through; the guard must reject the true product.
279    #[test]
280    fn broadcast_len_rejects_a_product_that_wraps_to_zero_on_32_bits() {
281        assert_eq!(65_536u32.wrapping_mul(65_536), 0);
282        assert_eq!(broadcast_len(65_536, 65_536), None);
283        assert_eq!(broadcast_len(1_048_576, 16_384), None);
284    }
285}
ravenrs_sheet/calc/eval/array.rs

ravenrs_sheet/calc/eval/
array.rs
