1 //! Code shared by trait and projection goals for candidate assembly.
3 use super::infcx_ext::InferCtxtExt;
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};
14 /// A candidate is a possible way to prove a goal.
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>,
24 /// Possible ways the given goal can be proven.
25 #[derive(Debug, Clone, Copy)]
26 pub(super) enum CandidateSource {
27 /// A user written impl.
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();
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.
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
47 /// An assumption from the environment.
49 /// More precicely we've used the `n-th` assumption in the `param_env`.
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`.
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
65 /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
72 /// type Assoc: Clone;
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();
84 pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy + Eq {
85 fn self_ty(self) -> Ty<'tcx>;
87 fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
89 fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
91 fn consider_impl_candidate(
92 ecx: &mut EvalCtxt<'_, 'tcx>,
93 goal: Goal<'tcx, Self>,
95 ) -> QueryResult<'tcx>;
97 fn consider_assumption(
98 ecx: &mut EvalCtxt<'_, 'tcx>,
99 goal: Goal<'tcx, Self>,
100 assumption: ty::Predicate<'tcx>,
101 ) -> QueryResult<'tcx>;
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>;
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>;
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>;
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>;
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>;
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>;
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>;
151 // `Pointee` is always implemented.
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
156 fn consider_builtin_pointee_candidate(
157 ecx: &mut EvalCtxt<'_, 'tcx>,
158 goal: Goal<'tcx, Self>,
159 ) -> QueryResult<'tcx>;
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>;
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>;
178 impl<'tcx> EvalCtxt<'_, 'tcx> {
179 pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
182 ) -> Vec<Candidate<'tcx>> {
183 debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal));
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(),
195 let mut candidates = Vec::new();
197 self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
199 self.assemble_impl_candidates(goal, &mut candidates);
201 self.assemble_builtin_impl_candidates(goal, &mut candidates);
203 self.assemble_param_env_candidates(goal, &mut candidates);
205 self.assemble_alias_bound_candidates(goal, &mut candidates);
207 self.assemble_object_bound_candidates(goal, &mut candidates);
212 /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
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>>(
220 candidates: &mut Vec<Candidate<'tcx>>,
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 {
227 self.infcx.probe(|_| {
228 let normalized_ty = self.infcx.next_ty_infer();
229 let normalizes_to_goal = goal.with(
231 ty::Binder::dummy(ty::ProjectionPredicate {
233 term: normalized_ty.into(),
236 let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
237 Ok((_, certainty)) => certainty,
238 Err(NoSolution) => return,
240 let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty);
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);
255 candidates.push(normalized_candidate);
260 fn assemble_impl_candidates<G: GoalKind<'tcx>>(
263 candidates: &mut Vec<Candidate<'tcx>>,
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) => (),
277 fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
280 candidates: &mut Vec<Candidate<'tcx>>,
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)
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)
312 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
314 Err(NoSolution) => (),
318 fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
321 candidates: &mut Vec<Candidate<'tcx>>,
323 for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
324 match G::consider_assumption(self, goal, assumption) {
326 candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
328 Err(NoSolution) => (),
333 fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
336 candidates: &mut Vec<Candidate<'tcx>>,
338 let alias_ty = match goal.predicate.self_ty().kind() {
356 | ty::GeneratorWitness(_)
357 | ty::GeneratorWitnessMIR(..)
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,
369 for (assumption, _) in self
371 .bound_explicit_item_bounds(alias_ty.def_id)
372 .subst_iter_copied(self.tcx(), alias_ty.substs)
374 match G::consider_assumption(self, goal, assumption) {
376 candidates.push(Candidate { source: CandidateSource::AliasBound, result })
378 Err(NoSolution) => (),
383 fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
386 candidates: &mut Vec<Candidate<'tcx>>,
388 let self_ty = goal.predicate.self_ty();
389 let bounds = match *self_ty.kind() {
407 | ty::GeneratorWitness(_)
408 | ty::GeneratorWitnessMIR(..)
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,
420 let tcx = self.tcx();
422 elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
424 match G::consider_assumption(self, goal, assumption.predicate) {
426 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
428 Err(NoSolution) => (),