formualizer_eval/engine/graph/
range_deps.rs

1use super::*;
2
3impl DependencyGraph {
4    /// Public wrapper to add range-dependent edges.
5    pub fn add_range_edges(
6        &mut self,
7        dependent: VertexId,
8        ranges: &[SharedRangeRef<'static>],
9        current_sheet_id: SheetId,
10    ) {
11        self.add_range_dependent_edges(dependent, ranges, current_sheet_id);
12    }
13
14    /// Return the compressed range dependencies recorded for a formula vertex, if any.
15    /// These are `SharedRangeRef` entries that were not expanded into explicit
16    /// cell edges due to `range_expansion_limit` or due to infinite/partial bounds.
17    pub fn get_range_dependencies(
18        &self,
19        vertex: VertexId,
20    ) -> Option<&Vec<SharedRangeRef<'static>>> {
21        self.formula_to_range_deps.get(&vertex)
22    }
23
24    #[cfg(test)]
25    pub(crate) fn formula_to_range_deps(
26        &self,
27    ) -> &FxHashMap<VertexId, Vec<SharedRangeRef<'static>>> {
28        &self.formula_to_range_deps
29    }
30
31    #[cfg(test)]
32    pub(crate) fn stripe_to_dependents(&self) -> &FxHashMap<StripeKey, FxHashSet<VertexId>> {
33        &self.stripe_to_dependents
34    }
35
36    pub(super) fn add_range_dependent_edges(
37        &mut self,
38        dependent: VertexId,
39        ranges: &[SharedRangeRef<'static>],
40        current_sheet_id: SheetId,
41    ) {
42        if ranges.is_empty() {
43            return;
44        }
45
46        self.formula_to_range_deps
47            .insert(dependent, ranges.to_vec());
48
49        for range in ranges {
50            let sheet_id = match range.sheet {
51                SharedSheetLocator::Id(id) => id,
52                _ => current_sheet_id,
53            };
54
55            let s_row = range.start_row.map(|b| b.index);
56            let e_row = range.end_row.map(|b| b.index);
57            let s_col = range.start_col.map(|b| b.index);
58            let e_col = range.end_col.map(|b| b.index);
59
60            let col_stripes = (s_row.is_none() && e_row.is_none())
61                || (s_col.is_some() && e_col.is_some() && (s_row.is_none() || e_row.is_none()));
62            let row_stripes = (s_col.is_none() && e_col.is_none())
63                || (s_row.is_some() && e_row.is_some() && (s_col.is_none() || e_col.is_none()));
64
65            if col_stripes && !row_stripes {
66                let sc = s_col.unwrap_or(0);
67                let ec = e_col.unwrap_or(sc);
68                for col in sc..=ec {
69                    let key = StripeKey {
70                        sheet_id,
71                        stripe_type: StripeType::Column,
72                        index: col,
73                    };
74                    self.stripe_to_dependents
75                        .entry(key.clone())
76                        .or_default()
77                        .insert(dependent);
78                    #[cfg(test)]
79                    {
80                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1) {
81                            self.instr.stripe_inserts += 1;
82                        }
83                    }
84                }
85                continue;
86            }
87
88            if row_stripes && !col_stripes {
89                let sr = s_row.unwrap_or(0);
90                let er = e_row.unwrap_or(sr);
91                for row in sr..=er {
92                    let key = StripeKey {
93                        sheet_id,
94                        stripe_type: StripeType::Row,
95                        index: row,
96                    };
97                    self.stripe_to_dependents
98                        .entry(key.clone())
99                        .or_default()
100                        .insert(dependent);
101                    #[cfg(test)]
102                    {
103                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1) {
104                            self.instr.stripe_inserts += 1;
105                        }
106                    }
107                }
108                continue;
109            }
110
111            let start_row = s_row.unwrap_or(0);
112            let start_col = s_col.unwrap_or(0);
113            let end_row = e_row.unwrap_or(start_row);
114            let end_col = e_col.unwrap_or(start_col);
115
116            let height = end_row.saturating_sub(start_row) + 1;
117            let width = end_col.saturating_sub(start_col) + 1;
118
119            if self.config.enable_block_stripes && height > 1 && width > 1 {
120                let start_block_row = start_row / BLOCK_H;
121                let end_block_row = end_row / BLOCK_H;
122                let start_block_col = start_col / BLOCK_W;
123                let end_block_col = end_col / BLOCK_W;
124
125                for block_row in start_block_row..=end_block_row {
126                    for block_col in start_block_col..=end_block_col {
127                        let key = StripeKey {
128                            sheet_id,
129                            stripe_type: StripeType::Block,
130                            index: block_index(block_row * BLOCK_H, block_col * BLOCK_W),
131                        };
132                        self.stripe_to_dependents
133                            .entry(key.clone())
134                            .or_default()
135                            .insert(dependent);
136                        #[cfg(test)]
137                        {
138                            if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1) {
139                                self.instr.stripe_inserts += 1;
140                            }
141                        }
142                    }
143                }
144            } else if height > width {
145                for col in start_col..=end_col {
146                    let key = StripeKey {
147                        sheet_id,
148                        stripe_type: StripeType::Column,
149                        index: col,
150                    };
151                    self.stripe_to_dependents
152                        .entry(key.clone())
153                        .or_default()
154                        .insert(dependent);
155                    #[cfg(test)]
156                    {
157                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1) {
158                            self.instr.stripe_inserts += 1;
159                        }
160                    }
161                }
162            } else {
163                for row in start_row..=end_row {
164                    let key = StripeKey {
165                        sheet_id,
166                        stripe_type: StripeType::Row,
167                        index: row,
168                    };
169                    self.stripe_to_dependents
170                        .entry(key.clone())
171                        .or_default()
172                        .insert(dependent);
173                    #[cfg(test)]
174                    {
175                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1) {
176                            self.instr.stripe_inserts += 1;
177                        }
178                    }
179                }
180            }
181        }
182    }
183
184    /// Fast-path: add range dependencies using compact RangeKey.
185    pub fn add_range_deps_from_keys(
186        &mut self,
187        dependent: VertexId,
188        keys: &[crate::engine::plan::RangeKey],
189        current_sheet_id: SheetId,
190    ) {
191        use crate::engine::plan::RangeKey as RK;
192        if keys.is_empty() {
193            return;
194        }
195
196        let mut shared_ranges: Vec<SharedRangeRef<'static>> = Vec::with_capacity(keys.len());
197        for k in keys {
198            let sheet_loc = SharedSheetLocator::Id(match k {
199                RK::Rect { sheet, .. }
200                | RK::WholeRow { sheet, .. }
201                | RK::WholeCol { sheet, .. }
202                | RK::OpenRect { sheet, .. } => *sheet,
203            });
204
205            let mk_axis = |idx0: u32| formualizer_common::AxisBound::new(idx0, false);
206
207            let built = match k {
208                RK::Rect { start, end, .. } => {
209                    let sr = mk_axis(start.row());
210                    let sc = mk_axis(start.col());
211                    let er = mk_axis(end.row());
212                    let ec = mk_axis(end.col());
213                    SharedRangeRef::from_parts(sheet_loc, Some(sr), Some(sc), Some(er), Some(ec))
214                        .ok()
215                }
216                RK::WholeRow { row, .. } => {
217                    let r0 = row.saturating_sub(1);
218                    let b = mk_axis(r0);
219                    SharedRangeRef::from_parts(sheet_loc, Some(b), None, Some(b), None).ok()
220                }
221                RK::WholeCol { col, .. } => {
222                    let c0 = col.saturating_sub(1);
223                    let b = mk_axis(c0);
224                    SharedRangeRef::from_parts(sheet_loc, None, Some(b), None, Some(b)).ok()
225                }
226                RK::OpenRect { start, end, .. } => {
227                    let (sr, sc) = match start {
228                        Some(p) => (Some(mk_axis(p.row())), Some(mk_axis(p.col()))),
229                        None => (None, None),
230                    };
231                    let (er, ec) = match end {
232                        Some(p) => (Some(mk_axis(p.row())), Some(mk_axis(p.col()))),
233                        None => (None, None),
234                    };
235                    SharedRangeRef::from_parts(sheet_loc, sr, sc, er, ec).ok()
236                }
237            };
238
239            if let Some(r) = built {
240                shared_ranges.push(r.into_owned());
241            }
242        }
243
244        if shared_ranges.is_empty() {
245            return;
246        }
247
248        self.formula_to_range_deps
249            .insert(dependent, shared_ranges.clone());
250
251        for range in &shared_ranges {
252            let sheet_id = match range.sheet {
253                SharedSheetLocator::Id(id) => id,
254                _ => current_sheet_id,
255            };
256
257            let s_row = range.start_row.map(|b| b.index);
258            let e_row = range.end_row.map(|b| b.index);
259            let s_col = range.start_col.map(|b| b.index);
260            let e_col = range.end_col.map(|b| b.index);
261
262            let col_stripes = (s_row.is_none() && e_row.is_none())
263                || (s_col.is_some() && e_col.is_some() && (s_row.is_none() || e_row.is_none()));
264            let row_stripes = (s_col.is_none() && e_col.is_none())
265                || (s_row.is_some() && e_row.is_some() && (s_col.is_none() || e_col.is_none()));
266
267            if col_stripes && !row_stripes {
268                let sc = s_col.unwrap_or(0);
269                let ec = e_col.unwrap_or(sc);
270                for col in sc..=ec {
271                    let key = StripeKey {
272                        sheet_id,
273                        stripe_type: StripeType::Column,
274                        index: col,
275                    };
276                    self.stripe_to_dependents
277                        .entry(key)
278                        .or_default()
279                        .insert(dependent);
280                }
281                continue;
282            }
283
284            if row_stripes && !col_stripes {
285                let sr = s_row.unwrap_or(0);
286                let er = e_row.unwrap_or(sr);
287                for row in sr..=er {
288                    let key = StripeKey {
289                        sheet_id,
290                        stripe_type: StripeType::Row,
291                        index: row,
292                    };
293                    self.stripe_to_dependents
294                        .entry(key)
295                        .or_default()
296                        .insert(dependent);
297                }
298                continue;
299            }
300
301            let start_row = s_row.unwrap_or(0);
302            let start_col = s_col.unwrap_or(0);
303            let end_row = e_row.unwrap_or(start_row);
304            let end_col = e_col.unwrap_or(start_col);
305
306            let height = end_row.saturating_sub(start_row) + 1;
307            let width = end_col.saturating_sub(start_col) + 1;
308
309            if self.config.enable_block_stripes && height > 1 && width > 1 {
310                let start_block_row = start_row / BLOCK_H;
311                let end_block_row = end_row / BLOCK_H;
312                let start_block_col = start_col / BLOCK_W;
313                let end_block_col = end_col / BLOCK_W;
314
315                for block_row in start_block_row..=end_block_row {
316                    for block_col in start_block_col..=end_block_col {
317                        let key = StripeKey {
318                            sheet_id,
319                            stripe_type: StripeType::Block,
320                            index: block_index(block_row * BLOCK_H, block_col * BLOCK_W),
321                        };
322                        self.stripe_to_dependents
323                            .entry(key)
324                            .or_default()
325                            .insert(dependent);
326                    }
327                }
328            } else if height > width {
329                for col in start_col..=end_col {
330                    let key = StripeKey {
331                        sheet_id,
332                        stripe_type: StripeType::Column,
333                        index: col,
334                    };
335                    self.stripe_to_dependents
336                        .entry(key)
337                        .or_default()
338                        .insert(dependent);
339                }
340            } else {
341                for row in start_row..=end_row {
342                    let key = StripeKey {
343                        sheet_id,
344                        stripe_type: StripeType::Row,
345                        index: row,
346                    };
347                    self.stripe_to_dependents
348                        .entry(key)
349                        .or_default()
350                        .insert(dependent);
351                }
352            }
353        }
354    }
355}
formualizer_eval/engine/graph/range_deps.rs

formualizer_eval/engine/graph/
range_deps.rs
