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 #[cfg(doc)]
   5 use super::trait_goals::structural_traits::*;
   6 use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, QueryResult};
   7 use rustc_hir::def_id::DefId;
   8 use rustc_infer::traits::query::NoSolution;
   9 use rustc_infer::traits::util::elaborate_predicates;
  10 use rustc_middle::ty::TypeFoldable;
  11 use rustc_middle::ty::{self, Ty, TyCtxt};
  12 use std::fmt::Debug;
  13
  14 /// A candidate is a possible way to prove a goal.
  15 ///
  16 /// It consists of both the `source`, which describes how that goal would be proven,
  17 /// and the `result` when using the given `source`.
  18 #[derive(Debug, Clone)]
  19 pub(super) struct Candidate<'tcx> {
  20     pub(super) source: CandidateSource,
  21     pub(super) result: CanonicalResponse<'tcx>,
  22 }
  23
  24 /// Possible ways the given goal can be proven.
  25 #[derive(Debug, Clone, Copy)]
  26 pub(super) enum CandidateSource {
  27     /// A user written impl.
  28     ///
  29     /// ## Examples
  30     ///
  31     /// ```rust
  32     /// fn main() {
  33     ///     let x: Vec<u32> = Vec::new();
  34     ///     // This uses the impl from the standard library to prove `Vec<T>: Clone`.
  35     ///     let y = x.clone();
  36     /// }
  37     /// ```
  38     Impl(DefId),
  39     /// A builtin impl generated by the compiler. When adding a new special
  40     /// trait, try to use actual impls whenever possible. Builtin impls should
  41     /// only be used in cases where the impl cannot be manually be written.
  42     ///
  43     /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`.
  44     /// For a list of all traits with builtin impls, check out the
  45     /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not
  46     BuiltinImpl,
  47     /// An assumption from the environment.
  48     ///
  49     /// More precicely we've used the `n-th` assumption in the `param_env`.
  50     ///
  51     /// ## Examples
  52     ///
  53     /// ```rust
  54     /// fn is_clone<T: Clone>(x: T) -> (T, T) {
  55     ///     // This uses the assumption `T: Clone` from the `where`-bounds
  56     ///     // to prove `T: Clone`.
  57     ///     (x.clone(), x)
  58     /// }
  59     /// ```
  60     ParamEnv(usize),
  61     /// If the self type is an alias type, e.g. an opaque type or a projection,
  62     /// we know the bounds on that alias to hold even without knowing its concrete
  63     /// underlying type.
  64     ///
  65     /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
  66     /// the self type.
  67     ///
  68     /// ## Examples
  69     ///
  70     /// ```rust
  71     /// trait Trait {
  72     ///     type Assoc: Clone;
  73     /// }
  74     ///
  75     /// fn foo<T: Trait>(x: <T as Trait>::Assoc) {
  76     ///     // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in
  77     ///     // in the trait definition.
  78     ///     let _y = x.clone();
  79     /// }
  80     /// ```
  81     AliasBound,
  82 }
  83
  84 pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy + Eq {
  85     fn self_ty(self) -> Ty<'tcx>;
  86
  87     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
  88
  89     fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
  90
  91     fn consider_impl_candidate(
  92         ecx: &mut EvalCtxt<'_, 'tcx>,
  93         goal: Goal<'tcx, Self>,
  94         impl_def_id: DefId,
  95     ) -> QueryResult<'tcx>;
  96
  97     fn consider_assumption(
  98         ecx: &mut EvalCtxt<'_, 'tcx>,
  99         goal: Goal<'tcx, Self>,
 100         assumption: ty::Predicate<'tcx>,
 101     ) -> QueryResult<'tcx>;
 102
 103     // A type implements an `auto trait` if its components do as well. These components
 104     // are given by built-in rules from [`instantiate_constituent_tys_for_auto_trait`].
 105     fn consider_auto_trait_candidate(
 106         ecx: &mut EvalCtxt<'_, 'tcx>,
 107         goal: Goal<'tcx, Self>,
 108     ) -> QueryResult<'tcx>;
 109
 110     // A trait alias holds if the RHS traits and `where` clauses hold.
 111     fn consider_trait_alias_candidate(
 112         ecx: &mut EvalCtxt<'_, 'tcx>,
 113         goal: Goal<'tcx, Self>,
 114     ) -> QueryResult<'tcx>;
 115
 116     // A type is `Copy` or `Clone` if its components are `Sized`. These components
 117     // are given by built-in rules from [`instantiate_constituent_tys_for_sized_trait`].
 118     fn consider_builtin_sized_candidate(
 119         ecx: &mut EvalCtxt<'_, 'tcx>,
 120         goal: Goal<'tcx, Self>,
 121     ) -> QueryResult<'tcx>;
 122
 123     // A type is `Copy` or `Clone` if its components are `Copy` or `Clone`. These
 124     // components are given by built-in rules from [`instantiate_constituent_tys_for_copy_clone_trait`].
 125     fn consider_builtin_copy_clone_candidate(
 126         ecx: &mut EvalCtxt<'_, 'tcx>,
 127         goal: Goal<'tcx, Self>,
 128     ) -> QueryResult<'tcx>;
 129
 130     // A type is `PointerSized` if we can compute its layout, and that layout
 131     // matches the layout of `usize`.
 132     fn consider_builtin_pointer_sized_candidate(
 133         ecx: &mut EvalCtxt<'_, 'tcx>,
 134         goal: Goal<'tcx, Self>,
 135     ) -> QueryResult<'tcx>;
 136
 137     // A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
 138     // family of traits where `A` is given by the signature of the type.
 139     fn consider_builtin_fn_trait_candidates(
 140         ecx: &mut EvalCtxt<'_, 'tcx>,
 141         goal: Goal<'tcx, Self>,
 142         kind: ty::ClosureKind,
 143     ) -> QueryResult<'tcx>;
 144
 145     // `Tuple` is implemented if the `Self` type is a tuple.
 146     fn consider_builtin_tuple_candidate(
 147         ecx: &mut EvalCtxt<'_, 'tcx>,
 148         goal: Goal<'tcx, Self>,
 149     ) -> QueryResult<'tcx>;
 150
 151     // `Pointee` is always implemented.
 152     //
 153     // See the projection implementation for the `Metadata` types for all of
 154     // the built-in types. For structs, the metadata type is given by the struct
 155     // tail.
 156     fn consider_builtin_pointee_candidate(
 157         ecx: &mut EvalCtxt<'_, 'tcx>,
 158         goal: Goal<'tcx, Self>,
 159     ) -> QueryResult<'tcx>;
 160
 161     // A generator (that comes from an `async` desugaring) is known to implement
 162     // `Future<Output = O>`, where `O` is given by the generator's return type
 163     // that was computed during type-checking.
 164     fn consider_builtin_future_candidate(
 165         ecx: &mut EvalCtxt<'_, 'tcx>,
 166         goal: Goal<'tcx, Self>,
 167     ) -> QueryResult<'tcx>;
 168
 169     // A generator (that doesn't come from an `async` desugaring) is known to
 170     // implement `Generator<R, Yield = Y, Return = O>`, given the resume, yield,
 171     // and return types of the generator computed during type-checking.
 172     fn consider_builtin_generator_candidate(
 173         ecx: &mut EvalCtxt<'_, 'tcx>,
 174         goal: Goal<'tcx, Self>,
 175     ) -> QueryResult<'tcx>;
 176 }
 177
 178 impl<'tcx> EvalCtxt<'_, 'tcx> {
 179     pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
 180         &mut self,
 181         goal: Goal<'tcx, G>,
 182     ) -> Vec<Candidate<'tcx>> {
 183         debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal));
 184
 185         // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule,
 186         // object bound, alias bound, etc. We are unable to determine this until we can at
 187         // least structually resolve the type one layer.
 188         if goal.predicate.self_ty().is_ty_var() {
 189             return vec![Candidate {
 190                 source: CandidateSource::BuiltinImpl,
 191                 result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(),
 192             }];
 193         }
 194
 195         let mut candidates = Vec::new();
 196
 197         self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
 198
 199         self.assemble_impl_candidates(goal, &mut candidates);
 200
 201         self.assemble_builtin_impl_candidates(goal, &mut candidates);
 202
 203         self.assemble_param_env_candidates(goal, &mut candidates);
 204
 205         self.assemble_alias_bound_candidates(goal, &mut candidates);
 206
 207         self.assemble_object_bound_candidates(goal, &mut candidates);
 208
 209         candidates
 210     }
 211
 212     /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
 213     ///
 214     /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
 215     /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
 216     /// this case as projections as self types add `
 217     fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
 218         &mut self,
 219         goal: Goal<'tcx, G>,
 220         candidates: &mut Vec<Candidate<'tcx>>,
 221     ) {
 222         let tcx = self.tcx();
 223         // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
 224         let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
 225             return
 226         };
 227         self.infcx.probe(|_| {
 228             let normalized_ty = self.infcx.next_ty_infer();
 229             let normalizes_to_goal = goal.with(
 230                 tcx,
 231                 ty::Binder::dummy(ty::ProjectionPredicate {
 232                     projection_ty,
 233                     term: normalized_ty.into(),
 234                 }),
 235             );
 236             let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
 237                 Ok((_, certainty)) => certainty,
 238                 Err(NoSolution) => return,
 239             };
 240             let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty);
 241
 242             // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
 243             // This doesn't work as long as we use `CandidateSource` in winnowing.
 244             let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
 245             let normalized_candidates = self.assemble_and_evaluate_candidates(goal);
 246             for mut normalized_candidate in normalized_candidates {
 247                 normalized_candidate.result =
 248                     normalized_candidate.result.unchecked_map(|mut response| {
 249                         // FIXME: This currently hides overflow in the normalization step of the self type
 250                         // which is probably wrong. Maybe `unify_and` should actually keep overflow as
 251                         // we treat it as non-fatal anyways.
 252                         response.certainty = response.certainty.unify_and(normalization_certainty);
 253                         response
 254                     });
 255                 candidates.push(normalized_candidate);
 256             }
 257         })
 258     }
 259
 260     fn assemble_impl_candidates<G: GoalKind<'tcx>>(
 261         &mut self,
 262         goal: Goal<'tcx, G>,
 263         candidates: &mut Vec<Candidate<'tcx>>,
 264     ) {
 265         let tcx = self.tcx();
 266         tcx.for_each_relevant_impl(
 267             goal.predicate.trait_def_id(tcx),
 268             goal.predicate.self_ty(),
 269             |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
 270                 Ok(result) => candidates
 271                     .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
 272                 Err(NoSolution) => (),
 273             },
 274         );
 275     }
 276
 277     fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
 278         &mut self,
 279         goal: Goal<'tcx, G>,
 280         candidates: &mut Vec<Candidate<'tcx>>,
 281     ) {
 282         let lang_items = self.tcx().lang_items();
 283         let trait_def_id = goal.predicate.trait_def_id(self.tcx());
 284         let result = if self.tcx().trait_is_auto(trait_def_id) {
 285             G::consider_auto_trait_candidate(self, goal)
 286         } else if self.tcx().trait_is_alias(trait_def_id) {
 287             G::consider_trait_alias_candidate(self, goal)
 288         } else if lang_items.sized_trait() == Some(trait_def_id) {
 289             G::consider_builtin_sized_candidate(self, goal)
 290         } else if lang_items.copy_trait() == Some(trait_def_id)
 291             || lang_items.clone_trait() == Some(trait_def_id)
 292         {
 293             G::consider_builtin_copy_clone_candidate(self, goal)
 294         } else if lang_items.pointer_sized() == Some(trait_def_id) {
 295             G::consider_builtin_pointer_sized_candidate(self, goal)
 296         } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) {
 297             G::consider_builtin_fn_trait_candidates(self, goal, kind)
 298         } else if lang_items.tuple_trait() == Some(trait_def_id) {
 299             G::consider_builtin_tuple_candidate(self, goal)
 300         } else if lang_items.pointee_trait() == Some(trait_def_id) {
 301             G::consider_builtin_pointee_candidate(self, goal)
 302         } else if lang_items.future_trait() == Some(trait_def_id) {
 303             G::consider_builtin_future_candidate(self, goal)
 304         } else if lang_items.gen_trait() == Some(trait_def_id) {
 305             G::consider_builtin_generator_candidate(self, goal)
 306         } else {
 307             Err(NoSolution)
 308         };
 309
 310         match result {
 311             Ok(result) => {
 312                 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 313             }
 314             Err(NoSolution) => (),
 315         }
 316     }
 317
 318     fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
 319         &mut self,
 320         goal: Goal<'tcx, G>,
 321         candidates: &mut Vec<Candidate<'tcx>>,
 322     ) {
 323         for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
 324             match G::consider_assumption(self, goal, assumption) {
 325                 Ok(result) => {
 326                     candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
 327                 }
 328                 Err(NoSolution) => (),
 329             }
 330         }
 331     }
 332
 333     fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
 334         &mut self,
 335         goal: Goal<'tcx, G>,
 336         candidates: &mut Vec<Candidate<'tcx>>,
 337     ) {
 338         let alias_ty = match goal.predicate.self_ty().kind() {
 339             ty::Bool
 340             | ty::Char
 341             | ty::Int(_)
 342             | ty::Uint(_)
 343             | ty::Float(_)
 344             | ty::Adt(_, _)
 345             | ty::Foreign(_)
 346             | ty::Str
 347             | ty::Array(_, _)
 348             | ty::Slice(_)
 349             | ty::RawPtr(_)
 350             | ty::Ref(_, _, _)
 351             | ty::FnDef(_, _)
 352             | ty::FnPtr(_)
 353             | ty::Dynamic(..)
 354             | ty::Closure(..)
 355             | ty::Generator(..)
 356             | ty::GeneratorWitness(_)
 357             | ty::GeneratorWitnessMIR(..)
 358             | ty::Never
 359             | ty::Tuple(_)
 360             | ty::Param(_)
 361             | ty::Placeholder(..)
 362             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 363             | ty::Error(_) => return,
 364             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
 365             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
 366             ty::Alias(_, alias_ty) => alias_ty,
 367         };
 368
 369         for (assumption, _) in self
 370             .tcx()
 371             .bound_explicit_item_bounds(alias_ty.def_id)
 372             .subst_iter_copied(self.tcx(), alias_ty.substs)
 373         {
 374             match G::consider_assumption(self, goal, assumption) {
 375                 Ok(result) => {
 376                     candidates.push(Candidate { source: CandidateSource::AliasBound, result })
 377                 }
 378                 Err(NoSolution) => (),
 379             }
 380         }
 381     }
 382
 383     fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
 384         &mut self,
 385         goal: Goal<'tcx, G>,
 386         candidates: &mut Vec<Candidate<'tcx>>,
 387     ) {
 388         let self_ty = goal.predicate.self_ty();
 389         let bounds = match *self_ty.kind() {
 390             ty::Bool
 391             | ty::Char
 392             | ty::Int(_)
 393             | ty::Uint(_)
 394             | ty::Float(_)
 395             | ty::Adt(_, _)
 396             | ty::Foreign(_)
 397             | ty::Str
 398             | ty::Array(_, _)
 399             | ty::Slice(_)
 400             | ty::RawPtr(_)
 401             | ty::Ref(_, _, _)
 402             | ty::FnDef(_, _)
 403             | ty::FnPtr(_)
 404             | ty::Alias(..)
 405             | ty::Closure(..)
 406             | ty::Generator(..)
 407             | ty::GeneratorWitness(_)
 408             | ty::GeneratorWitnessMIR(..)
 409             | ty::Never
 410             | ty::Tuple(_)
 411             | ty::Param(_)
 412             | ty::Placeholder(..)
 413             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 414             | ty::Error(_) => return,
 415             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
 416             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
 417             ty::Dynamic(bounds, ..) => bounds,
 418         };
 419
 420         let tcx = self.tcx();
 421         for assumption in
 422             elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
 423         {
 424             match G::consider_assumption(self, goal, assumption.predicate) {
 425                 Ok(result) => {
 426                     candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 427                 }
 428                 Err(NoSolution) => (),
 429             }
 430         }
 431     }
 432 }