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/extra/data.rs

@@ -42,15 +42,6 @@ pub(super) fn table_resize(s: &mut Session, p: &Json) -> Result<Json> {
     })
 }
 
-/// Most cells (rows × columns, blanks included) Get Data imports. The rows are built densely
-/// before they are written, so a few sparse records or one far-away CSV cell must not expand
-/// into a rectangle of billions of slots.
-const MAX_IMPORT_CELLS: u64 = 10_000_000;
-
-fn too_many_cells() -> EngineError {
-    EngineError::Other(format!("The data is too large to import ({MAX_IMPORT_CELLS} cells at most)."))
-}
-
 pub(super) fn from_csv(s: &mut Session, p: &Json) -> Result<Json> {
     let bytes = if let Some(t) = str_param(p, "text") {
         t.as_bytes().to_vec()
@@ -66,22 +57,15 @@ pub(super) fn from_csv(s: &mut Session, p: &Json) -> Result<Json> {
         if text.trim_start().starts_with('[') {
             let arr: Vec<Json> = serde_json::from_str(&text).map_err(|e| bad("data.getData", e.to_string()))?;
             let mut keys: Vec<String> = Vec::new();
-            let mut seen: std::collections::HashSet<&str> = std::collections::HashSet::new();
             for o in &arr {
                 if let Some(m) = o.as_object() {
                     for k in m.keys() {
-                        if seen.insert(k.as_str()) {
+                        if !keys.contains(k) {
                             keys.push(k.clone());
                         }
                     }
                 }
             }
-            if keys.len() > gridcraft_core::MAX_COLS as usize {
-                return Err(EngineError::Other("The data has more fields than a sheet has columns.".into()));
-            }
-            if (arr.len() as u64 + 1).saturating_mul(keys.len().max(1) as u64) > MAX_IMPORT_CELLS {
-                return Err(too_many_cells());
-            }
             let mut out = vec![keys.iter().map(|k| json!(k)).collect::<Vec<_>>()];
             for o in &arr {
                 out.push(keys.iter().map(|k| o.get(k).cloned().unwrap_or(Json::Null)).collect());
@@ -95,9 +79,6 @@ pub(super) fn from_csv(s: &mut Session, p: &Json) -> Result<Json> {
             let wb = gridcraft_xlsx::read_csv(&bytes, &opts).map_err(|e| EngineError::Other(e.to_string()))?;
             let sh = wb.sheet(0).ok_or(EngineError::NoDocument)?;
             let Some(u) = sh.used_range() else { return Err(EngineError::Other("The file is empty.".into())) };
-            if u.count() > MAX_IMPORT_CELLS {
-                return Err(too_many_cells());
-            }
             (u.start.row..=u.end.row)
                 .map(|r| {
                     (u.start.col..=u.end.col)
@@ -148,35 +129,3 @@ pub(super) fn queries(s: &mut Session, _: &Json) -> Result<Json> {
             .collect(),
     ))
 }
-
-#[cfg(test)]
-mod tests {
-    use serde_json::json;
-
-    use crate::Session;
-
-    fn s() -> Session {
-        let mut s = Session::new();
-        s.new_workbook();
-        s
-    }
-
-    #[test]
-    fn sparse_imports_are_refused_before_their_rows_are_built() {
-        let mut s = s();
-        let sheets = s.doc().unwrap().wb.sheets.len();
-        // 5,000 records with one field each: 5,001 × 5,000 slots once every record gets every field.
-        let records: Vec<_> = (0..5_000).map(|i| json!({ format!("k{i}"): i })).collect();
-        let text = serde_json::to_string(&records).unwrap();
-        let err = s.execute("data.getData", json!({"text": text})).expect_err("too many cells");
-        assert!(err.to_string().contains("too large"), "{err}");
-        // A CSV whose last line reaches 16,001 columns, 1,000 lines down.
-        let text = format!("1{}{}x", "\n".repeat(999), ",".repeat(16_000));
-        let err = s.execute("data.fromTextCsv", json!({"text": text})).expect_err("too many cells");
-        assert!(err.to_string().contains("too large"), "{err}");
-        assert_eq!(s.doc().unwrap().wb.sheets.len(), sheets);
-        // Small imports still work.
-        let out = s.execute("data.getData", json!({"text": r#"[{"a": 1}, {"b": 2}]"#})).unwrap();
-        assert_eq!((out["rows"].as_u64(), out["cols"].as_u64()), (Some(3), Some(2)), "{out}");
-    }
-}

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