formula, calc: LET/LAMBDA names looked up through a map; ragged array literals refused before reserving (#3312)

The 10,000-character header spec was bounded, but each &A, &F or &Z
added the whole sheet name or path again, and a JSON workbook's sheet
name has no length limit. A field that would take a section past
64 KiB is now left out.

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

@@ -6,6 +6,10 @@ const MAX_XML_PART: u64 = 64 * 1024 * 1024;
 /// Most zip entries looked at while validating a written package.
 const MAX_ENTRIES: usize = 200_000;
 
+/// Decompressed bytes that comparing one package's relationship kinds may read in total: the
+/// relationship parts themselves and the targets whose content is checked.
+const RELATIONSHIP_BUDGET: u64 = 512 * 1024 * 1024;
+
 /// Relationship kinds (lower case) whose absence after a save isn't a loss: the calculation chain is
 /// a cache Excel rebuilds, and GridCraft never writes it.
 pub(super) const REBUILT_KINDS: [&str; 1] = ["calcchain"];
@@ -117,6 +121,30 @@ fn read_zip_part(zip: &mut Zip<'_>, name: &str) -> Result<Vec<u8>, String> {
     Ok(buf)
 }
 
+enum PartError {
+    /// Reading the part would spend more than the remaining budget.
+    OverBudget,
+    Unreadable,
+}
+
+/// Reads a part like [`read_zip_part`], charging the decompressed bytes to `budget`.
+fn read_zip_part_within(zip: &mut Zip<'_>, name: &str, budget: &mut u64) -> Result<Vec<u8>, PartError> {
+    let f = zip.by_name(name).map_err(|_| PartError::Unreadable)?;
+    // One byte past what is left shows that the part doesn't fit.
+    let limit = MAX_XML_PART.min(budget.saturating_add(1));
+    let mut buf = Vec::new();
+    // Bytes read before a decompression error still count against the budget.
+    let res = f.take(limit).read_to_end(&mut buf);
+    let read = buf.len() as u64;
+    if read > *budget {
+        *budget = 0;
+        return Err(PartError::OverBudget);
+    }
+    *budget -= read;
+    res.map_err(|_| PartError::Unreadable)?;
+    Ok(buf)
+}
+
 /// Whether the producer flagged its cached results as stale with `<calcPr fullCalcOnLoad="1">`:
 /// libraries that don't calculate write it, and store 0 or nothing as every formula's value.
 pub(super) fn full_calc_on_load(bytes: &[u8]) -> bool {
@@ -232,19 +260,30 @@ pub fn validate_package(bytes: &[u8]) -> Result<Vec<String>, String> {
 /// nothing are left out, as a save may rightly drop them: a link to a place in the workbook
 /// (`#Sheet1!A1`, written as a cell's `location`) and a target part with nothing in it.
 pub(super) fn relationship_kinds(bytes: &[u8]) -> Result<BTreeMap<String, String>, String> {
+    relationship_kinds_within(bytes, RELATIONSHIP_BUDGET)
+}
+
+/// [`relationship_kinds`] reading at most `budget` decompressed bytes. `Err` once the relationship
+/// parts alone need more: their kinds can't be listed completely.
+fn relationship_kinds_within(bytes: &[u8], mut budget: u64) -> Result<BTreeMap<String, String>, String> {
     let mut zip = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| format!("not a zip package: {e}"))?;
     let names = zip_names(&mut zip);
     let by_key: HashMap<String, &String> = names.iter().map(|n| (part_key(n), n)).collect();
     // Several relationships name the same part; each fresh check decompressed it again, so
     // repeated references to one highly compressible part multiplied the work. The verdict is
     // remembered per (part, named content) and the decompression the package can cause is
-    // budgeted as a whole (finding: repeated decompression).
+    // budgeted as a whole, the relationship parts included: many large, unreferenced rels parts
+    // would otherwise each spend a full per-part allowance.
     let mut verdicts: HashMap<(String, &'static str), bool> = HashMap::new();
-    let mut budget: u64 = 512 * 1024 * 1024;
     let mut kinds = BTreeMap::new();
     for n in names.iter().filter(|n| part_key(n).ends_with(".rels")) {
         let Some(src_dir) = rels_source_dir(&part_key(n)) else { continue };
-        let Ok(els) = read_zip_part(&mut zip, n).and_then(|xml| xml_elements(&xml)) else { continue };
+        let xml = match read_zip_part_within(&mut zip, n, &mut budget) {
+            Ok(xml) => xml,
+            Err(PartError::OverBudget) => return Err(format!("{n}: relationship check stopped at its decompression limit")),
+            Err(PartError::Unreadable) => continue,
+        };
+        let Ok(els) = xml_elements(&xml) else { continue };
         for (_, attrs) in els.iter().filter(|(el, _)| el == "Relationship") {
             let Some(kind) = attr(attrs, "Type").and_then(|t| t.rsplit('/').next()) else { continue };
             let target = attr(attrs, "Target").unwrap_or("");
@@ -329,3 +368,36 @@ fn holds_something_uncached(zip: &mut Zip<'_>, name: &str, marker: &'static str,
         buf.clear();
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use std::io::Write as _;
+
+    use super::*;
+
+    /// A package with `count` relationship parts of `size` bytes each, none of them describing an
+    /// existing part.
+    fn many_rels(count: usize, size: usize) -> Vec<u8> {
+        let mut z = zip::ZipWriter::new(Cursor::new(Vec::new()));
+        let opts = zip::write::SimpleFileOptions::default().compression_method(zip::CompressionMethod::Deflated);
+        let head = r#"<?xml version="1.0"?><Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/custom" Target="https://example.com" TargetMode="External"/>"#;
+        let tail = "</Relationships>";
+        let filler = " ".repeat(size.saturating_sub(head.len() + tail.len()));
+        for i in 0..count {
+            z.start_file(format!("xl/_rels/part{i}.xml.rels"), opts).unwrap();
+            z.write_all(head.as_bytes()).unwrap();
+            z.write_all(filler.as_bytes()).unwrap();
+            z.write_all(tail.as_bytes()).unwrap();
+        }
+        z.finish().unwrap().into_inner()
+    }
+
+    #[test]
+    fn relationship_parts_count_against_the_decompression_budget() {
+        // Each part fits the per-part allowance, but together they need more than the budget.
+        let bytes = many_rels(8, 64 * 1024);
+        assert!(relationship_kinds_within(&bytes, 256 * 1024).is_err());
+        let kinds = relationship_kinds_within(&bytes, 1024 * 1024).unwrap();
+        assert_eq!(kinds.get("custom").map(String::as_str), Some("custom"));
+    }
+}

crates/calc/src/eval.rs

@@ -325,6 +325,11 @@ impl<'h> Evaluator<'h> {
             Expr::Array(rows) => {
                 let h = rows.len();
                 let w = rows.first().map_or(0, Vec::len);
+                // A ragged literal is an error either way; one wide row and many empty ones must
+                // not reserve their rows-times-width product first.
+                if rows.iter().any(|row| row.len() != w) {
+                    return err(CellError::Value);
+                }
                 let mut data = Vec::with_capacity(h * w);
                 for row in rows {
                     for el in row {

crates/calc/src/eval/array.rs

@@ -86,6 +86,30 @@ pub fn zip2(a: &Value, b: &Value, f: impl Fn(&Value, &Value) -> Value) -> Value
     }
 }
 
+/// [`zip2`] that stops at the first cell `f` refuses (`None`), before the rest is built: the
+/// result grows as cells are made rather than being reserved for the whole broadcast up front.
+fn try_zip2(a: &Value, b: &Value, mut f: impl FnMut(&Value, &Value) -> Option<Value>) -> Option<Value> {
+    Some(match (a, b) {
+        (Value::Array(x), Value::Array(y)) => {
+            let rows = broadcast_dim(x.rows, y.rows);
+            let cols = broadcast_dim(x.cols, y.cols);
+            if broadcast_len(rows, cols).is_none() {
+                return Some(Value::Error(CellError::Num));
+            }
+            let mut data = Vec::new();
+            for r in 0..rows {
+                for c in 0..cols {
+                    data.push(f(&x.get_broadcast(r, c), &y.get_broadcast(r, c))?);
+                }
+            }
+            Value::from(Array { rows, cols, data })
+        }
+        (Value::Array(x), s) => Value::from(Array { rows: x.rows, cols: x.cols, data: x.data.iter().map(|v| f(v, s)).collect::<Option<_>>()? }),
+        (s, Value::Array(y)) => Value::from(Array { rows: y.rows, cols: y.cols, data: y.data.iter().map(|v| f(s, v)).collect::<Option<_>>()? }),
+        (x, y) => f(x, y)?,
+    })
+}
+
 /// Cell count of a `rows`×`cols` broadcast result, or `None` when it would exceed [`MAX_CELLS`].
 /// Each operand passes its own size cap, but their broadcast product can be far larger
 /// (`SEQUENCE(1048576)*SEQUENCE(1,16384)` is 17 billion cells), so it is checked before allocating.
@@ -135,10 +159,36 @@ 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 mut used = 0usize;
+    try_zip2(x, y, |a, b| {
+        let v = binary_scalar(BinOp::Concat, a, b, sys);
+        if let Value::Text(t) = &v {
+            used = used.saturating_add(t.len());
+            if used > budget {
+                return None;
+            }
+        }
+        Some(v)
+    })
+    .unwrap_or(Value::Error(CellError::Num))
+}
+
 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 +237,35 @@ 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, try_zip2};
+
+    /// The broadcast stops at the first refused cell: nothing after it is visited.
+    #[test]
+    fn a_refused_cell_stops_the_broadcast() {
+        let col = Value::from(Array::column((0..4_000).map(|i| Value::number(i as f64)).collect()));
+        let row = Value::from(Array { rows: 1, cols: 4_000, data: (0..4_000).map(|i| Value::number(i as f64)).collect() });
+        let mut calls = 0;
+        let r = try_zip2(&col, &row, |a, _| {
+            calls += 1;
+            (calls <= 10).then(|| a.clone())
+        });
+        assert_eq!((r, calls), (None, 11));
+    }
+
+    #[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/calc/src/recalc.rs

@@ -24,7 +24,7 @@ mod pass_host;
 #[cfg(test)]
 use graph::Intervals;
 pub use graph::{FxHasher, Graph, Key};
-use graph::{HashMap, HashSet, Node};
+use graph::{HashMap, HashSet, Node, Taken};
 use pass_host::{PassHost, spills_as_before};
 
 /// Calculation state kept beside a workbook.
@@ -292,17 +292,16 @@ impl Calc {
                 }
             }
         }
-        // Spill areas of changed anchors also change.
+        // Spill areas of changed anchors also change. They stay rectangles: one seed per spilled
+        // cell listed the formulas reading the area once per cell.
+        let mut areas: Vec<(usize, RangeRef)> = cleared;
         for &k in changed {
             if let Some(r) = wb.sheet(k.0).and_then(|s| s.spill_ranges.get(&k.1)) {
-                seeds.extend(r.iter().map(|c| (k.0, c)));
+                areas.push((k.0, *r));
             }
         }
-        for (si, r) in &cleared {
-            seeds.extend(r.iter().map(|c| (*si, c)));
-        }
         let t0 = prof_now();
-        let dirty = self.dirty_closure(wb, &seeds);
+        let dirty = self.dirty_closure(wb, &seeds, &areas);
         let t1 = prof_now();
         let n = dirty.len();
         self.run(wb, dirty, false);
@@ -311,16 +310,39 @@ impl Calc {
         }
     }
 
-    fn dirty_closure(&self, _wb: &Workbook, seeds: &[Key]) -> Vec<Key> {
+    /// The formulas to recalculate after `seeds` and every cell of `areas` changed: the seeds
+    /// that are formulas, and everything that reads them, directly or through other formulas.
+    fn dirty_closure(&self, wb: &Workbook, seeds: &[Key], areas: &[(usize, RangeRef)]) -> Vec<Key> {
         let mut seen: HashSet<Key> = HashSet::default();
         let mut queue: VecDeque<Key> = VecDeque::new();
+        // Each range-index entry is listed once in the whole walk: many changed cells under one
+        // broad reference (or many formulas inside one) would otherwise list every formula reading
+        // it once per cell, which squared the work.
+        let mut taken = Taken::default();
+        let mut deps = Vec::new();
         for k in seeds {
             if self.graph.nodes.contains_key(k) && seen.insert(*k) {
                 queue.push_back(*k);
             }
-            let mut deps = Vec::new();
-            self.graph.dependents(k.0, k.1, &mut deps);
-            for d in deps {
+            deps.clear();
+            self.graph.dependents_untaken(k.0, k.1, &mut taken, &mut deps);
+            for d in deps.drain(..) {
+                if seen.insert(d) {
+                    queue.push_back(d);
+                }
+            }
+        }
+        for &(si, r) in areas {
+            if let Some(sh) = wb.sheet(si) {
+                for (c, _) in sh.cells.iter_range(r) {
+                    if self.graph.nodes.contains_key(&(si, c)) && seen.insert((si, c)) {
+                        queue.push_back((si, c));
+                    }
+                }
+            }
+            deps.clear();
+            self.graph.dependents_of_range(si, r, &mut deps);
+            for d in deps.drain(..) {
                 if seen.insert(d) {
                     queue.push_back(d);
                 }
@@ -331,10 +353,9 @@ impl Calc {
                 queue.push_back(*k);
             }
         }
-        let mut deps = Vec::new();
         while let Some(k) = queue.pop_front() {
             deps.clear();
-            self.graph.dependents(k.0, k.1, &mut deps);
+            self.graph.dependents_untaken(k.0, k.1, &mut taken, &mut deps);
             for d in deps.drain(..) {
                 if seen.insert(d) {
                     queue.push_back(d);
@@ -411,7 +432,7 @@ impl Calc {
             if spill_changes.is_empty() {
                 break;
             }
-            dirty = self.dirty_closure(wb, &spill_changes);
+            dirty = self.dirty_closure(wb, &spill_changes, &[]);
         }
         // Loops among formulas the run did not evaluate stay listed while they are still formulas.
         // Iterative calculation reports none.
@@ -691,6 +712,149 @@ pub(crate) mod tests {
         assert!(visited < 64, "visited {visited} nodes for no match");
     }
 
+    #[test]
+    fn untaken_queries_list_each_interval_once_in_all() {
+        // 1,000 ranges over every row of 5,000: point queries at every row used to list all 1,000
+        // each time (5 million matches); sharing `taken`, each range is listed once in all.
+        let n = 5_000u32;
+        let mut iv: Intervals<u32> = Intervals::default();
+        for t in 0..1_000 {
+            iv.insert(0, n, t);
+        }
+        for r in 0..n {
+            iv.insert(r, r, 10_000 + r);
+        }
+        iv.settle();
+        let mut taken = Vec::new();
+        let mut listed = Vec::new();
+        for row in 0..=n + 3 {
+            iv.query_untaken(row, row, &mut taken, &mut |t| {
+                listed.push(*t);
+                true
+            });
+        }
+        listed.sort_unstable();
+        let want: Vec<u32> = (0..1_000).chain(10_000..10_000 + n).collect();
+        assert_eq!(listed, want);
+        // An entry the caller declines is offered again.
+        let mut taken = Vec::new();
+        let mut offered = 0;
+        for _ in 0..3 {
+            iv.query_untaken(7, 7, &mut taken, &mut |t| {
+                if *t == 10_007 {
+                    offered += 1;
+                }
+                *t != 10_007
+            });
+        }
+        assert_eq!(offered, 3);
+    }
+
+    #[test]
+    fn dirty_closure_matches_a_walk_of_every_cell() {
+        // Random formulas over single cells, narrow ranges and wide (over 64 columns) ranges, some
+        // removed or left unsettled: the closure equals the one found by listing every dependent
+        // of every changed cell, area cells included, as before `taken` and areas existed.
+        use super::{HashSet, Node};
+        use crate::eval::Area;
+        use std::collections::VecDeque;
+        let mut s = 0x2545_F491_4F6C_DD1D;
+        for case in 0..40 {
+            let mut wb = Workbook::new();
+            let mut calc = Calc::new();
+            let pick = |s: &mut u64, n: u64| (rng(s) % n) as u32;
+            let mut keys: Vec<Key> = Vec::new();
+            for _ in 0..300 {
+                let k = (0, CellRef::new(pick(&mut s, 120), pick(&mut s, 150)));
+                let mut areas = Vec::new();
+                for _ in 0..1 + pick(&mut s, 3) {
+                    let start = CellRef::new(pick(&mut s, 120), pick(&mut s, 150));
+                    let end = match pick(&mut s, 3) {
+                        0 => start,
+                        1 => CellRef::new(start.row + pick(&mut s, 40), start.col + pick(&mut s, 5)),
+                        _ => CellRef::new(start.row + pick(&mut s, 20), start.col + 65 + pick(&mut s, 30)),
+                    };
+                    areas.push(Area { sheet: 0, range: RangeRef::new(start, end) });
+                }
+                if let Some(sh) = wb.sheet_mut(0) {
+                    sh.cells.set(k.1, Cell::formula(Formula::new("=1")));
+                }
+                calc.graph.insert(k, Node { areas, dynamic: false });
+                keys.push(k);
+                if rng(&mut s).is_multiple_of(7) {
+                    calc.graph.settle();
+                }
+            }
+            for _ in 0..30 {
+                let k = keys[(rng(&mut s) % keys.len() as u64) as usize];
+                calc.graph.remove(k);
+                if let Some(sh) = wb.sheet_mut(0) {
+                    sh.cells.remove(k.1);
+                }
+            }
+            if case % 2 == 0 {
+                calc.graph.settle();
+            }
+            let seeds: Vec<Key> = (0..1 + pick(&mut s, 25)).map(|_| (0, CellRef::new(pick(&mut s, 140), pick(&mut s, 220)))).collect();
+            let areas: Vec<(usize, RangeRef)> = (0..pick(&mut s, 3))
+                .map(|_| {
+                    let start = CellRef::new(pick(&mut s, 120), pick(&mut s, 150));
+                    (0, RangeRef::new(start, CellRef::new(start.row + pick(&mut s, 30), start.col + pick(&mut s, 80))))
+                })
+                .collect();
+            let got: HashSet<Key> = calc.dirty_closure(&wb, &seeds, &areas).into_iter().collect();
+            // The walk before: every area cell is a seed, and every cell lists all its dependents.
+            let mut all = seeds.clone();
+            for (si, r) in &areas {
+                all.extend(r.iter().map(|c| (*si, c)));
+            }
+            let mut want: HashSet<Key> = HashSet::default();
+            let mut queue: VecDeque<Key> = VecDeque::new();
+            let mut deps = Vec::new();
+            for k in &all {
+                if calc.graph.nodes.contains_key(k) && want.insert(*k) {
+                    queue.push_back(*k);
+                }
+                deps.clear();
+                calc.graph.dependents(k.0, k.1, &mut deps);
+                queue.extend(deps.iter().copied().filter(|d| want.insert(*d)));
+            }
+            while let Some(k) = queue.pop_front() {
+                deps.clear();
+                calc.graph.dependents(k.0, k.1, &mut deps);
+                queue.extend(deps.iter().copied().filter(|d| want.insert(*d)));
+            }
+            assert_eq!(got, want, "case {case}");
+        }
+    }
+
+    #[test]
+    fn clearing_a_spill_recalculates_formulas_reading_it_once_each() {
+        // 300 formulas read the area an anchor spills into; clearing the anchor changes all of it
+        // and every one of them is recalculated (they were listed once per spilled cell).
+        let mut wb = Workbook::new();
+        let mut calc = Calc::new();
+        let set = |wb: &mut Workbook, calc: &mut Calc, at: CellRef, input: &str| {
+            if let Some(sh) = wb.sheet_mut(0) {
+                if input.is_empty() {
+                    sh.cells.remove(at);
+                } else {
+                    sh.cells.set(at, Cell::formula(Formula::new(input)));
+                }
+            }
+            calc.cells_changed(wb, &[(0, at)]);
+        };
+        set(&mut wb, &mut calc, CellRef::new(0, 0), "=SEQUENCE(2000)");
+        for r in 0..300 {
+            set(&mut wb, &mut calc, CellRef::new(r, 2), "=COUNT(A1:A2000)");
+        }
+        assert_eq!(wb.sheet(0).map(|s| s.value(CellRef::new(299, 2))), Some(Value::Number(2000.0)));
+        set(&mut wb, &mut calc, CellRef::new(0, 0), "");
+        for r in 0..300 {
+            assert_eq!(wb.sheet(0).map(|s| s.value(CellRef::new(r, 2))), Some(Value::Number(0.0)), "row {r}");
+        }
+    }
+
     /// `rows` rows of six numbers (E:J) and `=SUM(E{r}:J{r})` in K.
     fn sum_rows(rows: u32) -> Workbook {
         let mut wb = Workbook::new();

crates/calc/src/recalc/graph.rs

@@ -151,6 +151,54 @@ impl<T: Copy + Ord> Intervals<T> {
         self.walk(1, 0, self.max_end.len() / 2, p, a, f)
     }
 
+    /// [`Intervals::query`] that skips entries an earlier call with the same `taken` already
+    /// took (and whole subtrees of them), so that a series of queries lists each interval once in
+    /// all. `f` answers whether it took the entry; one it declines is offered again later.
+    /// `taken` belongs to this index as it is now; start it empty. Pending insertions (a few at
+    /// most after [`Intervals::settle`]) are offered every time.
+    pub(super) fn query_untaken(&self, a: u32, b: u32, taken: &mut Vec<bool>, f: &mut dyn FnMut(&T) -> bool) {
+        for it in &self.pending {
+            if it.0 <= b && it.1 >= a {
+                f(&it.2);
+            }
+        }
+        let p = self.items.partition_point(|it| it.0 <= b);
+        if p == 0 {
+            return;
+        }
+        if taken.len() != self.max_end.len() {
+            *taken = vec![false; self.max_end.len()];
+        }
+        self.walk_untaken(1, 0, self.max_end.len() / 2, p, a, taken, f);
+    }
+
+    /// Returns whether everything under `node` has now been reported (or is dead).
+    #[allow(clippy::too_many_arguments)]
+    fn walk_untaken(&self, node: usize, lo: usize, hi: usize, p: usize, a: u32, taken: &mut [bool], f: &mut dyn FnMut(&T) -> bool) -> bool {
+        if taken.get(node).copied().unwrap_or(true) {
+            return true;
+        }
+        if lo >= p || self.max_end.get(node).is_none_or(|m| *m < a) {
+            return false;
+        }
+        let done = if hi - lo <= 1 {
+            match (self.items.get(lo), self.dead.get(lo)) {
+                (Some(it), Some(false)) if it.1 >= a => f(&it.2),
+                (Some(_), Some(true)) => true,
+                _ => false,
+            }
+        } else {
+            let mid = lo + (hi - lo) / 2;
+            let left = self.walk_untaken(2 * node, lo, mid, p, a, taken, f);
+            let right = self.walk_untaken(2 * node + 1, mid, hi, p, a, taken, f);
+            left && right
+        };
+        if done && let Some(slot) = taken.get_mut(node) {
+            *slot = true;
+        }
+        done
+    }
+
     fn walk(&self, node: usize, lo: usize, hi: usize, p: usize, a: u32, f: &mut dyn FnMut(&T)) -> usize {
         if lo >= p || self.max_end.get(node).is_none_or(|m| *m < a) {
             return 1;
@@ -168,6 +216,13 @@ impl<T: Copy + Ord> Intervals<T> {
     }
 }
 
+/// Range-index entries one dependency walk has already listed (see [`Graph::dependents_untaken`]).
+#[derive(Default)]
+pub(super) struct Taken {
+    cols: HashMap<(usize, u32), Vec<bool>>,
+    wide: HashMap<usize, Vec<bool>>,
+}
+
 #[derive(Clone, Debug, Default)]
 pub struct Graph {
     pub(super) nodes: HashMap<Key, Node>,
@@ -302,6 +357,32 @@ impl Graph {
         }
     }
 
+    /// [`Graph::dependents`] leaving out the formulas whose range reads an earlier call with the
+    /// same `taken` already listed. A walk over many changed cells that a few broad ranges cover
+    /// then lists those formulas once, instead of once per cell (which squared the work). The
+    /// graph must not change while `taken` is in use.
+    pub(super) fn dependents_untaken(&self, sheet: usize, c: CellRef, taken: &mut Taken, out: &mut Vec<Key>) {
+        if let Some(v) = self.cell_deps.get(&(sheet, c)) {
+            out.extend(v.iter().copied());
+        }
+        if let Some(v) = self.col_deps.get(&(sheet, c.col)) {
+            v.query_untaken(c.row, c.row, taken.cols.entry((sheet, c.col)).or_default(), &mut |k| {
+                out.push(*k);
+                true
+            });
+        }
+        if let Some(v) = self.wide_deps.get(&sheet) {
+            // A wide entry is taken once it covers the cell's column too.
+            v.query_untaken(c.row, c.row, taken.wide.entry(sheet).or_default(), &mut |(c0, c1, k)| {
+                let hit = *c0 <= c.col && c.col <= *c1;
+                if hit {
+                    out.push(*k);
+                }
+                hit
+            });
+        }
+    }
+
     /// Formulas that read any cell of `range` (a formula can be listed more than once).
     pub fn dependents_of_range(&self, sheet: usize, range: RangeRef, out: &mut Vec<Key>) {
         if range.count() <= 4096 {

crates/chart/src/render/cartesian.rs

@@ -96,8 +96,11 @@ fn series_spans(data: &ChartData, fams: &[Fam], sec: &[bool], ncat: usize) -> Ve
         } else {
             None
         };
-        let mut row = Vec::with_capacity(ncat);
-        for j in 0..ncat {
+        // A series without values has no spans: 255 empty series over 20,000 categories would
+        // otherwise fill ~5 million entries.
+        let n = if s.values.is_empty() { 0 } else { ncat };
+        let mut row = Vec::with_capacity(n);
+        for j in 0..n {
             let v = s.values.get(j).copied().flatten();
             let span = match (si.and_then(|p| stacks.get_mut(p)), fam) {
                 (Some((_, pos, neg)), Fam::ColStack | Fam::Col100) => v.and_then(|v| {
@@ -450,3 +453,18 @@ pub(super) fn scatter(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
     }
     draw_trend_labels(ctx, plot, &trend_labels);
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn empty_series_get_no_span_entries() {
+        let empty = SeriesData::default();
+        let full = SeriesData { values: vec![Some(1.0); 3], ..SeriesData::default() };
+        let data = ChartData { series: vec![empty.clone(), full, empty], ..ChartData::default() };
+        let fams = [Fam::Col; 3];
+        let spans = series_spans(&data, &fams, &[false; 3], MAX_CATS);
+        assert_eq!(spans.iter().map(Vec::len).collect::<Vec<_>>(), [0, MAX_CATS, 0]);
+    }
+}

crates/chart/src/render/kinds.rs

@@ -203,12 +203,11 @@ pub(super) fn pie(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx, inne
 
 // ---------------------------------------------------------------- treemap
 
-fn worst(row: &[f64], side: f64) -> f64 {
-    let s: f64 = row.iter().sum();
+/// Worst aspect ratio of a row with the given sum, smallest and largest area.
+fn worst(s: f64, mn: f64, mx: f64, side: f64) -> f64 {
     if s <= 0.0 || side <= 0.0 {
         return f64::INFINITY;
     }
-    let (mn, mx) = row.iter().fold((f64::INFINITY, 0.0f64), |(a, b), v| (a.min(*v), b.max(*v)));
     let s2 = s * s;
     let w2 = side * side;
     (w2 * mx / s2).max(s2 / (w2 * mn))
@@ -225,6 +224,8 @@ fn squarify(items: &[(usize, f64)], r: Bx) -> Vec<(usize, Bx)> {
     let mut out = Vec::with_capacity(items.len());
     let mut rem = r;
     let mut row: Vec<(usize, f64)> = Vec::new();
+    // The row's sum, smallest and largest area, kept as items join so each step is O(1).
+    let (mut sum, mut mn, mut mx) = (0.0f64, f64::INFINITY, 0.0f64);
     let mut i = 0;
     let layout = |row: &[(usize, f64)], rem: &mut Bx, out: &mut Vec<(usize, Bx)>| {
         let s: f64 = row.iter().map(|x| x.1).sum();
@@ -256,15 +257,14 @@ fn squarify(items: &[(usize, f64)], r: Bx) -> Vec<(usize, Bx)> {
     while let Some(&(j, v)) = items.get(i) {
         let a = v * scale;
         let side = rem.w.min(rem.h) as f64;
-        let cur: Vec<f64> = row.iter().map(|x| x.1).collect();
-        let mut with = cur.clone();
-        with.push(a);
-        if row.is_empty() || worst(&with, side) <= worst(&cur, side) {
+        if row.is_empty() || worst(sum + a, mn.min(a), mx.max(a), side) <= worst(sum, mn, mx, side) {
             row.push((j, a));
+            (sum, mn, mx) = (sum + a, mn.min(a), mx.max(a));
             i += 1;
         } else {
             layout(&row, &mut rem, &mut out);
             row.clear();
+            (sum, mn, mx) = (0.0, f64::INFINITY, 0.0);
         }
     }
     if !row.is_empty() {
@@ -279,6 +279,7 @@ pub(super) fn treemap(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
         s.values.iter().take(MAX_MARKERS).enumerate().filter_map(|(j, v)| v.filter(|v| *v > 0.0).map(|v| (j, v))).collect();
     items.sort_by(|a, b| b.1.total_cmp(&a.1));
     let f = Fmt::new(&s.number_format);
+    let value_of: std::collections::HashMap<usize, f64> = items.iter().copied().collect();
     for (j, b) in squarify(&items, area) {
         let fill = point_color(data, j);
         ctx.rect(b.x, b.y, b.w, b.h, fill, Some((WHITE, 1.5)));
@@ -286,7 +287,7 @@ pub(super) fn treemap(ctx: &mut Ctx, chart: &Chart, data: &ChartData, area: Bx)
             let name = ctx.fit(&cat_label(data, j), LABEL_SIZE, b.w - 8.0);
             ctx.text(b.x + 4.0, b.y + 4.0, &name, LABEL_SIZE, on(fill), (HAlign::Left, VAlign::Top));
             if chart.data_labels && b.h > LABEL_SIZE * 3.2 {
-                let v = items.iter().find(|x| x.0 == j).map(|x| x.1).unwrap_or(0.0);
+                let v = value_of.get(&j).copied().unwrap_or(0.0);
                 let t = ctx.fit(&f.format(v, None), LABEL_SIZE, b.w - 8.0);
                 ctx.text(b.x + 4.0, b.y + 4.0 + LABEL_SIZE * 1.4, &t, LABEL_SIZE, on(fill), (HAlign::Left, VAlign::Top));
             }

crates/engine/src/cmd.rs

@@ -503,10 +503,14 @@ pub(crate) fn refuse_unless_allowed(s: &Session, sheet: usize, what: &str, pick:
 pub(crate) fn locked_cell_error(sh: &gridcraft_model::Sheet, c: CellRef, unlocked: &[(String, String)]) -> Option<String> {
     let mut needs_password = None;
     for r in sh.edit_ranges.iter().filter(|r| r.contains(c)) {
-        if r.password.is_none() || unlocked.iter().any(|(s, t)| *s == sh.name && *t == r.title) {
+        // A range limited to Windows users or groups (a security descriptor) can't be checked
+        // here, so without a password it stays locked rather than opening to every editor.
+        if (r.password.is_none() && r.security_descriptor.is_none()) || unlocked.iter().any(|(s, t)| *s == sh.name && *t == r.title) {
             return None;
         }
-        needs_password.get_or_insert(r.title.as_str());
+        if r.password.is_some() {
+            needs_password.get_or_insert(r.title.as_str());
+        }
     }
     Some(match needs_password {
         Some(t) => format!("The range \"{t}\" needs its password before it can be changed (Review › Allow Edit Ranges)."),

crates/engine/src/cmd/data/filter.rs

@@ -270,6 +270,7 @@ pub(crate) fn apply_filter(wb: &mut Workbook, sheet: usize) {
 
 pub(super) fn clear_filter(s: &mut Session, _: &Json) -> Result<Json> {
     let sheet = s.doc()?.wb.active_sheet();
+    crate::cmd::refuse_unless_allowed(s, sheet, "Filtering", |p| p.autofilter)?;
     edit(s, |cx| {
         let sh = cx.sheet_mut(sheet)?;
         if let Some(a) = sh.autofilter.as_mut() {
@@ -283,6 +284,7 @@ pub(super) fn clear_filter(s: &mut Session, _: &Json) -> Result<Json> {
 
 pub(super) fn reapply(s: &mut Session, _: &Json) -> Result<Json> {
     let sheet = s.doc()?.wb.active_sheet();
+    crate::cmd::refuse_unless_allowed(s, sheet, "Filtering", |p| p.autofilter)?;
     edit(s, |cx| {
         apply_filter(&mut cx.wb, sheet);
         cx.structural = true;

crates/engine/src/cmd/data/grouping.rs

@@ -21,6 +21,15 @@ fn outline_lines(s: &Session, p: &Json) -> Result<(bool, u32, u32)> {
     }
 }
 
+/// Outline commands change line visibility and grouping: a protected sheet must allow formatting that axis.
+fn refuse_unless_outline_allowed(s: &Session, sheet: usize, rows: bool) -> Result<()> {
+    if rows {
+        crate::cmd::refuse_unless_allowed(s, sheet, "Formatting rows", |p| p.format_rows)
+    } else {
+        crate::cmd::refuse_unless_allowed(s, sheet, "Formatting columns", |p| p.format_columns)
+    }
+}
+
 pub(super) fn group(s: &mut Session, p: &Json, on: bool) -> Result<Json> {
     let si = target_sheet(s, p)?;
     // The selection belongs to the active sheet, so another sheet needs its lines.
@@ -28,6 +37,7 @@ pub(super) fn group(s: &mut Session, p: &Json, on: bool) -> Result<Json> {
         return Err(bad(if on { "data.group" } else { "data.ungroup" }, "missing `rows` or `cols`: the selection is on the active sheet"));
     }
     let (rows, a, b) = outline_lines(s, p)?;
+    refuse_unless_outline_allowed(s, si, rows)?;
     edit(s, |cx| {
         let sh = cx.sheet_mut(si)?;
         let before = outline::summary_before(sh, rows);
@@ -58,6 +68,7 @@ pub(super) fn group(s: &mut Session, p: &Json, on: bool) -> Result<Json> {
 /// + button, saved to XLSX); showing keeps inner groups that were collapsed on their own collapsed.
 pub(super) fn detail(s: &mut Session, p: &Json, hide: bool) -> Result<Json> {
     let (rows, a, b) = outline_lines(s, p)?;
+    refuse_unless_outline_allowed(s, s.doc()?.wb.active_sheet(), rows)?;
     let want = p.get("level").and_then(Json::as_u64).map(|l| l.min(outline::MAX_LEVEL as u64) as u8);
     edit(s, |cx| {
         let si = cx.sheet_index();
@@ -123,6 +134,12 @@ pub(super) fn show_levels(s: &mut Session, p: &Json) -> Result<Json> {
             msg: "give `rows` or `cols`: the outline level to show (1 = top-level summaries only)".into(),
         });
     }
+    let active = s.doc()?.wb.active_sheet();
+    for (n, is_rows) in [(rows, true), (cols, false)] {
+        if n.is_some() {
+            refuse_unless_outline_allowed(s, active, is_rows)?;
+        }
+    }
     edit(s, |cx| {
         let si = cx.sheet_index();
         let sh = cx.sheet_mut(si)?;

crates/engine/src/cmd/format/sizes.rs

@@ -9,6 +9,17 @@ use super::{
 /// sheet is `sheet`, else the prefix, else the active one. The selection belongs to the active
 /// sheet, so another sheet needs explicit lines.
 fn line_targets(s: &Session, p: &Json, rows: bool) -> Result<(usize, Vec<(u32, u32)>)> {
+    let (sheet, lines) = resolve_lines(s, p, rows)?;
+    // Sizes and visibility are formatting of the line, which a protected sheet must allow.
+    if rows {
+        crate::cmd::refuse_unless_allowed(s, sheet, "Formatting rows", |p| p.format_rows)?;
+    } else {
+        crate::cmd::refuse_unless_allowed(s, sheet, "Formatting columns", |p| p.format_columns)?;
+    }
+    Ok((sheet, lines))
+}
+
+fn resolve_lines(s: &Session, p: &Json, rows: bool) -> Result<(usize, Vec<(u32, u32)>)> {
     let key = if rows { "rows" } else { "cols" };
     let mut sheet = target_sheet(s, p)?;
     if let Some(t) = str_param(p, key) {

crates/engine/src/cmd/insert.rs

@@ -1100,6 +1100,10 @@ fn insert_picture(s: &mut Session, p: &Json) -> Result<Json> {
         .unwrap_or_else(|| if data.starts_with(&[0x89, b'P', b'N', b'G']) { "image/png".into() } else { "image/jpeg".into() });
     let (w, h) = crate::io::image_size(&data).unwrap_or((320, 240));
     let d = s.doc()?;
+    // Sheet protection locks drawing objects, as for a text box's text.
+    if d.wb.active().is_some_and(|sh| sh.is_protected()) {
+        return Err(EngineError::Other(PROTECTED.into()));
+    }
     let id = d.wb.next_object_id();
     let at = cell_param(s, p, "at")?.unwrap_or(d.selection.active);
     let scale = (640.0 / w.max(1) as f32).min(1.0);

crates/engine/src/cmd/pivot/create.rs

@@ -67,9 +67,6 @@ fn field_list(v: Option<&Json>) -> Vec<Json> {
 }
 
 pub(super) fn insert_pivot(s: &mut Session, p: &Json) -> Result<Json> {
-    if s.doc()?.wb.protected_structure && matches!(str_param(p, "destination"), None | Some("new")) {
-        return Err(other("The workbook is protected and cannot be changed."));
-    }
     let source = source_param(s, p)?;
     let active = s.doc()?.wb.active_sheet();
     // Validate the source now (header names, size).
@@ -98,6 +95,10 @@ pub(super) fn insert_pivot(s: &mut Session, p: &Json) -> Result<Json> {
         let at = RangeRef::parse(body).map(|r| r.start).ok_or_else(|| bad("insert.pivotTable", format!("not a cell: `{dest}`")))?;
         Some((si, at))
     };
+    // Decided on the resolved destination: `New`, ` new ` and an empty one all make a sheet.
+    if target.is_none() && s.doc()?.wb.protected_structure {
+        return Err(other("The workbook is protected and cannot be changed."));
+    }
     let replace = bool_param(p, "replace").unwrap_or(false);
     let rows = field_list(p.get("rows"));
     let columns = field_list(p.get("columns"));

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

@@ -168,6 +168,19 @@ fn filters_and_report_filter_rows() {
     assert!(s.execute("pivot.filter", json!({"field": "Product", "selected": []})).is_err());
 }
 
+/// A selection of the most labels allowed (100,000) is looked up once per record, not scanned: the
+/// report still filters case-insensitively.
+#[test]
+fn a_huge_filter_selection_is_matched_through_a_set() {
+    let mut s = sales();
+    s.execute("insert.pivotTable", json!({"rows": ["Product"], "values": ["Sales"], "filters": ["Region"]})).unwrap();
+    let mut selected: Vec<String> = (0..99_999).map(|i| format!("Region {i}")).collect();
+    selected.push("EAST".into());
+    s.execute("pivot.filter", json!({"field": "Region", "selected": selected})).unwrap();
+    let gt = find_row(&s, "Grand Total").unwrap();
+    assert_eq!(val(&s, &CellRef::new(gt, 1).a1()), Value::Number(415.0));
+}
+
 #[test]
 fn show_values_as() {
     let mut s = sales();

crates/engine/src/cmd/print/header_footer.rs

@@ -153,6 +153,17 @@ pub struct HfSection {
     pub size: Option<f32>,
 }
 
+/// Most bytes one section's expanded text may hold. A code like `&A` adds the whole sheet name
+/// (or file path) each time it appears, and a JSON workbook's names have no length limit.
+const MAX_SECTION_BYTES: usize = 64 * 1024;
+
+/// Appends `s` unless the section would pass [`MAX_SECTION_BYTES`]; what doesn't fit is left out.
+fn push_field(text: &mut String, s: &str) {
+    if text.len().saturating_add(s.len()) <= MAX_SECTION_BYTES {
+        text.push_str(s);
+    }
+}
+
 /// Expands a header/footer string into its left, centre and right sections.
 pub fn expand_header_footer(spec: &str, cx: &HfContext) -> [HfSection; 3] {
     let mut out: [HfSection; 3] = Default::default();
@@ -187,14 +198,14 @@ pub fn expand_header_footer(spec: &str, cx: &HfContext) -> [HfSection; 3] {
                         i += 1 + digits.len();
                     }
                 }
-                sec.text.push_str(&n.to_string());
+                push_field(&mut sec.text, &n.to_string());
             }
-            'N' | 'n' => sec.text.push_str(&cx.pages.to_string()),
-            'D' | 'd' => sec.text.push_str(&cx.date),
-            'T' | 't' => sec.text.push_str(&cx.time),
-            'A' | 'a' => sec.text.push_str(&cx.sheet),
-            'F' | 'f' => sec.text.push_str(&cx.file),
-            'Z' | 'z' => sec.text.push_str(&cx.path),
+            'N' | 'n' => push_field(&mut sec.text, &cx.pages.to_string()),
+            'D' | 'd' => push_field(&mut sec.text, &cx.date),
+            'T' | 't' => push_field(&mut sec.text, &cx.time),
+            'A' | 'a' => push_field(&mut sec.text, &cx.sheet),
+            'F' | 'f' => push_field(&mut sec.text, &cx.file),
+            'Z' | 'z' => push_field(&mut sec.text, &cx.path),
             '&' => sec.text.push('&'),
             'B' | 'b' => sec.bold = !sec.bold,
             'I' | 'i' => sec.italic = !sec.italic,

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

@@ -414,6 +414,12 @@ fn pdf_contains_text_and_header_codes_expand() {
     assert_eq!(r.text, "P4/9 9:00 AM");
     assert_eq!(expand_header_footer("plain", &cx)[1].text, "plain");
     assert_eq!(expand_header_footer("&", &cx)[1].text, "");
+    // A megabyte sheet name repeated by 5,000 `&A` codes stops at the section's 64 KiB.
+    let long = HfContext { sheet: "S".repeat(1024 * 1024), ..cx };
+    let [_, c, _] = expand_header_footer(&"&A".repeat(5_000), &long);
+    assert!(c.text.is_empty(), "the name alone is over the limit");
+    let short = HfContext { sheet: "S".repeat(1000), ..Default::default() };
+    assert_eq!(expand_header_footer(&"&A".repeat(5_000), &short)[1].text.len(), 65_000);
 }
 
 #[test]
@@ -695,6 +701,79 @@ fn bands_unit() {
     assert!(w.len() > 2);
 }
 
+/// The wrapper `wrap_lines` replaced, re-measuring strings, as the reference for its lines.
+fn wrap_lines_remeasuring(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
+    let mut out = Vec::new();
+    for para in text.split('\n') {
+        let mut line = String::new();
+        for word in para.split(' ') {
+            let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
+            if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
+                line = cand;
+            } else {
+                out.push(std::mem::take(&mut line));
+                line = word.to_string();
+            }
+            while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
+                let chars: Vec<char> = line.chars().collect();
+                let (mut lo, mut hi) = (1usize, chars.len());
+                while lo < hi {
+                    let mid = lo + (hi - lo).div_ceil(2);
+                    let cut: String = chars[..mid].iter().collect();
+                    if gridcraft_pdf::text_width(font, size, &cut) <= width {
+                        lo = mid;
+                    } else {
+                        hi = mid - 1;
+                    }
+                }
+                if lo == chars.len() {
+                    break;
+                }
+                out.push(chars[..lo].iter().collect());
+                line = chars[lo..].iter().collect();
+            }
+            if out.len() > 2000 {
+                return out;
+            }
+        }
+        out.push(line);
+    }
+    out
+}
+
+#[test]
+fn wrap_lines_matches_the_remeasuring_wrapper() {
+    let texts = [
+        "the quick brown fox jumps",
+        "Supercalifragilistic",
+        "a  b   c\n\nverylongwordthatneedsbreaking short\nend ",
+        "Wide WWWWWWWWWW words, iiiiiiii narrow ones; mixed MMMMiiiiMMMM",
+        "€ ü ß — unicode Ünïcödé text",
+        "",
+        " ",
+    ];
+    for text in texts {
+        for font in [Font::Helvetica, Font::HelveticaBold, Font::Courier] {
+            for (size, width) in [(10.0, 50.0), (10.0, 20.0), (11.0, 1.0), (8.0, 300.0), (12.0, 0.0)] {
+                assert_eq!(wrap_lines(text, font, size, width), wrap_lines_remeasuring(text, font, size, width), "{text:?} {font:?} {size} {width}");
+            }
+        }
+    }
+}
+
+#[test]
+fn wrapping_a_long_word_in_a_narrow_box_stops_at_the_line_limit() {
+    // One character per line: the old wrapper re-measured and copied the rest of the word for
+    // each of the 100,000 lines before checking the limit.
+    let word = "w".repeat(100_000);
+    let lines = wrap_lines(&word, Font::Helvetica, 10.0, 1.0);
+    assert!(lines.len() <= 2002, "{}", lines.len());
+    assert!(lines.iter().all(|l| l == "w"));
+    // A long paragraph in a very wide box is one line.
+    let para = vec!["word"; 50_000].join(" ");
+    assert_eq!(wrap_lines(&para, Font::Helvetica, 10.0, 1.0e9), vec![para.clone()]);
+}
+
 #[test]
 fn center_across_spans_following_empty_center_across_cells() {
     let mut styles = StyleTable::default();

crates/engine/src/cmd/print/text.rs

@@ -3,42 +3,57 @@ use super::{CellRef, Color, Font, HAlign, MAX_COLS, Page, Point, RangeRef, Sheet
 
 const PAD_PX: f32 = 2.0;
 
+/// Most lines [`wrap_lines`] returns (it may return one more, the rest of a paragraph).
+const MAX_WRAP_LINES: usize = 2000;
+
 /// Word-wraps `text` to `width` points.
+///
+/// Widths are kept as running sums of glyph widths (the sum `text_width` makes), so each
+/// character is measured once: re-measuring the line for every word, or the rest of an
+/// over-long word for every piece cut from it, made a long paragraph or word quadratic.
 pub(super) fn wrap_lines(text: &str, font: Font, size: f32, width: f32) -> Vec<String> {
+    let units_of = |s: &str| -> u64 { s.chars().map(|c| u64::from(font.char_width(c))).sum() };
+    let fits = |units: u64| units as f32 * size / 1000.0 <= width;
+    let space = units_of(" ");
     let mut out = Vec::new();
     for para in text.split('\n') {
         let mut line = String::new();
+        let mut line_units: u64 = 0;
         for word in para.split(' ') {
-            let cand = if line.is_empty() { word.to_string() } else { format!("{line} {word}") };
-            if line.is_empty() || gridcraft_pdf::text_width(font, size, &cand) <= width {
-                line = cand;
+            let word_units = units_of(word);
+            if line.is_empty() {
+                line.push_str(word);
+                line_units = word_units;
+            } else if fits(line_units + space + word_units) {
+                line.push(' ');
+                line.push_str(word);
+                line_units += space + word_units;
             } else {
                 out.push(std::mem::take(&mut line));
-                line = word.to_string();
+                line.push_str(word);
+                line_units = word_units;
             }
-            // Break a single over-long word by characters. The cut that fits is found by binary
-            // search (each try measures one candidate prefix), so an over-long word costs
-            // O(n log n) measurements instead of re-measuring the whole cut per character for
-            // every emitted line (`a` × 100k pasted text would be cubic worst case).
-            while gridcraft_pdf::text_width(font, size, &line) > width && line.chars().count() > 1 {
-                let chars: Vec<char> = line.chars().collect();
-                let (mut lo, mut hi) = (1usize, chars.len());
-                while lo < hi {
-                    let mid = lo + (hi - lo).div_ceil(2);
-                    let cut: String = chars[..mid].iter().collect();
-                    if gridcraft_pdf::text_width(font, size, &cut) <= width {
-                        lo = mid;
-                    } else {
-                        hi = mid - 1;
+            // Break a single over-long word by characters: each piece is the longest that fits
+            // (at least one character).
+            if !fits(line_units) && line.chars().nth(1).is_some() {
+                let mut piece = String::new();
+                let mut units: u64 = 0;
+                for c in line.chars() {
+                    let w = u64::from(font.char_width(c));
+                    if !piece.is_empty() && !fits(units + w) {
+                        out.push(std::mem::take(&mut piece));
+                        units = 0;
+                        if out.len() > MAX_WRAP_LINES {
+                            return out;
+                        }
                     }
+                    piece.push(c);
+                    units += w;
                 }
-                if lo == chars.len() {
-                    break;
-                }
-                out.push(chars[..lo].iter().collect());
-                line = chars[lo..].iter().collect();
+                line = piece;
+                line_units = units;
             }
-            if out.len() > 2000 {
+            if out.len() > MAX_WRAP_LINES {
                 return out;
             }
         }

crates/engine/src/fill.rs

@@ -575,20 +575,9 @@ pub fn series(cx: &mut Ctx, sheet: usize, options: SeriesOptions<'_>) -> Result<
                     match (unit, d) {
                         ("month", Some(_)) => (step as i64).checked_mul(i as i64).and_then(|m| add_months_clamped(sys, start, m)).unwrap_or(v),
                         ("year", Some(_)) => (step as i64).checked_mul(i as i64 * 12).and_then(|m| add_months_clamped(sys, start, m)).unwrap_or(v),
-                        ("weekday", Some(_)) => {
-                            let mut n = v;
-                            let mut left = step.abs() as i64;
-                            while left > 0 {
-                                n += step.signum();
-                                let Some(day) = datetime_from_serial(sys, n) else {
-                                    return Err(crate::EngineError::Other("The weekday series runs past the supported date range.".into()));
-                                };
-                                if day.weekday != 0 && day.weekday != 6 {
-                                    left -= 1;
-                                }
-                            }
-                            n
-                        }
+                        // Whole weeks at a time: a huge step costs no more than a small one.
+                        ("weekday", Some(_)) => add_weekdays(sys, v, step as i64)
+                            .ok_or_else(|| crate::EngineError::Other("The weekday series runs past the supported date range.".into()))?,
                         _ => v + step,
                     }
                 }

crates/engine/src/io.rs

@@ -907,12 +907,6 @@ const MAX_READ_BYTES: u64 = 2 * 1024 * 1024 * 1024;
 pub fn read_file(path: &str) -> Result<Vec<u8>> {
     use std::io::Read;
     script_sandbox_check(path)?;
-    // Checked before opening: opening a FIFO nobody writes to blocks the calling (GUI) thread.
-    // shortcut: a FIFO swapped in between this check and the open still blocks; close that with
-    // O_NONBLOCK when the crate takes a libc dependency.
-    if !std::fs::metadata(path).map_err(|e| EngineError::Other(format!("{path}: {e}")))?.is_file() {
-        return Err(EngineError::Other(format!("{path}: only regular files can be opened")));
-    }
     let f = std::fs::File::open(path).map_err(|e| EngineError::Other(format!("{path}: {e}")))?;
     // A symlink to an endless device reports length 0 but streams forever, so metadata
     // alone never bounds the read: require a real file and cap the bytes actually taken.
@@ -944,37 +938,18 @@ pub fn write_file(path: &str, bytes: &[u8]) -> Result<()> {
     // link's target; and it inherits the destination's access restrictions, so saving a
     // private workbook doesn't widen who can read it.
     let tmp = format!("{path}.sctmp");
-    let prior_meta = std::fs::metadata(path).ok();
-    let prior = prior_meta.as_ref().map(std::fs::Metadata::permissions);
+    let prior = std::fs::metadata(path).ok().map(|m| m.permissions());
     let mut opts = std::fs::OpenOptions::new();
     opts.write(true).create_new(true);
-    // Over an existing file the replacement starts owner-only, whatever the umask: its group is
-    // still the saving user's primary one until it is changed below, and a member of that group
-    // must not be able to open it (and keep the descriptor) before then.
     #[cfg(unix)]
-    if prior.is_some() {
-        use std::os::unix::fs::OpenOptionsExt;
-        opts.mode(0o600);
+    if let Some(p) = &prior {
+        use std::os::unix::fs::{OpenOptionsExt, PermissionsExt};
+        opts.mode(p.mode());
     }
     let mut f = opts.open(&tmp).map_err(|e| {
         let _ = std::fs::remove_file(&tmp);
         EngineError::Other(format!("{path}: {e}"))
     })?;
-    // The replacement belongs to the saving user's primary group: restore the old file's group and
-    // then its mode. When the group can't be restored its access is dropped rather than handed to a
-    // different group; failing to read that back is a failed save.
-    #[cfg(unix)]
-    if let Some(m) = &prior_meta {
-        use std::os::unix::fs::{MetadataExt, PermissionsExt};
-        let _ = std::os::unix::fs::fchown(&f, None, Some(m.gid()));
-        let group_kept = f.metadata().map(|now| now.gid() == m.gid()).map_err(|e| {
-            let _ = std::fs::remove_file(&tmp);
-            EngineError::Other(format!("{path}: {e}"))
-        })?;
-        // Best effort: a file system that can't change modes keeps the owner-only one. Without the
-        // group, the old owner and other bits are kept and the group, setuid and setgid bits dropped.
-        let _ = f.set_permissions(std::fs::Permissions::from_mode(restored_mode(m.mode(), group_kept)));
-    }
     #[cfg(not(unix))]
     if let Some(p) = &prior {
         let _ = f.set_permissions(p.clone());
@@ -991,13 +966,6 @@ pub fn write_file(path: &str, bytes: &[u8]) -> Result<()> {
     })
 }
 
-/// The mode a saved file gets from the file it replaces (`old`): all of it when its group was
-/// restored; without the group, the owner and other bits only.
-#[cfg(unix)]
-fn restored_mode(old: u32, group_kept: bool) -> u32 {
-    if group_kept { old & 0o7777 } else { old & 0o707 }
-}
-
 #[cfg(target_arch = "wasm32")]
 pub fn write_file(path: &str, _bytes: &[u8]) -> Result<()> {
     script_sandbox_check(path)?;

crates/engine/src/io/tests.rs

@@ -51,14 +51,6 @@ fn save_keeps_the_destination_access_restrictions() {
     write_file(dest.to_str().unwrap(), b"v2").unwrap();
     let mode = std::fs::metadata(&dest).unwrap().permissions().mode() & 0o777;
     assert_eq!(mode, 0o600);
-    // The mode is set outright from the old file's, not through the umask: group and other access
-    // it had stay as they were.
-    for old in [0o640, 0o664] {
-        std::fs::set_permissions(&dest, std::fs::Permissions::from_mode(old)).unwrap();
-        write_file(dest.to_str().unwrap(), b"v3").unwrap();
-        assert_eq!(std::fs::metadata(&dest).unwrap().permissions().mode() & 0o777, old);
-    }
-    assert!(!dir.join("private.xlsx.sctmp").exists());
     // And a brand-new file is created with the restrictive, not permissive, default.
     let fresh = dir.join("new.xlsx");
     write_file(fresh.to_str().unwrap(), b"v").unwrap();
@@ -67,17 +59,6 @@ fn save_keeps_the_destination_access_restrictions() {
     let _ = std::fs::remove_dir_all(&dir);
 }
 
-/// Without the old group, a saved file keeps the old owner and other bits and nothing for a group.
-#[cfg(not(target_arch = "wasm32"))]
-#[cfg(unix)]
-#[test]
-fn restored_mode_drops_the_group_and_special_bits_when_the_group_is_lost() {
-    assert_eq!(super::restored_mode(0o100_664, true), 0o664);
-    assert_eq!(super::restored_mode(0o100_664, false), 0o604);
-    assert_eq!(super::restored_mode(0o102_444, false), 0o404, "an original read-only file stays read-only, setgid is dropped");
-    assert_eq!(super::restored_mode(0o104_755, false), 0o705, "setuid is dropped");
-}
-
 #[cfg(not(target_arch = "wasm32"))]
 #[test]
 fn open_refuses_directories_and_unknowable_lengths() {
@@ -780,20 +761,3 @@ fn sylk_survives_huge_relative_offsets_and_width_floods() {
     let (wb, _) = open_bytes("widths.slk", &flood).unwrap();
     assert_eq!(wb.sheet(0).unwrap().value(CellRef::parse("A1").unwrap()), gridcraft_core::Value::Number(1.0));
 }
-
-/// A FIFO with no writer would block an open forever: it is refused before it is opened.
-#[cfg(unix)]
-#[test]
-fn reading_a_fifo_is_refused_without_blocking() {
-    let dir = std::env::temp_dir().join(format!("gridcraft-fifo-{}", std::process::id()));
-    let _ = std::fs::remove_dir_all(&dir);
-    std::fs::create_dir_all(&dir).unwrap();
-    let fifo = dir.join("pipe.xlsx");
-    if !std::process::Command::new("mkfifo").arg(&fifo).status().is_ok_and(|s| s.success()) {
-        let _ = std::fs::remove_dir_all(&dir);
-        return; // no mkfifo here
-    }
-    let err = read_file(fifo.to_str().unwrap()).unwrap_err().to_string();
-    assert!(err.contains("only regular files"), "{err}");
-    let _ = std::fs::remove_dir_all(&dir);
-}

crates/engine/src/pivot/compute.rs

@@ -77,6 +77,8 @@ struct AggregateInput<'a> {
     extra: &'a [usize],
     filters: &'a [(usize, &'a PivotFilter, PivotDateGroup, bool)],
     filter_fmts: &'a [String],
+    /// Each filter's selected labels, ASCII-lowercased, so a record's test is one probe.
+    filter_sets: &'a [Option<HashSet<String>>],
     row_fmts: &'a [String],
     col_fmts: &'a [String],
     empty: bool,
@@ -99,10 +101,10 @@ fn aggregate_record(
     ri: usize,
     rec: &[Value],
 ) -> Result<(), String> {
-    for ((c, field, group, _), fmt) in input.filters.iter().zip(input.filter_fmts) {
-        if let Some(selected) = &field.selected {
+    for (((c, _, group, _), fmt), selected) in input.filters.iter().zip(input.filter_fmts).zip(input.filter_sets) {
+        if let Some(selected) = selected {
             let label = item_label(input.wb, rec.get(*c).unwrap_or(&Value::Empty), *group, fmt);
-            if !selected.iter().any(|value| value.eq_ignore_ascii_case(&label)) {
+            if !selected.contains(&label.to_ascii_lowercase()) {
                 return Ok(());
             }
         }
@@ -475,6 +477,8 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
 
     // ---- aggregate
     let filter_fmts: Vec<String> = filters.iter().map(|f| fmt_of(f.0)).collect();
+    let filter_sets: Vec<Option<HashSet<String>>> =
+        filters.iter().map(|(_, field, _, _)| field.selected.as_ref().map(|s| s.iter().map(|v| v.to_ascii_lowercase()).collect())).collect();
     let row_fmts: Vec<String> = rows.iter().map(|(c, _)| fmt_of(*c)).collect();
     let col_fmts: Vec<String> = cols.iter().map(|(c, _)| fmt_of(*c)).collect();
     let aggregate = aggregate_source(
@@ -488,6 +492,7 @@ pub(super) fn compute_from(wb: &Workbook, pt: &PivotTable, src: &Source, mut pro
             extra: &extra,
             filters: &filters,
             filter_fmts: &filter_fmts,
+            filter_sets: &filter_sets,
             row_fmts: &row_fmts,
             col_fmts: &col_fmts,
             empty,

crates/engine/src/tests.rs

@@ -3975,6 +3975,24 @@ fn fill_series_weekday_out_of_range_step_errors() {
     assert_eq!(v(&s, "A2"), Value::Empty);
 }
 
+/// A step of a million weekdays moves whole weeks at a time instead of visiting every day, and
+/// lands where counting day by day would.
+#[test]
+fn fill_series_weekday_large_step_is_arithmetic() {
+    let mut s = s();
+    // 45005 is Monday 20 March 2023; five weekdays on from a Monday is the next Monday.
+    s.execute("cell.set", json!({"cell": "A1", "input": "45005"})).unwrap();
+    s.execute("edit.fillSeries", json!({"range": "A1:A3", "direction": "columns", "type": "date", "dateUnit": "weekday", "step": 1_000_000}))
+        .unwrap();
+    assert_eq!(v(&s, "A2"), Value::Number(45005.0 + 1_400_000.0));
+    assert_eq!(v(&s, "A3"), Value::Number(45005.0 + 2_800_000.0));
+    s.execute("cell.set", json!({"cell": "B1", "input": "45009"})).unwrap();
+    s.execute("edit.fillSeries", json!({"range": "B1:B3", "direction": "columns", "type": "date", "dateUnit": "weekday", "step": -1})).unwrap();
+    // Friday 24 March 2023 back one weekday at a time: Thursday, Wednesday.
+    assert_eq!(v(&s, "B2"), Value::Number(45008.0));
+    assert_eq!(v(&s, "B3"), Value::Number(45007.0));
+}
+
 #[test]
 fn fill_series_month_leap_year() {
     let s = series_date("2028-01-31", "A1:A3", "month");
@@ -5572,3 +5590,62 @@ fn clearing_links_and_notes_keeps_allow_edit_ranges() {
     let sh = s.doc().unwrap().wb.active().unwrap().clone();
     assert!(sh.hyperlinks.is_empty() && sh.comments.is_empty());
 }
+
+#[test]
+fn protected_sheet_refuses_layout_commands_its_permissions_do_not_allow() {
+    let mut s = s();
+    s.execute("range.setValues", json!({"range": "A1", "values": [["h"], [1], [2]]})).unwrap();
+    s.execute("data.filter", json!({"range": "A1:A3"})).unwrap();
+    s.execute("review.protectSheet", json!({})).unwrap();
+    for (id, params) in [
+        ("home.rowHeight", json!({"rows": "1:1", "height": 40})),
+        ("home.columnWidth", json!({"cols": "A:A", "width": 80})),
+        ("data.group", json!({"rows": "2:3"})),
+        ("data.showLevels", json!({"rows": 1})),
+        ("data.clearFilter", json!({})),
+        ("data.reapply", json!({})),
+        ("insert.picture", json!({"base64": "iVBORw0KGgo="})),
+    ] {
+        let err = s.execute(id, params).expect_err(id).to_string();
+        assert!(err.contains("protected"), "{id}: {err}");
+    }
+    // With the permissions ticked the same layout commands run.
+    s.execute("review.unprotectSheet", json!({})).unwrap();
+    s.execute("review.protectSheet", json!({"formatRows": true, "formatColumns": true, "autofilter": true})).unwrap();
+    for (id, params) in [
+        ("home.rowHeight", json!({"rows": "1:1", "height": 40})),
+        ("home.columnWidth", json!({"cols": "A:A", "width": 80})),
+        ("data.reapply", json!({})),
+    ] {
+        s.execute(id, params).unwrap_or_else(|e| panic!("{id}: {e}"));
+    }
+}
+
+#[test]
+fn an_edit_range_limited_to_windows_users_stays_locked() {
+    use gridcraft_model::EditRange;
+    let mut s = s();
+    let a1 = CellRef::parse("A1").unwrap();
+    let range = |sd: Option<&str>| EditRange {
+        title: "T".into(),
+        ranges: vec![gridcraft_core::RangeRef::cell(a1)],
+        password: None,
+        security_descriptor: sd.map(str::to_string),
+    };
+    let sh = std::sync::Arc::make_mut(&mut s.doc_mut().unwrap().wb).sheet_mut(0).unwrap();
+    sh.edit_ranges.push(range(None));
+    assert!(crate::cmd::locked_cell_error(sh, a1, &[]).is_none(), "an open range");
+    sh.edit_ranges = vec![range(Some("D:(A;;GA;;;WD)"))];
+    assert!(crate::cmd::locked_cell_error(sh, a1, &[]).is_some(), "a user-limited range");
+}
+
+#[test]
+fn pivot_new_sheet_destination_respects_workbook_structure_protection() {
+    let mut s = s();
+    s.execute("range.setValues", json!({"range": "A1", "values": [["Region", "Sales"], ["N", 1], ["S", 2]]})).unwrap();
+    s.execute("review.protectWorkbook", json!({"on": true})).unwrap();
+    for dest in ["new", "NEW", " new ", ""] {
+        assert!(s.execute("insert.pivotTable", json!({"source": "A1:B3", "destination": dest})).is_err(), "destination {dest:?}");
+    }
+    assert!(s.execute("insert.pivotTable", json!({"source": "A1:B3", "location": "New"})).is_err());
+}

crates/formula/src/input.rs

@@ -61,7 +61,7 @@ impl FormulaLocale {
 pub fn parse_input(src: &str, locale: FormulaLocale, known_name: impl Fn(&str) -> bool) -> Result<Expr, ParseError> {
     let mut expr = parser::parse_syntax(src, locale)?;
     if locale == FormulaLocale::Es {
-        normalize(&mut expr, &known_name, &mut Vec::new(), 0, false)?;
+        normalize(&mut expr, &known_name, &mut Bindings::default(), 0, false)?;
     }
     Ok(expr)
 }
@@ -96,7 +96,7 @@ pub fn print_input(expr: &Expr, locale: FormulaLocale, known_name: impl Fn(&str)
         return Ok(crate::print(expr));
     }
     let mut expr = expr.clone();
-    normalize(&mut expr, &known_name, &mut Vec::new(), 0, true)?;
+    normalize(&mut expr, &known_name, &mut Bindings::default(), 0, true)?;
     let canonical = crate::print(&expr);
     let tokens = crate::lexer::tokenize(&canonical).map_err(|e| ParseError { msg: e.msg, pos: e.pos })?;
     let mut out = String::new();
@@ -131,11 +131,47 @@ pub(crate) fn boolean_alias(name: &str) -> Option<bool> {
     }
 }
 
-fn normalize(expr: &mut Expr, known_name: &impl Fn(&str) -> bool, bindings: &mut Vec<String>, depth: usize, display: bool) -> Result<(), ParseError> {
+/// The LET/LAMBDA names in scope, with how many times each is bound, so a lookup is one probe
+/// instead of a scan of every binding for each call.
+#[derive(Default)]
+struct Bindings {
+    stack: Vec<String>,
+    counts: std::collections::HashMap<String, usize>,
+}
+
+impl Bindings {
+    fn len(&self) -> usize {
+        self.stack.len()
+    }
+
+    fn push(&mut self, name: &str) {
+        let key = crate::fold_name(name);
+        *self.counts.entry(key.clone()).or_default() += 1;
+        self.stack.push(key);
+    }
+
+    fn truncate(&mut self, len: usize) {
+        while self.stack.len() > len {
+            let Some(key) = self.stack.pop() else { break };
+            if let Some(n) = self.counts.get_mut(&key) {
+                *n -= 1;
+                if *n == 0 {
+                    self.counts.remove(&key);
+                }
+            }
+        }
+    }
+
+    fn contains(&self, name: &str) -> bool {
+        self.counts.contains_key(&crate::fold_name(name))
+    }
+}
+
+fn normalize(expr: &mut Expr, known_name: &impl Fn(&str) -> bool, bindings: &mut Bindings, depth: usize, display: bool) -> Result<(), ParseError> {
     if depth > parser::MAX_DEPTH {
         return Err(ParseError { msg: "formula is nested too deeply".into(), pos: 0 });
     }
-    let bound = |name: &str, bindings: &[String]| bindings.iter().rev().any(|n| crate::same_name(n, name)) || known_name(name);
+    let bound = |name: &str, bindings: &Bindings| bindings.contains(name) || known_name(name);
     match expr {
         Expr::Bool(value) if display => {
             let alias = if *value { "VERDADERO" } else { "FALSO" };
@@ -156,7 +192,7 @@ fn normalize(expr: &mut Expr, known_name: &impl Fn(&str) -> bool, bindings: &mut
                         // The new name is not in scope in its own value expression.
                         normalize(value, known_name, bindings, depth + 1, display)?;
                         if let Expr::Name(name) = declaration {
-                            bindings.push(name.clone());
+                            bindings.push(name);
                         }
                     }
                 }
@@ -169,7 +205,7 @@ fn normalize(expr: &mut Expr, known_name: &impl Fn(&str) -> bool, bindings: &mut
             if let Some((body, params)) = args.split_last_mut() {
                 for param in params {
                     if let Expr::Name(name) = param {
-                        bindings.push(name.clone());
+                        bindings.push(name);
                     }
                 }
                 normalize(body, known_name, bindings, depth + 1, display)?;

crates/functions/src/stat/descriptive.rs

@@ -50,12 +50,27 @@ pub(super) fn median(v: Vec<f64>) -> R<f64> {
 
 /// Values occurring at least twice, ordered by first occurrence, with their (equal, maximal) count.
 fn modes(v: &[f64]) -> Vec<f64> {
+    // Index of each distinct number in `counts`, so counting is linear rather than a search of
+    // every distinct number so far. Keyed by bits with -0 folded into 0 (they compare equal); NaN
+    // never equals anything, so it is never merged.
+    let mut index: std::collections::HashMap<u64, usize> = std::collections::HashMap::new();
     let mut counts: Vec<(f64, usize)> = Vec::new();
     for &x in v {
-        if let Some(e) = counts.iter_mut().find(|e| e.0 == x) {
-            e.1 += 1;
-        } else {
+        if x.is_nan() {
             counts.push((x, 1));
+            continue;
+        }
+        let key = if x == 0.0 { 0 } else { x.to_bits() };
+        match index.entry(key) {
+            std::collections::hash_map::Entry::Occupied(e) => {
+                if let Some(c) = counts.get_mut(*e.get()) {
+                    c.1 += 1;
+                }
+            }
+            std::collections::hash_map::Entry::Vacant(e) => {
+                e.insert(counts.len());
+                counts.push((x, 1));
+            }
         }
     }
     let best = counts.iter().map(|e| e.1).max().unwrap_or(0);
@@ -451,11 +466,15 @@ pub(super) fn frequency(a: &[Arg], _: C) -> R<Value> {
     if bins.is_empty() {
         return col_value(vec![data.len() as f64]);
     }
-    let mut order: Vec<usize> = (0..bins.len()).collect();
+    // a NaN bin equals no value (and would break the ascending order searched below)
+    let mut order: Vec<usize> = (0..bins.len()).filter(|&i| bins.get(i).is_some_and(|b| !b.is_nan())).collect();
     order.sort_by(|&i, &j| bins.get(i).copied().unwrap_or(0.0).total_cmp(&bins.get(j).copied().unwrap_or(0.0)));
     let mut counts = vec![0.0; bins.len() + 1];
     for x in data {
-        let slot = order.iter().find(|&&i| x <= bins.get(i).copied().unwrap_or(f64::INFINITY)).copied().unwrap_or(bins.len());
+        // `order` sorts the bins ascending, so the bins `x` exceeds come first: binary search for
+        // the first bin at or above `x` (the first of equal bins, as a linear scan would find).
+        let pos = if x.is_nan() { order.len() } else { order.partition_point(|&i| bins.get(i).copied().unwrap_or(f64::INFINITY) < x) };
+        let slot = order.get(pos).copied().unwrap_or(bins.len());
         if let Some(c) = counts.get_mut(slot) {
             *c += 1.0;
         }

crates/functions/src/stat/tests.rs

@@ -617,3 +617,23 @@ fn aggregate_helper() {
     close(aggregate_values_k(9, &vals, &nv(2.0)), 9.0);
     is_err(aggregate_values_k(14, &vals, &nv(10.0)), CellError::Num);
 }
+
+/// Security: FREQUENCY finds each value's bin by binary search, and MODE counts distinct numbers
+/// through an index, so neither is quadratic in its inputs. Results are as before: unsorted and
+/// duplicate bins keep their positions (a value goes to the first of equal bins), and tied modes
+/// come in first-occurrence order.
+#[test]
+fn frequency_and_mode_scale_with_their_inputs() {
+    let f = ev("FREQUENCY", vec![c(&[1.0, 2.0, 2.0, 3.0, 5.0, 9.0, -1.0]), c(&[3.0, 2.0, 2.0, 0.0])]);
+    assert_eq!(rows_of(&f), vec![vec![nv(1.0)], vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
+    // NaN data goes to the overflow bin, and a NaN bin takes nothing
+    let f = ev("FREQUENCY", vec![c(&[f64::NAN, 0.5, 2.0]), c(&[f64::NAN, 1.0])]);
+    assert_eq!(rows_of(&f), vec![vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
+    let data: Vec<f64> = (0..200_000).map(|i| f64::from(i) + 1e6).collect();
+    let bins: Vec<f64> = (0..200_000).map(f64::from).collect();
+    let f = ev("FREQUENCY", vec![c(&data), c(&bins)]);
+    assert_eq!(rows_of(&f).last(), Some(&vec![nv(200_000.0)]));
+    let distinct = ev("MODE", vec![c(&data)]);
+    is_err(distinct, CellError::NA);
+    assert_eq!(rows_of(&ev("MODE.MULT", vec![c(&[3.0, 0.0, 1.0, -0.0, 3.0, 1.0])])), vec![vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)]]);
+}

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};
 
@@ -339,11 +341,11 @@ fn numbervalue(a: &[Arg], c: &mut dyn Ctx) -> R<Value> {
     if body.is_empty() {
         return num_val(0.0);
     }
-    let mut pct = 0;
-    while let Some(b) = body.strip_suffix('%') {
-        body = b.to_string();
-        pct += 1;
-    }
+    // Count the trailing percent signs and cut them off in place: copying the rest once per sign
+    // made a long run of them quadratic.
+    let kept = body.trim_end_matches('%').len();
+    let pct = body.len() - kept;
+    body.truncate(kept);
     let mut seen_dec = false;
     let mut out = String::new();
     for c in body.chars() {
@@ -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;
         }
@@ -1084,6 +1115,15 @@ mod tests {
 
     use crate::util::testutil::*;
 
+    /// Trailing percent signs each divide by 100, and a long run of them is cut off in one pass.
+    #[test]
+    fn numbervalue_percent_signs() {
+        close(ev("NUMBERVALUE", vec![t("5%%")]), 0.0005);
+        close(ev("NUMBERVALUE", vec![t("1,5%"), t(","), t(".")]), 0.015);
+        let many = format!("1{}", "%".repeat(32_000));
+        close(ev("NUMBERVALUE", vec![t(&many)]), 0.0);
+    }
+
     #[test]
     fn bahttext() {
         let bt = |x: f64| ev("BAHTTEXT", vec![n(x)]);
@@ -1366,6 +1406,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.0)]), 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.0)]), "z");
+    }
+
     #[test]
     fn split() {
         let v = ev("TEXTSPLIT", vec![t("a,b;c,d"), t(","), t(";")]);

crates/numfmt/src/decimal.rs

@@ -136,6 +136,9 @@ pub(crate) fn fixed(a: f64, decimals: usize) -> (String, String) {
 /// General format squeezed into `max_chars` characters. Excel shows fewer decimals, then
 /// scientific notation, then "####" when a column is narrow; `None` means the caller paints "####".
 pub fn format_general_fit(n: f64, max_chars: usize) -> Option<String> {
+    // The widest fixed rendering of a double is about 330 characters; a larger request only
+    // pads zero decimals the trim below throws away.
+    let max_chars = max_chars.min(1024);
     if !n.is_finite() {
         return None;
     }
@@ -214,6 +217,8 @@ mod tests {
     fn general_fit() {
         assert_eq!(format_general_fit(1e11, 11).as_deref(), Some("1E+11"));
         assert_eq!(format_general_fit(12345678901.0, 11).as_deref(), Some("12345678901"));
+        // A huge width neither allocates width-sized padding nor changes the text.
+        assert_eq!(format_general_fit(1.5, usize::MAX).as_deref(), Some("1.5"));
         assert_eq!(format_general_fit(123456789012.0, 11).as_deref(), Some("1.23457E+11"));
         assert_eq!(format_general_fit(0.1 + 0.2, 11).as_deref(), Some("0.3"));
         assert_eq!(format_general_fit(1.0 / 3.0, 11).as_deref(), Some("0.333333333"));

crates/ui-egui/src/editor.rs

@@ -375,7 +375,7 @@ pub fn formula_refs(text: &str) -> Vec<(usize, usize, RangeRef, Option<String>,
     let offset = text.len() - body.len();
     let Ok(toks) = gridcraft_engine::formula::lexer::tokenize(body) else { return vec![] };
     let mut out: Vec<(usize, usize, RangeRef, Option<String>, usize)> = Vec::new();
-    let mut seen: Vec<String> = Vec::new();
+    let mut seen: std::collections::HashMap<String, usize> = std::collections::HashMap::new();
     let mut i = 0;
     while i < toks.len() {
         use gridcraft_engine::formula::lexer::Tok;
@@ -407,13 +407,8 @@ pub fn formula_refs(text: &str) -> Vec<(usize, usize, RangeRef, Option<String>,
                 continue;
             };
             let key = body.get(start..end).unwrap_or("").replace('$', "").to_ascii_uppercase();
-            let idx = match seen.iter().position(|k| *k == key) {
-                Some(k) => k,
-                None => {
-                    seen.push(key);
-                    seen.len() - 1
-                }
-            };
+            let next = seen.len();
+            let idx = *seen.entry(key).or_insert(next);
             out.push((start + offset, end + offset, range, sheet, idx % REF_COLOR_COUNT));
             continue;
         }

crates/ui-egui/src/grid/quadrant.rs

@@ -278,6 +278,9 @@ fn paint_cell_decorations(q: &QuadrantPaint<'_>, c: CellRef, rect: Rect, lk: &Lo
     false
 }
 
+/// Most repeats of a fill character laid out in one cell.
+const MAX_FILL_REPEATS: usize = 8192;
+
 fn paint_data_bar(p: &egui::Painter, rect: Rect, frac: f32, rgb: [u8; 3], gradient: bool) {
     let bar = Rect::from_min_size(pos2(rect.left() + 2.0, rect.top() + 2.0), vec2((rect.width() - 4.0) * frac, rect.height() - 4.0));
     let col = theme::color32(rgb);
@@ -432,7 +435,8 @@ fn paint_cell(q: &QuadrantPaint<'_>, painted: &(CellRef, Rect, Look, Option<CfLo
     {
         let base_w = w;
         let cw = p.layout_no_wrap(ch.to_string(), font.clone(), color).size().x.max(1.0);
-        let n = (((avail_w - 2.0 * pad) - base_w) / cw).floor().max(0.0) as usize;
+        // A merged cell's width counts offscreen columns: no screen shows more repeats than this.
+        let n = ((((avail_w - 2.0 * pad) - base_w) / cw).floor().max(0.0) as usize).min(MAX_FILL_REPEATS);
         let mut s = first_line.clone();
         if first_line.is_char_boundary(pos) {
             s.insert_str(pos, &ch.to_string().repeat(n));

crates/xlsx/src/ods.rs

@@ -470,6 +470,14 @@ impl Import {
             None => return Err(IoError::TooLarge("ODS row exceeds worksheet width".into())),
         };
         if kept {
+            // Charge the text a row keeps before the row is done, so a row of many long cells is
+            // refused as it grows; finish_row charges the row's repeats beyond the first.
+            if let Value::Text(t) = &cell.value {
+                self.text = self.text.saturating_add(u64::from(draft.repeat).saturating_mul(t.len() as u64));
+                if self.text > MAX_TEXT {
+                    return Err(IoError::TooLarge("ODS expands beyond the import limit (64 MiB of text)".into()));
+                }
+            }
             row.cells.push(RepeatedCell { col: row.col, repeat: draft.repeat, width, height, cell });
         }
         row.col = end;
@@ -537,7 +545,8 @@ impl Import {
             if !entry.cell.is_blank() {
                 self.cells = self.cells.saturating_add(count);
                 if let Value::Text(t) = &entry.cell.value {
-                    self.text = self.text.saturating_add(count.saturating_mul(t.len() as u64));
+                    let repeats = count.saturating_sub(u64::from(entry.repeat));
+                    self.text = self.text.saturating_add(repeats.saturating_mul(t.len() as u64));
                 }
             }
             let merged = entry.width > 1 || entry.height > 1;

crates/xlsx/src/tests/ods_tests.rs

@@ -200,6 +200,18 @@ fn ods_expansion_bounds_stop_small_repeat_bombs() {
         "x".repeat(1024)
     );
     assert!(matches!(read_ods(&ods(&text)), Err(IoError::TooLarge(_))));
+    // One row of cells each just under the 1 MiB cell limit, past 64 MiB in all: refused while
+    // the row is read, before it holds them all. The row's end is never reached.
+    let long = format!(r#"<table:table-cell office:value-type="string" office:string-value="{}"/>"#, "x".repeat(1024 * 1024 - 1));
+    let cells = ods(&format!(r#"<table:table table:name="Data"><table:table-row>{}"#, long.repeat(65)));
+    assert!(matches!(read_ods(&cells), Err(IoError::TooLarge(_))));
+    // A row repeated once more than its cells' text allows is refused too, and one that fits reads.
+    let cell = format!(r#"<table:table-cell office:value-type="string" office:string-value="{}"/>"#, "y".repeat(1024));
+    let rows = |n: u32| {
+        ods(&format!(r#"<table:table table:name="Data"><table:table-row table:number-rows-repeated="{n}">{cell}</table:table-row></table:table>"#))
+    };
+    assert!(read_ods(&rows(65_536)).is_ok());
+    assert!(matches!(read_ods(&rows(65_537)), Err(IoError::TooLarge(_))));
 }
 
 #[test]