Rework collapse method to work correctly with more complex supertrait graphs

9 files changed, 265 insertions, 21 deletions

diff --git a/compiler/rustc_hir_typeck/src/method/probe.rs b/compiler/rustc_hir_typeck/src/method/probe.rs
index f16fb2c7674..b3e48fd5bb5 100644
--- a/compiler/rustc_hir_typeck/src/method/probe.rs
+++ b/compiler/rustc_hir_typeck/src/method/probe.rs
@@ -2112,34 +2112,59 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
         self_ty: Ty<'tcx>,
         probes: &[(&Candidate<'tcx>, ProbeResult)],
     ) -> Option<Pick<'tcx>> {
-        let mut child_pick = probes[0].0;
-        let mut supertraits: SsoHashSet<_> =
-            supertrait_def_ids(self.tcx, child_pick.item.trait_container(self.tcx)?).collect();
+        let mut child_candidate = probes[0].0;
+        let mut child_trait = child_candidate.item.trait_container(self.tcx)?;
+        let mut supertraits: SsoHashSet<_> = supertrait_def_ids(self.tcx, child_trait).collect();
+
+        let mut remaining_candidates: Vec<_> = probes[1..].iter().map(|&(p, _)| p).collect();
+        while !remaining_candidates.is_empty() {
+            let mut made_progress = false;
+            let mut next_round = vec![];
+
+            for remaining_candidate in remaining_candidates {
+                let remaining_trait = remaining_candidate.item.trait_container(self.tcx)?;
+                if supertraits.contains(&remaining_trait) {
+                    made_progress = true;
+                    continue;
+                }
 
-        // All other picks should be a supertrait of the `child_pick`.
-        // If it's not, then we update the `child_pick` and the `supertraits`
-        // list.
-        for (p, _) in &probes[1..] {
-            let p_container = p.item.trait_container(self.tcx)?;
-            if !supertraits.contains(&p_container) {
                 // This pick is not a supertrait of the `child_pick`.
-                // Check if it's a subtrait of the `child_pick`, which
-                // is sufficient to imply that all of the previous picks
-                // are also supertraits of this pick.
-                supertraits = supertrait_def_ids(self.tcx, p_container).collect();
-                if supertraits.contains(&child_pick.item.trait_container(self.tcx).unwrap()) {
-                    child_pick = *p;
-                } else {
-                    // `child_pick` is not a supertrait of this pick. Bail.
-                    return None;
+                // Check if it's a subtrait of the `child_pick`, instead.
+                // If it is, then it must have been a subtrait of every
+                // other pick we've eliminated at this point. It will
+                // take over at this point.
+                let remaining_trait_supertraits: SsoHashSet<_> =
+                    supertrait_def_ids(self.tcx, remaining_trait).collect();
+                if remaining_trait_supertraits.contains(&child_trait) {
+                    child_candidate = remaining_candidate;
+                    child_trait = remaining_trait;
+                    supertraits = remaining_trait_supertraits;
+                    made_progress = true;
+                    continue;
                 }
+
+                // `child_pick` is not a supertrait of this pick.
+                // Don't bail here, since we may be comparing two supertraits
+                // of a common subtrait. These two supertraits won't be related
+                // at all, but we will pick them up next round when we find their
+                // child as we continue iterating in this round.
+                next_round.push(remaining_candidate);
+            }
+
+            if made_progress {
+                // If we've made progress, iterate again.
+                remaining_candidates = next_round;
+            } else {
+                // Otherwise, we must have at least two candidates which
+                // are not related to each other at all.
+                return None;
             }
         }
 
         Some(Pick {
-            item: child_pick.item,
+            item: child_candidate.item,
             kind: TraitPick,
-            import_ids: child_pick.import_ids.clone(),
+            import_ids: child_candidate.import_ids.clone(),
             autoderefs: 0,
             autoref_or_ptr_adjustment: None,
             self_ty,
@@ -2147,7 +2172,7 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
             shadowed_candidates: probes
                 .iter()
                 .map(|(c, _)| c.item)
-                .filter(|item| item.def_id != child_pick.item.def_id)
+                .filter(|item| item.def_id != child_candidate.item.def_id)
                 .collect(),
             receiver_steps: None,
         })
diff --git a/tests/ui/methods/supertrait-shadowing/common-ancestor-2.rs b/tests/ui/methods/supertrait-shadowing/common-ancestor-2.rs
new file mode 100644
index 00000000000..91a64561824
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/common-ancestor-2.rs
@@ -0,0 +1,32 @@
+//@ run-pass
+//@ check-run-results
+
+#![feature(supertrait_item_shadowing)]
+#![warn(supertrait_item_shadowing_usage)]
+#![allow(dead_code)]
+
+trait A {
+    fn hello(&self) {
+        println!("A");
+    }
+}
+impl<T> A for T {}
+
+trait B {
+    fn hello(&self) {
+        println!("B");
+    }
+}
+impl<T> B for T {}
+
+trait C: A + B {
+    fn hello(&self) {
+        println!("C");
+    }
+}
+impl<T> C for T {}
+
+fn main() {
+    ().hello();
+    //~^ WARN trait item `hello` from `C` shadows identically named item from supertrait
+}
diff --git a/tests/ui/methods/supertrait-shadowing/common-ancestor-2.run.stdout b/tests/ui/methods/supertrait-shadowing/common-ancestor-2.run.stdout
new file mode 100644
index 00000000000..3cc58df8375
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/common-ancestor-2.run.stdout
@@ -0,0 +1 @@
+C
diff --git a/tests/ui/methods/supertrait-shadowing/common-ancestor-2.stderr b/tests/ui/methods/supertrait-shadowing/common-ancestor-2.stderr
new file mode 100644
index 00000000000..a22c5430fef
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/common-ancestor-2.stderr
@@ -0,0 +1,27 @@
+warning: trait item `hello` from `C` shadows identically named item from supertrait
+  --> $DIR/common-ancestor-2.rs:30:8
+   |
+LL |     ().hello();
+   |        ^^^^^
+   |
+note: item from `C` shadows a supertrait item
+  --> $DIR/common-ancestor-2.rs:23:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: items from several supertraits are shadowed: `A` and `B`
+  --> $DIR/common-ancestor-2.rs:9:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+...
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: the lint level is defined here
+  --> $DIR/common-ancestor-2.rs:5:9
+   |
+LL | #![warn(supertrait_item_shadowing_usage)]
+   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+warning: 1 warning emitted
+
diff --git a/tests/ui/methods/supertrait-shadowing/common-ancestor-3.rs b/tests/ui/methods/supertrait-shadowing/common-ancestor-3.rs
new file mode 100644
index 00000000000..c2b0ef39bb1
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/common-ancestor-3.rs
@@ -0,0 +1,41 @@
+//@ run-pass
+//@ check-run-results
+
+#![feature(supertrait_item_shadowing)]
+#![warn(supertrait_item_shadowing_usage)]
+#![allow(dead_code)]
+
+trait A {
+    fn hello(&self) {
+        println!("A");
+    }
+}
+impl<T> A for T {}
+
+trait B {
+    fn hello(&self) {
+        println!("B");
+    }
+}
+impl<T> B for T {}
+
+trait C: A + B {
+    fn hello(&self) {
+        println!("C");
+    }
+}
+impl<T> C for T {}
+
+// `D` extends `C` which extends `B` and `A`
+
+trait D: C {
+    fn hello(&self) {
+        println!("D");
+    }
+}
+impl<T> D for T {}
+
+fn main() {
+    ().hello();
+    //~^ WARN trait item `hello` from `D` shadows identically named item from supertrait
+}
diff --git a/tests/ui/methods/supertrait-shadowing/common-ancestor-3.run.stdout b/tests/ui/methods/supertrait-shadowing/common-ancestor-3.run.stdout
new file mode 100644
index 00000000000..17848105018
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/common-ancestor-3.run.stdout
@@ -0,0 +1 @@
+D
diff --git a/tests/ui/methods/supertrait-shadowing/common-ancestor-3.stderr b/tests/ui/methods/supertrait-shadowing/common-ancestor-3.stderr
new file mode 100644
index 00000000000..072f4fe0208
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/common-ancestor-3.stderr
@@ -0,0 +1,30 @@
+warning: trait item `hello` from `D` shadows identically named item from supertrait
+  --> $DIR/common-ancestor-3.rs:39:8
+   |
+LL |     ().hello();
+   |        ^^^^^
+   |
+note: item from `D` shadows a supertrait item
+  --> $DIR/common-ancestor-3.rs:32:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: items from several supertraits are shadowed: `A`, `B`, and `C`
+  --> $DIR/common-ancestor-3.rs:9:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+...
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+...
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: the lint level is defined here
+  --> $DIR/common-ancestor-3.rs:5:9
+   |
+LL | #![warn(supertrait_item_shadowing_usage)]
+   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+warning: 1 warning emitted
+
diff --git a/tests/ui/methods/supertrait-shadowing/no-common-ancestor-2.rs b/tests/ui/methods/supertrait-shadowing/no-common-ancestor-2.rs
new file mode 100644
index 00000000000..2834ca31b71
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/no-common-ancestor-2.rs
@@ -0,0 +1,37 @@
+#![feature(supertrait_item_shadowing)]
+
+trait A {
+    fn hello(&self) {
+        println!("A");
+    }
+}
+impl<T> A for T {}
+
+trait B {
+    fn hello(&self) {
+        println!("B");
+    }
+}
+impl<T> B for T {}
+
+trait C: A + B {
+    fn hello(&self) {
+        println!("C");
+    }
+}
+impl<T> C for T {}
+
+// Since `D` is not a subtrait of `C`,
+// we have no obvious lower bound.
+
+trait D: B {
+    fn hello(&self) {
+        println!("D");
+    }
+}
+impl<T> D for T {}
+
+fn main() {
+    ().hello();
+    //~^ ERROR multiple applicable items in scope
+}
diff --git a/tests/ui/methods/supertrait-shadowing/no-common-ancestor-2.stderr b/tests/ui/methods/supertrait-shadowing/no-common-ancestor-2.stderr
new file mode 100644
index 00000000000..231cb9b1cb2
--- /dev/null
+++ b/tests/ui/methods/supertrait-shadowing/no-common-ancestor-2.stderr
@@ -0,0 +1,50 @@
+error[E0034]: multiple applicable items in scope
+  --> $DIR/no-common-ancestor-2.rs:35:8
+   |
+LL |     ().hello();
+   |        ^^^^^ multiple `hello` found
+   |
+note: candidate #1 is defined in an impl of the trait `A` for the type `T`
+  --> $DIR/no-common-ancestor-2.rs:4:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: candidate #2 is defined in an impl of the trait `B` for the type `T`
+  --> $DIR/no-common-ancestor-2.rs:11:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: candidate #3 is defined in an impl of the trait `C` for the type `T`
+  --> $DIR/no-common-ancestor-2.rs:18:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+note: candidate #4 is defined in an impl of the trait `D` for the type `T`
+  --> $DIR/no-common-ancestor-2.rs:28:5
+   |
+LL |     fn hello(&self) {
+   |     ^^^^^^^^^^^^^^^
+help: disambiguate the method for candidate #1
+   |
+LL -     ().hello();
+LL +     A::hello(&());
+   |
+help: disambiguate the method for candidate #2
+   |
+LL -     ().hello();
+LL +     B::hello(&());
+   |
+help: disambiguate the method for candidate #3
+   |
+LL -     ().hello();
+LL +     C::hello(&());
+   |
+help: disambiguate the method for candidate #4
+   |
+LL -     ().hello();
+LL +     D::hello(&());
+   |
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0034`.