Unify region variables when projecting associated types

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

24 files changed, 80 insertions, 2 deletions

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`.