mirror of
https://github.com/storytold/gridcraft.git
synced 2026-11-03 00:41:56 -06:00
Compare commits
1
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
 Dylan M. Taylor
|
19c6f70e2a |
+14
-178
@@ -24,7 +24,7 @@ mod pass_host;
|
||||
#[cfg(test)]
|
||||
use graph::Intervals;
|
||||
pub use graph::{FxHasher, Graph, Key};
|
||||
use graph::{HashMap, HashSet, Node, Taken};
|
||||
use graph::{HashMap, HashSet, Node};
|
||||
use pass_host::{PassHost, spills_as_before};
|
||||
|
||||
/// Calculation state kept beside a workbook.
|
||||
@@ -292,16 +292,17 @@ impl Calc {
|
||||
}
|
||||
}
|
||||
}
|
||||
// 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;
|
||||
// Spill areas of changed anchors also change.
|
||||
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));
|
||||
seeds.extend(r.iter().map(|c| (k.0, c)));
|
||||
}
|
||||
}
|
||||
for (si, r) in &cleared {
|
||||
seeds.extend(r.iter().map(|c| (*si, c)));
|
||||
}
|
||||
let t0 = prof_now();
|
||||
let dirty = self.dirty_closure(wb, &seeds, &areas);
|
||||
let dirty = self.dirty_closure(wb, &seeds);
|
||||
let t1 = prof_now();
|
||||
let n = dirty.len();
|
||||
self.run(wb, dirty, false);
|
||||
@@ -310,39 +311,16 @@ impl Calc {
|
||||
}
|
||||
}
|
||||
|
||||
/// 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> {
|
||||
fn dirty_closure(&self, _wb: &Workbook, seeds: &[Key]) -> 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(..) {
|
||||
let mut deps = Vec::new();
|
||||
self.graph.dependents(k.0, k.1, &mut deps);
|
||||
for d in deps {
|
||||
if seen.insert(d) {
|
||||
queue.push_back(d);
|
||||
}
|
||||
@@ -353,9 +331,10 @@ impl Calc {
|
||||
queue.push_back(*k);
|
||||
}
|
||||
}
|
||||
let mut deps = Vec::new();
|
||||
while let Some(k) = queue.pop_front() {
|
||||
deps.clear();
|
||||
self.graph.dependents_untaken(k.0, k.1, &mut taken, &mut deps);
|
||||
self.graph.dependents(k.0, k.1, &mut deps);
|
||||
for d in deps.drain(..) {
|
||||
if seen.insert(d) {
|
||||
queue.push_back(d);
|
||||
@@ -432,7 +411,7 @@ impl Calc {
|
||||
if spill_changes.is_empty() {
|
||||
break;
|
||||
}
|
||||
dirty = self.dirty_closure(wb, &spill_changes, &[]);
|
||||
dirty = self.dirty_closure(wb, &spill_changes);
|
||||
}
|
||||
// Loops among formulas the run did not evaluate stay listed while they are still formulas.
|
||||
// Iterative calculation reports none.
|
||||
@@ -712,149 +691,6 @@ pub(crate) mod tests {
|
||||
assert!(visited < 64, "visited {visited} nodes for no match");
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn untaken_queries_list_each_interval_once_in_all() {
|
||||
// 1,000 ranges over every row of 5,000: point queries at every row used to list all 1,000
|
||||
// each time (5 million matches); sharing `taken`, each range is listed once in all.
|
||||
let n = 5_000u32;
|
||||
let mut iv: Intervals<u32> = Intervals::default();
|
||||
for t in 0..1_000 {
|
||||
iv.insert(0, n, t);
|
||||
}
|
||||
for r in 0..n {
|
||||
iv.insert(r, r, 10_000 + r);
|
||||
}
|
||||
iv.settle();
|
||||
let mut taken = Vec::new();
|
||||
let mut listed = Vec::new();
|
||||
for row in 0..=n + 3 {
|
||||
iv.query_untaken(row, row, &mut taken, &mut |t| {
|
||||
listed.push(*t);
|
||||
true
|
||||
});
|
||||
}
|
||||
listed.sort_unstable();
|
||||
let want: Vec<u32> = (0..1_000).chain(10_000..10_000 + n).collect();
|
||||
assert_eq!(listed, want);
|
||||
// An entry the caller declines is offered again.
|
||||
let mut taken = Vec::new();
|
||||
let mut offered = 0;
|
||||
for _ in 0..3 {
|
||||
iv.query_untaken(7, 7, &mut taken, &mut |t| {
|
||||
if *t == 10_007 {
|
||||
offered += 1;
|
||||
}
|
||||
*t != 10_007
|
||||
});
|
||||
}
|
||||
assert_eq!(offered, 3);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn dirty_closure_matches_a_walk_of_every_cell() {
|
||||
// Random formulas over single cells, narrow ranges and wide (over 64 columns) ranges, some
|
||||
// removed or left unsettled: the closure equals the one found by listing every dependent
|
||||
// of every changed cell, area cells included, as before `taken` and areas existed.
|
||||
use super::{HashSet, Node};
|
||||
use crate::eval::Area;
|
||||
use std::collections::VecDeque;
|
||||
let mut s = 0x2545_F491_4F6C_DD1D;
|
||||
for case in 0..40 {
|
||||
let mut wb = Workbook::new();
|
||||
let mut calc = Calc::new();
|
||||
let pick = |s: &mut u64, n: u64| (rng(s) % n) as u32;
|
||||
let mut keys: Vec<Key> = Vec::new();
|
||||
for _ in 0..300 {
|
||||
let k = (0, CellRef::new(pick(&mut s, 120), pick(&mut s, 150)));
|
||||
let mut areas = Vec::new();
|
||||
for _ in 0..1 + pick(&mut s, 3) {
|
||||
let start = CellRef::new(pick(&mut s, 120), pick(&mut s, 150));
|
||||
let end = match pick(&mut s, 3) {
|
||||
0 => start,
|
||||
1 => CellRef::new(start.row + pick(&mut s, 40), start.col + pick(&mut s, 5)),
|
||||
_ => CellRef::new(start.row + pick(&mut s, 20), start.col + 65 + pick(&mut s, 30)),
|
||||
};
|
||||
areas.push(Area { sheet: 0, range: RangeRef::new(start, end) });
|
||||
}
|
||||
if let Some(sh) = wb.sheet_mut(0) {
|
||||
sh.cells.set(k.1, Cell::formula(Formula::new("=1")));
|
||||
}
|
||||
calc.graph.insert(k, Node { areas, dynamic: false });
|
||||
keys.push(k);
|
||||
if rng(&mut s).is_multiple_of(7) {
|
||||
calc.graph.settle();
|
||||
}
|
||||
}
|
||||
for _ in 0..30 {
|
||||
let k = keys[(rng(&mut s) % keys.len() as u64) as usize];
|
||||
calc.graph.remove(k);
|
||||
if let Some(sh) = wb.sheet_mut(0) {
|
||||
sh.cells.remove(k.1);
|
||||
}
|
||||
}
|
||||
if case % 2 == 0 {
|
||||
calc.graph.settle();
|
||||
}
|
||||
let seeds: Vec<Key> = (0..1 + pick(&mut s, 25)).map(|_| (0, CellRef::new(pick(&mut s, 140), pick(&mut s, 220)))).collect();
|
||||
let areas: Vec<(usize, RangeRef)> = (0..pick(&mut s, 3))
|
||||
.map(|_| {
|
||||
let start = CellRef::new(pick(&mut s, 120), pick(&mut s, 150));
|
||||
(0, RangeRef::new(start, CellRef::new(start.row + pick(&mut s, 30), start.col + pick(&mut s, 80))))
|
||||
})
|
||||
.collect();
|
||||
let got: HashSet<Key> = calc.dirty_closure(&wb, &seeds, &areas).into_iter().collect();
|
||||
// The walk before: every area cell is a seed, and every cell lists all its dependents.
|
||||
let mut all = seeds.clone();
|
||||
for (si, r) in &areas {
|
||||
all.extend(r.iter().map(|c| (*si, c)));
|
||||
}
|
||||
let mut want: HashSet<Key> = HashSet::default();
|
||||
let mut queue: VecDeque<Key> = VecDeque::new();
|
||||
let mut deps = Vec::new();
|
||||
for k in &all {
|
||||
if calc.graph.nodes.contains_key(k) && want.insert(*k) {
|
||||
queue.push_back(*k);
|
||||
}
|
||||
deps.clear();
|
||||
calc.graph.dependents(k.0, k.1, &mut deps);
|
||||
queue.extend(deps.iter().copied().filter(|d| want.insert(*d)));
|
||||
}
|
||||
while let Some(k) = queue.pop_front() {
|
||||
deps.clear();
|
||||
calc.graph.dependents(k.0, k.1, &mut deps);
|
||||
queue.extend(deps.iter().copied().filter(|d| want.insert(*d)));
|
||||
}
|
||||
assert_eq!(got, want, "case {case}");
|
||||
}
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn clearing_a_spill_recalculates_formulas_reading_it_once_each() {
|
||||
// 300 formulas read the area an anchor spills into; clearing the anchor changes all of it
|
||||
// and every one of them is recalculated (they were listed once per spilled cell).
|
||||
let mut wb = Workbook::new();
|
||||
let mut calc = Calc::new();
|
||||
let set = |wb: &mut Workbook, calc: &mut Calc, at: CellRef, input: &str| {
|
||||
if let Some(sh) = wb.sheet_mut(0) {
|
||||
if input.is_empty() {
|
||||
sh.cells.remove(at);
|
||||
} else {
|
||||
sh.cells.set(at, Cell::formula(Formula::new(input)));
|
||||
}
|
||||
}
|
||||
calc.cells_changed(wb, &[(0, at)]);
|
||||
};
|
||||
set(&mut wb, &mut calc, CellRef::new(0, 0), "=SEQUENCE(2000)");
|
||||
for r in 0..300 {
|
||||
set(&mut wb, &mut calc, CellRef::new(r, 2), "=COUNT(A1:A2000)");
|
||||
}
|
||||
assert_eq!(wb.sheet(0).map(|s| s.value(CellRef::new(299, 2))), Some(Value::Number(2000.0)));
|
||||
set(&mut wb, &mut calc, CellRef::new(0, 0), "");
|
||||
for r in 0..300 {
|
||||
assert_eq!(wb.sheet(0).map(|s| s.value(CellRef::new(r, 2))), Some(Value::Number(0.0)), "row {r}");
|
||||
}
|
||||
}
|
||||
|
||||
/// `rows` rows of six numbers (E:J) and `=SUM(E{r}:J{r})` in K.
|
||||
fn sum_rows(rows: u32) -> Workbook {
|
||||
let mut wb = Workbook::new();
|
||||
|
||||
@@ -151,54 +151,6 @@ impl<T: Copy + Ord> Intervals<T> {
|
||||
self.walk(1, 0, self.max_end.len() / 2, p, a, f)
|
||||
}
|
||||
|
||||
/// [`Intervals::query`] that skips entries an earlier call with the same `taken` already
|
||||
/// took (and whole subtrees of them), so that a series of queries lists each interval once in
|
||||
/// all. `f` answers whether it took the entry; one it declines is offered again later.
|
||||
/// `taken` belongs to this index as it is now; start it empty. Pending insertions (a few at
|
||||
/// most after [`Intervals::settle`]) are offered every time.
|
||||
pub(super) fn query_untaken(&self, a: u32, b: u32, taken: &mut Vec<bool>, f: &mut dyn FnMut(&T) -> bool) {
|
||||
for it in &self.pending {
|
||||
if it.0 <= b && it.1 >= a {
|
||||
f(&it.2);
|
||||
}
|
||||
}
|
||||
let p = self.items.partition_point(|it| it.0 <= b);
|
||||
if p == 0 {
|
||||
return;
|
||||
}
|
||||
if taken.len() != self.max_end.len() {
|
||||
*taken = vec![false; self.max_end.len()];
|
||||
}
|
||||
self.walk_untaken(1, 0, self.max_end.len() / 2, p, a, taken, f);
|
||||
}
|
||||
|
||||
/// Returns whether everything under `node` has now been reported (or is dead).
|
||||
#[allow(clippy::too_many_arguments)]
|
||||
fn walk_untaken(&self, node: usize, lo: usize, hi: usize, p: usize, a: u32, taken: &mut [bool], f: &mut dyn FnMut(&T) -> bool) -> bool {
|
||||
if taken.get(node).copied().unwrap_or(true) {
|
||||
return true;
|
||||
}
|
||||
if lo >= p || self.max_end.get(node).is_none_or(|m| *m < a) {
|
||||
return false;
|
||||
}
|
||||
let done = if hi - lo <= 1 {
|
||||
match (self.items.get(lo), self.dead.get(lo)) {
|
||||
(Some(it), Some(false)) if it.1 >= a => f(&it.2),
|
||||
(Some(_), Some(true)) => true,
|
||||
_ => false,
|
||||
}
|
||||
} else {
|
||||
let mid = lo + (hi - lo) / 2;
|
||||
let left = self.walk_untaken(2 * node, lo, mid, p, a, taken, f);
|
||||
let right = self.walk_untaken(2 * node + 1, mid, hi, p, a, taken, f);
|
||||
left && right
|
||||
};
|
||||
if done && let Some(slot) = taken.get_mut(node) {
|
||||
*slot = true;
|
||||
}
|
||||
done
|
||||
}
|
||||
|
||||
fn walk(&self, node: usize, lo: usize, hi: usize, p: usize, a: u32, f: &mut dyn FnMut(&T)) -> usize {
|
||||
if lo >= p || self.max_end.get(node).is_none_or(|m| *m < a) {
|
||||
return 1;
|
||||
@@ -216,13 +168,6 @@ impl<T: Copy + Ord> Intervals<T> {
|
||||
}
|
||||
}
|
||||
|
||||
/// Range-index entries one dependency walk has already listed (see [`Graph::dependents_untaken`]).
|
||||
#[derive(Default)]
|
||||
pub(super) struct Taken {
|
||||
cols: HashMap<(usize, u32), Vec<bool>>,
|
||||
wide: HashMap<usize, Vec<bool>>,
|
||||
}
|
||||
|
||||
#[derive(Clone, Debug, Default)]
|
||||
pub struct Graph {
|
||||
pub(super) nodes: HashMap<Key, Node>,
|
||||
@@ -357,32 +302,6 @@ impl Graph {
|
||||
}
|
||||
}
|
||||
|
||||
/// [`Graph::dependents`] leaving out the formulas whose range reads an earlier call with the
|
||||
/// same `taken` already listed. A walk over many changed cells that a few broad ranges cover
|
||||
/// then lists those formulas once, instead of once per cell (which squared the work). The
|
||||
/// graph must not change while `taken` is in use.
|
||||
pub(super) fn dependents_untaken(&self, sheet: usize, c: CellRef, taken: &mut Taken, out: &mut Vec<Key>) {
|
||||
if let Some(v) = self.cell_deps.get(&(sheet, c)) {
|
||||
out.extend(v.iter().copied());
|
||||
}
|
||||
if let Some(v) = self.col_deps.get(&(sheet, c.col)) {
|
||||
v.query_untaken(c.row, c.row, taken.cols.entry((sheet, c.col)).or_default(), &mut |k| {
|
||||
out.push(*k);
|
||||
true
|
||||
});
|
||||
}
|
||||
if let Some(v) = self.wide_deps.get(&sheet) {
|
||||
// A wide entry is taken once it covers the cell's column too.
|
||||
v.query_untaken(c.row, c.row, taken.wide.entry(sheet).or_default(), &mut |(c0, c1, k)| {
|
||||
let hit = *c0 <= c.col && c.col <= *c1;
|
||||
if hit {
|
||||
out.push(*k);
|
||||
}
|
||||
hit
|
||||
});
|
||||
}
|
||||
}
|
||||
|
||||
/// Formulas that read any cell of `range` (a formula can be listed more than once).
|
||||
pub fn dependents_of_range(&self, sheet: usize, range: RangeRef, out: &mut Vec<Key>) {
|
||||
if range.count() <= 4096 {
|
||||
|
||||
@@ -50,12 +50,27 @@ pub(super) fn median(v: Vec<f64>) -> R<f64> {
|
||||
|
||||
/// Values occurring at least twice, ordered by first occurrence, with their (equal, maximal) count.
|
||||
fn modes(v: &[f64]) -> Vec<f64> {
|
||||
// Index of each distinct number in `counts`, so counting is linear rather than a search of
|
||||
// every distinct number so far. Keyed by bits with -0 folded into 0 (they compare equal); NaN
|
||||
// never equals anything, so it is never merged.
|
||||
let mut index: std::collections::HashMap<u64, usize> = std::collections::HashMap::new();
|
||||
let mut counts: Vec<(f64, usize)> = Vec::new();
|
||||
for &x in v {
|
||||
if let Some(e) = counts.iter_mut().find(|e| e.0 == x) {
|
||||
e.1 += 1;
|
||||
} else {
|
||||
if x.is_nan() {
|
||||
counts.push((x, 1));
|
||||
continue;
|
||||
}
|
||||
let key = if x == 0.0 { 0 } else { x.to_bits() };
|
||||
match index.entry(key) {
|
||||
std::collections::hash_map::Entry::Occupied(e) => {
|
||||
if let Some(c) = counts.get_mut(*e.get()) {
|
||||
c.1 += 1;
|
||||
}
|
||||
}
|
||||
std::collections::hash_map::Entry::Vacant(e) => {
|
||||
e.insert(counts.len());
|
||||
counts.push((x, 1));
|
||||
}
|
||||
}
|
||||
}
|
||||
let best = counts.iter().map(|e| e.1).max().unwrap_or(0);
|
||||
@@ -455,7 +470,10 @@ pub(super) fn frequency(a: &[Arg], _: C) -> R<Value> {
|
||||
order.sort_by(|&i, &j| bins.get(i).copied().unwrap_or(0.0).total_cmp(&bins.get(j).copied().unwrap_or(0.0)));
|
||||
let mut counts = vec![0.0; bins.len() + 1];
|
||||
for x in data {
|
||||
let slot = order.iter().find(|&&i| x <= bins.get(i).copied().unwrap_or(f64::INFINITY)).copied().unwrap_or(bins.len());
|
||||
// `order` sorts the bins ascending, so the bins `x` exceeds come first: binary search for
|
||||
// the first bin at or above `x` (the first of equal bins, as a linear scan would find).
|
||||
let pos = order.partition_point(|&i| bins.get(i).copied().unwrap_or(f64::INFINITY) < x);
|
||||
let slot = order.get(pos).copied().unwrap_or(bins.len());
|
||||
if let Some(c) = counts.get_mut(slot) {
|
||||
*c += 1.0;
|
||||
}
|
||||
|
||||
@@ -617,3 +617,20 @@ fn aggregate_helper() {
|
||||
close(aggregate_values_k(9, &vals, &nv(2.0)), 9.0);
|
||||
is_err(aggregate_values_k(14, &vals, &nv(10.0)), CellError::Num);
|
||||
}
|
||||
|
||||
/// Security: FREQUENCY finds each value's bin by binary search, and MODE counts distinct numbers
|
||||
/// through an index, so neither is quadratic in its inputs. Results are as before: unsorted and
|
||||
/// duplicate bins keep their positions (a value goes to the first of equal bins), and tied modes
|
||||
/// come in first-occurrence order.
|
||||
#[test]
|
||||
fn frequency_and_mode_scale_with_their_inputs() {
|
||||
let f = ev("FREQUENCY", vec![c(&[1.0, 2.0, 2.0, 3.0, 5.0, 9.0, -1.0]), c(&[3.0, 2.0, 2.0, 0.0])]);
|
||||
assert_eq!(rows_of(&f), vec![vec![nv(1.0)], vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
|
||||
let data: Vec<f64> = (0..200_000).map(|i| f64::from(i) + 1e6).collect();
|
||||
let bins: Vec<f64> = (0..200_000).map(f64::from).collect();
|
||||
let f = ev("FREQUENCY", vec![c(&data), c(&bins)]);
|
||||
assert_eq!(rows_of(&f).last(), Some(&vec![nv(200_000.0)]));
|
||||
let distinct = ev("MODE", vec![c(&data)]);
|
||||
is_err(distinct, CellError::NA);
|
||||
assert_eq!(rows_of(&ev("MODE.MULT", vec![c(&[3.0, 0.0, 1.0, -0.0, 3.0, 1.0])])), vec![vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)]]);
|
||||
}
|
||||
|
||||
Reference in New Issue
Block a user