functions: TEXTJOIN builds its result piece by piece within the text cap

TEXTJOIN converted every input and delimiter into an owned String before
joining, so many references to one long shared text copied gigabytes before
the joined length was ever checked. Errors are now found first without
building text (so they still win in argument order), then each piece and
delimiter is converted only as it is appended, stopping at the cap.

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

@@ -228,82 +228,6 @@ 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));
@@ -313,18 +237,17 @@ 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 = 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 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 cells: Vec<CellRef> = if block.count() <= DENSE_BLOCK {
-        block.iter().filter(|c| !covered.covers(*c)).collect()
+        block.iter().filter(|c| !covered(*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.covers(*c));
+        set.retain(|c| !covered(*c));
         set
     };
     pg.save();
@@ -354,14 +277,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()
-                || by_start.contains_key(c)
+                || merges.iter().any(|m| m.start == *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 by_start.get(&c) {
+        match merges.iter().find(|m| m.start == c) {
             Some(m) => {
                 let (x, y, w, h) = b.rect(*m);
                 (x, y, w, h, true)
@@ -399,7 +322,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 by_start.get(c).filter(|_| merged) {
+        let (right, bottom) = match merges.iter().find(|m| m.start == *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,
@@ -484,12 +407,11 @@ 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 = by_start.get(cell).copied().unwrap_or(RangeRef::cell(*cell));
+        let cell_range = b.sh.merges.iter().find(|m| m.start == *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 {
@@ -581,44 +503,3 @@ 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);
-    }
-}

crates/functions/src/text.rs

@@ -53,25 +53,41 @@ 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> {
-    let delims: Vec<String> = as_array(&arg(a, 0)?.value).iter().map(|v| v.to_text()).collect::<R<_>>()?;
+    // 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 ignore = boolean(a, 1)?;
-    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 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 out = String::new();
-    for (i, s) in items.iter().enumerate() {
-        if i > 0 && !delims.is_empty() {
-            push_capped(&mut out, &delims[(i - 1) % delims.len()])?;
+    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;
         }
-        push_capped(&mut out, s)?;
+        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;
     }
     check_len(out)
 }
@@ -1131,6 +1147,22 @@ 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()])
     }