compiler/rustc_trait_selection/src/solve/assembly.rs

   1 //! Code shared by trait and projection goals for candidate assembly.
   2
   3 use super::infcx_ext::InferCtxtExt;
   4 use super::{CanonicalResponse, Certainty, EvalCtxt, Goal};
   5 use rustc_hir::def_id::DefId;
   6 use rustc_infer::traits::query::NoSolution;
   7 use rustc_middle::ty::TypeFoldable;
   8 use rustc_middle::ty::{self, Ty, TyCtxt};
   9 use std::fmt::Debug;
  10
  11 /// A candidate is a possible way to prove a goal.
  12 ///
  13 /// It consists of both the `source`, which describes how that goal would be proven,
  14 /// and the `result` when using the given `source`.
  15 #[derive(Debug, Clone)]
  16 pub(super) struct Candidate<'tcx> {
  17     pub(super) source: CandidateSource,
  18     pub(super) result: CanonicalResponse<'tcx>,
  19 }
  20
  21 /// Possible ways the given goal can be proven.
  22 #[derive(Debug, Clone, Copy)]
  23 pub(super) enum CandidateSource {
  24     /// A user written impl.
  25     ///
  26     /// ## Examples
  27     ///
  28     /// ```rust
  29     /// fn main() {
  30     ///     let x: Vec<u32> = Vec::new();
  31     ///     // This uses the impl from the standard library to prove `Vec<T>: Clone`.
  32     ///     let y = x.clone();
  33     /// }
  34     /// ```
  35     Impl(DefId),
  36     /// A builtin impl generated by the compiler. When adding a new special
  37     /// trait, try to use actual impls whenever possible. Builtin impls should
  38     /// only be used in cases where the impl cannot be manually be written.
  39     ///
  40     /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`.
  41     /// For a list of all traits with builtin impls, check out the
  42     /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not
  43     BuiltinImpl,
  44     /// An assumption from the environment.
  45     ///
  46     /// More precicely we've used the `n-th` assumption in the `param_env`.
  47     ///
  48     /// ## Examples
  49     ///
  50     /// ```rust
  51     /// fn is_clone<T: Clone>(x: T) -> (T, T) {
  52     ///     // This uses the assumption `T: Clone` from the `where`-bounds
  53     ///     // to prove `T: Clone`.
  54     ///     (x.clone(), x)
  55     /// }
  56     /// ```
  57     ParamEnv(usize),
  58     /// If the self type is an alias type, e.g. an opaque type or a projection,
  59     /// we know the bounds on that alias to hold even without knowing its concrete
  60     /// underlying type.
  61     ///
  62     /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
  63     /// the self type.
  64     ///
  65     /// ## Examples
  66     ///
  67     /// ```rust
  68     /// trait Trait {
  69     ///     type Assoc: Clone;
  70     /// }
  71     ///
  72     /// fn foo<T: Trait>(x: <T as Trait>::Assoc) {
  73     ///     // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in
  74     ///     // in the trait definition.
  75     ///     let _y = x.clone();
  76     /// }
  77     /// ```
  78     AliasBound(usize),
  79 }
  80
  81 pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy {
  82     fn self_ty(self) -> Ty<'tcx>;
  83
  84     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
  85
  86     fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
  87
  88     fn consider_impl_candidate(
  89         ecx: &mut EvalCtxt<'_, 'tcx>,
  90         goal: Goal<'tcx, Self>,
  91         impl_def_id: DefId,
  92     ) -> Result<Certainty, NoSolution>;
  93
  94     fn consider_builtin_sized_candidate(
  95         ecx: &mut EvalCtxt<'_, 'tcx>,
  96         goal: Goal<'tcx, Self>,
  97     ) -> Result<Certainty, NoSolution>;
  98
  99     fn consider_assumption(
 100         ecx: &mut EvalCtxt<'_, 'tcx>,
 101         goal: Goal<'tcx, Self>,
 102         assumption: ty::Predicate<'tcx>,
 103     ) -> Result<Certainty, NoSolution>;
 104 }
 105 impl<'tcx> EvalCtxt<'_, 'tcx> {
 106     pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
 107         &mut self,
 108         goal: Goal<'tcx, G>,
 109     ) -> Vec<Candidate<'tcx>> {
 110         let mut candidates = Vec::new();
 111
 112         self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
 113
 114         self.assemble_impl_candidates(goal, &mut candidates);
 115
 116         self.assemble_builtin_impl_candidates(goal, &mut candidates);
 117
 118         self.assemble_param_env_candidates(goal, &mut candidates);
 119
 120         self.assemble_alias_bound_candidates(goal, &mut candidates);
 121
 122         candidates
 123     }
 124
 125     /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
 126     ///
 127     /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
 128     /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
 129     /// this case as projections as self types add `
 130     fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
 131         &mut self,
 132         goal: Goal<'tcx, G>,
 133         candidates: &mut Vec<Candidate<'tcx>>,
 134     ) {
 135         let tcx = self.tcx();
 136         // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
 137         let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
 138             return
 139         };
 140         self.infcx.probe(|_| {
 141             let normalized_ty = self.infcx.next_ty_infer();
 142             let normalizes_to_goal = goal.with(
 143                 tcx,
 144                 ty::Binder::dummy(ty::ProjectionPredicate {
 145                     projection_ty,
 146                     term: normalized_ty.into(),
 147                 }),
 148             );
 149             let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
 150                 Ok((_, certainty)) => certainty,
 151                 Err(NoSolution) => return,
 152             };
 153
 154             // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
 155             // This doesn't work as long as we use `CandidateSource` in winnowing.
 156             let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
 157             // FIXME: This is broken if we care about the `usize` of `AliasBound` because the self type
 158             // could be normalized to yet another projection with different item bounds.
 159             let normalized_candidates = self.assemble_and_evaluate_candidates(goal);
 160             for mut normalized_candidate in normalized_candidates {
 161                 normalized_candidate.result =
 162                     normalized_candidate.result.unchecked_map(|mut response| {
 163                         // FIXME: This currently hides overflow in the normalization step of the self type
 164                         // which is probably wrong. Maybe `unify_and` should actually keep overflow as
 165                         // we treat it as non-fatal anyways.
 166                         response.certainty = response.certainty.unify_and(normalization_certainty);
 167                         response
 168                     });
 169                 candidates.push(normalized_candidate);
 170             }
 171         })
 172     }
 173
 174     fn assemble_impl_candidates<G: GoalKind<'tcx>>(
 175         &mut self,
 176         goal: Goal<'tcx, G>,
 177         candidates: &mut Vec<Candidate<'tcx>>,
 178     ) {
 179         let tcx = self.tcx();
 180         tcx.for_each_relevant_impl(
 181             goal.predicate.trait_def_id(tcx),
 182             goal.predicate.self_ty(),
 183             |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id)
 184                 .and_then(|certainty| self.make_canonical_response(certainty))
 185             {
 186                 Ok(result) => candidates
 187                     .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
 188                 Err(NoSolution) => (),
 189             },
 190         );
 191     }
 192
 193     fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
 194         &mut self,
 195         goal: Goal<'tcx, G>,
 196         candidates: &mut Vec<Candidate<'tcx>>,
 197     ) {
 198         let lang_items = self.tcx().lang_items();
 199         let trait_def_id = goal.predicate.trait_def_id(self.tcx());
 200         let result = if lang_items.sized_trait() == Some(trait_def_id) {
 201             G::consider_builtin_sized_candidate(self, goal)
 202         } else {
 203             Err(NoSolution)
 204         };
 205
 206         match result.and_then(|certainty| self.make_canonical_response(certainty)) {
 207             Ok(result) => {
 208                 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 209             }
 210             Err(NoSolution) => (),
 211         }
 212     }
 213
 214     fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
 215         &mut self,
 216         goal: Goal<'tcx, G>,
 217         candidates: &mut Vec<Candidate<'tcx>>,
 218     ) {
 219         for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
 220             match G::consider_assumption(self, goal, assumption)
 221                 .and_then(|certainty| self.make_canonical_response(certainty))
 222             {
 223                 Ok(result) => {
 224                     candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
 225                 }
 226                 Err(NoSolution) => (),
 227             }
 228         }
 229     }
 230
 231     fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
 232         &mut self,
 233         goal: Goal<'tcx, G>,
 234         candidates: &mut Vec<Candidate<'tcx>>,
 235     ) {
 236         let alias_ty = match goal.predicate.self_ty().kind() {
 237             ty::Bool
 238             | ty::Char
 239             | ty::Int(_)
 240             | ty::Uint(_)
 241             | ty::Float(_)
 242             | ty::Adt(_, _)
 243             | ty::Foreign(_)
 244             | ty::Str
 245             | ty::Array(_, _)
 246             | ty::Slice(_)
 247             | ty::RawPtr(_)
 248             | ty::Ref(_, _, _)
 249             | ty::FnDef(_, _)
 250             | ty::FnPtr(_)
 251             | ty::Dynamic(..)
 252             | ty::Closure(..)
 253             | ty::Generator(..)
 254             | ty::GeneratorWitness(_)
 255             | ty::Never
 256             | ty::Tuple(_)
 257             | ty::Param(_)
 258             | ty::Placeholder(..)
 259             | ty::Infer(_)
 260             | ty::Error(_) => return,
 261             ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
 262             ty::Alias(_, alias_ty) => alias_ty,
 263         };
 264
 265         for (i, (assumption, _)) in self
 266             .tcx()
 267             .bound_explicit_item_bounds(alias_ty.def_id)
 268             .subst_iter_copied(self.tcx(), alias_ty.substs)
 269             .enumerate()
 270         {
 271             match G::consider_assumption(self, goal, assumption)
 272                 .and_then(|certainty| self.make_canonical_response(certainty))
 273             {
 274                 Ok(result) => {
 275                     candidates.push(Candidate { source: CandidateSource::AliasBound(i), result })
 276                 }
 277                 Err(NoSolution) => (),
 278             }
 279         }
 280     }
 281 }