Rollup merge of #107004 - compiler-errors:new-solver-new-candidates-2, r=lcnr

Implement some candidates for the new solver (redux)

Based on #106718, so the diff is hard to read without it. See [here](https://github.com/rust-lang/rust/compare/98700cf481bce946bff316b56836cfffd885127b...compiler-errors:rust:new-solver-new-candidates-2) for an easier view until that one lands.

Of note:
* 44af916020fb43c12070125c45b6dee4ec303bbc fixes a bug where we need to make the query response *inside* of a probe, or else we make no inference progress (I think)
* 50daad5acd2f163d03e7ffab942534f09bc36e2e implements `consider_assumption` for traits and predicates. I'm not sure if using `sup` here is necessary or if `eq` is fine.
* We decided that all of the `instantiate_constituent_tys_for_*` functions are verbose but ok, since they need to be exhaustive and the logic between each of them is not similar enough, right?

r? ``@lcnr``

7 files changed, 442 insertions, 47 deletions

diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index ccac6e8f77a..d681df14af1 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -2357,6 +2357,11 @@ impl<'tcx> TyCtxt<'tcx> {
         self.trait_def(trait_def_id).has_auto_impl
     }
 
+    /// Returns `true` if this is a trait alias.
+    pub fn trait_is_alias(self, trait_def_id: DefId) -> bool {
+        self.def_kind(trait_def_id) == DefKind::TraitAlias
+    }
+
     pub fn trait_is_coinductive(self, trait_def_id: DefId) -> bool {
         self.trait_is_auto(trait_def_id) || self.lang_items().sized_trait() == Some(trait_def_id)
     }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs
index cd6e4d2bccd..2336fb53aec 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly.rs
@@ -1,9 +1,10 @@
 //! Code shared by trait and projection goals for candidate assembly.
 
 use super::infcx_ext::InferCtxtExt;
-use super::{CanonicalResponse, Certainty, EvalCtxt, Goal};
+use super::{CanonicalResponse, EvalCtxt, Goal, QueryResult};
 use rustc_hir::def_id::DefId;
 use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::util::elaborate_predicates;
 use rustc_middle::ty::TypeFoldable;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use std::fmt::Debug;
@@ -89,19 +90,35 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
         impl_def_id: DefId,
-    ) -> Result<Certainty, NoSolution>;
+    ) -> QueryResult<'tcx>;
+
+    fn consider_assumption(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_auto_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_trait_alias_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
 
     fn consider_builtin_sized_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
-    ) -> Result<Certainty, NoSolution>;
+    ) -> QueryResult<'tcx>;
 
-    fn consider_assumption(
+    fn consider_builtin_copy_clone_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
-        assumption: ty::Predicate<'tcx>,
-    ) -> Result<Certainty, NoSolution>;
+    ) -> QueryResult<'tcx>;
 }
+
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
         &mut self,
@@ -119,6 +136,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         self.assemble_alias_bound_candidates(goal, &mut candidates);
 
+        self.assemble_object_bound_candidates(goal, &mut candidates);
+
         candidates
     }
 
@@ -180,9 +199,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         tcx.for_each_relevant_impl(
             goal.predicate.trait_def_id(tcx),
             goal.predicate.self_ty(),
-            |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id)
-                .and_then(|certainty| self.make_canonical_response(certainty))
-            {
+            |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
                 Ok(result) => candidates
                     .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
                 Err(NoSolution) => (),
@@ -197,13 +214,21 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) {
         let lang_items = self.tcx().lang_items();
         let trait_def_id = goal.predicate.trait_def_id(self.tcx());
-        let result = if lang_items.sized_trait() == Some(trait_def_id) {
+        let result = if self.tcx().trait_is_auto(trait_def_id) {
+            G::consider_auto_trait_candidate(self, goal)
+        } else if self.tcx().trait_is_alias(trait_def_id) {
+            G::consider_trait_alias_candidate(self, goal)
+        } else if lang_items.sized_trait() == Some(trait_def_id) {
             G::consider_builtin_sized_candidate(self, goal)
+        } else if lang_items.copy_trait() == Some(trait_def_id)
+            || lang_items.clone_trait() == Some(trait_def_id)
+        {
+            G::consider_builtin_copy_clone_candidate(self, goal)
         } else {
             Err(NoSolution)
         };
 
-        match result.and_then(|certainty| self.make_canonical_response(certainty)) {
+        match result {
             Ok(result) => {
                 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
             }
@@ -217,9 +242,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         candidates: &mut Vec<Candidate<'tcx>>,
     ) {
         for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
-            match G::consider_assumption(self, goal, assumption)
-                .and_then(|certainty| self.make_canonical_response(certainty))
-            {
+            match G::consider_assumption(self, goal, assumption) {
                 Ok(result) => {
                     candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
                 }
@@ -268,9 +291,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             .subst_iter_copied(self.tcx(), alias_ty.substs)
             .enumerate()
         {
-            match G::consider_assumption(self, goal, assumption)
-                .and_then(|certainty| self.make_canonical_response(certainty))
-            {
+            match G::consider_assumption(self, goal, assumption) {
                 Ok(result) => {
                     candidates.push(Candidate { source: CandidateSource::AliasBound(i), result })
                 }
@@ -278,4 +299,52 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             }
         }
     }
+
+    fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let self_ty = goal.predicate.self_ty();
+        let bounds = match *self_ty.kind() {
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Uint(_)
+            | ty::Float(_)
+            | ty::Adt(_, _)
+            | ty::Foreign(_)
+            | ty::Str
+            | ty::Array(_, _)
+            | ty::Slice(_)
+            | ty::RawPtr(_)
+            | ty::Ref(_, _, _)
+            | ty::FnDef(_, _)
+            | ty::FnPtr(_)
+            | ty::Alias(..)
+            | ty::Closure(..)
+            | ty::Generator(..)
+            | ty::GeneratorWitness(_)
+            | ty::Never
+            | ty::Tuple(_)
+            | ty::Param(_)
+            | ty::Placeholder(..)
+            | ty::Infer(_)
+            | ty::Error(_) => return,
+            ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
+            ty::Dynamic(bounds, ..) => bounds,
+        };
+
+        let tcx = self.tcx();
+        for assumption in
+            elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
+        {
+            match G::consider_assumption(self, goal, assumption.predicate) {
+                Ok(result) => {
+                    candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
+                }
+                Err(NoSolution) => (),
+            }
+        }
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/infcx_ext.rs b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs
index 9b7feb50537..42f597c781d 100644
--- a/compiler/rustc_trait_selection/src/solve/infcx_ext.rs
+++ b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs
@@ -1,10 +1,10 @@
 use rustc_infer::infer::at::ToTrace;
 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
-use rustc_infer::infer::{InferCtxt, InferOk};
+use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::ObligationCause;
 use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
-use rustc_middle::ty::{self, Ty};
+use rustc_middle::ty::{self, Ty, TypeFoldable};
 use rustc_span::DUMMY_SP;
 
 use super::Goal;
@@ -25,6 +25,11 @@ pub(super) trait InferCtxtExt<'tcx> {
         lhs: T,
         rhs: T,
     ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution>;
+
+    fn instantiate_bound_vars_with_infer<T: TypeFoldable<'tcx> + Copy>(
+        &self,
+        value: ty::Binder<'tcx, T>,
+    ) -> T;
 }
 
 impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> {
@@ -59,4 +64,15 @@ impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> {
                 NoSolution
             })
     }
+
+    fn instantiate_bound_vars_with_infer<T: TypeFoldable<'tcx> + Copy>(
+        &self,
+        value: ty::Binder<'tcx, T>,
+    ) -> T {
+        self.replace_bound_vars_with_fresh_vars(
+            DUMMY_SP,
+            LateBoundRegionConversionTime::HigherRankedType,
+            value,
+        )
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 579cd6a2d59..32eb84635b5 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -313,6 +313,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             }
         })
     }
+
+    fn evaluate_all_and_make_canonical_response(
+        &mut self,
+        goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
+    ) -> QueryResult<'tcx> {
+        self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty))
+    }
 }
 
 #[instrument(level = "debug", skip(infcx), ret)]
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 0658836fb9c..00c7edf0ef8 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -191,7 +191,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
         impl_def_id: DefId,
-    ) -> Result<Certainty, NoSolution> {
+    ) -> QueryResult<'tcx> {
         let tcx = ecx.tcx();
 
         let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx);
@@ -229,7 +229,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 impl_def_id
             )? else {
                 let certainty = Certainty::Maybe(MaybeCause::Ambiguity);
-                return Ok(trait_ref_certainty.unify_and(certainty));
+                return ecx.make_canonical_response(trait_ref_certainty.unify_and(certainty));
             };
 
             if !assoc_def.item.defaultness(tcx).has_value() {
@@ -286,27 +286,70 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             let rhs_certainty =
                 ecx.evaluate_all(nested_goals).expect("failed to unify with unconstrained term");
 
-            Ok(trait_ref_certainty.unify_and(rhs_certainty))
+            ecx.make_canonical_response(trait_ref_certainty.unify_and(rhs_certainty))
         })
     }
 
+    fn consider_assumption(
+        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() {
+            ecx.infcx.probe(|_| {
+                let assumption_projection_pred =
+                    ecx.infcx.instantiate_bound_vars_with_infer(poly_projection_pred);
+                let nested_goals = ecx.infcx.eq(
+                    goal.param_env,
+                    goal.predicate.projection_ty,
+                    assumption_projection_pred.projection_ty,
+                )?;
+                let subst_certainty = ecx.evaluate_all(nested_goals)?;
+
+                // The term of our goal should be fully unconstrained, so this should never fail.
+                //
+                // It can however be ambiguous when the resolved type is a projection.
+                let nested_goals = ecx
+                    .infcx
+                    .eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)
+                    .expect("failed to unify with unconstrained term");
+                let rhs_certainty = ecx
+                    .evaluate_all(nested_goals)
+                    .expect("failed to unify with unconstrained term");
+
+                ecx.make_canonical_response(subst_certainty.unify_and(rhs_certainty))
+            })
+        } else {
+            Err(NoSolution)
+        }
+    }
+
+    fn consider_auto_trait_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("auto traits do not have associated types: {:?}", goal);
+    }
+
+    fn consider_trait_alias_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("trait aliases do not have associated types: {:?}", goal);
+    }
+
     fn consider_builtin_sized_candidate(
         _ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
-    ) -> Result<Certainty, NoSolution> {
+    ) -> QueryResult<'tcx> {
         bug!("`Sized` does not have an associated type: {:?}", goal);
     }
 
-    fn consider_assumption(
+    fn consider_builtin_copy_clone_candidate(
         _ecx: &mut EvalCtxt<'_, 'tcx>,
-        _goal: Goal<'tcx, Self>,
-        assumption: ty::Predicate<'tcx>,
-    ) -> Result<Certainty, NoSolution> {
-        if let Some(_poly_projection_pred) = assumption.to_opt_poly_projection_pred() {
-            unimplemented!()
-        } else {
-            Err(NoSolution)
-        }
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`Copy`/`Clone` does not have an associated type: {:?}", goal);
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index bbe175d5cc8..1ebcfd03c14 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -4,14 +4,17 @@ use std::iter;
 
 use super::assembly::{self, Candidate, CandidateSource};
 use super::infcx_ext::InferCtxtExt;
-use super::{Certainty, EvalCtxt, Goal, QueryResult};
+use super::{EvalCtxt, Goal, QueryResult};
 use rustc_hir::def_id::DefId;
+use rustc_infer::infer::InferCtxt;
 use rustc_infer::traits::query::NoSolution;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::TraitPredicate;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_span::DUMMY_SP;
 
+mod structural_traits;
+
 impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
     fn self_ty(self) -> Ty<'tcx> {
         self.self_ty()
@@ -29,7 +32,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, TraitPredicate<'tcx>>,
         impl_def_id: DefId,
-    ) -> Result<Certainty, NoSolution> {
+    ) -> QueryResult<'tcx> {
         let tcx = ecx.tcx();
 
         let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
@@ -53,31 +56,104 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                 .into_iter()
                 .map(|pred| goal.with(tcx, pred));
             nested_goals.extend(where_clause_bounds);
-            ecx.evaluate_all(nested_goals)
+            ecx.evaluate_all_and_make_canonical_response(nested_goals)
         })
     }
 
-    fn consider_builtin_sized_candidate(
-        _ecx: &mut EvalCtxt<'_, 'tcx>,
-        _goal: Goal<'tcx, Self>,
-    ) -> Result<Certainty, NoSolution> {
-        unimplemented!();
-    }
-
     fn consider_assumption(
-        _ecx: &mut EvalCtxt<'_, 'tcx>,
-        _goal: Goal<'tcx, Self>,
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
         assumption: ty::Predicate<'tcx>,
-    ) -> Result<Certainty, NoSolution> {
-        if let Some(_poly_trait_pred) = assumption.to_opt_poly_trait_pred() {
-            unimplemented!()
+    ) -> QueryResult<'tcx> {
+        if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred() {
+            // FIXME: Constness and polarity
+            ecx.infcx.probe(|_| {
+                let assumption_trait_pred =
+                    ecx.infcx.instantiate_bound_vars_with_infer(poly_trait_pred);
+                let nested_goals = ecx.infcx.eq(
+                    goal.param_env,
+                    goal.predicate.trait_ref,
+                    assumption_trait_pred.trait_ref,
+                )?;
+                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>,
+    ) -> QueryResult<'tcx> {
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            goal,
+            structural_traits::instantiate_constituent_tys_for_auto_trait,
+        )
+    }
+
+    fn consider_trait_alias_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        let tcx = ecx.tcx();
+
+        ecx.infcx.probe(|_| {
+            let nested_obligations = tcx
+                .predicates_of(goal.predicate.def_id())
+                .instantiate(tcx, goal.predicate.trait_ref.substs);
+            ecx.evaluate_all_and_make_canonical_response(
+                nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(),
+            )
+        })
+    }
+
+    fn consider_builtin_sized_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            goal,
+            structural_traits::instantiate_constituent_tys_for_sized_trait,
+        )
+    }
+
+    fn consider_builtin_copy_clone_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            goal,
+            structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
+        )
+    }
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
+    /// Convenience function for traits that are structural, i.e. that only
+    /// have nested subgoals that only change the self type. Unlike other
+    /// evaluate-like helpers, this does a probe, so it doesn't need to be
+    /// wrapped in one.
+    fn probe_and_evaluate_goal_for_constituent_tys(
+        &mut self,
+        goal: Goal<'tcx, TraitPredicate<'tcx>>,
+        constituent_tys: impl Fn(&InferCtxt<'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
+    ) -> QueryResult<'tcx> {
+        self.infcx.probe(|_| {
+            self.evaluate_all_and_make_canonical_response(
+                constituent_tys(self.infcx, goal.predicate.self_ty())?
+                    .into_iter()
+                    .map(|ty| {
+                        goal.with(
+                            self.tcx(),
+                            ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)),
+                        )
+                    })
+                    .collect(),
+            )
+        })
+    }
+
     pub(super) fn compute_trait_goal(
         &mut self,
         goal: Goal<'tcx, TraitPredicate<'tcx>>,
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
new file mode 100644
index 00000000000..bbc0c772532
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
@@ -0,0 +1,179 @@
+use rustc_hir::{Movability, Mutability};
+use rustc_infer::{infer::InferCtxt, traits::query::NoSolution};
+use rustc_middle::ty::{self, Ty};
+
+// Calculates the constituent types of a type for `auto trait` purposes.
+//
+// For types with an "existential" binder, i.e. generator witnesses, we also
+// instantiate the binder with placeholders eagerly.
+pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<Ty<'tcx>>, NoSolution> {
+    let tcx = infcx.tcx;
+    match *ty.kind() {
+        ty::Uint(_)
+        | ty::Int(_)
+        | ty::Bool
+        | ty::Float(_)
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::Str
+        | ty::Error(_)
+        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+        | ty::Never
+        | ty::Char => Ok(vec![]),
+
+        ty::Placeholder(..)
+        | ty::Dynamic(..)
+        | ty::Param(..)
+        | ty::Foreign(..)
+        | ty::Alias(ty::Projection, ..)
+        | ty::Bound(..)
+        | ty::Infer(ty::TyVar(_)) => {
+            // FIXME: Do we need to mark anything as ambiguous here? Yeah?
+            Err(NoSolution)
+        }
+
+        ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(),
+
+        ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => {
+            Ok(vec![element_ty])
+        }
+
+        ty::Array(element_ty, _) | ty::Slice(element_ty) => Ok(vec![element_ty]),
+
+        ty::Tuple(ref tys) => {
+            // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
+            Ok(tys.iter().collect())
+        }
+
+        ty::Closure(_, ref substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]),
+
+        ty::Generator(_, ref substs, _) => {
+            let generator_substs = substs.as_generator();
+            Ok(vec![generator_substs.tupled_upvars_ty(), generator_substs.witness()])
+        }
+
+        ty::GeneratorWitness(types) => {
+            Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec())
+        }
+
+        // For `PhantomData<T>`, we pass `T`.
+        ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]),
+
+        ty::Adt(def, substs) => Ok(def.all_fields().map(|f| f.ty(tcx, substs)).collect()),
+
+        ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) => {
+            // We can resolve the `impl Trait` to its concrete type,
+            // which enforces a DAG between the functions requiring
+            // the auto trait bounds in question.
+            Ok(vec![tcx.bound_type_of(def_id).subst(tcx, substs)])
+        }
+    }
+}
+
+pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<Ty<'tcx>>, NoSolution> {
+    match *ty.kind() {
+        ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+        | ty::Uint(_)
+        | ty::Int(_)
+        | ty::Bool
+        | ty::Float(_)
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::RawPtr(..)
+        | ty::Char
+        | ty::Ref(..)
+        | ty::Generator(..)
+        | ty::GeneratorWitness(..)
+        | ty::Array(..)
+        | ty::Closure(..)
+        | ty::Never
+        | ty::Dynamic(_, _, ty::DynStar)
+        | ty::Error(_) => Ok(vec![]),
+
+        ty::Str
+        | ty::Slice(_)
+        | ty::Dynamic(..)
+        | ty::Foreign(..)
+        | ty::Alias(..)
+        | ty::Param(_) => Err(NoSolution),
+
+        ty::Infer(ty::TyVar(_)) => bug!("FIXME: ambiguous"),
+
+        ty::Placeholder(..)
+        | ty::Bound(..)
+        | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(),
+
+        ty::Tuple(tys) => Ok(tys.to_vec()),
+
+        ty::Adt(def, substs) => {
+            let sized_crit = def.sized_constraint(infcx.tcx);
+            Ok(sized_crit
+                .0
+                .iter()
+                .map(|ty| sized_crit.rebind(*ty).subst(infcx.tcx, substs))
+                .collect())
+        }
+    }
+}
+
+pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<Ty<'tcx>>, NoSolution> {
+    match *ty.kind() {
+        ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::Error(_) => Ok(vec![]),
+
+        // Implementations are provided in core
+        ty::Uint(_)
+        | ty::Int(_)
+        | ty::Bool
+        | ty::Float(_)
+        | ty::Char
+        | ty::RawPtr(..)
+        | ty::Never
+        | ty::Ref(_, _, Mutability::Not)
+        | ty::Array(..) => Err(NoSolution),
+
+        ty::Dynamic(..)
+        | ty::Str
+        | ty::Slice(_)
+        | ty::Generator(_, _, Movability::Static)
+        | ty::Foreign(..)
+        | ty::Ref(_, _, Mutability::Mut)
+        | ty::Adt(_, _)
+        | ty::Alias(_, _)
+        | ty::Param(_) => Err(NoSolution),
+
+        ty::Infer(ty::TyVar(_)) => bug!("FIXME: ambiguous"),
+
+        ty::Placeholder(..)
+        | ty::Bound(..)
+        | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(),
+
+        ty::Tuple(tys) => Ok(tys.to_vec()),
+
+        ty::Closure(_, substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]),
+
+        ty::Generator(_, substs, Movability::Movable) => {
+            if infcx.tcx.features().generator_clone {
+                let generator = substs.as_generator();
+                Ok(vec![generator.tupled_upvars_ty(), generator.witness()])
+            } else {
+                Err(NoSolution)
+            }
+        }
+
+        ty::GeneratorWitness(types) => {
+            Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec())
+        }
+    }
+}