3 //! Confirmation unifies the output type parameters of the trait
4 //! with the values found in the obligation, possibly yielding a
5 //! type error. See the [rustc dev guide] for more details.
8 //! https://rustc-dev-guide.rust-lang.org/traits/resolution.html#confirmation
9 use rustc_ast
::Mutability
;
10 use rustc_data_structures
::stack
::ensure_sufficient_stack
;
11 use rustc_hir
::lang_items
::LangItem
;
12 use rustc_infer
::infer
::LateBoundRegionConversionTime
::HigherRankedType
;
13 use rustc_infer
::infer
::{DefineOpaqueTypes, InferOk}
;
14 use rustc_middle
::traits
::{BuiltinImplSource, SelectionOutputTypeParameterMismatch}
;
15 use rustc_middle
::ty
::{
16 self, GenericArgs
, GenericArgsRef
, GenericParamDefKind
, ToPolyTraitRef
, ToPredicate
,
17 TraitPredicate
, Ty
, TyCtxt
, TypeVisitableExt
,
19 use rustc_span
::def_id
::DefId
;
21 use crate::traits
::project
::{normalize_with_depth, normalize_with_depth_to}
;
22 use crate::traits
::util
::{self, closure_trait_ref_and_return_type}
;
23 use crate::traits
::vtable
::{
24 count_own_vtable_entries
, prepare_vtable_segments
, vtable_trait_first_method_offset
,
28 BuiltinDerivedObligation
, ImplDerivedObligation
, ImplDerivedObligationCause
, ImplSource
,
29 ImplSourceUserDefinedData
, Normalized
, Obligation
, ObligationCause
,
30 OutputTypeParameterMismatch
, PolyTraitObligation
, PredicateObligation
, Selection
,
31 SelectionError
, TraitNotObjectSafe
, Unimplemented
,
34 use super::BuiltinImplConditions
;
35 use super::SelectionCandidate
::{self, *}
;
36 use super::SelectionContext
;
39 use std
::ops
::ControlFlow
;
41 impl<'cx
, 'tcx
> SelectionContext
<'cx
, 'tcx
> {
42 #[instrument(level = "debug", skip(self))]
43 pub(super) fn confirm_candidate(
45 obligation
: &PolyTraitObligation
<'tcx
>,
46 candidate
: SelectionCandidate
<'tcx
>,
47 ) -> Result
<Selection
<'tcx
>, SelectionError
<'tcx
>> {
48 let mut impl_src
= match candidate
{
49 BuiltinCandidate { has_nested }
=> {
50 let data
= self.confirm_builtin_candidate(obligation
, has_nested
);
51 ImplSource
::Builtin(BuiltinImplSource
::Misc
, data
)
54 TransmutabilityCandidate
=> {
55 let data
= self.confirm_transmutability_candidate(obligation
)?
;
56 ImplSource
::Builtin(BuiltinImplSource
::Misc
, data
)
59 ParamCandidate(param
) => {
61 self.confirm_param_candidate(obligation
, param
.map_bound(|t
| t
.trait_ref
));
62 ImplSource
::Param(obligations
)
65 ImplCandidate(impl_def_id
) => {
66 ImplSource
::UserDefined(self.confirm_impl_candidate(obligation
, impl_def_id
))
69 AutoImplCandidate
=> {
70 let data
= self.confirm_auto_impl_candidate(obligation
)?
;
71 ImplSource
::Builtin(BuiltinImplSource
::Misc
, data
)
74 ProjectionCandidate(idx
, _
) => {
75 let obligations
= self.confirm_projection_candidate(obligation
, idx
)?
;
76 ImplSource
::Param(obligations
)
79 ObjectCandidate(idx
) => self.confirm_object_candidate(obligation
, idx
)?
,
81 ClosureCandidate { .. }
=> {
82 let vtable_closure
= self.confirm_closure_candidate(obligation
)?
;
83 ImplSource
::Builtin(BuiltinImplSource
::Misc
, vtable_closure
)
86 GeneratorCandidate
=> {
87 let vtable_generator
= self.confirm_generator_candidate(obligation
)?
;
88 ImplSource
::Builtin(BuiltinImplSource
::Misc
, vtable_generator
)
92 let vtable_future
= self.confirm_future_candidate(obligation
)?
;
93 ImplSource
::Builtin(BuiltinImplSource
::Misc
, vtable_future
)
96 FnPointerCandidate { is_const }
=> {
97 let data
= self.confirm_fn_pointer_candidate(obligation
, is_const
)?
;
98 ImplSource
::Builtin(BuiltinImplSource
::Misc
, data
)
101 TraitAliasCandidate
=> {
102 let data
= self.confirm_trait_alias_candidate(obligation
);
103 ImplSource
::Builtin(BuiltinImplSource
::Misc
, data
)
106 BuiltinObjectCandidate
=> {
107 // This indicates something like `Trait + Send: Send`. In this case, we know that
108 // this holds because that's what the object type is telling us, and there's really
109 // no additional obligations to prove and no types in particular to unify, etc.
110 ImplSource
::Builtin(BuiltinImplSource
::Misc
, Vec
::new())
113 BuiltinUnsizeCandidate
=> self.confirm_builtin_unsize_candidate(obligation
)?
,
115 TraitUpcastingUnsizeCandidate(idx
) => {
116 self.confirm_trait_upcasting_unsize_candidate(obligation
, idx
)?
119 ConstDestructCandidate(def_id
) => {
120 let data
= self.confirm_const_destruct_candidate(obligation
, def_id
)?
;
121 ImplSource
::Builtin(BuiltinImplSource
::Misc
, data
)
125 // The obligations returned by confirmation are recursively evaluated
126 // so we need to make sure they have the correct depth.
127 for subobligation
in impl_src
.borrow_nested_obligations_mut() {
128 subobligation
.set_depth_from_parent(obligation
.recursion_depth
);
134 fn confirm_projection_candidate(
136 obligation
: &PolyTraitObligation
<'tcx
>,
138 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
139 let tcx
= self.tcx();
141 let trait_predicate
= self.infcx
.shallow_resolve(obligation
.predicate
);
142 let placeholder_trait_predicate
=
143 self.infcx
.instantiate_binder_with_placeholders(trait_predicate
).trait_ref
;
144 let placeholder_self_ty
= placeholder_trait_predicate
.self_ty();
145 let placeholder_trait_predicate
= ty
::Binder
::dummy(placeholder_trait_predicate
);
146 let (def_id
, args
) = match *placeholder_self_ty
.kind() {
147 // Excluding IATs and type aliases here as they don't have meaningful item bounds.
148 ty
::Alias(ty
::Projection
| ty
::Opaque
, ty
::AliasTy { def_id, args, .. }
) => {
151 _
=> bug
!("projection candidate for unexpected type: {:?}", placeholder_self_ty
),
154 let candidate_predicate
=
155 tcx
.item_bounds(def_id
).map_bound(|i
| i
[idx
]).instantiate(tcx
, args
);
156 let candidate
= candidate_predicate
158 .expect("projection candidate is not a trait predicate")
159 .map_bound(|t
| t
.trait_ref
);
160 let mut obligations
= Vec
::new();
161 let candidate
= normalize_with_depth_to(
163 obligation
.param_env
,
164 obligation
.cause
.clone(),
165 obligation
.recursion_depth
+ 1,
170 obligations
.extend(self.infcx
.commit_if_ok(|_
| {
172 .at(&obligation
.cause
, obligation
.param_env
)
173 .sup(DefineOpaqueTypes
::No
, placeholder_trait_predicate
, candidate
)
174 .map(|InferOk { obligations, .. }
| obligations
)
175 .map_err(|_
| Unimplemented
)
178 if let ty
::Alias(ty
::Projection
, ..) = placeholder_self_ty
.kind() {
179 let predicates
= tcx
.predicates_of(def_id
).instantiate_own(tcx
, args
);
180 for (predicate
, _
) in predicates
{
181 let normalized
= normalize_with_depth_to(
183 obligation
.param_env
,
184 obligation
.cause
.clone(),
185 obligation
.recursion_depth
+ 1,
189 obligations
.push(Obligation
::with_depth(
191 obligation
.cause
.clone(),
192 obligation
.recursion_depth
+ 1,
193 obligation
.param_env
,
202 fn confirm_param_candidate(
204 obligation
: &PolyTraitObligation
<'tcx
>,
205 param
: ty
::PolyTraitRef
<'tcx
>,
206 ) -> Vec
<PredicateObligation
<'tcx
>> {
207 debug
!(?obligation
, ?param
, "confirm_param_candidate");
209 // During evaluation, we already checked that this
210 // where-clause trait-ref could be unified with the obligation
211 // trait-ref. Repeat that unification now without any
212 // transactional boundary; it should not fail.
213 match self.match_where_clause_trait_ref(obligation
, param
) {
214 Ok(obligations
) => obligations
,
217 "Where clause `{:?}` was applicable to `{:?}` but now is not",
225 fn confirm_builtin_candidate(
227 obligation
: &PolyTraitObligation
<'tcx
>,
229 ) -> Vec
<PredicateObligation
<'tcx
>> {
230 debug
!(?obligation
, ?has_nested
, "confirm_builtin_candidate");
232 let lang_items
= self.tcx().lang_items();
233 let obligations
= if has_nested
{
234 let trait_def
= obligation
.predicate
.def_id();
235 let conditions
= if Some(trait_def
) == lang_items
.sized_trait() {
236 self.sized_conditions(obligation
)
237 } else if Some(trait_def
) == lang_items
.copy_trait() {
238 self.copy_clone_conditions(obligation
)
239 } else if Some(trait_def
) == lang_items
.clone_trait() {
240 self.copy_clone_conditions(obligation
)
242 bug
!("unexpected builtin trait {:?}", trait_def
)
244 let BuiltinImplConditions
::Where(nested
) = conditions
else {
245 bug
!("obligation {:?} had matched a builtin impl but now doesn't", obligation
);
248 let cause
= obligation
.derived_cause(BuiltinDerivedObligation
);
249 self.collect_predicates_for_types(
250 obligation
.param_env
,
252 obligation
.recursion_depth
+ 1,
260 debug
!(?obligations
);
265 #[instrument(level = "debug", skip(self))]
266 fn confirm_transmutability_candidate(
268 obligation
: &PolyTraitObligation
<'tcx
>,
269 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
270 use rustc_transmute
::{Answer, Condition}
;
271 #[instrument(level = "debug", skip(tcx, obligation, predicate))]
272 fn flatten_answer_tree
<'tcx
>(
274 obligation
: &PolyTraitObligation
<'tcx
>,
275 predicate
: TraitPredicate
<'tcx
>,
276 cond
: Condition
<rustc_transmute
::layout
::rustc
::Ref
<'tcx
>>,
277 ) -> Vec
<PredicateObligation
<'tcx
>> {
279 // FIXME(bryangarza): Add separate `IfAny` case, instead of treating as `IfAll`
280 // Not possible until the trait solver supports disjunctions of obligations
281 Condition
::IfAll(conds
) | Condition
::IfAny(conds
) => conds
283 .flat_map(|cond
| flatten_answer_tree(tcx
, obligation
, predicate
, cond
))
285 Condition
::IfTransmutable { src, dst }
=> {
286 let trait_def_id
= obligation
.predicate
.def_id();
287 let scope
= predicate
.trait_ref
.args
.type_at(2);
288 let assume_const
= predicate
.trait_ref
.args
.const_at(3);
289 let make_obl
= |from_ty
, to_ty
| {
290 let trait_ref1
= ty
::TraitRef
::new(
294 ty
::GenericArg
::from(to_ty
),
295 ty
::GenericArg
::from(from_ty
),
296 ty
::GenericArg
::from(scope
),
297 ty
::GenericArg
::from(assume_const
),
300 Obligation
::with_depth(
302 obligation
.cause
.clone(),
303 obligation
.recursion_depth
+ 1,
304 obligation
.param_env
,
309 // If Dst is mutable, check bidirectionally.
310 // For example, transmuting bool -> u8 is OK as long as you can't update that u8
311 // to be > 1, because you could later transmute the u8 back to a bool and get UB.
312 match dst
.mutability
{
313 Mutability
::Not
=> vec
![make_obl(src
.ty
, dst
.ty
)],
314 Mutability
::Mut
=> vec
![make_obl(src
.ty
, dst
.ty
), make_obl(dst
.ty
, src
.ty
)],
320 // We erase regions here because transmutability calls layout queries,
321 // which does not handle inference regions and doesn't particularly
322 // care about other regions. Erasing late-bound regions is equivalent
323 // to instantiating the binder with placeholders then erasing those
324 // placeholder regions.
326 self.tcx().erase_regions(self.tcx().erase_late_bound_regions(obligation
.predicate
));
328 let Some(assume
) = rustc_transmute
::Assume
::from_const(
330 obligation
.param_env
,
331 predicate
.trait_ref
.args
.const_at(3),
333 return Err(Unimplemented
);
336 let dst
= predicate
.trait_ref
.args
.type_at(0);
337 let src
= predicate
.trait_ref
.args
.type_at(1);
339 let mut transmute_env
= rustc_transmute
::TransmuteTypeEnv
::new(self.infcx
);
340 let maybe_transmutable
= transmute_env
.is_transmutable(
341 obligation
.cause
.clone(),
342 rustc_transmute
::Types { dst, src }
,
343 predicate
.trait_ref
.args
.type_at(2),
347 let fully_flattened
= match maybe_transmutable
{
348 Answer
::No(_
) => Err(Unimplemented
)?
,
349 Answer
::If(cond
) => flatten_answer_tree(self.tcx(), obligation
, predicate
, cond
),
350 Answer
::Yes
=> vec
![],
353 debug
!(?fully_flattened
);
357 /// This handles the case where an `auto trait Foo` impl is being used.
358 /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
360 /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
361 /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
362 fn confirm_auto_impl_candidate(
364 obligation
: &PolyTraitObligation
<'tcx
>,
365 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
366 debug
!(?obligation
, "confirm_auto_impl_candidate");
368 let self_ty
= self.infcx
.shallow_resolve(obligation
.predicate
.self_ty());
369 let types
= self.constituent_types_for_ty(self_ty
)?
;
370 Ok(self.vtable_auto_impl(obligation
, obligation
.predicate
.def_id(), types
))
373 /// See `confirm_auto_impl_candidate`.
376 obligation
: &PolyTraitObligation
<'tcx
>,
378 nested
: ty
::Binder
<'tcx
, Vec
<Ty
<'tcx
>>>,
379 ) -> Vec
<PredicateObligation
<'tcx
>> {
380 debug
!(?nested
, "vtable_auto_impl");
381 ensure_sufficient_stack(|| {
382 let cause
= obligation
.derived_cause(BuiltinDerivedObligation
);
384 let poly_trait_ref
= obligation
.predicate
.to_poly_trait_ref();
385 let trait_ref
= self.infcx
.instantiate_binder_with_placeholders(poly_trait_ref
);
386 let trait_obligations
: Vec
<PredicateObligation
<'_
>> = self.impl_or_trait_obligations(
388 obligation
.recursion_depth
+ 1,
389 obligation
.param_env
,
392 obligation
.predicate
,
395 let mut obligations
= self.collect_predicates_for_types(
396 obligation
.param_env
,
398 obligation
.recursion_depth
+ 1,
403 // Adds the predicates from the trait. Note that this contains a `Self: Trait`
404 // predicate as usual. It won't have any effect since auto traits are coinductive.
405 obligations
.extend(trait_obligations
);
407 debug
!(?obligations
, "vtable_auto_impl");
413 fn confirm_impl_candidate(
415 obligation
: &PolyTraitObligation
<'tcx
>,
417 ) -> ImplSourceUserDefinedData
<'tcx
, PredicateObligation
<'tcx
>> {
418 debug
!(?obligation
, ?impl_def_id
, "confirm_impl_candidate");
420 // First, create the substitutions by matching the impl again,
421 // this time not in a probe.
422 let args
= self.rematch_impl(impl_def_id
, obligation
);
423 debug
!(?args
, "impl args");
424 ensure_sufficient_stack(|| {
429 obligation
.recursion_depth
+ 1,
430 obligation
.param_env
,
431 obligation
.predicate
,
439 args
: Normalized
<'tcx
, GenericArgsRef
<'tcx
>>,
440 cause
: &ObligationCause
<'tcx
>,
441 recursion_depth
: usize,
442 param_env
: ty
::ParamEnv
<'tcx
>,
443 parent_trait_pred
: ty
::Binder
<'tcx
, ty
::TraitPredicate
<'tcx
>>,
444 ) -> ImplSourceUserDefinedData
<'tcx
, PredicateObligation
<'tcx
>> {
445 debug
!(?impl_def_id
, ?args
, ?recursion_depth
, "vtable_impl");
447 let mut impl_obligations
= self.impl_or_trait_obligations(
456 debug
!(?impl_obligations
, "vtable_impl");
458 // Because of RFC447, the impl-trait-ref and obligations
459 // are sufficient to determine the impl args, without
460 // relying on projections in the impl-trait-ref.
462 // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
463 impl_obligations
.extend(args
.obligations
);
465 ImplSourceUserDefinedData { impl_def_id, args: args.value, nested: impl_obligations }
468 fn confirm_object_candidate(
470 obligation
: &PolyTraitObligation
<'tcx
>,
472 ) -> Result
<ImplSource
<'tcx
, PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
473 let tcx
= self.tcx();
474 debug
!(?obligation
, ?index
, "confirm_object_candidate");
476 let trait_predicate
= self.infcx
.instantiate_binder_with_placeholders(obligation
.predicate
);
477 let self_ty
= self.infcx
.shallow_resolve(trait_predicate
.self_ty());
478 let obligation_trait_ref
= ty
::Binder
::dummy(trait_predicate
.trait_ref
);
479 let ty
::Dynamic(data
, ..) = *self_ty
.kind() else {
480 span_bug
!(obligation
.cause
.span
, "object candidate with non-object");
483 let object_trait_ref
= data
.principal().unwrap_or_else(|| {
484 span_bug
!(obligation
.cause
.span
, "object candidate with no principal")
486 let object_trait_ref
= self.infcx
.instantiate_binder_with_fresh_vars(
487 obligation
.cause
.span
,
491 let object_trait_ref
= object_trait_ref
.with_self_ty(self.tcx(), self_ty
);
493 let mut nested
= vec
![];
495 let mut supertraits
= util
::supertraits(tcx
, ty
::Binder
::dummy(object_trait_ref
));
496 let unnormalized_upcast_trait_ref
=
497 supertraits
.nth(index
).expect("supertraits iterator no longer has as many elements");
499 let upcast_trait_ref
= normalize_with_depth_to(
501 obligation
.param_env
,
502 obligation
.cause
.clone(),
503 obligation
.recursion_depth
+ 1,
504 unnormalized_upcast_trait_ref
,
508 nested
.extend(self.infcx
.commit_if_ok(|_
| {
510 .at(&obligation
.cause
, obligation
.param_env
)
511 .sup(DefineOpaqueTypes
::No
, obligation_trait_ref
, upcast_trait_ref
)
512 .map(|InferOk { obligations, .. }
| obligations
)
513 .map_err(|_
| Unimplemented
)
516 // Check supertraits hold. This is so that their associated type bounds
517 // will be checked in the code below.
518 for super_trait
in tcx
519 .super_predicates_of(trait_predicate
.def_id())
520 .instantiate(tcx
, trait_predicate
.trait_ref
.args
)
524 let normalized_super_trait
= normalize_with_depth_to(
526 obligation
.param_env
,
527 obligation
.cause
.clone(),
528 obligation
.recursion_depth
+ 1,
532 nested
.push(obligation
.with(tcx
, normalized_super_trait
));
535 let assoc_types
: Vec
<_
> = tcx
536 .associated_items(trait_predicate
.def_id())
537 .in_definition_order()
538 // Associated types that require `Self: Sized` do not show up in the built-in
539 // implementation of `Trait for dyn Trait`, and can be dropped here.
540 .filter(|item
| !tcx
.generics_require_sized_self(item
.def_id
))
542 |item
| if item
.kind
== ty
::AssocKind
::Type { Some(item.def_id) }
else { None }
,
546 for assoc_type
in assoc_types
{
547 let defs
: &ty
::Generics
= tcx
.generics_of(assoc_type
);
549 if !defs
.params
.is_empty() && !tcx
.features().generic_associated_types_extended
{
550 tcx
.sess
.delay_span_bug(
551 obligation
.cause
.span
,
552 "GATs in trait object shouldn't have been considered",
554 return Err(SelectionError
::TraitNotObjectSafe(trait_predicate
.trait_ref
.def_id
));
557 // This maybe belongs in wf, but that can't (doesn't) handle
558 // higher-ranked things.
559 // Prevent, e.g., `dyn Iterator<Item = str>`.
560 for bound
in self.tcx().item_bounds(assoc_type
).transpose_iter() {
561 let subst_bound
= if defs
.count() == 0 {
562 bound
.instantiate(tcx
, trait_predicate
.trait_ref
.args
)
564 let mut args
= smallvec
::SmallVec
::with_capacity(defs
.count());
565 args
.extend(trait_predicate
.trait_ref
.args
.iter());
566 let mut bound_vars
: smallvec
::SmallVec
<[ty
::BoundVariableKind
; 8]> =
567 smallvec
::SmallVec
::with_capacity(
568 bound
.skip_binder().kind().bound_vars().len() + defs
.count(),
570 bound_vars
.extend(bound
.skip_binder().kind().bound_vars().into_iter());
571 GenericArgs
::fill_single(&mut args
, defs
, &mut |param
, _
| match param
.kind
{
572 GenericParamDefKind
::Type { .. }
=> {
573 let kind
= ty
::BoundTyKind
::Param(param
.def_id
, param
.name
);
574 let bound_var
= ty
::BoundVariableKind
::Ty(kind
);
575 bound_vars
.push(bound_var
);
580 var
: ty
::BoundVar
::from_usize(bound_vars
.len() - 1),
586 GenericParamDefKind
::Lifetime
=> {
587 let kind
= ty
::BoundRegionKind
::BrNamed(param
.def_id
, param
.name
);
588 let bound_var
= ty
::BoundVariableKind
::Region(kind
);
589 bound_vars
.push(bound_var
);
590 ty
::Region
::new_late_bound(
594 var
: ty
::BoundVar
::from_usize(bound_vars
.len() - 1),
600 GenericParamDefKind
::Const { .. }
=> {
601 let bound_var
= ty
::BoundVariableKind
::Const
;
602 bound_vars
.push(bound_var
);
603 ty
::Const
::new_bound(
606 ty
::BoundVar
::from_usize(bound_vars
.len() - 1),
607 tcx
.type_of(param
.def_id
)
609 .expect("const parameter types cannot be generic"),
614 let bound_vars
= tcx
.mk_bound_variable_kinds(&bound_vars
);
615 let assoc_ty_args
= tcx
.mk_args(&args
);
617 bound
.map_bound(|b
| b
.kind().skip_binder()).instantiate(tcx
, assoc_ty_args
);
618 ty
::Binder
::bind_with_vars(bound
, bound_vars
).to_predicate(tcx
)
620 let normalized_bound
= normalize_with_depth_to(
622 obligation
.param_env
,
623 obligation
.cause
.clone(),
624 obligation
.recursion_depth
+ 1,
628 nested
.push(obligation
.with(tcx
, normalized_bound
));
632 debug
!(?nested
, "object nested obligations");
634 let vtable_base
= vtable_trait_first_method_offset(
636 (unnormalized_upcast_trait_ref
, ty
::Binder
::dummy(object_trait_ref
)),
639 Ok(ImplSource
::Builtin(BuiltinImplSource
::Object { vtable_base: vtable_base }
, nested
))
642 fn confirm_fn_pointer_candidate(
644 obligation
: &PolyTraitObligation
<'tcx
>,
647 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
648 debug
!(?obligation
, "confirm_fn_pointer_candidate");
650 let tcx
= self.tcx();
652 let Some(self_ty
) = self.infcx
.shallow_resolve(obligation
.self_ty().no_bound_vars()) else {
653 // FIXME: Ideally we'd support `for<'a> fn(&'a ()): Fn(&'a ())`,
654 // but we do not currently. Luckily, such a bound is not
655 // particularly useful, so we don't expect users to write
657 return Err(SelectionError
::Unimplemented
);
660 let sig
= self_ty
.fn_sig(tcx
);
661 let trait_ref
= closure_trait_ref_and_return_type(
663 obligation
.predicate
.def_id(),
666 util
::TupleArgumentsFlag
::Yes
,
668 .map_bound(|(trait_ref
, _
)| trait_ref
);
670 let mut nested
= self.confirm_poly_trait_refs(obligation
, trait_ref
)?
;
671 let cause
= obligation
.derived_cause(BuiltinDerivedObligation
);
673 // Confirm the `type Output: Sized;` bound that is present on `FnOnce`
674 let output_ty
= self.infcx
.instantiate_binder_with_placeholders(sig
.output());
675 let output_ty
= normalize_with_depth_to(
677 obligation
.param_env
,
679 obligation
.recursion_depth
,
683 let tr
= ty
::TraitRef
::from_lang_item(self.tcx(), LangItem
::Sized
, cause
.span
, [output_ty
]);
684 nested
.push(Obligation
::new(self.infcx
.tcx
, cause
, obligation
.param_env
, tr
));
689 fn confirm_trait_alias_candidate(
691 obligation
: &PolyTraitObligation
<'tcx
>,
692 ) -> Vec
<PredicateObligation
<'tcx
>> {
693 debug
!(?obligation
, "confirm_trait_alias_candidate");
695 let predicate
= self.infcx
.instantiate_binder_with_placeholders(obligation
.predicate
);
696 let trait_ref
= predicate
.trait_ref
;
697 let trait_def_id
= trait_ref
.def_id
;
698 let args
= trait_ref
.args
;
700 let trait_obligations
= self.impl_or_trait_obligations(
702 obligation
.recursion_depth
,
703 obligation
.param_env
,
706 obligation
.predicate
,
709 debug
!(?trait_def_id
, ?trait_obligations
, "trait alias obligations");
714 fn confirm_generator_candidate(
716 obligation
: &PolyTraitObligation
<'tcx
>,
717 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
718 // Okay to skip binder because the args on generator types never
719 // touch bound regions, they just capture the in-scope
720 // type/region parameters.
721 let self_ty
= self.infcx
.shallow_resolve(obligation
.self_ty().skip_binder());
722 let ty
::Generator(generator_def_id
, args
, _
) = *self_ty
.kind() else {
723 bug
!("closure candidate for non-closure {:?}", obligation
);
726 debug
!(?obligation
, ?generator_def_id
, ?args
, "confirm_generator_candidate");
728 let gen_sig
= args
.as_generator().poly_sig();
730 // NOTE: The self-type is a generator type and hence is
731 // in fact unparameterized (or at least does not reference any
732 // regions bound in the obligation).
733 let self_ty
= obligation
737 .expect("unboxed closure type should not capture bound vars from the predicate");
739 let trait_ref
= super::util
::generator_trait_ref_and_outputs(
741 obligation
.predicate
.def_id(),
745 .map_bound(|(trait_ref
, ..)| trait_ref
);
747 let nested
= self.confirm_poly_trait_refs(obligation
, trait_ref
)?
;
748 debug
!(?trait_ref
, ?nested
, "generator candidate obligations");
753 fn confirm_future_candidate(
755 obligation
: &PolyTraitObligation
<'tcx
>,
756 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
757 // Okay to skip binder because the args on generator types never
758 // touch bound regions, they just capture the in-scope
759 // type/region parameters.
760 let self_ty
= self.infcx
.shallow_resolve(obligation
.self_ty().skip_binder());
761 let ty
::Generator(generator_def_id
, args
, _
) = *self_ty
.kind() else {
762 bug
!("closure candidate for non-closure {:?}", obligation
);
765 debug
!(?obligation
, ?generator_def_id
, ?args
, "confirm_future_candidate");
767 let gen_sig
= args
.as_generator().poly_sig();
769 let trait_ref
= super::util
::future_trait_ref_and_outputs(
771 obligation
.predicate
.def_id(),
772 obligation
.predicate
.no_bound_vars().expect("future has no bound vars").self_ty(),
775 .map_bound(|(trait_ref
, ..)| trait_ref
);
777 let nested
= self.confirm_poly_trait_refs(obligation
, trait_ref
)?
;
778 debug
!(?trait_ref
, ?nested
, "future candidate obligations");
783 #[instrument(skip(self), level = "debug")]
784 fn confirm_closure_candidate(
786 obligation
: &PolyTraitObligation
<'tcx
>,
787 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
790 .fn_trait_kind_from_def_id(obligation
.predicate
.def_id())
791 .unwrap_or_else(|| bug
!("closure candidate for non-fn trait {:?}", obligation
));
793 // Okay to skip binder because the args on closure types never
794 // touch bound regions, they just capture the in-scope
795 // type/region parameters.
796 let self_ty
= self.infcx
.shallow_resolve(obligation
.self_ty().skip_binder());
797 let ty
::Closure(closure_def_id
, args
) = *self_ty
.kind() else {
798 bug
!("closure candidate for non-closure {:?}", obligation
);
801 let trait_ref
= self.closure_trait_ref_unnormalized(obligation
, args
);
802 let mut nested
= self.confirm_poly_trait_refs(obligation
, trait_ref
)?
;
804 debug
!(?closure_def_id
, ?trait_ref
, ?nested
, "confirm closure candidate obligations");
806 nested
.push(obligation
.with(
808 ty
::Binder
::dummy(ty
::PredicateKind
::ClosureKind(closure_def_id
, args
, kind
)),
814 /// In the case of closure types and fn pointers,
815 /// we currently treat the input type parameters on the trait as
816 /// outputs. This means that when we have a match we have only
817 /// considered the self type, so we have to go back and make sure
818 /// to relate the argument types too. This is kind of wrong, but
819 /// since we control the full set of impls, also not that wrong,
820 /// and it DOES yield better error messages (since we don't report
821 /// errors as if there is no applicable impl, but rather report
822 /// errors are about mismatched argument types.
824 /// Here is an example. Imagine we have a closure expression
825 /// and we desugared it so that the type of the expression is
826 /// `Closure`, and `Closure` expects `i32` as argument. Then it
827 /// is "as if" the compiler generated this impl:
828 /// ```ignore (illustrative)
829 /// impl Fn(i32) for Closure { ... }
831 /// Now imagine our obligation is `Closure: Fn(usize)`. So far
832 /// we have matched the self type `Closure`. At this point we'll
833 /// compare the `i32` to `usize` and generate an error.
835 /// Note that this checking occurs *after* the impl has selected,
836 /// because these output type parameters should not affect the
837 /// selection of the impl. Therefore, if there is a mismatch, we
838 /// report an error to the user.
839 #[instrument(skip(self), level = "trace")]
840 fn confirm_poly_trait_refs(
842 obligation
: &PolyTraitObligation
<'tcx
>,
843 self_ty_trait_ref
: ty
::PolyTraitRef
<'tcx
>,
844 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
845 let obligation_trait_ref
= obligation
.predicate
.to_poly_trait_ref();
846 // Normalize the obligation and expected trait refs together, because why not
847 let Normalized { obligations: nested, value: (obligation_trait_ref, expected_trait_ref) }
=
848 ensure_sufficient_stack(|| {
849 normalize_with_depth(
851 obligation
.param_env
,
852 obligation
.cause
.clone(),
853 obligation
.recursion_depth
+ 1,
854 (obligation_trait_ref
, self_ty_trait_ref
),
858 // needed to define opaque types for tests/ui/type-alias-impl-trait/assoc-projection-ice.rs
860 .at(&obligation
.cause
, obligation
.param_env
)
861 .sup(DefineOpaqueTypes
::Yes
, obligation_trait_ref
, expected_trait_ref
)
862 .map(|InferOk { mut obligations, .. }
| {
863 obligations
.extend(nested
);
867 OutputTypeParameterMismatch(Box
::new(SelectionOutputTypeParameterMismatch
{
868 expected_trait_ref
: obligation_trait_ref
,
869 found_trait_ref
: expected_trait_ref
,
875 fn confirm_trait_upcasting_unsize_candidate(
877 obligation
: &PolyTraitObligation
<'tcx
>,
879 ) -> Result
<ImplSource
<'tcx
, PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
880 let tcx
= self.tcx();
882 // `assemble_candidates_for_unsizing` should ensure there are no late-bound
883 // regions here. See the comment there for more details.
884 let predicate
= obligation
.predicate
.no_bound_vars().unwrap();
885 let a_ty
= self.infcx
.shallow_resolve(predicate
.self_ty());
886 let b_ty
= self.infcx
.shallow_resolve(predicate
.trait_ref
.args
.type_at(1));
888 let ty
::Dynamic(a_data
, a_region
, ty
::Dyn
) = *a_ty
.kind() else { bug!() }
;
889 let ty
::Dynamic(b_data
, b_region
, ty
::Dyn
) = *b_ty
.kind() else { bug!() }
;
891 let source_principal
= a_data
.principal().unwrap().with_self_ty(tcx
, a_ty
);
892 let unnormalized_upcast_principal
=
893 util
::supertraits(tcx
, source_principal
).nth(idx
).unwrap();
896 .match_upcast_principal(
898 unnormalized_upcast_principal
,
904 .expect("did not expect ambiguity during confirmation");
906 let vtable_segment_callback
= {
907 let mut vptr_offset
= 0;
910 VtblSegment
::MetadataDSA
=> {
911 vptr_offset
+= TyCtxt
::COMMON_VTABLE_ENTRIES
.len();
913 VtblSegment
::TraitOwnEntries { trait_ref, emit_vptr }
=> {
914 vptr_offset
+= count_own_vtable_entries(tcx
, trait_ref
);
915 if trait_ref
== unnormalized_upcast_principal
{
917 return ControlFlow
::Break(Some(vptr_offset
));
919 return ControlFlow
::Break(None
);
928 ControlFlow
::Continue(())
932 let vtable_vptr_slot
=
933 prepare_vtable_segments(tcx
, source_principal
, vtable_segment_callback
).unwrap();
935 Ok(ImplSource
::Builtin(BuiltinImplSource
::TraitUpcasting { vtable_vptr_slot }
, nested
))
938 fn confirm_builtin_unsize_candidate(
940 obligation
: &PolyTraitObligation
<'tcx
>,
941 ) -> Result
<ImplSource
<'tcx
, PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
942 let tcx
= self.tcx();
944 // `assemble_candidates_for_unsizing` should ensure there are no late-bound
945 // regions here. See the comment there for more details.
946 let source
= self.infcx
.shallow_resolve(obligation
.self_ty().no_bound_vars().unwrap());
947 let target
= obligation
.predicate
.skip_binder().trait_ref
.args
.type_at(1);
948 let target
= self.infcx
.shallow_resolve(target
);
949 debug
!(?source
, ?target
, "confirm_builtin_unsize_candidate");
951 Ok(match (source
.kind(), target
.kind()) {
952 // Trait+Kx+'a -> Trait+Ky+'b (auto traits and lifetime subtyping).
953 (&ty
::Dynamic(ref data_a
, r_a
, dyn_a
), &ty
::Dynamic(ref data_b
, r_b
, dyn_b
))
956 // See `assemble_candidates_for_unsizing` for more info.
957 // We already checked the compatibility of auto traits within `assemble_candidates_for_unsizing`.
960 .map(|b
| b
.map_bound(ty
::ExistentialPredicate
::Trait
))
965 .map(|b
| b
.map_bound(ty
::ExistentialPredicate
::Projection
)),
970 .map(ty
::ExistentialPredicate
::AutoTrait
)
971 .map(ty
::Binder
::dummy
),
973 let existential_predicates
= tcx
.mk_poly_existential_predicates_from_iter(iter
);
974 let source_trait
= Ty
::new_dynamic(tcx
, existential_predicates
, r_b
, dyn_a
);
976 // Require that the traits involved in this upcast are **equal**;
977 // only the **lifetime bound** is changed.
978 let InferOk { mut obligations, .. }
= self
980 .at(&obligation
.cause
, obligation
.param_env
)
981 .sup(DefineOpaqueTypes
::No
, target
, source_trait
)
982 .map_err(|_
| Unimplemented
)?
;
984 // Register one obligation for 'a: 'b.
985 let outlives
= ty
::OutlivesPredicate(r_a
, r_b
);
986 obligations
.push(Obligation
::with_depth(
988 obligation
.cause
.clone(),
989 obligation
.recursion_depth
+ 1,
990 obligation
.param_env
,
991 obligation
.predicate
.rebind(outlives
),
994 ImplSource
::Builtin(BuiltinImplSource
::Misc
, obligations
)
998 (_
, &ty
::Dynamic(ref data
, r
, ty
::Dyn
)) => {
999 let mut object_dids
= data
.auto_traits().chain(data
.principal_def_id());
1000 if let Some(did
) = object_dids
.find(|did
| !tcx
.check_is_object_safe(*did
)) {
1001 return Err(TraitNotObjectSafe(did
));
1004 let predicate_to_obligation
= |predicate
| {
1005 Obligation
::with_depth(
1007 obligation
.cause
.clone(),
1008 obligation
.recursion_depth
+ 1,
1009 obligation
.param_env
,
1014 // Create obligations:
1015 // - Casting `T` to `Trait`
1016 // - For all the various builtin bounds attached to the object cast. (In other
1017 // words, if the object type is `Foo + Send`, this would create an obligation for
1018 // the `Send` check.)
1019 // - Projection predicates
1020 let mut nested
: Vec
<_
> = data
1022 .map(|predicate
| predicate_to_obligation(predicate
.with_self_ty(tcx
, source
)))
1025 // We can only make objects from sized types.
1026 let tr
= ty
::TraitRef
::from_lang_item(
1029 obligation
.cause
.span
,
1032 nested
.push(predicate_to_obligation(tr
.to_predicate(tcx
)));
1034 // If the type is `Foo + 'a`, ensure that the type
1035 // being cast to `Foo + 'a` outlives `'a`:
1036 let outlives
= ty
::OutlivesPredicate(source
, r
);
1037 nested
.push(predicate_to_obligation(
1038 ty
::Binder
::dummy(ty
::ClauseKind
::TypeOutlives(outlives
)).to_predicate(tcx
),
1041 ImplSource
::Builtin(BuiltinImplSource
::Misc
, nested
)
1044 // `[T; n]` -> `[T]`
1045 (&ty
::Array(a
, _
), &ty
::Slice(b
)) => {
1046 let InferOk { obligations, .. }
= self
1048 .at(&obligation
.cause
, obligation
.param_env
)
1049 .eq(DefineOpaqueTypes
::No
, b
, a
)
1050 .map_err(|_
| Unimplemented
)?
;
1052 ImplSource
::Builtin(BuiltinImplSource
::Misc
, obligations
)
1055 // `Struct<T>` -> `Struct<U>`
1056 (&ty
::Adt(def
, args_a
), &ty
::Adt(_
, args_b
)) => {
1057 let unsizing_params
= tcx
.unsizing_params_for_adt(def
.did());
1058 if unsizing_params
.is_empty() {
1059 return Err(Unimplemented
);
1062 let tail_field
= def
.non_enum_variant().tail();
1063 let tail_field_ty
= tcx
.type_of(tail_field
.did
);
1065 let mut nested
= vec
![];
1067 // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`,
1068 // normalizing in the process, since `type_of` returns something directly from
1069 // astconv (which means it's un-normalized).
1070 let source_tail
= normalize_with_depth_to(
1072 obligation
.param_env
,
1073 obligation
.cause
.clone(),
1074 obligation
.recursion_depth
+ 1,
1075 tail_field_ty
.instantiate(tcx
, args_a
),
1078 let target_tail
= normalize_with_depth_to(
1080 obligation
.param_env
,
1081 obligation
.cause
.clone(),
1082 obligation
.recursion_depth
+ 1,
1083 tail_field_ty
.instantiate(tcx
, args_b
),
1087 // Check that the source struct with the target's
1088 // unsizing parameters is equal to the target.
1090 tcx
.mk_args_from_iter(args_a
.iter().enumerate().map(|(i
, k
)| {
1091 if unsizing_params
.contains(i
as u32) { args_b[i] }
else { k }
1093 let new_struct
= Ty
::new_adt(tcx
, def
, args
);
1094 let InferOk { obligations, .. }
= self
1096 .at(&obligation
.cause
, obligation
.param_env
)
1097 .eq(DefineOpaqueTypes
::No
, target
, new_struct
)
1098 .map_err(|_
| Unimplemented
)?
;
1099 nested
.extend(obligations
);
1101 // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate.
1102 let tail_unsize_obligation
= obligation
.with(
1106 obligation
.predicate
.def_id(),
1107 [source_tail
, target_tail
],
1110 nested
.push(tail_unsize_obligation
);
1112 ImplSource
::Builtin(BuiltinImplSource
::Misc
, nested
)
1115 // `(.., T)` -> `(.., U)`
1116 (&ty
::Tuple(tys_a
), &ty
::Tuple(tys_b
)) => {
1117 assert_eq
!(tys_a
.len(), tys_b
.len());
1119 // The last field of the tuple has to exist.
1120 let (&a_last
, a_mid
) = tys_a
.split_last().ok_or(Unimplemented
)?
;
1121 let &b_last
= tys_b
.last().unwrap();
1123 // Check that the source tuple with the target's
1124 // last element is equal to the target.
1126 Ty
::new_tup_from_iter(tcx
, a_mid
.iter().copied().chain(iter
::once(b_last
)));
1127 let InferOk { mut obligations, .. }
= self
1129 .at(&obligation
.cause
, obligation
.param_env
)
1130 .eq(DefineOpaqueTypes
::No
, target
, new_tuple
)
1131 .map_err(|_
| Unimplemented
)?
;
1133 // Add a nested `T: Unsize<U>` predicate.
1134 let last_unsize_obligation
= obligation
.with(
1136 ty
::TraitRef
::new(tcx
, obligation
.predicate
.def_id(), [a_last
, b_last
]),
1138 obligations
.push(last_unsize_obligation
);
1140 ImplSource
::Builtin(BuiltinImplSource
::TupleUnsizing
, obligations
)
1143 _
=> bug
!("source: {source}, target: {target}"),
1147 fn confirm_const_destruct_candidate(
1149 obligation
: &PolyTraitObligation
<'tcx
>,
1150 impl_def_id
: Option
<DefId
>,
1151 ) -> Result
<Vec
<PredicateObligation
<'tcx
>>, SelectionError
<'tcx
>> {
1152 // `~const Destruct` in a non-const environment is always trivially true, since our type is `Drop`
1158 let drop_trait
= self.tcx().require_lang_item(LangItem
::Drop
, None
);
1160 let tcx
= self.tcx();
1161 let self_ty
= self.infcx
.shallow_resolve(obligation
.self_ty());
1163 let mut nested
= vec
![];
1164 let cause
= obligation
.derived_cause(BuiltinDerivedObligation
);
1166 // If we have a custom `impl const Drop`, then
1167 // first check it like a regular impl candidate.
1168 // This is copied from confirm_impl_candidate but remaps the predicate to `~const Drop` beforehand.
1169 if let Some(impl_def_id
) = impl_def_id
{
1170 let mut new_obligation
= obligation
.clone();
1171 new_obligation
.predicate
= new_obligation
.predicate
.map_bound(|mut trait_pred
| {
1172 trait_pred
.trait_ref
.def_id
= drop_trait
;
1175 let args
= self.rematch_impl(impl_def_id
, &new_obligation
);
1176 debug
!(?args
, "impl args");
1178 let cause
= obligation
.derived_cause(|derived
| {
1179 ImplDerivedObligation(Box
::new(ImplDerivedObligationCause
{
1181 impl_or_alias_def_id
: impl_def_id
,
1182 impl_def_predicate_index
: None
,
1183 span
: obligation
.cause
.span
,
1186 let obligations
= ensure_sufficient_stack(|| {
1191 new_obligation
.recursion_depth
+ 1,
1192 new_obligation
.param_env
,
1193 obligation
.predicate
,
1196 nested
.extend(obligations
.nested
);
1199 // We want to confirm the ADT's fields if we have an ADT
1200 let mut stack
= match *self_ty
.skip_binder().kind() {
1201 ty
::Adt(def
, args
) => def
.all_fields().map(|f
| f
.ty(tcx
, args
)).collect(),
1202 _
=> vec
![self_ty
.skip_binder()],
1205 while let Some(nested_ty
) = stack
.pop() {
1206 match *nested_ty
.kind() {
1207 // We know these types are trivially drop
1213 | ty
::Infer(ty
::IntVar(_
))
1214 | ty
::Infer(ty
::FloatVar(_
))
1221 | ty
::Foreign(_
) => {}
1223 // `ManuallyDrop` is trivially drop
1224 ty
::Adt(def
, _
) if Some(def
.did()) == tcx
.lang_items().manually_drop() => {}
1226 // These types are built-in, so we can fast-track by registering
1227 // nested predicates for their constituent type(s)
1228 ty
::Array(ty
, _
) | ty
::Slice(ty
) => {
1232 stack
.extend(tys
.iter());
1234 ty
::Closure(_
, args
) => {
1235 stack
.push(args
.as_closure().tupled_upvars_ty());
1237 ty
::Generator(_
, args
, _
) => {
1238 let generator
= args
.as_generator();
1239 stack
.extend([generator
.tupled_upvars_ty(), generator
.witness()]);
1241 ty
::GeneratorWitness(def_id
, args
) => {
1242 let tcx
= self.tcx();
1243 stack
.extend(tcx
.generator_hidden_types(def_id
).map(|bty
| {
1244 let ty
= bty
.instantiate(tcx
, args
);
1245 debug_assert
!(!ty
.has_late_bound_regions());
1250 // If we have a projection type, make sure to normalize it so we replace it
1251 // with a fresh infer variable
1252 ty
::Alias(ty
::Projection
| ty
::Inherent
, ..) => {
1253 // FIXME(effects) this needs constness
1254 let predicate
= normalize_with_depth_to(
1256 obligation
.param_env
,
1258 obligation
.recursion_depth
+ 1,
1259 self_ty
.rebind(ty
::TraitPredicate
{
1260 trait_ref
: ty
::TraitRef
::from_lang_item(
1266 polarity
: ty
::ImplPolarity
::Positive
,
1271 nested
.push(Obligation
::with_depth(
1274 obligation
.recursion_depth
+ 1,
1275 obligation
.param_env
,
1280 // If we have any other type (e.g. an ADT), just register a nested obligation
1281 // since it's either not `const Drop` (and we raise an error during selection),
1282 // or it's an ADT (and we need to check for a custom impl during selection)
1284 // FIXME(effects) this needs constness
1285 let predicate
= self_ty
.rebind(ty
::TraitPredicate
{
1286 trait_ref
: ty
::TraitRef
::from_lang_item(
1292 polarity
: ty
::ImplPolarity
::Positive
,
1295 nested
.push(Obligation
::with_depth(
1298 obligation
.recursion_depth
+ 1,
1299 obligation
.param_env
,