Find and Replace: bound the text a replacement builds

Each occurrence copied the whole replacement string, so a cell full of
short matches and a long replacement expanded tens of kilobytes of
input into about a gigabyte, in both the case-sensitive and the
case-insensitive paths.

Replacement now builds the new text only while it stays within
Excel's 32,767 characters per cell (counted as UTF-8 bytes, 4 each at
most) and within 256 MiB for the whole command, checking before each
copy. Past either limit the command fails and changes nothing.

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/cmd/edit/find.rs

@@ -104,6 +104,13 @@ pub(super) fn find(s: &mut Session, p: &Json) -> Result<Json> {
     Ok(json!({"cell": c.a1(), "sheet": si, "value": t, "count": hits.len()}))
 }
 
+/// Longest text one replacement may give a cell, in bytes: Excel's 32,767 characters, each up to
+/// four bytes. Every occurrence copies the replacement text, so a short cell full of matches and a
+/// long replacement would otherwise expand to gigabytes.
+const REPLACE_CELL_MAX_BYTES: usize = 32_767 * 4;
+/// Most bytes of replaced text one Replace All builds across all its cells.
+const REPLACE_TOTAL_MAX_BYTES: usize = 256 * 1024 * 1024;
+
 pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
     let what = str_param(p, "what").unwrap_or("").to_string();
     let with = str_param(p, "with").unwrap_or("").to_string();
@@ -119,6 +126,7 @@ pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
     let n = edit(s, |cx| {
         let sheets: Vec<usize> = if workbook { (0..cx.wb.sheets.len()).collect() } else { vec![cx.wb.active_sheet()] };
         let mut n = 0;
+        let mut total = 0usize;
         for si in sheets {
             let cells: Vec<(CellRef, String)> =
                 cx.wb.sheet(si).map(|sh| sh.cells.iter().map(|(c, _)| (c, sh.input_text(c))).collect()).unwrap_or_default();
@@ -130,12 +138,19 @@ pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
                     continue;
                 }
                 let new = if whole {
-                    with.clone()
+                    Some(with.clone()).filter(|w| w.len() <= REPLACE_CELL_MAX_BYTES)
                 } else if case {
-                    text.replace(&what, &with)
+                    replace_cs_within(&text, &what, &with, REPLACE_CELL_MAX_BYTES)
                 } else {
-                    replace_ci(&text, &what, &with)
+                    replace_ci_within(&text, &what, &with, REPLACE_CELL_MAX_BYTES)
                 };
+                let Some(new) = new else {
+                    return Err(EngineError::Other(format!("The replacement makes the text of {} too long.", c.a1())));
+                };
+                total = total.saturating_add(new.len());
+                if total > REPLACE_TOTAL_MAX_BYTES {
+                    return Err(EngineError::Other("The replacements make too much text. Replace in a smaller range.".into()));
+                }
                 // A Python cell's text is its code: the replacement edits the code and the cell
                 // stays a Python cell. Code that would no longer fit in a PY formula is left as it was.
                 let old_py = cx.wb.sheet(si).and_then(|sh| sh.cell(c)).and_then(|x| x.py.clone());
@@ -190,7 +205,37 @@ fn folds_in_place(s: &str) -> bool {
     })
 }
 
+#[cfg(test)]
 pub(super) fn replace_ci(text: &str, what: &str, with: &str) -> String {
+    replace_ci_within(text, what, with, usize::MAX).unwrap_or_default()
+}
+
+/// `text` with every `what` replaced by `with`, or `None` once the result passes `limit` bytes
+/// (checked before each copy, so nothing larger is allocated).
+pub(super) fn replace_cs_within(text: &str, what: &str, with: &str, limit: usize) -> Option<String> {
+    if what.is_empty() {
+        return (text.len() <= limit).then(|| text.to_string());
+    }
+    let mut out = String::new();
+    let mut i = 0;
+    for (pos, m) in text.match_indices(what) {
+        if out.len() + (pos - i) + with.len() > limit {
+            return None;
+        }
+        out.push_str(text.get(i..pos).unwrap_or(""));
+        out.push_str(with);
+        i = pos + m.len();
+    }
+    let rest = text.get(i..).unwrap_or("");
+    if out.len() + rest.len() > limit {
+        return None;
+    }
+    out.push_str(rest);
+    Some(out)
+}
+
+/// Case-insensitive [`replace_cs_within`].
+pub(super) fn replace_ci_within(text: &str, what: &str, with: &str, limit: usize) -> Option<String> {
     let lower = text.to_lowercase();
     let w = what.to_lowercase();
     // Slicing `text` at positions found in `lower` is only sound when folding kept every byte
@@ -198,15 +243,22 @@ pub(super) fn replace_ci(text: &str, what: &str, with: &str) -> String {
     // boundaries (U+212A KELVIN SIGN shrinks 3→1 bytes, U+0130 grows 2→3), where the tail used
     // to be dropped. Those fall back to the case-sensitive replace, as length changes already do.
     if lower.len() != text.len() || w.is_empty() || !folds_in_place(text) || !folds_in_place(what) {
-        return text.replace(what, with);
+        return replace_cs_within(text, what, with, limit);
     }
     let mut out = String::new();
     let mut i = 0;
     while let Some(pos) = lower.get(i..).and_then(|s| s.find(&w)) {
+        if out.len() + pos + with.len() > limit {
+            return None;
+        }
         out.push_str(text.get(i..i + pos).unwrap_or(""));
         out.push_str(with);
         i += pos + w.len();
     }
-    out.push_str(text.get(i..).unwrap_or(""));
-    out
+    let rest = text.get(i..).unwrap_or("");
+    if out.len() + rest.len() > limit {
+        return None;
+    }
+    out.push_str(rest);
+    Some(out)
 }

crates/engine/src/cmd/edit/tests.rs

@@ -353,6 +353,36 @@ fn cut_paste_that_overflows_the_grid_moves_nothing() {
     assert_eq!(get(&mut s, "XFD2")["value"], json!(2.0));
 }
 
+#[test]
+fn replace_refuses_text_that_would_grow_past_a_cell() {
+    // 10,000 matches × a 1,000-character replacement would make a 10 MB cell (and a few such
+    // cells gigabytes); the replacement is refused before that text is built.
+    let mut s = Session::new();
+    s.new_workbook();
+    let long = "a".repeat(10_000);
+    s.execute("range.setValues", json!({"range": "A1", "values": [[long.clone()], ["abc"]]})).unwrap();
+    for case in [false, true] {
+        let err = s.execute("edit.replace", json!({"what": "a", "with": "x".repeat(1_000), "matchCase": case})).expect_err("too long");
+        assert!(err.to_string().contains("too long"), "{err}");
+        assert_eq!(s.execute("cell.get", json!({"cell": "A1"})).unwrap()["value"], json!(long));
+        assert_eq!(s.execute("cell.get", json!({"cell": "A2"})).unwrap()["value"], json!("abc"));
+    }
+    // A replacement that stays within a cell's limit still happens.
+    s.execute("edit.replace", json!({"what": "b", "with": "x".repeat(100)})).unwrap();
+    assert_eq!(s.execute("cell.get", json!({"cell": "A2"})).unwrap()["value"], json!(format!("a{}c", "x".repeat(100))));
+}
+
+#[test]
+fn bounded_replace_stops_at_its_limit() {
+    use super::find::{replace_ci_within, replace_cs_within};
+    assert_eq!(replace_cs_within("abab", "a", "xy", 6).as_deref(), Some("xybxyb"));
+    assert_eq!(replace_cs_within("abab", "a", "xy", 5), None);
+    assert_eq!(replace_ci_within("AbAb", "a", "xy", 6).as_deref(), Some("xybxyb"));
+    assert_eq!(replace_ci_within("AbAb", "a", "xy", 5), None);
+    assert_eq!(replace_cs_within("abc", "z", "", 3).as_deref(), Some("abc"));
+    assert_eq!(replace_cs_within("abc", "z", "", 2), None);
+}
+
 #[test]
 fn replace_case_insensitive() {
     assert_eq!(replace_ci("Apple apple APPLE", "apple", "pear"), "pear pear pear");

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