merge main into fix/sec-html-export-merge-index

Save as Web Page and the clipboard's HTML scanned every merge of the
sheet for every cell, counted a merge's span over all the rows the file
gave it, placed each picture by summing every custom row before it, and
grew the page without a byte limit. Merges are now indexed once over
the exported rectangle (overlapping merges past a few visits per cell
are refused), spans use prefix counts clipped to the table, anchors use
LineIndex, and the page stops at 256 MiB with an error.

crates/engine/src/cmd/solver/reports.rs

@@ -52,19 +52,14 @@ pub(super) fn abs_ref(c: CellRef) -> String {
     format!("${}${}", gridcraft_core::col_to_letters(c.col), u64::from(c.row) + 1)
 }
 
-/// How many cells to the left and above a cell its name is searched for.
-const NAME_REACH: u32 = 1_000;
-
 /// A cell's name in the reports: the nearest text to its left and the nearest text above it.
 pub(super) fn cell_name(sh: &Sheet, c: CellRef) -> String {
     let text = |c: CellRef| match sh.value(c) {
         Value::Text(t) if !t.trim().is_empty() => Some(t.to_string()),
         _ => None,
     };
-    // Labels are next to their cells: looking further than this on a sparse sheet only costs time
-    // (a thousand cells near the last row would each probe a million empty coordinates).
-    let left = (c.col.saturating_sub(NAME_REACH)..c.col).rev().find_map(|col| text(CellRef::new(c.row, col)));
-    let top = (c.row.saturating_sub(NAME_REACH)..c.row).rev().find_map(|row| text(CellRef::new(row, c.col)));
+    let left = (0..c.col).rev().find_map(|col| text(CellRef::new(c.row, col)));
+    let top = (0..c.row).rev().find_map(|row| text(CellRef::new(row, c.col)));
     [left, top].into_iter().flatten().collect::<Vec<_>>().join(" ")
 }
 
@@ -443,17 +438,3 @@ pub(super) fn report(s: &mut Session, p: &Json) -> Result<Json> {
     }
     Ok(out)
 }
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-
-    #[test]
-    fn a_name_is_searched_only_a_bounded_distance() {
-        let mut sh = Sheet::new("S".to_string());
-        sh.set_cell(CellRef::new(0, 0), gridcraft_model::Cell::value(Value::text("Far")));
-        sh.set_cell(CellRef::new(5, 4), gridcraft_model::Cell::value(Value::text("Near")));
-        assert_eq!(cell_name(&sh, CellRef::new(5, 5)), "Near");
-        assert_eq!(cell_name(&sh, CellRef::new(0, NAME_REACH + 1)), "");
-    }
-}

crates/engine/src/cmd/whatif/scenarios.rs

@@ -189,9 +189,6 @@ pub(super) fn scenario_delete(s: &mut Session, p: &Json) -> Result<Json> {
     Ok(json!({"deleted": removed.name}))
 }
 
-/// Most changing-cell-by-scenario cells one Scenario Summary writes.
-const MAX_SUMMARY_CELLS: usize = 1_000_000;
-
 pub(super) fn scenario_summary(s: &mut Session, p: &Json) -> Result<Json> {
     const CMD: &str = "data.scenarioSummary";
     let d = s.doc()?;
@@ -214,24 +211,17 @@ pub(super) fn scenario_summary(s: &mut Session, p: &Json) -> Result<Json> {
     // Changing cells of every scenario, first-seen order; per scenario its values.
     let mut changing: Vec<CellRef> = Vec::new();
     let mut per: Vec<HashMap<CellRef, Value>> = Vec::new();
-    let mut seen: std::collections::HashSet<CellRef> = Default::default();
     for sc in &scenarios {
         let (_, cells) = cell_list(&d.wb, &sc.changing, CMD, MAX_SCENARIO_CELLS)?;
         let mut m = HashMap::new();
         for (c, v) in cells.iter().zip(sc.values.iter()) {
-            if seen.insert(*c) {
+            if !changing.contains(c) {
                 changing.push(*c);
             }
             m.insert(*c, json_value(v, &d.wb));
         }
         per.push(m);
     }
-    // The summary has a cell for every changing cell in every scenario, filled from the current
-    // value where a scenario doesn't set it, so small disjoint scenarios multiply.
-    // Each result cell is a row of the summary too, with a cell per scenario.
-    if changing.len().saturating_add(results.len()).saturating_mul(per.len()) > MAX_SUMMARY_CELLS {
-        return Err(bad(CMD, "the scenarios together change too many cells for a summary"));
-    }
     let current: Vec<Value> = changing.iter().map(|c| sh.value(*c)).collect();
     let current_results: Vec<Value> = results.iter().map(|c| sh.value(*c)).collect();
     let mut trial = Trial::new(d);

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

@@ -310,25 +310,3 @@ fn consolidate_keys_are_indexed_and_the_output_is_bounded() {
     let r = s.execute("data.consolidate", json!({"sources": ["A1:A10000", "A1:XFC1"], "destination": "A1"}));
     assert!(r.unwrap_err().to_string().contains("too large"));
 }
-
-#[test]
-fn scenario_summary_refuses_a_matrix_over_its_cell_limit() {
-    let mut s = s();
-    // 200 scenarios of 32 disjoint cells: 6,400 changing cells x 200 scenarios = 1.28 million cells.
-    for i in 0..200 {
-        let (a, b) = (i * 32 + 1, i * 32 + 32);
-        s.execute("data.scenarioAdd", json!({"name": format!("S{i}"), "changing": format!("A{a}:A{b}")})).unwrap();
-    }
-    assert!(s.execute("data.scenarioSummary", json!({})).is_err());
-}
-
-#[test]
-fn scenario_summary_counts_result_rows_in_its_cell_limit() {
-    let mut s = s();
-    // 900 scenarios of one distinct cell each are 810,000 cells; 255 result rows take it past the limit.
-    for i in 0..900 {
-        s.execute("data.scenarioAdd", json!({"name": format!("S{i}"), "changing": format!("A{}", i + 1)})).unwrap();
-    }
-    let err = s.execute("data.scenarioSummary", json!({"resultCells": "C1:C255"})).unwrap_err().to_string();
-    assert!(err.contains("too many cells"), "{err}");
-}

crates/engine/src/io.rs

@@ -3,7 +3,7 @@
 use std::fmt::Write as _;
 
 use gridcraft_core::{CellRef, RangeRef};
-use gridcraft_model::{Sheet, Workbook};
+use gridcraft_model::{LineIndex, Sheet, Workbook};
 
 use crate::{EngineError, Result};
 
@@ -681,6 +681,23 @@ 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> {
@@ -689,6 +706,7 @@ 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 {
@@ -698,7 +716,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) = sh.merges.iter().find(|m| m.contains(c)).and_then(|m| m.intersection(&r)) {
+            let span = if let Some(merged) = merges.get(&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;
@@ -761,6 +779,14 @@ 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> {
@@ -803,6 +829,23 @@ 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)) {
@@ -821,20 +864,19 @@ 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);
-                if sh.merges.iter().any(|m| m.contains(c) && m.start != c) || (fixed && sh.is_col_hidden(col)) {
+                let merge = merges.get(&c);
+                if merge.is_some_and(|m| 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 = sh
-                    .merges
-                    .iter()
-                    .find(|m| m.start == c)
+                let span = merge
                     .map(|m| {
                         if fixed {
-                            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();
+                            // 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));
                             format!(" rowspan=\"{rows}\" colspan=\"{cols}\"")
                         } else {
                             format!(" rowspan=\"{}\" colspan=\"{}\"", m.height(), m.width())
@@ -842,6 +884,9 @@ 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>");
         }
@@ -849,12 +894,15 @@ 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.
-        let (left, top) = used.map_or((0.0, 0.0), |r| (sh.col_left(r.start.col), sh.row_top(r.start.row)));
+        // 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 place = |a: &gridcraft_model::Anchor| {
             format!(
                 "position:absolute;left:{}px;top:{}px;width:{}px;height:{}px",
-                sh.col_left(a.cell.col) - left + f64::from(a.dx),
-                sh.row_top(a.cell.row) - top + f64::from(a.dy),
+                ci.start(a.cell.col) - left + f64::from(a.dx),
+                ri.start(a.cell.row) - top + f64::from(a.dy),
                 a.width.max(0.0),
                 a.height.max(0.0)
             )
@@ -868,15 +916,24 @@ 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

@@ -810,3 +810,57 @@ fn reading_a_fifo_is_refused_without_blocking() {
     assert!(err.contains("only regular files"), "{err}");
     let _ = std::fs::remove_dir_all(&dir);
 }
+
+/// 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/engine/src/lib.rs

@@ -237,22 +237,6 @@ const JOURNAL_MAX_ENTRIES: usize = 10_000;
 pub(crate) const JOURNAL_MAX_BYTES: usize = 64 * 1024 * 1024;
 const UNDO_BYTES_LIMIT: usize = 128 * 1024 * 1024;
 
-/// Comment and hyperlink text of a sheet: a changed sheet's snapshot keeps its own copy of these
-/// strings (an edit deep-copies them), so they count against the history budget with the cells.
-fn sheet_text_bytes(sheet: &gridcraft_model::Sheet) -> usize {
-    let comments = sheet.comments.values().fold(0usize, |sum, c| {
-        // The vectors' own storage counts too: an empty reply still takes an element.
-        let replies = c.replies.iter().fold(0usize, |n, (a, t)| n.saturating_add(a.len()).saturating_add(t.len()));
-        let replies = replies.saturating_add(c.replies.capacity().saturating_mul(std::mem::size_of::<(String, String)>()));
-        let dates = c.dates.iter().fold(0usize, |n, d| n.saturating_add(d.len()));
-        let dates = dates.saturating_add(c.dates.capacity().saturating_mul(std::mem::size_of::<String>()));
-        sum.saturating_add(std::mem::size_of::<gridcraft_model::Comment>() + c.author.len() + c.text.len() + replies + dates)
-    });
-    sheet.hyperlinks.values().fold(comments, |sum, h| {
-        sum.saturating_add(std::mem::size_of::<gridcraft_model::Hyperlink>() + h.target.len() + h.tooltip.as_ref().map_or(0, String::len))
-    })
-}
-
 fn history_retained_bytes(older: &Workbook, newer: &Workbook) -> usize {
     let mut bytes = std::mem::size_of::<Workbook>();
     for (index, sheet) in older.sheets.iter().enumerate() {
@@ -264,7 +248,6 @@ fn history_retained_bytes(older: &Workbook, newer: &Workbook) -> usize {
         let empty = gridcraft_model::CellStore::new();
         let next = newer.sheets.get(index).map_or(&empty, |next| &next.cells);
         bytes = bytes.saturating_add(sheet.cells.retained_bytes_against(next));
-        bytes = bytes.saturating_add(sheet_text_bytes(sheet));
     }
     // Snapshots share the macro list until a change to it; a snapshot with its own list keeps it.
     if !older.macros.shares(&newer.macros) {

crates/engine/src/tests.rs

@@ -6526,26 +6526,3 @@ fn pivot_new_sheet_destination_respects_workbook_structure_protection() {
     }
     assert!(s.execute("insert.pivotTable", json!({"source": "A1:B3", "location": "New"})).is_err());
 }
-
-#[test]
-fn history_charges_a_changed_sheets_comment_text() {
-    let mut s = s();
-    s.execute("review.newNote", json!({"cell": "A1", "text": "n".repeat(30_000), "author": "Example"})).unwrap();
-    let older = (*s.doc().unwrap().wb).clone();
-    s.execute("cell.set", json!({"cell": "B2", "input": "x"})).unwrap();
-    let newer = (*s.doc().unwrap().wb).clone();
-    // The older snapshot owns the comment text now that the sheet changed under it.
-    assert!(crate::history_retained_bytes(&older, &newer) >= 30_000);
-}
-
-#[test]
-fn history_charges_the_storage_of_empty_comment_replies() {
-    let mut s = s();
-    s.execute("review.newComment", json!({"cell": "A1", "text": "c", "author": "Ann"})).unwrap();
-    for _ in 0..500 {
-        s.execute("review.replyComment", json!({"cell": "A1", "text": "", "author": ""})).unwrap();
-    }
-    let sheet = s.doc().unwrap().wb.sheet(0).unwrap().clone();
-    // 500 replies of no text are still 500 elements.
-    assert!(crate::sheet_text_bytes(&sheet) >= 500 * std::mem::size_of::<(String, String)>());
-}