Make everything builtin!

5 files changed, 211 insertions, 264 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 942f4088472..ab90db6ff58 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -3,17 +3,16 @@
 use super::search_graph::OverflowHandler;
 use super::{EvalCtxt, SolverMode};
 use crate::traits::coherence;
-use rustc_data_structures::fx::FxIndexSet;
 use rustc_hir::def_id::DefId;
 use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::util::elaborate;
 use rustc_infer::traits::Reveal;
 use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult};
+use rustc_middle::traits::BuiltinImplSource;
 use rustc_middle::ty::fast_reject::{SimplifiedType, TreatParams};
-use rustc_middle::ty::TypeVisitableExt;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_middle::ty::{fast_reject, TypeFoldable};
+use rustc_middle::ty::{ToPredicate, TypeVisitableExt};
 use rustc_span::ErrorGuaranteed;
 use std::fmt::Debug;
 
@@ -89,17 +88,6 @@ pub(super) enum CandidateSource {
     AliasBound,
 }
 
-/// Records additional information about what kind of built-in impl this is.
-/// This should only be used by selection.
-#[derive(Debug, Clone, Copy)]
-pub(super) enum BuiltinImplSource {
-    TraitUpcasting,
-    TupleUnsize,
-    Object,
-    Misc,
-    Ambiguity,
-}
-
 /// Methods used to assemble candidates for either trait or projection goals.
 pub(super) trait GoalKind<'tcx>:
     TypeFoldable<TyCtxt<'tcx>> + Copy + Eq + std::fmt::Display
@@ -282,20 +270,6 @@ pub(super) trait GoalKind<'tcx>:
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx>;
 
-    /// Consider (possibly several) goals to upcast or unsize a type to another
-    /// type.
-    ///
-    /// The most common forms of unsizing are array to slice, and concrete (Sized)
-    /// type into a `dyn Trait`. ADTs and Tuples can also have their final field
-    /// unsized if it's generic.
-    ///
-    /// `dyn Trait1` can be unsized to `dyn Trait2` if they are the same trait, or
-    /// if `Trait2` is a (transitive) supertrait of `Trait2`.
-    fn consider_builtin_unsize_and_upcast_candidates(
-        _ecx: &mut EvalCtxt<'_, 'tcx>,
-        goal: Goal<'tcx, Self>,
-    ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)>;
-
     fn consider_builtin_discriminant_kind_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
@@ -310,6 +284,25 @@ pub(super) trait GoalKind<'tcx>:
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx>;
+
+    /// Consider (possibly several) candidates to upcast or unsize a type to another
+    /// type.
+    ///
+    /// The most common forms of unsizing are array to slice, and concrete (Sized)
+    /// type into a `dyn Trait`. ADTs and Tuples can also have their final field
+    /// unsized if it's generic.
+    ///
+    /// `dyn Trait1` can be unsized to `dyn Trait2` if they are the same trait, or
+    /// if `Trait2` is a (transitive) supertrait of `Trait2`.
+    ///
+    /// We return the `BuiltinImplSource` for each candidate as it is needed
+    /// for unsize coercion in hir typeck and because it is difficult to
+    /// otherwise recompute this for codegen. This is a bit of a mess but the
+    /// easiest way to maintain the existing behavior for now.
+    fn consider_builtin_unsize_and_upcast_candidates(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)>;
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
@@ -343,7 +336,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> Option<Vec<Candidate<'tcx>>> {
         goal.predicate.self_ty().is_ty_var().then(|| {
             vec![Candidate {
-                source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity),
+                source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
                 result: self
                     .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                     .unwrap(),
@@ -412,7 +405,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                             Certainty::Maybe(MaybeCause::Overflow),
                         )?;
                         Ok(vec![Candidate {
-                            source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity),
+                            source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
                             result,
                         }])
                     },
@@ -848,29 +841,47 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             ty::Dynamic(bounds, ..) => bounds,
         };
 
-        let own_bounds: FxIndexSet<_> =
-            bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)).collect();
-        for assumption in elaborate(tcx, own_bounds.iter().copied())
-            // we only care about bounds that match the `Self` type
-            .filter_only_self()
-        {
-            // FIXME: Predicates are fully elaborated in the object type's existential bounds
-            // list. We want to only consider these pre-elaborated projections, and not other
-            // projection predicates that we reach by elaborating the principal trait ref,
-            // since that'll cause ambiguity.
-            //
-            // We can remove this when we have implemented lifetime intersections in responses.
-            if assumption.as_projection_clause().is_some() && !own_bounds.contains(&assumption) {
-                continue;
+        // Consider all of the auto-trait and projection bounds, which don't
+        // need to be recorded as a `BuiltinImplSource::Object` since they don't
+        // really have a vtable base...
+        for bound in bounds {
+            match bound.skip_binder() {
+                ty::ExistentialPredicate::Trait(_) => {
+                    // Skip principal
+                }
+                ty::ExistentialPredicate::Projection(_)
+                | ty::ExistentialPredicate::AutoTrait(_) => {
+                    match G::consider_object_bound_candidate(
+                        self,
+                        goal,
+                        bound.with_self_ty(tcx, self_ty),
+                    ) {
+                        Ok(result) => candidates.push(Candidate {
+                            source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
+                            result,
+                        }),
+                        Err(NoSolution) => (),
+                    }
+                }
             }
+        }
 
-            match G::consider_object_bound_candidate(self, goal, assumption) {
-                Ok(result) => candidates.push(Candidate {
-                    source: CandidateSource::BuiltinImpl(BuiltinImplSource::Object),
-                    result,
-                }),
-                Err(NoSolution) => (),
-            }
+        // FIXME: We only need to do *any* of this if we're considering a trait goal,
+        // since we don't need to look at any supertrait or anything if we are doing
+        // a projection goal.
+        if let Some(principal) = bounds.principal() {
+            let principal_trait_ref = principal.with_self_ty(tcx, self_ty);
+            self.walk_vtable(principal_trait_ref, |ecx, assumption, vtable_base, _| {
+                match G::consider_object_bound_candidate(ecx, goal, assumption.to_predicate(tcx)) {
+                    Ok(result) => candidates.push(Candidate {
+                        source: CandidateSource::BuiltinImpl(BuiltinImplSource::Object {
+                            vtable_base,
+                        }),
+                        result,
+                    }),
+                    Err(NoSolution) => (),
+                }
+            });
         }
     }
 
@@ -890,7 +901,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                         .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                     {
                         Ok(result) => candidates.push(Candidate {
-                            source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity),
+                            source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
                             result,
                         }),
                         // FIXME: This will be reachable at some point if we're in
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
index 6e0aa08c307..b04d77f0a1a 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
@@ -25,6 +25,7 @@ use std::io::Write;
 use std::ops::ControlFlow;
 
 use crate::traits::specialization_graph;
+use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment};
 
 use super::inspect::ProofTreeBuilder;
 use super::search_graph::{self, OverflowHandler};
@@ -920,4 +921,39 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             Err(ErrorHandled::TooGeneric) => None,
         }
     }
+
+    /// Walk through the vtable of a principal trait ref, executing a `supertrait_visitor`
+    /// for every trait ref encountered (including the principal). Passes both the vtable
+    /// base and the (optional) vptr slot.
+    pub(super) fn walk_vtable(
+        &mut self,
+        principal: ty::PolyTraitRef<'tcx>,
+        mut supertrait_visitor: impl FnMut(&mut Self, ty::PolyTraitRef<'tcx>, usize, Option<usize>),
+    ) {
+        let tcx = self.tcx();
+        let mut offset = 0;
+        prepare_vtable_segments::<()>(tcx, principal, |segment| {
+            match segment {
+                VtblSegment::MetadataDSA => {
+                    offset += TyCtxt::COMMON_VTABLE_ENTRIES.len();
+                }
+                VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
+                    let own_vtable_entries = count_own_vtable_entries(tcx, trait_ref);
+
+                    supertrait_visitor(
+                        self,
+                        trait_ref,
+                        offset,
+                        emit_vptr.then(|| offset + own_vtable_entries),
+                    );
+
+                    offset += own_vtable_entries;
+                    if emit_vptr {
+                        offset += 1;
+                    }
+                }
+            }
+            ControlFlow::Continue(())
+        });
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs
index cdfbaedb8c2..6045001510e 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs
@@ -1,25 +1,20 @@
-use std::ops::ControlFlow;
-
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
-use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk};
-use rustc_infer::traits::util::supertraits;
+use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt};
 use rustc_infer::traits::{
     Obligation, PolyTraitObligation, PredicateObligation, Selection, SelectionResult, TraitEngine,
 };
 use rustc_middle::traits::solve::{CanonicalInput, Certainty, Goal};
 use rustc_middle::traits::{
-    ImplSource, ImplSourceObjectData, ImplSourceTraitUpcastingData, ImplSourceUserDefinedData,
-    ObligationCause, SelectionError,
+    BuiltinImplSource, ImplSource, ImplSourceUserDefinedData, ObligationCause, SelectionError,
 };
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_span::DUMMY_SP;
 
-use crate::solve::assembly::{BuiltinImplSource, Candidate, CandidateSource};
+use crate::solve::assembly::{Candidate, CandidateSource};
 use crate::solve::eval_ctxt::{EvalCtxt, GenerateProofTree};
 use crate::solve::inspect::ProofTreeBuilder;
 use crate::solve::search_graph::OverflowHandler;
-use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment};
 use crate::traits::StructurallyNormalizeExt;
 use crate::traits::TraitEngineExt;
 
@@ -105,47 +100,26 @@ impl<'tcx> InferCtxtSelectExt<'tcx> for InferCtxt<'tcx> {
                 rematch_impl(self, goal, def_id, nested_obligations)
             }
 
-            // Rematching the dyn upcast or object goal will instantiate the same nested
-            // goals that would have caused the ambiguity, so we can still make progress here
-            // regardless.
-            // FIXME: This doesn't actually check the object bounds hold here.
-            (
-                _,
-                CandidateSource::BuiltinImpl(
-                    BuiltinImplSource::Object | BuiltinImplSource::TraitUpcasting,
-                ),
-            ) => rematch_object(self, goal, nested_obligations),
-
-            (
-                Certainty::Maybe(_),
-                CandidateSource::BuiltinImpl(
-                    BuiltinImplSource::Misc | BuiltinImplSource::TupleUnsize,
-                ),
-            ) if self.tcx.lang_items().unsize_trait() == Some(goal.predicate.def_id()) => {
-                rematch_unsize(self, goal, nested_obligations)
-            }
-
-            (Certainty::Yes, CandidateSource::BuiltinImpl(BuiltinImplSource::TupleUnsize))
+            (Certainty::Maybe(_), CandidateSource::BuiltinImpl(src))
                 if self.tcx.lang_items().unsize_trait() == Some(goal.predicate.def_id()) =>
             {
-                Ok(Some(ImplSource::TupleUnsizing(nested_obligations)))
+                rematch_unsize(self, goal, nested_obligations, src)
             }
 
             // Technically some builtin impls have nested obligations, but if
             // `Certainty::Yes`, then they should've all been verified and don't
             // need re-checking.
-            (Certainty::Yes, CandidateSource::BuiltinImpl(BuiltinImplSource::Misc)) => {
-                Ok(Some(ImplSource::Builtin(nested_obligations)))
+            (Certainty::Yes, CandidateSource::BuiltinImpl(src)) => {
+                Ok(Some(ImplSource::Builtin(src, nested_obligations)))
             }
 
             // It's fine not to do anything to rematch these, since there are no
             // nested obligations.
             (Certainty::Yes, CandidateSource::ParamEnv(_) | CandidateSource::AliasBound) => {
-                Ok(Some(ImplSource::Param(nested_obligations, ty::BoundConstness::NotConst)))
+                Ok(Some(ImplSource::Param(ty::BoundConstness::NotConst, nested_obligations)))
             }
 
-            (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity))
-            | (Certainty::Maybe(_), _) => Ok(None),
+            (Certainty::Maybe(_), _) => Ok(None),
         }
     }
 }
@@ -192,11 +166,12 @@ fn candidate_should_be_dropped_in_favor_of<'tcx>(
         }
         (_, CandidateSource::ParamEnv(_)) => true,
 
+        // FIXME: we could prefer earlier vtable bases perhaps...
         (
-            CandidateSource::BuiltinImpl(BuiltinImplSource::Object),
-            CandidateSource::BuiltinImpl(BuiltinImplSource::Object),
+            CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }),
+            CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }),
         ) => false,
-        (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Object)) => true,
+        (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. })) => true,
 
         (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => {
             tcx.specializes((other_def_id, victim_def_id))
@@ -234,108 +209,6 @@ fn rematch_impl<'tcx>(
     Ok(Some(ImplSource::UserDefined(ImplSourceUserDefinedData { impl_def_id, args, nested })))
 }
 
-fn rematch_object<'tcx>(
-    infcx: &InferCtxt<'tcx>,
-    goal: Goal<'tcx, ty::TraitPredicate<'tcx>>,
-    mut nested: Vec<PredicateObligation<'tcx>>,
-) -> SelectionResult<'tcx, Selection<'tcx>> {
-    let a_ty = structurally_normalize(goal.predicate.self_ty(), infcx, goal.param_env, &mut nested);
-    let ty::Dynamic(data, _, source_kind) = *a_ty.kind() else { bug!() };
-    let source_trait_ref = data.principal().unwrap().with_self_ty(infcx.tcx, a_ty);
-
-    let (is_upcasting, target_trait_ref_unnormalized) =
-        if Some(goal.predicate.def_id()) == infcx.tcx.lang_items().unsize_trait() {
-            assert_eq!(source_kind, ty::Dyn, "cannot upcast dyn*");
-            let b_ty = structurally_normalize(
-                goal.predicate.trait_ref.args.type_at(1),
-                infcx,
-                goal.param_env,
-                &mut nested,
-            );
-            if let ty::Dynamic(data, _, ty::Dyn) = *b_ty.kind() {
-                // FIXME: We also need to ensure that the source lifetime outlives the
-                // target lifetime. This doesn't matter for codegen, though, and only
-                // *really* matters if the goal's certainty is ambiguous.
-                (true, data.principal().unwrap().with_self_ty(infcx.tcx, a_ty))
-            } else {
-                bug!()
-            }
-        } else {
-            (false, ty::Binder::dummy(goal.predicate.trait_ref))
-        };
-
-    let mut target_trait_ref = None;
-    for candidate_trait_ref in supertraits(infcx.tcx, source_trait_ref) {
-        let result = infcx.commit_if_ok(|_| {
-            infcx.at(&ObligationCause::dummy(), goal.param_env).eq(
-                DefineOpaqueTypes::No,
-                target_trait_ref_unnormalized,
-                candidate_trait_ref,
-            )
-
-            // FIXME: We probably should at least shallowly verify these...
-        });
-
-        match result {
-            Ok(InferOk { value: (), obligations }) => {
-                target_trait_ref = Some(candidate_trait_ref);
-                nested.extend(obligations);
-                break;
-            }
-            Err(_) => continue,
-        }
-    }
-
-    let target_trait_ref = target_trait_ref.unwrap();
-
-    let mut offset = 0;
-    let Some((vtable_base, vtable_vptr_slot)) =
-        prepare_vtable_segments(infcx.tcx, source_trait_ref, |segment| {
-            match segment {
-                VtblSegment::MetadataDSA => {
-                    offset += TyCtxt::COMMON_VTABLE_ENTRIES.len();
-                }
-                VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
-                    let own_vtable_entries = count_own_vtable_entries(infcx.tcx, trait_ref);
-
-                    if trait_ref == target_trait_ref {
-                        if emit_vptr {
-                            return ControlFlow::Break((
-                                offset,
-                                Some(offset + count_own_vtable_entries(infcx.tcx, trait_ref)),
-                            ));
-                        } else {
-                            return ControlFlow::Break((offset, None));
-                        }
-                    }
-
-                    offset += own_vtable_entries;
-                    if emit_vptr {
-                        offset += 1;
-                    }
-                }
-            }
-            ControlFlow::Continue(())
-        })
-    else {
-        bug!();
-    };
-
-    // If we're upcasting, get the offset of the vtable pointer, otherwise get
-    // the base of the vtable.
-    Ok(Some(if is_upcasting {
-        // If source and target trait def ids are identical,
-        // then we are simply removing auto traits.
-        if source_trait_ref.def_id() == target_trait_ref.def_id() {
-            ImplSource::Builtin(nested)
-        } else {
-            ImplSource::TraitUpcasting(ImplSourceTraitUpcastingData { vtable_vptr_slot, nested })
-        }
-    } else {
-        ImplSource::Object(ImplSourceObjectData { vtable_base, nested })
-    }))
-}
-
 /// The `Unsize` trait is particularly important to coercion, so we try rematch it.
 /// NOTE: This must stay in sync with `consider_builtin_unsize_candidate` in trait
 /// goal assembly in the solver, both for soundness and in order to avoid ICEs.
@@ -343,6 +216,7 @@ fn rematch_unsize<'tcx>(
     infcx: &InferCtxt<'tcx>,
     goal: Goal<'tcx, ty::TraitPredicate<'tcx>>,
     mut nested: Vec<PredicateObligation<'tcx>>,
+    source: BuiltinImplSource,
 ) -> SelectionResult<'tcx, Selection<'tcx>> {
     let tcx = infcx.tcx;
     let a_ty = structurally_normalize(goal.predicate.self_ty(), infcx, goal.param_env, &mut nested);
@@ -379,6 +253,8 @@ fn rematch_unsize<'tcx>(
                 goal.param_env,
                 ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region)),
             ));
+
+            Ok(Some(ImplSource::Builtin(source, nested)))
         }
         // `[T; n]` -> `[T]` unsizing
         (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => {
@@ -389,6 +265,8 @@ fn rematch_unsize<'tcx>(
                     .expect("expected rematch to succeed")
                     .into_obligations(),
             );
+
+            Ok(Some(ImplSource::Builtin(source, nested)))
         }
         // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>`
         (&ty::Adt(a_def, a_args), &ty::Adt(b_def, b_args))
@@ -439,6 +317,8 @@ fn rematch_unsize<'tcx>(
                 goal.param_env,
                 ty::TraitRef::new(tcx, goal.predicate.def_id(), [a_tail_ty, b_tail_ty]),
             ));
+
+            Ok(Some(ImplSource::Builtin(source, nested)))
         }
         // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>`
         (&ty::Tuple(a_tys), &ty::Tuple(b_tys))
@@ -467,15 +347,18 @@ fn rematch_unsize<'tcx>(
             ));
 
             // We need to be able to detect tuple unsizing to require its feature gate.
-            return Ok(Some(ImplSource::TupleUnsizing(nested)));
+            assert_eq!(
+                source,
+                BuiltinImplSource::TupleUnsizing,
+                "compiler-errors wants to know if this can ever be triggered..."
+            );
+            Ok(Some(ImplSource::Builtin(source, nested)))
         }
         // FIXME: We *could* ICE here if either:
         // 1. the certainty is `Certainty::Yes`,
         // 2. we're in codegen (which should mean `Certainty::Yes`).
-        _ => return Ok(None),
+        _ => Ok(None),
     }
-
-    Ok(Some(ImplSource::Builtin(nested)))
 }
 
 fn structurally_normalize<'tcx>(
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 0f4fec50427..03ade738bb6 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -1,6 +1,6 @@
 use crate::traits::specialization_graph;
 
-use super::assembly::{self, structural_traits, BuiltinImplSource};
+use super::assembly::{self, structural_traits};
 use super::EvalCtxt;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefId;
@@ -10,6 +10,7 @@ use rustc_infer::traits::specialization_graph::LeafDef;
 use rustc_infer::traits::Reveal;
 use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
+use rustc_middle::traits::BuiltinImplSource;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::ProjectionPredicate;
 use rustc_middle::ty::{self, Ty, TyCtxt};
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 7f813c58c84..24ea9b5ea12 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -1,15 +1,14 @@
 //! Dealing with trait goals, i.e. `T: Trait<'a, U>`.
 
-use super::assembly::{self, structural_traits, BuiltinImplSource};
+use super::assembly::{self, structural_traits};
 use super::search_graph::OverflowHandler;
 use super::{EvalCtxt, SolverMode};
 use rustc_hir::def_id::DefId;
 use rustc_hir::{LangItem, Movability};
 use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::util::supertraits;
 use rustc_middle::traits::solve::inspect::CandidateKind;
-use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
-use rustc_middle::traits::Reveal;
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult};
+use rustc_middle::traits::{BuiltinImplSource, Reveal};
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections};
 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
 use rustc_middle::ty::{TraitPredicate, TypeVisitableExt};
@@ -382,37 +381,48 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             let b_ty = match ecx
                 .normalize_non_self_ty(goal.predicate.trait_ref.args.type_at(1), goal.param_env)
             {
-                Ok(Some(b_ty)) if !b_ty.is_ty_var() => b_ty,
-                Ok(_) => {
-                    return vec![(
-                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+                Ok(Some(b_ty)) => {
+                    // If we have a type var, then bail with ambiguity.
+                    if b_ty.is_ty_var() {
+                        return vec![(
+                            ecx.evaluate_added_goals_and_make_canonical_response(
+                                Certainty::AMBIGUOUS,
+                            )
                             .unwrap(),
-                        BuiltinImplSource::Ambiguity,
+                            BuiltinImplSource::Misc,
+                        )];
+                    } else {
+                        b_ty
+                    }
+                }
+                Ok(None) => {
+                    return vec![(
+                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Maybe(
+                            MaybeCause::Overflow,
+                        ))
+                        .unwrap(),
+                        BuiltinImplSource::Misc,
                     )];
                 }
                 Err(_) => return vec![],
             };
 
             let mut results = vec![];
+            results.extend(ecx.consider_builtin_dyn_upcast_candidates(goal.param_env, a_ty, b_ty));
             results.extend(
-                ecx.consider_builtin_dyn_upcast_candidates(goal.param_env, a_ty, b_ty)
+                ecx.consider_builtin_unsize_candidate(goal.with(ecx.tcx(), (a_ty, b_ty)))
                     .into_iter()
-                    .map(|resp| (resp, BuiltinImplSource::TraitUpcasting)),
-            );
-            results.extend(
-                ecx.consider_builtin_unsize_candidate(goal.param_env, a_ty, b_ty).into_iter().map(
-                    |resp| {
+                    .map(|resp| {
                         // If we're unsizing from tuple -> tuple, detect
                         let source =
                             if matches!((a_ty.kind(), b_ty.kind()), (ty::Tuple(..), ty::Tuple(..)))
                             {
-                                BuiltinImplSource::TupleUnsize
+                                BuiltinImplSource::TupleUnsizing
                             } else {
                                 BuiltinImplSource::Misc
                             };
                         (resp, source)
-                    },
-                ),
+                    }),
             );
 
             results
@@ -484,10 +494,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     fn consider_builtin_unsize_candidate(
         &mut self,
-        param_env: ty::ParamEnv<'tcx>,
-        a_ty: Ty<'tcx>,
-        b_ty: Ty<'tcx>,
+        goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>,
     ) -> QueryResult<'tcx> {
+        let Goal { param_env, predicate: (a_ty, b_ty) } = goal;
         self.probe_candidate("builtin unsize").enter(|ecx| {
             let tcx = ecx.tcx();
             match (a_ty.kind(), b_ty.kind()) {
@@ -614,7 +623,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         param_env: ty::ParamEnv<'tcx>,
         a_ty: Ty<'tcx>,
         b_ty: Ty<'tcx>,
-    ) -> Vec<CanonicalResponse<'tcx>> {
+    ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> {
         if a_ty.is_ty_var() || b_ty.is_ty_var() {
             bug!("unexpected type variable in unsize goal")
         }
@@ -634,57 +643,64 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             return vec![];
         }
 
-        let mut unsize_dyn_to_principal = |principal: Option<ty::PolyExistentialTraitRef<'tcx>>| {
-            self.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(param_env, new_a_ty, b_ty)?;
-                ecx.add_goal(Goal::new(
-                    tcx,
-                    param_env,
-                    ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)),
-                ));
-                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-            })
-        };
+        // 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(param_env, new_a_ty, b_ty)?;
+                        ecx.add_goal(Goal::new(
+                            tcx,
+                            param_env,
+                            ty::Binder::dummy(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(response) = unsize_dyn_to_principal(a_data.principal()) {
-                responses.push(response);
-            }
-        } else if let Some(a_principal) = a_data.principal()
-            && let Some(b_principal) = b_data.principal()
-        {
-            for super_trait_ref in supertraits(tcx, a_principal.with_self_ty(tcx, a_ty)) {
-                if super_trait_ref.def_id() != b_principal.def_id() {
-                    continue;
-                }
-                let erased_trait_ref = super_trait_ref
-                    .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref));
-                if let Ok(response) = unsize_dyn_to_principal(Some(erased_trait_ref)) {
-                    responses.push(response);
-                }
+            if let Ok(resp) = unsize_dyn_to_principal(self, 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,
+                        Some(new_a_principal.map_bound(|trait_ref| {
+                            ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)
+                        })),
+                    ) {
+                        responses
+                            .push((resp, BuiltinImplSource::TraitUpcasting { vtable_vptr_slot }));
+                    }
+                },
+            );
         }
 
         responses