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.

apps/gridcraft-cli/src/check/package.rs

@@ -6,10 +6,6 @@ const MAX_XML_PART: u64 = 64 * 1024 * 1024;
 /// Most zip entries looked at while validating a written package.
 const MAX_ENTRIES: usize = 200_000;
 
-/// Decompressed bytes that comparing one package's relationship kinds may read in total: the
-/// relationship parts themselves and the targets whose content is checked.
-const RELATIONSHIP_BUDGET: u64 = 512 * 1024 * 1024;
-
 /// Relationship kinds (lower case) whose absence after a save isn't a loss: the calculation chain is
 /// a cache Excel rebuilds, and GridCraft never writes it.
 pub(super) const REBUILT_KINDS: [&str; 1] = ["calcchain"];
@@ -121,28 +117,6 @@ fn read_zip_part(zip: &mut Zip<'_>, name: &str) -> Result<Vec<u8>, String> {
     Ok(buf)
 }
 
-enum PartError {
-    /// Reading the part would spend more than the remaining budget.
-    OverBudget,
-    Unreadable,
-}
-
-/// Reads a part like [`read_zip_part`], charging the decompressed bytes to `budget`.
-fn read_zip_part_within(zip: &mut Zip<'_>, name: &str, budget: &mut u64) -> Result<Vec<u8>, PartError> {
-    let f = zip.by_name(name).map_err(|_| PartError::Unreadable)?;
-    // One byte past what is left shows that the part doesn't fit.
-    let limit = MAX_XML_PART.min(budget.saturating_add(1));
-    let mut buf = Vec::new();
-    f.take(limit).read_to_end(&mut buf).map_err(|_| PartError::Unreadable)?;
-    let read = buf.len() as u64;
-    if read > *budget {
-        *budget = 0;
-        return Err(PartError::OverBudget);
-    }
-    *budget -= read;
-    Ok(buf)
-}
-
 /// Whether the producer flagged its cached results as stale with `<calcPr fullCalcOnLoad="1">`:
 /// libraries that don't calculate write it, and store 0 or nothing as every formula's value.
 pub(super) fn full_calc_on_load(bytes: &[u8]) -> bool {
@@ -258,30 +232,19 @@ pub fn validate_package(bytes: &[u8]) -> Result<Vec<String>, String> {
 /// nothing are left out, as a save may rightly drop them: a link to a place in the workbook
 /// (`#Sheet1!A1`, written as a cell's `location`) and a target part with nothing in it.
 pub(super) fn relationship_kinds(bytes: &[u8]) -> Result<BTreeMap<String, String>, String> {
-    relationship_kinds_within(bytes, RELATIONSHIP_BUDGET)
-}
-
-/// [`relationship_kinds`] reading at most `budget` decompressed bytes. `Err` once the relationship
-/// parts alone need more: their kinds can't be listed completely.
-fn relationship_kinds_within(bytes: &[u8], mut budget: u64) -> Result<BTreeMap<String, String>, String> {
     let mut zip = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| format!("not a zip package: {e}"))?;
     let names = zip_names(&mut zip);
     let by_key: HashMap<String, &String> = names.iter().map(|n| (part_key(n), n)).collect();
     // Several relationships name the same part; each fresh check decompressed it again, so
     // repeated references to one highly compressible part multiplied the work. The verdict is
     // remembered per (part, named content) and the decompression the package can cause is
-    // budgeted as a whole, the relationship parts included: many large, unreferenced rels parts
-    // would otherwise each spend a full per-part allowance.
+    // budgeted as a whole (finding: repeated decompression).
     let mut verdicts: HashMap<(String, &'static str), bool> = HashMap::new();
+    let mut budget: u64 = 512 * 1024 * 1024;
     let mut kinds = BTreeMap::new();
     for n in names.iter().filter(|n| part_key(n).ends_with(".rels")) {
         let Some(src_dir) = rels_source_dir(&part_key(n)) else { continue };
-        let xml = match read_zip_part_within(&mut zip, n, &mut budget) {
-            Ok(xml) => xml,
-            Err(PartError::OverBudget) => return Err(format!("{n}: relationship check stopped at its decompression limit")),
-            Err(PartError::Unreadable) => continue,
-        };
-        let Ok(els) = xml_elements(&xml) else { continue };
+        let Ok(els) = read_zip_part(&mut zip, n).and_then(|xml| xml_elements(&xml)) else { continue };
         for (_, attrs) in els.iter().filter(|(el, _)| el == "Relationship") {
             let Some(kind) = attr(attrs, "Type").and_then(|t| t.rsplit('/').next()) else { continue };
             let target = attr(attrs, "Target").unwrap_or("");
@@ -366,36 +329,3 @@ fn holds_something_uncached(zip: &mut Zip<'_>, name: &str, marker: &'static str,
         buf.clear();
     }
 }
-
-#[cfg(test)]
-mod tests {
-    use std::io::Write as _;
-
-    use super::*;
-
-    /// A package with `count` relationship parts of `size` bytes each, none of them describing an
-    /// existing part.
-    fn many_rels(count: usize, size: usize) -> Vec<u8> {
-        let mut z = zip::ZipWriter::new(Cursor::new(Vec::new()));
-        let opts = zip::write::SimpleFileOptions::default().compression_method(zip::CompressionMethod::Deflated);
-        let head = r#"<?xml version="1.0"?><Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/custom" Target="https://example.com" TargetMode="External"/>"#;
-        let tail = "</Relationships>";
-        let filler = " ".repeat(size.saturating_sub(head.len() + tail.len()));
-        for i in 0..count {
-            z.start_file(format!("xl/_rels/part{i}.xml.rels"), opts).unwrap();
-            z.write_all(head.as_bytes()).unwrap();
-            z.write_all(filler.as_bytes()).unwrap();
-            z.write_all(tail.as_bytes()).unwrap();
-        }
-        z.finish().unwrap().into_inner()
-    }
-
-    #[test]
-    fn relationship_parts_count_against_the_decompression_budget() {
-        // Each part fits the per-part allowance, but together they need more than the budget.
-        let bytes = many_rels(8, 64 * 1024);
-        assert!(relationship_kinds_within(&bytes, 256 * 1024).is_err());
-        let kinds = relationship_kinds_within(&bytes, 1024 * 1024).unwrap();
-        assert_eq!(kinds.get("custom").map(String::as_str), Some("custom"));
-    }
-}

crates/chart/src/resolve.rs

@@ -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,21 @@ 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);
+                budget -= xs.len().min(budget);
+                Some(xs).filter(|xs| !xs.iter().any(Value::is_text)).map(|xs| xs.iter().map(to_num).collect())
+            }
             _ => None,
         };
         if categories.is_none()
@@ -248,7 +269,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()

crates/chart/src/tests.rs

@@ -1258,3 +1258,21 @@ 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,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];

crates/engine/src/io.rs

@@ -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);
             }
         }