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 /// Methods used to assemble candidates for either trait or projection goals.
  85 pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy + Eq {
  86     fn self_ty(self) -> Ty<'tcx>;
  87
  88     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
  89
  90     fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
  91
  92     fn consider_impl_candidate(
  93         ecx: &mut EvalCtxt<'_, 'tcx>,
  94         goal: Goal<'tcx, Self>,
  95         impl_def_id: DefId,
  96     ) -> QueryResult<'tcx>;
  97
  98     fn consider_assumption(
  99         ecx: &mut EvalCtxt<'_, 'tcx>,
 100         goal: Goal<'tcx, Self>,
 101         assumption: ty::Predicate<'tcx>,
 102     ) -> QueryResult<'tcx>;
 103
 104     // A type implements an `auto trait` if its components do as well. These components
 105     // are given by built-in rules from [`instantiate_constituent_tys_for_auto_trait`].
 106     fn consider_auto_trait_candidate(
 107         ecx: &mut EvalCtxt<'_, 'tcx>,
 108         goal: Goal<'tcx, Self>,
 109     ) -> QueryResult<'tcx>;
 110
 111     // A trait alias holds if the RHS traits and `where` clauses hold.
 112     fn consider_trait_alias_candidate(
 113         ecx: &mut EvalCtxt<'_, 'tcx>,
 114         goal: Goal<'tcx, Self>,
 115     ) -> QueryResult<'tcx>;
 116
 117     // A type is `Copy` or `Clone` if its components are `Sized`. These components
 118     // are given by built-in rules from [`instantiate_constituent_tys_for_sized_trait`].
 119     fn consider_builtin_sized_candidate(
 120         ecx: &mut EvalCtxt<'_, 'tcx>,
 121         goal: Goal<'tcx, Self>,
 122     ) -> QueryResult<'tcx>;
 123
 124     // A type is `Copy` or `Clone` if its components are `Copy` or `Clone`. These
 125     // components are given by built-in rules from [`instantiate_constituent_tys_for_copy_clone_trait`].
 126     fn consider_builtin_copy_clone_candidate(
 127         ecx: &mut EvalCtxt<'_, 'tcx>,
 128         goal: Goal<'tcx, Self>,
 129     ) -> QueryResult<'tcx>;
 130
 131     // A type is `PointerSized` if we can compute its layout, and that layout
 132     // matches the layout of `usize`.
 133     fn consider_builtin_pointer_sized_candidate(
 134         ecx: &mut EvalCtxt<'_, 'tcx>,
 135         goal: Goal<'tcx, Self>,
 136     ) -> QueryResult<'tcx>;
 137
 138     // A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
 139     // family of traits where `A` is given by the signature of the type.
 140     fn consider_builtin_fn_trait_candidates(
 141         ecx: &mut EvalCtxt<'_, 'tcx>,
 142         goal: Goal<'tcx, Self>,
 143         kind: ty::ClosureKind,
 144     ) -> QueryResult<'tcx>;
 145
 146     // `Tuple` is implemented if the `Self` type is a tuple.
 147     fn consider_builtin_tuple_candidate(
 148         ecx: &mut EvalCtxt<'_, 'tcx>,
 149         goal: Goal<'tcx, Self>,
 150     ) -> QueryResult<'tcx>;
 151
 152     // `Pointee` is always implemented.
 153     //
 154     // See the projection implementation for the `Metadata` types for all of
 155     // the built-in types. For structs, the metadata type is given by the struct
 156     // tail.
 157     fn consider_builtin_pointee_candidate(
 158         ecx: &mut EvalCtxt<'_, 'tcx>,
 159         goal: Goal<'tcx, Self>,
 160     ) -> QueryResult<'tcx>;
 161
 162     // A generator (that comes from an `async` desugaring) is known to implement
 163     // `Future<Output = O>`, where `O` is given by the generator's return type
 164     // that was computed during type-checking.
 165     fn consider_builtin_future_candidate(
 166         ecx: &mut EvalCtxt<'_, 'tcx>,
 167         goal: Goal<'tcx, Self>,
 168     ) -> QueryResult<'tcx>;
 169
 170     // A generator (that doesn't come from an `async` desugaring) is known to
 171     // implement `Generator<R, Yield = Y, Return = O>`, given the resume, yield,
 172     // and return types of the generator computed during type-checking.
 173     fn consider_builtin_generator_candidate(
 174         ecx: &mut EvalCtxt<'_, 'tcx>,
 175         goal: Goal<'tcx, Self>,
 176     ) -> QueryResult<'tcx>;
 177
 178     // The most common forms of unsizing are array to slice, and concrete (Sized)
 179     // type into a `dyn Trait`. ADTs and Tuples can also have their final field
 180     // unsized if it's generic.
 181     fn consider_builtin_unsize_candidate(
 182         ecx: &mut EvalCtxt<'_, 'tcx>,
 183         goal: Goal<'tcx, Self>,
 184     ) -> QueryResult<'tcx>;
 185
 186     // `dyn Trait1` can be unsized to `dyn Trait2` if they are the same trait, or
 187     // if `Trait2` is a (transitive) supertrait of `Trait2`.
 188     fn consider_builtin_dyn_upcast_candidates(
 189         ecx: &mut EvalCtxt<'_, 'tcx>,
 190         goal: Goal<'tcx, Self>,
 191     ) -> Vec<CanonicalResponse<'tcx>>;
 192
 193     fn consider_builtin_discriminant_kind_candidate(
 194         ecx: &mut EvalCtxt<'_, 'tcx>,
 195         goal: Goal<'tcx, Self>,
 196     ) -> QueryResult<'tcx>;
 197 }
 198
 199 impl<'tcx> EvalCtxt<'_, 'tcx> {
 200     pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
 201         &mut self,
 202         goal: Goal<'tcx, G>,
 203     ) -> Vec<Candidate<'tcx>> {
 204         debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal));
 205
 206         // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule,
 207         // object bound, alias bound, etc. We are unable to determine this until we can at
 208         // least structually resolve the type one layer.
 209         if goal.predicate.self_ty().is_ty_var() {
 210             return vec![Candidate {
 211                 source: CandidateSource::BuiltinImpl,
 212                 result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(),
 213             }];
 214         }
 215
 216         let mut candidates = Vec::new();
 217
 218         self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
 219
 220         self.assemble_impl_candidates(goal, &mut candidates);
 221
 222         self.assemble_builtin_impl_candidates(goal, &mut candidates);
 223
 224         self.assemble_param_env_candidates(goal, &mut candidates);
 225
 226         self.assemble_alias_bound_candidates(goal, &mut candidates);
 227
 228         self.assemble_object_bound_candidates(goal, &mut candidates);
 229
 230         candidates
 231     }
 232
 233     /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
 234     ///
 235     /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
 236     /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
 237     /// this case as projections as self types add `
 238     fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
 239         &mut self,
 240         goal: Goal<'tcx, G>,
 241         candidates: &mut Vec<Candidate<'tcx>>,
 242     ) {
 243         let tcx = self.tcx();
 244         // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
 245         let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
 246             return
 247         };
 248         self.infcx.probe(|_| {
 249             let normalized_ty = self.infcx.next_ty_infer();
 250             let normalizes_to_goal = goal.with(
 251                 tcx,
 252                 ty::Binder::dummy(ty::ProjectionPredicate {
 253                     projection_ty,
 254                     term: normalized_ty.into(),
 255                 }),
 256             );
 257             let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
 258                 Ok((_, certainty)) => certainty,
 259                 Err(NoSolution) => return,
 260             };
 261             let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty);
 262
 263             // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
 264             // This doesn't work as long as we use `CandidateSource` in winnowing.
 265             let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
 266             let normalized_candidates = self.assemble_and_evaluate_candidates(goal);
 267             for mut normalized_candidate in normalized_candidates {
 268                 normalized_candidate.result =
 269                     normalized_candidate.result.unchecked_map(|mut response| {
 270                         // FIXME: This currently hides overflow in the normalization step of the self type
 271                         // which is probably wrong. Maybe `unify_and` should actually keep overflow as
 272                         // we treat it as non-fatal anyways.
 273                         response.certainty = response.certainty.unify_and(normalization_certainty);
 274                         response
 275                     });
 276                 candidates.push(normalized_candidate);
 277             }
 278         })
 279     }
 280
 281     fn assemble_impl_candidates<G: GoalKind<'tcx>>(
 282         &mut self,
 283         goal: Goal<'tcx, G>,
 284         candidates: &mut Vec<Candidate<'tcx>>,
 285     ) {
 286         let tcx = self.tcx();
 287         tcx.for_each_relevant_impl(
 288             goal.predicate.trait_def_id(tcx),
 289             goal.predicate.self_ty(),
 290             |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
 291                 Ok(result) => candidates
 292                     .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
 293                 Err(NoSolution) => (),
 294             },
 295         );
 296     }
 297
 298     fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
 299         &mut self,
 300         goal: Goal<'tcx, G>,
 301         candidates: &mut Vec<Candidate<'tcx>>,
 302     ) {
 303         let lang_items = self.tcx().lang_items();
 304         let trait_def_id = goal.predicate.trait_def_id(self.tcx());
 305         let result = if self.tcx().trait_is_auto(trait_def_id) {
 306             G::consider_auto_trait_candidate(self, goal)
 307         } else if self.tcx().trait_is_alias(trait_def_id) {
 308             G::consider_trait_alias_candidate(self, goal)
 309         } else if lang_items.sized_trait() == Some(trait_def_id) {
 310             G::consider_builtin_sized_candidate(self, goal)
 311         } else if lang_items.copy_trait() == Some(trait_def_id)
 312             || lang_items.clone_trait() == Some(trait_def_id)
 313         {
 314             G::consider_builtin_copy_clone_candidate(self, goal)
 315         } else if lang_items.pointer_sized() == Some(trait_def_id) {
 316             G::consider_builtin_pointer_sized_candidate(self, goal)
 317         } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) {
 318             G::consider_builtin_fn_trait_candidates(self, goal, kind)
 319         } else if lang_items.tuple_trait() == Some(trait_def_id) {
 320             G::consider_builtin_tuple_candidate(self, goal)
 321         } else if lang_items.pointee_trait() == Some(trait_def_id) {
 322             G::consider_builtin_pointee_candidate(self, goal)
 323         } else if lang_items.future_trait() == Some(trait_def_id) {
 324             G::consider_builtin_future_candidate(self, goal)
 325         } else if lang_items.gen_trait() == Some(trait_def_id) {
 326             G::consider_builtin_generator_candidate(self, goal)
 327         } else if lang_items.unsize_trait() == Some(trait_def_id) {
 328             G::consider_builtin_unsize_candidate(self, goal)
 329         } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) {
 330             G::consider_builtin_discriminant_kind_candidate(self, goal)
 331         } else {
 332             Err(NoSolution)
 333         };
 334
 335         match result {
 336             Ok(result) => {
 337                 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 338             }
 339             Err(NoSolution) => (),
 340         }
 341
 342         // There may be multiple unsize candidates for a trait with several supertraits:
 343         // `trait Foo: Bar<A> + Bar<B>` and `dyn Foo: Unsize<dyn Bar<_>>`
 344         if lang_items.unsize_trait() == Some(trait_def_id) {
 345             for result in G::consider_builtin_dyn_upcast_candidates(self, goal) {
 346                 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result });
 347             }
 348         }
 349     }
 350
 351     fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
 352         &mut self,
 353         goal: Goal<'tcx, G>,
 354         candidates: &mut Vec<Candidate<'tcx>>,
 355     ) {
 356         for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
 357             match G::consider_assumption(self, goal, assumption) {
 358                 Ok(result) => {
 359                     candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
 360                 }
 361                 Err(NoSolution) => (),
 362             }
 363         }
 364     }
 365
 366     fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
 367         &mut self,
 368         goal: Goal<'tcx, G>,
 369         candidates: &mut Vec<Candidate<'tcx>>,
 370     ) {
 371         let alias_ty = match goal.predicate.self_ty().kind() {
 372             ty::Bool
 373             | ty::Char
 374             | ty::Int(_)
 375             | ty::Uint(_)
 376             | ty::Float(_)
 377             | ty::Adt(_, _)
 378             | ty::Foreign(_)
 379             | ty::Str
 380             | ty::Array(_, _)
 381             | ty::Slice(_)
 382             | ty::RawPtr(_)
 383             | ty::Ref(_, _, _)
 384             | ty::FnDef(_, _)
 385             | ty::FnPtr(_)
 386             | ty::Dynamic(..)
 387             | ty::Closure(..)
 388             | ty::Generator(..)
 389             | ty::GeneratorWitness(_)
 390             | ty::GeneratorWitnessMIR(..)
 391             | ty::Never
 392             | ty::Tuple(_)
 393             | ty::Param(_)
 394             | ty::Placeholder(..)
 395             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 396             | ty::Error(_) => return,
 397             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
 398             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
 399             ty::Alias(_, alias_ty) => alias_ty,
 400         };
 401
 402         for (assumption, _) in self
 403             .tcx()
 404             .bound_explicit_item_bounds(alias_ty.def_id)
 405             .subst_iter_copied(self.tcx(), alias_ty.substs)
 406         {
 407             match G::consider_assumption(self, goal, assumption) {
 408                 Ok(result) => {
 409                     candidates.push(Candidate { source: CandidateSource::AliasBound, result })
 410                 }
 411                 Err(NoSolution) => (),
 412             }
 413         }
 414     }
 415
 416     fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
 417         &mut self,
 418         goal: Goal<'tcx, G>,
 419         candidates: &mut Vec<Candidate<'tcx>>,
 420     ) {
 421         let self_ty = goal.predicate.self_ty();
 422         let bounds = match *self_ty.kind() {
 423             ty::Bool
 424             | ty::Char
 425             | ty::Int(_)
 426             | ty::Uint(_)
 427             | ty::Float(_)
 428             | ty::Adt(_, _)
 429             | ty::Foreign(_)
 430             | ty::Str
 431             | ty::Array(_, _)
 432             | ty::Slice(_)
 433             | ty::RawPtr(_)
 434             | ty::Ref(_, _, _)
 435             | ty::FnDef(_, _)
 436             | ty::FnPtr(_)
 437             | ty::Alias(..)
 438             | ty::Closure(..)
 439             | ty::Generator(..)
 440             | ty::GeneratorWitness(_)
 441             | ty::GeneratorWitnessMIR(..)
 442             | ty::Never
 443             | ty::Tuple(_)
 444             | ty::Param(_)
 445             | ty::Placeholder(..)
 446             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 447             | ty::Error(_) => return,
 448             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
 449             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
 450             ty::Dynamic(bounds, ..) => bounds,
 451         };
 452
 453         let tcx = self.tcx();
 454         for assumption in
 455             elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
 456         {
 457             match G::consider_assumption(self, goal, assumption.predicate) {
 458                 Ok(result) => {
 459                     candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
 460                 }
 461                 Err(NoSolution) => (),
 462             }
 463         }
 464     }
 465 }