1use crate::CellId;
22use std::collections::{BTreeMap, BTreeSet, VecDeque};
23use std::vec::Vec;
24
25fn precedents(engine: &crate::Engine, node: &CellId) -> Vec<CellId> {
29 let (sheet, row, col) = node;
30 let mut out: Vec<CellId> = engine
31 .graph_for(sheet)
32 .map(|g| {
33 g.precedents((*row, *col))
34 .into_iter()
35 .map(|(r, c)| (sheet.clone(), r, c))
36 .collect::<Vec<_>>()
37 })
38 .unwrap_or_default();
39 if let Some(xs) = engine.cross_precedents(node) {
40 out.extend(xs.iter().cloned());
41 }
42 out
43}
44
45pub(crate) fn dependents(engine: &crate::Engine, node: &CellId) -> Vec<CellId> {
48 let (sheet, row, col) = node;
49 let mut out: Vec<CellId> = engine
50 .graph_for(sheet)
51 .map(|g| {
52 g.dependents((*row, *col))
53 .into_iter()
54 .map(|(r, c)| (sheet.clone(), r, c))
55 .collect::<Vec<_>>()
56 })
57 .unwrap_or_default();
58 if let Some(xs) = engine.cross_dependents(node) {
59 out.extend(xs.iter().cloned());
60 }
61 out
62}
63
64pub(crate) fn formula_cells(engine: &crate::Engine) -> BTreeSet<CellId> {
66 engine.formula_nodes()
67}
68
69pub(crate) fn topological_order(engine: &crate::Engine) -> Vec<CellId> {
77 let nodes = formula_cells(engine);
78 let mut indegree: BTreeMap<&CellId, usize> = nodes.iter().map(|n| (n, 0)).collect();
79 let mut adj: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
81 for n in &nodes {
82 for p in precedents(engine, n) {
83 if let Some(pn) = nodes.get(&p) {
86 if let Some(deg) = indegree.get_mut(n) {
87 *deg += 1;
88 }
89 adj.entry(pn).or_default().push(n);
90 }
91 }
92 }
93 kahn(indegree, &adj)
94}
95
96pub(crate) fn topological_order_restricted(
101 engine: &crate::Engine,
102 work: &BTreeSet<CellId>,
103) -> Vec<CellId> {
104 let mut indegree: BTreeMap<&CellId, usize> = work.iter().map(|n| (n, 0)).collect();
105 let mut adj: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
106 for n in work {
107 for p in precedents(engine, n) {
108 if let Some(pn) = work.get(&p) {
109 if let Some(deg) = indegree.get_mut(n) {
110 *deg += 1;
111 }
112 adj.entry(pn).or_default().push(n);
113 }
114 }
115 }
116 kahn(indegree, &adj)
117}
118
119fn kahn(
123 mut indegree: BTreeMap<&CellId, usize>,
124 adj: &BTreeMap<&CellId, Vec<&CellId>>,
125) -> Vec<CellId> {
126 let mut frontier: BTreeSet<&CellId> = indegree
127 .iter()
128 .filter(|(_, &d)| d == 0)
129 .map(|(&n, _)| n)
130 .collect();
131 let mut order: Vec<CellId> = Vec::with_capacity(indegree.len());
132 while let Some(n) = frontier.pop_first() {
133 order.push(n.clone());
134 if let Some(deps) = adj.get(n) {
135 for &d in deps {
136 if let Some(deg) = indegree.get_mut(d) {
137 *deg -= 1;
138 if *deg == 0 {
139 frontier.insert(d);
140 }
141 }
142 }
143 }
144 }
145 order
146}
147
148pub(crate) fn dirty_closure(
151 engine: &crate::Engine,
152 seeds: impl IntoIterator<Item = CellId>,
153) -> BTreeSet<CellId> {
154 let mut seen: BTreeSet<CellId> = seeds.into_iter().collect();
155 let mut queue: VecDeque<CellId> = seen.iter().cloned().collect();
156 while let Some(n) = queue.pop_front() {
157 for d in dependents(engine, &n) {
158 if seen.insert(d.clone()) {
159 queue.push_back(d);
160 }
161 }
162 }
163 seen
164}
165
166pub(crate) fn circular_members(engine: &crate::Engine, leftover: &[CellId]) -> Vec<CellId> {
172 if leftover.is_empty() {
173 return Vec::new();
174 }
175 let set: BTreeSet<&CellId> = leftover.iter().collect();
176 let mut forward: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
178 let mut reverse: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
179 for n in leftover {
180 for p in precedents(engine, n) {
181 if let Some(pn) = set.get(&p) {
182 forward.entry(n).or_default().push(*pn);
183 reverse.entry(*pn).or_default().push(n);
184 }
185 }
186 }
187
188 let mut finished: Vec<&CellId> = Vec::with_capacity(leftover.len());
190 let mut state: BTreeMap<&CellId, u8> = BTreeMap::new(); for start in leftover {
192 if state.get(start).copied().unwrap_or(0) != 0 {
193 continue;
194 }
195 let mut stack: Vec<(&CellId, usize)> = vec![(start, 0)];
196 state.insert(start, 1);
197 while let Some(top) = stack.last_mut() {
198 let (n, idx) = *top;
199 let next = forward.get(n).and_then(|ns| ns.get(idx)).copied();
200 if let Some(c) = next {
201 top.1 += 1;
202 if state.get(c).copied().unwrap_or(0) == 0 {
203 state.insert(c, 1);
204 stack.push((c, 0));
205 }
206 } else {
207 state.insert(n, 2);
208 finished.push(n);
209 stack.pop();
210 }
211 }
212 }
213
214 let mut assigned: BTreeMap<&CellId, usize> = BTreeMap::new();
216 let mut components: Vec<Vec<&CellId>> = Vec::new();
217 for &n in finished.iter().rev() {
218 if assigned.contains_key(n) {
219 continue;
220 }
221 let id = components.len();
222 let mut members: Vec<&CellId> = Vec::new();
223 let mut queue: VecDeque<&CellId> = VecDeque::from([n]);
224 assigned.insert(n, id);
225 while let Some(c) = queue.pop_front() {
226 members.push(c);
227 for d in reverse.get(c).into_iter().flatten() {
228 if !assigned.contains_key(d) {
229 assigned.insert(d, id);
230 queue.push_back(*d);
231 }
232 }
233 }
234 components.push(members);
235 }
236
237 let mut cycle_cells: BTreeSet<CellId> = BTreeSet::new();
239 for members in &components {
240 let single = members.first();
241 let self_edge = members.len() == 1
242 && single.is_some_and(|n| forward.get(n).is_some_and(|ns| ns.contains(n)));
243 if members.len() > 1 || self_edge {
244 cycle_cells.extend(members.iter().map(|n| (*n).clone()));
245 }
246 }
247 cycle_cells.into_iter().collect()
248}
249
250#[cfg(test)]
252pub(crate) fn a1(node: &CellId) -> String {
253 let (sheet, row, col) = node;
254 format!(
255 "{sheet}!{}{}",
256 formula_lang::ast::col_name(col + 1),
257 row + 1
258 )
259}
260
261#[cfg(test)]
262mod tests {
263 #![allow(
264 clippy::unwrap_used,
265 clippy::expect_used,
266 clippy::panic,
267 clippy::indexing_slicing
268 )]
269
270 use super::*;
271 use crate::Engine;
272
273 fn n(sheet: &str, row: u32, col: u32) -> CellId {
274 (sheet.to_string(), row, col)
275 }
276
277 #[test]
278 fn topo_orders_a_cross_sheet_chain() {
279 let mut e = Engine::new();
280 e.set_cell("S1", 0, 0, "1").unwrap();
281 e.set_cell("S2", 0, 0, "=S1!A1+1").unwrap();
282 e.set_cell("S1", 0, 1, "=S2!A1+1").unwrap();
283 let order = topological_order(&e);
284 let a1s: Vec<String> = order.iter().map(a1).collect();
285 assert_eq!(a1s, vec!["S2!A1", "S1!B1"]);
286 }
287
288 #[test]
289 fn closure_flows_across_sheets() {
290 let mut e = Engine::new();
291 e.set_cell("S1", 0, 0, "1").unwrap();
292 e.set_cell("S2", 0, 0, "=S1!A1+1").unwrap();
293 e.set_cell("S2", 0, 1, "=S2!A1+1").unwrap();
294 let dirty = dirty_closure(&e, [n("S1", 0, 0)]);
295 let a1s: Vec<String> = dirty.iter().map(a1).collect();
296 assert_eq!(a1s, vec!["S1!A1", "S2!A1", "S2!B1"]);
297 }
298
299 #[test]
300 fn cycles_are_reported_exactly_not_downstream() {
301 let mut e = Engine::new();
303 e.set_cell("S", 0, 0, "=B1+1").unwrap();
304 e.set_cell("S", 0, 1, "=A1+1").unwrap();
305 e.set_cell("S", 0, 2, "=A1+1").unwrap();
306 let order = topological_order(&e);
307 assert_eq!(order, Vec::<CellId>::new());
308 let left = formula_cells(&e)
309 .into_iter()
310 .filter(|n| !order.contains(n))
311 .collect::<Vec<_>>();
312 let cyc = circular_members(&e, &left);
313 let a1s: Vec<String> = cyc.iter().map(a1).collect();
314 assert_eq!(a1s, vec!["S!A1", "S!B1"]);
315 }
316
317 #[test]
318 fn cross_sheet_cycles_are_found() {
319 let mut e = Engine::new();
320 e.set_cell("S1", 0, 0, "=S2!A1+1").unwrap();
321 e.set_cell("S2", 0, 0, "=S1!A1+1").unwrap();
322 let order = topological_order(&e);
323 assert_eq!(order, Vec::<CellId>::new());
324 let left: Vec<CellId> = formula_cells(&e).into_iter().collect();
325 let cyc = circular_members(&e, &left);
326 assert_eq!(cyc.len(), 2);
327 }
328
329 #[test]
330 fn a1_notation_is_one_based() {
331 assert_eq!(a1(&n("S", 0, 0)), "S!A1");
332 assert_eq!(a1(&n("S", 1, 27)), "S!AB2");
333 }
334}