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