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/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/cmd/print/tests.rs

@@ -695,79 +695,6 @@ fn bands_unit() {
     assert!(w.len() > 2);
 }
 
-/// The wrapper `wrap_lines` replaced, re-measuring strings, as the reference for its lines.
-fn wrap_lines_remeasuring(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
-    let mut out = Vec::new();
-    for para in text.split('\n') {
-        let mut line = String::new();
-        for word in para.split(' ') {
-            let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
-            if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
-                line = cand;
-            } else {
-                out.push(std::mem::take(&mut line));
-                line = word.to_string();
-            }
-            while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
-                let chars: Vec<char> = line.chars().collect();
-                let (mut lo, mut hi) = (1usize, chars.len());
-                while lo < hi {
-                    let mid = lo + (hi - lo).div_ceil(2);
-                    let cut: String = chars[..mid].iter().collect();
-                    if gridcraft_pdf::text_width(font, size, &cut) <= width {
-                        lo = mid;
-                    } else {
-                        hi = mid - 1;
-                    }
-                }
-                if lo == chars.len() {
-                    break;
-                }
-                out.push(chars[..lo].iter().collect());
-                line = chars[lo..].iter().collect();
-            }
-            if out.len() > 2000 {
-                return out;
-            }
-        }
-        out.push(line);
-    }
-    out
-}
-
-#[test]
-fn wrap_lines_matches_the_remeasuring_wrapper() {
-    let texts = [
-        "the quick brown fox jumps",
-        "Supercalifragilistic",
-        "a  b   c\n\nverylongwordthatneedsbreaking short\nend ",
-        "Wide WWWWWWWWWW words, iiiiiiii narrow ones; mixed MMMMiiiiMMMM",
-        "€ ü ß — unicode Ünïcödé text",
-        "",
-        " ",
-    ];
-    for text in texts {
-        for font in [Font::Helvetica, Font::HelveticaBold, Font::Courier] {
-            for (size, width) in [(10.0, 50.0), (10.0, 20.0), (11.0, 1.0), (8.0, 300.0), (12.0, 0.0)] {
-                assert_eq!(wrap_lines(text, font, size, width), wrap_lines_remeasuring(text, font, size, width), "{text:?} {font:?} {size} {width}");
-            }
-        }
-    }
-}
-
-#[test]
-fn wrapping_a_long_word_in_a_narrow_box_stops_at_the_line_limit() {
-    // One character per line: the old wrapper re-measured and copied the rest of the word for
-    // each of the 100,000 lines before checking the limit.
-    let word = "w".repeat(100_000);
-    let lines = wrap_lines(&word, Font::Helvetica, 10.0, 1.0);
-    assert!(lines.len() <= 2002, "{}", lines.len());
-    assert!(lines.iter().all(|l| l == "w"));
-    // A long paragraph in a very wide box is one line.
-    let para = vec!["word"; 50_000].join(" ");
-    assert_eq!(wrap_lines(&para, Font::Helvetica, 10.0, 1.0e9), vec![para.clone()]);
-}
-
 #[test]
 fn center_across_spans_following_empty_center_across_cells() {
     let mut styles = StyleTable::default();

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

@@ -3,57 +3,42 @@ use super::{CellRef, Color, Font, HAlign, MAX_COLS, Page, Point, RangeRef, Sheet
 
 const PAD_PX: f32 = 2.0;
 
-/// Most lines [`wrap_lines`] returns (it may return one more, the rest of a paragraph).
-const MAX_WRAP_LINES: usize = 2000;
-
 /// Word-wraps `text` to `width` points.
-///
-/// Widths are kept as running sums of glyph widths (the sum `text_width` makes), so each
-/// character is measured once: re-measuring the line for every word, or the rest of an
-/// over-long word for every piece cut from it, made a long paragraph or word quadratic.
 pub(super) fn wrap_lines(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
-    let units_of = |s: &str| -> u64 { s.chars().map(|c| u64::from(font.char_width(c))).sum() };
-    let fits = |units: u64| units as f32 * size / 1000.0 <= width;
-    let space = units_of(" ");
     let mut out = Vec::new();
     for para in text.split('\n') {
         let mut line = String::new();
-        let mut line_units: u64 = 0;
         for word in para.split(' ') {
-            let word_units = units_of(word);
-            if line.is_empty() {
-                line.push_str(word);
-                line_units = word_units;
-            } else if fits(line_units + space + word_units) {
-                line.push(' ');
-                line.push_str(word);
-                line_units += space + word_units;
+            let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
+            if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
+                line = cand;
             } else {
                 out.push(std::mem::take(&mut line));
-                line.push_str(word);
-                line_units = word_units;
+                line = word.to_string();
             }
-            // Break a single over-long word by characters: each piece is the longest that fits
-            // (at least one character).
-            if !fits(line_units) && line.chars().nth(1).is_some() {
-                let mut piece = String::new();
-                let mut units: u64 = 0;
-                for c in line.chars() {
-                    let w = u64::from(font.char_width(c));
-                    if !piece.is_empty() && !fits(units + w) {
-                        out.push(std::mem::take(&mut piece));
-                        units = 0;
-                        if out.len() > MAX_WRAP_LINES {
-                            return out;
-                        }
+            // Break a single over-long word by characters. The cut that fits is found by binary
+            // search (each try measures one candidate prefix), so an over-long word costs
+            // O(n log n) measurements instead of re-measuring the whole cut per character for
+            // every emitted line (`a` × 100k pasted text would be cubic worst case).
+            while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
+                let chars: Vec<char> = line.chars().collect();
+                let (mut lo, mut hi) = (1usize, chars.len());
+                while lo < hi {
+                    let mid = lo + (hi - lo).div_ceil(2);
+                    let cut: String = chars[..mid].iter().collect();
+                    if gridcraft_pdf::text_width(font, size, &cut) <= width {
+                        lo = mid;
+                    } else {
+                        hi = mid - 1;
                     }
-                    piece.push(c);
-                    units += w;
                 }
-                line = piece;
-                line_units = units;
+                if lo == chars.len() {
+                    break;
+                }
+                out.push(chars[..lo].iter().collect());
+                line = chars[lo..].iter().collect();
             }
-            if out.len() > MAX_WRAP_LINES {
+            if out.len() > 2000 {
                 return out;
             }
         }