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/raster.rs

@@ -7,12 +7,6 @@ use crate::{Prim, Rgba};
 /// Largest image we allocate (pixels).
 const MAX_PIXELS: u64 = 64 * 1024 * 1024;
 const SUB: usize = 4;
-/// Scan-conversion work one [`rasterize`] call may do: edge tests (an active edge at one
-/// sub-sample) plus covered pixels blended. Edges are only tested on the rows they cross, but a
-/// caller can still pass enough geometry to keep the rasteriser busy for minutes on a small
-/// image; once the allowance is spent the remaining fills are skipped. 2^28 is about a second,
-/// far beyond any chart.
-const MAX_SCAN_WORK: u64 = 1 << 28;
 
 type Path = Vec<Vec<[f32; 2]>>;
 
@@ -21,8 +15,6 @@ struct Canvas {
     h: usize,
     buf: Vec<u8>,
     acc: Vec<f32>,
-    /// Scan-conversion work left (see [`MAX_SCAN_WORK`]).
-    work: u64,
 }
 
 impl Canvas {
@@ -49,8 +41,7 @@ impl Canvas {
 
     /// Fills a multi-contour path with the even-odd rule.
     fn fill(&mut self, path: &Path, color: Rgba) {
-        // Each edge as [top y, bottom y, x0, y0, x1, y1].
-        let mut edges: Vec<[f32; 6]> = Vec::new();
+        let mut edges: Vec<[f32; 4]> = Vec::new();
         let (mut minx, mut miny, mut maxx, mut maxy) = (f32::INFINITY, f32::INFINITY, f32::NEG_INFINITY, f32::NEG_INFINITY);
         for c in path {
             if c.len() < 3 || !c.iter().all(|p| p[0].is_finite() && p[1].is_finite()) {
@@ -63,7 +54,7 @@ impl Canvas {
                 miny = miny.min(p[1]);
                 maxy = maxy.max(p[1]);
                 if p[1] != q[1] {
-                    edges.push([p[1].min(q[1]), p[1].max(q[1]), p[0], p[1], q[0], q[1]]);
+                    edges.push([p[0], p[1], q[0], q[1]]);
                 }
             }
         }
@@ -81,26 +72,8 @@ impl Canvas {
         if self.acc.len() < bw + 1 {
             self.acc.resize(bw + 1, 0.0);
         }
-        // Active-edge list: edges join when the scan reaches their top and leave past their
-        // bottom, so each row tests only the edges crossing it instead of every edge.
-        edges.sort_by(|a, b| a[0].total_cmp(&b[0]));
-        let mut pending = edges.iter().peekable();
-        let mut active: Vec<[f32; 6]> = Vec::new();
         let mut xs: Vec<f32> = Vec::new();
         for py in y0..y1 {
-            while let Some(e) = pending.next_if(|e| e[0] < py as f32 + 1.0) {
-                active.push(*e);
-            }
-            active.retain(|e| e[1] > py as f32);
-            if active.is_empty() {
-                continue;
-            }
-            let tests = (active.len() * SUB) as u64;
-            if tests > self.work {
-                self.work = 0;
-                return;
-            }
-            self.work -= tests;
             for v in self.acc.iter_mut().take(bw) {
                 *v = 0.0;
             }
@@ -108,9 +81,10 @@ impl Canvas {
             for s in 0..SUB {
                 let sy = py as f32 + (s as f32 + 0.5) / SUB as f32;
                 xs.clear();
-                for e in &active {
-                    if sy >= e[0] && sy < e[1] {
-                        xs.push(e[2] + (sy - e[3]) * (e[4] - e[2]) / (e[5] - e[3]));
+                for e in &edges {
+                    let (ya, yb) = if e[1] < e[3] { (e[1], e[3]) } else { (e[3], e[1]) };
+                    if sy >= ya && sy < yb {
+                        xs.push(e[0] + (sy - e[1]) * (e[2] - e[0]) / (e[3] - e[1]));
                     }
                 }
                 xs.sort_by(f32::total_cmp);
@@ -136,7 +110,6 @@ impl Canvas {
             if !any {
                 continue;
             }
-            self.work = self.work.saturating_sub(bw as u64);
             for px in x0..x1 {
                 let cov = self.acc.get(px - x0).copied().unwrap_or(0.0);
                 if cov > 0.0 {
@@ -239,7 +212,7 @@ pub fn rasterize(prims: &[Prim], w: u32, h: u32, background: Rgba) -> Vec<u8> {
     for _ in 0..w * h {
         buf.extend_from_slice(&background);
     }
-    let mut cv = Canvas { w, h, buf, acc: Vec::new(), work: MAX_SCAN_WORK };
+    let mut cv = Canvas { w, h, buf, acc: Vec::new() };
     for p in prims {
         match p {
             Prim::Rect { x, y, w, h, fill, stroke, radius } => {
@@ -301,31 +274,6 @@ pub fn rasterize(prims: &[Prim], w: u32, h: u32, background: Rgba) -> Vec<u8> {
 mod tests {
     use super::*;
 
-    /// Security: each row tests only the edges crossing it. A polygon of 100,000 tiny edges over
-    /// 4,000 rows tested every edge at every sub-sample of every row (1.6 billion tests).
-    #[test]
-    fn many_short_edges_scan_only_their_rows() {
-        let mut pts: Vec<[f32; 2]> = (0..100_000).map(|i| [if i % 2 == 0 { 0.0 } else { 0.5 }, i as f32 * 0.04]).collect();
-        pts.push([2.0, 4_000.0]);
-        pts.push([2.0, 0.0]);
-        let img = rasterize(&[Prim::Polygon { pts, fill: [255, 0, 0, 255], stroke: None }], 2, 4_000, [0, 0, 0, 0]);
-        // The right-hand pixel of every row is inside the polygon.
-        assert_eq!(img.get(4..8), Some(&[255, 0, 0, 255][..]));
-        assert_eq!(img.get(4 * (2 * 3_999 + 1)..4 * (2 * 3_999 + 2)), Some(&[255, 0, 0, 255][..]));
-    }
-
-    /// Security: scan conversion stops once the call's work allowance is spent.
-    #[test]
-    fn fills_stop_when_the_work_allowance_is_spent() {
-        let square = vec![vec![[0.0, 0.0], [4.0, 0.0], [4.0, 4.0], [0.0, 4.0]]];
-        let mut cv = Canvas { w: 4, h: 4, buf: vec![0; 64], acc: Vec::new(), work: 2 * SUB as u64 * 4 + 16 };
-        cv.fill(&square, [255; 4]);
-        assert!(cv.buf.iter().all(|&b| b == 255));
-        cv.buf = vec![0; 64];
-        cv.fill(&square, [255; 4]);
-        assert!(cv.buf.iter().all(|&b| b == 0));
-    }
-
     #[test]
     fn dashed_geometry_stays_within_the_dash_budget() {
         // Forty very long dashed lines, each allowed 10_000 dashes per segment: before the

crates/chart/src/render/lines.rs

@@ -56,13 +56,7 @@ pub(super) fn decimate(pts: Vec<[f32; 2]>, max: usize) -> Vec<[f32; 2]> {
 
 /// 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.
-///
-/// The points interpolation adds are budgeted across all the runs of the line, not per run:
-/// short runs between gaps escape decimation, and 100 sub-segments each would turn a
-/// 100,000-point series of three-point runs into millions of points. Past the budget the
-/// remaining runs are drawn through their data points only.
 pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, width: f32, smooth: Option<Bx>) {
-    let mut budget = MAX_LINE_PTS * 2;
     let mut run: Vec<[f32; 2]> = Vec::new();
     for p in pts.iter().chain(std::iter::once(&None)) {
         match p {
@@ -71,11 +65,7 @@ pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, wi
                 if run.len() >= 2 {
                     let r = decimate(std::mem::take(&mut run), MAX_LINE_PTS);
                     let r = match smooth {
-                        Some(plot) => {
-                            let r = smooth_run(r, plot, budget);
-                            budget = budget.saturating_sub(r.len());
-                            r
-                        }
+                        Some(plot) => smooth_run(r, plot),
                         None => r,
                     };
                     ctx.line(r, color, width);
@@ -88,15 +78,15 @@ pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, wi
 }
 
 /// Catmull-Rom spline through `pts`: every segment gets the same number of sub-segments (up to
-/// 100), chosen so the whole curve stays within `cap` points (one per data point when `cap` is
-/// smaller than that). Endpoints are
+/// 100), chosen so the whole curve stays within `MAX_LINE_PTS * 2` points. Endpoints are
 /// duplicated so the curve passes through the first and last points, and the curve is clamped
 /// to the `plot` box (a spline overshoots its data near sharp turns).
-fn smooth_run(pts: Vec<[f32; 2]>, plot: Bx, cap: usize) -> Vec<[f32; 2]> {
+fn smooth_run(pts: Vec<[f32; 2]>, plot: Bx) -> Vec<[f32; 2]> {
     let n = pts.len();
     if n < 3 {
         return pts;
     }
+    let cap = MAX_LINE_PTS * 2;
     let steps = (cap / n).clamp(1, 100);
     let mut out: Vec<[f32; 2]> = Vec::with_capacity(n.saturating_mul(steps).min(cap) + 1);
     let at = |i: isize| -> [f32; 2] {
@@ -149,7 +139,7 @@ mod smooth_tests {
     fn long_runs_are_smoothed_uniformly_within_the_cap() {
         let plot = Bx { x: 0.0, y: 0.0, w: 3000.0, h: 100.0 };
         let pts: Vec<[f32; 2]> = (0..1500).map(|i| [i as f32 * 2.0, if i % 2 == 0 { 20.0 } else { 80.0 }]).collect();
-        let out = smooth_run(pts, plot, MAX_LINE_PTS * 2);
+        let out = smooth_run(pts, plot);
         assert!(out.len() <= MAX_LINE_PTS * 2 + 1, "{}", out.len());
         // Two sub-segments per segment all the way to the end, not 100 each and then a straight tail.
         assert_eq!(out.len(), 1499 * 2 + 1);
@@ -161,26 +151,8 @@ mod smooth_tests {
         let plot = Bx { x: 0.0, y: 10.0, w: 300.0, h: 100.0 };
         // A step right at the plot edges: Catmull-Rom overshoots past both.
         let pts = vec![[0.0, 110.0], [100.0, 110.0], [110.0, 10.0], [200.0, 10.0], [300.0, 10.0]];
-        let out = smooth_run(pts, plot, MAX_LINE_PTS * 2);
+        let out = smooth_run(pts, plot);
         assert!(out.len() > 5);
         assert!(out.iter().all(|p| (0.0..=300.0).contains(&p[0]) && (10.0..=110.0).contains(&p[1])));
     }
-
-    /// Security: smoothing budgets its added points across every run of a line. A series of
-    /// three-point runs between gaps used to get 100 sub-segments per run, 67 times its data.
-    #[test]
-    fn gap_separated_runs_share_one_smoothing_budget() {
-        let plot = Bx { x: 0.0, y: 0.0, w: 1e6, h: 100.0 };
-        let pts: Vec<Option<[f32; 2]>> =
-            (0..100_000).map(|i| if i % 4 == 3 { None } else { Some([i as f32, if i % 2 == 0 { 20.0 } else { 80.0 }]) }).collect();
-        let m = crate::ApproxMeasure;
-        let mut ctx = Ctx { out: Vec::new(), m: &m };
-        draw_runs(&mut ctx, &pts, WHITE, 1.0, Some(plot));
-        let total: usize = ctx.out.iter().map(|p| if let Prim::Line { pts, .. } = p { pts.len() } else { 0 }).sum();
-        // 75,000 data points, plus at most the budget added by interpolation.
-        assert!(total <= 75_000 + MAX_LINE_PTS * 2, "{total}");
-        assert_eq!(ctx.out.len(), 25_000);
-        // The first runs are still smoothed.
-        assert!(matches!(ctx.out.first(), Some(Prim::Line { pts, .. }) if pts.len() > 3));
-    }
 }

crates/chart/src/resolve.rs

@@ -133,46 +133,6 @@ fn value_text(v: &Value) -> String {
     }
 }
 
-/// Characters kept of one category label: an axis label never shows more (labels are fitted to
-/// the axis), and copying more only costs memory.
-const MAX_LABEL_CHARS: usize = 255;
-/// Bytes of category label text kept per series. One long text broadcast by a short formula
-/// (`IF(SEQUENCE(100000), long_text)`) is a single shared value, but turning every element into
-/// its own label copied it 100,000 times (gigabytes). Labels past the budget are empty.
-const MAX_CATEGORY_BYTES: usize = 8 << 20;
-
-/// At most [`MAX_LABEL_CHARS`] characters and `room` bytes of `s`, cut at a character boundary.
-fn clip_label(s: &str, room: usize) -> String {
-    let mut end = 0;
-    for (n, (i, c)) in s.char_indices().enumerate() {
-        if n >= MAX_LABEL_CHARS || i + c.len_utf8() > room {
-            break;
-        }
-        end = i + c.len_utf8();
-    }
-    s.get(..end).unwrap_or_default().to_string()
-}
-
-/// The label of category `i` (value `v`) in at most `room` bytes: formatted with its source
-/// cell's number format when it is a number.
-fn category_label(wb: &Workbook, src: Option<(&gridcraft_model::Sheet, RangeRef)>, i: usize, v: &Value, room: usize) -> String {
-    if let (Some((s, r)), Value::Number(_)) = (src, v) {
-        let w = r.width().max(1) as usize;
-        let at = r.start.offset((i / w) as i64, (i % w) as i64);
-        if let Some(c) = at {
-            let code = &wb.styles.get(s.style_id(c)).num_fmt.0;
-            if !code.eq_ignore_ascii_case("general") {
-                return clip_label(&format_value(v, &NumberFormat::parse_cached(code), wb.date_system).text, room);
-            }
-        }
-    }
-    // Text is clipped before it is copied: the source may be one long shared string.
-    match v {
-        Value::Text(t) => clip_label(t, room),
-        _ => clip_label(&value_text(v), room),
-    }
-}
-
 /// Category labels, formatted with each source cell's number format (dates, currency…), and
 /// the outer levels of a multi-level axis: a category range wider than a column of values (or
 /// taller than a row of values) groups its innermost labels, year beside month. Each outer level
@@ -181,14 +141,21 @@ fn category_table(wb: &Workbook, sheet: usize, formula: &str, values: &str) -> (
     let vals = eval_list(wb, sheet, formula);
     let cells: Option<(usize, RangeRef)> = parse_ref(wb, sheet, formula);
     let src = cells.and_then(|(sh, r)| wb.sheet(sh).map(|s| (s, r)));
-    let mut room = MAX_CATEGORY_BYTES;
     let texts: Vec<String> = vals
         .iter()
         .enumerate()
         .map(|(i, v)| {
-            let label = category_label(wb, src, i, v, room);
-            room = room.saturating_sub(label.len());
-            label
+            if let (Some((s, r)), Value::Number(_)) = (src, v) {
+                let w = r.width().max(1) as usize;
+                let at = r.start.offset((i / w) as i64, (i % w) as i64);
+                if let Some(c) = at {
+                    let code = &wb.styles.get(s.style_id(c)).num_fmt.0;
+                    if !code.eq_ignore_ascii_case("general") {
+                        return format_value(v, &NumberFormat::parse_cached(code), wb.date_system).text;
+                    }
+                }
+            }
+            value_text(v)
         })
         .collect();
     let Some((_, r)) = src else { return (texts, vec![]) };
@@ -309,23 +276,3 @@ pub fn resolve(wb: &Workbook, sheet: usize, chart: &Chart) -> ChartData {
     let palette = default_palette(&wb.theme, n.min(PALETTE_CYCLE));
     ChartData { categories, category_levels, series, palette }
 }
-
-#[cfg(test)]
-mod label_budget_tests {
-    use gridcraft_model::Workbook;
-
-    /// Security: category labels are clipped before they are copied, with one byte budget per
-    /// series. A formula broadcasting one long text to 100,000 categories used to copy it
-    /// 100,000 times (3.3 GB).
-    #[test]
-    fn category_labels_share_one_byte_budget() {
-        let wb = Workbook::new();
-        let (texts, _) = super::category_table(&wb, 0, r#"=IF(SEQUENCE(100000),REPT("x",32767))"#, "");
-        assert_eq!(texts.len(), 100_000);
-        assert_eq!(texts.first().map(String::len), Some(super::MAX_LABEL_CHARS));
-        assert!(texts.iter().map(String::len).sum::<usize>() <= super::MAX_CATEGORY_BYTES);
-        // Labels are cut at character boundaries.
-        assert_eq!(super::clip_label("aé", 2), "a");
-        assert_eq!(super::clip_label("aé", 3), "aé");
-    }
-}

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