Rollup merge of #120836 - lcnr:param-env-hide-impl, r=BoxyUwU

hide impls if trait bound is proven from env

AVERT YOUR EYES `@compiler-errors`

fixes https://github.com/rust-lang/trait-system-refactor-initiative/issues/76 and https://github.com/rust-lang/trait-system-refactor-initiative/issues/12#issuecomment-1865234925

this is kinda ugly and I hate it, but I wasn't able to think of a cleaner approach for now. I am also unsure whether we have to refine this filtering later on, so by making the change pretty minimal it should be easier to improve going forward.

r? `@BoxyUwU`

17 files changed, 316 insertions, 82 deletions

diff --git a/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.rs b/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.rs
index c7e2e2d5e04..f6c75317a34 100644
--- a/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.rs
+++ b/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.rs
@@ -24,6 +24,18 @@ where
 {
 }
 
+// HACK: This impls is necessary so that the impl above is well-formed.
+//
+// When checking that the impl above is well-formed we check `B<T>: Trait<'a, 'b>`
+// with the where clauses `A<T>: Trait<'a, 'b>` and `A<T> NotImplemented`. Trying to
+// use the impl itself to prove that adds region constraints as we uniquified the
+// regions in the `A<T>: Trait<'a, 'b>` where-bound. As both the impl above
+// and the impl below now apply with some constraints, we failed with ambiguity.
+impl<'a, 'b, T: ?Sized> Trait<'a, 'b> for B<T>
+where
+    A<T>: NotImplemented,
+{}
+
 // This impl directly requires 'b to be equal to 'static.
 //
 // Because of the coinductive cycle through `C<T>` it also requires
diff --git a/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr b/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr
index 7b3075f4ff3..0cbd9654044 100644
--- a/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr
+++ b/tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr
@@ -1,5 +1,5 @@
 error: lifetime may not live long enough
-  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:47:5
+  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:59:5
    |
 LL | fn check<'a, T: ?Sized>() {
    |          -- lifetime `'a` defined here
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/ambig-env-no-shadow.rs b/tests/ui/traits/next-solver/env-shadows-impls/ambig-env-no-shadow.rs
new file mode 100644
index 00000000000..37730d38c7a
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/ambig-env-no-shadow.rs
@@ -0,0 +1,40 @@
+// compile-flags: -Znext-solver
+// check-pass
+
+// If a trait goal is proven using the environment, we discard
+// impl candidates when normalizing. However, in this example
+// the env candidates start as ambiguous and end up not applying,
+// so normalization should succeed later on.
+
+trait Trait<T>: Sized {
+    type Assoc: From<Self>;
+}
+
+impl<T, U> Trait<U> for T {
+    type Assoc = T;
+}
+
+fn mk_assoc<T: Trait<U>, U>(t: T, _: U) -> <T as Trait<U>>::Assoc {
+    t.into()
+}
+
+fn generic<T>(t: T) -> T
+where
+    T: Trait<u32>,
+    T: Trait<i16>,
+{
+    let u = Default::default();
+
+    // at this point we have 2 ambig env candidates
+    let ret: T = mk_assoc(t, u);
+
+    // now both env candidates don't apply, so we're now able to
+    // normalize using this impl candidates. For this to work
+    // the normalizes-to must have remained ambiguous above.
+    let _: u8 = u;
+    ret
+}
+
+fn main() {
+    assert_eq!(generic(1), 1);
+}
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-1.rs b/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-1.rs
new file mode 100644
index 00000000000..63742d0d1a1
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-1.rs
@@ -0,0 +1,30 @@
+// compile-flags: -Znext-solver
+// check-pass
+
+// Normalizing `<T as Trait>::TraitAssoc` in the elaborated environment
+// `[T: Trait, T: Super, <T as Super>::SuperAssoc = <T as Trait>::TraitAssoc]`
+// has a single impl candidate, which uses the environment to
+// normalize `<T as Trait>::TraitAssoc` to itself. We avoid this overflow
+// by discarding impl candidates the trait bound is proven by a where-clause.
+
+// https://github.com/rust-lang/trait-system-refactor-initiative/issues/76
+trait Super {
+    type SuperAssoc;
+}
+
+trait Trait: Super<SuperAssoc = Self::TraitAssoc> {
+    type TraitAssoc;
+}
+
+impl<T, U> Trait for T
+where
+    T: Super<SuperAssoc = U>,
+{
+    type TraitAssoc = U;
+}
+
+fn overflow<T: Trait>() {
+    let x: <T as Trait>::TraitAssoc;
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-2.rs b/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-2.rs
new file mode 100644
index 00000000000..b0ef0d44baf
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-2.rs
@@ -0,0 +1,29 @@
+// revisions: next current
+//[next] compile-flags: -Znext-solver
+// check-pass
+
+#![allow(warnings)]
+trait Trait<U> {
+    type Assoc;
+}
+
+impl<T> Trait<u64> for T {
+    type Assoc = T;
+}
+
+fn lazy_init<T: Trait<U>, U>() -> (T, <T as Trait<U>>::Assoc) {
+    todo!()
+}
+
+fn foo<T: Trait<u32, Assoc = T>>(x: T) {
+    // When considering impl candidates to be equally valid as env candidates
+    // this ends up being ambiguous as `U` can be both `u32´ and `u64` here.
+    //
+    // This is acceptable breakage but we should still note that it's
+    // theoretically breaking.
+    let (delayed, mut proj) = lazy_init::<_, _>();
+    proj = x;
+    let _: T = delayed;
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-3.rs b/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-3.rs
new file mode 100644
index 00000000000..807e19a4a58
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/discard-impls-shadowed-by-env-3.rs
@@ -0,0 +1,18 @@
+// compile-flags: -Znext-solver
+// check-pass
+
+// If we normalize using the impl here the constraints from normalization and
+// trait goals can differ. This is especially bad if normalization results
+// in stronger constraints.
+trait Trait<'a> {
+    type Assoc;
+}
+
+impl<T> Trait<'static> for T {
+    type Assoc = ();
+}
+
+// normalizing requires `'a == 'static`, the trait bound does not.
+fn foo<'a, T: Trait<'a>>(_: T::Assoc) {}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/normalizes_to_ignores_unnormalizable_candidate.rs b/tests/ui/traits/next-solver/env-shadows-impls/normalizes_to_ignores_unnormalizable_candidate.rs
new file mode 100644
index 00000000000..af2c44ea233
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/normalizes_to_ignores_unnormalizable_candidate.rs
@@ -0,0 +1,29 @@
+// compile-flags: -Znext-solver
+
+// Checks whether the new solver is smart enough to infer `?0 = U` when solving:
+// `normalizes-to(<Vec<?0> as Trait>::Assoc, u8)`
+// with `normalizes-to(<Vec<U> as Trait>::Assoc, u8)` in the paramenv even when
+// there is a separate `Vec<T>: Trait` bound  in the paramenv.
+//
+// We currently intentionally do not guide inference this way.
+
+trait Trait {
+    type Assoc;
+}
+
+fn foo<T: Trait<Assoc = u8>>(x: T) {}
+
+fn unconstrained<T>() -> Vec<T> {
+    todo!()
+}
+
+fn bar<T, U>()
+where
+    Vec<T>: Trait,
+    Vec<U>: Trait<Assoc = u8>,
+{
+    foo(unconstrained())
+    //~^ ERROR type annotations needed
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/normalizes_to_ignores_unnormalizable_candidate.self_infer.stderr b/tests/ui/traits/next-solver/env-shadows-impls/normalizes_to_ignores_unnormalizable_candidate.stderr
index c1a8b74df08..36d281e11dd 100644
--- a/tests/ui/traits/next-solver/normalizes_to_ignores_unnormalizable_candidate.self_infer.stderr
+++ b/tests/ui/traits/next-solver/env-shadows-impls/normalizes_to_ignores_unnormalizable_candidate.stderr
@@ -1,21 +1,21 @@
 error[E0283]: type annotations needed
-  --> $DIR/normalizes_to_ignores_unnormalizable_candidate.rs:36:5
+  --> $DIR/normalizes_to_ignores_unnormalizable_candidate.rs:25:5
    |
 LL |     foo(unconstrained())
    |     ^^^ --------------- type must be known at this point
    |     |
    |     cannot infer type of the type parameter `T` declared on the function `foo`
    |
-   = note: cannot satisfy `_: Trait`
+   = note: cannot satisfy `Vec<_>: Trait`
 note: required by a bound in `foo`
-  --> $DIR/normalizes_to_ignores_unnormalizable_candidate.rs:19:11
+  --> $DIR/normalizes_to_ignores_unnormalizable_candidate.rs:14:11
    |
 LL | fn foo<T: Trait<Assoc = u8>>(x: T) {}
    |           ^^^^^^^^^^^^^^^^^ required by this bound in `foo`
 help: consider specifying the generic argument
    |
-LL |     foo::<T>(unconstrained())
-   |        +++++
+LL |     foo::<Vec<T>>(unconstrained())
+   |        ++++++++++
 
 error: aborting due to 1 previous error
 
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/param-candidate-shadows-project.rs b/tests/ui/traits/next-solver/env-shadows-impls/param-candidate-shadows-project.rs
new file mode 100644
index 00000000000..5989e605bd9
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/param-candidate-shadows-project.rs
@@ -0,0 +1,31 @@
+// compile-flags: -Znext-solver
+
+trait Foo {
+    type Assoc;
+}
+
+trait Bar {}
+
+impl<T> Foo for T {
+    type Assoc = i32;
+}
+
+impl<T> Bar for T where T: Foo<Assoc = i32> {}
+
+fn require_bar<T: Bar>() {}
+
+fn foo<T: Foo>() {
+    // Unlike the classic solver, the new solver previously projected
+    // `<T as Foo>::Assoc = _` down to `i32` even though there's a param-env
+    // candidate here, since we don't assemble any param-env projection
+    // candidates for `T: Foo` alone.
+    //
+    // However, allowing impl candidates shadowed by env candidates results
+    // in multiple issues, so we explicitly hide them, e.g.
+    //
+    //     https://github.com/rust-lang/trait-system-refactor-initiative/issues/76
+    require_bar::<T>();
+    //~^ ERROR the trait bound `T: Bar` is not satisfied
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/env-shadows-impls/param-candidate-shadows-project.stderr b/tests/ui/traits/next-solver/env-shadows-impls/param-candidate-shadows-project.stderr
new file mode 100644
index 00000000000..2785357e792
--- /dev/null
+++ b/tests/ui/traits/next-solver/env-shadows-impls/param-candidate-shadows-project.stderr
@@ -0,0 +1,19 @@
+error[E0277]: the trait bound `T: Bar` is not satisfied
+  --> $DIR/param-candidate-shadows-project.rs:27:19
+   |
+LL |     require_bar::<T>();
+   |                   ^ the trait `Bar` is not implemented for `T`
+   |
+note: required by a bound in `require_bar`
+  --> $DIR/param-candidate-shadows-project.rs:15:19
+   |
+LL | fn require_bar<T: Bar>() {}
+   |                   ^^^ required by this bound in `require_bar`
+help: consider further restricting this bound
+   |
+LL | fn foo<T: Foo + Bar>() {
+   |               +++++
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/traits/next-solver/generalize/occurs-check-nested-alias.next.stderr b/tests/ui/traits/next-solver/generalize/occurs-check-nested-alias.next.stderr
index ad8b24a39c7..aaadf604a80 100644
--- a/tests/ui/traits/next-solver/generalize/occurs-check-nested-alias.next.stderr
+++ b/tests/ui/traits/next-solver/generalize/occurs-check-nested-alias.next.stderr
@@ -1,11 +1,9 @@
-error[E0275]: overflow evaluating the requirement `<<T as Id<_>>::Id as Unnormalizable>::Assoc == _`
+error[E0284]: type annotations needed: cannot satisfy `<<T as Id<_>>::Id as Unnormalizable>::Assoc == _`
   --> $DIR/occurs-check-nested-alias.rs:36:9
    |
 LL |     x = y;
-   |         ^
-   |
-   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`occurs_check_nested_alias`)
+   |         ^ cannot satisfy `<<T as Id<_>>::Id as Unnormalizable>::Assoc == _`
 
 error: aborting due to 1 previous error
 
-For more information about this error, try `rustc --explain E0275`.
+For more information about this error, try `rustc --explain E0284`.
diff --git a/tests/ui/traits/next-solver/normalize-param-env-2.rs b/tests/ui/traits/next-solver/normalize-param-env-2.rs
index ce084651bfb..9da1f8dbec1 100644
--- a/tests/ui/traits/next-solver/normalize-param-env-2.rs
+++ b/tests/ui/traits/next-solver/normalize-param-env-2.rs
@@ -1,24 +1,29 @@
-// check-pass
 // compile-flags: -Znext-solver
-// Issue 92505
+// known-bug: #92505
 
+// When checking that the impl method where-bounds are implied by the trait,
+// we prove  `<() as A<T>>::Assoc: A<T>` in the environment `<() as A<T>>::Assoc: A<T>`.
+//
+// Normalizing `<() as A<T>>::Assoc` is ambiguous in that environment. The
+// where-bound `<() as A<T>>::Assoc: A<T>` may apply, resulting in overflow.
 trait A<T> {
-    type I;
+    type Assoc;
 
     fn f()
     where
-        Self::I: A<T>,
+        Self::Assoc: A<T>,
     {
     }
 }
 
 impl<T> A<T> for () {
-    type I = ();
+    type Assoc = ();
 
     fn f()
     where
-        Self::I: A<T>,
+        Self::Assoc: A<T>,
     {
+
         <() as A<T>>::f();
     }
 }
diff --git a/tests/ui/traits/next-solver/normalize-param-env-2.stderr b/tests/ui/traits/next-solver/normalize-param-env-2.stderr
new file mode 100644
index 00000000000..a52022e539e
--- /dev/null
+++ b/tests/ui/traits/next-solver/normalize-param-env-2.stderr
@@ -0,0 +1,35 @@
+error[E0275]: overflow evaluating the requirement `<() as A<T>>::Assoc: A<T>`
+  --> $DIR/normalize-param-env-2.rs:24:22
+   |
+LL |         Self::Assoc: A<T>,
+   |                      ^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`normalize_param_env_2`)
+note: the requirement `<() as A<T>>::Assoc: A<T>` appears on the `impl`'s method `f` but not on the corresponding trait's method
+  --> $DIR/normalize-param-env-2.rs:12:8
+   |
+LL | trait A<T> {
+   |       - in this trait
+...
+LL |     fn f()
+   |        ^ this trait's method doesn't have the requirement `<() as A<T>>::Assoc: A<T>`
+
+error[E0275]: overflow evaluating the requirement `<() as A<T>>::Assoc: A<T>`
+  --> $DIR/normalize-param-env-2.rs:24:22
+   |
+LL |         Self::Assoc: A<T>,
+   |                      ^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`normalize_param_env_2`)
+
+error[E0275]: overflow evaluating the requirement `<() as A<T>>::Assoc well-formed`
+  --> $DIR/normalize-param-env-2.rs:24:22
+   |
+LL |         Self::Assoc: A<T>,
+   |                      ^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`normalize_param_env_2`)
+
+error: aborting due to 3 previous errors
+
+For more information about this error, try `rustc --explain E0275`.
diff --git a/tests/ui/traits/next-solver/normalize-param-env-4.next.stderr b/tests/ui/traits/next-solver/normalize-param-env-4.next.stderr
new file mode 100644
index 00000000000..dec820c61b0
--- /dev/null
+++ b/tests/ui/traits/next-solver/normalize-param-env-4.next.stderr
@@ -0,0 +1,19 @@
+error[E0275]: overflow evaluating the requirement `<T as Trait>::Assoc: Trait`
+  --> $DIR/normalize-param-env-4.rs:18:26
+   |
+LL |     <T as Trait>::Assoc: Trait,
+   |                          ^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`normalize_param_env_4`)
+
+error[E0275]: overflow evaluating the requirement `<T as Trait>::Assoc well-formed`
+  --> $DIR/normalize-param-env-4.rs:18:26
+   |
+LL |     <T as Trait>::Assoc: Trait,
+   |                          ^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`normalize_param_env_4`)
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0275`.
diff --git a/tests/ui/traits/next-solver/normalize-param-env-4.rs b/tests/ui/traits/next-solver/normalize-param-env-4.rs
new file mode 100644
index 00000000000..d49f7492297
--- /dev/null
+++ b/tests/ui/traits/next-solver/normalize-param-env-4.rs
@@ -0,0 +1,34 @@
+// revisions: current next
+//[next] compile-flags: -Znext-solver
+//[next] known-bug: #92505
+//[current] check-pass
+
+trait Trait {
+    type Assoc;
+}
+
+impl<T> Trait for T {
+    type Assoc = T;
+}
+
+fn impls_trait<T: Trait>() {}
+
+fn foo<T>()
+where
+    <T as Trait>::Assoc: Trait,
+{
+    // Trying to use `<T as Trait>::Assoc: Trait` to prove `T: Trait`
+    // requires normalizing `<T as Trait>::Assoc`. We do not normalize
+    // using impl candidates if there's a where-bound for that trait.
+    //
+    // We therefore check whether `T: Trait` is proven by the environment.
+    // For that we try to apply the `<T as Trait>::Assoc: Trait` candidate,
+    // trying to normalize its self type results in overflow.
+    //
+    // In the old solver we eagerly normalize the environment, ignoring the
+    // unnormalized `<T as Trait>::Assoc: Trait` where-bound when normalizing
+    // `<T as Trait>::Asosc`
+    impls_trait::<T>();
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/normalizes_to_ignores_unnormalizable_candidate.rs b/tests/ui/traits/next-solver/normalizes_to_ignores_unnormalizable_candidate.rs
deleted file mode 100644
index 7dc87daccd9..00000000000
--- a/tests/ui/traits/next-solver/normalizes_to_ignores_unnormalizable_candidate.rs
+++ /dev/null
@@ -1,40 +0,0 @@
-// [no_self_infer] check-pass
-// compile-flags: -Znext-solver
-// revisions: self_infer no_self_infer
-
-// checks that the new solver is smart enough to infer `?0 = U` when solving:
-// `normalizes-to(<Vec<?0> as Trait>::Assoc, u8)`
-// with `normalizes-to(<Vec<U> as Trait>::Assoc, u8)` in the paramenv even when
-// there is a separate `Vec<T>: Trait` bound  in the paramenv.
-//
-// FIXME(-Znext-solver)
-// This could also compile for `normalizes-to(<?0 as Trait>::Assoc, u8)` but
-// we currently immediately consider a goal ambiguous if the self type is an
-// inference variable.
-
-trait Trait {
-    type Assoc;
-}
-
-fn foo<T: Trait<Assoc = u8>>(x: T) {}
-
-#[cfg(self_infer)]
-fn unconstrained<T>() -> T {
-    todo!()
-}
-
-#[cfg(no_self_infer)]
-fn unconstrained<T>() -> Vec<T> {
-    todo!()
-}
-
-fn bar<T, U>()
-where
-    Vec<T>: Trait,
-    Vec<U>: Trait<Assoc = u8>,
-{
-    foo(unconstrained())
-    //[self_infer]~^ ERROR type annotations needed
-}
-
-fn main() {}
diff --git a/tests/ui/traits/next-solver/param-candidate-doesnt-shadow-project.rs b/tests/ui/traits/next-solver/param-candidate-doesnt-shadow-project.rs
deleted file mode 100644
index f67b073c53c..00000000000
--- a/tests/ui/traits/next-solver/param-candidate-doesnt-shadow-project.rs
+++ /dev/null
@@ -1,25 +0,0 @@
-// compile-flags: -Znext-solver
-// check-pass
-
-trait Foo {
-    type Assoc;
-}
-
-trait Bar {}
-
-impl<T> Foo for T {
-    type Assoc = i32;
-}
-
-impl<T> Bar for T where T: Foo<Assoc = i32> {}
-
-fn require_bar<T: Bar>() {}
-
-fn foo<T: Foo>() {
-    // Unlike the classic solver, `<T as Foo>::Assoc = _` will still project
-    // down to `i32` even though there's a param-env candidate here, since we
-    // don't assemble any param-env projection candidates for `T: Foo` alone.
-    require_bar::<T>();
-}
-
-fn main() {}