xls: charge expanded shared-formula text to the import's text allowance

Shared-formula followers each kept their own printed formula text, but
none of it counted against the 256 MB text allowance, so compact PtgExp
records could expand into gigabytes of retained formulas. Each attach
now charges its text; past the allowance the formula is dropped and the
cell keeps its cached value.

crates/functions/src/text.rs

@@ -1,7 +1,5 @@
 //! Text functions.
 
-use std::collections::HashMap;
-
 use gridcraft_core::parse::parse_number_text_in;
 use gridcraft_core::{CellError, Value, number_to_text};
 
@@ -543,52 +541,23 @@ 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. 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)>> {
+/// 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)> {
     let t = if insensitive { fold(text) } else { text.to_vec() };
-    let mut ds: Vec<Vec<char>> = delims.iter().filter(|d| !d.is_empty()).map(|d| if insensitive { fold(d) } else { d.clone() }).collect();
+    let 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 Ok((0..=t.len()).map(|i| (i, i)).collect());
+        return (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 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))? {
+            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 {
                 Some(l) => {
                     out.push((j - l, j));
                     j -= l;
@@ -597,12 +566,12 @@ fn find_matches(text: &[char], delims: &[Vec<char>], insensitive: bool, from_end
             }
         }
         out.reverse();
-        return Ok(out);
+        return out;
     }
     let mut i = 0;
     while i < t.len() {
-        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))? {
+        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 {
             Some(l) => {
                 out.push((i, i + l));
                 i += l;
@@ -610,7 +579,7 @@ fn find_matches(text: &[char], delims: &[Vec<char>], insensitive: bool, from_end
             None => i += 1,
         }
     }
-    Ok(out)
+    out
 }
 
 fn text_before_after(a: &[Arg], before: bool) -> R<Value> {
@@ -622,7 +591,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()) {
@@ -651,18 +620,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) -> R<Vec<Vec<char>>> {
+fn split_by(s: &[char], delims: &[Vec<char>], insensitive: bool) -> Vec<Vec<char>> {
     if delims.iter().all(Vec::is_empty) {
-        return Ok(vec![s.to_vec()]);
+        return 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());
-    Ok(out)
+    out
 }
 
 fn textsplit(a: &[Arg], _c: &mut dyn Ctx) -> R<Value> {
@@ -679,12 +648,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;
         }
@@ -1397,24 +1366,6 @@ 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/tests/xls_tests.rs

@@ -652,3 +652,19 @@ fn xls_short_window2_is_ignored() {
         assert_eq!(v(&wb, 0, "A1"), Value::Number(7.0));
     }
 }
+
+/// Shared-formula followers each keep their own text, charged to the workbook's text allowance:
+/// with no allowance left they keep their cached values, and the import still succeeds.
+#[test]
+fn shared_formula_text_counts_against_the_text_allowance() {
+    let file = compound("Workbook", &sample(false));
+    // The smallest allowance that reads every string: nothing is left for expanded formulas.
+    let left = (0..1000).find(|n| crate::xls::read_xls_with(&file, crate::xls::Budget::with_text_left(*n)).is_ok()).unwrap();
+    let (wb, report) = crate::xls::read_xls_with(&file, crate::xls::Budget::with_text_left(left)).unwrap();
+    assert_eq!(ftext(&wb, "B6"), None);
+    assert_eq!(v(&wb, 0, "B6"), Value::Number(20.0));
+    assert!(report.warnings.iter().any(|w| w.contains("shared-formula text")), "{:?}", report.warnings);
+    // With room, the followers keep their formulas.
+    let (wb, _) = crate::xls::read_xls_with(&file, crate::xls::Budget::default()).unwrap();
+    assert!(ftext(&wb, "B6").is_some());
+}

crates/xlsx/src/xls.rs

@@ -89,6 +89,11 @@ impl Budget {
     pub(crate) fn with_max_records(max_records: usize) -> Self {
         Budget { max_records, ..Budget::default() }
     }
+    /// A budget with only `left` bytes of text allowance (tests).
+    #[cfg(test)]
+    pub(crate) fn with_text_left(left: usize) -> Self {
+        Budget { text: MAX_TEXT.saturating_sub(left), ..Budget::default() }
+    }
     fn record(&mut self) -> Result<(), IoError> {
         self.records = self.records.saturating_add(1);
         if self.records > self.max_records {
@@ -103,6 +108,16 @@ impl Budget {
         }
         Ok(())
     }
+    /// Charges `len` bytes of text if they fit the allowance, leaving it untouched otherwise:
+    /// for text the import can do without (expanded shared formulas keep their cached values).
+    fn try_text(&mut self, len: usize) -> bool {
+        let total = self.text.saturating_add(len);
+        let fits = total <= MAX_TEXT;
+        if fits {
+            self.text = total;
+        }
+        fits
+    }
     fn text(&mut self, len: usize) -> Result<(), IoError> {
         self.text = self.text.saturating_add(len);
         if self.text > MAX_TEXT {
@@ -487,6 +502,7 @@ fn rk(v: u32) -> Value {
 /// keep their cached values).
 fn resolve_pending(
     st: &mut SheetState<'_>,
+    budget: &mut Budget,
     arrays: &HashMap<CellRef, (RangeRef, Parsed)>,
     shared: &HashMap<CellRef, Parsed>,
     pending: &[Pending],
@@ -504,6 +520,18 @@ fn resolve_pending(
             }
             shared_attaches += 1;
             st.attach(p.pos, f, Mode::Shared, None);
+            let len = st.sheet.cell(p.pos).and_then(|c| c.formula.as_ref()).map(|f| f.text.len());
+            // Every follower keeps its own text: charge it to the workbook's text allowance, and
+            // past it drop the formula again so the cell keeps its cached value.
+            if let Some(len) = len
+                && !budget.try_text(len)
+            {
+                if let Some(cell) = st.sheet.cells.get_mut(p.pos) {
+                    cell.formula = None;
+                }
+                st.unsupported("more shared-formula text than the import allows");
+                break;
+            }
             let imported = st.sheet.cell(p.pos).and_then(|c| c.formula.as_ref()).is_some_and(|f| f.text.chars().count() <= MAX_SHARED_TEMPLATE);
             if !imported {
                 failed.insert(p.anchor);
@@ -586,7 +614,7 @@ fn worksheet(
     // Shared and array formulas: their definitions follow the first cell that uses them.
     let (arrays, shared) = (std::mem::take(&mut st.arrays), std::mem::take(&mut st.shared));
     let pending = std::mem::take(&mut st.pending);
-    resolve_pending(&mut st, &arrays, &shared, &pending);
+    resolve_pending(&mut st, budget, &arrays, &shared, &pending);
     blank_array_followers(&mut st, &pending);
     if st.dropped > 0 {
         report.warn(format!("{} cells outside the grid were skipped.", st.dropped));