ravenrs_sheet/calc/

recalc.rs

//! Dependency graph and recalculation.
//!
//! The graph maps every formula cell to its static precedents (resolved areas). A reverse index
//! answers "which formulas read this cell?": single-cell precedents in a hash map, ranges as row
//! intervals per column (wide ranges per sheet), each an interval index so a lookup costs
//! O(log n + matches) however many ranges share the column. After an edit, the dirty set is the
//! transitive closure of dependents; it is evaluated in topological order, with on-demand
//! evaluation as a safety net for dynamic references. Cycles produce `#CIRC!` unless iterative
//! calculation is on: then a formula read while it is being evaluated gives its previous value,
//! and the formulas that read one are evaluated again until the loop settles
//! (`PassHost::iterate_loops`).

use std::collections::VecDeque;

use crate::base::{Array, CellError, CellRef, RangeRef, Value};
use crate::formula::Expr;
use crate::model::{CalcMode, Workbook};

use crate::calc::eval::{Evaluator, Host, precedents, stack_position};

mod graph;
mod pass_host;

#[cfg(test)]
use graph::Intervals;
pub use graph::{FxHasher, Graph, Key};
use graph::{HashMap, HashSet, Node, Taken};
use pass_host::{PassHost, spills_as_before};

/// Calculation state kept beside a workbook.
#[derive(Clone, Debug)]
pub struct Calc {
    pub graph: Graph,
    rng: u64,
    /// Fixed "now" for deterministic tests; `None` = system clock.
    pub fixed_now: Option<f64>,
    /// Cells whose formulas have errors from cycles.
    pub circular: Vec<Key>,
    pub last_recalc_cells: usize,
}

impl Default for Calc {
    fn default() -> Self {
        Calc { graph: Graph::default(), rng: 0x9E37_79B9_7F4A_7C15, fixed_now: None, circular: vec![], last_recalc_cells: 0 }
    }
}

/// Pops one finished component off Tarjan's stack, labelling its nodes with `comp_index`. The
/// component is everything up to and including `root`.
fn pop_component(stack: &mut Vec<usize>, on_stack: &mut [bool], comp: &mut [usize], comp_index: usize, root: usize) {
    while let Some(w) = stack.pop() {
        on_stack[w] = false;
        comp[w] = comp_index;
        if w == root {
            break;
        }
    }
}

/// Strongly connected components of a graph given as adjacency lists (Tarjan, iterative): each
/// node's component index, and the number of nodes in each component.
fn components(edges: &[Vec<usize>]) -> (Vec<usize>, Vec<usize>) {
    let n = edges.len();
    let (mut low, mut num) = (vec![0usize; n], vec![usize::MAX; n]);
    let (mut on_stack, mut stack, mut comp) = (vec![false; n], Vec::new(), vec![usize::MAX; n]);
    let (mut next, mut comps) = (0usize, 0usize);
    for root in 0..n {
        if num[root] != usize::MAX {
            continue;
        }
        let mut call: Vec<(usize, usize)> = vec![(root, 0)];
        num[root] = next;
        low[root] = next;
        next += 1;
        stack.push(root);
        on_stack[root] = true;
        while let Some(top) = call.last_mut() {
            let v = top.0;
            if let Some(&w) = edges.get(v).and_then(|e| e.get(top.1)) {
                top.1 += 1;
                if num[w] == usize::MAX {
                    num[w] = next;
                    low[w] = next;
                    next += 1;
                    stack.push(w);
                    on_stack[w] = true;
                    call.push((w, 0));
                } else if on_stack[w] {
                    low[v] = low[v].min(num[w]);
                }
                continue;
            }
            call.pop();
            if let Some(&(u, _)) = call.last() {
                low[u] = low[u].min(low[v]);
            }
            if low[v] == num[v] {
                pop_component(&mut stack, &mut on_stack, &mut comp, comps, v);
                comps += 1;
            }
        }
    }
    let mut size = vec![0usize; comps];
    for &c in &comp {
        if let Some(s) = size.get_mut(c) {
            *s += 1;
        }
    }
    (comp, size)
}

impl Calc {
    pub fn new() -> Self {
        Self::default()
    }

    fn now(&self) -> f64 {
        if let Some(n) = self.fixed_now {
            return n;
        }
        now_serial()
    }

    /// Rebuilds the graph from scratch.
    pub fn rebuild(&mut self, wb: &Workbook) {
        self.graph = Graph::default();
        let mut circ = Vec::new();
        for (si, sheet) in wb.sheets.iter().enumerate() {
            for (c, cell) in sheet.cells.iter() {
                if let Some(f) = &cell.formula
                    && let Some((areas, dynamic)) = f.with_expr(|e| precedents(wb, si, e))
                {
                    self.graph.insert((si, c), Node { areas, dynamic });
                    if cell.value == Value::Error(CellError::Circ) {
                        circ.push((si, c));
                    }
                } else if cell.py.is_some() {
                    // A Python cell lays out its kept result, so it is calculated like a formula
                    // that reads nothing: its spill is blocked and unblocked like a formula's.
                    self.graph.insert((si, c), Node { areas: Vec::new(), dynamic: false });
                }
            }
        }
        self.graph.settle();
        self.circular = if wb.calc.iterative { Vec::new() } else { self.loops_among(&circ) };
    }

    /// The circular references of a rebuilt workbook (after undo, redo or a rollback, which put
    /// back cells without calculating them), from the formulas whose cached value is `#CIRC!`:
    /// the listed cells still on a loop, and one cell of each loop none of them is on.
    fn loops_among(&self, circ: &[Key]) -> Vec<Key> {
        if circ.is_empty() {
            return Vec::new();
        }
        let n = circ.len();
        let index: HashMap<Key, usize> = circ.iter().enumerate().map(|(i, k)| (*k, i)).collect();
        // Edges from a cell to the `#CIRC!` formulas that read it; loops are the same either way.
        let mut deps = Vec::new();
        let edges: Vec<Vec<usize>> = circ
            .iter()
            .map(|k| {
                deps.clear();
                self.graph.dependents(k.0, k.1, &mut deps);
                let mut e: Vec<usize> = deps.iter().filter_map(|d| index.get(d).copied()).collect();
                e.sort_unstable();
                e.dedup();
                e
            })
            .collect();
        // Loop members: nodes in a component of more than one, or with an edge to themselves.
        let (comp, size) = components(&edges);
        let on_loop = |i: usize| comp.get(i).and_then(|c| size.get(*c)).is_some_and(|s| *s > 1) || edges.get(i).is_some_and(|e| e.contains(&i));
        // A formula with dynamic references (INDIRECT, OFFSET) may close a loop the graph can't see.
        let mut out: Vec<Key> =
            self.circular.iter().copied().filter(|k| index.get(k).is_some_and(|&i| on_loop(i) || self.graph.dynamic.contains(k))).collect();
        let mut covered: HashSet<usize> = out.iter().filter_map(|k| index.get(k)).filter_map(|&i| comp.get(i).copied()).collect();
        let mut order: Vec<usize> = (0..n).collect();
        order.sort_by_key(|&i| circ.get(i).map(|(s, c)| (*s, c.row, c.col)));
        for i in order {
            if let (Some(&c), Some(&k)) = (comp.get(i), circ.get(i))
                && on_loop(i)
                && covered.insert(c)
            {
                out.push(k);
            }
        }
        out
    }

    /// Recalculates every formula (F9 / Ctrl+Alt+F9, and after loading).
    pub fn recalc_all(&mut self, wb: &mut Workbook) {
        self.rebuild(wb);
        // Spills are laid out again from the formulas where they are now (a structural edit moves
        // or deletes the formulas, not the values they spilled).
        for i in 0..wb.sheets.len() {
            if wb.sheet(i).is_some_and(|s| !s.spill_ranges.is_empty() || !s.spill.is_empty())
                && let Some(sh) = wb.sheet_mut(i)
            {
                sh.spill.clear();
                sh.spill_ranges.clear();
            }
        }
        let all: Vec<Key> = self.graph.nodes.keys().copied().collect();
        self.run(wb, all, true);
    }

    /// Updates the graph for cells whose content changed and recalculates what depends on them.
    pub fn cells_changed(&mut self, wb: &mut Workbook, changed: &[Key]) {
        let mut cleared: Vec<(usize, RangeRef)> = Vec::new();
        for &k in changed {
            let precedent =
                wb.sheet(k.0).and_then(|s| s.cell(k.1)).and_then(|c| c.formula.as_ref()).and_then(|f| f.with_expr(|e| precedents(wb, k.0, e)));
            let py = wb.sheet(k.0).and_then(|s| s.cell(k.1)).and_then(|c| c.py.as_ref());
            let python = py.is_some();
            // A Python cell whose result (if any) is not an array spills nothing.
            let spills = py.and_then(|p| p.result_value()).is_some_and(|v| matches!(v, Value::Array(_)));
            match precedent {
                Some((areas, dynamic)) => {
                    self.graph.insert(k, Node { areas, dynamic });
                }
                // See `rebuild`: its spill is laid out again from its result when it is calculated.
                None if python => {
                    self.graph.insert(k, Node { areas: Vec::new(), dynamic: false });
                    // New code has no result yet: the spill the cell had (its old result's, or a
                    // formula's) goes, and what read it is recalculated, as for a formula
                    // replaced by a constant.
                    if !spills
                        && let Some(sh) = wb.sheet_mut(k.0)
                        && let Some(r) = sh.spill_ranges.remove(&k.1)
                    {
                        sh.clear_spill(r);
                        cleared.push((k.0, r));
                    }
                }
                None => {
                    self.graph.remove(k);
                    // A formula replaced by a constant (or cleared) takes its spilled values with it.
                    if let Some(sh) = wb.sheet_mut(k.0)
                        && let Some(r) = sh.spill_ranges.remove(&k.1)
                    {
                        for c in r.iter() {
                            sh.spill.remove(&c);
                        }
                        cleared.push((k.0, r));
                    }
                    // A formula that doesn't parse evaluates to #NAME?.
                    if let Some(cell) = wb.sheet_mut(k.0).and_then(|s| s.cells.get_mut(k.1))
                        && cell.formula.is_some()
                    {
                        cell.value = Value::Error(CellError::Name);
                    }
                }
            }
        }
        self.graph.settle();
        if wb.calc.mode == CalcMode::Manual {
            // Only the edited formulas themselves are evaluated.
            let own: Vec<Key> = changed.iter().copied().filter(|k| self.graph.nodes.contains_key(k)).collect();
            self.run(wb, own, false);
            return;
        }
        let mut seeds: Vec<Key> = changed.to_vec();
        let mut emptied: Vec<Key> = Vec::new();
        // Typing into (or clearing) a cell a dynamic array spills over (or would spill over)
        // re-evaluates the anchor, which may now be blocked or unblocked.
        for &k in changed {
            if let Some(sh) = wb.sheet(k.0) {
                for (anchor, r) in &sh.spill_ranges {
                    if *anchor != k.1 && r.contains(k.1) {
                        seeds.push((k.0, *anchor));
                    }
                }
                for (c, cell) in sh.cells.iter_range(RangeRef::new(CellRef::new(k.1.row.saturating_sub(64), k.1.col.saturating_sub(64)), k.1)) {
                    if c != k.1 && cell.value == Value::Error(CellError::Spill) {
                        seeds.push((k.0, c));
                    }
                }
                if !sh.cells.has(k.1) {
                    match emptied.iter_mut().find(|x| x.0 == k.0) {
                        Some(x) => x.1 = CellRef::new(x.1.row.max(k.1.row), x.1.col.max(k.1.col)),
                        None => emptied.push(k),
                    }
                }
            }
        }
        // An emptied cell can unblock an anchor any distance above or to the left of it.
        for (si, end) in emptied {
            for &(s, c) in self.graph.nodes.keys() {
                if s == si && c.row <= end.row && c.col <= end.col && wb.sheet(s).is_some_and(|sh| sh.value(c) == Value::Error(CellError::Spill)) {
                    seeds.push((s, c));
                }
            }
        }
        // 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)) {
                areas.push((k.0, *r));
            }
        }
        let t0 = prof_now();
        let dirty = self.dirty_closure(wb, &seeds, &areas);
        let t1 = prof_now();
        let n = dirty.len();
        self.run(wb, dirty, false);
        if std::env::var_os("GRIDCRAFT_PROFILE").is_some() {
            eprintln!("recalc: {} seeds, closure {} cells {:.1} ms, run {:.1} ms", seeds.len(), n, t1 - t0, prof_now() - t1);
        }
    }

    /// 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);
            }
            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);
                }
            }
        }
        for k in &self.graph.dynamic {
            if seen.insert(*k) {
                queue.push_back(*k);
            }
        }
        while let Some(k) = queue.pop_front() {
            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);
                }
            }
        }
        seen.into_iter().collect()
    }

    /// Evaluates the dirty set and writes results (and spills) back.
    fn run(&mut self, wb: &mut Workbook, mut dirty: Vec<Key>, full: bool) {
        let mut dynamic_again = !self.graph.dynamic.is_empty();
        self.last_recalc_cells = 0;
        for _round in 0..8 {
            if dirty.is_empty() {
                break;
            }
            // Row-major order is a good topological guess; on-demand evaluation fixes the rest.
            dirty.sort_by_key(|(s, c)| (*s, c.row, c.col));
            let mut exprs: HashMap<Key, std::sync::Arc<Expr>> = HashMap::with_capacity_and_hasher(dirty.len(), Default::default());
            for k in &dirty {
                if let Some(e) = wb.sheet(k.0).and_then(|s| s.cell(k.1)).and_then(|c| c.formula.as_ref()).and_then(|f| f.expr_arc()) {
                    exprs.insert(*k, e);
                }
            }
            let python: HashMap<Key, Value> = dirty
                .iter()
                .filter_map(|k| wb.sheet(k.0).and_then(|s| s.cell(k.1)).and_then(|c| c.py.as_ref()).and_then(|p| p.result_value()).map(|v| (*k, v)))
                .collect();
            let now = self.now();
            let mut rng = self.rng;
            let tp = prof_now();
            let (results, spills, cycles) = {
                let mut host = PassHost::new(wb, &exprs, &mut rng, now).with_python(python);
                host.iterate = wb.calc.iterative;
                for k in &dirty {
                    host.calculate(*k);
                }
                if host.iterate && !host.members.is_empty() {
                    let passes = host.iterate_loops(&dirty, wb.calc.max_iterations, wb.calc.max_change);
                    if std::env::var_os("GRIDCRAFT_PROFILE").is_some() {
                        eprintln!("  iterative calculation: {} passes over {} formulas", passes, host.tainted.len());
                    }
                }
                (host.results, host.spills, host.cycles)
            };
            self.rng = rng;
            if std::env::var_os("GRIDCRAFT_PROFILE").is_some() {
                eprintln!("  eval {} formulas {:.1} ms", results.len(), prof_now() - tp);
            }
            let tw = prof_now();
            self.last_recalc_cells += results.len();
            // The loops this round finds replace the ones listed for the formulas it evaluated.
            if !self.circular.is_empty() {
                let evaluated: HashSet<Key> = dirty.iter().copied().collect();
                self.circular.retain(|k| !evaluated.contains(k));
            }
            self.circular.extend(cycles);
            let mut spill_changes = self.write_back(wb, &dirty, results, &spills);
            // Formulas with references only known while evaluating (INDIRECT, OFFSET) may have read
            // a spill area before it was laid out: they are evaluated once more.
            if dynamic_again && !spills.is_empty() {
                dynamic_again = false;
                spill_changes.extend(self.graph.dynamic.iter().copied());
            }
            if full {
                // Everything was already evaluated once; spill dependents need another pass.
            }
            if std::env::var_os("GRIDCRAFT_PROFILE").is_some() {
                eprintln!("  write-back {:.1} ms", prof_now() - tw);
            }
            spill_changes.sort_by_key(|(s, c)| (*s, c.row, c.col));
            spill_changes.dedup();
            if spill_changes.is_empty() {
                break;
            }
            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.
        if wb.calc.iterative {
            self.circular.clear();
        } else {
            self.circular.retain(|k| self.graph.nodes.contains_key(k));
        }
    }

    fn write_back(
        &mut self,
        wb: &mut Workbook,
        dirty: &[Key],
        results: HashMap<Key, Value>,
        spills: &HashMap<Key, std::sync::Arc<Array>>,
    ) -> Vec<Key> {
        let mut spill_changes = Vec::new();
        let mut freed = Vec::new();
        for (key, value) in results {
            let Some(sheet) = wb.sheet_mut(key.0) else { continue };
            if let Some(cell) = sheet.cells.get_mut(key.1)
                && cell.value != value
            {
                cell.value = value;
            }
        }
        for key in dirty {
            let new = spills.get(key);
            let Some(sheet) = wb.sheet_mut(key.0) else { continue };
            let old = sheet.spill_ranges.get(&key.1).copied();
            if old.is_none() && new.is_none() {
                continue;
            }
            // An unchanged spill does not alter any values its dependents read.
            if let (Some(range), Some(array)) = (old, new)
                && spills_as_before(sheet, key.1, range, array)
            {
                continue;
            }
            if let Some(range) = old {
                for cell in range.iter() {
                    sheet.spill.remove(&cell);
                }
                sheet.spill_ranges.remove(&key.1);
            }
            let mut changed_range = old;
            if let Some(array) = new {
                let end = CellRef::new(key.1.row.saturating_add(array.rows as u32 - 1), key.1.col.saturating_add(array.cols as u32 - 1));
                let range = RangeRef::new(key.1, end);
                let blocked = spill_is_blocked(sheet, key.1, range, end);
                if blocked {
                    if let Some(cell) = sheet.cells.get_mut(key.1) {
                        cell.value = Value::Error(CellError::Spill);
                    }
                    let mut blocked_dependents = Vec::new();
                    self.graph.dependents_of_range(key.0, range, &mut blocked_dependents);
                    spill_changes.extend(blocked_dependents.into_iter().filter(|dependent| dependent != key));
                } else {
                    fill_spill(sheet, key.1, range, array);
                    changed_range = Some(changed_range.map_or(range, |previous| previous.union(&range)));
                }
            }
            if let Some(range) = changed_range {
                let mut dependents = Vec::new();
                self.graph.dependents_of_range(key.0, range, &mut dependents);
                let freed_old_range = match (old, sheet.spill_ranges.get(&key.1)) {
                    (Some(previous), Some(current)) => !(current.contains(previous.start) && current.contains(previous.end)),
                    (_, None) => true,
                    (None, Some(_)) => false,
                };
                spill_changes.extend(dependents.into_iter().filter(|dependent| dependent != key || freed_old_range));
            }
            if let Some(previous) = old
                && !sheet.spill_ranges.get(&key.1).is_some_and(|current| current.contains(previous.start) && current.contains(previous.end))
            {
                freed.push((key.0, previous));
            }
        }
        for (sheet_index, range) in freed {
            for &(sheet, cell) in self.graph.nodes.keys() {
                let was_blocked_cell = cell.row <= range.end.row
                    && cell.col <= range.end.col
                    && wb.sheet(sheet).is_some_and(|sheet| sheet.value(cell) == Value::Error(CellError::Spill));
                if sheet == sheet_index && was_blocked_cell {
                    spill_changes.push((sheet, cell));
                }
            }
        }
        spill_changes
    }
}

fn spill_is_blocked(sheet: &crate::model::Sheet, anchor: CellRef, range: RangeRef, end: CellRef) -> bool {
    end.row >= crate::base::MAX_ROWS
        || end.col >= crate::base::MAX_COLS
        || range.iter().any(|cell| cell != anchor && (sheet.cells.has(cell) || sheet.spill.contains_key(&cell)))
        || sheet.merges.iter().any(|merge| merge.intersects(&range))
        || sheet.tables.iter().any(|table| table.range.contains(anchor))
}

fn fill_spill(sheet: &mut crate::model::Sheet, anchor: CellRef, range: RangeRef, array: &Array) {
    for (index, cell) in range.iter().enumerate() {
        if cell != anchor {
            sheet.spill.insert(cell, array.data.get(index).cloned().unwrap_or_default());
        }
    }
    sheet.spill_ranges.insert(anchor, range);
}

/// Current date-time as a serial (1900 system), from the system clock (browser clock on wasm).
/// UTC; the local offset isn't available without platform calls. Falls back to a fixed date only
/// when no clock is available.
pub fn now_serial() -> f64 {
    crate::base::date::unix_now_ms().map_or(46302.5, crate::base::date::serial_from_unix_ms)
}

/// Evaluates a formula in the context of a cell without storing it (conditional formats, data
/// validation, Evaluate Formula, Name Manager previews, the CLI `eval`).
pub fn evaluate(wb: &Workbook, sheet: usize, at: CellRef, formula: &str) -> Value {
    let body = formula.strip_prefix('=').unwrap_or(formula);
    let Ok(expr) = crate::formula::parse(body) else { return Value::Error(CellError::Name) };
    evaluate_expr(wb, sheet, at, &expr)
}

pub fn evaluate_expr(wb: &Workbook, sheet: usize, at: CellRef, expr: &Expr) -> Value {
    let exprs = HashMap::default();
    let mut rng = 0x1234_5678_9ABC_DEF0u64;
    let mut host = PassHost::new(wb, &exprs, &mut rng, now_serial());
    let mut ev = Evaluator::new(&mut host, sheet, at);
    ev.value(expr)
}

fn prof_now() -> f64 {
    crate::base::date::unix_now_ms().unwrap_or(0.0)
}

#[cfg(test)]
pub(crate) mod tests {
    use std::time::Duration;

    use crate::base::{CellRef, RangeRef, Value};
    use crate::model::{Cell, Formula, Workbook};

    use super::{Calc, HashMap, Host, Intervals, Key, PassHost};

    /// xorshift64 for repeatable pseudo-random cases.
    fn rng(state: &mut u64) -> u64 {
        *state ^= *state << 13;
        *state ^= *state >> 7;
        *state ^= *state << 17;
        *state
    }

    fn found(iv: &Intervals<u32>, a: u32, b: u32) -> Vec<u32> {
        let mut v = Vec::new();
        iv.query(a, b, &mut |t| v.push(*t));
        v.sort_unstable();
        v
    }

    /// A 1,000 x 1,000 Python result laid out from A1 in a pass, with the same values already
    /// spilled on the sheet from the last calculation, as a full recalculation finds them.
    fn big_python_spill() -> (Workbook, HashMap<Key, Value>) {
        let n = 1_000usize;
        let data: Vec<Value> = (0..n * n).map(|i| Value::Number(i as f64)).collect();
        let array = crate::base::Array::new(n, n, data.clone()).unwrap();
        let mut wb = Workbook::new();
        let sh = wb.sheet_mut(0).unwrap();
        let anchor = CellRef::new(0, 0);
        let py = crate::model::PyCode::new("big");
        sh.set_cell(anchor, Cell { value: Value::Number(0.0), py: Some(std::sync::Arc::new(py)), ..Cell::default() });
        let area = RangeRef::new(anchor, CellRef::new(n as u32 - 1, n as u32 - 1));
        sh.spill_ranges.insert(anchor, area);
        for (i, c) in area.iter().enumerate().skip(1) {
            sh.spill.insert(c, data[i].clone());
        }
        let mut python = HashMap::default();
        python.insert((0, anchor), Value::Array(std::sync::Arc::new(array)));
        (wb, python)
    }

    #[test]
    fn a_read_beside_a_large_spill_walks_none_of_it() {
        let (wb, python) = big_python_spill();
        let exprs = HashMap::default();
        let mut rng = 1u64;
        let mut host = PassHost::new(&wb, &exprs, &mut rng, 0.0).with_python(python);
        assert_eq!(host.cell_value(0, CellRef::new(0, 0)), Value::Number(0.0));
        // Beside the spill (column ALM, the 1,001st), over the rows it covers.
        let beside = RangeRef::parse("ALM1:ALM1000").unwrap();
        host.spill_visits = 0;
        assert!(host.range_values(0, beside).iter().all(Value::is_empty));
        assert!(host.visit_range(0, beside, &mut |_| true), "a disjoint read takes the fast path");
        assert_eq!(host.spill_visits, 0, "nothing of the spill is walked");
        // A read inside it still sees the spilled values, walking only the cells it reads.
        let inside = RangeRef::parse("B2:C3").unwrap();
        host.spill_visits = 0;
        assert_eq!(host.range_values(0, inside), [1_001.0, 1_002.0, 2_001.0, 2_002.0].map(Value::Number).to_vec());
        assert!(host.spill_visits <= 8, "{}", host.spill_visits);
        assert!(!host.visit_range(0, inside, &mut |_| true), "an overlapping read leaves the block to range_values");
    }

    #[test]
    fn intervals_match_a_linear_scan() {
        let mut iv: Intervals<u32> = Intervals::default();
        let mut model: Vec<(u32, u32, u32)> = Vec::new();
        let mut s = 0x9E37_79B9_7F4A_7C15;
        for step in 0..20_000u32 {
            let roll = rng(&mut s) % 10;
            if roll < 6 || model.is_empty() {
                let r0 = (rng(&mut s) % 500) as u32;
                let r1 = r0 + (rng(&mut s) % 40) as u32;
                if !model.contains(&(r0, r1, step)) {
                    iv.insert(r0, r1, step);
                    model.push((r0, r1, step));
                }
            } else {
                let i = (rng(&mut s) % model.len() as u64) as usize;
                let (r0, r1, t) = model.swap_remove(i);
                iv.remove(r0, r1, t);
                if roll == 9 {
                    // Removed and put back before the next merge.
                    iv.insert(r0, r1, t);
                    model.push((r0, r1, t));
                }
            }
            if rng(&mut s).is_multiple_of(50) {
                iv.settle();
            }
            if step.is_multiple_of(97) {
                let a = (rng(&mut s) % 560) as u32;
                let b = a + (rng(&mut s) % 30) as u32;
                let mut want: Vec<u32> = model.iter().filter(|(r0, r1, _)| *r0 <= b && *r1 >= a).map(|(_, _, t)| *t).collect();
                want.sort_unstable();
                assert_eq!(found(&iv, a, b), want, "rows {a}..={b} at step {step}");
            }
        }
        iv.settle();
        for row in 0..560 {
            let mut want: Vec<u32> = model.iter().filter(|(r0, r1, _)| *r0 <= row && row <= *r1).map(|(_, _, t)| *t).collect();
            want.sort_unstable();
            assert_eq!(found(&iv, row, row), want, "row {row}");
        }
        for (r0, r1, t) in std::mem::take(&mut model) {
            iv.remove(r0, r1, t);
        }
        iv.settle();
        assert!(iv.is_empty());
    }

    #[test]
    fn interval_queries_cost_log_n_plus_matches() {
        // 40k one-row ranges (like =SUM(E1:J1) down a column) and 1k ranges over everything:
        // a point query visits O(log n) tree nodes per match, not every range in the column.
        let n = 40_000u32;
        let mut iv: Intervals<u32> = Intervals::default();
        for r in 0..n {
            iv.insert(r, r, r);
        }
        for t in 0..1_000 {
            iv.insert(0, n, n + t);
        }
        iv.settle();
        let mut worst = 0;
        for row in (0..n).step_by(7) {
            let mut k = 0;
            let visited = iv.query(row, row, &mut |_| k += 1);
            assert_eq!(k, 1_001);
            worst = worst.max(visited);
        }
        // 1,001 matches in a tree of depth 16: well under 4 nodes per match plus the path.
        assert!(worst < 4 * 1_001 + 64, "visited {worst} nodes");
        let mut k = 0;
        let visited = iv.query(n + 1, n + 5, &mut |_| k += 1);
        assert_eq!(k, 0);
        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::calc::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();
        if let Some(sh) = wb.sheet_mut(0) {
            for r in 0..rows {
                for c in 4..10 {
                    sh.cells.set(CellRef::new(r, c), Cell::value(Value::Number(f64::from(r % 97 + c))));
                }
                sh.cells.set(CellRef::new(r, 10), Cell::formula(Formula::new(&format!("=SUM(E{0}:J{0})", r + 1))));
            }
        }
        wb
    }

    /// Opening (full recalc), changing every value of a column, and re-entering every formula.
    fn open_and_bulk_edit(rows: u32) -> Duration {
        let mut wb = sum_rows(rows);
        let mut calc = Calc::new();
        let started = crate::base::date::unix_now_ms().unwrap_or(0.0);
        calc.recalc_all(&mut wb);
        let values: Vec<Key> = (0..rows).map(|r| (0, CellRef::new(r, 4))).collect();
        if let Some(sh) = wb.sheet_mut(0) {
            for (_, c) in &values {
                sh.cells.set(*c, Cell::value(Value::Number(1.0)));
            }
        }
        calc.cells_changed(&mut wb, &values);
        let formulas: Vec<Key> = (0..rows).map(|r| (0, CellRef::new(r, 10))).collect();
        calc.cells_changed(&mut wb, &formulas);
        let ended = crate::base::date::unix_now_ms().unwrap_or(started);
        let elapsed = Duration::from_secs_f64((ended - started).max(0.0) / 1000.0);
        let last = wb.sheet(0).map(|s| s.value(CellRef::new(rows - 1, 10)));
        let r = rows - 1;
        assert_eq!(last, Some(Value::Number(f64::from(1 + (5..10).map(|c| r % 97 + c).sum::<u32>()))));
        elapsed
    }

    #[test]
    fn range_formulas_recalc_and_bulk_edit_correctly() {
        // The values behind the timing test below, checked on every run.
        open_and_bulk_edit(500);
    }

    #[test]
    #[ignore = "timing-sensitive; run with --ignored in release"]
    fn recalc_with_range_formulas_scales_linearly() {
        // Each row's SUM reads a range in the same columns. Recalculating on open used to walk
        // every row per range read (the used range), and finding a cell's dependents scanned
        // every range in its column: 4x the rows took 16x the time. Linear is 4x; allow 8x.
        let best = |rows| (0..3).map(|_| open_and_bulk_edit(rows)).min().unwrap_or_default();
        let small = best(5_000);
        let large = best(20_000);
        assert!(large < small * 8 + Duration::from_millis(100), "5k rows {small:?}, 20k rows {large:?}");
    }

    #[test]
    fn range_dependents_after_edits() {
        // Formulas that read ranges, wide ranges and whole columns, found again after edits.
        let mut wb = Workbook::new();
        let mut calc = Calc::new();
        let set = |wb: &mut Workbook, calc: &mut Calc, at: &str, input: &str| {
            let c = CellRef::parse(at).unwrap();
            let cell = if input.starts_with('=') { Cell::formula(Formula::new(input)) } else { Cell::value(Value::Number(input.parse().unwrap())) };
            wb.sheet_mut(0).unwrap().cells.set(c, cell);
            calc.cells_changed(wb, &[(0, c)]);
        };
        let num = |wb: &Workbook, at: &str| {
            let v = wb.sheet(0).unwrap().value(CellRef::parse(at).unwrap());
            v.as_f64().unwrap_or_else(|| panic!("{at} = {v:?}"))
        };
        set(&mut wb, &mut calc, "A1", "1");
        set(&mut wb, &mut calc, "B2", "2");
        set(&mut wb, &mut calc, "CZ3", "3");
        set(&mut wb, &mut calc, "DA5", "=SUM(A1:B2)");
        set(&mut wb, &mut calc, "DA6", "=SUM(A1:CZ3)");
        set(&mut wb, &mut calc, "DA7", "=SUM(B:B)");
        set(&mut wb, &mut calc, "DA8", "=SUM(2:2)");
        assert_eq!((num(&wb, "DA5"), num(&wb, "DA6"), num(&wb, "DA7"), num(&wb, "DA8")), (3.0, 6.0, 2.0, 2.0));
        set(&mut wb, &mut calc, "B2", "20");
        assert_eq!((num(&wb, "DA5"), num(&wb, "DA6"), num(&wb, "DA7"), num(&wb, "DA8")), (21.0, 24.0, 20.0, 20.0));
        // Re-entering a formula with another range drops the old one.
        set(&mut wb, &mut calc, "DA5", "=SUM(A1:A2)");
        set(&mut wb, &mut calc, "B2", "5");
        assert_eq!(num(&wb, "DA5"), 1.0);
        let mut deps = Vec::new();
        calc.graph.dependents(0, CellRef::parse("B2").unwrap(), &mut deps);
        deps.sort_unstable();
        let at = |s: &str| (0, CellRef::parse(s).unwrap());
        assert_eq!(deps, vec![at("DA6"), at("DA7"), at("DA8")]);
        deps.clear();
        calc.graph.dependents_of_range(0, RangeRef::new(CellRef::parse("A1").unwrap(), CellRef::parse("A9").unwrap()), &mut deps);
        deps.sort_unstable();
        deps.dedup();
        assert_eq!(deps, vec![at("DA5"), at("DA6"), at("DA8")]);
        set(&mut wb, &mut calc, "CZ3", "30");
        assert_eq!(num(&wb, "DA6"), 36.0);
        // Ranges on another sheet.
        wb.sheets.push(std::sync::Arc::new(crate::model::Sheet::new("Data")));
        set(&mut wb, &mut calc, "DA9", "=SUM(Data!A1:A3)+SUM(Data!A:CZ)");
        assert_eq!(num(&wb, "DA9"), 0.0);
        wb.sheet_mut(1).unwrap().cells.set(CellRef::parse("A2").unwrap(), Cell::value(Value::Number(4.0)));
        calc.cells_changed(&mut wb, &[(1, CellRef::parse("A2").unwrap())]);
        assert_eq!(num(&wb, "DA9"), 8.0);
        deps.clear();
        calc.graph.dependents(1, CellRef::parse("A2").unwrap(), &mut deps);
        assert_eq!(deps, vec![at("DA9"), at("DA9")]);
    }

    /// A formula at the nesting limit reading thousands of formulas not calculated yet suspends the
    /// evaluations in progress once, not once per formula read.
    #[test]
    fn wide_read_at_the_nesting_limit_suspends_once() {
        const WIDTH: u32 = 3000;
        let mut wb = Workbook::new();
        let mut exprs = HashMap::default();
        let mut put = |wb: &mut Workbook, at: String, text: String| {
            let at = CellRef::parse(&at).unwrap();
            wb.sheet_mut(0).unwrap().cells.set(at, Cell::formula(Formula::new(&text)));
            exprs.insert((0, at), std::sync::Arc::new(crate::formula::parse(&text[1..]).unwrap()));
        };
        // A1 reads A2, ..., A64 (the 64th formula deep) reads a wide range of formulas.
        for r in 1..64 {
            put(&mut wb, format!("A{r}"), format!("=A{}+1", r + 1));
        }
        put(&mut wb, "A64".to_string(), format!("=SUM(B1:B{WIDTH})"));
        for r in 1..=WIDTH {
            put(&mut wb, format!("B{r}"), format!("={r}*2"));
        }
        let mut rng = 1u64;
        let mut host = PassHost::new(&wb, &exprs, &mut rng, 0.0);
        host.calculate((0, CellRef::parse("A1").unwrap()));
        let total = (WIDTH * (WIDTH + 1)) as f64;
        assert_eq!(host.results.get(&(0, CellRef::parse("A1").unwrap())), Some(&Value::Number(total + 63.0)));
        assert!(host.cycles.is_empty());
        assert!(host.suspensions <= 3, "{} suspensions", host.suspensions);
    }

    /// For tests of `PassHost::visit_range`, which can't be reached from outside this module: the
    /// values it hands over for `range` while the formulas in `pending` (cell, formula) have not been
    /// calculated yet, or `None` when it declines the block.
    pub(crate) fn probe_visit_range(wb: &Workbook, pending: &[(&str, &str)], range: RangeRef) -> Option<Vec<Value>> {
        let mut exprs = HashMap::default();
        for (at, formula) in pending {
            let expr = crate::formula::parse(formula.strip_prefix('=').unwrap_or(formula)).ok()?;
            exprs.insert((0, CellRef::parse(at)?), std::sync::Arc::new(expr));
        }

        // A cell in `pending` is calculated the first time something reads it, which is the state
        // of a real pass partway through; `visit_range` has to cope with the formulas it reads
        // being calculated under it.
        let mut rng = 1u64;
        let mut host = PassHost::new(wb, &exprs, &mut rng, 0.0);

        let mut seen = Vec::new();
        host.visit_range(0, range, &mut |v| {
            seen.push(v.clone());
            true
        })
        .then_some(seen)
    }
}