print: hold the print area to the grid; render each chart once and budget picture and chart output across pages

crates/engine/src/cmd/print.rs

@@ -32,8 +32,26 @@ use header_footer::draw_header_footer;
 pub use header_footer::{
     HF_FIELDS, HfContext, HfSection, codes_to_fields, expand_header_footer, fields_to_codes, hf_date_time, join_header_footer, split_header_footer,
 };
-/// Decoded pictures (bytes, width, height) keyed by (sheet, picture); `None` = undecodable.
-type PicCache = std::collections::HashMap<(usize, usize), Option<(Vec<u8>, u32, u32)>>;
+type DecodedPicture = (Vec<u8>, u32, u32);
+
+/// What one PDF render shares across the pages an object spans.
+#[derive(Default)]
+struct PicCache {
+    /// Decoded pictures (bytes, width, height) keyed by (sheet, picture); `None` = undecodable.
+    decoded: std::collections::HashMap<(usize, usize), Option<DecodedPicture>>,
+    /// Laid-out charts keyed by (sheet, chart), rendered once however many pages they touch.
+    charts: std::collections::HashMap<(usize, usize), Vec<gridcraft_chart::Prim>>,
+    /// Bytes of picture pixels embedded so far, and chart primitives emitted so far. Each page an
+    /// object touches gets its own copy in the PDF, so a workbook-controlled anchor over thousands
+    /// of pages would multiply them without bound.
+    image_bytes: usize,
+    chart_prims: usize,
+}
+
+/// Most picture pixel bytes (RGBA, before PDF packing) one render embeds across all pages.
+const MAX_EMBEDDED_IMAGE_BYTES: usize = 512 * 1024 * 1024;
+/// Most chart primitives one render draws across all pages.
+const MAX_CHART_PRIMS: usize = 4_000_000;
 
 #[cfg(test)]
 use layout::bands;
@@ -102,7 +120,7 @@ pub fn render_pdf(wb: &Workbook, layouts: &[SheetLayout], file: &str, path: &str
     let mut printed_blocks = Vec::new();
     // Decoded pictures are reused across the pages their anchor covers: a floating picture
     // spanning 40 pages was decoded (and pushed into the PDF) 40 times (#2389).
-    let mut pics = PicCache::new();
+    let mut pics = PicCache::default();
     for lay in layouts {
         let Some(sh) = wb.sheet(lay.sheet) else { continue };
         let mut cf = if sh.cond_formats.is_empty() { None } else { Some(crate::cf::CfCache::new()) };

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

@@ -224,6 +224,12 @@ pub fn layout_sheet(wb: &Workbook, si: usize, opts: &PrintOptions, range_overrid
         Some(r) => trim_full(sh, r),
         None => print_range(sh).unwrap_or(RangeRef::cell(CellRef::new(0, 0))),
     };
+    // A print area from a file or JSON can name coordinates past the grid; pagination walks every
+    // line of the area (zero-height rows never fill a band), so it is held to the grid first.
+    let area = RangeRef::new(
+        CellRef::new(area.start.row.min(MAX_ROWS - 1), area.start.col.min(MAX_COLS - 1)),
+        CellRef::new(area.end.row.min(MAX_ROWS - 1), area.end.col.min(MAX_COLS - 1)),
+    );
     let title_rows = title_span(st.title_rows, MAX_ROWS);
     let title_cols = title_span(st.title_cols, MAX_COLS);
     let digits = format!("{}", area.end.row + 1).len() as f32;
@@ -379,3 +385,19 @@ pub(super) fn segments(titles: Option<(u32, u32)>, band: (u32, u32)) -> Vec<(u32
 pub(super) fn seg_size(sh: &Sheet, seg: (u32, u32), rows: bool) -> f32 {
     if rows { (seg.0..=seg.1).map(|r| sh.row_height(r)).sum() } else { (seg.0..=seg.1).map(|c| sh.col_width(c)).sum() }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn a_print_area_past_the_grid_is_held_to_the_grid() {
+        let mut wb = Workbook::new();
+        let sh = wb.sheet_mut(0).unwrap();
+        sh.default_row_height = 0.0;
+        sh.print.print_area = Some(RangeRef { start: CellRef::new(0, 0), end: CellRef::new(u32::MAX, u32::MAX) });
+        let lay = layout_sheet(&wb, 0, &PrintOptions::default(), None).unwrap();
+        assert_eq!((lay.area.end.row, lay.area.end.col), (MAX_ROWS - 1, MAX_COLS - 1));
+        assert!(lay.pages.len() <= MAX_PAGES);
+    }
+}

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

@@ -88,9 +88,14 @@ pub(super) fn draw_objects(pg: &mut Page, wb: &Workbook, si: usize, sh: &Sheet,
         let (x, y, w, h) = place(r);
         // About 150 dpi is plenty for print.
         let (mw, mh) = (((w / 72.0) * 150.0).ceil().clamp(1.0, 4000.0) as u32, ((h / 72.0) * 150.0).ceil().clamp(1.0, 4000.0) as u32);
-        let decoded = pics.entry((si, imi)).or_insert_with(|| decode_image(&im.data, mw, mh));
+        let decoded = pics.decoded.entry((si, imi)).or_insert_with(|| decode_image(&im.data, mw, mh));
         if let Some((px, pw, ph)) = decoded.as_ref() {
-            pg.image_rgba(Rect::new(x, y, w, h), px, [*pw, *ph]);
+            // Every page the picture touches embeds its own copy: past the budget it is left out.
+            let bytes = px.len();
+            if pics.image_bytes.saturating_add(bytes) <= super::MAX_EMBEDDED_IMAGE_BYTES {
+                pics.image_bytes += bytes;
+                pg.image_rgba(Rect::new(x, y, w, h), px, [*pw, *ph]);
+            }
         }
     }
     for shp in &sh.shapes {
@@ -120,15 +125,21 @@ pub(super) fn draw_objects(pg: &mut Page, wb: &Workbook, si: usize, sh: &Sheet,
         }
         draw_shape(pg, wb, shp, b, (x, y, w, h));
     }
-    for ch in &sh.charts {
+    for (chi, ch) in sh.charts.iter().enumerate() {
         let r = anchor_rect(sh, &ch.anchor);
         if !visible(r) {
             continue;
         }
         let (x, y, _, _) = place(r);
-        let data = gridcraft_chart::resolve(wb, si, ch);
-        let prims = gridcraft_chart::render(ch, &data, r.2 as f32, r.3 as f32, &PdfMeasure);
-        draw_prims(pg, &prims, Xf { ox: x, oy: y, k: b.k });
+        let prims = pics.charts.entry((si, chi)).or_insert_with(|| {
+            let data = gridcraft_chart::resolve(wb, si, ch);
+            gridcraft_chart::render(ch, &data, r.2 as f32, r.3 as f32, &PdfMeasure)
+        });
+        // As for pictures, each page gets its own copy of the drawing commands.
+        if pics.chart_prims.saturating_add(prims.len()) <= super::MAX_CHART_PRIMS {
+            pics.chart_prims += prims.len();
+            draw_prims(pg, prims, Xf { ox: x, oy: y, k: b.k });
+        }
     }
     pg.restore();
 }

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

crates/xlsx/src/richdata.rs

@@ -142,22 +142,13 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
     let Some(image_rel_list) = read_xml(cx, &image_rels_path, "richValueRels")? else { return Ok(vec![]) };
     let image_rels = cx.pkg.rels(&image_rels_path)?;
     let structures = entries(cx, &structures, "s")?;
-    // Each structure's key layout, worked out once: every value would otherwise walk its
-    // structure's keys again. Only local-image structures matter here.
-    let layouts: Vec<Option<Layout>> = structures.iter().map(|s| Layout::of(s)).collect();
     let image_rel_list = entries(cx, &image_rel_list, "rel")?;
-    // Relationships by id, a repeated id recorded as invalid (`None`), so a value's lookup is
-    // one probe rather than a scan of the whole table for duplicates.
-    let mut rels_by_id: HashMap<&str, Option<&Rel>> = HashMap::new();
-    for rel in &image_rels {
-        rels_by_id.entry(rel.id.as_str()).and_modify(|r| *r = None).or_insert(Some(rel));
-    }
     let values = entries(cx, &data, "rv")?;
     let mut pictures = Vec::with_capacity(values.len());
     let mut cache = HashMap::new();
     let mut total = 0usize;
     for value in values {
-        let picture = read_value(cx, value, &layouts, &image_rel_list, &rels_by_id, &mut cache, &mut total)?;
+        let picture = read_value(cx, value, &structures, &image_rel_list, &image_rels, &mut cache, &mut total)?;
         if picture.is_none() {
             cx.warn("some rich values are unsupported or malformed; their scalar fallbacks were retained (cell pictures may be missing)");
         }
@@ -197,56 +188,43 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
         .collect())
 }
 
-/// Where a `_localImage` structure keeps the values a picture needs.
-struct Layout {
-    keys: usize,
-    /// Index of the one `_rvRel:LocalImageIdentifier` key of type `i`, if exactly one.
-    image: Option<usize>,
-    /// Index of the one `Text` key of type `s`, if exactly one.
-    text: Option<usize>,
-}
-
-impl Layout {
-    fn of(structure: &El) -> Option<Layout> {
-        if structure.attr("t") != Some("_localImage") {
-            return None;
-        }
-        let keys: Vec<&El> = structure.kids("k").collect();
-        let one = |name: &str, ty: &str| {
-            let mut matches = keys.iter().enumerate().filter(|(_, k)| k.attr("n") == Some(name));
-            let (i, key) = matches.next()?;
-            (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(i)
-        };
-        Some(Layout { keys: keys.len(), image: one("_rvRel:LocalImageIdentifier", "i"), text: one("Text", "s") })
-    }
-}
-
 fn read_value(
     cx: &mut Ctx<'_>,
     value: &El,
-    layouts: &[Option<Layout>],
+    structures: &[&El],
     image_rel_list: &[&El],
-    rels_by_id: &HashMap<&str, Option<&Rel>>,
+    image_rels: &[Rel],
     cache: &mut HashMap<(String, String), Arc<CellPicture>>,
     total: &mut usize,
 ) -> Result<Option<Arc<CellPicture>>, IoError> {
-    let Some(Some(layout)) = value.attr_u32("s").and_then(|n| layouts.get(n as usize)) else { return Ok(None) };
-    let values: Vec<_> = value.kids("v").collect();
-    if layout.keys != values.len() {
+    let Some(structure) = value.attr_u32("s").and_then(|n| structures.get(n as usize)) else { return Ok(None) };
+    if structure.attr("t") != Some("_localImage") {
         return Ok(None);
     }
-    let lookup = |slot: Option<usize>| slot.and_then(|i| values.get(i)).map(|v| v.text.as_str());
-    let Some(rel_id) =
-        lookup(layout.image).and_then(|v| v.trim().parse::<usize>().ok()).and_then(|n| image_rel_list.get(n)).and_then(|rel| rel.attr("id"))
+    let keys: Vec<_> = structure.kids("k").collect();
+    let values: Vec<_> = value.kids("v").collect();
+    if keys.len() != values.len() {
+        return Ok(None);
+    }
+    let lookup = |name: &str, ty: &str| {
+        let mut matches = keys.iter().zip(&values).filter(|(k, _)| k.attr("n") == Some(name));
+        let (key, value) = matches.next()?;
+        (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(value.text.as_str())
+    };
+    let Some(rel_id) = lookup("_rvRel:LocalImageIdentifier", "i")
+        .and_then(|v| v.trim().parse::<usize>().ok())
+        .and_then(|n| image_rel_list.get(n))
+        .and_then(|rel| rel.attr("id"))
     else {
         return Ok(None);
     };
-    let Some(found) = rels_by_id.get(rel_id) else { return Ok(None) };
-    let Some(rel) = found.filter(|rel| rel.kind == "image" && !rel.external) else {
+    let mut matches = image_rels.iter().filter(|rel| rel.id == rel_id);
+    let Some(rel) = matches.next() else { return Ok(None) };
+    if matches.next().is_some() || rel.kind != "image" || rel.external {
         cx.warn("a cell picture has an external or invalid image relationship; kept its scalar fallback");
         return Ok(None);
-    };
-    let alt = lookup(layout.text).unwrap_or("").to_string();
+    }
+    let alt = lookup("Text", "s").unwrap_or("").to_string();
     let key = (normalize(&rel.target), alt.clone());
     if let Some(picture) = cache.get(&key) {
         return Ok(Some(picture.clone()));

crates/xlsx/src/tests/richdata_tests.rs

@@ -294,27 +294,3 @@ fn picture_metadata_limits_and_relationship_read_errors_do_not_block_workbooks()
         assert!(report.warnings.iter().any(|w| w.contains("cell-picture data could not be read")), "{:?}", report.warnings);
     }
 }
-
-/// Many values over one wide structure, and a repeated relationship id: the structure's layout
-/// is worked out once and relationships are indexed, so the import is linear in the records;
-/// the repeated id is invalid and keeps the scalar fallback.
-#[test]
-fn wide_structures_and_repeated_relationship_ids_are_resolved_through_indexes() {
-    let mut parts = independent_parts(false);
-    // 200,000 keys in one structure and 50,000 short values that name it: rebuilding the key
-    // list per value would be ten billion steps.
-    let padding = r#"<k n="pad" t="s"/>"#.repeat(200_000);
-    replace(&mut parts, "rich/structures.xml", r#"<k n="CalcOrigin" t="i"/>"#, &format!(r#"<k n="CalcOrigin" t="i"/>{padding}"#));
-    let values = r#"<rv s="1"><v/></rv>"#.repeat(50_000);
-    replace(&mut parts, "rich/values.xml", r#"<rv s="1"><v>green &amp; &lt;image&gt;</v><v>1</v><v>5</v></rv>"#, &values);
-    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
-    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
-    assert!(report.warnings.iter().any(|w| w.contains("picture")), "{:?}", report.warnings);
-    // The same id twice makes every reference to it invalid.
-    let mut parts = independent_parts(false);
-    let dup = r#"<Relationship Id="opaqueImageId" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/image" Target="../media/original.bin"/>"#;
-    replace(&mut parts, "rich/_rels/images.xml.rels", dup, &dup.repeat(2));
-    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
-    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
-    assert!(report.warnings.iter().any(|w| w.contains("invalid image relationship")), "{:?}", report.warnings);
-}