1 //! Code shared by trait and projection goals for candidate assembly.
3 use super::infcx_ext::InferCtxtExt;
4 use super::{CanonicalResponse, EvalCtxt, Goal, 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 {
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>;
122 impl<'tcx> EvalCtxt<'_, 'tcx> {
123 pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
126 ) -> Vec<Candidate<'tcx>> {
127 let mut candidates = Vec::new();
129 self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
131 self.assemble_impl_candidates(goal, &mut candidates);
133 self.assemble_builtin_impl_candidates(goal, &mut candidates);
135 self.assemble_param_env_candidates(goal, &mut candidates);
137 self.assemble_alias_bound_candidates(goal, &mut candidates);
139 self.assemble_object_bound_candidates(goal, &mut candidates);
144 /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
146 /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
147 /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
148 /// this case as projections as self types add `
149 fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
152 candidates: &mut Vec<Candidate<'tcx>>,
154 let tcx = self.tcx();
155 // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
156 let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
159 self.infcx.probe(|_| {
160 let normalized_ty = self.infcx.next_ty_infer();
161 let normalizes_to_goal = goal.with(
163 ty::Binder::dummy(ty::ProjectionPredicate {
165 term: normalized_ty.into(),
168 let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
169 Ok((_, certainty)) => certainty,
170 Err(NoSolution) => return,
173 // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
174 // This doesn't work as long as we use `CandidateSource` in winnowing.
175 let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
176 // FIXME: This is broken if we care about the `usize` of `AliasBound` because the self type
177 // could be normalized to yet another projection with different item bounds.
178 let normalized_candidates = self.assemble_and_evaluate_candidates(goal);
179 for mut normalized_candidate in normalized_candidates {
180 normalized_candidate.result =
181 normalized_candidate.result.unchecked_map(|mut response| {
182 // FIXME: This currently hides overflow in the normalization step of the self type
183 // which is probably wrong. Maybe `unify_and` should actually keep overflow as
184 // we treat it as non-fatal anyways.
185 response.certainty = response.certainty.unify_and(normalization_certainty);
188 candidates.push(normalized_candidate);
193 fn assemble_impl_candidates<G: GoalKind<'tcx>>(
196 candidates: &mut Vec<Candidate<'tcx>>,
198 let tcx = self.tcx();
199 tcx.for_each_relevant_impl(
200 goal.predicate.trait_def_id(tcx),
201 goal.predicate.self_ty(),
202 |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
203 Ok(result) => candidates
204 .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
205 Err(NoSolution) => (),
210 fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
213 candidates: &mut Vec<Candidate<'tcx>>,
215 let lang_items = self.tcx().lang_items();
216 let trait_def_id = goal.predicate.trait_def_id(self.tcx());
217 let result = if self.tcx().trait_is_auto(trait_def_id) {
218 G::consider_auto_trait_candidate(self, goal)
219 } else if self.tcx().trait_is_alias(trait_def_id) {
220 G::consider_trait_alias_candidate(self, goal)
221 } else if lang_items.sized_trait() == Some(trait_def_id) {
222 G::consider_builtin_sized_candidate(self, goal)
223 } else if lang_items.copy_trait() == Some(trait_def_id)
224 || lang_items.clone_trait() == Some(trait_def_id)
226 G::consider_builtin_copy_clone_candidate(self, goal)
233 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
235 Err(NoSolution) => (),
239 fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
242 candidates: &mut Vec<Candidate<'tcx>>,
244 for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
245 match G::consider_assumption(self, goal, assumption) {
247 candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
249 Err(NoSolution) => (),
254 fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
257 candidates: &mut Vec<Candidate<'tcx>>,
259 let alias_ty = match goal.predicate.self_ty().kind() {
277 | ty::GeneratorWitness(_)
281 | ty::Placeholder(..)
283 | ty::Error(_) => return,
284 ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
285 ty::Alias(_, alias_ty) => alias_ty,
288 for (i, (assumption, _)) in self
290 .bound_explicit_item_bounds(alias_ty.def_id)
291 .subst_iter_copied(self.tcx(), alias_ty.substs)
294 match G::consider_assumption(self, goal, assumption) {
296 candidates.push(Candidate { source: CandidateSource::AliasBound(i), result })
298 Err(NoSolution) => (),
303 fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
306 candidates: &mut Vec<Candidate<'tcx>>,
308 let self_ty = goal.predicate.self_ty();
309 let bounds = match *self_ty.kind() {
327 | ty::GeneratorWitness(_)
331 | ty::Placeholder(..)
333 | ty::Error(_) => return,
334 ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
335 ty::Dynamic(bounds, ..) => bounds,
338 let tcx = self.tcx();
340 elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
342 match G::consider_assumption(self, goal, assumption.predicate) {
344 candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
346 Err(NoSolution) => (),