formualizer_eval/engine/graph/
formula_analysis.rs

1use super::*;
2use formualizer_parse::parser::ASTNode;
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
32struct GraphReferenceContext<'a> {
33    graph: &'a mut DependencyGraph,
34    current_sheet_id: SheetId,
35    dependencies: &'a mut FxHashSet<VertexId>,
36    range_dependencies: &'a mut Vec<SharedRangeRef<'static>>,
37    created_placeholders: &'a mut Vec<CellRef>,
38    named_dependencies: &'a mut Vec<VertexId>,
39    unresolved_names: &'a mut FxHashSet<String>,
40    unresolved_name_policy: UnresolvedNamePolicy,
41}
42
43fn graph_no_local_bindings(
44    _: &GraphReferenceContext<'_>,
45    _: &str,
46    _: usize,
47) -> crate::engine::refs::LocalBindingStyle {
48    crate::engine::refs::LocalBindingStyle::None
49}
50
51fn graph_data_store<'context>(
52    context: &'context GraphReferenceContext<'_>,
53) -> &'context super::super::arena::DataStore {
54    &context.graph.data_store
55}
56
57fn graph_sheet_registry<'context>(
58    context: &'context GraphReferenceContext<'_>,
59) -> &'context super::super::sheet_registry::SheetRegistry {
60    &context.graph.sheet_reg
61}
62
63fn collect_graph_reference(
64    context: &mut GraphReferenceContext<'_>,
65    reference: crate::engine::refs::SemanticReference<'_>,
66) -> Result<(), ExcelError> {
67    use crate::engine::refs::SemanticReference;
68
69    match reference {
70        SemanticReference::ExternalSource(external) => match external.kind {
71            formualizer_parse::parser::ExternalRefKind::Cell { .. } => {
72                let name = external.raw.as_str();
73                if let Some(source) = context.graph.resolve_source_scalar_entry(name) {
74                    context.dependencies.insert(source.vertex);
75                    Ok(())
76                } else {
77                    Err(ExcelError::new(ExcelErrorKind::Name)
78                        .with_message(format!("Undefined name: {name}")))
79                }
80            }
81            formualizer_parse::parser::ExternalRefKind::Range { .. } => {
82                let name = external.raw.as_str();
83                if let Some(source) = context.graph.resolve_source_table_entry(name) {
84                    context.dependencies.insert(source.vertex);
85                    Ok(())
86                } else {
87                    Err(ExcelError::new(ExcelErrorKind::Name)
88                        .with_message(format!("Undefined table: {name}")))
89                }
90            }
91        },
92        SemanticReference::Cell(cell) => {
93            let sheet_id = match cell.sheet.name() {
94                Some(name) => context.graph.resolve_existing_sheet_id(name)?,
95                None => context.current_sheet_id,
96            };
97            let address = CellRef::new(sheet_id, Coord::from_excel(cell.row, cell.col, true, true));
98            let vertex = context
99                .graph
100                .get_or_create_vertex(&address, context.created_placeholders);
101            context.dependencies.insert(vertex);
102            Ok(())
103        }
104        SemanticReference::OpenRange(range) => {
105            if let Some(SharedRef::Range(range)) = range.original.to_sheet_ref_lossy() {
106                let owned = range.into_owned();
107                let sheet_id = match owned.sheet {
108                    SharedSheetLocator::Id(id) => id,
109                    SharedSheetLocator::Current => context.current_sheet_id,
110                    SharedSheetLocator::Name(name) => {
111                        context.graph.resolve_existing_sheet_id(name.as_ref())?
112                    }
113                };
114                context.range_dependencies.push(SharedRangeRef {
115                    sheet: SharedSheetLocator::Id(sheet_id),
116                    start_row: owned.start_row,
117                    start_col: owned.start_col,
118                    end_row: owned.end_row,
119                    end_col: owned.end_col,
120                });
121            }
122            Ok(())
123        }
124        SemanticReference::FiniteRange(range) => {
125            let (sr, sc, er, ec) = range
126                .finite_bounds()
127                .expect("finite reference must have all bounds");
128            if range.is_reversed() {
129                return Err(ExcelError::new(ExcelErrorKind::Ref));
130            }
131            let area = range.saturating_area().expect("finite area");
132
133            // Graph ingest's configured default is 64. This policy intentionally
134            // remains independent from dependency planning's historical 16.
135            if area <= context.graph.config.range_expansion_limit as u64 {
136                let sheet_id = match range.sheet.name() {
137                    Some(name) => context.graph.resolve_existing_sheet_id(name)?,
138                    None => context.current_sheet_id,
139                };
140                for row in sr..=er {
141                    for col in sc..=ec {
142                        let address =
143                            CellRef::new(sheet_id, Coord::from_excel(row, col, true, true));
144                        let vertex = context
145                            .graph
146                            .get_or_create_vertex(&address, context.created_placeholders);
147                        context.dependencies.insert(vertex);
148                    }
149                }
150            } else if let Some(SharedRef::Range(range)) = range.original.to_sheet_ref_lossy() {
151                let owned = range.into_owned();
152                let sheet_id = match owned.sheet {
153                    SharedSheetLocator::Id(id) => id,
154                    SharedSheetLocator::Current => context.current_sheet_id,
155                    SharedSheetLocator::Name(name) => {
156                        context.graph.resolve_existing_sheet_id(name.as_ref())?
157                    }
158                };
159                context.range_dependencies.push(SharedRangeRef {
160                    sheet: SharedSheetLocator::Id(sheet_id),
161                    start_row: owned.start_row,
162                    start_col: owned.start_col,
163                    end_row: owned.end_row,
164                    end_col: owned.end_col,
165                });
166            }
167            Ok(())
168        }
169        SemanticReference::Name(name) => {
170            if let Some(named_range) = context
171                .graph
172                .resolve_name_entry(name, context.current_sheet_id)
173            {
174                context.dependencies.insert(named_range.vertex);
175                context.named_dependencies.push(named_range.vertex);
176            } else if let Some(source) = context.graph.resolve_source_scalar_entry(name) {
177                context.dependencies.insert(source.vertex);
178            } else {
179                match context.unresolved_name_policy {
180                    UnresolvedNamePolicy::Error => {
181                        return Err(ExcelError::new(ExcelErrorKind::Name)
182                            .with_message(format!("Undefined name: {name}")));
183                    }
184                    UnresolvedNamePolicy::Collect => {
185                        context.unresolved_names.insert(name.to_string());
186                    }
187                }
188            }
189            Ok(())
190        }
191        SemanticReference::Table(table_reference) => {
192            if let Some(table) = context.graph.resolve_table_entry(&table_reference.name) {
193                context.dependencies.insert(table.vertex);
194            } else if let Some(source) = context
195                .graph
196                .resolve_source_table_entry(&table_reference.name)
197            {
198                context.dependencies.insert(source.vertex);
199            } else {
200                return Err(ExcelError::new(ExcelErrorKind::Name)
201                    .with_message(format!("Undefined table: {}", table_reference.name)));
202            }
203            Ok(())
204        }
205        SemanticReference::ThreeDimensional(_) | SemanticReference::Unsupported(_) => Ok(()),
206    }
207}
208impl DependencyGraph {
209    // Helper methods for formula analysis / dependency extraction.
210
211    pub(super) fn extract_dependencies(
212        &mut self,
213        ast: &ASTNode,
214        current_sheet_id: SheetId,
215    ) -> ExtractDependenciesResult {
216        let (dependencies, ranges, placeholders, named_dependencies, _pending_names) =
217            self.extract_dependencies_inner(ast, current_sheet_id, UnresolvedNamePolicy::Error)?;
218        Ok((dependencies, ranges, placeholders, named_dependencies))
219    }
220
221    pub(super) fn extract_dependencies_with_pending_names(
222        &mut self,
223        ast: &ASTNode,
224        current_sheet_id: SheetId,
225    ) -> ExtractDependenciesWithPendingNamesResult {
226        self.extract_dependencies_inner(ast, current_sheet_id, UnresolvedNamePolicy::Collect)
227    }
228
229    pub(super) fn extract_dependencies_arena(
230        &mut self,
231        ast_id: AstNodeId,
232        current_sheet_id: SheetId,
233    ) -> ExtractDependenciesResult {
234        let (dependencies, ranges, placeholders, named_dependencies, _pending_names) = self
235            .extract_dependencies_inner_arena(
236                ast_id,
237                current_sheet_id,
238                UnresolvedNamePolicy::Error,
239            )?;
240        Ok((dependencies, ranges, placeholders, named_dependencies))
241    }
242
243    pub(super) fn extract_dependencies_with_pending_names_arena(
244        &mut self,
245        ast_id: AstNodeId,
246        current_sheet_id: SheetId,
247    ) -> ExtractDependenciesWithPendingNamesResult {
248        self.extract_dependencies_inner_arena(
249            ast_id,
250            current_sheet_id,
251            UnresolvedNamePolicy::Collect,
252        )
253    }
254
255    fn extract_dependencies_inner_arena(
256        &mut self,
257        ast_id: AstNodeId,
258        current_sheet_id: SheetId,
259        unresolved_name_policy: UnresolvedNamePolicy,
260    ) -> ExtractDependenciesWithPendingNamesResult {
261        let mut dependencies = FxHashSet::default();
262        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
263        let mut created_placeholders = Vec::new();
264        let mut named_dependencies = Vec::new();
265        let mut unresolved_names = FxHashSet::default();
266        let mut context = GraphReferenceContext {
267            graph: self,
268            current_sheet_id,
269            dependencies: &mut dependencies,
270            range_dependencies: &mut range_dependencies,
271            created_placeholders: &mut created_placeholders,
272            named_dependencies: &mut named_dependencies,
273            unresolved_names: &mut unresolved_names,
274            unresolved_name_policy,
275        };
276        crate::engine::refs::visit_arena_references(
277            ast_id,
278            &mut context,
279            graph_data_store,
280            graph_sheet_registry,
281            collect_graph_reference,
282        )?;
283
284        // Deduplicate range references.
285        let mut deduped_ranges = Vec::new();
286        for range_ref in range_dependencies {
287            if !deduped_ranges.contains(&range_ref) {
288                deduped_ranges.push(range_ref);
289            }
290        }
291
292        named_dependencies.sort_unstable_by_key(|v| v.0);
293        named_dependencies.dedup_by_key(|v| v.0);
294
295        let mut unresolved_names: Vec<String> = unresolved_names.into_iter().collect();
296        unresolved_names.sort();
297
298        Ok((
299            dependencies.into_iter().collect(),
300            deduped_ranges,
301            created_placeholders,
302            named_dependencies,
303            unresolved_names,
304        ))
305    }
306
307    fn extract_dependencies_inner(
308        &mut self,
309        ast: &ASTNode,
310        current_sheet_id: SheetId,
311        unresolved_name_policy: UnresolvedNamePolicy,
312    ) -> ExtractDependenciesWithPendingNamesResult {
313        let mut dependencies = FxHashSet::default();
314        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
315        let mut created_placeholders = Vec::new();
316        let mut named_dependencies = Vec::new();
317        let mut unresolved_names = FxHashSet::default();
318        let mut context = GraphReferenceContext {
319            graph: self,
320            current_sheet_id,
321            dependencies: &mut dependencies,
322            range_dependencies: &mut range_dependencies,
323            created_placeholders: &mut created_placeholders,
324            named_dependencies: &mut named_dependencies,
325            unresolved_names: &mut unresolved_names,
326            unresolved_name_policy,
327        };
328        crate::engine::refs::visit_tree_references(
329            ast,
330            &mut context,
331            graph_no_local_bindings,
332            collect_graph_reference,
333        )?;
334
335        // Deduplicate range references.
336        let mut deduped_ranges = Vec::new();
337        for range_ref in range_dependencies {
338            if !deduped_ranges.contains(&range_ref) {
339                deduped_ranges.push(range_ref);
340            }
341        }
342
343        named_dependencies.sort_unstable_by_key(|v| v.0);
344        named_dependencies.dedup_by_key(|v| v.0);
345
346        let mut unresolved_names: Vec<String> = unresolved_names.into_iter().collect();
347        unresolved_names.sort();
348
349        Ok((
350            dependencies.into_iter().collect(),
351            deduped_ranges,
352            created_placeholders,
353            named_dependencies,
354            unresolved_names,
355        ))
356    }
357
358    pub(super) fn is_ast_volatile(&self, ast: &ASTNode) -> bool {
359        if ast.contains_volatile() {
360            return true;
361        }
362
363        use formualizer_parse::parser::ASTNodeType;
364
365        match &ast.node_type {
366            ASTNodeType::Function { name, args } => {
367                if let Some(func) = crate::function_registry::get("", name)
368                    && func.caps().contains(crate::function::FnCaps::VOLATILE)
369                {
370                    return true;
371                }
372                args.iter().any(|arg| self.is_ast_volatile(arg))
373            }
374            ASTNodeType::BinaryOp { left, right, .. } => {
375                self.is_ast_volatile(left) || self.is_ast_volatile(right)
376            }
377            ASTNodeType::UnaryOp { expr, .. } => self.is_ast_volatile(expr),
378            ASTNodeType::Array(rows) => rows
379                .iter()
380                .any(|row| row.iter().any(|cell| self.is_ast_volatile(cell))),
381            ASTNodeType::Call { callee, args } => {
382                self.is_ast_volatile(callee) || args.iter().any(|a| self.is_ast_volatile(a))
383            }
384            _ => false,
385        }
386    }
387
388    pub fn is_ast_dynamic(&self, ast: &ASTNode) -> bool {
389        use formualizer_parse::parser::ASTNodeType;
390
391        match &ast.node_type {
392            ASTNodeType::Function { name, args } => {
393                if let Some(func) = crate::function_registry::get("", name)
394                    && func
395                        .caps()
396                        .contains(crate::function::FnCaps::DYNAMIC_DEPENDENCY)
397                {
398                    return true;
399                }
400                args.iter().any(|arg| self.is_ast_dynamic(arg))
401            }
402            ASTNodeType::BinaryOp { left, right, .. } => {
403                self.is_ast_dynamic(left) || self.is_ast_dynamic(right)
404            }
405            ASTNodeType::UnaryOp { expr, .. } => self.is_ast_dynamic(expr),
406            ASTNodeType::Array(rows) => rows
407                .iter()
408                .any(|row| row.iter().any(|cell| self.is_ast_dynamic(cell))),
409            ASTNodeType::Call { callee, args } => {
410                self.is_ast_dynamic(callee) || args.iter().any(|a| self.is_ast_dynamic(a))
411            }
412            _ => false,
413        }
414    }
415}
formualizer_eval/engine/graph/formula_analysis.rs

formualizer_eval/engine/graph/
formula_analysis.rs
