formualizer_eval/engine/
virtual_deps.rs

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

formualizer_eval/engine/
virtual_deps.rs
