//! in the first place). See README.md for a general overview of how
//! to use this class.
-use fnv::{FnvHashMap, FnvHashSet};
+use fx::{FxHashMap, FxHashSet};
use std::cell::Cell;
use std::collections::hash_map::Entry;
obligation: &mut Self::Obligation)
-> Result<Option<Vec<Self::Obligation>>, Self::Error>;
- fn process_backedge<'c, I>(&mut self, cycle: I,
+ /// As we do the cycle check, we invoke this callback when we
+ /// encounter an actual cycle. `cycle` is an iterator that starts
+ /// at the start of the cycle in the stack and walks **toward the
+ /// top**.
+ ///
+ /// 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>;
}
/// backtrace iterator (which uses `split_at`).
nodes: Vec<Node<O>>,
/// A cache of predicates that have been successfully completed.
- done_cache: FnvHashSet<O::Predicate>,
+ done_cache: FxHashSet<O::Predicate>,
/// An cache of the nodes in `nodes`, indexed by predicate.
- waiting_cache: FnvHashMap<O::Predicate, NodeIndex>,
+ waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
/// A list of the obligations added in snapshots, to allow
/// for their removal.
cache_list: Vec<O::Predicate>,
ObligationForest {
nodes: vec![],
snapshots: vec![],
- done_cache: FnvHashSet(),
- waiting_cache: FnvHashMap(),
+ done_cache: FxHashSet(),
+ waiting_cache: FxHashMap(),
cache_list: vec![],
scratch: Some(vec![]),
}
}
}
Entry::Vacant(v) => {
- debug!("register_obligation_at({:?}, {:?}) - ok",
- obligation, parent);
+ debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
+ obligation, parent, self.nodes.len());
v.insert(NodeIndex::new(self.nodes.len()));
self.cache_list.push(obligation.as_predicate().clone());
self.nodes.push(Node::new(parent, obligation));
where P: ObligationProcessor<Obligation=O>
{
let mut stack = self.scratch.take().unwrap();
+ debug_assert!(stack.is_empty());
+
+ debug!("process_cycles()");
- for node in 0..self.nodes.len() {
- self.find_cycles_from_node(&mut stack, processor, node);
+ for index in 0..self.nodes.len() {
+ // For rustc-benchmarks/inflate-0.1.0 this state test is extremely
+ // hot and the state is almost always `Pending` or `Waiting`. It's
+ // a win to handle the no-op cases immediately to avoid the cost of
+ // the function call.
+ let state = self.nodes[index].state.get();
+ match state {
+ NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {},
+ _ => self.find_cycles_from_node(&mut stack, processor, index),
+ }
}
+ debug!("process_cycles: complete");
+
+ debug_assert!(stack.is_empty());
self.scratch = Some(stack);
}
NodeState::OnDfsStack => {
let index =
stack.iter().rposition(|n| *n == index).unwrap();
- // I need a Clone closure
- #[derive(Clone)]
- struct GetObligation<'a, O: 'a>(&'a [Node<O>]);
- impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
- type Output = &'a O;
- extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
- &self.0[*args.0].obligation
- }
- }
- impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
- extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
- &self.0[*args.0].obligation
- }
- }
-
processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
PhantomData);
}
trace
}
- /// Marks all nodes that depend on a pending node as NodeState;:Waiting.
+ #[inline]
+ fn mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
+ if let Some(parent) = node.parent {
+ self.mark_as_waiting_from(&self.nodes[parent.get()]);
+ }
+
+ for dependent in &node.dependents {
+ self.mark_as_waiting_from(&self.nodes[dependent.get()]);
+ }
+ }
+
+ /// Marks all nodes that depend on a pending node as NodeState::Waiting.
fn mark_as_waiting(&self) {
for node in &self.nodes {
if node.state.get() == NodeState::Waiting {
for node in &self.nodes {
if node.state.get() == NodeState::Pending {
- self.mark_as_waiting_from(node)
+ self.mark_neighbors_as_waiting_from(node);
}
}
}
fn mark_as_waiting_from(&self, node: &Node<O>) {
match node.state.get() {
- NodeState::Pending | NodeState::Done => {},
NodeState::Waiting | NodeState::Error | NodeState::OnDfsStack => return,
- NodeState::Success => {
- node.state.set(NodeState::Waiting);
- }
- }
-
- if let Some(parent) = node.parent {
- self.mark_as_waiting_from(&self.nodes[parent.get()]);
+ NodeState::Success => node.state.set(NodeState::Waiting),
+ NodeState::Pending | NodeState::Done => {},
}
- for dependent in &node.dependents {
- self.mark_as_waiting_from(&self.nodes[dependent.get()]);
- }
+ self.mark_neighbors_as_waiting_from(node);
}
/// Compresses the vector, removing all popped nodes. This adjusts
// self.nodes[i..] are unchanged
for i in 0..self.nodes.len() {
match self.nodes[i].state.get() {
+ NodeState::Pending | NodeState::Waiting => {
+ if dead_nodes > 0 {
+ self.nodes.swap(i, i - dead_nodes);
+ node_rewrites[i] -= dead_nodes;
+ }
+ }
NodeState::Done => {
self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
// FIXME(HashMap): why can't I get my key back?
self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
+ node_rewrites[i] = nodes_len;
+ dead_nodes += 1;
}
NodeState::Error => {
// We *intentionally* remove the node from the cache at this point. Otherwise
// tests must come up with a different type on every type error they
// check against.
self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
+ node_rewrites[i] = nodes_len;
+ dead_nodes += 1;
}
- _ => {}
- }
-
- if self.nodes[i].is_popped() {
- node_rewrites[i] = nodes_len;
- dead_nodes += 1;
- } else {
- if dead_nodes > 0 {
- self.nodes.swap(i, i - dead_nodes);
- node_rewrites[i] -= dead_nodes;
- }
+ NodeState::OnDfsStack | NodeState::Success => unreachable!()
}
}
dependents: vec![],
}
}
+}
+
+// I need a Clone closure
+#[derive(Clone)]
+struct GetObligation<'a, O: 'a>(&'a [Node<O>]);
+
+impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
+ type Output = &'a O;
+ extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
+ &self.0[*args.0].obligation
+ }
+}
- fn is_popped(&self) -> bool {
- match self.state.get() {
- NodeState::Pending | NodeState::Waiting => false,
- NodeState::Error | NodeState::Done => true,
- NodeState::OnDfsStack | NodeState::Success => unreachable!()
- }
+impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
+ extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
+ &self.0[*args.0].obligation
}
}
projects / rust.git / blobdiff