compiler/rustc_trait_selection/src/traits/wf.rs

   1 use crate::infer::InferCtxt;
   2 use crate::opaque_types::required_region_bounds;
   3 use crate::traits;
   4 use rustc_data_structures::sync::Lrc;
   5 use rustc_hir as hir;
   6 use rustc_hir::def_id::DefId;
   7 use rustc_hir::lang_items::LangItem;
   8 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, SubstsRef};
   9 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness};
  10 use rustc_span::Span;
  11
  12 use std::iter;
  13 /// Returns the set of obligations needed to make `arg` well-formed.
  14 /// If `arg` contains unresolved inference variables, this may include
  15 /// further WF obligations. However, if `arg` IS an unresolved
  16 /// inference variable, returns `None`, because we are not able to
  17 /// make any progress at all. This is to prevent "livelock" where we
  18 /// say "$0 is WF if $0 is WF".
  19 pub fn obligations<'a, 'tcx>(
  20     infcx: &InferCtxt<'a, 'tcx>,
  21     param_env: ty::ParamEnv<'tcx>,
  22     body_id: hir::HirId,
  23     recursion_depth: usize,
  24     arg: GenericArg<'tcx>,
  25     span: Span,
  26 ) -> Option<Vec<traits::PredicateObligation<'tcx>>> {
  27     // Handle the "livelock" case (see comment above) by bailing out if necessary.
  28     let arg = match arg.unpack() {
  29         GenericArgKind::Type(ty) => {
  30             match ty.kind() {
  31                 ty::Infer(ty::TyVar(_)) => {
  32                     let resolved_ty = infcx.shallow_resolve(ty);
  33                     if resolved_ty == ty {
  34                         // No progress, bail out to prevent "livelock".
  35                         return None;
  36                     }
  37
  38                     resolved_ty
  39                 }
  40                 _ => ty,
  41             }
  42             .into()
  43         }
  44         GenericArgKind::Const(ct) => {
  45             match ct.val {
  46                 ty::ConstKind::Infer(infer) => {
  47                     let resolved = infcx.shallow_resolve(infer);
  48                     if resolved == infer {
  49                         // No progress.
  50                         return None;
  51                     }
  52
  53                     infcx.tcx.mk_const(ty::Const { val: ty::ConstKind::Infer(resolved), ty: ct.ty })
  54                 }
  55                 _ => ct,
  56             }
  57             .into()
  58         }
  59         // There is nothing we have to do for lifetimes.
  60         GenericArgKind::Lifetime(..) => return Some(Vec::new()),
  61     };
  62
  63     let mut wf =
  64         WfPredicates { infcx, param_env, body_id, span, out: vec![], recursion_depth, item: None };
  65     wf.compute(arg);
  66     debug!("wf::obligations({:?}, body_id={:?}) = {:?}", arg, body_id, wf.out);
  67
  68     let result = wf.normalize();
  69     debug!("wf::obligations({:?}, body_id={:?}) ~~> {:?}", arg, body_id, result);
  70     Some(result)
  71 }
  72
  73 /// Returns the obligations that make this trait reference
  74 /// well-formed.  For example, if there is a trait `Set` defined like
  75 /// `trait Set<K:Eq>`, then the trait reference `Foo: Set<Bar>` is WF
  76 /// if `Bar: Eq`.
  77 pub fn trait_obligations<'a, 'tcx>(
  78     infcx: &InferCtxt<'a, 'tcx>,
  79     param_env: ty::ParamEnv<'tcx>,
  80     body_id: hir::HirId,
  81     trait_ref: &ty::TraitRef<'tcx>,
  82     span: Span,
  83     item: Option<&'tcx hir::Item<'tcx>>,
  84 ) -> Vec<traits::PredicateObligation<'tcx>> {
  85     let mut wf =
  86         WfPredicates { infcx, param_env, body_id, span, out: vec![], recursion_depth: 0, item };
  87     wf.compute_trait_ref(trait_ref, Elaborate::All);
  88     debug!(obligations = ?wf.out);
  89     wf.normalize()
  90 }
  91
  92 pub fn predicate_obligations<'a, 'tcx>(
  93     infcx: &InferCtxt<'a, 'tcx>,
  94     param_env: ty::ParamEnv<'tcx>,
  95     body_id: hir::HirId,
  96     predicate: ty::Predicate<'tcx>,
  97     span: Span,
  98 ) -> Vec<traits::PredicateObligation<'tcx>> {
  99     let mut wf = WfPredicates {
 100         infcx,
 101         param_env,
 102         body_id,
 103         span,
 104         out: vec![],
 105         recursion_depth: 0,
 106         item: None,
 107     };
 108
 109     // It's ok to skip the binder here because wf code is prepared for it
 110     match predicate.kind().skip_binder() {
 111         ty::PredicateKind::Trait(t, _) => {
 112             wf.compute_trait_ref(&t.trait_ref, Elaborate::None);
 113         }
 114         ty::PredicateKind::RegionOutlives(..) => {}
 115         ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(ty, _reg)) => {
 116             wf.compute(ty.into());
 117         }
 118         ty::PredicateKind::Projection(t) => {
 119             wf.compute_projection(t.projection_ty);
 120             wf.compute(t.ty.into());
 121         }
 122         ty::PredicateKind::WellFormed(arg) => {
 123             wf.compute(arg);
 124         }
 125         ty::PredicateKind::ObjectSafe(_) => {}
 126         ty::PredicateKind::ClosureKind(..) => {}
 127         ty::PredicateKind::Subtype(ty::SubtypePredicate { a, b, a_is_expected: _ }) => {
 128             wf.compute(a.into());
 129             wf.compute(b.into());
 130         }
 131         ty::PredicateKind::ConstEvaluatable(def, substs) => {
 132             let obligations = wf.nominal_obligations(def.did, substs);
 133             wf.out.extend(obligations);
 134
 135             for arg in substs.iter() {
 136                 wf.compute(arg);
 137             }
 138         }
 139         ty::PredicateKind::ConstEquate(c1, c2) => {
 140             wf.compute(c1.into());
 141             wf.compute(c2.into());
 142         }
 143         ty::PredicateKind::TypeWellFormedFromEnv(..) => {
 144             bug!("TypeWellFormedFromEnv is only used for Chalk")
 145         }
 146     }
 147
 148     wf.normalize()
 149 }
 150
 151 struct WfPredicates<'a, 'tcx> {
 152     infcx: &'a InferCtxt<'a, 'tcx>,
 153     param_env: ty::ParamEnv<'tcx>,
 154     body_id: hir::HirId,
 155     span: Span,
 156     out: Vec<traits::PredicateObligation<'tcx>>,
 157     recursion_depth: usize,
 158     item: Option<&'tcx hir::Item<'tcx>>,
 159 }
 160
 161 /// Controls whether we "elaborate" supertraits and so forth on the WF
 162 /// predicates. This is a kind of hack to address #43784. The
 163 /// underlying problem in that issue was a trait structure like:
 164 ///
 165 /// ```
 166 /// trait Foo: Copy { }
 167 /// trait Bar: Foo { }
 168 /// impl<T: Bar> Foo for T { }
 169 /// impl<T> Bar for T { }
 170 /// ```
 171 ///
 172 /// Here, in the `Foo` impl, we will check that `T: Copy` holds -- but
 173 /// we decide that this is true because `T: Bar` is in the
 174 /// where-clauses (and we can elaborate that to include `T:
 175 /// Copy`). This wouldn't be a problem, except that when we check the
 176 /// `Bar` impl, we decide that `T: Foo` must hold because of the `Foo`
 177 /// impl. And so nowhere did we check that `T: Copy` holds!
 178 ///
 179 /// To resolve this, we elaborate the WF requirements that must be
 180 /// proven when checking impls. This means that (e.g.) the `impl Bar
 181 /// for T` will be forced to prove not only that `T: Foo` but also `T:
 182 /// Copy` (which it won't be able to do, because there is no `Copy`
 183 /// impl for `T`).
 184 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 185 enum Elaborate {
 186     All,
 187     None,
 188 }
 189
 190 fn extend_cause_with_original_assoc_item_obligation<'tcx>(
 191     tcx: TyCtxt<'tcx>,
 192     trait_ref: &ty::TraitRef<'tcx>,
 193     item: Option<&hir::Item<'tcx>>,
 194     cause: &mut traits::ObligationCause<'tcx>,
 195     pred: &ty::Predicate<'tcx>,
 196     mut trait_assoc_items: impl Iterator<Item = &'tcx ty::AssocItem>,
 197 ) {
 198     debug!(
 199         "extended_cause_with_original_assoc_item_obligation {:?} {:?} {:?} {:?}",
 200         trait_ref, item, cause, pred
 201     );
 202     let items = match item {
 203         Some(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.items,
 204         _ => return,
 205     };
 206     let fix_span =
 207         |impl_item_ref: &hir::ImplItemRef<'_>| match tcx.hir().impl_item(impl_item_ref.id).kind {
 208             hir::ImplItemKind::Const(ty, _) | hir::ImplItemKind::TyAlias(ty) => ty.span,
 209             _ => impl_item_ref.span,
 210         };
 211
 212     // It is fine to skip the binder as we don't care about regions here.
 213     match pred.kind().skip_binder() {
 214         ty::PredicateKind::Projection(proj) => {
 215             // The obligation comes not from the current `impl` nor the `trait` being implemented,
 216             // but rather from a "second order" obligation, where an associated type has a
 217             // projection coming from another associated type. See
 218             // `src/test/ui/associated-types/point-at-type-on-obligation-failure.rs` and
 219             // `traits-assoc-type-in-supertrait-bad.rs`.
 220             if let ty::Projection(projection_ty) = proj.ty.kind() {
 221                 let trait_assoc_item = tcx.associated_item(projection_ty.item_def_id);
 222                 if let Some(impl_item_span) =
 223                     items.iter().find(|item| item.ident == trait_assoc_item.ident).map(fix_span)
 224                 {
 225                     cause.make_mut().span = impl_item_span;
 226                 }
 227             }
 228         }
 229         ty::PredicateKind::Trait(pred, _) => {
 230             // An associated item obligation born out of the `trait` failed to be met. An example
 231             // can be seen in `ui/associated-types/point-at-type-on-obligation-failure-2.rs`.
 232             debug!("extended_cause_with_original_assoc_item_obligation trait proj {:?}", pred);
 233             if let ty::Projection(ty::ProjectionTy { item_def_id, .. }) = *pred.self_ty().kind() {
 234                 if let Some(impl_item_span) = trait_assoc_items
 235                     .find(|i| i.def_id == item_def_id)
 236                     .and_then(|trait_assoc_item| {
 237                         items.iter().find(|i| i.ident == trait_assoc_item.ident).map(fix_span)
 238                     })
 239                 {
 240                     cause.make_mut().span = impl_item_span;
 241                 }
 242             }
 243         }
 244         _ => {}
 245     }
 246 }
 247
 248 impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
 249     fn tcx(&self) -> TyCtxt<'tcx> {
 250         self.infcx.tcx
 251     }
 252
 253     fn cause(&self, code: traits::ObligationCauseCode<'tcx>) -> traits::ObligationCause<'tcx> {
 254         traits::ObligationCause::new(self.span, self.body_id, code)
 255     }
 256
 257     fn normalize(mut self) -> Vec<traits::PredicateObligation<'tcx>> {
 258         let cause = self.cause(traits::MiscObligation);
 259         let infcx = &mut self.infcx;
 260         let param_env = self.param_env;
 261         let mut obligations = Vec::with_capacity(self.out.len());
 262         for mut obligation in self.out {
 263             assert!(!obligation.has_escaping_bound_vars());
 264             let mut selcx = traits::SelectionContext::new(infcx);
 265             // Don't normalize the whole obligation, the param env is either
 266             // already normalized, or we're currently normalizing the
 267             // param_env. Either way we should only normalize the predicate.
 268             let normalized_predicate = traits::project::normalize_with_depth_to(
 269                 &mut selcx,
 270                 param_env,
 271                 cause.clone(),
 272                 self.recursion_depth,
 273                 obligation.predicate,
 274                 &mut obligations,
 275             );
 276             obligation.predicate = normalized_predicate;
 277             obligations.push(obligation);
 278         }
 279         obligations
 280     }
 281
 282     /// Pushes the obligations required for `trait_ref` to be WF into `self.out`.
 283     fn compute_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>, elaborate: Elaborate) {
 284         let tcx = self.infcx.tcx;
 285         let obligations = self.nominal_obligations(trait_ref.def_id, trait_ref.substs);
 286
 287         debug!("compute_trait_ref obligations {:?}", obligations);
 288         let cause = self.cause(traits::MiscObligation);
 289         let param_env = self.param_env;
 290         let depth = self.recursion_depth;
 291
 292         let item = self.item;
 293
 294         let extend = |obligation: traits::PredicateObligation<'tcx>| {
 295             let mut cause = cause.clone();
 296             if let Some(parent_trait_ref) = obligation.predicate.to_opt_poly_trait_ref() {
 297                 let derived_cause = traits::DerivedObligationCause {
 298                     parent_trait_ref: parent_trait_ref.value,
 299                     parent_code: Lrc::new(obligation.cause.code.clone()),
 300                 };
 301                 cause.make_mut().code =
 302                     traits::ObligationCauseCode::DerivedObligation(derived_cause);
 303             }
 304             extend_cause_with_original_assoc_item_obligation(
 305                 tcx,
 306                 trait_ref,
 307                 item,
 308                 &mut cause,
 309                 &obligation.predicate,
 310                 tcx.associated_items(trait_ref.def_id).in_definition_order(),
 311             );
 312             traits::Obligation::with_depth(cause, depth, param_env, obligation.predicate)
 313         };
 314
 315         if let Elaborate::All = elaborate {
 316             let implied_obligations = traits::util::elaborate_obligations(tcx, obligations);
 317             let implied_obligations = implied_obligations.map(extend);
 318             self.out.extend(implied_obligations);
 319         } else {
 320             self.out.extend(obligations);
 321         }
 322
 323         let tcx = self.tcx();
 324         self.out.extend(
 325             trait_ref
 326                 .substs
 327                 .iter()
 328                 .enumerate()
 329                 .filter(|(_, arg)| {
 330                     matches!(arg.unpack(), GenericArgKind::Type(..) | GenericArgKind::Const(..))
 331                 })
 332                 .filter(|(_, arg)| !arg.has_escaping_bound_vars())
 333                 .map(|(i, arg)| {
 334                     let mut new_cause = cause.clone();
 335                     // The first subst is the self ty - use the correct span for it.
 336                     if i == 0 {
 337                         if let Some(hir::ItemKind::Impl(hir::Impl { self_ty, .. })) =
 338                             item.map(|i| &i.kind)
 339                         {
 340                             new_cause.make_mut().span = self_ty.span;
 341                         }
 342                     }
 343                     traits::Obligation::with_depth(
 344                         new_cause,
 345                         depth,
 346                         param_env,
 347                         ty::PredicateKind::WellFormed(arg).to_predicate(tcx),
 348                     )
 349                 }),
 350         );
 351     }
 352
 353     /// Pushes the obligations required for `trait_ref::Item` to be WF
 354     /// into `self.out`.
 355     fn compute_projection(&mut self, data: ty::ProjectionTy<'tcx>) {
 356         // A projection is well-formed if
 357         //
 358         // (a) its predicates hold (*)
 359         // (b) its substs are wf
 360         //
 361         // (*) The predicates of an associated type include the predicates of
 362         //     the trait that it's contained in. For example, given
 363         //
 364         // trait A<T>: Clone {
 365         //     type X where T: Copy;
 366         // }
 367         //
 368         // The predicates of `<() as A<i32>>::X` are:
 369         // [
 370         //     `(): Sized`
 371         //     `(): Clone`
 372         //     `(): A<i32>`
 373         //     `i32: Sized`
 374         //     `i32: Clone`
 375         //     `i32: Copy`
 376         // ]
 377         let obligations = self.nominal_obligations(data.item_def_id, data.substs);
 378         self.out.extend(obligations);
 379
 380         let tcx = self.tcx();
 381         let cause = self.cause(traits::MiscObligation);
 382         let param_env = self.param_env;
 383         let depth = self.recursion_depth;
 384
 385         self.out.extend(
 386             data.substs
 387                 .iter()
 388                 .filter(|arg| {
 389                     matches!(arg.unpack(), GenericArgKind::Type(..) | GenericArgKind::Const(..))
 390                 })
 391                 .filter(|arg| !arg.has_escaping_bound_vars())
 392                 .map(|arg| {
 393                     traits::Obligation::with_depth(
 394                         cause.clone(),
 395                         depth,
 396                         param_env,
 397                         ty::PredicateKind::WellFormed(arg).to_predicate(tcx),
 398                     )
 399                 }),
 400         );
 401     }
 402
 403     fn require_sized(&mut self, subty: Ty<'tcx>, cause: traits::ObligationCauseCode<'tcx>) {
 404         if !subty.has_escaping_bound_vars() {
 405             let cause = self.cause(cause);
 406             let trait_ref = ty::TraitRef {
 407                 def_id: self.infcx.tcx.require_lang_item(LangItem::Sized, None),
 408                 substs: self.infcx.tcx.mk_substs_trait(subty, &[]),
 409             };
 410             self.out.push(traits::Obligation::with_depth(
 411                 cause,
 412                 self.recursion_depth,
 413                 self.param_env,
 414                 trait_ref.without_const().to_predicate(self.infcx.tcx),
 415             ));
 416         }
 417     }
 418
 419     /// Pushes all the predicates needed to validate that `ty` is WF into `out`.
 420     fn compute(&mut self, arg: GenericArg<'tcx>) {
 421         let mut walker = arg.walk();
 422         let param_env = self.param_env;
 423         let depth = self.recursion_depth;
 424         while let Some(arg) = walker.next() {
 425             let ty = match arg.unpack() {
 426                 GenericArgKind::Type(ty) => ty,
 427
 428                 // No WF constraints for lifetimes being present, any outlives
 429                 // obligations are handled by the parent (e.g. `ty::Ref`).
 430                 GenericArgKind::Lifetime(_) => continue,
 431
 432                 GenericArgKind::Const(constant) => {
 433                     match constant.val {
 434                         ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs, promoted }) => {
 435                             assert!(promoted.is_none());
 436
 437                             let obligations = self.nominal_obligations(def.did, substs);
 438                             self.out.extend(obligations);
 439
 440                             let predicate = ty::PredicateKind::ConstEvaluatable(def, substs)
 441                                 .to_predicate(self.tcx());
 442                             let cause = self.cause(traits::MiscObligation);
 443                             self.out.push(traits::Obligation::with_depth(
 444                                 cause,
 445                                 self.recursion_depth,
 446                                 self.param_env,
 447                                 predicate,
 448                             ));
 449                         }
 450                         ty::ConstKind::Infer(infer) => {
 451                             let resolved = self.infcx.shallow_resolve(infer);
 452                             // the `InferConst` changed, meaning that we made progress.
 453                             if resolved != infer {
 454                                 let cause = self.cause(traits::MiscObligation);
 455
 456                                 let resolved_constant = self.infcx.tcx.mk_const(ty::Const {
 457                                     val: ty::ConstKind::Infer(resolved),
 458                                     ..*constant
 459                                 });
 460                                 self.out.push(traits::Obligation::with_depth(
 461                                     cause,
 462                                     self.recursion_depth,
 463                                     self.param_env,
 464                                     ty::PredicateKind::WellFormed(resolved_constant.into())
 465                                         .to_predicate(self.tcx()),
 466                                 ));
 467                             }
 468                         }
 469                         ty::ConstKind::Error(_)
 470                         | ty::ConstKind::Param(_)
 471                         | ty::ConstKind::Bound(..)
 472                         | ty::ConstKind::Placeholder(..) => {
 473                             // These variants are trivially WF, so nothing to do here.
 474                         }
 475                         ty::ConstKind::Value(..) => {
 476                             // FIXME: Enforce that values are structurally-matchable.
 477                         }
 478                     }
 479                     continue;
 480                 }
 481             };
 482
 483             match *ty.kind() {
 484                 ty::Bool
 485                 | ty::Char
 486                 | ty::Int(..)
 487                 | ty::Uint(..)
 488                 | ty::Float(..)
 489                 | ty::Error(_)
 490                 | ty::Str
 491                 | ty::GeneratorWitness(..)
 492                 | ty::Never
 493                 | ty::Param(_)
 494                 | ty::Bound(..)
 495                 | ty::Placeholder(..)
 496                 | ty::Foreign(..) => {
 497                     // WfScalar, WfParameter, etc
 498                 }
 499
 500                 // Can only infer to `ty::Int(_) | ty::Uint(_)`.
 501                 ty::Infer(ty::IntVar(_)) => {}
 502
 503                 // Can only infer to `ty::Float(_)`.
 504                 ty::Infer(ty::FloatVar(_)) => {}
 505
 506                 ty::Slice(subty) => {
 507                     self.require_sized(subty, traits::SliceOrArrayElem);
 508                 }
 509
 510                 ty::Array(subty, _) => {
 511                     self.require_sized(subty, traits::SliceOrArrayElem);
 512                     // Note that we handle the len is implicitly checked while walking `arg`.
 513                 }
 514
 515                 ty::Tuple(ref tys) => {
 516                     if let Some((_last, rest)) = tys.split_last() {
 517                         for elem in rest {
 518                             self.require_sized(elem.expect_ty(), traits::TupleElem);
 519                         }
 520                     }
 521                 }
 522
 523                 ty::RawPtr(_) => {
 524                     // Simple cases that are WF if their type args are WF.
 525                 }
 526
 527                 ty::Projection(data) => {
 528                     walker.skip_current_subtree(); // Subtree handled by compute_projection.
 529                     self.compute_projection(data);
 530                 }
 531
 532                 ty::Adt(def, substs) => {
 533                     // WfNominalType
 534                     let obligations = self.nominal_obligations(def.did, substs);
 535                     self.out.extend(obligations);
 536                 }
 537
 538                 ty::FnDef(did, substs) => {
 539                     let obligations = self.nominal_obligations(did, substs);
 540                     self.out.extend(obligations);
 541                 }
 542
 543                 ty::Ref(r, rty, _) => {
 544                     // WfReference
 545                     if !r.has_escaping_bound_vars() && !rty.has_escaping_bound_vars() {
 546                         let cause = self.cause(traits::ReferenceOutlivesReferent(ty));
 547                         self.out.push(traits::Obligation::with_depth(
 548                             cause,
 549                             depth,
 550                             param_env,
 551                             ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(rty, r))
 552                                 .to_predicate(self.tcx()),
 553                         ));
 554                     }
 555                 }
 556
 557                 ty::Generator(..) => {
 558                     // Walk ALL the types in the generator: this will
 559                     // include the upvar types as well as the yield
 560                     // type. Note that this is mildly distinct from
 561                     // the closure case, where we have to be careful
 562                     // about the signature of the closure. We don't
 563                     // have the problem of implied bounds here since
 564                     // generators don't take arguments.
 565                 }
 566
 567                 ty::Closure(_, substs) => {
 568                     // Only check the upvar types for WF, not the rest
 569                     // of the types within. This is needed because we
 570                     // capture the signature and it may not be WF
 571                     // without the implied bounds. Consider a closure
 572                     // like `|x: &'a T|` -- it may be that `T: 'a` is
 573                     // not known to hold in the creator's context (and
 574                     // indeed the closure may not be invoked by its
 575                     // creator, but rather turned to someone who *can*
 576                     // verify that).
 577                     //
 578                     // The special treatment of closures here really
 579                     // ought not to be necessary either; the problem
 580                     // is related to #25860 -- there is no way for us
 581                     // to express a fn type complete with the implied
 582                     // bounds that it is assuming. I think in reality
 583                     // the WF rules around fn are a bit messed up, and
 584                     // that is the rot problem: `fn(&'a T)` should
 585                     // probably always be WF, because it should be
 586                     // shorthand for something like `where(T: 'a) {
 587                     // fn(&'a T) }`, as discussed in #25860.
 588                     //
 589                     // Note that we are also skipping the generic
 590                     // types. This is consistent with the `outlives`
 591                     // code, but anyway doesn't matter: within the fn
 592                     // body where they are created, the generics will
 593                     // always be WF, and outside of that fn body we
 594                     // are not directly inspecting closure types
 595                     // anyway, except via auto trait matching (which
 596                     // only inspects the upvar types).
 597                     walker.skip_current_subtree(); // subtree handled below
 598                     // FIXME(eddyb) add the type to `walker` instead of recursing.
 599                     self.compute(substs.as_closure().tupled_upvars_ty().into());
 600                 }
 601
 602                 ty::FnPtr(_) => {
 603                     // let the loop iterate into the argument/return
 604                     // types appearing in the fn signature
 605                 }
 606
 607                 ty::Opaque(did, substs) => {
 608                     // all of the requirements on type parameters
 609                     // should've been checked by the instantiation
 610                     // of whatever returned this exact `impl Trait`.
 611
 612                     // for named opaque `impl Trait` types we still need to check them
 613                     if ty::is_impl_trait_defn(self.infcx.tcx, did).is_none() {
 614                         let obligations = self.nominal_obligations(did, substs);
 615                         self.out.extend(obligations);
 616                     }
 617                 }
 618
 619                 ty::Dynamic(data, r) => {
 620                     // WfObject
 621                     //
 622                     // Here, we defer WF checking due to higher-ranked
 623                     // regions. This is perhaps not ideal.
 624                     self.from_object_ty(ty, data, r);
 625
 626                     // FIXME(#27579) RFC also considers adding trait
 627                     // obligations that don't refer to Self and
 628                     // checking those
 629
 630                     let defer_to_coercion = self.tcx().features().object_safe_for_dispatch;
 631
 632                     if !defer_to_coercion {
 633                         let cause = self.cause(traits::MiscObligation);
 634                         let component_traits = data.auto_traits().chain(data.principal_def_id());
 635                         let tcx = self.tcx();
 636                         self.out.extend(component_traits.map(|did| {
 637                             traits::Obligation::with_depth(
 638                                 cause.clone(),
 639                                 depth,
 640                                 param_env,
 641                                 ty::PredicateKind::ObjectSafe(did).to_predicate(tcx),
 642                             )
 643                         }));
 644                     }
 645                 }
 646
 647                 // Inference variables are the complicated case, since we don't
 648                 // know what type they are. We do two things:
 649                 //
 650                 // 1. Check if they have been resolved, and if so proceed with
 651                 //    THAT type.
 652                 // 2. If not, we've at least simplified things (e.g., we went
 653                 //    from `Vec<$0>: WF` to `$0: WF`), so we can
 654                 //    register a pending obligation and keep
 655                 //    moving. (Goal is that an "inductive hypothesis"
 656                 //    is satisfied to ensure termination.)
 657                 // See also the comment on `fn obligations`, describing "livelock"
 658                 // prevention, which happens before this can be reached.
 659                 ty::Infer(_) => {
 660                     let ty = self.infcx.shallow_resolve(ty);
 661                     if let ty::Infer(ty::TyVar(_)) = ty.kind() {
 662                         // Not yet resolved, but we've made progress.
 663                         let cause = self.cause(traits::MiscObligation);
 664                         self.out.push(traits::Obligation::with_depth(
 665                             cause,
 666                             self.recursion_depth,
 667                             param_env,
 668                             ty::PredicateKind::WellFormed(ty.into()).to_predicate(self.tcx()),
 669                         ));
 670                     } else {
 671                         // Yes, resolved, proceed with the result.
 672                         // FIXME(eddyb) add the type to `walker` instead of recursing.
 673                         self.compute(ty.into());
 674                     }
 675                 }
 676             }
 677         }
 678     }
 679
 680     fn nominal_obligations(
 681         &mut self,
 682         def_id: DefId,
 683         substs: SubstsRef<'tcx>,
 684     ) -> Vec<traits::PredicateObligation<'tcx>> {
 685         let predicates = self.infcx.tcx.predicates_of(def_id);
 686         let mut origins = vec![def_id; predicates.predicates.len()];
 687         let mut head = predicates;
 688         while let Some(parent) = head.parent {
 689             head = self.infcx.tcx.predicates_of(parent);
 690             origins.extend(iter::repeat(parent).take(head.predicates.len()));
 691         }
 692
 693         let predicates = predicates.instantiate(self.infcx.tcx, substs);
 694         debug_assert_eq!(predicates.predicates.len(), origins.len());
 695
 696         iter::zip(iter::zip(predicates.predicates, predicates.spans), origins.into_iter().rev())
 697             .map(|((pred, span), origin_def_id)| {
 698                 let cause = self.cause(traits::BindingObligation(origin_def_id, span));
 699                 traits::Obligation::with_depth(cause, self.recursion_depth, self.param_env, pred)
 700             })
 701             .filter(|pred| !pred.has_escaping_bound_vars())
 702             .collect()
 703     }
 704
 705     fn from_object_ty(
 706         &mut self,
 707         ty: Ty<'tcx>,
 708         data: &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>,
 709         region: ty::Region<'tcx>,
 710     ) {
 711         // Imagine a type like this:
 712         //
 713         //     trait Foo { }
 714         //     trait Bar<'c> : 'c { }
 715         //
 716         //     &'b (Foo+'c+Bar<'d>)
 717         //         ^
 718         //
 719         // In this case, the following relationships must hold:
 720         //
 721         //     'b <= 'c
 722         //     'd <= 'c
 723         //
 724         // The first conditions is due to the normal region pointer
 725         // rules, which say that a reference cannot outlive its
 726         // referent.
 727         //
 728         // The final condition may be a bit surprising. In particular,
 729         // you may expect that it would have been `'c <= 'd`, since
 730         // usually lifetimes of outer things are conservative
 731         // approximations for inner things. However, it works somewhat
 732         // differently with trait objects: here the idea is that if the
 733         // user specifies a region bound (`'c`, in this case) it is the
 734         // "master bound" that *implies* that bounds from other traits are
 735         // all met. (Remember that *all bounds* in a type like
 736         // `Foo+Bar+Zed` must be met, not just one, hence if we write
 737         // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
 738         // 'y.)
 739         //
 740         // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
 741         // am looking forward to the future here.
 742         if !data.has_escaping_bound_vars() && !region.has_escaping_bound_vars() {
 743             let implicit_bounds = object_region_bounds(self.infcx.tcx, data);
 744
 745             let explicit_bound = region;
 746
 747             self.out.reserve(implicit_bounds.len());
 748             for implicit_bound in implicit_bounds {
 749                 let cause = self.cause(traits::ObjectTypeBound(ty, explicit_bound));
 750                 let outlives =
 751                     ty::Binder::dummy(ty::OutlivesPredicate(explicit_bound, implicit_bound));
 752                 self.out.push(traits::Obligation::with_depth(
 753                     cause,
 754                     self.recursion_depth,
 755                     self.param_env,
 756                     outlives.to_predicate(self.infcx.tcx),
 757                 ));
 758             }
 759         }
 760     }
 761 }
 762
 763 /// Given an object type like `SomeTrait + Send`, computes the lifetime
 764 /// bounds that must hold on the elided self type. These are derived
 765 /// from the declarations of `SomeTrait`, `Send`, and friends -- if
 766 /// they declare `trait SomeTrait : 'static`, for example, then
 767 /// `'static` would appear in the list. The hard work is done by
 768 /// `infer::required_region_bounds`, see that for more information.
 769 pub fn object_region_bounds<'tcx>(
 770     tcx: TyCtxt<'tcx>,
 771     existential_predicates: &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>,
 772 ) -> Vec<ty::Region<'tcx>> {
 773     // Since we don't actually *know* the self type for an object,
 774     // this "open(err)" serves as a kind of dummy standin -- basically
 775     // a placeholder type.
 776     let open_ty = tcx.mk_ty_infer(ty::FreshTy(0));
 777
 778     let predicates = existential_predicates.iter().filter_map(|predicate| {
 779         if let ty::ExistentialPredicate::Projection(_) = predicate.skip_binder() {
 780             None
 781         } else {
 782             Some(predicate.with_self_ty(tcx, open_ty))
 783         }
 784     });
 785
 786     required_region_bounds(tcx, open_ty, predicates)
 787 }