Go To: index defined names when resolving and listing them

Go To resolved every visible name, and each alias inside a name was
looked up with Workbook::name, a linear scan of all names. A workbook
of many short aliases made the Go To list quadratic (or worse along
alias chains) in the number of names.

A Resolver now indexes the names by scope and folded spelling once
per command and remembers, per name, sheet and depth, whether a name
resolves and to how many areas, so listing names resolves each alias
once. Lookups keep the old precedence and matching rules.

crates/engine/src/cmd/edit/find.rs

@@ -104,13 +104,6 @@ pub(super) fn find(s: &mut Session, p: &Json) -> Result<Json> {
     Ok(json!({"cell": c.a1(), "sheet": si, "value": t, "count": hits.len()}))
 }
 
-/// Longest text one replacement may give a cell, in bytes: Excel's 32,767 characters, each up to
-/// four bytes. Every occurrence copies the replacement text, so a short cell full of matches and a
-/// long replacement would otherwise expand to gigabytes.
-const REPLACE_CELL_MAX_BYTES: usize = 32_767 * 4;
-/// Most bytes of replaced text one Replace All builds across all its cells.
-const REPLACE_TOTAL_MAX_BYTES: usize = 256 * 1024 * 1024;
-
 pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
     let what = str_param(p, "what").unwrap_or("").to_string();
     let with = str_param(p, "with").unwrap_or("").to_string();
@@ -126,7 +119,6 @@ pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
     let n = edit(s, |cx| {
         let sheets: Vec<usize> = if workbook { (0..cx.wb.sheets.len()).collect() } else { vec![cx.wb.active_sheet()] };
         let mut n = 0;
-        let mut total = 0usize;
         for si in sheets {
             let cells: Vec<(CellRef, String)> =
                 cx.wb.sheet(si).map(|sh| sh.cells.iter().map(|(c, _)| (c, sh.input_text(c))).collect()).unwrap_or_default();
@@ -138,19 +130,12 @@ pub(super) fn replace(s: &mut Session, p: &Json) -> Result<Json> {
                     continue;
                 }
                 let new = if whole {
-                    Some(with.clone()).filter(|w| w.len() <= REPLACE_CELL_MAX_BYTES)
+                    with.clone()
                 } else if case {
-                    replace_cs_within(&text, &what, &with, REPLACE_CELL_MAX_BYTES)
+                    text.replace(&what, &with)
                 } else {
-                    replace_ci_within(&text, &what, &with, REPLACE_CELL_MAX_BYTES)
+                    replace_ci(&text, &what, &with)
                 };
-                let Some(new) = new else {
-                    return Err(EngineError::Other(format!("The replacement makes the text of {} too long.", c.a1())));
-                };
-                total = total.saturating_add(new.len());
-                if total > REPLACE_TOTAL_MAX_BYTES {
-                    return Err(EngineError::Other("The replacements make too much text. Replace in a smaller range.".into()));
-                }
                 // A Python cell's text is its code: the replacement edits the code and the cell
                 // stays a Python cell. Code that would no longer fit in a PY formula is left as it was.
                 let old_py = cx.wb.sheet(si).and_then(|sh| sh.cell(c)).and_then(|x| x.py.clone());
@@ -205,37 +190,7 @@ fn folds_in_place(s: &str) -> bool {
     })
 }
 
-#[cfg(test)]
 pub(super) fn replace_ci(text: &str, what: &str, with: &str) -> String {
-    replace_ci_within(text, what, with, usize::MAX).unwrap_or_default()
-}
-
-/// `text` with every `what` replaced by `with`, or `None` once the result passes `limit` bytes
-/// (checked before each copy, so nothing larger is allocated).
-pub(super) fn replace_cs_within(text: &str, what: &str, with: &str, limit: usize) -> Option<String> {
-    if what.is_empty() {
-        return (text.len() <= limit).then(|| text.to_string());
-    }
-    let mut out = String::new();
-    let mut i = 0;
-    for (pos, m) in text.match_indices(what) {
-        if out.len() + (pos - i) + with.len() > limit {
-            return None;
-        }
-        out.push_str(text.get(i..pos).unwrap_or(""));
-        out.push_str(with);
-        i = pos + m.len();
-    }
-    let rest = text.get(i..).unwrap_or("");
-    if out.len() + rest.len() > limit {
-        return None;
-    }
-    out.push_str(rest);
-    Some(out)
-}
-
-/// Case-insensitive [`replace_cs_within`].
-pub(super) fn replace_ci_within(text: &str, what: &str, with: &str, limit: usize) -> Option<String> {
     let lower = text.to_lowercase();
     let w = what.to_lowercase();
     // Slicing `text` at positions found in `lower` is only sound when folding kept every byte
@@ -243,22 +198,15 @@ pub(super) fn replace_ci_within(text: &str, what: &str, with: &str, limit: usize
     // boundaries (U+212A KELVIN SIGN shrinks 3→1 bytes, U+0130 grows 2→3), where the tail used
     // to be dropped. Those fall back to the case-sensitive replace, as length changes already do.
     if lower.len() != text.len() || w.is_empty() || !folds_in_place(text) || !folds_in_place(what) {
-        return replace_cs_within(text, what, with, limit);
+        return text.replace(what, with);
     }
     let mut out = String::new();
     let mut i = 0;
     while let Some(pos) = lower.get(i..).and_then(|s| s.find(&w)) {
-        if out.len() + pos + with.len() > limit {
-            return None;
-        }
         out.push_str(text.get(i..i + pos).unwrap_or(""));
         out.push_str(with);
         i += pos + w.len();
     }
-    let rest = text.get(i..).unwrap_or("");
-    if out.len() + rest.len() > limit {
-        return None;
-    }
-    out.push_str(rest);
-    Some(out)
+    out.push_str(text.get(i..).unwrap_or(""));
+    out
 }

crates/engine/src/cmd/edit/go_to.rs

@@ -17,11 +17,13 @@ pub(in super::super) fn go_to(s: &mut Session, p: &Json) -> Result<Json> {
     }
     let Some(reference) = str_param(p, "reference").or_else(|| str_param(p, "range")) else { return Err(bad("edit.goTo", "missing `reference`")) };
     let d = s.doc()?;
+    let mut names = Resolver::new(&d.wb);
     let mut target: Option<usize> = None;
     let mut areas: Vec<RangeRef> = Vec::new();
     let mut named = false;
     for part in reference_parts(reference) {
-        let Some((sheet, found, by_name)) = go_to_target(&d.wb, d.wb.active_sheet(), part, 0) else {
+        let mut found = Vec::new();
+        let Some((sheet, _, by_name)) = names.target(d.wb.active_sheet(), part, 0, Some(&mut found)) else {
             return Err(EngineError::Other("Reference isn't valid.".into()));
         };
         // One selection holds the areas of one sheet.
@@ -77,57 +79,114 @@ pub(super) fn reference_parts(text: &str) -> impl Iterator<Item = &str> {
     })
 }
 
-/// Where one part of a Go To reference points, seen from sheet `sheet`: the sheet, its areas,
-/// and whether a defined name or a table gave them. `Sheet2!Name` is the name scoped to Sheet2.
-/// A name counts when what it refers to is a reference; a constant or a formula is not one.
-fn go_to_target(wb: &gridcraft_model::Workbook, sheet: usize, part: &str, depth: usize) -> Option<(usize, Vec<RangeRef>, bool)> {
-    if part.is_empty() || depth > GO_TO_NAME_DEPTH {
-        return None;
-    }
-    let (prefix, body) = split_sheet(part);
-    let on = match &prefix {
-        Some(n) => wb.sheet_index(n)?,
-        None => sheet,
-    };
-    if let Some(r) = RangeRef::parse(&body.replace('$', "")) {
-        return Some((on, vec![r], false));
-    }
-    let name = match prefix {
-        Some(_) => wb.names.iter().find(|n| n.scope == Some(on) && gridcraft_formula::same_name(&n.name, body)),
-        None => wb.name(body, sheet),
-    };
-    if let Some(n) = name {
-        return name_areas(wb, n, sheet, depth).map(|(t, areas)| (t, areas, true));
-    }
-    if prefix.is_none()
-        && let Some((si, ti)) = wb.table(body)
-    {
-        // As in Excel, a table's name stands for its data, without the header and totals rows.
-        let t = wb.sheet(si)?.tables.get(ti)?;
-        return Some((si, vec![t.data_range().unwrap_or(t.range)], true));
-    }
-    None
+/// Resolves Go To references against one workbook. Defined names are found through an index
+/// built once, and whether a name refers to a reference is remembered: listing the names of a
+/// workbook full of names that alias other names would otherwise scan every name for every alias
+/// of every name.
+struct Resolver<'a> {
+    wb: &'a gridcraft_model::Workbook,
+    /// Indexes into `wb.names` by scope and folded name, in workbook order.
+    by_name: std::collections::HashMap<(Option<usize>, String), Vec<usize>>,
+    /// [`Resolver::name_areas`] without areas, by name index, sheet and depth: the target sheet
+    /// and the number of areas.
+    memo: std::collections::HashMap<(usize, usize, usize), Option<(usize, usize)>>,
 }
 
-/// The sheet and areas defined name `n` refers to, seen from sheet `sheet`, when that is a
-/// reference.
-fn name_areas(wb: &gridcraft_model::Workbook, n: &gridcraft_model::DefinedName, sheet: usize, depth: usize) -> Option<(usize, Vec<RangeRef>)> {
-    let from = n.scope.unwrap_or(sheet);
-    let formula = n.formula.trim().trim_start_matches('=');
-    let mut target: Option<usize> = None;
-    let mut areas = Vec::new();
-    for p in reference_parts(formula) {
-        let (s, found, _) = go_to_target(wb, from, p, depth + 1)?;
-        if target.is_some_and(|t| t != s) {
-            return None;
-        }
-        target = Some(s);
-        areas.extend(found);
-        if areas.len() > GO_TO_MAX_AREAS {
-            return None;
+impl<'a> Resolver<'a> {
+    fn new(wb: &'a gridcraft_model::Workbook) -> Self {
+        let mut by_name: std::collections::HashMap<(Option<usize>, String), Vec<usize>> = std::collections::HashMap::new();
+        for (i, n) in wb.names.iter().enumerate() {
+            by_name.entry((n.scope, gridcraft_formula::fold_name(&n.name))).or_default().push(i);
         }
+        Self { wb, by_name, memo: std::collections::HashMap::new() }
+    }
+
+    /// The first name of scope `scope` that `same` accepts, as a scan of `wb.names` finds it.
+    /// Names `same` accepts fold alike, so only that bucket is checked.
+    fn find(&self, scope: Option<usize>, body: &str, same: impl Fn(&str, &str) -> bool) -> Option<usize> {
+        self.by_name
+            .get(&(scope, gridcraft_formula::fold_name(body)))?
+            .iter()
+            .copied()
+            .find(|&i| self.wb.names.get(i).is_some_and(|n| same(&n.name, body)))
+    }
+
+    /// Where one part of a Go To reference points, seen from sheet `sheet`: the sheet, how many
+    /// areas (appended to `areas` when given), and whether a defined name or a table gave them.
+    /// `Sheet2!Name` is the name scoped to Sheet2. A name counts when what it refers to is a
+    /// reference; a constant or a formula is not one.
+    fn target(&mut self, sheet: usize, part: &str, depth: usize, areas: Option<&mut Vec<RangeRef>>) -> Option<(usize, usize, bool)> {
+        let wb = self.wb;
+        if part.is_empty() || depth > GO_TO_NAME_DEPTH {
+            return None;
+        }
+        let (prefix, body) = split_sheet(part);
+        let on = match &prefix {
+            Some(n) => wb.sheet_index(n)?,
+            None => sheet,
+        };
+        if let Some(r) = RangeRef::parse(&body.replace('$', "")) {
+            if let Some(a) = areas {
+                a.push(r);
+            }
+            return Some((on, 1, false));
+        }
+        // As `Workbook::name`: the sheet's own name, else the workbook's.
+        let name = match prefix {
+            Some(_) => self.find(Some(on), body, gridcraft_formula::same_name),
+            None => self.find(Some(sheet), body, str::eq_ignore_ascii_case).or_else(|| self.find(None, body, str::eq_ignore_ascii_case)),
+        };
+        if let Some(i) = name {
+            return self.name_areas(i, sheet, depth, areas).map(|(t, n)| (t, n, true));
+        }
+        if prefix.is_none()
+            && let Some((si, ti)) = wb.table(body)
+        {
+            // As in Excel, a table's name stands for its data, without the header and totals rows.
+            let t = wb.sheet(si)?.tables.get(ti)?;
+            if let Some(a) = areas {
+                a.push(t.data_range().unwrap_or(t.range));
+            }
+            return Some((si, 1, true));
+        }
+        None
+    }
+
+    /// The sheet and number of areas defined name `wb.names[i]` refers to, seen from sheet
+    /// `sheet`, when that is a reference; the areas are appended to `areas` when given.
+    fn name_areas(&mut self, i: usize, sheet: usize, depth: usize, mut areas: Option<&mut Vec<RangeRef>>) -> Option<(usize, usize)> {
+        let key = (i, sheet, depth);
+        if areas.is_none()
+            && let Some(known) = self.memo.get(&key)
+        {
+            return *known;
+        }
+        let out = self.name_areas_uncached(i, sheet, depth, areas.as_deref_mut());
+        if areas.is_none() {
+            self.memo.insert(key, out);
+        }
+        out
+    }
+
+    fn name_areas_uncached(&mut self, i: usize, sheet: usize, depth: usize, mut areas: Option<&mut Vec<RangeRef>>) -> Option<(usize, usize)> {
+        let n = self.wb.names.get(i)?;
+        let from = n.scope.unwrap_or(sheet);
+        let formula = n.formula.trim().trim_start_matches('=');
+        let mut target: Option<usize> = None;
+        let mut count = 0usize;
+        for p in reference_parts(formula) {
+            let (s, found, _) = self.target(from, p, depth + 1, areas.as_deref_mut())?;
+            if target.is_some_and(|t| t != s) {
+                return None;
+            }
+            target = Some(s);
+            count += found;
+            if count > GO_TO_MAX_AREAS {
+                return None;
+            }
+        }
+        target.map(|t| (t, count))
     }
-    target.map(|t| (t, areas))
 }
 
 /// The names the Go To dialog lists, seen from sheet `sheet`: the named ranges of the workbook and
@@ -137,11 +196,13 @@ fn name_areas(wb: &gridcraft_model::Workbook, n: &gridcraft_model::DefinedName,
 pub fn go_to_names(wb: &gridcraft_model::Workbook, sheet: usize) -> Vec<String> {
     let own: std::collections::HashSet<String> =
         wb.names.iter().filter(|n| n.scope == Some(sheet)).map(|n| gridcraft_formula::fold_name(&n.name)).collect();
+    let mut names = Resolver::new(wb);
     let mut out: Vec<String> = wb
         .names
         .iter()
-        .filter(|n| !n.hidden && name_areas(wb, n, sheet, 0).is_some())
-        .filter_map(|n| match n.scope {
+        .enumerate()
+        .filter(|(i, n)| !n.hidden && names.name_areas(*i, sheet, 0, None).is_some())
+        .filter_map(|(_, n)| match n.scope {
             None if own.contains(&gridcraft_formula::fold_name(&n.name)) => None,
             None => Some(n.name.clone()),
             Some(s) if s == sheet => Some(n.name.clone()),

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

@@ -42,6 +42,28 @@ fn go_to_lists_the_named_ranges_of_every_sheet() {
     assert_eq!(list["names"], json!(["Areas", "Local", "Price", "Sheet1!Own", "type"]), "{list}");
 }
 
+/// Thousands of names that alias other names are listed with one lookup per alias, not a scan of
+/// every name for each; aliases resolve through the chain like a single name does.
+#[test]
+fn go_to_lists_many_aliases_and_follows_them() {
+    let mut s = go_to_workbook();
+    let wb = std::sync::Arc::make_mut(&mut s.doc_mut().unwrap().wb);
+    let alias = |name: String, formula: String| gridcraft_model::DefinedName { name, scope: None, formula, comment: String::new(), hidden: false };
+    wb.names.push(alias("Chain0".into(), "Areas".into()));
+    for i in 1..20_000 {
+        wb.names.push(alias(format!("Chain{i}"), format!("Chain{},price", i - 1)));
+    }
+    let list = s.execute("edit.goTo", json!({"list": true})).unwrap();
+    let names: Vec<&str> = list["names"].as_array().unwrap().iter().filter_map(|n| n.as_str()).collect();
+    // Chain0..Chain6 are within the name depth Go To follows; longer chains are not ranges.
+    for i in 0..7 {
+        assert!(names.contains(&format!("Chain{i}").as_str()), "Chain{i} in {names:?}");
+    }
+    assert!(!names.contains(&"Chain7"), "{names:?}");
+    let out = s.execute("edit.goTo", json!({"reference": "chain1"})).unwrap();
+    assert_eq!(out["selection"], "A1,C3:C4,B2:B5", "{out}");
+}
+
 #[test]
 fn go_to_a_name_scoped_to_another_sheet_goes_to_that_sheet() {
     let mut s = go_to_workbook();
@@ -353,36 +375,6 @@ fn cut_paste_that_overflows_the_grid_moves_nothing() {
     assert_eq!(get(&mut s, "XFD2")["value"], json!(2.0));
 }
 
-#[test]
-fn replace_refuses_text_that_would_grow_past_a_cell() {
-    // 10,000 matches × a 1,000-character replacement would make a 10 MB cell (and a few such
-    // cells gigabytes); the replacement is refused before that text is built.
-    let mut s = Session::new();
-    s.new_workbook();
-    let long = "a".repeat(10_000);
-    s.execute("range.setValues", json!({"range": "A1", "values": [[long.clone()], ["abc"]]})).unwrap();
-    for case in [false, true] {
-        let err = s.execute("edit.replace", json!({"what": "a", "with": "x".repeat(1_000), "matchCase": case})).expect_err("too long");
-        assert!(err.to_string().contains("too long"), "{err}");
-        assert_eq!(s.execute("cell.get", json!({"cell": "A1"})).unwrap()["value"], json!(long));
-        assert_eq!(s.execute("cell.get", json!({"cell": "A2"})).unwrap()["value"], json!("abc"));
-    }
-    // A replacement that stays within a cell's limit still happens.
-    s.execute("edit.replace", json!({"what": "b", "with": "x".repeat(100)})).unwrap();
-    assert_eq!(s.execute("cell.get", json!({"cell": "A2"})).unwrap()["value"], json!(format!("a{}c", "x".repeat(100))));
-}
-
-#[test]
-fn bounded_replace_stops_at_its_limit() {
-    use super::find::{replace_ci_within, replace_cs_within};
-    assert_eq!(replace_cs_within("abab", "a", "xy", 6).as_deref(), Some("xybxyb"));
-    assert_eq!(replace_cs_within("abab", "a", "xy", 5), None);
-    assert_eq!(replace_ci_within("AbAb", "a", "xy", 6).as_deref(), Some("xybxyb"));
-    assert_eq!(replace_ci_within("AbAb", "a", "xy", 5), None);
-    assert_eq!(replace_cs_within("abc", "z", "", 3).as_deref(), Some("abc"));
-    assert_eq!(replace_cs_within("abc", "z", "", 2), None);
-}
-
 #[test]
 fn replace_case_insensitive() {
     assert_eq!(replace_ci("Apple apple APPLE", "apple", "pear"), "pear pear pear");