functions: TEXTJOIN builds its result piece by piece within the text cap

TEXTJOIN converted every input and delimiter into an owned String before
joining, so many references to one long shared text copied gigabytes before
the joined length was ever checked. Errors are now found first without
building text (so they still win in argument order), then each piece and
delimiter is converted only as it is appended, stopping at the cap.

crates/engine/src/cf.rs

@@ -1,7 +1,7 @@
 //! Conditional formatting evaluation: what extra style, data bar, colour scale or icon a cell
 //! gets.
 
-use std::collections::{HashMap, HashSet};
+use std::collections::HashMap;
 
 use gridcraft_core::{CellRef, RangeRef, Value, compare};
 use gridcraft_model::{CfOperator, CfRule, CfValueKind, Color, CondFormat, PatternType, Sheet, Style, Underline, Workbook, default_icon_thresholds};
@@ -47,8 +47,6 @@ enum StatsNeed {
 fn stats_need(rule: &CfRule) -> Option<StatsNeed> {
     match rule {
         CfRule::Duplicate { .. } | CfRule::Unique { .. } => Some(StatsNeed::Counts),
-        // only two- and three-colour scales paint: no statistics for the others
-        CfRule::ColorScale { stops } if !matches!(stops.len(), 2 | 3) => None,
         CfRule::Top10 { .. } | CfRule::AboveAverage { .. } | CfRule::ColorScale { .. } | CfRule::DataBar { .. } | CfRule::IconSet { .. } => {
             Some(StatsNeed::Numbers)
         }
@@ -72,58 +70,15 @@ thread_local! {
     static SCANNED: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
 }
 
-/// Most cells one rule's statistics visit, across all of its ranges together: a rule repeating
-/// the same range many times must not multiply the scan.
-const STATS_SCAN_LIMIT: usize = 2_000_000;
-
-/// Steps through the spilled cells inside `r`, row-major: `Some(cell)` for each, and `None` for a
-/// jump past the spills left or right of the columns on a row (one step per row, however many
-/// there are), so unrelated spills between a narrow range's corners cost little.
-fn spill_steps(sh: &Sheet, r: RangeRef) -> impl Iterator<Item = Option<CellRef>> + '_ {
-    let mut cur = Some(r.start);
-    std::iter::from_fn(move || {
-        let at = cur.filter(|at| *at <= r.end)?;
-        let (&c, _) = sh.spill.range(at..=r.end).next()?;
-        if c.col < r.start.col {
-            cur = Some(CellRef::new(c.row, r.start.col));
-            Some(None)
-        } else if c.col > r.end.col {
-            cur = c.row.checked_add(1).map(|row| CellRef::new(row, r.start.col));
-            Some(None)
-        } else {
-            cur = c.col.checked_add(1).map(|col| CellRef::new(c.row, col));
-            Some(Some(c))
-        }
-    })
-}
-
 fn numbers_in(sh: &Sheet, ranges: &[RangeRef], need: StatsNeed) -> (Vec<f64>, HashMap<String, usize>) {
     let mut nums = Vec::new();
     let mut counts = HashMap::new();
-    let mut budget = STATS_SCAN_LIMIT;
-    let mut seen: HashSet<RangeRef> = HashSet::new();
-    let used = sh.used_range();
     for r in ranges {
-        if budget == 0 {
-            break;
-        }
-        let r = match used.and_then(|u| r.intersection(&u)) {
+        let r = match sh.used_range().and_then(|u| r.intersection(&u)) {
             Some(x) => x,
             None => continue,
         };
-        // The same range listed twice counts its cells once.
-        if !seen.insert(r) {
-            continue;
-        }
-        // Only stored and spilled cells hold values: blank cells of a sparse range cost nothing,
-        // so a value far down a huge range is still counted. Every cell looked at is charged.
-        let stored = sh.cells.iter_range(r).map(|(c, _)| (Some(c), true));
-        let spilled = spill_steps(sh, r).map(|c| (c, false));
-        for (c, is_stored) in stored.chain(spilled).take(budget) {
-            budget -= 1;
-            // a skip over spills outside the columns (charged, not read), or a spilled value
-            // under a stored cell, which was read with it
-            let Some(c) = c.filter(|c| is_stored || sh.cells.get(*c).is_none()) else { continue };
+        for c in r.iter().take(2_000_000) {
             #[cfg(test)]
             SCANNED.with(|n| n.set(n.get() + 1));
             let v = sh.value(c);
@@ -323,8 +278,7 @@ impl CfCache {
                     _ => None,
                 },
                 CfRule::ColorScale { stops } => {
-                    // Only two- and three-colour scales paint: evaluate no thresholds for others.
-                    if let Some(n) = v.as_f64().filter(|_| matches!(stops.len(), 2 | 3)) {
+                    if let Some(n) = v.as_f64() {
                         let pts: Vec<(f64, [u8; 3])> = stops
                             .iter()
                             .map(|(k, col)| (threshold(wb, sheet, c, st, k), col.resolve(&wb.theme).unwrap_or([255, 255, 255])))
@@ -606,89 +560,6 @@ mod tests {
         assert_eq!(SCANNED.with(|n| n.get()), 10_000);
     }
 
-    /// A rule listing the same range many times scans it once, and never more than the shared
-    /// limit however many ranges it holds.
-    #[test]
-    fn repeated_ranges_share_one_scan_budget() {
-        let mut s = crate::Session::new();
-        s.new_workbook();
-        s.execute("range.setValues", json!({"range": "A1", "values": [[1], [2], [3]]})).unwrap();
-        s.execute("range.setValues", json!({"range": "XFD1048576", "values": [[4]]})).unwrap();
-        let d = s.doc().unwrap();
-        let sh = d.wb.sheet(0).unwrap();
-        let dense = RangeRef::parse("A1:XFD1048576").unwrap();
-        let small = RangeRef::parse("A1:A3").unwrap();
-        SCANNED.with(|n| n.set(0));
-        let st = RuleStats::build(sh, &vec![small; 1000], StatsNeed::Numbers);
-        assert_eq!(st.sorted, vec![1.0, 2.0, 3.0]);
-        assert_eq!(SCANNED.with(|n| n.get()), 3);
-        let shifted: Vec<RangeRef> = (0..50).map(|i| RangeRef::new(CellRef::new(i, 0), dense.end)).collect();
-        SCANNED.with(|n| n.set(0));
-        RuleStats::build(sh, &shifted, StatsNeed::Numbers);
-        assert!(SCANNED.with(|n| n.get()) <= STATS_SCAN_LIMIT);
-    }
-
-    /// Blank cells of a sparse range are not charged to the scan budget: a value at the end of two
-    /// million-row columns still counts, so duplicates are found.
-    #[test]
-    fn sparse_ranges_keep_their_values_under_the_scan_budget() {
-        let mut s = crate::Session::new();
-        s.new_workbook();
-        s.execute("range.setValues", json!({"range": "A1", "values": [[7]]})).unwrap();
-        s.execute("range.setValues", json!({"range": "B1048576", "values": [[7]]})).unwrap();
-        let d = s.doc().unwrap();
-        let sh = d.wb.sheet(0).unwrap();
-        let ranges = [RangeRef::parse("A1:A1048576").unwrap(), RangeRef::parse("B1:B1048576").unwrap()];
-        SCANNED.with(|n| n.set(0));
-        let st = RuleStats::build(sh, &ranges, StatsNeed::Counts);
-        assert_eq!(st.counts.get("7"), Some(&2));
-        assert_eq!(SCANNED.with(|n| n.get()), 2);
-    }
-
-    /// Spills left and right of a narrow range, between its corners, are skipped a row at a time:
-    /// they do not use the budget that the in-range spills need.
-    #[test]
-    fn spills_outside_a_narrow_range_do_not_use_its_scan_budget() {
-        let mut s = crate::Session::new();
-        s.new_workbook();
-        let d = s.doc().unwrap();
-        let mut sh = d.wb.sheet(0).unwrap().clone();
-        for row in 0..1000 {
-            for col in [0u32, 5, 6, 7] {
-                sh.spill.insert(CellRef::new(row, col), Value::Number(1.0));
-            }
-        }
-        let r = RangeRef::parse("F1:G1000").unwrap();
-        let steps: Vec<_> = spill_steps(&sh, r).collect();
-        assert_eq!(steps.iter().flatten().count(), 2000);
-        // column A is skipped one step a row, never one per cell
-        assert!(steps.len() <= 2000 + 1000, "{}", steps.len());
-        let narrow = RangeRef::parse("C1:C1000").unwrap();
-        assert_eq!(spill_steps(&sh, narrow).flatten().count(), 0);
-    }
-
-    /// A colour scale with an unsupported number of stops paints nothing and evaluates none of them.
-    #[test]
-    fn colour_scales_with_other_stop_counts_paint_nothing() {
-        let mut s = crate::Session::new();
-        s.new_workbook();
-        s.execute("range.setValues", json!({"range": "A1", "values": [[1], [5]]})).unwrap();
-        let mut wb: Workbook = (*s.doc().unwrap().wb).clone();
-        let stop = (CfValueKind::Formula("=1".into()), Color::default());
-        let rule = |n: usize| CondFormat {
-            ranges: vec![RangeRef::parse("A1:A2").unwrap()],
-            rule: CfRule::ColorScale { stops: vec![stop.clone(); n] },
-            priority: 1,
-            stop_if_true: false,
-        };
-        wb.sheet_mut(0).unwrap().cond_formats.push(rule(4));
-        let mut cache = CfCache::new();
-        assert_eq!(cache.look(&wb, 0, CellRef::parse("A1").unwrap()).and_then(|l| l.scale_fill), None);
-        wb.sheet_mut(0).unwrap().cond_formats = vec![rule(2)];
-        let mut cache = CfCache::new();
-        assert!(cache.look(&wb, 0, CellRef::parse("A1").unwrap()).and_then(|l| l.scale_fill).is_some());
-    }
-
     #[test]
     fn cell_value_operator_names() {
         let mut s = crate::Session::new();

crates/functions/src/text.rs

@@ -53,25 +53,41 @@ fn concat(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
     check_len(out)
 }
 
+/// The error `v.to_text()` would give, found without building any text.
+fn text_error(v: &Value) -> Option<CellError> {
+    match v {
+        Value::Error(e) => Some(*e),
+        Value::Array(a) => a.data.first().and_then(text_error),
+        _ => None,
+    }
+}
+
 fn textjoin(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
-    let delims: Vec<String> = as_array(&arg(a, 0)?.value).iter().map(|v| v.to_text()).collect::<R<_>>()?;
+    // Errors are found first, in argument order, so they win as before; text is then built one
+    // piece at a time into the capped output, so many references to one long text (or a long
+    // delimiter list) stop at the cap instead of first copying every piece.
+    let delims = as_array(&arg(a, 0)?.value);
+    if let Some(e) = delims.iter().find_map(text_error) {
+        return Err(e);
+    }
     let ignore = boolean(a, 1)?;
-    let mut items = Vec::new();
-    for x in a.iter().skip(2) {
-        for v in as_array(&x.value).iter() {
-            let s = v.to_text()?;
-            if ignore && s.is_empty() {
-                continue;
-            }
-            items.push(s);
-        }
+    let items: Vec<_> = a.iter().skip(2).map(|x| as_array(&x.value)).collect();
+    if let Some(e) = items.iter().flat_map(|x| x.iter()).find_map(text_error) {
+        return Err(e);
     }
     let mut out = String::new();
-    for (i, s) in items.iter().enumerate() {
-        if i > 0 && !delims.is_empty() {
-            push_capped(&mut out, &delims[(i - 1) % delims.len()])?;
+    let mut joined = 0usize;
+    for v in items.iter().flat_map(|x| x.iter()) {
+        let s = v.to_text()?;
+        if ignore && s.is_empty() {
+            continue;
         }
-        push_capped(&mut out, s)?;
+        if joined > 0 && !delims.data.is_empty() {
+            let d = delims.data.get((joined - 1) % delims.data.len()).map(Value::to_text).transpose()?.unwrap_or_default();
+            push_capped(&mut out, &d)?;
+        }
+        push_capped(&mut out, &s)?;
+        joined += 1;
     }
     check_len(out)
 }
@@ -1131,6 +1147,22 @@ mod tests {
         assert_eq!(rows_of(&ev("CONCATENATE", vec![av(row_t(&["a", "b"])), t("x")])), vec![vec![tv("ax"), tv("bx")]]);
     }
 
+    /// Security: TEXTJOIN builds its result piece by piece and stops at the text cap, rather
+    /// than first copying every input (100,000 references to one 32,767-character text were
+    /// 3 GB of copies). Errors among the inputs still win, in argument order.
+    #[test]
+    fn textjoin_stops_at_the_text_cap() {
+        use gridcraft_core::Array;
+        let long = tv(&"x".repeat(32_767));
+        let many = || av(Array::filled(100_000, 1, long.clone()).into());
+        is_err(ev("TEXTJOIN", vec![t(","), b(true), many()]), CellError::Value);
+        is_err(ev("TEXTJOIN", vec![av(Array::filled(1, 100_000, long.clone()).into()), b(false), t("a"), t("b")]), CellError::Value);
+        is_err(ev("TEXTJOIN", vec![t(","), b(true), many(), e(CellError::Div0)]), CellError::Div0);
+        is_err(ev("TEXTJOIN", vec![av(arr(vec![vec![tv(","), Value::Error(CellError::NA)]])), b(true), t("a")]), CellError::NA);
+        // Delimiters cycle and are converted only where used.
+        is_text(ev("TEXTJOIN", vec![av(arr(vec![vec![nv(1.0), tv(";")]])), b(false), t("a"), t("b"), t("c"), t("d")]), "a1b;c1d");
+    }
+
     fn row_t(xs: &[&str]) -> Value {
         arr(vec![xs.iter().map(|x| tv(x)).collect()])
     }