Rework upcasting

2 files changed, 168 insertions, 96 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 14a5b9656e5..41565fe5dd9 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -444,7 +444,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             Err(NoSolution) => vec![],
         };
 
-        ecx.probe(|_| CandidateKind::DynUpcastingAssembly).enter(|ecx| {
+        ecx.probe(|_| CandidateKind::UnsizeAssembly).enter(|ecx| {
             let a_ty = goal.predicate.self_ty();
             // We need to normalize the b_ty since it's matched structurally
             // in the other functions below.
@@ -526,7 +526,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         b_region: ty::Region<'tcx>,
     ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> {
         let tcx = self.tcx();
-        let Goal { predicate: (a_ty, b_ty), .. } = goal;
+        let Goal { predicate: (a_ty, _b_ty), .. } = goal;
 
         // All of a's auto traits need to be in b's auto traits.
         let auto_traits_compatible =
@@ -535,51 +535,30 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             return vec![];
         }
 
-        // Try to match `a_ty` against `b_ty`, replacing `a_ty`'s principal trait ref with
-        // the supertrait principal and subtyping the types.
-        let unsize_dyn_to_principal =
-            |ecx: &mut Self, principal: Option<ty::PolyExistentialTraitRef<'tcx>>| {
-                ecx.probe_candidate("upcast dyn to principle").enter(
-                    |ecx| -> Result<_, NoSolution> {
-                        // Require that all of the trait predicates from A match B, except for
-                        // the auto traits. We do this by constructing a new A type with B's
-                        // auto traits, and equating these types.
-                        let new_a_data = principal
-                            .into_iter()
-                            .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait))
-                            .chain(a_data.iter().filter(|a| {
-                                matches!(a.skip_binder(), ty::ExistentialPredicate::Projection(_))
-                            }))
-                            .chain(
-                                b_data
-                                    .auto_traits()
-                                    .map(ty::ExistentialPredicate::AutoTrait)
-                                    .map(ty::Binder::dummy),
-                            );
-                        let new_a_data = tcx.mk_poly_existential_predicates_from_iter(new_a_data);
-                        let new_a_ty = Ty::new_dynamic(tcx, new_a_data, b_region, ty::Dyn);
-
-                        // We also require that A's lifetime outlives B's lifetime.
-                        ecx.eq(goal.param_env, new_a_ty, b_ty)?;
-                        ecx.add_goal(goal.with(tcx, ty::OutlivesPredicate(a_region, b_region)));
-                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-                    },
-                )
-            };
-
         let mut responses = vec![];
         // If the principal def ids match (or are both none), then we're not doing
         // trait upcasting. We're just removing auto traits (or shortening the lifetime).
         if a_data.principal_def_id() == b_data.principal_def_id() {
-            if let Ok(resp) = unsize_dyn_to_principal(self, a_data.principal()) {
+            if let Ok(resp) = self.consider_builtin_upcast_to_principal(
+                goal,
+                a_data,
+                a_region,
+                b_data,
+                b_region,
+                a_data.principal(),
+            ) {
                 responses.push((resp, BuiltinImplSource::Misc));
             }
         } else if let Some(a_principal) = a_data.principal() {
             self.walk_vtable(
                 a_principal.with_self_ty(tcx, a_ty),
                 |ecx, new_a_principal, _, vtable_vptr_slot| {
-                    if let Ok(resp) = unsize_dyn_to_principal(
-                        ecx,
+                    if let Ok(resp) = ecx.consider_builtin_upcast_to_principal(
+                        goal,
+                        a_data,
+                        a_region,
+                        b_data,
+                        b_region,
                         Some(new_a_principal.map_bound(|trait_ref| {
                             ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)
                         })),
@@ -631,6 +610,78 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
+    fn consider_builtin_upcast_to_principal(
+        &mut self,
+        goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>,
+        a_data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
+        a_region: ty::Region<'tcx>,
+        b_data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
+        b_region: ty::Region<'tcx>,
+        upcast_principal: Option<ty::PolyExistentialTraitRef<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        let param_env = goal.param_env;
+
+        // More than one projection in a_ty's bounds may match the projection
+        // in b_ty's bound. Use this to first determine *which* apply without
+        // having any inference side-effects. We process obligations because
+        // unification may initially succeed due to deferred projection equality.
+        let projection_may_match = |ecx: &mut Self, source_projection, target_projection| {
+            ecx.probe(|_| CandidateKind::UpcastProbe)
+                .enter(|ecx| -> Result<(), NoSolution> {
+                    ecx.eq(param_env, source_projection, target_projection)?;
+                    let _ = ecx.try_evaluate_added_goals()?;
+                    Ok(())
+                })
+                .is_ok()
+        };
+
+        for bound in b_data {
+            match bound.skip_binder() {
+                // Check that a's supertrait (upcast_principal) is compatible
+                // with the target (b_ty).
+                ty::ExistentialPredicate::Trait(target_principal) => {
+                    self.eq(param_env, upcast_principal.unwrap(), bound.rebind(target_principal))?;
+                }
+                // Check that b_ty's projection is satisfied by exactly one of
+                // a_ty's projections. First, we look through the list to see if
+                // any match. If not, error. Then, if *more* than one matches, we
+                // return ambiguity. Otherwise, if exactly one matches, equate
+                // it with b_ty's projection.
+                ty::ExistentialPredicate::Projection(target_projection) => {
+                    let target_projection = bound.rebind(target_projection);
+                    let mut matching_projections =
+                        a_data.projection_bounds().filter(|source_projection| {
+                            projection_may_match(self, *source_projection, target_projection)
+                        });
+                    let Some(source_projection) = matching_projections.next() else {
+                        return Err(NoSolution);
+                    };
+                    if matching_projections.next().is_some() {
+                        return self.evaluate_added_goals_and_make_canonical_response(
+                            Certainty::AMBIGUOUS,
+                        );
+                    }
+                    self.eq(param_env, source_projection, target_projection)?;
+                }
+                // Check that b_ty's auto traits are present in a_ty's bounds.
+                ty::ExistentialPredicate::AutoTrait(def_id) => {
+                    if !a_data.auto_traits().any(|source_def_id| source_def_id == def_id) {
+                        return Err(NoSolution);
+                    }
+                }
+            }
+        }
+
+        // Also require that a_ty's lifetime outlives b_ty's lifetime.
+        self.add_goal(Goal::new(
+            self.tcx(),
+            param_env,
+            ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)),
+        ));
+
+        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+    }
+
     /// We have the following builtin impls for arrays:
     /// ```ignore (builtin impl example)
     /// impl<T: ?Sized, const N: usize> Unsize<[T]> for [T; N] {}
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index bf09681c66d..77304984402 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -879,68 +879,89 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         // `assemble_candidates_for_unsizing` should ensure there are no late-bound
         // regions here. See the comment there for more details.
-        let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
-        let target = obligation.predicate.skip_binder().trait_ref.args.type_at(1);
-        let target = self.infcx.shallow_resolve(target);
+        let predicate = obligation.predicate.no_bound_vars().unwrap();
+        let a_ty = self.infcx.shallow_resolve(predicate.self_ty());
+        let b_ty = self.infcx.shallow_resolve(predicate.trait_ref.args.type_at(1));
+
+        let ty::Dynamic(a_data, a_region, ty::Dyn) = *a_ty.kind() else { bug!() };
+        let ty::Dynamic(b_data, b_region, ty::Dyn) = *b_ty.kind() else { bug!() };
 
-        debug!(?source, ?target, "confirm_trait_upcasting_unsize_candidate");
+        let source_principal = a_data.principal().unwrap().with_self_ty(tcx, a_ty);
+        let upcast_principal = util::supertraits(tcx, source_principal).nth(idx).unwrap();
 
         let mut nested = vec![];
-        let source_trait_ref;
-        let upcast_trait_ref;
-        match (source.kind(), target.kind()) {
-            // TraitA+Kx+'a -> TraitB+Ky+'b (trait upcasting coercion).
-            (
-                &ty::Dynamic(ref data_a, r_a, repr_a @ ty::Dyn),
-                &ty::Dynamic(ref data_b, r_b, ty::Dyn),
-            ) => {
-                // See `assemble_candidates_for_unsizing` for more info.
-                // We already checked the compatibility of auto traits within `assemble_candidates_for_unsizing`.
-                let principal_a = data_a.principal().unwrap();
-                source_trait_ref = principal_a.with_self_ty(tcx, source);
-                upcast_trait_ref = util::supertraits(tcx, source_trait_ref).nth(idx).unwrap();
-                assert_eq!(data_b.principal_def_id(), Some(upcast_trait_ref.def_id()));
-                let existential_predicate = upcast_trait_ref.map_bound(|trait_ref| {
-                    ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef::erase_self_ty(
-                        tcx, trait_ref,
-                    ))
-                });
-                let iter = Some(existential_predicate)
-                    .into_iter()
-                    .chain(
-                        data_a
-                            .projection_bounds()
-                            .map(|b| b.map_bound(ty::ExistentialPredicate::Projection)),
-                    )
-                    .chain(
-                        data_b
-                            .auto_traits()
-                            .map(ty::ExistentialPredicate::AutoTrait)
-                            .map(ty::Binder::dummy),
+        for bound in b_data {
+            match bound.skip_binder() {
+                // Check that a's supertrait (upcast_principal) is compatible
+                // with the target (b_ty).
+                ty::ExistentialPredicate::Trait(target_principal) => {
+                    nested.extend(
+                        self.infcx
+                            .at(&obligation.cause, obligation.param_env)
+                            .sup(
+                                DefineOpaqueTypes::No,
+                                upcast_principal.map_bound(|trait_ref| {
+                                    ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)
+                                }),
+                                bound.rebind(target_principal),
+                            )
+                            .map_err(|_| SelectionError::Unimplemented)?
+                            .into_obligations(),
                     );
-                let existential_predicates = tcx.mk_poly_existential_predicates_from_iter(iter);
-                let source_trait = Ty::new_dynamic(tcx, existential_predicates, r_b, repr_a);
-
-                // Require that the traits involved in this upcast are **equal**;
-                // only the **lifetime bound** is changed.
-                let InferOk { obligations, .. } = self
-                    .infcx
-                    .at(&obligation.cause, obligation.param_env)
-                    .sup(DefineOpaqueTypes::No, target, source_trait)
-                    .map_err(|_| Unimplemented)?;
-                nested.extend(obligations);
-
-                let outlives = ty::OutlivesPredicate(r_a, r_b);
-                nested.push(Obligation::with_depth(
-                    tcx,
-                    obligation.cause.clone(),
-                    obligation.recursion_depth + 1,
-                    obligation.param_env,
-                    obligation.predicate.rebind(outlives),
-                ));
+                }
+                // Check that b_ty's projection is satisfied by exactly one of
+                // a_ty's projections. First, we look through the list to see if
+                // any match. If not, error. Then, if *more* than one matches, we
+                // return ambiguity. Otherwise, if exactly one matches, equate
+                // it with b_ty's projection.
+                ty::ExistentialPredicate::Projection(target_projection) => {
+                    let target_projection = bound.rebind(target_projection);
+                    let mut matching_projections =
+                        a_data.projection_bounds().filter(|source_projection| {
+                            // Eager normalization means that we can just use can_eq
+                            // here instead of equating and processing obligations.
+                            self.infcx.can_eq(
+                                obligation.param_env,
+                                *source_projection,
+                                target_projection,
+                            )
+                        });
+                    let Some(source_projection) = matching_projections.next() else {
+                        return Err(SelectionError::Unimplemented);
+                    };
+                    if matching_projections.next().is_some() {
+                        // This is incomplete but I don't care. We should never
+                        // have more than one projection that ever applies with
+                        // eager norm and actually implementable traits, since
+                        // you can't have two supertraits like:
+                        // `trait A: B<i32, Assoc = First> + B<i32, Assoc = Second>`
+                        return Err(SelectionError::Unimplemented);
+                    }
+                    nested.extend(
+                        self.infcx
+                            .at(&obligation.cause, obligation.param_env)
+                            .sup(DefineOpaqueTypes::No, source_projection, target_projection)
+                            .map_err(|_| SelectionError::Unimplemented)?
+                            .into_obligations(),
+                    );
+                }
+                // Check that b_ty's auto trait is present in a_ty's bounds.
+                ty::ExistentialPredicate::AutoTrait(def_id) => {
+                    if !a_data.auto_traits().any(|source_def_id| source_def_id == def_id) {
+                        return Err(SelectionError::Unimplemented);
+                    }
+                }
             }
-            _ => bug!(),
-        };
+        }
+
+        // Also require that a_ty's lifetime outlives b_ty's lifetime.
+        nested.push(Obligation::with_depth(
+            tcx,
+            obligation.cause.clone(),
+            obligation.recursion_depth + 1,
+            obligation.param_env,
+            ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)),
+        ));
 
         let vtable_segment_callback = {
             let mut vptr_offset = 0;
@@ -951,7 +972,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     }
                     VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
                         vptr_offset += count_own_vtable_entries(tcx, trait_ref);
-                        if trait_ref == upcast_trait_ref {
+                        if trait_ref == upcast_principal {
                             if emit_vptr {
                                 return ControlFlow::Break(Some(vptr_offset));
                             } else {
@@ -969,7 +990,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         };
 
         let vtable_vptr_slot =
-            prepare_vtable_segments(tcx, source_trait_ref, vtable_segment_callback).unwrap();
+            prepare_vtable_segments(tcx, source_principal, vtable_segment_callback).unwrap();
 
         Ok(ImplSource::Builtin(BuiltinImplSource::TraitUpcasting { vtable_vptr_slot }, nested))
     }