Unify region variables when projecting associated types

This is required to avoid cycles when evaluating auto trait
predicates.

29 files changed, 133 insertions, 35 deletions

diff --git a/src/librustc_infer/infer/canonical/canonicalizer.rs b/src/librustc_infer/infer/canonical/canonicalizer.rs
index c2dae6ba4f8..8695b9616ee 100644
--- a/src/librustc_infer/infer/canonical/canonicalizer.rs
+++ b/src/librustc_infer/infer/canonical/canonicalizer.rs
@@ -314,18 +314,25 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
             }
 
             ty::ReVar(vid) => {
-                let r = self
+                let resolved_vid = self
                     .infcx
                     .unwrap()
                     .inner
                     .borrow_mut()
                     .unwrap_region_constraints()
-                    .opportunistic_resolve_var(self.tcx, vid);
+                    .opportunistic_resolve_var(vid);
                 debug!(
                     "canonical: region var found with vid {:?}, \
                      opportunistically resolved to {:?}",
                     vid, r
                 );
+                // micro-optimize -- avoid an interner look-up if the vid
+                // hasn't changed.
+                let r = if vid == resolved_vid {
+                    r
+                } else {
+                    self.tcx.mk_region(ty::ReVar(resolved_vid))
+                };
                 self.canonicalize_region_mode.canonicalize_free_region(self, r)
             }
 
diff --git a/src/librustc_infer/infer/region_constraints/mod.rs b/src/librustc_infer/infer/region_constraints/mod.rs
index 626774617a6..90d61a78f9b 100644
--- a/src/librustc_infer/infer/region_constraints/mod.rs
+++ b/src/librustc_infer/infer/region_constraints/mod.rs
@@ -50,10 +50,10 @@ pub struct RegionConstraintStorage<'tcx> {
     /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this
     /// table. You can then call `opportunistic_resolve_var` early
     /// which will map R1 and R2 to some common region (i.e., either
-    /// R1 or R2). This is important when dropck and other such code
-    /// is iterating to a fixed point, because otherwise we sometimes
-    /// would wind up with a fresh stream of region variables that
-    /// have been equated but appear distinct.
+    /// R1 or R2). This is important when fulfillment, dropck and other such
+    /// code is iterating to a fixed point, because otherwise we sometimes
+    /// would wind up with a fresh stream of region variables that have been
+    /// equated but appear distinct.
     pub(super) unification_table: ut::UnificationTableStorage<ty::RegionVid>,
 
     /// a flag set to true when we perform any unifications; this is used
@@ -714,13 +714,8 @@ impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
         }
     }
 
-    pub fn opportunistic_resolve_var(
-        &mut self,
-        tcx: TyCtxt<'tcx>,
-        rid: RegionVid,
-    ) -> ty::Region<'tcx> {
-        let vid = self.unification_table().probe_value(rid).min_vid;
-        tcx.mk_region(ty::ReVar(vid))
+    pub fn opportunistic_resolve_var(&mut self, rid: RegionVid) -> ty::RegionVid {
+        self.unification_table().probe_value(rid).min_vid
     }
 
     fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> {
diff --git a/src/librustc_infer/infer/resolve.rs b/src/librustc_infer/infer/resolve.rs
index e28cf49c7f2..bda38301f1c 100644
--- a/src/librustc_infer/infer/resolve.rs
+++ b/src/librustc_infer/infer/resolve.rs
@@ -46,51 +46,56 @@ impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticVarResolver<'a, 'tcx> {
     }
 }
 
-/// The opportunistic type and region resolver is similar to the
-/// opportunistic type resolver, but also opportunistically resolves
-/// regions. It is useful for canonicalization.
-pub struct OpportunisticTypeAndRegionResolver<'a, 'tcx> {
+/// The opportunistic region resolver opportunistically resolves regions
+/// variables to the variable with the least variable id. It is used when
+/// normlizing projections to avoid hitting the recursion limit by creating
+/// many versions of a predicate for types that in the end have to unify.
+///
+/// If you want to resolve type and const variables as well, call
+/// [InferCtxt::resolve_vars_if_possible] first.
+pub struct OpportunisticRegionResolver<'a, 'tcx> {
     infcx: &'a InferCtxt<'a, 'tcx>,
 }
 
-impl<'a, 'tcx> OpportunisticTypeAndRegionResolver<'a, 'tcx> {
+impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> {
     pub fn new(infcx: &'a InferCtxt<'a, 'tcx>) -> Self {
-        OpportunisticTypeAndRegionResolver { infcx }
+        OpportunisticRegionResolver { infcx }
     }
 }
 
-impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticTypeAndRegionResolver<'a, 'tcx> {
+impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticRegionResolver<'a, 'tcx> {
     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
         self.infcx.tcx
     }
 
     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
-        if !t.needs_infer() {
+        if !t.has_infer_regions() {
             t // micro-optimize -- if there is nothing in this type that this fold affects...
         } else {
-            let t0 = self.infcx.shallow_resolve(t);
-            t0.super_fold_with(self)
+            t.super_fold_with(self)
         }
     }
 
     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
         match *r {
-            ty::ReVar(rid) => self
-                .infcx
-                .inner
-                .borrow_mut()
-                .unwrap_region_constraints()
-                .opportunistic_resolve_var(self.tcx(), rid),
+            ty::ReVar(rid) => {
+                let resolved = self
+                    .infcx
+                    .inner
+                    .borrow_mut()
+                    .unwrap_region_constraints()
+                    .opportunistic_resolve_var(rid);
+                if resolved == rid { r } else { self.tcx().mk_region(ty::ReVar(resolved)) }
+            }
             _ => r,
         }
     }
 
     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
-        if !ct.needs_infer() {
+        if !ct.has_infer_regions() {
             ct // micro-optimize -- if there is nothing in this const that this fold affects...
         } else {
-            let c0 = self.infcx.shallow_resolve(ct);
-            c0.super_fold_with(self)
+            ct.super_fold_with(self)
         }
     }
 }
diff --git a/src/librustc_middle/ty/fold.rs b/src/librustc_middle/ty/fold.rs
index 248dd00ef47..24dbf7b8c46 100644
--- a/src/librustc_middle/ty/fold.rs
+++ b/src/librustc_middle/ty/fold.rs
@@ -87,6 +87,9 @@ pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
     fn has_param_types_or_consts(&self) -> bool {
         self.has_type_flags(TypeFlags::HAS_TY_PARAM | TypeFlags::HAS_CT_PARAM)
     }
+    fn has_infer_regions(&self) -> bool {
+        self.has_type_flags(TypeFlags::HAS_RE_INFER)
+    }
     fn has_infer_types(&self) -> bool {
         self.has_type_flags(TypeFlags::HAS_TY_INFER)
     }
diff --git a/src/librustc_trait_selection/traits/project.rs b/src/librustc_trait_selection/traits/project.rs
index 9492c3c3409..bccd903f57e 100644
--- a/src/librustc_trait_selection/traits/project.rs
+++ b/src/librustc_trait_selection/traits/project.rs
@@ -24,6 +24,7 @@ use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_errors::ErrorReported;
 use rustc_hir::def_id::DefId;
 use rustc_hir::lang_items::{FnOnceTraitLangItem, GeneratorTraitLangItem};
+use rustc_infer::infer::resolve::OpportunisticRegionResolver;
 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
 use rustc_middle::ty::subst::Subst;
 use rustc_middle::ty::util::IntTypeExt;
@@ -1146,7 +1147,7 @@ fn confirm_candidate<'cx, 'tcx>(
 ) -> Progress<'tcx> {
     debug!("confirm_candidate(candidate={:?}, obligation={:?})", candidate, obligation);
 
-    match candidate {
+    let mut progress = match candidate {
         ProjectionTyCandidate::ParamEnv(poly_projection)
         | ProjectionTyCandidate::TraitDef(poly_projection) => {
             confirm_param_env_candidate(selcx, obligation, poly_projection)
@@ -1155,7 +1156,16 @@ fn confirm_candidate<'cx, 'tcx>(
         ProjectionTyCandidate::Select(impl_source) => {
             confirm_select_candidate(selcx, obligation, obligation_trait_ref, impl_source)
         }
+    };
+    // When checking for cycle during evaluation, we compare predicates with
+    // "syntactic" equality. Since normalization generally introduces a type
+    // with new region variables, we need to resolve them to existing variables
+    // when possible for this to work. See `auto-trait-projection-recursion.rs`
+    // for a case where this matters.
+    if progress.ty.has_infer_regions() {
+        progress.ty = OpportunisticRegionResolver::new(selcx.infcx()).fold_ty(progress.ty);
     }
+    progress
 }
 
 fn confirm_select_candidate<'cx, 'tcx>(
diff --git a/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr b/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr
index 137cb83ccd3..0a05fc6bb82 100644
--- a/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr
+++ b/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr
@@ -1,8 +1,8 @@
 error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
-  --> $DIR/project-fn-ret-invariant.rs:48:8
+  --> $DIR/project-fn-ret-invariant.rs:48:4
    |
 LL |    bar(foo, x)
-   |        ^^^
+   |    ^^^^^^^^^^^
    |
 note: first, the lifetime cannot outlive the lifetime `'a` as defined on the function body at 44:8...
   --> $DIR/project-fn-ret-invariant.rs:44:8
diff --git a/src/test/ui/auto-is-contextual.rs b/src/test/ui/auto-traits/auto-is-contextual.rs
index a2ddd5374c0..a2ddd5374c0 100644
--- a/src/test/ui/auto-is-contextual.rs
+++ b/src/test/ui/auto-traits/auto-is-contextual.rs
diff --git a/src/test/ui/auto-traits/auto-trait-projection-recursion.rs b/src/test/ui/auto-traits/auto-trait-projection-recursion.rs
new file mode 100644
index 00000000000..a36f26f02e9
--- /dev/null
+++ b/src/test/ui/auto-traits/auto-trait-projection-recursion.rs
@@ -0,0 +1,34 @@
+// Checking the `Send` bound in `main` requires:
+//
+// checking             <C<'static> as Y>::P: Send
+// which normalizes to  Box<X<C<'?1>>>: Send
+// which needs          X<C<'?1>>: Send
+// which needs          <C<'?1> as Y>::P: Send
+//
+// At this point we used to normalize the predicate to `Box<X<C<'?2>>>: Send`
+// and continue in a loop where we created new region variables to the
+// recursion limit. To avoid this we now "canonicalize" region variables to
+// lowest unified region vid. This means we instead have to prove
+// `Box<X<C<'?1>>>: Send`, which we can because auto traits are coinductive.
+
+// check-pass
+
+// Avoid a really long error message if this regresses.
+#![recursion_limit="20"]
+
+trait Y {
+    type P;
+}
+
+impl<'a> Y for C<'a> {
+    type P = Box<X<C<'a>>>;
+}
+
+struct C<'a>(&'a ());
+struct X<T: Y>(T::P);
+
+fn is_send<S: Send>() {}
+
+fn main() {
+    is_send::<X<C<'static>>>();
+}
diff --git a/src/test/ui/auto-trait-validation.rs b/src/test/ui/auto-traits/auto-trait-validation.rs
index 34d6c3da00e..34d6c3da00e 100644
--- a/src/test/ui/auto-trait-validation.rs
+++ b/src/test/ui/auto-traits/auto-trait-validation.rs
diff --git a/src/test/ui/auto-trait-validation.stderr b/src/test/ui/auto-traits/auto-trait-validation.stderr
index 4040e66c6af..4040e66c6af 100644
--- a/src/test/ui/auto-trait-validation.stderr
+++ b/src/test/ui/auto-traits/auto-trait-validation.stderr
diff --git a/src/test/ui/traits/auto-traits.rs b/src/test/ui/auto-traits/auto-traits.rs
index 15fdddc5f3f..15fdddc5f3f 100644
--- a/src/test/ui/traits/auto-traits.rs
+++ b/src/test/ui/auto-traits/auto-traits.rs
diff --git a/src/test/ui/issues/issue-23080-2.rs b/src/test/ui/auto-traits/issue-23080-2.rs
index 7f6b9e3fba7..7f6b9e3fba7 100644
--- a/src/test/ui/issues/issue-23080-2.rs
+++ b/src/test/ui/auto-traits/issue-23080-2.rs
diff --git a/src/test/ui/issues/issue-23080-2.stderr b/src/test/ui/auto-traits/issue-23080-2.stderr
index 48ce09aaa34..48ce09aaa34 100644
--- a/src/test/ui/issues/issue-23080-2.stderr
+++ b/src/test/ui/auto-traits/issue-23080-2.stderr
diff --git a/src/test/ui/issues/issue-23080.rs b/src/test/ui/auto-traits/issue-23080.rs
index 035db82ba5d..035db82ba5d 100644
--- a/src/test/ui/issues/issue-23080.rs
+++ b/src/test/ui/auto-traits/issue-23080.rs
diff --git a/src/test/ui/issues/issue-23080.stderr b/src/test/ui/auto-traits/issue-23080.stderr
index 73ecb1c362e..73ecb1c362e 100644
--- a/src/test/ui/issues/issue-23080.stderr
+++ b/src/test/ui/auto-traits/issue-23080.stderr
diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.rs b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.rs
index 8824a6d2767..8824a6d2767 100644
--- a/src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.rs
+++ b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.rs
diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.stderr b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.stderr
index 63b3300f6db..63b3300f6db 100644
--- a/src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.stderr
+++ b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.stderr
diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits.rs b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.rs
index edbca915124..edbca915124 100644
--- a/src/test/ui/typeck/typeck-auto-trait-no-supertraits.rs
+++ b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.rs
diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits.stderr b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.stderr
index 796638fc54d..796638fc54d 100644
--- a/src/test/ui/typeck/typeck-auto-trait-no-supertraits.stderr
+++ b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.stderr
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.rs
index 71ac2b466c1..71ac2b466c1 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.rs
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.rs
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.stderr
index 53ba9b8a3f6..53ba9b8a3f6 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.stderr
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.stderr
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.rs
index 6483b9213dc..6483b9213dc 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types.rs
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.rs
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.stderr
index bc500004984..bc500004984 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types.stderr
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.stderr
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-negation.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-negation.rs
index 47cab60625d..47cab60625d 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-negation.rs
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-negation.rs
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-negation.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-negation.stderr
index 76a6994cb00..76a6994cb00 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-negation.stderr
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-negation.stderr
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-precedence.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.rs
index 614a5ff55b1..614a5ff55b1 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-precedence.rs
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.rs
diff --git a/src/test/ui/typeck/typeck-default-trait-impl-precedence.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr
index 5962d191292..5962d191292 100644
--- a/src/test/ui/typeck/typeck-default-trait-impl-precedence.stderr
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr
diff --git a/src/test/ui/traits/traits-inductive-overflow-lifetime.rs b/src/test/ui/traits/traits-inductive-overflow-lifetime.rs
new file mode 100644
index 00000000000..205d50a2ed9
--- /dev/null
+++ b/src/test/ui/traits/traits-inductive-overflow-lifetime.rs
@@ -0,0 +1,30 @@
+// Test that we don't hit the recursion limit for short cycles involving lifetimes.
+
+// Shouldn't hit this, we should realize that we're in a cycle sooner.
+#![recursion_limit="20"]
+
+trait NotAuto {}
+trait Y {
+    type P;
+}
+
+impl<'a> Y for C<'a> {
+    type P = Box<X<C<'a>>>;
+}
+
+struct C<'a>(&'a ());
+struct X<T: Y>(T::P);
+
+impl<T: NotAuto> NotAuto for Box<T> {}
+impl<T: Y> NotAuto for X<T> where T::P: NotAuto {}
+impl<'a> NotAuto for C<'a> {}
+
+fn is_send<S: NotAuto>() {}
+//~^ NOTE: required
+
+fn main() {
+    // Should only be a few notes.
+    is_send::<X<C<'static>>>();
+    //~^ ERROR overflow evaluating
+    //~| NOTE: required
+}
diff --git a/src/test/ui/traits/traits-inductive-overflow-lifetime.stderr b/src/test/ui/traits/traits-inductive-overflow-lifetime.stderr
new file mode 100644
index 00000000000..9a227229ea4
--- /dev/null
+++ b/src/test/ui/traits/traits-inductive-overflow-lifetime.stderr
@@ -0,0 +1,14 @@
+error[E0275]: overflow evaluating the requirement `std::boxed::Box<X<C<'_>>>: NotAuto`
+  --> $DIR/traits-inductive-overflow-lifetime.rs:27:5
+   |
+LL | fn is_send<S: NotAuto>() {}
+   |               ------- required by this bound in `is_send`
+...
+LL |     is_send::<X<C<'static>>>();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `NotAuto` for `X<C<'static>>`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0275`.