add and move trait solver cycle tests

21 files changed, 215 insertions, 1 deletions

diff --git a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.rs b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.rs
index 1dca86d3630..1dca86d3630 100644
--- a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.rs
+++ b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.rs
diff --git a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.stderr b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.stderr
index 47004821ad7..47004821ad7 100644
--- a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.stderr
+++ b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.stderr
diff --git a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.rs b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs
index fcafdcf637a..fcafdcf637a 100644
--- a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.rs
+++ b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs
diff --git a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.stderr b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr
index 7d3535e1f01..7d3535e1f01 100644
--- a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.stderr
+++ b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr
diff --git a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs
index 0cd14f05c8d..0cd14f05c8d 100644
--- a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs
+++ b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs
diff --git a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.stderr b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr
index f1871ff0564..f1871ff0564 100644
--- a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.stderr
+++ b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr
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 00000000000..5617e45adf6
--- /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 00000000000..4b8846da535
--- /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 00000000000..cda98789886
--- /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 00000000000..57227321a6d
--- /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 00000000000..d4851eb694b
--- /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 00000000000..530e6d0ecf3
--- /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/leak-check-coinductive-cycle.rs b/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs
index 1f7d4a49c90..a6d31872673 100644
--- a/tests/ui/traits/new-solver/leak-check-coinductive-cycle.rs
+++ b/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs
@@ -1,5 +1,5 @@
-// check-pass
 // compile-flags: -Ztrait-solver=next
+// check-pass
 #![feature(rustc_attrs)]
 
 #[rustc_coinductive]
diff --git a/tests/ui/traits/new-solver/provisional-result-done.rs b/tests/ui/traits/new-solver/cycles/provisional-result-done.rs
index 589d34dd7ab..589d34dd7ab 100644
--- a/tests/ui/traits/new-solver/provisional-result-done.rs
+++ b/tests/ui/traits/new-solver/cycles/provisional-result-done.rs
diff --git a/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs b/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs
index 7d15b8c6392..af35a6195e0 100644
--- a/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs
+++ b/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs
@@ -1,6 +1,10 @@
 // compile-flags: -Ztrait-solver=next
 // check-pass
 
+// Test that selection prefers the builtin trait object impl for `Any`
+// instead of the user defined impl. Both impls apply to the trait
+// object.
+
 use std::any::Any;
 
 fn needs_usize(_: &usize) {}
diff --git a/tests/ui/traits/new-solver/exponential-trait-goals.rs b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.rs
index b37f09ee185..b37f09ee185 100644
--- a/tests/ui/traits/new-solver/exponential-trait-goals.rs
+++ b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.rs
diff --git a/tests/ui/traits/new-solver/exponential-trait-goals.stderr b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.stderr
index 28a99cbbca6..28a99cbbca6 100644
--- a/tests/ui/traits/new-solver/exponential-trait-goals.stderr
+++ b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.stderr
diff --git a/tests/ui/traits/new-solver/recursive-self-normalization-2.rs b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.rs
index d086db475ac..d086db475ac 100644
--- a/tests/ui/traits/new-solver/recursive-self-normalization-2.rs
+++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.rs
diff --git a/tests/ui/traits/new-solver/recursive-self-normalization-2.stderr b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.stderr
index eebaf21d7df..eebaf21d7df 100644
--- a/tests/ui/traits/new-solver/recursive-self-normalization-2.stderr
+++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.stderr
diff --git a/tests/ui/traits/new-solver/recursive-self-normalization.rs b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.rs
index d15df7dea73..d15df7dea73 100644
--- a/tests/ui/traits/new-solver/recursive-self-normalization.rs
+++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.rs
diff --git a/tests/ui/traits/new-solver/recursive-self-normalization.stderr b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.stderr
index 6a87fe2f121..6a87fe2f121 100644
--- a/tests/ui/traits/new-solver/recursive-self-normalization.stderr
+++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.stderr