Row auto-fit: sweep merges once per sheet instead of per row

auto_row_height() picked the merges touching a row by scanning every
merge on the sheet, and opening a workbook (fit_imported_rows) or a
commit fitting many rows called it per row, so rows x merges
comparisons ran synchronously on open.

Rows are fitted in ascending order, so a MergeSweep sorts the sheet's
merges by first row once and keeps only those active on the current
row. All comparisons count against MERGE_FIT_WORK (50,000,000) per
pass; past it the remaining rows keep the heights they have.
auto_row_height keeps its signature for single rows.

crates/engine/src/cmd.rs

@@ -440,8 +440,14 @@ pub(crate) fn commit<R>(d: &mut DocState, f: impl FnOnce(&mut Ctx) -> Result<R>)
     }
     fit_rows.sort_unstable();
     fit_rows.dedup();
+    let mut sweep: Option<(usize, MergeSweep)> = None;
     for (si, row) in fit_rows {
-        auto_row_height(&mut wb, si, row);
+        if sweep.as_ref().is_none_or(|(at, _)| *at != si) {
+            sweep = wb.sheet(si).map(|sh| (si, MergeSweep::new(sh)));
+        }
+        if let Some((_, sw)) = sweep.as_mut() {
+            fit_row_height(&mut wb, si, row, sw);
+        }
     }
     if let Some(t0) = t0 {
         eprintln!("commit: + rows {:?}", since(t0));
@@ -596,6 +602,65 @@ fn wrapped_line_count(line: &str, width: f32, size: f32, bold: bool) -> f32 {
 /// Line breaks in a cell's text count only when the cell wraps, as in Excel: with Wrap Text off
 /// a multi-line value shows on one line and AutoFit gives a one-line row.
 pub fn auto_row_height(wb: &mut Workbook, si: usize, row: u32) {
+    let Some(sh) = wb.sheet(si) else { return };
+    let mut sweep = MergeSweep::new(sh);
+    fit_row_height(wb, si, row, &mut sweep);
+}
+
+/// Most merge comparisons one auto-fit pass (a commit, or opening a workbook) makes. Past it the
+/// remaining rows keep the heights they have rather than stall on a sheet whose merges overlap
+/// the fitted rows many times over.
+const MERGE_FIT_WORK: usize = 50_000_000;
+
+/// The merged areas of one sheet that touch a row, for rows visited in ascending order: the
+/// merges are sorted by first row once and swept, so fitting many rows never rescans every merge
+/// per row. All comparisons count against [`MERGE_FIT_WORK`].
+pub(crate) struct MergeSweep {
+    by_start: Vec<gridcraft_core::RangeRef>,
+    next: usize,
+    active: Vec<gridcraft_core::RangeRef>,
+    budget: usize,
+}
+
+impl MergeSweep {
+    pub(crate) fn new(sh: &gridcraft_model::Sheet) -> Self {
+        let mut by_start: Vec<gridcraft_core::RangeRef> = sh.merges.iter().copied().filter(|m| !m.is_single()).collect();
+        by_start.sort_unstable_by_key(|m| m.start.row);
+        let budget = MERGE_FIT_WORK.saturating_sub(by_start.len());
+        Self { by_start, next: 0, active: Vec::new(), budget }
+    }
+
+    /// Takes `n` comparisons from the budget; `false` once it is spent.
+    fn charge(&mut self, n: usize) -> bool {
+        match self.budget.checked_sub(n) {
+            Some(rest) => {
+                self.budget = rest;
+                true
+            }
+            None => {
+                self.budget = 0;
+                false
+            }
+        }
+    }
+
+    /// The merges covering `row`, or `None` when the budget is spent. Rows must not decrease
+    /// between calls (skipping rows is fine).
+    fn at(&mut self, row: u32) -> Option<Vec<gridcraft_core::RangeRef>> {
+        while let Some(m) = self.by_start.get(self.next).filter(|m| m.start.row <= row) {
+            self.active.push(*m);
+            self.next += 1;
+        }
+        if !self.charge(self.active.len()) {
+            return None;
+        }
+        self.active.retain(|m| m.end.row >= row);
+        Some(self.active.clone())
+    }
+}
+
+/// [`auto_row_height`] with the sheet's merges taken from `sweep`.
+pub(crate) fn fit_row_height(wb: &mut Workbook, si: usize, row: u32, sweep: &mut MergeSweep) {
     let Some(sh) = wb.sheet(si) else { return };
     if sh.rows.get(&row).is_some_and(|i| i.custom) {
         return;
@@ -625,9 +690,14 @@ pub fn auto_row_height(wb: &mut Workbook, si: usize, row: u32) {
     // picked out once, and per cell the candidates are re-checked (normally none or a couple;
     // a sheet with many merges and many saved columns would otherwise scan all of them per
     // cell, rows × merges × columns).
-    let row_merges: Vec<gridcraft_core::RangeRef> =
-        sh.merges.iter().copied().filter(|m| !m.is_single() && m.start.row <= row && row <= m.end.row).collect();
+    // Rows are fitted in ascending order, so the merges touching this one come from a sweep over
+    // the sheet's merges sorted once, not from a scan of all of them. Out of budget: the row keeps
+    // the height it has.
+    let Some(row_merges) = sweep.at(row) else { return };
     for (c, cell) in sh.cells.row(row, 0, gridcraft_core::MAX_COLS - 1) {
+        if !sweep.charge(row_merges.len()) {
+            return;
+        }
         // Merged cells never auto-fit their rows, like Excel (column autofit skips them too).
         if row_merges.iter().any(|m| m.contains(CellRef::new(row, c))) {
             continue;

crates/engine/src/io.rs

@@ -93,9 +93,11 @@ fn fit_imported_rows(wb: &mut Workbook) {
         let mut rows: Vec<u32> = sh.cells.iter().map(|(c, _)| c.row).collect();
         rows.sort_unstable();
         rows.dedup();
+        // One sweep over the sheet's merges for all of its rows, in ascending order.
+        let mut sweep = crate::cmd::MergeSweep::new(sh);
         for row in rows {
             let before = wb.sheet(si).and_then(|sh| sh.rows.get(&row)).and_then(|i| i.size);
-            crate::cmd::auto_row_height(wb, si, row);
+            crate::cmd::fit_row_height(wb, si, row, &mut sweep);
             let Some(before) = before else { continue };
             let after = wb.sheet(si).and_then(|sh| sh.rows.get(&row)).and_then(|i| i.size);
             if after.is_none_or(|a| before > a + 0.5)

crates/engine/tests/it/row_autofit.rs

@@ -59,3 +59,31 @@ fn whole_row_format_keeps_hidden_rows_hidden() {
     assert!(info.size.unwrap_or(before) > before + 10.0, "hidden row still grows to its font: before={before}, size={:?}", info.size);
     assert!(info.hidden, "formatting a hidden row must not unhide it");
 }
+
+#[test]
+fn many_merges_fit_rows_the_same_and_skip_merged_cells() {
+    // Rows are fitted with one sweep over the sheet's merges; a merged cell still never grows
+    // its row, and rows next to thousands of merges still fit.
+    let mut s = gridcraft_engine::Session::new();
+    s.new_workbook();
+    let values: Vec<_> = (0..2_000).map(|i| json!([format!("v{i}")])).collect();
+    s.execute("range.setValues", json!({"range": "A1", "values": values})).unwrap();
+    {
+        let sh = sheet_mut(&mut s);
+        sh.merges.push(gridcraft_engine::core::RangeRef::parse("A3:B4").unwrap());
+        for i in 0..20_000u32 {
+            let row = 4 + i % 1_990;
+            sh.merges.push(gridcraft_engine::core::RangeRef::new(
+                gridcraft_engine::core::CellRef::new(row, 3 + (i % 7) * 2),
+                gridcraft_engine::core::CellRef::new(row + 3, 4 + (i % 7) * 2),
+            ));
+        }
+    }
+    s.execute("home.fontSize", json!({"range": "A:A", "size": 20})).unwrap();
+    let sh = s.doc().unwrap().wb.active().unwrap();
+    let default = sh.default_row_height;
+    assert!(sh.row_height(0) > 30.0 && sh.row_height(1_999) > 30.0, "rows with big text grow");
+    assert_eq!(sh.row_height(2), default, "a merged cell does not grow its row");
+    assert_eq!(sh.row_height(3), default, "nor any row of the merge");
+    assert!(sh.row_height(4) > 30.0 && sh.row_height(1_000) > 30.0, "rows beside other merges grow");
+}

crates/functions/src/text.rs

@@ -53,41 +53,25 @@ fn concat(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
     check_len(out)
 }
 
-/// The error `v.to_text()` would give, found without building any text.
-fn text_error(v: &Value) -> Option<CellError> {
-    match v {
-        Value::Error(e) => Some(*e),
-        Value::Array(a) => a.data.first().and_then(text_error),
-        _ => None,
-    }
-}
-
 fn textjoin(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
-    // Errors are found first, in argument order, so they win as before; text is then built one
-    // piece at a time into the capped output, so many references to one long text (or a long
-    // delimiter list) stop at the cap instead of first copying every piece.
-    let delims = as_array(&arg(a, 0)?.value);
-    if let Some(e) = delims.iter().find_map(text_error) {
-        return Err(e);
-    }
+    let delims: Vec<String> = as_array(&arg(a, 0)?.value).iter().map(|v| v.to_text()).collect::<R<_>>()?;
     let ignore = boolean(a, 1)?;
-    let items: Vec<_> = a.iter().skip(2).map(|x| as_array(&x.value)).collect();
-    if let Some(e) = items.iter().flat_map(|x| x.iter()).find_map(text_error) {
-        return Err(e);
+    let mut items = Vec::new();
+    for x in a.iter().skip(2) {
+        for v in as_array(&x.value).iter() {
+            let s = v.to_text()?;
+            if ignore && s.is_empty() {
+                continue;
+            }
+            items.push(s);
+        }
     }
     let mut out = String::new();
-    let mut joined = 0usize;
-    for v in items.iter().flat_map(|x| x.iter()) {
-        let s = v.to_text()?;
-        if ignore && s.is_empty() {
-            continue;
+    for (i, s) in items.iter().enumerate() {
+        if i > 0 && !delims.is_empty() {
+            push_capped(&mut out, &delims[(i - 1) % delims.len()])?;
         }
-        if joined > 0 && !delims.data.is_empty() {
-            let d = delims.data.get((joined - 1) % delims.data.len()).map(Value::to_text).transpose()?.unwrap_or_default();
-            push_capped(&mut out, &d)?;
-        }
-        push_capped(&mut out, &s)?;
-        joined += 1;
+        push_capped(&mut out, s)?;
     }
     check_len(out)
 }
@@ -1147,22 +1131,6 @@ mod tests {
         assert_eq!(rows_of(&ev("CONCATENATE", vec![av(row_t(&["a", "b"])), t("x")])), vec![vec![tv("ax"), tv("bx")]]);
     }
 
-    /// Security: TEXTJOIN builds its result piece by piece and stops at the text cap, rather
-    /// than first copying every input (100,000 references to one 32,767-character text were
-    /// 3 GB of copies). Errors among the inputs still win, in argument order.
-    #[test]
-    fn textjoin_stops_at_the_text_cap() {
-        use gridcraft_core::Array;
-        let long = tv(&"x".repeat(32_767));
-        let many = || av(Array::filled(100_000, 1, long.clone()).into());
-        is_err(ev("TEXTJOIN", vec![t(","), b(true), many()]), CellError::Value);
-        is_err(ev("TEXTJOIN", vec![av(Array::filled(1, 100_000, long.clone()).into()), b(false), t("a"), t("b")]), CellError::Value);
-        is_err(ev("TEXTJOIN", vec![t(","), b(true), many(), e(CellError::Div0)]), CellError::Div0);
-        is_err(ev("TEXTJOIN", vec![av(arr(vec![vec![tv(","), Value::Error(CellError::NA)]])), b(true), t("a")]), CellError::NA);
-        // Delimiters cycle and are converted only where used.
-        is_text(ev("TEXTJOIN", vec![av(arr(vec![vec![nv(1.0), tv(";")]])), b(false), t("a"), t("b"), t("c"), t("d")]), "a1b;c1d");
-    }
-
     fn row_t(xs: &[&str]) -> Value {
         arr(vec![xs.iter().map(|x| tv(x)).collect()])
     }