]> git.proxmox.com Git - rustc.git/blob - src/librustc/ty/contents.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / 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<'tcx> ty::TyS<'tcx> {
143 pub fn type_contents(&'tcx self, cx: &TyCtxt<'tcx>) -> TypeContents {
144 return cx.tc_cache.memoize(self, || tc_ty(cx, self, &mut FnvHashMap()));
145
146 fn tc_ty<'tcx>(cx: &TyCtxt<'tcx>,
147 ty: Ty<'tcx>,
148 cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents
149 {
150 // Subtle: Note that we are *not* using cx.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 cx.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 match cache.get(&ty) {
172 Some(tc) => { return *tc; }
173 None => {}
174 }
175 match cx.tc_cache.borrow().get(&ty) { // Must check both caches!
176 Some(tc) => { return *tc; }
177 None => {}
178 }
179 cache.insert(ty, TC::None);
180
181 let result = match ty.sty {
182 // usize and isize are ffi-unsafe
183 ty::TyUint(ast::UintTy::Us) | ty::TyInt(ast::IntTy::Is) => {
184 TC::None
185 }
186
187 // Scalar and unique types are sendable, and durable
188 ty::TyInfer(ty::FreshIntTy(_)) | ty::TyInfer(ty::FreshFloatTy(_)) |
189 ty::TyBool | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
190 ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar => {
191 TC::None
192 }
193
194 ty::TyBox(typ) => {
195 tc_ty(cx, typ, cache).owned_pointer()
196 }
197
198 ty::TyTrait(_) => {
199 TC::All - TC::InteriorParam
200 }
201
202 ty::TyRawPtr(_) => {
203 TC::None
204 }
205
206 ty::TyRef(_, _) => {
207 TC::None
208 }
209
210 ty::TyArray(ty, _) => {
211 tc_ty(cx, ty, cache)
212 }
213
214 ty::TySlice(ty) => {
215 tc_ty(cx, ty, cache)
216 }
217 ty::TyStr => TC::None,
218
219 ty::TyClosure(_, ref substs) => {
220 TypeContents::union(&substs.upvar_tys, |ty| tc_ty(cx, &ty, cache))
221 }
222
223 ty::TyTuple(ref tys) => {
224 TypeContents::union(&tys[..],
225 |ty| tc_ty(cx, *ty, cache))
226 }
227
228 ty::TyStruct(def, substs) | ty::TyEnum(def, substs) => {
229 let mut res =
230 TypeContents::union(&def.variants, |v| {
231 TypeContents::union(&v.fields, |f| {
232 tc_ty(cx, f.ty(cx, substs), cache)
233 })
234 });
235
236 if def.has_dtor() {
237 res = res | TC::OwnsDtor;
238 }
239
240 apply_lang_items(cx, def.did, res)
241 }
242
243 ty::TyProjection(..) |
244 ty::TyParam(_) => {
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(cx: &TyCtxt, did: DefId, tc: TypeContents)
259 -> TypeContents {
260 if Some(did) == cx.lang_items.unsafe_cell_type() {
261 tc | TC::InteriorUnsafe
262 } else {
263 tc
264 }
265 }
266 }
267 }