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
63/// `PreparationPolicy::BestEffort` on a collecting extraction: a missing
64/// sheet or table becomes a pending symbol link (re-bound when it is added)
65/// instead of a preparation error.
66fn defer_unbound(
67    context: &mut GraphReferenceContext<'_>,
68    kind: &str,
69    name: &str,
70    error: ExcelError,
71) -> Result<(), ExcelError> {
72    let tombstone = kind == "sheet" && DependencyGraph::is_tombstone_sheet(name);
73    if !name.is_empty()
74        && !tombstone
75        && context.unresolved_name_policy == UnresolvedNamePolicy::Collect
76        && context.graph.config.preparation_policy == crate::engine::PreparationPolicy::BestEffort
77    {
78        context
79            .unresolved_names
80            .insert(DependencyGraph::unbound_symbol_key(kind, name));
81        Ok(())
82    } else {
83        Err(error)
84    }
85}
86
87/// A direct cell dependency: its vertex when it has one, else the cell
88/// (`created_placeholders` now lists the cells without a vertex; a
89/// reference no longer creates one, decision 27).
90fn push_cell_dependency(context: &mut GraphReferenceContext<'_>, address: CellRef) {
91    match context.graph.dep_vertex(&address) {
92        Some(vertex) => {
93            context.dependencies.insert(vertex);
94        }
95        None => {
96            if !context
97                .created_placeholders
98                .iter()
99                .any(|c| super::same_cell(c, &address))
100            {
101                context.created_placeholders.push(address);
102            }
103        }
104    }
105}
106
107fn collect_graph_reference(
108    context: &mut GraphReferenceContext<'_>,
109    reference: crate::engine::refs::SemanticReference<'_>,
110) -> Result<(), ExcelError> {
111    use crate::engine::refs::SemanticReference;
112
113    match reference {
114        SemanticReference::ExternalSource(external) => match external.kind {
115            formualizer_parse::parser::ExternalRefKind::Cell { .. } => {
116                let name = external.raw.as_str();
117                if let Some(source) = context.graph.resolve_source_scalar_entry(name) {
118                    context.dependencies.insert(source.vertex);
119                    Ok(())
120                } else {
121                    Err(ExcelError::new(ExcelErrorKind::Name)
122                        .with_message(format!("Undefined name: {name}")))
123                }
124            }
125            formualizer_parse::parser::ExternalRefKind::Range { .. } => {
126                let name = external.raw.as_str();
127                if let Some(source) = context.graph.resolve_source_table_entry(name) {
128                    context.dependencies.insert(source.vertex);
129                    Ok(())
130                } else if crate::engine::refs::unbound_external_range_defers(&external.kind)
131                    && context.unresolved_name_policy == UnresolvedNamePolicy::Collect
132                {
133                    context.unresolved_names.insert(name.to_string());
134                    Ok(())
135                } else {
136                    Err(ExcelError::new(ExcelErrorKind::Name)
137                        .with_message(format!("Undefined table: {name}")))
138                }
139            }
140        },
141        SemanticReference::Cell(cell) => {
142            let sheet_id = match cell.sheet.name() {
143                Some(name) => match context.graph.resolve_existing_sheet_id(name) {
144                    Ok(id) => id,
145                    Err(e) => return defer_unbound(context, "sheet", name, e),
146                },
147                None => context.current_sheet_id,
148            };
149            let address = CellRef::new(sheet_id, Coord::from_excel(cell.row, cell.col, true, true));
150            push_cell_dependency(context, address);
151            Ok(())
152        }
153        SemanticReference::OpenRange(range) => {
154            let sheet_name = range.sheet.name();
155            if let Some(SharedRef::Range(range)) = range.original.to_sheet_ref_lossy() {
156                let owned = range.into_owned();
157                // `Current` is the sheet the formula lives on.
158                let sheet_id = match context
159                    .graph
160                    .sheet_reg()
161                    .resolve_locator(&owned.sheet, context.current_sheet_id)
162                {
163                    Ok(id) => id,
164                    Err(e) => return defer_unbound(context, "sheet", sheet_name.unwrap_or(""), e),
165                };
166                context.range_dependencies.push(SharedRangeRef {
167                    sheet: SharedSheetLocator::Id(sheet_id),
168                    start_row: owned.start_row,
169                    start_col: owned.start_col,
170                    end_row: owned.end_row,
171                    end_col: owned.end_col,
172                });
173            }
174            Ok(())
175        }
176        SemanticReference::FiniteRange(range) => {
177            let (sr, sc, er, ec) = range
178                .finite_bounds()
179                .expect("finite reference must have all bounds");
180            if range.is_reversed() {
181                return Err(ExcelError::new(ExcelErrorKind::Ref));
182            }
183            let area = range.saturating_area().expect("finite area");
184
185            // Graph ingest's configured default is 64. This policy intentionally
186            // remains independent from dependency planning's historical 16.
187            if area <= context.graph.config.range_expansion_limit as u64 {
188                let sheet_id = match range.sheet.name() {
189                    Some(name) => match context.graph.resolve_existing_sheet_id(name) {
190                        Ok(id) => id,
191                        Err(e) => return defer_unbound(context, "sheet", name, e),
192                    },
193                    None => context.current_sheet_id,
194                };
195                for row in sr..=er {
196                    for col in sc..=ec {
197                        let address =
198                            CellRef::new(sheet_id, Coord::from_excel(row, col, true, true));
199                        push_cell_dependency(context, address);
200                    }
201                }
202            } else if let Some(SharedRef::Range(shared)) = range.original.to_sheet_ref_lossy() {
203                let owned = shared.into_owned();
204                // `Current` is the sheet the formula lives on.
205                let sheet_id = match context
206                    .graph
207                    .sheet_reg()
208                    .resolve_locator(&owned.sheet, context.current_sheet_id)
209                {
210                    Ok(id) => id,
211                    Err(e) => {
212                        return defer_unbound(
213                            context,
214                            "sheet",
215                            range.sheet.name().unwrap_or(""),
216                            e,
217                        );
218                    }
219                };
220                context.range_dependencies.push(SharedRangeRef {
221                    sheet: SharedSheetLocator::Id(sheet_id),
222                    start_row: owned.start_row,
223                    start_col: owned.start_col,
224                    end_row: owned.end_row,
225                    end_col: owned.end_col,
226                });
227            }
228            Ok(())
229        }
230        SemanticReference::Name(name) => {
231            if let Some(named_range) = context
232                .graph
233                .resolve_name_entry(name, context.current_sheet_id)
234            {
235                context.dependencies.insert(named_range.vertex);
236                context.named_dependencies.push(named_range.vertex);
237            } else if let Some(source) = context.graph.resolve_source_scalar_entry(name) {
238                context.dependencies.insert(source.vertex);
239            } else {
240                match context.unresolved_name_policy {
241                    UnresolvedNamePolicy::Error => {
242                        return Err(ExcelError::new(ExcelErrorKind::Name)
243                            .with_message(format!("Undefined name: {name}")));
244                    }
245                    UnresolvedNamePolicy::Collect => {
246                        context.unresolved_names.insert(name.to_string());
247                    }
248                }
249            }
250            Ok(())
251        }
252        SemanticReference::Table(table_reference) => {
253            if let Some(table) = context.graph.resolve_table_entry(&table_reference.name) {
254                context.dependencies.insert(table.vertex);
255            } else if let Some(source) = context
256                .graph
257                .resolve_source_table_entry(&table_reference.name)
258            {
259                context.dependencies.insert(source.vertex);
260            } else {
261                return defer_unbound(
262                    context,
263                    "table",
264                    &table_reference.name,
265                    ExcelError::new(ExcelErrorKind::Name)
266                        .with_message(format!("Undefined table: {}", table_reference.name)),
267                );
268            }
269            Ok(())
270        }
271        SemanticReference::ThreeDimensional(_) | SemanticReference::Unsupported(_) => Ok(()),
272    }
273}
274impl DependencyGraph {
275    // Helper methods for formula analysis / dependency extraction.
276
277    pub(super) fn extract_dependencies(
278        &mut self,
279        ast: &ASTNode,
280        current_sheet_id: SheetId,
281    ) -> ExtractDependenciesResult {
282        let (dependencies, ranges, placeholders, named_dependencies, _pending_names) =
283            self.extract_dependencies_inner(ast, current_sheet_id, UnresolvedNamePolicy::Error)?;
284        Ok((dependencies, ranges, placeholders, named_dependencies))
285    }
286
287    pub(super) fn extract_dependencies_with_pending_names(
288        &mut self,
289        ast: &ASTNode,
290        current_sheet_id: SheetId,
291    ) -> ExtractDependenciesWithPendingNamesResult {
292        self.extract_dependencies_inner(ast, current_sheet_id, UnresolvedNamePolicy::Collect)
293    }
294
295    pub(super) fn extract_dependencies_arena(
296        &mut self,
297        ast_id: AstNodeId,
298        current_sheet_id: SheetId,
299    ) -> ExtractDependenciesResult {
300        let (dependencies, ranges, placeholders, named_dependencies, _pending_names) = self
301            .extract_dependencies_inner_arena(
302                ast_id,
303                current_sheet_id,
304                UnresolvedNamePolicy::Error,
305            )?;
306        Ok((dependencies, ranges, placeholders, named_dependencies))
307    }
308
309    pub(super) fn extract_dependencies_with_pending_names_arena(
310        &mut self,
311        ast_id: AstNodeId,
312        current_sheet_id: SheetId,
313    ) -> ExtractDependenciesWithPendingNamesResult {
314        self.extract_dependencies_inner_arena(
315            ast_id,
316            current_sheet_id,
317            UnresolvedNamePolicy::Collect,
318        )
319    }
320
321    fn extract_dependencies_inner_arena(
322        &mut self,
323        ast_id: AstNodeId,
324        current_sheet_id: SheetId,
325        unresolved_name_policy: UnresolvedNamePolicy,
326    ) -> ExtractDependenciesWithPendingNamesResult {
327        let mut dependencies = FxHashSet::default();
328        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
329        let mut created_placeholders = Vec::new();
330        let mut named_dependencies = Vec::new();
331        let mut unresolved_names = FxHashSet::default();
332        let mut context = GraphReferenceContext {
333            graph: self,
334            current_sheet_id,
335            dependencies: &mut dependencies,
336            range_dependencies: &mut range_dependencies,
337            created_placeholders: &mut created_placeholders,
338            named_dependencies: &mut named_dependencies,
339            unresolved_names: &mut unresolved_names,
340            unresolved_name_policy,
341        };
342        crate::engine::refs::visit_arena_references(
343            ast_id,
344            &mut context,
345            graph_data_store,
346            graph_sheet_registry,
347            collect_graph_reference,
348        )?;
349
350        // Deduplicate range references.
351        let mut deduped_ranges = Vec::new();
352        for range_ref in range_dependencies {
353            if !deduped_ranges.contains(&range_ref) {
354                deduped_ranges.push(range_ref);
355            }
356        }
357
358        named_dependencies.sort_unstable_by_key(|v| v.0);
359        named_dependencies.dedup_by_key(|v| v.0);
360
361        let mut unresolved_names: Vec<String> = unresolved_names.into_iter().collect();
362        unresolved_names.sort();
363
364        Ok((
365            dependencies.into_iter().collect(),
366            deduped_ranges,
367            created_placeholders,
368            named_dependencies,
369            unresolved_names,
370        ))
371    }
372
373    fn extract_dependencies_inner(
374        &mut self,
375        ast: &ASTNode,
376        current_sheet_id: SheetId,
377        unresolved_name_policy: UnresolvedNamePolicy,
378    ) -> ExtractDependenciesWithPendingNamesResult {
379        let mut dependencies = FxHashSet::default();
380        let mut range_dependencies: Vec<SharedRangeRef<'static>> = Vec::new();
381        let mut created_placeholders = Vec::new();
382        let mut named_dependencies = Vec::new();
383        let mut unresolved_names = FxHashSet::default();
384        let mut context = GraphReferenceContext {
385            graph: self,
386            current_sheet_id,
387            dependencies: &mut dependencies,
388            range_dependencies: &mut range_dependencies,
389            created_placeholders: &mut created_placeholders,
390            named_dependencies: &mut named_dependencies,
391            unresolved_names: &mut unresolved_names,
392            unresolved_name_policy,
393        };
394        crate::engine::refs::visit_tree_references(
395            ast,
396            &mut context,
397            graph_no_local_bindings,
398            collect_graph_reference,
399        )?;
400
401        // Deduplicate range references.
402        let mut deduped_ranges = Vec::new();
403        for range_ref in range_dependencies {
404            if !deduped_ranges.contains(&range_ref) {
405                deduped_ranges.push(range_ref);
406            }
407        }
408
409        named_dependencies.sort_unstable_by_key(|v| v.0);
410        named_dependencies.dedup_by_key(|v| v.0);
411
412        let mut unresolved_names: Vec<String> = unresolved_names.into_iter().collect();
413        unresolved_names.sort();
414
415        Ok((
416            dependencies.into_iter().collect(),
417            deduped_ranges,
418            created_placeholders,
419            named_dependencies,
420            unresolved_names,
421        ))
422    }
423
424    pub(super) fn is_ast_volatile(&self, ast: &ASTNode) -> bool {
425        if ast.contains_volatile() {
426            return true;
427        }
428
429        use formualizer_parse::parser::ASTNodeType;
430
431        match &ast.node_type {
432            ASTNodeType::Function { name, args } => {
433                if let Some(func) = crate::function_registry::get("", name)
434                    && func.caps().contains(crate::function::FnCaps::VOLATILE)
435                {
436                    return true;
437                }
438                args.iter().any(|arg| self.is_ast_volatile(arg))
439            }
440            ASTNodeType::BinaryOp { left, right, .. } => {
441                self.is_ast_volatile(left) || self.is_ast_volatile(right)
442            }
443            ASTNodeType::UnaryOp { expr, .. } => self.is_ast_volatile(expr),
444            ASTNodeType::Array(rows) => rows
445                .iter()
446                .any(|row| row.iter().any(|cell| self.is_ast_volatile(cell))),
447            ASTNodeType::Call { callee, args } => {
448                self.is_ast_volatile(callee) || args.iter().any(|a| self.is_ast_volatile(a))
449            }
450            _ => false,
451        }
452    }
453
454    pub fn is_ast_dynamic(&self, ast: &ASTNode) -> bool {
455        use formualizer_parse::parser::ASTNodeType;
456
457        match &ast.node_type {
458            ASTNodeType::Function { name, args } => {
459                if let Some(func) = crate::function_registry::get("", name)
460                    && func
461                        .caps()
462                        .contains(crate::function::FnCaps::DYNAMIC_DEPENDENCY)
463                {
464                    return true;
465                }
466                args.iter().any(|arg| self.is_ast_dynamic(arg))
467            }
468            ASTNodeType::BinaryOp { left, right, .. } => {
469                self.is_ast_dynamic(left) || self.is_ast_dynamic(right)
470            }
471            ASTNodeType::UnaryOp { expr, .. } => self.is_ast_dynamic(expr),
472            ASTNodeType::Array(rows) => rows
473                .iter()
474                .any(|row| row.iter().any(|cell| self.is_ast_dynamic(cell))),
475            ASTNodeType::Call { callee, args } => {
476                self.is_ast_dynamic(callee) || args.iter().any(|a| self.is_ast_dynamic(a))
477            }
478            _ => false,
479        }
480    }
481}
formualizer_eval/engine/graph/formula_analysis.rs

formualizer_eval/engine/graph/
formula_analysis.rs
