Skip to main content

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    /// True when a (possibly open-ended) range region on `sheet_id` covers
37    /// the formula vertex's own cell. Used to record a self-loop for
38    /// stripe-compressed / whole-axis self-inclusion (#120): such references
39    /// never produce explicit cell edges, so the ingest self-reference check
40    /// (which scans expanded cell deps) misses them. `None` bounds mean the
41    /// axis is unbounded (whole column/row), which always covers the cell.
42    fn range_region_contains_self(
43        &self,
44        dependent: VertexId,
45        sheet_id: SheetId,
46        s_row: Option<u32>,
47        e_row: Option<u32>,
48        s_col: Option<u32>,
49        e_col: Option<u32>,
50    ) -> bool {
51        if self.store.sheet_id(dependent) != sheet_id {
52            return false;
53        }
54        let coord = self.store.coord(dependent);
55        let r0 = coord.row();
56        let c0 = coord.col();
57        s_row.is_none_or(|s| r0 >= s)
58            && e_row.is_none_or(|e| r0 <= e)
59            && s_col.is_none_or(|s| c0 >= s)
60            && e_col.is_none_or(|e| c0 <= e)
61    }
62
63    /// Record a self-loop edge (vertex → itself). The edge store and Tarjan
64    /// both treat self-loops as cycles (`separate_cycles` via `has_self_loop`).
65    fn record_self_loop(&mut self, vertex: VertexId) {
66        if !self.has_self_loop(vertex) {
67            self.edges.add_edge(vertex, vertex);
68        }
69    }
70
71    pub(super) fn add_range_dependent_edges(
72        &mut self,
73        dependent: VertexId,
74        ranges: &[SharedRangeRef<'static>],
75        current_sheet_id: SheetId,
76    ) {
77        if ranges.is_empty() {
78            return;
79        }
80
81        self.formula_to_range_deps
82            .insert(dependent, ranges.to_vec());
83
84        for range in ranges {
85            let sheet_id = match range.sheet {
86                SharedSheetLocator::Id(id) => id,
87                _ => current_sheet_id,
88            };
89
90            let s_row = range.start_row.map(|b| b.index);
91            let e_row = range.end_row.map(|b| b.index);
92            let s_col = range.start_col.map(|b| b.index);
93            let e_col = range.end_col.map(|b| b.index);
94
95            // #120: a compressed range whose region covers this formula's own
96            // cell is a self-reference. Record a self-loop so SCC detection
97            // flags the cycle (the ingest self-ref check only sees expanded
98            // cell edges, which compressed ranges do not produce).
99            if self.range_region_contains_self(dependent, sheet_id, s_row, e_row, s_col, e_col) {
100                self.record_self_loop(dependent);
101            }
102
103            let col_stripes = (s_row.is_none() && e_row.is_none())
104                || (s_col.is_some() && e_col.is_some() && (s_row.is_none() || e_row.is_none()));
105            let row_stripes = (s_col.is_none() && e_col.is_none())
106                || (s_row.is_some() && e_row.is_some() && (s_col.is_none() || e_col.is_none()));
107
108            if col_stripes && !row_stripes {
109                let sc = s_col.unwrap_or(0);
110                let ec = e_col.unwrap_or(sc);
111                for col in sc..=ec {
112                    let key = StripeKey {
113                        sheet_id,
114                        stripe_type: StripeType::Column,
115                        index: col,
116                    };
117                    self.stripe_to_dependents
118                        .entry(key.clone())
119                        .or_default()
120                        .insert(dependent);
121                    #[cfg(test)]
122                    {
123                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
124                            && let Ok(mut g) = self.instr.lock()
125                        {
126                            g.stripe_inserts += 1;
127                        }
128                    }
129                }
130                continue;
131            }
132
133            if row_stripes && !col_stripes {
134                let sr = s_row.unwrap_or(0);
135                let er = e_row.unwrap_or(sr);
136                for row in sr..=er {
137                    let key = StripeKey {
138                        sheet_id,
139                        stripe_type: StripeType::Row,
140                        index: row,
141                    };
142                    self.stripe_to_dependents
143                        .entry(key.clone())
144                        .or_default()
145                        .insert(dependent);
146                    #[cfg(test)]
147                    {
148                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
149                            && let Ok(mut g) = self.instr.lock()
150                        {
151                            g.stripe_inserts += 1;
152                        }
153                    }
154                }
155                continue;
156            }
157
158            let start_row = s_row.unwrap_or(0);
159            let start_col = s_col.unwrap_or(0);
160            let end_row = e_row.unwrap_or(start_row);
161            let end_col = e_col.unwrap_or(start_col);
162
163            let height = end_row.saturating_sub(start_row) + 1;
164            let width = end_col.saturating_sub(start_col) + 1;
165
166            if self.config.enable_block_stripes && height > 1 && width > 1 {
167                let start_block_row = start_row / BLOCK_H;
168                let end_block_row = end_row / BLOCK_H;
169                let start_block_col = start_col / BLOCK_W;
170                let end_block_col = end_col / BLOCK_W;
171
172                for block_row in start_block_row..=end_block_row {
173                    for block_col in start_block_col..=end_block_col {
174                        let key = StripeKey {
175                            sheet_id,
176                            stripe_type: StripeType::Block,
177                            index: block_index(block_row * BLOCK_H, block_col * BLOCK_W),
178                        };
179                        self.stripe_to_dependents
180                            .entry(key.clone())
181                            .or_default()
182                            .insert(dependent);
183                        #[cfg(test)]
184                        {
185                            if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
186                                && let Ok(mut g) = self.instr.lock()
187                            {
188                                g.stripe_inserts += 1;
189                            }
190                        }
191                    }
192                }
193            } else if height > width {
194                for col in start_col..=end_col {
195                    let key = StripeKey {
196                        sheet_id,
197                        stripe_type: StripeType::Column,
198                        index: col,
199                    };
200                    self.stripe_to_dependents
201                        .entry(key.clone())
202                        .or_default()
203                        .insert(dependent);
204                    #[cfg(test)]
205                    {
206                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
207                            && let Ok(mut g) = self.instr.lock()
208                        {
209                            g.stripe_inserts += 1;
210                        }
211                    }
212                }
213            } else {
214                for row in start_row..=end_row {
215                    let key = StripeKey {
216                        sheet_id,
217                        stripe_type: StripeType::Row,
218                        index: row,
219                    };
220                    self.stripe_to_dependents
221                        .entry(key.clone())
222                        .or_default()
223                        .insert(dependent);
224                    #[cfg(test)]
225                    {
226                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
227                            && let Ok(mut g) = self.instr.lock()
228                        {
229                            g.stripe_inserts += 1;
230                        }
231                    }
232                }
233            }
234        }
235    }
236
237    /// Fast-path: add range dependencies using compact RangeKey.
238    pub fn add_range_deps_from_keys(
239        &mut self,
240        dependent: VertexId,
241        keys: &[crate::engine::plan::RangeKey],
242        current_sheet_id: SheetId,
243    ) {
244        use crate::engine::plan::RangeKey as RK;
245        if keys.is_empty() {
246            return;
247        }
248
249        let mut shared_ranges: Vec<SharedRangeRef<'static>> = Vec::with_capacity(keys.len());
250        for k in keys {
251            let sheet_loc = SharedSheetLocator::Id(match k {
252                RK::Rect { sheet, .. }
253                | RK::WholeRow { sheet, .. }
254                | RK::WholeCol { sheet, .. }
255                | RK::OpenRect { sheet, .. } => *sheet,
256            });
257
258            let mk_axis = |idx0: u32| formualizer_common::AxisBound::new(idx0, false);
259
260            let built = match k {
261                RK::Rect { start, end, .. } => {
262                    let sr = mk_axis(start.row());
263                    let sc = mk_axis(start.col());
264                    let er = mk_axis(end.row());
265                    let ec = mk_axis(end.col());
266                    SharedRangeRef::from_parts(sheet_loc, Some(sr), Some(sc), Some(er), Some(ec))
267                        .ok()
268                }
269                RK::WholeRow { row, .. } => {
270                    let r0 = row.saturating_sub(1);
271                    let b = mk_axis(r0);
272                    SharedRangeRef::from_parts(sheet_loc, Some(b), None, Some(b), None).ok()
273                }
274                RK::WholeCol { col, .. } => {
275                    let c0 = col.saturating_sub(1);
276                    let b = mk_axis(c0);
277                    SharedRangeRef::from_parts(sheet_loc, None, Some(b), None, Some(b)).ok()
278                }
279                RK::OpenRect { start, end, .. } => {
280                    let (sr, sc) = match start {
281                        Some(p) => (Some(mk_axis(p.row())), Some(mk_axis(p.col()))),
282                        None => (None, None),
283                    };
284                    let (er, ec) = match end {
285                        Some(p) => (Some(mk_axis(p.row())), Some(mk_axis(p.col()))),
286                        None => (None, None),
287                    };
288                    SharedRangeRef::from_parts(sheet_loc, sr, sc, er, ec).ok()
289                }
290            };
291
292            if let Some(r) = built {
293                shared_ranges.push(r.into_owned());
294            }
295        }
296
297        if shared_ranges.is_empty() {
298            return;
299        }
300
301        self.formula_to_range_deps
302            .insert(dependent, shared_ranges.clone());
303
304        for range in &shared_ranges {
305            let sheet_id = match range.sheet {
306                SharedSheetLocator::Id(id) => id,
307                _ => current_sheet_id,
308            };
309
310            let s_row = range.start_row.map(|b| b.index);
311            let e_row = range.end_row.map(|b| b.index);
312            let s_col = range.start_col.map(|b| b.index);
313            let e_col = range.end_col.map(|b| b.index);
314
315            // #120: see add_range_dependent_edges — compressed range covering
316            // the formula's own cell records a self-loop for SCC detection.
317            if self.range_region_contains_self(dependent, sheet_id, s_row, e_row, s_col, e_col) {
318                self.record_self_loop(dependent);
319            }
320
321            let col_stripes = (s_row.is_none() && e_row.is_none())
322                || (s_col.is_some() && e_col.is_some() && (s_row.is_none() || e_row.is_none()));
323            let row_stripes = (s_col.is_none() && e_col.is_none())
324                || (s_row.is_some() && e_row.is_some() && (s_col.is_none() || e_col.is_none()));
325
326            if col_stripes && !row_stripes {
327                let sc = s_col.unwrap_or(0);
328                let ec = e_col.unwrap_or(sc);
329                for col in sc..=ec {
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                continue;
341            }
342
343            if row_stripes && !col_stripes {
344                let sr = s_row.unwrap_or(0);
345                let er = e_row.unwrap_or(sr);
346                for row in sr..=er {
347                    let key = StripeKey {
348                        sheet_id,
349                        stripe_type: StripeType::Row,
350                        index: row,
351                    };
352                    self.stripe_to_dependents
353                        .entry(key)
354                        .or_default()
355                        .insert(dependent);
356                }
357                continue;
358            }
359
360            let start_row = s_row.unwrap_or(0);
361            let start_col = s_col.unwrap_or(0);
362            let end_row = e_row.unwrap_or(start_row);
363            let end_col = e_col.unwrap_or(start_col);
364
365            let height = end_row.saturating_sub(start_row) + 1;
366            let width = end_col.saturating_sub(start_col) + 1;
367
368            if self.config.enable_block_stripes && height > 1 && width > 1 {
369                let start_block_row = start_row / BLOCK_H;
370                let end_block_row = end_row / BLOCK_H;
371                let start_block_col = start_col / BLOCK_W;
372                let end_block_col = end_col / BLOCK_W;
373
374                for block_row in start_block_row..=end_block_row {
375                    for block_col in start_block_col..=end_block_col {
376                        let key = StripeKey {
377                            sheet_id,
378                            stripe_type: StripeType::Block,
379                            index: block_index(block_row * BLOCK_H, block_col * BLOCK_W),
380                        };
381                        self.stripe_to_dependents
382                            .entry(key)
383                            .or_default()
384                            .insert(dependent);
385                    }
386                }
387            } else if height > width {
388                for col in start_col..=end_col {
389                    let key = StripeKey {
390                        sheet_id,
391                        stripe_type: StripeType::Column,
392                        index: col,
393                    };
394                    self.stripe_to_dependents
395                        .entry(key)
396                        .or_default()
397                        .insert(dependent);
398                }
399            } else {
400                for row in start_row..=end_row {
401                    let key = StripeKey {
402                        sheet_id,
403                        stripe_type: StripeType::Row,
404                        index: row,
405                    };
406                    self.stripe_to_dependents
407                        .entry(key)
408                        .or_default()
409                        .insert(dependent);
410                }
411            }
412        }
413    }
414}