]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
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 | ||
54a0048b SL |
11 | use hir::def_id::{DefId}; |
12 | use ty::{self, Ty, TyCtxt}; | |
9cc50fc6 | 13 | use util::common::MemoizationMap; |
e9174d1e SL |
14 | use util::nodemap::FnvHashMap; |
15 | ||
16 | use std::fmt; | |
17 | use std::ops; | |
18 | ||
b039eaaf | 19 | use syntax::ast; |
e9174d1e SL |
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 | ||
a7813a04 | 92 | pub fn needs_drop(&self, _: TyCtxt) -> bool { |
e9174d1e SL |
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 | ||
a7813a04 XL |
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())); | |
e9174d1e | 145 | |
a7813a04 XL |
146 | fn tc_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
147 | ty: Ty<'tcx>, | |
148 | cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents | |
e9174d1e | 149 | { |
a7813a04 | 150 | // Subtle: Note that we are *not* using tcx.tc_cache here but rather a |
e9174d1e SL |
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 | |
a7813a04 | 166 | // we stored this intermediate value into tcx.tc_cache, then later |
e9174d1e SL |
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. | |
3157f602 XL |
171 | if let Some(tc) = cache.get(&ty) { |
172 | return *tc; | |
e9174d1e | 173 | } |
3157f602 XL |
174 | // Must check both caches! |
175 | if let Some(tc) = tcx.tc_cache.borrow().get(&ty) { | |
176 | return *tc; | |
e9174d1e SL |
177 | } |
178 | cache.insert(ty, TC::None); | |
179 | ||
180 | let result = match ty.sty { | |
181 | // usize and isize are ffi-unsafe | |
7453a54e | 182 | ty::TyUint(ast::UintTy::Us) | ty::TyInt(ast::IntTy::Is) => { |
e9174d1e SL |
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(_) | | |
54a0048b | 189 | ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar => { |
e9174d1e SL |
190 | TC::None |
191 | } | |
192 | ||
193 | ty::TyBox(typ) => { | |
a7813a04 | 194 | tc_ty(tcx, typ, cache).owned_pointer() |
e9174d1e SL |
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, _) => { | |
a7813a04 | 210 | tc_ty(tcx, ty, cache) |
e9174d1e SL |
211 | } |
212 | ||
213 | ty::TySlice(ty) => { | |
a7813a04 | 214 | tc_ty(tcx, ty, cache) |
e9174d1e SL |
215 | } |
216 | ty::TyStr => TC::None, | |
217 | ||
218 | ty::TyClosure(_, ref substs) => { | |
a7813a04 | 219 | TypeContents::union(&substs.upvar_tys, |ty| tc_ty(tcx, &ty, cache)) |
e9174d1e SL |
220 | } |
221 | ||
222 | ty::TyTuple(ref tys) => { | |
223 | TypeContents::union(&tys[..], | |
a7813a04 | 224 | |ty| tc_ty(tcx, *ty, cache)) |
e9174d1e SL |
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| { | |
a7813a04 | 231 | tc_ty(tcx, f.ty(tcx, substs), cache) |
e9174d1e SL |
232 | }) |
233 | }); | |
234 | ||
235 | if def.has_dtor() { | |
236 | res = res | TC::OwnsDtor; | |
237 | } | |
238 | ||
a7813a04 | 239 | apply_lang_items(tcx, def.did, res) |
e9174d1e SL |
240 | } |
241 | ||
242 | ty::TyProjection(..) | | |
243 | ty::TyParam(_) => { | |
244 | TC::All | |
245 | } | |
246 | ||
247 | ty::TyInfer(_) | | |
248 | ty::TyError => { | |
54a0048b | 249 | bug!("asked to compute contents of error type"); |
e9174d1e SL |
250 | } |
251 | }; | |
252 | ||
253 | cache.insert(ty, result); | |
254 | result | |
255 | } | |
256 | ||
a7813a04 XL |
257 | fn apply_lang_items<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
258 | did: DefId, tc: TypeContents) | |
259 | -> TypeContents { | |
260 | if Some(did) == tcx.lang_items.unsafe_cell_type() { | |
e9174d1e SL |
261 | tc | TC::InteriorUnsafe |
262 | } else { | |
263 | tc | |
264 | } | |
265 | } | |
266 | } | |
267 | } |