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

formualizer_eval/engine/
virtual_deps.rs
