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