Avoid cycles from projection bounds

Only check the own predicates of associated types when confirming
projection candidates.
Also consider implied bounds when comparing trait and impl methods.

11 files changed, 118 insertions, 81 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index 71a4623cd62..8f7513cf27c 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -28,7 +28,6 @@ use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
 use rustc_middle::ty::subst::Subst;
 use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, WithConstness};
 use rustc_span::symbol::sym;
-use rustc_span::DUMMY_SP;
 
 pub use rustc_middle::traits::Reveal;
 
@@ -1409,6 +1408,7 @@ fn confirm_param_env_candidate<'cx, 'tcx>(
     match infcx.at(cause, param_env).eq(cache_trait_ref, obligation_trait_ref) {
         Ok(InferOk { value: _, obligations }) => {
             nested_obligations.extend(obligations);
+            assoc_ty_own_obligations(selcx, obligation, &mut nested_obligations);
             Progress { ty: cache_entry.ty, obligations: nested_obligations }
         }
         Err(e) => {
@@ -1430,7 +1430,7 @@ fn confirm_impl_candidate<'cx, 'tcx>(
 ) -> Progress<'tcx> {
     let tcx = selcx.tcx();
 
-    let ImplSourceUserDefinedData { impl_def_id, substs, nested } = impl_impl_source;
+    let ImplSourceUserDefinedData { impl_def_id, substs, mut nested } = impl_impl_source;
     let assoc_item_id = obligation.predicate.item_def_id;
     let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
 
@@ -1463,15 +1463,48 @@ fn confirm_impl_candidate<'cx, 'tcx>(
     let ty = tcx.type_of(assoc_ty.item.def_id);
     if substs.len() != tcx.generics_of(assoc_ty.item.def_id).count() {
         let err = tcx.ty_error_with_message(
-            DUMMY_SP,
+            obligation.cause.span,
             "impl item and trait item have different parameter counts",
         );
         Progress { ty: err, obligations: nested }
     } else {
+        assoc_ty_own_obligations(selcx, obligation, &mut nested);
         Progress { ty: ty.subst(tcx, substs), obligations: nested }
     }
 }
 
+// Get obligations corresponding to the predicates from the where-clause of the
+// associated type itself.
+// Note: `feature(generic_associated_types)` is required to write such
+// predicates, even for non-generic associcated types.
+fn assoc_ty_own_obligations<'cx, 'tcx>(
+    selcx: &mut SelectionContext<'cx, 'tcx>,
+    obligation: &ProjectionTyObligation<'tcx>,
+    nested: &mut Vec<PredicateObligation<'tcx>>,
+) {
+    let tcx = selcx.tcx();
+    for predicate in tcx
+        .predicates_of(obligation.predicate.item_def_id)
+        .instantiate_own(tcx, obligation.predicate.substs)
+        .predicates
+    {
+        let normalized = normalize_with_depth_to(
+            selcx,
+            obligation.param_env,
+            obligation.cause.clone(),
+            obligation.recursion_depth + 1,
+            &predicate,
+            nested,
+        );
+        nested.push(Obligation::with_depth(
+            obligation.cause.clone(),
+            obligation.recursion_depth + 1,
+            obligation.param_env,
+            normalized,
+        ));
+    }
+}
+
 /// Locate the definition of an associated type in the specialization hierarchy,
 /// starting from the given impl.
 ///
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index 1e68554fecf..21293615bc9 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -157,22 +157,26 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         );
                     }),
             );
-            // Require that the projection is well-formed.
-            let self_ty = self.infcx.replace_bound_vars_with_placeholders(&bound_self_ty);
-            let self_ty = normalize_with_depth_to(
-                self,
-                obligation.param_env,
-                obligation.cause.clone(),
-                obligation.recursion_depth + 1,
-                &self_ty,
-                &mut obligations,
-            );
-            obligations.push(Obligation::with_depth(
-                obligation.cause.clone(),
-                obligation.recursion_depth + 1,
-                obligation.param_env,
-                ty::PredicateKind::WellFormed(self_ty.into()).to_predicate(tcx),
-            ));
+
+            if let ty::Projection(..) = bound_self_ty.skip_binder().kind {
+                for predicate in tcx.predicates_of(def_id).instantiate_own(tcx, substs).predicates {
+                    let normalized = normalize_with_depth_to(
+                        self,
+                        obligation.param_env,
+                        obligation.cause.clone(),
+                        obligation.recursion_depth + 1,
+                        &predicate,
+                        &mut obligations,
+                    );
+                    obligations.push(Obligation::with_depth(
+                        obligation.cause.clone(),
+                        obligation.recursion_depth + 1,
+                        obligation.param_env,
+                        normalized,
+                    ));
+                }
+            }
+
             obligations
         })
     }
diff --git a/compiler/rustc_typeck/src/check/compare_method.rs b/compiler/rustc_typeck/src/check/compare_method.rs
index ee21167ff97..788590e50f3 100644
--- a/compiler/rustc_typeck/src/check/compare_method.rs
+++ b/compiler/rustc_typeck/src/check/compare_method.rs
@@ -328,7 +328,7 @@ fn compare_predicate_entailment<'tcx>(
         // Finally, resolve all regions. This catches wily misuses of
         // lifetime parameters.
         let fcx = FnCtxt::new(&inh, param_env, impl_m_hir_id);
-        fcx.regionck_item(impl_m_hir_id, impl_m_span, &[]);
+        fcx.regionck_item(impl_m_hir_id, impl_m_span, trait_sig.inputs_and_output);
 
         Ok(())
     })
diff --git a/src/test/ui/associated-types/wf-cycle-2.rs b/src/test/ui/associated-types/wf-cycle-2.rs
new file mode 100644
index 00000000000..d7467ac2237
--- /dev/null
+++ b/src/test/ui/associated-types/wf-cycle-2.rs
@@ -0,0 +1,18 @@
+// check-pass
+
+trait IntoIt {
+    type Item;
+}
+
+impl<I> IntoIt for I {
+    type Item = ();
+}
+
+trait BaseGraph
+where
+    <Self::VertexIter as IntoIt>::Item: Sized,
+{
+    type VertexIter: IntoIt;
+}
+
+fn main() {}
diff --git a/src/test/ui/associated-types/wf-cycle.rs b/src/test/ui/associated-types/wf-cycle.rs
new file mode 100644
index 00000000000..cf6508551a5
--- /dev/null
+++ b/src/test/ui/associated-types/wf-cycle.rs
@@ -0,0 +1,13 @@
+// check-pass
+
+trait A {
+    type U: Copy;
+}
+
+trait B where
+    <Self::V as A>::U: Copy,
+{
+    type V: A;
+}
+
+fn main() {}
diff --git a/src/test/ui/regions/regions-trait-1.rs b/src/test/ui/regions/regions-trait-1.rs
index 0da8ac53695..b6dab1c32e8 100644
--- a/src/test/ui/regions/regions-trait-1.rs
+++ b/src/test/ui/regions/regions-trait-1.rs
@@ -1,30 +1,33 @@
-#![feature(box_syntax)]
+// check-pass
 
-struct Ctxt { v: usize }
+struct Ctxt {
+    v: usize,
+}
 
 trait GetCtxt {
     // Here the `&` is bound in the method definition:
     fn get_ctxt(&self) -> &Ctxt;
 }
 
-struct HasCtxt<'a> { c: &'a Ctxt }
+struct HasCtxt<'a> {
+    c: &'a Ctxt,
+}
 
 impl<'a> GetCtxt for HasCtxt<'a> {
-
-    // Here an error occurs because we used `&self` but
-    // the definition used `&`:
-    fn get_ctxt(&self) -> &'a Ctxt { //~ ERROR method not compatible with trait
+    // Ok: Have implied bound of WF(&'b HasCtxt<'a>)
+    // so know 'a: 'b
+    // so know &'a Ctxt <: &'b Ctxt
+    fn get_ctxt<'b>(&'b self) -> &'a Ctxt {
         self.c
     }
-
 }
 
-fn get_v(gc: Box<dyn GetCtxt>) -> usize {
+fn get_v(gc: Box<dyn GetCtxt + '_>) -> usize {
     gc.get_ctxt().v
 }
 
 fn main() {
     let ctxt = Ctxt { v: 22 };
     let hc = HasCtxt { c: &ctxt };
-    assert_eq!(get_v(box hc as Box<dyn GetCtxt>), 22);
+    assert_eq!(get_v(Box::new(hc) as Box<dyn GetCtxt>), 22);
 }
diff --git a/src/test/ui/regions/regions-trait-1.stderr b/src/test/ui/regions/regions-trait-1.stderr
deleted file mode 100644
index 92d96a722d4..00000000000
--- a/src/test/ui/regions/regions-trait-1.stderr
+++ /dev/null
@@ -1,22 +0,0 @@
-error[E0308]: method not compatible with trait
-  --> $DIR/regions-trait-1.rs:16:5
-   |
-LL |     fn get_ctxt(&self) -> &'a Ctxt {
-   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
-   |
-   = note: expected fn pointer `fn(&HasCtxt<'a>) -> &Ctxt`
-              found fn pointer `fn(&HasCtxt<'a>) -> &'a Ctxt`
-note: the lifetime `'a` as defined on the impl at 12:6...
-  --> $DIR/regions-trait-1.rs:12:6
-   |
-LL | impl<'a> GetCtxt for HasCtxt<'a> {
-   |      ^^
-note: ...does not necessarily outlive the anonymous lifetime #1 defined on the method body at 16:5
-  --> $DIR/regions-trait-1.rs:16:5
-   |
-LL |     fn get_ctxt(&self) -> &'a Ctxt {
-   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-
-error: aborting due to previous error
-
-For more information about this error, try `rustc --explain E0308`.
diff --git a/src/test/ui/specialization/issue-38091-2.rs b/src/test/ui/specialization/issue-38091-2.rs
index da7f6737733..9ed0b240d0a 100644
--- a/src/test/ui/specialization/issue-38091-2.rs
+++ b/src/test/ui/specialization/issue-38091-2.rs
@@ -1,3 +1,6 @@
+// build-fail
+//~^ ERROR overflow evaluating the requirement `i32: Check`
+
 #![feature(specialization)]
 //~^ WARN the feature `specialization` is incomplete
 
@@ -5,7 +8,10 @@ trait Iterate<'a> {
     type Ty: Valid;
     fn iterate(self);
 }
-impl<'a, T> Iterate<'a> for T where T: Check {
+impl<'a, T> Iterate<'a> for T
+where
+    T: Check,
+{
     default type Ty = ();
     default fn iterate(self) {}
 }
@@ -19,5 +25,4 @@ impl Valid for () {}
 
 fn main() {
     Iterate::iterate(0);
-    //~^ ERROR overflow evaluating the requirement `{integer}: Check`
 }
diff --git a/src/test/ui/specialization/issue-38091-2.stderr b/src/test/ui/specialization/issue-38091-2.stderr
index e776ff0fafb..a314c26ad14 100644
--- a/src/test/ui/specialization/issue-38091-2.stderr
+++ b/src/test/ui/specialization/issue-38091-2.stderr
@@ -1,5 +1,5 @@
 warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
-  --> $DIR/issue-38091-2.rs:1:12
+  --> $DIR/issue-38091-2.rs:4:12
    |
 LL | #![feature(specialization)]
    |            ^^^^^^^^^^^^^^
@@ -7,16 +7,9 @@ LL | #![feature(specialization)]
    = note: `#[warn(incomplete_features)]` on by default
    = note: see issue #31844 <https://github.com/rust-lang/rust/issues/31844> for more information
 
-error[E0275]: overflow evaluating the requirement `{integer}: Check`
-  --> $DIR/issue-38091-2.rs:21:5
+error[E0275]: overflow evaluating the requirement `i32: Check`
    |
-LL |     fn iterate(self);
-   |     ----------------- required by `Iterate::iterate`
-...
-LL |     Iterate::iterate(0);
-   |     ^^^^^^^^^^^^^^^^
-   |
-   = note: required because of the requirements on the impl of `Iterate<'_>` for `{integer}`
+   = note: required because of the requirements on the impl of `Iterate` for `i32`
 
 error: aborting due to previous error; 1 warning emitted
 
diff --git a/src/test/ui/specialization/issue-38091.rs b/src/test/ui/specialization/issue-38091.rs
index cc0eeb53687..5b398368a67 100644
--- a/src/test/ui/specialization/issue-38091.rs
+++ b/src/test/ui/specialization/issue-38091.rs
@@ -5,7 +5,10 @@ trait Iterate<'a> {
     type Ty: Valid;
     fn iterate(self);
 }
-impl<'a, T> Iterate<'a> for T where T: Check {
+impl<'a, T> Iterate<'a> for T
+where
+    T: Check,
+{
     default type Ty = ();
     //~^ ERROR the trait bound `(): Valid` is not satisfied
     default fn iterate(self) {}
@@ -18,5 +21,4 @@ trait Valid {}
 
 fn main() {
     Iterate::iterate(0);
-    //~^ ERROR overflow evaluating the requirement `{integer}: Check`
 }
diff --git a/src/test/ui/specialization/issue-38091.stderr b/src/test/ui/specialization/issue-38091.stderr
index beec702b89e..6be0f26849f 100644
--- a/src/test/ui/specialization/issue-38091.stderr
+++ b/src/test/ui/specialization/issue-38091.stderr
@@ -8,7 +8,7 @@ LL | #![feature(specialization)]
    = note: see issue #31844 <https://github.com/rust-lang/rust/issues/31844> for more information
 
 error[E0277]: the trait bound `(): Valid` is not satisfied
-  --> $DIR/issue-38091.rs:9:5
+  --> $DIR/issue-38091.rs:12:5
    |
 LL |     type Ty: Valid;
    |              ----- required by this bound in `Iterate::Ty`
@@ -16,18 +16,6 @@ LL |     type Ty: Valid;
 LL |     default type Ty = ();
    |     ^^^^^^^^^^^^^^^^^^^^^ the trait `Valid` is not implemented for `()`
 
-error[E0275]: overflow evaluating the requirement `{integer}: Check`
-  --> $DIR/issue-38091.rs:20:5
-   |
-LL |     fn iterate(self);
-   |     ----------------- required by `Iterate::iterate`
-...
-LL |     Iterate::iterate(0);
-   |     ^^^^^^^^^^^^^^^^
-   |
-   = note: required because of the requirements on the impl of `Iterate<'_>` for `{integer}`
-
-error: aborting due to 2 previous errors; 1 warning emitted
+error: aborting due to previous error; 1 warning emitted
 
-Some errors have detailed explanations: E0275, E0277.
-For more information about an error, try `rustc --explain E0275`.
+For more information about this error, try `rustc --explain E0277`.