diff options
| -rw-r--r-- | src/librustc_data_structures/obligation_forest/mod.rs | 191 |
1 files changed, 80 insertions, 111 deletions
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs index 92bd196aaa3..974d9dcfae4 100644 --- a/src/librustc_data_structures/obligation_forest/mod.rs +++ b/src/librustc_data_structures/obligation_forest/mod.rs @@ -129,7 +129,7 @@ type ObligationTreeIdGenerator = pub struct ObligationForest<O: ForestObligation> { /// The list of obligations. In between calls to `process_obligations`, - /// this list only contains nodes in the `Pending` or `Success` state. + /// this list only contains nodes in the `Pending` or `Waiting` state. /// /// `usize` indices are used here and throughout this module, rather than /// `rustc_index::newtype_index!` indices, because this code is hot enough @@ -137,10 +137,6 @@ pub struct ObligationForest<O: ForestObligation> { /// significant, and space considerations are not important. nodes: Vec<Node<O>>, - /// The process generation is 1 on the first call to `process_obligations`, - /// 2 on the second call, etc. - gen: u32, - /// A cache of predicates that have been successfully completed. done_cache: FxHashSet<O::Predicate>, @@ -196,9 +192,9 @@ impl<O> Node<O> { } } -/// The state of one node in some tree within the forest. This -/// represents the current state of processing for the obligation (of -/// type `O`) associated with this node. +/// The state of one node in some tree within the forest. This represents the +/// current state of processing for the obligation (of type `O`) associated +/// with this node. /// /// The non-`Error` state transitions are as follows. /// ``` @@ -210,51 +206,47 @@ impl<O> Node<O> { /// | /// | process_obligations() /// v -/// Success(not_waiting()) -/// | | -/// | | mark_still_waiting_nodes() +/// Success +/// | ^ +/// | | mark_successes() /// | v -/// | Success(still_waiting()) -/// | | -/// | | compress() -/// v v +/// | Waiting +/// | +/// | process_cycles() +/// v +/// Done +/// | +/// | compress() +/// v /// (Removed) /// ``` /// The `Error` state can be introduced in several places, via `error_at()`. /// /// Outside of `ObligationForest` methods, nodes should be either `Pending` or -/// `Success`. +/// `Waiting`. #[derive(Debug, Copy, Clone, PartialEq, Eq)] enum NodeState { /// This obligation has not yet been selected successfully. Cannot have /// subobligations. Pending, - /// This obligation was selected successfully, but it may be waiting on one - /// or more pending subobligations, as indicated by the `WaitingState`. - Success(WaitingState), + /// This obligation was selected successfully, but may or may not have + /// subobligations. + Success, + + /// This obligation was selected successfully, but it has a pending + /// subobligation. + Waiting, + + /// This obligation, along with its subobligations, are complete, and will + /// be removed in the next collection. + Done, /// This obligation was resolved to an error. It will be removed by the /// next compression step. Error, } -/// Indicates when a `Success` node was last (if ever) waiting on one or more -/// `Pending` nodes. The notion of "when" comes from `ObligationForest::gen`. -/// - 0: "Not waiting". This is a special value, set by `process_obligation`, -/// and usable because generation counting starts at 1. -/// - 1..ObligationForest::gen: "Was waiting" in a previous generation, but -/// waiting no longer. In other words, finished. -/// - ObligationForest::gen: "Still waiting" in this generation. -/// -/// Things to note about this encoding: -/// - Every time `ObligationForest::gen` is incremented, all the "still -/// waiting" nodes automatically become "was waiting". -/// - `ObligationForest::is_still_waiting` is very cheap. -/// -#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd)] -struct WaitingState(u32); - #[derive(Debug)] pub struct Outcome<O, E> { /// Obligations that were completely evaluated, including all @@ -291,7 +283,6 @@ impl<O: ForestObligation> ObligationForest<O> { pub fn new() -> ObligationForest<O> { ObligationForest { nodes: vec![], - gen: 0, done_cache: Default::default(), active_cache: Default::default(), node_rewrites: RefCell::new(vec![]), @@ -392,18 +383,6 @@ impl<O: ForestObligation> ObligationForest<O> { .insert(node.obligation.as_predicate().clone()); } - fn not_waiting() -> WaitingState { - WaitingState(0) - } - - fn still_waiting(&self) -> WaitingState { - WaitingState(self.gen) - } - - fn is_still_waiting(&self, waiting: WaitingState) -> bool { - waiting.0 == self.gen - } - /// Performs a pass through the obligation list. This must /// be called in a loop until `outcome.stalled` is false. /// @@ -416,8 +395,6 @@ impl<O: ForestObligation> ObligationForest<O> { where P: ObligationProcessor<Obligation = O>, { - self.gen += 1; - let mut errors = vec![]; let mut stalled = true; @@ -450,7 +427,7 @@ impl<O: ForestObligation> ObligationForest<O> { ProcessResult::Changed(children) => { // We are not (yet) stalled. stalled = false; - node.state.set(NodeState::Success(Self::not_waiting())); + node.state.set(NodeState::Success); for child in children { let st = self.register_obligation_at(child, Some(index)); @@ -479,7 +456,7 @@ impl<O: ForestObligation> ObligationForest<O> { }; } - self.mark_still_waiting_nodes(); + self.mark_successes(); self.process_cycles(processor); let completed = self.compress(do_completed); @@ -519,41 +496,50 @@ impl<O: ForestObligation> ObligationForest<O> { trace } - /// Mark all `Success` nodes that depend on a pending node as still - /// waiting. Upon completion, any `Success` nodes that aren't still waiting - /// can be removed by `compress`. - fn mark_still_waiting_nodes(&self) { + /// Mark all `Waiting` nodes as `Success`, except those that depend on a + /// pending node. + fn mark_successes(&self) { + // Convert all `Waiting` nodes to `Success`. + for node in &self.nodes { + if node.state.get() == NodeState::Waiting { + node.state.set(NodeState::Success); + } + } + + // Convert `Success` nodes that depend on a pending node back to + // `Waiting`. for node in &self.nodes { if node.state.get() == NodeState::Pending { // This call site is hot. - self.inlined_mark_dependents_as_still_waiting(node); + self.inlined_mark_dependents_as_waiting(node); } } } // This always-inlined function is for the hot call site. #[inline(always)] - fn inlined_mark_dependents_as_still_waiting(&self, node: &Node<O>) { + fn inlined_mark_dependents_as_waiting(&self, node: &Node<O>) { for &index in node.dependents.iter() { let node = &self.nodes[index]; - if let NodeState::Success(waiting) = node.state.get() { - if !self.is_still_waiting(waiting) { - node.state.set(NodeState::Success(self.still_waiting())); - // This call site is cold. - self.uninlined_mark_dependents_as_still_waiting(node); - } + let state = node.state.get(); + if state == NodeState::Success { + node.state.set(NodeState::Waiting); + // This call site is cold. + self.uninlined_mark_dependents_as_waiting(node); + } else { + debug_assert!(state == NodeState::Waiting || state == NodeState::Error) } } } // This never-inlined function is for the cold call site. #[inline(never)] - fn uninlined_mark_dependents_as_still_waiting(&self, node: &Node<O>) { - self.inlined_mark_dependents_as_still_waiting(node) + fn uninlined_mark_dependents_as_waiting(&self, node: &Node<O>) { + self.inlined_mark_dependents_as_waiting(node) } - /// Report cycles between all `Success` nodes that aren't still waiting. - /// This must be called after `mark_still_waiting_nodes`. + /// Report cycles between all `Success` nodes, and convert all `Success` + /// nodes to `Done`. This must be called after `mark_successes`. fn process_cycles<P>(&self, processor: &mut P) where P: ObligationProcessor<Obligation = O>, @@ -564,46 +550,35 @@ impl<O: ForestObligation> ObligationForest<O> { // For some benchmarks this state test is extremely hot. It's a win // to handle the no-op cases immediately to avoid the cost of the // function call. - if let NodeState::Success(waiting) = node.state.get() { - if !self.is_still_waiting(waiting) { - self.find_cycles_from_node(&mut stack, processor, index, index); - } + if node.state.get() == NodeState::Success { + self.find_cycles_from_node(&mut stack, processor, index); } } debug_assert!(stack.is_empty()); } - fn find_cycles_from_node<P>( - &self, - stack: &mut Vec<usize>, - processor: &mut P, - min_index: usize, - index: usize, - ) where + fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, index: usize) + where P: ObligationProcessor<Obligation = O>, { let node = &self.nodes[index]; - if let NodeState::Success(waiting) = node.state.get() { - if !self.is_still_waiting(waiting) { - match stack.iter().rposition(|&n| n == index) { - None => { - stack.push(index); - for &dep_index in node.dependents.iter() { - // The index check avoids re-considering a node. - if dep_index >= min_index { - self.find_cycles_from_node(stack, processor, min_index, dep_index); - } - } - stack.pop(); - } - Some(rpos) => { - // Cycle detected. - processor.process_backedge( - stack[rpos..].iter().map(GetObligation(&self.nodes)), - PhantomData, - ); + if node.state.get() == NodeState::Success { + match stack.iter().rposition(|&n| n == index) { + None => { + stack.push(index); + for &dep_index in node.dependents.iter() { + self.find_cycles_from_node(stack, processor, dep_index); } + stack.pop(); + node.state.set(NodeState::Done); + } + Some(rpos) => { + // Cycle detected. + processor.process_backedge( + stack[rpos..].iter().map(GetObligation(&self.nodes)), + PhantomData, + ); } } } @@ -611,8 +586,7 @@ impl<O: ForestObligation> ObligationForest<O> { /// Compresses the vector, removing all popped nodes. This adjusts the /// indices and hence invalidates any outstanding indices. `process_cycles` - /// must be run beforehand to remove any cycles on not-still-waiting - /// `Success` nodes. + /// must be run beforehand to remove any cycles on `Success` nodes. #[inline(never)] fn compress(&mut self, do_completed: DoCompleted) -> Option<Vec<O>> { let orig_nodes_len = self.nodes.len(); @@ -620,7 +594,7 @@ impl<O: ForestObligation> ObligationForest<O> { debug_assert!(node_rewrites.is_empty()); node_rewrites.extend(0..orig_nodes_len); let mut dead_nodes = 0; - let mut removed_success_obligations: Vec<O> = vec![]; + let mut removed_done_obligations: Vec<O> = vec![]; // Move removable nodes to the end, preserving the order of the // remaining nodes. @@ -632,19 +606,13 @@ impl<O: ForestObligation> ObligationForest<O> { for index in 0..orig_nodes_len { let node = &self.nodes[index]; match node.state.get() { - NodeState::Pending => { - if dead_nodes > 0 { - self.nodes.swap(index, index - dead_nodes); - node_rewrites[index] -= dead_nodes; - } - } - NodeState::Success(waiting) if self.is_still_waiting(waiting) => { + NodeState::Pending | NodeState::Waiting => { if dead_nodes > 0 { self.nodes.swap(index, index - dead_nodes); node_rewrites[index] -= dead_nodes; } } - NodeState::Success(_) => { + NodeState::Done => { // This lookup can fail because the contents of // `self.active_cache` are not guaranteed to match those of // `self.nodes`. See the comment in `process_obligation` @@ -658,7 +626,7 @@ impl<O: ForestObligation> ObligationForest<O> { } if do_completed == DoCompleted::Yes { // Extract the success stories. - removed_success_obligations.push(node.obligation.clone()); + removed_done_obligations.push(node.obligation.clone()); } node_rewrites[index] = orig_nodes_len; dead_nodes += 1; @@ -672,6 +640,7 @@ impl<O: ForestObligation> ObligationForest<O> { node_rewrites[index] = orig_nodes_len; dead_nodes += 1; } + NodeState::Success => unreachable!(), } } @@ -684,7 +653,7 @@ impl<O: ForestObligation> ObligationForest<O> { node_rewrites.truncate(0); self.node_rewrites.replace(node_rewrites); - if do_completed == DoCompleted::Yes { Some(removed_success_obligations) } else { None } + if do_completed == DoCompleted::Yes { Some(removed_done_obligations) } else { None } } fn apply_rewrites(&mut self, node_rewrites: &[usize]) { |