gridline_engine/engine/
cycle.rs

1//! Circular dependency detection for formula cells.
2//!
3//! When a formula is entered, we must verify it doesn't create a cycle
4//! (e.g., A1 references B1, B1 references C1, C1 references A1).
5//! This module uses depth-first search to detect such cycles before
6//! they cause infinite evaluation loops.
7
8use std::collections::HashSet;
9
10use super::{CellRef, Grid};
11
12/// Detect circular dependencies starting from a cell.
13/// Returns Some(cycle_path) if a cycle is found, None otherwise.
14pub fn detect_cycle(start: &CellRef, grid: &Grid) -> Option<Vec<CellRef>> {
15    let mut visiting = HashSet::new();
16    let mut path = Vec::new();
17
18    if detect_cycle_dfs(start, grid, &mut visiting, &mut path) {
19        Some(path)
20    } else {
21        None
22    }
23}
24
25fn detect_cycle_dfs(
26    current: &CellRef,
27    grid: &Grid,
28    visiting: &mut HashSet<CellRef>,
29    path: &mut Vec<CellRef>,
30) -> bool {
31    if visiting.contains(current) {
32        path.push(current.clone());
33        return true;
34    }
35
36    let deps = match grid.get(current) {
37        Some(entry) => entry.depends_on.clone(),
38        None => return false,
39    };
40
41    visiting.insert(current.clone());
42    path.push(current.clone());
43
44    for dep in &deps {
45        if detect_cycle_dfs(dep, grid, visiting, path) {
46            return true;
47        }
48    }
49
50    path.pop();
51    visiting.remove(current);
52    false
53}
gridline_engine/engine/cycle.rs

gridline_engine/engine/
cycle.rs
