functions: match TEXTSPLIT/TEXTBEFORE/TEXTAFTER delimiters through an index, within a work limit

The delimiter matcher compared every delimiter, duplicates included, at
every position of the text. Delimiters are now deduplicated and grouped
by the character a match is anchored on, and a search that would
compare more than 100 million characters returns #VALUE!.

crates/functions/src/text.rs

@@ -1,5 +1,7 @@
 //! Text functions.
 
+use std::collections::HashMap;
+
 use gridcraft_core::parse::parse_number_text_in;
 use gridcraft_core::{CellError, Value, number_to_text};
 
@@ -541,23 +543,52 @@ fn delimiters(v: &Value) -> R<Vec<Vec<char>>> {
     as_array(v).iter().map(|d| d.to_text().map(|s| chars(&s))).collect()
 }
 
+/// Most delimiter characters compared in one search: text length × delimiters is the formula's
+/// to choose, so the search gives up with `#VALUE!` rather than run on.
+const MAX_MATCH_WORK: u64 = 100_000_000;
+
 /// Non-overlapping delimiter matches (start, end) in char positions, in ascending order. Scans left
 /// to right preferring the longest delimiter starting at each position, or (`from_end`) right to
 /// left preferring the longest delimiter ending at each position. Empty delimiters are ignored unless all
-/// delimiters are empty, in which case every position matches with zero length.
-fn find_matches(text: &[char], delims: &[Vec<char>], insensitive: bool, from_end: bool) -> Vec<(usize, usize)> {
+/// delimiters are empty, in which case every position matches with zero length. Repeated
+/// delimiters are tried once, and only those whose first (or, from the end, last) character is the
+/// one at hand; a search past [`MAX_MATCH_WORK`] is `#VALUE!`.
+fn find_matches(text: &[char], delims: &[Vec<char>], insensitive: bool, from_end: bool) -> R<Vec<(usize, usize)>> {
     let t = if insensitive { fold(text) } else { text.to_vec() };
-    let ds: Vec<Vec<char>> = delims.iter().filter(|d| !d.is_empty()).map(|d| if insensitive { fold(d) } else { d.clone() }).collect();
+    let mut ds: Vec<Vec<char>> = delims.iter().filter(|d| !d.is_empty()).map(|d| if insensitive { fold(d) } else { d.clone() }).collect();
     if ds.is_empty() {
-        return (0..=t.len()).map(|i| (i, i)).collect();
+        return Ok((0..=t.len()).map(|i| (i, i)).collect());
     }
+    ds.sort_unstable();
+    ds.dedup();
+    // Delimiters by the character a match is anchored on.
+    let mut by_char: HashMap<char, Vec<&[char]>> = HashMap::new();
+    for d in &ds {
+        let anchor = if from_end { d.last() } else { d.first() };
+        if let Some(&c) = anchor {
+            by_char.entry(c).or_default().push(d);
+        }
+    }
+    let mut work = 0u64;
+    let mut longest = |candidates: Option<&Vec<&[char]>>, fits: &dyn Fn(&[char]) -> bool| -> R<Option<usize>> {
+        let mut best = None;
+        for d in candidates.into_iter().flatten() {
+            work = work.saturating_add(d.len() as u64);
+            if work > MAX_MATCH_WORK {
+                return Err(CellError::Value);
+            }
+            if fits(d) {
+                best = best.max(Some(d.len()));
+            }
+        }
+        Ok(best)
+    };
     let mut out = Vec::new();
     if from_end {
         let mut j = t.len();
         while j > 0 {
-            let best =
-                ds.iter().filter(|d| j.checked_sub(d.len()).and_then(|st| t.get(st..j)).is_some_and(|w| w == d.as_slice())).map(Vec::len).max();
-            match best {
+            let at = t.get(j - 1).and_then(|c| by_char.get(c));
+            match longest(at, &|d| j.checked_sub(d.len()).and_then(|st| t.get(st..j)).is_some_and(|w| w == d))? {
                 Some(l) => {
                     out.push((j - l, j));
                     j -= l;
@@ -566,12 +597,12 @@ fn find_matches(text: &[char], delims: &[Vec<char>], insensitive: bool, from_end
             }
         }
         out.reverse();
-        return out;
+        return Ok(out);
     }
     let mut i = 0;
     while i < t.len() {
-        let best = ds.iter().filter(|d| t.get(i..i + d.len()).is_some_and(|w| w == d.as_slice())).map(Vec::len).max();
-        match best {
+        let at = t.get(i).and_then(|c| by_char.get(c));
+        match longest(at, &|d| t.get(i..i + d.len()).is_some_and(|w| w == d))? {
             Some(l) => {
                 out.push((i, i + l));
                 i += l;
@@ -579,7 +610,7 @@ fn find_matches(text: &[char], delims: &[Vec<char>], insensitive: bool, from_end
             None => i += 1,
         }
     }
-    out
+    Ok(out)
 }
 
 fn text_before_after(a: &[Arg], before: bool) -> R<Value> {
@@ -591,7 +622,7 @@ fn text_before_after(a: &[Arg], before: bool) -> R<Value> {
     if !(0..=1).contains(&mode) || inst == 0 || inst.unsigned_abs() as usize > s.len().max(1) {
         return Err(CellError::Value);
     }
-    let mut m = find_matches(&s, &delims, mode == 1, inst < 0);
+    let mut m = find_matches(&s, &delims, mode == 1, inst < 0)?;
     if match_end {
         if inst > 0 {
             if m.last().is_none_or(|x| x.0 != s.len()) {
@@ -620,18 +651,18 @@ fn textafter(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
     text_before_after(a, false)
 }
 
-fn split_by(s: &[char], delims: &[Vec<char>], insensitive: bool) -> Vec<Vec<char>> {
+fn split_by(s: &[char], delims: &[Vec<char>], insensitive: bool) -> R<Vec<Vec<char>>> {
     if delims.iter().all(Vec::is_empty) {
-        return vec![s.to_vec()];
+        return Ok(vec![s.to_vec()]);
     }
     let mut out = Vec::new();
     let mut last = 0;
-    for (st, en) in find_matches(s, delims, insensitive, false) {
+    for (st, en) in find_matches(s, delims, insensitive, false)? {
         out.push(s[last..st].to_vec());
         last = en;
     }
     out.push(s[last..].to_vec());
-    out
+    Ok(out)
 }
 
 fn textsplit(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
@@ -648,12 +679,12 @@ fn textsplit(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
     }
     let pad = if has(a, 5) { scalar(arg(a, 5)?) } else { Value::Error(CellError::NA) };
     let mut rows: Vec<Vec<String>> = Vec::new();
-    for r in split_by(&s, &row_d, mode == 1) {
+    for r in split_by(&s, &row_d, mode == 1)? {
         if ignore && r.is_empty() {
             continue;
         }
         let cells: Vec<String> =
-            split_by(&r, &col_d, mode == 1).into_iter().filter(|c| !(ignore && c.is_empty())).map(|c| c.into_iter().collect()).collect();
+            split_by(&r, &col_d, mode == 1)?.into_iter().filter(|c| !(ignore && c.is_empty())).map(|c| c.into_iter().collect()).collect();
         if ignore && cells.is_empty() {
             continue;
         }
@@ -1366,6 +1397,24 @@ mod tests {
         is_text(ev("TEXTAFTER", vec![t("aaa"), t("aa"), n(1.0)]), "a");
     }
 
+    /// Thousands of copies of one delimiter are tried once; delimiters that can't start where the
+    /// scan stands aren't compared; a search over a budget of comparisons is `#VALUE!`.
+    #[test]
+    fn delimiter_matching_stays_bounded() {
+        let text = "ab,".repeat(10_000);
+        let same: Vec<&str> = vec![","; 50_000];
+        let v = ev("TEXTSPLIT", vec![t(&text), av(row_t(&same))]);
+        assert_eq!(rows_of(&v).first().map(Vec::len), Some(10_001));
+        // Distinct long delimiters that start and end like every position: refused, not run.
+        let long: Vec<String> = (0..5_000).map(|i| format!("a{i}{}", "a".repeat(1_000))).collect();
+        let long: Vec<&str> = long.iter().map(String::as_str).collect();
+        is_err(ev("TEXTSPLIT", vec![t(&"a".repeat(30_000)), av(row_t(&long))]), CellError::Value);
+        is_err(ev("TEXTBEFORE", vec![t(&"a".repeat(30_000)), av(row_t(&long)), n(-1)]), CellError::Value);
+        // Longest match wins at a position, from either end.
+        is_text(ev("TEXTBEFORE", vec![t("x--y-z"), av(row_t(&["-", "--"]))]), "x");
+        is_text(ev("TEXTAFTER", vec![t("x--y-z"), av(row_t(&["-", "--"])), n(-1)]), "z");
+    }
+
     #[test]
     fn split() {
         let v = ev("TEXTSPLIT", vec![t("a,b;c,d"), t(","), t(";")]);

crates/xlsx/src/passthrough/write.rs

@@ -254,37 +254,27 @@ pub(crate) fn sheet_names_in(formula: &str) -> Vec<String> {
 /// Whether a kept chart sheet can be written back: its chart's series must still refer to sheets
 /// that exist under the same names (the chart is kept as it was, so a series on a deleted or
 /// renamed sheet would be left pointing at nothing), and no worksheet may have taken its name.
-///
-/// `refs` caches, by relationship id, the sheet names a chart sheet's graph refers to (`None`
-/// when the relationship is missing): entries sharing one graph are analysed once.
-fn chart_sheet_usable<'p>(wb: &Workbook, p: &'p Preserved, s: &'p PreservedSheet, refs: &mut HashMap<&'p str, Option<Vec<String>>>) -> bool {
+fn chart_sheet_usable(wb: &Workbook, p: &Preserved, s: &PreservedSheet) -> bool {
     let same = |a: &str, b: &str| a.chars().take(31).collect::<String>().eq_ignore_ascii_case(&b.chars().take(31).collect::<String>());
     if wb.sheets.iter().any(|w| same(&w.name, &s.name)) {
         return false;
     }
-    let names = refs.entry(s.rel_id.as_str()).or_insert_with(|| {
-        let root = p.rels.iter().find(|r| r.id == s.rel_id)?;
-        let parts = reachable(p, root);
-        let mut formulas = vec![];
-        for q in p.parts.iter().filter(|q| parts.contains(&normalize(&q.name)) && q.content_type.contains("chart")) {
-            if let Ok(x) = xml::parse(&q.data) {
-                chart_formulas(&x, &mut formulas);
-            }
+    let Some(root) = p.rels.iter().find(|r| r.id == s.rel_id) else { return false };
+    let parts = reachable(p, root);
+    let mut formulas = vec![];
+    for q in p.parts.iter().filter(|q| parts.contains(&normalize(&q.name)) && q.content_type.contains("chart")) {
+        if let Ok(x) = xml::parse(&q.data) {
+            chart_formulas(&x, &mut formulas);
         }
-        Some(formulas.iter().flat_map(|f| sheet_names_in(f)).collect())
-    });
-    let Some(names) = names else { return false };
-    names.iter().all(|n| wb.sheets.iter().any(|w| same(&w.name, n)))
+    }
+    formulas.iter().flat_map(|f| sheet_names_in(f)).all(|n| wb.sheets.iter().any(|w| same(&w.name, &n)))
 }
 
 /// Writes the workbook's kept parts and relationships. Chart sheets that can't be written back
 /// (see [`chart_sheet_usable`]) are left out with the parts only they reach.
 pub fn write_workbook(wb: &Workbook, wb_rels: &mut Rels, out: &mut Out) -> WorkbookKept {
     let Some(p) = wb.preserved.as_deref() else { return WorkbookKept::default() };
-    let (live, dropped): (Vec<&PreservedSheet>, Vec<&PreservedSheet>) = {
-        let mut refs = HashMap::new();
-        p.sheets.iter().partition(|s| chart_sheet_usable(wb, p, s, &mut refs))
-    };
+    let (live, dropped): (Vec<&PreservedSheet>, Vec<&PreservedSheet>) = p.sheets.iter().partition(|s| chart_sheet_usable(wb, p, s));
     let root_of = |s: &PreservedSheet| p.rels.iter().find(|r| r.id == s.rel_id);
     let dropped_ids: HashSet<&str> = dropped.iter().map(|s| s.rel_id.as_str()).collect();
     // Parts reached only by dropped chart sheets go with them.

crates/xlsx/src/tests/passthrough_tests.rs

@@ -696,32 +696,6 @@ fn chartsheet_package() -> Vec<u8> {
     ])
 }
 
-/// Thousands of chart-sheet entries naming one chart sheet's relationship: its graph is walked
-/// and its charts parsed once when saving, not once per entry.
-#[test]
-fn chart_sheet_entries_sharing_a_graph_are_checked_once() {
-    let bytes = chartsheet_package();
-    let mut z = zip::ZipArchive::new(std::io::Cursor::new(bytes)).unwrap();
-    let mut parts: Vec<(String, Vec<u8>)> = Vec::new();
-    for i in 0..z.len() {
-        let mut f = z.by_index(i).unwrap();
-        let mut data = Vec::new();
-        f.read_to_end(&mut data).unwrap();
-        parts.push((f.name().to_string(), data));
-    }
-    let extra: String = (0..3_000).map(|i| format!(r#"<sheet name="Copy{i}" sheetId="{}" r:id="rId2"/>"#, 100 + i)).collect();
-    for (name, data) in &mut parts {
-        if name == "xl/workbook.xml" {
-            *data = String::from_utf8(data.clone()).unwrap().replace("</sheets>", &format!("{extra}</sheets>")).into_bytes();
-        }
-    }
-    let refs: Vec<(&str, &[u8])> = parts.iter().map(|(n, d)| (n.as_str(), d.as_slice())).collect();
-    let (wb, _) = read_xlsx(&make_zip(&refs)).unwrap();
-    let u = Unpacked::new(&write_xlsx(&wb).unwrap());
-    u.assert_valid();
-    assert!(written_sheets(&u).iter().any(|(n, _)| n == "Chart1"));
-}
-
 /// The sheets of a written workbook: (name, state) in file order.
 fn written_sheets(u: &Unpacked) -> Vec<(String, String)> {
     let wb = xml::parse(u.parts.get("xl/workbook.xml").unwrap()).unwrap();