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/functions/src/lift.rs

@@ -68,70 +68,26 @@ const SCANS: &[&str] = &["VLOOKUP", "HLOOKUP", "LOOKUP", "MATCH", "XLOOKUP", "XM
 /// `XMATCH(SEQUENCE(1048576), -SEQUENCE(1048576))` runs for hours and hangs opening the file.
 /// Past the budget the call is `#NUM!`, as MMULT is past 2e9 multiply-adds. 5e8 keeps the worst
 /// case to a few seconds and still admits 5,000 needles over a 100,000-row table.
-///
-/// The same budget covers all the work of a lifted call added up across its elements: criteria
-/// aggregates rescanning their ranges, period loops, and array results built per element.
 const LIFTED_SCAN_BUDGET: usize = 500_000_000;
 
-/// Criteria aggregates: every call tests each cell of its ranges against its criteria, so a call
-/// lifted over `n` criteria does `n` x (range cells) work, like the [`SCANS`] lookups.
-const CRITERIA: &[&str] = &["COUNTIF", "COUNTIFS", "SUMIF", "SUMIFS", "AVERAGEIF", "AVERAGEIFS", "MAXIFS", "MINIFS"];
-
-/// Cumulative TVM functions that step through every period from `start_period` (argument 3) to
-/// `end_period` (argument 4) on each call.
-const PERIOD_LOOPS: &[&str] = &["CUMIPMT", "CUMPRINC"];
-
-/// The work every lifted call of `spec` repeats over its non-lifted arguments: the longest vector
-/// a [`SCANS`] lookup searches, or every cell a [`CRITERIA`] aggregate tests. 0 for other
-/// functions.
+/// The length of the longest vector a lifted call of `spec` searches per needle: 0 unless `spec`
+/// is one of the [`SCANS`] lookups and a non-lifted argument is an array.
 fn scan_len(spec: &FnSpec, args: &[Arg]) -> usize {
-    let scans = SCANS.contains(&spec.name);
-    if !scans && !CRITERIA.contains(&spec.name) {
+    if !SCANS.contains(&spec.name) {
         return 0;
     }
-    let lens = args.iter().enumerate().filter(|(i, _)| !spec.is_scalar_arg(*i)).filter_map(|(_, a)| match &a.value {
-        Value::Array(arr) => Some(if scans { arr.rows.max(arr.cols) } else { arr.data.len() }),
-        _ => None,
-    });
-    if scans { lens.max().unwrap_or(0) } else { lens.fold(0, usize::saturating_add) }
-}
-
-/// The work of one lifted call that depends on its own (lifted) scalar arguments: the number of
-/// periods a [`PERIOD_LOOPS`] function steps through. 0 for other functions.
-fn call_cost(spec: &FnSpec, cell_args: &[Arg]) -> usize {
-    if !PERIOD_LOOPS.contains(&spec.name) {
-        return 0;
-    }
-    let period = |i: usize| match cell_args.get(i).map(|a| &a.value) {
-        Some(Value::Number(n)) if n.is_finite() => Some(n.trunc()),
-        _ => None,
-    };
-    match (period(3), period(4)) {
-        // The function itself refuses spans past 1e7 periods; anything larger costs the cap.
-        (Some(start), Some(end)) if end >= start => ((end - start) + 1.0).min(1e8) as usize,
-        _ => 0,
-    }
+    args.iter()
+        .enumerate()
+        .filter(|(i, _)| !spec.is_scalar_arg(*i))
+        .filter_map(|(_, a)| match &a.value {
+            Value::Array(arr) => Some(arr.rows.max(arr.cols)),
+            _ => None,
+        })
+        .max()
+        .unwrap_or(0)
 }
 
 pub(crate) fn call_lifted(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx) -> Value {
-    call_lifted_within(spec, args, ctx, LIFTED_SCAN_BUDGET)
-}
-
-/// Sets the lifted arguments of `cell_args` to their elements at (`r`, `c`).
-fn element_args(spec: &FnSpec, args: &[Arg], r: usize, c: usize, cell_args: &mut [Arg]) {
-    for (i, a) in args.iter().enumerate() {
-        if spec.is_scalar_arg(i)
-            && let Value::Array(arr) = &a.value
-            && let Some(slot) = cell_args.get_mut(i)
-        {
-            let v = arr.get_broadcast(r, c);
-            slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
-        }
-    }
-}
-
-/// [`call_lifted`] with every call's work added up against `budget` (see [`LIFTED_SCAN_BUDGET`]).
-fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: usize) -> Value {
     let rejected = if spec.value_args.is_empty() { None } else { reject_multi_cell_refs(spec, args) };
     let args = rejected.as_deref().unwrap_or(args);
     let mut rows = 0usize;
@@ -150,42 +106,25 @@ fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: us
         return (spec.imp)(args, ctx);
     }
     let needles = rows.saturating_mul(cols);
-    // Every call is charged its repeated scan (at least 1), its own period loop, and the cells of
-    // an array result (built in full, though only its first cell is kept), so lifting a scalar
-    // argument can't multiply what one call may do into hours of work:
-    // `COUNTIF(big_range, SEQUENCE(1e4))`, `CUMIPMT(0.1, 1e7, 1, 1, SEQUENCE(1e4,,1e7,0), 0)`,
-    // `MUNIT(SEQUENCE(1e4,,3000,0))`.
-    let per_call = scan_len(spec, args).max(1);
-    let mut cell_args: Vec<Arg> = args.to_vec();
-    let mut spent = needles.saturating_mul(per_call);
-    if needles > MAX_CELLS || spent > budget {
+    if needles > MAX_CELLS || needles.saturating_mul(scan_len(spec, args)) > LIFTED_SCAN_BUDGET {
         return Value::Error(CellError::Num);
     }
-    // Period loops are known before any call runs, so a call over budget does none of them.
-    if PERIOD_LOOPS.contains(&spec.name) {
-        for r in 0..rows {
-            for c in 0..cols {
-                element_args(spec, args, r, c, &mut cell_args);
-                spent = spent.saturating_add(call_cost(spec, &cell_args));
-                if spent > budget {
-                    return Value::Error(CellError::Num);
-                }
-            }
-        }
-    }
+    let mut cell_args: Vec<Arg> = args.to_vec();
     let mut data = Vec::with_capacity(rows * cols);
     for r in 0..rows {
         for c in 0..cols {
-            element_args(spec, args, r, c, &mut cell_args);
+            for (i, a) in args.iter().enumerate() {
+                if spec.is_scalar_arg(i)
+                    && let Value::Array(arr) = &a.value
+                    && let Some(slot) = cell_args.get_mut(i)
+                {
+                    let v = arr.get_broadcast(r, c);
+                    slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
+                }
+            }
             let out = (spec.imp)(&cell_args, ctx);
             data.push(match out {
-                Value::Array(a) => {
-                    spent = spent.saturating_add(a.data.len());
-                    if spent > budget {
-                        return Value::Error(CellError::Num);
-                    }
-                    a.data.first().cloned().unwrap_or(Value::Empty)
-                }
+                Value::Array(a) => a.data.first().cloned().unwrap_or(Value::Empty),
                 v => v,
             });
         }
@@ -270,52 +209,6 @@ mod tests {
         assert_eq!(rows_of(&out), vec![vec![nv(-1.0)]; 1000]);
     }
 
-    /// Security: lifting a criteria aggregate rescans its range for every criterion, so criteria
-    /// x range cells past the budget is `#NUM!` before any scan runs.
-    #[test]
-    fn lifted_criteria_aggregates_stop_past_their_work_budget() {
-        use gridcraft_core::Array;
-        let tall = |n: usize| av(Array::filled(n, 1, nv(-1.0)).into());
-        is_err(ev("COUNTIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        is_err(ev("SUMIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        is_err(ev("COUNTIFS", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        // Two ranges of 250,000 cells each count together.
-        is_err(ev("SUMIFS", vec![tall(250_000), tall(250_000), tall(1001)]), CellError::Num);
-        let counts = ev("COUNTIF", vec![av(col(&[1.0, 2.0, 2.0])), av(col(&[2.0, 1.0, 5.0]))]);
-        assert_eq!(rows_of(&counts), vec![vec![nv(2.0)], vec![nv(1.0)], vec![nv(0.0)]]);
-        for name in super::CRITERIA.iter().chain(super::PERIOD_LOOPS) {
-            assert!(crate::lookup(name).is_some(), "{name} isn't registered");
-        }
-    }
-
-    /// Security: CUMIPMT and CUMPRINC loop over their periods once per lifted element; the
-    /// periods of all elements are added up first, so an over-budget call runs none of them.
-    #[test]
-    fn lifted_period_loops_stop_past_their_work_budget() {
-        use gridcraft_core::Array;
-        let ends = |len: usize, end: f64| av(Array::filled(len, 1, nv(end)).into());
-        let args = |len: usize, end: f64| vec![n(0.01), n(1e7), n(1000.0), n(1.0), ends(len, end), n(0.0)];
-        // 51 elements of 1e7 periods each is past 5e8.
-        is_err(ev("CUMIPMT", args(51, 1e7)), CellError::Num);
-        is_err(ev("CUMPRINC", args(51, 1e7)), CellError::Num);
-        let out = ev("CUMIPMT", args(2, 12.0));
-        assert_eq!(rows_of(&out).len(), 2);
-        assert!(matches!(rows_of(&out).first().and_then(|r| r.first()), Some(Value::Number(x)) if *x < 0.0));
-    }
-
-    /// Security: an array-producing function lifted over a computed array builds each element's
-    /// whole result before keeping one cell; their cells count against the budget.
-    #[test]
-    fn lifted_array_results_count_against_the_budget() {
-        use gridcraft_core::Array;
-        let spec = crate::lookup("MUNIT").unwrap_or_else(|| panic!("MUNIT isn't registered"));
-        let dims = |n: usize| [av(Array::filled(n, 1, nv(10.0)).into())];
-        // Ten 10x10 identity matrices are 1,000 cells.
-        let out = super::call_lifted_within(spec, &dims(10), &mut TestCtx::default(), 1_010);
-        assert_eq!(rows_of(&out), vec![vec![nv(1.0)]; 10]);
-        is_err(super::call_lifted_within(spec, &dims(11), &mut TestCtx::default(), 1_010), CellError::Num);
-    }
-
     #[test]
     fn value_params_reject_multi_cell_references() {
         let s = FnSpec { value_args: &[true, false], ..spec() };

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()])
     }