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_data_structures::stack::ensure_sufficient_stack;
10 use rustc_hir::lang_items::LangItem;
11 use rustc_index::bit_set::GrowableBitSet;
12 use rustc_infer::infer::{self, InferOk};
13 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst, SubstsRef};
14 use rustc_middle::ty::{self, Ty};
15 use rustc_middle::ty::{ToPolyTraitRef, ToPredicate, WithConstness};
16 use rustc_span::def_id::DefId;
18 use crate::traits::project::{self, normalize_with_depth};
19 use crate::traits::select::TraitObligationExt;
20 use crate::traits::util;
21 use crate::traits::util::{closure_trait_ref_and_return_type, predicate_for_trait_def};
22 use crate::traits::ImplSource;
23 use crate::traits::Normalized;
24 use crate::traits::OutputTypeParameterMismatch;
25 use crate::traits::Selection;
26 use crate::traits::TraitNotObjectSafe;
27 use crate::traits::{BuiltinDerivedObligation, ImplDerivedObligation};
29 ImplSourceAutoImplData, ImplSourceBuiltinData, ImplSourceClosureData,
30 ImplSourceDiscriminantKindData, ImplSourceFnPointerData, ImplSourceGeneratorData,
31 ImplSourceObjectData, ImplSourceTraitAliasData, ImplSourceUserDefinedData,
33 use crate::traits::{ObjectCastObligation, PredicateObligation, TraitObligation};
34 use crate::traits::{Obligation, ObligationCause};
35 use crate::traits::{SelectionError, Unimplemented};
37 use super::BuiltinImplConditions;
38 use super::SelectionCandidate::{self, *};
39 use super::SelectionContext;
43 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
44 pub(super) fn confirm_candidate(
46 obligation: &TraitObligation<'tcx>,
47 candidate: SelectionCandidate<'tcx>,
48 ) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
49 debug!("confirm_candidate({:?}, {:?})", obligation, candidate);
52 BuiltinCandidate { has_nested } => {
53 let data = self.confirm_builtin_candidate(obligation, has_nested);
54 Ok(ImplSource::Builtin(data))
57 ParamCandidate(param) => {
58 let obligations = self.confirm_param_candidate(obligation, param);
59 Ok(ImplSource::Param(obligations))
62 ImplCandidate(impl_def_id) => {
63 Ok(ImplSource::UserDefined(self.confirm_impl_candidate(obligation, impl_def_id)))
66 AutoImplCandidate(trait_def_id) => {
67 let data = self.confirm_auto_impl_candidate(obligation, trait_def_id);
68 Ok(ImplSource::AutoImpl(data))
71 ProjectionCandidate => {
72 let obligations = self.confirm_projection_candidate(obligation);
73 Ok(ImplSource::Param(obligations))
77 let vtable_closure = self.confirm_closure_candidate(obligation)?;
78 Ok(ImplSource::Closure(vtable_closure))
81 GeneratorCandidate => {
82 let vtable_generator = self.confirm_generator_candidate(obligation)?;
83 Ok(ImplSource::Generator(vtable_generator))
86 FnPointerCandidate => {
87 let data = self.confirm_fn_pointer_candidate(obligation)?;
88 Ok(ImplSource::FnPointer(data))
91 DiscriminantKindCandidate => {
92 Ok(ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData))
95 TraitAliasCandidate(alias_def_id) => {
96 let data = self.confirm_trait_alias_candidate(obligation, alias_def_id);
97 Ok(ImplSource::TraitAlias(data))
101 let data = self.confirm_object_candidate(obligation);
102 Ok(ImplSource::Object(data))
105 BuiltinObjectCandidate => {
106 // This indicates something like `Trait + Send: Send`. In this case, we know that
107 // this holds because that's what the object type is telling us, and there's really
108 // no additional obligations to prove and no types in particular to unify, etc.
109 Ok(ImplSource::Param(Vec::new()))
112 BuiltinUnsizeCandidate => {
113 let data = self.confirm_builtin_unsize_candidate(obligation)?;
114 Ok(ImplSource::Builtin(data))
119 fn confirm_projection_candidate(
121 obligation: &TraitObligation<'tcx>,
122 ) -> Vec<PredicateObligation<'tcx>> {
123 self.infcx.commit_unconditionally(|_| {
125 .match_projection_obligation_against_definition_bounds(obligation)
126 .unwrap_or_else(|| bug!("Can't find selected projection candidate"));
127 let mut obligations = self
129 .at(&obligation.cause, obligation.param_env)
130 .sup(obligation.predicate.to_poly_trait_ref(), candidate)
131 .map(|InferOk { obligations, .. }| obligations)
132 .unwrap_or_else(|_| {
134 "Projection bound `{:?}` was applicable to `{:?}` but now is not",
139 // Require that the projection is well-formed.
140 let self_ty = obligation.predicate.skip_binder().self_ty();
141 obligations.push(Obligation::new(
142 obligation.cause.clone(),
143 obligation.param_env,
144 ty::PredicateKind::WellFormed(self_ty.into()).to_predicate(self.tcx()),
150 fn confirm_param_candidate(
152 obligation: &TraitObligation<'tcx>,
153 param: ty::PolyTraitRef<'tcx>,
154 ) -> Vec<PredicateObligation<'tcx>> {
155 debug!("confirm_param_candidate({:?},{:?})", obligation, param);
157 // During evaluation, we already checked that this
158 // where-clause trait-ref could be unified with the obligation
159 // trait-ref. Repeat that unification now without any
160 // transactional boundary; it should not fail.
161 match self.match_where_clause_trait_ref(obligation, param) {
162 Ok(obligations) => obligations,
165 "Where clause `{:?}` was applicable to `{:?}` but now is not",
173 fn confirm_builtin_candidate(
175 obligation: &TraitObligation<'tcx>,
177 ) -> ImplSourceBuiltinData<PredicateObligation<'tcx>> {
178 debug!("confirm_builtin_candidate({:?}, {:?})", obligation, has_nested);
180 let lang_items = self.tcx().lang_items();
181 let obligations = if has_nested {
182 let trait_def = obligation.predicate.def_id();
183 let conditions = if Some(trait_def) == lang_items.sized_trait() {
184 self.sized_conditions(obligation)
185 } else if Some(trait_def) == lang_items.copy_trait() {
186 self.copy_clone_conditions(obligation)
187 } else if Some(trait_def) == lang_items.clone_trait() {
188 self.copy_clone_conditions(obligation)
190 bug!("unexpected builtin trait {:?}", trait_def)
192 let nested = match conditions {
193 BuiltinImplConditions::Where(nested) => nested,
194 _ => bug!("obligation {:?} had matched a builtin impl but now doesn't", obligation),
197 let cause = obligation.derived_cause(BuiltinDerivedObligation);
198 ensure_sufficient_stack(|| {
199 self.collect_predicates_for_types(
200 obligation.param_env,
202 obligation.recursion_depth + 1,
211 debug!("confirm_builtin_candidate: obligations={:?}", obligations);
213 ImplSourceBuiltinData { nested: obligations }
216 /// This handles the case where a `auto trait Foo` impl is being used.
217 /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
219 /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
220 /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
221 fn confirm_auto_impl_candidate(
223 obligation: &TraitObligation<'tcx>,
225 ) -> ImplSourceAutoImplData<PredicateObligation<'tcx>> {
226 debug!("confirm_auto_impl_candidate({:?}, {:?})", obligation, trait_def_id);
228 let types = obligation.predicate.map_bound(|inner| {
229 let self_ty = self.infcx.shallow_resolve(inner.self_ty());
230 self.constituent_types_for_ty(self_ty)
232 self.vtable_auto_impl(obligation, trait_def_id, types)
235 /// See `confirm_auto_impl_candidate`.
238 obligation: &TraitObligation<'tcx>,
240 nested: ty::Binder<Vec<Ty<'tcx>>>,
241 ) -> ImplSourceAutoImplData<PredicateObligation<'tcx>> {
242 debug!("vtable_auto_impl: nested={:?}", nested);
243 ensure_sufficient_stack(|| {
244 let cause = obligation.derived_cause(BuiltinDerivedObligation);
245 let mut obligations = self.collect_predicates_for_types(
246 obligation.param_env,
248 obligation.recursion_depth + 1,
253 let trait_obligations: Vec<PredicateObligation<'_>> =
254 self.infcx.commit_unconditionally(|_| {
255 let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
257 self.infcx.replace_bound_vars_with_placeholders(&poly_trait_ref);
258 let cause = obligation.derived_cause(ImplDerivedObligation);
259 self.impl_or_trait_obligations(
261 obligation.recursion_depth + 1,
262 obligation.param_env,
268 // Adds the predicates from the trait. Note that this contains a `Self: Trait`
269 // predicate as usual. It won't have any effect since auto traits are coinductive.
270 obligations.extend(trait_obligations);
272 debug!("vtable_auto_impl: obligations={:?}", obligations);
274 ImplSourceAutoImplData { trait_def_id, nested: obligations }
278 fn confirm_impl_candidate(
280 obligation: &TraitObligation<'tcx>,
282 ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
283 debug!("confirm_impl_candidate({:?},{:?})", obligation, impl_def_id);
285 // First, create the substitutions by matching the impl again,
286 // this time not in a probe.
287 self.infcx.commit_unconditionally(|_| {
288 let substs = self.rematch_impl(impl_def_id, obligation);
289 debug!("confirm_impl_candidate: substs={:?}", substs);
290 let cause = obligation.derived_cause(ImplDerivedObligation);
291 ensure_sufficient_stack(|| {
296 obligation.recursion_depth + 1,
297 obligation.param_env,
306 mut substs: Normalized<'tcx, SubstsRef<'tcx>>,
307 cause: ObligationCause<'tcx>,
308 recursion_depth: usize,
309 param_env: ty::ParamEnv<'tcx>,
310 ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
312 "vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={})",
313 impl_def_id, substs, recursion_depth,
316 let mut impl_obligations = self.impl_or_trait_obligations(
325 "vtable_impl: impl_def_id={:?} impl_obligations={:?}",
326 impl_def_id, impl_obligations
329 // Because of RFC447, the impl-trait-ref and obligations
330 // are sufficient to determine the impl substs, without
331 // relying on projections in the impl-trait-ref.
333 // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
334 impl_obligations.append(&mut substs.obligations);
336 ImplSourceUserDefinedData { impl_def_id, substs: substs.value, nested: impl_obligations }
339 fn confirm_object_candidate(
341 obligation: &TraitObligation<'tcx>,
342 ) -> ImplSourceObjectData<'tcx, PredicateObligation<'tcx>> {
343 debug!("confirm_object_candidate({:?})", obligation);
345 let self_ty = self.infcx.replace_bound_vars_with_placeholders(&obligation.self_ty());
346 let data = match self_ty.kind() {
347 ty::Dynamic(data, ..) => data,
348 _ => span_bug!(obligation.cause.span, "object candidate with non-object"),
351 let poly_trait_ref = data
354 span_bug!(obligation.cause.span, "object candidate with no principal")
356 .with_self_ty(self.tcx(), self_ty);
358 let mut upcast_trait_ref = None;
359 let mut nested = vec![];
363 let tcx = self.tcx();
365 // We want to find the first supertrait in the list of
366 // supertraits that we can unify with, and do that
367 // unification. We know that there is exactly one in the list
368 // where we can unify, because otherwise select would have
369 // reported an ambiguity. (When we do find a match, also
370 // record it for later.)
371 let nonmatching = util::supertraits(tcx, poly_trait_ref).take_while(|&t| {
372 match self.infcx.commit_if_ok(|_| self.match_poly_trait_ref(obligation, t)) {
374 upcast_trait_ref = Some(t);
375 nested.extend(obligations);
382 // Additionally, for each of the non-matching predicates that
383 // we pass over, we sum up the set of number of vtable
384 // entries, so that we can compute the offset for the selected
386 vtable_base = nonmatching.map(|t| super::util::count_own_vtable_entries(tcx, t)).sum();
389 for bound in data.skip_binder() {
391 ty::ExistentialPredicate::Projection(projection) => {
392 // This maybe belongs in wf, but that can't (doesn't) handle
393 // higher-ranked things.
394 // Prevent, e.g., `dyn Iterator<Item = str>`.
395 // FIXME(generic_associated_types): We need some way to
396 // ensure that for `dyn for<'a> X<Item<'a> = &'a ()>` the
397 // bound holds for all `'a`.
398 let (infer_projection, _) = self.infcx.replace_bound_vars_with_fresh_vars(
399 obligation.cause.span,
400 infer::HigherRankedType,
401 &ty::Binder::bind(projection),
404 iter::once(self_ty.into()).chain(infer_projection.substs).collect();
406 self.tcx().item_bounds(projection.item_def_id).iter().map(|bound| {
407 // In the example above, `bound` is `<Self as Iterator>::Item: Sized`
408 // `subst_bound` is `str: Sized`.
409 let subst_bound = util::subst_assoc_item_bound(
416 obligation.cause.clone(),
417 obligation.param_env.clone(),
421 debug!("confirm_object_candidate: adding bounds: {:?}", bounds);
422 nested.extend(bounds);
424 ty::ExistentialPredicate::Trait(_) | ty::ExistentialPredicate::AutoTrait(_) => {}
428 debug!("confirm_object_candidate: nested: {:?}", nested);
429 ImplSourceObjectData { upcast_trait_ref: upcast_trait_ref.unwrap(), vtable_base, nested }
432 fn confirm_fn_pointer_candidate(
434 obligation: &TraitObligation<'tcx>,
435 ) -> Result<ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>>
437 debug!("confirm_fn_pointer_candidate({:?})", obligation);
439 // Okay to skip binder; it is reintroduced below.
440 let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
441 let sig = self_ty.fn_sig(self.tcx());
442 let trait_ref = closure_trait_ref_and_return_type(
444 obligation.predicate.def_id(),
447 util::TupleArgumentsFlag::Yes,
449 .map_bound(|(trait_ref, _)| trait_ref);
451 let Normalized { value: trait_ref, obligations } = ensure_sufficient_stack(|| {
452 project::normalize_with_depth(
454 obligation.param_env,
455 obligation.cause.clone(),
456 obligation.recursion_depth + 1,
461 self.confirm_poly_trait_refs(
462 obligation.cause.clone(),
463 obligation.param_env,
464 obligation.predicate.to_poly_trait_ref(),
467 Ok(ImplSourceFnPointerData { fn_ty: self_ty, nested: obligations })
470 fn confirm_trait_alias_candidate(
472 obligation: &TraitObligation<'tcx>,
474 ) -> ImplSourceTraitAliasData<'tcx, PredicateObligation<'tcx>> {
475 debug!("confirm_trait_alias_candidate({:?}, {:?})", obligation, alias_def_id);
477 self.infcx.commit_unconditionally(|_| {
479 self.infcx().replace_bound_vars_with_placeholders(&obligation.predicate);
480 let trait_ref = predicate.trait_ref;
481 let trait_def_id = trait_ref.def_id;
482 let substs = trait_ref.substs;
484 let trait_obligations = self.impl_or_trait_obligations(
485 obligation.cause.clone(),
486 obligation.recursion_depth,
487 obligation.param_env,
493 "confirm_trait_alias_candidate: trait_def_id={:?} trait_obligations={:?}",
494 trait_def_id, trait_obligations
497 ImplSourceTraitAliasData { alias_def_id, substs, nested: trait_obligations }
501 fn confirm_generator_candidate(
503 obligation: &TraitObligation<'tcx>,
504 ) -> Result<ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>>
506 // Okay to skip binder because the substs on generator types never
507 // touch bound regions, they just capture the in-scope
508 // type/region parameters.
509 let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
510 let (generator_def_id, substs) = match *self_ty.kind() {
511 ty::Generator(id, substs, _) => (id, substs),
512 _ => bug!("closure candidate for non-closure {:?}", obligation),
515 debug!("confirm_generator_candidate({:?},{:?},{:?})", obligation, generator_def_id, substs);
517 let trait_ref = self.generator_trait_ref_unnormalized(obligation, substs);
518 let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
519 normalize_with_depth(
521 obligation.param_env,
522 obligation.cause.clone(),
523 obligation.recursion_depth + 1,
529 "confirm_generator_candidate(generator_def_id={:?}, \
530 trait_ref={:?}, obligations={:?})",
531 generator_def_id, trait_ref, obligations
534 obligations.extend(self.confirm_poly_trait_refs(
535 obligation.cause.clone(),
536 obligation.param_env,
537 obligation.predicate.to_poly_trait_ref(),
541 Ok(ImplSourceGeneratorData { generator_def_id, substs, nested: obligations })
544 fn confirm_closure_candidate(
546 obligation: &TraitObligation<'tcx>,
547 ) -> Result<ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
548 debug!("confirm_closure_candidate({:?})", obligation);
552 .fn_trait_kind_from_lang_item(obligation.predicate.def_id())
553 .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation));
555 // Okay to skip binder because the substs on closure types never
556 // touch bound regions, they just capture the in-scope
557 // type/region parameters.
558 let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
559 let (closure_def_id, substs) = match *self_ty.kind() {
560 ty::Closure(id, substs) => (id, substs),
561 _ => bug!("closure candidate for non-closure {:?}", obligation),
564 let trait_ref = self.closure_trait_ref_unnormalized(obligation, substs);
565 let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
566 normalize_with_depth(
568 obligation.param_env,
569 obligation.cause.clone(),
570 obligation.recursion_depth + 1,
576 "confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
577 closure_def_id, trait_ref, obligations
580 obligations.extend(self.confirm_poly_trait_refs(
581 obligation.cause.clone(),
582 obligation.param_env,
583 obligation.predicate.to_poly_trait_ref(),
589 if !self.tcx().sess.opts.debugging_opts.chalk {
590 obligations.push(Obligation::new(
591 obligation.cause.clone(),
592 obligation.param_env,
593 ty::PredicateAtom::ClosureKind(closure_def_id, substs, kind)
594 .to_predicate(self.tcx()),
598 Ok(ImplSourceClosureData { closure_def_id, substs, nested: obligations })
601 /// In the case of closure types and fn pointers,
602 /// we currently treat the input type parameters on the trait as
603 /// outputs. This means that when we have a match we have only
604 /// considered the self type, so we have to go back and make sure
605 /// to relate the argument types too. This is kind of wrong, but
606 /// since we control the full set of impls, also not that wrong,
607 /// and it DOES yield better error messages (since we don't report
608 /// errors as if there is no applicable impl, but rather report
609 /// errors are about mismatched argument types.
611 /// Here is an example. Imagine we have a closure expression
612 /// and we desugared it so that the type of the expression is
613 /// `Closure`, and `Closure` expects `i32` as argument. Then it
614 /// is "as if" the compiler generated this impl:
616 /// impl Fn(i32) for Closure { ... }
618 /// Now imagine our obligation is `Closure: Fn(usize)`. So far
619 /// we have matched the self type `Closure`. At this point we'll
620 /// compare the `i32` to `usize` and generate an error.
622 /// Note that this checking occurs *after* the impl has selected,
623 /// because these output type parameters should not affect the
624 /// selection of the impl. Therefore, if there is a mismatch, we
625 /// report an error to the user.
626 fn confirm_poly_trait_refs(
628 obligation_cause: ObligationCause<'tcx>,
629 obligation_param_env: ty::ParamEnv<'tcx>,
630 obligation_trait_ref: ty::PolyTraitRef<'tcx>,
631 expected_trait_ref: ty::PolyTraitRef<'tcx>,
632 ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
634 .at(&obligation_cause, obligation_param_env)
635 .sup(obligation_trait_ref, expected_trait_ref)
636 .map(|InferOk { obligations, .. }| obligations)
637 .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
640 fn confirm_builtin_unsize_candidate(
642 obligation: &TraitObligation<'tcx>,
643 ) -> Result<ImplSourceBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
644 let tcx = self.tcx();
646 // `assemble_candidates_for_unsizing` should ensure there are no late-bound
647 // regions here. See the comment there for more details.
648 let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
649 let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
650 let target = self.infcx.shallow_resolve(target);
652 debug!("confirm_builtin_unsize_candidate(source={:?}, target={:?})", source, target);
654 let mut nested = vec![];
655 match (source.kind(), target.kind()) {
656 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
657 (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => {
658 // See `assemble_candidates_for_unsizing` for more info.
659 let existential_predicates = data_a.map_bound(|data_a| {
662 .map(ty::ExistentialPredicate::Trait)
664 .chain(data_a.projection_bounds().map(ty::ExistentialPredicate::Projection))
665 .chain(data_b.auto_traits().map(ty::ExistentialPredicate::AutoTrait));
666 tcx.mk_existential_predicates(iter)
668 let source_trait = tcx.mk_dynamic(existential_predicates, r_b);
670 // Require that the traits involved in this upcast are **equal**;
671 // only the **lifetime bound** is changed.
672 let InferOk { obligations, .. } = self
674 .at(&obligation.cause, obligation.param_env)
675 .sup(target, source_trait)
676 .map_err(|_| Unimplemented)?;
677 nested.extend(obligations);
679 // Register one obligation for 'a: 'b.
680 let cause = ObligationCause::new(
681 obligation.cause.span,
682 obligation.cause.body_id,
683 ObjectCastObligation(target),
685 let outlives = ty::OutlivesPredicate(r_a, r_b);
686 nested.push(Obligation::with_depth(
688 obligation.recursion_depth + 1,
689 obligation.param_env,
690 ty::Binder::bind(outlives).to_predicate(tcx),
695 (_, &ty::Dynamic(ref data, r)) => {
696 let mut object_dids = data.auto_traits().chain(data.principal_def_id());
697 if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) {
698 return Err(TraitNotObjectSafe(did));
701 let cause = ObligationCause::new(
702 obligation.cause.span,
703 obligation.cause.body_id,
704 ObjectCastObligation(target),
707 let predicate_to_obligation = |predicate| {
708 Obligation::with_depth(
710 obligation.recursion_depth + 1,
711 obligation.param_env,
716 // Create obligations:
717 // - Casting `T` to `Trait`
718 // - For all the various builtin bounds attached to the object cast. (In other
719 // words, if the object type is `Foo + Send`, this would create an obligation for
720 // the `Send` check.)
721 // - Projection predicates
723 data.iter().map(|predicate| {
724 predicate_to_obligation(predicate.with_self_ty(tcx, source))
728 // We can only make objects from sized types.
729 let tr = ty::TraitRef::new(
730 tcx.require_lang_item(LangItem::Sized, None),
731 tcx.mk_substs_trait(source, &[]),
733 nested.push(predicate_to_obligation(tr.without_const().to_predicate(tcx)));
735 // If the type is `Foo + 'a`, ensure that the type
736 // being cast to `Foo + 'a` outlives `'a`:
737 let outlives = ty::OutlivesPredicate(source, r);
738 nested.push(predicate_to_obligation(ty::Binder::dummy(outlives).to_predicate(tcx)));
742 (&ty::Array(a, _), &ty::Slice(b)) => {
743 let InferOk { obligations, .. } = self
745 .at(&obligation.cause, obligation.param_env)
747 .map_err(|_| Unimplemented)?;
748 nested.extend(obligations);
751 // `Struct<T>` -> `Struct<U>`
752 (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => {
753 let maybe_unsizing_param_idx = |arg: GenericArg<'tcx>| match arg.unpack() {
754 GenericArgKind::Type(ty) => match ty.kind() {
755 ty::Param(p) => Some(p.index),
759 // Lifetimes aren't allowed to change during unsizing.
760 GenericArgKind::Lifetime(_) => None,
762 GenericArgKind::Const(ct) => match ct.val {
763 ty::ConstKind::Param(p) => Some(p.index),
768 // The last field of the structure has to exist and contain type/const parameters.
769 let (tail_field, prefix_fields) =
770 def.non_enum_variant().fields.split_last().ok_or(Unimplemented)?;
771 let tail_field_ty = tcx.type_of(tail_field.did);
773 let mut unsizing_params = GrowableBitSet::new_empty();
774 let mut found = false;
775 for arg in tail_field_ty.walk() {
776 if let Some(i) = maybe_unsizing_param_idx(arg) {
777 unsizing_params.insert(i);
782 return Err(Unimplemented);
785 // Ensure none of the other fields mention the parameters used
787 // FIXME(eddyb) cache this (including computing `unsizing_params`)
788 // by putting it in a query; it would only need the `DefId` as it
789 // looks at declared field types, not anything substituted.
790 for field in prefix_fields {
791 for arg in tcx.type_of(field.did).walk() {
792 if let Some(i) = maybe_unsizing_param_idx(arg) {
793 if unsizing_params.contains(i) {
794 return Err(Unimplemented);
800 // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
801 let source_tail = tail_field_ty.subst(tcx, substs_a);
802 let target_tail = tail_field_ty.subst(tcx, substs_b);
804 // Check that the source struct with the target's
805 // unsizing parameters is equal to the target.
806 let substs = tcx.mk_substs(substs_a.iter().enumerate().map(|(i, k)| {
807 if unsizing_params.contains(i as u32) { substs_b[i] } else { k }
809 let new_struct = tcx.mk_adt(def, substs);
810 let InferOk { obligations, .. } = self
812 .at(&obligation.cause, obligation.param_env)
813 .eq(target, new_struct)
814 .map_err(|_| Unimplemented)?;
815 nested.extend(obligations);
817 // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate.
818 nested.push(predicate_for_trait_def(
820 obligation.param_env,
821 obligation.cause.clone(),
822 obligation.predicate.def_id(),
823 obligation.recursion_depth + 1,
825 &[target_tail.into()],
829 // `(.., T)` -> `(.., U)`
830 (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
831 assert_eq!(tys_a.len(), tys_b.len());
833 // The last field of the tuple has to exist.
834 let (&a_last, a_mid) = tys_a.split_last().ok_or(Unimplemented)?;
835 let &b_last = tys_b.last().unwrap();
837 // Check that the source tuple with the target's
838 // last element is equal to the target.
839 let new_tuple = tcx.mk_tup(
840 a_mid.iter().map(|k| k.expect_ty()).chain(iter::once(b_last.expect_ty())),
842 let InferOk { obligations, .. } = self
844 .at(&obligation.cause, obligation.param_env)
845 .eq(target, new_tuple)
846 .map_err(|_| Unimplemented)?;
847 nested.extend(obligations);
849 // Construct the nested `T: Unsize<U>` predicate.
850 nested.push(ensure_sufficient_stack(|| {
851 predicate_for_trait_def(
853 obligation.param_env,
854 obligation.cause.clone(),
855 obligation.predicate.def_id(),
856 obligation.recursion_depth + 1,
866 Ok(ImplSourceBuiltinData { nested })