1 //! Code shared by trait and projection goals for candidate assembly.
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};
12 /// A candidate is a possible way to prove a goal.
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>,
22 /// Possible ways the given goal can be proven.
23 #[derive(Debug, Clone, Copy)]
24 pub(super) enum CandidateSource {
25 /// A user written impl.
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();
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.
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
45 /// An assumption from the environment.
47 /// More precicely we've used the `n-th` assumption in the `param_env`.
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`.
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
63 /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
70 /// type Assoc: Clone;
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();
82 pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy + Eq {
83 fn self_ty(self) -> Ty<'tcx>;
85 fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
87 fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
89 fn consider_impl_candidate(
90 ecx: &mut EvalCtxt<'_, 'tcx>,
91 goal: Goal<'tcx, Self>,
93 ) -> QueryResult<'tcx>;
95 fn consider_assumption(
96 ecx: &mut EvalCtxt<'_, 'tcx>,
97 goal: Goal<'tcx, Self>,
98 assumption: ty::Predicate<'tcx>,
99 ) -> QueryResult<'tcx>;
101 fn consider_auto_trait_candidate(
102 ecx: &mut EvalCtxt<'_, 'tcx>,
103 goal: Goal<'tcx, Self>,
104 ) -> QueryResult<'tcx>;
106 fn consider_trait_alias_candidate(
107 ecx: &mut EvalCtxt<'_, 'tcx>,
108 goal: Goal<'tcx, Self>,
109 ) -> QueryResult<'tcx>;
111 fn consider_builtin_sized_candidate(
112 ecx: &mut EvalCtxt<'_, 'tcx>,
113 goal: Goal<'tcx, Self>,
114 ) -> QueryResult<'tcx>;
116 fn consider_builtin_copy_clone_candidate(
117 ecx: &mut EvalCtxt<'_, 'tcx>,
118 goal: Goal<'tcx, Self>,
119 ) -> QueryResult<'tcx>;
121 fn consider_builtin_pointer_sized_candidate(
122 ecx: &mut EvalCtxt<'_, 'tcx>,
123 goal: Goal<'tcx, Self>,
124 ) -> QueryResult<'tcx>;
126 fn consider_builtin_fn_trait_candidates(
127 ecx: &mut EvalCtxt<'_, 'tcx>,
128 goal: Goal<'tcx, Self>,
129 kind: ty::ClosureKind,
130 ) -> QueryResult<'tcx>;
132 fn consider_builtin_tuple_candidate(
133 ecx: &mut EvalCtxt<'_, 'tcx>,
134 goal: Goal<'tcx, Self>,
135 ) -> QueryResult<'tcx>;
138 impl<'tcx> EvalCtxt<'_, 'tcx> {
139 pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
142 ) -> Vec<Candidate<'tcx>> {
143 debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal));
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,
152 .make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity))
157 let mut candidates = Vec::new();
159 self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
161 self.assemble_impl_candidates(goal, &mut candidates);
163 self.assemble_builtin_impl_candidates(goal, &mut candidates);
165 self.assemble_param_env_candidates(goal, &mut candidates);
167 self.assemble_alias_bound_candidates(goal, &mut candidates);
169 self.assemble_object_bound_candidates(goal, &mut candidates);
174 /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
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>>(
182 candidates: &mut Vec<Candidate<'tcx>>,
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 {
189 self.infcx.probe(|_| {
190 let normalized_ty = self.infcx.next_ty_infer();
191 let normalizes_to_goal = goal.with(
193 ty::Binder::dummy(ty::ProjectionPredicate {
195 term: normalized_ty.into(),
198 let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
199 Ok((_, certainty)) => certainty,
200 Err(NoSolution) => return,
202 let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty);
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);
219 candidates.push(normalized_candidate);
224 fn assemble_impl_candidates<G: GoalKind<'tcx>>(
227 candidates: &mut Vec<Candidate<'tcx>>,
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) => (),
241 fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
244 candidates: &mut Vec<Candidate<'tcx>>,
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)
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)
270 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
272 Err(NoSolution) => (),
276 fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
279 candidates: &mut Vec<Candidate<'tcx>>,
281 for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
282 match G::consider_assumption(self, goal, assumption) {
284 candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
286 Err(NoSolution) => (),
291 fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
294 candidates: &mut Vec<Candidate<'tcx>>,
296 let alias_ty = match goal.predicate.self_ty().kind() {
314 | ty::GeneratorWitness(_)
318 | ty::Placeholder(..)
320 | ty::Error(_) => return,
321 ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
322 ty::Alias(_, alias_ty) => alias_ty,
325 for (i, (assumption, _)) in self
327 .bound_explicit_item_bounds(alias_ty.def_id)
328 .subst_iter_copied(self.tcx(), alias_ty.substs)
331 match G::consider_assumption(self, goal, assumption) {
333 candidates.push(Candidate { source: CandidateSource::AliasBound(i), result })
335 Err(NoSolution) => (),
340 fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
343 candidates: &mut Vec<Candidate<'tcx>>,
345 let self_ty = goal.predicate.self_ty();
346 let bounds = match *self_ty.kind() {
364 | ty::GeneratorWitness(_)
368 | ty::Placeholder(..)
370 | ty::Error(_) => return,
371 ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
372 ty::Dynamic(bounds, ..) => bounds,
375 let tcx = self.tcx();
377 elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
379 match G::consider_assumption(self, goal, assumption.predicate) {
381 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
383 Err(NoSolution) => (),