]>
Commit | Line | Data |
---|---|---|
7453a54e SL |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! The `ObligationForest` is a utility data structure used in trait | |
12 | //! matching to track the set of outstanding obligations (those not | |
13 | //! yet resolved to success or error). It also tracks the "backtrace" | |
14 | //! of each pending obligation (why we are trying to figure this out | |
15 | //! in the first place). See README.md for a general overview of how | |
16 | //! to use this class. | |
17 | ||
a7813a04 XL |
18 | use fnv::{FnvHashMap, FnvHashSet}; |
19 | ||
20 | use std::cell::Cell; | |
21 | use std::collections::hash_map::Entry; | |
7453a54e | 22 | use std::fmt::Debug; |
a7813a04 XL |
23 | use std::hash; |
24 | use std::marker::PhantomData; | |
7453a54e SL |
25 | |
26 | mod node_index; | |
27 | use self::node_index::NodeIndex; | |
28 | ||
7453a54e SL |
29 | #[cfg(test)] |
30 | mod test; | |
31 | ||
a7813a04 XL |
32 | pub trait ForestObligation : Clone + Debug { |
33 | type Predicate : Clone + hash::Hash + Eq + Debug; | |
34 | ||
35 | fn as_predicate(&self) -> &Self::Predicate; | |
36 | } | |
37 | ||
38 | pub trait ObligationProcessor { | |
39 | type Obligation : ForestObligation; | |
40 | type Error : Debug; | |
41 | ||
42 | fn process_obligation(&mut self, | |
43 | obligation: &mut Self::Obligation) | |
44 | -> Result<Option<Vec<Self::Obligation>>, Self::Error>; | |
45 | ||
46 | fn process_backedge<'c, I>(&mut self, cycle: I, | |
47 | _marker: PhantomData<&'c Self::Obligation>) | |
48 | where I: Clone + Iterator<Item=&'c Self::Obligation>; | |
49 | } | |
50 | ||
51 | struct SnapshotData { | |
52 | node_len: usize, | |
53 | cache_list_len: usize, | |
54 | } | |
55 | ||
56 | pub struct ObligationForest<O: ForestObligation> { | |
7453a54e SL |
57 | /// The list of obligations. In between calls to |
58 | /// `process_obligations`, this list only contains nodes in the | |
59 | /// `Pending` or `Success` state (with a non-zero number of | |
60 | /// incomplete children). During processing, some of those nodes | |
61 | /// may be changed to the error state, or we may find that they | |
62 | /// are completed (That is, `num_incomplete_children` drops to 0). | |
63 | /// At the end of processing, those nodes will be removed by a | |
64 | /// call to `compress`. | |
65 | /// | |
66 | /// At all times we maintain the invariant that every node appears | |
67 | /// at a higher index than its parent. This is needed by the | |
68 | /// backtrace iterator (which uses `split_at`). | |
69 | nodes: Vec<Node<O>>, | |
a7813a04 XL |
70 | /// A cache of predicates that have been successfully completed. |
71 | done_cache: FnvHashSet<O::Predicate>, | |
72 | /// An cache of the nodes in `nodes`, indexed by predicate. | |
73 | waiting_cache: FnvHashMap<O::Predicate, NodeIndex>, | |
74 | /// A list of the obligations added in snapshots, to allow | |
75 | /// for their removal. | |
76 | cache_list: Vec<O::Predicate>, | |
77 | snapshots: Vec<SnapshotData>, | |
78 | scratch: Option<Vec<usize>>, | |
7453a54e SL |
79 | } |
80 | ||
81 | pub struct Snapshot { | |
82 | len: usize, | |
83 | } | |
84 | ||
a7813a04 | 85 | #[derive(Debug)] |
7453a54e | 86 | struct Node<O> { |
a7813a04 XL |
87 | obligation: O, |
88 | state: Cell<NodeState>, | |
89 | ||
90 | /// Obligations that depend on this obligation for their | |
91 | /// completion. They must all be in a non-pending state. | |
92 | dependents: Vec<NodeIndex>, | |
93 | /// The parent of a node - the original obligation of | |
94 | /// which it is a subobligation. Except for error reporting, | |
95 | /// this is just another member of `dependents`. | |
7453a54e | 96 | parent: Option<NodeIndex>, |
7453a54e SL |
97 | } |
98 | ||
99 | /// The state of one node in some tree within the forest. This | |
100 | /// represents the current state of processing for the obligation (of | |
101 | /// type `O`) associated with this node. | |
a7813a04 XL |
102 | /// |
103 | /// Outside of ObligationForest methods, nodes should be either Pending | |
104 | /// or Waiting. | |
105 | #[derive(Debug, Copy, Clone, PartialEq, Eq)] | |
106 | enum NodeState { | |
107 | /// Obligations for which selection had not yet returned a | |
108 | /// non-ambiguous result. | |
109 | Pending, | |
110 | ||
111 | /// This obligation was selected successfuly, but may or | |
112 | /// may not have subobligations. | |
113 | Success, | |
114 | ||
115 | /// This obligation was selected sucessfully, but it has | |
116 | /// a pending subobligation. | |
117 | Waiting, | |
118 | ||
119 | /// This obligation, along with its subobligations, are complete, | |
120 | /// and will be removed in the next collection. | |
121 | Done, | |
7453a54e SL |
122 | |
123 | /// This obligation was resolved to an error. Error nodes are | |
124 | /// removed from the vector by the compression step. | |
125 | Error, | |
a7813a04 XL |
126 | |
127 | /// This is a temporary state used in DFS loops to detect cycles, | |
128 | /// it should not exist outside of these DFSes. | |
129 | OnDfsStack, | |
7453a54e SL |
130 | } |
131 | ||
132 | #[derive(Debug)] | |
54a0048b | 133 | pub struct Outcome<O, E> { |
7453a54e SL |
134 | /// Obligations that were completely evaluated, including all |
135 | /// (transitive) subobligations. | |
136 | pub completed: Vec<O>, | |
137 | ||
138 | /// Backtrace of obligations that were found to be in error. | |
54a0048b | 139 | pub errors: Vec<Error<O, E>>, |
7453a54e SL |
140 | |
141 | /// If true, then we saw no successful obligations, which means | |
142 | /// there is no point in further iteration. This is based on the | |
143 | /// assumption that when trait matching returns `Err` or | |
144 | /// `Ok(None)`, those results do not affect environmental | |
145 | /// inference state. (Note that if we invoke `process_obligations` | |
146 | /// with no pending obligations, stalled will be true.) | |
147 | pub stalled: bool, | |
148 | } | |
149 | ||
150 | #[derive(Debug, PartialEq, Eq)] | |
54a0048b | 151 | pub struct Error<O, E> { |
7453a54e SL |
152 | pub error: E, |
153 | pub backtrace: Vec<O>, | |
154 | } | |
155 | ||
a7813a04 XL |
156 | impl<O: ForestObligation> ObligationForest<O> { |
157 | pub fn new() -> ObligationForest<O> { | |
7453a54e | 158 | ObligationForest { |
7453a54e | 159 | nodes: vec![], |
54a0048b | 160 | snapshots: vec![], |
a7813a04 XL |
161 | done_cache: FnvHashSet(), |
162 | waiting_cache: FnvHashMap(), | |
163 | cache_list: vec![], | |
164 | scratch: Some(vec![]), | |
7453a54e SL |
165 | } |
166 | } | |
167 | ||
168 | /// Return the total number of nodes in the forest that have not | |
169 | /// yet been fully resolved. | |
170 | pub fn len(&self) -> usize { | |
171 | self.nodes.len() | |
172 | } | |
173 | ||
174 | pub fn start_snapshot(&mut self) -> Snapshot { | |
a7813a04 XL |
175 | self.snapshots.push(SnapshotData { |
176 | node_len: self.nodes.len(), | |
177 | cache_list_len: self.cache_list.len() | |
178 | }); | |
7453a54e SL |
179 | Snapshot { len: self.snapshots.len() } |
180 | } | |
181 | ||
182 | pub fn commit_snapshot(&mut self, snapshot: Snapshot) { | |
183 | assert_eq!(snapshot.len, self.snapshots.len()); | |
a7813a04 XL |
184 | let info = self.snapshots.pop().unwrap(); |
185 | assert!(self.nodes.len() >= info.node_len); | |
186 | assert!(self.cache_list.len() >= info.cache_list_len); | |
7453a54e SL |
187 | } |
188 | ||
189 | pub fn rollback_snapshot(&mut self, snapshot: Snapshot) { | |
190 | // Check that we are obeying stack discipline. | |
191 | assert_eq!(snapshot.len, self.snapshots.len()); | |
a7813a04 | 192 | let info = self.snapshots.pop().unwrap(); |
7453a54e | 193 | |
a7813a04 XL |
194 | for entry in &self.cache_list[info.cache_list_len..] { |
195 | self.done_cache.remove(entry); | |
196 | self.waiting_cache.remove(entry); | |
7453a54e SL |
197 | } |
198 | ||
a7813a04 XL |
199 | self.nodes.truncate(info.node_len); |
200 | self.cache_list.truncate(info.cache_list_len); | |
7453a54e SL |
201 | } |
202 | ||
203 | pub fn in_snapshot(&self) -> bool { | |
204 | !self.snapshots.is_empty() | |
205 | } | |
206 | ||
a7813a04 | 207 | /// Registers an obligation |
7453a54e | 208 | /// |
a7813a04 XL |
209 | /// This CAN be done in a snapshot |
210 | pub fn register_obligation(&mut self, obligation: O) { | |
211 | // Ignore errors here - there is no guarantee of success. | |
212 | let _ = self.register_obligation_at(obligation, None); | |
213 | } | |
214 | ||
215 | // returns Err(()) if we already know this obligation failed. | |
216 | fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>) | |
217 | -> Result<(), ()> | |
218 | { | |
219 | if self.done_cache.contains(obligation.as_predicate()) { | |
220 | return Ok(()) | |
221 | } | |
222 | ||
223 | match self.waiting_cache.entry(obligation.as_predicate().clone()) { | |
224 | Entry::Occupied(o) => { | |
225 | debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!", | |
226 | obligation, parent, o.get()); | |
227 | if let Some(parent) = parent { | |
228 | if self.nodes[o.get().get()].dependents.contains(&parent) { | |
229 | debug!("register_obligation_at({:?}, {:?}) - duplicate subobligation", | |
230 | obligation, parent); | |
231 | } else { | |
232 | self.nodes[o.get().get()].dependents.push(parent); | |
233 | } | |
234 | } | |
235 | if let NodeState::Error = self.nodes[o.get().get()].state.get() { | |
236 | Err(()) | |
237 | } else { | |
238 | Ok(()) | |
239 | } | |
240 | } | |
241 | Entry::Vacant(v) => { | |
242 | debug!("register_obligation_at({:?}, {:?}) - ok", | |
243 | obligation, parent); | |
244 | v.insert(NodeIndex::new(self.nodes.len())); | |
245 | self.cache_list.push(obligation.as_predicate().clone()); | |
246 | self.nodes.push(Node::new(parent, obligation)); | |
247 | Ok(()) | |
248 | } | |
249 | } | |
7453a54e SL |
250 | } |
251 | ||
252 | /// Convert all remaining obligations to the given error. | |
253 | /// | |
254 | /// This cannot be done during a snapshot. | |
54a0048b | 255 | pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> { |
7453a54e SL |
256 | assert!(!self.in_snapshot()); |
257 | let mut errors = vec![]; | |
258 | for index in 0..self.nodes.len() { | |
a7813a04 XL |
259 | if let NodeState::Pending = self.nodes[index].state.get() { |
260 | let backtrace = self.error_at(index); | |
54a0048b SL |
261 | errors.push(Error { |
262 | error: error.clone(), | |
263 | backtrace: backtrace, | |
264 | }); | |
7453a54e SL |
265 | } |
266 | } | |
267 | let successful_obligations = self.compress(); | |
268 | assert!(successful_obligations.is_empty()); | |
269 | errors | |
270 | } | |
271 | ||
272 | /// Returns the set of obligations that are in a pending state. | |
54a0048b SL |
273 | pub fn pending_obligations(&self) -> Vec<O> |
274 | where O: Clone | |
275 | { | |
276 | self.nodes | |
277 | .iter() | |
a7813a04 XL |
278 | .filter(|n| n.state.get() == NodeState::Pending) |
279 | .map(|n| n.obligation.clone()) | |
54a0048b | 280 | .collect() |
7453a54e SL |
281 | } |
282 | ||
a7813a04 XL |
283 | /// Perform a pass through the obligation list. This must |
284 | /// be called in a loop until `outcome.stalled` is false. | |
7453a54e SL |
285 | /// |
286 | /// This CANNOT be unrolled (presently, at least). | |
a7813a04 XL |
287 | pub fn process_obligations<P>(&mut self, processor: &mut P) -> Outcome<O, P::Error> |
288 | where P: ObligationProcessor<Obligation=O> | |
7453a54e SL |
289 | { |
290 | debug!("process_obligations(len={})", self.nodes.len()); | |
291 | assert!(!self.in_snapshot()); // cannot unroll this action | |
292 | ||
293 | let mut errors = vec![]; | |
294 | let mut stalled = true; | |
295 | ||
7453a54e | 296 | for index in 0..self.nodes.len() { |
7453a54e | 297 | debug!("process_obligations: node {} == {:?}", |
54a0048b | 298 | index, |
a7813a04 XL |
299 | self.nodes[index]); |
300 | ||
301 | let result = match self.nodes[index] { | |
302 | Node { state: ref _state, ref mut obligation, .. } | |
303 | if _state.get() == NodeState::Pending => | |
304 | { | |
305 | processor.process_obligation(obligation) | |
7453a54e | 306 | } |
a7813a04 | 307 | _ => continue |
7453a54e SL |
308 | }; |
309 | ||
54a0048b SL |
310 | debug!("process_obligations: node {} got result {:?}", |
311 | index, | |
312 | result); | |
7453a54e SL |
313 | |
314 | match result { | |
315 | Ok(None) => { | |
316 | // no change in state | |
317 | } | |
318 | Ok(Some(children)) => { | |
319 | // if we saw a Some(_) result, we are not (yet) stalled | |
320 | stalled = false; | |
a7813a04 XL |
321 | self.nodes[index].state.set(NodeState::Success); |
322 | ||
323 | for child in children { | |
324 | let st = self.register_obligation_at( | |
325 | child, | |
326 | Some(NodeIndex::new(index)) | |
327 | ); | |
328 | if let Err(()) = st { | |
329 | // error already reported - propagate it | |
330 | // to our node. | |
331 | self.error_at(index); | |
332 | } | |
333 | } | |
7453a54e SL |
334 | } |
335 | Err(err) => { | |
a7813a04 | 336 | let backtrace = self.error_at(index); |
54a0048b SL |
337 | errors.push(Error { |
338 | error: err, | |
339 | backtrace: backtrace, | |
340 | }); | |
7453a54e SL |
341 | } |
342 | } | |
343 | } | |
344 | ||
a7813a04 XL |
345 | self.mark_as_waiting(); |
346 | self.process_cycles(processor); | |
347 | ||
7453a54e | 348 | // Now we have to compress the result |
a7813a04 | 349 | let completed_obligations = self.compress(); |
7453a54e SL |
350 | |
351 | debug!("process_obligations: complete"); | |
352 | ||
353 | Outcome { | |
a7813a04 | 354 | completed: completed_obligations, |
7453a54e SL |
355 | errors: errors, |
356 | stalled: stalled, | |
357 | } | |
358 | } | |
359 | ||
a7813a04 XL |
360 | /// Mark all NodeState::Success nodes as NodeState::Done and |
361 | /// report all cycles between them. This should be called | |
362 | /// after `mark_as_waiting` marks all nodes with pending | |
363 | /// subobligations as NodeState::Waiting. | |
364 | fn process_cycles<P>(&mut self, processor: &mut P) | |
365 | where P: ObligationProcessor<Obligation=O> | |
366 | { | |
367 | let mut stack = self.scratch.take().unwrap(); | |
368 | ||
369 | for node in 0..self.nodes.len() { | |
370 | self.find_cycles_from_node(&mut stack, processor, node); | |
7453a54e SL |
371 | } |
372 | ||
a7813a04 | 373 | self.scratch = Some(stack); |
7453a54e SL |
374 | } |
375 | ||
a7813a04 XL |
376 | fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, |
377 | processor: &mut P, index: usize) | |
378 | where P: ObligationProcessor<Obligation=O> | |
379 | { | |
380 | let node = &self.nodes[index]; | |
381 | let state = node.state.get(); | |
382 | match state { | |
383 | NodeState::OnDfsStack => { | |
384 | let index = | |
385 | stack.iter().rposition(|n| *n == index).unwrap(); | |
386 | // I need a Clone closure | |
387 | #[derive(Clone)] | |
388 | struct GetObligation<'a, O: 'a>(&'a [Node<O>]); | |
389 | impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> { | |
390 | type Output = &'a O; | |
391 | extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O { | |
392 | &self.0[*args.0].obligation | |
393 | } | |
394 | } | |
395 | impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> { | |
396 | extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O { | |
397 | &self.0[*args.0].obligation | |
7453a54e SL |
398 | } |
399 | } | |
7453a54e | 400 | |
a7813a04 XL |
401 | processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)), |
402 | PhantomData); | |
403 | } | |
404 | NodeState::Success => { | |
405 | node.state.set(NodeState::OnDfsStack); | |
406 | stack.push(index); | |
407 | if let Some(parent) = node.parent { | |
408 | self.find_cycles_from_node(stack, processor, parent.get()); | |
409 | } | |
410 | for dependent in &node.dependents { | |
411 | self.find_cycles_from_node(stack, processor, dependent.get()); | |
412 | } | |
413 | stack.pop(); | |
414 | node.state.set(NodeState::Done); | |
415 | }, | |
416 | NodeState::Waiting | NodeState::Pending => { | |
417 | // this node is still reachable from some pending node. We | |
418 | // will get to it when they are all processed. | |
419 | } | |
420 | NodeState::Done | NodeState::Error => { | |
421 | // already processed that node | |
422 | } | |
423 | }; | |
7453a54e SL |
424 | } |
425 | ||
426 | /// Returns a vector of obligations for `p` and all of its | |
427 | /// ancestors, putting them into the error state in the process. | |
a7813a04 XL |
428 | fn error_at(&mut self, p: usize) -> Vec<O> { |
429 | let mut error_stack = self.scratch.take().unwrap(); | |
7453a54e | 430 | let mut trace = vec![]; |
a7813a04 XL |
431 | |
432 | let mut n = p; | |
7453a54e | 433 | loop { |
a7813a04 XL |
434 | self.nodes[n].state.set(NodeState::Error); |
435 | trace.push(self.nodes[n].obligation.clone()); | |
436 | error_stack.extend(self.nodes[n].dependents.iter().map(|x| x.get())); | |
7453a54e SL |
437 | |
438 | // loop to the parent | |
a7813a04 XL |
439 | match self.nodes[n].parent { |
440 | Some(q) => n = q.get(), | |
441 | None => break | |
442 | } | |
443 | } | |
444 | ||
445 | loop { | |
446 | // non-standard `while let` to bypass #6393 | |
447 | let i = match error_stack.pop() { | |
448 | Some(i) => i, | |
449 | None => break | |
450 | }; | |
451 | ||
452 | let node = &self.nodes[i]; | |
453 | ||
454 | match node.state.get() { | |
455 | NodeState::Error => continue, | |
456 | _ => node.state.set(NodeState::Error) | |
457 | } | |
458 | ||
459 | error_stack.extend( | |
460 | node.dependents.iter().cloned().chain(node.parent).map(|x| x.get()) | |
461 | ); | |
462 | } | |
463 | ||
464 | self.scratch = Some(error_stack); | |
465 | trace | |
466 | } | |
467 | ||
468 | /// Marks all nodes that depend on a pending node as NodeState;:Waiting. | |
469 | fn mark_as_waiting(&self) { | |
470 | for node in &self.nodes { | |
471 | if node.state.get() == NodeState::Waiting { | |
472 | node.state.set(NodeState::Success); | |
473 | } | |
474 | } | |
475 | ||
476 | for node in &self.nodes { | |
477 | if node.state.get() == NodeState::Pending { | |
478 | self.mark_as_waiting_from(node) | |
7453a54e SL |
479 | } |
480 | } | |
481 | } | |
482 | ||
a7813a04 XL |
483 | fn mark_as_waiting_from(&self, node: &Node<O>) { |
484 | match node.state.get() { | |
485 | NodeState::Pending | NodeState::Done => {}, | |
486 | NodeState::Waiting | NodeState::Error | NodeState::OnDfsStack => return, | |
487 | NodeState::Success => { | |
488 | node.state.set(NodeState::Waiting); | |
489 | } | |
490 | } | |
491 | ||
492 | if let Some(parent) = node.parent { | |
493 | self.mark_as_waiting_from(&self.nodes[parent.get()]); | |
494 | } | |
495 | ||
496 | for dependent in &node.dependents { | |
497 | self.mark_as_waiting_from(&self.nodes[dependent.get()]); | |
498 | } | |
499 | } | |
500 | ||
7453a54e SL |
501 | /// Compresses the vector, removing all popped nodes. This adjusts |
502 | /// the indices and hence invalidates any outstanding | |
503 | /// indices. Cannot be used during a transaction. | |
a7813a04 XL |
504 | /// |
505 | /// Beforehand, all nodes must be marked as `Done` and no cycles | |
506 | /// on these nodes may be present. This is done by e.g. `process_cycles`. | |
507 | #[inline(never)] | |
7453a54e SL |
508 | fn compress(&mut self) -> Vec<O> { |
509 | assert!(!self.in_snapshot()); // didn't write code to unroll this action | |
7453a54e | 510 | |
7453a54e | 511 | let nodes_len = self.nodes.len(); |
a7813a04 XL |
512 | let mut node_rewrites: Vec<_> = self.scratch.take().unwrap(); |
513 | node_rewrites.extend(0..nodes_len); | |
514 | let mut dead_nodes = 0; | |
7453a54e | 515 | |
a7813a04 XL |
516 | // Now move all popped nodes to the end. Try to keep the order. |
517 | // | |
518 | // LOOP INVARIANT: | |
519 | // self.nodes[0..i - dead_nodes] are the first remaining nodes | |
520 | // self.nodes[i - dead_nodes..i] are all dead | |
521 | // self.nodes[i..] are unchanged | |
522 | for i in 0..self.nodes.len() { | |
523 | match self.nodes[i].state.get() { | |
524 | NodeState::Done => { | |
525 | self.waiting_cache.remove(self.nodes[i].obligation.as_predicate()); | |
526 | // FIXME(HashMap): why can't I get my key back? | |
527 | self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone()); | |
528 | } | |
529 | NodeState::Error => { | |
530 | // We *intentionally* remove the node from the cache at this point. Otherwise | |
531 | // tests must come up with a different type on every type error they | |
532 | // check against. | |
533 | self.waiting_cache.remove(self.nodes[i].obligation.as_predicate()); | |
534 | } | |
535 | _ => {} | |
7453a54e | 536 | } |
7453a54e | 537 | |
7453a54e | 538 | if self.nodes[i].is_popped() { |
a7813a04 | 539 | node_rewrites[i] = nodes_len; |
7453a54e | 540 | dead_nodes += 1; |
a7813a04 XL |
541 | } else { |
542 | if dead_nodes > 0 { | |
543 | self.nodes.swap(i, i - dead_nodes); | |
544 | node_rewrites[i] -= dead_nodes; | |
545 | } | |
7453a54e SL |
546 | } |
547 | } | |
548 | ||
549 | // No compression needed. | |
a7813a04 XL |
550 | if dead_nodes == 0 { |
551 | node_rewrites.truncate(0); | |
552 | self.scratch = Some(node_rewrites); | |
7453a54e SL |
553 | return vec![]; |
554 | } | |
555 | ||
7453a54e SL |
556 | // Pop off all the nodes we killed and extract the success |
557 | // stories. | |
54a0048b SL |
558 | let successful = (0..dead_nodes) |
559 | .map(|_| self.nodes.pop().unwrap()) | |
560 | .flat_map(|node| { | |
a7813a04 | 561 | match node.state.get() { |
54a0048b | 562 | NodeState::Error => None, |
a7813a04 XL |
563 | NodeState::Done => Some(node.obligation), |
564 | _ => unreachable!() | |
54a0048b SL |
565 | } |
566 | }) | |
a7813a04 XL |
567 | .collect(); |
568 | self.apply_rewrites(&node_rewrites); | |
569 | ||
570 | node_rewrites.truncate(0); | |
571 | self.scratch = Some(node_rewrites); | |
572 | ||
573 | successful | |
574 | } | |
575 | ||
576 | fn apply_rewrites(&mut self, node_rewrites: &[usize]) { | |
577 | let nodes_len = node_rewrites.len(); | |
7453a54e | 578 | |
7453a54e | 579 | for node in &mut self.nodes { |
a7813a04 | 580 | if let Some(index) = node.parent { |
7453a54e | 581 | let new_index = node_rewrites[index.get()]; |
a7813a04 XL |
582 | if new_index >= nodes_len { |
583 | // parent dead due to error | |
584 | node.parent = None; | |
585 | } else { | |
586 | node.parent = Some(NodeIndex::new(new_index)); | |
587 | } | |
7453a54e SL |
588 | } |
589 | ||
a7813a04 XL |
590 | let mut i = 0; |
591 | while i < node.dependents.len() { | |
592 | let new_index = node_rewrites[node.dependents[i].get()]; | |
593 | if new_index >= nodes_len { | |
594 | node.dependents.swap_remove(i); | |
595 | } else { | |
596 | node.dependents[i] = NodeIndex::new(new_index); | |
597 | i += 1; | |
598 | } | |
599 | } | |
7453a54e SL |
600 | } |
601 | ||
a7813a04 XL |
602 | let mut kill_list = vec![]; |
603 | for (predicate, index) in self.waiting_cache.iter_mut() { | |
604 | let new_index = node_rewrites[index.get()]; | |
605 | if new_index >= nodes_len { | |
606 | kill_list.push(predicate.clone()); | |
607 | } else { | |
608 | *index = NodeIndex::new(new_index); | |
609 | } | |
610 | } | |
611 | ||
612 | for predicate in kill_list { self.waiting_cache.remove(&predicate); } | |
7453a54e SL |
613 | } |
614 | } | |
615 | ||
616 | impl<O> Node<O> { | |
a7813a04 | 617 | fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> { |
7453a54e | 618 | Node { |
a7813a04 | 619 | obligation: obligation, |
7453a54e | 620 | parent: parent, |
a7813a04 XL |
621 | state: Cell::new(NodeState::Pending), |
622 | dependents: vec![], | |
7453a54e SL |
623 | } |
624 | } | |
625 | ||
626 | fn is_popped(&self) -> bool { | |
a7813a04 XL |
627 | match self.state.get() { |
628 | NodeState::Pending | NodeState::Waiting => false, | |
629 | NodeState::Error | NodeState::Done => true, | |
630 | NodeState::OnDfsStack | NodeState::Success => unreachable!() | |
7453a54e SL |
631 | } |
632 | } | |
633 | } |