functions: one work budget across every call of a lifted function

A function lifted over a computed array runs once per element, and only the
six lookups counted their repeated work against LIFTED_SCAN_BUDGET. Criteria
aggregates rescanned their ranges per criterion, CUMIPMT/CUMPRINC stepped
through up to 1e7 periods per element, and array-producing functions such as
MUNIT built a whole result per element before keeping its first cell.

The budget now covers all of it: COUNTIF/SUMIF/AVERAGEIF(S)/MAXIFS/MINIFS
charge their range cells per call, the period loops of every element are
added up before any runs, and array results charge their cells as they are
built. Past the budget the call is #NUM!, as lifted lookups already are.

crates/chart/src/resolve.rs

@@ -11,10 +11,6 @@ use crate::{ChartData, Rgba, SeriesData, TrendlineData};
 pub(crate) const MAX_POINTS: usize = 100_000;
 /// Cap on series per chart.
 pub(crate) const MAX_SERIES: usize = 255;
-/// Cap on the points of all series of one chart together (values, X values and bubble sizes):
-/// [`MAX_SERIES`] × [`MAX_POINTS`] would let a few short whole-column references retain and
-/// draw tens of millions of points. Series past it get only what is left, or no points.
-pub(crate) const MAX_CHART_POINTS: usize = 1_000_000;
 /// Cap on trendlines drawn per series.
 pub(crate) const MAX_TRENDLINES: usize = 16;
 
@@ -81,15 +77,10 @@ fn union_parts(f: &str) -> Option<Vec<&str>> {
 /// Evaluates a series formula to a flat list of values (row-major), capped. A union of
 /// references (`(A1:A3,A5)`, as PivotCharts use) is read part by part.
 fn eval_list(wb: &Workbook, sheet: usize, formula: &str) -> Vec<Value> {
-    eval_list_in(wb, sheet, formula, 0, MAX_POINTS)
+    eval_list_in(wb, sheet, formula, 0)
 }
 
-/// [`eval_list`] keeping at most `cap` values (and never more than [`MAX_POINTS`]).
-fn eval_list_capped(wb: &Workbook, sheet: usize, formula: &str, cap: usize) -> Vec<Value> {
-    eval_list_in(wb, sheet, formula, 0, cap.min(MAX_POINTS))
-}
-
-fn eval_list_in(wb: &Workbook, sheet: usize, formula: &str, depth: u32, cap: usize) -> Vec<Value> {
+fn eval_list_in(wb: &Workbook, sheet: usize, formula: &str, depth: u32) -> Vec<Value> {
     let f = formula.trim();
     if f.is_empty() {
         return vec![];
@@ -99,19 +90,16 @@ fn eval_list_in(wb: &Workbook, sheet: usize, formula: &str, depth: u32, cap: usi
     {
         let mut out = Vec::new();
         for p in parts {
-            if out.len() >= cap {
+            if out.len() >= MAX_POINTS {
                 break;
             }
-            let rest = cap - out.len();
-            out.extend(eval_list_in(wb, sheet, p, depth + 1, rest).into_iter().take(rest));
+            let rest = MAX_POINTS - out.len();
+            out.extend(eval_list_in(wb, sheet, p, depth + 1).into_iter().take(rest));
         }
         return out;
     }
-    if cap == 0 {
-        return vec![];
-    }
     match evaluate(wb, sheet, CellRef::default(), f) {
-        Value::Array(a) => a.iter().take(cap).cloned().collect(),
+        Value::Array(a) => a.iter().take(MAX_POINTS).cloned().collect(),
         v => vec![v],
     }
 }
@@ -123,11 +111,8 @@ fn to_num(v: &Value) -> Option<f64> {
     }
 }
 
-/// A series formula's numbers, at most `cap` of them; `cap` is reduced by what was taken.
-fn nums(wb: &Workbook, sheet: usize, formula: &str, cap: &mut usize) -> Vec<Option<f64>> {
-    let out: Vec<Option<f64>> = eval_list_capped(wb, sheet, formula, *cap).iter().map(to_num).collect();
-    *cap -= out.len().min(*cap);
-    out
+fn nums(wb: &Workbook, sheet: usize, formula: &str) -> Vec<Option<f64>> {
+    eval_list(wb, sheet, formula).iter().map(to_num).collect()
 }
 
 /// Number format code of the first cell of a reference ("General" when not a reference).
@@ -243,21 +228,15 @@ pub fn resolve(wb: &Workbook, sheet: usize, chart: &Chart) -> ChartData {
     let mut series = Vec::new();
     let mut categories: Option<Vec<String>> = None;
     let mut category_levels = Vec::new();
-    // One point budget for the whole chart, not one per series.
-    let mut budget = MAX_CHART_POINTS;
     for (i, s) in chart.series.iter().take(MAX_SERIES).enumerate() {
-        let values = nums(wb, sheet, &s.values, &mut budget);
+        let values = nums(wb, sheet, &s.values);
         let name = s.name.as_deref().map(|n| series_name(wb, sheet, n)).filter(|n| !n.is_empty()).unwrap_or_else(|| format!("Series{}", i + 1));
         let color =
             s.color.as_ref().and_then(|c| c.resolve(&wb.theme)).map(|[r, g, b]| [r, g, b, 0xFF]).unwrap_or_else(|| series_color(&wb.theme, i));
         let kind = effective_kind(chart.kind, s.kind, i);
         let x = match (&s.categories, numeric_x || matches!(kind, ChartKind::Scatter | ChartKind::ScatterLines | ChartKind::Bubble)) {
             // X values with text in them (labels) are ignored: the points are numbered 1..n.
-            (Some(f), true) => {
-                let xs = eval_list_capped(wb, sheet, f, budget);
-                budget -= xs.len().min(budget);
-                Some(xs).filter(|xs| !xs.iter().any(Value::is_text)).map(|xs| xs.iter().map(to_num).collect())
-            }
+            (Some(f), true) => Some(eval_list(wb, sheet, f)).filter(|xs| !xs.iter().any(Value::is_text)).map(|xs| xs.iter().map(to_num).collect()),
             _ => None,
         };
         if categories.is_none()
@@ -269,7 +248,7 @@ pub fn resolve(wb: &Workbook, sheet: usize, chart: &Chart) -> ChartData {
                 category_levels = outer;
             }
         }
-        let sizes = s.bubble_sizes.as_deref().map(|f| nums(wb, sheet, f, &mut budget));
+        let sizes = s.bubble_sizes.as_deref().map(|f| nums(wb, sheet, f));
         let trendlines = s
             .trendlines
             .iter()

crates/chart/src/tests.rs

@@ -1258,21 +1258,3 @@ fn box_whisker_draws_each_series_quartile_method() {
     // The boxes span 3.5 and 2.5 data units on the same value axis.
     assert!((heights[0] / heights[1] - 1.4).abs() < 0.001);
 }
-
-#[test]
-fn series_share_one_point_budget() {
-    // Many series over the same long column each get a share of one chart-wide budget, not
-    // `MAX_POINTS` apiece.
-    let mut wb = Workbook::new();
-    let s = wb.sheet_mut(0).unwrap();
-    s.set_value(CellRef::new(0, 0), Value::Number(1.0));
-    s.set_value(CellRef::new(59_999, 0), Value::Number(2.0));
-    let mut c = chart(ChartKind::ColumnClustered);
-    c.series = (0..40).map(|_| Series { values: "Sheet1!$A$1:$A$60000".into(), ..Default::default() }).collect();
-    let d = resolve(&wb, 0, &c);
-    assert_eq!(d.series.len(), 40);
-    assert_eq!(d.series[0].values.len(), 60_000);
-    let total: usize = d.series.iter().map(|s| s.values.len()).sum();
-    assert_eq!(total, crate::resolve::MAX_CHART_POINTS);
-    assert!(d.series.last().is_some_and(|s| s.values.is_empty()));
-}

crates/engine/src/chart_svg.rs

@@ -10,10 +10,6 @@ use crate::io::esc;
 /// Widest or tallest chart written; larger anchors are clamped.
 const MAX_SIDE: f32 = 16_384.0;
 
-/// Most bytes of SVG written for the charts of one web page together. A chart past what is
-/// left is left out of the page rather than grown without bound.
-pub(crate) const MAX_PAGE_SVG_BYTES: usize = 64 * 1024 * 1024;
-
 struct HelveticaMeasure;
 
 impl gridcraft_chart::Measure for HelveticaMeasure {
@@ -22,34 +18,24 @@ impl gridcraft_chart::Measure for HelveticaMeasure {
     }
 }
 
-/// `chart` of sheet `sheet` as an `<svg>` element placed by `style`, or `None` for a degenerate
-/// size or an element longer than `budget` bytes.
-pub(crate) fn chart_svg(wb: &Workbook, sheet: usize, chart: &Chart, style: &str, budget: usize) -> Option<String> {
+/// `chart` of sheet `sheet` as an `<svg>` element placed by `style`, or `None` for a degenerate size.
+pub(crate) fn chart_svg(wb: &Workbook, sheet: usize, chart: &Chart, style: &str) -> Option<String> {
     let (w, h) = (chart.anchor.width.min(MAX_SIDE), chart.anchor.height.min(MAX_SIDE));
     if !(w >= 1.0 && h >= 1.0) {
         return None;
     }
     let data = gridcraft_chart::resolve(wb, sheet, chart);
     let prims = gridcraft_chart::render(chart, &data, w, h, &HelveticaMeasure);
-    prims_svg_within(&prims, w, h, style, budget)
+    Some(prims_svg(&prims, w, h, style))
 }
 
-#[cfg(test)]
 fn prims_svg(prims: &[Prim], w: f32, h: f32, style: &str) -> String {
-    prims_svg_within(prims, w, h, style, usize::MAX).unwrap_or_default()
-}
-
-/// The `<svg>` element, or `None` as soon as it grows past `budget` bytes.
-fn prims_svg_within(prims: &[Prim], w: f32, h: f32, style: &str, budget: usize) -> Option<String> {
     let mut out = String::new();
     let _ = write!(
         out,
         "<svg xmlns=\"http://www.w3.org/2000/svg\" width=\"{w}\" height=\"{h}\" viewBox=\"0 0 {w} {h}\" font-family=\"Helvetica,Arial,sans-serif\" style=\"{style}\">"
     );
     for p in prims {
-        if out.len() > budget {
-            return None;
-        }
         match p {
             Prim::Rect { x, y, w, h, fill, stroke, radius } => {
                 let _ = write!(out, "<rect x=\"{}\" y=\"{}\" width=\"{}\" height=\"{}\"", num(*x), num(*y), num(*w), num(*h));
@@ -106,7 +92,7 @@ fn prims_svg_within(prims: &[Prim], w: f32, h: f32, style: &str, budget: usize)
         }
     }
     out.push_str("</svg>");
-    (out.len() <= budget).then_some(out)
+    out
 }
 
 /// Fill and stroke attributes of an open shape element; the caller closes it.
@@ -163,17 +149,6 @@ fn num(v: f32) -> String {
 mod tests {
     use super::*;
 
-    #[test]
-    fn an_svg_past_its_byte_budget_is_left_out() {
-        let rect = Prim::Rect { x: 1.0, y: 2.0, w: 3.0, h: 4.0, fill: Some([255, 0, 0, 255]), stroke: None, radius: 0.0 };
-        let prims = vec![rect; 10_000];
-        let full = prims_svg(&prims, 100.0, 50.0, "");
-        assert!(full.len() > 100_000);
-        assert_eq!(prims_svg_within(&prims, 100.0, 50.0, "", full.len()), Some(full.clone()));
-        assert_eq!(prims_svg_within(&prims, 100.0, 50.0, "", full.len() - 1), None);
-        assert_eq!(prims_svg_within(&prims, 100.0, 50.0, "", 1_000), None);
-    }
-
     #[test]
     fn every_primitive_becomes_an_svg_element() {
         let red = [255, 0, 0, 255];

crates/engine/src/io.rs

@@ -736,10 +736,8 @@ pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
                 place(&im.anchor)
             );
         }
-        let mut svg_budget = crate::chart_svg::MAX_PAGE_SVG_BYTES;
         for ch in &sh.charts {
-            if let Some(svg) = crate::chart_svg::chart_svg(wb, sheet, ch, &place(&ch.anchor), svg_budget) {
-                svg_budget -= svg.len();
+            if let Some(svg) = crate::chart_svg::chart_svg(wb, sheet, ch, &place(&ch.anchor)) {
                 out.push_str(&svg);
             }
         }

crates/functions/src/lift.rs

@@ -68,26 +68,70 @@ 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;
 
-/// 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.
+/// 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.
 fn scan_len(spec: &FnSpec, args: &[Arg]) -> usize {
-    if !SCANS.contains(&spec.name) {
+    let scans = SCANS.contains(&spec.name);
+    if !scans && !CRITERIA.contains(&spec.name) {
         return 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)
+    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,
+    }
 }
 
 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;
@@ -106,25 +150,42 @@ pub(crate) fn call_lifted(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx) -> Val
         return (spec.imp)(args, ctx);
     }
     let needles = rows.saturating_mul(cols);
-    if needles > MAX_CELLS || needles.saturating_mul(scan_len(spec, args)) > LIFTED_SCAN_BUDGET {
+    // 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 {
         return Value::Error(CellError::Num);
     }
-    let mut cell_args: Vec<Arg> = args.to_vec();
+    // 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 data = Vec::with_capacity(rows * cols);
     for r in 0..rows {
         for c in 0..cols {
-            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 };
-                }
-            }
+            element_args(spec, args, r, c, &mut cell_args);
             let out = (spec.imp)(&cell_args, ctx);
             data.push(match out {
-                Value::Array(a) => a.data.first().cloned().unwrap_or(Value::Empty),
+                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)
+                }
                 v => v,
             });
         }
@@ -209,6 +270,52 @@ 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() };