Rollup merge of #105661 - lcnr:evaluate-new, r=compiler-errors

implement the skeleton of the updated trait solver

cc ```@rust-lang/initiative-trait-system-refactor```

This is mostly following the architecture discussed in the types team meetup.

After discussing the desired changes for the trait solver, we encountered cyclic dependencies between them. Most notably between changing evaluate to be canonical and returning inference constraints. We cannot canonicalize evaluate without returning inference constraints due to coinductive cycles. However, caching inference constraints also relies on canonicalization. Implementing both of these changes at once in-place is not feasible.

This somewhat closely mirrors the current `evaluate` implementation with the following notable differences:
- it moves `project` into the core solver, allowing us to correctly deal with coinductive projections (will be required for implied bounds, perfect derive)
- it changes trait solver overflow to be non-fatal (required to backcompat breakage from changes to the iteration order of nested goals, deferred projection equality, generally very useful)
- it returns inference constraints and canonicalizes inputs and outputs (required for a lot things, most notably merging fulfill and evaluate, and deferred projection equality)
- it is implemented to work with lazy normalization

A lot of things aren't yet implemented, but the remaining FIXMEs should all be fairly self-contained and parallelizable. If the architecture looks correct and is what we want here, I would like to quickly merge this and then split the work.

r? ```@compiler-errors``` / ```@rust-lang/types``` :3

2 files changed, 54 insertions, 0 deletions

diff --git a/src/test/ui/traits/solver-cycles/inductive-canonical-cycle.rs b/src/test/ui/traits/solver-cycles/inductive-canonical-cycle.rs
new file mode 100644
index 00000000000..a3bb76d7e3b
--- /dev/null
+++ b/src/test/ui/traits/solver-cycles/inductive-canonical-cycle.rs
@@ -0,0 +1,28 @@
+// known-bug
+
+// This should compile but fails with the current solver.
+//
+// This checks that the new solver uses `Ambiguous` when hitting the
+// inductive cycle here when proving `exists<^0, ^1> (): Trait<^0, ^1>`
+// which requires proving `Trait<?1, ?0>` but that has the same
+// canonical representation.
+trait Trait<T, U> {}
+
+impl<T, U> Trait<T, U> for ()
+where
+    (): Trait<U, T>,
+    T: OtherTrait,
+{}
+
+trait OtherTrait {}
+impl OtherTrait for u32 {}
+
+fn require_trait<T, U>()
+where
+    (): Trait<T, U>
+{}
+
+fn main() {
+    require_trait::<_, _>();
+    //~^ ERROR overflow evaluating
+}
diff --git a/src/test/ui/traits/solver-cycles/inductive-canonical-cycle.stderr b/src/test/ui/traits/solver-cycles/inductive-canonical-cycle.stderr
new file mode 100644
index 00000000000..e4b84e07822
--- /dev/null
+++ b/src/test/ui/traits/solver-cycles/inductive-canonical-cycle.stderr
@@ -0,0 +1,26 @@
+error[E0275]: overflow evaluating the requirement `_: Sized`
+  --> $DIR/inductive-canonical-cycle.rs:26:5
+   |
+LL |     require_trait::<_, _>();
+   |     ^^^^^^^^^^^^^^^^^^^^^
+   |
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`inductive_canonical_cycle`)
+note: required for `()` to implement `Trait<_, _>`
+  --> $DIR/inductive-canonical-cycle.rs:11:12
+   |
+LL | impl<T, U> Trait<T, U> for ()
+   |            ^^^^^^^^^^^     ^^
+   = note: 128 redundant requirements hidden
+   = note: required for `()` to implement `Trait<_, _>`
+note: required by a bound in `require_trait`
+  --> $DIR/inductive-canonical-cycle.rs:22:9
+   |
+LL | fn require_trait<T, U>()
+   |    ------------- required by a bound in this
+LL | where
+LL |     (): Trait<T, U>
+   |         ^^^^^^^^^^^ required by this bound in `require_trait`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0275`.