formualizer_eval/engine/graph/
names.rs

1use super::*;
2use formualizer_common::parse_a1_1based;
3
4#[inline]
5fn normalize_ascii_key(name: &str) -> String {
6    name.to_ascii_lowercase()
7}
8
9/// Validate that a name conforms to Excel naming rules.
10fn is_valid_excel_name(name: &str) -> bool {
11    // Excel name rules:
12    // 1. Must start with a letter, underscore, or backslash
13    // 2. Can contain letters, numbers, periods, and underscores
14    // 3. Cannot be a cell reference (like A1, B2, etc.)
15    // 4. Cannot exceed 255 characters
16    // 5. Cannot contain spaces
17
18    if name.is_empty() || name.len() > 255 {
19        return false;
20    }
21
22    if parse_a1_1based(name).is_ok() {
23        return false;
24    }
25
26    let mut chars = name.chars();
27
28    // First character must be letter, underscore, or backslash
29    if let Some(first) = chars.next()
30        && !first.is_alphabetic()
31        && first != '_'
32        && first != '\\'
33    {
34        return false;
35    }
36
37    // Remaining characters must be letters, digits, periods, or underscores
38    for c in chars {
39        if !c.is_alphanumeric() && c != '.' && c != '_' {
40            return false;
41        }
42    }
43
44    true
45}
46
47/// Helper function to adjust a named definition during structural operations.
48fn adjust_named_definition(
49    definition: &mut NamedDefinition,
50    adjuster: &crate::engine::graph::editor::reference_adjuster::ReferenceAdjuster,
51    operation: &crate::engine::graph::editor::reference_adjuster::ShiftOperation,
52) -> Result<(), ExcelError> {
53    match definition {
54        NamedDefinition::Cell(cell_ref) => {
55            if let Some(adjusted) = adjuster.adjust_cell_ref(cell_ref, operation) {
56                *cell_ref = adjusted;
57            } else {
58                return Err(ExcelError::new(ExcelErrorKind::Ref));
59            }
60        }
61        NamedDefinition::Range(range_ref) => {
62            let adjusted_start = adjuster.adjust_cell_ref(&range_ref.start, operation);
63            let adjusted_end = adjuster.adjust_cell_ref(&range_ref.end, operation);
64
65            if let (Some(start), Some(end)) = (adjusted_start, adjusted_end) {
66                range_ref.start = start;
67                range_ref.end = end;
68            } else {
69                return Err(ExcelError::new(ExcelErrorKind::Ref));
70            }
71        }
72        NamedDefinition::Literal(_) => {
73            // Constant names are not affected by structural shifts.
74        }
75        NamedDefinition::Formula {
76            ast,
77            dependencies,
78            range_deps,
79        } => {
80            let adjusted_ast = adjuster.adjust_ast(ast, operation);
81            *ast = adjusted_ast;
82
83            dependencies.clear();
84            range_deps.clear();
85        }
86    }
87    Ok(())
88}
89
90impl DependencyGraph {
91    #[inline]
92    fn name_lookup_key(&self, name: &str) -> String {
93        if self.config.case_sensitive_names {
94            name.to_string()
95        } else {
96            normalize_ascii_key(name)
97        }
98    }
99
100    fn canonical_name_in_scope(&self, scope: NameScope, name: &str) -> Option<String> {
101        let key = self.name_lookup_key(name);
102        match scope {
103            NameScope::Workbook => self.named_ranges_lookup.get(&key).cloned(),
104            NameScope::Sheet(sheet_id) => self
105                .sheet_named_ranges_lookup
106                .get(&(sheet_id, key))
107                .cloned(),
108        }
109    }
110
111    fn next_name_coord(&mut self) -> AbsCoord {
112        let seq = self.name_vertex_seq;
113        self.name_vertex_seq = self.name_vertex_seq.wrapping_add(1);
114        let row = (seq / 16_384).min(0x000F_FFFF);
115        let col = seq % 16_384;
116        AbsCoord::new(row, col)
117    }
118
119    pub(super) fn allocate_name_vertex(&mut self, scope: NameScope) -> VertexId {
120        let coord = self.next_name_coord();
121        let sheet_id = match scope {
122            NameScope::Sheet(id) => id,
123            NameScope::Workbook => self.default_sheet_id,
124        };
125        let vertex_id = self.store.allocate(coord, sheet_id, 0x01);
126        self.store.set_kind(vertex_id, VertexKind::NamedScalar);
127        self.store.set_dirty(vertex_id, true);
128        self.edges.add_vertex(coord, vertex_id.0);
129        self.dirty_vertices.insert(vertex_id);
130        vertex_id
131    }
132
133    // Named Range Methods
134
135    /// Define a new named range
136    pub fn define_name(
137        &mut self,
138        name: &str,
139        definition: NamedDefinition,
140        scope: NameScope,
141    ) -> Result<(), ExcelError> {
142        // Validate name
143        if !is_valid_excel_name(name) {
144            return Err(
145                ExcelError::new(ExcelErrorKind::Name).with_message(format!("Invalid name: {name}"))
146            );
147        }
148
149        // Check for duplicates / collisions (respect case-sensitivity config)
150        let lookup_key = self.name_lookup_key(name);
151        match scope {
152            NameScope::Workbook => {
153                if let Some(existing) = self.named_ranges_lookup.get(&lookup_key) {
154                    return Err(ExcelError::new(ExcelErrorKind::Name).with_message(format!(
155                        "Name collision under normalization: '{name}' conflicts with '{existing}'"
156                    )));
157                }
158            }
159            NameScope::Sheet(sheet_id) => {
160                if let Some(existing) = self
161                    .sheet_named_ranges_lookup
162                    .get(&(sheet_id, lookup_key.clone()))
163                {
164                    return Err(ExcelError::new(ExcelErrorKind::Name).with_message(format!(
165                        "Name collision under normalization in sheet: '{name}' conflicts with '{existing}'"
166                    )));
167                }
168            }
169        }
170
171        let mut final_definition = definition;
172        // Extract dependencies if formula
173        if let NamedDefinition::Formula { ref ast, .. } = final_definition {
174            let (deps, range_deps, _, _) = self.extract_dependencies(
175                ast,
176                match scope {
177                    NameScope::Sheet(id) => id,
178                    NameScope::Workbook => self.default_sheet_id,
179                },
180            )?;
181            final_definition = NamedDefinition::Formula {
182                ast: ast.clone(),
183                dependencies: deps,
184                range_deps,
185            };
186        }
187
188        // Allocate vertex only after dependency extraction succeeds
189        let vertex_id = self.allocate_name_vertex(scope);
190
191        let named_range = NamedRange {
192            definition: final_definition,
193            scope,
194            dependents: FxHashSet::default(),
195            vertex: vertex_id,
196        };
197
198        if matches!(named_range.definition, NamedDefinition::Range(_)) {
199            self.store.set_kind(vertex_id, VertexKind::NamedArray);
200        } else {
201            self.store.set_kind(vertex_id, VertexKind::NamedScalar);
202        }
203
204        let referenced_names =
205            self.rebuild_name_dependencies(vertex_id, &named_range.definition, scope);
206        if !referenced_names.is_empty() {
207            self.attach_vertex_to_names(vertex_id, &referenced_names);
208        }
209
210        let key = name.to_string();
211
212        match scope {
213            NameScope::Workbook => {
214                self.named_ranges.insert(key.clone(), named_range);
215                self.named_ranges_lookup
216                    .insert(self.name_lookup_key(&key), key.clone());
217            }
218            NameScope::Sheet(id) => {
219                self.sheet_named_ranges
220                    .insert((id, key.clone()), named_range);
221                self.sheet_named_ranges_lookup
222                    .insert((id, self.name_lookup_key(&key)), key.clone());
223            }
224        }
225
226        self.name_vertex_lookup.insert(vertex_id, (scope, key));
227        self.resolve_pending_name_references(scope, name, vertex_id);
228
229        Ok(())
230    }
231
232    /// Iterate workbook-scoped named ranges (for bindings/testing)
233    pub fn named_ranges_iter(&self) -> impl Iterator<Item = (&String, &NamedRange)> {
234        self.named_ranges.iter()
235    }
236
237    /// Iterate sheet-scoped named ranges (for bindings/testing)
238    pub fn sheet_named_ranges_iter(
239        &self,
240    ) -> impl Iterator<Item = (&(SheetId, String), &NamedRange)> {
241        self.sheet_named_ranges.iter()
242    }
243
244    pub fn resolve_name_entry(&self, name: &str, current_sheet: SheetId) -> Option<&NamedRange> {
245        if self.config.case_sensitive_names {
246            self.sheet_named_ranges
247                .get(&(current_sheet, name.to_string()))
248                .or_else(|| self.named_ranges.get(name))
249        } else {
250            let key = self.name_lookup_key(name);
251            self.sheet_named_ranges_lookup
252                .get(&(current_sheet, key.clone()))
253                .and_then(|canon| self.sheet_named_ranges.get(&(current_sheet, canon.clone())))
254                .or_else(|| {
255                    self.named_ranges_lookup
256                        .get(&key)
257                        .and_then(|canon| self.named_ranges.get(canon))
258                })
259        }
260    }
261
262    /// Resolve a named range to its definition
263    pub fn resolve_name(&self, name: &str, current_sheet: SheetId) -> Option<&NamedDefinition> {
264        self.resolve_name_entry(name, current_sheet)
265            .map(|nr| &nr.definition)
266    }
267
268    pub fn named_range_by_vertex(&self, vertex: VertexId) -> Option<&NamedRange> {
269        self.name_vertex_lookup
270            .get(&vertex)
271            .and_then(|(scope, name)| match scope {
272                NameScope::Workbook => self.named_ranges.get(name),
273                NameScope::Sheet(sheet_id) => {
274                    self.sheet_named_ranges.get(&(*sheet_id, name.clone()))
275                }
276            })
277    }
278
279    /// Update an existing named range definition
280    pub fn update_name(
281        &mut self,
282        name: &str,
283        new_definition: NamedDefinition,
284        scope: NameScope,
285    ) -> Result<(), ExcelError> {
286        let Some(canon_name) = self.canonical_name_in_scope(scope, name) else {
287            return Err(ExcelError::new(ExcelErrorKind::Name)
288                .with_message(format!("Name not found: {name}")));
289        };
290
291        // First collect dependents to avoid borrow checker issues
292        let dependents_to_dirty = match scope {
293            NameScope::Workbook => self
294                .named_ranges
295                .get(&canon_name)
296                .map(|nr| nr.dependents.iter().copied().collect::<Vec<_>>()),
297            NameScope::Sheet(id) => self
298                .sheet_named_ranges
299                .get(&(id, canon_name.clone()))
300                .map(|nr| nr.dependents.iter().copied().collect::<Vec<_>>()),
301        };
302
303        if let Some(dependents) = dependents_to_dirty {
304            // Mark all dependents as dirty
305            for vertex_id in dependents {
306                self.mark_vertex_dirty(vertex_id);
307            }
308
309            // Now update the definition
310            let named_range = match scope {
311                NameScope::Workbook => self.named_ranges.get_mut(&canon_name),
312                NameScope::Sheet(id) => self.sheet_named_ranges.get_mut(&(id, canon_name.clone())),
313            };
314
315            let mut update_data: Option<(VertexId, NameScope, NamedDefinition, bool)> = None;
316            if let Some(named_range) = named_range {
317                named_range.definition = new_definition;
318                named_range.dependents.clear();
319                let is_range = matches!(named_range.definition, NamedDefinition::Range(_));
320                update_data = Some((
321                    named_range.vertex,
322                    named_range.scope,
323                    named_range.definition.clone(),
324                    is_range,
325                ));
326            }
327
328            if let Some((vertex, scope_value, definition_snapshot, is_range)) = update_data {
329                self.detach_vertex_from_names(vertex);
330
331                if is_range {
332                    self.store.set_kind(vertex, VertexKind::NamedArray);
333                } else {
334                    self.store.set_kind(vertex, VertexKind::NamedScalar);
335                }
336                self.store.set_dirty(vertex, true);
337                self.dirty_vertices.insert(vertex);
338
339                let referenced_names =
340                    self.rebuild_name_dependencies(vertex, &definition_snapshot, scope_value);
341                if !referenced_names.is_empty() {
342                    self.attach_vertex_to_names(vertex, &referenced_names);
343                }
344            }
345
346            Ok(())
347        } else {
348            Err(ExcelError::new(ExcelErrorKind::Name)
349                .with_message(format!("Name not found: {name}")))
350        }
351    }
352
353    /// Delete a named range
354    pub fn delete_name(&mut self, name: &str, scope: NameScope) -> Result<(), ExcelError> {
355        let Some(canon_name) = self.canonical_name_in_scope(scope, name) else {
356            return Err(ExcelError::new(ExcelErrorKind::Name)
357                .with_message(format!("Name not found: {name}")));
358        };
359
360        let named_range = match scope {
361            NameScope::Workbook => {
362                let removed = self.named_ranges.remove(&canon_name);
363                let key = self.name_lookup_key(&canon_name);
364                self.named_ranges_lookup.remove(&key);
365                removed
366            }
367            NameScope::Sheet(id) => {
368                let removed = self.sheet_named_ranges.remove(&(id, canon_name.clone()));
369                let key = self.name_lookup_key(&canon_name);
370                self.sheet_named_ranges_lookup.remove(&(id, key));
371                removed
372            }
373        };
374
375        if let Some(named_range) = named_range {
376            let mut affected: FxHashSet<VertexId> = FxHashSet::default();
377            for &vertex_id in &named_range.dependents {
378                affected.insert(vertex_id);
379            }
380            for (vertex_id, names) in self.vertex_to_names.iter() {
381                if names.contains(&named_range.vertex) {
382                    affected.insert(*vertex_id);
383                }
384            }
385            for vertex_id in affected {
386                self.mark_vertex_dirty(vertex_id);
387                if let Some(names) = self.vertex_to_names.get_mut(&vertex_id) {
388                    names.retain(|vid| *vid != named_range.vertex);
389                    if names.is_empty() {
390                        self.vertex_to_names.remove(&vertex_id);
391                    }
392                }
393            }
394            self.mark_named_vertex_deleted(&named_range);
395            Ok(())
396        } else {
397            Err(ExcelError::new(ExcelErrorKind::Name)
398                .with_message(format!("Name not found: {name}")))
399        }
400    }
401
402    pub(super) fn detach_vertex_from_names(&mut self, vertex: VertexId) {
403        if let Some(prior) = self.vertex_to_names.remove(&vertex) {
404            for name_vertex in prior {
405                if let Some((scope, name)) = self.name_vertex_lookup.get(&name_vertex).cloned() {
406                    match scope {
407                        NameScope::Workbook => {
408                            if let Some(entry) = self.named_ranges.get_mut(&name) {
409                                entry.dependents.remove(&vertex);
410                            }
411                        }
412                        NameScope::Sheet(sheet_id) => {
413                            if let Some(entry) =
414                                self.sheet_named_ranges.get_mut(&(sheet_id, name.clone()))
415                            {
416                                entry.dependents.remove(&vertex);
417                            }
418                        }
419                    }
420                }
421            }
422        }
423    }
424
425    pub(crate) fn attach_vertex_to_names(&mut self, vertex: VertexId, names: &[VertexId]) {
426        if names.is_empty() {
427            return;
428        }
429        let mut unique = FxHashSet::default();
430        let mut recorded = Vec::new();
431        for &name_vertex in names {
432            if !unique.insert(name_vertex) {
433                continue;
434            }
435            if let Some((scope, name)) = self.name_vertex_lookup.get(&name_vertex).cloned() {
436                match scope {
437                    NameScope::Workbook => {
438                        if let Some(entry) = self.named_ranges.get_mut(&name) {
439                            entry.dependents.insert(vertex);
440                        }
441                    }
442                    NameScope::Sheet(sheet_id) => {
443                        if let Some(entry) =
444                            self.sheet_named_ranges.get_mut(&(sheet_id, name.clone()))
445                        {
446                            entry.dependents.insert(vertex);
447                        }
448                    }
449                }
450                recorded.push(name_vertex);
451            }
452        }
453        if !recorded.is_empty() {
454            self.vertex_to_names.insert(vertex, recorded);
455        }
456    }
457
458    pub(super) fn unregister_name_cell_dependencies(&mut self, name_vertex: VertexId) {
459        if let Some(prev) = self.name_to_cell_dependencies.remove(&name_vertex) {
460            for dep in prev {
461                if let Some(set) = self.cell_to_name_dependents.get_mut(&dep) {
462                    set.remove(&name_vertex);
463                    if set.is_empty() {
464                        self.cell_to_name_dependents.remove(&dep);
465                    }
466                }
467            }
468        }
469    }
470
471    pub(super) fn register_name_cell_dependencies(
472        &mut self,
473        name_vertex: VertexId,
474        dependencies: &[VertexId],
475    ) {
476        self.unregister_name_cell_dependencies(name_vertex);
477        if dependencies.is_empty() {
478            return;
479        }
480        for dep in dependencies {
481            self.cell_to_name_dependents
482                .entry(*dep)
483                .or_default()
484                .insert(name_vertex);
485        }
486        self.name_to_cell_dependencies
487            .insert(name_vertex, dependencies.to_vec());
488    }
489
490    pub(crate) fn record_pending_name_reference(
491        &mut self,
492        sheet_id: SheetId,
493        name: &str,
494        formula_vertex: VertexId,
495    ) {
496        let key = self.name_lookup_key(name);
497        self.pending_name_links
498            .entry(key)
499            .or_default()
500            .push((sheet_id, formula_vertex));
501    }
502
503    fn resolve_pending_name_references(
504        &mut self,
505        scope: NameScope,
506        name: &str,
507        named_vertex: VertexId,
508    ) {
509        let key = self.name_lookup_key(name);
510        if let Some(mut entries) = self.pending_name_links.remove(&key) {
511            let mut remaining: Vec<(SheetId, VertexId)> = Vec::new();
512            for (sheet_id, formula_vertex) in entries.drain(..) {
513                let attach = match scope {
514                    NameScope::Workbook => true,
515                    NameScope::Sheet(expected) => expected == sheet_id,
516                };
517                if attach {
518                    self.add_dependent_edges(formula_vertex, &[named_vertex]);
519                    self.attach_vertex_to_names(formula_vertex, &[named_vertex]);
520                } else {
521                    remaining.push((sheet_id, formula_vertex));
522                }
523            }
524            if !remaining.is_empty() {
525                self.pending_name_links.insert(key, remaining);
526            }
527        }
528    }
529
530    pub(super) fn name_depends_on_vertex(
531        &self,
532        name_vertex: VertexId,
533        target: VertexId,
534        visited: &mut FxHashSet<VertexId>,
535    ) -> bool {
536        if !visited.insert(name_vertex) {
537            return false;
538        }
539
540        for dependency in self.edges.out_edges(name_vertex).iter().copied() {
541            if dependency == target {
542                return true;
543            }
544
545            if matches!(
546                self.store.kind(dependency),
547                VertexKind::NamedScalar | VertexKind::NamedArray
548            ) && self.name_depends_on_vertex(dependency, target, visited)
549            {
550                return true;
551            }
552        }
553
554        false
555    }
556
557    pub(super) fn rebuild_name_dependencies(
558        &mut self,
559        vertex: VertexId,
560        definition: &NamedDefinition,
561        scope: NameScope,
562    ) -> Vec<VertexId> {
563        self.remove_dependent_edges(vertex);
564        self.unregister_name_cell_dependencies(vertex);
565
566        let mut dependencies: Vec<VertexId> = Vec::new();
567        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
568        let mut placeholders = Vec::new();
569
570        match definition {
571            NamedDefinition::Cell(cell_ref) => {
572                let vertex_id = self.get_or_create_vertex(cell_ref, &mut placeholders);
573                dependencies.push(vertex_id);
574            }
575            NamedDefinition::Range(range_ref) => {
576                let height = range_ref
577                    .end
578                    .coord
579                    .row()
580                    .saturating_sub(range_ref.start.coord.row())
581                    + 1;
582                let width = range_ref
583                    .end
584                    .coord
585                    .col()
586                    .saturating_sub(range_ref.start.coord.col())
587                    + 1;
588                let size = (width * height) as usize;
589
590                if size <= self.config.range_expansion_limit {
591                    for row in range_ref.start.coord.row()..=range_ref.end.coord.row() {
592                        for col in range_ref.start.coord.col()..=range_ref.end.coord.col() {
593                            let coord = Coord::new(row, col, true, true);
594                            let addr = CellRef::new(range_ref.start.sheet_id, coord);
595                            let vertex_id = self.get_or_create_vertex(&addr, &mut placeholders);
596                            dependencies.push(vertex_id);
597                        }
598                    }
599                } else {
600                    let sheet_loc = SharedSheetLocator::Id(range_ref.start.sheet_id);
601                    let sr = formualizer_common::AxisBound::new(
602                        range_ref.start.coord.row(),
603                        range_ref.start.coord.row_abs(),
604                    );
605                    let sc = formualizer_common::AxisBound::new(
606                        range_ref.start.coord.col(),
607                        range_ref.start.coord.col_abs(),
608                    );
609                    let er = formualizer_common::AxisBound::new(
610                        range_ref.end.coord.row(),
611                        range_ref.end.coord.row_abs(),
612                    );
613                    let ec = formualizer_common::AxisBound::new(
614                        range_ref.end.coord.col(),
615                        range_ref.end.coord.col_abs(),
616                    );
617                    if let Ok(r) = SharedRangeRef::from_parts(
618                        sheet_loc,
619                        Some(sr),
620                        Some(sc),
621                        Some(er),
622                        Some(ec),
623                    ) {
624                        range_dependencies.push(r.into_owned());
625                    }
626                }
627            }
628            NamedDefinition::Literal(_) => {
629                // No dependencies.
630            }
631            NamedDefinition::Formula {
632                dependencies: formula_deps,
633                range_deps,
634                ..
635            } => {
636                dependencies.extend(formula_deps.iter().copied());
637                range_dependencies.extend(range_deps.iter().cloned());
638            }
639        }
640
641        if !dependencies.is_empty() {
642            self.add_dependent_edges(vertex, &dependencies);
643        }
644        self.register_name_cell_dependencies(vertex, &dependencies);
645
646        if !range_dependencies.is_empty() {
647            let sheet_id = match scope {
648                NameScope::Sheet(id) => id,
649                NameScope::Workbook => self.default_sheet_id,
650            };
651            self.add_range_dependent_edges(vertex, &range_dependencies, sheet_id);
652        }
653
654        dependencies
655            .iter()
656            .filter(|vid| {
657                matches!(
658                    self.store.kind(**vid),
659                    VertexKind::NamedScalar | VertexKind::NamedArray
660                )
661            })
662            .copied()
663            .collect()
664    }
665
666    pub fn adjust_named_ranges(
667        &mut self,
668        operation: &crate::engine::graph::editor::reference_adjuster::ShiftOperation,
669    ) -> Result<(), ExcelError> {
670        let adjuster = crate::engine::graph::editor::reference_adjuster::ReferenceAdjuster::new();
671
672        // Adjust workbook-scoped names
673        for named_range in self.named_ranges.values_mut() {
674            adjust_named_definition(&mut named_range.definition, &adjuster, operation)?;
675        }
676
677        // Adjust sheet-scoped names
678        for named_range in self.sheet_named_ranges.values_mut() {
679            adjust_named_definition(&mut named_range.definition, &adjuster, operation)?;
680        }
681
682        Ok(())
683    }
684
685    /// Mark a vertex as having a #NAME! error
686    pub fn mark_as_name_error(&mut self, vertex_id: VertexId) {
687        // Mark the vertex as dirty
688        self.mark_vertex_dirty(vertex_id);
689    }
690
691    pub(super) fn mark_named_vertex_deleted(&mut self, named_range: &NamedRange) {
692        self.detach_vertex_from_names(named_range.vertex);
693        self.remove_dependent_edges(named_range.vertex);
694        self.unregister_name_cell_dependencies(named_range.vertex);
695        self.store.mark_deleted(named_range.vertex, true);
696        self.vertex_values.remove(&named_range.vertex);
697        self.vertex_formulas.remove(&named_range.vertex);
698        self.dirty_vertices.remove(&named_range.vertex);
699        self.volatile_vertices.remove(&named_range.vertex);
700        self.vertex_to_names.remove(&named_range.vertex);
701        self.name_vertex_lookup.remove(&named_range.vertex);
702    }
703}
formualizer_eval/engine/graph/names.rs

formualizer_eval/engine/graph/
names.rs
