engine: PivotTable filters test each record against a set of selected labels (#3279)

Every source record scanned the filter's whole selection, so a large
selection multiplied by many records was slow even when nothing passed.
Each filter's labels are lowercased into a set once per computation.

crates/chart/src/render/kinds.rs

@@ -203,11 +203,12 @@ pub(super) fn pie(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx, inne
 
 // ---------------------------------------------------------------- treemap
 
-/// Worst aspect ratio of a row with the given sum, smallest and largest area.
-fn worst(s: f64, mn: f64, mx: f64, side: f64) -> f64 {
+fn worst(row: &[f64], side: f64) -> f64 {
+    let s: f64 = row.iter().sum();
     if s <= 0.0 || side <= 0.0 {
         return f64::INFINITY;
     }
+    let (mn, mx) = row.iter().fold((f64::INFINITY, 0.0f64), |(a, b), v| (a.min(*v), b.max(*v)));
     let s2 = s * s;
     let w2 = side * side;
     (w2 * mx / s2).max(s2 / (w2 * mn))
@@ -224,8 +225,6 @@ fn squarify(items: &[(usize, f64)], r: Bx) -> Vec<(usize, Bx)> {
     let mut out = Vec::with_capacity(items.len());
     let mut rem = r;
     let mut row: Vec<(usize, f64)> = Vec::new();
-    // The row's sum, smallest and largest area, kept as items join so each step is O(1).
-    let (mut sum, mut mn, mut mx) = (0.0f64, f64::INFINITY, 0.0f64);
     let mut i = 0;
     let layout = |row: &[(usize, f64)], rem: &mut Bx, out: &mut Vec<(usize, Bx)>| {
         let s: f64 = row.iter().map(|x| x.1).sum();
@@ -257,14 +256,15 @@ fn squarify(items: &[(usize, f64)], r: Bx) -> Vec<(usize, Bx)> {
     while let Some(&(j, v)) = items.get(i) {
         let a = v * scale;
         let side = rem.w.min(rem.h) as f64;
-        if row.is_empty() || worst(sum + a, mn.min(a), mx.max(a), side) <= worst(sum, mn, mx, side) {
+        let cur: Vec<f64> = row.iter().map(|x| x.1).collect();
+        let mut with = cur.clone();
+        with.push(a);
+        if row.is_empty() || worst(&with, side) <= worst(&cur, side) {
             row.push((j, a));
-            (sum, mn, mx) = (sum + a, mn.min(a), mx.max(a));
             i += 1;
         } else {
             layout(&row, &mut rem, &mut out);
             row.clear();
-            (sum, mn, mx) = (0.0, f64::INFINITY, 0.0);
         }
     }
     if !row.is_empty() {
@@ -279,7 +279,6 @@ pub(super) fn treemap(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
         s.values.iter().take(MAX_MARKERS).enumerate().filter_map(|(j, v)| v.filter(|v| *v > 0.0).map(|v| (j, v))).collect();
     items.sort_by(|a, b| b.1.total_cmp(&a.1));
     let f = Fmt::new(&s.number_format);
-    let value_of: std::collections::HashMap<usize, f64> = items.iter().copied().collect();
     for (j, b) in squarify(&items, area) {
         let fill = point_color(data, j);
         ctx.rect(b.x, b.y, b.w, b.h, fill, Some((WHITE, 1.5)));
@@ -287,7 +286,7 @@ pub(super) fn treemap(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
             let name = ctx.fit(&cat_label(data, j), LABEL_SIZE, b.w - 8.0);
             ctx.text(b.x + 4.0, b.y + 4.0, &name, LABEL_SIZE, on(fill), (HAlign::Left, VAlign::Top));
             if chart.data_labels && b.h > LABEL_SIZE * 3.2 {
-                let v = value_of.get(&j).copied().unwrap_or(0.0);
+                let v = items.iter().find(|x| x.0 == j).map(|x| x.1).unwrap_or(0.0);
                 let t = ctx.fit(&f.format(v, None), LABEL_SIZE, b.w - 8.0);
                 ctx.text(b.x + 4.0, b.y + 4.0 + LABEL_SIZE * 1.4, &t, LABEL_SIZE, on(fill), (HAlign::Left, VAlign::Top));
             }

crates/engine/src/cmd/pivot/tests.rs

@@ -168,6 +168,19 @@ fn filters_and_report_filter_rows() {
     assert!(s.execute("pivot.filter", json!({"field": "Product", "selected": []})).is_err());
 }
 
+/// A selection of the most labels allowed (100,000) is looked up once per record, not scanned: the
+/// report still filters case-insensitively.
+#[test]
+fn a_huge_filter_selection_is_matched_through_a_set() {
+    let mut s = sales();
+    s.execute("insert.pivotTable", json!({"rows": ["Product"], "values": ["Sales"], "filters": ["Region"]})).unwrap();
+    let mut selected: Vec<String> = (0..99_999).map(|i| format!("Region {i}")).collect();
+    selected.push("EAST".into());
+    s.execute("pivot.filter", json!({"field": "Region", "selected": selected})).unwrap();
+    let gt = find_row(&s, "Grand Total").unwrap();
+    assert_eq!(val(&s, &CellRef::new(gt, 1).a1()), Value::Number(415.0));
+}
+
 #[test]
 fn show_values_as() {
     let mut s = sales();

crates/engine/src/pivot/compute.rs

@@ -77,6 +77,8 @@ struct AggregateInput<'a> {
     extra: &'a [usize],
     filters: &'a [(usize, &'a PivotFilter, PivotDateGroup, bool)],
     filter_fmts: &'a [String],
+    /// Each filter's selected labels, ASCII-lowercased, so a record's test is one probe.
+    filter_sets: &'a [Option<HashSet<String>>],
     row_fmts: &'a [String],
     col_fmts: &'a [String],
     empty: bool,
@@ -99,10 +101,10 @@ fn aggregate_record(
     ri: usize,
     rec: &[Value],
 ) -> Result<(), String> {
-    for ((c, field, group, _), fmt) in input.filters.iter().zip(input.filter_fmts) {
-        if let Some(selected) = &field.selected {
+    for (((c, _, group, _), fmt), selected) in input.filters.iter().zip(input.filter_fmts).zip(input.filter_sets) {
+        if let Some(selected) = selected {
             let label = item_label(input.wb, rec.get(*c).unwrap_or(&Value::Empty), *group, fmt);
-            if !selected.iter().any(|value| value.eq_ignore_ascii_case(&label)) {
+            if !selected.contains(&label.to_ascii_lowercase()) {
                 return Ok(());
             }
         }
@@ -475,6 +477,8 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
 
     // ---- aggregate
     let filter_fmts: Vec<String> = filters.iter().map(|f| fmt_of(f.0)).collect();
+    let filter_sets: Vec<Option<HashSet<String>>> =
+        filters.iter().map(|(_, field, _, _)| field.selected.as_ref().map(|s| s.iter().map(|v| v.to_ascii_lowercase()).collect())).collect();
     let row_fmts: Vec<String> = rows.iter().map(|(c, _)| fmt_of(*c)).collect();
     let col_fmts: Vec<String> = cols.iter().map(|(c, _)| fmt_of(*c)).collect();
     let aggregate = aggregate_source(
@@ -488,6 +492,7 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
             extra: &extra,
             filters: &filters,
             filter_fmts: &filter_fmts,
+            filter_sets: &filter_sets,
             row_fmts: &row_fmts,
             col_fmts: &col_fmts,
             empty,

crates/numfmt/src/decimal.rs

@@ -136,9 +136,6 @@ pub(crate) fn fixed(a: f64, decimals: usize) -> (String, String) {
 /// General format squeezed into `max_chars` characters. Excel shows fewer decimals, then
 /// scientific notation, then "####" when a column is narrow; `None` means the caller paints "####".
 pub fn format_general_fit(n: f64, max_chars: usize) -> Option<String> {
-    // The widest fixed rendering of a double is about 330 characters; a larger request only
-    // pads zero decimals the trim below throws away.
-    let max_chars = max_chars.min(1024);
     if !n.is_finite() {
         return None;
     }
@@ -217,8 +214,6 @@ mod tests {
     fn general_fit() {
         assert_eq!(format_general_fit(1e11, 11).as_deref(), Some("1E+11"));
         assert_eq!(format_general_fit(12345678901.0, 11).as_deref(), Some("12345678901"));
-        // A huge width neither allocates width-sized padding nor changes the text.
-        assert_eq!(format_general_fit(1.5, usize::MAX).as_deref(), Some("1.5"));
         assert_eq!(format_general_fit(123456789012.0, 11).as_deref(), Some("1.23457E+11"));
         assert_eq!(format_general_fit(0.1 + 0.2, 11).as_deref(), Some("0.3"));
         assert_eq!(format_general_fit(1.0 / 3.0, 11).as_deref(), Some("0.333333333"));