cell_sheet_core/formula/
deps.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2
3use crate::formula::ast::*;
4use crate::formula::eval;
5use crate::formula::parser;
6use crate::model::{CellError, CellPos, CellValue, Sheet};
7
8pub struct DepGraph {
9    pub dependents: HashMap<CellPos, HashSet<CellPos>>,
10    pub dependencies: HashMap<CellPos, HashSet<CellPos>>,
11}
12
13impl Default for DepGraph {
14    fn default() -> Self {
15        Self::new()
16    }
17}
18
19impl DepGraph {
20    pub fn new() -> Self {
21        DepGraph {
22            dependents: HashMap::new(),
23            dependencies: HashMap::new(),
24        }
25    }
26
27    pub fn set_dependencies(&mut self, cell: CellPos, deps: Vec<CellPos>) {
28        if let Some(old_deps) = self.dependencies.remove(&cell) {
29            for dep in &old_deps {
30                if let Some(set) = self.dependents.get_mut(dep) {
31                    set.remove(&cell);
32                }
33            }
34        }
35        let dep_set: HashSet<CellPos> = deps.into_iter().collect();
36        for dep in &dep_set {
37            self.dependents.entry(*dep).or_default().insert(cell);
38        }
39        self.dependencies.insert(cell, dep_set);
40    }
41
42    /// Drop `cell` from the graph: removes its outgoing dependency edges and
43    /// any reverse-edge bookkeeping. Use when the cell is cleared or rewritten
44    /// as a non-formula value so stale entries don't accumulate.
45    pub fn remove(&mut self, cell: CellPos) {
46        if let Some(old_deps) = self.dependencies.remove(&cell) {
47            for dep in &old_deps {
48                if let Some(set) = self.dependents.get_mut(dep) {
49                    set.remove(&cell);
50                }
51            }
52        }
53    }
54}
55
56pub fn extract_deps(formula: &str) -> Vec<CellPos> {
57    let expr = match parser::parse(formula) {
58        Ok(e) => e,
59        Err(_) => return vec![],
60    };
61    let mut deps = Vec::new();
62    collect_refs(&expr, &mut deps);
63    deps
64}
65
66fn collect_refs(expr: &Expr, out: &mut Vec<CellPos>) {
67    match expr {
68        Expr::CellRef(r) => {
69            out.push((r.row, r.col));
70        }
71        Expr::Range { start, end } => {
72            let r1 = start.row.min(end.row);
73            let r2 = start.row.max(end.row);
74            let c1 = start.col.min(end.col);
75            let c2 = start.col.max(end.col);
76            for r in r1..=r2 {
77                for c in c1..=c2 {
78                    out.push((r, c));
79                }
80            }
81        }
82        Expr::BinaryOp { left, right, .. } => {
83            collect_refs(left, out);
84            collect_refs(right, out);
85        }
86        Expr::UnaryNeg(inner) => collect_refs(inner, out),
87        Expr::FnCall { args, .. } => {
88            for arg in args {
89                collect_refs(arg, out);
90            }
91        }
92        _ => {}
93    }
94}
95
96pub fn set_formula(sheet: &mut Sheet, deps: &mut DepGraph, pos: CellPos, raw: &str) {
97    sheet.set_cell(pos, raw);
98    let formula = &raw[1..]; // strip '='
99    let dep_list = extract_deps(formula);
100    deps.set_dependencies(pos, dep_list);
101}
102
103pub fn mark_dirty(sheet: &mut Sheet, deps: &DepGraph, pos: CellPos) {
104    let mut queue = VecDeque::new();
105    queue.push_back(pos);
106    while let Some(cell) = queue.pop_front() {
107        if let Some(dependents) = deps.dependents.get(&cell) {
108            for &dep in dependents {
109                if let Some(c) = sheet.cells.get_mut(&dep) {
110                    if !c.dirty {
111                        c.dirty = true;
112                        queue.push_back(dep);
113                    }
114                }
115            }
116        }
117    }
118}
119
120pub fn recalculate(sheet: &mut Sheet, deps: &DepGraph) {
121    let formula_cells: Vec<CellPos> = sheet
122        .cells
123        .iter()
124        .filter(|(_, cell)| cell.raw.starts_with('='))
125        .map(|(pos, _)| *pos)
126        .collect();
127
128    let formula_set: HashSet<CellPos> = formula_cells.iter().cloned().collect();
129
130    let mut in_degree: HashMap<CellPos, usize> = HashMap::new();
131    for &cell in &formula_cells {
132        let count = deps
133            .dependencies
134            .get(&cell)
135            .map(|d| d.iter().filter(|p| formula_set.contains(p)).count())
136            .unwrap_or(0);
137        in_degree.insert(cell, count);
138    }
139
140    let mut queue: VecDeque<CellPos> = in_degree
141        .iter()
142        .filter(|(_, &deg)| deg == 0)
143        .map(|(&pos, _)| pos)
144        .collect();
145
146    let mut order = Vec::new();
147
148    while let Some(cell) = queue.pop_front() {
149        order.push(cell);
150        if let Some(dependents) = deps.dependents.get(&cell) {
151            for &dep in dependents {
152                if let Some(deg) = in_degree.get_mut(&dep) {
153                    *deg -= 1;
154                    if *deg == 0 {
155                        queue.push_back(dep);
156                    }
157                }
158            }
159        }
160    }
161
162    let ordered_set: HashSet<CellPos> = order.iter().cloned().collect();
163    for &cell in &formula_cells {
164        if !ordered_set.contains(&cell) {
165            if let Some(c) = sheet.cells.get_mut(&cell) {
166                c.value = CellValue::Error(CellError::Circ);
167                c.dirty = false;
168            }
169        }
170    }
171
172    for pos in order {
173        let raw = match sheet.get_cell(pos) {
174            Some(cell) if cell.raw.starts_with('=') => cell.raw.clone(),
175            _ => continue,
176        };
177        let formula = &raw[1..];
178        let value = eval::evaluate(formula, sheet);
179        if let Some(cell) = sheet.cells.get_mut(&pos) {
180            cell.value = value;
181            cell.dirty = false;
182        }
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use super::*;
189    use crate::model::{CellValue, Sheet};
190
191    #[test]
192    fn extract_deps_cell_ref() {
193        let deps = extract_deps("A1+B1");
194        assert_eq!(deps, vec![(0, 0), (0, 1)]);
195    }
196
197    #[test]
198    fn extract_deps_range() {
199        let deps = extract_deps("SUM(A1:A3)");
200        assert_eq!(deps, vec![(0, 0), (1, 0), (2, 0)]);
201    }
202
203    #[test]
204    fn extract_deps_no_refs() {
205        let deps = extract_deps("1+2");
206        assert!(deps.is_empty());
207    }
208
209    #[test]
210    fn recalc_simple() {
211        let mut sheet = Sheet::new();
212        let mut deps = DepGraph::new();
213        sheet.set_cell((0, 0), "10");
214        set_formula(&mut sheet, &mut deps, (0, 1), "=A1+5");
215        recalculate(&mut sheet, &deps);
216        assert_eq!(
217            sheet.get_cell((0, 1)).unwrap().value,
218            CellValue::Number(15.0)
219        );
220    }
221
222    #[test]
223    fn recalc_chain() {
224        let mut sheet = Sheet::new();
225        let mut deps = DepGraph::new();
226        sheet.set_cell((0, 0), "10");
227        set_formula(&mut sheet, &mut deps, (0, 1), "=A1*2");
228        set_formula(&mut sheet, &mut deps, (0, 2), "=B1+1");
229        recalculate(&mut sheet, &deps);
230        assert_eq!(
231            sheet.get_cell((0, 1)).unwrap().value,
232            CellValue::Number(20.0)
233        );
234        assert_eq!(
235            sheet.get_cell((0, 2)).unwrap().value,
236            CellValue::Number(21.0)
237        );
238    }
239
240    #[test]
241    fn recalc_circular_reference() {
242        let mut sheet = Sheet::new();
243        let mut deps = DepGraph::new();
244        set_formula(&mut sheet, &mut deps, (0, 0), "=B1");
245        set_formula(&mut sheet, &mut deps, (0, 1), "=A1");
246        recalculate(&mut sheet, &deps);
247        assert_eq!(
248            sheet.get_cell((0, 0)).unwrap().value,
249            CellValue::Error(CellError::Circ)
250        );
251        assert_eq!(
252            sheet.get_cell((0, 1)).unwrap().value,
253            CellValue::Error(CellError::Circ)
254        );
255    }
256
257    #[test]
258    fn recalc_after_value_change() {
259        let mut sheet = Sheet::new();
260        let mut deps = DepGraph::new();
261        sheet.set_cell((0, 0), "10");
262        set_formula(&mut sheet, &mut deps, (0, 1), "=A1+5");
263        recalculate(&mut sheet, &deps);
264        assert_eq!(
265            sheet.get_cell((0, 1)).unwrap().value,
266            CellValue::Number(15.0)
267        );
268
269        sheet.set_cell((0, 0), "20");
270        mark_dirty(&mut sheet, &deps, (0, 0));
271        recalculate(&mut sheet, &deps);
272        assert_eq!(
273            sheet.get_cell((0, 1)).unwrap().value,
274            CellValue::Number(25.0)
275        );
276    }
277
278    #[test]
279    fn remove_drops_edges() {
280        let mut sheet = Sheet::new();
281        let mut deps = DepGraph::new();
282        sheet.set_cell((0, 0), "10");
283        set_formula(&mut sheet, &mut deps, (0, 1), "=A1+5");
284        assert!(deps.dependencies.contains_key(&(0, 1)));
285        assert!(deps.dependents.get(&(0, 0)).unwrap().contains(&(0, 1)));
286
287        deps.remove((0, 1));
288
289        assert!(!deps.dependencies.contains_key(&(0, 1)));
290        assert!(!deps
291            .dependents
292            .get(&(0, 0))
293            .map(|s| s.contains(&(0, 1)))
294            .unwrap_or(false));
295    }
296
297    #[test]
298    fn self_reference_is_circular() {
299        let mut sheet = Sheet::new();
300        let mut deps = DepGraph::new();
301        set_formula(&mut sheet, &mut deps, (0, 0), "=A1+1");
302        recalculate(&mut sheet, &deps);
303        assert_eq!(
304            sheet.get_cell((0, 0)).unwrap().value,
305            CellValue::Error(CellError::Circ)
306        );
307    }
308}
cell_sheet_core/formula/deps.rs

cell_sheet_core/formula/
deps.rs
