formualizer_eval/engine/
plan.rs

1use crate::SheetId;
2use crate::engine::sheet_registry::SheetRegistry;
3use formualizer_common::Coord as AbsCoord;
4use formualizer_common::CoordBuildHasher;
5use formualizer_common::ExcelError;
6use formualizer_common::PackedSheetCell;
7use formualizer_parse::parser::{CollectPolicy, ReferenceType};
8use std::collections::HashMap;
9
10/// Compact range descriptor used during planning (engine-only)
11#[derive(Debug, Clone, PartialEq, Eq, Hash)]
12pub enum RangeKey {
13    Rect {
14        sheet: SheetId,
15        start: AbsCoord,
16        end: AbsCoord, // inclusive
17    },
18    WholeRow {
19        sheet: SheetId,
20        row: u32,
21    },
22    WholeCol {
23        sheet: SheetId,
24        col: u32,
25    },
26    /// Partially bounded rectangle; None means unbounded in that direction
27    OpenRect {
28        sheet: SheetId,
29        start: Option<AbsCoord>,
30        end: Option<AbsCoord>,
31    },
32}
33
34/// Bitflags conveying per-formula traits
35pub type FormulaFlags = u8;
36pub const F_VOLATILE: FormulaFlags = 0b0000_0001;
37pub const F_HAS_RANGES: FormulaFlags = 0b0000_0010;
38pub const F_HAS_NAMES: FormulaFlags = 0b0000_0100;
39pub const F_HAS_TABLES: FormulaFlags = 0b0001_0000;
40pub const F_LIKELY_ARRAY: FormulaFlags = 0b0000_1000;
41
42#[derive(Debug, Default, Clone)]
43pub struct DependencyPlan {
44    pub formula_targets: Vec<(SheetId, AbsCoord)>,
45    pub global_cells: Vec<(SheetId, AbsCoord)>,
46    pub vertex_pool: Vec<(SheetId, AbsCoord)>,
47    pub vertex_pool_packed: Vec<PackedSheetCell>,
48    pub formula_target_pool_indices: Vec<u32>,
49    pub global_cell_pool_indices: Vec<u32>,
50    pub per_formula_cells: Vec<Vec<u32>>, // indices into global_cells
51    pub per_formula_ranges: Vec<Vec<RangeKey>>,
52    pub per_formula_names: Vec<Vec<String>>,
53    pub per_formula_tables: Vec<Vec<String>>,
54    pub per_formula_flags: Vec<FormulaFlags>,
55    pub edges_flat: Option<Vec<u32>>, // optional flat adjacency (indices into global_cells)
56    pub offsets: Option<Vec<u32>>,    // len = num_formulas + 1 when edges_flat is Some
57}
58
59/// Build a compact dependency plan from ASTs without mutating the graph.
60/// Sheets referenced by name are resolved/created through SheetRegistry at plan time.
61pub fn build_dependency_plan<'a, I>(
62    sheet_reg: &mut SheetRegistry,
63    formulas: I,
64    policy: &CollectPolicy,
65    volatile_flags: Option<&[bool]>,
66) -> Result<DependencyPlan, ExcelError>
67where
68    I: Iterator<Item = (&'a str, u32, u32, &'a formualizer_parse::parser::ASTNode)>,
69{
70    let mut plan = DependencyPlan::default();
71
72    // Global cell pool: packed absolute cell -> index.
73    //
74    // Uses CoordBuildHasher because FxHasher's weak avalanche collides badly
75    // on structured packed keys (PackedSheetCell reserves bits 50..64 and has
76    // narrow dynamic range on row-major workloads), turning this O(N) loop
77    // into O(N^2). See formualizer_common::coord_hash.
78    let mut cell_index: HashMap<PackedSheetCell, u32, CoordBuildHasher> =
79        HashMap::with_hasher(CoordBuildHasher);
80    // Unified vertex pool for loader-specialized ensure.
81    let mut vertex_pool_index: HashMap<PackedSheetCell, u32, CoordBuildHasher> =
82        HashMap::with_hasher(CoordBuildHasher);
83
84    let mut ensure_vertex_pool_index =
85        |plan: &mut DependencyPlan, key: (SheetId, AbsCoord)| -> u32 {
86            let packed = PackedSheetCell::try_new(key.0, key.1.row(), key.1.col())
87                .expect("plan vertex pool coordinate must fit PackedSheetCell");
88            match vertex_pool_index.get(&packed) {
89                Some(&idx) => idx,
90                None => {
91                    let new_idx = plan.vertex_pool.len() as u32;
92                    plan.vertex_pool.push(key);
93                    plan.vertex_pool_packed.push(packed);
94                    vertex_pool_index.insert(packed, new_idx);
95                    new_idx
96                }
97            }
98        };
99
100    for (i, (sheet_name, row, col, ast)) in formulas.enumerate() {
101        let sheet_id = sheet_reg.id_for(sheet_name);
102        let target = (sheet_id, AbsCoord::from_excel(row, col));
103        plan.formula_targets.push(target);
104        let target_pool_idx = ensure_vertex_pool_index(&mut plan, target);
105        plan.formula_target_pool_indices.push(target_pool_idx);
106
107        let mut flags: FormulaFlags = 0;
108        if let Some(v) = volatile_flags.and_then(|v| v.get(i)).copied()
109            && v
110        {
111            flags |= F_VOLATILE;
112        }
113
114        let mut per_cells: Vec<u32> = Vec::new();
115        let mut per_ranges: Vec<RangeKey> = Vec::new();
116        let mut per_names: Vec<String> = Vec::new();
117        let mut per_tables: Vec<String> = Vec::new();
118
119        // Collect references using core collector (may expand small ranges per policy)
120        let refs = ast.collect_references(policy);
121        for r in refs {
122            match r {
123                ReferenceType::Cell {
124                    sheet, row, col, ..
125                } => {
126                    let dep_sheet = sheet
127                        .as_deref()
128                        .map(|name| sheet_reg.id_for(name))
129                        .unwrap_or(sheet_id);
130                    let key = (dep_sheet, AbsCoord::from_excel(row, col));
131                    let packed = PackedSheetCell::try_new(dep_sheet, key.1.row(), key.1.col())
132                        .expect("plan dependency coordinate must fit PackedSheetCell");
133                    let idx = match cell_index.get(&packed) {
134                        Some(&idx) => idx,
135                        None => {
136                            let new_idx = plan.global_cells.len() as u32;
137                            plan.global_cells.push(key);
138                            cell_index.insert(packed, new_idx);
139                            let pool_idx = ensure_vertex_pool_index(&mut plan, key);
140                            plan.global_cell_pool_indices.push(pool_idx);
141                            new_idx
142                        }
143                    };
144                    per_cells.push(idx);
145                }
146                ReferenceType::Range {
147                    sheet,
148                    start_row,
149                    start_col,
150                    end_row,
151                    end_col,
152                    ..
153                } => {
154                    let dep_sheet = sheet
155                        .as_deref()
156                        .map(|name| sheet_reg.id_for(name))
157                        .unwrap_or(sheet_id);
158                    match (start_row, start_col, end_row, end_col) {
159                        (Some(sr), Some(sc), Some(er), Some(ec)) => {
160                            per_ranges.push(RangeKey::Rect {
161                                sheet: dep_sheet,
162                                start: AbsCoord::from_excel(sr, sc),
163                                end: AbsCoord::from_excel(er, ec),
164                            })
165                        }
166                        (None, Some(c), None, Some(ec)) if c == ec => {
167                            per_ranges.push(RangeKey::WholeCol {
168                                sheet: dep_sheet,
169                                col: c,
170                            })
171                        }
172                        (Some(r), None, Some(er), None) if r == er => {
173                            per_ranges.push(RangeKey::WholeRow {
174                                sheet: dep_sheet,
175                                row: r,
176                            })
177                        }
178                        _ => per_ranges.push(RangeKey::OpenRect {
179                            sheet: dep_sheet,
180                            start: start_row
181                                .zip(start_col)
182                                .map(|(r, c)| AbsCoord::from_excel(r, c)),
183                            end: end_row
184                                .zip(end_col)
185                                .map(|(r, c)| AbsCoord::from_excel(r, c)),
186                        }),
187                    }
188                }
189                ReferenceType::External(ext) => match ext.kind {
190                    formualizer_parse::parser::ExternalRefKind::Cell { .. } => {
191                        flags |= F_HAS_NAMES;
192                        per_names.push(ext.raw.clone());
193                    }
194                    formualizer_parse::parser::ExternalRefKind::Range { .. } => {
195                        flags |= F_HAS_TABLES;
196                        per_tables.push(ext.raw.clone());
197                    }
198                },
199                ReferenceType::NamedRange(name) => {
200                    // Resolution handled later; mark via flags if caller cares
201                    flags |= F_HAS_NAMES;
202                    per_names.push(name);
203                }
204                ReferenceType::Table(tref) => {
205                    flags |= F_HAS_TABLES;
206                    per_tables.push(tref.name);
207                }
208                // 3D refs are parsed but not yet planned. They neither create
209                // dependencies nor participate in the cell/range plan; the
210                // evaluator will surface #N/IMPL! when one is encountered.
211                ReferenceType::Cell3D { .. } | ReferenceType::Range3D { .. } => {}
212            }
213        }
214
215        plan.per_formula_cells.push(per_cells);
216        plan.per_formula_ranges.push(per_ranges);
217        plan.per_formula_names.push(per_names);
218        plan.per_formula_tables.push(per_tables);
219        plan.per_formula_flags.push(flags);
220    }
221
222    Ok(plan)
223}
formualizer_eval/engine/plan.rs

formualizer_eval/engine/
plan.rs
