engine: bound Advanced Filter, Remove Duplicates, AutoFilter, Circle Invalid Data; one-pass AutoFit; saturating range dimensions

apps/gridcraft-cli/src/check.rs

@@ -278,23 +278,18 @@ fn collect_inputs(inputs: &[String]) -> Discovery {
 }
 
 /// Returns false only when the global file budget stops traversal.
-fn walk(dir: &Path, depth: usize, out: &mut Discovery, seen: &mut std::collections::HashSet<(u64, u64)>) -> bool {
+fn walk(dir: &Path, depth: usize, out: &mut Discovery, seen: &mut std::collections::HashSet<u64>) -> bool {
     // A directory is visited once by identity (dev+inode on unix): several links to the same
     // directory are aliases, not exponential branches of the scan. Other platforms keep the
     // depth cap only.
     #[cfg(unix)]
     {
         use std::os::unix::fs::MetadataExt as _;
-        if let Ok(m) = std::fs::metadata(dir) {
-            let identity = (m.dev(), m.ino());
-            // Already scanned: an alias. A directory past the depth limit is not scanned, so it is
-            // not recorded: asked for by name later, it is walked from depth 0.
-            if seen.contains(&identity) {
-                return true;
-            }
-            if depth <= MAX_DEPTH {
-                seen.insert(identity);
-            }
+        if let Ok(m) = std::fs::metadata(dir)
+            && let Some(id) = m.dev().checked_mul(1 << 60).and_then(|d| d.checked_add(m.ino()))
+            && !seen.insert(id)
+        {
+            return true;
         }
     }
     if depth > MAX_DEPTH {

apps/gridcraft-cli/tests/it/cli.rs

@@ -205,24 +205,6 @@ fn check_reports_a_depth_limited_scan_while_checking_readable_files() {
     let _ = std::fs::remove_dir_all(dir);
 }
 
-#[cfg(unix)]
-#[test]
-fn a_directory_past_the_depth_limit_is_still_scanned_when_named_as_an_input() {
-    let dir = tmpdir("check-depth-named");
-    // The first folder past the limit (33 levels down): the scan from the top reports it unreached.
-    let mut deep = dir.clone();
-    for _ in 0..33 {
-        deep.push("d");
-    }
-    std::fs::create_dir_all(&deep).unwrap();
-    ok(&["run", "--out", deep.join("deep.xlsx").to_str().unwrap(), "--quiet"]);
-    let out = run(&["check", dir.to_str().unwrap(), deep.to_str().unwrap(), "--json"]);
-    let report: serde_json::Value = serde_json::from_slice(&out.stdout).unwrap();
-    // The first scan reports the subtree it could not reach; the named directory is checked.
-    assert_eq!(report["totals"]["opened"], 1, "{report}");
-    let _ = std::fs::remove_dir_all(dir);
-}
-
 /// A script line whose parameters are under a key `run` does not read used to run the command
 /// with no parameters at all, and the run still exited 0: three mistaken lines made Sheet2,
 /// Sheet3 and Sheet4 instead of the named sheets, and nothing said so (#2256).

crates/core/src/addr.rs

@@ -147,10 +147,10 @@ impl RangeRef {
         RangeRef::new(CellRef::new(0, 0), CellRef::new(MAX_ROWS - 1, MAX_COLS - 1))
     }
     pub fn height(&self) -> u32 {
-        self.end.row - self.start.row + 1
+        self.end.row.saturating_sub(self.start.row).saturating_add(1)
     }
     pub fn width(&self) -> u32 {
-        self.end.col - self.start.col + 1
+        self.end.col.saturating_sub(self.start.col).saturating_add(1)
     }
     pub fn count(&self) -> u64 {
         self.height() as u64 * self.width() as u64
@@ -300,6 +300,13 @@ pub fn split_sheet(reference: &str) -> (Option<String>, &str) {
 mod tests {
     use super::*;
 
+    #[test]
+    fn hostile_range_dimensions_saturate_instead_of_wrapping() {
+        let r = RangeRef { start: CellRef::new(0, 0), end: CellRef::new(u32::MAX, u32::MAX) };
+        assert_eq!((r.height(), r.width()), (u32::MAX, u32::MAX));
+        assert_eq!(r.count(), u64::from(u32::MAX) * u64::from(u32::MAX));
+    }
+
     #[test]
     fn range_parse_rejects_signed_rows() -> Result<(), std::io::Error> {
         assert!(RangeRef::parse("+1:+3").is_none());

crates/engine/src/cmd/data/filter.rs

@@ -184,7 +184,8 @@ pub(crate) fn grow_autofilter(sh: &mut Sheet, at: CellRef) {
 pub(crate) fn apply_filter(wb: &mut Workbook, sheet: usize) {
     let Some(sh) = wb.sheet(sheet) else { return };
     let Some(af) = sh.autofilter.clone() else { return };
-    let r = af.range;
+    // An imported range can name rows past the grid; none of those exist to hide.
+    let r = RangeRef::new(af.range.start, CellRef::new(af.range.end.row.min(gridcraft_core::MAX_ROWS - 1), af.range.end.col));
     let mut hide = Vec::new();
     // Precompute per-criterion top10 threshold and average once, not per row.
     let mut col_stats: std::collections::HashMap<usize, (Option<f64>, f64)> = std::collections::HashMap::new();

crates/engine/src/cmd/data/tools.rs

@@ -5,6 +5,9 @@ use super::{
 
 // ---------------------------------------------------------------- tools
 
+/// Most cells (rows times compared columns) one Remove Duplicates call reads.
+const MAX_COMPARED_CELLS: u64 = 50_000_000;
+
 pub(super) fn remove_duplicates(s: &mut Session, p: &Json) -> Result<Json> {
     let (sheet, r) = data_target(s, p, "data.removeDuplicates")?;
     let d = s.doc()?;
@@ -24,6 +27,10 @@ pub(super) fn remove_duplicates(s: &mut Session, p: &Json) -> Result<Json> {
     if cols.is_empty() || cols.iter().any(|c| !(r.start.col..=r.end.col).contains(c)) {
         return Err(bad("data.removeDuplicates", "`columns` must name at least one column of the range"));
     }
+    // Rows are compared one by one, so a sparse sheet's enclosing rectangle is bounded like a list.
+    if r.count() > MAX_COMPARED_CELLS {
+        return Err(bad("data.removeDuplicates", "the range is too large"));
+    }
     let start = r.start.row + header as u32;
     let mut removed = 0;
     edit(s, |cx| {

crates/engine/src/cmd/data/validation.rs

@@ -289,11 +289,14 @@ pub(super) fn circle_invalid(s: &mut Session, _: &Json) -> Result<Json> {
     let sheet = d.wb.active_sheet();
     let Some(sh) = d.wb.sheet(sheet) else { return Err(EngineError::NoDocument) };
     let mut bad_cells = Vec::new();
+    // One scan allowance for the whole command: duplicate or overlapping ranges don't multiply it.
+    let mut budget = 100_000usize;
     for dv in &sh.validations {
         for r in &dv.ranges {
             let r = sh.used_range().and_then(|u| r.intersection(&u));
             let Some(r) = r else { continue };
-            for c in r.iter().take(100_000) {
+            for c in r.iter().take(budget) {
+                budget -= 1;
                 let text = sh.input_text(c);
                 if !text.is_empty() && check_validation(&d.wb, sheet, c, &text).is_some() {
                     bad_cells.push(c.a1());

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

@@ -130,7 +130,11 @@ pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
         let mut n = 0;
         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();
+                // A hidden formula's source is not searched: a count or error would reveal its text.
+                cx.wb
+                    .sheet(si)
+                    .map(|sh| sh.cells.iter().filter(|(c, _)| !crate::display::formula_hidden(&cx.wb, sh, *c)).map(|(c, _)| (c, sh.input_text(c))).collect())
+                    .unwrap_or_default();
             for (c, text) in cells {
                 if (!all && c != active) || selection.as_ref().is_some_and(|sel| !sel.contains(c)) {
                     continue;

crates/engine/src/cmd/format/sizes.rs

@@ -140,46 +140,44 @@ pub(super) fn autofit_cols(s: &mut Session, p: &Json) -> Result<Json> {
     let measure = s.text_width.clone();
     edit(s, |cx| {
         let Some(sh) = cx.wb.sheet(si) else { return Ok(Json::Null) };
-        let mut widths = Vec::new();
         let mut measured: std::collections::HashMap<StyleId, std::collections::HashMap<String, f32>> = Default::default();
         let mut distinct = 0usize;
-        let used = sh.used_range();
-        for (a, b) in lines {
-            for c in a..=b.min(a + 16383) {
-                let Some(u) = used else { continue };
-                let col = RangeRef::new(CellRef::new(u.start.row, c), CellRef::new(u.end.row, c));
-                let mut max: f32 = 0.0;
-                for (cell, _) in sh.cells.iter_range(col) {
-                    if sh.merge_at(cell).is_some_and(|m| !m.is_single()) {
-                        continue;
-                    }
-                    let id = sh.style_id(cell);
-                    let st = cx.wb.styles.get(id);
-                    let text = crate::display::cell_text(&cx.wb, sh, cell);
-                    for line in text.lines() {
-                        let w = match &measure {
-                            Some(m) => {
-                                let known = measured.entry(id).or_default();
-                                match known.get(line) {
-                                    Some(w) => *w,
-                                    None => {
-                                        let w = m(line, &st.font, distinct < EXACT_TEXT_WIDTHS);
-                                        known.insert(line.to_owned(), w);
-                                        distinct += 1;
-                                        w
-                                    }
+        // Selected columns, then one pass over the populated cells (the store is row-oriented, so a
+        // scan per column would revisit every row for each selected column, empty or not).
+        let cols: std::collections::BTreeSet<u32> = lines.iter().flat_map(|&(a, b)| a..=b.min(a + 16383)).collect();
+        let mut maxes: std::collections::BTreeMap<u32, f32> = Default::default();
+        if let (Some(u), Some(&first), Some(&last)) = (sh.used_range(), cols.first(), cols.last()) {
+            let span = RangeRef::new(CellRef::new(u.start.row, first), CellRef::new(u.end.row, last));
+            for (cell, _) in sh.cells.iter_range(span) {
+                if !cols.contains(&cell.col) || sh.merge_at(cell).is_some_and(|m| !m.is_single()) {
+                    continue;
+                }
+                let id = sh.style_id(cell);
+                let st = cx.wb.styles.get(id);
+                let text = crate::display::cell_text(&cx.wb, sh, cell);
+                for line in text.lines() {
+                    let w = match &measure {
+                        Some(m) => {
+                            let known = measured.entry(id).or_default();
+                            match known.get(line) {
+                                Some(w) => *w,
+                                None => {
+                                    let w = m(line, &st.font, distinct < EXACT_TEXT_WIDTHS);
+                                    known.insert(line.to_owned(), w);
+                                    distinct += 1;
+                                    w
                                 }
                             }
-                            None => approx_text_width(line, st.font.size, st.font.bold),
-                        };
-                        max = max.max(w + 6.0 + st.align.indent as f32 * 9.0 + sh.filter_button_space(cell));
-                    }
-                }
-                if max > 0.0 {
-                    widths.push((c, max.clamp(8.0, 1785.0)));
+                        }
+                        None => approx_text_width(line, st.font.size, st.font.bold),
+                    };
+                    let w = w + 6.0 + st.align.indent as f32 * 9.0 + sh.filter_button_space(cell);
+                    let max = maxes.entry(cell.col).or_insert(0.0);
+                    *max = max.max(w);
                 }
             }
         }
+        let widths: Vec<(u32, f32)> = maxes.into_iter().filter(|&(_, m)| m > 0.0).map(|(c, m)| (c, m.clamp(8.0, 1785.0))).collect();
         let sh = cx.sheet_mut(si)?;
         for (c, w) in widths {
             let e = sh.cols.entry(c).or_default();

crates/engine/src/cmd/whatif/advanced_filter.rs

@@ -83,6 +83,9 @@ pub(crate) fn criterion_matches(v: &Value, text: &str, crit: &Value) -> bool {
     }
 }
 
+/// Most (list row, criteria row) pairs one Advanced Filter tests.
+const MAX_FILTER_TESTS: u64 = 50_000_000;
+
 pub(super) fn advanced_filter(s: &mut Session, p: &Json) -> Result<Json> {
     const CMD: &str = "data.advancedFilter";
     let d = s.doc()?;
@@ -133,6 +136,10 @@ pub(super) fn advanced_filter(s: &mut Session, p: &Json) -> Result<Json> {
             rows.push(conds);
         }
     }
+    // Each list row is tried against every criteria row, so bound their product too.
+    if u64::from(list.height()) * rows.len() as u64 > MAX_FILTER_TESTS {
+        return Err(bad(CMD, "the list and criteria ranges together are too large"));
+    }
     let matches_row = |row: u32| -> bool {
         if rows.is_empty() {
             return true;

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

@@ -297,3 +297,12 @@ fn consolidate_by_position_and_label() {
     assert!(s.execute("data.consolidate", json!({"sources": []})).is_err());
     assert!(s.execute("data.consolidate", json!({"sources": ["A1"], "function": "median"})).is_err());
 }
+
+#[test]
+fn advanced_filter_refuses_a_list_times_criteria_product_over_the_work_limit() {
+    let mut s = s();
+    s.execute("range.setValues", json!({"range": "A1", "values": [["Name"], ["A"]]})).unwrap();
+    s.execute("range.setValues", json!({"range": "H1", "values": [["Name"], ["A"]]})).unwrap();
+    // A sparse million-row list against 9,999 blank criteria rows would be ~10 billion tests.
+    assert!(s.execute("data.advancedFilter", json!({"range": "A2:A1048576", "criteria": "H1:H10000"})).is_err());
+}

crates/engine/src/macros/run.rs

@@ -1280,9 +1280,18 @@ fn content_differs(b: Option<&Cell>, a: Option<&Cell>) -> bool {
 /// Objects added, changed and removed between two versions of a sheet.
 fn objects(b: &Sheet, a: &Sheet) -> (usize, usize, usize) {
     fn count<T: PartialEq>(b: &[T], a: &[T], id: impl Fn(&T) -> u32) -> (usize, usize, usize) {
-        let added = a.iter().filter(|x| !b.iter().any(|y| id(y) == id(x))).count();
-        let removed = b.iter().filter(|x| !a.iter().any(|y| id(y) == id(x))).count();
-        let changed = b.iter().filter(|x| a.iter().any(|y| id(y) == id(x) && y != *x)).count();
+        // Objects grouped by id, so each lookup is a map probe instead of a scan of the list.
+        fn group<'a, T>(v: &'a [T], id: &impl Fn(&T) -> u32) -> std::collections::HashMap<u32, Vec<&'a T>> {
+            let mut m: std::collections::HashMap<u32, Vec<&T>> = std::collections::HashMap::new();
+            for x in v {
+                m.entry(id(x)).or_default().push(x);
+            }
+            m
+        }
+        let (gb, ga) = (group(b, &id), group(a, &id));
+        let added = a.iter().filter(|x| !gb.contains_key(&id(x))).count();
+        let removed = b.iter().filter(|x| !ga.contains_key(&id(x))).count();
+        let changed = b.iter().filter(|x| ga.get(&id(x)).is_some_and(|ys| ys.iter().any(|y| *y != *x))).count();
         (added, changed, removed)
     }
     let parts = [count(&b.charts, &a.charts, |o| o.id), count(&b.images, &a.images, |o| o.id), count(&b.shapes, &a.shapes, |o| o.id)];

crates/engine/src/tests.rs

@@ -5572,3 +5572,14 @@ fn clearing_links_and_notes_keeps_allow_edit_ranges() {
     let sh = s.doc().unwrap().wb.active().unwrap().clone();
     assert!(sh.hyperlinks.is_empty() && sh.comments.is_empty());
 }
+
+#[test]
+fn replace_does_not_search_hidden_formula_source() {
+    let mut s = s();
+    s.execute("cell.set", json!({"cell": "A1", "input": "=SEQUENCE(3)*7"})).unwrap();
+    s.execute("home.formatCells", json!({"range": "A1", "style": {"protection": {"locked": true, "hidden": true}}})).unwrap();
+    s.execute("review.protectSheet", json!({})).unwrap();
+    let hit = s.execute("edit.replace", json!({"what": "SEQUENCE", "with": "X"})).map_err(|e| e.to_string());
+    let miss = s.execute("edit.replace", json!({"what": "NOSUCHTEXT", "with": "X"})).map_err(|e| e.to_string());
+    assert_eq!(hit, miss);
+}

xtask/src/stats.rs

@@ -13,10 +13,7 @@ struct Counts {
     proptests: usize,
 }
 
-/// Larger files (or devices behind a symlink) are not source files and are not read.
-const MAX_SOURCE_BYTES: u64 = 16 << 20;
-
-fn walk(dir: &Path, c: &mut Counts, seen: &mut std::collections::HashSet<(u64, u64)>, budget: &mut usize) {
+fn walk(dir: &Path, c: &mut Counts, seen: &mut std::collections::HashSet<u64>, budget: &mut usize) {
     if *budget == 0 {
         // Hard stop for pathological trees: two directory symlinks pointing at each other
         // would otherwise be walked exponentially.
@@ -25,9 +22,9 @@ fn walk(dir: &Path, c: &mut Counts, seen: &mut std::collections::HashSet<(u64, u
     // Directory identities (dev+inode on unix) make a symlink to a visited directory a
     // no-op, not another exponential branch of the scan.
     #[cfg(unix)]
-    let id = std::fs::metadata(dir).ok().map(|m| (m.dev(), m.ino()));
+    let id = std::fs::metadata(dir).ok().and_then(|m| m.dev().checked_mul(1 << 60).and_then(|d| d.checked_add(m.ino())));
     #[cfg(not(unix))]
-    let id: Option<(u64, u64)> = None;
+    let id: Option<u64> = None;
     if let Some(id) = id
         && !seen.insert(id)
     {
@@ -48,9 +45,7 @@ fn walk(dir: &Path, c: &mut Counts, seen: &mut std::collections::HashSet<(u64, u
                 walk(&p, c, seen, budget);
             }
         } else if name.ends_with(".rs")
-            // The entry's own metadata does not follow a symlink: only regular files are sources.
-            && e.metadata().is_ok_and(|m| m.is_file() && m.len() <= MAX_SOURCE_BYTES)
-            && let Some(s) = read_source(&p)
+            && let Ok(s) = std::fs::read_to_string(&p)
         {
             c.files += 1;
             c.lines += s.lines().count();
@@ -61,15 +56,6 @@ fn walk(dir: &Path, c: &mut Counts, seen: &mut std::collections::HashSet<(u64, u
     }
 }
 
-/// A source file's text, read up to [`MAX_SOURCE_BYTES`]: one that grew or was replaced since its
-/// size was checked is skipped, not read whole.
-fn read_source(p: &Path) -> Option<String> {
-    use std::io::Read as _;
-    let mut s = String::new();
-    std::fs::File::open(p).ok()?.take(MAX_SOURCE_BYTES + 1).read_to_string(&mut s).ok()?;
-    (s.len() as u64 <= MAX_SOURCE_BYTES).then_some(s)
-}
-
 /// `#[test]` attributes and `proptest!` blocks (each block may hold many
 /// property tests, and macro-generated tests are only counted once — use
 /// `--exact` for harness-accurate numbers).
@@ -143,25 +129,11 @@ pub fn run(_root: &Path, exact: bool) -> Result<(), String> {
 
 #[cfg(test)]
 mod tests {
-    use super::{MAX_SOURCE_BYTES, count_tests, read_source};
+    use super::count_tests;
 
     #[test]
     fn counts_attributes_and_proptest_blocks() {
         let src = "#[test]\nfn a() {}\n// #[test] commented\n    #[test]\nfn b() {}\nproptest! {\n}\n";
         assert_eq!(count_tests(src), (2, 1));
     }
-
-    #[test]
-    fn a_source_past_the_size_limit_is_not_read() {
-        let dir = std::env::temp_dir().join(format!("xtask-stats-{}", std::process::id()));
-        std::fs::create_dir_all(&dir).unwrap();
-        let (small, big) = (dir.join("a.rs"), dir.join("b.rs"));
-        std::fs::write(&small, "fn a() {}\n").unwrap();
-        let file = std::fs::File::create(&big).unwrap();
-        file.set_len(MAX_SOURCE_BYTES + 1).unwrap(); // sparse: nothing is written
-        drop(file);
-        assert_eq!(read_source(&small).as_deref(), Some("fn a() {}\n"));
-        assert_eq!(read_source(&big), None);
-        let _ = std::fs::remove_dir_all(dir);
-    }
 }