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