address review: cache the chart-sheet usability verdict per relationship id instead of every reference

chart_sheet_usable walked a chart sheet's relationship graph and parsed
its charts for every workbook entry, so many entries naming one shared
graph multiplied the work. The referenced sheet names are now cached by
relationship id.

crates/engine/src/io.rs

@@ -3,7 +3,7 @@
 use std::fmt::Write as _;
 
 use gridcraft_core::{CellRef, RangeRef};
-use gridcraft_model::{LineIndex, Sheet, Workbook};
+use gridcraft_model::{Sheet, Workbook};
 
 use crate::{EngineError, Result};
 
@@ -548,23 +548,6 @@ fn table_dir(sh: &Sheet) -> &'static str {
 const CLIPBOARD_HTML_MAX_BYTES: usize = 4 * 1024 * 1024;
 const CLIPBOARD_HTML_MAX_CELLS: u64 = 10_000;
 
-/// The merge covering each cell of `rect`, as `Sheet::merge_at` would find it (the first in the
-/// sheet's list), built once so a table lookup is one probe instead of a scan of every merge.
-/// `None` when overlapping merges would cost more than a few visits per cell of `rect`: a
-/// hostile file's merge list can't multiply the work of a bounded export.
-fn merge_index(sh: &Sheet, rect: RangeRef) -> Option<std::collections::HashMap<CellRef, RangeRef>> {
-    let mut map = std::collections::HashMap::new();
-    let mut left = rect.count().saturating_mul(4);
-    for m in &sh.merges {
-        let Some(part) = m.intersection(&rect) else { continue };
-        left = left.checked_sub(part.count())?;
-        for c in part.iter() {
-            map.entry(c).or_insert(*m);
-        }
-    }
-    Some(map)
-}
-
 /// An HTML fragment for the same range as `plain_text`, previously produced by
 /// `display::range_text`. Large copies keep plain text only; never return a partial table.
 pub(crate) fn range_html(wb: &Workbook, sheet: usize, r: RangeRef, plain_text: &str) -> Option<String> {
@@ -573,7 +556,6 @@ pub(crate) fn range_html(wb: &Workbook, sheet: usize, r: RangeRef, plain_text: &
         return None;
     }
     let sh = wb.sheet(sheet)?;
-    let merges = merge_index(sh, r)?;
     let mut out = ClipboardHtml(String::new());
     write!(out, "<table{} style=\"border-collapse:collapse;font-family:Calibri,Carlito,Arial,sans-serif;font-size:11pt\">", table_dir(sh)).ok()?;
     for row in r.start.row..=r.end.row {
@@ -583,7 +565,7 @@ pub(crate) fn range_html(wb: &Workbook, sheet: usize, r: RangeRef, plain_text: &
         out.write_str("<tr>").ok()?;
         for col in r.start.col..=r.end.col {
             let c = CellRef::new(row, col);
-            let span = if let Some(merged) = merges.get(&c).and_then(|m| m.intersection(&r)) {
+            let span = if let Some(merged) = sh.merges.iter().find(|m| m.contains(c)).and_then(|m| m.intersection(&r)) {
                 let first_row = (merged.start.row..=merged.end.row).find(|&row| !sh.is_row_hidden(row))?;
                 if c != CellRef::new(first_row, merged.start.col) {
                     continue;
@@ -646,14 +628,6 @@ const HTML_EXPORT_MAX_ROWS: u32 = 100_001;
 /// tall, wide one) would otherwise be gigabytes of `<td></td>` before finishing (#2387).
 const HTML_EXPORT_MAX_CELLS: u64 = 4_000_000;
 
-/// Most bytes of one web page. Every cell may hold long text (shared across many cells in the
-/// file), so the cell count alone doesn't bound the page; past this the export fails instead.
-const HTML_EXPORT_MAX_BYTES: usize = 256 * 1024 * 1024;
-
-fn html_too_big() -> EngineError {
-    EngineError::Other(format!("the web page would be over {} MiB. Save as .xlsx or CSV instead.", HTML_EXPORT_MAX_BYTES / (1024 * 1024)))
-}
-
 /// A sheet as a standalone HTML table (Save as Web Page). A sheet with pictures gets the sheet's
 /// own column widths and row heights so each picture and chart (inline SVG) can sit at its anchor.
 pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
@@ -696,23 +670,6 @@ pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
                 r.width()
             )));
         }
-        let merges = merge_index(sh, r).ok_or_else(|| EngineError::Other("the sheet's merged cells overlap too much for a web page.".into()))?;
-        // Visible rows and columns of the table before each line, so a merge's span is counted
-        // in constant time whatever the file says its size is.
-        let visible_before = |hidden: &dyn Fn(u32) -> bool, from: u32, to: u32| {
-            let mut v = Vec::with_capacity((to - from) as usize + 2);
-            v.push(0u32);
-            for line in from..=to {
-                v.push(v.last().copied().unwrap_or(0) + u32::from(!hidden(line)));
-            }
-            v
-        };
-        let rows_before = visible_before(&|y| sh.is_row_hidden(y), r.start.row, r.end.row);
-        let cols_before = visible_before(&|x| sh.is_col_hidden(x), r.start.col, r.end.col);
-        let visible = |before: &[u32], from: u32, a: u32, b: u32| {
-            let at = |line: u32| before.get((line - from) as usize).copied().unwrap_or(0);
-            at(b + 1) - at(a)
-        };
         if fixed {
             out.push_str("<colgroup>");
             for col in (r.start.col..=r.end.col).filter(|&c| !sh.is_col_hidden(c)) {
@@ -731,19 +688,20 @@ pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
             }
             for col in r.start.col..=r.end.col {
                 let c = CellRef::new(row, col);
-                let merge = merges.get(&c);
-                if merge.is_some_and(|m| m.start != c) || (fixed && sh.is_col_hidden(col)) {
+                if sh.merges.iter().any(|m| m.contains(c) && m.start != c) || (fixed && sh.is_col_hidden(col)) {
                     continue;
                 }
                 let text = crate::display::cell_text(wb, sh, c);
                 let dir = CellDir::of(sh, c, &text);
                 let css = html_cell_css(wb, sh, c, dir);
-                let span = merge
+                let span = sh
+                    .merges
+                    .iter()
+                    .find(|m| m.start == c)
                     .map(|m| {
                         if fixed {
-                            // Spans count the table's visible lines: the merge is clipped to the table.
-                            let rows = visible(&rows_before, r.start.row, m.start.row, m.end.row.min(r.end.row));
-                            let cols = visible(&cols_before, r.start.col, m.start.col, m.end.col.min(r.end.col));
+                            let rows = (m.start.row..=m.end.row).filter(|&y| !sh.is_row_hidden(y)).count();
+                            let cols = (m.start.col..=m.end.col).filter(|&x| !sh.is_col_hidden(x)).count();
                             format!(" rowspan=\"{rows}\" colspan=\"{cols}\"")
                         } else {
                             format!(" rowspan=\"{}\" colspan=\"{}\"", m.height(), m.width())
@@ -751,9 +709,6 @@ pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
                     })
                     .unwrap_or_default();
                 let _ = write!(out, "<td style=\"{css}\"{}{span}>{}</td>", dir.attr(), esc(&text));
-                if out.len() > HTML_EXPORT_MAX_BYTES {
-                    return Err(html_too_big());
-                }
             }
             out.push_str("</tr>");
         }
@@ -761,15 +716,12 @@ pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
     out.push_str("</table>");
     if fixed {
         // Sheet units are CSS pixels; the table starts at the used range, not at A1.
-        // Indexed positions: each anchor would otherwise sum every custom row and column before it.
-        let ri = LineIndex::new(&sh.rows, sh.default_row_height, gridcraft_core::MAX_ROWS);
-        let ci = LineIndex::new(&sh.cols, sh.default_col_width, gridcraft_core::MAX_COLS);
-        let (left, top) = used.map_or((0.0, 0.0), |r| (ci.start(r.start.col), ri.start(r.start.row)));
+        let (left, top) = used.map_or((0.0, 0.0), |r| (sh.col_left(r.start.col), sh.row_top(r.start.row)));
         let place = |a: &gridcraft_model::Anchor| {
             format!(
                 "position:absolute;left:{}px;top:{}px;width:{}px;height:{}px",
-                ci.start(a.cell.col) - left + f64::from(a.dx),
-                ri.start(a.cell.row) - top + f64::from(a.dy),
+                sh.col_left(a.cell.col) - left + f64::from(a.dx),
+                sh.row_top(a.cell.row) - top + f64::from(a.dy),
                 a.width.max(0.0),
                 a.height.max(0.0)
             )
@@ -783,24 +735,15 @@ pub fn to_html(wb: &Workbook, sheet: usize) -> Result<String> {
                 esc(&im.alt),
                 place(&im.anchor)
             );
-            if out.len() > HTML_EXPORT_MAX_BYTES {
-                return Err(html_too_big());
-            }
         }
         for ch in &sh.charts {
             if let Some(svg) = crate::chart_svg::chart_svg(wb, sheet, ch, &place(&ch.anchor)) {
                 out.push_str(&svg);
-                if out.len() > HTML_EXPORT_MAX_BYTES {
-                    return Err(html_too_big());
-                }
             }
         }
         out.push_str("</div>");
     }
     out.push_str("</body></html>");
-    if out.len() > HTML_EXPORT_MAX_BYTES {
-        return Err(html_too_big());
-    }
     Ok(out)
 }
 

crates/engine/src/io/tests.rs

@@ -604,57 +604,3 @@ fn opening_google_sheets_export_unwraps_only_formulas_gridcraft_calculates() {
     assert_eq!(text("A2").as_deref(), Some("IFERROR(__XLUDF.DUMMYFUNCTION(\"GOOGLETRANSLATE(\"\"hi\"\",\"\"en\"\",\"\"fr\"\")\"),\"salut\")"));
     assert_eq!(opened.sheets[0].cells.get(CellRef::parse("A2").unwrap()).map(|c| c.value.clone()), Some(Value::text("salut")));
 }
-
-/// Merges far from what is copied or exported, in a hostile number, are indexed once instead of
-/// being scanned for every cell; a merge running past the table is clipped to it.
-#[test]
-fn html_merge_lookups_and_spans_stay_bounded() {
-    let mut wb = book_with_picture("A1", (0, 0));
-    let sh = wb.sheet_mut(0).unwrap();
-    for i in 0..200_000u32 {
-        sh.merges.push(RangeRef::new(CellRef::new(500_000 + i * 2, 5), CellRef::new(500_000 + i * 2, 6)));
-    }
-    sh.merges.push(RangeRef::new(CellRef::new(0, 0), CellRef::new(gridcraft_core::MAX_ROWS - 1, 1)));
-    sh.set_value(CellRef::new(2, 1), gridcraft_core::Value::Number(2.0));
-    let html = copied(&wb, "A1:C50");
-    assert!(html.contains("rowspan=\"50\" colspan=\"2\""), "{html}");
-    let page = to_html(&wb, 0).unwrap();
-    // The table is A1:B3 (the used range): the whole-height merge spans its three rows only.
-    assert!(page.contains("rowspan=\"3\" colspan=\"2\""), "{page}");
-    // Merges stacked over one another past a few per cell are refused, not walked.
-    let sh = wb.sheet_mut(0).unwrap();
-    sh.merges = vec![RangeRef::new(CellRef::new(0, 0), CellRef::new(2, 1)); 100];
-    assert!(to_html(&wb, 0).is_err());
-    assert!(range_html(&wb, 0, RangeRef::parse("A1:B3").unwrap(), "").is_none());
-}
-
-/// Thousands of pictures over thousands of custom rows: each is placed through a row index.
-#[test]
-fn html_export_places_many_pictures_over_many_custom_rows() {
-    let mut wb = book_with_picture("A1", (0, 0));
-    let sh = wb.sheet_mut(0).unwrap();
-    for row in 0..50_000 {
-        sh.rows.insert(row, gridcraft_model::LineInfo { size: Some(30.0), ..Default::default() });
-    }
-    let image = sh.images[0].clone();
-    for i in 0..5_000u32 {
-        let mut im = image.clone();
-        im.anchor.cell = CellRef::new(40_000 + i, 0);
-        sh.images.push(im);
-    }
-    let page = to_html(&wb, 0).unwrap();
-    assert!(page.contains(&format!("top:{}px", 30 * 44_999)), "last picture placed by the index");
-}
-
-/// One long text shown by many cells: the page fails at its byte limit instead of growing on.
-#[test]
-fn html_export_refuses_a_page_past_its_byte_limit() {
-    let mut wb = Workbook::new();
-    let sh = wb.sheet_mut(0).unwrap();
-    let text = gridcraft_core::Value::text("x".repeat(32_000));
-    for row in 0..10_000 {
-        sh.set_value(CellRef::new(row, 0), text.clone());
-    }
-    let err = to_html(&wb, 0).unwrap_err();
-    assert!(err.to_string().contains("MiB"), "{err}");
-}

crates/xlsx/src/passthrough/write.rs

@@ -254,27 +254,36 @@ pub(crate) fn sheet_names_in(formula: &str) -> Vec<String> {
 /// Whether a kept chart sheet can be written back: its chart's series must still refer to sheets
 /// that exist under the same names (the chart is kept as it was, so a series on a deleted or
 /// renamed sheet would be left pointing at nothing), and no worksheet may have taken its name.
-fn chart_sheet_usable(wb: &Workbook, p: &Preserved, s: &PreservedSheet) -> bool {
+///
+/// `usable` caches, by relationship id, whether that chart sheet's graph refers only to sheets
+/// that exist (`false` when the relationship is missing): entries sharing one graph are analysed
+/// once, and only the verdict is kept, not the references it came from.
+fn chart_sheet_usable<'p>(wb: &Workbook, p: &'p Preserved, s: &'p PreservedSheet, usable: &mut HashMap<&'p str, bool>) -> bool {
     let same = |a: &str, b: &str| a.chars().take(31).collect::<String>().eq_ignore_ascii_case(&b.chars().take(31).collect::<String>());
     if wb.sheets.iter().any(|w| same(&w.name, &s.name)) {
         return false;
     }
-    let Some(root) = p.rels.iter().find(|r| r.id == s.rel_id) else { return false };
-    let parts = reachable(p, root);
-    let mut formulas = vec![];
-    for q in p.parts.iter().filter(|q| parts.contains(&normalize(&q.name)) && q.content_type.contains("chart")) {
-        if let Ok(x) = xml::parse(&q.data) {
-            chart_formulas(&x, &mut formulas);
+    *usable.entry(s.rel_id.as_str()).or_insert_with(|| {
+        let Some(root) = p.rels.iter().find(|r| r.id == s.rel_id) else { return false };
+        let parts = reachable(p, root);
+        let mut formulas = vec![];
+        for q in p.parts.iter().filter(|q| parts.contains(&normalize(&q.name)) && q.content_type.contains("chart")) {
+            if let Ok(x) = xml::parse(&q.data) {
+                chart_formulas(&x, &mut formulas);
+            }
         }
-    }
-    formulas.iter().flat_map(|f| sheet_names_in(f)).all(|n| wb.sheets.iter().any(|w| same(&w.name, &n)))
+        formulas.iter().flat_map(|f| sheet_names_in(f)).all(|n| wb.sheets.iter().any(|w| same(&w.name, &n)))
+    })
 }
 
 /// Writes the workbook's kept parts and relationships. Chart sheets that can't be written back
 /// (see [`chart_sheet_usable`]) are left out with the parts only they reach.
 pub fn write_workbook(wb: &Workbook, wb_rels: &mut Rels, out: &mut Out) -> WorkbookKept {
     let Some(p) = wb.preserved.as_deref() else { return WorkbookKept::default() };
-    let (live, dropped): (Vec<&PreservedSheet>, Vec<&PreservedSheet>) = p.sheets.iter().partition(|s| chart_sheet_usable(wb, p, s));
+    let (live, dropped): (Vec<&PreservedSheet>, Vec<&PreservedSheet>) = {
+        let mut refs = HashMap::new();
+        p.sheets.iter().partition(|s| chart_sheet_usable(wb, p, s, &mut refs))
+    };
     let root_of = |s: &PreservedSheet| p.rels.iter().find(|r| r.id == s.rel_id);
     let dropped_ids: HashSet<&str> = dropped.iter().map(|s| s.rel_id.as_str()).collect();
     // Parts reached only by dropped chart sheets go with them.

crates/xlsx/src/tests/passthrough_tests.rs

@@ -696,6 +696,32 @@ fn chartsheet_package() -> Vec<u8> {
     ])
 }
 
+/// Thousands of chart-sheet entries naming one chart sheet's relationship: its graph is walked
+/// and its charts parsed once when saving, not once per entry.
+#[test]
+fn chart_sheet_entries_sharing_a_graph_are_checked_once() {
+    let bytes = chartsheet_package();
+    let mut z = zip::ZipArchive::new(std::io::Cursor::new(bytes)).unwrap();
+    let mut parts: Vec<(String, Vec<u8>)> = Vec::new();
+    for i in 0..z.len() {
+        let mut f = z.by_index(i).unwrap();
+        let mut data = Vec::new();
+        f.read_to_end(&mut data).unwrap();
+        parts.push((f.name().to_string(), data));
+    }
+    let extra: String = (0..3_000).map(|i| format!(r#"<sheet name="Copy{i}" sheetId="{}" r:id="rId2"/>"#, 100 + i)).collect();
+    for (name, data) in &mut parts {
+        if name == "xl/workbook.xml" {
+            *data = String::from_utf8(data.clone()).unwrap().replace("</sheets>", &format!("{extra}</sheets>")).into_bytes();
+        }
+    }
+    let refs: Vec<(&str, &[u8])> = parts.iter().map(|(n, d)| (n.as_str(), d.as_slice())).collect();
+    let (wb, _) = read_xlsx(&make_zip(&refs)).unwrap();
+    let u = Unpacked::new(&write_xlsx(&wb).unwrap());
+    u.assert_valid();
+    assert!(written_sheets(&u).iter().any(|(n, _)| n == "Chart1"));
+}
+
 /// The sheets of a written workbook: (name, state) in file order.
 fn written_sheets(u: &Unpacked) -> Vec<(String, String)> {
     let wb = xml::parse(u.parts.get("xl/workbook.xml").unwrap()).unwrap();