PDF export: index merged areas when drawing a block

draw_block checked every cell against every merge meeting the block,
and the fill, border and text passes searched the merge list again
for each merge start, so an imported sheet with many merge ranges in
a print area cost cells x merges (and merges x merges) comparisons.

The merges meeting a block are now gathered once and swept down the
rows: whether a cell is covered is a BTreeMap lookup among the merges
active on its row, and merge starts are found through a HashMap. A
merge overlapping one kept before it (only possible in a damaged file)
is left out, as Excel does when it repairs the file. Hyperlink
rectangles use the same index instead of scanning all sheet merges.

crates/chart/src/render/cartesian.rs

@@ -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 });
                     }

crates/chart/src/render/lines.rs

@@ -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");
-    }
 }

crates/core/src/addr.rs

@@ -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 [

crates/engine/src/cf.rs

@@ -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,

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

@@ -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,

crates/engine/src/cmd/data/validation.rs

@@ -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;

crates/engine/src/cmd/edit/paste_special.rs

@@ -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)];

crates/engine/src/cmd/insert.rs

@@ -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() {

crates/engine/src/cmd/print/draw.rs

@@ -228,6 +228,82 @@ fn draw_border(pg: &mut Page, b: &BorderLine, wb: &Workbook, start: Point, end:
     pg.stroke_line_dashed(Point::new(x0, y0), Point::new(x1, y1), lw, color, &border_dash(b.style, k));
 }
 
+/// Merged areas active at one row of a downward sweep, kept disjoint: by first column, their last
+/// column and last row. Adding, dropping and looking up a merge costs log(active merges).
+#[derive(Default)]
+struct MergeSweep {
+    cols: std::collections::BTreeMap<u32, (u32, u32)>,
+    /// (last row, first column) of the active merges, soonest ending first.
+    ends: std::collections::BinaryHeap<std::cmp::Reverse<(u32, u32)>>,
+}
+
+impl MergeSweep {
+    /// Moves down to `row` (rows never decrease), dropping the merges that end above it.
+    fn advance(&mut self, row: u32) {
+        while let Some(std::cmp::Reverse((end, col))) = self.ends.peek().copied() {
+            if end >= row {
+                break;
+            }
+            self.ends.pop();
+            self.cols.remove(&col);
+        }
+    }
+
+    /// Does an active merge meet columns `c0..=c1`? The intervals are disjoint, so only the last
+    /// one starting at or before `c1` can.
+    fn meets(&self, c0: u32, c1: u32) -> bool {
+        self.cols.range(..=c1).next_back().is_some_and(|(_, (end, _))| *end >= c0)
+    }
+
+    /// Adds merge `m`, at row `row`, unless it overlaps an active one.
+    fn add(&mut self, m: RangeRef, row: u32) -> bool {
+        self.advance(row);
+        if self.meets(m.start.col, m.end.col) {
+            return false;
+        }
+        self.cols.insert(m.start.col, (m.end.col, m.end.row));
+        self.ends.push(std::cmp::Reverse((m.end.row, m.start.col)));
+        true
+    }
+}
+
+/// The merged areas that meet `block`, ordered by the row where they enter it, then by column,
+/// leaving out any that overlaps one kept before it (only a damaged file has overlapping merges;
+/// Excel drops them when it repairs one). One sweep down the rows instead of a scan of every
+/// merge per cell.
+fn block_merges(sh: &Sheet, block: RangeRef) -> Vec<RangeRef> {
+    let top = |m: &RangeRef| m.start.row.max(block.start.row);
+    let mut merges: Vec<RangeRef> = sh.merges.iter().filter(|m| m.intersects(&block)).copied().collect();
+    merges.sort_by_key(|m| (top(m), m.start.col));
+    let mut sweep = MergeSweep::default();
+    merges.retain(|m| sweep.add(*m, top(m)));
+    merges
+}
+
+/// Answers "is this cell inside a merge?" for cells asked in row-major order, from the merges of
+/// [`block_merges`].
+struct Covered<'a> {
+    merges: &'a [RangeRef],
+    top: u32,
+    next: usize,
+    sweep: MergeSweep,
+}
+
+impl<'a> Covered<'a> {
+    fn new(merges: &'a [RangeRef], block: RangeRef) -> Self {
+        Self { merges, top: block.start.row, next: 0, sweep: MergeSweep::default() }
+    }
+
+    fn covers(&mut self, c: CellRef) -> bool {
+        while let Some(m) = self.merges.get(self.next).filter(|m| m.start.row.max(self.top) <= c.row) {
+            self.sweep.add(*m, m.start.row.max(self.top));
+            self.next += 1;
+        }
+        self.sweep.advance(c.row);
+        self.sweep.meets(c.col, c.col)
+    }
+}
+
 /// Draws the cells of a block: fills, gridlines, data bars, borders and text.
 pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Option<crate::cf::CfCache>) {
     let (bx, by) = (b.xs.first().copied().unwrap_or(0.0), b.ys.first().copied().unwrap_or(0.0));
@@ -237,17 +313,18 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
     }
     let block = b.range();
     let sh = b.sh;
-    let merges: Vec<RangeRef> = sh.merges.iter().filter(|m| m.intersects(&block)).copied().collect();
-    let covered = |c: CellRef| merges.iter().any(|m| m.contains(c));
-    // Cells worth visiting.
+    let merges = block_merges(sh, block);
+    let by_start: std::collections::HashMap<CellRef, RangeRef> = merges.iter().map(|m| (m.start, *m)).collect();
+    // Cells worth visiting, in row-major order (which `Covered` needs).
+    let mut covered = Covered::new(&merges, block);
     let cells: Vec<CellRef> = if block.count() <= DENSE_BLOCK {
-        block.iter().filter(|c| !covered(*c)).collect()
+        block.iter().filter(|c| !covered.covers(*c)).collect()
     } else {
         let mut set: Vec<CellRef> = sh.cells.iter_range(block).map(|(c, _)| c).collect();
         set.extend(sh.spill.range(block.start..=block.end).map(|(c, _)| *c).filter(|c| block.contains(*c)));
         set.sort_unstable();
         set.dedup();
-        set.retain(|c| !covered(*c));
+        set.retain(|c| !covered.covers(*c));
         set
     };
     pg.save();
@@ -277,14 +354,14 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
         .filter(|(c, l)| {
             l.fill.is_some()
                 || l.cf.is_some()
-                || merges.iter().any(|m| m.start == *c)
+                || by_start.contains_key(c)
                 || !sh.value(*c).is_empty()
                 || l.style.borders != Borders::default()
                 || l.style.num_fmt.as_str() == "checkbox"
         })
         .collect();
     let rect_of = |c: CellRef| -> (f32, f32, f32, f32, bool) {
-        match merges.iter().find(|m| m.start == c) {
+        match by_start.get(&c) {
             Some(m) => {
                 let (x, y, w, h) = b.rect(*m);
                 (x, y, w, h, true)
@@ -322,7 +399,7 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
             continue;
         }
         let bd = &l.style.borders;
-        let (right, bottom) = match merges.iter().find(|m| m.start == *c).filter(|_| merged) {
+        let (right, bottom) = match by_start.get(c).filter(|_| merged) {
             Some(m) => (
                 b.wb.styles.get(sh.style_id(CellRef::new(m.start.row, m.end.col))).borders.right,
                 b.wb.styles.get(sh.style_id(CellRef::new(m.end.row, m.start.col))).borders.bottom,
@@ -407,11 +484,12 @@ pub(super) struct PrintedBlock {
 pub(super) fn draw_block_links(pg: &mut Page, b: &Block, page: usize, pending: &mut Vec<PendingPdfLink>) {
     let range = b.range();
     let (Some(&bx), Some(&by), Some(&right), Some(&bottom)) = (b.xs.first(), b.ys.first(), b.xs.last(), b.ys.last()) else { return };
+    let by_start: std::collections::HashMap<CellRef, RangeRef> = block_merges(b.sh, range).into_iter().map(|m| (m.start, m)).collect();
     for (cell, link) in b.sh.hyperlinks.range(range.start..=range.end) {
         if !range.contains(*cell) {
             continue;
         }
-        let cell_range = b.sh.merges.iter().find(|m| m.start == *cell).copied().unwrap_or(RangeRef::cell(*cell));
+        let cell_range = by_start.get(cell).copied().unwrap_or(RangeRef::cell(*cell));
         let (x, y, w, h) = b.rect(cell_range);
         let (x0, y0, x1, y1) = (x.max(bx), y.max(by), (x + w).min(right), (y + h).min(bottom));
         if x1 <= x0 || y1 <= y0 {
@@ -503,3 +581,44 @@ pub(super) fn make_block<'a>(
     }
     Block { wb, si, sh, rows, cols, xs, ys, k, scale: lay.scale }
 }
+
+#[cfg(test)]
+mod merge_tests {
+    use super::{CellRef, Covered, RangeRef, Sheet, block_merges};
+
+    fn r(a: &str) -> RangeRef {
+        RangeRef::parse(a).unwrap()
+    }
+
+    #[test]
+    fn block_merges_drop_overlaps_and_cover_like_a_scan() {
+        let mut sh = Sheet::new("S");
+        sh.merges = vec![r("B2:C3"), r("E1:F8"), r("B2:B5"), r("A10:D10"), r("H3:H4"), r("Z1:Z2"), r("C3:D4"), r("A1:A1048576")];
+        let block = r("B1:H12");
+        let merges = block_merges(&sh, block);
+        // B2:B5 and C3:D4 overlap B2:C3, which comes first; Z1:Z2 is outside the block.
+        assert_eq!(merges, vec![r("E1:F8"), r("B2:C3"), r("H3:H4"), r("A10:D10")]);
+        let mut covered = Covered::new(&merges, block);
+        for c in block.iter() {
+            assert_eq!(covered.covers(c), merges.iter().any(|m| m.contains(c)), "{}", c.a1());
+        }
+        // Cells asked sparsely, still in order.
+        let mut covered = Covered::new(&merges, block);
+        for (a, want) in [("C1", false), ("F5", true), ("G5", false), ("D10", true), ("H12", false)] {
+            assert_eq!(covered.covers(CellRef::parse(a).unwrap()), want, "{a}");
+        }
+    }
+
+    #[test]
+    fn many_stacked_merges_are_swept_once() {
+        // 50,000 merges over the same cells: one is kept, and the block is checked against it
+        // without comparing every cell with every merge.
+        let mut sh = Sheet::new("S");
+        sh.merges = (0..50_000u32).map(|i| RangeRef::new(CellRef::new(0, 0), CellRef::new(199, 1 + i % 50))).collect();
+        let block = r("A1:AZ200");
+        let merges = block_merges(&sh, block);
+        assert_eq!(merges, vec![r("A1:B200")]);
+        let mut covered = Covered::new(&merges, block);
+        assert_eq!(block.iter().filter(|c| covered.covers(*c)).count(), 400);
+    }
+}

crates/engine/src/io.rs

@@ -755,10 +755,10 @@ thread_local! {
 /// While one is alive, [`read_file`] and [`write_file`] on this thread refuse every path: a
 /// stored script's steps run inside one (#2178), so no command reaches the file system from a
 /// script whatever its parameters are called. Dropping it (also on unwind) lifts the refusal.
-pub struct ScriptSandbox(());
+pub(crate) struct ScriptSandbox(());
 
 impl ScriptSandbox {
-    pub fn enter() -> Self {
+    pub(crate) fn enter() -> Self {
         let _ = SCRIPT_SANDBOX.try_with(|c| c.set(c.get().saturating_add(1)));
         ScriptSandbox(())
     }

crates/engine/src/tests.rs

@@ -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 {

crates/ui-egui/src/grid/editor.rs

@@ -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);

crates/ui-egui/src/ribbon/home.rs

@@ -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;

crates/ui-egui/tests/it/font_size_box.rs

@@ -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:?}");
-}

crates/ui-egui/tests/it/ribbon_layout.rs

@@ -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();

crates/xlsx/src/sheet_write/rules.rs

@@ -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)));

crates/xlsx/src/tests/roundtrip.rs

@@ -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}");
-}

xtask/src/keytips.rs

@@ -77,8 +77,6 @@ fn probe_live_commands(calls: &[(String, String)]) -> Probe {
         let params = if params.is_empty() { serde_json::json!({}) } else { serde_json::from_str(params).unwrap_or_default() };
         let mut s = Session::new();
         s.new_workbook();
-        // The JSON picks the commands and their params: none of them may touch the file system.
-        let _sandbox = gridcraft_engine::io::ScriptSandbox::enter();
         let status = match s.execute(id, params.clone()) {
             Ok(_) => {
                 if s.journal.iter().any(|(jid, _)| jid == id) {
@@ -183,16 +181,15 @@ fn parse_and_probe(source: &str) -> Result<(Vec<Entry>, Probe), String> {
                 }
             }
         }
-        let excel = e.get("excel").and_then(|v| v.as_str()).unwrap_or("").to_string();
-        let note = e.get("note").and_then(|v| v.as_str()).unwrap_or("").to_string();
-        // These are written into generated Rust: a target inside string literals and format
-        // strings, the annotations after `//`. Refuse anything that could end either.
-        for (field, text) in [("target", &target), ("excel", &excel), ("note", &note)] {
-            if text.chars().any(|c| c.is_control() || matches!(c, '"' | '\\' | '{' | '}')) {
-                return Err(format!("{at}: `{field}` must not hold quotes, backslashes, braces or control characters: {text:?}"));
-            }
-        }
-        entries.push(Entry { seq, kind, target, pending, params, excel, note });
+        entries.push(Entry {
+            seq,
+            kind,
+            target,
+            pending,
+            params,
+            excel: e.get("excel").and_then(|v| v.as_str()).unwrap_or("").to_string(),
+            note: e.get("note").and_then(|v| v.as_str()).unwrap_or("").to_string(),
+        });
     }
     // JSON order is authoritative and curated: the first entry for a tab is its canonical
     // badge (legacy aliases come later), and groups stay together. Do not sort.
@@ -437,34 +434,3 @@ fn reset(h: &mut Harness) {
     key(h, Key::Escape); // leave keytip mode entirely
 }
 "#;
-
-#[cfg(all(test, feature = "engine"))]
-mod tests {
-    use super::*;
-
-    /// Text that would end a comment or string literal in the generated Rust is refused.
-    #[test]
-    fn annotations_and_targets_cannot_escape_generated_code() {
-        for entry in [
-            r#"{"seq": "Q", "kind": "command", "target": "edit.copy", "note": "x\nfn evil() {}"}"#,
-            r#"{"seq": "Q", "kind": "command", "target": "edit.copy", "excel": "a\rb"}"#,
-            r#"{"seq": "Q", "kind": "dialog", "target": "x\"); evil(); (\""}"#,
-            r#"{"seq": "Q", "kind": "control", "target": "{0}"}"#,
-        ] {
-            let doc = format!(r#"{{"sequences": [{entry}]}}"#);
-            assert!(parse_and_probe(&doc).is_err(), "{entry}");
-        }
-        assert!(parse_and_probe(r#"{"sequences": [{"seq": "Q", "kind": "control", "target": "fontSize", "note": "Font Size box"}]}"#).is_ok());
-    }
-
-    /// A probed command may not write files, whatever its params say.
-    #[test]
-    fn probes_cannot_touch_the_file_system() {
-        let path = std::env::temp_dir().join(format!("keytips-probe-{}.pdf", std::process::id()));
-        let _ = fs::remove_file(&path);
-        let calls = vec![("file.exportPdf".to_string(), serde_json::json!({ "path": path.to_string_lossy() }).to_string())];
-        let probe = probe_live_commands(&calls);
-        assert_eq!(probe.values().copied().collect::<Vec<_>>(), [2]);
-        assert!(!path.exists());
-    }
-}