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