Rollup merge of #41249 - GuillaumeGomez:rustdoc-render, r=steveklabnik,frewsxcv

[rust.git] / src / librustc_data_structures / obligation_forest / mod.rs

diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index a2bfa784e8aed0725ca6e50034fd096d3b2703a7..3515e5c5ede35a3f9c67fc4692aa33544527f787 100644 (file)
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -15,7 +15,7 @@
 //! 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;
@@ -43,7 +43,16 @@ fn process_obligation(&mut self,
                           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>;
 }
@@ -68,9 +77,9 @@ pub struct ObligationForest<O: ForestObligation> {
     /// 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>,
@@ -158,8 +167,8 @@ pub fn new() -> ObligationForest<O> {
         ObligationForest {
             nodes: vec![],
             snapshots: vec![],
-            done_cache: FnvHashSet(),
-            waiting_cache: FnvHashMap(),
+            done_cache: FxHashSet(),
+            waiting_cache: FxHashMap(),
             cache_list: vec![],
             scratch: Some(vec![]),
         }
@@ -239,8 +248,8 @@ fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
                 }
             }
             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));
@@ -376,6 +385,9 @@ fn process_cycles<P>(&mut self, processor: &mut P)
         where P: ObligationProcessor<Obligation=O>
     {
         let mut stack = self.scratch.take().unwrap();
+        debug_assert!(stack.is_empty());
+
+        debug!("process_cycles()");
 
         for index in 0..self.nodes.len() {
             // For rustc-benchmarks/inflate-0.1.0 this state test is extremely
@@ -389,6 +401,9 @@ fn process_cycles<P>(&mut self, processor: &mut P)
             }
         }
 
+        debug!("process_cycles: complete");
+
+        debug_assert!(stack.is_empty());
         self.scratch = Some(stack);
     }
 
@@ -402,21 +417,6 @@ fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>,
             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);
             }
@@ -645,3 +645,20 @@ fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
         }
     }
 }
+
+// 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
+    }
+}