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

formualizer_eval/engine/graph/
formula_analysis.rs
