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