Merging upstream version 1.73.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

14 files changed, 478 insertions, 0 deletions

diff --git a/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs
new file mode 100644
index 000000000..fcafdcf63
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs
@@ -0,0 +1,32 @@
+// compile-flags: -Ztrait-solver=next
+
+// Proving `W<?0>: Trait` instantiates `?0` with `(W<?1>, W<?2>)` and then
+// proves `W<?1>: Trait` and `W<?2>: Trait`, resulting in a coinductive cycle.
+//
+// Proving coinductive cycles runs until we reach a fixpoint. This fixpoint is
+// never reached here and each step doubles the amount of nested obligations.
+//
+// This previously caused a hang in the trait solver, see
+// https://github.com/rust-lang/trait-system-refactor-initiative/issues/13.
+
+#![feature(rustc_attrs)]
+
+#[rustc_coinductive]
+trait Trait {}
+
+struct W<T>(T);
+
+impl<T, U> Trait for W<(W<T>, W<U>)>
+where
+    W<T>: Trait,
+    W<U>: Trait,
+{
+}
+
+fn impls<T: Trait>() {}
+
+fn main() {
+    impls::<W<_>>();
+    //~^ ERROR type annotations needed
+    //~| ERROR overflow evaluating the requirement
+}
diff --git a/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr
new file mode 100644
index 000000000..7d3535e1f
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr
@@ -0,0 +1,23 @@
+error[E0282]: type annotations needed
+  --> $DIR/fixpoint-exponential-growth.rs:29:5
+   |
+LL |     impls::<W<_>>();
+   |     ^^^^^^^^^^^^^ cannot infer type of the type parameter `T` declared on the function `impls`
+
+error[E0275]: overflow evaluating the requirement `W<_>: Trait`
+  --> $DIR/fixpoint-exponential-growth.rs:29:5
+   |
+LL |     impls::<W<_>>();
+   |     ^^^^^^^^^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`fixpoint_exponential_growth`)
+note: required by a bound in `impls`
+  --> $DIR/fixpoint-exponential-growth.rs:26:13
+   |
+LL | fn impls<T: Trait>() {}
+   |             ^^^^^ required by this bound in `impls`
+
+error: aborting due to 2 previous errors
+
+Some errors have detailed explanations: E0275, E0282.
+For more information about an error, try `rustc --explain E0275`.
diff --git a/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs
new file mode 100644
index 000000000..0cd14f05c
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs
@@ -0,0 +1,69 @@
+// compile-flags: -Ztrait-solver=next
+#![feature(rustc_attrs)]
+
+// This test is incredibly subtle. At its core the goal is to get a coinductive cycle,
+// which, depending on its root goal, either holds or errors. We achieve this by getting
+// incomplete inference via a `ParamEnv` candidate in the `A<T>` impl and required
+// inference from an `Impl` candidate in the `B<T>` impl.
+//
+// To make global cache accesses stronger than the guidance from the where-bounds, we add
+// another coinductive cycle from `A<T>: Trait<U, V, D>` to `A<T>: Trait<U, D, V>` and only
+// constrain `D` directly. This means that any candidates which rely on `V` only make
+// progress in the second iteration, allowing a cache access in the first iteration to take
+// precedence.
+//
+// tl;dr: our caching of coinductive cycles was broken and this is a regression
+// test for that.
+
+#[rustc_coinductive]
+trait Trait<T: ?Sized, V: ?Sized, D: ?Sized> {}
+struct A<T: ?Sized>(*const T);
+struct B<T: ?Sized>(*const T);
+
+trait IncompleteGuidance<T: ?Sized, V: ?Sized> {}
+impl<T: ?Sized, U: ?Sized + 'static> IncompleteGuidance<U, u8> for T {}
+impl<T: ?Sized, U: ?Sized + 'static> IncompleteGuidance<U, i8> for T {}
+impl<T: ?Sized, U: ?Sized + 'static> IncompleteGuidance<U, i16> for T {}
+
+trait ImplGuidance<T: ?Sized, V: ?Sized> {}
+impl<T: ?Sized> ImplGuidance<u32, u8> for T {}
+impl<T: ?Sized> ImplGuidance<i32, i8> for T {}
+
+impl<T: ?Sized, U: ?Sized, V: ?Sized, D: ?Sized> Trait<U, V, D> for A<T>
+where
+    T: IncompleteGuidance<U, V>,
+    A<T>: Trait<U, D, V>,
+    B<T>: Trait<U, V, D>,
+    (): ToU8<D>,
+{
+}
+
+trait ToU8<T: ?Sized> {}
+impl ToU8<u8> for () {}
+
+impl<T: ?Sized, U: ?Sized, V: ?Sized, D: ?Sized> Trait<U, V, D> for B<T>
+where
+    T: ImplGuidance<U, V>,
+    A<T>: Trait<U, V, D>,
+{
+}
+
+fn impls_trait<T: ?Sized + Trait<U, V, D>, U: ?Sized, V: ?Sized, D: ?Sized>() {}
+
+fn with_bound<X>()
+where
+    X: IncompleteGuidance<i32, u8>,
+    X: IncompleteGuidance<u32, i8>,
+    X: IncompleteGuidance<u32, i16>,
+{
+    impls_trait::<B<X>, _, _, _>(); // entering the cycle from `B` works
+
+    // entering the cycle from `A` fails, but would work if we were to use the cache
+    // result of `B<X>`.
+    impls_trait::<A<X>, _, _, _>();
+    //~^ ERROR the trait bound `A<X>: Trait<_, _, _>` is not satisfied
+}
+
+fn main() {
+    with_bound::<u32>();
+}
diff --git a/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr
new file mode 100644
index 000000000..f1871ff05
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr
@@ -0,0 +1,16 @@
+error[E0277]: the trait bound `A<X>: Trait<_, _, _>` is not satisfied
+  --> $DIR/incompleteness-unstable-result.rs:63:19
+   |
+LL |     impls_trait::<A<X>, _, _, _>();
+   |                   ^^^^ the trait `Trait<_, _, _>` is not implemented for `A<X>`
+   |
+   = help: the trait `Trait<U, V, D>` is implemented for `A<T>`
+note: required by a bound in `impls_trait`
+  --> $DIR/incompleteness-unstable-result.rs:51:28
+   |
+LL | fn impls_trait<T: ?Sized + Trait<U, V, D>, U: ?Sized, V: ?Sized, D: ?Sized>() {}
+   |                            ^^^^^^^^^^^^^^ required by this bound in `impls_trait`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.rs b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.rs
new file mode 100644
index 000000000..5617e45ad
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.rs
@@ -0,0 +1,37 @@
+// compile-flags: -Ztrait-solver=next
+#![feature(rustc_attrs)]
+
+// Test that having both an inductive and a coinductive cycle
+// is handled correctly.
+
+#[rustc_coinductive]
+trait Trait {}
+impl<T: Inductive + Coinductive> Trait for T {}
+
+trait Inductive {}
+impl<T: Trait> Inductive for T {}
+#[rustc_coinductive]
+trait Coinductive {}
+impl<T: Trait> Coinductive for T {}
+
+fn impls_trait<T: Trait>() {}
+
+#[rustc_coinductive]
+trait TraitRev {}
+impl<T: CoinductiveRev + InductiveRev> TraitRev for T {}
+
+trait InductiveRev {}
+impl<T: TraitRev> InductiveRev for T {}
+#[rustc_coinductive]
+trait CoinductiveRev {}
+impl<T: TraitRev> CoinductiveRev for T {}
+
+fn impls_trait_rev<T: TraitRev>() {}
+
+fn main() {
+    impls_trait::<()>();
+    //~^ ERROR overflow evaluating the requirement
+
+    impls_trait_rev::<()>();
+    //~^ ERROR overflow evaluating the requirement
+}
diff --git a/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.stderr b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.stderr
new file mode 100644
index 000000000..4b8846da5
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.stderr
@@ -0,0 +1,29 @@
+error[E0275]: overflow evaluating the requirement `(): Trait`
+  --> $DIR/double-cycle-inductive-coinductive.rs:32:5
+   |
+LL |     impls_trait::<()>();
+   |     ^^^^^^^^^^^^^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`double_cycle_inductive_coinductive`)
+note: required by a bound in `impls_trait`
+  --> $DIR/double-cycle-inductive-coinductive.rs:17:19
+   |
+LL | fn impls_trait<T: Trait>() {}
+   |                   ^^^^^ required by this bound in `impls_trait`
+
+error[E0275]: overflow evaluating the requirement `(): TraitRev`
+  --> $DIR/double-cycle-inductive-coinductive.rs:35:5
+   |
+LL |     impls_trait_rev::<()>();
+   |     ^^^^^^^^^^^^^^^^^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`double_cycle_inductive_coinductive`)
+note: required by a bound in `impls_trait_rev`
+  --> $DIR/double-cycle-inductive-coinductive.rs:29:23
+   |
+LL | fn impls_trait_rev<T: TraitRev>() {}
+   |                       ^^^^^^^^ required by this bound in `impls_trait_rev`
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0275`.
diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.rs b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.rs
new file mode 100644
index 000000000..cda987898
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.rs
@@ -0,0 +1,48 @@
+// compile-flags: -Ztrait-solver=next
+#![feature(trivial_bounds, marker_trait_attr)]
+#![allow(trivial_bounds)]
+// This previously triggered a bug in the provisional cache.
+//
+// This has the proof tree
+// - `MultipleCandidates: Trait` proven via impl-one
+//   - `MultipleNested: Trait` via impl
+//     - `MultipleCandidates: Trait` (inductive cycle ~> OVERFLOW)
+//     - `DoesNotImpl: Trait` (ERR)
+// - `MultipleCandidates: Trait` proven via impl-two
+//   - `MultipleNested: Trait` (in provisional cache ~> OVERFLOW)
+//
+// We previously incorrectly treated the `MultipleCandidates: Trait` as
+// overflow because it was in the cache and reached via an inductive cycle.
+// It should be `NoSolution`.
+
+struct MultipleCandidates;
+struct MultipleNested;
+struct DoesNotImpl;
+
+#[marker]
+trait Trait {}
+
+// impl-one
+impl Trait for MultipleCandidates
+where
+    MultipleNested: Trait
+{}
+
+// impl-two
+impl Trait for MultipleCandidates
+where
+    MultipleNested: Trait,
+{}
+
+impl Trait for MultipleNested
+where
+    MultipleCandidates: Trait,
+    DoesNotImpl: Trait,
+{}
+
+fn impls_trait<T: Trait>() {}
+
+fn main() {
+    impls_trait::<MultipleCandidates>();
+    //~^ ERROR the trait bound `MultipleCandidates: Trait` is not satisfied
+}
diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.stderr b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.stderr
new file mode 100644
index 000000000..57227321a
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.stderr
@@ -0,0 +1,16 @@
+error[E0277]: the trait bound `MultipleCandidates: Trait` is not satisfied
+  --> $DIR/inductive-cycle-but-err.rs:46:19
+   |
+LL |     impls_trait::<MultipleCandidates>();
+   |                   ^^^^^^^^^^^^^^^^^^ the trait `Trait` is not implemented for `MultipleCandidates`
+   |
+   = help: the trait `Trait` is implemented for `MultipleCandidates`
+note: required by a bound in `impls_trait`
+  --> $DIR/inductive-cycle-but-err.rs:43:19
+   |
+LL | fn impls_trait<T: Trait>() {}
+   |                   ^^^^^ required by this bound in `impls_trait`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-but-ok.rs b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-ok.rs
new file mode 100644
index 000000000..d4851eb69
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-ok.rs
@@ -0,0 +1,44 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+#![feature(trivial_bounds, marker_trait_attr)]
+#![allow(trivial_bounds)]
+
+// This previously triggered a bug in the provisional cache.
+//
+// This has the proof tree
+// - `Root: Trait` proven via impl
+//   - `MultipleCandidates: Trait`
+//     - candidate: overflow-impl
+//       - `Root: Trait` (inductive cycle ~> OVERFLOW)
+//     - candidate: trivial-impl ~> YES
+//     - merge respones ~> YES
+//   - `MultipleCandidates: Trait` (in provisional cache ~> OVERFLOW)
+//
+// We previously incorrectly treated the `MultipleCandidates: Trait` as
+// overflow because it was in the cache and reached via an inductive cycle.
+// It should be `YES`.
+
+struct Root;
+struct MultipleCandidates;
+
+#[marker]
+trait Trait {}
+impl Trait for Root
+where
+    MultipleCandidates: Trait,
+    MultipleCandidates: Trait,
+{}
+
+// overflow-impl
+impl Trait for MultipleCandidates
+where
+    Root: Trait,
+{}
+// trivial-impl
+impl Trait for MultipleCandidates {}
+
+fn impls_trait<T: Trait>() {}
+
+fn main() {
+    impls_trait::<Root>();
+}
diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-discarded-coinductive-constraints.rs b/tests/ui/traits/new-solver/cycles/inductive-cycle-discarded-coinductive-constraints.rs
new file mode 100644
index 000000000..530e6d0ec
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-discarded-coinductive-constraints.rs
@@ -0,0 +1,36 @@
+// check-pass
+// compile-flags: -Ztrait-solver=next
+#![feature(rustc_attrs, marker_trait_attr)]
+#[rustc_coinductive]
+trait Trait {}
+
+impl<T, U> Trait for (T, U)
+where
+    (U, T): Trait,
+    (T, U): Inductive,
+    (): ConstrainToU32<T>,
+{}
+
+trait ConstrainToU32<T> {}
+impl ConstrainToU32<u32> for () {}
+
+// We only prefer the candidate without an inductive cycle
+// once the inductive cycle has the same constraints as the
+// other goal.
+#[marker]
+trait Inductive {}
+impl<T, U> Inductive for (T, U)
+where
+    (T, U): Trait,
+{}
+
+impl Inductive for (u32, u32) {}
+
+fn impls_trait<T, U>()
+where
+    (T, U): Trait,
+{}
+
+fn main() {
+    impls_trait::<_, _>();
+}
diff --git a/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs
new file mode 100644
index 000000000..3cfe7ab87
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs
@@ -0,0 +1,46 @@
+// compile-flags: -Ztrait-solver=next
+#![feature(rustc_attrs, trivial_bounds)]
+
+// We have to be careful here:
+//
+// We either have the provisional result of `A -> B -> A` on the
+// stack, which is a fully coinductive cycle. Accessing the
+// provisional result for `B` as part of the `A -> C -> B -> A` cycle
+// has to make sure we don't just use the result of `A -> B -> A` as the
+// new cycle is inductive.
+//
+// Alternatively, if we have `A -> C -> A` first, then `A -> B -> A` has
+// a purely inductive stack, so something could also go wrong here.
+
+#[rustc_coinductive]
+trait A {}
+#[rustc_coinductive]
+trait B {}
+trait C {}
+
+impl<T: B + C> A for T {}
+impl<T: A> B for T {}
+impl<T: B> C for T {}
+
+fn impls_a<T: A>() {}
+
+// The same test with reordered where clauses to make sure we're actually testing anything.
+#[rustc_coinductive]
+trait AR {}
+#[rustc_coinductive]
+trait BR {}
+trait CR {}
+
+impl<T: CR + BR> AR for T {}
+impl<T: AR> BR for T {}
+impl<T: BR> CR for T {}
+
+fn impls_ar<T: AR>() {}
+
+fn main() {
+    impls_a::<()>();
+    // FIXME(-Ztrait-solver=next): This is broken and should error.
+
+    impls_ar::<()>();
+    //~^ ERROR overflow evaluating the requirement `(): AR`
+}
diff --git a/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr
new file mode 100644
index 000000000..0e1c86c1b
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr
@@ -0,0 +1,16 @@
+error[E0275]: overflow evaluating the requirement `(): AR`
+  --> $DIR/inductive-not-on-stack.rs:44:5
+   |
+LL |     impls_ar::<()>();
+   |     ^^^^^^^^^^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`inductive_not_on_stack`)
+note: required by a bound in `impls_ar`
+  --> $DIR/inductive-not-on-stack.rs:38:16
+   |
+LL | fn impls_ar<T: AR>() {}
+   |                ^^ required by this bound in `impls_ar`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0275`.
diff --git a/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs b/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs
new file mode 100644
index 000000000..a6d318726
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs
@@ -0,0 +1,33 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+#![feature(rustc_attrs)]
+
+#[rustc_coinductive]
+trait Trait<T> {}
+impl<'a, 'b, T> Trait<T> for (&'a (), &'b ())
+where
+    'b: 'a,
+    &'a (): Trait<T>,
+{}
+
+impl Trait<i32> for &'static () {}
+impl<'a> Trait<u32> for &'a ()
+where
+    for<'b> (&'a (), &'b ()): Trait<u32>,
+{}
+
+
+fn impls_trait<T: Trait<U>, U>() {}
+
+fn main() {
+    // This infers to `impls_trait::<(&'static (), &'static ()), i32>();`
+    //
+    // In the first attempt we have 2 candidates for `&'a (): Trait<_>`
+    // and we get ambiguity. The result is therefore ambiguity with a `'b: 'a`
+    // constraint. The next attempt then uses that provisional result when
+    // trying to apply `impl<'a> Trait<u32> for &'a ()`. This means we get a
+    // `for<'b> 'b: 'a` bound which fails the leak check. Because of this we
+    // end up with a single impl for `&'a (): Trait<_>` which infers `_` to `i32`
+    // and succeeds.
+    impls_trait::<(&(), &()), _>();
+}
diff --git a/tests/ui/traits/new-solver/cycles/provisional-result-done.rs b/tests/ui/traits/new-solver/cycles/provisional-result-done.rs
new file mode 100644
index 000000000..589d34dd7
--- /dev/null
+++ b/tests/ui/traits/new-solver/cycles/provisional-result-done.rs
@@ -0,0 +1,33 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+// This tests checks that we update results in the provisional cache when
+// we pop a goal from the stack.
+#![feature(auto_traits)]
+auto trait Coinductive {}
+struct Foo<T>(T);
+struct Bar<T>(T);
+
+impl<T> Coinductive for Foo<T>
+where
+    Bar<T>: Coinductive
+{}
+
+impl<T> Coinductive for Bar<T>
+where
+    Foo<T>: Coinductive,
+    Bar<T>: ConstrainInfer,
+{}
+
+trait ConstrainInfer {}
+impl ConstrainInfer for Bar<u8> {}
+impl ConstrainInfer for Foo<u16> {}
+
+fn impls<T: Coinductive>() -> T { todo!() }
+
+fn constrain<T: ConstrainInfer>(_: T) {}
+
+fn main() {
+    // This should constrain `_` to `u8`.
+    impls::<Foo<_>>();
+}