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