]>
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 | ||
11 | //! misc. type-system utilities too small to deserve their own file | |
12 | ||
54a0048b | 13 | use hir::def_id::DefId; |
476ff2be | 14 | use hir::map::DefPathData; |
a7813a04 | 15 | use infer::InferCtxt; |
32a655c1 | 16 | use hir::map as hir_map; |
5bcae85e | 17 | use traits::{self, Reveal}; |
32a655c1 | 18 | use ty::{self, Ty, TyCtxt, TypeAndMut, TypeFlags, TypeFoldable}; |
54a0048b | 19 | use ty::{Disr, ParameterEnvironment}; |
5bcae85e | 20 | use ty::fold::TypeVisitor; |
54a0048b SL |
21 | use ty::layout::{Layout, LayoutError}; |
22 | use ty::TypeVariants::*; | |
476ff2be SL |
23 | use util::nodemap::FxHashMap; |
24 | use middle::lang_items; | |
54a0048b SL |
25 | |
26 | use rustc_const_math::{ConstInt, ConstIsize, ConstUsize}; | |
476ff2be | 27 | use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult}; |
e9174d1e | 28 | |
9e0c209e | 29 | use std::cell::RefCell; |
e9174d1e | 30 | use std::cmp; |
476ff2be | 31 | use std::hash::Hash; |
5bcae85e | 32 | use std::intrinsics; |
b039eaaf | 33 | use syntax::ast::{self, Name}; |
a7813a04 | 34 | use syntax::attr::{self, SignedInt, UnsignedInt}; |
3157f602 | 35 | use syntax_pos::Span; |
e9174d1e | 36 | |
54a0048b | 37 | use hir; |
e9174d1e SL |
38 | |
39 | pub trait IntTypeExt { | |
a7813a04 XL |
40 | fn to_ty<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx>; |
41 | fn disr_incr<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, val: Option<Disr>) | |
42 | -> Option<Disr>; | |
54a0048b | 43 | fn assert_ty_matches(&self, val: Disr); |
a7813a04 | 44 | fn initial_discriminant<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Disr; |
e9174d1e SL |
45 | } |
46 | ||
47 | impl IntTypeExt for attr::IntType { | |
a7813a04 | 48 | fn to_ty<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> { |
e9174d1e | 49 | match *self { |
a7813a04 XL |
50 | SignedInt(ast::IntTy::I8) => tcx.types.i8, |
51 | SignedInt(ast::IntTy::I16) => tcx.types.i16, | |
52 | SignedInt(ast::IntTy::I32) => tcx.types.i32, | |
53 | SignedInt(ast::IntTy::I64) => tcx.types.i64, | |
32a655c1 | 54 | SignedInt(ast::IntTy::I128) => tcx.types.i128, |
a7813a04 XL |
55 | SignedInt(ast::IntTy::Is) => tcx.types.isize, |
56 | UnsignedInt(ast::UintTy::U8) => tcx.types.u8, | |
57 | UnsignedInt(ast::UintTy::U16) => tcx.types.u16, | |
58 | UnsignedInt(ast::UintTy::U32) => tcx.types.u32, | |
59 | UnsignedInt(ast::UintTy::U64) => tcx.types.u64, | |
32a655c1 | 60 | UnsignedInt(ast::UintTy::U128) => tcx.types.u128, |
a7813a04 | 61 | UnsignedInt(ast::UintTy::Us) => tcx.types.usize, |
e9174d1e SL |
62 | } |
63 | } | |
64 | ||
a7813a04 | 65 | fn initial_discriminant<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Disr { |
e9174d1e | 66 | match *self { |
54a0048b SL |
67 | SignedInt(ast::IntTy::I8) => ConstInt::I8(0), |
68 | SignedInt(ast::IntTy::I16) => ConstInt::I16(0), | |
69 | SignedInt(ast::IntTy::I32) => ConstInt::I32(0), | |
70 | SignedInt(ast::IntTy::I64) => ConstInt::I64(0), | |
32a655c1 | 71 | SignedInt(ast::IntTy::I128) => ConstInt::I128(0), |
54a0048b | 72 | SignedInt(ast::IntTy::Is) => match tcx.sess.target.int_type { |
3157f602 | 73 | ast::IntTy::I16 => ConstInt::Isize(ConstIsize::Is16(0)), |
54a0048b SL |
74 | ast::IntTy::I32 => ConstInt::Isize(ConstIsize::Is32(0)), |
75 | ast::IntTy::I64 => ConstInt::Isize(ConstIsize::Is64(0)), | |
76 | _ => bug!(), | |
77 | }, | |
78 | UnsignedInt(ast::UintTy::U8) => ConstInt::U8(0), | |
79 | UnsignedInt(ast::UintTy::U16) => ConstInt::U16(0), | |
80 | UnsignedInt(ast::UintTy::U32) => ConstInt::U32(0), | |
81 | UnsignedInt(ast::UintTy::U64) => ConstInt::U64(0), | |
32a655c1 | 82 | UnsignedInt(ast::UintTy::U128) => ConstInt::U128(0), |
54a0048b | 83 | UnsignedInt(ast::UintTy::Us) => match tcx.sess.target.uint_type { |
3157f602 | 84 | ast::UintTy::U16 => ConstInt::Usize(ConstUsize::Us16(0)), |
54a0048b SL |
85 | ast::UintTy::U32 => ConstInt::Usize(ConstUsize::Us32(0)), |
86 | ast::UintTy::U64 => ConstInt::Usize(ConstUsize::Us64(0)), | |
87 | _ => bug!(), | |
88 | }, | |
e9174d1e SL |
89 | } |
90 | } | |
91 | ||
54a0048b SL |
92 | fn assert_ty_matches(&self, val: Disr) { |
93 | match (*self, val) { | |
94 | (SignedInt(ast::IntTy::I8), ConstInt::I8(_)) => {}, | |
95 | (SignedInt(ast::IntTy::I16), ConstInt::I16(_)) => {}, | |
96 | (SignedInt(ast::IntTy::I32), ConstInt::I32(_)) => {}, | |
97 | (SignedInt(ast::IntTy::I64), ConstInt::I64(_)) => {}, | |
32a655c1 | 98 | (SignedInt(ast::IntTy::I128), ConstInt::I128(_)) => {}, |
54a0048b SL |
99 | (SignedInt(ast::IntTy::Is), ConstInt::Isize(_)) => {}, |
100 | (UnsignedInt(ast::UintTy::U8), ConstInt::U8(_)) => {}, | |
101 | (UnsignedInt(ast::UintTy::U16), ConstInt::U16(_)) => {}, | |
102 | (UnsignedInt(ast::UintTy::U32), ConstInt::U32(_)) => {}, | |
103 | (UnsignedInt(ast::UintTy::U64), ConstInt::U64(_)) => {}, | |
32a655c1 | 104 | (UnsignedInt(ast::UintTy::U128), ConstInt::U128(_)) => {}, |
54a0048b SL |
105 | (UnsignedInt(ast::UintTy::Us), ConstInt::Usize(_)) => {}, |
106 | _ => bug!("disr type mismatch: {:?} vs {:?}", self, val), | |
e9174d1e SL |
107 | } |
108 | } | |
109 | ||
a7813a04 XL |
110 | fn disr_incr<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, val: Option<Disr>) |
111 | -> Option<Disr> { | |
112 | if let Some(val) = val { | |
113 | self.assert_ty_matches(val); | |
114 | (val + ConstInt::Infer(1)).ok() | |
115 | } else { | |
116 | Some(self.initial_discriminant(tcx)) | |
117 | } | |
e9174d1e SL |
118 | } |
119 | } | |
120 | ||
121 | ||
122 | #[derive(Copy, Clone)] | |
32a655c1 SL |
123 | pub enum CopyImplementationError<'tcx> { |
124 | InfrigingField(&'tcx ty::FieldDef), | |
e9174d1e SL |
125 | NotAnAdt, |
126 | HasDestructor | |
127 | } | |
128 | ||
129 | /// Describes whether a type is representable. For types that are not | |
130 | /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to | |
131 | /// distinguish between types that are recursive with themselves and types that | |
132 | /// contain a different recursive type. These cases can therefore be treated | |
133 | /// differently when reporting errors. | |
134 | /// | |
135 | /// The ordering of the cases is significant. They are sorted so that cmp::max | |
136 | /// will keep the "more erroneous" of two values. | |
137 | #[derive(Copy, Clone, PartialOrd, Ord, Eq, PartialEq, Debug)] | |
138 | pub enum Representability { | |
139 | Representable, | |
140 | ContainsRecursive, | |
141 | SelfRecursive, | |
142 | } | |
143 | ||
a7813a04 XL |
144 | impl<'tcx> ParameterEnvironment<'tcx> { |
145 | pub fn can_type_implement_copy<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
146 | self_type: Ty<'tcx>, span: Span) | |
32a655c1 | 147 | -> Result<(), CopyImplementationError> { |
e9174d1e | 148 | // FIXME: (@jroesch) float this code up |
32a655c1 SL |
149 | tcx.infer_ctxt(self.clone(), Reveal::NotSpecializable).enter(|infcx| { |
150 | let (adt, substs) = match self_type.sty { | |
151 | ty::TyAdt(adt, substs) => (adt, substs), | |
a7813a04 XL |
152 | _ => return Err(CopyImplementationError::NotAnAdt) |
153 | }; | |
e9174d1e | 154 | |
32a655c1 SL |
155 | let field_implements_copy = |field: &ty::FieldDef| { |
156 | let cause = traits::ObligationCause::dummy(); | |
157 | match traits::fully_normalize(&infcx, cause, &field.ty(tcx, substs)) { | |
158 | Ok(ty) => !infcx.type_moves_by_default(ty, span), | |
159 | Err(..) => false | |
160 | } | |
161 | }; | |
162 | ||
163 | for variant in &adt.variants { | |
164 | for field in &variant.fields { | |
165 | if !field_implements_copy(field) { | |
166 | return Err(CopyImplementationError::InfrigingField(field)); | |
167 | } | |
168 | } | |
169 | } | |
170 | ||
a7813a04 XL |
171 | if adt.has_dtor() { |
172 | return Err(CopyImplementationError::HasDestructor); | |
173 | } | |
e9174d1e | 174 | |
a7813a04 XL |
175 | Ok(()) |
176 | }) | |
e9174d1e SL |
177 | } |
178 | } | |
179 | ||
a7813a04 | 180 | impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { |
5bcae85e SL |
181 | pub fn has_error_field(self, ty: Ty<'tcx>) -> bool { |
182 | match ty.sty { | |
9e0c209e | 183 | ty::TyAdt(def, substs) => { |
5bcae85e SL |
184 | for field in def.all_fields() { |
185 | let field_ty = field.ty(self, substs); | |
186 | if let TyError = field_ty.sty { | |
187 | return true; | |
188 | } | |
189 | } | |
190 | } | |
191 | _ => () | |
192 | } | |
193 | false | |
194 | } | |
195 | ||
e9174d1e SL |
196 | /// Returns the type of element at index `i` in tuple or tuple-like type `t`. |
197 | /// For an enum `t`, `variant` is None only if `t` is a univariant enum. | |
a7813a04 | 198 | pub fn positional_element_ty(self, |
e9174d1e SL |
199 | ty: Ty<'tcx>, |
200 | i: usize, | |
201 | variant: Option<DefId>) -> Option<Ty<'tcx>> { | |
202 | match (&ty.sty, variant) { | |
9e0c209e SL |
203 | (&TyAdt(adt, substs), Some(vid)) => { |
204 | adt.variant_with_id(vid).fields.get(i).map(|f| f.ty(self, substs)) | |
e9174d1e | 205 | } |
9e0c209e SL |
206 | (&TyAdt(adt, substs), None) => { |
207 | // Don't use `struct_variant`, this may be a univariant enum. | |
208 | adt.variants[0].fields.get(i).map(|f| f.ty(self, substs)) | |
e9174d1e SL |
209 | } |
210 | (&TyTuple(ref v), None) => v.get(i).cloned(), | |
211 | _ => None | |
212 | } | |
213 | } | |
214 | ||
215 | /// Returns the type of element at field `n` in struct or struct-like type `t`. | |
216 | /// For an enum `t`, `variant` must be some def id. | |
a7813a04 | 217 | pub fn named_element_ty(self, |
e9174d1e SL |
218 | ty: Ty<'tcx>, |
219 | n: Name, | |
220 | variant: Option<DefId>) -> Option<Ty<'tcx>> { | |
221 | match (&ty.sty, variant) { | |
9e0c209e SL |
222 | (&TyAdt(adt, substs), Some(vid)) => { |
223 | adt.variant_with_id(vid).find_field_named(n).map(|f| f.ty(self, substs)) | |
e9174d1e | 224 | } |
9e0c209e SL |
225 | (&TyAdt(adt, substs), None) => { |
226 | adt.struct_variant().find_field_named(n).map(|f| f.ty(self, substs)) | |
e9174d1e SL |
227 | } |
228 | _ => return None | |
229 | } | |
230 | } | |
231 | ||
54a0048b SL |
232 | /// Returns the IntType representation. |
233 | /// This used to ensure `int_ty` doesn't contain `usize` and `isize` | |
234 | /// by converting them to their actual types. That doesn't happen anymore. | |
a7813a04 | 235 | pub fn enum_repr_type(self, opt_hint: Option<&attr::ReprAttr>) -> attr::IntType { |
54a0048b | 236 | match opt_hint { |
e9174d1e | 237 | // Feed in the given type |
9e0c209e | 238 | Some(&attr::ReprInt(int_t)) => int_t, |
e9174d1e SL |
239 | // ... but provide sensible default if none provided |
240 | // | |
241 | // NB. Historically `fn enum_variants` generate i64 here, while | |
242 | // rustc_typeck::check would generate isize. | |
7453a54e | 243 | _ => SignedInt(ast::IntTy::Is), |
54a0048b | 244 | } |
e9174d1e SL |
245 | } |
246 | ||
247 | /// Returns the deeply last field of nested structures, or the same type, | |
248 | /// if not a structure at all. Corresponds to the only possible unsized | |
249 | /// field, and its type can be used to determine unsizing strategy. | |
a7813a04 | 250 | pub fn struct_tail(self, mut ty: Ty<'tcx>) -> Ty<'tcx> { |
9e0c209e SL |
251 | while let TyAdt(def, substs) = ty.sty { |
252 | if !def.is_struct() { | |
253 | break | |
254 | } | |
e9174d1e SL |
255 | match def.struct_variant().fields.last() { |
256 | Some(f) => ty = f.ty(self, substs), | |
257 | None => break | |
258 | } | |
259 | } | |
260 | ty | |
261 | } | |
262 | ||
263 | /// Same as applying struct_tail on `source` and `target`, but only | |
264 | /// keeps going as long as the two types are instances of the same | |
265 | /// structure definitions. | |
266 | /// For `(Foo<Foo<T>>, Foo<Trait>)`, the result will be `(Foo<T>, Trait)`, | |
267 | /// whereas struct_tail produces `T`, and `Trait`, respectively. | |
a7813a04 | 268 | pub fn struct_lockstep_tails(self, |
e9174d1e SL |
269 | source: Ty<'tcx>, |
270 | target: Ty<'tcx>) | |
271 | -> (Ty<'tcx>, Ty<'tcx>) { | |
272 | let (mut a, mut b) = (source, target); | |
9e0c209e SL |
273 | while let (&TyAdt(a_def, a_substs), &TyAdt(b_def, b_substs)) = (&a.sty, &b.sty) { |
274 | if a_def != b_def || !a_def.is_struct() { | |
275 | break | |
e9174d1e | 276 | } |
9e0c209e SL |
277 | match a_def.struct_variant().fields.last() { |
278 | Some(f) => { | |
279 | a = f.ty(self, a_substs); | |
280 | b = f.ty(self, b_substs); | |
281 | } | |
282 | _ => break | |
e9174d1e SL |
283 | } |
284 | } | |
285 | (a, b) | |
286 | } | |
287 | ||
e9174d1e SL |
288 | /// Given a set of predicates that apply to an object type, returns |
289 | /// the region bounds that the (erased) `Self` type must | |
290 | /// outlive. Precisely *because* the `Self` type is erased, the | |
291 | /// parameter `erased_self_ty` must be supplied to indicate what type | |
292 | /// has been used to represent `Self` in the predicates | |
293 | /// themselves. This should really be a unique type; `FreshTy(0)` is a | |
294 | /// popular choice. | |
295 | /// | |
296 | /// NB: in some cases, particularly around higher-ranked bounds, | |
297 | /// this function returns a kind of conservative approximation. | |
298 | /// That is, all regions returned by this function are definitely | |
299 | /// required, but there may be other region bounds that are not | |
300 | /// returned, as well as requirements like `for<'a> T: 'a`. | |
301 | /// | |
302 | /// Requires that trait definitions have been processed so that we can | |
303 | /// elaborate predicates and walk supertraits. | |
a7813a04 | 304 | pub fn required_region_bounds(self, |
e9174d1e SL |
305 | erased_self_ty: Ty<'tcx>, |
306 | predicates: Vec<ty::Predicate<'tcx>>) | |
9e0c209e | 307 | -> Vec<&'tcx ty::Region> { |
e9174d1e SL |
308 | debug!("required_region_bounds(erased_self_ty={:?}, predicates={:?})", |
309 | erased_self_ty, | |
310 | predicates); | |
311 | ||
312 | assert!(!erased_self_ty.has_escaping_regions()); | |
313 | ||
314 | traits::elaborate_predicates(self, predicates) | |
315 | .filter_map(|predicate| { | |
316 | match predicate { | |
317 | ty::Predicate::Projection(..) | | |
318 | ty::Predicate::Trait(..) | | |
319 | ty::Predicate::Equate(..) | | |
320 | ty::Predicate::WellFormed(..) | | |
321 | ty::Predicate::ObjectSafe(..) | | |
a7813a04 | 322 | ty::Predicate::ClosureKind(..) | |
e9174d1e SL |
323 | ty::Predicate::RegionOutlives(..) => { |
324 | None | |
325 | } | |
326 | ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(t, r))) => { | |
327 | // Search for a bound of the form `erased_self_ty | |
328 | // : 'a`, but be wary of something like `for<'a> | |
329 | // erased_self_ty : 'a` (we interpret a | |
330 | // higher-ranked bound like that as 'static, | |
331 | // though at present the code in `fulfill.rs` | |
332 | // considers such bounds to be unsatisfiable, so | |
333 | // it's kind of a moot point since you could never | |
334 | // construct such an object, but this seems | |
335 | // correct even if that code changes). | |
336 | if t == erased_self_ty && !r.has_escaping_regions() { | |
337 | Some(r) | |
338 | } else { | |
339 | None | |
340 | } | |
341 | } | |
342 | } | |
343 | }) | |
344 | .collect() | |
345 | } | |
346 | ||
347 | /// Creates a hash of the type `Ty` which will be the same no matter what crate | |
348 | /// context it's calculated within. This is used by the `type_id` intrinsic. | |
5bcae85e | 349 | pub fn type_id_hash(self, ty: Ty<'tcx>) -> u64 { |
476ff2be | 350 | let mut hasher = TypeIdHasher::new(self); |
5bcae85e | 351 | hasher.visit_ty(ty); |
9e0c209e | 352 | hasher.finish() |
e9174d1e SL |
353 | } |
354 | ||
b039eaaf SL |
355 | /// Returns true if this ADT is a dtorck type. |
356 | /// | |
357 | /// Invoking the destructor of a dtorck type during usual cleanup | |
358 | /// (e.g. the glue emitted for stack unwinding) requires all | |
359 | /// lifetimes in the type-structure of `adt` to strictly outlive | |
360 | /// the adt value itself. | |
361 | /// | |
362 | /// If `adt` is not dtorck, then the adt's destructor can be | |
363 | /// invoked even when there are lifetimes in the type-structure of | |
364 | /// `adt` that do not strictly outlive the adt value itself. | |
365 | /// (This allows programs to make cyclic structures without | |
366 | /// resorting to unasfe means; see RFCs 769 and 1238). | |
476ff2be | 367 | pub fn is_adt_dtorck(self, adt: &ty::AdtDef) -> bool { |
e9174d1e SL |
368 | let dtor_method = match adt.destructor() { |
369 | Some(dtor) => dtor, | |
370 | None => return false | |
371 | }; | |
b039eaaf SL |
372 | |
373 | // RFC 1238: if the destructor method is tagged with the | |
374 | // attribute `unsafe_destructor_blind_to_params`, then the | |
375 | // compiler is being instructed to *assume* that the | |
376 | // destructor will not access borrowed data, | |
377 | // even if such data is otherwise reachable. | |
e9174d1e | 378 | // |
b039eaaf SL |
379 | // Such access can be in plain sight (e.g. dereferencing |
380 | // `*foo.0` of `Foo<'a>(&'a u32)`) or indirectly hidden | |
381 | // (e.g. calling `foo.0.clone()` of `Foo<T:Clone>`). | |
382 | return !self.has_attr(dtor_method, "unsafe_destructor_blind_to_params"); | |
383 | } | |
9e0c209e | 384 | |
476ff2be SL |
385 | pub fn closure_base_def_id(&self, def_id: DefId) -> DefId { |
386 | let mut def_id = def_id; | |
387 | while self.def_key(def_id).disambiguated_data.data == DefPathData::ClosureExpr { | |
388 | def_id = self.parent_def_id(def_id).unwrap_or_else(|| { | |
389 | bug!("closure {:?} has no parent", def_id); | |
390 | }); | |
391 | } | |
392 | def_id | |
9e0c209e SL |
393 | } |
394 | } | |
395 | ||
476ff2be | 396 | pub struct TypeIdHasher<'a, 'gcx: 'a+'tcx, 'tcx: 'a, W> { |
5bcae85e | 397 | tcx: TyCtxt<'a, 'gcx, 'tcx>, |
476ff2be | 398 | state: StableHasher<W>, |
5bcae85e SL |
399 | } |
400 | ||
476ff2be SL |
401 | impl<'a, 'gcx, 'tcx, W> TypeIdHasher<'a, 'gcx, 'tcx, W> |
402 | where W: StableHasherResult | |
403 | { | |
404 | pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Self { | |
405 | TypeIdHasher { tcx: tcx, state: StableHasher::new() } | |
9e0c209e SL |
406 | } |
407 | ||
476ff2be SL |
408 | pub fn finish(self) -> W { |
409 | self.state.finish() | |
5bcae85e SL |
410 | } |
411 | ||
476ff2be SL |
412 | pub fn hash<T: Hash>(&mut self, x: T) { |
413 | x.hash(&mut self.state); | |
9e0c209e SL |
414 | } |
415 | ||
5bcae85e SL |
416 | fn hash_discriminant_u8<T>(&mut self, x: &T) { |
417 | let v = unsafe { | |
418 | intrinsics::discriminant_value(x) | |
419 | }; | |
420 | let b = v as u8; | |
421 | assert_eq!(v, b as u64); | |
422 | self.hash(b) | |
423 | } | |
424 | ||
425 | fn def_id(&mut self, did: DefId) { | |
9e0c209e SL |
426 | // Hash the DefPath corresponding to the DefId, which is independent |
427 | // of compiler internal state. | |
428 | let path = self.tcx.def_path(did); | |
429 | self.def_path(&path) | |
430 | } | |
5bcae85e | 431 | |
32a655c1 | 432 | pub fn def_path(&mut self, def_path: &hir_map::DefPath) { |
9e0c209e | 433 | def_path.deterministic_hash_to(self.tcx, &mut self.state); |
5bcae85e SL |
434 | } |
435 | } | |
436 | ||
476ff2be SL |
437 | impl<'a, 'gcx, 'tcx, W> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx, W> |
438 | where W: StableHasherResult | |
439 | { | |
5bcae85e SL |
440 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool { |
441 | // Distinguish between the Ty variants uniformly. | |
442 | self.hash_discriminant_u8(&ty.sty); | |
443 | ||
444 | match ty.sty { | |
445 | TyInt(i) => self.hash(i), | |
446 | TyUint(u) => self.hash(u), | |
447 | TyFloat(f) => self.hash(f), | |
5bcae85e SL |
448 | TyArray(_, n) => self.hash(n), |
449 | TyRawPtr(m) | | |
450 | TyRef(_, m) => self.hash(m.mutbl), | |
451 | TyClosure(def_id, _) | | |
452 | TyAnon(def_id, _) | | |
9e0c209e SL |
453 | TyFnDef(def_id, ..) => self.def_id(def_id), |
454 | TyAdt(d, _) => self.def_id(d.did), | |
5bcae85e SL |
455 | TyFnPtr(f) => { |
456 | self.hash(f.unsafety); | |
457 | self.hash(f.abi); | |
458 | self.hash(f.sig.variadic()); | |
476ff2be | 459 | self.hash(f.sig.skip_binder().inputs().len()); |
5bcae85e | 460 | } |
476ff2be SL |
461 | TyDynamic(ref data, ..) => { |
462 | if let Some(p) = data.principal() { | |
463 | self.def_id(p.def_id()); | |
464 | } | |
465 | for d in data.auto_traits() { | |
466 | self.def_id(d); | |
467 | } | |
5bcae85e SL |
468 | } |
469 | TyTuple(tys) => { | |
470 | self.hash(tys.len()); | |
471 | } | |
472 | TyParam(p) => { | |
5bcae85e SL |
473 | self.hash(p.idx); |
474 | self.hash(p.name.as_str()); | |
475 | } | |
476 | TyProjection(ref data) => { | |
477 | self.def_id(data.trait_ref.def_id); | |
478 | self.hash(data.item_name.as_str()); | |
479 | } | |
480 | TyNever | | |
481 | TyBool | | |
482 | TyChar | | |
483 | TyStr | | |
9e0c209e SL |
484 | TySlice(_) => {} |
485 | ||
486 | TyError | | |
487 | TyInfer(_) => bug!("TypeIdHasher: unexpected type {}", ty) | |
5bcae85e SL |
488 | } |
489 | ||
490 | ty.super_visit_with(self) | |
491 | } | |
492 | ||
9e0c209e SL |
493 | fn visit_region(&mut self, r: &'tcx ty::Region) -> bool { |
494 | match *r { | |
495 | ty::ReErased => { | |
5bcae85e SL |
496 | self.hash::<u32>(0); |
497 | } | |
498 | ty::ReLateBound(db, ty::BrAnon(i)) => { | |
499 | assert!(db.depth > 0); | |
500 | self.hash::<u32>(db.depth); | |
501 | self.hash(i); | |
502 | } | |
9e0c209e | 503 | ty::ReStatic | |
5bcae85e SL |
504 | ty::ReEmpty | |
505 | ty::ReEarlyBound(..) | | |
506 | ty::ReLateBound(..) | | |
507 | ty::ReFree(..) | | |
508 | ty::ReScope(..) | | |
509 | ty::ReVar(..) | | |
510 | ty::ReSkolemized(..) => { | |
9e0c209e | 511 | bug!("TypeIdHasher: unexpected region {:?}", r) |
5bcae85e SL |
512 | } |
513 | } | |
514 | false | |
515 | } | |
516 | ||
517 | fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, x: &ty::Binder<T>) -> bool { | |
518 | // Anonymize late-bound regions so that, for example: | |
519 | // `for<'a, b> fn(&'a &'b T)` and `for<'a, b> fn(&'b &'a T)` | |
520 | // result in the same TypeId (the two types are equivalent). | |
521 | self.tcx.anonymize_late_bound_regions(x).super_visit_with(self) | |
522 | } | |
523 | } | |
524 | ||
a7813a04 XL |
525 | impl<'a, 'tcx> ty::TyS<'tcx> { |
526 | fn impls_bound(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
527 | param_env: &ParameterEnvironment<'tcx>, | |
476ff2be SL |
528 | def_id: DefId, |
529 | cache: &RefCell<FxHashMap<Ty<'tcx>, bool>>, | |
9e0c209e | 530 | span: Span) -> bool |
e9174d1e | 531 | { |
9e0c209e SL |
532 | if self.has_param_types() || self.has_self_ty() { |
533 | if let Some(result) = cache.borrow().get(self) { | |
534 | return *result; | |
535 | } | |
536 | } | |
537 | let result = | |
32a655c1 | 538 | tcx.infer_ctxt(param_env.clone(), Reveal::ExactMatch) |
9e0c209e | 539 | .enter(|infcx| { |
476ff2be | 540 | traits::type_known_to_meet_bound(&infcx, self, def_id, span) |
9e0c209e SL |
541 | }); |
542 | if self.has_param_types() || self.has_self_ty() { | |
543 | cache.borrow_mut().insert(self, result); | |
544 | } | |
545 | return result; | |
e9174d1e SL |
546 | } |
547 | ||
548 | // FIXME (@jroesch): I made this public to use it, not sure if should be private | |
a7813a04 XL |
549 | pub fn moves_by_default(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
550 | param_env: &ParameterEnvironment<'tcx>, | |
551 | span: Span) -> bool { | |
e9174d1e SL |
552 | if self.flags.get().intersects(TypeFlags::MOVENESS_CACHED) { |
553 | return self.flags.get().intersects(TypeFlags::MOVES_BY_DEFAULT); | |
554 | } | |
555 | ||
556 | assert!(!self.needs_infer()); | |
557 | ||
558 | // Fast-path for primitive types | |
559 | let result = match self.sty { | |
5bcae85e | 560 | TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) | TyNever | |
54a0048b | 561 | TyRawPtr(..) | TyFnDef(..) | TyFnPtr(_) | TyRef(_, TypeAndMut { |
e9174d1e SL |
562 | mutbl: hir::MutImmutable, .. |
563 | }) => Some(false), | |
564 | ||
32a655c1 | 565 | TyStr | TyRef(_, TypeAndMut { |
e9174d1e SL |
566 | mutbl: hir::MutMutable, .. |
567 | }) => Some(true), | |
568 | ||
476ff2be | 569 | TyArray(..) | TySlice(..) | TyDynamic(..) | TyTuple(..) | |
9e0c209e | 570 | TyClosure(..) | TyAdt(..) | TyAnon(..) | |
e9174d1e | 571 | TyProjection(..) | TyParam(..) | TyInfer(..) | TyError => None |
9e0c209e | 572 | }.unwrap_or_else(|| { |
476ff2be SL |
573 | !self.impls_bound(tcx, param_env, |
574 | tcx.require_lang_item(lang_items::CopyTraitLangItem), | |
575 | ¶m_env.is_copy_cache, span) }); | |
e9174d1e SL |
576 | |
577 | if !self.has_param_types() && !self.has_self_ty() { | |
578 | self.flags.set(self.flags.get() | if result { | |
579 | TypeFlags::MOVENESS_CACHED | TypeFlags::MOVES_BY_DEFAULT | |
580 | } else { | |
581 | TypeFlags::MOVENESS_CACHED | |
582 | }); | |
583 | } | |
584 | ||
585 | result | |
586 | } | |
587 | ||
588 | #[inline] | |
a7813a04 XL |
589 | pub fn is_sized(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
590 | param_env: &ParameterEnvironment<'tcx>, | |
591 | span: Span) -> bool | |
e9174d1e SL |
592 | { |
593 | if self.flags.get().intersects(TypeFlags::SIZEDNESS_CACHED) { | |
594 | return self.flags.get().intersects(TypeFlags::IS_SIZED); | |
595 | } | |
596 | ||
a7813a04 | 597 | self.is_sized_uncached(tcx, param_env, span) |
e9174d1e SL |
598 | } |
599 | ||
a7813a04 XL |
600 | fn is_sized_uncached(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
601 | param_env: &ParameterEnvironment<'tcx>, | |
602 | span: Span) -> bool { | |
e9174d1e SL |
603 | assert!(!self.needs_infer()); |
604 | ||
605 | // Fast-path for primitive types | |
606 | let result = match self.sty { | |
607 | TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) | | |
32a655c1 | 608 | TyRawPtr(..) | TyRef(..) | TyFnDef(..) | TyFnPtr(_) | |
5bcae85e | 609 | TyArray(..) | TyTuple(..) | TyClosure(..) | TyNever => Some(true), |
e9174d1e | 610 | |
476ff2be | 611 | TyStr | TyDynamic(..) | TySlice(_) => Some(false), |
e9174d1e | 612 | |
9e0c209e | 613 | TyAdt(..) | TyProjection(..) | TyParam(..) | |
5bcae85e | 614 | TyInfer(..) | TyAnon(..) | TyError => None |
9e0c209e | 615 | }.unwrap_or_else(|| { |
476ff2be SL |
616 | self.impls_bound(tcx, param_env, tcx.require_lang_item(lang_items::SizedTraitLangItem), |
617 | ¶m_env.is_sized_cache, span) }); | |
e9174d1e SL |
618 | |
619 | if !self.has_param_types() && !self.has_self_ty() { | |
620 | self.flags.set(self.flags.get() | if result { | |
621 | TypeFlags::SIZEDNESS_CACHED | TypeFlags::IS_SIZED | |
622 | } else { | |
623 | TypeFlags::SIZEDNESS_CACHED | |
624 | }); | |
625 | } | |
626 | ||
627 | result | |
628 | } | |
629 | ||
54a0048b | 630 | #[inline] |
a7813a04 XL |
631 | pub fn layout<'lcx>(&'tcx self, infcx: &InferCtxt<'a, 'tcx, 'lcx>) |
632 | -> Result<&'tcx Layout, LayoutError<'tcx>> { | |
633 | let tcx = infcx.tcx.global_tcx(); | |
54a0048b SL |
634 | let can_cache = !self.has_param_types() && !self.has_self_ty(); |
635 | if can_cache { | |
a7813a04 | 636 | if let Some(&cached) = tcx.layout_cache.borrow().get(&self) { |
54a0048b SL |
637 | return Ok(cached); |
638 | } | |
639 | } | |
640 | ||
9e0c209e SL |
641 | let rec_limit = tcx.sess.recursion_limit.get(); |
642 | let depth = tcx.layout_depth.get(); | |
643 | if depth > rec_limit { | |
644 | tcx.sess.fatal( | |
645 | &format!("overflow representing the type `{}`", self)); | |
646 | } | |
647 | ||
648 | tcx.layout_depth.set(depth+1); | |
54a0048b | 649 | let layout = Layout::compute_uncached(self, infcx)?; |
54a0048b | 650 | if can_cache { |
a7813a04 | 651 | tcx.layout_cache.borrow_mut().insert(self, layout); |
54a0048b | 652 | } |
9e0c209e | 653 | tcx.layout_depth.set(depth); |
54a0048b SL |
654 | Ok(layout) |
655 | } | |
656 | ||
e9174d1e SL |
657 | |
658 | /// Check whether a type is representable. This means it cannot contain unboxed | |
659 | /// structural recursion. This check is needed for structs and enums. | |
a7813a04 XL |
660 | pub fn is_representable(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span) |
661 | -> Representability { | |
e9174d1e SL |
662 | |
663 | // Iterate until something non-representable is found | |
a7813a04 XL |
664 | fn find_nonrepresentable<'a, 'tcx, It>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
665 | sp: Span, | |
666 | seen: &mut Vec<Ty<'tcx>>, | |
667 | iter: It) | |
668 | -> Representability | |
669 | where It: Iterator<Item=Ty<'tcx>> { | |
e9174d1e | 670 | iter.fold(Representability::Representable, |
a7813a04 | 671 | |r, ty| cmp::max(r, is_type_structurally_recursive(tcx, sp, seen, ty))) |
e9174d1e SL |
672 | } |
673 | ||
a7813a04 XL |
674 | fn are_inner_types_recursive<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span, |
675 | seen: &mut Vec<Ty<'tcx>>, ty: Ty<'tcx>) | |
676 | -> Representability { | |
e9174d1e SL |
677 | match ty.sty { |
678 | TyTuple(ref ts) => { | |
a7813a04 | 679 | find_nonrepresentable(tcx, sp, seen, ts.iter().cloned()) |
e9174d1e SL |
680 | } |
681 | // Fixed-length vectors. | |
682 | // FIXME(#11924) Behavior undecided for zero-length vectors. | |
683 | TyArray(ty, _) => { | |
a7813a04 | 684 | is_type_structurally_recursive(tcx, sp, seen, ty) |
e9174d1e | 685 | } |
9e0c209e | 686 | TyAdt(def, substs) => { |
a7813a04 | 687 | find_nonrepresentable(tcx, |
e9174d1e SL |
688 | sp, |
689 | seen, | |
a7813a04 | 690 | def.all_fields().map(|f| f.ty(tcx, substs))) |
e9174d1e SL |
691 | } |
692 | TyClosure(..) => { | |
693 | // this check is run on type definitions, so we don't expect | |
694 | // to see closure types | |
54a0048b | 695 | bug!("requires check invoked on inapplicable type: {:?}", ty) |
e9174d1e SL |
696 | } |
697 | _ => Representability::Representable, | |
698 | } | |
699 | } | |
700 | ||
476ff2be | 701 | fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool { |
e9174d1e | 702 | match ty.sty { |
9e0c209e | 703 | TyAdt(ty_def, _) => { |
e9174d1e SL |
704 | ty_def == def |
705 | } | |
706 | _ => false | |
707 | } | |
708 | } | |
709 | ||
710 | fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool { | |
711 | match (&a.sty, &b.sty) { | |
9e0c209e | 712 | (&TyAdt(did_a, substs_a), &TyAdt(did_b, substs_b)) => { |
e9174d1e SL |
713 | if did_a != did_b { |
714 | return false; | |
715 | } | |
716 | ||
9e0c209e | 717 | substs_a.types().zip(substs_b.types()).all(|(a, b)| same_type(a, b)) |
e9174d1e SL |
718 | } |
719 | _ => { | |
720 | a == b | |
721 | } | |
722 | } | |
723 | } | |
724 | ||
725 | // Does the type `ty` directly (without indirection through a pointer) | |
726 | // contain any types on stack `seen`? | |
a7813a04 XL |
727 | fn is_type_structurally_recursive<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
728 | sp: Span, | |
729 | seen: &mut Vec<Ty<'tcx>>, | |
730 | ty: Ty<'tcx>) -> Representability { | |
e9174d1e SL |
731 | debug!("is_type_structurally_recursive: {:?}", ty); |
732 | ||
733 | match ty.sty { | |
9e0c209e | 734 | TyAdt(def, _) => { |
e9174d1e SL |
735 | { |
736 | // Iterate through stack of previously seen types. | |
737 | let mut iter = seen.iter(); | |
738 | ||
739 | // The first item in `seen` is the type we are actually curious about. | |
740 | // We want to return SelfRecursive if this type contains itself. | |
741 | // It is important that we DON'T take generic parameters into account | |
742 | // for this check, so that Bar<T> in this example counts as SelfRecursive: | |
743 | // | |
744 | // struct Foo; | |
745 | // struct Bar<T> { x: Bar<Foo> } | |
746 | ||
3157f602 XL |
747 | if let Some(&seen_type) = iter.next() { |
748 | if same_struct_or_enum(seen_type, def) { | |
749 | debug!("SelfRecursive: {:?} contains {:?}", | |
750 | seen_type, | |
751 | ty); | |
752 | return Representability::SelfRecursive; | |
e9174d1e | 753 | } |
e9174d1e SL |
754 | } |
755 | ||
756 | // We also need to know whether the first item contains other types | |
757 | // that are structurally recursive. If we don't catch this case, we | |
758 | // will recurse infinitely for some inputs. | |
759 | // | |
760 | // It is important that we DO take generic parameters into account | |
761 | // here, so that code like this is considered SelfRecursive, not | |
762 | // ContainsRecursive: | |
763 | // | |
764 | // struct Foo { Option<Option<Foo>> } | |
765 | ||
766 | for &seen_type in iter { | |
767 | if same_type(ty, seen_type) { | |
768 | debug!("ContainsRecursive: {:?} contains {:?}", | |
769 | seen_type, | |
770 | ty); | |
771 | return Representability::ContainsRecursive; | |
772 | } | |
773 | } | |
774 | } | |
775 | ||
776 | // For structs and enums, track all previously seen types by pushing them | |
777 | // onto the 'seen' stack. | |
778 | seen.push(ty); | |
a7813a04 | 779 | let out = are_inner_types_recursive(tcx, sp, seen, ty); |
e9174d1e SL |
780 | seen.pop(); |
781 | out | |
782 | } | |
783 | _ => { | |
784 | // No need to push in other cases. | |
a7813a04 | 785 | are_inner_types_recursive(tcx, sp, seen, ty) |
e9174d1e SL |
786 | } |
787 | } | |
788 | } | |
789 | ||
790 | debug!("is_type_representable: {:?}", self); | |
791 | ||
792 | // To avoid a stack overflow when checking an enum variant or struct that | |
793 | // contains a different, structurally recursive type, maintain a stack | |
794 | // of seen types and check recursion for each of them (issues #3008, #3779). | |
795 | let mut seen: Vec<Ty> = Vec::new(); | |
a7813a04 | 796 | let r = is_type_structurally_recursive(tcx, sp, &mut seen, self); |
e9174d1e SL |
797 | debug!("is_type_representable: {:?} is {:?}", self, r); |
798 | r | |
799 | } | |
800 | } |