Rollup merge of #108333 - compiler-errors:new-solver-object-sound, r=lcnr

Make object bound candidates sound in the new trait solver

r? `@lcnr`

9 files changed, 309 insertions, 3 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs
index 6172a9539f6..dec9f8016b0 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly.rs
@@ -99,6 +99,15 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
         requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
     ) -> QueryResult<'tcx>;
 
+    // Consider a clause specifically for a `dyn Trait` self type. This requires
+    // additionally checking all of the supertraits and object bounds to hold,
+    // since they're not implied by the well-formedness of the object type.
+    fn consider_object_bound_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx>;
+
     fn consider_impl_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
@@ -455,7 +464,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         for assumption in
             elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
         {
-            match G::consider_implied_clause(self, goal, assumption.predicate, []) {
+            match G::consider_object_bound_candidate(self, goal, assumption.predicate) {
                 Ok(result) => {
                     candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
                 }
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index d4fdd545737..88fd8bb8bd0 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -128,6 +128,51 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         }
     }
 
+    fn consider_object_bound_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx> {
+        if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred()
+            && poly_projection_pred.projection_def_id() == goal.predicate.def_id()
+        {
+            ecx.probe(|ecx| {
+                let assumption_projection_pred =
+                    ecx.instantiate_binder_with_infer(poly_projection_pred);
+                let mut nested_goals = ecx.eq(
+                    goal.param_env,
+                    goal.predicate.projection_ty,
+                    assumption_projection_pred.projection_ty,
+                )?;
+
+                let tcx = ecx.tcx();
+                let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
+                    bug!("expected object type in `consider_object_bound_candidate`");
+                };
+                nested_goals.extend(
+                    structural_traits::predicates_for_object_candidate(
+                        ecx,
+                        goal.param_env,
+                        goal.predicate.projection_ty.trait_ref(tcx),
+                        bounds,
+                    )
+                    .into_iter()
+                    .map(|pred| goal.with(tcx, pred)),
+                );
+
+                let subst_certainty = ecx.evaluate_all(nested_goals)?;
+
+                ecx.eq_term_and_make_canonical_response(
+                    goal,
+                    subst_certainty,
+                    assumption_projection_pred.term,
+                )
+            })
+        } else {
+            Err(NoSolution)
+        }
+    }
+
     fn consider_impl_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 68bb7c877e3..5c499c36e9b 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -86,6 +86,46 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         }
     }
 
+    fn consider_object_bound_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx> {
+        if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred()
+            && poly_trait_pred.def_id() == goal.predicate.def_id()
+        {
+            // FIXME: Constness and polarity
+            ecx.probe(|ecx| {
+                let assumption_trait_pred =
+                    ecx.instantiate_binder_with_infer(poly_trait_pred);
+                let mut nested_goals = ecx.eq(
+                    goal.param_env,
+                    goal.predicate.trait_ref,
+                    assumption_trait_pred.trait_ref,
+                )?;
+
+                let tcx = ecx.tcx();
+                let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
+                    bug!("expected object type in `consider_object_bound_candidate`");
+                };
+                nested_goals.extend(
+                    structural_traits::predicates_for_object_candidate(
+                        ecx,
+                        goal.param_env,
+                        goal.predicate.trait_ref,
+                        bounds,
+                    )
+                    .into_iter()
+                    .map(|pred| goal.with(tcx, pred)),
+                );
+
+                ecx.evaluate_all_and_make_canonical_response(nested_goals)
+            })
+        } else {
+            Err(NoSolution)
+        }
+    }
+
     fn consider_auto_trait_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
index 3a887f54587..f7d1b4be74b 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
@@ -1,6 +1,7 @@
-use rustc_hir::{Movability, Mutability};
+use rustc_data_structures::fx::FxHashMap;
+use rustc_hir::{def_id::DefId, Movability, Mutability};
 use rustc_infer::traits::query::NoSolution;
-use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable};
 
 use crate::solve::EvalCtxt;
 
@@ -231,3 +232,112 @@ pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>(
         }
     }
 }
+
+/// Assemble a list of predicates that would be present on a theoretical
+/// user impl for an object type. These predicates must be checked any time
+/// we assemble a built-in object candidate for an object type, since they
+/// are not implied by the well-formedness of the type.
+///
+/// For example, given the following traits:
+///
+/// ```rust,ignore (theoretical code)
+/// trait Foo: Baz {
+///     type Bar: Copy;
+/// }
+///
+/// trait Baz {}
+/// ```
+///
+/// For the dyn type `dyn Foo<Item = Ty>`, we can imagine there being a
+/// pair of theoretical impls:
+///
+/// ```rust,ignore (theoretical code)
+/// impl Foo for dyn Foo<Item = Ty>
+/// where
+///     Self: Baz,
+///     <Self as Foo>::Bar: Copy,
+/// {
+///     type Bar = Ty;
+/// }
+///
+/// impl Baz for dyn Foo<Item = Ty> {}
+/// ```
+///
+/// However, in order to make such impls well-formed, we need to do an
+/// additional step of eagerly folding the associated types in the where
+/// clauses of the impl. In this example, that means replacing
+/// `<Self as Foo>::Bar` with `Ty` in the first impl.
+pub(crate) fn predicates_for_object_candidate<'tcx>(
+    ecx: &EvalCtxt<'_, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    trait_ref: ty::TraitRef<'tcx>,
+    object_bound: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
+) -> Vec<ty::Predicate<'tcx>> {
+    let tcx = ecx.tcx();
+    let mut requirements = vec![];
+    requirements.extend(
+        tcx.super_predicates_of(trait_ref.def_id).instantiate(tcx, trait_ref.substs).predicates,
+    );
+    for item in tcx.associated_items(trait_ref.def_id).in_definition_order() {
+        // FIXME(associated_const_equality): Also add associated consts to
+        // the requirements here.
+        if item.kind == ty::AssocKind::Type {
+            requirements.extend(tcx.item_bounds(item.def_id).subst(tcx, trait_ref.substs));
+        }
+    }
+
+    let mut replace_projection_with = FxHashMap::default();
+    for bound in object_bound {
+        if let ty::ExistentialPredicate::Projection(proj) = bound.skip_binder() {
+            let proj = proj.with_self_ty(tcx, trait_ref.self_ty());
+            let old_ty = replace_projection_with.insert(proj.def_id(), bound.rebind(proj));
+            assert_eq!(
+                old_ty,
+                None,
+                "{} has two substitutions: {} and {}",
+                proj.projection_ty,
+                proj.term,
+                old_ty.unwrap()
+            );
+        }
+    }
+
+    requirements.fold_with(&mut ReplaceProjectionWith {
+        ecx,
+        param_env,
+        mapping: replace_projection_with,
+    })
+}
+
+struct ReplaceProjectionWith<'a, 'tcx> {
+    ecx: &'a EvalCtxt<'a, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    mapping: FxHashMap<DefId, ty::PolyProjectionPredicate<'tcx>>,
+}
+
+impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> {
+    fn interner(&self) -> TyCtxt<'tcx> {
+        self.ecx.tcx()
+    }
+
+    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
+        if let ty::Alias(ty::Projection, alias_ty) = *ty.kind()
+            && let Some(replacement) = self.mapping.get(&alias_ty.def_id)
+        {
+            // We may have a case where our object type's projection bound is higher-ranked,
+            // but the where clauses we instantiated are not. We can solve this by instantiating
+            // the binder at the usage site.
+            let proj = self.ecx.instantiate_binder_with_infer(*replacement);
+            // FIXME: Technically this folder could be fallible?
+            let nested = self
+                .ecx
+                .eq(self.param_env, alias_ty, proj.projection_ty)
+                .expect("expected to be able to unify goal projection with dyn's projection");
+            // FIXME: Technically we could register these too..
+            assert!(nested.is_empty(), "did not expect unification to have any nested goals");
+            proj.term.ty().unwrap()
+        } else {
+            ty.super_fold_with(self)
+        }
+    }
+}
diff --git a/tests/ui/traits/new-solver/higher-ranked-dyn-bounds.rs b/tests/ui/traits/new-solver/higher-ranked-dyn-bounds.rs
new file mode 100644
index 00000000000..c886aeeda3e
--- /dev/null
+++ b/tests/ui/traits/new-solver/higher-ranked-dyn-bounds.rs
@@ -0,0 +1,17 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+trait Trait<'a> {
+    type Item: for<'b> Trait2<'b>;
+}
+
+trait Trait2<'a> {}
+impl Trait2<'_> for () {}
+
+fn needs_trait(_: Box<impl for<'a> Trait<'a> + ?Sized>) {}
+
+fn foo(x: Box<dyn for<'a> Trait<'a, Item = ()>>) {
+    needs_trait(x);
+}
+
+fn main() {}
diff --git a/tests/ui/traits/new-solver/more-object-bound.rs b/tests/ui/traits/new-solver/more-object-bound.rs
new file mode 100644
index 00000000000..712759ef0e6
--- /dev/null
+++ b/tests/ui/traits/new-solver/more-object-bound.rs
@@ -0,0 +1,27 @@
+// compile-flags: -Ztrait-solver=next
+// From #80800
+
+trait SuperTrait {
+    type A;
+    type B;
+}
+
+trait Trait: SuperTrait<A = <Self as SuperTrait>::B> {}
+
+fn transmute<A, B>(x: A) -> B {
+    foo::<A, B, dyn Trait<A = A, B = B>>(x)
+    //~^ ERROR type annotations needed: cannot satisfy `dyn Trait<A = A, B = B>: Trait`
+}
+
+fn foo<A, B, T: ?Sized>(x: T::A) -> B
+where
+    T: Trait<B = B>,
+{
+    x
+}
+
+static X: u8 = 0;
+fn main() {
+    let x = transmute::<&u8, &[u8; 1_000_000]>(&X);
+    println!("{:?}", x[100_000]);
+}
diff --git a/tests/ui/traits/new-solver/more-object-bound.stderr b/tests/ui/traits/new-solver/more-object-bound.stderr
new file mode 100644
index 00000000000..208fdecb08f
--- /dev/null
+++ b/tests/ui/traits/new-solver/more-object-bound.stderr
@@ -0,0 +1,19 @@
+error[E0283]: type annotations needed: cannot satisfy `dyn Trait<A = A, B = B>: Trait`
+  --> $DIR/more-object-bound.rs:12:5
+   |
+LL |     foo::<A, B, dyn Trait<A = A, B = B>>(x)
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: cannot satisfy `dyn Trait<A = A, B = B>: Trait`
+note: required by a bound in `foo`
+  --> $DIR/more-object-bound.rs:18:8
+   |
+LL | fn foo<A, B, T: ?Sized>(x: T::A) -> B
+   |    --- required by a bound in this function
+LL | where
+LL |     T: Trait<B = B>,
+   |        ^^^^^^^^^^^^ required by this bound in `foo`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0283`.
diff --git a/tests/ui/traits/new-solver/object-unsafety.rs b/tests/ui/traits/new-solver/object-unsafety.rs
new file mode 100644
index 00000000000..7bdd863a762
--- /dev/null
+++ b/tests/ui/traits/new-solver/object-unsafety.rs
@@ -0,0 +1,20 @@
+// compile-flags: -Ztrait-solver=next
+
+trait Setup {
+    type From: Copy;
+}
+
+fn copy<U: Setup + ?Sized>(from: &U::From) -> U::From {
+    *from
+}
+
+pub fn copy_any<T>(t: &T) -> T {
+    copy::<dyn Setup<From=T>>(t)
+    //~^ ERROR the trait bound `dyn Setup<From = T>: Setup` is not satisfied
+}
+
+fn main() {
+    let x = String::from("Hello, world");
+    let y = copy_any(&x);
+    println!("{y}");
+}
diff --git a/tests/ui/traits/new-solver/object-unsafety.stderr b/tests/ui/traits/new-solver/object-unsafety.stderr
new file mode 100644
index 00000000000..198ac623df8
--- /dev/null
+++ b/tests/ui/traits/new-solver/object-unsafety.stderr
@@ -0,0 +1,19 @@
+error[E0277]: the trait bound `dyn Setup<From = T>: Setup` is not satisfied
+  --> $DIR/object-unsafety.rs:12:12
+   |
+LL |     copy::<dyn Setup<From=T>>(t)
+   |            ^^^^^^^^^^^^^^^^^ the trait `Setup` is not implemented for `dyn Setup<From = T>`
+   |
+note: required by a bound in `copy`
+  --> $DIR/object-unsafety.rs:7:12
+   |
+LL | fn copy<U: Setup + ?Sized>(from: &U::From) -> U::From {
+   |            ^^^^^ required by this bound in `copy`
+help: consider introducing a `where` clause, but there might be an alternative better way to express this requirement
+   |
+LL | pub fn copy_any<T>(t: &T) -> T where dyn Setup<From = T>: Setup {
+   |                                ++++++++++++++++++++++++++++++++
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.