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::{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::TraitPredicate;
13 use rustc_middle::ty::{self, Ty, TyCtxt};
14 use rustc_span::DUMMY_SP;
16 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,
132 impl<'tcx> EvalCtxt<'_, 'tcx> {
133 /// Convenience function for traits that are structural, i.e. that only
134 /// have nested subgoals that only change the self type. Unlike other
135 /// evaluate-like helpers, this does a probe, so it doesn't need to be
137 fn probe_and_evaluate_goal_for_constituent_tys(
139 goal: Goal<'tcx, TraitPredicate<'tcx>>,
140 constituent_tys: impl Fn(&InferCtxt<'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
141 ) -> QueryResult<'tcx> {
142 self.infcx.probe(|_| {
143 self.evaluate_all_and_make_canonical_response(
144 constituent_tys(self.infcx, goal.predicate.self_ty())?
149 ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)),
157 pub(super) fn compute_trait_goal(
159 goal: Goal<'tcx, TraitPredicate<'tcx>>,
160 ) -> QueryResult<'tcx> {
161 let candidates = self.assemble_and_evaluate_candidates(goal);
162 self.merge_trait_candidates_discard_reservation_impls(candidates)
165 #[instrument(level = "debug", skip(self), ret)]
166 pub(super) fn merge_trait_candidates_discard_reservation_impls(
168 mut candidates: Vec<Candidate<'tcx>>,
169 ) -> QueryResult<'tcx> {
170 match candidates.len() {
171 0 => return Err(NoSolution),
172 1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result),
176 if candidates.len() > 1 {
178 'outer: while i < candidates.len() {
179 for j in (0..candidates.len()).filter(|&j| i != j) {
180 if self.trait_candidate_should_be_dropped_in_favor_of(
184 debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
185 candidates.swap_remove(i);
190 debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
191 // If there are *STILL* multiple candidates, give up
192 // and report ambiguity.
195 debug!("multiple matches, ambig");
196 // FIXME: return overflow if all candidates overflow, otherwise return ambiguity.
202 Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result)
205 fn trait_candidate_should_be_dropped_in_favor_of(
207 candidate: &Candidate<'tcx>,
208 other: &Candidate<'tcx>,
210 // FIXME: implement this
211 match (candidate.source, other.source) {
212 (CandidateSource::Impl(_), _)
213 | (CandidateSource::ParamEnv(_), _)
214 | (CandidateSource::AliasBound(_), _)
215 | (CandidateSource::BuiltinImpl, _) => unimplemented!(),
219 fn discard_reservation_impl(&self, candidate: Candidate<'tcx>) -> Candidate<'tcx> {
220 if let CandidateSource::Impl(def_id) = candidate.source {
221 if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) {
222 debug!("Selected reservation impl");
223 // FIXME: reduce candidate to ambiguous
224 // FIXME: replace `var_values` with identity, yeet external constraints.