solverforge_core/domain/
cascade.rs1use super::PlanningSolution;
15
16const UNVISITED: usize = usize::MAX;
17
18#[derive(Default)]
25pub struct CascadePropagation {
26 offsets: Vec<usize>,
29 dependents: Vec<usize>,
30 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 pub fn new<S: PlanningSolution>(solution: &S) -> Self {
48 let mut propagation = Self::default();
49 propagation.rebuild_dependencies(solution);
50 propagation
51 }
52
53 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 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 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 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 #[cold]
247 fn mark_cycles<S: PlanningSolution>(&mut self, solution: &S) {
248 let mut next_order = 0;
249 let mut components = Vec::new();
250 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}