formualizer_eval/engine/
virtual_deps.rs

1use crate::engine::VertexId;
2use crate::engine::VertexKind;
3use crate::engine::eval::Engine;
4use crate::engine::template::region::Region;
5use crate::engine::used_extent::{
6    ExtentPolicy, OpenRangeBounds, ResolvedExtent, resolve_used_extent_with_fallback,
7};
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        if self.engine.graph.sheet_index(sheet_id).is_none() {
56            return;
57        }
58
59        let mut out = self.collected.lock().unwrap();
60        for u in self.engine.graph.vertices_in_cols(sheet_id, sc0, ec0) {
61            let Some(row0) = self.engine.graph.vertex_grid_addr(u).map(|addr| addr.row()) else {
62                continue;
63            };
64            if row0 < sr0 || row0 > er0 {
65                continue;
66            }
67            match self.engine.graph.get_vertex_kind(u) {
68                VertexKind::FormulaScalar | VertexKind::FormulaArray
69                    if (self.engine.graph.is_dirty(u) || self.engine.graph.is_volatile(u)) =>
70                {
71                    out.insert(u);
72                }
73                _ => {}
74            }
75        }
76    }
77
78    fn collect_formula_vertices_for_range(
79        &self,
80        sheet_name: &str,
81        start_row: Option<u32>,
82        start_col: Option<u32>,
83        end_row: Option<u32>,
84        end_col: Option<u32>,
85    ) {
86        let Some(extent) = resolve_used_extent_with_fallback(
87            OpenRangeBounds {
88                start_row,
89                start_column: start_col,
90                end_row,
91                end_column: end_col,
92            },
93            ExtentPolicy::EvaluationCompat {
94                fallback_row: None,
95                fallback_column: None,
96            },
97            || {
98                self.engine
99                    .sheet_bounds(sheet_name)
100                    .map(|_| self.engine.config.max_open_ended_rows)
101            },
102            || {
103                self.engine
104                    .sheet_bounds(sheet_name)
105                    .map(|_| self.engine.config.max_open_ended_cols)
106            },
107            |first, last| self.engine.used_rows_for_columns(sheet_name, first, last),
108            |first, last| self.engine.used_cols_for_rows(sheet_name, first, last),
109        ) else {
110            return;
111        };
112
113        self.collect_formula_vertices_in_rect(
114            sheet_name,
115            extent.start_row,
116            extent.start_column,
117            extent.end_row,
118            extent.end_column,
119        );
120    }
121}
122
123impl<'a, R: EvaluationContext> ReferenceResolver for DynamicRefCollector<'a, R> {
124    fn resolve_cell_reference(
125        &self,
126        sheet: Option<&str>,
127        row: u32,
128        col: u32,
129    ) -> Result<LiteralValue, ExcelError> {
130        let sheet_name = sheet.unwrap_or(self.current_sheet);
131        if let Some(sheet_id) = self.engine.graph.sheet_id(sheet_name) {
132            self.collected_regions.lock().unwrap().insert(Region::point(
133                sheet_id,
134                row.saturating_sub(1),
135                col.saturating_sub(1),
136            ));
137        }
138        if let Some(vid) = self
139            .engine
140            .graph
141            .get_vertex_id_for_address(&self.engine.graph.make_cell_ref(sheet_name, row, col))
142        {
143            self.collected.lock().unwrap().insert(vid);
144        }
145        self.engine.resolve_cell_reference(sheet, row, col)
146    }
147}
148
149impl<'a, R: EvaluationContext> RangeResolver for DynamicRefCollector<'a, R> {
150    fn resolve_range_reference(
151        &self,
152        sheet: Option<&str>,
153        sr: Option<u32>,
154        sc: Option<u32>,
155        er: Option<u32>,
156        ec: Option<u32>,
157    ) -> Result<Box<dyn Range>, ExcelError> {
158        let sheet_name = sheet.unwrap_or(self.current_sheet);
159        self.collect_formula_vertices_for_range(sheet_name, sr, sc, er, ec);
160        self.engine.resolve_range_reference(sheet, sr, sc, er, ec)
161    }
162}
163
164impl<'a, R: EvaluationContext> NamedRangeResolver for DynamicRefCollector<'a, R> {
165    fn resolve_named_range_reference(
166        &self,
167        name: &str,
168    ) -> Result<Vec<Vec<LiteralValue>>, ExcelError> {
169        self.engine.resolve_named_range_reference(name)
170    }
171}
172
173impl<'a, R: EvaluationContext> TableResolver for DynamicRefCollector<'a, R> {
174    fn resolve_table_reference(&self, tref: &TableReference) -> Result<Box<dyn Table>, ExcelError> {
175        self.engine.resolve_table_reference(tref)
176    }
177}
178
179impl<'a, R: EvaluationContext> SourceResolver for DynamicRefCollector<'a, R> {
180    fn source_scalar_version(&self, name: &str) -> Option<u64> {
181        self.engine.source_scalar_version(name)
182    }
183    fn resolve_source_scalar(&self, name: &str) -> Result<LiteralValue, ExcelError> {
184        self.engine.resolve_source_scalar(name)
185    }
186    fn source_table_version(&self, name: &str) -> Option<u64> {
187        self.engine.source_table_version(name)
188    }
189    fn resolve_source_table(&self, name: &str) -> Result<Box<dyn Table>, ExcelError> {
190        self.engine.resolve_source_table(name)
191    }
192}
193
194impl<'a, R: EvaluationContext> Resolver for DynamicRefCollector<'a, R> {}
195
196impl<'a, R: EvaluationContext> FunctionProvider for DynamicRefCollector<'a, R> {
197    fn planning_semantic_revision(&self) -> Option<u64> {
198        self.engine.planning_semantic_revision()
199    }
200
201    fn get_function(
202        &self,
203        ns: &str,
204        name: &str,
205    ) -> Option<std::sync::Arc<dyn crate::traits::Function>> {
206        self.engine.get_function(ns, name)
207    }
208
209    fn get_function_for_planning(
210        &self,
211        ns: &str,
212        name: &str,
213    ) -> Option<std::sync::Arc<dyn crate::traits::Function>> {
214        self.engine.get_function_for_planning(ns, name)
215    }
216}
217
218impl<'a, R: EvaluationContext> EvaluationContext for DynamicRefCollector<'a, R> {
219    fn operation_diagnostic_collector(
220        &self,
221    ) -> Option<&crate::operation_diagnostics::OperationDiagnosticCollector> {
222        self.engine.operation_diagnostic_collector()
223    }
224
225    fn cancellation_token(&self) -> Option<crate::engine::CancelToken> {
226        self.engine.cancellation_token()
227    }
228
229    fn materialized_array_cells(&self) -> u64 {
230        self.engine.materialized_array_cells()
231    }
232
233    fn resolve_cell_format(
234        &self,
235        sheet: Option<&str>,
236        row: u32,
237        col: u32,
238        current_sheet: &str,
239    ) -> Option<crate::format::FormatId> {
240        self.engine
241            .resolve_cell_format(sheet, row, col, current_sheet)
242    }
243
244    fn format_class(
245        &self,
246        format: crate::format::FormatId,
247    ) -> Option<formualizer_common::numfmt::FormatClass> {
248        self.engine.format_class(format)
249    }
250
251    fn record_cell_derived_format(
252        &self,
253        sheet: &str,
254        row: u32,
255        col: u32,
256        format: Option<crate::format::FormatId>,
257    ) {
258        self.engine
259            .record_cell_derived_format(sheet, row, col, format)
260    }
261
262    fn resolve_range_view<'c>(
263        &'c self,
264        reference: &ReferenceType,
265        current_sheet: &str,
266    ) -> Result<crate::engine::range_view::RangeView<'c>, ExcelError> {
267        // Collect vertices directly
268        match reference {
269            ReferenceType::Cell {
270                sheet, row, col, ..
271            } => {
272                let sheet_name = sheet.as_deref().unwrap_or(current_sheet);
273                self.collect_formula_vertices_in_rect(sheet_name, *row, *col, *row, *col);
274            }
275            ReferenceType::Range {
276                sheet,
277                start_row,
278                start_col,
279                end_row,
280                end_col,
281                ..
282            } => {
283                let sheet_name = sheet.as_deref().unwrap_or(current_sheet);
284                self.collect_formula_vertices_for_range(
285                    sheet_name, *start_row, *start_col, *end_row, *end_col,
286                );
287            }
288            ReferenceType::NamedRange(name) => {
289                let sid = self.engine.sheet_id(current_sheet);
290                if let Some(s) = sid
291                    && let Some(nr) = self.engine.graph.resolve_name_entry(name, s)
292                {
293                    let vid = nr.vertex;
294                    self.collected.lock().unwrap().insert(vid);
295                }
296            }
297            ReferenceType::Table(_) => {
298                // Table references might be tricky, skip for now or resolve from graph if possible
299            }
300            _ => {}
301        }
302
303        self.engine.resolve_range_view(reference, current_sheet)
304    }
305
306    fn resolve_spill_reference(
307        &self,
308        anchor: &ReferenceType,
309        current_sheet: &str,
310    ) -> Result<ReferenceType, ExcelError> {
311        // The anchor is a dependency whether or not it currently spills.
312        match anchor {
313            ReferenceType::Cell {
314                sheet, row, col, ..
315            } => {
316                let sheet_name = sheet.as_deref().unwrap_or(current_sheet);
317                self.collect_formula_vertices_in_rect(sheet_name, *row, *col, *row, *col);
318            }
319            ReferenceType::NamedRange(name) => {
320                if let Some(sheet_id) = self.engine.sheet_id(current_sheet)
321                    && let Some(named) = self.engine.graph.resolve_name_entry(name, sheet_id)
322                {
323                    self.collected.lock().unwrap().insert(named.vertex);
324                }
325            }
326            _ => {}
327        }
328        self.engine.resolve_spill_reference(anchor, current_sheet)
329    }
330}
331
332pub struct RangeVirtualDepProvider;
333
334impl RangeVirtualDepProvider {
335    pub(crate) fn resolve_range<R: EvaluationContext>(
336        engine: &Engine<R>,
337        sheet_name: &str,
338        range: &formualizer_common::SheetRangeRef<'_>,
339    ) -> Option<ResolvedExtent> {
340        resolve_used_extent_with_fallback(
341            OpenRangeBounds {
342                start_row: range.start_row.map(|bound| bound.index + 1),
343                start_column: range.start_col.map(|bound| bound.index + 1),
344                end_row: range.end_row.map(|bound| bound.index + 1),
345                end_column: range.end_col.map(|bound| bound.index + 1),
346            },
347            ExtentPolicy::VirtualDependencyCompat {
348                fallback_row: None,
349                fallback_column: None,
350            },
351            || {
352                engine
353                    .sheet_bounds(sheet_name)
354                    .map(|_| engine.config.max_open_ended_rows)
355            },
356            || {
357                engine
358                    .sheet_bounds(sheet_name)
359                    .map(|_| engine.config.max_open_ended_cols)
360            },
361            |first, last| engine.used_rows_for_columns(sheet_name, first, last),
362            |first, last| engine.used_cols_for_rows(sheet_name, first, last),
363        )
364    }
365
366    #[cfg(any(test, feature = "legacy_oracle"))]
367    pub fn get_virtual_deps<R: EvaluationContext>(
368        engine: &Engine<R>,
369        v: VertexId,
370    ) -> Vec<VertexId> {
371        let mut deps = Vec::new();
372        if let Some(ranges) = engine.graph.get_range_dependencies(v) {
373            let current_sheet_id = engine.graph.get_vertex_sheet_id(v);
374            for r in ranges {
375                let sheet_id = match r.sheet {
376                    formualizer_common::SheetLocator::Id(id) => id,
377                    _ => current_sheet_id,
378                };
379                let sheet_name = engine.graph.sheet_name(sheet_id);
380
381                let Some(extent) = Self::resolve_range(engine, sheet_name, r) else {
382                    continue;
383                };
384                let sr = extent.start_row;
385                let sc = extent.start_column;
386                let er = extent.end_row;
387                let ec = extent.end_column;
388
389                if engine.graph.sheet_index(sheet_id).is_some() {
390                    let sr0 = sr.saturating_sub(1);
391                    let er0 = er.saturating_sub(1);
392                    let sc0 = sc.saturating_sub(1);
393                    let ec0 = ec.saturating_sub(1);
394                    for u in engine.graph.vertices_in_cols(sheet_id, sc0, ec0) {
395                        let Some(pc) = engine.graph.vertex_grid_addr(u) else {
396                            continue;
397                        };
398                        let row0 = pc.row();
399                        if row0 < sr0 || row0 > er0 {
400                            continue;
401                        }
402                        match engine.graph.get_vertex_kind(u) {
403                            VertexKind::FormulaScalar | VertexKind::FormulaArray
404                                if (engine.graph.is_dirty(u) || engine.graph.is_volatile(u))
405                                    && u != v =>
406                            {
407                                deps.push(u);
408                            }
409                            _ => {}
410                        }
411                    }
412                }
413            }
414        }
415        deps
416    }
417}
418
419pub struct VirtualDepBuilder<'a, R: EvaluationContext> {
420    engine: &'a Engine<R>,
421}
422
423impl<'a, R: EvaluationContext> VirtualDepBuilder<'a, R> {
424    pub fn new(engine: &'a Engine<R>) -> Self {
425        Self { engine }
426    }
427    /// Plan hints for `candidates`. Under `unified_authority` a compressed
428    /// range read is an ordinary static edge of the relation (R-1), so the
429    /// planner already orders every formula inside the range before its
430    /// reader; only dynamic readers get hints (design §8.2). Enumerating the
431    /// range members costs |readers| × |range formulas| hints (100M for
432    /// 1,000 SUMIFS over a 100k formula column), and resolving their used
433    /// extent at plan time caches it before same-pass spills commit.
434    pub fn build(
435        &self,
436        candidates: &[VertexId],
437    ) -> (
438        rustc_hash::FxHashMap<VertexId, Vec<VertexId>>,
439        Vec<VertexId>,
440    ) {
441        self.build_inner(candidates, false)
442    }
443
444    /// Legacy's hints, range members included: what the legacy scheduler
445    /// (the test oracle) needs, since its range stripes carry no edges.
446    pub fn build_with_range_members(
447        &self,
448        candidates: &[VertexId],
449    ) -> (
450        rustc_hash::FxHashMap<VertexId, Vec<VertexId>>,
451        Vec<VertexId>,
452    ) {
453        self.build_inner(candidates, true)
454    }
455
456    fn build_inner(
457        &self,
458        candidates: &[VertexId],
459        range_members: bool,
460    ) -> (
461        rustc_hash::FxHashMap<VertexId, Vec<VertexId>>,
462        Vec<VertexId>,
463    ) {
464        let mut vdeps: rustc_hash::FxHashMap<VertexId, Vec<VertexId>> =
465            rustc_hash::FxHashMap::default();
466        let augmented_vertices: Vec<VertexId> = Vec::new(); // Will be populated in Phase 3
467
468        for &v in candidates {
469            // Range members are legacy's hints (its stripes carry no
470            // scheduling edges): the oracle scheduler's input only.
471            #[cfg(any(test, feature = "legacy_oracle"))]
472            let mut deps = if range_members {
473                RangeVirtualDepProvider::get_virtual_deps(self.engine, v)
474            } else {
475                Vec::new()
476            };
477            #[cfg(not(any(test, feature = "legacy_oracle")))]
478            let mut deps = Vec::new();
479            // Under the authority a reader with an observed read set is
480            // planned from it (rdi_dyn, rectangle hints); the pre-probe is
481            // for first evaluations only (design §8.2).
482            let observed =
483                !range_members && self.engine.graph.authority_host().observed(v).is_some();
484            let dynamic_deps = if observed {
485                Vec::new()
486            } else {
487                DynamicRefVirtualDepProvider::get_virtual_deps(self.engine, v)
488            };
489
490            deps.extend(dynamic_deps);
491            deps.sort_unstable();
492            deps.dedup();
493
494            if !deps.is_empty() {
495                vdeps.insert(v, deps);
496            }
497        }
498
499        (vdeps, augmented_vertices)
500    }
501}
502
503pub struct DynamicRefVirtualDepProvider;
504
505impl DynamicRefVirtualDepProvider {
506    fn collect<R: EvaluationContext>(
507        engine: &Engine<R>,
508        v: VertexId,
509    ) -> (Vec<VertexId>, Vec<Region>) {
510        if !engine.graph.is_dynamic(v) {
511            return (Vec::new(), Vec::new());
512        }
513        let Some(view) = engine.graph.formula_view(v) else {
514            return (Vec::new(), Vec::new());
515        };
516        let sheet_id = engine.graph.get_vertex_sheet_id(v);
517        let sheet_name = engine.graph.sheet_name(sheet_id);
518        // Discovery can select branches from retained, dirty precedent values.
519        // Count that physical work as speculative inside a request; public
520        // dependency queries outside a request must not mutate its last report.
521        let _diagnostics = engine.operation_diagnostic_collector().map(|collector| {
522            collector.scope(if engine.diagnostic_request_active() {
523                crate::operation_diagnostics::Mode::Speculative
524            } else {
525                crate::operation_diagnostics::Mode::Suppressed
526            })
527        });
528        let collector = DynamicRefCollector::new(engine, sheet_name);
529        let cell_ref = engine
530            .graph
531            .get_cell_ref(v)
532            .unwrap_or_else(|| engine.graph.make_cell_ref(sheet_name, 0, 0));
533        // This query is public and may run outside an evaluation request, when
534        // the per-request function table can be empty or stale: use it only
535        // when it is current, otherwise resolve through the provider.
536        let interpreter = Interpreter::new_with_cell(&collector, sheet_name, cell_ref);
537        let interpreter = match engine.current_resolved_functions() {
538            Some(table) => interpreter.with_resolved_functions(table),
539            None => interpreter,
540        };
541        let _ = interpreter.evaluate_formula_view(
542            view,
543            engine.graph.data_store(),
544            engine.graph.sheet_reg(),
545        );
546        let mut deps = collector
547            .collected
548            .lock()
549            .unwrap()
550            .iter()
551            .copied()
552            .filter(|&dependency| dependency != v)
553            .collect::<Vec<_>>();
554        deps.sort_unstable();
555        deps.dedup();
556        let mut regions = collector
557            .collected_regions
558            .lock()
559            .unwrap()
560            .iter()
561            .copied()
562            .collect::<Vec<_>>();
563        regions.sort_by_key(|region| {
564            let (rows, cols) = region.axis_ranges();
565            (region.sheet_id(), rows.query_bounds(), cols.query_bounds())
566        });
567        regions.dedup();
568        (deps, regions)
569    }
570
571    pub fn get_virtual_deps<R: EvaluationContext>(
572        engine: &Engine<R>,
573        v: VertexId,
574    ) -> Vec<VertexId> {
575        Self::collect(engine, v).0
576    }
577
578    pub(crate) fn get_virtual_regions<R: EvaluationContext>(
579        engine: &Engine<R>,
580        v: VertexId,
581    ) -> Vec<Region> {
582        Self::collect(engine, v).1
583    }
584}
585
586#[cfg(test)]
587mod tests {
588    use super::DynamicRefVirtualDepProvider;
589    use crate::engine::{Engine, EvalConfig};
590    use crate::test_workbook::TestWorkbook;
591
592    /// The query is public and may run before any evaluation request has
593    /// refreshed the per-request function table.
594    #[test]
595    fn virtual_deps_before_any_evaluation_request() {
596        crate::builtins::load_builtins();
597        let mut engine = Engine::new(TestWorkbook::new(), EvalConfig::default());
598        engine.add_sheet("S").expect("sheet");
599        engine
600            .set_cell_formula("S", 1, 1, formualizer_parse::parse("=42").expect("parse"))
601            .expect("A1");
602        engine
603            .set_cell_formula(
604                "S",
605                1,
606                2,
607                formualizer_parse::parse("=INDIRECT(\"A1\")+0").expect("parse"),
608            )
609            .expect("B1");
610        let found: usize = engine
611            .evaluation_vertices()
612            .into_iter()
613            .map(|v| DynamicRefVirtualDepProvider::get_virtual_deps(&engine, v).len())
614            .sum();
615        assert!(
616            found > 0,
617            "INDIRECT's target must be found before the first request"
618        );
619    }
620}
formualizer_eval/engine/virtual_deps.rs

formualizer_eval/engine/
virtual_deps.rs
