Auto merge of #144405 - lcnr:hir-typeck-uniquify, r=BoxyUwU

uniquify root goals during HIR typeck

We need to rely on region identity to deal with hangs such as https://github.com/rust-lang/trait-system-refactor-initiative/issues/210 and to keep the current behavior of `fn try_merge_responses`.

This is a problem as borrowck starts by replacing each *occurrence* of a region with a unique inference variable. This frequently splits a single region during HIR typeck into multiple distinct regions. As we assume goals to always succeed during borrowck, relying on two occurances of a region being identical during HIR typeck causes ICE. See the now fixed examples in https://github.com/rust-lang/trait-system-refactor-initiative/issues/27 and rust-lang/rust#139409.

We've previously tried to avoid this issue by always *uniquifying* regions when canonicalizing goals. This prevents caching subtrees during canonicalization which resulted in hangs for very large types. People rely on such types in practice, which caused us to revert our attempt to reinstate `#[type_length_limit]` in https://github.com/rust-lang/rust/pull/127670. The complete list of changes here:
- rust-lang/rust#107981
- rust-lang/rust#110180
- rust-lang/rust#114117
- rust-lang/rust#130821

After more consideration, all occurrences of such large types need to happen outside of typeck/borrowck. We know this as we already walk over all types in the MIR body when replacing their regions with nll vars.

This PR therefore enables us to rely on region identity inside of the trait solver by exclusively **uniquifying root goals during HIR typeck**. These are the only goals we assume to hold during borrowck. This is insufficient as type inference variables may "hide" regions we later uniquify. Because of this, we now stash proven goals which depend on inference variables in HIR typeck and reprove them after writeback. This closes https://github.com/rust-lang/trait-system-refactor-initiative/issues/127.

This was originally part of rust-lang/rust#144258 but I've moved it into a separate PR. While I believe we need to rely on region identity to fix the performance issues in some way, I don't know whether rust-lang/rust#144258 is the best approach to actually do so. Regardless of how we deal with the hangs however, this change is necessary and desirable regardless.

r? `@compiler-errors` or `@BoxyUwU`

7 files changed, 125 insertions, 12 deletions

diff --git a/tests/crashes/139409.rs b/tests/crashes/139409.rs
deleted file mode 100644
index 68cbfa153de..00000000000
--- a/tests/crashes/139409.rs
+++ /dev/null
@@ -1,12 +0,0 @@
-//@ known-bug: #139409
-//@ compile-flags: -Znext-solver=globally
-
-fn main() {
-    trait B<C> {}
-    impl<C> B<C> for () {}
-    trait D<C, E>: B<C> + B<E> {
-        fn f(&self) {}
-    }
-    impl<C, E> D<C, E> for () {}
-    (&() as &dyn D<&(), &()>).f()
-}
diff --git a/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-1.next.stderr b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-1.next.stderr
new file mode 100644
index 00000000000..141a07b4be7
--- /dev/null
+++ b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-1.next.stderr
@@ -0,0 +1,19 @@
+error[E0283]: type annotations needed: cannot satisfy `dyn D<&(), &()>: B<&()>`
+  --> $DIR/ambiguity-due-to-uniquification-1.rs:15:31
+   |
+LL |     (&() as &dyn D<&(), &()>).f()
+   |                               ^
+   |
+   = note: cannot satisfy `dyn D<&(), &()>: B<&()>`
+   = help: the trait `B<C>` is implemented for `()`
+note: required by a bound in `D::f`
+  --> $DIR/ambiguity-due-to-uniquification-1.rs:10:16
+   |
+LL | trait D<C, E>: B<C> + B<E> {
+   |                ^^^^ required by this bound in `D::f`
+LL |     fn f(&self) {}
+   |        - required by a bound in this associated function
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0283`.
diff --git a/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-1.rs b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-1.rs
new file mode 100644
index 00000000000..cfdf74046fb
--- /dev/null
+++ b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-1.rs
@@ -0,0 +1,17 @@
+//@ revisions: current next
+//@[next] compile-flags: -Znext-solver
+//@ ignore-compare-mode-next-solver (explicit revisions)
+//@[current] check-pass
+
+// Regression test for #139409 and trait-system-refactor-initiative#27.
+
+trait B<C> {}
+impl<C> B<C> for () {}
+trait D<C, E>: B<C> + B<E> {
+    fn f(&self) {}
+}
+impl<C, E> D<C, E> for () {}
+fn main() {
+    (&() as &dyn D<&(), &()>).f()
+    //[next]~^ ERROR type annotations needed: cannot satisfy `dyn D<&(), &()>: B<&()>`
+}
diff --git a/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-2.next.stderr b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-2.next.stderr
new file mode 100644
index 00000000000..3b478889996
--- /dev/null
+++ b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-2.next.stderr
@@ -0,0 +1,17 @@
+error[E0283]: type annotations needed: cannot satisfy `impl Trait<'x> + Trait<'y>: Trait<'y>`
+  --> $DIR/ambiguity-due-to-uniquification-2.rs:16:23
+   |
+LL |     impls_trait::<'y, _>(foo::<'x, 'y>());
+   |                       ^
+   |
+   = note: cannot satisfy `impl Trait<'x> + Trait<'y>: Trait<'y>`
+   = help: the trait `Trait<'t>` is implemented for `()`
+note: required by a bound in `impls_trait`
+  --> $DIR/ambiguity-due-to-uniquification-2.rs:13:23
+   |
+LL | fn impls_trait<'x, T: Trait<'x>>(_: T) {}
+   |                       ^^^^^^^^^ required by this bound in `impls_trait`
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0283`.
diff --git a/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-2.rs b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-2.rs
new file mode 100644
index 00000000000..2a9a8b80cc0
--- /dev/null
+++ b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-2.rs
@@ -0,0 +1,20 @@
+//@ revisions: current next
+//@[next] compile-flags: -Znext-solver
+//@ ignore-compare-mode-next-solver (explicit revisions)
+//@[current] check-pass
+
+// Regression test from trait-system-refactor-initiative#27.
+
+trait Trait<'t> {}
+impl<'t> Trait<'t> for () {}
+
+fn foo<'x, 'y>() -> impl Trait<'x> + Trait<'y> {}
+
+fn impls_trait<'x, T: Trait<'x>>(_: T) {}
+
+fn bar<'x, 'y>() {
+    impls_trait::<'y, _>(foo::<'x, 'y>());
+    //[next]~^ ERROR type annotations needed: cannot satisfy `impl Trait<'x> + Trait<'y>: Trait<'y>`
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-3.next.stderr b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-3.next.stderr
new file mode 100644
index 00000000000..e25f892b365
--- /dev/null
+++ b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-3.next.stderr
@@ -0,0 +1,19 @@
+error[E0283]: type annotations needed: cannot satisfy `(dyn Object<&(), &()> + 'static): Trait<&()>`
+  --> $DIR/ambiguity-due-to-uniquification-3.rs:28:17
+   |
+LL |     impls_trait(obj, t);
+   |     ----------- ^^^
+   |     |
+   |     required by a bound introduced by this call
+   |
+   = note: cannot satisfy `(dyn Object<&(), &()> + 'static): Trait<&()>`
+   = help: the trait `Trait<T>` is implemented for `()`
+note: required by a bound in `impls_trait`
+  --> $DIR/ambiguity-due-to-uniquification-3.rs:24:19
+   |
+LL | fn impls_trait<T: Trait<U>, U>(_: Inv<T>, _: Inv<U>) {}
+   |                   ^^^^^^^^ required by this bound in `impls_trait`
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0283`.
diff --git a/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-3.rs b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-3.rs
new file mode 100644
index 00000000000..6dcd9d5bdf4
--- /dev/null
+++ b/tests/ui/traits/next-solver/assembly/ambiguity-due-to-uniquification-3.rs
@@ -0,0 +1,33 @@
+//@ revisions: current next
+//@[next] compile-flags: -Znext-solver
+//@ ignore-compare-mode-next-solver (explicit revisions)
+//@[current] check-pass
+
+// Regression test from trait-system-refactor-initiative#27.
+//
+// Unlike in the previous two tests, `dyn Object<?x, ?y>: Trait<?x>` relies
+// on structural identity of type inference variables. This inference variable
+// gets constrained to a type containing a region later on. To prevent this
+// from causing an ICE during MIR borrowck, we stash goals which depend on
+// inference variables and then reprove them at the end of HIR typeck.
+
+#![feature(rustc_attrs)]
+#![rustc_no_implicit_bounds]
+trait Trait<T> {}
+impl<T> Trait<T> for () {}
+
+trait Object<T, U>: Trait<T> + Trait<U> {}
+
+#[derive(Clone, Copy)]
+struct Inv<T>(*mut T);
+fn foo<T: Sized, U: Sized>() -> (Inv<dyn Object<T, U>>, Inv<T>) { todo!() }
+fn impls_trait<T: Trait<U>, U>(_: Inv<T>, _: Inv<U>) {}
+
+fn bar() {
+    let (obj, t) = foo();
+    impls_trait(obj, t);
+    //[next]~^ ERROR type annotations needed
+    let _: Inv<dyn Object<&(), &()>> = obj;
+}
+
+fn main() {}