#[cfg(test)]
mod tests;
-pub trait ForestObligation : Clone + Debug {
- type Predicate : Clone + hash::Hash + Eq + Debug;
+pub trait ForestObligation: Clone + Debug {
+ type Predicate: Clone + hash::Hash + Eq + Debug;
fn as_predicate(&self) -> &Self::Predicate;
}
pub trait ObligationProcessor {
- type Obligation : ForestObligation;
- type Error : Debug;
+ type Obligation: ForestObligation;
+ type Error: Debug;
- fn process_obligation(&mut self,
- obligation: &mut Self::Obligation)
- -> ProcessResult<Self::Obligation, Self::Error>;
+ fn process_obligation(
+ &mut self,
+ obligation: &mut Self::Obligation,
+ ) -> ProcessResult<Self::Obligation, Self::Error>;
/// As we do the cycle check, we invoke this callback when we
/// encounter an actual cycle. `cycle` is an iterator that starts
/// In other words, if we had O1 which required O2 which required
/// O3 which required O1, we would give an iterator yielding O1,
/// O2, O3 (O1 is not yielded twice).
- fn process_backedge<'c, I>(&mut self,
- cycle: I,
- _marker: PhantomData<&'c Self::Obligation>)
- where I: Clone + Iterator<Item=&'c Self::Obligation>;
+ fn process_backedge<'c, I>(&mut self, cycle: I, _marker: PhantomData<&'c Self::Obligation>)
+ where
+ I: Clone + Iterator<Item = &'c Self::Obligation>;
}
/// The result type used by `process_obligation`.
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
/// 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>,
}
impl<O> Node<O> {
- fn new(
- parent: Option<usize>,
- obligation: O,
- obligation_tree_id: ObligationTreeId
- ) -> Node<O> {
+ fn new(parent: Option<usize>, obligation: O, obligation_tree_id: ObligationTreeId) -> Node<O> {
Node {
obligation,
state: Cell::new(NodeState::Pending),
- dependents:
- if let Some(parent_index) = parent {
- vec![parent_index]
- } else {
- vec![]
- },
+ dependents: if let Some(parent_index) = parent { vec![parent_index] } else { vec![] },
has_parent: parent.is_some(),
obligation_tree_id,
}
}
}
-/// 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.
/// ```
/// |
/// | 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
pub fn new() -> ObligationForest<O> {
ObligationForest {
nodes: vec![],
- gen: 0,
done_cache: Default::default(),
active_cache: Default::default(),
node_rewrites: RefCell::new(vec![]),
node.dependents.push(parent_index);
}
}
- if let NodeState::Error = node.state.get() {
- Err(())
- } else {
- Ok(())
- }
+ if let NodeState::Error = node.state.get() { Err(()) } else { Ok(()) }
}
Entry::Vacant(v) => {
let obligation_tree_id = match parent {
None => self.obligation_tree_id_generator.next().unwrap(),
};
- let already_failed =
- parent.is_some()
- && self.error_cache
- .get(&obligation_tree_id)
- .map(|errors| errors.contains(obligation.as_predicate()))
- .unwrap_or(false);
+ let already_failed = parent.is_some()
+ && self
+ .error_cache
+ .get(&obligation_tree_id)
+ .map(|errors| errors.contains(obligation.as_predicate()))
+ .unwrap_or(false);
if already_failed {
Err(())
/// Converts all remaining obligations to the given error.
pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
- let errors = self.nodes.iter().enumerate()
+ let errors = self
+ .nodes
+ .iter()
+ .enumerate()
.filter(|(_index, node)| node.state.get() == NodeState::Pending)
- .map(|(index, _node)| {
- Error {
- error: error.clone(),
- backtrace: self.error_at(index),
- }
- })
+ .map(|(index, _node)| Error { error: error.clone(), backtrace: self.error_at(index) })
.collect();
let successful_obligations = self.compress(DoCompleted::Yes);
/// Returns the set of obligations that are in a pending state.
pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P>
- where F: Fn(&O) -> P
+ where
+ F: Fn(&O) -> P,
{
- self.nodes.iter()
+ self.nodes
+ .iter()
.filter(|node| node.state.get() == NodeState::Pending)
.map(|node| f(&node.obligation))
.collect()
.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.
///
/// This _cannot_ be unrolled (presently, at least).
- pub fn process_obligations<P>(&mut self, processor: &mut P, do_completed: DoCompleted)
- -> Outcome<O, P::Error>
- where P: ObligationProcessor<Obligation=O>
+ pub fn process_obligations<P>(
+ &mut self,
+ processor: &mut P,
+ do_completed: DoCompleted,
+ ) -> Outcome<O, P::Error>
+ where
+ P: ObligationProcessor<Obligation = O>,
{
- self.gen += 1;
-
let mut errors = vec![];
let mut stalled = true;
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)
- );
+ let st = self.register_obligation_at(child, Some(index));
if let Err(()) = st {
// Error already reported - propagate it
// to our node.
}
ProcessResult::Error(err) => {
stalled = false;
- errors.push(Error {
- error: err,
- backtrace: self.error_at(index),
- });
+ errors.push(Error { error: err, backtrace: self.error_at(index) });
}
}
index += 1;
};
}
- self.mark_still_waiting_nodes();
+ self.mark_successes();
self.process_cycles(processor);
let completed = self.compress(do_completed);
- Outcome {
- completed,
- errors,
- stalled,
- }
+ Outcome { completed, errors, stalled }
}
/// Returns a vector of obligations for `p` and all of its
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>
+ where
+ P: ObligationProcessor<Obligation = O>,
{
let mut stack = vec![];
// 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 P: ObligationProcessor<Obligation=O>
+ 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,
+ );
}
}
}
/// 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();
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.
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`
}
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;
node_rewrites[index] = orig_nodes_len;
dead_nodes += 1;
}
+ NodeState::Success => unreachable!(),
}
}
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]) {
projects / rust.git / blobdiff