src/librustc_trait_selection/traits/select/confirmation.rs

   1 //! Confirmation.
   2 //!
   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.
   6 //!
   7 //! [rustc dev guide]:
   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;
  11 use rustc_index::bit_set::GrowableBitSet;
  12 use rustc_infer::infer::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;
  17
  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::Normalized;
  23 use crate::traits::OutputTypeParameterMismatch;
  24 use crate::traits::Selection;
  25 use crate::traits::TraitNotObjectSafe;
  26 use crate::traits::{BuiltinDerivedObligation, ImplDerivedObligation};
  27 use crate::traits::{
  28     ImplSourceAutoImpl, ImplSourceBuiltin, ImplSourceClosure, ImplSourceDiscriminantKind,
  29     ImplSourceFnPointer, ImplSourceGenerator, ImplSourceObject, ImplSourceParam,
  30     ImplSourceTraitAlias, ImplSourceUserDefined,
  31 };
  32 use crate::traits::{
  33     ImplSourceAutoImplData, ImplSourceBuiltinData, ImplSourceClosureData,
  34     ImplSourceDiscriminantKindData, ImplSourceFnPointerData, ImplSourceGeneratorData,
  35     ImplSourceObjectData, ImplSourceTraitAliasData, ImplSourceUserDefinedData,
  36 };
  37 use crate::traits::{ObjectCastObligation, PredicateObligation, TraitObligation};
  38 use crate::traits::{Obligation, ObligationCause};
  39 use crate::traits::{SelectionError, Unimplemented};
  40
  41 use super::BuiltinImplConditions;
  42 use super::SelectionCandidate::{self, *};
  43 use super::SelectionContext;
  44
  45 use std::iter;
  46
  47 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
  48     pub(super) fn confirm_candidate(
  49         &mut self,
  50         obligation: &TraitObligation<'tcx>,
  51         candidate: SelectionCandidate<'tcx>,
  52     ) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
  53         debug!("confirm_candidate({:?}, {:?})", obligation, candidate);
  54
  55         match candidate {
  56             BuiltinCandidate { has_nested } => {
  57                 let data = self.confirm_builtin_candidate(obligation, has_nested);
  58                 Ok(ImplSourceBuiltin(data))
  59             }
  60
  61             ParamCandidate(param) => {
  62                 let obligations = self.confirm_param_candidate(obligation, param);
  63                 Ok(ImplSourceParam(obligations))
  64             }
  65
  66             ImplCandidate(impl_def_id) => {
  67                 Ok(ImplSourceUserDefined(self.confirm_impl_candidate(obligation, impl_def_id)))
  68             }
  69
  70             AutoImplCandidate(trait_def_id) => {
  71                 let data = self.confirm_auto_impl_candidate(obligation, trait_def_id);
  72                 Ok(ImplSourceAutoImpl(data))
  73             }
  74
  75             ProjectionCandidate => {
  76                 self.confirm_projection_candidate(obligation);
  77                 Ok(ImplSourceParam(Vec::new()))
  78             }
  79
  80             ClosureCandidate => {
  81                 let vtable_closure = self.confirm_closure_candidate(obligation)?;
  82                 Ok(ImplSourceClosure(vtable_closure))
  83             }
  84
  85             GeneratorCandidate => {
  86                 let vtable_generator = self.confirm_generator_candidate(obligation)?;
  87                 Ok(ImplSourceGenerator(vtable_generator))
  88             }
  89
  90             FnPointerCandidate => {
  91                 let data = self.confirm_fn_pointer_candidate(obligation)?;
  92                 Ok(ImplSourceFnPointer(data))
  93             }
  94
  95             DiscriminantKindCandidate => {
  96                 Ok(ImplSourceDiscriminantKind(ImplSourceDiscriminantKindData))
  97             }
  98
  99             TraitAliasCandidate(alias_def_id) => {
 100                 let data = self.confirm_trait_alias_candidate(obligation, alias_def_id);
 101                 Ok(ImplSourceTraitAlias(data))
 102             }
 103
 104             ObjectCandidate => {
 105                 let data = self.confirm_object_candidate(obligation);
 106                 Ok(ImplSourceObject(data))
 107             }
 108
 109             BuiltinObjectCandidate => {
 110                 // This indicates something like `Trait + Send: Send`. In this case, we know that
 111                 // this holds because that's what the object type is telling us, and there's really
 112                 // no additional obligations to prove and no types in particular to unify, etc.
 113                 Ok(ImplSourceParam(Vec::new()))
 114             }
 115
 116             BuiltinUnsizeCandidate => {
 117                 let data = self.confirm_builtin_unsize_candidate(obligation)?;
 118                 Ok(ImplSourceBuiltin(data))
 119             }
 120         }
 121     }
 122
 123     fn confirm_projection_candidate(&mut self, obligation: &TraitObligation<'tcx>) {
 124         self.infcx.commit_unconditionally(|_| {
 125             let result = self.match_projection_obligation_against_definition_bounds(obligation);
 126             assert!(result);
 127         })
 128     }
 129
 130     fn confirm_param_candidate(
 131         &mut self,
 132         obligation: &TraitObligation<'tcx>,
 133         param: ty::PolyTraitRef<'tcx>,
 134     ) -> Vec<PredicateObligation<'tcx>> {
 135         debug!("confirm_param_candidate({:?},{:?})", obligation, param);
 136
 137         // During evaluation, we already checked that this
 138         // where-clause trait-ref could be unified with the obligation
 139         // trait-ref. Repeat that unification now without any
 140         // transactional boundary; it should not fail.
 141         match self.match_where_clause_trait_ref(obligation, param) {
 142             Ok(obligations) => obligations,
 143             Err(()) => {
 144                 bug!(
 145                     "Where clause `{:?}` was applicable to `{:?}` but now is not",
 146                     param,
 147                     obligation
 148                 );
 149             }
 150         }
 151     }
 152
 153     fn confirm_builtin_candidate(
 154         &mut self,
 155         obligation: &TraitObligation<'tcx>,
 156         has_nested: bool,
 157     ) -> ImplSourceBuiltinData<PredicateObligation<'tcx>> {
 158         debug!("confirm_builtin_candidate({:?}, {:?})", obligation, has_nested);
 159
 160         let lang_items = self.tcx().lang_items();
 161         let obligations = if has_nested {
 162             let trait_def = obligation.predicate.def_id();
 163             let conditions = if Some(trait_def) == lang_items.sized_trait() {
 164                 self.sized_conditions(obligation)
 165             } else if Some(trait_def) == lang_items.copy_trait() {
 166                 self.copy_clone_conditions(obligation)
 167             } else if Some(trait_def) == lang_items.clone_trait() {
 168                 self.copy_clone_conditions(obligation)
 169             } else {
 170                 bug!("unexpected builtin trait {:?}", trait_def)
 171             };
 172             let nested = match conditions {
 173                 BuiltinImplConditions::Where(nested) => nested,
 174                 _ => bug!("obligation {:?} had matched a builtin impl but now doesn't", obligation),
 175             };
 176
 177             let cause = obligation.derived_cause(BuiltinDerivedObligation);
 178             ensure_sufficient_stack(|| {
 179                 self.collect_predicates_for_types(
 180                     obligation.param_env,
 181                     cause,
 182                     obligation.recursion_depth + 1,
 183                     trait_def,
 184                     nested,
 185                 )
 186             })
 187         } else {
 188             vec![]
 189         };
 190
 191         debug!("confirm_builtin_candidate: obligations={:?}", obligations);
 192
 193         ImplSourceBuiltinData { nested: obligations }
 194     }
 195
 196     /// This handles the case where a `auto trait Foo` impl is being used.
 197     /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
 198     ///
 199     /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
 200     /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
 201     fn confirm_auto_impl_candidate(
 202         &mut self,
 203         obligation: &TraitObligation<'tcx>,
 204         trait_def_id: DefId,
 205     ) -> ImplSourceAutoImplData<PredicateObligation<'tcx>> {
 206         debug!("confirm_auto_impl_candidate({:?}, {:?})", obligation, trait_def_id);
 207
 208         let types = obligation.predicate.map_bound(|inner| {
 209             let self_ty = self.infcx.shallow_resolve(inner.self_ty());
 210             self.constituent_types_for_ty(self_ty)
 211         });
 212         self.vtable_auto_impl(obligation, trait_def_id, types)
 213     }
 214
 215     /// See `confirm_auto_impl_candidate`.
 216     fn vtable_auto_impl(
 217         &mut self,
 218         obligation: &TraitObligation<'tcx>,
 219         trait_def_id: DefId,
 220         nested: ty::Binder<Vec<Ty<'tcx>>>,
 221     ) -> ImplSourceAutoImplData<PredicateObligation<'tcx>> {
 222         debug!("vtable_auto_impl: nested={:?}", nested);
 223         ensure_sufficient_stack(|| {
 224             let cause = obligation.derived_cause(BuiltinDerivedObligation);
 225             let mut obligations = self.collect_predicates_for_types(
 226                 obligation.param_env,
 227                 cause,
 228                 obligation.recursion_depth + 1,
 229                 trait_def_id,
 230                 nested,
 231             );
 232
 233             let trait_obligations: Vec<PredicateObligation<'_>> =
 234                 self.infcx.commit_unconditionally(|_| {
 235                     let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
 236                     let (trait_ref, _) =
 237                         self.infcx.replace_bound_vars_with_placeholders(&poly_trait_ref);
 238                     let cause = obligation.derived_cause(ImplDerivedObligation);
 239                     self.impl_or_trait_obligations(
 240                         cause,
 241                         obligation.recursion_depth + 1,
 242                         obligation.param_env,
 243                         trait_def_id,
 244                         &trait_ref.substs,
 245                     )
 246                 });
 247
 248             // Adds the predicates from the trait.  Note that this contains a `Self: Trait`
 249             // predicate as usual.  It won't have any effect since auto traits are coinductive.
 250             obligations.extend(trait_obligations);
 251
 252             debug!("vtable_auto_impl: obligations={:?}", obligations);
 253
 254             ImplSourceAutoImplData { trait_def_id, nested: obligations }
 255         })
 256     }
 257
 258     fn confirm_impl_candidate(
 259         &mut self,
 260         obligation: &TraitObligation<'tcx>,
 261         impl_def_id: DefId,
 262     ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
 263         debug!("confirm_impl_candidate({:?},{:?})", obligation, impl_def_id);
 264
 265         // First, create the substitutions by matching the impl again,
 266         // this time not in a probe.
 267         self.infcx.commit_unconditionally(|_| {
 268             let substs = self.rematch_impl(impl_def_id, obligation);
 269             debug!("confirm_impl_candidate: substs={:?}", substs);
 270             let cause = obligation.derived_cause(ImplDerivedObligation);
 271             ensure_sufficient_stack(|| {
 272                 self.vtable_impl(
 273                     impl_def_id,
 274                     substs,
 275                     cause,
 276                     obligation.recursion_depth + 1,
 277                     obligation.param_env,
 278                 )
 279             })
 280         })
 281     }
 282
 283     fn vtable_impl(
 284         &mut self,
 285         impl_def_id: DefId,
 286         mut substs: Normalized<'tcx, SubstsRef<'tcx>>,
 287         cause: ObligationCause<'tcx>,
 288         recursion_depth: usize,
 289         param_env: ty::ParamEnv<'tcx>,
 290     ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
 291         debug!(
 292             "vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={})",
 293             impl_def_id, substs, recursion_depth,
 294         );
 295
 296         let mut impl_obligations = self.impl_or_trait_obligations(
 297             cause,
 298             recursion_depth,
 299             param_env,
 300             impl_def_id,
 301             &substs.value,
 302         );
 303
 304         debug!(
 305             "vtable_impl: impl_def_id={:?} impl_obligations={:?}",
 306             impl_def_id, impl_obligations
 307         );
 308
 309         // Because of RFC447, the impl-trait-ref and obligations
 310         // are sufficient to determine the impl substs, without
 311         // relying on projections in the impl-trait-ref.
 312         //
 313         // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
 314         impl_obligations.append(&mut substs.obligations);
 315
 316         ImplSourceUserDefinedData { impl_def_id, substs: substs.value, nested: impl_obligations }
 317     }
 318
 319     fn confirm_object_candidate(
 320         &mut self,
 321         obligation: &TraitObligation<'tcx>,
 322     ) -> ImplSourceObjectData<'tcx, PredicateObligation<'tcx>> {
 323         debug!("confirm_object_candidate({:?})", obligation);
 324
 325         // FIXME(nmatsakis) skipping binder here seems wrong -- we should
 326         // probably flatten the binder from the obligation and the binder
 327         // from the object. Have to try to make a broken test case that
 328         // results.
 329         let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
 330         let poly_trait_ref = match self_ty.kind {
 331             ty::Dynamic(ref data, ..) => data
 332                 .principal()
 333                 .unwrap_or_else(|| {
 334                     span_bug!(obligation.cause.span, "object candidate with no principal")
 335                 })
 336                 .with_self_ty(self.tcx(), self_ty),
 337             _ => span_bug!(obligation.cause.span, "object candidate with non-object"),
 338         };
 339
 340         let mut upcast_trait_ref = None;
 341         let mut nested = vec![];
 342         let vtable_base;
 343
 344         {
 345             let tcx = self.tcx();
 346
 347             // We want to find the first supertrait in the list of
 348             // supertraits that we can unify with, and do that
 349             // unification. We know that there is exactly one in the list
 350             // where we can unify, because otherwise select would have
 351             // reported an ambiguity. (When we do find a match, also
 352             // record it for later.)
 353             let nonmatching = util::supertraits(tcx, poly_trait_ref).take_while(|&t| {
 354                 match self.infcx.commit_if_ok(|_| self.match_poly_trait_ref(obligation, t)) {
 355                     Ok(obligations) => {
 356                         upcast_trait_ref = Some(t);
 357                         nested.extend(obligations);
 358                         false
 359                     }
 360                     Err(_) => true,
 361                 }
 362             });
 363
 364             // Additionally, for each of the non-matching predicates that
 365             // we pass over, we sum up the set of number of vtable
 366             // entries, so that we can compute the offset for the selected
 367             // trait.
 368             vtable_base = nonmatching.map(|t| super::util::count_own_vtable_entries(tcx, t)).sum();
 369         }
 370
 371         ImplSourceObjectData { upcast_trait_ref: upcast_trait_ref.unwrap(), vtable_base, nested }
 372     }
 373
 374     fn confirm_fn_pointer_candidate(
 375         &mut self,
 376         obligation: &TraitObligation<'tcx>,
 377     ) -> Result<ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>>
 378     {
 379         debug!("confirm_fn_pointer_candidate({:?})", obligation);
 380
 381         // Okay to skip binder; it is reintroduced below.
 382         let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
 383         let sig = self_ty.fn_sig(self.tcx());
 384         let trait_ref = closure_trait_ref_and_return_type(
 385             self.tcx(),
 386             obligation.predicate.def_id(),
 387             self_ty,
 388             sig,
 389             util::TupleArgumentsFlag::Yes,
 390         )
 391         .map_bound(|(trait_ref, _)| trait_ref);
 392
 393         let Normalized { value: trait_ref, obligations } = ensure_sufficient_stack(|| {
 394             project::normalize_with_depth(
 395                 self,
 396                 obligation.param_env,
 397                 obligation.cause.clone(),
 398                 obligation.recursion_depth + 1,
 399                 &trait_ref,
 400             )
 401         });
 402
 403         self.confirm_poly_trait_refs(
 404             obligation.cause.clone(),
 405             obligation.param_env,
 406             obligation.predicate.to_poly_trait_ref(),
 407             trait_ref,
 408         )?;
 409         Ok(ImplSourceFnPointerData { fn_ty: self_ty, nested: obligations })
 410     }
 411
 412     fn confirm_trait_alias_candidate(
 413         &mut self,
 414         obligation: &TraitObligation<'tcx>,
 415         alias_def_id: DefId,
 416     ) -> ImplSourceTraitAliasData<'tcx, PredicateObligation<'tcx>> {
 417         debug!("confirm_trait_alias_candidate({:?}, {:?})", obligation, alias_def_id);
 418
 419         self.infcx.commit_unconditionally(|_| {
 420             let (predicate, _) =
 421                 self.infcx().replace_bound_vars_with_placeholders(&obligation.predicate);
 422             let trait_ref = predicate.trait_ref;
 423             let trait_def_id = trait_ref.def_id;
 424             let substs = trait_ref.substs;
 425
 426             let trait_obligations = self.impl_or_trait_obligations(
 427                 obligation.cause.clone(),
 428                 obligation.recursion_depth,
 429                 obligation.param_env,
 430                 trait_def_id,
 431                 &substs,
 432             );
 433
 434             debug!(
 435                 "confirm_trait_alias_candidate: trait_def_id={:?} trait_obligations={:?}",
 436                 trait_def_id, trait_obligations
 437             );
 438
 439             ImplSourceTraitAliasData { alias_def_id, substs, nested: trait_obligations }
 440         })
 441     }
 442
 443     fn confirm_generator_candidate(
 444         &mut self,
 445         obligation: &TraitObligation<'tcx>,
 446     ) -> Result<ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>>
 447     {
 448         // Okay to skip binder because the substs on generator types never
 449         // touch bound regions, they just capture the in-scope
 450         // type/region parameters.
 451         let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
 452         let (generator_def_id, substs) = match self_ty.kind {
 453             ty::Generator(id, substs, _) => (id, substs),
 454             _ => bug!("closure candidate for non-closure {:?}", obligation),
 455         };
 456
 457         debug!("confirm_generator_candidate({:?},{:?},{:?})", obligation, generator_def_id, substs);
 458
 459         let trait_ref = self.generator_trait_ref_unnormalized(obligation, substs);
 460         let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
 461             normalize_with_depth(
 462                 self,
 463                 obligation.param_env,
 464                 obligation.cause.clone(),
 465                 obligation.recursion_depth + 1,
 466                 &trait_ref,
 467             )
 468         });
 469
 470         debug!(
 471             "confirm_generator_candidate(generator_def_id={:?}, \
 472              trait_ref={:?}, obligations={:?})",
 473             generator_def_id, trait_ref, obligations
 474         );
 475
 476         obligations.extend(self.confirm_poly_trait_refs(
 477             obligation.cause.clone(),
 478             obligation.param_env,
 479             obligation.predicate.to_poly_trait_ref(),
 480             trait_ref,
 481         )?);
 482
 483         Ok(ImplSourceGeneratorData { generator_def_id, substs, nested: obligations })
 484     }
 485
 486     fn confirm_closure_candidate(
 487         &mut self,
 488         obligation: &TraitObligation<'tcx>,
 489     ) -> Result<ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
 490         debug!("confirm_closure_candidate({:?})", obligation);
 491
 492         let kind = self
 493             .tcx()
 494             .fn_trait_kind_from_lang_item(obligation.predicate.def_id())
 495             .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation));
 496
 497         // Okay to skip binder because the substs on closure types never
 498         // touch bound regions, they just capture the in-scope
 499         // type/region parameters.
 500         let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
 501         let (closure_def_id, substs) = match self_ty.kind {
 502             ty::Closure(id, substs) => (id, substs),
 503             _ => bug!("closure candidate for non-closure {:?}", obligation),
 504         };
 505
 506         let trait_ref = self.closure_trait_ref_unnormalized(obligation, substs);
 507         let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
 508             normalize_with_depth(
 509                 self,
 510                 obligation.param_env,
 511                 obligation.cause.clone(),
 512                 obligation.recursion_depth + 1,
 513                 &trait_ref,
 514             )
 515         });
 516
 517         debug!(
 518             "confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
 519             closure_def_id, trait_ref, obligations
 520         );
 521
 522         obligations.extend(self.confirm_poly_trait_refs(
 523             obligation.cause.clone(),
 524             obligation.param_env,
 525             obligation.predicate.to_poly_trait_ref(),
 526             trait_ref,
 527         )?);
 528
 529         // FIXME: Chalk
 530
 531         if !self.tcx().sess.opts.debugging_opts.chalk {
 532             obligations.push(Obligation::new(
 533                 obligation.cause.clone(),
 534                 obligation.param_env,
 535                 ty::PredicateKind::ClosureKind(closure_def_id, substs, kind)
 536                     .to_predicate(self.tcx()),
 537             ));
 538         }
 539
 540         Ok(ImplSourceClosureData { closure_def_id, substs, nested: obligations })
 541     }
 542
 543     /// In the case of closure types and fn pointers,
 544     /// we currently treat the input type parameters on the trait as
 545     /// outputs. This means that when we have a match we have only
 546     /// considered the self type, so we have to go back and make sure
 547     /// to relate the argument types too. This is kind of wrong, but
 548     /// since we control the full set of impls, also not that wrong,
 549     /// and it DOES yield better error messages (since we don't report
 550     /// errors as if there is no applicable impl, but rather report
 551     /// errors are about mismatched argument types.
 552     ///
 553     /// Here is an example. Imagine we have a closure expression
 554     /// and we desugared it so that the type of the expression is
 555     /// `Closure`, and `Closure` expects `i32` as argument. Then it
 556     /// is "as if" the compiler generated this impl:
 557     ///
 558     ///     impl Fn(i32) for Closure { ... }
 559     ///
 560     /// Now imagine our obligation is `Closure: Fn(usize)`. So far
 561     /// we have matched the self type `Closure`. At this point we'll
 562     /// compare the `i32` to `usize` and generate an error.
 563     ///
 564     /// Note that this checking occurs *after* the impl has selected,
 565     /// because these output type parameters should not affect the
 566     /// selection of the impl. Therefore, if there is a mismatch, we
 567     /// report an error to the user.
 568     fn confirm_poly_trait_refs(
 569         &mut self,
 570         obligation_cause: ObligationCause<'tcx>,
 571         obligation_param_env: ty::ParamEnv<'tcx>,
 572         obligation_trait_ref: ty::PolyTraitRef<'tcx>,
 573         expected_trait_ref: ty::PolyTraitRef<'tcx>,
 574     ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
 575         self.infcx
 576             .at(&obligation_cause, obligation_param_env)
 577             .sup(obligation_trait_ref, expected_trait_ref)
 578             .map(|InferOk { obligations, .. }| obligations)
 579             .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
 580     }
 581
 582     fn confirm_builtin_unsize_candidate(
 583         &mut self,
 584         obligation: &TraitObligation<'tcx>,
 585     ) -> Result<ImplSourceBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
 586         let tcx = self.tcx();
 587
 588         // `assemble_candidates_for_unsizing` should ensure there are no late-bound
 589         // regions here. See the comment there for more details.
 590         let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
 591         let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
 592         let target = self.infcx.shallow_resolve(target);
 593
 594         debug!("confirm_builtin_unsize_candidate(source={:?}, target={:?})", source, target);
 595
 596         let mut nested = vec![];
 597         match (&source.kind, &target.kind) {
 598             // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
 599             (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => {
 600                 // See `assemble_candidates_for_unsizing` for more info.
 601                 let existential_predicates = data_a.map_bound(|data_a| {
 602                     let iter = data_a
 603                         .principal()
 604                         .map(ty::ExistentialPredicate::Trait)
 605                         .into_iter()
 606                         .chain(data_a.projection_bounds().map(ty::ExistentialPredicate::Projection))
 607                         .chain(data_b.auto_traits().map(ty::ExistentialPredicate::AutoTrait));
 608                     tcx.mk_existential_predicates(iter)
 609                 });
 610                 let source_trait = tcx.mk_dynamic(existential_predicates, r_b);
 611
 612                 // Require that the traits involved in this upcast are **equal**;
 613                 // only the **lifetime bound** is changed.
 614                 let InferOk { obligations, .. } = self
 615                     .infcx
 616                     .at(&obligation.cause, obligation.param_env)
 617                     .sup(target, source_trait)
 618                     .map_err(|_| Unimplemented)?;
 619                 nested.extend(obligations);
 620
 621                 // Register one obligation for 'a: 'b.
 622                 let cause = ObligationCause::new(
 623                     obligation.cause.span,
 624                     obligation.cause.body_id,
 625                     ObjectCastObligation(target),
 626                 );
 627                 let outlives = ty::OutlivesPredicate(r_a, r_b);
 628                 nested.push(Obligation::with_depth(
 629                     cause,
 630                     obligation.recursion_depth + 1,
 631                     obligation.param_env,
 632                     ty::Binder::bind(outlives).to_predicate(tcx),
 633                 ));
 634             }
 635
 636             // `T` -> `Trait`
 637             (_, &ty::Dynamic(ref data, r)) => {
 638                 let mut object_dids = data.auto_traits().chain(data.principal_def_id());
 639                 if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) {
 640                     return Err(TraitNotObjectSafe(did));
 641                 }
 642
 643                 let cause = ObligationCause::new(
 644                     obligation.cause.span,
 645                     obligation.cause.body_id,
 646                     ObjectCastObligation(target),
 647                 );
 648
 649                 let predicate_to_obligation = |predicate| {
 650                     Obligation::with_depth(
 651                         cause.clone(),
 652                         obligation.recursion_depth + 1,
 653                         obligation.param_env,
 654                         predicate,
 655                     )
 656                 };
 657
 658                 // Create obligations:
 659                 //  - Casting `T` to `Trait`
 660                 //  - For all the various builtin bounds attached to the object cast. (In other
 661                 //  words, if the object type is `Foo + Send`, this would create an obligation for
 662                 //  the `Send` check.)
 663                 //  - Projection predicates
 664                 nested.extend(
 665                     data.iter().map(|predicate| {
 666                         predicate_to_obligation(predicate.with_self_ty(tcx, source))
 667                     }),
 668                 );
 669
 670                 // We can only make objects from sized types.
 671                 let tr = ty::TraitRef::new(
 672                     tcx.require_lang_item(lang_items::SizedTraitLangItem, None),
 673                     tcx.mk_substs_trait(source, &[]),
 674                 );
 675                 nested.push(predicate_to_obligation(tr.without_const().to_predicate(tcx)));
 676
 677                 // If the type is `Foo + 'a`, ensure that the type
 678                 // being cast to `Foo + 'a` outlives `'a`:
 679                 let outlives = ty::OutlivesPredicate(source, r);
 680                 nested.push(predicate_to_obligation(ty::Binder::dummy(outlives).to_predicate(tcx)));
 681             }
 682
 683             // `[T; n]` -> `[T]`
 684             (&ty::Array(a, _), &ty::Slice(b)) => {
 685                 let InferOk { obligations, .. } = self
 686                     .infcx
 687                     .at(&obligation.cause, obligation.param_env)
 688                     .eq(b, a)
 689                     .map_err(|_| Unimplemented)?;
 690                 nested.extend(obligations);
 691             }
 692
 693             // `Struct<T>` -> `Struct<U>`
 694             (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => {
 695                 let maybe_unsizing_param_idx = |arg: GenericArg<'tcx>| match arg.unpack() {
 696                     GenericArgKind::Type(ty) => match ty.kind {
 697                         ty::Param(p) => Some(p.index),
 698                         _ => None,
 699                     },
 700
 701                     // Lifetimes aren't allowed to change during unsizing.
 702                     GenericArgKind::Lifetime(_) => None,
 703
 704                     GenericArgKind::Const(ct) => match ct.val {
 705                         ty::ConstKind::Param(p) => Some(p.index),
 706                         _ => None,
 707                     },
 708                 };
 709
 710                 // The last field of the structure has to exist and contain type/const parameters.
 711                 let (tail_field, prefix_fields) =
 712                     def.non_enum_variant().fields.split_last().ok_or(Unimplemented)?;
 713                 let tail_field_ty = tcx.type_of(tail_field.did);
 714
 715                 let mut unsizing_params = GrowableBitSet::new_empty();
 716                 let mut found = false;
 717                 for arg in tail_field_ty.walk() {
 718                     if let Some(i) = maybe_unsizing_param_idx(arg) {
 719                         unsizing_params.insert(i);
 720                         found = true;
 721                     }
 722                 }
 723                 if !found {
 724                     return Err(Unimplemented);
 725                 }
 726
 727                 // Ensure none of the other fields mention the parameters used
 728                 // in unsizing.
 729                 // FIXME(eddyb) cache this (including computing `unsizing_params`)
 730                 // by putting it in a query; it would only need the `DefId` as it
 731                 // looks at declared field types, not anything substituted.
 732                 for field in prefix_fields {
 733                     for arg in tcx.type_of(field.did).walk() {
 734                         if let Some(i) = maybe_unsizing_param_idx(arg) {
 735                             if unsizing_params.contains(i) {
 736                                 return Err(Unimplemented);
 737                             }
 738                         }
 739                     }
 740                 }
 741
 742                 // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
 743                 let source_tail = tail_field_ty.subst(tcx, substs_a);
 744                 let target_tail = tail_field_ty.subst(tcx, substs_b);
 745
 746                 // Check that the source struct with the target's
 747                 // unsizing parameters is equal to the target.
 748                 let substs = tcx.mk_substs(substs_a.iter().enumerate().map(|(i, k)| {
 749                     if unsizing_params.contains(i as u32) { substs_b[i] } else { k }
 750                 }));
 751                 let new_struct = tcx.mk_adt(def, substs);
 752                 let InferOk { obligations, .. } = self
 753                     .infcx
 754                     .at(&obligation.cause, obligation.param_env)
 755                     .eq(target, new_struct)
 756                     .map_err(|_| Unimplemented)?;
 757                 nested.extend(obligations);
 758
 759                 // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate.
 760                 nested.push(predicate_for_trait_def(
 761                     tcx,
 762                     obligation.param_env,
 763                     obligation.cause.clone(),
 764                     obligation.predicate.def_id(),
 765                     obligation.recursion_depth + 1,
 766                     source_tail,
 767                     &[target_tail.into()],
 768                 ));
 769             }
 770
 771             // `(.., T)` -> `(.., U)`
 772             (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
 773                 assert_eq!(tys_a.len(), tys_b.len());
 774
 775                 // The last field of the tuple has to exist.
 776                 let (&a_last, a_mid) = tys_a.split_last().ok_or(Unimplemented)?;
 777                 let &b_last = tys_b.last().unwrap();
 778
 779                 // Check that the source tuple with the target's
 780                 // last element is equal to the target.
 781                 let new_tuple = tcx.mk_tup(
 782                     a_mid.iter().map(|k| k.expect_ty()).chain(iter::once(b_last.expect_ty())),
 783                 );
 784                 let InferOk { obligations, .. } = self
 785                     .infcx
 786                     .at(&obligation.cause, obligation.param_env)
 787                     .eq(target, new_tuple)
 788                     .map_err(|_| Unimplemented)?;
 789                 nested.extend(obligations);
 790
 791                 // Construct the nested `T: Unsize<U>` predicate.
 792                 nested.push(ensure_sufficient_stack(|| {
 793                     predicate_for_trait_def(
 794                         tcx,
 795                         obligation.param_env,
 796                         obligation.cause.clone(),
 797                         obligation.predicate.def_id(),
 798                         obligation.recursion_depth + 1,
 799                         a_last.expect_ty(),
 800                         &[b_last],
 801                     )
 802                 }));
 803             }
 804
 805             _ => bug!(),
 806         };
 807
 808         Ok(ImplSourceBuiltinData { nested })
 809     }
 810 }