Auto merge of #53255 - orium:fix-bug-overflow-send, r=arielb1

Add a per-tree error cache to the obligation forest

This implements part of what @nikomatsakis mentioned in  https://github.com/rust-lang/rust/pull/30533#issuecomment-170705871:

> 1. If you find that a new obligation is a duplicate of one already in the tree, the proper processing is:
>      * if that other location is your parent, you should abort with a cycle error (or accept it, if coinductive)
>      * if that other location is not an ancestor, you can safely ignore the new obligation

In particular it implements the "if that other location is your parent accept it, if coinductive" part.  This fixes #40827.

I have to say that I'm not 100% confident that this is rock solid.  This is my first pull request :tada:, and I didn't know anything about the trait resolver before this.  In particular I'm not totally sure that comparing predicates is enough (for instance, do we need to compare `param_env` as well?).  Also, I'm not sure what @nikomatsakis mentions [here](https://github.com/rust-lang/rust/issues/30977#issue-127091096), but it might be something that affects this PR:

> In particular, I am wary of getting things wrong around inference variables! We can always add things to the set in their current state, and if unifications occur then the obligation is just kind of out-of-date, but I want to be sure we don't accidentally fail to notice that something is our ancestor. I decided this was subtle enough to merit its own PR.

Anyway, go ahead and review :slightly_smiling_face:.

Ref #30977.

# Performance

We are now copying vectors around, so I decided to do some benchmarking.  A simple benchmark shows that this does not seem to affect performance in a measurable way:

I ran `cargo clean && cargo build` 20 times on actix-web (84b27db) and these are the results:

```text
rustc master:

            Mean        Std.Dev.    Min         Median      Max
real        66.637      2.996       57.220      67.714      69.314
user        307.293     14.741      258.093     312.209     320.702
sys         12.524      0.653       10.499      12.726      13.193

rustc fix-bug-overflow-send:

            Mean        Std.Dev.    Min         Median      Max
real        66.297      4.310       53.532      67.516      70.348
user        306.812     22.371      236.917     314.748     326.229
sys         12.757      0.952       9.671       13.125      13.544
```

I will do a more comprehensive benchmark (compiling rustc stage1) and post the results.

r? @nikomatsakis, @nnethercote

PS: It is better to review this commit-by-commit.

2 files changed, 76 insertions, 25 deletions

diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 7ef88852685..f159857e744 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -65,6 +65,12 @@ pub enum ProcessResult<O, E> {
     Error(E),
 }
 
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+struct ObligationTreeId(usize);
+
+type ObligationTreeIdGenerator =
+    ::std::iter::Map<::std::ops::RangeFrom<usize>, fn(usize) -> ObligationTreeId>;
+
 pub struct ObligationForest<O: ForestObligation> {
     /// The list of obligations. In between calls to
     /// `process_obligations`, this list only contains nodes in the
@@ -79,11 +85,25 @@ pub struct ObligationForest<O: ForestObligation> {
     /// at a higher index than its parent. This is needed by the
     /// backtrace iterator (which uses `split_at`).
     nodes: Vec<Node<O>>,
+
     /// A cache of predicates that have been successfully completed.
     done_cache: FxHashSet<O::Predicate>,
+
     /// An cache of the nodes in `nodes`, indexed by predicate.
     waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
+
     scratch: Option<Vec<usize>>,
+
+    obligation_tree_id_generator: ObligationTreeIdGenerator,
+
+    /// Per tree error cache.  This is used to deduplicate errors,
+    /// which is necessary to avoid trait resolution overflow in
+    /// some cases.
+    ///
+    /// See [this][details] for details.
+    ///
+    /// [details]: https://github.com/rust-lang/rust/pull/53255#issuecomment-421184780
+    error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::Predicate>>,
 }
 
 #[derive(Debug)]
@@ -99,6 +119,9 @@ struct Node<O> {
     /// Obligations that depend on this obligation for their
     /// completion. They must all be in a non-pending state.
     dependents: Vec<NodeIndex>,
+
+    /// Identifier of the obligation tree to which this node belongs.
+    obligation_tree_id: ObligationTreeId,
 }
 
 /// The state of one node in some tree within the forest. This
@@ -165,6 +188,8 @@ impl<O: ForestObligation> ObligationForest<O> {
             done_cache: FxHashSet(),
             waiting_cache: FxHashMap(),
             scratch: Some(vec![]),
+            obligation_tree_id_generator: (0..).map(|i| ObligationTreeId(i)),
+            error_cache: FxHashMap(),
         }
     }
 
@@ -187,7 +212,7 @@ impl<O: ForestObligation> ObligationForest<O> {
                               -> Result<(), ()>
     {
         if self.done_cache.contains(obligation.as_predicate()) {
-            return Ok(())
+            return Ok(());
         }
 
         match self.waiting_cache.entry(obligation.as_predicate().clone()) {
@@ -214,9 +239,29 @@ impl<O: ForestObligation> ObligationForest<O> {
             Entry::Vacant(v) => {
                 debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
                        obligation, parent, self.nodes.len());
-                v.insert(NodeIndex::new(self.nodes.len()));
-                self.nodes.push(Node::new(parent, obligation));
-                Ok(())
+
+                let obligation_tree_id = match parent {
+                    Some(p) => {
+                        let parent_node = &self.nodes[p.get()];
+                        parent_node.obligation_tree_id
+                    }
+                    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);
+
+                if already_failed {
+                    Err(())
+                } else {
+                    v.insert(NodeIndex::new(self.nodes.len()));
+                    self.nodes.push(Node::new(parent, obligation, obligation_tree_id));
+                    Ok(())
+                }
             }
         }
     }
@@ -251,6 +296,15 @@ impl<O: ForestObligation> ObligationForest<O> {
             .collect()
     }
 
+    fn insert_into_error_cache(&mut self, node_index: usize) {
+        let node = &self.nodes[node_index];
+
+        self.error_cache
+            .entry(node.obligation_tree_id)
+            .or_insert_with(|| FxHashSet())
+            .insert(node.obligation.as_predicate().clone());
+    }
+
     /// Perform a pass through the obligation list. This must
     /// be called in a loop until `outcome.stalled` is false.
     ///
@@ -264,22 +318,15 @@ impl<O: ForestObligation> ObligationForest<O> {
         let mut stalled = true;
 
         for index in 0..self.nodes.len() {
-            debug!("process_obligations: node {} == {:?}",
-                   index,
-                   self.nodes[index]);
+            debug!("process_obligations: node {} == {:?}", index, self.nodes[index]);
 
             let result = match self.nodes[index] {
-                Node { state: ref _state, ref mut obligation, .. }
-                    if _state.get() == NodeState::Pending =>
-                {
-                    processor.process_obligation(obligation)
-                }
+                Node { ref state, ref mut obligation, .. } if state.get() == NodeState::Pending =>
+                    processor.process_obligation(obligation),
                 _ => continue
             };
 
-            debug!("process_obligations: node {} got result {:?}",
-                   index,
-                   result);
+            debug!("process_obligations: node {} got result {:?}", index, result);
 
             match result {
                 ProcessResult::Unchanged => {
@@ -420,13 +467,13 @@ impl<O: ForestObligation> ObligationForest<O> {
         }
 
         while let Some(i) = error_stack.pop() {
-            let node = &self.nodes[i];
-
-            match node.state.get() {
+            match self.nodes[i].state.get() {
                 NodeState::Error => continue,
-                _ => node.state.set(NodeState::Error)
+                _ => self.nodes[i].state.set(NodeState::Error),
             }
 
+            let node = &self.nodes[i];
+
             error_stack.extend(
                 node.parent.iter().chain(node.dependents.iter()).map(|x| x.get())
             );
@@ -514,6 +561,7 @@ impl<O: ForestObligation> ObligationForest<O> {
                     self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
                     node_rewrites[i] = nodes_len;
                     dead_nodes += 1;
+                    self.insert_into_error_cache(i);
                 }
                 NodeState::OnDfsStack | NodeState::Success => unreachable!()
             }
@@ -587,12 +635,17 @@ impl<O: ForestObligation> ObligationForest<O> {
 }
 
 impl<O> Node<O> {
-    fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
+    fn new(
+        parent: Option<NodeIndex>,
+        obligation: O,
+        obligation_tree_id: ObligationTreeId
+    ) -> Node<O> {
         Node {
             obligation,
             state: Cell::new(NodeState::Pending),
             parent,
             dependents: vec![],
+            obligation_tree_id,
         }
     }
 }
diff --git a/src/librustc_data_structures/obligation_forest/test.rs b/src/librustc_data_structures/obligation_forest/test.rs
index 527a1ef0ec4..c27a65e3431 100644
--- a/src/librustc_data_structures/obligation_forest/test.rs
+++ b/src/librustc_data_structures/obligation_forest/test.rs
@@ -59,8 +59,9 @@ impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O,
 
     fn process_backedge<'c, I>(&mut self, _cycle: I,
                                _marker: PhantomData<&'c Self::Obligation>)
-        where I: Clone + Iterator<Item=&'c Self::Obligation> {
-        }
+        where I: Clone + Iterator<Item=&'c Self::Obligation>
+    {
+    }
 }
 
 
@@ -350,11 +351,8 @@ fn done_dependency() {
         }, |_|{}));
     assert_eq!(ok, vec!["(A,B,C): Sized"]);
     assert_eq!(err.len(), 0);
-
-
 }
 
-
 #[test]
 fn orphan() {
     // check that orphaned nodes are handled correctly