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