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