chart: bound scan conversion, spline points and category label bytes

- The rasteriser tested every edge of a path at every sub-sample of every
  covered row. It now keeps an active-edge list (edges sorted by top, joining
  and leaving as the scan passes them), and one rasterize call has a total
  scan-work allowance after which remaining fills are skipped.
- Smoothed lines budgeted interpolated points per run, so gap-separated short
  runs escaped both decimation and the cap. The budget is now shared by all
  runs of a line; once spent, runs are drawn through their data points.
- Category labels copied every text value in full. Labels are clipped to 255
  characters before copying, within an 8 MiB budget per series.

crates/chart/src/raster.rs

@@ -7,6 +7,12 @@ 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]>>;
 
@@ -15,6 +21,8 @@ struct Canvas {
     h: usize,
     buf: Vec<u8>,
     acc: Vec<f32>,
+    /// Scan-conversion work left (see [`MAX_SCAN_WORK`]).
+    work: u64,
 }
 
 impl Canvas {
@@ -41,7 +49,8 @@ impl Canvas {
 
     /// Fills a multi-contour path with the even-odd rule.
     fn fill(&mut self, path: &Path, color: Rgba) {
-        let mut edges: Vec<[f32; 4]> = Vec::new();
+        // Each edge as [top y, bottom y, x0, y0, x1, y1].
+        let mut edges: Vec<[f32; 6]> = 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()) {
@@ -54,7 +63,7 @@ impl Canvas {
                 miny = miny.min(p[1]);
                 maxy = maxy.max(p[1]);
                 if p[1] != q[1] {
-                    edges.push([p[0], p[1], q[0], q[1]]);
+                    edges.push([p[1].min(q[1]), p[1].max(q[1]), p[0], p[1], q[0], q[1]]);
                 }
             }
         }
@@ -72,8 +81,26 @@ 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;
             }
@@ -81,10 +108,9 @@ 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 &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]));
+                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]));
                     }
                 }
                 xs.sort_by(f32::total_cmp);
@@ -110,6 +136,7 @@ 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 {
@@ -212,7 +239,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() };
+    let mut cv = Canvas { w, h, buf, acc: Vec::new(), work: MAX_SCAN_WORK };
     for p in prims {
         match p {
             Prim::Rect { x, y, w, h, fill, stroke, radius } => {
@@ -274,6 +301,31 @@ 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,7 +56,13 @@ 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 {
@@ -65,7 +71,11 @@ 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) => smooth_run(r, plot),
+                        Some(plot) => {
+                            let r = smooth_run(r, plot, budget);
+                            budget = budget.saturating_sub(r.len());
+                            r
+                        }
                         None => r,
                     };
                     ctx.line(r, color, width);
@@ -78,15 +88,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 `MAX_LINE_PTS * 2` points. Endpoints are
+/// 100), chosen so the whole curve stays within `cap` points (one per data point when `cap` is
+/// smaller than that). 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) -> Vec<[f32; 2]> {
+fn smooth_run(pts: Vec<[f32; 2]>, plot: Bx, cap: usize) -> 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] {
@@ -139,7 +149,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);
+        let out = smooth_run(pts, plot, MAX_LINE_PTS * 2);
         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);
@@ -151,8 +161,26 @@ 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);
+        let out = smooth_run(pts, plot, MAX_LINE_PTS * 2);
         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,6 +133,46 @@ 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
@@ -141,21 +181,14 @@ 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)| {
-            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)
+            let label = category_label(wb, src, i, v, room);
+            room = room.saturating_sub(label.len());
+            label
         })
         .collect();
     let Some((_, r)) = src else { return (texts, vec![]) };
@@ -276,3 +309,23 @@ 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,82 +228,6 @@ 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));
@@ -313,18 +237,17 @@ 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 = 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 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 cells: Vec<CellRef> = if block.count() <= DENSE_BLOCK {
-        block.iter().filter(|c| !covered.covers(*c)).collect()
+        block.iter().filter(|c| !covered(*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.covers(*c));
+        set.retain(|c| !covered(*c));
         set
     };
     pg.save();
@@ -354,14 +277,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()
-                || by_start.contains_key(c)
+                || merges.iter().any(|m| m.start == *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 by_start.get(&c) {
+        match merges.iter().find(|m| m.start == c) {
             Some(m) => {
                 let (x, y, w, h) = b.rect(*m);
                 (x, y, w, h, true)
@@ -399,7 +322,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 by_start.get(c).filter(|_| merged) {
+        let (right, bottom) = match merges.iter().find(|m| m.start == *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,
@@ -484,12 +407,11 @@ 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 = by_start.get(cell).copied().unwrap_or(RangeRef::cell(*cell));
+        let cell_range = b.sh.merges.iter().find(|m| m.start == *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 {
@@ -581,44 +503,3 @@ 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);
-    }
-}