src/librustc/traits/object_safety.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! "Object safety" refers to the ability for a trait to be converted
  12 //! to an object. In general, traits may only be converted to an
  13 //! object if all of their methods meet certain criteria. In particular,
  14 //! they must:
  15 //!
  16 //!   - have a suitable receiver from which we can extract a vtable and coerce to a "thin" version
  17 //!     that doesn't contain the vtable;
  18 //!   - not reference the erased type `Self` except for in this receiver;
  19 //!   - not have generic type parameters
  20
  21 use super::elaborate_predicates;
  22
  23 use hir::def_id::DefId;
  24 use lint;
  25 use traits::{self, Obligation, ObligationCause};
  26 use ty::{self, Ty, TyCtxt, TypeFoldable, Predicate, ToPredicate};
  27 use ty::subst::{Subst, Substs};
  28 use std::borrow::Cow;
  29 use std::iter::{self};
  30 use syntax::ast::{self, Name};
  31 use syntax_pos::Span;
  32
  33 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  34 pub enum ObjectSafetyViolation {
  35     /// Self : Sized declared on the trait
  36     SizedSelf,
  37
  38     /// Supertrait reference references `Self` an in illegal location
  39     /// (e.g. `trait Foo : Bar<Self>`)
  40     SupertraitSelf,
  41
  42     /// Method has something illegal
  43     Method(ast::Name, MethodViolationCode),
  44
  45     /// Associated const
  46     AssociatedConst(ast::Name),
  47 }
  48
  49 impl ObjectSafetyViolation {
  50     pub fn error_msg(&self) -> Cow<'static, str> {
  51         match *self {
  52             ObjectSafetyViolation::SizedSelf =>
  53                 "the trait cannot require that `Self : Sized`".into(),
  54             ObjectSafetyViolation::SupertraitSelf =>
  55                 "the trait cannot use `Self` as a type parameter \
  56                  in the supertraits or where-clauses".into(),
  57             ObjectSafetyViolation::Method(name, MethodViolationCode::StaticMethod) =>
  58                 format!("method `{}` has no receiver", name).into(),
  59             ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelf) =>
  60                 format!("method `{}` references the `Self` type \
  61                          in its arguments or return type", name).into(),
  62             ObjectSafetyViolation::Method(name,
  63                                             MethodViolationCode::WhereClauseReferencesSelf(_)) =>
  64                 format!("method `{}` references the `Self` type in where clauses", name).into(),
  65             ObjectSafetyViolation::Method(name, MethodViolationCode::Generic) =>
  66                 format!("method `{}` has generic type parameters", name).into(),
  67             ObjectSafetyViolation::Method(name, MethodViolationCode::UndispatchableReceiver) =>
  68                 format!("method `{}`'s receiver cannot be dispatched on", name).into(),
  69             ObjectSafetyViolation::AssociatedConst(name) =>
  70                 format!("the trait cannot contain associated consts like `{}`", name).into(),
  71         }
  72     }
  73 }
  74
  75 /// Reasons a method might not be object-safe.
  76 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  77 pub enum MethodViolationCode {
  78     /// e.g., `fn foo()`
  79     StaticMethod,
  80
  81     /// e.g., `fn foo(&self, x: Self)` or `fn foo(&self) -> Self`
  82     ReferencesSelf,
  83
  84     /// e.g. `fn foo(&self) where Self: Clone`
  85     WhereClauseReferencesSelf(Span),
  86
  87     /// e.g., `fn foo<A>()`
  88     Generic,
  89
  90     /// the method's receiver (`self` argument) can't be dispatched on
  91     UndispatchableReceiver,
  92 }
  93
  94 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
  95
  96     /// Returns the object safety violations that affect
  97     /// astconv - currently, Self in supertraits. This is needed
  98     /// because `object_safety_violations` can't be used during
  99     /// type collection.
 100     pub fn astconv_object_safety_violations(self, trait_def_id: DefId)
 101                                             -> Vec<ObjectSafetyViolation>
 102     {
 103         let violations = traits::supertrait_def_ids(self, trait_def_id)
 104             .filter(|&def_id| self.predicates_reference_self(def_id, true))
 105             .map(|_| ObjectSafetyViolation::SupertraitSelf)
 106             .collect();
 107
 108         debug!("astconv_object_safety_violations(trait_def_id={:?}) = {:?}",
 109                trait_def_id,
 110                violations);
 111
 112         violations
 113     }
 114
 115     pub fn object_safety_violations(self, trait_def_id: DefId)
 116                                     -> Vec<ObjectSafetyViolation>
 117     {
 118         debug!("object_safety_violations: {:?}", trait_def_id);
 119
 120         traits::supertrait_def_ids(self, trait_def_id)
 121             .flat_map(|def_id| self.object_safety_violations_for_trait(def_id))
 122             .collect()
 123     }
 124
 125     fn object_safety_violations_for_trait(self, trait_def_id: DefId)
 126                                           -> Vec<ObjectSafetyViolation>
 127     {
 128         // Check methods for violations.
 129         let mut violations: Vec<_> = self.associated_items(trait_def_id)
 130             .filter(|item| item.kind == ty::AssociatedKind::Method)
 131             .filter_map(|item|
 132                 self.object_safety_violation_for_method(trait_def_id, &item)
 133                     .map(|code| ObjectSafetyViolation::Method(item.ident.name, code))
 134             ).filter(|violation| {
 135                 if let ObjectSafetyViolation::Method(_,
 136                     MethodViolationCode::WhereClauseReferencesSelf(span)) = violation
 137                 {
 138                     // Using `CRATE_NODE_ID` is wrong, but it's hard to get a more precise id.
 139                     // It's also hard to get a use site span, so we use the method definition span.
 140                     self.lint_node_note(
 141                         lint::builtin::WHERE_CLAUSES_OBJECT_SAFETY,
 142                         ast::CRATE_NODE_ID,
 143                         *span,
 144                         &format!("the trait `{}` cannot be made into an object",
 145                                  self.item_path_str(trait_def_id)),
 146                         &violation.error_msg());
 147                     false
 148                 } else {
 149                     true
 150                 }
 151             }).collect();
 152
 153         // Check the trait itself.
 154         if self.trait_has_sized_self(trait_def_id) {
 155             violations.push(ObjectSafetyViolation::SizedSelf);
 156         }
 157         if self.predicates_reference_self(trait_def_id, false) {
 158             violations.push(ObjectSafetyViolation::SupertraitSelf);
 159         }
 160
 161         violations.extend(self.associated_items(trait_def_id)
 162             .filter(|item| item.kind == ty::AssociatedKind::Const)
 163             .map(|item| ObjectSafetyViolation::AssociatedConst(item.ident.name)));
 164
 165         debug!("object_safety_violations_for_trait(trait_def_id={:?}) = {:?}",
 166                trait_def_id,
 167                violations);
 168
 169         violations
 170     }
 171
 172     fn predicates_reference_self(
 173         self,
 174         trait_def_id: DefId,
 175         supertraits_only: bool) -> bool
 176     {
 177         let trait_ref = ty::Binder::dummy(ty::TraitRef::identity(self, trait_def_id));
 178         let predicates = if supertraits_only {
 179             self.super_predicates_of(trait_def_id)
 180         } else {
 181             self.predicates_of(trait_def_id)
 182         };
 183         predicates
 184             .predicates
 185             .iter()
 186             .map(|(predicate, _)| predicate.subst_supertrait(self, &trait_ref))
 187             .any(|predicate| {
 188                 match predicate {
 189                     ty::Predicate::Trait(ref data) => {
 190                         // In the case of a trait predicate, we can skip the "self" type.
 191                         data.skip_binder().input_types().skip(1).any(|t| t.has_self_ty())
 192                     }
 193                     ty::Predicate::Projection(..) |
 194                     ty::Predicate::WellFormed(..) |
 195                     ty::Predicate::ObjectSafe(..) |
 196                     ty::Predicate::TypeOutlives(..) |
 197                     ty::Predicate::RegionOutlives(..) |
 198                     ty::Predicate::ClosureKind(..) |
 199                     ty::Predicate::Subtype(..) |
 200                     ty::Predicate::ConstEvaluatable(..) => {
 201                         false
 202                     }
 203                 }
 204             })
 205     }
 206
 207     fn trait_has_sized_self(self, trait_def_id: DefId) -> bool {
 208         self.generics_require_sized_self(trait_def_id)
 209     }
 210
 211     fn generics_require_sized_self(self, def_id: DefId) -> bool {
 212         let sized_def_id = match self.lang_items().sized_trait() {
 213             Some(def_id) => def_id,
 214             None => { return false; /* No Sized trait, can't require it! */ }
 215         };
 216
 217         // Search for a predicate like `Self : Sized` amongst the trait bounds.
 218         let predicates = self.predicates_of(def_id);
 219         let predicates = predicates.instantiate_identity(self).predicates;
 220         elaborate_predicates(self, predicates)
 221             .any(|predicate| match predicate {
 222                 ty::Predicate::Trait(ref trait_pred) if trait_pred.def_id() == sized_def_id => {
 223                     trait_pred.skip_binder().self_ty().is_self()
 224                 }
 225                 ty::Predicate::Projection(..) |
 226                 ty::Predicate::Trait(..) |
 227                 ty::Predicate::Subtype(..) |
 228                 ty::Predicate::RegionOutlives(..) |
 229                 ty::Predicate::WellFormed(..) |
 230                 ty::Predicate::ObjectSafe(..) |
 231                 ty::Predicate::ClosureKind(..) |
 232                 ty::Predicate::TypeOutlives(..) |
 233                 ty::Predicate::ConstEvaluatable(..) => {
 234                     false
 235                 }
 236             }
 237         )
 238     }
 239
 240     /// Returns `Some(_)` if this method makes the containing trait not object safe.
 241     fn object_safety_violation_for_method(self,
 242                                           trait_def_id: DefId,
 243                                           method: &ty::AssociatedItem)
 244                                           -> Option<MethodViolationCode>
 245     {
 246         // Any method that has a `Self : Sized` requisite is otherwise
 247         // exempt from the regulations.
 248         if self.generics_require_sized_self(method.def_id) {
 249             return None;
 250         }
 251
 252         self.virtual_call_violation_for_method(trait_def_id, method)
 253     }
 254
 255     /// We say a method is *vtable safe* if it can be invoked on a trait
 256     /// object.  Note that object-safe traits can have some
 257     /// non-vtable-safe methods, so long as they require `Self:Sized` or
 258     /// otherwise ensure that they cannot be used when `Self=Trait`.
 259     pub fn is_vtable_safe_method(self,
 260                                  trait_def_id: DefId,
 261                                  method: &ty::AssociatedItem)
 262                                  -> bool
 263     {
 264         // Any method that has a `Self : Sized` requisite can't be called.
 265         if self.generics_require_sized_self(method.def_id) {
 266             return false;
 267         }
 268
 269         match self.virtual_call_violation_for_method(trait_def_id, method) {
 270             None | Some(MethodViolationCode::WhereClauseReferencesSelf(_)) => true,
 271             Some(_) => false,
 272         }
 273     }
 274
 275     /// Returns `Some(_)` if this method cannot be called on a trait
 276     /// object; this does not necessarily imply that the enclosing trait
 277     /// is not object safe, because the method might have a where clause
 278     /// `Self:Sized`.
 279     fn virtual_call_violation_for_method(self,
 280                                          trait_def_id: DefId,
 281                                          method: &ty::AssociatedItem)
 282                                          -> Option<MethodViolationCode>
 283     {
 284         // The method's first parameter must be named `self`
 285         if !method.method_has_self_argument {
 286             return Some(MethodViolationCode::StaticMethod);
 287         }
 288
 289         let sig = self.fn_sig(method.def_id);
 290
 291         for input_ty in &sig.skip_binder().inputs()[1..] {
 292             if self.contains_illegal_self_type_reference(trait_def_id, input_ty) {
 293                 return Some(MethodViolationCode::ReferencesSelf);
 294             }
 295         }
 296         if self.contains_illegal_self_type_reference(trait_def_id, sig.output().skip_binder()) {
 297             return Some(MethodViolationCode::ReferencesSelf);
 298         }
 299
 300         // We can't monomorphize things like `fn foo<A>(...)`.
 301         if self.generics_of(method.def_id).own_counts().types != 0 {
 302             return Some(MethodViolationCode::Generic);
 303         }
 304
 305         if self.predicates_of(method.def_id).predicates.iter()
 306                 // A trait object can't claim to live more than the concrete type,
 307                 // so outlives predicates will always hold.
 308                 .cloned()
 309                 .filter(|(p, _)| p.to_opt_type_outlives().is_none())
 310                 .collect::<Vec<_>>()
 311                 // Do a shallow visit so that `contains_illegal_self_type_reference`
 312                 // may apply it's custom visiting.
 313                 .visit_tys_shallow(|t| self.contains_illegal_self_type_reference(trait_def_id, t)) {
 314             let span = self.def_span(method.def_id);
 315             return Some(MethodViolationCode::WhereClauseReferencesSelf(span));
 316         }
 317
 318         let receiver_ty = self.liberate_late_bound_regions(
 319             method.def_id,
 320             &sig.map_bound(|sig| sig.inputs()[0]),
 321         );
 322
 323         // until `unsized_locals` is fully implemented, `self: Self` can't be dispatched on.
 324         // However, this is already considered object-safe. We allow it as a special case here.
 325         // FIXME(mikeyhew) get rid of this `if` statement once `receiver_is_dispatchable` allows
 326         // `Receiver: Unsize<Receiver[Self => dyn Trait]>`
 327         if receiver_ty != self.mk_self_type() {
 328             if !self.receiver_is_dispatchable(method, receiver_ty) {
 329                 return Some(MethodViolationCode::UndispatchableReceiver);
 330             } else {
 331                 // sanity check to make sure the receiver actually has the layout of a pointer
 332
 333                 use ty::layout::Abi;
 334
 335                 let param_env = self.param_env(method.def_id);
 336
 337                 let abi_of_ty = |ty: Ty<'tcx>| -> &Abi {
 338                     match self.layout_of(param_env.and(ty)) {
 339                         Ok(layout) => &layout.abi,
 340                         Err(err) => bug!(
 341                             "Error: {}\n while computing layout for type {:?}", err, ty
 342                         )
 343                     }
 344                 };
 345
 346                 // e.g. Rc<()>
 347                 let unit_receiver_ty = self.receiver_for_self_ty(
 348                     receiver_ty, self.mk_unit(), method.def_id
 349                 );
 350
 351                 match abi_of_ty(unit_receiver_ty) {
 352                     &Abi::Scalar(..) => (),
 353                     abi => bug!("Receiver when Self = () should have a Scalar ABI, found {:?}", abi)
 354                 }
 355
 356                 let trait_object_ty = self.object_ty_for_trait(
 357                     trait_def_id, self.mk_region(ty::ReStatic)
 358                 );
 359
 360                 // e.g. Rc<dyn Trait>
 361                 let trait_object_receiver = self.receiver_for_self_ty(
 362                     receiver_ty, trait_object_ty, method.def_id
 363                 );
 364
 365                 match abi_of_ty(trait_object_receiver) {
 366                     &Abi::ScalarPair(..) => (),
 367                     abi => bug!(
 368                         "Receiver when Self = {} should have a ScalarPair ABI, found {:?}",
 369                         trait_object_ty, abi
 370                     )
 371                 }
 372             }
 373         }
 374
 375         None
 376     }
 377
 378     /// performs a type substitution to produce the version of receiver_ty when `Self = self_ty`
 379     /// e.g. for receiver_ty = `Rc<Self>` and self_ty = `Foo`, returns `Rc<Foo>`
 380     fn receiver_for_self_ty(
 381         self, receiver_ty: Ty<'tcx>, self_ty: Ty<'tcx>, method_def_id: DefId
 382     ) -> Ty<'tcx> {
 383         let substs = Substs::for_item(self, method_def_id, |param, _| {
 384             if param.index == 0 {
 385                 self_ty.into()
 386             } else {
 387                 self.mk_param_from_def(param)
 388             }
 389         });
 390
 391         receiver_ty.subst(self, substs)
 392     }
 393
 394     /// creates the object type for the current trait. For example,
 395     /// if the current trait is `Deref`, then this will be
 396     /// `dyn Deref<Target=Self::Target> + 'static`
 397     fn object_ty_for_trait(self, trait_def_id: DefId, lifetime: ty::Region<'tcx>) -> Ty<'tcx> {
 398         debug!("object_ty_for_trait: trait_def_id={:?}", trait_def_id);
 399
 400         let trait_ref = ty::TraitRef::identity(self, trait_def_id);
 401
 402         let trait_predicate = ty::ExistentialPredicate::Trait(
 403             ty::ExistentialTraitRef::erase_self_ty(self, trait_ref)
 404         );
 405
 406         let mut associated_types = traits::supertraits(self, ty::Binder::dummy(trait_ref))
 407             .flat_map(|trait_ref| self.associated_items(trait_ref.def_id()))
 408             .filter(|item| item.kind == ty::AssociatedKind::Type)
 409             .collect::<Vec<_>>();
 410
 411         // existential predicates need to be in a specific order
 412         associated_types.sort_by_cached_key(|item| self.def_path_hash(item.def_id));
 413
 414         let projection_predicates = associated_types.into_iter().map(|item| {
 415             ty::ExistentialPredicate::Projection(ty::ExistentialProjection {
 416                 ty: self.mk_projection(item.def_id, trait_ref.substs),
 417                 item_def_id: item.def_id,
 418                 substs: trait_ref.substs,
 419             })
 420         });
 421
 422         let existential_predicates = self.mk_existential_predicates(
 423             iter::once(trait_predicate).chain(projection_predicates)
 424         );
 425
 426         let object_ty = self.mk_dynamic(
 427             ty::Binder::dummy(existential_predicates),
 428             lifetime,
 429         );
 430
 431         debug!("object_ty_for_trait: object_ty=`{}`", object_ty);
 432
 433         object_ty
 434     }
 435
 436     /// checks the method's receiver (the `self` argument) can be dispatched on when `Self` is a
 437     /// trait object. We require that `DispatchableFromDyn` be implemented for the receiver type
 438     /// in the following way:
 439     /// - let `Receiver` be the type of the `self` argument, i.e `Self`, `&Self`, `Rc<Self>`
 440     /// - require the following bound:
 441     ///
 442     ///        Receiver[Self => T]: DispatchFromDyn<Receiver[Self => dyn Trait]>
 443     ///
 444     ///    where `Foo[X => Y]` means "the same type as `Foo`, but with `X` replaced with `Y`"
 445     ///   (substitution notation).
 446     ///
 447     /// some examples of receiver types and their required obligation
 448     /// - `&'a mut self` requires `&'a mut Self: DispatchFromDyn<&'a mut dyn Trait>`
 449     /// - `self: Rc<Self>` requires `Rc<Self>: DispatchFromDyn<Rc<dyn Trait>>`
 450     /// - `self: Pin<Box<Self>>` requires `Pin<Box<Self>>: DispatchFromDyn<Pin<Box<dyn Trait>>>`
 451     ///
 452     /// The only case where the receiver is not dispatchable, but is still a valid receiver
 453     /// type (just not object-safe), is when there is more than one level of pointer indirection.
 454     /// e.g. `self: &&Self`, `self: &Rc<Self>`, `self: Box<Box<Self>>`. In these cases, there
 455     /// is no way, or at least no inexpensive way, to coerce the receiver from the version where
 456     /// `Self = dyn Trait` to the version where `Self = T`, where `T` is the unknown erased type
 457     /// contained by the trait object, because the object that needs to be coerced is behind
 458     /// a pointer.
 459     ///
 460     /// In practice, we cannot use `dyn Trait` explicitly in the obligation because it would result
 461     /// in a new check that `Trait` is object safe, creating a cycle. So instead, we fudge a little
 462     /// by introducing a new type parameter `U` such that `Self: Unsize<U>` and `U: Trait + ?Sized`,
 463     /// and use `U` in place of `dyn Trait`. Written as a chalk-style query:
 464     ///
 465     ///     forall (U: Trait + ?Sized) {
 466     ///         if (Self: Unsize<U>) {
 467     ///             Receiver: DispatchFromDyn<Receiver[Self => U]>
 468     ///         }
 469     ///     }
 470     ///
 471     /// for `self: &'a mut Self`, this means `&'a mut Self: DispatchFromDyn<&'a mut U>`
 472     /// for `self: Rc<Self>`, this means `Rc<Self>: DispatchFromDyn<Rc<U>>`
 473     /// for `self: Pin<Box<Self>>`, this means `Pin<Box<Self>>: DispatchFromDyn<Pin<Box<U>>>`
 474     //
 475     // FIXME(mikeyhew) when unsized receivers are implemented as part of unsized rvalues, add this
 476     // fallback query: `Receiver: Unsize<Receiver[Self => U]>` to support receivers like
 477     // `self: Wrapper<Self>`.
 478     #[allow(dead_code)]
 479     fn receiver_is_dispatchable(
 480         self,
 481         method: &ty::AssociatedItem,
 482         receiver_ty: Ty<'tcx>,
 483     ) -> bool {
 484         debug!("receiver_is_dispatchable: method = {:?}, receiver_ty = {:?}", method, receiver_ty);
 485
 486         let traits = (self.lang_items().unsize_trait(),
 487                       self.lang_items().dispatch_from_dyn_trait());
 488         let (unsize_did, dispatch_from_dyn_did) = if let (Some(u), Some(cu)) = traits {
 489             (u, cu)
 490         } else {
 491             debug!("receiver_is_dispatchable: Missing Unsize or DispatchFromDyn traits");
 492             return false;
 493         };
 494
 495         // the type `U` in the query
 496         // use a bogus type parameter to mimick a forall(U) query using u32::MAX for now.
 497         // FIXME(mikeyhew) this is a total hack, and we should replace it when real forall queries
 498         // are implemented
 499         let unsized_self_ty: Ty<'tcx> = self.mk_ty_param(
 500             ::std::u32::MAX,
 501             Name::intern("RustaceansAreAwesome").as_interned_str(),
 502         );
 503
 504         // `Receiver[Self => U]`
 505         let unsized_receiver_ty = self.receiver_for_self_ty(
 506             receiver_ty, unsized_self_ty, method.def_id
 507         );
 508
 509         // create a modified param env, with `Self: Unsize<U>` and `U: Trait` added to caller bounds
 510         // `U: ?Sized` is already implied here
 511         let param_env = {
 512             let mut param_env = self.param_env(method.def_id);
 513
 514             // Self: Unsize<U>
 515             let unsize_predicate = ty::TraitRef {
 516                 def_id: unsize_did,
 517                 substs: self.mk_substs_trait(self.mk_self_type(), &[unsized_self_ty.into()]),
 518             }.to_predicate();
 519
 520             // U: Trait<Arg1, ..., ArgN>
 521             let trait_predicate = {
 522                 let substs = Substs::for_item(self, method.container.assert_trait(), |param, _| {
 523                     if param.index == 0 {
 524                         unsized_self_ty.into()
 525                     } else {
 526                         self.mk_param_from_def(param)
 527                     }
 528                 });
 529
 530                 ty::TraitRef {
 531                     def_id: unsize_did,
 532                     substs,
 533                 }.to_predicate()
 534             };
 535
 536             let caller_bounds: Vec<Predicate<'tcx>> = param_env.caller_bounds.iter().cloned()
 537                 .chain(iter::once(unsize_predicate))
 538                 .chain(iter::once(trait_predicate))
 539                 .collect();
 540
 541             param_env.caller_bounds = self.intern_predicates(&caller_bounds);
 542
 543             param_env
 544         };
 545
 546         // Receiver: DispatchFromDyn<Receiver[Self => U]>
 547         let obligation = {
 548             let predicate = ty::TraitRef {
 549                 def_id: dispatch_from_dyn_did,
 550                 substs: self.mk_substs_trait(receiver_ty, &[unsized_receiver_ty.into()]),
 551             }.to_predicate();
 552
 553             Obligation::new(
 554                 ObligationCause::dummy(),
 555                 param_env,
 556                 predicate,
 557             )
 558         };
 559
 560         self.infer_ctxt().enter(|ref infcx| {
 561             // the receiver is dispatchable iff the obligation holds
 562             infcx.predicate_must_hold(&obligation)
 563         })
 564     }
 565
 566     fn contains_illegal_self_type_reference(self,
 567                                             trait_def_id: DefId,
 568                                             ty: Ty<'tcx>)
 569                                             -> bool
 570     {
 571         // This is somewhat subtle. In general, we want to forbid
 572         // references to `Self` in the argument and return types,
 573         // since the value of `Self` is erased. However, there is one
 574         // exception: it is ok to reference `Self` in order to access
 575         // an associated type of the current trait, since we retain
 576         // the value of those associated types in the object type
 577         // itself.
 578         //
 579         // ```rust
 580         // trait SuperTrait {
 581         //     type X;
 582         // }
 583         //
 584         // trait Trait : SuperTrait {
 585         //     type Y;
 586         //     fn foo(&self, x: Self) // bad
 587         //     fn foo(&self) -> Self // bad
 588         //     fn foo(&self) -> Option<Self> // bad
 589         //     fn foo(&self) -> Self::Y // OK, desugars to next example
 590         //     fn foo(&self) -> <Self as Trait>::Y // OK
 591         //     fn foo(&self) -> Self::X // OK, desugars to next example
 592         //     fn foo(&self) -> <Self as SuperTrait>::X // OK
 593         // }
 594         // ```
 595         //
 596         // However, it is not as simple as allowing `Self` in a projected
 597         // type, because there are illegal ways to use `Self` as well:
 598         //
 599         // ```rust
 600         // trait Trait : SuperTrait {
 601         //     ...
 602         //     fn foo(&self) -> <Self as SomeOtherTrait>::X;
 603         // }
 604         // ```
 605         //
 606         // Here we will not have the type of `X` recorded in the
 607         // object type, and we cannot resolve `Self as SomeOtherTrait`
 608         // without knowing what `Self` is.
 609
 610         let mut supertraits: Option<Vec<ty::PolyTraitRef<'tcx>>> = None;
 611         let mut error = false;
 612         ty.maybe_walk(|ty| {
 613             match ty.sty {
 614                 ty::Param(ref param_ty) => {
 615                     if param_ty.is_self() {
 616                         error = true;
 617                     }
 618
 619                     false // no contained types to walk
 620                 }
 621
 622                 ty::Projection(ref data) => {
 623                     // This is a projected type `<Foo as SomeTrait>::X`.
 624
 625                     // Compute supertraits of current trait lazily.
 626                     if supertraits.is_none() {
 627                         let trait_ref = ty::Binder::bind(
 628                             ty::TraitRef::identity(self, trait_def_id),
 629                         );
 630                         supertraits = Some(traits::supertraits(self, trait_ref).collect());
 631                     }
 632
 633                     // Determine whether the trait reference `Foo as
 634                     // SomeTrait` is in fact a supertrait of the
 635                     // current trait. In that case, this type is
 636                     // legal, because the type `X` will be specified
 637                     // in the object type.  Note that we can just use
 638                     // direct equality here because all of these types
 639                     // are part of the formal parameter listing, and
 640                     // hence there should be no inference variables.
 641                     let projection_trait_ref = ty::Binder::bind(data.trait_ref(self));
 642                     let is_supertrait_of_current_trait =
 643                         supertraits.as_ref().unwrap().contains(&projection_trait_ref);
 644
 645                     if is_supertrait_of_current_trait {
 646                         false // do not walk contained types, do not report error, do collect $200
 647                     } else {
 648                         true // DO walk contained types, POSSIBLY reporting an error
 649                     }
 650                 }
 651
 652                 _ => true, // walk contained types, if any
 653             }
 654         });
 655
 656         error
 657     }
 658 }
 659
 660 pub(super) fn is_object_safe_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 661                                                 trait_def_id: DefId) -> bool {
 662     tcx.object_safety_violations(trait_def_id).is_empty()
 663 }