Compare commits

..
Author SHA1 Message Date
Dylan M. Taylor 2afabb4f7e address review: charge X values to the chart point budget only when they are kept 2026-11-04 00:55:09 +00:00
Dylan M. Taylor a2737739cc Charts: one point budget per chart and a byte budget for web-page SVG
A chart resolved every series reference into its own vector of up to
100,000 points, so 255 short whole-column series retained and drew
25.5 million points, and Save as Web Page wrote one SVG element per
mark without any output limit.

- resolve() shares MAX_CHART_POINTS (1,000,000) across the values,
  X values and bubble sizes of all series; a series past the budget
  gets what is left.
- chart_svg() stops writing once a chart passes the bytes left of a
  64 MiB per-page budget and leaves that chart out.
2026-11-02 20:26:24 -05:00
5 changed files with 132 additions and 149 deletions
+37 -11
View File
@@ -11,6 +11,10 @@ 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;
@@ -77,10 +81,15 @@ 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)
eval_list_in(wb, sheet, formula, 0, MAX_POINTS)
}
fn eval_list_in(wb: &Workbook, sheet: usize, formula: &str, depth: u32) -> Vec<Value> {
/// [`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> {
let f = formula.trim();
if f.is_empty() {
return vec![];
@@ -90,16 +99,19 @@ fn eval_list_in(wb: &Workbook, sheet: usize, formula: &str, depth: u32) -> Vec<V
{
let mut out = Vec::new();
for p in parts {
if out.len() >= MAX_POINTS {
if out.len() >= cap {
break;
}
let rest = MAX_POINTS - out.len();
out.extend(eval_list_in(wb, sheet, p, depth + 1).into_iter().take(rest));
let rest = cap - out.len();
out.extend(eval_list_in(wb, sheet, p, depth + 1, rest).into_iter().take(rest));
}
return out;
}
if cap == 0 {
return vec![];
}
match evaluate(wb, sheet, CellRef::default(), f) {
Value::Array(a) => a.iter().take(MAX_POINTS).cloned().collect(),
Value::Array(a) => a.iter().take(cap).cloned().collect(),
v => vec![v],
}
}
@@ -111,8 +123,11 @@ fn to_num(v: &Value) -> Option<f64> {
}
}
fn nums(wb: &Workbook, sheet: usize, formula: &str) -> Vec<Option<f64>> {
eval_list(wb, sheet, formula).iter().map(to_num).collect()
/// 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
}
/// Number format code of the first cell of a reference ("General" when not a reference).
@@ -228,15 +243,26 @@ 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);
let values = nums(wb, sheet, &s.values, &mut budget);
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) => Some(eval_list(wb, sheet, f)).filter(|xs| !xs.iter().any(Value::is_text)).map(|xs| xs.iter().map(to_num).collect()),
(Some(f), true) => {
let xs = eval_list_capped(wb, sheet, f, budget);
// Only X values that are kept are charged to the budget.
if xs.iter().any(Value::is_text) {
None
} else {
budget -= xs.len().min(budget);
Some(xs.iter().map(to_num).collect())
}
}
_ => None,
};
if categories.is_none()
@@ -248,7 +274,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));
let sizes = s.bubble_sizes.as_deref().map(|f| nums(wb, sheet, f, &mut budget));
let trendlines = s
.trendlines
.iter()
+38
View File
@@ -1258,3 +1258,41 @@ 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()));
}
#[test]
fn rejected_text_x_values_are_not_charged_to_the_point_budget() {
// A text X range is ignored (the points are numbered), so repeating it in many series must not
// use up the chart's budget and leave the later series without values.
let mut wb = Workbook::new();
let s = wb.sheet_mut(0).unwrap();
for r in 0..100 {
s.set_value(CellRef::new(r, 0), Value::Number(f64::from(r)));
}
s.set_value(CellRef::new(0, 1), Value::text("label"));
s.set_value(CellRef::new(59_999, 1), Value::Number(2.0));
let mut c = chart(ChartKind::Scatter);
c.series = (0..40)
.map(|_| Series { values: "Sheet1!$A$1:$A$100".into(), categories: Some("Sheet1!$B$1:$B$60000".into()), ..Default::default() })
.collect();
let d = resolve(&wb, 0, &c);
assert_eq!(d.series.len(), 40);
assert!(d.series.iter().all(|s| s.values.len() == 100 && s.x.is_none()));
}
+29 -4
View File
@@ -10,6 +10,10 @@ 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 {
@@ -18,24 +22,34 @@ impl gridcraft_chart::Measure for HelveticaMeasure {
}
}
/// `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> {
/// `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> {
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);
Some(prims_svg(&prims, w, h, style))
prims_svg_within(&prims, w, h, style, budget)
}
#[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));
@@ -92,7 +106,7 @@ fn prims_svg(prims: &[Prim], w: f32, h: f32, style: &str) -> String {
}
}
out.push_str("</svg>");
out
(out.len() <= budget).then_some(out)
}
/// Fill and stroke attributes of an open shape element; the caller closes it.
@@ -149,6 +163,17 @@ 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];
+3 -1
View File
@@ -736,8 +736,10 @@ 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)) {
if let Some(svg) = crate::chart_svg::chart_svg(wb, sheet, ch, &place(&ch.anchor), svg_budget) {
svg_budget -= svg.len();
out.push_str(&svg);
}
}
+25 -133
View File
@@ -3,7 +3,7 @@
use gridcraft_core::{Array, CellError, Value};
use crate::util::{MAX_CELLS, num};
use crate::util::MAX_CELLS;
use crate::{Arg, Ctx, FnSpec};
/// Value-parameter masks (see [`FnSpec::value_args`]), observed in Excel 365: a reference to more
@@ -68,68 +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;
}
// The function's own coercion (text like "10000000" counts), so no loop goes uncharged.
let period = |i: usize| num(cell_args, i).ok().filter(|n| n.is_finite()).map(f64::trunc);
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;
@@ -148,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,
});
}
@@ -268,55 +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);
// Numeric text is coerced by the function, so its periods are charged the same.
let text_ends = av(Array::filled(51, 1, Value::text("10000000")).into());
is_err(ev("CUMIPMT", vec![n(0.01), n(1e7), n(1000.0), n(1.0), text_ends, n(0.0)]), 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() };