PDF export: wrap text with running widths

wrap_lines split an over-long word by re-measuring and copying the
rest of the word for every piece it cut, and only checked its line
limit once the word was done, so one long word in a narrow text box
cost word length x pieces. Each new word also re-measured the whole
line built so far.

Line and piece widths are now running sums of glyph widths (the same
sum text_width makes), so every character is measured once, and the
line limit is checked while a word is being split. The lines produced
are unchanged; a test compares them with the old wrapper.

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

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

@@ -695,6 +695,79 @@ 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,42 +3,57 @@ 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 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;
+            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;
             } else {
                 out.push(std::mem::take(&mut line));
-                line = word.to_string();
+                line.push_str(word);
+                line_units = word_units;
             }
-            // 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;
+            // 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;
+                        }
                     }
+                    piece.push(c);
+                    units += w;
                 }
-                if lo == chars.len() {
-                    break;
-                }
-                out.push(chars[..lo].iter().collect());
-                line = chars[lo..].iter().collect();
+                line = piece;
+                line_units = units;
             }
-            if out.len() > 2000 {
+            if out.len() > MAX_WRAP_LINES {
                 return out;
             }
         }