xlsx: rename repeated table headers without retrying handed-out suffixes (#3213)

table_columns restarted its suffix search at 2 for every duplicate
header, lowercasing and hashing every candidate already in use, so a
table of repeated headers was exported in quadratic time. The next
suffix to try is now remembered per lowercased base.

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

@@ -31,20 +31,41 @@ 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();
-    // 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());
+    // 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());
             }
+            continue;
         }
-        if set.len() == before {
-            break;
+        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);
+            }
         }
     }
     set

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

@@ -178,6 +178,28 @@ 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/engine/src/cmd.rs

@@ -459,8 +459,11 @@ 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), whichever command made it. Sheets are matched by name, so moving, renaming or
-/// deleting a sheet isn't an edit of its cells.
+/// 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.
 fn check_protection(old: &Workbook, new: &Workbook, unlocked: &[(String, String)]) -> Result<()> {
     for sh in &old.sheets {
         if !sh.is_protected() {
@@ -471,7 +474,8 @@ fn check_protection(old: &Workbook, new: &Workbook, unlocked: &[(String, String)
             continue;
         }
         for c in sh.cells.diff(&after.cells) {
-            if !same_content(sh.cell(c), after.cell(c))
+            let unlocked_now = !new.styles.get(after.style_id(c)).protection.locked;
+            if (unlocked_now || !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 (`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)?;
+    // 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)?;
 
     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,6 +5297,42 @@ 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/xlsx/src/sheet_write/parts.rs

@@ -1,3 +1,5 @@
+use std::collections::HashMap;
+
 use super::*;
 
 /// Valid table name: letters, digits, `_` and `.`, starting with a letter, `_` or `\`
@@ -21,16 +23,24 @@ pub(super) fn table_name(name: &str, used: &mut HashSet<String>, n: u32) -> Stri
 pub(super) fn table_columns(t: &Table) -> Vec<String> {
     let w = t.range.width() as usize;
     let mut used = HashSet::new();
+    // The next suffix to try per lowercased base, so repeated headers don't retry every suffix
+    // already handed out.
+    let mut next: HashMap<String, u32> = HashMap::new();
     (0..w)
         .map(|i| {
             let base = t.columns.get(i).map(|c| c.name.clone()).filter(|n| !n.trim().is_empty()).unwrap_or_else(|| format!("Column{}", i + 1));
-            let mut name = base.clone();
-            let mut k = 2;
-            while !used.insert(name.to_lowercase()) {
-                name = format!("{base}{k}");
-                k += 1;
+            let lower = base.to_lowercase();
+            if used.insert(lower.clone()) {
+                return base;
+            }
+            let k = next.entry(lower).or_insert(2);
+            loop {
+                let name = format!("{base}{k}");
+                *k += 1;
+                if used.insert(name.to_lowercase()) {
+                    return name;
+                }
             }
-            name
         })
         .collect()
 }
@@ -371,3 +381,38 @@ pub(super) fn vml_xml(sheet: &Sheet, n: u32) -> String {
     s.push_str("</xml>");
     s
 }
+
+#[cfg(test)]
+mod tests {
+    use gridcraft_model::TableColumn;
+
+    use super::*;
+
+    #[test]
+    fn repeated_headers_are_renamed_without_retrying_suffixes() {
+        let col = |n: &str| TableColumn { name: n.into(), totals: TotalsFn::None, totals_label: None, formula: None, unique_name: None, xml: None };
+        let mut columns: Vec<TableColumn> = (0..10_000).map(|_| col("Total")).collect();
+        columns[1] = col("total3");
+        let t = Table {
+            id: 1,
+            name: "T".into(),
+            range: RangeRef::parse("A1:NTP2").unwrap(),
+            header_row: true,
+            totals_row: false,
+            columns,
+            style: String::new(),
+            banded_rows: false,
+            banded_cols: false,
+            first_col: false,
+            last_col: false,
+            filter_button: false,
+            filter: vec![],
+            table_type: None,
+            connection_id: None,
+        };
+        let names = table_columns(&t);
+        assert_eq!(names.len(), 10_000);
+        assert_eq!(&names[..4], ["Total", "total3", "Total2", "Total4"]);
+        assert_eq!(names.iter().map(|n| n.to_lowercase()).collect::<HashSet<_>>().len(), 10_000);
+    }
+}