Skip to main content

solverforge_core/domain/
cascade.rs

1//! Propagation of cascading list shadows across list owners.
2//!
3//! A cascading value depends on the element's previous element in its list
4//! and on the elements it declares it depends on, which other owners' lists
5//! may hold. The dependency graph has an edge from an element's previous
6//! element and from each of its dependencies to the element. After list
7//! changes, [`CascadePropagation::propagate`] visits the downstream cone of
8//! the changed elements and recomputes it in dependency order: an element is
9//! recomputed at most once, only after every input in the cone is final, and
10//! only when an input value changed (or it is a changed element itself), so
11//! propagation stops where a recomputed value equals the old one. Elements
12//! on a dependency cycle have no defined value and are unset.
13
14use super::PlanningSolution;
15
16const UNVISITED: usize = usize::MAX;
17
18/// Reusable propagation state for one solution's cascading shadow.
19///
20/// Holds the reverse index of the declared dependencies, built by
21/// [`rebuild_dependencies`](Self::rebuild_dependencies) and valid while the
22/// dependencies and the element count stay unchanged, plus per-element
23/// scratch that every propagation leaves cleared.
24#[derive(Default)]
25pub struct CascadePropagation {
26    // Elements that declare a dependency on each element, as compressed
27    // rows: the dependents of `e` are `dependents[offsets[e]..offsets[e + 1]]`.
28    offsets: Vec<usize>,
29    dependents: Vec<usize>,
30    // Per-element scratch, cleared after each propagation.
31    in_cone: Vec<bool>,
32    dirty: Vec<bool>,
33    done: Vec<bool>,
34    cycle: Vec<bool>,
35    pending_inputs: Vec<usize>,
36    order: Vec<usize>,
37    low: Vec<usize>,
38    on_stack: Vec<bool>,
39    cone: Vec<usize>,
40    stack: Vec<usize>,
41    ready: Vec<usize>,
42    scratch: Vec<usize>,
43}
44
45impl CascadePropagation {
46    /// Propagation state for `solution`, with its dependency index built.
47    pub fn new<S: PlanningSolution>(solution: &S) -> Self {
48        let mut propagation = Self::default();
49        propagation.rebuild_dependencies(solution);
50        propagation
51    }
52
53    /// Rebuilds the reverse dependency index from `solution` and sizes the
54    /// per-element scratch to its element count.
55    ///
56    /// # Panics
57    ///
58    /// When an element declares a dependency on an element index that does
59    /// not exist.
60    pub fn rebuild_dependencies<S: PlanningSolution>(&mut self, solution: &S) {
61        let count = solution.cascading_element_count();
62        self.offsets.clear();
63        self.offsets.resize(count + 1, 0);
64        for element in 0..count {
65            self.scratch.clear();
66            solution.cascading_dependencies(element, &mut self.scratch);
67            for &dependency in &self.scratch {
68                assert!(
69                    dependency < count,
70                    "cascading element {element} depends on element {dependency}, but there are only {count} elements"
71                );
72                self.offsets[dependency + 1] += 1;
73            }
74        }
75        for element in 0..count {
76            self.offsets[element + 1] += self.offsets[element];
77        }
78        self.dependents.clear();
79        self.dependents.resize(self.offsets[count], 0);
80        let mut fill = self.offsets.clone();
81        for element in 0..count {
82            self.scratch.clear();
83            solution.cascading_dependencies(element, &mut self.scratch);
84            for &dependency in &self.scratch {
85                self.dependents[fill[dependency]] = element;
86                fill[dependency] += 1;
87            }
88        }
89        self.scratch.clear();
90        for flags in [
91            &mut self.in_cone,
92            &mut self.dirty,
93            &mut self.done,
94            &mut self.cycle,
95            &mut self.on_stack,
96        ] {
97            flags.clear();
98            flags.resize(count, false);
99        }
100        self.pending_inputs.clear();
101        self.pending_inputs.resize(count, 0);
102        self.order.clear();
103        self.order.resize(count, UNVISITED);
104        self.low.clear();
105        self.low.resize(count, UNVISITED);
106    }
107
108    /// Recomputes every cascading value of `solution` from scratch.
109    pub fn refresh_all<S: PlanningSolution>(solution: &mut S) {
110        let mut propagation = Self::new(solution);
111        let count = solution.cascading_element_count();
112        propagation.propagate(solution, 0..count, |_, _| {});
113    }
114
115    /// Recomputes the cascading values downstream of `changed`, the elements
116    /// whose list position or list membership changed.
117    ///
118    /// Every element of `changed` is recomputed; another element of the
119    /// downstream cone is recomputed when one of its inputs changed value, or
120    /// when it is held by a list but unset (it may have left a dependency
121    /// cycle). Each element is recomputed at most once, after all of its
122    /// inputs in the cone. Before an element's value is written,
123    /// `before_write` is called with the solution still holding the old value
124    /// and the element index.
125    pub fn propagate<S, I, W>(&mut self, solution: &mut S, changed: I, mut before_write: W)
126    where
127        S: PlanningSolution,
128        I: IntoIterator<Item = usize>,
129        W: FnMut(&S, usize),
130    {
131        for element in changed {
132            self.dirty[element] = true;
133            if !self.in_cone[element] {
134                self.in_cone[element] = true;
135                self.cone.push(element);
136                self.stack.push(element);
137            }
138        }
139        while let Some(element) = self.stack.pop() {
140            if let Some(next) = solution.cascading_next(element) {
141                self.reach(next);
142            }
143            for position in self.offsets[element]..self.offsets[element + 1] {
144                self.reach(self.dependents[position]);
145            }
146        }
147
148        self.ready.extend(
149            self.cone
150                .iter()
151                .copied()
152                .filter(|&element| self.pending_inputs[element] == 0),
153        );
154        let mut finished = 0;
155        loop {
156            while let Some(element) = self.ready.pop() {
157                self.done[element] = true;
158                finished += 1;
159                let assigned = solution.cascading_assigned(element);
160                if (self.dirty[element] || (assigned && solution.cascading_unset(element)))
161                    && solution.update_cascading_shadow(element, assigned, |solution| {
162                        before_write(solution, element)
163                    })
164                {
165                    self.mark_outputs_dirty(solution, element);
166                }
167                self.release_outputs(solution, element);
168            }
169            if finished == self.cone.len() {
170                break;
171            }
172            // The remaining elements wait on a dependency cycle. Cycle
173            // members are unset; the elements downstream of them are then
174            // computed from the unset values.
175            self.mark_cycles(solution);
176            for index in 0..self.cone.len() {
177                let element = self.cone[index];
178                if self.cycle[element] && !self.done[element] {
179                    self.done[element] = true;
180                    finished += 1;
181                    if solution.update_cascading_shadow(element, false, |solution| {
182                        before_write(solution, element)
183                    }) {
184                        self.mark_outputs_dirty(solution, element);
185                    }
186                }
187            }
188            for index in 0..self.cone.len() {
189                let element = self.cone[index];
190                if self.cycle[element] {
191                    self.release_outputs(solution, element);
192                }
193            }
194        }
195
196        for &element in &self.cone {
197            self.in_cone[element] = false;
198            self.dirty[element] = false;
199            self.done[element] = false;
200            self.cycle[element] = false;
201            self.pending_inputs[element] = 0;
202            self.order[element] = UNVISITED;
203            self.low[element] = UNVISITED;
204        }
205        self.cone.clear();
206    }
207
208    fn reach(&mut self, element: usize) {
209        self.pending_inputs[element] += 1;
210        if !self.in_cone[element] {
211            self.in_cone[element] = true;
212            self.cone.push(element);
213            self.stack.push(element);
214        }
215    }
216
217    fn mark_outputs_dirty<S: PlanningSolution>(&mut self, solution: &S, element: usize) {
218        if let Some(next) = solution.cascading_next(element) {
219            self.dirty[next] = true;
220        }
221        for position in self.offsets[element]..self.offsets[element + 1] {
222            self.dirty[self.dependents[position]] = true;
223        }
224    }
225
226    fn release_outputs<S: PlanningSolution>(&mut self, solution: &S, element: usize) {
227        if let Some(next) = solution.cascading_next(element) {
228            self.release(next);
229        }
230        for position in self.offsets[element]..self.offsets[element + 1] {
231            self.release(self.dependents[position]);
232        }
233    }
234
235    fn release(&mut self, element: usize) {
236        self.pending_inputs[element] -= 1;
237        if self.pending_inputs[element] == 0 && !self.done[element] && !self.cycle[element] {
238            self.ready.push(element);
239        }
240    }
241
242    /// Marks the members of every dependency cycle among the unfinished
243    /// elements of the cone (strongly connected components with more than
244    /// one element, or an element that depends on itself). Runs only when
245    /// propagation stalls on a cycle.
246    #[cold]
247    fn mark_cycles<S: PlanningSolution>(&mut self, solution: &S) {
248        let mut next_order = 0;
249        let mut components = Vec::new();
250        // Each frame holds an element and its unfinished outputs still to visit.
251        let mut frames: Vec<(usize, Vec<usize>)> = Vec::new();
252        for index in 0..self.cone.len() {
253            let root = self.cone[index];
254            if self.done[root] || self.order[root] != UNVISITED {
255                continue;
256            }
257            self.enter(
258                solution,
259                root,
260                &mut next_order,
261                &mut components,
262                &mut frames,
263            );
264            while let Some((element, outputs)) = frames.last_mut() {
265                let element = *element;
266                if let Some(output) = outputs.pop() {
267                    if self.order[output] == UNVISITED {
268                        self.enter(
269                            solution,
270                            output,
271                            &mut next_order,
272                            &mut components,
273                            &mut frames,
274                        );
275                    } else if self.on_stack[output] {
276                        self.low[element] = self.low[element].min(self.order[output]);
277                    }
278                    continue;
279                }
280                frames.pop();
281                if let Some((parent, _)) = frames.last() {
282                    self.low[*parent] = self.low[*parent].min(self.low[element]);
283                }
284                if self.low[element] == self.order[element] {
285                    let start = components
286                        .iter()
287                        .rposition(|&member| member == element)
288                        .expect("component root is on the stack");
289                    let self_loop = self.depends_on_itself(solution, element);
290                    let is_cycle = components.len() - start > 1 || self_loop;
291                    for member in components.drain(start..) {
292                        self.on_stack[member] = false;
293                        self.cycle[member] = is_cycle;
294                    }
295                }
296            }
297        }
298    }
299
300    fn enter<S: PlanningSolution>(
301        &mut self,
302        solution: &S,
303        element: usize,
304        next_order: &mut usize,
305        components: &mut Vec<usize>,
306        frames: &mut Vec<(usize, Vec<usize>)>,
307    ) {
308        self.order[element] = *next_order;
309        self.low[element] = *next_order;
310        *next_order += 1;
311        self.on_stack[element] = true;
312        components.push(element);
313        let mut outputs = Vec::new();
314        if let Some(next) = solution.cascading_next(element) {
315            outputs.push(next);
316        }
317        outputs
318            .extend_from_slice(&self.dependents[self.offsets[element]..self.offsets[element + 1]]);
319        outputs.retain(|&output| self.in_cone[output] && !self.done[output]);
320        frames.push((element, outputs));
321    }
322
323    fn depends_on_itself<S: PlanningSolution>(&self, solution: &S, element: usize) -> bool {
324        solution.cascading_next(element) == Some(element)
325            || self.dependents[self.offsets[element]..self.offsets[element + 1]].contains(&element)
326    }
327}