formualizer_eval/engine/
virtual_deps.rs

1use crate::engine::VertexId;
2use crate::engine::VertexKind;
3use crate::engine::eval::Engine;
4use crate::engine::used_extent::{
5    ExtentPolicy, OpenRangeBounds, ResolvedExtent, resolve_used_extent_with_fallback,
6};
7use crate::formula_plane::region_index::Region;
8use crate::traits::{
9    EvaluationContext, FunctionProvider, NamedRangeResolver, Range, RangeResolver,
10    ReferenceResolver, Resolver, SourceResolver, Table, TableResolver,
11};
12use formualizer_common::{ExcelError, LiteralValue};
13use formualizer_parse::parser::{ReferenceType, TableReference};
14use rustc_hash::FxHashSet;
15use std::sync::Mutex;
16
17use crate::interpreter::Interpreter;
18
19pub struct DynamicRefCollector<'a, R: EvaluationContext> {
20    pub engine: &'a Engine<R>,
21    pub current_sheet: &'a str,
22    pub(crate) collected: Mutex<FxHashSet<VertexId>>,
23    pub(crate) collected_regions: Mutex<FxHashSet<Region>>,
24}
25
26impl<'a, R: EvaluationContext> DynamicRefCollector<'a, R> {
27    pub fn new(engine: &'a Engine<R>, current_sheet: &'a str) -> Self {
28        Self {
29            engine,
30            current_sheet,
31            collected: Mutex::new(FxHashSet::default()),
32            collected_regions: Mutex::new(FxHashSet::default()),
33        }
34    }
35
36    fn collect_formula_vertices_in_rect(
37        &self,
38        sheet_name: &str,
39        sr: u32,
40        sc: u32,
41        er: u32,
42        ec: u32,
43    ) {
44        let Some(sheet_id) = self.engine.graph.sheet_id(sheet_name) else {
45            return;
46        };
47        let sr0 = sr.saturating_sub(1);
48        let er0 = er.saturating_sub(1);
49        let sc0 = sc.saturating_sub(1);
50        let ec0 = ec.saturating_sub(1);
51        self.collected_regions
52            .lock()
53            .unwrap()
54            .insert(Region::rect(sheet_id, sr0, er0, sc0, ec0).normalized());
55        let Some(index) = self.engine.graph.sheet_index(sheet_id) else {
56            return;
57        };
58
59        let mut out = self.collected.lock().unwrap();
60        for u in index.vertices_in_col_range(sc0, ec0) {
61            let row0 = self.engine.graph.vertex_coord(u).row();
62            if row0 < sr0 || row0 > er0 {
63                continue;
64            }
65            match self.engine.graph.get_vertex_kind(u) {
66                VertexKind::FormulaScalar | VertexKind::FormulaArray => {
67                    if self.engine.graph.is_dirty(u) || self.engine.graph.is_volatile(u) {
68                        out.insert(u);
69                    }
70                }
71                _ => {}
72            }
73        }
74    }
75
76    fn collect_formula_vertices_for_range(
77        &self,
78        sheet_name: &str,
79        start_row: Option<u32>,
80        start_col: Option<u32>,
81        end_row: Option<u32>,
82        end_col: Option<u32>,
83    ) {
84        let Some(extent) = resolve_used_extent_with_fallback(
85            OpenRangeBounds {
86                start_row,
87                start_column: start_col,
88                end_row,
89                end_column: end_col,
90            },
91            ExtentPolicy::EvaluationCompat {
92                fallback_row: None,
93                fallback_column: None,
94            },
95            || {
96                self.engine
97                    .sheet_bounds(sheet_name)
98                    .map(|_| self.engine.config.max_open_ended_rows)
99            },
100            || {
101                self.engine
102                    .sheet_bounds(sheet_name)
103                    .map(|_| self.engine.config.max_open_ended_cols)
104            },
105            |first, last| self.engine.used_rows_for_columns(sheet_name, first, last),
106            |first, last| self.engine.used_cols_for_rows(sheet_name, first, last),
107        ) else {
108            return;
109        };
110
111        self.collect_formula_vertices_in_rect(
112            sheet_name,
113            extent.start_row,
114            extent.start_column,
115            extent.end_row,
116            extent.end_column,
117        );
118    }
119}
120
121impl<'a, R: EvaluationContext> ReferenceResolver for DynamicRefCollector<'a, R> {
122    fn resolve_cell_reference(
123        &self,
124        sheet: Option<&str>,
125        row: u32,
126        col: u32,
127    ) -> Result<LiteralValue, ExcelError> {
128        let sheet_name = sheet.unwrap_or(self.current_sheet);
129        if let Some(sheet_id) = self.engine.graph.sheet_id(sheet_name) {
130            self.collected_regions.lock().unwrap().insert(Region::point(
131                sheet_id,
132                row.saturating_sub(1),
133                col.saturating_sub(1),
134            ));
135        }
136        if let Some(&vid) = self
137            .engine
138            .graph
139            .get_vertex_id_for_address(&self.engine.graph.make_cell_ref(sheet_name, row, col))
140        {
141            self.collected.lock().unwrap().insert(vid);
142        }
143        self.engine.resolve_cell_reference(sheet, row, col)
144    }
145}
146
147impl<'a, R: EvaluationContext> RangeResolver for DynamicRefCollector<'a, R> {
148    fn resolve_range_reference(
149        &self,
150        sheet: Option<&str>,
151        sr: Option<u32>,
152        sc: Option<u32>,
153        er: Option<u32>,
154        ec: Option<u32>,
155    ) -> Result<Box<dyn Range>, ExcelError> {
156        let sheet_name = sheet.unwrap_or(self.current_sheet);
157        self.collect_formula_vertices_for_range(sheet_name, sr, sc, er, ec);
158        self.engine.resolve_range_reference(sheet, sr, sc, er, ec)
159    }
160}
161
162impl<'a, R: EvaluationContext> NamedRangeResolver for DynamicRefCollector<'a, R> {
163    fn resolve_named_range_reference(
164        &self,
165        name: &str,
166    ) -> Result<Vec<Vec<LiteralValue>>, ExcelError> {
167        self.engine.resolve_named_range_reference(name)
168    }
169}
170
171impl<'a, R: EvaluationContext> TableResolver for DynamicRefCollector<'a, R> {
172    fn resolve_table_reference(&self, tref: &TableReference) -> Result<Box<dyn Table>, ExcelError> {
173        self.engine.resolve_table_reference(tref)
174    }
175}
176
177impl<'a, R: EvaluationContext> SourceResolver for DynamicRefCollector<'a, R> {
178    fn source_scalar_version(&self, name: &str) -> Option<u64> {
179        self.engine.source_scalar_version(name)
180    }
181    fn resolve_source_scalar(&self, name: &str) -> Result<LiteralValue, ExcelError> {
182        self.engine.resolve_source_scalar(name)
183    }
184    fn source_table_version(&self, name: &str) -> Option<u64> {
185        self.engine.source_table_version(name)
186    }
187    fn resolve_source_table(&self, name: &str) -> Result<Box<dyn Table>, ExcelError> {
188        self.engine.resolve_source_table(name)
189    }
190}
191
192impl<'a, R: EvaluationContext> Resolver for DynamicRefCollector<'a, R> {}
193
194impl<'a, R: EvaluationContext> FunctionProvider for DynamicRefCollector<'a, R> {
195    fn planning_semantic_revision(&self) -> Option<u64> {
196        self.engine.planning_semantic_revision()
197    }
198
199    fn get_function(
200        &self,
201        ns: &str,
202        name: &str,
203    ) -> Option<std::sync::Arc<dyn crate::traits::Function>> {
204        self.engine.get_function(ns, name)
205    }
206
207    fn get_function_for_planning(
208        &self,
209        ns: &str,
210        name: &str,
211    ) -> Option<std::sync::Arc<dyn crate::traits::Function>> {
212        self.engine.get_function_for_planning(ns, name)
213    }
214}
215
216impl<'a, R: EvaluationContext> EvaluationContext for DynamicRefCollector<'a, R> {
217    fn cancellation_token(&self) -> Option<crate::engine::CancelToken> {
218        self.engine.cancellation_token()
219    }
220
221    fn resolve_range_view<'c>(
222        &'c self,
223        reference: &ReferenceType,
224        current_sheet: &str,
225    ) -> Result<crate::engine::range_view::RangeView<'c>, ExcelError> {
226        // Collect vertices directly
227        match reference {
228            ReferenceType::Cell {
229                sheet, row, col, ..
230            } => {
231                let sheet_name = sheet.as_deref().unwrap_or(current_sheet);
232                self.collect_formula_vertices_in_rect(sheet_name, *row, *col, *row, *col);
233            }
234            ReferenceType::Range {
235                sheet,
236                start_row,
237                start_col,
238                end_row,
239                end_col,
240                ..
241            } => {
242                let sheet_name = sheet.as_deref().unwrap_or(current_sheet);
243                self.collect_formula_vertices_for_range(
244                    sheet_name, *start_row, *start_col, *end_row, *end_col,
245                );
246            }
247            ReferenceType::NamedRange(name) => {
248                let sid = self.engine.sheet_id(current_sheet);
249                if let Some(s) = sid
250                    && let Some(nr) = self.engine.graph.resolve_name_entry(name, s)
251                {
252                    let vid = nr.vertex;
253                    self.collected.lock().unwrap().insert(vid);
254                }
255            }
256            ReferenceType::Table(_) => {
257                // Table references might be tricky, skip for now or resolve from graph if possible
258            }
259            _ => {}
260        }
261
262        self.engine.resolve_range_view(reference, current_sheet)
263    }
264}
265
266pub struct RangeVirtualDepProvider;
267
268impl RangeVirtualDepProvider {
269    pub(crate) fn resolve_range<R: EvaluationContext>(
270        engine: &Engine<R>,
271        sheet_name: &str,
272        range: &formualizer_common::SheetRangeRef<'_>,
273    ) -> Option<ResolvedExtent> {
274        resolve_used_extent_with_fallback(
275            OpenRangeBounds {
276                start_row: range.start_row.map(|bound| bound.index + 1),
277                start_column: range.start_col.map(|bound| bound.index + 1),
278                end_row: range.end_row.map(|bound| bound.index + 1),
279                end_column: range.end_col.map(|bound| bound.index + 1),
280            },
281            ExtentPolicy::VirtualDependencyCompat {
282                fallback_row: None,
283                fallback_column: None,
284            },
285            || {
286                engine
287                    .sheet_bounds(sheet_name)
288                    .map(|_| engine.config.max_open_ended_rows)
289            },
290            || {
291                engine
292                    .sheet_bounds(sheet_name)
293                    .map(|_| engine.config.max_open_ended_cols)
294            },
295            |first, last| engine.used_rows_for_columns(sheet_name, first, last),
296            |first, last| engine.used_cols_for_rows(sheet_name, first, last),
297        )
298    }
299
300    pub fn get_virtual_deps<R: EvaluationContext>(
301        engine: &Engine<R>,
302        v: VertexId,
303    ) -> Vec<VertexId> {
304        let mut deps = Vec::new();
305        if let Some(ranges) = engine.graph.get_range_dependencies(v) {
306            let current_sheet_id = engine.graph.get_vertex_sheet_id(v);
307            for r in ranges {
308                let sheet_id = match r.sheet {
309                    formualizer_common::SheetLocator::Id(id) => id,
310                    _ => current_sheet_id,
311                };
312                let sheet_name = engine.graph.sheet_name(sheet_id);
313
314                let Some(extent) = Self::resolve_range(engine, sheet_name, r) else {
315                    continue;
316                };
317                let sr = extent.start_row;
318                let sc = extent.start_column;
319                let er = extent.end_row;
320                let ec = extent.end_column;
321
322                if let Some(index) = engine.graph.sheet_index(sheet_id) {
323                    let sr0 = sr.saturating_sub(1);
324                    let er0 = er.saturating_sub(1);
325                    let sc0 = sc.saturating_sub(1);
326                    let ec0 = ec.saturating_sub(1);
327                    for u in index.vertices_in_col_range(sc0, ec0) {
328                        let pc = engine.graph.vertex_coord(u);
329                        let row0 = pc.row();
330                        if row0 < sr0 || row0 > er0 {
331                            continue;
332                        }
333                        match engine.graph.get_vertex_kind(u) {
334                            VertexKind::FormulaScalar | VertexKind::FormulaArray => {
335                                if (engine.graph.is_dirty(u) || engine.graph.is_volatile(u))
336                                    && u != v
337                                {
338                                    deps.push(u);
339                                }
340                            }
341                            _ => {}
342                        }
343                    }
344                }
345            }
346        }
347        deps
348    }
349}
350
351pub struct VirtualDepBuilder<'a, R: EvaluationContext> {
352    engine: &'a Engine<R>,
353}
354
355impl<'a, R: EvaluationContext> VirtualDepBuilder<'a, R> {
356    pub fn new(engine: &'a Engine<R>) -> Self {
357        Self { engine }
358    }
359    pub fn build(
360        &self,
361        candidates: &[VertexId],
362    ) -> (
363        rustc_hash::FxHashMap<VertexId, Vec<VertexId>>,
364        Vec<VertexId>,
365    ) {
366        let mut vdeps: rustc_hash::FxHashMap<VertexId, Vec<VertexId>> =
367            rustc_hash::FxHashMap::default();
368        let augmented_vertices: Vec<VertexId> = Vec::new(); // Will be populated in Phase 3
369
370        for &v in candidates {
371            let mut deps = RangeVirtualDepProvider::get_virtual_deps(self.engine, v);
372            let dynamic_deps = DynamicRefVirtualDepProvider::get_virtual_deps(self.engine, v);
373
374            deps.extend(dynamic_deps);
375            deps.sort_unstable();
376            deps.dedup();
377
378            if !deps.is_empty() {
379                vdeps.insert(v, deps);
380            }
381        }
382
383        (vdeps, augmented_vertices)
384    }
385}
386
387pub struct DynamicRefVirtualDepProvider;
388
389impl DynamicRefVirtualDepProvider {
390    fn collect<R: EvaluationContext>(
391        engine: &Engine<R>,
392        v: VertexId,
393    ) -> (Vec<VertexId>, Vec<Region>) {
394        if !engine.graph.is_dynamic(v) {
395            return (Vec::new(), Vec::new());
396        }
397        let Some(ast_id) = engine.graph.get_formula_id(v) else {
398            return (Vec::new(), Vec::new());
399        };
400        let sheet_id = engine.graph.get_vertex_sheet_id(v);
401        let sheet_name = engine.graph.sheet_name(sheet_id);
402        let collector = DynamicRefCollector::new(engine, sheet_name);
403        let cell_ref = engine
404            .graph
405            .get_cell_ref(v)
406            .unwrap_or_else(|| engine.graph.make_cell_ref(sheet_name, 0, 0));
407        let interpreter = Interpreter::new_with_cell(&collector, sheet_name, cell_ref);
408        let _ = interpreter.evaluate_arena_ast(
409            ast_id,
410            engine.graph.data_store(),
411            engine.graph.sheet_reg(),
412        );
413        let mut deps = collector
414            .collected
415            .lock()
416            .unwrap()
417            .iter()
418            .copied()
419            .filter(|&dependency| dependency != v)
420            .collect::<Vec<_>>();
421        deps.sort_unstable();
422        deps.dedup();
423        let mut regions = collector
424            .collected_regions
425            .lock()
426            .unwrap()
427            .iter()
428            .copied()
429            .collect::<Vec<_>>();
430        regions.sort_by_key(|region| {
431            let (rows, cols) = region.axis_ranges();
432            (region.sheet_id(), rows.query_bounds(), cols.query_bounds())
433        });
434        regions.dedup();
435        (deps, regions)
436    }
437
438    pub fn get_virtual_deps<R: EvaluationContext>(
439        engine: &Engine<R>,
440        v: VertexId,
441    ) -> Vec<VertexId> {
442        Self::collect(engine, v).0
443    }
444
445    pub(crate) fn get_virtual_regions<R: EvaluationContext>(
446        engine: &Engine<R>,
447        v: VertexId,
448    ) -> Vec<Region> {
449        Self::collect(engine, v).1
450    }
451}
formualizer_eval/engine/virtual_deps.rs

formualizer_eval/engine/
virtual_deps.rs
