diff --git a/crates/calc/src/lib.rs b/crates/calc/src/lib.rs --- a/crates/calc/src/lib.rs +++ b/crates/calc/src/lib.rs @@ -5,6 +5,7 @@ pub mod eval; pub mod recalc; +mod spill_index; mod trimrange; pub use eval::{Area, SPECIAL_FUNCTIONS, is_known_function}; diff --git a/crates/calc/src/recalc.rs b/crates/calc/src/recalc.rs --- a/crates/calc/src/recalc.rs +++ b/crates/calc/src/recalc.rs @@ -18,6 +18,10 @@ use gridcraft_formula::Expr; use gridcraft_model::{CalcMode, Workbook}; use crate::eval::{Area, Evaluator, Host, precedents, stack_position}; +use crate::spill_index::{SpillIndex, indexing_pays}; + +/// Changed cells (in one `cells_changed`) from which a sheet's spill areas may be indexed. +const INDEX_SPILLS_FROM: usize = 16; mod graph; mod pass_host; @@ -243,11 +247,33 @@ impl Calc { let mut emptied: Vec = 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. + // With many changed cells (a paste) a sheet's spill areas are indexed once instead of being + // walked for each one, when registering them costs less than walking them would. + let mut areas = SpillIndex::default(); + let mut strategy: HashMap = HashMap::default(); + let mut at = Vec::new(); 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)); + let indexed = changed.len() > INDEX_SPILLS_FROM + && !sh.spill_ranges.is_empty() + && *strategy.entry(k.0).or_insert_with(|| { + let indexed = indexing_pays(sh.spill_ranges.values(), changed.len()); + if indexed { + for (anchor, r) in &sh.spill_ranges { + areas.insert_rect((k.0, *anchor), *r, false); + } + } + indexed + }); + if indexed { + // Anchor order, as walking `spill_ranges` gives. + areas.meeting(k.0, RangeRef::new(k.1, k.1), &mut at); + seeds.extend(at.iter().filter(|a| **a != k.1).map(|a| (k.0, *a))); + } else { + 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)) { diff --git a/crates/calc/src/recalc/pass_host.rs b/crates/calc/src/recalc/pass_host.rs --- a/crates/calc/src/recalc/pass_host.rs +++ b/crates/calc/src/recalc/pass_host.rs @@ -1,5 +1,6 @@ use super::graph::{HashMap, HashSet, Key}; use super::*; +use crate::spill_index::{Cover, SpillIndex}; /// Formulas a formula may calculate on demand one inside the other (each needing one another's /// value before it is done). Each level takes stack, so a chain deeper than this is suspended and @@ -19,6 +20,8 @@ pub(super) struct PassHost<'a> { in_progress: HashSet, /// New spills found during the pass: anchor → array. pub(super) spills: HashMap>, + /// Where the areas in `spills` are, so a read finds the ones it meets without scanning them all. + spill_index: SpillIndex, /// Used range per sheet: the workbook doesn't change during a pass, and working it out walks /// every row, so once per sheet rather than once per range read. used: HashMap>, @@ -73,6 +76,7 @@ impl<'a> PassHost<'a> { pending: exprs.keys().copied().collect(), in_progress: HashSet::default(), spills: HashMap::default(), + spill_index: SpillIndex::default(), used: HashMap::default(), rng, now, @@ -98,6 +102,30 @@ impl<'a> PassHost<'a> { } } +/// Most spill areas a range read meets before they are checked for overlapping one another by +/// walking all of the pass's spills instead of comparing pairs. +const MAX_UNORDERED_HITS: usize = 16; + +/// Whether an array at `anchor` covers `c`. +fn spill_covers(anchor: CellRef, arr: &Array, c: CellRef) -> bool { + c.row >= anchor.row && c.col >= anchor.col && ((c.row - anchor.row) as usize) < arr.rows && ((c.col - anchor.col) as usize) < arr.cols +} + +/// Whether two of the spill areas anchored at `hits` share a cell inside `range`. +fn spill_hits_overlap(index: &SpillIndex, sheet: usize, hits: &[CellRef], range: RangeRef) -> bool { + let rects: Vec = hits.iter().filter_map(|a| index.area(sheet, *a)).filter(|(_, empty)| !empty).map(|(r, _)| r).collect(); + rects.iter().enumerate().any(|(i, a)| { + rects.iter().skip(i + 1).any(|b| { + a.intersects(b) + && RangeRef::new( + CellRef::new(a.start.row.max(b.start.row), a.start.col.max(b.start.col)), + CellRef::new(a.end.row.min(b.end.row), a.end.col.min(b.end.col)), + ) + .intersects(&range) + }) + }) +} + /// Whether an array result at `k` can't spill: it is in a table, or its area runs off the sheet, /// overlaps merged cells, holds other cells, or another formula's spill (unless that formula is /// recalculated in this pass, and so may spill elsewhere now). @@ -285,6 +313,7 @@ impl PassHost<'_> { // value -- a FILTER matching one row, a SORT or UNIQUE over one item -- so `C1#` // is the 1 x 1 range and `ROWS(C1#)` is 1, as in Excel (#1491). A formula that // returns a scalar never reaches this arm, so it does not become an anchor. + self.spill_index.insert(k, a.rows, a.cols); self.spills.insert(k, a.clone()); a.data.first().cloned().unwrap_or_default() } @@ -295,6 +324,7 @@ impl PassHost<'_> { let v = match self.spills.get(&k) { Some(a) if spill_blocked(self, k, a) => { self.spills.remove(&k); + self.spill_index.remove(k); Value::Error(CellError::Spill) } _ => v, @@ -341,7 +371,11 @@ impl PassHost<'_> { while passes < max_iterations.min(max_passes) && !self.converged(max_change) { self.prev = again.iter().filter_map(|k| self.results.remove(k).map(|v| (*k, v))).collect(); self.pending = set.clone(); - self.spills.retain(|a, _| !set.contains(a)); + let gone: Vec = self.spills.keys().filter(|a| set.contains(a)).copied().collect(); + for a in gone { + self.spills.remove(&a); + self.spill_index.remove(a); + } for k in &again { self.calculate(*k); } @@ -425,17 +459,19 @@ impl Host for PassHost<'_> { if self.pending.contains(&k) || self.results.contains_key(&k) { return self.compute(k); } - // A cell covered by a spill computed in this pass. - for (anchor, arr) in &self.spills { - if anchor.0 == sheet && c.row >= anchor.1.row && c.col >= anchor.1.col { - let (dr, dc) = ((c.row - anchor.1.row) as usize, (c.col - anchor.1.col) as usize); - if dr < arr.rows && dc < arr.cols { - if self.iterate && self.tainted.contains(anchor) { - self.taint = true; - } - return arr.get(dr, dc).cloned().unwrap_or_default(); - } + // A cell covered by a spill computed in this pass. Where several overlap, the first in + // `spills`' iteration order counts, as it always has. + let covering = match self.spill_index.covering(sheet, c) { + Cover::None => None, + Cover::One(a) => self.spills.get_key_value(&(sheet, a)), + Cover::Many => self.spills.iter().find(|(a, arr)| a.0 == sheet && spill_covers(a.1, arr, c)), + }; + if let Some((anchor, arr)) = covering { + let (dr, dc) = ((c.row - anchor.1.row) as usize, (c.col - anchor.1.col) as usize); + if self.iterate && self.tainted.contains(anchor) { + self.taint = true; } + return arr.get(dr, dc).cloned().unwrap_or_default(); } self.wb.sheet(sheet).map(|s| s.value(c)).unwrap_or_default() } @@ -471,41 +507,44 @@ impl Host for PassHost<'_> { } } if !self.spills.is_empty() { - let new: Vec<(usize, Value)> = self - .spills - .iter() - .filter(|(a, _)| a.0 == sheet) - .flat_map(|(a, arr)| { - let mut v = Vec::new(); - for r in 0..arr.rows { - for cc in 0..arr.cols { - let c = CellRef::new(a.1.row.saturating_add(r as u32), a.1.col.saturating_add(cc as u32)); - if c != a.1 && range.contains(c) { - v.push(( - (c.row - range.start.row) as usize * w + (c.col - range.start.col) as usize, - arr.get(r, cc).cloned().unwrap_or_default(), - )); - } - } - } - v - }) - .collect(); + let mut hits = Vec::new(); + self.spill_index.meeting(sheet, range, &mut hits); // Iterating: an array spilled by a formula that read a previous value. - if self.iterate - && self.spills.iter().any(|(a, arr)| { - let end = CellRef::new( - a.1.row.saturating_add((arr.rows as u32).saturating_sub(1)), - a.1.col.saturating_add((arr.cols as u32).saturating_sub(1)), - ); - a.0 == sheet && self.tainted.contains(a) && RangeRef::new(a.1, end).intersects(&range) - }) - { + if self.iterate && hits.iter().any(|a| self.tainted.contains(&(sheet, *a))) { self.taint = true; } - for (i, v) in new { - if let Some(slot) = out.get_mut(i) { - *slot = v; + // Where areas overlap inside the range, the last in `spills`' iteration order wins, + // as it always has; otherwise the order doesn't matter. + let ordered = hits.len() > MAX_UNORDERED_HITS || spill_hits_overlap(&self.spill_index, sheet, &hits, range); + let mut put = |anchor: CellRef, arr: &Array| { + if arr.rows == 0 || arr.cols == 0 { + return; + } + let (r0, c0) = (range.start.row.max(anchor.row), range.start.col.max(anchor.col)); + let r1 = range.end.row.min(anchor.row.saturating_add((arr.rows as u32).saturating_sub(1))); + let c1 = range.end.col.min(anchor.col.saturating_add((arr.cols as u32).saturating_sub(1))); + for r in r0..=r1 { + for cc in c0..=c1 { + if (r, cc) != (anchor.row, anchor.col) + && let Some(slot) = out.get_mut((r - range.start.row) as usize * w + (cc - range.start.col) as usize) + { + *slot = arr.get((r - anchor.row) as usize, (cc - anchor.col) as usize).cloned().unwrap_or_default(); + } + } + } + }; + if ordered { + let wanted: HashSet = hits.iter().map(|a| (sheet, *a)).collect(); + for (a, arr) in &self.spills { + if wanted.contains(a) { + put(a.1, arr); + } + } + } else { + for a in &hits { + if let Some(arr) = self.spills.get(&(sheet, *a)) { + put(*a, arr); + } } } } @@ -524,7 +563,7 @@ impl Host for PassHost<'_> { } // Spilled values sit between the stored cells (and the formulas just calculated may have // produced some): leave such blocks to `range_values`. - if self.spills.keys().any(|a| a.0 == sheet) || sh.spill.range(range.start..=range.end).any(|(c, _)| range.contains(*c)) { + if self.spill_index.has_sheet(sheet) || sh.spill.range(range.start..=range.end).any(|(c, _)| range.contains(*c)) { return false; } for (c, cell) in sh.cells.iter_range(range) { diff --git a/crates/calc/src/spill_index.rs b/crates/calc/src/spill_index.rs new file mode 100644 --- /dev/null +++ b/crates/calc/src/spill_index.rs @@ -0,0 +1,204 @@ +//! A spatial index over spill areas: which areas cover a cell, and which meet a range, without +//! looking at every area. Areas are registered in 16 x 16 cell blocks, so a lookup touches one +//! block (a cell) or the blocks a range covers (a range) rather than every spill on the sheet. + +use crate::recalc::{FxHasher, Key}; +use gridcraft_core::{CellRef, RangeRef}; +use std::hash::BuildHasherDefault; + +type HashMap = std::collections::HashMap>; + +/// Block edge in cells (rows and columns). +const BLOCK: u32 = 16; + +/// One indexed area: its rectangle, and whether it covers no cells (an array with no rows or no +/// columns still meets the ranges its anchor is in, as a 1 x 1 area does for taint tracking). +#[derive(Clone, Copy)] +struct Entry { + rect: RangeRef, + empty: bool, +} + +#[derive(Default)] +struct SheetAreas { + entries: HashMap, + blocks: HashMap<(u32, u32), Vec>, +} + +/// What covers a cell. +pub(crate) enum Cover { + None, + One(CellRef), + /// Several areas overlap here: the caller decides which one counts. + Many, +} + +#[derive(Default)] +pub(crate) struct SpillIndex { + sheets: HashMap, +} + +fn block_span(rect: &RangeRef) -> (u32, u32, u32, u32) { + (rect.start.row / BLOCK, rect.end.row / BLOCK, rect.start.col / BLOCK, rect.end.col / BLOCK) +} + +/// Whether registering `areas` in blocks costs less than checking each of them against each of +/// `lookups` cells would: a few block entries cost about one containment check each. A tall or +/// wide area (a full-height column spill takes 65,536 blocks) is cheaper to test directly. +pub(crate) fn indexing_pays<'a>(areas: impl ExactSizeIterator, lookups: usize) -> bool { + const BLOCK_COST: u64 = 16; + let budget = (lookups as u64).saturating_mul(areas.len() as u64) / BLOCK_COST; + let mut blocks = 0u64; + for r in areas { + let (r0, r1, c0, c1) = block_span(r); + blocks = blocks.saturating_add(u64::from(r1 - r0 + 1) * u64::from(c1 - c0 + 1)); + if blocks > budget { + return false; + } + } + true +} + +impl SpillIndex { + /// Whether any area is indexed on `sheet`. + pub(crate) fn has_sheet(&self, sheet: usize) -> bool { + self.sheets.get(&sheet).is_some_and(|s| !s.entries.is_empty()) + } + + /// Indexes the area an array of `rows` x `cols` anchored at `anchor` covers (replacing the + /// one already indexed for that anchor). + pub(crate) fn insert(&mut self, (sheet, anchor): Key, rows: usize, cols: usize) { + let end = + CellRef::new(anchor.row.saturating_add((rows as u32).saturating_sub(1)), anchor.col.saturating_add((cols as u32).saturating_sub(1))); + self.insert_rect((sheet, anchor), RangeRef::new(anchor, end), rows == 0 || cols == 0); + } + + /// Indexes an area given as a range. + pub(crate) fn insert_rect(&mut self, (sheet, anchor): Key, rect: RangeRef, empty: bool) { + self.remove((sheet, anchor)); + let areas = self.sheets.entry(sheet).or_default(); + let (r0, r1, c0, c1) = block_span(&rect); + for br in r0..=r1 { + for bc in c0..=c1 { + areas.blocks.entry((br, bc)).or_default().push(anchor); + } + } + areas.entries.insert(anchor, Entry { rect, empty }); + } + + pub(crate) fn remove(&mut self, (sheet, anchor): Key) { + let Some(areas) = self.sheets.get_mut(&sheet) else { return }; + let Some(old) = areas.entries.remove(&anchor) else { return }; + let (r0, r1, c0, c1) = block_span(&old.rect); + for br in r0..=r1 { + for bc in c0..=c1 { + if let Some(list) = areas.blocks.get_mut(&(br, bc)) { + list.retain(|a| *a != anchor); + if list.is_empty() { + areas.blocks.remove(&(br, bc)); + } + } + } + } + } + + /// The areas that cover `c`. + pub(crate) fn covering(&self, sheet: usize, c: CellRef) -> Cover { + let Some(areas) = self.sheets.get(&sheet) else { return Cover::None }; + let Some(list) = areas.blocks.get(&(c.row / BLOCK, c.col / BLOCK)) else { return Cover::None }; + let mut found = Cover::None; + for a in list { + if let Some(e) = areas.entries.get(a) + && !e.empty + && e.rect.contains(c) + { + found = match found { + Cover::None => Cover::One(*a), + _ => return Cover::Many, + }; + } + } + found + } + + /// The anchors of the areas whose rectangle meets `range` (an empty area counts through its + /// anchor cell), sorted by anchor. + pub(crate) fn meeting(&self, sheet: usize, range: RangeRef, out: &mut Vec) { + out.clear(); + let Some(areas) = self.sheets.get(&sheet) else { return }; + let (r0, r1, c0, c1) = block_span(&range); + let touched = u64::from(r1 - r0 + 1) * u64::from(c1 - c0 + 1); + if touched > 4 * areas.entries.len() as u64 + 16 { + // A range wider than the areas are many: look at each area once. + out.extend(areas.entries.iter().filter(|(_, e)| e.rect.intersects(&range)).map(|(a, _)| *a)); + } else { + for br in r0..=r1 { + for bc in c0..=c1 { + if let Some(list) = areas.blocks.get(&(br, bc)) { + out.extend(list.iter().copied().filter(|a| areas.entries.get(a).is_some_and(|e| e.rect.intersects(&range)))); + } + } + } + } + out.sort_unstable(); + out.dedup(); + } + + /// The rectangle indexed for `anchor` and whether it covers no cells. + pub(crate) fn area(&self, sheet: usize, anchor: CellRef) -> Option<(RangeRef, bool)> { + self.sheets.get(&sheet)?.entries.get(&anchor).map(|e| (e.rect, e.empty)) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + fn at(r: u32, c: u32) -> CellRef { + CellRef::new(r, c) + } + + #[test] + fn finds_the_areas_covering_a_cell_and_meeting_a_range() { + let mut ix = SpillIndex::default(); + ix.insert((0, at(0, 0)), 40, 3); + ix.insert((0, at(30, 1)), 1, 40); + ix.insert((1, at(0, 0)), 5, 5); + assert!(matches!(ix.covering(0, at(39, 2)), Cover::One(a) if a == at(0, 0))); + assert!(matches!(ix.covering(0, at(30, 2)), Cover::Many)); + assert!(matches!(ix.covering(0, at(40, 0)), Cover::None)); + assert!(matches!(ix.covering(2, at(0, 0)), Cover::None)); + let mut hits = Vec::new(); + ix.meeting(0, RangeRef::new(at(30, 30), at(50, 60)), &mut hits); + assert_eq!(hits, vec![at(30, 1)]); + ix.meeting(0, RangeRef::new(at(0, 0), at(1_000_000, 16_000)), &mut hits); + assert_eq!(hits, vec![at(0, 0), at(30, 1)]); + ix.remove((0, at(30, 1))); + assert!(matches!(ix.covering(0, at(30, 2)), Cover::One(_))); + assert!(ix.has_sheet(1) && !ix.has_sheet(2)); + ix.insert((0, at(0, 0)), 1, 1); + assert!(matches!(ix.covering(0, at(39, 2)), Cover::None)); + } + + #[test] + fn tall_or_wide_areas_are_not_worth_indexing_for_a_small_paste() { + let column = RangeRef::new(at(0, 0), at(1_048_575, 0)); + assert!(!indexing_pays([column].iter(), 17)); + assert!(!indexing_pays([column].iter(), 1_000)); + // Many small areas pay back for a paste of a hundred cells. + let small: Vec = (0..1_000).map(|i| RangeRef::new(at(i * 3, 0), at(i * 3 + 2, 0))).collect(); + assert!(indexing_pays(small.iter(), 100)); + // A big area among many areas is paid for by a big paste. + assert!(indexing_pays([column].iter(), 2_000_000)); + } + + #[test] + fn an_area_without_cells_covers_none_but_is_met_at_its_anchor() { + let mut ix = SpillIndex::default(); + ix.insert((0, at(3, 3)), 0, 4); + assert!(matches!(ix.covering(0, at(3, 3)), Cover::None)); + let mut hits = Vec::new(); + ix.meeting(0, RangeRef::new(at(3, 3), at(3, 3)), &mut hits); + assert_eq!(hits, vec![at(3, 3)]); + } +} diff --git a/crates/calc/src/tests.rs b/crates/calc/src/tests.rs --- a/crates/calc/src/tests.rs +++ b/crates/calc/src/tests.rs @@ -2274,3 +2274,79 @@ fn loan_schedule_residue_keeps_excels_sign() { } assert_eq!(t.get("P7"), Value::Text("".into())); } + +/// A full-height column spill (inside the 10,000,000-cell cap) and a paste of 17 cells elsewhere: +/// the paste must not register the spill's 65,536 blocks, and a paste over the spill must still +/// block it. +fn tall_spill_book() -> T { + let mut t = T::new(); + t.set("A1", "=SEQUENCE(1048576)"); + t.calc.recalc_all(&mut t.wb); + assert_eq!(t.num("A1048576"), 1_048_576.0); + t +} + +fn paste_into(t: &mut T, cells: &[(u32, u32)]) { + let changed: Vec<(usize, CellRef)> = cells.iter().map(|&(r, c)| (0, CellRef::new(r, c))).collect(); + for k in &changed { + t.wb.sheet_mut(0).unwrap().cells.set(k.1, Cell::value(Value::Number(1.0))); + } + t.calc.cells_changed(&mut t.wb, &changed); +} + +#[test] +fn a_paste_beside_a_tall_spill_leaves_it_alone_and_one_over_it_blocks_it() { + let mut t = tall_spill_book(); + let beside: Vec<(u32, u32)> = (0..17).map(|i| (i, 5)).collect(); + paste_into(&mut t, &beside); + assert_eq!(t.num("A1048576"), 1_048_576.0); + let over: Vec<(u32, u32)> = (0..17).map(|i| (500_000 + i, if i == 9 { 0 } else { 5 })).collect(); + paste_into(&mut t, &over); + assert_eq!(t.get("A1"), Value::Error(CellError::Spill)); +} + +/// Probe: `cells_changed` for a 17-cell paste in column F beside the tall spill. +/// `cargo test -p gridcraft-calc --release -- --ignored --nocapture tall_spill_paste_probe` +#[test] +#[ignore] +#[allow(clippy::disallowed_methods)] +fn tall_spill_paste_probe() { + let mut t = tall_spill_book(); + let mut best = std::time::Duration::MAX; + for round in 0..9u32 { + let beside: Vec<(u32, u32)> = (0..17).map(|i| (round * 20 + i, 5)).collect(); + let start = std::time::Instant::now(); + paste_into(&mut t, &beside); + best = best.min(start.elapsed()); + } + eprintln!("tall spill, 17-cell paste beside it: best of 9 = {best:?}"); +} + +#[test] +fn many_spills_are_read_and_blocked_by_a_paste() { + let mut t = T::new(); + // 40 arrays of 3 rows side by side in rows 1-3, and a reader of a range over two of them. + for i in 0..40u32 { + let anchor = CellRef::new(0, 2 * i); + t.wb.sheet_mut(0).unwrap().cells.set(anchor, Cell::formula(Formula::new(&format!("=SEQUENCE(3,1,{})", 10 * i)))); + } + t.set("A10", "=SUM(C1:F3)"); + t.set("A12", "=COUNT(C1:F3)"); + t.set("A11", "=C2*1"); + t.calc.recalc_all(&mut t.wb); + assert_eq!(t.num("A10"), (10 + 11 + 12 + 20 + 21 + 22) as f64); + assert_eq!(t.num("A11"), 11.0); + assert_eq!(t.num("A12"), 6.0); + // Pasting 20 cells (more than one spill's width worth, so the changed set is indexed) over + // the second row of every other array blocks those arrays; the rest are unchanged. + let changed: Vec<(usize, CellRef)> = (0..20u32).map(|i| (0, CellRef::new(1, 4 * i))).collect(); + for k in &changed { + t.wb.sheet_mut(0).unwrap().cells.set(k.1, Cell::value(Value::Number(1.0))); + } + t.calc.cells_changed(&mut t.wb, &changed); + assert_eq!(t.get("E1"), Value::Error(CellError::Spill)); + assert_eq!(t.get("C1"), Value::Number(10.0)); + assert_eq!(t.get("G2"), Value::Number(31.0)); + assert_eq!(t.get("A10"), Value::Error(CellError::Spill)); + assert_eq!(t.num("A12"), 4.0); +}