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/chart/src/render/cartesian.rs

@@ -96,11 +96,8 @@ fn series_spans(data: &ChartData, fams: &[Fam], sec: &[bool], ncat: usize) -> Ve
         } else {
             None
         };
-        // A series without values has no spans: 255 empty series over 20,000 categories would
-        // otherwise fill ~5 million entries.
-        let n = if s.values.is_empty() { 0 } else { ncat };
-        let mut row = Vec::with_capacity(n);
-        for j in 0..n {
+        let mut row = Vec::with_capacity(ncat);
+        for j in 0..ncat {
             let v = s.values.get(j).copied().flatten();
             let span = match (si.and_then(|p| stacks.get_mut(p)), fam) {
                 (Some((_, pos, neg)), Fam::ColStack | Fam::Col100) => v.and_then(|v| {
@@ -453,18 +450,3 @@ pub(super) fn scatter(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
     }
     draw_trend_labels(ctx, plot, &trend_labels);
 }
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-
-    #[test]
-    fn empty_series_get_no_span_entries() {
-        let empty = SeriesData::default();
-        let full = SeriesData { values: vec![Some(1.0); 3], ..SeriesData::default() };
-        let data = ChartData { series: vec![empty.clone(), full, empty], ..ChartData::default() };
-        let fams = [Fam::Col; 3];
-        let spans = series_spans(&data, &fams, &[false; 3], MAX_CATS);
-        assert_eq!(spans.iter().map(Vec::len).collect::<Vec<_>>(), [0, MAX_CATS, 0]);
-    }
-}

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) {
-            e.1 += 1;
-        } else {
+        if x.is_nan() {
             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)]]);
+}