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;
  17 //!   - not reference the erased type `Self` except for in this receiver;
  18 //!   - not have generic type parameters
  19
  20 use super::supertraits;
  21 use super::elaborate_predicates;
  22
  23 use hir::def_id::DefId;
  24 use ty::subst::{self, SelfSpace, TypeSpace};
  25 use traits;
  26 use ty::{self, ToPolyTraitRef, Ty, TyCtxt, TypeFoldable};
  27 use std::rc::Rc;
  28 use syntax::ast;
  29
  30 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
  31 pub enum ObjectSafetyViolation<'tcx> {
  32     /// Self : Sized declared on the trait
  33     SizedSelf,
  34
  35     /// Supertrait reference references `Self` an in illegal location
  36     /// (e.g. `trait Foo : Bar<Self>`)
  37     SupertraitSelf,
  38
  39     /// Method has something illegal
  40     Method(Rc<ty::Method<'tcx>>, MethodViolationCode),
  41 }
  42
  43 /// Reasons a method might not be object-safe.
  44 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  45 pub enum MethodViolationCode {
  46     /// e.g., `fn foo()`
  47     StaticMethod,
  48
  49     /// e.g., `fn foo(&self, x: Self)` or `fn foo(&self) -> Self`
  50     ReferencesSelf,
  51
  52     /// e.g., `fn foo<A>()`
  53     Generic,
  54 }
  55
  56 pub fn is_object_safe<'tcx>(tcx: &TyCtxt<'tcx>,
  57                             trait_def_id: DefId)
  58                             -> bool
  59 {
  60     // Because we query yes/no results frequently, we keep a cache:
  61     let def = tcx.lookup_trait_def(trait_def_id);
  62
  63     let result = def.object_safety().unwrap_or_else(|| {
  64         let result = object_safety_violations(tcx, trait_def_id).is_empty();
  65
  66         // Record just a yes/no result in the cache; this is what is
  67         // queried most frequently. Note that this may overwrite a
  68         // previous result, but always with the same thing.
  69         def.set_object_safety(result);
  70
  71         result
  72     });
  73
  74     debug!("is_object_safe({:?}) = {}", trait_def_id, result);
  75
  76     result
  77 }
  78
  79 /// Returns the object safety violations that affect
  80 /// astconv - currently, Self in supertraits. This is needed
  81 /// because `object_safety_violations` can't be used during
  82 /// type collection.
  83 pub fn astconv_object_safety_violations<'tcx>(tcx: &TyCtxt<'tcx>,
  84                                               trait_def_id: DefId)
  85                                               -> Vec<ObjectSafetyViolation<'tcx>>
  86 {
  87     let mut violations = vec![];
  88
  89     if supertraits_reference_self(tcx, trait_def_id) {
  90         violations.push(ObjectSafetyViolation::SupertraitSelf);
  91     }
  92
  93     debug!("object_safety_violations_for_trait(trait_def_id={:?}) = {:?}",
  94            trait_def_id,
  95            violations);
  96
  97     violations
  98 }
  99
 100 pub fn object_safety_violations<'tcx>(tcx: &TyCtxt<'tcx>,
 101                                       trait_def_id: DefId)
 102                                       -> Vec<ObjectSafetyViolation<'tcx>>
 103 {
 104     traits::supertrait_def_ids(tcx, trait_def_id)
 105         .flat_map(|def_id| object_safety_violations_for_trait(tcx, def_id))
 106         .collect()
 107 }
 108
 109 fn object_safety_violations_for_trait<'tcx>(tcx: &TyCtxt<'tcx>,
 110                                             trait_def_id: DefId)
 111                                             -> Vec<ObjectSafetyViolation<'tcx>>
 112 {
 113     // Check methods for violations.
 114     let mut violations: Vec<_> =
 115         tcx.trait_items(trait_def_id).iter()
 116         .filter_map(|item| {
 117             match *item {
 118                 ty::MethodTraitItem(ref m) => {
 119                     object_safety_violation_for_method(tcx, trait_def_id, &m)
 120                         .map(|code| ObjectSafetyViolation::Method(m.clone(), code))
 121                 }
 122                 _ => None,
 123             }
 124         })
 125         .collect();
 126
 127     // Check the trait itself.
 128     if trait_has_sized_self(tcx, trait_def_id) {
 129         violations.push(ObjectSafetyViolation::SizedSelf);
 130     }
 131     if supertraits_reference_self(tcx, trait_def_id) {
 132         violations.push(ObjectSafetyViolation::SupertraitSelf);
 133     }
 134
 135     debug!("object_safety_violations_for_trait(trait_def_id={:?}) = {:?}",
 136            trait_def_id,
 137            violations);
 138
 139     violations
 140 }
 141
 142 pub fn supertraits_reference_self<'tcx>(tcx: &TyCtxt<'tcx>,
 143                                         trait_def_id: DefId)
 144                                         -> bool
 145 {
 146     let trait_def = tcx.lookup_trait_def(trait_def_id);
 147     let trait_ref = trait_def.trait_ref.clone();
 148     let trait_ref = trait_ref.to_poly_trait_ref();
 149     let predicates = tcx.lookup_super_predicates(trait_def_id);
 150     predicates
 151         .predicates
 152         .into_iter()
 153         .map(|predicate| predicate.subst_supertrait(tcx, &trait_ref))
 154         .any(|predicate| {
 155             match predicate {
 156                 ty::Predicate::Trait(ref data) => {
 157                     // In the case of a trait predicate, we can skip the "self" type.
 158                     data.0.trait_ref.substs.types.get_slice(TypeSpace)
 159                                                  .iter()
 160                                                  .cloned()
 161                                                  .any(|t| t.has_self_ty())
 162                 }
 163                 ty::Predicate::Projection(..) |
 164                 ty::Predicate::WellFormed(..) |
 165                 ty::Predicate::ObjectSafe(..) |
 166                 ty::Predicate::TypeOutlives(..) |
 167                 ty::Predicate::RegionOutlives(..) |
 168                 ty::Predicate::Equate(..) => {
 169                     false
 170                 }
 171             }
 172         })
 173 }
 174
 175 fn trait_has_sized_self<'tcx>(tcx: &TyCtxt<'tcx>,
 176                               trait_def_id: DefId)
 177                               -> bool
 178 {
 179     let trait_def = tcx.lookup_trait_def(trait_def_id);
 180     let trait_predicates = tcx.lookup_predicates(trait_def_id);
 181     generics_require_sized_self(tcx, &trait_def.generics, &trait_predicates)
 182 }
 183
 184 fn generics_require_sized_self<'tcx>(tcx: &TyCtxt<'tcx>,
 185                                      generics: &ty::Generics<'tcx>,
 186                                      predicates: &ty::GenericPredicates<'tcx>)
 187                                      -> bool
 188 {
 189     let sized_def_id = match tcx.lang_items.sized_trait() {
 190         Some(def_id) => def_id,
 191         None => { return false; /* No Sized trait, can't require it! */ }
 192     };
 193
 194     // Search for a predicate like `Self : Sized` amongst the trait bounds.
 195     let free_substs = tcx.construct_free_substs(generics,
 196                                                 tcx.region_maps.node_extent(ast::DUMMY_NODE_ID));
 197     let predicates = predicates.instantiate(tcx, &free_substs).predicates.into_vec();
 198     elaborate_predicates(tcx, predicates)
 199         .any(|predicate| {
 200             match predicate {
 201                 ty::Predicate::Trait(ref trait_pred) if trait_pred.def_id() == sized_def_id => {
 202                     trait_pred.0.self_ty().is_self()
 203                 }
 204                 ty::Predicate::Projection(..) |
 205                 ty::Predicate::Trait(..) |
 206                 ty::Predicate::Equate(..) |
 207                 ty::Predicate::RegionOutlives(..) |
 208                 ty::Predicate::WellFormed(..) |
 209                 ty::Predicate::ObjectSafe(..) |
 210                 ty::Predicate::TypeOutlives(..) => {
 211                     false
 212                 }
 213             }
 214         })
 215 }
 216
 217 /// Returns `Some(_)` if this method makes the containing trait not object safe.
 218 fn object_safety_violation_for_method<'tcx>(tcx: &TyCtxt<'tcx>,
 219                                             trait_def_id: DefId,
 220                                             method: &ty::Method<'tcx>)
 221                                             -> Option<MethodViolationCode>
 222 {
 223     // Any method that has a `Self : Sized` requisite is otherwise
 224     // exempt from the regulations.
 225     if generics_require_sized_self(tcx, &method.generics, &method.predicates) {
 226         return None;
 227     }
 228
 229     virtual_call_violation_for_method(tcx, trait_def_id, method)
 230 }
 231
 232 /// We say a method is *vtable safe* if it can be invoked on a trait
 233 /// object.  Note that object-safe traits can have some
 234 /// non-vtable-safe methods, so long as they require `Self:Sized` or
 235 /// otherwise ensure that they cannot be used when `Self=Trait`.
 236 pub fn is_vtable_safe_method<'tcx>(tcx: &TyCtxt<'tcx>,
 237                                    trait_def_id: DefId,
 238                                    method: &ty::Method<'tcx>)
 239                                    -> bool
 240 {
 241     virtual_call_violation_for_method(tcx, trait_def_id, method).is_none()
 242 }
 243
 244 /// Returns `Some(_)` if this method cannot be called on a trait
 245 /// object; this does not necessarily imply that the enclosing trait
 246 /// is not object safe, because the method might have a where clause
 247 /// `Self:Sized`.
 248 fn virtual_call_violation_for_method<'tcx>(tcx: &TyCtxt<'tcx>,
 249                                            trait_def_id: DefId,
 250                                            method: &ty::Method<'tcx>)
 251                                            -> Option<MethodViolationCode>
 252 {
 253     // The method's first parameter must be something that derefs (or
 254     // autorefs) to `&self`. For now, we only accept `self`, `&self`
 255     // and `Box<Self>`.
 256     match method.explicit_self {
 257         ty::ExplicitSelfCategory::Static => {
 258             return Some(MethodViolationCode::StaticMethod);
 259         }
 260
 261         ty::ExplicitSelfCategory::ByValue |
 262         ty::ExplicitSelfCategory::ByReference(..) |
 263         ty::ExplicitSelfCategory::ByBox => {
 264         }
 265     }
 266
 267     // The `Self` type is erased, so it should not appear in list of
 268     // arguments or return type apart from the receiver.
 269     let ref sig = method.fty.sig;
 270     for &input_ty in &sig.0.inputs[1..] {
 271         if contains_illegal_self_type_reference(tcx, trait_def_id, input_ty) {
 272             return Some(MethodViolationCode::ReferencesSelf);
 273         }
 274     }
 275     if let ty::FnConverging(result_type) = sig.0.output {
 276         if contains_illegal_self_type_reference(tcx, trait_def_id, result_type) {
 277             return Some(MethodViolationCode::ReferencesSelf);
 278         }
 279     }
 280
 281     // We can't monomorphize things like `fn foo<A>(...)`.
 282     if !method.generics.types.is_empty_in(subst::FnSpace) {
 283         return Some(MethodViolationCode::Generic);
 284     }
 285
 286     None
 287 }
 288
 289 fn contains_illegal_self_type_reference<'tcx>(tcx: &TyCtxt<'tcx>,
 290                                               trait_def_id: DefId,
 291                                               ty: Ty<'tcx>)
 292                                               -> bool
 293 {
 294     // This is somewhat subtle. In general, we want to forbid
 295     // references to `Self` in the argument and return types,
 296     // since the value of `Self` is erased. However, there is one
 297     // exception: it is ok to reference `Self` in order to access
 298     // an associated type of the current trait, since we retain
 299     // the value of those associated types in the object type
 300     // itself.
 301     //
 302     // ```rust
 303     // trait SuperTrait {
 304     //     type X;
 305     // }
 306     //
 307     // trait Trait : SuperTrait {
 308     //     type Y;
 309     //     fn foo(&self, x: Self) // bad
 310     //     fn foo(&self) -> Self // bad
 311     //     fn foo(&self) -> Option<Self> // bad
 312     //     fn foo(&self) -> Self::Y // OK, desugars to next example
 313     //     fn foo(&self) -> <Self as Trait>::Y // OK
 314     //     fn foo(&self) -> Self::X // OK, desugars to next example
 315     //     fn foo(&self) -> <Self as SuperTrait>::X // OK
 316     // }
 317     // ```
 318     //
 319     // However, it is not as simple as allowing `Self` in a projected
 320     // type, because there are illegal ways to use `Self` as well:
 321     //
 322     // ```rust
 323     // trait Trait : SuperTrait {
 324     //     ...
 325     //     fn foo(&self) -> <Self as SomeOtherTrait>::X;
 326     // }
 327     // ```
 328     //
 329     // Here we will not have the type of `X` recorded in the
 330     // object type, and we cannot resolve `Self as SomeOtherTrait`
 331     // without knowing what `Self` is.
 332
 333     let mut supertraits: Option<Vec<ty::PolyTraitRef<'tcx>>> = None;
 334     let mut error = false;
 335     ty.maybe_walk(|ty| {
 336         match ty.sty {
 337             ty::TyParam(ref param_ty) => {
 338                 if param_ty.space == SelfSpace {
 339                     error = true;
 340                 }
 341
 342                 false // no contained types to walk
 343             }
 344
 345             ty::TyProjection(ref data) => {
 346                 // This is a projected type `<Foo as SomeTrait>::X`.
 347
 348                 // Compute supertraits of current trait lazily.
 349                 if supertraits.is_none() {
 350                     let trait_def = tcx.lookup_trait_def(trait_def_id);
 351                     let trait_ref = ty::Binder(trait_def.trait_ref.clone());
 352                     supertraits = Some(traits::supertraits(tcx, trait_ref).collect());
 353                 }
 354
 355                 // Determine whether the trait reference `Foo as
 356                 // SomeTrait` is in fact a supertrait of the
 357                 // current trait. In that case, this type is
 358                 // legal, because the type `X` will be specified
 359                 // in the object type.  Note that we can just use
 360                 // direct equality here because all of these types
 361                 // are part of the formal parameter listing, and
 362                 // hence there should be no inference variables.
 363                 let projection_trait_ref = ty::Binder(data.trait_ref.clone());
 364                 let is_supertrait_of_current_trait =
 365                     supertraits.as_ref().unwrap().contains(&projection_trait_ref);
 366
 367                 if is_supertrait_of_current_trait {
 368                     false // do not walk contained types, do not report error, do collect $200
 369                 } else {
 370                     true // DO walk contained types, POSSIBLY reporting an error
 371                 }
 372             }
 373
 374             _ => true, // walk contained types, if any
 375         }
 376     });
 377
 378     error
 379 }