src/librustc/ty/contents.rs

   1 // Copyright 2012-2015 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 use hir::def_id::{DefId};
  12 use ty::{self, Ty, TyCtxt};
  13 use util::common::MemoizationMap;
  14 use util::nodemap::FnvHashMap;
  15
  16 use std::fmt;
  17 use std::ops;
  18
  19 use syntax::ast;
  20
  21 /// Type contents is how the type checker reasons about kinds.
  22 /// They track what kinds of things are found within a type.  You can
  23 /// think of them as kind of an "anti-kind".  They track the kinds of values
  24 /// and thinks that are contained in types.  Having a larger contents for
  25 /// a type tends to rule that type *out* from various kinds.  For example,
  26 /// a type that contains a reference is not sendable.
  27 ///
  28 /// The reason we compute type contents and not kinds is that it is
  29 /// easier for me (nmatsakis) to think about what is contained within
  30 /// a type than to think about what is *not* contained within a type.
  31 #[derive(Clone, Copy)]
  32 pub struct TypeContents {
  33     pub bits: u64
  34 }
  35
  36 macro_rules! def_type_content_sets {
  37     (mod $mname:ident { $($name:ident = $bits:expr),+ }) => {
  38         #[allow(non_snake_case)]
  39         mod $mname {
  40             use super::TypeContents;
  41             $(
  42                 #[allow(non_upper_case_globals)]
  43                 pub const $name: TypeContents = TypeContents { bits: $bits };
  44              )+
  45         }
  46     }
  47 }
  48
  49 def_type_content_sets! {
  50     mod TC {
  51         None                                = 0b0000_0000__0000_0000__0000,
  52
  53         // Things that are interior to the value (first nibble):
  54         InteriorUnsafe                      = 0b0000_0000__0000_0000__0010,
  55         InteriorParam                       = 0b0000_0000__0000_0000__0100,
  56         // InteriorAll                         = 0b00000000__00000000__1111,
  57
  58         // Things that are owned by the value (second and third nibbles):
  59         OwnsOwned                           = 0b0000_0000__0000_0001__0000,
  60         OwnsDtor                            = 0b0000_0000__0000_0010__0000,
  61         OwnsAll                             = 0b0000_0000__1111_1111__0000,
  62
  63         // Things that mean drop glue is necessary
  64         NeedsDrop                           = 0b0000_0000__0000_0111__0000,
  65
  66         // All bits
  67         All                                 = 0b1111_1111__1111_1111__1111
  68     }
  69 }
  70
  71 impl TypeContents {
  72     pub fn when(&self, cond: bool) -> TypeContents {
  73         if cond {*self} else {TC::None}
  74     }
  75
  76     pub fn intersects(&self, tc: TypeContents) -> bool {
  77         (self.bits & tc.bits) != 0
  78     }
  79
  80     pub fn owns_owned(&self) -> bool {
  81         self.intersects(TC::OwnsOwned)
  82     }
  83
  84     pub fn interior_param(&self) -> bool {
  85         self.intersects(TC::InteriorParam)
  86     }
  87
  88     pub fn interior_unsafe(&self) -> bool {
  89         self.intersects(TC::InteriorUnsafe)
  90     }
  91
  92     pub fn needs_drop(&self, _: TyCtxt) -> bool {
  93         self.intersects(TC::NeedsDrop)
  94     }
  95
  96     /// Includes only those bits that still apply when indirected through a `Box` pointer
  97     pub fn owned_pointer(&self) -> TypeContents {
  98         TC::OwnsOwned | (*self & TC::OwnsAll)
  99     }
 100
 101     pub fn union<T, F>(v: &[T], mut f: F) -> TypeContents where
 102         F: FnMut(&T) -> TypeContents,
 103     {
 104         v.iter().fold(TC::None, |tc, ty| tc | f(ty))
 105     }
 106
 107     pub fn has_dtor(&self) -> bool {
 108         self.intersects(TC::OwnsDtor)
 109     }
 110 }
 111
 112 impl ops::BitOr for TypeContents {
 113     type Output = TypeContents;
 114
 115     fn bitor(self, other: TypeContents) -> TypeContents {
 116         TypeContents {bits: self.bits | other.bits}
 117     }
 118 }
 119
 120 impl ops::BitAnd for TypeContents {
 121     type Output = TypeContents;
 122
 123     fn bitand(self, other: TypeContents) -> TypeContents {
 124         TypeContents {bits: self.bits & other.bits}
 125     }
 126 }
 127
 128 impl ops::Sub for TypeContents {
 129     type Output = TypeContents;
 130
 131     fn sub(self, other: TypeContents) -> TypeContents {
 132         TypeContents {bits: self.bits & !other.bits}
 133     }
 134 }
 135
 136 impl fmt::Debug for TypeContents {
 137     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 138         write!(f, "TypeContents({:b})", self.bits)
 139     }
 140 }
 141
 142 impl<'a, 'tcx> ty::TyS<'tcx> {
 143     pub fn type_contents(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> TypeContents {
 144         return tcx.tc_cache.memoize(self, || tc_ty(tcx, self, &mut FnvHashMap()));
 145
 146         fn tc_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 147                            ty: Ty<'tcx>,
 148                            cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents
 149         {
 150             // Subtle: Note that we are *not* using tcx.tc_cache here but rather a
 151             // private cache for this walk.  This is needed in the case of cyclic
 152             // types like:
 153             //
 154             //     struct List { next: Box<Option<List>>, ... }
 155             //
 156             // When computing the type contents of such a type, we wind up deeply
 157             // recursing as we go.  So when we encounter the recursive reference
 158             // to List, we temporarily use TC::None as its contents.  Later we'll
 159             // patch up the cache with the correct value, once we've computed it
 160             // (this is basically a co-inductive process, if that helps).  So in
 161             // the end we'll compute TC::OwnsOwned, in this case.
 162             //
 163             // The problem is, as we are doing the computation, we will also
 164             // compute an *intermediate* contents for, e.g., Option<List> of
 165             // TC::None.  This is ok during the computation of List itself, but if
 166             // we stored this intermediate value into tcx.tc_cache, then later
 167             // requests for the contents of Option<List> would also yield TC::None
 168             // which is incorrect.  This value was computed based on the crutch
 169             // value for the type contents of list.  The correct value is
 170             // TC::OwnsOwned.  This manifested as issue #4821.
 171             if let Some(tc) = cache.get(&ty) {
 172                 return *tc;
 173             }
 174             // Must check both caches!
 175             if let Some(tc) = tcx.tc_cache.borrow().get(&ty) {
 176                 return *tc;
 177             }
 178             cache.insert(ty, TC::None);
 179
 180             let result = match ty.sty {
 181                 // usize and isize are ffi-unsafe
 182                 ty::TyUint(ast::UintTy::Us) | ty::TyInt(ast::IntTy::Is) => {
 183                     TC::None
 184                 }
 185
 186                 // Scalar and unique types are sendable, and durable
 187                 ty::TyInfer(ty::FreshIntTy(_)) | ty::TyInfer(ty::FreshFloatTy(_)) |
 188                 ty::TyBool | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
 189                 ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar => {
 190                     TC::None
 191                 }
 192
 193                 ty::TyBox(typ) => {
 194                     tc_ty(tcx, typ, cache).owned_pointer()
 195                 }
 196
 197                 ty::TyTrait(_) => {
 198                     TC::All - TC::InteriorParam
 199                 }
 200
 201                 ty::TyRawPtr(_) => {
 202                     TC::None
 203                 }
 204
 205                 ty::TyRef(_, _) => {
 206                     TC::None
 207                 }
 208
 209                 ty::TyArray(ty, _) => {
 210                     tc_ty(tcx, ty, cache)
 211                 }
 212
 213                 ty::TySlice(ty) => {
 214                     tc_ty(tcx, ty, cache)
 215                 }
 216                 ty::TyStr => TC::None,
 217
 218                 ty::TyClosure(_, ref substs) => {
 219                     TypeContents::union(&substs.upvar_tys, |ty| tc_ty(tcx, &ty, cache))
 220                 }
 221
 222                 ty::TyTuple(ref tys) => {
 223                     TypeContents::union(&tys[..],
 224                                         |ty| tc_ty(tcx, *ty, cache))
 225                 }
 226
 227                 ty::TyStruct(def, substs) | ty::TyEnum(def, substs) => {
 228                     let mut res =
 229                         TypeContents::union(&def.variants, |v| {
 230                             TypeContents::union(&v.fields, |f| {
 231                                 tc_ty(tcx, f.ty(tcx, substs), cache)
 232                             })
 233                         });
 234
 235                     if def.has_dtor() {
 236                         res = res | TC::OwnsDtor;
 237                     }
 238
 239                     apply_lang_items(tcx, def.did, res)
 240                 }
 241
 242                 ty::TyProjection(..) |
 243                 ty::TyParam(_) |
 244                 ty::TyAnon(..) => {
 245                     TC::All
 246                 }
 247
 248                 ty::TyInfer(_) |
 249                 ty::TyError => {
 250                     bug!("asked to compute contents of error type");
 251                 }
 252             };
 253
 254             cache.insert(ty, result);
 255             result
 256         }
 257
 258         fn apply_lang_items<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 259                                       did: DefId, tc: TypeContents)
 260                                       -> TypeContents {
 261             if Some(did) == tcx.lang_items.unsafe_cell_type() {
 262                 tc | TC::InteriorUnsafe
 263             } else {
 264                 tc
 265             }
 266         }
 267     }
 268 }