formualizer_eval/engine/
target_preparation.rs

1use std::collections::{BTreeMap, BTreeSet};
2use std::time::{Duration, Instant};
3
4use formualizer_common::RangeAddress;
5
6use super::{EvaluationBudgets, VertexId};
7use crate::formula_plane::region_index::Region;
8use crate::formula_plane::runtime::FormulaSpanRef;
9use crate::reference::CellRef;
10
11pub type RequestId = u64;
12
13#[cfg(test)]
14#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
15pub(crate) enum TargetPreparationFault {
16    #[default]
17    None,
18    AfterDiscovery,
19    FinalRevisionValidation,
20    FinalGraphValidation,
21    Admission,
22    Reservation,
23    BeforeFirstMutation,
24}
25
26#[derive(Clone, Debug, PartialEq, Eq, Hash)]
27pub enum EvaluationTarget {
28    Cell {
29        sheet: String,
30        row: u32,
31        col: u32,
32    },
33    Range(RangeAddress),
34    Name {
35        name: String,
36        scope_sheet: Option<String>,
37    },
38    Table {
39        name: String,
40        selection: TableSelection,
41    },
42}
43
44#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
45pub(crate) enum TargetProducer {
46    Legacy(VertexId),
47    Span {
48        span_ref: FormulaSpanRef,
49        demanded: Region,
50    },
51    Symbol(VertexId),
52    ValueOnly(CellRef),
53}
54
55#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
56pub enum TableSelection {
57    #[default]
58    Whole,
59    Headers,
60    Data,
61    Totals,
62    Column(String),
63    Columns {
64        start: String,
65        end: String,
66    },
67}
68
69#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
70pub enum OpaquePreparePolicy {
71    #[default]
72    Widen,
73    Error,
74}
75
76#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
77#[non_exhaustive]
78pub enum PrepareScope {
79    #[default]
80    Exact,
81    Sheets(Vec<String>),
82    Workbook,
83}
84
85#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
86#[non_exhaustive]
87pub enum OpaqueReason {
88    DynamicReference,
89    RuntimeTextReference,
90    UnknownFunction,
91    UnknownCustomFunction,
92    UnresolvedCrossSheetBinding,
93    UnresolvedName,
94    UnresolvedTable,
95    FormulaName,
96    DeferredSourcePackage,
97    UnsupportedSourceSemantics,
98    UncertainDefaultSheetBinding,
99}
100
101/// Controls that apply to a whole target evaluation: preparation *and*
102/// evaluation. Cancellation and the deadline are hoisted onto the engine for the
103/// duration of the call, so every checkpoint in both phases observes them.
104#[derive(Clone, Debug)]
105pub struct TargetEvalOptions<'a> {
106    pub request_id: Option<RequestId>,
107    pub cancel: Option<crate::engine::CancelToken>,
108    pub deadline: Option<Instant>,
109    pub budgets: Option<&'a EvaluationBudgets>,
110    pub opaque_policy: OpaquePreparePolicy,
111}
112
113impl Default for TargetEvalOptions<'_> {
114    fn default() -> Self {
115        Self {
116            request_id: None,
117            cancel: None,
118            deadline: None,
119            budgets: None,
120            opaque_policy: OpaquePreparePolicy::Widen,
121        }
122    }
123}
124
125#[derive(Clone, Debug, Default, PartialEq, Eq)]
126#[non_exhaustive]
127pub struct PreparationRevision {
128    pub graph: u64,
129    /// Raw FormulaPlane epoch. Kept separate from each authority-index counter so
130    /// unrelated component revisions cannot collide through arithmetic folding.
131    pub authority: u64,
132    pub authority_indexes: u64,
133    pub authority_indexed_plane: u64,
134    pub staged: u64,
135    pub symbols: u64,
136    pub semantic: u64,
137    pub provider: Option<u64>,
138}
139
140#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
141#[non_exhaustive]
142pub enum PreparationOutcome {
143    #[default]
144    Prepared,
145    CompatibilityPrepared,
146}
147
148#[derive(Clone, Debug, Default, PartialEq, Eq)]
149#[non_exhaustive]
150pub struct PreparedTargetGraphReport {
151    pub request_id: RequestId,
152    pub requested_targets: usize,
153    pub normalized_regions: usize,
154    pub normalized_target_list: Vec<EvaluationTarget>,
155    pub selected_staged_cells: usize,
156    /// Total family proposals owned by the whole deferred packages selected by
157    /// this request. Selection and consumption are package-atomic.
158    pub selected_source_families: usize,
159    pub retained_staged_cells: usize,
160    pub selected_cells: Vec<RangeAddress>,
161    pub retained_cells: Vec<RangeAddress>,
162    pub widened_scope: PrepareScope,
163    pub widening_reasons: Vec<OpaqueReason>,
164    pub revisions: PreparationRevision,
165    pub commit_window: Duration,
166    pub estimated_scratch_bytes: u64,
167    pub observed_scratch_bytes: u64,
168    pub estimated_commit_work: u64,
169    pub actual_commit_work: u64,
170    pub outcome: PreparationOutcome,
171}
172
173#[derive(Clone, Copy, Debug, PartialEq, Eq)]
174pub(crate) struct StagedFormulaLease {
175    pub(crate) row: u32,
176    pub(crate) col: u32,
177    pub(crate) generation: u64,
178    pub(crate) insertion_order: u64,
179}
180
181#[derive(Clone, Copy, Debug, PartialEq, Eq)]
182struct StagedFormulaPresence {
183    generation: u64,
184    insertion_order: u64,
185}
186
187#[derive(Clone, Copy, Debug, PartialEq, Eq)]
188pub(crate) struct StagedPackageLease {
189    pub(crate) generation: u64,
190    pub(crate) family_count: usize,
191}
192
193#[derive(Clone, Copy, Debug, PartialEq, Eq)]
194struct StagedPackageRect {
195    start_row: u32,
196    start_col: u32,
197    end_row: u32,
198    end_col: u32,
199}
200
201impl StagedPackageRect {
202    fn intersects(self, start_row: u32, start_col: u32, end_row: u32, end_col: u32) -> bool {
203        self.start_row <= end_row
204            && start_row <= self.end_row
205            && self.start_col <= end_col
206            && start_col <= self.end_col
207    }
208}
209
210#[derive(Clone, Debug)]
211struct StagedPackagePresence {
212    generation: u64,
213    family_count: usize,
214    geometry: Vec<StagedPackageRect>,
215    fallback_points: BTreeSet<(u32, u32)>,
216    geometry_complete: bool,
217}
218
219#[derive(Clone, Debug, Default)]
220pub(crate) struct StagedFormulaIndex {
221    revision: u64,
222    next_generation: u64,
223    next_insertion_order: u64,
224    sheets: BTreeMap<String, BTreeMap<(u32, u32), StagedFormulaPresence>>,
225    packages: BTreeMap<String, StagedPackagePresence>,
226}
227
228impl StagedFormulaIndex {
229    fn bump(&mut self) {
230        self.revision = self
231            .revision
232            .checked_add(1)
233            .expect("staged formula index revision exhausted");
234    }
235
236    pub(crate) fn revision(&self) -> u64 {
237        self.revision
238    }
239
240    pub(crate) fn stage(&mut self, sheet: &str, row: u32, col: u32) {
241        let generation = self.next_generation;
242        self.next_generation = self
243            .next_generation
244            .checked_add(1)
245            .expect("staged formula generation exhausted");
246        let entries = self.sheets.entry(sheet.to_string()).or_default();
247        let insertion_order = entries.get(&(row, col)).map_or_else(
248            || {
249                let order = self.next_insertion_order;
250                self.next_insertion_order = self
251                    .next_insertion_order
252                    .checked_add(1)
253                    .expect("staged formula insertion order exhausted");
254                order
255            },
256            |entry| entry.insertion_order,
257        );
258        entries.insert(
259            (row, col),
260            StagedFormulaPresence {
261                generation,
262                insertion_order,
263            },
264        );
265        self.bump();
266    }
267
268    pub(crate) fn remove(&mut self, sheet: &str, row: u32, col: u32) -> bool {
269        let removed = self
270            .sheets
271            .get_mut(sheet)
272            .is_some_and(|entries| entries.remove(&(row, col)).is_some());
273        if self.sheets.get(sheet).is_some_and(BTreeMap::is_empty) {
274            self.sheets.remove(sheet);
275        }
276        if removed {
277            self.bump();
278        }
279        removed
280    }
281
282    pub(crate) fn clear_sheet(&mut self, sheet: &str) {
283        let changed = self.sheets.remove(sheet).is_some() | self.packages.remove(sheet).is_some();
284        if changed {
285            self.bump();
286        }
287    }
288
289    pub(crate) fn clear_all(&mut self) {
290        if !self.sheets.is_empty() || !self.packages.is_empty() {
291            self.sheets.clear();
292            self.packages.clear();
293            self.bump();
294        }
295    }
296
297    pub(crate) fn set_package(
298        &mut self,
299        sheet: &str,
300        package: Option<&super::DeferredFormulaPackage>,
301    ) {
302        let changed = if let Some(package) = package {
303            let generation = self.next_generation;
304            self.next_generation = self
305                .next_generation
306                .checked_add(1)
307                .expect("staged package generation exhausted");
308            let mut geometry = Vec::new();
309            for family in &package.families {
310                match &family.members {
311                    super::SourceFamilyMembers::CompleteDomain(domain) => {
312                        let rect = domain.rect();
313                        geometry.push(StagedPackageRect {
314                            start_row: rect.start.row.saturating_add(1),
315                            start_col: rect.start.col.saturating_add(1),
316                            end_row: rect.end.row.saturating_add(1),
317                            end_col: rect.end.col.saturating_add(1),
318                        });
319                    }
320                    super::SourceFamilyMembers::ExplicitMembers(members) => {
321                        geometry.extend(members.as_slice().iter().map(|coord| StagedPackageRect {
322                            start_row: coord.row.saturating_add(1),
323                            start_col: coord.col.saturating_add(1),
324                            end_row: coord.row.saturating_add(1),
325                            end_col: coord.col.saturating_add(1),
326                        }));
327                    }
328                }
329            }
330            geometry.extend(
331                package
332                    .partitioned_families
333                    .iter()
334                    .map(|family| StagedPackageRect {
335                        start_row: family.declared.start.row.saturating_add(1),
336                        start_col: family.declared.start.col.saturating_add(1),
337                        end_row: family.declared.end.row.saturating_add(1),
338                        end_col: family.declared.end.col.saturating_add(1),
339                    }),
340            );
341            let fallback_points = package
342                .source_coordinates
343                .iter()
344                .map(|coord| (coord.row.saturating_add(1), coord.col.saturating_add(1)))
345                .collect();
346            let geometry_complete = package.source_geometry_complete
347                || package.report.source_formula_records_spooled == 0;
348            self.packages.insert(
349                sheet.to_string(),
350                StagedPackagePresence {
351                    generation,
352                    family_count: package.families.len() + package.partitioned_families.len(),
353                    geometry,
354                    fallback_points,
355                    geometry_complete,
356                },
357            );
358            true
359        } else {
360            self.packages.remove(sheet).is_some()
361        };
362        if changed {
363            self.bump();
364        }
365    }
366
367    pub(crate) fn touch_package(&mut self, sheet: &str) {
368        if let Some(package) = self.packages.get_mut(sheet) {
369            package.generation = self.next_generation;
370            self.next_generation = self
371                .next_generation
372                .checked_add(1)
373                .expect("staged package generation exhausted");
374            self.bump();
375        }
376    }
377
378    pub(crate) fn has_packages(&self) -> bool {
379        !self.packages.is_empty()
380    }
381
382    pub(crate) fn package_sheets(&self) -> impl Iterator<Item = &str> {
383        self.packages.keys().map(String::as_str)
384    }
385
386    pub(crate) fn package_for_region(
387        &self,
388        sheet: &str,
389        start_row: u32,
390        start_col: u32,
391        end_row: u32,
392        end_col: u32,
393    ) -> Option<Result<StagedPackageLease, ()>> {
394        let package = self.packages.get(sheet)?;
395        let intersects = package
396            .geometry
397            .iter()
398            .copied()
399            .any(|rect| rect.intersects(start_row, start_col, end_row, end_col))
400            || package
401                .fallback_points
402                .range((start_row, 0)..=(end_row, u32::MAX))
403                .any(|&(row, col)| col >= start_col && col <= end_col);
404        if intersects {
405            Some(Ok(StagedPackageLease {
406                generation: package.generation,
407                family_count: package.family_count,
408            }))
409        } else if package.geometry_complete {
410            None
411        } else {
412            Some(Err(()))
413        }
414    }
415
416    pub(crate) fn package_lease_for_sheet(&self, sheet: &str) -> Option<StagedPackageLease> {
417        self.packages.get(sheet).map(|package| StagedPackageLease {
418            generation: package.generation,
419            family_count: package.family_count,
420        })
421    }
422
423    pub(crate) fn package_lease_matches(&self, sheet: &str, lease: StagedPackageLease) -> bool {
424        self.packages.get(sheet).is_some_and(|package| {
425            package.generation == lease.generation && package.family_count == lease.family_count
426        })
427    }
428
429    pub(crate) fn leases_in_region(
430        &self,
431        sheet: &str,
432        start_row: u32,
433        start_col: u32,
434        end_row: u32,
435        end_col: u32,
436    ) -> Vec<StagedFormulaLease> {
437        let mut leases = self
438            .sheets
439            .get(sheet)
440            .into_iter()
441            .flat_map(|entries| entries.range((start_row, 0)..=(end_row, u32::MAX)))
442            .filter_map(|(&(row, col), entry)| {
443                (col >= start_col && col <= end_col).then_some(StagedFormulaLease {
444                    row,
445                    col,
446                    generation: entry.generation,
447                    insertion_order: entry.insertion_order,
448                })
449            })
450            .collect::<Vec<_>>();
451        leases.sort_by_key(|lease| lease.insertion_order);
452        leases
453    }
454
455    pub(crate) fn leases_for_sheet(&self, sheet: &str) -> Vec<StagedFormulaLease> {
456        self.leases_in_region(sheet, 1, 1, u32::MAX, u32::MAX)
457    }
458
459    pub(crate) fn all_leases(&self) -> Vec<(String, StagedFormulaLease)> {
460        let mut leases = self
461            .sheets
462            .iter()
463            .flat_map(|(sheet, entries)| {
464                entries.iter().map(move |(&(row, col), entry)| {
465                    (
466                        sheet.clone(),
467                        StagedFormulaLease {
468                            row,
469                            col,
470                            generation: entry.generation,
471                            insertion_order: entry.insertion_order,
472                        },
473                    )
474                })
475            })
476            .collect::<Vec<_>>();
477        leases.sort_by_key(|(_, lease)| lease.insertion_order);
478        leases
479    }
480
481    pub(crate) fn lease_matches(&self, sheet: &str, lease: StagedFormulaLease) -> bool {
482        self.sheets
483            .get(sheet)
484            .and_then(|entries| entries.get(&(lease.row, lease.col)))
485            .is_some_and(|entry| {
486                entry.generation == lease.generation
487                    && entry.insertion_order == lease.insertion_order
488            })
489    }
490
491    pub(crate) fn ordinary_count(&self) -> usize {
492        self.sheets.values().map(BTreeMap::len).sum()
493    }
494
495    #[cfg(test)]
496    pub(crate) fn package_count(&self) -> usize {
497        self.packages.len()
498    }
499}
500
501/// Former name of [`TargetEvalOptions`]. The struct governs the whole call, not
502/// only preparation, so it was renamed before the name was frozen by a release.
503#[deprecated(since = "0.8.0", note = "renamed to TargetEvalOptions")]
504pub type PrepareTargetsOptions<'a> = TargetEvalOptions<'a>;
formualizer_eval/engine/target_preparation.rs

formualizer_eval/engine/
target_preparation.rs
