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/ods.rs

@@ -317,7 +317,7 @@ impl Import {
                     return Err(IoError::TooLarge("ODS contains more than 1024 sheets".into()));
                 }
                 let original = attr(reader, e, TABLE, b"name")?.unwrap_or_default();
-                let mut name = crate::read::SheetNames::of(&self.wb).unique(original.trim_matches('\''), self.wb.sheets.len());
+                let mut name = crate::read::unique_name(&self.wb, original.trim_matches('\''), self.wb.sheets.len());
                 if self.wb.check_sheet_name(&name, None).is_err() {
                     name = self.wb.next_sheet_name();
                 }

crates/xlsx/src/read.rs

@@ -1,6 +1,5 @@
 //! Reading the workbook part and everything hanging off it.
 
-use std::collections::{HashMap, HashSet};
 use std::sync::Arc;
 
 use gridcraft_core::{DateSystem, RangeRef};
@@ -305,7 +304,6 @@ pub fn read_xlsx<'a>(bytes: &'a [u8], known_function: Option<&'a dyn Fn(&str) ->
     let mut file_to_model: Vec<Option<usize>> = vec![];
     let mut pivot_caches = crate::pivot::CachesIn::new(&wb_xml, &wb_rels);
     let sheet_els: Vec<El> = wb_xml.child("sheets").map(|s| s.kids("sheet").cloned().collect()).unwrap_or_default();
-    let mut names = SheetNames::default();
     for (i, se) in sheet_els.iter().enumerate() {
         let name = se.attr("name").unwrap_or("").to_string();
         let rel = se.attr("id").and_then(|id| wb_rels.iter().find(|r| r.id == id)).cloned();
@@ -324,7 +322,7 @@ pub fn read_xlsx<'a>(bytes: &'a [u8], known_function: Option<&'a dyn Fn(&str) ->
             file_to_model.push(None);
             continue;
         }
-        let name = names.unique(&name, i);
+        let name = unique_name(&wb, &name, i);
         let mut sheet = match crate::sheet_read::read_sheet(&mut cx, &rel.target, &name) {
             Ok(s) => s,
             Err(IoError::TooLarge(m)) => return Err(IoError::TooLarge(m)),
@@ -457,44 +455,15 @@ pub fn read_xlsx<'a>(bytes: &'a [u8], known_function: Option<&'a dyn Fn(&str) ->
     Ok((wb, cx.report))
 }
 
-/// The sheet names an import has assigned so far, for repairing repeated ones.
-#[derive(Default)]
-pub(crate) struct SheetNames {
-    /// Assigned names, ASCII-lowercased.
-    taken: HashSet<String>,
-    /// For each lowercased stem, the next suffix to try: a file full of repeated names would
-    /// otherwise retry every occupied suffix for every sheet.
-    next: HashMap<String, u64>,
-}
-
-impl SheetNames {
-    pub(crate) fn of(wb: &Workbook) -> Self {
-        SheetNames { taken: wb.sheets.iter().map(|s| s.name.to_ascii_lowercase()).collect(), next: HashMap::new() }
+pub(crate) fn unique_name(wb: &Workbook, name: &str, i: usize) -> String {
+    let mut base: String = name.chars().filter(|c| !matches!(c, ':' | '\\' | '/' | '?' | '*' | '[' | ']')).take(31).collect();
+    if base.trim().is_empty() {
+        base = format!("Sheet{}", i + 1);
     }
-
-    /// A valid name for the i-th sheet, unique among the names assigned so far, which it joins.
-    pub(crate) fn unique(&mut self, name: &str, i: usize) -> String {
-        let mut base: String = name.chars().filter(|c| !matches!(c, ':' | '\\' | '/' | '?' | '*' | '[' | ']')).take(31).collect();
-        if base.trim().is_empty() {
-            base = format!("Sheet{}", i + 1);
-        }
-        let name = if self.taken.contains(&base.to_ascii_lowercase()) {
-            let stem: String = base.chars().take(25).collect();
-            let next = self.next.entry(stem.to_ascii_lowercase()).or_insert(2);
-            let found = (*next..).find(|n| !self.taken.contains(&format!("{stem} ({n})").to_ascii_lowercase()));
-            match found {
-                Some(n) => {
-                    *next = n + 1;
-                    format!("{stem} ({n})")
-                }
-                None => base,
-            }
-        } else {
-            base
-        };
-        self.taken.insert(name.to_ascii_lowercase());
-        name
+    if wb.sheet_index(&base).is_none() {
+        return base;
     }
+    (2..).map(|n| format!("{} ({n})", base.chars().take(25).collect::<String>())).find(|n| wb.sheet_index(n).is_none()).unwrap_or(base)
 }
 
 /// Strips a sheet qualifier (`'My Sheet'!$A$1` → `$A$1`).

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);
+    }
+}

crates/xlsx/src/tests/sheet_names.rs

@@ -35,17 +35,3 @@ fn sheet_ids_survive_a_save() {
     let (again, _) = crate::read_xlsx(&write_xlsx(&read).unwrap()).unwrap();
     assert_eq!(again.sheets.iter().map(|s| s.file_id).collect::<Vec<_>>(), ids);
 }
-
-/// Repairing repeated names takes one set lookup per candidate, so thousands of sheets sharing
-/// a name are renamed without rescanning the workbook for every suffix tried.
-#[test]
-fn repeated_sheet_names_are_repaired_without_rescans() {
-    let mut names = crate::read::SheetNames::default();
-    assert_eq!(names.unique("Data", 0), "Data");
-    assert_eq!(names.unique("data", 1), "data (2)");
-    assert_eq!(names.unique("", 2), "Sheet3");
-    assert_eq!(names.unique("Data (3)", 3), "Data (3)");
-    for i in 4..100_000 {
-        assert_eq!(names.unique("Data", i), format!("Data ({i})"));
-    }
-}