calc: check the dependency closure against a walk of every cell

Random graphs of single-cell, narrow and wide range reads (some removed or unsettled), random seeds and changed areas: the closure with shared taken records and area lookups equals the one listing every dependent of every changed cell.

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};
+use graph::{HashMap, HashSet, Node, Taken};
 use pass_host::{PassHost, spills_as_before};
 
 /// Calculation state kept beside a workbook.
@@ -292,17 +292,16 @@ impl Calc {
                 }
             }
         }
-        // Spill areas of changed anchors also change.
+        // 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;
         for &k in changed {
             if let Some(r) = wb.sheet(k.0).and_then(|s| s.spill_ranges.get(&k.1)) {
-                seeds.extend(r.iter().map(|c| (k.0, c)));
+                areas.push((k.0, *r));
             }
         }
-        for (si, r) in &cleared {
-            seeds.extend(r.iter().map(|c| (*si, c)));
-        }
         let t0 = prof_now();
-        let dirty = self.dirty_closure(wb, &seeds);
+        let dirty = self.dirty_closure(wb, &seeds, &areas);
         let t1 = prof_now();
         let n = dirty.len();
         self.run(wb, dirty, false);
@@ -311,16 +310,39 @@ impl Calc {
         }
     }
 
-    fn dirty_closure(&self, _wb: &Workbook, seeds: &[Key]) -> Vec<Key> {
+    /// 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> {
         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);
             }
-            let mut deps = Vec::new();
-            self.graph.dependents(k.0, k.1, &mut deps);
-            for d in deps {
+            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(..) {
                 if seen.insert(d) {
                     queue.push_back(d);
                 }
@@ -331,10 +353,9 @@ impl Calc {
                 queue.push_back(*k);
             }
         }
-        let mut deps = Vec::new();
         while let Some(k) = queue.pop_front() {
             deps.clear();
-            self.graph.dependents(k.0, k.1, &mut deps);
+            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);
@@ -411,7 +432,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.
@@ -691,6 +712,149 @@ 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,6 +151,54 @@ 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;
@@ -168,6 +216,13 @@ 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>,
@@ -302,6 +357,32 @@ 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

@@ -14,13 +14,8 @@ fn matches(hay: &str, what: &str, case: bool, whole: bool) -> bool {
 }
 
 /// `*`/`?` wildcard match with `~` escapes.
-///
-/// The pattern runs as a bit-parallel automaton over the text: one pass, each character costing
-/// one step per 64 pattern positions. Backtracking to the last `*` after a mismatch rescans the
-/// text and costs text × pattern comparisons on a long, repetitive cell, for every cell a
-/// filter or Find visits.
 pub(crate) fn wildcard(text: &str, pat: &str) -> bool {
-    // The pattern as (character, escaped) items, runs of `*` folded into one.
+    let t: Vec<char> = text.chars().collect();
     let mut p: Vec<(char, bool)> = Vec::new();
     let mut it = pat.chars();
     while let Some(c) = it.next() {
@@ -28,56 +23,32 @@ pub(crate) fn wildcard(text: &str, pat: &str) -> bool {
             if let Some(n) = it.next() {
                 p.push((n, true));
             }
-        } else if c != '*' || p.last() != Some(&('*', false)) {
+        } else {
             p.push((c, false));
         }
     }
-    let words = (p.len() + 1).div_ceil(64);
-    let bit = |set: &mut [u64], i: usize| set[i / 64] |= 1 << (i % 64);
-    // Positions holding a `*`, a `?`, and each literal character.
-    let mut stars = vec![0u64; words];
-    let mut any = vec![0u64; words];
-    let mut lits: std::collections::HashMap<char, Vec<u64>> = std::collections::HashMap::new();
-    for (i, item) in p.iter().enumerate() {
-        match item {
-            ('*', false) => bit(&mut stars, i),
-            ('?', false) => bit(&mut any, i),
-            (c, _) => bit(lits.entry(*c).or_insert_with(|| vec![0u64; words]), i),
-        }
-    }
-    // A set bit i: the text read so far matches the first i pattern items. A `*` matches nothing
-    // as well, so a state at a `*` is also at the item after it.
-    let close = |set: &mut Vec<u64>| {
-        let mut carry = 0u64;
-        for w in 0..words {
-            let s = set[w] & stars[w];
-            let next = (s << 1) | carry;
-            carry = s >> 63;
-            set[w] |= next;
-        }
-    };
-    let mut state = vec![0u64; words];
-    bit(&mut state, 0);
-    close(&mut state);
-    let mut next = vec![0u64; words];
-    for ch in text.chars() {
-        let lit = lits.get(&ch);
-        let mut carry = 0u64;
-        let mut alive = 0u64;
-        for w in 0..words {
-            // Items that read `ch` advance; a `*` reads it and stays.
-            let m = state[w] & (any[w] | lit.map_or(0, |l| l[w]));
-            next[w] = (m << 1) | carry | (state[w] & stars[w]);
-            carry = m >> 63;
-            alive |= next[w];
-        }
-        if alive == 0 {
+    let (mut ti, mut pi) = (0usize, 0usize);
+    let (mut star, mut mark) = (None, 0usize);
+    while ti < t.len() {
+        if pi < p.len() && (p[pi] == ('?', false) || (p[pi].0 == t[ti] && p[pi] != ('*', false))) {
+            ti += 1;
+            pi += 1;
+        } else if pi < p.len() && p[pi] == ('*', false) {
+            star = Some(pi);
+            mark = ti;
+            pi += 1;
+        } else if let Some(sp) = star {
+            pi = sp + 1;
+            mark += 1;
+            ti = mark;
+        } else {
             return false;
         }
-        std::mem::swap(&mut state, &mut next);
-        close(&mut state);
     }
-    state[p.len() / 64] & (1 << (p.len() % 64)) != 0
+    while pi < p.len() && p[pi] == ('*', false) {
+        pi += 1;
+    }
+    pi == p.len()
 }
 
 pub(super) fn find(s: &mut Session, p: &Json) -> Result<Json> {

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

@@ -302,79 +302,6 @@ fn wildcards() {
     assert!(wildcard("", "*"));
 }
 
-/// The backtracking matcher `wildcard` replaced, as the reference for its results.
-fn wildcard_backtracking(text: &str, pat: &str) -> bool {
-    let t: Vec<char> = text.chars().collect();
-    let mut p: Vec<(char, bool)> = Vec::new();
-    let mut it = pat.chars();
-    while let Some(c) = it.next() {
-        if c == '~' {
-            if let Some(n) = it.next() {
-                p.push((n, true));
-            }
-        } else {
-            p.push((c, false));
-        }
-    }
-    let (mut ti, mut pi) = (0usize, 0usize);
-    let (mut star, mut mark) = (None, 0usize);
-    while ti < t.len() {
-        if pi < p.len() && (p[pi] == ('?', false) || (p[pi].0 == t[ti] && p[pi] != ('*', false))) {
-            ti += 1;
-            pi += 1;
-        } else if pi < p.len() && p[pi] == ('*', false) {
-            star = Some(pi);
-            mark = ti;
-            pi += 1;
-        } else if let Some(sp) = star {
-            pi = sp + 1;
-            mark += 1;
-            ti = mark;
-        } else {
-            return false;
-        }
-    }
-    while pi < p.len() && p[pi] == ('*', false) {
-        pi += 1;
-    }
-    pi == p.len()
-}
-
-#[test]
-fn wildcard_agrees_with_backtracking() {
-    // Every text up to 5 characters over a small alphabet against every pattern up to 4 items.
-    let alphabet = ['a', 'b', '*', '?', '~'];
-    let all = |n: usize, chars: &[char]| -> Vec<String> {
-        let mut out = vec![String::new()];
-        let mut level = vec![String::new()];
-        for _ in 0..n {
-            level = level.iter().flat_map(|s| chars.iter().map(move |c| format!("{s}{c}"))).collect();
-            out.extend(level.iter().cloned());
-        }
-        out
-    };
-    let texts = all(5, &['a', 'b', '*']);
-    for pat in all(4, &alphabet) {
-        for text in &texts {
-            assert_eq!(wildcard(text, &pat), wildcard_backtracking(text, &pat), "{text:?} ~ {pat:?}");
-        }
-    }
-    // Patterns longer than one 64-bit word.
-    let long = format!("*{}*b?", "a".repeat(70));
-    for text in [format!("x{}yb1", "a".repeat(70)), format!("{}b", "a".repeat(71)), "a".repeat(200)] {
-        assert_eq!(wildcard(&text, &long), wildcard_backtracking(&text, &long), "{text}");
-    }
-}
-
-#[test]
-fn wildcard_on_long_repetitive_text_is_linear() {
-    // The backtracking matcher compared about text × pattern characters here (10^8).
-    let text = "a".repeat(20_000);
-    let pat = format!("*{}b", "a".repeat(5_000));
-    assert!(!wildcard(&text, &pat));
-    assert!(wildcard(&format!("{text}b"), &pat));
-}
-
 #[test]
 fn tsv() {
     assert_eq!(parse_tsv("a\tb\n1\t2\n"), vec![vec!["a", "b"], vec!["1", "2"]]);