Merge branch 'main' into fix/sec-mode-frequency-linear

MODE/MODE.SNGL/MODE.MULT searched the list of distinct numbers seen so far
for every input, and FREQUENCY scanned the sorted bins for every data value,
so both were quadratic in computed arrays. MODE now keys counts by value
(-0 folded into 0, NaN never merged) and keeps first-occurrence order;
FREQUENCY finds the first bin at or above each value with partition_point
over the order it already sorts. Results are unchanged.

crates/calc/src/eval/array.rs

@@ -86,30 +86,6 @@ pub fn zip2(a: &Value, b: &Value, f: impl Fn(&Value, &Value) -> Value) -> Value
     }
 }
 
-/// [`zip2`] that stops at the first cell `f` refuses (`None`), before the rest is built: the
-/// result grows as cells are made rather than being reserved for the whole broadcast up front.
-fn try_zip2(a: &Value, b: &Value, mut f: impl FnMut(&Value, &Value) -> Option<Value>) -> Option<Value> {
-    Some(match (a, b) {
-        (Value::Array(x), Value::Array(y)) => {
-            let rows = broadcast_dim(x.rows, y.rows);
-            let cols = broadcast_dim(x.cols, y.cols);
-            if broadcast_len(rows, cols).is_none() {
-                return Some(Value::Error(CellError::Num));
-            }
-            let mut data = Vec::new();
-            for r in 0..rows {
-                for c in 0..cols {
-                    data.push(f(&x.get_broadcast(r, c), &y.get_broadcast(r, c))?);
-                }
-            }
-            Value::from(Array { rows, cols, data })
-        }
-        (Value::Array(x), s) => Value::from(Array { rows: x.rows, cols: x.cols, data: x.data.iter().map(|v| f(v, s)).collect::<Option<_>>()? }),
-        (s, Value::Array(y)) => Value::from(Array { rows: y.rows, cols: y.cols, data: y.data.iter().map(|v| f(s, v)).collect::<Option<_>>()? }),
-        (x, y) => f(x, y)?,
-    })
-}
-
 /// Cell count of a `rows`×`cols` broadcast result, or `None` when it would exceed [`MAX_CELLS`].
 /// Each operand passes its own size cap, but their broadcast product can be far larger
 /// (`SEQUENCE(1048576)*SEQUENCE(1,16384)` is 17 billion cells), so it is checked before allocating.
@@ -159,36 +135,10 @@ pub(super) fn single(v: Value) -> Option<Value> {
     }
 }
 
-/// Text bytes that one `&` over arrays may produce in all. Each piece is capped on its own, but a
-/// compact formula can broadcast a long text across millions of cells
-/// (`SEQUENCE(4000,4000)&REPT("x",30000)` is 480 GB): past this the whole result is `#NUM!`, the
-/// error for a result too large to hold, before the rest is built.
-pub(super) const MAX_CONCAT_ARRAY_BYTES: usize = 512 * 1024 * 1024;
-
 pub fn binary_values(op: BinOp, x: &Value, y: &Value, sys: gridcraft_core::DateSystem) -> Value {
-    if op == BinOp::Concat && (matches!(x, Value::Array(_)) || matches!(y, Value::Array(_))) {
-        return concat_arrays(x, y, sys, MAX_CONCAT_ARRAY_BYTES);
-    }
     zip2(x, y, |a, b| binary_scalar(op, a, b, sys))
 }
 
-/// `x & y` with at least one array operand, giving `#NUM!` once the texts built so far pass `budget`
-/// bytes.
-fn concat_arrays(x: &Value, y: &Value, sys: gridcraft_core::DateSystem, budget: usize) -> Value {
-    let mut used = 0usize;
-    try_zip2(x, y, |a, b| {
-        let v = binary_scalar(BinOp::Concat, a, b, sys);
-        if let Value::Text(t) = &v {
-            used = used.saturating_add(t.len());
-            if used > budget {
-                return None;
-            }
-        }
-        Some(v)
-    })
-    .unwrap_or(Value::Error(CellError::Num))
-}
-
 fn binary_scalar(op: BinOp, a: &Value, b: &Value, sys: gridcraft_core::DateSystem) -> Value {
     if let Value::Error(e) = a {
         return Value::Error(*e);
@@ -237,35 +187,7 @@ fn binary_scalar(op: BinOp, a: &Value, b: &Value, sys: gridcraft_core::DateSyste
 
 #[cfg(test)]
 mod tests {
-    use super::{Array, BinOp, CellError, MAX_CELLS, Value, broadcast_len, concat_arrays, try_zip2};
+    use super::{MAX_CELLS, broadcast_len};
-
-    /// The broadcast stops at the first refused cell: nothing after it is visited.
-    #[test]
-    fn a_refused_cell_stops_the_broadcast() {
-        let col = Value::from(Array::column((0..4_000).map(|i| Value::number(i as f64)).collect()));
-        let row = Value::from(Array { rows: 1, cols: 4_000, data: (0..4_000).map(|i| Value::number(i as f64)).collect() });
-        let mut calls = 0;
-        let r = try_zip2(&col, &row, |a, _| {
-            calls += 1;
-            (calls <= 10).then(|| a.clone())
-        });
-        assert_eq!((r, calls), (None, 11));
-    }
-
-    #[test]
-    fn concatenating_arrays_stops_at_the_byte_budget() {
-        let sys = gridcraft_core::DateSystem::default();
-        let col = Value::from(Array::column((0..100).map(|i| Value::number(i as f64)).collect()));
-        let long = Value::text("x".repeat(100));
-        // 100 cells of 101 or 102 bytes each: about 10 KB in all.
-        let r = concat_arrays(&col, &long, sys, 20_000);
-        assert!(matches!(&r, Value::Array(a) if a.data.len() == 100), "{r:?}");
-        assert_eq!(concat_arrays(&col, &long, sys, 5_000), Value::Error(CellError::Num));
-        assert_eq!(concat_arrays(&long, &col, sys, 5_000), Value::Error(CellError::Num));
-        // Through the operator, a small result is unaffected.
-        let r = super::binary_values(BinOp::Concat, &col, &Value::text("a"), sys);
-        assert!(matches!(&r, Value::Array(a) if a.data.first() == Some(&Value::text("0a"))), "{r:?}");
-    }
 
     #[test]
     fn broadcast_len_caps_at_max_cells() {

crates/functions/src/stat/descriptive.rs

@@ -50,12 +50,27 @@ pub(super) fn median(v: Vec<f64>) -> R<f64> {
 
 /// Values occurring at least twice, ordered by first occurrence, with their (equal, maximal) count.
 fn modes(v: &[f64]) -> Vec<f64> {
+    // Index of each distinct number in `counts`, so counting is linear rather than a search of
+    // every distinct number so far. Keyed by bits with -0 folded into 0 (they compare equal); NaN
+    // never equals anything, so it is never merged.
+    let mut index: std::collections::HashMap<u64, usize> = std::collections::HashMap::new();
     let mut counts: Vec<(f64, usize)> = Vec::new();
     for &x in v {
-        if let Some(e) = counts.iter_mut().find(|e| e.0 == x) {
+        if x.is_nan() {
-            e.1 += 1;
-        } else {
             counts.push((x, 1));
+            continue;
+        }
+        let key = if x == 0.0 { 0 } else { x.to_bits() };
+        match index.entry(key) {
+            std::collections::hash_map::Entry::Occupied(e) => {
+                if let Some(c) = counts.get_mut(*e.get()) {
+                    c.1 += 1;
+                }
+            }
+            std::collections::hash_map::Entry::Vacant(e) => {
+                e.insert(counts.len());
+                counts.push((x, 1));
+            }
         }
     }
     let best = counts.iter().map(|e| e.1).max().unwrap_or(0);
@@ -451,11 +466,15 @@ pub(super) fn frequency(a: &[Arg], _: C) -> R<Value> {
     if bins.is_empty() {
         return col_value(vec![data.len() as f64]);
     }
-    let mut order: Vec<usize> = (0..bins.len()).collect();
+    // a NaN bin equals no value (and would break the ascending order searched below)
+    let mut order: Vec<usize> = (0..bins.len()).filter(|&i| bins.get(i).is_some_and(|b| !b.is_nan())).collect();
     order.sort_by(|&i, &j| bins.get(i).copied().unwrap_or(0.0).total_cmp(&bins.get(j).copied().unwrap_or(0.0)));
     let mut counts = vec![0.0; bins.len() + 1];
     for x in data {
-        let slot = order.iter().find(|&&i| x <= bins.get(i).copied().unwrap_or(f64::INFINITY)).copied().unwrap_or(bins.len());
+        // `order` sorts the bins ascending, so the bins `x` exceeds come first: binary search for
+        // the first bin at or above `x` (the first of equal bins, as a linear scan would find).
+        let pos = if x.is_nan() { order.len() } else { order.partition_point(|&i| bins.get(i).copied().unwrap_or(f64::INFINITY) < x) };
+        let slot = order.get(pos).copied().unwrap_or(bins.len());
         if let Some(c) = counts.get_mut(slot) {
             *c += 1.0;
         }

crates/functions/src/stat/tests.rs

@@ -617,3 +617,23 @@ fn aggregate_helper() {
     close(aggregate_values_k(9, &vals, &nv(2.0)), 9.0);
     is_err(aggregate_values_k(14, &vals, &nv(10.0)), CellError::Num);
 }
+
+/// Security: FREQUENCY finds each value's bin by binary search, and MODE counts distinct numbers
+/// through an index, so neither is quadratic in its inputs. Results are as before: unsorted and
+/// duplicate bins keep their positions (a value goes to the first of equal bins), and tied modes
+/// come in first-occurrence order.
+#[test]
+fn frequency_and_mode_scale_with_their_inputs() {
+    let f = ev("FREQUENCY", vec![c(&[1.0, 2.0, 2.0, 3.0, 5.0, 9.0, -1.0]), c(&[3.0, 2.0, 2.0, 0.0])]);
+    assert_eq!(rows_of(&f), vec![vec![nv(1.0)], vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
+    // NaN data goes to the overflow bin, and a NaN bin takes nothing
+    let f = ev("FREQUENCY", vec![c(&[f64::NAN, 0.5, 2.0]), c(&[f64::NAN, 1.0])]);
+    assert_eq!(rows_of(&f), vec![vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
+    let data: Vec<f64> = (0..200_000).map(|i| f64::from(i) + 1e6).collect();
+    let bins: Vec<f64> = (0..200_000).map(f64::from).collect();
+    let f = ev("FREQUENCY", vec![c(&data), c(&bins)]);
+    assert_eq!(rows_of(&f).last(), Some(&vec![nv(200_000.0)]));
+    let distinct = ev("MODE", vec![c(&data)]);
+    is_err(distinct, CellError::NA);
+    assert_eq!(rows_of(&ev("MODE.MULT", vec![c(&[3.0, 0.0, 1.0, -0.0, 3.0, 1.0])])), vec![vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)]]);
+}