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    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                            && let Ok(mut g) = self.instr.lock()
82                        {
83                            g.stripe_inserts += 1;
84                        }
85                    }
86                }
87                continue;
88            }
89
90            if row_stripes && !col_stripes {
91                let sr = s_row.unwrap_or(0);
92                let er = e_row.unwrap_or(sr);
93                for row in sr..=er {
94                    let key = StripeKey {
95                        sheet_id,
96                        stripe_type: StripeType::Row,
97                        index: row,
98                    };
99                    self.stripe_to_dependents
100                        .entry(key.clone())
101                        .or_default()
102                        .insert(dependent);
103                    #[cfg(test)]
104                    {
105                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
106                            && let Ok(mut g) = self.instr.lock()
107                        {
108                            g.stripe_inserts += 1;
109                        }
110                    }
111                }
112                continue;
113            }
114
115            let start_row = s_row.unwrap_or(0);
116            let start_col = s_col.unwrap_or(0);
117            let end_row = e_row.unwrap_or(start_row);
118            let end_col = e_col.unwrap_or(start_col);
119
120            let height = end_row.saturating_sub(start_row) + 1;
121            let width = end_col.saturating_sub(start_col) + 1;
122
123            if self.config.enable_block_stripes && height > 1 && width > 1 {
124                let start_block_row = start_row / BLOCK_H;
125                let end_block_row = end_row / BLOCK_H;
126                let start_block_col = start_col / BLOCK_W;
127                let end_block_col = end_col / BLOCK_W;
128
129                for block_row in start_block_row..=end_block_row {
130                    for block_col in start_block_col..=end_block_col {
131                        let key = StripeKey {
132                            sheet_id,
133                            stripe_type: StripeType::Block,
134                            index: block_index(block_row * BLOCK_H, block_col * BLOCK_W),
135                        };
136                        self.stripe_to_dependents
137                            .entry(key.clone())
138                            .or_default()
139                            .insert(dependent);
140                        #[cfg(test)]
141                        {
142                            if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
143                                && let Ok(mut g) = self.instr.lock()
144                            {
145                                g.stripe_inserts += 1;
146                            }
147                        }
148                    }
149                }
150            } else if height > width {
151                for col in start_col..=end_col {
152                    let key = StripeKey {
153                        sheet_id,
154                        stripe_type: StripeType::Column,
155                        index: col,
156                    };
157                    self.stripe_to_dependents
158                        .entry(key.clone())
159                        .or_default()
160                        .insert(dependent);
161                    #[cfg(test)]
162                    {
163                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
164                            && let Ok(mut g) = self.instr.lock()
165                        {
166                            g.stripe_inserts += 1;
167                        }
168                    }
169                }
170            } else {
171                for row in start_row..=end_row {
172                    let key = StripeKey {
173                        sheet_id,
174                        stripe_type: StripeType::Row,
175                        index: row,
176                    };
177                    self.stripe_to_dependents
178                        .entry(key.clone())
179                        .or_default()
180                        .insert(dependent);
181                    #[cfg(test)]
182                    {
183                        if self.stripe_to_dependents.get(&key).map(|s| s.len()) == Some(1)
184                            && let Ok(mut g) = self.instr.lock()
185                        {
186                            g.stripe_inserts += 1;
187                        }
188                    }
189                }
190            }
191        }
192    }
193
194    /// Fast-path: add range dependencies using compact RangeKey.
195    pub fn add_range_deps_from_keys(
196        &mut self,
197        dependent: VertexId,
198        keys: &[crate::engine::plan::RangeKey],
199        current_sheet_id: SheetId,
200    ) {
201        use crate::engine::plan::RangeKey as RK;
202        if keys.is_empty() {
203            return;
204        }
205
206        let mut shared_ranges: Vec<SharedRangeRef<'static>> = Vec::with_capacity(keys.len());
207        for k in keys {
208            let sheet_loc = SharedSheetLocator::Id(match k {
209                RK::Rect { sheet, .. }
210                | RK::WholeRow { sheet, .. }
211                | RK::WholeCol { sheet, .. }
212                | RK::OpenRect { sheet, .. } => *sheet,
213            });
214
215            let mk_axis = |idx0: u32| formualizer_common::AxisBound::new(idx0, false);
216
217            let built = match k {
218                RK::Rect { start, end, .. } => {
219                    let sr = mk_axis(start.row());
220                    let sc = mk_axis(start.col());
221                    let er = mk_axis(end.row());
222                    let ec = mk_axis(end.col());
223                    SharedRangeRef::from_parts(sheet_loc, Some(sr), Some(sc), Some(er), Some(ec))
224                        .ok()
225                }
226                RK::WholeRow { row, .. } => {
227                    let r0 = row.saturating_sub(1);
228                    let b = mk_axis(r0);
229                    SharedRangeRef::from_parts(sheet_loc, Some(b), None, Some(b), None).ok()
230                }
231                RK::WholeCol { col, .. } => {
232                    let c0 = col.saturating_sub(1);
233                    let b = mk_axis(c0);
234                    SharedRangeRef::from_parts(sheet_loc, None, Some(b), None, Some(b)).ok()
235                }
236                RK::OpenRect { start, end, .. } => {
237                    let (sr, sc) = match start {
238                        Some(p) => (Some(mk_axis(p.row())), Some(mk_axis(p.col()))),
239                        None => (None, None),
240                    };
241                    let (er, ec) = match end {
242                        Some(p) => (Some(mk_axis(p.row())), Some(mk_axis(p.col()))),
243                        None => (None, None),
244                    };
245                    SharedRangeRef::from_parts(sheet_loc, sr, sc, er, ec).ok()
246                }
247            };
248
249            if let Some(r) = built {
250                shared_ranges.push(r.into_owned());
251            }
252        }
253
254        if shared_ranges.is_empty() {
255            return;
256        }
257
258        self.formula_to_range_deps
259            .insert(dependent, shared_ranges.clone());
260
261        for range in &shared_ranges {
262            let sheet_id = match range.sheet {
263                SharedSheetLocator::Id(id) => id,
264                _ => current_sheet_id,
265            };
266
267            let s_row = range.start_row.map(|b| b.index);
268            let e_row = range.end_row.map(|b| b.index);
269            let s_col = range.start_col.map(|b| b.index);
270            let e_col = range.end_col.map(|b| b.index);
271
272            let col_stripes = (s_row.is_none() && e_row.is_none())
273                || (s_col.is_some() && e_col.is_some() && (s_row.is_none() || e_row.is_none()));
274            let row_stripes = (s_col.is_none() && e_col.is_none())
275                || (s_row.is_some() && e_row.is_some() && (s_col.is_none() || e_col.is_none()));
276
277            if col_stripes && !row_stripes {
278                let sc = s_col.unwrap_or(0);
279                let ec = e_col.unwrap_or(sc);
280                for col in sc..=ec {
281                    let key = StripeKey {
282                        sheet_id,
283                        stripe_type: StripeType::Column,
284                        index: col,
285                    };
286                    self.stripe_to_dependents
287                        .entry(key)
288                        .or_default()
289                        .insert(dependent);
290                }
291                continue;
292            }
293
294            if row_stripes && !col_stripes {
295                let sr = s_row.unwrap_or(0);
296                let er = e_row.unwrap_or(sr);
297                for row in sr..=er {
298                    let key = StripeKey {
299                        sheet_id,
300                        stripe_type: StripeType::Row,
301                        index: row,
302                    };
303                    self.stripe_to_dependents
304                        .entry(key)
305                        .or_default()
306                        .insert(dependent);
307                }
308                continue;
309            }
310
311            let start_row = s_row.unwrap_or(0);
312            let start_col = s_col.unwrap_or(0);
313            let end_row = e_row.unwrap_or(start_row);
314            let end_col = e_col.unwrap_or(start_col);
315
316            let height = end_row.saturating_sub(start_row) + 1;
317            let width = end_col.saturating_sub(start_col) + 1;
318
319            if self.config.enable_block_stripes && height > 1 && width > 1 {
320                let start_block_row = start_row / BLOCK_H;
321                let end_block_row = end_row / BLOCK_H;
322                let start_block_col = start_col / BLOCK_W;
323                let end_block_col = end_col / BLOCK_W;
324
325                for block_row in start_block_row..=end_block_row {
326                    for block_col in start_block_col..=end_block_col {
327                        let key = StripeKey {
328                            sheet_id,
329                            stripe_type: StripeType::Block,
330                            index: block_index(block_row * BLOCK_H, block_col * BLOCK_W),
331                        };
332                        self.stripe_to_dependents
333                            .entry(key)
334                            .or_default()
335                            .insert(dependent);
336                    }
337                }
338            } else if height > width {
339                for col in start_col..=end_col {
340                    let key = StripeKey {
341                        sheet_id,
342                        stripe_type: StripeType::Column,
343                        index: col,
344                    };
345                    self.stripe_to_dependents
346                        .entry(key)
347                        .or_default()
348                        .insert(dependent);
349                }
350            } else {
351                for row in start_row..=end_row {
352                    let key = StripeKey {
353                        sheet_id,
354                        stripe_type: StripeType::Row,
355                        index: row,
356                    };
357                    self.stripe_to_dependents
358                        .entry(key)
359                        .or_default()
360                        .insert(dependent);
361                }
362            }
363        }
364    }
365}