Auto merge of #56384 - scalexm:chalk, r=nikomatsakis

Implement the new-style trait solver

Final PR of what I believe to be a minimally working implementation of the new-style trait solver.

The new trait solver can be used by providing the `-Z chalk` command line flag. It is currently used everywhere in `rustc_typeck`, and for everything relying on `rustc::infer::canonical::query_response::enter_canonical_trait_query`.

The trait solver is invoked in rustc by using the `evaluate_goal` canonical query. This is not optimal because each call to `evaluate_goal` creates a new `chalk_engine::Forest`, hence rustc cannot use answers to intermediate goals produced by the root goal. We'll need to change that but I guess that's ok for now.

Some next steps, I think, are:
* handle region constraints: region constraints are computed but are completely ignored for now, I think we may need additional support from `chalk_engine` (as a side effect, types or trait references with outlive requirements cannot be proved well-formed)
* deactivate eager normalization in the presence of `-Z chalk` in order to leverage the lazy normalization strategy of the new-style trait solver
* add the remaining built-in impls (only `Sized` is supported currently)
* transition the compiler to using generic goals instead of predicates that still refer to named type parameters etc

I added a few very simple tests to check that the new solver has the right behavior, they won't be needed anymore once it is mature enough. Additionally it shows off that we get [implied bounds](https://github.com/rust-lang/rust/issues/44491) for free.

r? @nikomatsakis

13 files changed, 280 insertions, 2 deletions

diff --git a/src/test/compile-fail/chalkify/chalk_initial_program.rs b/src/test/compile-fail/chalkify/chalk_initial_program.rs
new file mode 100644
index 00000000000..df25bad622b
--- /dev/null
+++ b/src/test/compile-fail/chalkify/chalk_initial_program.rs
@@ -0,0 +1,16 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+
+impl Foo for i32 { }
+
+impl Foo for u32 { }
+
+fn gimme<F: Foo>() { }
+
+// Note: this also tests that `std::process::Termination` is implemented for `()`.
+fn main() {
+    gimme::<i32>();
+    gimme::<u32>();
+    gimme::<f32>(); //~ERROR the trait bound `f32: Foo` is not satisfied
+}
diff --git a/src/test/compile-fail/chalkify/generic_impls.rs b/src/test/compile-fail/chalkify/generic_impls.rs
new file mode 100644
index 00000000000..d70c6f8055d
--- /dev/null
+++ b/src/test/compile-fail/chalkify/generic_impls.rs
@@ -0,0 +1,18 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+
+impl<T> Foo for (T, u32) { }
+
+fn gimme<F: Foo>() { }
+
+fn foo<T>() {
+    gimme::<(T, u32)>();
+    gimme::<(Option<T>, u32)>();
+    gimme::<(Option<T>, f32)>(); //~ ERROR
+}
+
+fn main() {
+    gimme::<(i32, u32)>();
+    gimme::<(i32, f32)>(); //~ ERROR
+}
diff --git a/src/test/compile-fail/chalkify/impl_wf.rs b/src/test/compile-fail/chalkify/impl_wf.rs
new file mode 100644
index 00000000000..96b1b253371
--- /dev/null
+++ b/src/test/compile-fail/chalkify/impl_wf.rs
@@ -0,0 +1,38 @@
+// compile-flags: -Z chalk
+
+trait Foo: Sized { }
+
+trait Bar {
+    type Item: Foo;
+}
+
+impl Foo for i32 { }
+
+impl Foo for str { }
+//~^ ERROR the size for values of type `str` cannot be known at compilation time
+
+// Implicit `T: Sized` bound.
+impl<T> Foo for Option<T> { }
+
+impl Bar for () {
+    type Item = i32;
+}
+
+impl<T> Bar for Option<T> {
+    type Item = Option<T>;
+}
+
+impl Bar for f32 {
+//~^ ERROR the trait bound `f32: Foo` is not satisfied
+    type Item = f32;
+}
+
+trait Baz<U: ?Sized> where U: Foo { }
+
+impl Baz<i32> for i32 { }
+
+impl Baz<f32> for f32 { }
+//~^ ERROR the trait bound `f32: Foo` is not satisfied
+
+fn main() {
+}
diff --git a/src/test/compile-fail/chalkify/type_wf.rs b/src/test/compile-fail/chalkify/type_wf.rs
new file mode 100644
index 00000000000..d1aa975ddc2
--- /dev/null
+++ b/src/test/compile-fail/chalkify/type_wf.rs
@@ -0,0 +1,24 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+
+struct S<T: Foo> {
+    x: T,
+}
+
+impl Foo for i32 { }
+impl<T> Foo for Option<T> { }
+
+fn main() {
+    let s = S {
+       x: 5,
+    };
+
+    let s = S { //~ ERROR the trait bound `{float}: Foo` is not satisfied
+        x: 5.0,
+    };
+
+    let s = S {
+        x: Some(5.0),
+    };
+}
diff --git a/src/test/run-pass/chalkify/inherent_impl.rs b/src/test/run-pass/chalkify/inherent_impl.rs
new file mode 100644
index 00000000000..fbe30f11544
--- /dev/null
+++ b/src/test/run-pass/chalkify/inherent_impl.rs
@@ -0,0 +1,41 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+
+impl Foo for i32 { }
+
+struct S<T: Foo> {
+    x: T,
+}
+
+fn only_foo<T: Foo>(_x: &T) { }
+
+impl<T> S<T> {
+    // Test that we have the correct environment inside an inherent method.
+    fn dummy_foo(&self) {
+        only_foo(&self.x)
+    }
+}
+
+trait Bar { }
+impl Bar for u32 { }
+
+fn only_bar<T: Bar>() { }
+
+impl<T> S<T> {
+    // Test that the environment of `dummy_bar` adds up with the environment
+    // of the inherent impl.
+    fn dummy_bar<U: Bar>(&self) {
+        only_foo(&self.x);
+        only_bar::<U>();
+    }
+}
+
+fn main() {
+    let s = S {
+        x: 5,
+    };
+
+    s.dummy_foo();
+    s.dummy_bar::<u32>();
+}
diff --git a/src/test/run-pass/chalkify/projection.rs b/src/test/run-pass/chalkify/projection.rs
new file mode 100644
index 00000000000..a598f68d3f9
--- /dev/null
+++ b/src/test/run-pass/chalkify/projection.rs
@@ -0,0 +1,24 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+
+trait Bar {
+    type Item: Foo;
+}
+
+impl Foo for i32 { }
+impl Bar for i32 {
+    type Item = i32;
+}
+
+fn only_foo<T: Foo>() { }
+
+fn only_bar<T: Bar>() {
+    // `T` implements `Bar` hence `<T as Bar>::Item` must also implement `Bar`
+    only_foo::<T::Item>()
+}
+
+fn main() {
+    only_bar::<i32>();
+    only_foo::<<i32 as Bar>::Item>();
+}
diff --git a/src/test/run-pass/chalkify/super_trait.rs b/src/test/run-pass/chalkify/super_trait.rs
new file mode 100644
index 00000000000..441d61ef248
--- /dev/null
+++ b/src/test/run-pass/chalkify/super_trait.rs
@@ -0,0 +1,18 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+trait Bar: Foo { }
+
+impl Foo for i32 { }
+impl Bar for i32 { }
+
+fn only_foo<T: Foo>() { }
+
+fn only_bar<T: Bar>() {
+    // `T` implements `Bar` hence `T` must also implement `Foo`
+    only_foo::<T>()
+}
+
+fn main() {
+    only_bar::<i32>()
+}
diff --git a/src/test/run-pass/chalkify/trait_implied_bound.rs b/src/test/run-pass/chalkify/trait_implied_bound.rs
new file mode 100644
index 00000000000..f82453792ff
--- /dev/null
+++ b/src/test/run-pass/chalkify/trait_implied_bound.rs
@@ -0,0 +1,17 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+trait Bar<U> where U: Foo { }
+
+impl Foo for i32 { }
+impl Bar<i32> for i32 { }
+
+fn only_foo<T: Foo>() { }
+
+fn only_bar<U, T: Bar<U>>() {
+    only_foo::<U>()
+}
+
+fn main() {
+    only_bar::<i32, i32>()
+}
diff --git a/src/test/run-pass/chalkify/type_implied_bound.rs b/src/test/run-pass/chalkify/type_implied_bound.rs
new file mode 100644
index 00000000000..94d976d3242
--- /dev/null
+++ b/src/test/run-pass/chalkify/type_implied_bound.rs
@@ -0,0 +1,28 @@
+// compile-flags: -Z chalk
+
+trait Eq { }
+trait Hash: Eq { }
+
+impl Eq for i32 { }
+impl Hash for i32 { }
+
+struct Set<T: Hash> {
+    _x: T,
+}
+
+fn only_eq<T: Eq>() { }
+
+fn take_a_set<T>(_: &Set<T>) {
+    // `Set<T>` is an input type of `take_a_set`, hence we know that
+    // `T` must implement `Hash`, and we know in turn that `T` must
+    // implement `Eq`.
+    only_eq::<T>()
+}
+
+fn main() {
+    let set = Set {
+        _x: 5,
+    };
+
+    take_a_set(&set);
+}
diff --git a/src/test/ui/chalkify/type_inference.rs b/src/test/ui/chalkify/type_inference.rs
new file mode 100644
index 00000000000..62a53ec0317
--- /dev/null
+++ b/src/test/ui/chalkify/type_inference.rs
@@ -0,0 +1,26 @@
+// compile-flags: -Z chalk
+
+trait Foo { }
+impl Foo for i32 { }
+
+trait Bar { }
+impl Bar for i32 { }
+impl Bar for u32 { }
+
+fn only_foo<T: Foo>(_x: T) { }
+
+fn only_bar<T: Bar>(_x: T) { }
+
+fn main() {
+    let x = 5.0;
+
+    // The only type which implements `Foo` is `i32`, so the chalk trait solver
+    // is expecting a variable of type `i32`. This behavior differs from the
+    // old-style trait solver. I guess this will change, that's why I'm
+    // adding that test.
+    only_foo(x); //~ ERROR mismatched types
+
+    // Here we have two solutions so we get back the behavior of the old-style
+    // trait solver.
+    only_bar(x); //~ ERROR the trait bound `{float}: Bar` is not satisfied
+}
diff --git a/src/test/ui/chalkify/type_inference.stderr b/src/test/ui/chalkify/type_inference.stderr
new file mode 100644
index 00000000000..49ed97d7168
--- /dev/null
+++ b/src/test/ui/chalkify/type_inference.stderr
@@ -0,0 +1,28 @@
+error[E0308]: mismatched types
+  --> $DIR/type_inference.rs:21:14
+   |
+LL |     only_foo(x); //~ ERROR mismatched types
+   |              ^ expected i32, found floating-point variable
+   |
+   = note: expected type `i32`
+              found type `{float}`
+
+error[E0277]: the trait bound `{float}: Bar` is not satisfied
+  --> $DIR/type_inference.rs:25:5
+   |
+LL |     only_bar(x); //~ ERROR the trait bound `{float}: Bar` is not satisfied
+   |     ^^^^^^^^ the trait `Bar` is not implemented for `{float}`
+   |
+   = help: the following implementations were found:
+             <i32 as Bar>
+             <u32 as Bar>
+note: required by `only_bar`
+  --> $DIR/type_inference.rs:12:1
+   |
+LL | fn only_bar<T: Bar>(_x: T) { }
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 2 previous errors
+
+Some errors occurred: E0277, E0308.
+For more information about an error, try `rustc --explain E0277`.
diff --git a/src/test/ui/consts/const-size_of-cycle.stderr b/src/test/ui/consts/const-size_of-cycle.stderr
index b837889400c..8f9498e834d 100644
--- a/src/test/ui/consts/const-size_of-cycle.stderr
+++ b/src/test/ui/consts/const-size_of-cycle.stderr
@@ -10,7 +10,7 @@ note: ...which requires const-evaluating `Foo::bytes::{{constant}}`...
 LL |     intrinsics::size_of::<T>()
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
 note: ...which requires computing layout of `Foo`...
-note: ...which requires normalizing `ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: All }, value: [u8; _] }`...
+note: ...which requires normalizing `ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: All, def_id: None }, value: [u8; _] }`...
 note: ...which requires const-evaluating + checking `Foo::bytes::{{constant}}`...
   --> $DIR/const-size_of-cycle.rs:6:17
    |
diff --git a/src/test/ui/issues/issue-44415.stderr b/src/test/ui/issues/issue-44415.stderr
index 21a935f57a9..441f1b2a069 100644
--- a/src/test/ui/issues/issue-44415.stderr
+++ b/src/test/ui/issues/issue-44415.stderr
@@ -10,7 +10,7 @@ note: ...which requires const-evaluating `Foo::bytes::{{constant}}`...
 LL |     bytes: [u8; unsafe { intrinsics::size_of::<Foo>() }],
    |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 note: ...which requires computing layout of `Foo`...
-note: ...which requires normalizing `ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: All }, value: [u8; _] }`...
+note: ...which requires normalizing `ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: All, def_id: None }, value: [u8; _] }`...
 note: ...which requires const-evaluating + checking `Foo::bytes::{{constant}}`...
   --> $DIR/issue-44415.rs:6:17
    |