Compare commits

..
Author SHA1 Message Date
Dylan M. Taylor 0fc6a87d87 functions: one work budget across every call of a lifted function
A function lifted over a computed array runs once per element, and only the
six lookups counted their repeated work against LIFTED_SCAN_BUDGET. Criteria
aggregates rescanned their ranges per criterion, CUMIPMT/CUMPRINC stepped
through up to 1e7 periods per element, and array-producing functions such as
MUNIT built a whole result per element before keeping its first cell.

The budget now covers all of it: COUNTIF/SUMIF/AVERAGEIF(S)/MAXIFS/MINIFS
charge their range cells per call, the period loops of every element are
added up before any runs, and array results charge their cells as they are
built. Past the budget the call is #NUM!, as lifted lookups already are.
2026-11-02 22:18:09 -05:00
18 changed files with 153 additions and 432 deletions
+5 -2
View File
@@ -1,6 +1,6 @@
use super::frame::{Bx, CatAxis, ValAxis, frame, on, value_range};
use super::legend::{cat_label, plot_kind};
use super::lines::{decimate_area, draw_markers, draw_runs};
use super::lines::{decimate, draw_markers, draw_runs};
use super::trend::{draw_trend_labels, draw_trendlines, max_backward, max_forward, max_forward_slots, supports_trendline};
use super::{
Chart, ChartData, ChartKind, Ctx, Fmt, HAlign, LABEL_SIZE, MAX_CATS, MAX_LABELS, MAX_LINE_PTS, MAX_MARKERS, Prim, Scale, SeriesData, TEXT,
@@ -268,7 +268,10 @@ pub(super) fn cartesian(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx
base = vec![[b[0] - cw * 0.3, b[1]], [b[0] + cw * 0.3, b[1]]];
}
}
let poly = decimate_area(top, base, MAX_LINE_PTS * 2);
let top = decimate(top, MAX_LINE_PTS * 2);
let base = decimate(base, MAX_LINE_PTS * 2);
let mut poly = top;
poly.extend(base.into_iter().rev());
if poly.len() >= 3 {
ctx.out.push(Prim::Polygon { pts: poly, fill: s.color, stroke: None });
}
-133
View File
@@ -54,86 +54,6 @@ pub(super) fn decimate(pts: Vec<[f32; 2]>, max: usize) -> Vec<[f32; 2]> {
out
}
/// Decimates the top and baseline of an area chart together at the same horizontal indices so
/// `area_mesh`'s paired vertical-strip topology (`pts[i]` ↔ `pts[2n - 1 - i]`) is preserved.
pub(super) fn decimate_area(top: Vec<[f32; 2]>, base: Vec<[f32; 2]>, max: usize) -> Vec<[f32; 2]> {
let n = top.len().min(base.len());
if n == 0 {
return Vec::new();
}
if n <= max {
let mut poly = top;
poly.truncate(n);
poly.extend(base.into_iter().take(n).rev());
return poly;
}
let mut cols: Vec<[usize; 6]> = Vec::new();
let mut keep = Vec::with_capacity(max * 2);
let mut i = 0;
while i < n {
let col = top[i][0].floor();
let (start, mut t_mn, mut t_mx, mut b_mn, mut b_mx) = (i, i, i, i, i);
let mut k = i + 1;
while k < n && top[k][0].floor() == col {
if top[k][1] < top[t_mn][1] {
t_mn = k;
}
if top[k][1] > top[t_mx][1] {
t_mx = k;
}
if base[k][1] < base[b_mn][1] {
b_mn = k;
}
if base[k][1] > base[b_mx][1] {
b_mx = k;
}
k += 1;
}
let entry = [start, t_mn, t_mx, b_mn, b_mx, k - 1];
cols.push(entry);
let mut idx = entry;
idx.sort_unstable();
let mut last = usize::MAX;
for ix in idx {
if ix != last {
keep.push(ix);
last = ix;
}
}
i = k;
}
if keep.len() > max * 4 {
let max_groups = (max * 4 / 6).max(1);
let group_size = cols.len().div_ceil(max_groups);
keep.clear();
for ch in cols.chunks(group_size) {
let start = ch[0][0];
let end = ch.last().map_or(start, |c| c[5]);
let t_mn = ch.iter().map(|c| c[1]).min_by(|&a, &b| top[a][1].total_cmp(&top[b][1])).unwrap_or(start);
let t_mx = ch.iter().map(|c| c[2]).max_by(|&a, &b| top[a][1].total_cmp(&top[b][1])).unwrap_or(start);
let b_mn = ch.iter().map(|c| c[3]).min_by(|&a, &b| base[a][1].total_cmp(&base[b][1])).unwrap_or(start);
let b_mx = ch.iter().map(|c| c[4]).max_by(|&a, &b| base[a][1].total_cmp(&base[b][1])).unwrap_or(start);
let mut idx = [start, t_mn, t_mx, b_mn, b_mx, end];
idx.sort_unstable();
let mut last = usize::MAX;
for ix in idx {
if ix != last {
keep.push(ix);
last = ix;
}
}
}
}
let mut poly = Vec::with_capacity(keep.len() * 2);
for &ix in &keep {
poly.push(top[ix]);
}
for &ix in keep.iter().rev() {
poly.push(base[ix]);
}
poly
}
/// Draws a polyline split at gaps (`None`), decimated when long. With `smooth` (the plot box),
/// each run is interpolated with a Catmull-Rom spline so the line curves through the data points.
pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, width: f32, smooth: Option<Bx>) {
@@ -235,57 +155,4 @@ mod smooth_tests {
assert!(out.len() > 5);
assert!(out.iter().all(|p| (0.0..=300.0).contains(&p[0]) && (10.0..=110.0).contains(&p[1])));
}
#[test]
fn decimate_area_preserves_paired_vertical_strips() {
let top: Vec<[f32; 2]> = (0..1000).map(|i| [i as f32 * 0.25, ((i * 37) % 100) as f32]).collect();
let base: Vec<[f32; 2]> = (0..1000).map(|i| [i as f32 * 0.25, 100.0]).collect();
let poly = decimate_area(top, base, 64);
assert_eq!(poly.len() % 2, 0);
let half = poly.len() / 2;
for i in 0..half {
assert_eq!(poly[i][0], poly[poly.len() - 1 - i][0]);
assert_eq!(poly[poly.len() - 1 - i][1], 100.0);
}
}
#[test]
fn decimate_area_preserves_extrema_across_3000_columns() {
// 3,000 occupied pixel columns with 6 points per column (18,000 points total),
// where each column has distinct top and baseline extrema so the initial per-column
// index list exceeds `MAX_LINE_PTS * 2 * 4` (6,400).
let max = MAX_LINE_PTS * 2;
let mut top = Vec::with_capacity(18_000);
let mut base = Vec::with_capacity(18_000);
for col in 0..3_000 {
let y_top = [50.0, 20.0, 80.0, 50.0, 50.0, 50.0];
let y_base = [150.0, 150.0, 150.0, 120.0, 180.0, 150.0];
for s in 0..6 {
let x = col as f32 + s as f32 * 0.1;
top.push([x, y_top[s]]);
base.push([x, y_base[s]]);
}
}
// Plant sharp spikes on both top and baseline in interior columns.
top[777 * 6 + 1][1] = 1.0;
top[1999 * 6 + 2][1] = 99.0;
base[1234 * 6 + 3][1] = 101.0;
base[2501 * 6 + 4][1] = 199.0;
let poly = decimate_area(top, base, max);
assert_eq!(poly.len() % 2, 0);
let half = poly.len() / 2;
assert!(half <= max * 4, "retained {half} paired vertices, limit is {}", max * 4);
for i in 0..half {
assert_eq!(poly[i][0], poly[poly.len() - 1 - i][0]);
}
let top_kept = &poly[..half];
let base_kept = &poly[half..];
assert_eq!(top_kept.first().map(|p| p[0]), Some(0.0));
assert_eq!(top_kept.last().map(|p| p[0]), Some(2999.5));
assert!(top_kept.iter().any(|p| p[1] == 1.0), "top min spike preserved");
assert!(top_kept.iter().any(|p| p[1] == 99.0), "top max spike preserved");
assert!(base_kept.iter().any(|p| p[1] == 101.0), "base min spike preserved");
assert!(base_kept.iter().any(|p| p[1] == 199.0), "base max spike preserved");
}
}
-16
View File
@@ -188,12 +188,6 @@ impl RangeRef {
end: CellRef::new(self.end.row.max(o.end.row), self.end.col.max(o.end.col)),
}
}
/// The top-left cell of a list of areas: the lowest row and the lowest column across all of
/// them, whatever order they are listed in. Excel writes the relative formulas of a
/// multi-area validation or conditional format for this cell. `None` for no areas.
pub fn top_left(ranges: &[RangeRef]) -> Option<CellRef> {
ranges.iter().copied().reduce(|a, b| a.union(&b)).map(|r| r.start)
}
/// Row-major iterator over the cells. Callers must bound huge ranges themselves.
pub fn iter(&self) -> impl Iterator<Item = CellRef> + '_ {
let (r0, r1, c0, c1) = (self.start.row, self.end.row, self.start.col, self.end.col);
@@ -313,16 +307,6 @@ mod tests {
Ok(())
}
#[test]
fn top_left_spans_every_area_in_any_order() {
let areas: Vec<RangeRef> = ["H62:H68", "H26:H27", "H93:H95"].iter().filter_map(|a| RangeRef::parse(a)).collect();
assert_eq!(RangeRef::top_left(&areas), CellRef::parse("H26"));
// Lowest row and lowest column, even when they come from different areas.
let areas: Vec<RangeRef> = ["C5:D6", "E2", "B9"].iter().filter_map(|a| RangeRef::parse(a)).collect();
assert_eq!(RangeRef::top_left(&areas), CellRef::parse("B2"));
assert_eq!(RangeRef::top_left(&[]), None);
}
#[test]
fn sheet_quoting_follows_excel() {
for quoted in [
+1 -1
View File
@@ -244,7 +244,7 @@ impl CfCache {
let v = sh.value(c);
let no_stats = RuleStats::default();
for (idx, cf) in rules {
let first = RangeRef::top_left(&cf.ranges).unwrap_or(c);
let first = cf.ranges.first().map(|r| r.start).unwrap_or(c);
let st: &RuleStats = match stats_need(&cf.rule) {
Some(need) => &*self.stats.entry(idx).or_insert_with(|| RuleStats::build(sh, &cf.ranges, need)),
None => &no_stats,
-39
View File
@@ -480,45 +480,6 @@ fn a_list_typed_without_quotes_is_saved_as_a_quoted_list() {
assert_eq!(sheet_xml(&reopened), xml, "a second save writes the same rules");
}
#[test]
fn a_relative_list_source_is_read_from_the_cell_being_checked() {
// As in Excel, `=$B1:$B2` on A3:A4,A1:A2 is written for A1 (the top-left cell of all the
// areas) and lists B4:B5 at A4. It used to list B1:B2 in every cell.
let mut s = Session::new();
s.new_workbook();
s.execute("range.setValues", json!({"range": "B1:B5", "values": [["a"], ["b"], ["c"], ["d"], ["e"]]})).unwrap();
s.execute("data.validation", json!({"range": "A3:A4,A1:A2", "type": "list", "formula1": "=$B1:$B2"})).unwrap();
let wb = s.doc().unwrap().wb.clone();
let dv = wb.active().unwrap().validations[0].clone();
for (cell, items) in [("A1", ["a", "b"]), ("A2", ["b", "c"]), ("A3", ["c", "d"]), ("A4", ["d", "e"])] {
let at = CellRef::parse(cell).unwrap();
assert_eq!(list_items(&wb, 0, at, &dv), items, "{cell}");
for v in ["a", "b", "c", "d", "e"] {
assert_eq!(check_validation(&wb, 0, at, v).is_none(), items.contains(&v), "{cell} with {v}");
}
}
}
#[test]
fn a_list_source_that_takes_in_the_cell_does_not_list_the_value_being_typed() {
// `=$A1:$A2` on A2:A3 is A1:A2 at A2 and A2:A3 at A3. The list is the one before the entry, as
// in Excel; a new value used to land in its own source and pass.
let mut s = Session::new();
s.new_workbook();
s.execute("range.setValues", json!({"range": "A1:A2", "values": [["x"], ["y"]]})).unwrap();
s.execute("data.validation", json!({"range": "A2:A3", "type": "list", "formula1": "=$A1:$A2"})).unwrap();
let wb = &s.doc().unwrap().wb;
for (cell, accepted, refused) in [("A2", &["x", "y"][..], &["new"][..]), ("A3", &["y"], &["x", "new"])] {
let at = CellRef::parse(cell).unwrap();
for v in accepted {
assert!(check_validation(wb, 0, at, v).is_none(), "{cell} refuses {v}");
}
for v in refused {
assert!(check_validation(wb, 0, at, v).is_some(), "{cell} accepts {v}");
}
}
}
#[test]
fn a_rule_with_an_unknown_type_operator_or_error_style_is_refused() {
// A typo used to give a rule that validates nothing (`type="none"`) or the wrong check,
+7 -19
View File
@@ -38,18 +38,11 @@ fn subtract_range(r: RangeRef, cut: &RangeRef) -> Vec<RangeRef> {
}
/// Removes the cells of `cuts` from every validation, keeping the rest of each rule's ranges.
/// When the rule's top-left cell goes, its relative formulas are rewritten for the new top-left
/// cell, so the cells left keep checking the same cells.
pub(in super::super) fn remove_validation_cells(validations: &mut Vec<Validation>, cuts: &[RangeRef]) {
for dv in validations.iter_mut() {
let before = RangeRef::top_left(&dv.ranges);
for cut in cuts {
dv.ranges = dv.ranges.iter().flat_map(|r| subtract_range(*r, cut)).collect();
}
if let (Some(from), Some(to)) = (before, RangeRef::top_left(&dv.ranges)) {
dv.f1 = move_rule_formula(&dv.f1, from, to);
dv.f2 = dv.f2.take().map(|f| move_rule_formula(&f, from, to));
}
}
validations.retain(|d| !d.ranges.is_empty());
}
@@ -152,10 +145,8 @@ fn list_source(f: &str) -> String {
format!("\"{}\"", t.replace('"', "\"\""))
}
/// List entries of a list validation (literal or from a range) for the cell `at`. A relative
/// source is written for the rule's top-left cell and read from `at`, as in Excel (`=$B1:$B3` on
/// A1:A9 lists B5:B7 at A5).
pub fn list_items(wb: &Workbook, sheet: usize, at: CellRef, dv: &Validation) -> Vec<String> {
/// List entries of a list validation (literal or from a range).
pub fn list_items(wb: &Workbook, sheet: usize, dv: &Validation) -> Vec<String> {
let f = dv.f1.trim();
if is_literal_list(f) {
// A quoted list is a string literal: `""` inside stands for one `"`.
@@ -165,8 +156,8 @@ pub fn list_items(wb: &Workbook, sheet: usize, at: CellRef, dv: &Validation) ->
};
return items.split(',').map(|x| x.trim().to_string()).filter(|x| !x.is_empty()).collect();
}
let first = RangeRef::top_left(&dv.ranges).unwrap_or(at);
match gridcraft_calc::evaluate(wb, sheet, at, &formula_at(f, first, at)) {
let at = dv.ranges.first().map(|r| r.start).unwrap_or_default();
match gridcraft_calc::evaluate(wb, sheet, at, f) {
Value::Array(a) => a.data.iter().filter(|v| !v.is_empty()).map(Value::display).collect(),
v if !v.is_empty() && !v.is_error() => vec![v.display()],
_ => vec![],
@@ -184,10 +175,9 @@ pub fn check_validation(wb: &Workbook, sheet: usize, at: CellRef, input: &str) -
return None;
}
let v = gridcraft_core::parse::parse_input(input, wb.date_system).value;
// The formulas are written for the top-left cell of all the areas and see the value being entered,
// The formulas are written for the first cell of the range and see the value being entered,
// as in Excel (a custom `=A1>10` on A1:A9 checks A5's new value at A5).
let first = RangeRef::top_left(&dv.ranges).unwrap_or(at);
let original = wb;
let first = dv.ranges.first().map(|r| r.start).unwrap_or(at);
let entered;
let wb = if sh.value(at) == v {
wb
@@ -203,9 +193,7 @@ pub fn check_validation(wb: &Workbook, sheet: usize, at: CellRef, input: &str) -
let eval = |f: &str| gridcraft_calc::evaluate(wb, sheet, at, &formula_at(f, first, at));
let num = |f: &str| eval(f).to_number().ok();
let ok = match dv.kind {
// The list is the one the dropdown showed before the entry, as in Excel: a source that takes
// in the cell itself (`=$A1:$A2` on A2:A3 is A2:A3 at A3) doesn't list the value being typed.
ValidationKind::List => list_items(original, sheet, at, dv).iter().any(|x| x.eq_ignore_ascii_case(input)),
ValidationKind::List => list_items(wb, sheet, dv).iter().any(|x| x.eq_ignore_ascii_case(input)),
ValidationKind::Custom => eval(&dv.f1).to_bool().unwrap_or(false),
ValidationKind::TextLength => {
let n = input.chars().count() as f64;
+1 -1
View File
@@ -284,7 +284,7 @@ pub(super) fn paste_special(s: &mut Session, p: &Json) -> Result<Json> {
crate::cmd::data::remove_validation_cells(&mut sh.validations, &[RangeRef::new(dest, dest)]);
if let Some(mut dv) = rule {
// Relative references move with the rule, as pasted formulas do.
let first = RangeRef::top_left(&dv.ranges).unwrap_or(sc);
let first = dv.ranges.first().map_or(sc, |r| r.start);
dv.f1 = crate::cmd::data::move_rule_formula(&dv.f1, first, dest);
dv.f2 = dv.f2.map(|f| crate::cmd::data::move_rule_formula(&f, first, dest));
dv.ranges = vec![RangeRef::new(dest, dest)];
-19
View File
@@ -1733,13 +1733,7 @@ fn clear_cf(s: &mut Session, p: &Json) -> Result<Json> {
sh.cond_formats.clear();
} else {
for cf in sh.cond_formats.iter_mut() {
let before = RangeRef::top_left(&cf.ranges);
cf.ranges.retain(|r| !ranges.iter().any(|x| x.intersects(r)));
// The relative formulas are written for the top-left cell: when it goes, they're
// rewritten for the new one, so the areas left keep reading the same cells.
if let (Some(from), Some(to)) = (before, RangeRef::top_left(&cf.ranges)) {
rebase_cf_formulas(&mut cf.rule, from, to);
}
}
sh.cond_formats.retain(|c| !c.ranges.is_empty());
}
@@ -1747,19 +1741,6 @@ fn clear_cf(s: &mut Session, p: &Json) -> Result<Json> {
})
}
/// Moves the relative references of a rule's per-cell formulas written for `from` to `to`.
fn rebase_cf_formulas(rule: &mut CfRule, from: CellRef, to: CellRef) {
let mv = |f: &str| crate::cmd::data::move_rule_formula(f, from, to);
match rule {
CfRule::CellIs { a, b, .. } => {
*a = mv(a);
*b = b.as_deref().map(mv);
}
CfRule::Expression { formula, .. } => *formula = mv(formula),
_ => {}
}
}
fn manage_cf(s: &mut Session, p: &Json) -> Result<Json> {
let sheet = target_sheet(s, p)?;
if p.get("delete").is_none() && p.get("moveUp").is_none() && p.get("moveDown").is_none() {
-72
View File
@@ -2743,78 +2743,6 @@ fn validation_formulas_are_relative_and_see_the_new_value() {
assert!(!ok(&mut s, "C1", "50"));
}
#[test]
fn multi_area_rule_formulas_are_relative_to_the_top_left_cell_of_all_areas() {
// Issue #3152: Excel writes the formula for the top-left cell of all the areas (H26), whatever
// order they are listed in, not for the first area listed (H62).
let mut s = s();
s.execute("range.setValues", json!({"range": "F26:F27", "values": [[4], [5]]})).unwrap();
s.execute("data.validation", json!({"range": "H62:H68,H26:H27,H93:H95", "type": "custom", "formula1": "=MOD($H26,$F26)=0"})).unwrap();
let ok = |s: &mut Session, cell: &str, input: &str| s.execute("data.validate", json!({"cell": cell, "input": input})).unwrap()["ok"] == true;
assert!(ok(&mut s, "H26", "4"));
assert!(ok(&mut s, "H26", "8"));
assert!(!ok(&mut s, "H26", "3"));
assert!(ok(&mut s, "H27", "10"));
assert!(!ok(&mut s, "H27", "4"));
// Conditional formats anchor on the same cell: `=D2>0` on D5:D6,D2:D3 checks D2 at D2.
s.execute("range.setValues", json!({"range": "D2:D6", "values": [[1], [0], [0], [1], [0]]})).unwrap();
s.execute("home.conditionalFormat", json!({"range": "D5:D6,D2:D3", "rule": {"type": "expression", "formula": "=D2>0", "preset": "greenFill"}}))
.unwrap();
let wb = s.doc().unwrap().wb.clone();
let mut cache = crate::cf::CfCache::new();
let mut styled = |c: &str| cache.look(&wb, 0, CellRef::parse(c).unwrap()).and_then(|l| l.style).is_some();
assert_eq!([styled("D2"), styled("D3"), styled("D5"), styled("D6")], [true, false, true, false]);
}
#[test]
fn removing_a_rules_top_left_cell_rewrites_its_formulas_for_the_new_one() {
let mut s = s();
let ok = |s: &mut Session, cell: &str, input: &str| s.execute("data.validate", json!({"cell": cell, "input": input})).unwrap()["ok"] == true;
let f1 = |s: &Session| s.doc().unwrap().wb.active().unwrap().validations[0].f1.clone();
// One area: clearing A1 off A1:A9 leaves A2:A9, whose cells still check themselves.
s.execute("data.validation", json!({"range": "A1:A9", "type": "custom", "formula1": "=A1>10"})).unwrap();
s.execute("data.validation", json!({"range": "A1", "clear": true})).unwrap();
assert_eq!(f1(&s), "A2>10");
assert!(ok(&mut s, "A2", "20"));
assert!(!ok(&mut s, "A2", "5"));
s.execute("data.validation", json!({"range": "A1:A9", "clear": true})).unwrap();
// Several areas: clearing H26 moves the top-left cell to H27, where `$H27,$F27` is checked.
s.execute("range.setValues", json!({"range": "F26:F27", "values": [[4], [5]]})).unwrap();
s.execute("data.validation", json!({"range": "H62:H68,H26:H27", "type": "custom", "formula1": "=MOD($H26,$F26)=0"})).unwrap();
s.execute("data.validation", json!({"range": "H26", "clear": true})).unwrap();
assert_eq!(f1(&s), "MOD($H27,$F27)=0");
assert!(ok(&mut s, "H27", "10"));
assert!(!ok(&mut s, "H27", "4"));
// Absolute and literal formulas don't move.
s.execute("data.validation", json!({"range": "J1:J3", "type": "list", "formula1": "=$B$1:$B$2"})).unwrap();
s.execute("data.validation", json!({"range": "J1", "clear": true})).unwrap();
let dv = s.doc().unwrap().wb.active().unwrap().validations.iter().find(|d| d.ranges[0].a1() == "J2:J3").unwrap().f1.clone();
assert_eq!(dv, "$B$1:$B$2");
// Conditional formats: Clear Rules on D2 drops the D2:D3 area, and D5:D6 keeps reading itself.
s.execute("range.setValues", json!({"range": "D2:D6", "values": [[1], [0], [0], [0], [1]]})).unwrap();
s.execute("home.conditionalFormat", json!({"range": "D5:D6,D2:D3", "rule": {"type": "expression", "formula": "=D2>0", "preset": "greenFill"}}))
.unwrap();
s.execute("range.setValues", json!({"range": "E2:E6", "values": [[1], [0], [0], [0], [1]]})).unwrap();
s.execute("range.setValues", json!({"range": "G2:G6", "values": [[0], [9], [9], [9], [0]]})).unwrap();
s.execute(
"home.conditionalFormat",
json!({"range": "E5:E6,E2:E3", "rule": {"type": "cellIs", "operator": "greater", "value": "=G2", "preset": "lightRedFill"}}),
)
.unwrap();
s.execute("home.clearRules", json!({"range": "D2,E2"})).unwrap();
let rules: Vec<gridcraft_model::CfRule> = s.doc().unwrap().wb.active().unwrap().cond_formats.iter().map(|c| c.rule.clone()).collect();
assert!(rules.iter().any(|r| matches!(r, gridcraft_model::CfRule::Expression { formula, .. } if formula == "D5>0")), "{rules:?}");
assert!(rules.iter().any(|r| matches!(r, gridcraft_model::CfRule::CellIs { a, .. } if a == "G5")), "{rules:?}");
let wb = s.doc().unwrap().wb.clone();
let mut cache = crate::cf::CfCache::new();
let mut styled = |c: &str| cache.look(&wb, 0, CellRef::parse(c).unwrap()).and_then(|l| l.style).is_some();
assert_eq!([styled("D5"), styled("D6"), styled("E5"), styled("E6")], [false, true, false, true]);
}
#[test]
fn samples_build() {
for (name, _) in crate::sample::SAMPLES {
+131 -24
View File
@@ -68,26 +68,70 @@ const SCANS: &[&str] = &["VLOOKUP", "HLOOKUP", "LOOKUP", "MATCH", "XLOOKUP", "XM
/// `XMATCH(SEQUENCE(1048576), -SEQUENCE(1048576))` runs for hours and hangs opening the file.
/// Past the budget the call is `#NUM!`, as MMULT is past 2e9 multiply-adds. 5e8 keeps the worst
/// case to a few seconds and still admits 5,000 needles over a 100,000-row table.
///
/// The same budget covers all the work of a lifted call added up across its elements: criteria
/// aggregates rescanning their ranges, period loops, and array results built per element.
const LIFTED_SCAN_BUDGET: usize = 500_000_000;
/// The length of the longest vector a lifted call of `spec` searches per needle: 0 unless `spec`
/// is one of the [`SCANS`] lookups and a non-lifted argument is an array.
/// Criteria aggregates: every call tests each cell of its ranges against its criteria, so a call
/// lifted over `n` criteria does `n` x (range cells) work, like the [`SCANS`] lookups.
const CRITERIA: &[&str] = &["COUNTIF", "COUNTIFS", "SUMIF", "SUMIFS", "AVERAGEIF", "AVERAGEIFS", "MAXIFS", "MINIFS"];
/// Cumulative TVM functions that step through every period from `start_period` (argument 3) to
/// `end_period` (argument 4) on each call.
const PERIOD_LOOPS: &[&str] = &["CUMIPMT", "CUMPRINC"];
/// The work every lifted call of `spec` repeats over its non-lifted arguments: the longest vector
/// a [`SCANS`] lookup searches, or every cell a [`CRITERIA`] aggregate tests. 0 for other
/// functions.
fn scan_len(spec: &FnSpec, args: &[Arg]) -> usize {
if !SCANS.contains(&spec.name) {
let scans = SCANS.contains(&spec.name);
if !scans && !CRITERIA.contains(&spec.name) {
return 0;
}
args.iter()
.enumerate()
.filter(|(i, _)| !spec.is_scalar_arg(*i))
.filter_map(|(_, a)| match &a.value {
Value::Array(arr) => Some(arr.rows.max(arr.cols)),
_ => None,
})
.max()
.unwrap_or(0)
let lens = args.iter().enumerate().filter(|(i, _)| !spec.is_scalar_arg(*i)).filter_map(|(_, a)| match &a.value {
Value::Array(arr) => Some(if scans { arr.rows.max(arr.cols) } else { arr.data.len() }),
_ => None,
});
if scans { lens.max().unwrap_or(0) } else { lens.fold(0, usize::saturating_add) }
}
/// The work of one lifted call that depends on its own (lifted) scalar arguments: the number of
/// periods a [`PERIOD_LOOPS`] function steps through. 0 for other functions.
fn call_cost(spec: &FnSpec, cell_args: &[Arg]) -> usize {
if !PERIOD_LOOPS.contains(&spec.name) {
return 0;
}
let period = |i: usize| match cell_args.get(i).map(|a| &a.value) {
Some(Value::Number(n)) if n.is_finite() => Some(n.trunc()),
_ => None,
};
match (period(3), period(4)) {
// The function itself refuses spans past 1e7 periods; anything larger costs the cap.
(Some(start), Some(end)) if end >= start => ((end - start) + 1.0).min(1e8) as usize,
_ => 0,
}
}
pub(crate) fn call_lifted(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx) -> Value {
call_lifted_within(spec, args, ctx, LIFTED_SCAN_BUDGET)
}
/// Sets the lifted arguments of `cell_args` to their elements at (`r`, `c`).
fn element_args(spec: &FnSpec, args: &[Arg], r: usize, c: usize, cell_args: &mut [Arg]) {
for (i, a) in args.iter().enumerate() {
if spec.is_scalar_arg(i)
&& let Value::Array(arr) = &a.value
&& let Some(slot) = cell_args.get_mut(i)
{
let v = arr.get_broadcast(r, c);
slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
}
}
}
/// [`call_lifted`] with every call's work added up against `budget` (see [`LIFTED_SCAN_BUDGET`]).
fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: usize) -> Value {
let rejected = if spec.value_args.is_empty() { None } else { reject_multi_cell_refs(spec, args) };
let args = rejected.as_deref().unwrap_or(args);
let mut rows = 0usize;
@@ -106,25 +150,42 @@ pub(crate) fn call_lifted(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx) -> Val
return (spec.imp)(args, ctx);
}
let needles = rows.saturating_mul(cols);
if needles > MAX_CELLS || needles.saturating_mul(scan_len(spec, args)) > LIFTED_SCAN_BUDGET {
// Every call is charged its repeated scan (at least 1), its own period loop, and the cells of
// an array result (built in full, though only its first cell is kept), so lifting a scalar
// argument can't multiply what one call may do into hours of work:
// `COUNTIF(big_range, SEQUENCE(1e4))`, `CUMIPMT(0.1, 1e7, 1, 1, SEQUENCE(1e4,,1e7,0), 0)`,
// `MUNIT(SEQUENCE(1e4,,3000,0))`.
let per_call = scan_len(spec, args).max(1);
let mut cell_args: Vec<Arg> = args.to_vec();
let mut spent = needles.saturating_mul(per_call);
if needles > MAX_CELLS || spent > budget {
return Value::Error(CellError::Num);
}
let mut cell_args: Vec<Arg> = args.to_vec();
// Period loops are known before any call runs, so a call over budget does none of them.
if PERIOD_LOOPS.contains(&spec.name) {
for r in 0..rows {
for c in 0..cols {
element_args(spec, args, r, c, &mut cell_args);
spent = spent.saturating_add(call_cost(spec, &cell_args));
if spent > budget {
return Value::Error(CellError::Num);
}
}
}
}
let mut data = Vec::with_capacity(rows * cols);
for r in 0..rows {
for c in 0..cols {
for (i, a) in args.iter().enumerate() {
if spec.is_scalar_arg(i)
&& let Value::Array(arr) = &a.value
&& let Some(slot) = cell_args.get_mut(i)
{
let v = arr.get_broadcast(r, c);
slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
}
}
element_args(spec, args, r, c, &mut cell_args);
let out = (spec.imp)(&cell_args, ctx);
data.push(match out {
Value::Array(a) => a.data.first().cloned().unwrap_or(Value::Empty),
Value::Array(a) => {
spent = spent.saturating_add(a.data.len());
if spent > budget {
return Value::Error(CellError::Num);
}
a.data.first().cloned().unwrap_or(Value::Empty)
}
v => v,
});
}
@@ -209,6 +270,52 @@ mod tests {
assert_eq!(rows_of(&out), vec![vec![nv(-1.0)]; 1000]);
}
/// Security: lifting a criteria aggregate rescans its range for every criterion, so criteria
/// x range cells past the budget is `#NUM!` before any scan runs.
#[test]
fn lifted_criteria_aggregates_stop_past_their_work_budget() {
use gridcraft_core::Array;
let tall = |n: usize| av(Array::filled(n, 1, nv(-1.0)).into());
is_err(ev("COUNTIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
is_err(ev("SUMIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
is_err(ev("COUNTIFS", vec![tall(1_000_000), tall(501)]), CellError::Num);
// Two ranges of 250,000 cells each count together.
is_err(ev("SUMIFS", vec![tall(250_000), tall(250_000), tall(1001)]), CellError::Num);
let counts = ev("COUNTIF", vec![av(col(&[1.0, 2.0, 2.0])), av(col(&[2.0, 1.0, 5.0]))]);
assert_eq!(rows_of(&counts), vec![vec![nv(2.0)], vec![nv(1.0)], vec![nv(0.0)]]);
for name in super::CRITERIA.iter().chain(super::PERIOD_LOOPS) {
assert!(crate::lookup(name).is_some(), "{name} isn't registered");
}
}
/// Security: CUMIPMT and CUMPRINC loop over their periods once per lifted element; the
/// periods of all elements are added up first, so an over-budget call runs none of them.
#[test]
fn lifted_period_loops_stop_past_their_work_budget() {
use gridcraft_core::Array;
let ends = |len: usize, end: f64| av(Array::filled(len, 1, nv(end)).into());
let args = |len: usize, end: f64| vec![n(0.01), n(1e7), n(1000.0), n(1.0), ends(len, end), n(0.0)];
// 51 elements of 1e7 periods each is past 5e8.
is_err(ev("CUMIPMT", args(51, 1e7)), CellError::Num);
is_err(ev("CUMPRINC", args(51, 1e7)), CellError::Num);
let out = ev("CUMIPMT", args(2, 12.0));
assert_eq!(rows_of(&out).len(), 2);
assert!(matches!(rows_of(&out).first().and_then(|r| r.first()), Some(Value::Number(x)) if *x < 0.0));
}
/// Security: an array-producing function lifted over a computed array builds each element's
/// whole result before keeping one cell; their cells count against the budget.
#[test]
fn lifted_array_results_count_against_the_budget() {
use gridcraft_core::Array;
let spec = crate::lookup("MUNIT").unwrap_or_else(|| panic!("MUNIT isn't registered"));
let dims = |n: usize| [av(Array::filled(n, 1, nv(10.0)).into())];
// Ten 10x10 identity matrices are 1,000 cells.
let out = super::call_lifted_within(spec, &dims(10), &mut TestCtx::default(), 1_010);
assert_eq!(rows_of(&out), vec![vec![nv(1.0)]; 10]);
is_err(super::call_lifted_within(spec, &dims(11), &mut TestCtx::default(), 1_010), CellError::Num);
}
#[test]
fn value_params_reject_multi_cell_references() {
let s = FnSpec { value_args: &[true, false], ..spec() };
+1 -1
View File
@@ -125,7 +125,7 @@ pub(super) fn list_picker(app: &mut SheetApp, ui: &mut egui::Ui, geo: &Geo, was_
app.grid.list_picker = None;
return;
};
let items = gridcraft_engine::cmd::data::list_items(&wb, si, c, &dv);
let items = gridcraft_engine::cmd::data::list_items(&wb, si, &dv);
let r = geo.cell_rect(sh, c);
// Fit the popup to its rows (up to LIST_PICKER_MAX_ROWS); without a minimum the scroll area collapses to its 64 px default.
let height = list_picker_height(items.len(), LIST_PICKER_ROW_H, ui.spacing().item_spacing.y);
-3
View File
@@ -622,13 +622,10 @@ fn size_combo(app: &mut SheetApp, ui: &mut Ui, st: &Style) {
let arrow_rect = Rect::from_min_max(egui::pos2(frame.right() - 16.0, frame.top() + 1.0), egui::pos2(frame.right() - 1.0, frame.bottom() - 1.0));
let mut field_ui =
ui.new_child(egui::UiBuilder::new().max_rect(text_rect.shrink2(vec2(6.0, 0.0))).layout(egui::Layout::left_to_right(egui::Align::Center)));
// The text edit is `interact_size.y` tall and puts its text at the top of that unless told
// otherwise: center it, on the Font name's baseline (#3155).
let out = egui::TextEdit::singleline(&mut text)
.id(field)
.font(theme::ui_font(12.5))
.frame(egui::Frame::NONE)
.align(egui::Align2::LEFT_CENTER)
.desired_width(text_rect.width() - 12.0)
.show(&mut field_ui);
let resp = out.response;
+2 -31
View File
@@ -1,7 +1,6 @@
//! Home ▸ Font Size is a box you type a size into, with the standard sizes behind its arrow (#932),
//! and the size sits in the middle of that box (#3155).
//! Home ▸ Font Size is a box you type a size into, with the standard sizes behind its arrow (#932).
use egui::{Event, Key, Modifiers, Rect, Shape, accesskit::Role};
use egui::{Event, Key, Modifiers, accesskit::Role};
use egui_kittest::kittest::Queryable as _;
use gridcraft_engine::Session;
use gridcraft_engine::core::{CellRef, Value};
@@ -125,31 +124,3 @@ fn the_arrow_opens_the_plain_list_of_sizes() {
h.run_steps(3);
assert_eq!(size(&h, "A1"), 12.0, "Down from 11 then Enter picks 12");
}
/// The on-screen box of the painted text `text` that overlaps `within`. The grid's row headers
/// paint "11" too, so the size has to be looked for inside its own box.
fn painted_text(h: &Harness, text: &str, within: Rect) -> Rect {
h.output()
.shapes
.iter()
.find_map(|s| match &s.shape {
Shape::Text(t) if t.galley.job.text == text => {
let rect = t.galley.rect.translate(t.pos.to_vec2());
within.intersects(rect).then_some(rect)
}
_ => None,
})
.unwrap_or_else(|| panic!("{text:?} is painted inside {within:?}"))
}
#[test]
/// A text edit aligns its text to the top of its rect unless told otherwise, which left the size
/// 4 pt above the Font name's baseline.
fn the_size_is_vertically_centered_in_its_box() {
let h = harness();
let field = h.get_by_role_and_label(Role::TextInput, "Font Size").rect();
let value = painted_text(&h, "11", field);
let name = painted_text(&h, "Calibri", Rect::EVERYTHING);
assert!((value.center().y - field.center().y).abs() <= 1.0, "the size is centered in its box: {value:?} in {field:?}");
assert!((value.center().y - name.center().y).abs() <= 1.0, "the size is on the Font name's baseline: {value:?} against {name:?}");
}
+3 -5
View File
@@ -104,10 +104,7 @@ struct Clicks {
#[test]
/// The main button clicks once and the arrow twice separately; the tooltip keeps the platform shortcut, and the icon sits above the full-width label.
fn big_split_button_separates_the_default_action_from_the_menu() {
// The ribbon picks the shortcut by the OS egui reports, which kittest pins to Nix unless told:
// pin macOS, so the check is the same on every host (the other platforms' text is in
// `widgets::tests`).
let mut h = crate::common::builder().with_size(vec2(300.0, 200.0)).with_os(egui::os::OperatingSystem::Mac).build_ui_state(
let mut h = crate::common::builder().with_size(vec2(300.0, 200.0)).build_ui_state(
|ui, c: &mut Clicks| {
let (main, arrow) = widgets::big_split_button(ui, Icon::Sum, "Auto\nSum", "AutoSum");
c.main += u32::from(main.clicked());
@@ -128,7 +125,8 @@ fn big_split_button_separates_the_default_action_from_the_menu() {
h.ctx.all_styles_mut(|s| s.interaction.tooltip_delay = 0.0);
h.get_by_label("Auto Sum").hover();
h.run_steps(6);
assert!(h.query_by_value("AutoSum (\u{2318}\u{21e7}T)").is_some(), "tooltip with the macOS shortcut");
let shortcut = if cfg!(target_os = "macos") { "AutoSum (\u{2318}\u{21e7}T)" } else { "AutoSum (Alt+=)" };
assert!(h.query_by_value(shortcut).is_some(), "tooltip with the shortcut");
// The icon part sits above the label part, across the full width.
let main = h.get_by_label("Auto Sum").rect();
let arrow = h.get_by_label("Auto Sum options").rect();
+1 -3
View File
@@ -52,10 +52,8 @@ pub(super) fn x14_cfvo(v: &CfValueKind) -> String {
format!("<x14:cfvo type=\"{ty}\"><xm:f>{}</xm:f></x14:cfvo>", esc(&val))
}
/// One `cfRule` element. The formulas generated for text, blank, error and date rules refer to the
/// top-left cell of all the rule's areas, the cell Excel reads relative references from.
pub(super) fn cf_rule_xml(cf: &CondFormat, priority: u32, out: &mut Out) -> String {
let tl = RangeRef::top_left(&cf.ranges).map(|c| c.a1()).unwrap_or_else(|| "A1".into());
let tl = cf.ranges.first().map(|r| r.start.a1()).unwrap_or_else(|| "A1".into());
let stop = if cf.stop_if_true { " stopIfTrue=\"1\"" } else { "" };
let mut dxf = |st: &Style| dxf_id(&mut out.dxfs, st);
let f = |x: &str| format!("<formula>{}</formula>", esc(&text_to_file(x)));
-18
View File
@@ -1678,21 +1678,3 @@ fn workbook_view_writer_clamps_out_of_range_model_values() {
assert_eq!(back.view.tab_ratio, 1000);
}
}
#[test]
fn generated_rule_formulas_use_the_top_left_cell_of_every_area() {
// Issue #3152: the areas aren't in top-to-bottom order; the formula is written for C2, not C5.
let mut wb = Workbook::new();
let red = Box::new(Style::default());
wb.sheet_mut(0).unwrap().cond_formats.push(CondFormat {
ranges: vec![rr("C5:C6"), rr("C2:C3")],
rule: CfRule::ContainsText { text: "x".into(), style: red },
priority: 1,
stop_if_true: false,
});
let bytes = write_xlsx(&wb).unwrap();
let mut z = zip::ZipArchive::new(std::io::Cursor::new(bytes)).unwrap();
let mut xml = String::new();
z.by_name("xl/worksheets/sheet1.xml").unwrap().read_to_string(&mut xml).unwrap();
assert!(xml.contains("<formula>NOT(ISERROR(SEARCH(\"x\",C2)))</formula>"), "{xml}");
}
-16
View File
@@ -652,19 +652,3 @@ fn xls_short_window2_is_ignored() {
assert_eq!(v(&wb, 0, "A1"), Value::Number(7.0));
}
}
/// Shared-formula followers each keep their own text, charged to the workbook's text allowance:
/// with no allowance left they keep their cached values, and the import still succeeds.
#[test]
fn shared_formula_text_counts_against_the_text_allowance() {
let file = compound("Workbook", &sample(false));
// The smallest allowance that reads every string: nothing is left for expanded formulas.
let left = (0..1000).find(|n| crate::xls::read_xls_with(&file, crate::xls::Budget::with_text_left(*n)).is_ok()).unwrap();
let (wb, report) = crate::xls::read_xls_with(&file, crate::xls::Budget::with_text_left(left)).unwrap();
assert_eq!(ftext(&wb, "B6"), None);
assert_eq!(v(&wb, 0, "B6"), Value::Number(20.0));
assert!(report.warnings.iter().any(|w| w.contains("shared-formula text")), "{:?}", report.warnings);
// With room, the followers keep their formulas.
let (wb, _) = crate::xls::read_xls_with(&file, crate::xls::Budget::default()).unwrap();
assert!(ftext(&wb, "B6").is_some());
}
+1 -29
View File
@@ -89,11 +89,6 @@ impl Budget {
pub(crate) fn with_max_records(max_records: usize) -> Self {
Budget { max_records, ..Budget::default() }
}
/// A budget with only `left` bytes of text allowance (tests).
#[cfg(test)]
pub(crate) fn with_text_left(left: usize) -> Self {
Budget { text: MAX_TEXT.saturating_sub(left), ..Budget::default() }
}
fn record(&mut self) -> Result<(), IoError> {
self.records = self.records.saturating_add(1);
if self.records > self.max_records {
@@ -108,16 +103,6 @@ impl Budget {
}
Ok(())
}
/// Charges `len` bytes of text if they fit the allowance, leaving it untouched otherwise:
/// for text the import can do without (expanded shared formulas keep their cached values).
fn try_text(&mut self, len: usize) -> bool {
let total = self.text.saturating_add(len);
let fits = total <= MAX_TEXT;
if fits {
self.text = total;
}
fits
}
fn text(&mut self, len: usize) -> Result<(), IoError> {
self.text = self.text.saturating_add(len);
if self.text > MAX_TEXT {
@@ -502,7 +487,6 @@ fn rk(v: u32) -> Value {
/// keep their cached values).
fn resolve_pending(
st: &mut SheetState<'_>,
budget: &mut Budget,
arrays: &HashMap<CellRef, (RangeRef, Parsed)>,
shared: &HashMap<CellRef, Parsed>,
pending: &[Pending],
@@ -520,18 +504,6 @@ fn resolve_pending(
}
shared_attaches += 1;
st.attach(p.pos, f, Mode::Shared, None);
let len = st.sheet.cell(p.pos).and_then(|c| c.formula.as_ref()).map(|f| f.text.len());
// Every follower keeps its own text: charge it to the workbook's text allowance, and
// past it drop the formula again so the cell keeps its cached value.
if let Some(len) = len
&& !budget.try_text(len)
{
if let Some(cell) = st.sheet.cells.get_mut(p.pos) {
cell.formula = None;
}
st.unsupported("more shared-formula text than the import allows");
break;
}
let imported = st.sheet.cell(p.pos).and_then(|c| c.formula.as_ref()).is_some_and(|f| f.text.chars().count() <= MAX_SHARED_TEMPLATE);
if !imported {
failed.insert(p.anchor);
@@ -614,7 +586,7 @@ fn worksheet(
// Shared and array formulas: their definitions follow the first cell that uses them.
let (arrays, shared) = (std::mem::take(&mut st.arrays), std::mem::take(&mut st.shared));
let pending = std::mem::take(&mut st.pending);
resolve_pending(&mut st, budget, &arrays, &shared, &pending);
resolve_pending(&mut st, &arrays, &shared, &pending);
blank_array_followers(&mut st, &pending);
if st.dropped > 0 {
report.warn(format!("{} cells outside the grid were skipped.", st.dropped));