PDF export: index merged areas when drawing a block

draw_block checked every cell against every merge meeting the block,
and the fill, border and text passes searched the merge list again
for each merge start, so an imported sheet with many merge ranges in
a print area cost cells x merges (and merges x merges) comparisons.

The merges meeting a block are now gathered once and swept down the
rows: whether a cell is covered is a BTreeMap lookup among the merges
active on its row, and merge starts are found through a HashMap. A
merge overlapping one kept before it (only possible in a damaged file)
is left out, as Excel does when it repairs the file. Hyperlink
rectangles use the same index instead of scanning all sheet merges.

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/draw.rs

@@ -228,6 +228,82 @@ fn draw_border(pg: &mut Page, b: &BorderLine, wb: &Workbook, start: Point, end:
     pg.stroke_line_dashed(Point::new(x0, y0), Point::new(x1, y1), lw, color, &border_dash(b.style, k));
 }
 
+/// Merged areas active at one row of a downward sweep, kept disjoint: by first column, their last
+/// column and last row. Adding, dropping and looking up a merge costs log(active merges).
+#[derive(Default)]
+struct MergeSweep {
+    cols: std::collections::BTreeMap<u32, (u32, u32)>,
+    /// (last row, first column) of the active merges, soonest ending first.
+    ends: std::collections::BinaryHeap<std::cmp::Reverse<(u32, u32)>>,
+}
+
+impl MergeSweep {
+    /// Moves down to `row` (rows never decrease), dropping the merges that end above it.
+    fn advance(&mut self, row: u32) {
+        while let Some(std::cmp::Reverse((end, col))) = self.ends.peek().copied() {
+            if end >= row {
+                break;
+            }
+            self.ends.pop();
+            self.cols.remove(&col);
+        }
+    }
+
+    /// Does an active merge meet columns `c0..=c1`? The intervals are disjoint, so only the last
+    /// one starting at or before `c1` can.
+    fn meets(&self, c0: u32, c1: u32) -> bool {
+        self.cols.range(..=c1).next_back().is_some_and(|(_, (end, _))| *end >= c0)
+    }
+
+    /// Adds merge `m`, at row `row`, unless it overlaps an active one.
+    fn add(&mut self, m: RangeRef, row: u32) -> bool {
+        self.advance(row);
+        if self.meets(m.start.col, m.end.col) {
+            return false;
+        }
+        self.cols.insert(m.start.col, (m.end.col, m.end.row));
+        self.ends.push(std::cmp::Reverse((m.end.row, m.start.col)));
+        true
+    }
+}
+
+/// The merged areas that meet `block`, ordered by the row where they enter it, then by column,
+/// leaving out any that overlaps one kept before it (only a damaged file has overlapping merges;
+/// Excel drops them when it repairs one). One sweep down the rows instead of a scan of every
+/// merge per cell.
+fn block_merges(sh: &Sheet, block: RangeRef) -> Vec<RangeRef> {
+    let top = |m: &RangeRef| m.start.row.max(block.start.row);
+    let mut merges: Vec<RangeRef> = sh.merges.iter().filter(|m| m.intersects(&block)).copied().collect();
+    merges.sort_by_key(|m| (top(m), m.start.col));
+    let mut sweep = MergeSweep::default();
+    merges.retain(|m| sweep.add(*m, top(m)));
+    merges
+}
+
+/// Answers "is this cell inside a merge?" for cells asked in row-major order, from the merges of
+/// [`block_merges`].
+struct Covered<'a> {
+    merges: &'a [RangeRef],
+    top: u32,
+    next: usize,
+    sweep: MergeSweep,
+}
+
+impl<'a> Covered<'a> {
+    fn new(merges: &'a [RangeRef], block: RangeRef) -> Self {
+        Self { merges, top: block.start.row, next: 0, sweep: MergeSweep::default() }
+    }
+
+    fn covers(&mut self, c: CellRef) -> bool {
+        while let Some(m) = self.merges.get(self.next).filter(|m| m.start.row.max(self.top) <= c.row) {
+            self.sweep.add(*m, m.start.row.max(self.top));
+            self.next += 1;
+        }
+        self.sweep.advance(c.row);
+        self.sweep.meets(c.col, c.col)
+    }
+}
+
 /// Draws the cells of a block: fills, gridlines, data bars, borders and text.
 pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Option<crate::cf::CfCache>) {
     let (bx, by) = (b.xs.first().copied().unwrap_or(0.0), b.ys.first().copied().unwrap_or(0.0));
@@ -237,17 +313,18 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
     }
     let block = b.range();
     let sh = b.sh;
-    let merges: Vec<RangeRef> = sh.merges.iter().filter(|m| m.intersects(&block)).copied().collect();
-    let covered = |c: CellRef| merges.iter().any(|m| m.contains(c));
-    // Cells worth visiting.
+    let merges = block_merges(sh, block);
+    let by_start: std::collections::HashMap<CellRef, RangeRef> = merges.iter().map(|m| (m.start, *m)).collect();
+    // Cells worth visiting, in row-major order (which `Covered` needs).
+    let mut covered = Covered::new(&merges, block);
     let cells: Vec<CellRef> = if block.count() <= DENSE_BLOCK {
-        block.iter().filter(|c| !covered(*c)).collect()
+        block.iter().filter(|c| !covered.covers(*c)).collect()
     } else {
         let mut set: Vec<CellRef> = sh.cells.iter_range(block).map(|(c, _)| c).collect();
         set.extend(sh.spill.range(block.start..=block.end).map(|(c, _)| *c).filter(|c| block.contains(*c)));
         set.sort_unstable();
         set.dedup();
-        set.retain(|c| !covered(*c));
+        set.retain(|c| !covered.covers(*c));
         set
     };
     pg.save();
@@ -277,14 +354,14 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
         .filter(|(c, l)| {
             l.fill.is_some()
                 || l.cf.is_some()
-                || merges.iter().any(|m| m.start == *c)
+                || by_start.contains_key(c)
                 || !sh.value(*c).is_empty()
                 || l.style.borders != Borders::default()
                 || l.style.num_fmt.as_str() == "checkbox"
         })
         .collect();
     let rect_of = |c: CellRef| -> (f32, f32, f32, f32, bool) {
-        match merges.iter().find(|m| m.start == c) {
+        match by_start.get(&c) {
             Some(m) => {
                 let (x, y, w, h) = b.rect(*m);
                 (x, y, w, h, true)
@@ -322,7 +399,7 @@ pub(super) fn draw_block(pg: &mut Page, b: &Block, gridlines: bool, cf: &mut Opt
             continue;
         }
         let bd = &l.style.borders;
-        let (right, bottom) = match merges.iter().find(|m| m.start == *c).filter(|_| merged) {
+        let (right, bottom) = match by_start.get(c).filter(|_| merged) {
             Some(m) => (
                 b.wb.styles.get(sh.style_id(CellRef::new(m.start.row, m.end.col))).borders.right,
                 b.wb.styles.get(sh.style_id(CellRef::new(m.end.row, m.start.col))).borders.bottom,
@@ -407,11 +484,12 @@ pub(super) struct PrintedBlock {
 pub(super) fn draw_block_links(pg: &mut Page, b: &Block, page: usize, pending: &mut Vec<PendingPdfLink>) {
     let range = b.range();
     let (Some(&bx), Some(&by), Some(&right), Some(&bottom)) = (b.xs.first(), b.ys.first(), b.xs.last(), b.ys.last()) else { return };
+    let by_start: std::collections::HashMap<CellRef, RangeRef> = block_merges(b.sh, range).into_iter().map(|m| (m.start, m)).collect();
     for (cell, link) in b.sh.hyperlinks.range(range.start..=range.end) {
         if !range.contains(*cell) {
             continue;
         }
-        let cell_range = b.sh.merges.iter().find(|m| m.start == *cell).copied().unwrap_or(RangeRef::cell(*cell));
+        let cell_range = by_start.get(cell).copied().unwrap_or(RangeRef::cell(*cell));
         let (x, y, w, h) = b.rect(cell_range);
         let (x0, y0, x1, y1) = (x.max(bx), y.max(by), (x + w).min(right), (y + h).min(bottom));
         if x1 <= x0 || y1 <= y0 {
@@ -503,3 +581,44 @@ pub(super) fn make_block<'a>(
     }
     Block { wb, si, sh, rows, cols, xs, ys, k, scale: lay.scale }
 }
+
+#[cfg(test)]
+mod merge_tests {
+    use super::{CellRef, Covered, RangeRef, Sheet, block_merges};
+
+    fn r(a: &str) -> RangeRef {
+        RangeRef::parse(a).unwrap()
+    }
+
+    #[test]
+    fn block_merges_drop_overlaps_and_cover_like_a_scan() {
+        let mut sh = Sheet::new("S");
+        sh.merges = vec![r("B2:C3"), r("E1:F8"), r("B2:B5"), r("A10:D10"), r("H3:H4"), r("Z1:Z2"), r("C3:D4"), r("A1:A1048576")];
+        let block = r("B1:H12");
+        let merges = block_merges(&sh, block);
+        // B2:B5 and C3:D4 overlap B2:C3, which comes first; Z1:Z2 is outside the block.
+        assert_eq!(merges, vec![r("E1:F8"), r("B2:C3"), r("H3:H4"), r("A10:D10")]);
+        let mut covered = Covered::new(&merges, block);
+        for c in block.iter() {
+            assert_eq!(covered.covers(c), merges.iter().any(|m| m.contains(c)), "{}", c.a1());
+        }
+        // Cells asked sparsely, still in order.
+        let mut covered = Covered::new(&merges, block);
+        for (a, want) in [("C1", false), ("F5", true), ("G5", false), ("D10", true), ("H12", false)] {
+            assert_eq!(covered.covers(CellRef::parse(a).unwrap()), want, "{a}");
+        }
+    }
+
+    #[test]
+    fn many_stacked_merges_are_swept_once() {
+        // 50,000 merges over the same cells: one is kept, and the block is checked against it
+        // without comparing every cell with every merge.
+        let mut sh = Sheet::new("S");
+        sh.merges = (0..50_000u32).map(|i| RangeRef::new(CellRef::new(0, 0), CellRef::new(199, 1 + i % 50))).collect();
+        let block = r("A1:AZ200");
+        let merges = block_merges(&sh, block);
+        assert_eq!(merges, vec![r("A1:B200")]);
+        let mut covered = Covered::new(&merges, block);
+        assert_eq!(block.iter().filter(|c| covered.covers(*c)).count(), 400);
+    }
+}