diff --git a/crates/calc/src/eval.rs b/crates/calc/src/eval.rs --- a/crates/calc/src/eval.rs +++ b/crates/calc/src/eval.rs @@ -13,6 +13,7 @@ use gridcraft_model::Workbook; mod array; mod call; +mod criteria; mod format; mod lambda; mod reference_fns; @@ -115,6 +116,14 @@ pub trait Host { fn visit_range(&mut self, _sheet: usize, _range: RangeRef, _f: &mut dyn FnMut(&Value) -> bool) -> bool { false } + /// A scalar constant, only when reading it cannot calculate a formula or observe a spill. + fn constant_value(&self, _area: Area) -> Option { + None + } + /// Optional pass-local text criteria index; hosts decline formula/spill/iterative ranges. + fn text_criteria_index(&mut self, _range: Area, _target: Area) -> Option> { + None + } /// While a formula is calculated on demand inside another one: `stack_position()` where the /// outermost one started, which the stack budget is counted from. fn stack_top(&self) -> Option { @@ -258,6 +267,18 @@ impl<'h> Evaluator<'h> { if a.range.is_single() { return self.host.cell_value(a.sheet, a.range.start); } + let area = match self.materialized_area(a) { + Ok(area) => area, + Err(e) => return Value::Error(e), + }; + let range = area.range; + let (h, w) = (range.height() as usize, range.width() as usize); + let data = self.host.range_values(a.sheet, range); + Array::new(h, w, data).map(Value::from).unwrap_or(Value::Error(CellError::Value)) + } + + /// The exact area the normal array path reads, including its used-range trimming and cap. + fn materialized_area(&mut self, a: &Area) -> Result { // A reference keeps its size, so the array has its shape and its blanks count // (`=A1:A10`, `SUMPRODUCT(--(A1:A10=""))`). let cells = u64::from(a.range.height()) * u64::from(a.range.width()); @@ -268,10 +289,9 @@ impl<'h> Evaluator<'h> { let range = if full_size { a.range } else { self.trim(a) }; let (h, w) = (range.height() as usize, range.width() as usize); if (h as u64) * (w as u64) > MAX_CELLS { - return Value::Error(CellError::Num); + return Err(CellError::Num); } - let data = self.host.range_values(a.sheet, range); - Array::new(h, w, data).map(Value::from).unwrap_or(Value::Error(CellError::Value)) + Ok(Area { sheet: a.sheet, range }) } /// Trims the bottom/right of an area to the sheet's used range (keeps the top-left so diff --git a/crates/calc/src/eval/call.rs b/crates/calc/src/eval/call.rs --- a/crates/calc/src/eval/call.rs +++ b/crates/calc/src/eval/call.rs @@ -288,6 +288,9 @@ impl<'h> Evaluator<'h> { if let Some(kind) = Agg::of(spec.name) { return self.aggregate(kind, args); } + if let Some(value) = self.indexed_criteria(spec.name, args) { + return Ev::V(value); + } let mut evaluated = Vec::with_capacity(args.len()); // SUMIF/AVERAGEIF: the size of the criteria range (argument 1), which the sum range takes. let mut criteria_shape = None; diff --git a/crates/calc/src/eval/criteria.rs b/crates/calc/src/eval/criteria.rs new file mode 100644 --- /dev/null +++ b/crates/calc/src/eval/criteria.rs @@ -0,0 +1,44 @@ +use super::*; + +impl Evaluator<'_> { + /// Fast path for one literal text equality over constant reference ranges. No expression is + /// evaluated speculatively: a declined call takes the original path in its original order. + pub(super) fn indexed_criteria(&mut self, name: &str, args: &[Expr]) -> Option { + let (range_at, criterion_at, target_at, resize) = match (name, args.len()) { + ("COUNTIF" | "COUNTIFS", 2) => (0, 1, 0, false), + ("SUMIF" | "AVERAGEIF", 2) => (0, 1, 0, false), + ("SUMIF" | "AVERAGEIF", 3) => (0, 1, 2, true), + ("SUMIFS" | "AVERAGEIFS" | "MINIFS" | "MAXIFS", 3) => (1, 2, 0, false), + _ => return None, + }; + let mut range = self.criteria_area(args.get(range_at)?)?; + let mut target = self.criteria_area(args.get(target_at)?)?; + if resize { + target.range = resized_sum_range(target.range, range.range.height(), range.range.width()); + } else if range.range.height() != target.range.height() || range.range.width() != target.range.width() { + return None; + } + range = self.materialized_area(&range).ok()?; + target = self.materialized_area(&target).ok()?; + if range.range.height() != target.range.height() || range.range.width() != target.range.width() { + return None; + } + let criterion = match args.get(criterion_at)? { + Expr::Text(t) => Value::Text(t.clone()), + e @ Expr::Ref(_) => self.host.constant_value(self.criteria_area(e)?)?, + _ => return None, + }; + let key = gridcraft_functions::TextCriteriaIndex::key(&criterion)?; + let index = self.host.text_criteria_index(range, target)?; + Some(index.aggregate(name, &key)) + } + + fn criteria_area(&self, e: &Expr) -> Option { + let Expr::Ref(r) = e else { return None }; + let areas = self.reference_areas(r).ok()?; + match areas.as_slice() { + [area] => Some(*area), + _ => None, + } + } +} 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 @@ -22,6 +22,15 @@ pub(super) struct PassHost<'a> { /// 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>, + /// Optional constant-range indexes live only for this pass. None remembers an ineligible + /// range too, so thousands of calls do not repeatedly check the same formula cells. + text_criteria: HashMap<(Area, Area), Option>>, + /// First requests do not build indexes: running COUNTIF ranges are often used only once. + criteria_seen: HashSet<(Area, Area)>, + criteria_recent: VecDeque<(Area, Area)>, + criteria_cells: u64, + criteria_bytes: usize, + criteria_groups: usize, rng: &'a mut u64, now: f64, cycle: bool, @@ -74,6 +83,12 @@ impl<'a> PassHost<'a> { in_progress: HashSet::default(), spills: HashMap::default(), used: HashMap::default(), + text_criteria: HashMap::default(), + criteria_seen: HashSet::default(), + criteria_recent: VecDeque::new(), + criteria_cells: 0, + criteria_bytes: 0, + criteria_groups: 0, rng, now, cycle: false, @@ -299,6 +314,12 @@ impl PassHost<'_> { } _ => v, }; + if let Some(a) = self.spills.get(&k) { + let area = spill_area(k, a); + // A spill can fill cells that were empty when an index was built. Drop only + // intersecting indexes, so unrelated arrays do not disable criteria acceleration. + self.text_criteria.retain(|(source, target), _| !overlaps(*source, area) && !overlaps(*target, area)); + } self.results.insert(k, v.clone()); v } @@ -366,6 +387,16 @@ impl PassHost<'_> { } } +fn spill_area((sheet, anchor): Key, a: &Array) -> Area { + let end = + CellRef::new(anchor.row.saturating_add((a.rows as u32).saturating_sub(1)), anchor.col.saturating_add((a.cols as u32).saturating_sub(1))); + Area { sheet, range: RangeRef::new(anchor, end) } +} + +fn overlaps(a: Area, b: Area) -> bool { + a.sheet == b.sheet && a.range.intersects(&b.range) +} + /// A legacy (Ctrl+Shift+Enter) array formula's result fitted to the range it was entered in, as /// Excel does: a single row or column repeats across the range, a single value fills it, cells /// past the result show `#N/A`, and a result larger than the range is cut off. @@ -391,6 +422,80 @@ fn fit_to_range(v: Value, range: RangeRef) -> Value { } impl Host for PassHost<'_> { + fn constant_value(&self, area: Area) -> Option { + let sh = self.wb.sheet(area.sheet)?; + if self.iterate || !area.range.is_single() { + return None; + } + // A spill cannot overwrite a nonempty stored constant (spill_blocked). Empty cells + // may be covered by a new spill, so decline them without reading/evaluating anything. + match sh.cell(area.range.start) { + Some(cell) if cell.formula.is_some() || matches!(cell.value, Value::Array(_) | Value::Empty) => None, + Some(cell) => Some(cell.value.clone()), + None => None, + } + } + fn text_criteria_index(&mut self, range: Area, target: Area) -> Option> { + if self.iterate { + return None; + } + let source = self.wb.sheet(range.sheet)?; + let dest = self.wb.sheet(target.sheet)?; + let key = (range, target); + if let Some(index) = self.text_criteria.get(&key) { + return index.clone(); + } + if !self.criteria_seen.contains(&key) { + if self.criteria_recent.len() >= 1_024 + && let Some(old) = self.criteria_recent.pop_front() + { + self.criteria_seen.remove(&old); + } + self.criteria_seen.insert(key); + self.criteria_recent.push_back(key); + return None; + } + // Bound the cells inspected for optional builds, including ineligible ranges. Text + // and group allowances also bound retained keys and per-group/map overhead. Reaching + // any allowance changes no results: the ordinary evaluator remains the fallback. + let cells = u64::from(range.range.height()) * u64::from(range.range.width()); + if self.text_criteria.len() >= 1_024 || self.criteria_cells.saturating_add(cells) > 1_000_000 { + return None; + } + self.criteria_cells += cells; + let constant = |area: Area| { + self.wb + .sheet(area.sheet) + .is_some_and(|sh| sh.cells.iter_range(area.range).all(|(_, cell)| cell.formula.is_none() && !matches!(cell.value, Value::Array(_)))) + }; + let spill_overlaps = |area: Area| { + self.wb.sheet(area.sheet).is_some_and(|sh| { + sh.spill_ranges.values().any(|r| r.intersects(&area.range)) + || sh.spill.range(area.range.start..=area.range.end).any(|(c, _)| area.range.contains(*c)) + }) || self.spills.iter().any(|(k, a)| overlaps(area, spill_area(*k, a))) + }; + let index = if constant(range) && constant(target) && !spill_overlaps(range) && !spill_overlaps(target) { + let cells = source.cells.iter_range(range.range).map(|(at, cell)| { + let target_cell = + CellRef::new(target.range.start.row + at.row - range.range.start.row, target.range.start.col + at.col - range.range.start.col); + (&cell.value, dest.value_ref(target_cell).unwrap_or(&Value::Empty)) + }); + gridcraft_functions::TextCriteriaIndex::new( + cells, + 8_000_000usize.saturating_sub(self.criteria_bytes), + 100_000usize.saturating_sub(self.criteria_groups), + ) + .map(std::sync::Arc::new) + } else { + None + }; + if let Some(index) = &index { + self.criteria_bytes += index.text_bytes(); + self.criteria_groups += index.groups(); + } + self.text_criteria.insert(key, index.clone()); + index + } fn workbook(&self) -> &Workbook { self.wb } @@ -552,3 +657,139 @@ impl Host for PassHost<'_> { (x.wrapping_mul(0x2545_F491_4F6C_DD1D) >> 11) as f64 / (1u64 << 53) as f64 } } + +#[cfg(test)] +mod criteria_tests { + use super::*; + use gridcraft_model::{Cell, Formula}; + + #[test] + fn one_off_running_counts_do_not_exhaust_the_repeated_range_cache() { + let mut wb = Workbook::new(); + let mut exprs = HashMap::default(); + for r in 0..1_500 { + let sh = wb.sheet_mut(0).unwrap(); + sh.cells.set(CellRef::new(r, 0), Cell::value(Value::from(format!("key{r}")))); + sh.cells.set(CellRef::new(r, 1), Cell::value(Value::Number(1.0))); + for (col, text) in [(2, format!("=COUNTIF(A$1:A{0},A{0})", r + 1)), (3, format!("=SUMIF(A$1:A$1500,A{},B$1:B$1500)", r + 1))] { + let at = CellRef::new(r, col); + let formula = Formula::new(&text); + exprs.insert((0, at), formula.expr_arc().unwrap()); + sh.cells.set(at, Cell::formula(formula)); + } + } + let mut rng = 1; + let mut host = PassHost::new(&wb, &exprs, &mut rng, 0.0); + for col in [2, 3] { + for r in 0..1_500 { + let key = (0, CellRef::new(r, col)); + host.calculate(key); + assert_eq!(host.results.get(&key), Some(&Value::Number(1.0))); + } + if col == 2 { + assert_eq!(host.criteria_cells, 0, "one-off ranges spent the build allowance"); + } + } + assert_eq!(host.criteria_cells, 1_500); + assert_eq!(host.text_criteria.len(), 1); + assert!(host.criteria_seen.len() <= 1_024); + } + + #[test] + fn saved_spill_values_are_not_indexed_as_empty_stored_cells() { + let mut wb = Workbook::new(); + let mut exprs = HashMap::default(); + wb.sheet_mut(0).unwrap().cells.set(CellRef::new(0, 0), Cell::formula(Formula::new("={\"header\";\"key\";\"key\"}"))); + for r in 0..3 { + let at = CellRef::new(r, 2); + let formula = Formula::new("=COUNTIF(A2:A3,\"key\")"); + exprs.insert((0, at), formula.expr_arc().unwrap()); + wb.sheet_mut(0).unwrap().cells.set(at, Cell::formula(formula)); + } + Calc::new().recalc_all(&mut wb); + assert_eq!(wb.sheet(0).unwrap().value(CellRef::new(2, 0)), Value::from("key")); + // Only the criteria formulas are dirty in this pass. Their array precedent is saved. + let mut rng = 1; + let mut host = PassHost::new(&wb, &exprs, &mut rng, 0.0); + for r in 0..3 { + let key = (0, CellRef::new(r, 2)); + host.calculate(key); + assert_eq!(host.results.get(&key), Some(&Value::Number(2.0))); + } + assert!(host.spills.is_empty()); + assert_eq!(host.criteria_cells, 2); + assert!(host.text_criteria.values().all(Option::is_none)); + } + + #[test] + fn text_criteria_formulas_index_their_ranges_once_per_pass() { + use crate::eval::Area; + let mut wb = Workbook::new(); + let mut exprs = HashMap::default(); + for r in 0..500 { + wb.sheet_mut(0).unwrap().cells.set(CellRef::new(r, 0), Cell::value(Value::from(format!("key{r}")))); + wb.sheet_mut(0).unwrap().cells.set(CellRef::new(r, 1), Cell::value(Value::Number(f64::from(r)))); + for col in 2..5 { + let at = CellRef::new(r, col); + let formula = Formula::new(&format!("=SUMIF(A$1:A$500,A{},B$1:B$500)", r + 1)); + exprs.insert((0, at), formula.expr_arc().unwrap()); + wb.sheet_mut(0).unwrap().cells.set(at, Cell::formula(formula)); + } + } + let spill_anchor = CellRef::new(0, 25); + let formula = Formula::new("=SEQUENCE(2)"); + exprs.insert((0, spill_anchor), formula.expr_arc().unwrap()); + let sh = wb.sheet_mut(0).unwrap(); + sh.cells.set(spill_anchor, Cell::formula(formula)); + sh.spill.insert(CellRef::new(1, 25), Value::Number(2.0)); + sh.spill_ranges.insert(spill_anchor, RangeRef::parse("Z1:Z2").unwrap()); + let range = Area { sheet: 0, range: RangeRef::parse("A1:A500").unwrap() }; + let target = Area { sheet: 0, range: RangeRef::parse("B1:B500").unwrap() }; + let mut rng = 1; + let mut host = PassHost::new(&wb, &exprs, &mut rng, 0.0); + host.calculate((0, spill_anchor)); + for col in 2..5 { + for r in 0..500 { + let key = (0, CellRef::new(r, col)); + host.calculate(key); + assert_eq!(host.results.get(&key), Some(&Value::Number(f64::from(r)))); + } + } + // Exercise the real evaluator, so bypassing the fast path fails this active guard too. + assert_eq!(host.criteria_cells, 500); + assert_eq!(host.text_criteria.len(), 1); + host.iterate = true; + assert!(host.text_criteria_index(range, target).is_none()); + } + + #[test] + fn a_new_overlapping_spill_invalidates_a_text_criteria_index() { + for source_spills in [false, true] { + let mut wb = Workbook::new(); + let mut exprs = HashMap::default(); + let (anchor, array) = if source_spills { ("A1", "={\"header\";\"key\";\"key\"}") } else { ("B1", "={0;1;2}") }; + for (at, text) in + [("C1", "=SUMIF(A2:A3,\"key\",B2:B3)"), (anchor, array), ("C2", "=SUMIF(A2:A3,\"key\",B2:B3)"), ("C3", "=SUMIF(A2:A3,\"key\",B2:B3)")] + { + let cell = CellRef::parse(at).unwrap(); + let formula = Formula::new(text); + exprs.insert((0, cell), formula.expr_arc().unwrap()); + wb.sheet_mut(0).unwrap().cells.set(cell, Cell::formula(formula)); + } + for r in 1..=2 { + let (col, value) = if source_spills { (1, Value::Number(f64::from(r))) } else { (0, Value::from("key")) }; + wb.sheet_mut(0).unwrap().cells.set(CellRef::new(r, col), Cell::value(value)); + } + let mut rng = 1; + let mut host = PassHost::new(&wb, &exprs, &mut rng, 0.0); + host.calculate((0, CellRef::new(0, 2))); + assert_eq!(host.results.get(&(0, CellRef::new(0, 2))), Some(&Value::Number(0.0))); + host.calculate((0, CellRef::new(1, 2))); + assert_eq!(host.results.get(&(0, CellRef::new(1, 2))), Some(&Value::Number(0.0))); + assert_eq!(host.criteria_cells, 2); + host.calculate((0, CellRef::parse(anchor).unwrap())); + host.calculate((0, CellRef::new(2, 2))); + assert_eq!(host.results.get(&(0, CellRef::new(2, 2))), Some(&Value::Number(3.0))); + } + } +} 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 @@ -7,6 +7,146 @@ fn c(s: &str) -> CellRef { CellRef::parse(s).unwrap() } +/// Synthetic only: two large sheets and a small summary, shaped like #2751's private file. +fn criteria_profile(rows: u32, formula_cols: u32) -> Workbook { + let mut wb = Workbook::new(); + wb.sheets.push(std::sync::Arc::new(gridcraft_model::Sheet::new("Criteria"))); + wb.sheets.push(std::sync::Arc::new(gridcraft_model::Sheet::new("Summary"))); + for r in 0..rows { + let key = format!("Customer-{:05}-North", r % 97); + let data = wb.sheet_mut(0).unwrap(); + data.cells.set(CellRef::new(r, 0), Cell::value(Value::from(key.clone()))); + for col in 1..61 { + data.cells.set(CellRef::new(r, col), Cell::value(Value::Number(1.0))); + } + let sheet = wb.sheet_mut(1).unwrap(); + sheet.cells.set(CellRef::new(r, 0), Cell::value(Value::from(key))); + for col in 1..=formula_cols { + let row = r + 1; + let formula = match col % 3 { + 0 => format!("=COUNTIF(Sheet1!A:A,A{row})"), + 1 => format!("=SUMIF(Sheet1!A$1:A${rows},A{row},Sheet1!B$1:B${rows})"), + _ => format!("=AVERAGEIF(Sheet1!A:A,A{row},Sheet1!B:B)"), + }; + sheet.cells.set(CellRef::new(r, col), Cell::formula(Formula::new(&formula))); + } + } + wb.sheet_mut(1).unwrap().cells.set(CellRef::new(rows + 10, 58), Cell::value(Value::Number(1.0))); + wb.sheet_mut(2).unwrap().cells.set(CellRef::new(6, 16), Cell::value(Value::Number(1.0))); + wb +} + +#[test] +#[cfg(not(target_arch = "wasm32"))] +#[ignore = "timing-sensitive; run with --ignored in release"] +#[allow(clippy::disallowed_methods)] +fn criteria_profile_recalc_finishes() { + for unrelated_array in [false, true] { + let mut wb = criteria_profile(2_860, 58); + if unrelated_array { + let sh = wb.sheet_mut(0).unwrap(); + sh.cells.remove(CellRef::new(1, 25)); + sh.cells.set(CellRef::new(0, 25), Cell::formula(Formula::new("=SEQUENCE(2)"))); + } + let start = std::time::Instant::now(); + Calc::new().recalc_all(&mut wb); + let elapsed = start.elapsed(); + eprintln!("criteria profile (unrelated array={unrelated_array}): {elapsed:?}"); + if unrelated_array { + assert_eq!(wb.sheet(0).unwrap().value(CellRef::new(1, 25)), Value::Number(2.0), "the unrelated array must actually spill"); + } + for r in 0..2_860 { + let count = (2_860 - 1 - r % 97) / 97 + 1; + for col in 1..=58 { + let expected = if col % 3 == 2 { 1.0 } else { f64::from(count) }; + assert_eq!(wb.sheet(1).unwrap().value(CellRef::new(r, col)), Value::Number(expected)); + } + } + assert!(elapsed < std::time::Duration::from_secs(20), "criteria recalc took {elapsed:?}"); + } +} + +#[test] +fn indexed_text_criteria_resize_two_dimensional_targets_and_propagate_errors() { + let mut t = T::new(); + for (at, input) in [ + ("A1", "apple"), + ("B1", "pear"), + ("A2", "APPLE"), + ("B2", "Apple"), + ("B3", "pear"), + ("D5", "1"), + ("E5", "2"), + ("D6", "3"), + ("E6", "4"), + ("D7", "5"), + ("E7", "#N/A"), + ] { + t.set(at, input); + } + t.set("G1", "=SUMIF(A1:B3,\"apple\",D5)"); + t.set("G2", "=AVERAGEIF(A1:B3,\"apple\",D5)"); + t.set("H1", "=SUMIF(A1:B3,\"\"&\"apple\",D5)"); + t.set("H2", "=AVERAGEIF(A1:B3,\"\"&\"apple\",D5)"); + assert_eq!((t.num("G1"), t.num("G2")), (8.0, 8.0 / 3.0)); + assert_eq!((t.get("G1"), t.get("G2")), (t.get("H1"), t.get("H2"))); + t.set("B3", "apple"); + for at in ["G1", "G2", "H1", "H2"] { + assert_eq!(t.get(at), Value::Error(CellError::NA)); + } +} + +#[test] +fn indexed_text_criteria_match_the_scan_after_edits() { + let mut t = T::new(); + // Repeated text, Unicode simple folding, numeric-looking text, blanks, errors, and + // cancellation-sensitive sums. Concatenating the criterion forces the ordinary path. + let keys = ["Apple", "APPLE", "apple", "İ", "i", "i\u{307}", "*", "~", "12", "", "TRUE", "#N/A"]; + let targets = [1e16, 1.0, -1e16, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0]; + for (r, (key, n)) in keys.iter().zip(targets).enumerate() { + let sh = t.wb.sheet_mut(0).unwrap(); + sh.cells.set(CellRef::new(r as u32, 0), Cell::value(Value::from(*key))); + sh.cells.set(CellRef::new(r as u32, 1), Cell::value(Value::Number(n))); + } + t.wb.sheet_mut(0).unwrap().cells.set(c("B12"), Cell::value(Value::Error(CellError::NA))); + let long_criterion = "x".repeat(256); + let criteria = ["apple", "=APPLE", "i", "i\u{307}", "missing", "a*", "~*", "<>apple", "12", "", "TRUE", "#N/A", "é", &long_criterion]; + let names = ["COUNTIF", "COUNTIFS", "SUMIF", "SUMIFS", "AVERAGEIF", "AVERAGEIFS", "MINIFS", "MAXIFS"]; + let mut pairs = Vec::new(); + for (r, key) in criteria.iter().enumerate() { + t.wb.sheet_mut(0).unwrap().cells.set(CellRef::new(r as u32, 3), Cell::value(Value::from(*key))); + for (col, name) in names.iter().enumerate() { + let criterion = format!("D{}", r + 1); + let args = |criterion: &str| match *name { + "COUNTIF" | "COUNTIFS" => format!("A$1:A$12,{criterion}"), + "SUMIF" | "AVERAGEIF" => format!("A$1:A$12,{criterion},B$1:B$12"), + _ => format!("B$1:B$12,A$1:A$12,{criterion}"), + }; + let indexed = CellRef::new(r as u32, 5 + col as u32 * 2); + let scanned = CellRef::new(r as u32, indexed.col + 1); + let sh = t.wb.sheet_mut(0).unwrap(); + sh.cells.set(indexed, Cell::formula(Formula::new(&format!("={name}({})", args(&criterion))))); + sh.cells.set(scanned, Cell::formula(Formula::new(&format!("={name}({})", args(&format!("\"\"&{criterion}")))))); + pairs.push((indexed, scanned)); + } + } + t.calc.recalc_all(&mut t.wb); + let compare = |t: &T| { + for &(indexed, scanned) in &pairs { + let sh = t.wb.sheet(0).unwrap(); + assert_eq!(sh.value(indexed), sh.value(scanned), "{indexed:?}"); + } + }; + compare(&t); + for (at, value) in [("A1", "Pear"), ("B2", "100"), ("D1", "pear"), ("A3", "=\"pear\""), ("A3", "apple")] { + t.set(at, value); + compare(&t); + } + t.wb.calc.iterative = true; + t.calc.recalc_all(&mut t.wb); + compare(&t); +} + struct T { wb: Workbook, calc: Calc, diff --git a/crates/engine/tests/it/criteria_open.rs b/crates/engine/tests/it/criteria_open.rs new file mode 100644 --- /dev/null +++ b/crates/engine/tests/it/criteria_open.rs @@ -0,0 +1,52 @@ +use std::sync::Arc; + +use gridcraft_core::{CellRef, Value}; +use gridcraft_engine::Session; +use gridcraft_model::{Cell, Formula, Sheet, Workbook}; +use serde_json::json; + +#[test] +fn opening_synthetic_criteria_workbook_recalculates_and_accepts_edits() { + let rows = 2_860; + let mut wb = Workbook::new(); + wb.sheets.push(Arc::new(Sheet::new("Criteria"))); + wb.sheets.push(Arc::new(Sheet::new("Summary"))); + for r in 0..rows { + let key = Value::from(format!("Customer-{:05}-North", r % 97)); + let data = wb.sheet_mut(0).unwrap(); + data.cells.set(CellRef::new(r, 0), Cell::value(key.clone())); + data.cells.set(CellRef::new(r, 1), Cell::value(Value::Number(1.0))); + let criteria = wb.sheet_mut(1).unwrap(); + criteria.cells.set(CellRef::new(r, 0), Cell::value(key)); + let row = r + 1; + for (col, formula) in [ + format!("=COUNTIF(Sheet1!A:A,A{row})"), + format!("=SUMIF(Sheet1!A$1:A${rows},A{row},Sheet1!B$1:B${rows})"), + format!("=AVERAGEIF(Sheet1!A:A,A{row},Sheet1!B:B)"), + ] + .into_iter() + .enumerate() + { + criteria.cells.set(CellRef::new(r, col as u32 + 1), Cell::formula(Formula::new(&formula))); + } + } + // Same sheet extents as the reported private file, with fewer formula columns for CI. + wb.sheet_mut(0).unwrap().cells.set(CellRef::new(rows - 1, 60), Cell::value(Value::Number(1.0))); + wb.sheet_mut(1).unwrap().cells.set(CellRef::new(rows + 10, 58), Cell::value(Value::Number(1.0))); + wb.sheet_mut(2).unwrap().cells.set(CellRef::new(6, 16), Cell::value(Value::Number(1.0))); + let bytes = gridcraft_xlsx::write_xlsx(&wb).unwrap(); + let mut session = Session::new(); + session.execute("file.open", json!({"name": "synthetic-2751.xlsx", "base64": gridcraft_engine::io::base64_encode(&bytes)})).unwrap(); + for r in 0..rows { + let sheet = session.doc().unwrap().wb.sheet(1).unwrap(); + let count = f64::from((rows - 1 - r % 97) / 97 + 1); + assert_eq!(sheet.value(CellRef::new(r, 1)), Value::Number(count)); + assert_eq!(sheet.value(CellRef::new(r, 2)), Value::Number(count)); + assert_eq!(sheet.value(CellRef::new(r, 3)), Value::Number(1.0)); + } + session.execute("cell.set", json!({"cell": "B1", "input": "100"})).unwrap(); + let sheet = session.doc().unwrap().wb.sheet(1).unwrap(); + assert_eq!(sheet.value(CellRef::new(0, 1)), Value::Number(30.0)); + assert_eq!(sheet.value(CellRef::new(0, 2)), Value::Number(129.0)); + assert_eq!(sheet.value(CellRef::new(0, 3)), Value::Number(129.0 / 30.0)); +} diff --git a/crates/engine/tests/it/main.rs b/crates/engine/tests/it/main.rs --- a/crates/engine/tests/it/main.rs +++ b/crates/engine/tests/it/main.rs @@ -5,6 +5,7 @@ mod cf_formula_validate; mod chart_area_stacked100; mod chart_workbook_names; mod command_sequence_fuzz; +mod criteria_open; mod cross_sheet_cut; mod csv_export_budget; mod custom_filter_blanks; diff --git a/crates/functions/src/criteria.rs b/crates/functions/src/criteria.rs --- a/crates/functions/src/criteria.rs +++ b/crates/functions/src/criteria.rs @@ -1,6 +1,7 @@ //! Excel criteria (COUNTIF, SUMIFS, DCOUNT…) and wildcard matching. use std::cmp::Ordering; +use std::collections::HashMap; use gridcraft_core::parse::parse_number_text; use gridcraft_core::{CellError, Value, compare_numbers, compare_text}; @@ -9,6 +10,103 @@ use gridcraft_core::{CellError, Value, compare_numbers, compare_text}; /// counts them (😀 is two units); a longer one is `#VALUE!`. const MAX_CRITERION_UTF16_UNITS: usize = 255; +/// A pass-local index for literal text equality in the criteria aggregates. Each bucket folds +/// numbers in their original row-major order, just as SUMIF does after selecting its cells. +/// Numeric, wildcard, blank and comparison criteria still use the ordinary matcher. +#[derive(Default)] +pub struct TextCriteriaIndex { + groups: HashMap, + text_bytes: usize, +} + +#[derive(Default)] +struct TextGroup { + cells: usize, + numbers: usize, + sum: f64, + min: Option, + max: Option, + error: Option, +} + +impl TextCriteriaIndex { + /// The index key only when the existing parser accepts a literal text equality criterion. + /// Fold one character to one character, exactly like the criteria wildcard matcher (not + /// `compare_text`, whose Unicode folding can expand characters). + pub fn key(criterion: &Value) -> Option { + let c = Criterion::parse_arg(criterion).ok()?; + match c.operand { + Operand::Text(t) if c.op == Op::Eq && !t.contains(['*', '?', '~']) => Some(t.chars().map(lower_char).collect()), + _ => None, + } + } + + /// Builds from scalar cells and their aligned targets. `None` means the optional index + /// exceeded its text or group storage allowance; callers use the ordinary calculation. + pub fn new<'a>(cells: impl Iterator, max_text_bytes: usize, max_groups: usize) -> Option { + let mut index = Self::default(); + for (source, target) in cells { + let Value::Text(text) = source else { continue }; + if text.len() > max_text_bytes { + return None; + } + let key: String = text.chars().map(lower_char).collect(); + if !index.groups.contains_key(&key) { + if index.groups.len() >= max_groups { + return None; + } + index.text_bytes = index.text_bytes.checked_add(key.len())?; + if index.text_bytes > max_text_bytes { + return None; + } + } + let group = index.groups.entry(key).or_default(); + group.cells += 1; + match target { + Value::Number(n) => { + group.numbers += 1; + group.sum += n; + group.min = Some(group.min.map_or(*n, |v| v.min(*n))); + group.max = Some(group.max.map_or(*n, |v| v.max(*n))); + } + Value::Error(e) if group.error.is_none() => group.error = Some(*e), + _ => {} + } + } + Some(index) + } + + /// Bytes of folded text retained, for the host's pass-wide index allowance. + pub fn text_bytes(&self) -> usize { + self.text_bytes + } + + /// Number of distinct groups retained, for the host's per-group memory allowance. + pub fn groups(&self) -> usize { + self.groups.len() + } + + /// Answers one of the criteria aggregates for an already-parsed literal text key. + pub fn aggregate(&self, name: &str, key: &str) -> Value { + let empty = TextGroup::default(); + let group = self.groups.get(key).unwrap_or(&empty); + if matches!(name, "COUNTIF" | "COUNTIFS") { + return Value::Number(group.cells as f64); + } + if let Some(e) = group.error { + return Value::Error(e); + } + match name { + "SUMIF" | "SUMIFS" => Value::number(group.sum), + "AVERAGEIF" | "AVERAGEIFS" if group.numbers == 0 => Value::Error(CellError::Div0), + "AVERAGEIF" | "AVERAGEIFS" => Value::number(group.sum / group.numbers as f64), + "MINIFS" => Value::number(group.min.unwrap_or(0.0)), + "MAXIFS" => Value::number(group.max.unwrap_or(0.0)), + _ => Value::Error(CellError::Name), + } + } +} + #[derive(Clone, Copy, Debug, PartialEq, Eq)] enum Op { Eq, @@ -384,6 +482,50 @@ pub(crate) fn lookup_equal(needle: &Value, hay: &Value, wild: bool) -> bool { mod tests { use super::*; + #[test] + fn text_index_matches_the_ordinary_aggregates() { + use crate::util::testutil::{ev, rf, t}; + use gridcraft_core::Array; + + let keys: Vec = + ["apple", "APPLE", "Apple", "İ", "i", "i\u{307}", "é", "É", "12", "", "bad", "bad"].into_iter().map(Value::from).collect(); + let values = vec![ + Value::Number(1e16), + Value::Number(1.0), + Value::Number(-1e16), + Value::Number(4.0), + Value::Number(5.0), + Value::Number(6.0), + Value::Number(7.0), + Value::Bool(true), + Value::Number(9.0), + Value::Empty, + Value::Error(CellError::NA), + Value::Error(CellError::Div0), + ]; + let index = TextCriteriaIndex::new(keys.iter().zip(&values), 1024, 100).unwrap(); + for criterion in ["apple", "=APPLE", "i", "i\u{307}", "é", "missing", "bad"] { + let key = TextCriteriaIndex::key(&Value::from(criterion)).unwrap(); + for name in ["COUNTIF", "COUNTIFS", "SUMIF", "SUMIFS", "AVERAGEIF", "AVERAGEIFS", "MINIFS", "MAXIFS"] { + let source = rf(Value::from(Array::column(keys.clone()))); + let target = rf(Value::from(Array::column(values.clone()))); + let args = match name { + "COUNTIF" | "COUNTIFS" => vec![source, t(criterion)], + "SUMIF" | "AVERAGEIF" => vec![source, t(criterion), target], + _ => vec![target, source, t(criterion)], + }; + assert_eq!(index.aggregate(name, &key), ev(name, args), "{name}: {criterion}"); + } + } + for criterion in ["12", "TRUE", "#N/A", "", "=", "<>apple", "a*", "?", "~*", &"x".repeat(256)] { + assert!(TextCriteriaIndex::key(&Value::from(criterion)).is_none(), "{criterion}"); + } + assert!(TextCriteriaIndex::new(keys.iter().zip(&values), 2, 100).is_none()); + // An exhausted optional cache must not return a partial set of groups. + assert!(TextCriteriaIndex::new(keys.iter().zip(&values), 0, 100).is_none()); + assert!(TextCriteriaIndex::new(keys.iter().zip(&values), 1024, 1).is_none()); + } + fn m(c: &str, v: Value) -> bool { Criterion::parse(&Value::from(c)).matches(&v) } diff --git a/crates/functions/src/lib.rs b/crates/functions/src/lib.rs --- a/crates/functions/src/lib.rs +++ b/crates/functions/src/lib.rs @@ -78,6 +78,7 @@ pub(crate) mod stat; pub(crate) mod text; pub(crate) mod util; +pub use criteria::TextCriteriaIndex; pub use ets::Timeline; pub use stat::{aggregate_values, aggregate_values_k}; diff --git a/docs/target-app-parity.md b/docs/target-app-parity.md --- a/docs/target-app-parity.md +++ b/docs/target-app-parity.md @@ -1,6 +1,6 @@ # Target-app parity: GridCraft vs Microsoft Excel -> **Last reviewed:** 2026-10-11 · **Last updated:** 2026-10-22 · **Change:** minor (several windows: a native window per workbook window, New Window on the same workbook, Arrange All; no score change) · **Target:** Microsoft Excel (Microsoft 365) +> **Last reviewed:** 2026-10-11 · **Last updated:** 2026-10-27 · **Change:** minor (constant-range text criteria indexes; no score change) · **Target:** Microsoft Excel (Microsoft 365) This is the authoritative parity assessment. [`ROADMAP.md`](../ROADMAP.md) summarizes it, [`gaps.md`](gaps.md) lists every shortfall, and the area checklists hold the detail: @@ -207,12 +207,29 @@ Excel recalculates on every core (multi-threaded recalculation), streams large f | Edit → recalc, 100k dependents | ~0.4 s (2026-10-07), target < 100 ms | tens of ms | measured on the owner's machine; #66 since made range-formula recalc linear, not re-timed | | Grid scrolling | virtualised, O(log n) geometry with custom row heights | smooth | measured in code | | Open a ~100 MB XLSX | fails (#175) | opens | user report | +| Full recalc, synthetic #2751 profile (2,860 × 61 data, 165,880 criteria formulas) | 287.02 s → 0.492 s (0.483 s with an unrelated array) | not timed | measured, Windows x64 release build; `cargo test --release -p gridcraft-calc criteria_profile_recalc_finishes -- --ignored --nocapture` | | Whole-sheet operations | Fill and Remove Duplicates on a whole-sheet selection run out of memory or time (fix in PR #152) | fine | open PR | Work: streaming XLSX reader with shared-string and style dedup, multi-threaded recalc of independent chains (native only; WASM stays single-threaded), whole-column reference clamping, a `cargo xtask bench` with fixed workbooks so the numbers become measured. +Literal text equality in COUNTIF/SUMIF/AVERAGEIF and single-pair COUNTIFS/SUMIFS/AVERAGEIFS/ +MINIFS/MAXIFS uses a pass-local index over constant reference ranges. It retains row-major +summation and the criteria matcher's one-character Unicode folding. Formula-containing ranges, +overlapping spills, iterative calculation, numeric/wildcard/comparison criteria, multiple criteria pairs and +computed criteria retain the ordinary evaluator. Cache allowances (one million range cells, +8 MB of folded keys, 100,000 groups to bound per-group/map overhead, 1,024 entries per pass) +fall back without changing results; the cell allowance includes eligibility inspections. +Ranges are admitted on their second request using at most 1,024 recently seen range pairs, +so one-off running counts do not spend the build allowance. A larger interleaved working set +can still miss this optional cache and use the ordinary scan. +The timing above is Windows x64 release, not CPU-pinned, with other builds active during +portions of the baseline run. The synthetic +profile reproduces a criteria recalculation stall; the private XLS workbook and its sampled +`lookup_equal` path have not been verified with this change. File opening still recalculates +synchronously; this does not implement background opening or change the lookup functions. + ## Platforms | Platform | Excel | GridCraft | @@ -334,6 +351,7 @@ The inventory carried over from the 2026-10-07 ROADMAP.md, updated for what land | Date | Change | Summary | |---|---|---| +| 2026-10-27 | minor | Index repeated literal text criteria over constant ranges per recalc pass; synthetic #2751 profile 287.02 s → 0.492 s, with unchanged results, unrelated-spill support and conservative fallbacks | | 2026-10-22 | minor | Several windows on the desktop: a native window per workbook window, New Window on the same workbook, Switch Windows and Arrange All; "one window" removed from UI/UX fidelity, Hardware and the interaction-fidelity discount; no score change | | 2026-10-21 | minor | Page Setup paper sizes: `B4`/`B5`/`B6` are the JIS sizes Japanese Excel uses (ISO B4/B5/B6 by name), and Japanese Postcard, Japanese Double Postcard, the chou/kaku envelopes and A6 are added; PDF MediaBox and `file.print` follow, and the Size menu lists them | | 2026-10-18 | trivial | Stale chart notes: all chart kinds survive XLSX round-trip (PRs #158, #161) and trendlines landed |