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/chart/src/raster.rs

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

crates/chart/src/render/lines.rs

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

crates/chart/src/resolve.rs

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

crates/engine/src/cmd/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();