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!.

apps/gridcraft-cli/src/check/calc.rs

@@ -31,41 +31,20 @@ fn is_volatile(e: &Expr, volatile_names: &HashSet<String>) -> bool {
 }
 
 /// Upper-cased defined names whose formula is volatile, directly or through other names.
-///
-/// Volatility flows backwards along name references: each name is parsed and walked once, and a
-/// worklist carries volatility from a name to the names that use it. Rescanning every name until
-/// nothing changes was quadratic: a file listing its names so that each pass marked only one more
-/// did one full pass per name.
 pub(super) fn volatile_names(wb: &Workbook) -> HashSet<String> {
+    let parsed: Vec<(String, Option<Expr>)> =
+        wb.names.iter().map(|n| (n.name.to_ascii_uppercase(), gridcraft_engine::formula::parse(&n.formula).ok())).collect();
     let mut set = HashSet::new();
-    // Upper-cased name -> the names whose formulas refer to it.
-    let mut users: HashMap<String, Vec<String>> = HashMap::new();
-    let mut queue = Vec::new();
-    let none = HashSet::new();
-    for n in &wb.names {
-        let name = n.name.to_ascii_uppercase();
-        let Ok(e) = gridcraft_engine::formula::parse(&n.formula) else { continue };
-        if is_volatile(&e, &none) {
-            if set.insert(name.clone()) {
-                queue.push(name.clone());
+    // Each round adds at least one name or stops, so `len + 1` rounds reach the fixed point.
+    for _ in 0..=parsed.len() {
+        let before = set.len();
+        for (name, e) in &parsed {
+            if !set.contains(name) && e.as_ref().is_some_and(|e| is_volatile(e, &set)) {
+                set.insert(name.clone());
             }
-            continue;
         }
-        let mut used = BTreeSet::new();
-        e.walk(&mut |x| {
-            if let Expr::Name(r) = x {
-                used.insert(r.to_ascii_uppercase());
-            }
-        });
-        for r in used {
-            users.entry(r).or_default().push(name.clone());
-        }
-    }
-    while let Some(v) = queue.pop() {
-        for user in users.remove(&v).unwrap_or_default() {
-            if set.insert(user.clone()) {
-                queue.push(user);
-            }
+        if set.len() == before {
+            break;
         }
     }
     set

apps/gridcraft-cli/src/check/tests.rs

@@ -178,28 +178,6 @@ fn volatile_names_propagate() {
     assert_eq!(check(&wb, &Options::default()).calc.volatile, 1);
 }
 
-#[test]
-fn volatile_names_propagate_through_a_long_chain_in_one_walk() {
-    // Chain0 uses Chain1, Chain1 uses Chain2, ... and only the last is volatile: listed in this order, a rescan
-    // until nothing changes marked one name per pass (quadratic). Every name in the chain is
-    // volatile; a name off the chain is not.
-    const LEN: usize = 5_000;
-    let mut wb = book(&[("A1", "=1", n(1.0))]);
-    let name =
-        |name: String, formula: String| gridcraft_engine::model::DefinedName { name, scope: None, formula, comment: String::new(), hidden: false };
-    for i in 0..LEN {
-        let formula = if i + 1 == LEN { "NOW()".to_string() } else { format!("Chain{}+1", i + 1) };
-        wb.names.push(name(format!("Chain{i}"), formula));
-    }
-    wb.names.push(name("Plain".into(), "Chain0*0+Other".into()));
-    wb.names.push(name("Other".into(), "1".into()));
-    let set = volatile_names(&wb);
-    assert!((0..LEN).all(|i| set.contains(&format!("CHAIN{i}"))));
-    assert!(set.contains("PLAIN"));
-    assert!(!set.contains("OTHER"));
-    assert_eq!(set.len(), LEN + 1);
-}
-
 #[test]
 fn round_trip_of_a_simple_book_is_clean() {
     let mut wb = book(&[("A1", "2", n(2.0)), ("B1", "=A1*3", n(6.0)), ("A2", "x", Value::text("x"))]);

crates/chart/src/raster.rs

@@ -7,12 +7,6 @@ use crate::{Prim, Rgba};
 /// Largest image we allocate (pixels).
 const MAX_PIXELS: u64 = 64 * 1024 * 1024;
 const SUB: usize = 4;
-/// Scan-conversion work one [`rasterize`] call may do: edge tests (an active edge at one
-/// sub-sample) plus covered pixels blended. Edges are only tested on the rows they cross, but a
-/// caller can still pass enough geometry to keep the rasteriser busy for minutes on a small
-/// image; once the allowance is spent the remaining fills are skipped. 2^28 is about a second,
-/// far beyond any chart.
-const MAX_SCAN_WORK: u64 = 1 << 28;
 
 type Path = Vec<Vec<[f32; 2]>>;
 
@@ -21,8 +15,6 @@ struct Canvas {
     h: usize,
     buf: Vec<u8>,
     acc: Vec<f32>,
-    /// Scan-conversion work left (see [`MAX_SCAN_WORK`]).
-    work: u64,
 }
 
 impl Canvas {
@@ -49,8 +41,7 @@ impl Canvas {
 
     /// Fills a multi-contour path with the even-odd rule.
     fn fill(&mut self, path: &Path, color: Rgba) {
-        // Each edge as [top y, bottom y, x0, y0, x1, y1].
-        let mut edges: Vec<[f32; 6]> = Vec::new();
+        let mut edges: Vec<[f32; 4]> = Vec::new();
         let (mut minx, mut miny, mut maxx, mut maxy) = (f32::INFINITY, f32::INFINITY, f32::NEG_INFINITY, f32::NEG_INFINITY);
         for c in path {
             if c.len() < 3 || !c.iter().all(|p| p[0].is_finite() && p[1].is_finite()) {
@@ -63,7 +54,7 @@ impl Canvas {
                 miny = miny.min(p[1]);
                 maxy = maxy.max(p[1]);
                 if p[1] != q[1] {
-                    edges.push([p[1].min(q[1]), p[1].max(q[1]), p[0], p[1], q[0], q[1]]);
+                    edges.push([p[0], p[1], q[0], q[1]]);
                 }
             }
         }
@@ -81,26 +72,8 @@ impl Canvas {
         if self.acc.len() < bw + 1 {
             self.acc.resize(bw + 1, 0.0);
         }
-        // Active-edge list: edges join when the scan reaches their top and leave past their
-        // bottom, so each row tests only the edges crossing it instead of every edge.
-        edges.sort_by(|a, b| a[0].total_cmp(&b[0]));
-        let mut pending = edges.iter().peekable();
-        let mut active: Vec<[f32; 6]> = Vec::new();
         let mut xs: Vec<f32> = Vec::new();
         for py in y0..y1 {
-            while let Some(e) = pending.next_if(|e| e[0] < py as f32 + 1.0) {
-                active.push(*e);
-            }
-            active.retain(|e| e[1] > py as f32);
-            if active.is_empty() {
-                continue;
-            }
-            let tests = (active.len() * SUB) as u64;
-            if tests > self.work {
-                self.work = 0;
-                return;
-            }
-            self.work -= tests;
             for v in self.acc.iter_mut().take(bw) {
                 *v = 0.0;
             }
@@ -108,9 +81,10 @@ impl Canvas {
             for s in 0..SUB {
                 let sy = py as f32 + (s as f32 + 0.5) / SUB as f32;
                 xs.clear();
-                for e in &active {
-                    if sy >= e[0] && sy < e[1] {
-                        xs.push(e[2] + (sy - e[3]) * (e[4] - e[2]) / (e[5] - e[3]));
+                for e in &edges {
+                    let (ya, yb) = if e[1] < e[3] { (e[1], e[3]) } else { (e[3], e[1]) };
+                    if sy >= ya && sy < yb {
+                        xs.push(e[0] + (sy - e[1]) * (e[2] - e[0]) / (e[3] - e[1]));
                     }
                 }
                 xs.sort_by(f32::total_cmp);
@@ -136,7 +110,6 @@ impl Canvas {
             if !any {
                 continue;
             }
-            self.work = self.work.saturating_sub(bw as u64);
             for px in x0..x1 {
                 let cov = self.acc.get(px - x0).copied().unwrap_or(0.0);
                 if cov > 0.0 {
@@ -239,7 +212,7 @@ pub fn rasterize(prims: &[Prim], w: u32, h: u32, background: Rgba) -> Vec<u8> {
     for _ in 0..w * h {
         buf.extend_from_slice(&background);
     }
-    let mut cv = Canvas { w, h, buf, acc: Vec::new(), work: MAX_SCAN_WORK };
+    let mut cv = Canvas { w, h, buf, acc: Vec::new() };
     for p in prims {
         match p {
             Prim::Rect { x, y, w, h, fill, stroke, radius } => {
@@ -301,31 +274,6 @@ pub fn rasterize(prims: &[Prim], w: u32, h: u32, background: Rgba) -> Vec<u8> {
 mod tests {
     use super::*;
 
-    /// Security: each row tests only the edges crossing it. A polygon of 100,000 tiny edges over
-    /// 4,000 rows tested every edge at every sub-sample of every row (1.6 billion tests).
-    #[test]
-    fn many_short_edges_scan_only_their_rows() {
-        let mut pts: Vec<[f32; 2]> = (0..100_000).map(|i| [if i % 2 == 0 { 0.0 } else { 0.5 }, i as f32 * 0.04]).collect();
-        pts.push([2.0, 4_000.0]);
-        pts.push([2.0, 0.0]);
-        let img = rasterize(&[Prim::Polygon { pts, fill: [255, 0, 0, 255], stroke: None }], 2, 4_000, [0, 0, 0, 0]);
-        // The right-hand pixel of every row is inside the polygon.
-        assert_eq!(img.get(4..8), Some(&[255, 0, 0, 255][..]));
-        assert_eq!(img.get(4 * (2 * 3_999 + 1)..4 * (2 * 3_999 + 2)), Some(&[255, 0, 0, 255][..]));
-    }
-
-    /// Security: scan conversion stops once the call's work allowance is spent.
-    #[test]
-    fn fills_stop_when_the_work_allowance_is_spent() {
-        let square = vec![vec![[0.0, 0.0], [4.0, 0.0], [4.0, 4.0], [0.0, 4.0]]];
-        let mut cv = Canvas { w: 4, h: 4, buf: vec![0; 64], acc: Vec::new(), work: 2 * SUB as u64 * 4 + 16 };
-        cv.fill(&square, [255; 4]);
-        assert!(cv.buf.iter().all(|&b| b == 255));
-        cv.buf = vec![0; 64];
-        cv.fill(&square, [255; 4]);
-        assert!(cv.buf.iter().all(|&b| b == 0));
-    }
-
     #[test]
     fn dashed_geometry_stays_within_the_dash_budget() {
         // Forty very long dashed lines, each allowed 10_000 dashes per segment: before the

crates/chart/src/render/lines.rs

@@ -136,13 +136,7 @@ pub(super) fn decimate_area(top: Vec<[f32; 2]>, base: Vec<[f32; 2]>, max: usize)
 
 /// Draws a polyline split at gaps (`None`), decimated when long. With `smooth` (the plot box),
 /// each run is interpolated with a Catmull-Rom spline so the line curves through the data points.
-///
-/// The points interpolation adds are budgeted across all the runs of the line, not per run:
-/// short runs between gaps escape decimation, and 100 sub-segments each would turn a
-/// 100,000-point series of three-point runs into millions of points. Past the budget the
-/// remaining runs are drawn through their data points only.
 pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, width: f32, smooth: Option<Bx>) {
-    let mut budget = MAX_LINE_PTS * 2;
     let mut run: Vec<[f32; 2]> = Vec::new();
     for p in pts.iter().chain(std::iter::once(&None)) {
         match p {
@@ -151,11 +145,7 @@ pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, wi
                 if run.len() >= 2 {
                     let r = decimate(std::mem::take(&mut run), MAX_LINE_PTS);
                     let r = match smooth {
-                        Some(plot) => {
-                            let r = smooth_run(r, plot, budget);
-                            budget = budget.saturating_sub(r.len());
-                            r
-                        }
+                        Some(plot) => smooth_run(r, plot),
                         None => r,
                     };
                     ctx.line(r, color, width);
@@ -168,15 +158,15 @@ pub(super) fn draw_runs(ctx: &mut Ctx, pts: &[Option<[f32; 2]>], color: Rgba, wi
 }
 
 /// Catmull-Rom spline through `pts`: every segment gets the same number of sub-segments (up to
-/// 100), chosen so the whole curve stays within `cap` points (one per data point when `cap` is
-/// smaller than that). Endpoints are
+/// 100), chosen so the whole curve stays within `MAX_LINE_PTS * 2` points. Endpoints are
 /// duplicated so the curve passes through the first and last points, and the curve is clamped
 /// to the `plot` box (a spline overshoots its data near sharp turns).
-fn smooth_run(pts: Vec<[f32; 2]>, plot: Bx, cap: usize) -> Vec<[f32; 2]> {
+fn smooth_run(pts: Vec<[f32; 2]>, plot: Bx) -> Vec<[f32; 2]> {
     let n = pts.len();
     if n < 3 {
         return pts;
     }
+    let cap = MAX_LINE_PTS * 2;
     let steps = (cap / n).clamp(1, 100);
     let mut out: Vec<[f32; 2]> = Vec::with_capacity(n.saturating_mul(steps).min(cap) + 1);
     let at = |i: isize| -> [f32; 2] {
@@ -229,7 +219,7 @@ mod smooth_tests {
     fn long_runs_are_smoothed_uniformly_within_the_cap() {
         let plot = Bx { x: 0.0, y: 0.0, w: 3000.0, h: 100.0 };
         let pts: Vec<[f32; 2]> = (0..1500).map(|i| [i as f32 * 2.0, if i % 2 == 0 { 20.0 } else { 80.0 }]).collect();
-        let out = smooth_run(pts, plot, MAX_LINE_PTS * 2);
+        let out = smooth_run(pts, plot);
         assert!(out.len() <= MAX_LINE_PTS * 2 + 1, "{}", out.len());
         // Two sub-segments per segment all the way to the end, not 100 each and then a straight tail.
         assert_eq!(out.len(), 1499 * 2 + 1);
@@ -241,29 +231,11 @@ mod smooth_tests {
         let plot = Bx { x: 0.0, y: 10.0, w: 300.0, h: 100.0 };
         // A step right at the plot edges: Catmull-Rom overshoots past both.
         let pts = vec![[0.0, 110.0], [100.0, 110.0], [110.0, 10.0], [200.0, 10.0], [300.0, 10.0]];
-        let out = smooth_run(pts, plot, MAX_LINE_PTS * 2);
+        let out = smooth_run(pts, plot);
         assert!(out.len() > 5);
         assert!(out.iter().all(|p| (0.0..=300.0).contains(&p[0]) && (10.0..=110.0).contains(&p[1])));
     }
 
-    /// Security: smoothing budgets its added points across every run of a line. A series of
-    /// three-point runs between gaps used to get 100 sub-segments per run, 67 times its data.
-    #[test]
-    fn gap_separated_runs_share_one_smoothing_budget() {
-        let plot = Bx { x: 0.0, y: 0.0, w: 1e6, h: 100.0 };
-        let pts: Vec<Option<[f32; 2]>> =
-            (0..100_000).map(|i| if i % 4 == 3 { None } else { Some([i as f32, if i % 2 == 0 { 20.0 } else { 80.0 }]) }).collect();
-        let m = crate::ApproxMeasure;
-        let mut ctx = Ctx { out: Vec::new(), m: &m };
-        draw_runs(&mut ctx, &pts, WHITE, 1.0, Some(plot));
-        let total: usize = ctx.out.iter().map(|p| if let Prim::Line { pts, .. } = p { pts.len() } else { 0 }).sum();
-        // 75,000 data points, plus at most the budget added by interpolation.
-        assert!(total <= 75_000 + MAX_LINE_PTS * 2, "{total}");
-        assert_eq!(ctx.out.len(), 25_000);
-        // The first runs are still smoothed.
-        assert!(matches!(ctx.out.first(), Some(Prim::Line { pts, .. }) if pts.len() > 3));
-    }
-
     #[test]
     fn decimate_area_preserves_paired_vertical_strips() {
         let top: Vec<[f32; 2]> = (0..1000).map(|i| [i as f32 * 0.25, ((i * 37) % 100) as f32]).collect();

crates/chart/src/resolve.rs

@@ -133,46 +133,6 @@ fn value_text(v: &Value) -> String {
     }
 }
 
-/// Characters kept of one category label: an axis label never shows more (labels are fitted to
-/// the axis), and copying more only costs memory.
-const MAX_LABEL_CHARS: usize = 255;
-/// Bytes of category label text kept per series. One long text broadcast by a short formula
-/// (`IF(SEQUENCE(100000), long_text)`) is a single shared value, but turning every element into
-/// its own label copied it 100,000 times (gigabytes). Labels past the budget are empty.
-const MAX_CATEGORY_BYTES: usize = 8 << 20;
-
-/// At most [`MAX_LABEL_CHARS`] characters and `room` bytes of `s`, cut at a character boundary.
-fn clip_label(s: &str, room: usize) -> String {
-    let mut end = 0;
-    for (n, (i, c)) in s.char_indices().enumerate() {
-        if n >= MAX_LABEL_CHARS || i + c.len_utf8() > room {
-            break;
-        }
-        end = i + c.len_utf8();
-    }
-    s.get(..end).unwrap_or_default().to_string()
-}
-
-/// The label of category `i` (value `v`) in at most `room` bytes: formatted with its source
-/// cell's number format when it is a number.
-fn category_label(wb: &Workbook, src: Option<(&gridcraft_model::Sheet, RangeRef)>, i: usize, v: &Value, room: usize) -> String {
-    if let (Some((s, r)), Value::Number(_)) = (src, v) {
-        let w = r.width().max(1) as usize;
-        let at = r.start.offset((i / w) as i64, (i % w) as i64);
-        if let Some(c) = at {
-            let code = &wb.styles.get(s.style_id(c)).num_fmt.0;
-            if !code.eq_ignore_ascii_case("general") {
-                return clip_label(&format_value(v, &NumberFormat::parse_cached(code), wb.date_system).text, room);
-            }
-        }
-    }
-    // Text is clipped before it is copied: the source may be one long shared string.
-    match v {
-        Value::Text(t) => clip_label(t, room),
-        _ => clip_label(&value_text(v), room),
-    }
-}
-
 /// Category labels, formatted with each source cell's number format (dates, currency…), and
 /// the outer levels of a multi-level axis: a category range wider than a column of values (or
 /// taller than a row of values) groups its innermost labels, year beside month. Each outer level
@@ -181,14 +141,21 @@ fn category_table(wb: &Workbook, sheet: usize, formula: &str, values: &str) -> (
     let vals = eval_list(wb, sheet, formula);
     let cells: Option<(usize, RangeRef)> = parse_ref(wb, sheet, formula);
     let src = cells.and_then(|(sh, r)| wb.sheet(sh).map(|s| (s, r)));
-    let mut room = MAX_CATEGORY_BYTES;
     let texts: Vec<String> = vals
         .iter()
         .enumerate()
         .map(|(i, v)| {
-            let label = category_label(wb, src, i, v, room);
-            room = room.saturating_sub(label.len());
-            label
+            if let (Some((s, r)), Value::Number(_)) = (src, v) {
+                let w = r.width().max(1) as usize;
+                let at = r.start.offset((i / w) as i64, (i % w) as i64);
+                if let Some(c) = at {
+                    let code = &wb.styles.get(s.style_id(c)).num_fmt.0;
+                    if !code.eq_ignore_ascii_case("general") {
+                        return format_value(v, &NumberFormat::parse_cached(code), wb.date_system).text;
+                    }
+                }
+            }
+            value_text(v)
         })
         .collect();
     let Some((_, r)) = src else { return (texts, vec![]) };
@@ -309,23 +276,3 @@ pub fn resolve(wb: &Workbook, sheet: usize, chart: &Chart) -> ChartData {
     let palette = default_palette(&wb.theme, n.min(PALETTE_CYCLE));
     ChartData { categories, category_levels, series, palette }
 }
-
-#[cfg(test)]
-mod label_budget_tests {
-    use gridcraft_model::Workbook;
-
-    /// Security: category labels are clipped before they are copied, with one byte budget per
-    /// series. A formula broadcasting one long text to 100,000 categories used to copy it
-    /// 100,000 times (3.3 GB).
-    #[test]
-    fn category_labels_share_one_byte_budget() {
-        let wb = Workbook::new();
-        let (texts, _) = super::category_table(&wb, 0, r#"=IF(SEQUENCE(100000),REPT("x",32767))"#, "");
-        assert_eq!(texts.len(), 100_000);
-        assert_eq!(texts.first().map(String::len), Some(super::MAX_LABEL_CHARS));
-        assert!(texts.iter().map(String::len).sum::<usize>() <= super::MAX_CATEGORY_BYTES);
-        // Labels are cut at character boundaries.
-        assert_eq!(super::clip_label("aé", 2), "a");
-        assert_eq!(super::clip_label("aé", 3), "aé");
-    }
-}

crates/engine/src/cmd.rs

@@ -459,11 +459,8 @@ pub(crate) const TOUCH_LOG_LIMIT: usize = 1_000_000;
 pub(crate) const PROTECTED: &str = "The cell or chart you're trying to change is on a protected sheet.";
 
 /// Refuses an edit that changed what a locked cell on a protected sheet holds (its value or
-/// formula), or that unlocked it, whichever command made it. Sheets are matched by name, so
-/// moving, renaming or deleting a sheet isn't an edit of its cells. A sort or duplicate removal
-/// that moves an unlocked cell with equal content onto a locked one changes no content but would
-/// leave the cell editable, so the effective lock (row and column formats included) is compared
-/// as well.
+/// formula), whichever command made it. Sheets are matched by name, so moving, renaming or
+/// deleting a sheet isn't an edit of its cells.
 fn check_protection(old: &Workbook, new: &Workbook, unlocked: &[(String, String)]) -> Result<()> {
     for sh in &old.sheets {
         if !sh.is_protected() {
@@ -474,8 +471,7 @@ fn check_protection(old: &Workbook, new: &Workbook, unlocked: &[(String, String)
             continue;
         }
         for c in sh.cells.diff(&after.cells) {
-            let unlocked_now = !new.styles.get(after.style_id(c)).protection.locked;
-            if (unlocked_now || !same_content(sh.cell(c), after.cell(c)))
+            if !same_content(sh.cell(c), after.cell(c))
                 && old.styles.get(sh.style_id(c)).protection.locked
                 && let Some(m) = locked_cell_error(sh, c, unlocked)
             {

crates/engine/src/cmd/sheet.rs

@@ -398,10 +398,10 @@ fn move_columns(s: &mut Session, p: &Json) -> Result<Json> {
     {
         return Err(EngineError::Other("To prevent possible loss of data, columns cannot be shifted off of the worksheet.".into()));
     }
-    // The checks must authorize the sheet this command modifies, not whatever sheet is active:
-    // both get the index `target_sheet` resolved (from `sheet`, or a `Sheet!` range or cell).
-    check_lines_protection(s, &json!({"cols": RangeRef::cols(before, before).a1(), "sheet": sheet}), Axis::Cols, before, count, true)?;
-    check_lines_protection(s, &json!({"cols": RangeRef::cols(from, end - 1).a1(), "sheet": sheet}), Axis::Cols, from, count, false)?;
+    // The checks must authorize the sheet this command modifies (`target_sheet`), not whatever
+    // sheet is active: both carry the command's own `sheet` parameter on.
+    check_lines_protection(s, &json!({"cols": RangeRef::cols(before, before).a1(), "sheet": p.get("sheet")}), Axis::Cols, before, count, true)?;
+    check_lines_protection(s, &json!({"cols": RangeRef::cols(from, end - 1).a1(), "sheet": p.get("sheet")}), Axis::Cols, from, count, false)?;
 
     let moved_from = if before <= from { from + count } else { from };
     if moved_from.checked_add(count).is_none_or(|end| end > MAX_COLS) {

crates/engine/src/tests.rs

@@ -5297,42 +5297,6 @@ fn move_columns_checks_the_protection_of_the_named_sheet() {
     assert_eq!(v(&s, "A1"), Value::text("A"));
 }
 
-#[test]
-fn move_columns_checks_the_protection_of_a_sheet_named_by_its_range() {
-    // A `Sheet!` range or cell picks the sheet the move modifies; the protection checks must
-    // authorize that sheet too, not the active one.
-    let mut s = s();
-    s.execute("home.insertSheet", json!({"name": "P"})).unwrap();
-    s.execute("range.setValues", json!({"range": "A1", "values": [[1, 2, 3, 4]]})).unwrap();
-    s.execute("review.protectSheet", json!({})).unwrap();
-    s.execute("sheet.activate", json!({"sheet": 0})).unwrap();
-    for key in ["range", "cell"] {
-        let err = s.execute("sheet.moveColumns", json!({key: "P!A1", "cols": "B:C", "before": 4})).expect_err("moving columns on a protected sheet");
-        assert!(err.to_string().contains("protected"), "{err}");
-    }
-    let d = s.doc().unwrap();
-    let sh = &d.wb.sheets[d.wb.sheet_index("P").unwrap()];
-    let pv: Vec<Value> = (0..4).map(|c| sh.value(CellRef::new(0, c))).collect();
-    assert_eq!(pv, vec![Value::number(1.0), Value::number(2.0), Value::number(3.0), Value::number(4.0)]);
-}
-
-#[test]
-fn sorting_cannot_unlock_a_locked_cell_by_moving_equal_content_onto_it() {
-    // An unlocked 2 sorted onto a locked 2 leaves the content as it was, but would make the cell
-    // editable; the sort is refused instead.
-    let mut s = s();
-    s.execute("range.setValues", json!({"range": "A1", "values": [[2], [2], [1]]})).unwrap();
-    s.execute("home.lockCell", json!({"range": "A1", "on": false})).unwrap();
-    s.execute("home.lockCell", json!({"range": "A3", "on": false})).unwrap();
-    s.execute("review.protectSheet", json!({"sort": true})).unwrap();
-    let before = s.doc().unwrap().wb.clone();
-    let err =
-        s.execute("data.sort", json!({"range": "A1:A3", "header": false, "keys": [{"column": "A", "order": "asc"}]})).expect_err("sort unlocking A2");
-    assert!(err.to_string().contains("protected sheet"), "{err}");
-    assert_eq!(*s.doc().unwrap().wb, *before);
-    assert!(s.execute("cell.set", json!({"cell": "A2", "input": "9"})).is_err(), "A2 stays locked");
-}
-
 #[test]
 fn a_script_cannot_switch_windows() {
     // Stored scripts are scoped to their workbook: a step that activates another window would

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(";")]);