1 //! Dealing with trait goals, i.e. `T: Trait<'a, U>`.
5 use super::assembly::{self, Candidate, CandidateSource};
6 use super::infcx_ext::InferCtxtExt;
7 use super::{Certainty, EvalCtxt, Goal, QueryResult};
8 use rustc_hir::def_id::DefId;
9 use rustc_infer::infer::InferCtxt;
10 use rustc_infer::traits::query::NoSolution;
11 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
12 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
13 use rustc_middle::ty::{TraitPredicate, TypeVisitable};
14 use rustc_span::DUMMY_SP;
16 pub mod structural_traits;
18 impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
19 fn self_ty(self) -> Ty<'tcx> {
23 fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
24 self.with_self_ty(tcx, self_ty)
27 fn trait_def_id(self, _: TyCtxt<'tcx>) -> DefId {
31 fn consider_impl_candidate(
32 ecx: &mut EvalCtxt<'_, 'tcx>,
33 goal: Goal<'tcx, TraitPredicate<'tcx>>,
35 ) -> QueryResult<'tcx> {
38 let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
39 let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
40 if iter::zip(goal.predicate.trait_ref.substs, impl_trait_ref.skip_binder().substs)
41 .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp))
43 return Err(NoSolution);
47 let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id);
48 let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
50 let mut nested_goals =
51 ecx.infcx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
52 let where_clause_bounds = tcx
53 .predicates_of(impl_def_id)
54 .instantiate(tcx, impl_substs)
57 .map(|pred| goal.with(tcx, pred));
58 nested_goals.extend(where_clause_bounds);
59 ecx.evaluate_all_and_make_canonical_response(nested_goals)
63 fn consider_assumption(
64 ecx: &mut EvalCtxt<'_, 'tcx>,
65 goal: Goal<'tcx, Self>,
66 assumption: ty::Predicate<'tcx>,
67 ) -> QueryResult<'tcx> {
68 if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred() {
69 // FIXME: Constness and polarity
71 let assumption_trait_pred =
72 ecx.infcx.instantiate_bound_vars_with_infer(poly_trait_pred);
73 let nested_goals = ecx.infcx.eq(
75 goal.predicate.trait_ref,
76 assumption_trait_pred.trait_ref,
78 ecx.evaluate_all_and_make_canonical_response(nested_goals)
85 fn consider_auto_trait_candidate(
86 ecx: &mut EvalCtxt<'_, 'tcx>,
87 goal: Goal<'tcx, Self>,
88 ) -> QueryResult<'tcx> {
89 ecx.probe_and_evaluate_goal_for_constituent_tys(
91 structural_traits::instantiate_constituent_tys_for_auto_trait,
95 fn consider_trait_alias_candidate(
96 ecx: &mut EvalCtxt<'_, 'tcx>,
97 goal: Goal<'tcx, Self>,
98 ) -> QueryResult<'tcx> {
101 ecx.infcx.probe(|_| {
102 let nested_obligations = tcx
103 .predicates_of(goal.predicate.def_id())
104 .instantiate(tcx, goal.predicate.trait_ref.substs);
105 ecx.evaluate_all_and_make_canonical_response(
106 nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(),
111 fn consider_builtin_sized_candidate(
112 ecx: &mut EvalCtxt<'_, 'tcx>,
113 goal: Goal<'tcx, Self>,
114 ) -> QueryResult<'tcx> {
115 ecx.probe_and_evaluate_goal_for_constituent_tys(
117 structural_traits::instantiate_constituent_tys_for_sized_trait,
121 fn consider_builtin_copy_clone_candidate(
122 ecx: &mut EvalCtxt<'_, 'tcx>,
123 goal: Goal<'tcx, Self>,
124 ) -> QueryResult<'tcx> {
125 ecx.probe_and_evaluate_goal_for_constituent_tys(
127 structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
131 fn consider_builtin_pointer_sized_candidate(
132 ecx: &mut EvalCtxt<'_, 'tcx>,
133 goal: Goal<'tcx, Self>,
134 ) -> QueryResult<'tcx> {
135 if goal.predicate.self_ty().has_non_region_infer() {
136 return ecx.make_canonical_response(Certainty::AMBIGUOUS);
140 let self_ty = tcx.erase_regions(goal.predicate.self_ty());
142 if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty))
143 && let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout
144 && layout.layout.size() == usize_layout.size()
145 && layout.layout.align().abi == usize_layout.align().abi
147 // FIXME: We could make this faster by making a no-constraints response
148 ecx.make_canonical_response(Certainty::Yes)
154 fn consider_builtin_fn_trait_candidates(
155 ecx: &mut EvalCtxt<'_, 'tcx>,
156 goal: Goal<'tcx, Self>,
157 goal_kind: ty::ClosureKind,
158 ) -> QueryResult<'tcx> {
159 if let Some(tupled_inputs_and_output) =
160 structural_traits::extract_tupled_inputs_and_output_from_callable(
162 goal.predicate.self_ty(),
166 let pred = tupled_inputs_and_output
167 .map_bound(|(inputs, _)| {
169 .mk_trait_ref(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
171 .to_predicate(ecx.tcx());
172 Self::consider_assumption(ecx, goal, pred)
174 ecx.make_canonical_response(Certainty::AMBIGUOUS)
178 fn consider_builtin_tuple_candidate(
179 ecx: &mut EvalCtxt<'_, 'tcx>,
180 goal: Goal<'tcx, Self>,
181 ) -> QueryResult<'tcx> {
182 if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
183 ecx.make_canonical_response(Certainty::Yes)
189 fn consider_builtin_pointee_candidate(
190 ecx: &mut EvalCtxt<'_, 'tcx>,
191 _goal: Goal<'tcx, Self>,
192 ) -> QueryResult<'tcx> {
193 ecx.make_canonical_response(Certainty::Yes)
196 fn consider_builtin_future_candidate(
197 ecx: &mut EvalCtxt<'_, 'tcx>,
198 goal: Goal<'tcx, Self>,
199 ) -> QueryResult<'tcx> {
200 let ty::Generator(def_id, _, _) = *goal.predicate.self_ty().kind() else {
201 return Err(NoSolution);
204 // Generators are not futures unless they come from `async` desugaring
206 if !tcx.generator_is_async(def_id) {
207 return Err(NoSolution);
210 // Async generator unconditionally implement `Future`
211 ecx.make_canonical_response(Certainty::Yes)
214 fn consider_builtin_generator_candidate(
215 ecx: &mut EvalCtxt<'_, 'tcx>,
216 goal: Goal<'tcx, Self>,
217 ) -> QueryResult<'tcx> {
218 let self_ty = goal.predicate.self_ty();
219 let ty::Generator(def_id, substs, _) = *self_ty.kind() else {
220 return Err(NoSolution);
223 // `async`-desugared generators do not implement the generator trait
225 if tcx.generator_is_async(def_id) {
226 return Err(NoSolution);
229 let generator = substs.as_generator();
230 Self::consider_assumption(
234 tcx.mk_trait_ref(goal.predicate.def_id(), [self_ty, generator.resume_ty()]),
241 impl<'tcx> EvalCtxt<'_, 'tcx> {
242 /// Convenience function for traits that are structural, i.e. that only
243 /// have nested subgoals that only change the self type. Unlike other
244 /// evaluate-like helpers, this does a probe, so it doesn't need to be
246 fn probe_and_evaluate_goal_for_constituent_tys(
248 goal: Goal<'tcx, TraitPredicate<'tcx>>,
249 constituent_tys: impl Fn(&InferCtxt<'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
250 ) -> QueryResult<'tcx> {
251 self.infcx.probe(|_| {
252 self.evaluate_all_and_make_canonical_response(
253 constituent_tys(self.infcx, goal.predicate.self_ty())?
258 ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)),
266 pub(super) fn compute_trait_goal(
268 goal: Goal<'tcx, TraitPredicate<'tcx>>,
269 ) -> QueryResult<'tcx> {
270 let candidates = self.assemble_and_evaluate_candidates(goal);
271 self.merge_trait_candidates_discard_reservation_impls(candidates)
274 #[instrument(level = "debug", skip(self), ret)]
275 pub(super) fn merge_trait_candidates_discard_reservation_impls(
277 mut candidates: Vec<Candidate<'tcx>>,
278 ) -> QueryResult<'tcx> {
279 match candidates.len() {
280 0 => return Err(NoSolution),
281 1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result),
285 if candidates.len() > 1 {
287 'outer: while i < candidates.len() {
288 for j in (0..candidates.len()).filter(|&j| i != j) {
289 if self.trait_candidate_should_be_dropped_in_favor_of(
293 debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
294 candidates.swap_remove(i);
299 debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
300 // If there are *STILL* multiple candidates, give up
301 // and report ambiguity.
304 debug!("multiple matches, ambig");
305 // FIXME: return overflow if all candidates overflow, otherwise return ambiguity.
311 Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result)
314 fn trait_candidate_should_be_dropped_in_favor_of(
316 candidate: &Candidate<'tcx>,
317 other: &Candidate<'tcx>,
319 // FIXME: implement this
320 match (candidate.source, other.source) {
321 (CandidateSource::Impl(_), _)
322 | (CandidateSource::ParamEnv(_), _)
323 | (CandidateSource::AliasBound(_), _)
324 | (CandidateSource::BuiltinImpl, _) => unimplemented!(),
328 fn discard_reservation_impl(&self, candidate: Candidate<'tcx>) -> Candidate<'tcx> {
329 if let CandidateSource::Impl(def_id) = candidate.source {
330 if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) {
331 debug!("Selected reservation impl");
332 // FIXME: reduce candidate to ambiguous
333 // FIXME: replace `var_values` with identity, yeet external constraints.