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/calc/src/recalc.rs

@@ -24,7 +24,7 @@ mod pass_host;
 #[cfg(test)]
 use graph::Intervals;
 pub use graph::{FxHasher, Graph, Key};
-use graph::{HashMap, HashSet, Node, Taken};
+use graph::{HashMap, HashSet, Node};
 use pass_host::{PassHost, spills_as_before};
 
 /// Calculation state kept beside a workbook.
@@ -292,16 +292,17 @@ impl Calc {
                 }
             }
         }
-        // Spill areas of changed anchors also change. They stay rectangles: one seed per spilled
-        // cell listed the formulas reading the area once per cell.
-        let mut areas: Vec<(usize, RangeRef)> = cleared;
+        // Spill areas of changed anchors also change.
         for &k in changed {
             if let Some(r) = wb.sheet(k.0).and_then(|s| s.spill_ranges.get(&k.1)) {
-                areas.push((k.0, *r));
+                seeds.extend(r.iter().map(|c| (k.0, c)));
             }
         }
+        for (si, r) in &cleared {
+            seeds.extend(r.iter().map(|c| (*si, c)));
+        }
         let t0 = prof_now();
-        let dirty = self.dirty_closure(wb, &seeds, &areas);
+        let dirty = self.dirty_closure(wb, &seeds);
         let t1 = prof_now();
         let n = dirty.len();
         self.run(wb, dirty, false);
@@ -310,39 +311,16 @@ impl Calc {
         }
     }
 
-    /// The formulas to recalculate after `seeds` and every cell of `areas` changed: the seeds
-    /// that are formulas, and everything that reads them, directly or through other formulas.
-    fn dirty_closure(&self, wb: &Workbook, seeds: &[Key], areas: &[(usize, RangeRef)]) -> Vec<Key> {
+    fn dirty_closure(&self, _wb: &Workbook, seeds: &[Key]) -> Vec<Key> {
         let mut seen: HashSet<Key> = HashSet::default();
         let mut queue: VecDeque<Key> = VecDeque::new();
-        // Each range-index entry is listed once in the whole walk: many changed cells under one
-        // broad reference (or many formulas inside one) would otherwise list every formula reading
-        // it once per cell, which squared the work.
-        let mut taken = Taken::default();
-        let mut deps = Vec::new();
         for k in seeds {
             if self.graph.nodes.contains_key(k) && seen.insert(*k) {
                 queue.push_back(*k);
             }
-            deps.clear();
-            self.graph.dependents_untaken(k.0, k.1, &mut taken, &mut deps);
-            for d in deps.drain(..) {
-                if seen.insert(d) {
-                    queue.push_back(d);
-                }
-            }
-        }
-        for &(si, r) in areas {
-            if let Some(sh) = wb.sheet(si) {
-                for (c, _) in sh.cells.iter_range(r) {
-                    if self.graph.nodes.contains_key(&(si, c)) && seen.insert((si, c)) {
-                        queue.push_back((si, c));
-                    }
-                }
-            }
-            deps.clear();
-            self.graph.dependents_of_range(si, r, &mut deps);
-            for d in deps.drain(..) {
+            let mut deps = Vec::new();
+            self.graph.dependents(k.0, k.1, &mut deps);
+            for d in deps {
                 if seen.insert(d) {
                     queue.push_back(d);
                 }
@@ -353,9 +331,10 @@ impl Calc {
                 queue.push_back(*k);
             }
         }
+        let mut deps = Vec::new();
         while let Some(k) = queue.pop_front() {
             deps.clear();
-            self.graph.dependents_untaken(k.0, k.1, &mut taken, &mut deps);
+            self.graph.dependents(k.0, k.1, &mut deps);
             for d in deps.drain(..) {
                 if seen.insert(d) {
                     queue.push_back(d);
@@ -432,7 +411,7 @@ impl Calc {
             if spill_changes.is_empty() {
                 break;
             }
-            dirty = self.dirty_closure(wb, &spill_changes, &[]);
+            dirty = self.dirty_closure(wb, &spill_changes);
         }
         // Loops among formulas the run did not evaluate stay listed while they are still formulas.
         // Iterative calculation reports none.
@@ -712,149 +691,6 @@ pub(crate) mod tests {
         assert!(visited < 64, "visited {visited} nodes for no match");
     }
 
-    #[test]
-    fn untaken_queries_list_each_interval_once_in_all() {
-        // 1,000 ranges over every row of 5,000: point queries at every row used to list all 1,000
-        // each time (5 million matches); sharing `taken`, each range is listed once in all.
-        let n = 5_000u32;
-        let mut iv: Intervals<u32> = Intervals::default();
-        for t in 0..1_000 {
-            iv.insert(0, n, t);
-        }
-        for r in 0..n {
-            iv.insert(r, r, 10_000 + r);
-        }
-        iv.settle();
-        let mut taken = Vec::new();
-        let mut listed = Vec::new();
-        for row in 0..=n + 3 {
-            iv.query_untaken(row, row, &mut taken, &mut |t| {
-                listed.push(*t);
-                true
-            });
-        }
-        listed.sort_unstable();
-        let want: Vec<u32> = (0..1_000).chain(10_000..10_000 + n).collect();
-        assert_eq!(listed, want);
-        // An entry the caller declines is offered again.
-        let mut taken = Vec::new();
-        let mut offered = 0;
-        for _ in 0..3 {
-            iv.query_untaken(7, 7, &mut taken, &mut |t| {
-                if *t == 10_007 {
-                    offered += 1;
-                }
-                *t != 10_007
-            });
-        }
-        assert_eq!(offered, 3);
-    }
-
-    #[test]
-    fn dirty_closure_matches_a_walk_of_every_cell() {
-        // Random formulas over single cells, narrow ranges and wide (over 64 columns) ranges, some
-        // removed or left unsettled: the closure equals the one found by listing every dependent
-        // of every changed cell, area cells included, as before `taken` and areas existed.
-        use super::{HashSet, Node};
-        use crate::eval::Area;
-        use std::collections::VecDeque;
-        let mut s = 0x2545_F491_4F6C_DD1D;
-        for case in 0..40 {
-            let mut wb = Workbook::new();
-            let mut calc = Calc::new();
-            let pick = |s: &mut u64, n: u64| (rng(s) % n) as u32;
-            let mut keys: Vec<Key> = Vec::new();
-            for _ in 0..300 {
-                let k = (0, CellRef::new(pick(&mut s, 120), pick(&mut s, 150)));
-                let mut areas = Vec::new();
-                for _ in 0..1 + pick(&mut s, 3) {
-                    let start = CellRef::new(pick(&mut s, 120), pick(&mut s, 150));
-                    let end = match pick(&mut s, 3) {
-                        0 => start,
-                        1 => CellRef::new(start.row + pick(&mut s, 40), start.col + pick(&mut s, 5)),
-                        _ => CellRef::new(start.row + pick(&mut s, 20), start.col + 65 + pick(&mut s, 30)),
-                    };
-                    areas.push(Area { sheet: 0, range: RangeRef::new(start, end) });
-                }
-                if let Some(sh) = wb.sheet_mut(0) {
-                    sh.cells.set(k.1, Cell::formula(Formula::new("=1")));
-                }
-                calc.graph.insert(k, Node { areas, dynamic: false });
-                keys.push(k);
-                if rng(&mut s).is_multiple_of(7) {
-                    calc.graph.settle();
-                }
-            }
-            for _ in 0..30 {
-                let k = keys[(rng(&mut s) % keys.len() as u64) as usize];
-                calc.graph.remove(k);
-                if let Some(sh) = wb.sheet_mut(0) {
-                    sh.cells.remove(k.1);
-                }
-            }
-            if case % 2 == 0 {
-                calc.graph.settle();
-            }
-            let seeds: Vec<Key> = (0..1 + pick(&mut s, 25)).map(|_| (0, CellRef::new(pick(&mut s, 140), pick(&mut s, 220)))).collect();
-            let areas: Vec<(usize, RangeRef)> = (0..pick(&mut s, 3))
-                .map(|_| {
-                    let start = CellRef::new(pick(&mut s, 120), pick(&mut s, 150));
-                    (0, RangeRef::new(start, CellRef::new(start.row + pick(&mut s, 30), start.col + pick(&mut s, 80))))
-                })
-                .collect();
-            let got: HashSet<Key> = calc.dirty_closure(&wb, &seeds, &areas).into_iter().collect();
-            // The walk before: every area cell is a seed, and every cell lists all its dependents.
-            let mut all = seeds.clone();
-            for (si, r) in &areas {
-                all.extend(r.iter().map(|c| (*si, c)));
-            }
-            let mut want: HashSet<Key> = HashSet::default();
-            let mut queue: VecDeque<Key> = VecDeque::new();
-            let mut deps = Vec::new();
-            for k in &all {
-                if calc.graph.nodes.contains_key(k) && want.insert(*k) {
-                    queue.push_back(*k);
-                }
-                deps.clear();
-                calc.graph.dependents(k.0, k.1, &mut deps);
-                queue.extend(deps.iter().copied().filter(|d| want.insert(*d)));
-            }
-            while let Some(k) = queue.pop_front() {
-                deps.clear();
-                calc.graph.dependents(k.0, k.1, &mut deps);
-                queue.extend(deps.iter().copied().filter(|d| want.insert(*d)));
-            }
-            assert_eq!(got, want, "case {case}");
-        }
-    }
-
-    #[test]
-    fn clearing_a_spill_recalculates_formulas_reading_it_once_each() {
-        // 300 formulas read the area an anchor spills into; clearing the anchor changes all of it
-        // and every one of them is recalculated (they were listed once per spilled cell).
-        let mut wb = Workbook::new();
-        let mut calc = Calc::new();
-        let set = |wb: &mut Workbook, calc: &mut Calc, at: CellRef, input: &str| {
-            if let Some(sh) = wb.sheet_mut(0) {
-                if input.is_empty() {
-                    sh.cells.remove(at);
-                } else {
-                    sh.cells.set(at, Cell::formula(Formula::new(input)));
-                }
-            }
-            calc.cells_changed(wb, &[(0, at)]);
-        };
-        set(&mut wb, &mut calc, CellRef::new(0, 0), "=SEQUENCE(2000)");
-        for r in 0..300 {
-            set(&mut wb, &mut calc, CellRef::new(r, 2), "=COUNT(A1:A2000)");
-        }
-        assert_eq!(wb.sheet(0).map(|s| s.value(CellRef::new(299, 2))), Some(Value::Number(2000.0)));
-        set(&mut wb, &mut calc, CellRef::new(0, 0), "");
-        for r in 0..300 {
-            assert_eq!(wb.sheet(0).map(|s| s.value(CellRef::new(r, 2))), Some(Value::Number(0.0)), "row {r}");
-        }
-    }
-
     /// `rows` rows of six numbers (E:J) and `=SUM(E{r}:J{r})` in K.
     fn sum_rows(rows: u32) -> Workbook {
         let mut wb = Workbook::new();

crates/calc/src/recalc/graph.rs

@@ -151,54 +151,6 @@ impl<T: Copy + Ord> Intervals<T> {
         self.walk(1, 0, self.max_end.len() / 2, p, a, f)
     }
 
-    /// [`Intervals::query`] that skips entries an earlier call with the same `taken` already
-    /// took (and whole subtrees of them), so that a series of queries lists each interval once in
-    /// all. `f` answers whether it took the entry; one it declines is offered again later.
-    /// `taken` belongs to this index as it is now; start it empty. Pending insertions (a few at
-    /// most after [`Intervals::settle`]) are offered every time.
-    pub(super) fn query_untaken(&self, a: u32, b: u32, taken: &mut Vec<bool>, f: &mut dyn FnMut(&T) -> bool) {
-        for it in &self.pending {
-            if it.0 <= b && it.1 >= a {
-                f(&it.2);
-            }
-        }
-        let p = self.items.partition_point(|it| it.0 <= b);
-        if p == 0 {
-            return;
-        }
-        if taken.len() != self.max_end.len() {
-            *taken = vec![false; self.max_end.len()];
-        }
-        self.walk_untaken(1, 0, self.max_end.len() / 2, p, a, taken, f);
-    }
-
-    /// Returns whether everything under `node` has now been reported (or is dead).
-    #[allow(clippy::too_many_arguments)]
-    fn walk_untaken(&self, node: usize, lo: usize, hi: usize, p: usize, a: u32, taken: &mut [bool], f: &mut dyn FnMut(&T) -> bool) -> bool {
-        if taken.get(node).copied().unwrap_or(true) {
-            return true;
-        }
-        if lo >= p || self.max_end.get(node).is_none_or(|m| *m < a) {
-            return false;
-        }
-        let done = if hi - lo <= 1 {
-            match (self.items.get(lo), self.dead.get(lo)) {
-                (Some(it), Some(false)) if it.1 >= a => f(&it.2),
-                (Some(_), Some(true)) => true,
-                _ => false,
-            }
-        } else {
-            let mid = lo + (hi - lo) / 2;
-            let left = self.walk_untaken(2 * node, lo, mid, p, a, taken, f);
-            let right = self.walk_untaken(2 * node + 1, mid, hi, p, a, taken, f);
-            left && right
-        };
-        if done && let Some(slot) = taken.get_mut(node) {
-            *slot = true;
-        }
-        done
-    }
-
     fn walk(&self, node: usize, lo: usize, hi: usize, p: usize, a: u32, f: &mut dyn FnMut(&T)) -> usize {
         if lo >= p || self.max_end.get(node).is_none_or(|m| *m < a) {
             return 1;
@@ -216,13 +168,6 @@ impl<T: Copy + Ord> Intervals<T> {
     }
 }
 
-/// Range-index entries one dependency walk has already listed (see [`Graph::dependents_untaken`]).
-#[derive(Default)]
-pub(super) struct Taken {
-    cols: HashMap<(usize, u32), Vec<bool>>,
-    wide: HashMap<usize, Vec<bool>>,
-}
-
 #[derive(Clone, Debug, Default)]
 pub struct Graph {
     pub(super) nodes: HashMap<Key, Node>,
@@ -357,32 +302,6 @@ impl Graph {
         }
     }
 
-    /// [`Graph::dependents`] leaving out the formulas whose range reads an earlier call with the
-    /// same `taken` already listed. A walk over many changed cells that a few broad ranges cover
-    /// then lists those formulas once, instead of once per cell (which squared the work). The
-    /// graph must not change while `taken` is in use.
-    pub(super) fn dependents_untaken(&self, sheet: usize, c: CellRef, taken: &mut Taken, out: &mut Vec<Key>) {
-        if let Some(v) = self.cell_deps.get(&(sheet, c)) {
-            out.extend(v.iter().copied());
-        }
-        if let Some(v) = self.col_deps.get(&(sheet, c.col)) {
-            v.query_untaken(c.row, c.row, taken.cols.entry((sheet, c.col)).or_default(), &mut |k| {
-                out.push(*k);
-                true
-            });
-        }
-        if let Some(v) = self.wide_deps.get(&sheet) {
-            // A wide entry is taken once it covers the cell's column too.
-            v.query_untaken(c.row, c.row, taken.wide.entry(sheet).or_default(), &mut |(c0, c1, k)| {
-                let hit = *c0 <= c.col && c.col <= *c1;
-                if hit {
-                    out.push(*k);
-                }
-                hit
-            });
-        }
-    }
-
     /// Formulas that read any cell of `range` (a formula can be listed more than once).
     pub fn dependents_of_range(&self, sheet: usize, range: RangeRef, out: &mut Vec<Key>) {
         if range.count() <= 4096 {

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