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/edit/go_to.rs

@@ -17,13 +17,11 @@ pub(in super::super) fn go_to(s: &mut Session, p: &Json) -> Result<Json> {
     }
     let Some(reference) = str_param(p, "reference").or_else(|| str_param(p, "range")) else { return Err(bad("edit.goTo", "missing `reference`")) };
     let d = s.doc()?;
-    let mut names = Resolver::new(&d.wb);
     let mut target: Option<usize> = None;
     let mut areas: Vec<RangeRef> = Vec::new();
     let mut named = false;
     for part in reference_parts(reference) {
-        let mut found = Vec::new();
-        let Some((sheet, _, by_name)) = names.target(d.wb.active_sheet(), part, 0, Some(&mut found)) else {
+        let Some((sheet, found, by_name)) = go_to_target(&d.wb, d.wb.active_sheet(), part, 0) else {
             return Err(EngineError::Other("Reference isn't valid.".into()));
         };
         // One selection holds the areas of one sheet.
@@ -79,114 +77,57 @@ pub(super) fn reference_parts(text: &str) -> impl Iterator<Item = &str> {
     })
 }
 
-/// Resolves Go To references against one workbook. Defined names are found through an index
-/// built once, and whether a name refers to a reference is remembered: listing the names of a
-/// workbook full of names that alias other names would otherwise scan every name for every alias
-/// of every name.
-struct Resolver<'a> {
-    wb: &'a gridcraft_model::Workbook,
-    /// Indexes into `wb.names` by scope and folded name, in workbook order.
-    by_name: std::collections::HashMap<(Option<usize>, String), Vec<usize>>,
-    /// [`Resolver::name_areas`] without areas, by name index, sheet and depth: the target sheet
-    /// and the number of areas.
-    memo: std::collections::HashMap<(usize, usize, usize), Option<(usize, usize)>>,
+/// Where one part of a Go To reference points, seen from sheet `sheet`: the sheet, its areas,
+/// and whether a defined name or a table gave them. `Sheet2!Name` is the name scoped to Sheet2.
+/// A name counts when what it refers to is a reference; a constant or a formula is not one.
+fn go_to_target(wb: &gridcraft_model::Workbook, sheet: usize, part: &str, depth: usize) -> Option<(usize, Vec<RangeRef>, bool)> {
+    if part.is_empty() || depth > GO_TO_NAME_DEPTH {
+        return None;
+    }
+    let (prefix, body) = split_sheet(part);
+    let on = match &prefix {
+        Some(n) => wb.sheet_index(n)?,
+        None => sheet,
+    };
+    if let Some(r) = RangeRef::parse(&body.replace('$', "")) {
+        return Some((on, vec![r], false));
+    }
+    let name = match prefix {
+        Some(_) => wb.names.iter().find(|n| n.scope == Some(on) && gridcraft_formula::same_name(&n.name, body)),
+        None => wb.name(body, sheet),
+    };
+    if let Some(n) = name {
+        return name_areas(wb, n, sheet, depth).map(|(t, areas)| (t, areas, true));
+    }
+    if prefix.is_none()
+        && let Some((si, ti)) = wb.table(body)
+    {
+        // As in Excel, a table's name stands for its data, without the header and totals rows.
+        let t = wb.sheet(si)?.tables.get(ti)?;
+        return Some((si, vec![t.data_range().unwrap_or(t.range)], true));
+    }
+    None
 }
 
-impl<'a> Resolver<'a> {
-    fn new(wb: &'a gridcraft_model::Workbook) -> Self {
-        let mut by_name: std::collections::HashMap<(Option<usize>, String), Vec<usize>> = std::collections::HashMap::new();
-        for (i, n) in wb.names.iter().enumerate() {
-            by_name.entry((n.scope, gridcraft_formula::fold_name(&n.name))).or_default().push(i);
-        }
-        Self { wb, by_name, memo: std::collections::HashMap::new() }
-    }
-
-    /// The first name of scope `scope` that `same` accepts, as a scan of `wb.names` finds it.
-    /// Names `same` accepts fold alike, so only that bucket is checked.
-    fn find(&self, scope: Option<usize>, body: &str, same: impl Fn(&str, &str) -> bool) -> Option<usize> {
-        self.by_name
-            .get(&(scope, gridcraft_formula::fold_name(body)))?
-            .iter()
-            .copied()
-            .find(|&i| self.wb.names.get(i).is_some_and(|n| same(&n.name, body)))
-    }
-
-    /// Where one part of a Go To reference points, seen from sheet `sheet`: the sheet, how many
-    /// areas (appended to `areas` when given), and whether a defined name or a table gave them.
-    /// `Sheet2!Name` is the name scoped to Sheet2. A name counts when what it refers to is a
-    /// reference; a constant or a formula is not one.
-    fn target(&mut self, sheet: usize, part: &str, depth: usize, areas: Option<&mut Vec<RangeRef>>) -> Option<(usize, usize, bool)> {
-        let wb = self.wb;
-        if part.is_empty() || depth > GO_TO_NAME_DEPTH {
+/// The sheet and areas defined name `n` refers to, seen from sheet `sheet`, when that is a
+/// reference.
+fn name_areas(wb: &gridcraft_model::Workbook, n: &gridcraft_model::DefinedName, sheet: usize, depth: usize) -> Option<(usize, Vec<RangeRef>)> {
+    let from = n.scope.unwrap_or(sheet);
+    let formula = n.formula.trim().trim_start_matches('=');
+    let mut target: Option<usize> = None;
+    let mut areas = Vec::new();
+    for p in reference_parts(formula) {
+        let (s, found, _) = go_to_target(wb, from, p, depth + 1)?;
+        if target.is_some_and(|t| t != s) {
             return None;
         }
-        let (prefix, body) = split_sheet(part);
-        let on = match &prefix {
-            Some(n) => wb.sheet_index(n)?,
-            None => sheet,
-        };
-        if let Some(r) = RangeRef::parse(&body.replace('$', "")) {
-            if let Some(a) = areas {
-                a.push(r);
-            }
-            return Some((on, 1, false));
+        target = Some(s);
+        areas.extend(found);
+        if areas.len() > GO_TO_MAX_AREAS {
+            return None;
         }
-        // As `Workbook::name`: the sheet's own name, else the workbook's.
-        let name = match prefix {
-            Some(_) => self.find(Some(on), body, gridcraft_formula::same_name),
-            None => self.find(Some(sheet), body, str::eq_ignore_ascii_case).or_else(|| self.find(None, body, str::eq_ignore_ascii_case)),
-        };
-        if let Some(i) = name {
-            return self.name_areas(i, sheet, depth, areas).map(|(t, n)| (t, n, true));
-        }
-        if prefix.is_none()
-            && let Some((si, ti)) = wb.table(body)
-        {
-            // As in Excel, a table's name stands for its data, without the header and totals rows.
-            let t = wb.sheet(si)?.tables.get(ti)?;
-            if let Some(a) = areas {
-                a.push(t.data_range().unwrap_or(t.range));
-            }
-            return Some((si, 1, true));
-        }
-        None
-    }
-
-    /// The sheet and number of areas defined name `wb.names[i]` refers to, seen from sheet
-    /// `sheet`, when that is a reference; the areas are appended to `areas` when given.
-    fn name_areas(&mut self, i: usize, sheet: usize, depth: usize, mut areas: Option<&mut Vec<RangeRef>>) -> Option<(usize, usize)> {
-        let key = (i, sheet, depth);
-        if areas.is_none()
-            && let Some(known) = self.memo.get(&key)
-        {
-            return *known;
-        }
-        let out = self.name_areas_uncached(i, sheet, depth, areas.as_deref_mut());
-        if areas.is_none() {
-            self.memo.insert(key, out);
-        }
-        out
-    }
-
-    fn name_areas_uncached(&mut self, i: usize, sheet: usize, depth: usize, mut areas: Option<&mut Vec<RangeRef>>) -> Option<(usize, usize)> {
-        let n = self.wb.names.get(i)?;
-        let from = n.scope.unwrap_or(sheet);
-        let formula = n.formula.trim().trim_start_matches('=');
-        let mut target: Option<usize> = None;
-        let mut count = 0usize;
-        for p in reference_parts(formula) {
-            let (s, found, _) = self.target(from, p, depth + 1, areas.as_deref_mut())?;
-            if target.is_some_and(|t| t != s) {
-                return None;
-            }
-            target = Some(s);
-            count += found;
-            if count > GO_TO_MAX_AREAS {
-                return None;
-            }
-        }
-        target.map(|t| (t, count))
     }
+    target.map(|t| (t, areas))
 }
 
 /// The names the Go To dialog lists, seen from sheet `sheet`: the named ranges of the workbook and
@@ -196,13 +137,11 @@ impl<'a> Resolver<'a> {
 pub fn go_to_names(wb: &gridcraft_model::Workbook, sheet: usize) -> Vec<String> {
     let own: std::collections::HashSet<String> =
         wb.names.iter().filter(|n| n.scope == Some(sheet)).map(|n| gridcraft_formula::fold_name(&n.name)).collect();
-    let mut names = Resolver::new(wb);
     let mut out: Vec<String> = wb
         .names
         .iter()
-        .enumerate()
-        .filter(|(i, n)| !n.hidden && names.name_areas(*i, sheet, 0, None).is_some())
-        .filter_map(|(_, n)| match n.scope {
+        .filter(|n| !n.hidden && name_areas(wb, n, sheet, 0).is_some())
+        .filter_map(|n| match n.scope {
             None if own.contains(&gridcraft_formula::fold_name(&n.name)) => None,
             None => Some(n.name.clone()),
             Some(s) if s == sheet => Some(n.name.clone()),

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

@@ -42,28 +42,6 @@ fn go_to_lists_the_named_ranges_of_every_sheet() {
     assert_eq!(list["names"], json!(["Areas", "Local", "Price", "Sheet1!Own", "type"]), "{list}");
 }
 
-/// Thousands of names that alias other names are listed with one lookup per alias, not a scan of
-/// every name for each; aliases resolve through the chain like a single name does.
-#[test]
-fn go_to_lists_many_aliases_and_follows_them() {
-    let mut s = go_to_workbook();
-    let wb = std::sync::Arc::make_mut(&mut s.doc_mut().unwrap().wb);
-    let alias = |name: String, formula: String| gridcraft_model::DefinedName { name, scope: None, formula, comment: String::new(), hidden: false };
-    wb.names.push(alias("Chain0".into(), "Areas".into()));
-    for i in 1..20_000 {
-        wb.names.push(alias(format!("Chain{i}"), format!("Chain{},price", i - 1)));
-    }
-    let list = s.execute("edit.goTo", json!({"list": true})).unwrap();
-    let names: Vec<&str> = list["names"].as_array().unwrap().iter().filter_map(|n| n.as_str()).collect();
-    // Chain0..Chain6 are within the name depth Go To follows; longer chains are not ranges.
-    for i in 0..7 {
-        assert!(names.contains(&format!("Chain{i}").as_str()), "Chain{i} in {names:?}");
-    }
-    assert!(!names.contains(&"Chain7"), "{names:?}");
-    let out = s.execute("edit.goTo", json!({"reference": "chain1"})).unwrap();
-    assert_eq!(out["selection"], "A1,C3:C4,B2:B5", "{out}");
-}
-
 #[test]
 fn go_to_a_name_scoped_to_another_sheet_goes_to_that_sheet() {
     let mut s = go_to_workbook();

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