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::{CanonicalResponse, 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_infer::traits::util::supertraits;
12 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
13 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
14 use rustc_middle::ty::{TraitPredicate, TypeVisitable};
15 use rustc_span::DUMMY_SP;
17 pub mod structural_traits;
19 impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
20 fn self_ty(self) -> Ty<'tcx> {
24 fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
25 self.with_self_ty(tcx, self_ty)
28 fn trait_def_id(self, _: TyCtxt<'tcx>) -> DefId {
32 fn consider_impl_candidate(
33 ecx: &mut EvalCtxt<'_, 'tcx>,
34 goal: Goal<'tcx, TraitPredicate<'tcx>>,
36 ) -> QueryResult<'tcx> {
39 let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
40 let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
41 if iter::zip(goal.predicate.trait_ref.substs, impl_trait_ref.skip_binder().substs)
42 .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp))
44 return Err(NoSolution);
48 let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id);
49 let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
51 let mut nested_goals =
52 ecx.infcx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
53 let where_clause_bounds = tcx
54 .predicates_of(impl_def_id)
55 .instantiate(tcx, impl_substs)
58 .map(|pred| goal.with(tcx, pred));
59 nested_goals.extend(where_clause_bounds);
60 ecx.evaluate_all_and_make_canonical_response(nested_goals)
64 fn consider_assumption(
65 ecx: &mut EvalCtxt<'_, 'tcx>,
66 goal: Goal<'tcx, Self>,
67 assumption: ty::Predicate<'tcx>,
68 ) -> QueryResult<'tcx> {
69 if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred()
70 && poly_trait_pred.def_id() == goal.predicate.def_id()
72 // FIXME: Constness and polarity
74 let assumption_trait_pred =
75 ecx.infcx.instantiate_bound_vars_with_infer(poly_trait_pred);
76 let nested_goals = ecx.infcx.eq(
78 goal.predicate.trait_ref,
79 assumption_trait_pred.trait_ref,
81 ecx.evaluate_all_and_make_canonical_response(nested_goals)
88 fn consider_auto_trait_candidate(
89 ecx: &mut EvalCtxt<'_, 'tcx>,
90 goal: Goal<'tcx, Self>,
91 ) -> QueryResult<'tcx> {
92 ecx.probe_and_evaluate_goal_for_constituent_tys(
94 structural_traits::instantiate_constituent_tys_for_auto_trait,
98 fn consider_trait_alias_candidate(
99 ecx: &mut EvalCtxt<'_, 'tcx>,
100 goal: Goal<'tcx, Self>,
101 ) -> QueryResult<'tcx> {
104 ecx.infcx.probe(|_| {
105 let nested_obligations = tcx
106 .predicates_of(goal.predicate.def_id())
107 .instantiate(tcx, goal.predicate.trait_ref.substs);
108 ecx.evaluate_all_and_make_canonical_response(
109 nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(),
114 fn consider_builtin_sized_candidate(
115 ecx: &mut EvalCtxt<'_, 'tcx>,
116 goal: Goal<'tcx, Self>,
117 ) -> QueryResult<'tcx> {
118 ecx.probe_and_evaluate_goal_for_constituent_tys(
120 structural_traits::instantiate_constituent_tys_for_sized_trait,
124 fn consider_builtin_copy_clone_candidate(
125 ecx: &mut EvalCtxt<'_, 'tcx>,
126 goal: Goal<'tcx, Self>,
127 ) -> QueryResult<'tcx> {
128 ecx.probe_and_evaluate_goal_for_constituent_tys(
130 structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
134 fn consider_builtin_pointer_sized_candidate(
135 ecx: &mut EvalCtxt<'_, 'tcx>,
136 goal: Goal<'tcx, Self>,
137 ) -> QueryResult<'tcx> {
138 if goal.predicate.self_ty().has_non_region_infer() {
139 return ecx.make_canonical_response(Certainty::AMBIGUOUS);
143 let self_ty = tcx.erase_regions(goal.predicate.self_ty());
145 if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty))
146 && let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout
147 && layout.layout.size() == usize_layout.size()
148 && layout.layout.align().abi == usize_layout.align().abi
150 // FIXME: We could make this faster by making a no-constraints response
151 ecx.make_canonical_response(Certainty::Yes)
157 fn consider_builtin_fn_trait_candidates(
158 ecx: &mut EvalCtxt<'_, 'tcx>,
159 goal: Goal<'tcx, Self>,
160 goal_kind: ty::ClosureKind,
161 ) -> QueryResult<'tcx> {
162 if let Some(tupled_inputs_and_output) =
163 structural_traits::extract_tupled_inputs_and_output_from_callable(
165 goal.predicate.self_ty(),
169 let pred = tupled_inputs_and_output
170 .map_bound(|(inputs, _)| {
172 .mk_trait_ref(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
174 .to_predicate(ecx.tcx());
175 Self::consider_assumption(ecx, goal, pred)
177 ecx.make_canonical_response(Certainty::AMBIGUOUS)
181 fn consider_builtin_tuple_candidate(
182 ecx: &mut EvalCtxt<'_, 'tcx>,
183 goal: Goal<'tcx, Self>,
184 ) -> QueryResult<'tcx> {
185 if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
186 ecx.make_canonical_response(Certainty::Yes)
192 fn consider_builtin_pointee_candidate(
193 ecx: &mut EvalCtxt<'_, 'tcx>,
194 _goal: Goal<'tcx, Self>,
195 ) -> QueryResult<'tcx> {
196 ecx.make_canonical_response(Certainty::Yes)
199 fn consider_builtin_future_candidate(
200 ecx: &mut EvalCtxt<'_, 'tcx>,
201 goal: Goal<'tcx, Self>,
202 ) -> QueryResult<'tcx> {
203 let ty::Generator(def_id, _, _) = *goal.predicate.self_ty().kind() else {
204 return Err(NoSolution);
207 // Generators are not futures unless they come from `async` desugaring
209 if !tcx.generator_is_async(def_id) {
210 return Err(NoSolution);
213 // Async generator unconditionally implement `Future`
214 ecx.make_canonical_response(Certainty::Yes)
217 fn consider_builtin_generator_candidate(
218 ecx: &mut EvalCtxt<'_, 'tcx>,
219 goal: Goal<'tcx, Self>,
220 ) -> QueryResult<'tcx> {
221 let self_ty = goal.predicate.self_ty();
222 let ty::Generator(def_id, substs, _) = *self_ty.kind() else {
223 return Err(NoSolution);
226 // `async`-desugared generators do not implement the generator trait
228 if tcx.generator_is_async(def_id) {
229 return Err(NoSolution);
232 let generator = substs.as_generator();
233 Self::consider_assumption(
237 tcx.mk_trait_ref(goal.predicate.def_id(), [self_ty, generator.resume_ty()]),
243 fn consider_builtin_unsize_candidate(
244 ecx: &mut EvalCtxt<'_, 'tcx>,
245 goal: Goal<'tcx, Self>,
246 ) -> QueryResult<'tcx> {
248 let a_ty = goal.predicate.self_ty();
249 let b_ty = goal.predicate.trait_ref.substs.type_at(1);
250 if b_ty.is_ty_var() {
251 return ecx.make_canonical_response(Certainty::AMBIGUOUS);
253 ecx.infcx.probe(|_| {
254 match (a_ty.kind(), b_ty.kind()) {
255 // Trait upcasting, or `dyn Trait + Auto + 'a` -> `dyn Trait + 'b`
256 (&ty::Dynamic(_, _, ty::Dyn), &ty::Dynamic(_, _, ty::Dyn)) => {
257 // Dyn upcasting is handled separately, since due to upcasting,
258 // when there are two supertraits that differ by substs, we
259 // may return more than one query response.
260 return Err(NoSolution);
262 // `T` -> `dyn Trait` unsizing
263 (_, &ty::Dynamic(data, region, ty::Dyn)) => {
264 // Can only unsize to an object-safe type
267 .map_or(false, |def_id| !tcx.check_is_object_safe(def_id))
269 return Err(NoSolution);
272 let Some(sized_def_id) = tcx.lang_items().sized_trait() else {
273 return Err(NoSolution);
275 let nested_goals: Vec<_> = data
277 // Check that the type implements all of the predicates of the def-id.
278 // (i.e. the principal, all of the associated types match, and any auto traits)
279 .map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty)))
281 // The type must be Sized to be unsized.
284 ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty])),
286 // The type must outlive the lifetime of the `dyn` we're unsizing into.
287 goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))),
291 ecx.evaluate_all_and_make_canonical_response(nested_goals)
293 // `[T; n]` -> `[T]` unsizing
294 (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => {
295 // We just require that the element type stays the same
296 let nested_goals = ecx.infcx.eq(goal.param_env, a_elem_ty, b_elem_ty)?;
297 ecx.evaluate_all_and_make_canonical_response(nested_goals)
299 // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>`
300 (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs))
301 if a_def.is_struct() && a_def.did() == b_def.did() =>
303 let unsizing_params = tcx.unsizing_params_for_adt(a_def.did());
304 // We must be unsizing some type parameters. This also implies
305 // that the struct has a tail field.
306 if unsizing_params.is_empty() {
307 return Err(NoSolution);
310 let tail_field = a_def
314 .expect("expected unsized ADT to have a tail field");
315 let tail_field_ty = tcx.bound_type_of(tail_field.did);
317 let a_tail_ty = tail_field_ty.subst(tcx, a_substs);
318 let b_tail_ty = tail_field_ty.subst(tcx, b_substs);
320 // Substitute just the unsizing params from B into A. The type after
321 // this substitution must be equal to B. This is so we don't unsize
322 // unrelated type parameters.
323 let new_a_substs = tcx.mk_substs(a_substs.iter().enumerate().map(|(i, a)| {
324 if unsizing_params.contains(i as u32) { b_substs[i] } else { a }
326 let unsized_a_ty = tcx.mk_adt(a_def, new_a_substs);
328 // Finally, we require that `TailA: Unsize<TailB>` for the tail field
330 let mut nested_goals = ecx.infcx.eq(goal.param_env, unsized_a_ty, b_ty)?;
331 nested_goals.push(goal.with(
334 tcx.mk_trait_ref(goal.predicate.def_id(), [a_tail_ty, b_tail_ty]),
338 ecx.evaluate_all_and_make_canonical_response(nested_goals)
340 // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>`
341 (&ty::Tuple(a_tys), &ty::Tuple(b_tys))
342 if a_tys.len() == b_tys.len() && !a_tys.is_empty() =>
344 let (a_last_ty, a_rest_tys) = a_tys.split_last().unwrap();
345 let b_last_ty = b_tys.last().unwrap();
347 // Substitute just the tail field of B., and require that they're equal.
348 let unsized_a_ty = tcx.mk_tup(a_rest_tys.iter().chain([b_last_ty]));
349 let mut nested_goals = ecx.infcx.eq(goal.param_env, unsized_a_ty, b_ty)?;
351 // Similar to ADTs, require that the rest of the fields are equal.
352 nested_goals.push(goal.with(
355 tcx.mk_trait_ref(goal.predicate.def_id(), [*a_last_ty, *b_last_ty]),
359 ecx.evaluate_all_and_make_canonical_response(nested_goals)
361 _ => Err(NoSolution),
366 fn consider_builtin_dyn_upcast_candidates(
367 ecx: &mut EvalCtxt<'_, 'tcx>,
368 goal: Goal<'tcx, Self>,
369 ) -> Vec<CanonicalResponse<'tcx>> {
372 let a_ty = goal.predicate.self_ty();
373 let b_ty = goal.predicate.trait_ref.substs.type_at(1);
374 let ty::Dynamic(a_data, a_region, ty::Dyn) = *a_ty.kind() else {
377 let ty::Dynamic(b_data, b_region, ty::Dyn) = *b_ty.kind() else {
381 // All of a's auto traits need to be in b's auto traits.
382 let auto_traits_compatible =
383 b_data.auto_traits().all(|b| a_data.auto_traits().any(|a| a == b));
384 if !auto_traits_compatible {
388 let mut unsize_dyn_to_principal = |principal: Option<ty::PolyExistentialTraitRef<'tcx>>| {
389 ecx.infcx.probe(|_| -> Result<_, NoSolution> {
390 // Require that all of the trait predicates from A match B, except for
391 // the auto traits. We do this by constructing a new A type with B's
392 // auto traits, and equating these types.
393 let new_a_data = principal
395 .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait))
396 .chain(a_data.iter().filter(|a| {
397 matches!(a.skip_binder(), ty::ExistentialPredicate::Projection(_))
402 .map(ty::ExistentialPredicate::AutoTrait)
403 .map(ty::Binder::dummy),
405 let new_a_data = tcx.mk_poly_existential_predicates(new_a_data);
406 let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn);
408 // We also require that A's lifetime outlives B's lifetime.
409 let mut nested_obligations = ecx.infcx.eq(goal.param_env, new_a_ty, b_ty)?;
410 nested_obligations.push(
411 goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region))),
414 ecx.evaluate_all_and_make_canonical_response(nested_obligations)
418 let mut responses = vec![];
419 // If the principal def ids match (or are both none), then we're not doing
420 // trait upcasting. We're just removing auto traits (or shortening the lifetime).
421 if a_data.principal_def_id() == b_data.principal_def_id() {
422 if let Ok(response) = unsize_dyn_to_principal(a_data.principal()) {
423 responses.push(response);
425 } else if let Some(a_principal) = a_data.principal()
426 && let Some(b_principal) = b_data.principal()
428 for super_trait_ref in supertraits(tcx, a_principal.with_self_ty(tcx, a_ty)) {
429 if super_trait_ref.def_id() != b_principal.def_id() {
432 let erased_trait_ref = super_trait_ref
433 .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref));
434 if let Ok(response) = unsize_dyn_to_principal(Some(erased_trait_ref)) {
435 responses.push(response);
443 fn consider_builtin_discriminant_kind_candidate(
444 ecx: &mut EvalCtxt<'_, 'tcx>,
445 _goal: Goal<'tcx, Self>,
446 ) -> QueryResult<'tcx> {
447 // `DiscriminantKind` is automatically implemented for every type.
448 ecx.make_canonical_response(Certainty::Yes)
452 impl<'tcx> EvalCtxt<'_, 'tcx> {
453 /// Convenience function for traits that are structural, i.e. that only
454 /// have nested subgoals that only change the self type. Unlike other
455 /// evaluate-like helpers, this does a probe, so it doesn't need to be
457 fn probe_and_evaluate_goal_for_constituent_tys(
459 goal: Goal<'tcx, TraitPredicate<'tcx>>,
460 constituent_tys: impl Fn(&InferCtxt<'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
461 ) -> QueryResult<'tcx> {
462 self.infcx.probe(|_| {
463 self.evaluate_all_and_make_canonical_response(
464 constituent_tys(self.infcx, goal.predicate.self_ty())?
469 ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)),
477 pub(super) fn compute_trait_goal(
479 goal: Goal<'tcx, TraitPredicate<'tcx>>,
480 ) -> QueryResult<'tcx> {
481 let candidates = self.assemble_and_evaluate_candidates(goal);
482 self.merge_trait_candidates_discard_reservation_impls(candidates)
485 #[instrument(level = "debug", skip(self), ret)]
486 pub(super) fn merge_trait_candidates_discard_reservation_impls(
488 mut candidates: Vec<Candidate<'tcx>>,
489 ) -> QueryResult<'tcx> {
490 match candidates.len() {
491 0 => return Err(NoSolution),
492 1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result),
496 if candidates.len() > 1 {
498 'outer: while i < candidates.len() {
499 for j in (0..candidates.len()).filter(|&j| i != j) {
500 if self.trait_candidate_should_be_dropped_in_favor_of(
504 debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
505 candidates.swap_remove(i);
510 debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
511 // If there are *STILL* multiple candidates, give up
512 // and report ambiguity.
515 debug!("multiple matches, ambig");
516 // FIXME: return overflow if all candidates overflow, otherwise return ambiguity.
522 Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result)
525 fn trait_candidate_should_be_dropped_in_favor_of(
527 candidate: &Candidate<'tcx>,
528 other: &Candidate<'tcx>,
530 // FIXME: implement this
531 match (candidate.source, other.source) {
532 (CandidateSource::Impl(_), _)
533 | (CandidateSource::ParamEnv(_), _)
534 | (CandidateSource::AliasBound, _)
535 | (CandidateSource::BuiltinImpl, _) => unimplemented!(),
539 fn discard_reservation_impl(&self, candidate: Candidate<'tcx>) -> Candidate<'tcx> {
540 if let CandidateSource::Impl(def_id) = candidate.source {
541 if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) {
542 debug!("Selected reservation impl");
543 // FIXME: reduce candidate to ambiguous
544 // FIXME: replace `var_values` with identity, yeet external constraints.