Compare commits

..
13 changed files with 158 additions and 129 deletions
+2 -9
View File
@@ -147,10 +147,10 @@ impl RangeRef {
RangeRef::new(CellRef::new(0, 0), CellRef::new(MAX_ROWS - 1, MAX_COLS - 1))
}
pub fn height(&self) -> u32 {
self.end.row.saturating_sub(self.start.row).saturating_add(1)
self.end.row - self.start.row + 1
}
pub fn width(&self) -> u32 {
self.end.col.saturating_sub(self.start.col).saturating_add(1)
self.end.col - self.start.col + 1
}
pub fn count(&self) -> u64 {
self.height() as u64 * self.width() as u64
@@ -300,13 +300,6 @@ pub fn split_sheet(reference: &str) -> (Option<String>, &str) {
mod tests {
use super::*;
#[test]
fn hostile_range_dimensions_saturate_instead_of_wrapping() {
let r = RangeRef { start: CellRef::new(0, 0), end: CellRef::new(u32::MAX, u32::MAX) };
assert_eq!((r.height(), r.width()), (u32::MAX, u32::MAX));
assert_eq!(r.count(), u64::from(u32::MAX) * u64::from(u32::MAX));
}
#[test]
fn range_parse_rejects_signed_rows() -> Result<(), std::io::Error> {
assert!(RangeRef::parse("+1:+3").is_none());
+1 -2
View File
@@ -184,8 +184,7 @@ pub(crate) fn grow_autofilter(sh: &mut Sheet, at: CellRef) {
pub(crate) fn apply_filter(wb: &mut Workbook, sheet: usize) {
let Some(sh) = wb.sheet(sheet) else { return };
let Some(af) = sh.autofilter.clone() else { return };
// An imported range can name rows past the grid; none of those exist to hide.
let r = RangeRef::new(af.range.start, CellRef::new(af.range.end.row.min(gridcraft_core::MAX_ROWS - 1), af.range.end.col));
let r = af.range;
let mut hide = Vec::new();
// Precompute per-criterion top10 threshold and average once, not per row.
let mut col_stats: std::collections::HashMap<usize, (Option<f64>, f64)> = std::collections::HashMap::new();
-7
View File
@@ -5,9 +5,6 @@ use super::{
// ---------------------------------------------------------------- tools
/// Most cells (rows times compared columns) one Remove Duplicates call reads.
const MAX_COMPARED_CELLS: u64 = 50_000_000;
pub(super) fn remove_duplicates(s: &mut Session, p: &Json) -> Result<Json> {
let (sheet, r) = data_target(s, p, "data.removeDuplicates")?;
let d = s.doc()?;
@@ -27,10 +24,6 @@ pub(super) fn remove_duplicates(s: &mut Session, p: &Json) -> Result<Json> {
if cols.is_empty() || cols.iter().any(|c| !(r.start.col..=r.end.col).contains(c)) {
return Err(bad("data.removeDuplicates", "`columns` must name at least one column of the range"));
}
// Rows are compared one by one, so a sparse sheet's enclosing rectangle is bounded like a list.
if r.count() > MAX_COMPARED_CELLS {
return Err(bad("data.removeDuplicates", "the range is too large"));
}
let start = r.start.row + header as u32;
let mut removed = 0;
edit(s, |cx| {
+1 -4
View File
@@ -289,14 +289,11 @@ pub(super) fn circle_invalid(s: &mut Session, _: &Json) -> Result<Json> {
let sheet = d.wb.active_sheet();
let Some(sh) = d.wb.sheet(sheet) else { return Err(EngineError::NoDocument) };
let mut bad_cells = Vec::new();
// One scan allowance for the whole command: duplicate or overlapping ranges don't multiply it.
let mut budget = 100_000usize;
for dv in &sh.validations {
for r in &dv.ranges {
let r = sh.used_range().and_then(|u| r.intersection(&u));
let Some(r) = r else { continue };
for c in r.iter().take(budget) {
budget -= 1;
for c in r.iter().take(100_000) {
let text = sh.input_text(c);
if !text.is_empty() && check_validation(&d.wb, sheet, c, &text).is_some() {
bad_cells.push(c.a1());
+1 -5
View File
@@ -130,11 +130,7 @@ pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
let mut n = 0;
for si in sheets {
let cells: Vec<(CellRef, String)> =
// A hidden formula's source is not searched: a count or error would reveal its text.
cx.wb
.sheet(si)
.map(|sh| sh.cells.iter().filter(|(c, _)| !crate::display::formula_hidden(&cx.wb, sh, *c)).map(|(c, _)| (c, sh.input_text(c))).collect())
.unwrap_or_default();
cx.wb.sheet(si).map(|sh| sh.cells.iter().map(|(c, _)| (c, sh.input_text(c))).collect()).unwrap_or_default();
for (c, text) in cells {
if (!all && c != active) || selection.as_ref().is_some_and(|sel| !sel.contains(c)) {
continue;
+33 -31
View File
@@ -140,44 +140,46 @@ pub(super) fn autofit_cols(s: &mut Session, p: &Json) -> Result<Json> {
let measure = s.text_width.clone();
edit(s, |cx| {
let Some(sh) = cx.wb.sheet(si) else { return Ok(Json::Null) };
let mut widths = Vec::new();
let mut measured: std::collections::HashMap<StyleId, std::collections::HashMap<String, f32>> = Default::default();
let mut distinct = 0usize;
// Selected columns, then one pass over the populated cells (the store is row-oriented, so a
// scan per column would revisit every row for each selected column, empty or not).
let cols: std::collections::BTreeSet<u32> = lines.iter().flat_map(|&(a, b)| a..=b.min(a + 16383)).collect();
let mut maxes: std::collections::BTreeMap<u32, f32> = Default::default();
if let (Some(u), Some(&first), Some(&last)) = (sh.used_range(), cols.first(), cols.last()) {
let span = RangeRef::new(CellRef::new(u.start.row, first), CellRef::new(u.end.row, last));
for (cell, _) in sh.cells.iter_range(span) {
if !cols.contains(&cell.col) || sh.merge_at(cell).is_some_and(|m| !m.is_single()) {
continue;
}
let id = sh.style_id(cell);
let st = cx.wb.styles.get(id);
let text = crate::display::cell_text(&cx.wb, sh, cell);
for line in text.lines() {
let w = match &measure {
Some(m) => {
let known = measured.entry(id).or_default();
match known.get(line) {
Some(w) => *w,
None => {
let w = m(line, &st.font, distinct < EXACT_TEXT_WIDTHS);
known.insert(line.to_owned(), w);
distinct += 1;
w
let used = sh.used_range();
for (a, b) in lines {
for c in a..=b.min(a + 16383) {
let Some(u) = used else { continue };
let col = RangeRef::new(CellRef::new(u.start.row, c), CellRef::new(u.end.row, c));
let mut max: f32 = 0.0;
for (cell, _) in sh.cells.iter_range(col) {
if sh.merge_at(cell).is_some_and(|m| !m.is_single()) {
continue;
}
let id = sh.style_id(cell);
let st = cx.wb.styles.get(id);
let text = crate::display::cell_text(&cx.wb, sh, cell);
for line in text.lines() {
let w = match &measure {
Some(m) => {
let known = measured.entry(id).or_default();
match known.get(line) {
Some(w) => *w,
None => {
let w = m(line, &st.font, distinct < EXACT_TEXT_WIDTHS);
known.insert(line.to_owned(), w);
distinct += 1;
w
}
}
}
}
None => approx_text_width(line, st.font.size, st.font.bold),
};
let w = w + 6.0 + st.align.indent as f32 * 9.0 + sh.filter_button_space(cell);
let max = maxes.entry(cell.col).or_insert(0.0);
*max = max.max(w);
None => approx_text_width(line, st.font.size, st.font.bold),
};
max = max.max(w + 6.0 + st.align.indent as f32 * 9.0 + sh.filter_button_space(cell));
}
}
if max > 0.0 {
widths.push((c, max.clamp(8.0, 1785.0)));
}
}
}
let widths: Vec<(u32, f32)> = maxes.into_iter().filter(|&(_, m)| m > 0.0).map(|(c, m)| (c, m.clamp(8.0, 1785.0))).collect();
let sh = cx.sheet_mut(si)?;
for (c, w) in widths {
let e = sh.cols.entry(c).or_default();
@@ -83,9 +83,6 @@ pub(crate) fn criterion_matches(v: &Value, text: &str, crit: &Value) -> bool {
}
}
/// Most (list row, criteria row) pairs one Advanced Filter tests.
const MAX_FILTER_TESTS: u64 = 50_000_000;
pub(super) fn advanced_filter(s: &mut Session, p: &Json) -> Result<Json> {
const CMD: &str = "data.advancedFilter";
let d = s.doc()?;
@@ -136,10 +133,6 @@ pub(super) fn advanced_filter(s: &mut Session, p: &Json) -> Result<Json> {
rows.push(conds);
}
}
// Each list row is tried against every criteria row, so bound their product too.
if u64::from(list.height()) * rows.len() as u64 > MAX_FILTER_TESTS {
return Err(bad(CMD, "the list and criteria ranges together are too large"));
}
let matches_row = |row: u32| -> bool {
if rows.is_empty() {
return true;
-9
View File
@@ -297,12 +297,3 @@ fn consolidate_by_position_and_label() {
assert!(s.execute("data.consolidate", json!({"sources": []})).is_err());
assert!(s.execute("data.consolidate", json!({"sources": ["A1"], "function": "median"})).is_err());
}
#[test]
fn advanced_filter_refuses_a_list_times_criteria_product_over_the_work_limit() {
let mut s = s();
s.execute("range.setValues", json!({"range": "A1", "values": [["Name"], ["A"]]})).unwrap();
s.execute("range.setValues", json!({"range": "H1", "values": [["Name"], ["A"]]})).unwrap();
// A sparse million-row list against 9,999 blank criteria rows would be ~10 billion tests.
assert!(s.execute("data.advancedFilter", json!({"range": "A2:A1048576", "criteria": "H1:H10000"})).is_err());
}
+3 -12
View File
@@ -1280,18 +1280,9 @@ fn content_differs(b: Option<&Cell>, a: Option<&Cell>) -> bool {
/// Objects added, changed and removed between two versions of a sheet.
fn objects(b: &Sheet, a: &Sheet) -> (usize, usize, usize) {
fn count<T: PartialEq>(b: &[T], a: &[T], id: impl Fn(&T) -> u32) -> (usize, usize, usize) {
// Objects grouped by id, so each lookup is a map probe instead of a scan of the list.
fn group<'a, T>(v: &'a [T], id: &impl Fn(&T) -> u32) -> std::collections::HashMap<u32, Vec<&'a T>> {
let mut m: std::collections::HashMap<u32, Vec<&T>> = std::collections::HashMap::new();
for x in v {
m.entry(id(x)).or_default().push(x);
}
m
}
let (gb, ga) = (group(b, &id), group(a, &id));
let added = a.iter().filter(|x| !gb.contains_key(&id(x))).count();
let removed = b.iter().filter(|x| !ga.contains_key(&id(x))).count();
let changed = b.iter().filter(|x| ga.get(&id(x)).is_some_and(|ys| ys.iter().any(|y| *y != *x))).count();
let added = a.iter().filter(|x| !b.iter().any(|y| id(y) == id(x))).count();
let removed = b.iter().filter(|x| !a.iter().any(|y| id(y) == id(x))).count();
let changed = b.iter().filter(|x| a.iter().any(|y| id(y) == id(x) && y != *x)).count();
(added, changed, removed)
}
let parts = [count(&b.charts, &a.charts, |o| o.id), count(&b.images, &a.images, |o| o.id), count(&b.shapes, &a.shapes, |o| o.id)];
+24
View File
@@ -57,6 +57,10 @@ fn rows_ref(sheet: &str, origin: CellRef, col: u32, rows: &[u32]) -> Option<Stri
/// Most category rows a PivotChart plots.
const MAX_CHART_ROWS: usize = 10_000;
/// Most series a PivotChart gets: the chart renderer reads at most 255 series, and each one owns
/// reference text as long as its category rows, copied into every linked chart.
const MAX_CHART_SERIES: usize = 255;
/// A PivotChart's series for a report written at `origin`: categories are the innermost row
/// items, one series per item column (column items × value fields); totals are left out.
pub fn chart_series(sheet: &str, origin: CellRef, out: &Output) -> Vec<Series> {
@@ -64,6 +68,7 @@ pub fn chart_series(sheet: &str, origin: CellRef, out: &Output) -> Vec<Series> {
let categories = out.label_col.and_then(|c| rows_ref(sheet, origin, c, &rows));
out.chart_cols
.iter()
.take(MAX_CHART_SERIES)
.filter_map(|(c, name)| {
Some(Series {
name: Some(format!("\"{}\"", name.replace('"', "\"\""))),
@@ -106,3 +111,22 @@ pub fn clear_output(wb: &mut Workbook, sheet: usize, idx: usize) {
p.last_range = None;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_pivot_chart_gets_at_most_the_series_the_renderer_reads() {
let out = Output {
grid: vec![],
row_kinds: vec![],
body_offset: 0,
width: 1000,
chart_rows: vec![1, 2, 3],
chart_cols: (1..1000).map(|c| (c, format!("S{c}"))).collect(),
label_col: Some(0),
};
assert_eq!(chart_series("Sheet1", CellRef::new(0, 0), &out).len(), MAX_CHART_SERIES);
}
}
+64 -29
View File
@@ -1,5 +1,7 @@
use super::items::{Acc, FieldItems, build_tree, collect_siblings, is_collapsed, item_label};
use super::output::{AggMap, CellKind, ColKind, ColSpec, Ctx, Grid, Line, LineKind, Output, RowKind, ValSrc, data_cols_exceed_sheet, flatten_cols};
use super::output::{
AggMap, CellKind, ColKind, ColSpec, Ctx, Grid, Line, LineKind, Output, RowKind, ValSrc, caption, data_cols_exceed_sheet, flatten_cols,
};
use super::{
CalcSet, CellError, CellRef, HashMap, HashSet, MAX_AXIS_FIELDS, MAX_COLS, MAX_VALUE_FIELDS, PivotDateGroup, PivotField, PivotFilter, PivotFunc,
PivotLayout, PivotShowAs, PivotTable, PivotValue, Source, Value, Workbook, read_source,
@@ -92,6 +94,10 @@ struct AggregateData {
col_leaves: HashSet<Vec<u32>>,
}
/// Most accumulators (groups times value columns) one report may hold: twice what the 5 million
/// group limit allowed at one value field.
const MAX_ACCUMULATORS: usize = 16_000_000;
fn aggregate_record(
input: &AggregateInput<'_>,
data: &mut AggregateData,
@@ -150,7 +156,9 @@ fn aggregate_record(
if !input.cols.is_empty() && data_cols_exceed_sheet(data.col_leaves.len(), input.pt.grand_totals_rows, input.vals.len()) {
return Err("The PivotTable report will not fit on the sheet.".into());
}
if data.aggs.len() > 5_000_000 {
// Each entry holds one accumulator per value field and calculated-field source column, so the
// width counts too: a handful of groups over hundreds of fields is large as well.
if data.aggs.len() > 5_000_000 || data.aggs.len().saturating_mul(input.vals.len() + input.extra.len()) > MAX_ACCUMULATORS {
return Err("The PivotTable report is too large.".into());
}
Ok(())
@@ -257,8 +265,8 @@ fn write_headers(g: &mut Grid, input: HeaderInput<'_>) -> Result<(), String> {
let lv = spec.path.len().saturating_sub(1);
let label = spec.path.last().and_then(|it| col_items.get(lv).map(|fi| fi.label(*it))).unwrap_or_default();
let text = match vi {
Some(vi) if k > 1 => format!("{label} {}", val_name(*vi)),
_ => format!("{label} Total"),
Some(vi) if k > 1 => caption(&label, &val_name(*vi)),
_ => caption(&label, "Total"),
};
g.set(first_level + lv, c, Value::text(text), CellKind::ColLabel, 0, None);
}
@@ -316,6 +324,7 @@ struct ShowContext<'a> {
value_index: usize,
level0: &'a [u32],
siblings: &'a HashMap<Vec<u32>, Vec<u32>>,
cache: &'a ShowCache,
}
fn number(value: &Option<Value>) -> Option<f64> {
@@ -332,42 +341,67 @@ fn ratio(a: Value, b: Option<Value>) -> Value {
}
}
/// What Running Total and Rank need from other cells, computed once per sibling set instead of
/// once per displayed value (which rescanned the whole set every time).
type ShowKey = (Vec<u32>, Vec<u32>, usize);
/// Cumulative values by top-level item, and the total of all of them.
type RunningTotals = (HashMap<u32, f64>, f64);
#[derive(Default)]
struct ShowCache {
/// Ranked values' sibling numbers, sorted ascending without repeats, by (parent, column, value).
ranks: std::cell::RefCell<HashMap<ShowKey, Vec<f64>>>,
/// Running totals by top-level item, with the total of all of them, by (rest of path, column, value).
running: std::cell::RefCell<HashMap<ShowKey, RunningTotals>>,
}
fn running_total(raw: Value, lookup: &ValueLookup<'_>, context: &ShowContext<'_>) -> Value {
let Some((first, _)) = context.row_path.split_first() else { return raw };
let Some((first, rest)) = context.row_path.split_first() else { return raw };
if !matches!(raw, Value::Number(_)) {
return raw;
}
let mut total = 0.0;
for item in context.level0 {
let mut path = context.row_path.to_vec();
if let Some(first_item) = path.first_mut() {
*first_item = *item;
let mut cache = context.cache.running.borrow_mut();
let (by_item, all) = cache.entry((rest.to_vec(), context.col_path.to_vec(), context.value_index)).or_insert_with(|| {
let mut total = 0.0;
let mut by_item = HashMap::new();
for item in context.level0 {
let mut path = Vec::with_capacity(rest.len() + 1);
path.push(*item);
path.extend_from_slice(rest);
// An item with no number here adds nothing and is not stored (the shown cell always has one).
let Some(value) = number(&lookup.get(&path, context.col_path, context.value_index)) else { continue };
total += value;
by_item.entry(*item).or_insert(total);
}
total += number(&lookup.get(&path, context.col_path, context.value_index)).unwrap_or(0.0);
if item == first {
break;
}
}
Value::number(total)
(by_item, total)
});
Value::number(by_item.get(first).copied().unwrap_or(*all))
}
fn ranked_value(raw: Value, lookup: &ValueLookup<'_>, context: &ShowContext<'_>) -> Value {
let Some((_, parent)) = context.row_path.split_last() else { return Value::Empty };
let Some(me) = raw.as_f64() else { return raw };
let siblings = context.siblings.get(parent).cloned().unwrap_or_default();
let mut cache = context.cache.ranks.borrow_mut();
let sorted = cache.entry((parent.to_vec(), context.col_path.to_vec(), context.value_index)).or_insert_with(|| {
let mut all: Vec<f64> = context
.siblings
.get(parent)
.into_iter()
.flatten()
.filter_map(|sibling| {
let mut path = parent.to_vec();
path.push(*sibling);
number(&lookup.get(&path, context.col_path, context.value_index))
})
.collect();
all.sort_by(f64::total_cmp);
all.dedup();
all
});
// Excel's ranks are dense: ties share a rank and the next value takes the next one
// (5, 4, 3, 3, 4 rank 1, 2, 3, 3, 2), so count the distinct larger values.
let mut larger: Vec<f64> = siblings
.into_iter()
.filter_map(|sibling| {
let mut path = parent.to_vec();
path.push(sibling);
number(&lookup.get(&path, context.col_path, context.value_index)).filter(|value| *value > me)
})
.collect();
larger.sort_by(f64::total_cmp);
larger.dedup();
Value::number(larger.len() as f64 + 1.0)
let larger = sorted.len() - sorted.partition_point(|value| *value <= me);
Value::number(larger as f64 + 1.0)
}
fn show_value(definition: &PivotValue, raw: Value, lookup: &ValueLookup<'_>, context: &ShowContext<'_>) -> Value {
@@ -637,6 +671,7 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
})
.collect();
let lookup = ValueLookup { wb, source: src, calc: &calc, vals: &vals, extra: &extra, aggs: &aggs, value_count: k };
let show_cache = ShowCache::default();
let mut chart_rows: Vec<u32> = Vec::new();
let chart_cols: Vec<(u32, String)> = data_cols
.iter()
@@ -694,7 +729,7 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
let Some((_, vdef)) = vals.get(*vi) else { continue };
let cp = spec.path.as_slice();
let Some(raw) = lookup.get(rp, cp, *vi) else { continue };
let context = ShowContext { row_path: rp, col_path: cp, value_index: *vi, level0: &level0, siblings: &siblings };
let context = ShowContext { row_path: rp, col_path: cp, value_index: *vi, level0: &level0, siblings: &siblings, cache: &show_cache };
let shown = show_value(vdef, raw, &lookup, &context);
if let Some(pr) = probe.as_deref_mut() {
if pr.at == Some((r, l + j)) {
+29 -3
View File
@@ -121,6 +121,18 @@ pub(super) enum ColKind {
Grand,
}
/// Longest item caption Excel keeps; a subtotal caption repeats its parent's label for every value
/// field at every level, so a long source label is cut rather than multiplied.
const MAX_CAPTION_LABEL_CHARS: usize = 255;
/// `label` (cut to [`MAX_CAPTION_LABEL_CHARS`]) and `suffix`, as in "East Total".
pub(super) fn caption(label: &str, suffix: &str) -> String {
let mut out: String = label.chars().take(MAX_CAPTION_LABEL_CHARS).collect();
out.push(' ');
out.push_str(suffix);
out
}
pub(super) struct ColSpec {
pub(super) kind: ColKind,
pub(super) path: Vec<u32>,
@@ -162,7 +174,7 @@ impl Ctx<'_> {
leaf: false,
path: prefix.to_vec(),
values: true,
labels: vec![(col, Value::text(format!("{label} {name}")), indent, None)],
labels: vec![(col, Value::text(caption(label, name)), indent, None)],
vi: Some(vi),
});
}
@@ -249,7 +261,7 @@ impl Ctx<'_> {
leaf: false,
path: prefix.clone(),
values: true,
labels: vec![(col, Value::text(format!("{label} Total")), indent, None)],
labels: vec![(col, Value::text(caption(&label, "Total")), indent, None)],
vi,
});
}
@@ -316,7 +328,7 @@ impl Ctx<'_> {
leaf: false,
path: prefix.clone(),
values: true,
labels: vec![(col, Value::text(format!("{label} Total")), 0, None)],
labels: vec![(col, Value::text(caption(&label, "Total")), 0, None)],
vi,
});
}
@@ -438,3 +450,17 @@ pub(super) fn cell_style(lk: &Look, rk: RowKind, cell: &OutCell, last_header: bo
}
s
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn captions_cut_a_long_parent_label() {
assert_eq!(caption("East", "Total"), "East Total");
let long = "é".repeat(100_000);
let c = caption(&long, "Sum of Sales");
assert_eq!(c.chars().count(), MAX_CAPTION_LABEL_CHARS + " Sum of Sales".len());
assert!(c.ends_with(" Sum of Sales"));
}
}
-11
View File
@@ -5572,14 +5572,3 @@ fn clearing_links_and_notes_keeps_allow_edit_ranges() {
let sh = s.doc().unwrap().wb.active().unwrap().clone();
assert!(sh.hyperlinks.is_empty() && sh.comments.is_empty());
}
#[test]
fn replace_does_not_search_hidden_formula_source() {
let mut s = s();
s.execute("cell.set", json!({"cell": "A1", "input": "=SEQUENCE(3)*7"})).unwrap();
s.execute("home.formatCells", json!({"range": "A1", "style": {"protection": {"locked": true, "hidden": true}}})).unwrap();
s.execute("review.protectSheet", json!({})).unwrap();
let hit = s.execute("edit.replace", json!({"what": "SEQUENCE", "with": "X"})).map_err(|e| e.to_string());
let miss = s.execute("edit.replace", json!({"what": "NOSUCHTEXT", "with": "X"})).map_err(|e| e.to_string());
assert_eq!(hit, miss);
}