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, 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 + Eq {
  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     fn consider_builtin_pointer_sized_candidate(
 122         ecx: &mut EvalCtxt<'_, 'tcx>,
 123         goal: Goal<'tcx, Self>,
 124     ) -> QueryResult<'tcx>;
 125
 126     fn consider_builtin_fn_trait_candidates(
 127         ecx: &mut EvalCtxt<'_, 'tcx>,
 128         goal: Goal<'tcx, Self>,
 129         kind: ty::ClosureKind,
 130     ) -> QueryResult<'tcx>;
 131
 132     fn consider_builtin_tuple_candidate(
 133         ecx: &mut EvalCtxt<'_, 'tcx>,
 134         goal: Goal<'tcx, Self>,
 135     ) -> QueryResult<'tcx>;
 136
 137     fn consider_builtin_pointee_candidate(
 138         ecx: &mut EvalCtxt<'_, 'tcx>,
 139         goal: Goal<'tcx, Self>,
 140     ) -> QueryResult<'tcx>;
 141
 142     fn consider_builtin_future_candidate(
 143         ecx: &mut EvalCtxt<'_, 'tcx>,
 144         goal: Goal<'tcx, Self>,
 145     ) -> QueryResult<'tcx>;
 146
 147     fn consider_builtin_generator_candidate(
 148         ecx: &mut EvalCtxt<'_, 'tcx>,
 149         goal: Goal<'tcx, Self>,
 150     ) -> QueryResult<'tcx>;
 151 }
 152
 153 impl<'tcx> EvalCtxt<'_, 'tcx> {
 154     pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
 155         &mut self,
 156         goal: Goal<'tcx, G>,
 157     ) -> Vec<Candidate<'tcx>> {
 158         debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal));
 159
 160         // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule,
 161         // object bound, alias bound, etc. We are unable to determine this until we can at
 162         // least structually resolve the type one layer.
 163         if goal.predicate.self_ty().is_ty_var() {
 164             return vec![Candidate {
 165                 source: CandidateSource::BuiltinImpl,
 166                 result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(),
 167             }];
 168         }
 169
 170         let mut candidates = Vec::new();
 171
 172         self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
 173
 174         self.assemble_impl_candidates(goal, &mut candidates);
 175
 176         self.assemble_builtin_impl_candidates(goal, &mut candidates);
 177
 178         self.assemble_param_env_candidates(goal, &mut candidates);
 179
 180         self.assemble_alias_bound_candidates(goal, &mut candidates);
 181
 182         self.assemble_object_bound_candidates(goal, &mut candidates);
 183
 184         candidates
 185     }
 186
 187     /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
 188     ///
 189     /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
 190     /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
 191     /// this case as projections as self types add `
 192     fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
 193         &mut self,
 194         goal: Goal<'tcx, G>,
 195         candidates: &mut Vec<Candidate<'tcx>>,
 196     ) {
 197         let tcx = self.tcx();
 198         // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
 199         let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
 200             return
 201         };
 202         self.infcx.probe(|_| {
 203             let normalized_ty = self.infcx.next_ty_infer();
 204             let normalizes_to_goal = goal.with(
 205                 tcx,
 206                 ty::Binder::dummy(ty::ProjectionPredicate {
 207                     projection_ty,
 208                     term: normalized_ty.into(),
 209                 }),
 210             );
 211             let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
 212                 Ok((_, certainty)) => certainty,
 213                 Err(NoSolution) => return,
 214             };
 215             let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty);
 216
 217             // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
 218             // This doesn't work as long as we use `CandidateSource` in winnowing.
 219             let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
 220             // FIXME: This is broken if we care about the `usize` of `AliasBound` because the self type
 221             // could be normalized to yet another projection with different item bounds.
 222             let normalized_candidates = self.assemble_and_evaluate_candidates(goal);
 223             for mut normalized_candidate in normalized_candidates {
 224                 normalized_candidate.result =
 225                     normalized_candidate.result.unchecked_map(|mut response| {
 226                         // FIXME: This currently hides overflow in the normalization step of the self type
 227                         // which is probably wrong. Maybe `unify_and` should actually keep overflow as
 228                         // we treat it as non-fatal anyways.
 229                         response.certainty = response.certainty.unify_and(normalization_certainty);
 230                         response
 231                     });
 232                 candidates.push(normalized_candidate);
 233             }
 234         })
 235     }
 236
 237     fn assemble_impl_candidates<G: GoalKind<'tcx>>(
 238         &mut self,
 239         goal: Goal<'tcx, G>,
 240         candidates: &mut Vec<Candidate<'tcx>>,
 241     ) {
 242         let tcx = self.tcx();
 243         tcx.for_each_relevant_impl(
 244             goal.predicate.trait_def_id(tcx),
 245             goal.predicate.self_ty(),
 246             |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
 247                 Ok(result) => candidates
 248                     .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
 249                 Err(NoSolution) => (),
 250             },
 251         );
 252     }
 253
 254     fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
 255         &mut self,
 256         goal: Goal<'tcx, G>,
 257         candidates: &mut Vec<Candidate<'tcx>>,
 258     ) {
 259         let lang_items = self.tcx().lang_items();
 260         let trait_def_id = goal.predicate.trait_def_id(self.tcx());
 261         let result = if self.tcx().trait_is_auto(trait_def_id) {
 262             G::consider_auto_trait_candidate(self, goal)
 263         } else if self.tcx().trait_is_alias(trait_def_id) {
 264             G::consider_trait_alias_candidate(self, goal)
 265         } else if lang_items.sized_trait() == Some(trait_def_id) {
 266             G::consider_builtin_sized_candidate(self, goal)
 267         } else if lang_items.copy_trait() == Some(trait_def_id)
 268             || lang_items.clone_trait() == Some(trait_def_id)
 269         {
 270             G::consider_builtin_copy_clone_candidate(self, goal)
 271         } else if lang_items.pointer_sized() == Some(trait_def_id) {
 272             G::consider_builtin_pointer_sized_candidate(self, goal)
 273         } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) {
 274             G::consider_builtin_fn_trait_candidates(self, goal, kind)
 275         } else if lang_items.tuple_trait() == Some(trait_def_id) {
 276             G::consider_builtin_tuple_candidate(self, goal)
 277         } else if lang_items.pointee_trait() == Some(trait_def_id) {
 278             G::consider_builtin_pointee_candidate(self, goal)
 279         } else if lang_items.future_trait() == Some(trait_def_id) {
 280             G::consider_builtin_future_candidate(self, goal)
 281         } else if lang_items.gen_trait() == Some(trait_def_id) {
 282             G::consider_builtin_generator_candidate(self, goal)
 283         } else {
 284             Err(NoSolution)
 285         };
 286
 287         match result {
 288             Ok(result) => {
 289                 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 290             }
 291             Err(NoSolution) => (),
 292         }
 293     }
 294
 295     fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
 296         &mut self,
 297         goal: Goal<'tcx, G>,
 298         candidates: &mut Vec<Candidate<'tcx>>,
 299     ) {
 300         for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
 301             match G::consider_assumption(self, goal, assumption) {
 302                 Ok(result) => {
 303                     candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
 304                 }
 305                 Err(NoSolution) => (),
 306             }
 307         }
 308     }
 309
 310     fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
 311         &mut self,
 312         goal: Goal<'tcx, G>,
 313         candidates: &mut Vec<Candidate<'tcx>>,
 314     ) {
 315         let alias_ty = match goal.predicate.self_ty().kind() {
 316             ty::Bool
 317             | ty::Char
 318             | ty::Int(_)
 319             | ty::Uint(_)
 320             | ty::Float(_)
 321             | ty::Adt(_, _)
 322             | ty::Foreign(_)
 323             | ty::Str
 324             | ty::Array(_, _)
 325             | ty::Slice(_)
 326             | ty::RawPtr(_)
 327             | ty::Ref(_, _, _)
 328             | ty::FnDef(_, _)
 329             | ty::FnPtr(_)
 330             | ty::Dynamic(..)
 331             | ty::Closure(..)
 332             | ty::Generator(..)
 333             | ty::GeneratorWitness(_)
 334             | ty::Never
 335             | ty::Tuple(_)
 336             | ty::Param(_)
 337             | ty::Placeholder(..)
 338             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 339             | ty::Error(_) => return,
 340             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
 341             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
 342             ty::Alias(_, alias_ty) => alias_ty,
 343         };
 344
 345         for (i, (assumption, _)) in self
 346             .tcx()
 347             .bound_explicit_item_bounds(alias_ty.def_id)
 348             .subst_iter_copied(self.tcx(), alias_ty.substs)
 349             .enumerate()
 350         {
 351             match G::consider_assumption(self, goal, assumption) {
 352                 Ok(result) => {
 353                     candidates.push(Candidate { source: CandidateSource::AliasBound(i), result })
 354                 }
 355                 Err(NoSolution) => (),
 356             }
 357         }
 358     }
 359
 360     fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
 361         &mut self,
 362         goal: Goal<'tcx, G>,
 363         candidates: &mut Vec<Candidate<'tcx>>,
 364     ) {
 365         let self_ty = goal.predicate.self_ty();
 366         let bounds = match *self_ty.kind() {
 367             ty::Bool
 368             | ty::Char
 369             | ty::Int(_)
 370             | ty::Uint(_)
 371             | ty::Float(_)
 372             | ty::Adt(_, _)
 373             | ty::Foreign(_)
 374             | ty::Str
 375             | ty::Array(_, _)
 376             | ty::Slice(_)
 377             | ty::RawPtr(_)
 378             | ty::Ref(_, _, _)
 379             | ty::FnDef(_, _)
 380             | ty::FnPtr(_)
 381             | ty::Alias(..)
 382             | ty::Closure(..)
 383             | ty::Generator(..)
 384             | ty::GeneratorWitness(_)
 385             | ty::Never
 386             | ty::Tuple(_)
 387             | ty::Param(_)
 388             | ty::Placeholder(..)
 389             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 390             | ty::Error(_) => return,
 391             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
 392             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
 393             ty::Dynamic(bounds, ..) => bounds,
 394         };
 395
 396         let tcx = self.tcx();
 397         for assumption in
 398             elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
 399         {
 400             match G::consider_assumption(self, goal, assumption.predicate) {
 401                 Ok(result) => {
 402                     candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 403                 }
 404                 Err(NoSolution) => (),
 405             }
 406         }
 407     }
 408 }