formualizer_eval/engine/graph/
names.rs

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

formualizer_eval/engine/graph/
names.rs
