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