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/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,78 +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 `*` and a `?`, and where each literal character sits in the pattern.
-    let mut stars = vec![0u64; words];
-    let mut any = vec![0u64; words];
-    let mut at: std::collections::HashMap<char, Vec<usize>> = std::collections::HashMap::new();
-    for (i, item) in p.iter().enumerate() {
-        match item {
-            ('*', false) => bit(&mut stars, i),
-            ('?', false) => bit(&mut any, i),
-            (c, _) => at.entry(*c).or_default().push(i),
-        }
-    }
-    // A literal's bit mask is built when the text first reads it, and kept for the first
-    // `MAX_CACHED_MASKS` literals: a long pattern of mostly distinct characters would otherwise
-    // allocate a mask of the pattern's width for each one up front. Past the cap the mask is
-    // rebuilt in `scratch` from the character's positions, which costs about one step of the scan.
-    const MAX_CACHED_MASKS: usize = 256;
-    let mut masks: std::collections::HashMap<char, Vec<u64>> = std::collections::HashMap::new();
-    let mut scratch = vec![0u64; words];
-    // 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: Option<&[u64]> = match at.get(&ch) {
-            None => None,
-            Some(positions) if masks.contains_key(&ch) || masks.len() < MAX_CACHED_MASKS => {
-                let mask = masks.entry(ch).or_insert_with(|| {
-                    let mut m = vec![0u64; words];
-                    positions.iter().for_each(|&i| bit(&mut m, i));
-                    m
-                });
-                Some(mask)
-            }
-            Some(positions) => {
-                scratch.fill(0);
-                positions.iter().for_each(|&i| bit(&mut scratch, i));
-                Some(&scratch)
-            }
-        };
-        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,91 +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_with_many_distinct_literals_agrees_with_backtracking() {
-    // 600 distinct characters in the pattern: more than the masks kept, so the rest are rebuilt.
-    let chars: Vec<char> = (0x4E00u32..0x4E00 + 600).filter_map(char::from_u32).collect();
-    let word: String = chars.iter().collect();
-    let pat = format!("*{word}?{}", chars[3]);
-    for text in [format!("x{word}yq{}", chars[3]), word.clone(), format!("{word}{word}"), chars.iter().rev().collect::<String>()] {
-        assert_eq!(wildcard(&text, &pat), wildcard_backtracking(&text, &pat), "{} chars", text.chars().count());
-    }
-    assert!(wildcard(&format!("{word}zz{}", chars[3]).replace("zz", "z"), &pat));
-}
-
-#[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"]]);

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()])
     }