formualizer_eval/engine/graph/
formula_analysis.rs

1use super::*;
2use formualizer_parse::parser::{ASTNode, ASTNodeType, ReferenceType};
3
4// Type alias for complex return types (local to analysis).
5type ExtractDependenciesResult = Result<
6    (
7        Vec<VertexId>,
8        Vec<SharedRangeRef<'static>>,
9        Vec<CellRef>,
10        Vec<VertexId>,
11    ),
12    ExcelError,
13>;
14
15type ExtractDependenciesWithPendingNamesResult = Result<
16    (
17        Vec<VertexId>,
18        Vec<SharedRangeRef<'static>>,
19        Vec<CellRef>,
20        Vec<VertexId>,
21        Vec<String>,
22    ),
23    ExcelError,
24>;
25
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
27enum UnresolvedNamePolicy {
28    Error,
29    Collect,
30}
31
32impl DependencyGraph {
33    // Helper methods for formula analysis / dependency extraction.
34
35    pub(super) fn extract_dependencies(
36        &mut self,
37        ast: &ASTNode,
38        current_sheet_id: SheetId,
39    ) -> ExtractDependenciesResult {
40        let (dependencies, ranges, placeholders, named_dependencies, _pending_names) =
41            self.extract_dependencies_inner(ast, current_sheet_id, UnresolvedNamePolicy::Error)?;
42        Ok((dependencies, ranges, placeholders, named_dependencies))
43    }
44
45    pub(super) fn extract_dependencies_with_pending_names(
46        &mut self,
47        ast: &ASTNode,
48        current_sheet_id: SheetId,
49    ) -> ExtractDependenciesWithPendingNamesResult {
50        self.extract_dependencies_inner(ast, current_sheet_id, UnresolvedNamePolicy::Collect)
51    }
52
53    pub(super) fn extract_dependencies_arena(
54        &mut self,
55        ast_id: AstNodeId,
56        current_sheet_id: SheetId,
57    ) -> ExtractDependenciesResult {
58        let (dependencies, ranges, placeholders, named_dependencies, _pending_names) = self
59            .extract_dependencies_inner_arena(
60                ast_id,
61                current_sheet_id,
62                UnresolvedNamePolicy::Error,
63            )?;
64        Ok((dependencies, ranges, placeholders, named_dependencies))
65    }
66
67    pub(super) fn extract_dependencies_with_pending_names_arena(
68        &mut self,
69        ast_id: AstNodeId,
70        current_sheet_id: SheetId,
71    ) -> ExtractDependenciesWithPendingNamesResult {
72        self.extract_dependencies_inner_arena(
73            ast_id,
74            current_sheet_id,
75            UnresolvedNamePolicy::Collect,
76        )
77    }
78
79    fn extract_dependencies_inner_arena(
80        &mut self,
81        ast_id: AstNodeId,
82        current_sheet_id: SheetId,
83        unresolved_name_policy: UnresolvedNamePolicy,
84    ) -> ExtractDependenciesWithPendingNamesResult {
85        let mut dependencies = FxHashSet::default();
86        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
87        let mut created_placeholders = Vec::new();
88        let mut named_dependencies = Vec::new();
89        let mut unresolved_names = FxHashSet::default();
90        let mut local_scopes: Vec<FxHashSet<String>> = Vec::new();
91        self.extract_dependencies_recursive_arena(
92            ast_id,
93            current_sheet_id,
94            &mut dependencies,
95            &mut range_dependencies,
96            &mut created_placeholders,
97            &mut named_dependencies,
98            &mut unresolved_names,
99            &mut local_scopes,
100            unresolved_name_policy,
101        )?;
102
103        // Deduplicate range references.
104        let mut deduped_ranges = Vec::new();
105        for range_ref in range_dependencies {
106            if !deduped_ranges.contains(&range_ref) {
107                deduped_ranges.push(range_ref);
108            }
109        }
110
111        named_dependencies.sort_unstable_by_key(|v| v.0);
112        named_dependencies.dedup_by_key(|v| v.0);
113
114        let mut unresolved_names: Vec<String> = unresolved_names.into_iter().collect();
115        unresolved_names.sort();
116
117        Ok((
118            dependencies.into_iter().collect(),
119            deduped_ranges,
120            created_placeholders,
121            named_dependencies,
122            unresolved_names,
123        ))
124    }
125
126    fn extract_dependencies_recursive_arena(
127        &mut self,
128        ast_id: AstNodeId,
129        current_sheet_id: SheetId,
130        dependencies: &mut FxHashSet<VertexId>,
131        range_dependencies: &mut Vec<SharedRangeRef<'static>>,
132        created_placeholders: &mut Vec<CellRef>,
133        named_dependencies: &mut Vec<VertexId>,
134        unresolved_names: &mut FxHashSet<String>,
135        local_scopes: &mut Vec<FxHashSet<String>>,
136        unresolved_name_policy: UnresolvedNamePolicy,
137    ) -> Result<(), ExcelError> {
138        let Some(node) = self.data_store.get_node(ast_id).cloned() else {
139            return Err(
140                ExcelError::new(ExcelErrorKind::Value).with_message("Missing interned formula AST")
141            );
142        };
143
144        match node {
145            super::super::arena::ast::AstNodeData::Reference { ref_type, .. } => {
146                let reference = self
147                    .data_store
148                    .reconstruct_reference_type_for_eval(&ref_type, &self.sheet_reg);
149                match &reference {
150                    ReferenceType::External(ext) => match ext.kind {
151                        formualizer_parse::parser::ExternalRefKind::Cell { .. } => {
152                            let name = ext.raw.as_str();
153                            if let Some(source) = self.resolve_source_scalar_entry(name) {
154                                dependencies.insert(source.vertex);
155                            } else {
156                                return Err(ExcelError::new(ExcelErrorKind::Name)
157                                    .with_message(format!("Undefined name: {name}")));
158                            }
159                        }
160                        formualizer_parse::parser::ExternalRefKind::Range { .. } => {
161                            let name = ext.raw.as_str();
162                            if let Some(source) = self.resolve_source_table_entry(name) {
163                                dependencies.insert(source.vertex);
164                            } else {
165                                return Err(ExcelError::new(ExcelErrorKind::Name)
166                                    .with_message(format!("Undefined table: {name}")));
167                            }
168                        }
169                    },
170                    ReferenceType::Cell { .. } => {
171                        let vertex_id = self.get_or_create_vertex_for_reference(
172                            &reference,
173                            current_sheet_id,
174                            created_placeholders,
175                        )?;
176                        dependencies.insert(vertex_id);
177                    }
178                    ReferenceType::Range {
179                        sheet,
180                        start_row,
181                        start_col,
182                        end_row,
183                        end_col,
184                        ..
185                    } => {
186                        // If any bound is missing (infinite/partial range), always keep compressed.
187                        let has_unbounded = start_row.is_none()
188                            || end_row.is_none()
189                            || start_col.is_none()
190                            || end_col.is_none();
191                        if has_unbounded {
192                            if let Some(SharedRef::Range(range)) = reference.to_sheet_ref_lossy() {
193                                let owned = range.into_owned();
194                                let sheet_id = match owned.sheet {
195                                    SharedSheetLocator::Id(id) => id,
196                                    SharedSheetLocator::Current => current_sheet_id,
197                                    SharedSheetLocator::Name(name) => {
198                                        self.resolve_existing_sheet_id(name.as_ref())?
199                                    }
200                                };
201                                range_dependencies.push(SharedRangeRef {
202                                    sheet: SharedSheetLocator::Id(sheet_id),
203                                    start_row: owned.start_row,
204                                    start_col: owned.start_col,
205                                    end_row: owned.end_row,
206                                    end_col: owned.end_col,
207                                });
208                            }
209                        } else {
210                            let (Some(sr), Some(sc), Some(er), Some(ec)) =
211                                (*start_row, *start_col, *end_row, *end_col)
212                            else {
213                                return Err(ExcelError::new(ExcelErrorKind::Ref));
214                            };
215
216                            if sr > er || sc > ec {
217                                return Err(ExcelError::new(ExcelErrorKind::Ref));
218                            }
219
220                            let height = er.saturating_sub(sr) + 1;
221                            let width = ec.saturating_sub(sc) + 1;
222                            let size = (width * height) as usize;
223
224                            if size <= self.config.range_expansion_limit {
225                                // Expand to individual cells.
226                                let sheet_id = match sheet {
227                                    Some(name) => self.resolve_existing_sheet_id(name)?,
228                                    None => current_sheet_id,
229                                };
230                                for row in sr..=er {
231                                    for col in sc..=ec {
232                                        let coord = Coord::from_excel(row, col, true, true);
233                                        let addr = CellRef::new(sheet_id, coord);
234                                        let vertex_id =
235                                            self.get_or_create_vertex(&addr, created_placeholders);
236                                        dependencies.insert(vertex_id);
237                                    }
238                                }
239                            } else {
240                                // Keep as a compressed range dependency.
241                                if let Some(SharedRef::Range(range)) =
242                                    reference.to_sheet_ref_lossy()
243                                {
244                                    let owned = range.into_owned();
245                                    let sheet_id = match owned.sheet {
246                                        SharedSheetLocator::Id(id) => id,
247                                        SharedSheetLocator::Current => current_sheet_id,
248                                        SharedSheetLocator::Name(name) => {
249                                            self.resolve_existing_sheet_id(name.as_ref())?
250                                        }
251                                    };
252                                    range_dependencies.push(SharedRangeRef {
253                                        sheet: SharedSheetLocator::Id(sheet_id),
254                                        start_row: owned.start_row,
255                                        start_col: owned.start_col,
256                                        end_row: owned.end_row,
257                                        end_col: owned.end_col,
258                                    });
259                                }
260                            }
261                        }
262                    }
263                    ReferenceType::NamedRange(name) => {
264                        let key = name.to_ascii_uppercase();
265                        if local_scopes.iter().rev().any(|scope| scope.contains(&key)) {
266                            return Ok(());
267                        }
268
269                        if let Some(named_range) = self.resolve_name_entry(name, current_sheet_id) {
270                            dependencies.insert(named_range.vertex);
271                            named_dependencies.push(named_range.vertex);
272                        } else if let Some(source) = self.resolve_source_scalar_entry(name) {
273                            dependencies.insert(source.vertex);
274                        } else {
275                            match unresolved_name_policy {
276                                UnresolvedNamePolicy::Error => {
277                                    return Err(ExcelError::new(ExcelErrorKind::Name)
278                                        .with_message(format!("Undefined name: {name}")));
279                                }
280                                UnresolvedNamePolicy::Collect => {
281                                    unresolved_names.insert(name.to_string());
282                                }
283                            }
284                        }
285                    }
286                    ReferenceType::Table(tref) => {
287                        if let Some(table) = self.resolve_table_entry(&tref.name) {
288                            dependencies.insert(table.vertex);
289                        } else if let Some(source) = self.resolve_source_table_entry(&tref.name) {
290                            dependencies.insert(source.vertex);
291                        } else {
292                            return Err(ExcelError::new(ExcelErrorKind::Name)
293                                .with_message(format!("Undefined table: {}", tref.name)));
294                        }
295                    }
296                    // 3D references parse correctly but aren't yet wired through
297                    // the dependency graph; treat them as no-op dependencies for
298                    // now so formulas containing them still load. Evaluation will
299                    // surface #N/IMPL! via the Resolver path.
300                    ReferenceType::Cell3D { .. } | ReferenceType::Range3D { .. } => {}
301                }
302            }
303            super::super::arena::ast::AstNodeData::BinaryOp {
304                left_id, right_id, ..
305            } => {
306                self.extract_dependencies_recursive_arena(
307                    left_id,
308                    current_sheet_id,
309                    dependencies,
310                    range_dependencies,
311                    created_placeholders,
312                    named_dependencies,
313                    unresolved_names,
314                    local_scopes,
315                    unresolved_name_policy,
316                )?;
317                self.extract_dependencies_recursive_arena(
318                    right_id,
319                    current_sheet_id,
320                    dependencies,
321                    range_dependencies,
322                    created_placeholders,
323                    named_dependencies,
324                    unresolved_names,
325                    local_scopes,
326                    unresolved_name_policy,
327                )?;
328            }
329            super::super::arena::ast::AstNodeData::UnaryOp { expr_id, .. } => {
330                self.extract_dependencies_recursive_arena(
331                    expr_id,
332                    current_sheet_id,
333                    dependencies,
334                    range_dependencies,
335                    created_placeholders,
336                    named_dependencies,
337                    unresolved_names,
338                    local_scopes,
339                    unresolved_name_policy,
340                )?;
341            }
342            super::super::arena::ast::AstNodeData::Function { name_id, .. } => {
343                let name = self.data_store.resolve_ast_string(name_id).to_string();
344                let args: Vec<AstNodeId> = self
345                    .data_store
346                    .get_args(ast_id)
347                    .map_or_else(Vec::new, |args| args.to_vec());
348                if name.eq_ignore_ascii_case("LET") {
349                    if args.len() >= 3 && args.len() % 2 == 1 {
350                        local_scopes.push(FxHashSet::default());
351
352                        for pair_idx in (0..args.len() - 1).step_by(2) {
353                            self.extract_dependencies_recursive_arena(
354                                args[pair_idx + 1],
355                                current_sheet_id,
356                                dependencies,
357                                range_dependencies,
358                                created_placeholders,
359                                named_dependencies,
360                                unresolved_names,
361                                local_scopes,
362                                unresolved_name_policy,
363                            )?;
364
365                            if let Some(local_name) = self.arena_named_range_name(args[pair_idx])
366                                && let Some(scope) = local_scopes.last_mut()
367                            {
368                                scope.insert(local_name.to_ascii_uppercase());
369                            }
370                        }
371
372                        self.extract_dependencies_recursive_arena(
373                            args[args.len() - 1],
374                            current_sheet_id,
375                            dependencies,
376                            range_dependencies,
377                            created_placeholders,
378                            named_dependencies,
379                            unresolved_names,
380                            local_scopes,
381                            unresolved_name_policy,
382                        )?;
383
384                        local_scopes.pop();
385                    } else {
386                        for arg in args {
387                            self.extract_dependencies_recursive_arena(
388                                arg,
389                                current_sheet_id,
390                                dependencies,
391                                range_dependencies,
392                                created_placeholders,
393                                named_dependencies,
394                                unresolved_names,
395                                local_scopes,
396                                unresolved_name_policy,
397                            )?;
398                        }
399                    }
400                } else if name.eq_ignore_ascii_case("LAMBDA") {
401                    if let Some((&body, params)) = args.split_last() {
402                        let mut lambda_scope = FxHashSet::default();
403                        for param in params {
404                            if let Some(param_name) = self.arena_named_range_name(*param) {
405                                lambda_scope.insert(param_name.to_ascii_uppercase());
406                            }
407                        }
408                        local_scopes.push(lambda_scope);
409                        self.extract_dependencies_recursive_arena(
410                            body,
411                            current_sheet_id,
412                            dependencies,
413                            range_dependencies,
414                            created_placeholders,
415                            named_dependencies,
416                            unresolved_names,
417                            local_scopes,
418                            unresolved_name_policy,
419                        )?;
420                        local_scopes.pop();
421                    }
422                } else {
423                    for arg in args {
424                        self.extract_dependencies_recursive_arena(
425                            arg,
426                            current_sheet_id,
427                            dependencies,
428                            range_dependencies,
429                            created_placeholders,
430                            named_dependencies,
431                            unresolved_names,
432                            local_scopes,
433                            unresolved_name_policy,
434                        )?;
435                    }
436                }
437            }
438            super::super::arena::ast::AstNodeData::Array { .. } => {
439                let elements: Vec<AstNodeId> = self
440                    .data_store
441                    .get_array_elems(ast_id)
442                    .map_or_else(Vec::new, |(_, _, elems)| elems.to_vec());
443                for cell in elements {
444                    self.extract_dependencies_recursive_arena(
445                        cell,
446                        current_sheet_id,
447                        dependencies,
448                        range_dependencies,
449                        created_placeholders,
450                        named_dependencies,
451                        unresolved_names,
452                        local_scopes,
453                        unresolved_name_policy,
454                    )?;
455                }
456            }
457            super::super::arena::ast::AstNodeData::Literal(_) => {}
458        }
459        Ok(())
460    }
461
462    fn arena_named_range_name(&self, ast_id: AstNodeId) -> Option<String> {
463        match self.data_store.get_node(ast_id)? {
464            super::super::arena::ast::AstNodeData::Reference {
465                ref_type: super::super::arena::ast::CompactRefType::NamedRange(name_id),
466                ..
467            } => Some(self.data_store.resolve_ast_string(*name_id).to_string()),
468            _ => None,
469        }
470    }
471
472    fn extract_dependencies_inner(
473        &mut self,
474        ast: &ASTNode,
475        current_sheet_id: SheetId,
476        unresolved_name_policy: UnresolvedNamePolicy,
477    ) -> ExtractDependenciesWithPendingNamesResult {
478        let mut dependencies = FxHashSet::default();
479        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
480        let mut created_placeholders = Vec::new();
481        let mut named_dependencies = Vec::new();
482        let mut unresolved_names = FxHashSet::default();
483        let mut local_scopes: Vec<FxHashSet<String>> = Vec::new();
484        self.extract_dependencies_recursive(
485            ast,
486            current_sheet_id,
487            &mut dependencies,
488            &mut range_dependencies,
489            &mut created_placeholders,
490            &mut named_dependencies,
491            &mut unresolved_names,
492            &mut local_scopes,
493            unresolved_name_policy,
494        )?;
495
496        // Deduplicate range references.
497        let mut deduped_ranges = Vec::new();
498        for range_ref in range_dependencies {
499            if !deduped_ranges.contains(&range_ref) {
500                deduped_ranges.push(range_ref);
501            }
502        }
503
504        named_dependencies.sort_unstable_by_key(|v| v.0);
505        named_dependencies.dedup_by_key(|v| v.0);
506
507        let mut unresolved_names: Vec<String> = unresolved_names.into_iter().collect();
508        unresolved_names.sort();
509
510        Ok((
511            dependencies.into_iter().collect(),
512            deduped_ranges,
513            created_placeholders,
514            named_dependencies,
515            unresolved_names,
516        ))
517    }
518
519    fn extract_dependencies_recursive(
520        &mut self,
521        ast: &ASTNode,
522        current_sheet_id: SheetId,
523        dependencies: &mut FxHashSet<VertexId>,
524        range_dependencies: &mut Vec<SharedRangeRef<'static>>,
525        created_placeholders: &mut Vec<CellRef>,
526        named_dependencies: &mut Vec<VertexId>,
527        unresolved_names: &mut FxHashSet<String>,
528        local_scopes: &mut Vec<FxHashSet<String>>,
529        unresolved_name_policy: UnresolvedNamePolicy,
530    ) -> Result<(), ExcelError> {
531        match &ast.node_type {
532            ASTNodeType::Reference { reference, .. } => match reference {
533                ReferenceType::External(ext) => match ext.kind {
534                    formualizer_parse::parser::ExternalRefKind::Cell { .. } => {
535                        let name = ext.raw.as_str();
536                        if let Some(source) = self.resolve_source_scalar_entry(name) {
537                            dependencies.insert(source.vertex);
538                        } else {
539                            return Err(ExcelError::new(ExcelErrorKind::Name)
540                                .with_message(format!("Undefined name: {name}")));
541                        }
542                    }
543                    formualizer_parse::parser::ExternalRefKind::Range { .. } => {
544                        let name = ext.raw.as_str();
545                        if let Some(source) = self.resolve_source_table_entry(name) {
546                            dependencies.insert(source.vertex);
547                        } else {
548                            return Err(ExcelError::new(ExcelErrorKind::Name)
549                                .with_message(format!("Undefined table: {name}")));
550                        }
551                    }
552                },
553                ReferenceType::Cell { .. } => {
554                    let vertex_id = self.get_or_create_vertex_for_reference(
555                        reference,
556                        current_sheet_id,
557                        created_placeholders,
558                    )?;
559                    dependencies.insert(vertex_id);
560                }
561                ReferenceType::Range {
562                    sheet,
563                    start_row,
564                    start_col,
565                    end_row,
566                    end_col,
567                    ..
568                } => {
569                    // If any bound is missing (infinite/partial range), always keep compressed.
570                    let has_unbounded = start_row.is_none()
571                        || end_row.is_none()
572                        || start_col.is_none()
573                        || end_col.is_none();
574                    if has_unbounded {
575                        if let Some(SharedRef::Range(range)) = reference.to_sheet_ref_lossy() {
576                            let owned = range.into_owned();
577                            let sheet_id = match owned.sheet {
578                                SharedSheetLocator::Id(id) => id,
579                                SharedSheetLocator::Current => current_sheet_id,
580                                SharedSheetLocator::Name(name) => {
581                                    self.resolve_existing_sheet_id(name.as_ref())?
582                                }
583                            };
584                            range_dependencies.push(SharedRangeRef {
585                                sheet: SharedSheetLocator::Id(sheet_id),
586                                start_row: owned.start_row,
587                                start_col: owned.start_col,
588                                end_row: owned.end_row,
589                                end_col: owned.end_col,
590                            });
591                        }
592                    } else {
593                        let (Some(sr), Some(sc), Some(er), Some(ec)) =
594                            (*start_row, *start_col, *end_row, *end_col)
595                        else {
596                            return Err(ExcelError::new(ExcelErrorKind::Ref));
597                        };
598
599                        if sr > er || sc > ec {
600                            return Err(ExcelError::new(ExcelErrorKind::Ref));
601                        }
602
603                        let height = er.saturating_sub(sr) + 1;
604                        let width = ec.saturating_sub(sc) + 1;
605                        let size = (width * height) as usize;
606
607                        if size <= self.config.range_expansion_limit {
608                            // Expand to individual cells.
609                            let sheet_id = match sheet {
610                                Some(name) => self.resolve_existing_sheet_id(name)?,
611                                None => current_sheet_id,
612                            };
613                            for row in sr..=er {
614                                for col in sc..=ec {
615                                    let coord = Coord::from_excel(row, col, true, true);
616                                    let addr = CellRef::new(sheet_id, coord);
617                                    let vertex_id =
618                                        self.get_or_create_vertex(&addr, created_placeholders);
619                                    dependencies.insert(vertex_id);
620                                }
621                            }
622                        } else {
623                            // Keep as a compressed range dependency.
624                            if let Some(SharedRef::Range(range)) = reference.to_sheet_ref_lossy() {
625                                let owned = range.into_owned();
626                                let sheet_id = match owned.sheet {
627                                    SharedSheetLocator::Id(id) => id,
628                                    SharedSheetLocator::Current => current_sheet_id,
629                                    SharedSheetLocator::Name(name) => {
630                                        self.resolve_existing_sheet_id(name.as_ref())?
631                                    }
632                                };
633                                range_dependencies.push(SharedRangeRef {
634                                    sheet: SharedSheetLocator::Id(sheet_id),
635                                    start_row: owned.start_row,
636                                    start_col: owned.start_col,
637                                    end_row: owned.end_row,
638                                    end_col: owned.end_col,
639                                });
640                            }
641                        }
642                    }
643                }
644                ReferenceType::NamedRange(name) => {
645                    let key = name.to_ascii_uppercase();
646                    if local_scopes.iter().rev().any(|scope| scope.contains(&key)) {
647                        return Ok(());
648                    }
649
650                    if let Some(named_range) = self.resolve_name_entry(name, current_sheet_id) {
651                        dependencies.insert(named_range.vertex);
652                        named_dependencies.push(named_range.vertex);
653                    } else if let Some(source) = self.resolve_source_scalar_entry(name) {
654                        dependencies.insert(source.vertex);
655                    } else {
656                        match unresolved_name_policy {
657                            UnresolvedNamePolicy::Error => {
658                                return Err(ExcelError::new(ExcelErrorKind::Name)
659                                    .with_message(format!("Undefined name: {name}")));
660                            }
661                            UnresolvedNamePolicy::Collect => {
662                                unresolved_names.insert(name.to_string());
663                            }
664                        }
665                    }
666                }
667                ReferenceType::Table(tref) => {
668                    if let Some(table) = self.resolve_table_entry(&tref.name) {
669                        dependencies.insert(table.vertex);
670                    } else if let Some(source) = self.resolve_source_table_entry(&tref.name) {
671                        dependencies.insert(source.vertex);
672                    } else {
673                        return Err(ExcelError::new(ExcelErrorKind::Name)
674                            .with_message(format!("Undefined table: {}", tref.name)));
675                    }
676                }
677                // 3D references parse correctly but aren't yet wired through
678                // the dependency graph; treat them as no-op dependencies for
679                // now so formulas containing them still load. Evaluation will
680                // surface #N/IMPL! via the Resolver path.
681                ReferenceType::Cell3D { .. } | ReferenceType::Range3D { .. } => {}
682            },
683            ASTNodeType::BinaryOp { left, right, .. } => {
684                self.extract_dependencies_recursive(
685                    left,
686                    current_sheet_id,
687                    dependencies,
688                    range_dependencies,
689                    created_placeholders,
690                    named_dependencies,
691                    unresolved_names,
692                    local_scopes,
693                    unresolved_name_policy,
694                )?;
695                self.extract_dependencies_recursive(
696                    right,
697                    current_sheet_id,
698                    dependencies,
699                    range_dependencies,
700                    created_placeholders,
701                    named_dependencies,
702                    unresolved_names,
703                    local_scopes,
704                    unresolved_name_policy,
705                )?;
706            }
707            ASTNodeType::UnaryOp { expr, .. } => {
708                self.extract_dependencies_recursive(
709                    expr,
710                    current_sheet_id,
711                    dependencies,
712                    range_dependencies,
713                    created_placeholders,
714                    named_dependencies,
715                    unresolved_names,
716                    local_scopes,
717                    unresolved_name_policy,
718                )?;
719            }
720            ASTNodeType::Function { name, args } => {
721                if name.eq_ignore_ascii_case("LET") {
722                    if args.len() >= 3 && args.len() % 2 == 1 {
723                        local_scopes.push(FxHashSet::default());
724
725                        for pair_idx in (0..args.len() - 1).step_by(2) {
726                            self.extract_dependencies_recursive(
727                                &args[pair_idx + 1],
728                                current_sheet_id,
729                                dependencies,
730                                range_dependencies,
731                                created_placeholders,
732                                named_dependencies,
733                                unresolved_names,
734                                local_scopes,
735                                unresolved_name_policy,
736                            )?;
737
738                            if let ASTNodeType::Reference {
739                                reference: ReferenceType::NamedRange(local_name),
740                                ..
741                            } = &args[pair_idx].node_type
742                                && let Some(scope) = local_scopes.last_mut()
743                            {
744                                scope.insert(local_name.to_ascii_uppercase());
745                            }
746                        }
747
748                        self.extract_dependencies_recursive(
749                            &args[args.len() - 1],
750                            current_sheet_id,
751                            dependencies,
752                            range_dependencies,
753                            created_placeholders,
754                            named_dependencies,
755                            unresolved_names,
756                            local_scopes,
757                            unresolved_name_policy,
758                        )?;
759
760                        local_scopes.pop();
761                    } else {
762                        for arg in args {
763                            self.extract_dependencies_recursive(
764                                arg,
765                                current_sheet_id,
766                                dependencies,
767                                range_dependencies,
768                                created_placeholders,
769                                named_dependencies,
770                                unresolved_names,
771                                local_scopes,
772                                unresolved_name_policy,
773                            )?;
774                        }
775                    }
776                } else if name.eq_ignore_ascii_case("LAMBDA") {
777                    if let Some(body) = args.last() {
778                        let mut lambda_scope = FxHashSet::default();
779                        for param in &args[..args.len().saturating_sub(1)] {
780                            if let ASTNodeType::Reference {
781                                reference: ReferenceType::NamedRange(param_name),
782                                ..
783                            } = &param.node_type
784                            {
785                                lambda_scope.insert(param_name.to_ascii_uppercase());
786                            }
787                        }
788                        local_scopes.push(lambda_scope);
789                        self.extract_dependencies_recursive(
790                            body,
791                            current_sheet_id,
792                            dependencies,
793                            range_dependencies,
794                            created_placeholders,
795                            named_dependencies,
796                            unresolved_names,
797                            local_scopes,
798                            unresolved_name_policy,
799                        )?;
800                        local_scopes.pop();
801                    }
802                } else {
803                    for arg in args {
804                        self.extract_dependencies_recursive(
805                            arg,
806                            current_sheet_id,
807                            dependencies,
808                            range_dependencies,
809                            created_placeholders,
810                            named_dependencies,
811                            unresolved_names,
812                            local_scopes,
813                            unresolved_name_policy,
814                        )?;
815                    }
816                }
817            }
818            ASTNodeType::Array(rows) => {
819                for row in rows {
820                    for cell in row {
821                        self.extract_dependencies_recursive(
822                            cell,
823                            current_sheet_id,
824                            dependencies,
825                            range_dependencies,
826                            created_placeholders,
827                            named_dependencies,
828                            unresolved_names,
829                            local_scopes,
830                            unresolved_name_policy,
831                        )?;
832                    }
833                }
834            }
835            ASTNodeType::Call { callee, args } => {
836                // Walk both the callee and the call arguments so any references
837                // they contain are tracked. Full evaluator semantics for
838                // immediate-invocation calls are not yet implemented, but
839                // dependency collection must still cover them.
840                self.extract_dependencies_recursive(
841                    callee,
842                    current_sheet_id,
843                    dependencies,
844                    range_dependencies,
845                    created_placeholders,
846                    named_dependencies,
847                    unresolved_names,
848                    local_scopes,
849                    unresolved_name_policy,
850                )?;
851                for arg in args {
852                    self.extract_dependencies_recursive(
853                        arg,
854                        current_sheet_id,
855                        dependencies,
856                        range_dependencies,
857                        created_placeholders,
858                        named_dependencies,
859                        unresolved_names,
860                        local_scopes,
861                        unresolved_name_policy,
862                    )?;
863                }
864            }
865            ASTNodeType::Literal(_) => {}
866        }
867        Ok(())
868    }
869
870    /// Gets the VertexId for a reference, creating a placeholder vertex if it doesn't exist.
871    fn get_or_create_vertex_for_reference(
872        &mut self,
873        reference: &ReferenceType,
874        current_sheet_id: SheetId,
875        created_placeholders: &mut Vec<CellRef>,
876    ) -> Result<VertexId, ExcelError> {
877        match reference {
878            ReferenceType::Cell {
879                sheet, row, col, ..
880            } => {
881                let sheet_id = match sheet {
882                    Some(name) => self.resolve_existing_sheet_id(name)?,
883                    None => current_sheet_id,
884                };
885                let coord = Coord::from_excel(*row, *col, true, true);
886                let addr = CellRef::new(sheet_id, coord);
887                Ok(self.get_or_create_vertex(&addr, created_placeholders))
888            }
889            _ => Err(ExcelError::new(ExcelErrorKind::Value)
890                .with_message("Expected a cell reference, but got a range or other type.")),
891        }
892    }
893
894    #[inline]
895    pub(super) fn is_ast_volatile(&self, ast: &ASTNode) -> bool {
896        if ast.contains_volatile() {
897            return true;
898        }
899
900        use formualizer_parse::parser::ASTNodeType;
901
902        match &ast.node_type {
903            ASTNodeType::Function { name, args } => {
904                if let Some(func) = crate::function_registry::get("", name)
905                    && func.caps().contains(crate::function::FnCaps::VOLATILE)
906                {
907                    return true;
908                }
909                args.iter().any(|arg| self.is_ast_volatile(arg))
910            }
911            ASTNodeType::BinaryOp { left, right, .. } => {
912                self.is_ast_volatile(left) || self.is_ast_volatile(right)
913            }
914            ASTNodeType::UnaryOp { expr, .. } => self.is_ast_volatile(expr),
915            ASTNodeType::Array(rows) => rows
916                .iter()
917                .any(|row| row.iter().any(|cell| self.is_ast_volatile(cell))),
918            ASTNodeType::Call { callee, args } => {
919                self.is_ast_volatile(callee) || args.iter().any(|a| self.is_ast_volatile(a))
920            }
921            _ => false,
922        }
923    }
924
925    pub fn is_ast_dynamic(&self, ast: &ASTNode) -> bool {
926        use formualizer_parse::parser::ASTNodeType;
927
928        match &ast.node_type {
929            ASTNodeType::Function { name, args } => {
930                if let Some(func) = crate::function_registry::get("", name)
931                    && func
932                        .caps()
933                        .contains(crate::function::FnCaps::DYNAMIC_DEPENDENCY)
934                {
935                    return true;
936                }
937                args.iter().any(|arg| self.is_ast_dynamic(arg))
938            }
939            ASTNodeType::BinaryOp { left, right, .. } => {
940                self.is_ast_dynamic(left) || self.is_ast_dynamic(right)
941            }
942            ASTNodeType::UnaryOp { expr, .. } => self.is_ast_dynamic(expr),
943            ASTNodeType::Array(rows) => rows
944                .iter()
945                .any(|row| row.iter().any(|cell| self.is_ast_dynamic(cell))),
946            ASTNodeType::Call { callee, args } => {
947                self.is_ast_dynamic(callee) || args.iter().any(|a| self.is_ast_dynamic(a))
948            }
949            _ => false,
950        }
951    }
952}
formualizer_eval/engine/graph/formula_analysis.rs

formualizer_eval/engine/graph/
formula_analysis.rs
