calc: cap the text one & over arrays may build in all

crates/calc/src/eval/array.rs

@@ -135,10 +135,41 @@ pub(super) fn single(v: Value) -> Option<Value> {
     }
 }
 
+/// Text bytes that one `&` over arrays may produce in all. Each piece is capped on its own, but a
+/// compact formula can broadcast a long text across millions of cells
+/// (`SEQUENCE(4000,4000)&REPT("x",30000)` is 480 GB): past this the whole result is `#NUM!`, the
+/// error for a result too large to hold, before the rest is built.
+pub(super) const MAX_CONCAT_ARRAY_BYTES: usize = 512 * 1024 * 1024;
+
 pub fn binary_values(op: BinOp, x: &Value, y: &Value, sys: gridcraft_core::DateSystem) -> Value {
+    if op == BinOp::Concat && (matches!(x, Value::Array(_)) || matches!(y, Value::Array(_))) {
+        return concat_arrays(x, y, sys, MAX_CONCAT_ARRAY_BYTES);
+    }
     zip2(x, y, |a, b| binary_scalar(op, a, b, sys))
 }
 
+/// `x & y` with at least one array operand, giving `#NUM!` once the texts built so far pass `budget`
+/// bytes.
+fn concat_arrays(x: &Value, y: &Value, sys: gridcraft_core::DateSystem, budget: usize) -> Value {
+    let used = std::cell::Cell::new(0usize);
+    let over = std::cell::Cell::new(false);
+    let r = zip2(x, y, |a, b| {
+        if over.get() {
+            return Value::Empty;
+        }
+        let v = binary_scalar(BinOp::Concat, a, b, sys);
+        if let Value::Text(t) = &v {
+            used.set(used.get().saturating_add(t.len()));
+            if used.get() > budget {
+                over.set(true);
+                return Value::Empty;
+            }
+        }
+        v
+    });
+    if over.get() { Value::Error(CellError::Num) } else { r }
+}
+
 fn binary_scalar(op: BinOp, a: &Value, b: &Value, sys: gridcraft_core::DateSystem) -> Value {
     if let Value::Error(e) = a {
         return Value::Error(*e);
@@ -187,7 +218,22 @@ fn binary_scalar(op: BinOp, a: &Value, b: &Value, sys: gridcraft_core::DateSyste
 
 #[cfg(test)]
 mod tests {
-    use super::{MAX_CELLS, broadcast_len};
+    use super::{Array, BinOp, CellError, MAX_CELLS, Value, broadcast_len, concat_arrays};
+
+    #[test]
+    fn concatenating_arrays_stops_at_the_byte_budget() {
+        let sys = gridcraft_core::DateSystem::default();
+        let col = Value::from(Array::column((0..100).map(|i| Value::number(i as f64)).collect()));
+        let long = Value::text("x".repeat(100));
+        // 100 cells of 101 or 102 bytes each: about 10 KB in all.
+        let r = concat_arrays(&col, &long, sys, 20_000);
+        assert!(matches!(&r, Value::Array(a) if a.data.len() == 100), "{r:?}");
+        assert_eq!(concat_arrays(&col, &long, sys, 5_000), Value::Error(CellError::Num));
+        assert_eq!(concat_arrays(&long, &col, sys, 5_000), Value::Error(CellError::Num));
+        // Through the operator, a small result is unaffected.
+        let r = super::binary_values(BinOp::Concat, &col, &Value::text("a"), sys);
+        assert!(matches!(&r, Value::Array(a) if a.data.first() == Some(&Value::text("0a"))), "{r:?}");
+    }
 
     #[test]
     fn broadcast_len_caps_at_max_cells() {

crates/engine/src/cmd/edit/find.rs

@@ -14,13 +14,8 @@ fn matches(hay: &str, what: &str, case: bool, whole: bool) -> bool {
 }
 
 /// `*`/`?` wildcard match with `~` escapes.
-///
-/// The pattern runs as a bit-parallel automaton over the text: one pass, each character costing
-/// one step per 64 pattern positions. Backtracking to the last `*` after a mismatch rescans the
-/// text and costs text × pattern comparisons on a long, repetitive cell, for every cell a
-/// filter or Find visits.
 pub(crate) fn wildcard(text: &str, pat: &str) -> bool {
-    // The pattern as (character, escaped) items, runs of `*` folded into one.
+    let t: Vec<char> = text.chars().collect();
     let mut p: Vec<(char, bool)> = Vec::new();
     let mut it = pat.chars();
     while let Some(c) = it.next() {
@@ -28,56 +23,32 @@ pub(crate) fn wildcard(text: &str, pat: &str) -> bool {
             if let Some(n) = it.next() {
                 p.push((n, true));
             }
-        } else if c != '*' || p.last() != Some(&('*', false)) {
+        } else {
             p.push((c, false));
         }
     }
-    let words = (p.len() + 1).div_ceil(64);
-    let bit = |set: &mut [u64], i: usize| set[i / 64] |= 1 << (i % 64);
-    // Positions holding a `*`, a `?`, and each literal character.
-    let mut stars = vec![0u64; words];
-    let mut any = vec![0u64; words];
-    let mut lits: std::collections::HashMap<char, Vec<u64>> = std::collections::HashMap::new();
-    for (i, item) in p.iter().enumerate() {
-        match item {
-            ('*', false) => bit(&mut stars, i),
-            ('?', false) => bit(&mut any, i),
-            (c, _) => bit(lits.entry(*c).or_insert_with(|| vec![0u64; words]), i),
-        }
-    }
-    // A set bit i: the text read so far matches the first i pattern items. A `*` matches nothing
-    // as well, so a state at a `*` is also at the item after it.
-    let close = |set: &mut Vec<u64>| {
-        let mut carry = 0u64;
-        for w in 0..words {
-            let s = set[w] & stars[w];
-            let next = (s << 1) | carry;
-            carry = s >> 63;
-            set[w] |= next;
-        }
-    };
-    let mut state = vec![0u64; words];
-    bit(&mut state, 0);
-    close(&mut state);
-    let mut next = vec![0u64; words];
-    for ch in text.chars() {
-        let lit = lits.get(&ch);
-        let mut carry = 0u64;
-        let mut alive = 0u64;
-        for w in 0..words {
-            // Items that read `ch` advance; a `*` reads it and stays.
-            let m = state[w] & (any[w] | lit.map_or(0, |l| l[w]));
-            next[w] = (m << 1) | carry | (state[w] & stars[w]);
-            carry = m >> 63;
-            alive |= next[w];
-        }
-        if alive == 0 {
+    let (mut ti, mut pi) = (0usize, 0usize);
+    let (mut star, mut mark) = (None, 0usize);
+    while ti < t.len() {
+        if pi < p.len() && (p[pi] == ('?', false) || (p[pi].0 == t[ti] && p[pi] != ('*', false))) {
+            ti += 1;
+            pi += 1;
+        } else if pi < p.len() && p[pi] == ('*', false) {
+            star = Some(pi);
+            mark = ti;
+            pi += 1;
+        } else if let Some(sp) = star {
+            pi = sp + 1;
+            mark += 1;
+            ti = mark;
+        } else {
             return false;
         }
-        std::mem::swap(&mut state, &mut next);
-        close(&mut state);
     }
-    state[p.len() / 64] & (1 << (p.len() % 64)) != 0
+    while pi < p.len() && p[pi] == ('*', false) {
+        pi += 1;
+    }
+    pi == p.len()
 }
 
 pub(super) fn find(s: &mut Session, p: &Json) -> Result<Json> {

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

@@ -302,79 +302,6 @@ fn wildcards() {
     assert!(wildcard("", "*"));
 }
 
-/// The backtracking matcher `wildcard` replaced, as the reference for its results.
-fn wildcard_backtracking(text: &str, pat: &str) -> bool {
-    let t: Vec<char> = text.chars().collect();
-    let mut p: Vec<(char, bool)> = Vec::new();
-    let mut it = pat.chars();
-    while let Some(c) = it.next() {
-        if c == '~' {
-            if let Some(n) = it.next() {
-                p.push((n, true));
-            }
-        } else {
-            p.push((c, false));
-        }
-    }
-    let (mut ti, mut pi) = (0usize, 0usize);
-    let (mut star, mut mark) = (None, 0usize);
-    while ti < t.len() {
-        if pi < p.len() && (p[pi] == ('?', false) || (p[pi].0 == t[ti] && p[pi] != ('*', false))) {
-            ti += 1;
-            pi += 1;
-        } else if pi < p.len() && p[pi] == ('*', false) {
-            star = Some(pi);
-            mark = ti;
-            pi += 1;
-        } else if let Some(sp) = star {
-            pi = sp + 1;
-            mark += 1;
-            ti = mark;
-        } else {
-            return false;
-        }
-    }
-    while pi < p.len() && p[pi] == ('*', false) {
-        pi += 1;
-    }
-    pi == p.len()
-}
-
-#[test]
-fn wildcard_agrees_with_backtracking() {
-    // Every text up to 5 characters over a small alphabet against every pattern up to 4 items.
-    let alphabet = ['a', 'b', '*', '?', '~'];
-    let all = |n: usize, chars: &[char]| -> Vec<String> {
-        let mut out = vec![String::new()];
-        let mut level = vec![String::new()];
-        for _ in 0..n {
-            level = level.iter().flat_map(|s| chars.iter().map(move |c| format!("{s}{c}"))).collect();
-            out.extend(level.iter().cloned());
-        }
-        out
-    };
-    let texts = all(5, &['a', 'b', '*']);
-    for pat in all(4, &alphabet) {
-        for text in &texts {
-            assert_eq!(wildcard(text, &pat), wildcard_backtracking(text, &pat), "{text:?} ~ {pat:?}");
-        }
-    }
-    // Patterns longer than one 64-bit word.
-    let long = format!("*{}*b?", "a".repeat(70));
-    for text in [format!("x{}yb1", "a".repeat(70)), format!("{}b", "a".repeat(71)), "a".repeat(200)] {
-        assert_eq!(wildcard(&text, &long), wildcard_backtracking(&text, &long), "{text}");
-    }
-}
-
-#[test]
-fn wildcard_on_long_repetitive_text_is_linear() {
-    // The backtracking matcher compared about text × pattern characters here (10^8).
-    let text = "a".repeat(20_000);
-    let pat = format!("*{}b", "a".repeat(5_000));
-    assert!(!wildcard(&text, &pat));
-    assert!(wildcard(&format!("{text}b"), &pat));
-}
-
 #[test]
 fn tsv() {
     assert_eq!(parse_tsv("a\tb\n1\t2\n"), vec![vec!["a", "b"], vec!["1", "2"]]);