]>
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 | ||
13 | use back::svh::Svh; | |
14 | use middle::const_eval::{self, ConstVal, ErrKind}; | |
15 | use middle::const_eval::EvalHint::UncheckedExprHint; | |
16 | use middle::def_id::DefId; | |
b039eaaf | 17 | use middle::subst::{self, Subst, Substs}; |
e9174d1e SL |
18 | use middle::infer; |
19 | use middle::pat_util; | |
20 | use middle::traits; | |
21 | use middle::ty::{self, Ty, TypeAndMut, TypeFlags}; | |
22 | use middle::ty::{Disr, ParameterEnvironment}; | |
23 | use middle::ty::{HasTypeFlags, RegionEscape}; | |
24 | use middle::ty::TypeVariants::*; | |
25 | use util::num::ToPrimitive; | |
26 | ||
27 | use std::cmp; | |
28 | use std::hash::{Hash, SipHasher, Hasher}; | |
b039eaaf SL |
29 | use std::rc::Rc; |
30 | use syntax::ast::{self, Name}; | |
31 | use syntax::attr::{self, AttrMetaMethods, SignedInt, UnsignedInt}; | |
e9174d1e SL |
32 | use syntax::codemap::Span; |
33 | ||
34 | use rustc_front::hir; | |
e9174d1e SL |
35 | |
36 | pub trait IntTypeExt { | |
37 | fn to_ty<'tcx>(&self, cx: &ty::ctxt<'tcx>) -> Ty<'tcx>; | |
38 | fn i64_to_disr(&self, val: i64) -> Option<Disr>; | |
39 | fn u64_to_disr(&self, val: u64) -> Option<Disr>; | |
40 | fn disr_incr(&self, val: Disr) -> Option<Disr>; | |
41 | fn disr_string(&self, val: Disr) -> String; | |
42 | fn disr_wrap_incr(&self, val: Option<Disr>) -> Disr; | |
43 | } | |
44 | ||
45 | impl IntTypeExt for attr::IntType { | |
46 | fn to_ty<'tcx>(&self, cx: &ty::ctxt<'tcx>) -> Ty<'tcx> { | |
47 | match *self { | |
b039eaaf SL |
48 | SignedInt(ast::TyI8) => cx.types.i8, |
49 | SignedInt(ast::TyI16) => cx.types.i16, | |
50 | SignedInt(ast::TyI32) => cx.types.i32, | |
51 | SignedInt(ast::TyI64) => cx.types.i64, | |
52 | SignedInt(ast::TyIs) => cx.types.isize, | |
53 | UnsignedInt(ast::TyU8) => cx.types.u8, | |
54 | UnsignedInt(ast::TyU16) => cx.types.u16, | |
55 | UnsignedInt(ast::TyU32) => cx.types.u32, | |
56 | UnsignedInt(ast::TyU64) => cx.types.u64, | |
57 | UnsignedInt(ast::TyUs) => cx.types.usize, | |
e9174d1e SL |
58 | } |
59 | } | |
60 | ||
61 | fn i64_to_disr(&self, val: i64) -> Option<Disr> { | |
62 | match *self { | |
b039eaaf SL |
63 | SignedInt(ast::TyI8) => val.to_i8() .map(|v| v as Disr), |
64 | SignedInt(ast::TyI16) => val.to_i16() .map(|v| v as Disr), | |
65 | SignedInt(ast::TyI32) => val.to_i32() .map(|v| v as Disr), | |
66 | SignedInt(ast::TyI64) => val.to_i64() .map(|v| v as Disr), | |
67 | UnsignedInt(ast::TyU8) => val.to_u8() .map(|v| v as Disr), | |
68 | UnsignedInt(ast::TyU16) => val.to_u16() .map(|v| v as Disr), | |
69 | UnsignedInt(ast::TyU32) => val.to_u32() .map(|v| v as Disr), | |
70 | UnsignedInt(ast::TyU64) => val.to_u64() .map(|v| v as Disr), | |
71 | ||
72 | UnsignedInt(ast::TyUs) | | |
73 | SignedInt(ast::TyIs) => unreachable!(), | |
e9174d1e SL |
74 | } |
75 | } | |
76 | ||
77 | fn u64_to_disr(&self, val: u64) -> Option<Disr> { | |
78 | match *self { | |
b039eaaf SL |
79 | SignedInt(ast::TyI8) => val.to_i8() .map(|v| v as Disr), |
80 | SignedInt(ast::TyI16) => val.to_i16() .map(|v| v as Disr), | |
81 | SignedInt(ast::TyI32) => val.to_i32() .map(|v| v as Disr), | |
82 | SignedInt(ast::TyI64) => val.to_i64() .map(|v| v as Disr), | |
83 | UnsignedInt(ast::TyU8) => val.to_u8() .map(|v| v as Disr), | |
84 | UnsignedInt(ast::TyU16) => val.to_u16() .map(|v| v as Disr), | |
85 | UnsignedInt(ast::TyU32) => val.to_u32() .map(|v| v as Disr), | |
86 | UnsignedInt(ast::TyU64) => val.to_u64() .map(|v| v as Disr), | |
87 | ||
88 | UnsignedInt(ast::TyUs) | | |
89 | SignedInt(ast::TyIs) => unreachable!(), | |
e9174d1e SL |
90 | } |
91 | } | |
92 | ||
93 | fn disr_incr(&self, val: Disr) -> Option<Disr> { | |
94 | macro_rules! add1 { | |
95 | ($e:expr) => { $e.and_then(|v|v.checked_add(1)).map(|v| v as Disr) } | |
96 | } | |
97 | match *self { | |
98 | // SignedInt repr means we *want* to reinterpret the bits | |
99 | // treating the highest bit of Disr as a sign-bit, so | |
100 | // cast to i64 before range-checking. | |
b039eaaf SL |
101 | SignedInt(ast::TyI8) => add1!((val as i64).to_i8()), |
102 | SignedInt(ast::TyI16) => add1!((val as i64).to_i16()), | |
103 | SignedInt(ast::TyI32) => add1!((val as i64).to_i32()), | |
104 | SignedInt(ast::TyI64) => add1!(Some(val as i64)), | |
105 | ||
106 | UnsignedInt(ast::TyU8) => add1!(val.to_u8()), | |
107 | UnsignedInt(ast::TyU16) => add1!(val.to_u16()), | |
108 | UnsignedInt(ast::TyU32) => add1!(val.to_u32()), | |
109 | UnsignedInt(ast::TyU64) => add1!(Some(val)), | |
110 | ||
111 | UnsignedInt(ast::TyUs) | | |
112 | SignedInt(ast::TyIs) => unreachable!(), | |
e9174d1e SL |
113 | } |
114 | } | |
115 | ||
116 | // This returns a String because (1.) it is only used for | |
117 | // rendering an error message and (2.) a string can represent the | |
118 | // full range from `i64::MIN` through `u64::MAX`. | |
119 | fn disr_string(&self, val: Disr) -> String { | |
120 | match *self { | |
b039eaaf SL |
121 | SignedInt(ast::TyI8) => format!("{}", val as i8 ), |
122 | SignedInt(ast::TyI16) => format!("{}", val as i16), | |
123 | SignedInt(ast::TyI32) => format!("{}", val as i32), | |
124 | SignedInt(ast::TyI64) => format!("{}", val as i64), | |
125 | UnsignedInt(ast::TyU8) => format!("{}", val as u8 ), | |
126 | UnsignedInt(ast::TyU16) => format!("{}", val as u16), | |
127 | UnsignedInt(ast::TyU32) => format!("{}", val as u32), | |
128 | UnsignedInt(ast::TyU64) => format!("{}", val as u64), | |
129 | ||
130 | UnsignedInt(ast::TyUs) | | |
131 | SignedInt(ast::TyIs) => unreachable!(), | |
e9174d1e SL |
132 | } |
133 | } | |
134 | ||
135 | fn disr_wrap_incr(&self, val: Option<Disr>) -> Disr { | |
136 | macro_rules! add1 { | |
137 | ($e:expr) => { ($e).wrapping_add(1) as Disr } | |
138 | } | |
139 | let val = val.unwrap_or(ty::INITIAL_DISCRIMINANT_VALUE); | |
140 | match *self { | |
b039eaaf SL |
141 | SignedInt(ast::TyI8) => add1!(val as i8 ), |
142 | SignedInt(ast::TyI16) => add1!(val as i16), | |
143 | SignedInt(ast::TyI32) => add1!(val as i32), | |
144 | SignedInt(ast::TyI64) => add1!(val as i64), | |
145 | UnsignedInt(ast::TyU8) => add1!(val as u8 ), | |
146 | UnsignedInt(ast::TyU16) => add1!(val as u16), | |
147 | UnsignedInt(ast::TyU32) => add1!(val as u32), | |
148 | UnsignedInt(ast::TyU64) => add1!(val as u64), | |
149 | ||
150 | UnsignedInt(ast::TyUs) | | |
151 | SignedInt(ast::TyIs) => unreachable!(), | |
e9174d1e SL |
152 | } |
153 | } | |
154 | } | |
155 | ||
156 | ||
157 | #[derive(Copy, Clone)] | |
158 | pub enum CopyImplementationError { | |
159 | InfrigingField(Name), | |
160 | InfrigingVariant(Name), | |
161 | NotAnAdt, | |
162 | HasDestructor | |
163 | } | |
164 | ||
165 | /// Describes whether a type is representable. For types that are not | |
166 | /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to | |
167 | /// distinguish between types that are recursive with themselves and types that | |
168 | /// contain a different recursive type. These cases can therefore be treated | |
169 | /// differently when reporting errors. | |
170 | /// | |
171 | /// The ordering of the cases is significant. They are sorted so that cmp::max | |
172 | /// will keep the "more erroneous" of two values. | |
173 | #[derive(Copy, Clone, PartialOrd, Ord, Eq, PartialEq, Debug)] | |
174 | pub enum Representability { | |
175 | Representable, | |
176 | ContainsRecursive, | |
177 | SelfRecursive, | |
178 | } | |
179 | ||
180 | impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> { | |
181 | pub fn can_type_implement_copy(&self, self_type: Ty<'tcx>, span: Span) | |
182 | -> Result<(),CopyImplementationError> { | |
183 | let tcx = self.tcx; | |
184 | ||
185 | // FIXME: (@jroesch) float this code up | |
186 | let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(self.clone()), false); | |
187 | ||
188 | let adt = match self_type.sty { | |
189 | ty::TyStruct(struct_def, substs) => { | |
190 | for field in struct_def.all_fields() { | |
191 | let field_ty = field.ty(tcx, substs); | |
192 | if infcx.type_moves_by_default(field_ty, span) { | |
193 | return Err(CopyImplementationError::InfrigingField( | |
194 | field.name)) | |
195 | } | |
196 | } | |
197 | struct_def | |
198 | } | |
199 | ty::TyEnum(enum_def, substs) => { | |
200 | for variant in &enum_def.variants { | |
201 | for field in &variant.fields { | |
202 | let field_ty = field.ty(tcx, substs); | |
203 | if infcx.type_moves_by_default(field_ty, span) { | |
204 | return Err(CopyImplementationError::InfrigingVariant( | |
205 | variant.name)) | |
206 | } | |
207 | } | |
208 | } | |
209 | enum_def | |
210 | } | |
211 | _ => return Err(CopyImplementationError::NotAnAdt), | |
212 | }; | |
213 | ||
214 | if adt.has_dtor() { | |
215 | return Err(CopyImplementationError::HasDestructor) | |
216 | } | |
217 | ||
218 | Ok(()) | |
219 | } | |
220 | } | |
221 | ||
222 | impl<'tcx> ty::ctxt<'tcx> { | |
223 | pub fn pat_contains_ref_binding(&self, pat: &hir::Pat) -> Option<hir::Mutability> { | |
224 | pat_util::pat_contains_ref_binding(&self.def_map, pat) | |
225 | } | |
226 | ||
227 | pub fn arm_contains_ref_binding(&self, arm: &hir::Arm) -> Option<hir::Mutability> { | |
228 | pat_util::arm_contains_ref_binding(&self.def_map, arm) | |
229 | } | |
230 | ||
231 | /// Returns the type of element at index `i` in tuple or tuple-like type `t`. | |
232 | /// For an enum `t`, `variant` is None only if `t` is a univariant enum. | |
233 | pub fn positional_element_ty(&self, | |
234 | ty: Ty<'tcx>, | |
235 | i: usize, | |
236 | variant: Option<DefId>) -> Option<Ty<'tcx>> { | |
237 | match (&ty.sty, variant) { | |
238 | (&TyStruct(def, substs), None) => { | |
239 | def.struct_variant().fields.get(i).map(|f| f.ty(self, substs)) | |
240 | } | |
241 | (&TyEnum(def, substs), Some(vid)) => { | |
242 | def.variant_with_id(vid).fields.get(i).map(|f| f.ty(self, substs)) | |
243 | } | |
244 | (&TyEnum(def, substs), None) => { | |
245 | assert!(def.is_univariant()); | |
246 | def.variants[0].fields.get(i).map(|f| f.ty(self, substs)) | |
247 | } | |
248 | (&TyTuple(ref v), None) => v.get(i).cloned(), | |
249 | _ => None | |
250 | } | |
251 | } | |
252 | ||
253 | /// Returns the type of element at field `n` in struct or struct-like type `t`. | |
254 | /// For an enum `t`, `variant` must be some def id. | |
255 | pub fn named_element_ty(&self, | |
256 | ty: Ty<'tcx>, | |
257 | n: Name, | |
258 | variant: Option<DefId>) -> Option<Ty<'tcx>> { | |
259 | match (&ty.sty, variant) { | |
260 | (&TyStruct(def, substs), None) => { | |
261 | def.struct_variant().find_field_named(n).map(|f| f.ty(self, substs)) | |
262 | } | |
263 | (&TyEnum(def, substs), Some(vid)) => { | |
264 | def.variant_with_id(vid).find_field_named(n).map(|f| f.ty(self, substs)) | |
265 | } | |
266 | _ => return None | |
267 | } | |
268 | } | |
269 | ||
270 | /// Returns `(normalized_type, ty)`, where `normalized_type` is the | |
271 | /// IntType representation of one of {i64,i32,i16,i8,u64,u32,u16,u8}, | |
272 | /// and `ty` is the original type (i.e. may include `isize` or | |
273 | /// `usize`). | |
274 | pub fn enum_repr_type(&self, opt_hint: Option<&attr::ReprAttr>) | |
275 | -> (attr::IntType, Ty<'tcx>) { | |
276 | let repr_type = match opt_hint { | |
277 | // Feed in the given type | |
278 | Some(&attr::ReprInt(_, int_t)) => int_t, | |
279 | // ... but provide sensible default if none provided | |
280 | // | |
281 | // NB. Historically `fn enum_variants` generate i64 here, while | |
282 | // rustc_typeck::check would generate isize. | |
b039eaaf | 283 | _ => SignedInt(ast::TyIs), |
e9174d1e SL |
284 | }; |
285 | ||
286 | let repr_type_ty = repr_type.to_ty(self); | |
287 | let repr_type = match repr_type { | |
b039eaaf | 288 | SignedInt(ast::TyIs) => |
e9174d1e | 289 | SignedInt(self.sess.target.int_type), |
b039eaaf | 290 | UnsignedInt(ast::TyUs) => |
e9174d1e SL |
291 | UnsignedInt(self.sess.target.uint_type), |
292 | other => other | |
293 | }; | |
294 | ||
295 | (repr_type, repr_type_ty) | |
296 | } | |
297 | ||
298 | /// Returns the deeply last field of nested structures, or the same type, | |
299 | /// if not a structure at all. Corresponds to the only possible unsized | |
300 | /// field, and its type can be used to determine unsizing strategy. | |
301 | pub fn struct_tail(&self, mut ty: Ty<'tcx>) -> Ty<'tcx> { | |
302 | while let TyStruct(def, substs) = ty.sty { | |
303 | match def.struct_variant().fields.last() { | |
304 | Some(f) => ty = f.ty(self, substs), | |
305 | None => break | |
306 | } | |
307 | } | |
308 | ty | |
309 | } | |
310 | ||
311 | /// Same as applying struct_tail on `source` and `target`, but only | |
312 | /// keeps going as long as the two types are instances of the same | |
313 | /// structure definitions. | |
314 | /// For `(Foo<Foo<T>>, Foo<Trait>)`, the result will be `(Foo<T>, Trait)`, | |
315 | /// whereas struct_tail produces `T`, and `Trait`, respectively. | |
316 | pub fn struct_lockstep_tails(&self, | |
317 | source: Ty<'tcx>, | |
318 | target: Ty<'tcx>) | |
319 | -> (Ty<'tcx>, Ty<'tcx>) { | |
320 | let (mut a, mut b) = (source, target); | |
321 | while let (&TyStruct(a_def, a_substs), &TyStruct(b_def, b_substs)) = (&a.sty, &b.sty) { | |
322 | if a_def != b_def { | |
323 | break; | |
324 | } | |
325 | if let Some(f) = a_def.struct_variant().fields.last() { | |
326 | a = f.ty(self, a_substs); | |
327 | b = f.ty(self, b_substs); | |
328 | } else { | |
329 | break; | |
330 | } | |
331 | } | |
332 | (a, b) | |
333 | } | |
334 | ||
335 | /// Returns the repeat count for a repeating vector expression. | |
336 | pub fn eval_repeat_count(&self, count_expr: &hir::Expr) -> usize { | |
337 | let hint = UncheckedExprHint(self.types.usize); | |
b039eaaf | 338 | match const_eval::eval_const_expr_partial(self, count_expr, hint, None) { |
e9174d1e SL |
339 | Ok(val) => { |
340 | let found = match val { | |
341 | ConstVal::Uint(count) => return count as usize, | |
342 | ConstVal::Int(count) if count >= 0 => return count as usize, | |
343 | const_val => const_val.description(), | |
344 | }; | |
345 | span_err!(self.sess, count_expr.span, E0306, | |
346 | "expected positive integer for repeat count, found {}", | |
347 | found); | |
348 | } | |
349 | Err(err) => { | |
350 | let err_msg = match count_expr.node { | |
351 | hir::ExprPath(None, hir::Path { | |
352 | global: false, | |
353 | ref segments, | |
354 | .. | |
355 | }) if segments.len() == 1 => | |
356 | format!("found variable"), | |
357 | _ => match err.kind { | |
358 | ErrKind::MiscCatchAll => format!("but found {}", err.description()), | |
359 | _ => format!("but {}", err.description()) | |
360 | } | |
361 | }; | |
362 | span_err!(self.sess, count_expr.span, E0307, | |
363 | "expected constant integer for repeat count, {}", err_msg); | |
364 | } | |
365 | } | |
366 | 0 | |
367 | } | |
368 | ||
369 | /// Given a set of predicates that apply to an object type, returns | |
370 | /// the region bounds that the (erased) `Self` type must | |
371 | /// outlive. Precisely *because* the `Self` type is erased, the | |
372 | /// parameter `erased_self_ty` must be supplied to indicate what type | |
373 | /// has been used to represent `Self` in the predicates | |
374 | /// themselves. This should really be a unique type; `FreshTy(0)` is a | |
375 | /// popular choice. | |
376 | /// | |
377 | /// NB: in some cases, particularly around higher-ranked bounds, | |
378 | /// this function returns a kind of conservative approximation. | |
379 | /// That is, all regions returned by this function are definitely | |
380 | /// required, but there may be other region bounds that are not | |
381 | /// returned, as well as requirements like `for<'a> T: 'a`. | |
382 | /// | |
383 | /// Requires that trait definitions have been processed so that we can | |
384 | /// elaborate predicates and walk supertraits. | |
385 | pub fn required_region_bounds(&self, | |
386 | erased_self_ty: Ty<'tcx>, | |
387 | predicates: Vec<ty::Predicate<'tcx>>) | |
388 | -> Vec<ty::Region> { | |
389 | debug!("required_region_bounds(erased_self_ty={:?}, predicates={:?})", | |
390 | erased_self_ty, | |
391 | predicates); | |
392 | ||
393 | assert!(!erased_self_ty.has_escaping_regions()); | |
394 | ||
395 | traits::elaborate_predicates(self, predicates) | |
396 | .filter_map(|predicate| { | |
397 | match predicate { | |
398 | ty::Predicate::Projection(..) | | |
399 | ty::Predicate::Trait(..) | | |
400 | ty::Predicate::Equate(..) | | |
401 | ty::Predicate::WellFormed(..) | | |
402 | ty::Predicate::ObjectSafe(..) | | |
403 | ty::Predicate::RegionOutlives(..) => { | |
404 | None | |
405 | } | |
406 | ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(t, r))) => { | |
407 | // Search for a bound of the form `erased_self_ty | |
408 | // : 'a`, but be wary of something like `for<'a> | |
409 | // erased_self_ty : 'a` (we interpret a | |
410 | // higher-ranked bound like that as 'static, | |
411 | // though at present the code in `fulfill.rs` | |
412 | // considers such bounds to be unsatisfiable, so | |
413 | // it's kind of a moot point since you could never | |
414 | // construct such an object, but this seems | |
415 | // correct even if that code changes). | |
416 | if t == erased_self_ty && !r.has_escaping_regions() { | |
417 | Some(r) | |
418 | } else { | |
419 | None | |
420 | } | |
421 | } | |
422 | } | |
423 | }) | |
424 | .collect() | |
425 | } | |
426 | ||
427 | /// Creates a hash of the type `Ty` which will be the same no matter what crate | |
428 | /// context it's calculated within. This is used by the `type_id` intrinsic. | |
429 | pub fn hash_crate_independent(&self, ty: Ty<'tcx>, svh: &Svh) -> u64 { | |
430 | let mut state = SipHasher::new(); | |
431 | helper(self, ty, svh, &mut state); | |
432 | return state.finish(); | |
433 | ||
434 | fn helper<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh, | |
435 | state: &mut SipHasher) { | |
436 | macro_rules! byte { ($b:expr) => { ($b as u8).hash(state) } } | |
437 | macro_rules! hash { ($e:expr) => { $e.hash(state) } } | |
438 | ||
439 | let region = |state: &mut SipHasher, r: ty::Region| { | |
440 | match r { | |
441 | ty::ReStatic => {} | |
442 | ty::ReLateBound(db, ty::BrAnon(i)) => { | |
443 | db.hash(state); | |
444 | i.hash(state); | |
445 | } | |
446 | ty::ReEmpty | | |
447 | ty::ReEarlyBound(..) | | |
448 | ty::ReLateBound(..) | | |
449 | ty::ReFree(..) | | |
450 | ty::ReScope(..) | | |
451 | ty::ReVar(..) | | |
452 | ty::ReSkolemized(..) => { | |
453 | tcx.sess.bug("unexpected region found when hashing a type") | |
454 | } | |
455 | } | |
456 | }; | |
457 | let did = |state: &mut SipHasher, did: DefId| { | |
458 | let h = if did.is_local() { | |
459 | svh.clone() | |
460 | } else { | |
92a42be0 | 461 | tcx.sess.cstore.crate_hash(did.krate) |
e9174d1e SL |
462 | }; |
463 | h.as_str().hash(state); | |
b039eaaf | 464 | did.index.hash(state); |
e9174d1e SL |
465 | }; |
466 | let mt = |state: &mut SipHasher, mt: TypeAndMut| { | |
467 | mt.mutbl.hash(state); | |
468 | }; | |
469 | let fn_sig = |state: &mut SipHasher, sig: &ty::Binder<ty::FnSig<'tcx>>| { | |
470 | let sig = tcx.anonymize_late_bound_regions(sig).0; | |
471 | for a in &sig.inputs { helper(tcx, *a, svh, state); } | |
472 | if let ty::FnConverging(output) = sig.output { | |
473 | helper(tcx, output, svh, state); | |
474 | } | |
475 | }; | |
476 | ty.maybe_walk(|ty| { | |
477 | match ty.sty { | |
478 | TyBool => byte!(2), | |
479 | TyChar => byte!(3), | |
480 | TyInt(i) => { | |
481 | byte!(4); | |
482 | hash!(i); | |
483 | } | |
484 | TyUint(u) => { | |
485 | byte!(5); | |
486 | hash!(u); | |
487 | } | |
488 | TyFloat(f) => { | |
489 | byte!(6); | |
490 | hash!(f); | |
491 | } | |
492 | TyStr => { | |
493 | byte!(7); | |
494 | } | |
495 | TyEnum(d, _) => { | |
496 | byte!(8); | |
497 | did(state, d.did); | |
498 | } | |
499 | TyBox(_) => { | |
500 | byte!(9); | |
501 | } | |
502 | TyArray(_, n) => { | |
503 | byte!(10); | |
504 | n.hash(state); | |
505 | } | |
506 | TySlice(_) => { | |
507 | byte!(11); | |
508 | } | |
509 | TyRawPtr(m) => { | |
510 | byte!(12); | |
511 | mt(state, m); | |
512 | } | |
513 | TyRef(r, m) => { | |
514 | byte!(13); | |
515 | region(state, *r); | |
516 | mt(state, m); | |
517 | } | |
518 | TyBareFn(opt_def_id, ref b) => { | |
519 | byte!(14); | |
520 | hash!(opt_def_id); | |
521 | hash!(b.unsafety); | |
522 | hash!(b.abi); | |
523 | fn_sig(state, &b.sig); | |
524 | return false; | |
525 | } | |
526 | TyTrait(ref data) => { | |
527 | byte!(17); | |
528 | did(state, data.principal_def_id()); | |
529 | hash!(data.bounds); | |
530 | ||
531 | let principal = tcx.anonymize_late_bound_regions(&data.principal).0; | |
532 | for subty in &principal.substs.types { | |
533 | helper(tcx, subty, svh, state); | |
534 | } | |
535 | ||
536 | return false; | |
537 | } | |
538 | TyStruct(d, _) => { | |
539 | byte!(18); | |
540 | did(state, d.did); | |
541 | } | |
542 | TyTuple(ref inner) => { | |
543 | byte!(19); | |
544 | hash!(inner.len()); | |
545 | } | |
546 | TyParam(p) => { | |
547 | byte!(20); | |
548 | hash!(p.space); | |
549 | hash!(p.idx); | |
550 | hash!(p.name.as_str()); | |
551 | } | |
552 | TyInfer(_) => unreachable!(), | |
553 | TyError => byte!(21), | |
554 | TyClosure(d, _) => { | |
555 | byte!(22); | |
556 | did(state, d); | |
557 | } | |
558 | TyProjection(ref data) => { | |
559 | byte!(23); | |
560 | did(state, data.trait_ref.def_id); | |
561 | hash!(data.item_name.as_str()); | |
562 | } | |
563 | } | |
564 | true | |
565 | }); | |
566 | } | |
567 | } | |
568 | ||
b039eaaf SL |
569 | /// Returns true if this ADT is a dtorck type. |
570 | /// | |
571 | /// Invoking the destructor of a dtorck type during usual cleanup | |
572 | /// (e.g. the glue emitted for stack unwinding) requires all | |
573 | /// lifetimes in the type-structure of `adt` to strictly outlive | |
574 | /// the adt value itself. | |
575 | /// | |
576 | /// If `adt` is not dtorck, then the adt's destructor can be | |
577 | /// invoked even when there are lifetimes in the type-structure of | |
578 | /// `adt` that do not strictly outlive the adt value itself. | |
579 | /// (This allows programs to make cyclic structures without | |
580 | /// resorting to unasfe means; see RFCs 769 and 1238). | |
e9174d1e SL |
581 | pub fn is_adt_dtorck(&self, adt: ty::AdtDef<'tcx>) -> bool { |
582 | let dtor_method = match adt.destructor() { | |
583 | Some(dtor) => dtor, | |
584 | None => return false | |
585 | }; | |
b039eaaf SL |
586 | |
587 | // RFC 1238: if the destructor method is tagged with the | |
588 | // attribute `unsafe_destructor_blind_to_params`, then the | |
589 | // compiler is being instructed to *assume* that the | |
590 | // destructor will not access borrowed data, | |
591 | // even if such data is otherwise reachable. | |
e9174d1e | 592 | // |
b039eaaf SL |
593 | // Such access can be in plain sight (e.g. dereferencing |
594 | // `*foo.0` of `Foo<'a>(&'a u32)`) or indirectly hidden | |
595 | // (e.g. calling `foo.0.clone()` of `Foo<T:Clone>`). | |
596 | return !self.has_attr(dtor_method, "unsafe_destructor_blind_to_params"); | |
597 | } | |
598 | } | |
e9174d1e | 599 | |
b039eaaf SL |
600 | #[derive(Debug)] |
601 | pub struct ImplMethod<'tcx> { | |
602 | pub method: Rc<ty::Method<'tcx>>, | |
603 | pub substs: Substs<'tcx>, | |
604 | pub is_provided: bool | |
605 | } | |
e9174d1e | 606 | |
b039eaaf SL |
607 | impl<'tcx> ty::ctxt<'tcx> { |
608 | #[inline(never)] // is this perfy enough? | |
609 | pub fn get_impl_method(&self, | |
610 | impl_def_id: DefId, | |
611 | substs: Substs<'tcx>, | |
612 | name: Name) | |
613 | -> ImplMethod<'tcx> | |
614 | { | |
615 | // there don't seem to be nicer accessors to these: | |
616 | let impl_or_trait_items_map = self.impl_or_trait_items.borrow(); | |
617 | ||
618 | for impl_item in &self.impl_items.borrow()[&impl_def_id] { | |
619 | if let ty::MethodTraitItem(ref meth) = | |
620 | impl_or_trait_items_map[&impl_item.def_id()] { | |
621 | if meth.name == name { | |
622 | return ImplMethod { | |
623 | method: meth.clone(), | |
624 | substs: substs, | |
625 | is_provided: false | |
e9174d1e | 626 | } |
b039eaaf SL |
627 | } |
628 | } | |
629 | } | |
e9174d1e | 630 | |
b039eaaf SL |
631 | // It is not in the impl - get the default from the trait. |
632 | let trait_ref = self.impl_trait_ref(impl_def_id).unwrap(); | |
633 | for trait_item in self.trait_items(trait_ref.def_id).iter() { | |
634 | if let &ty::MethodTraitItem(ref meth) = trait_item { | |
635 | if meth.name == name { | |
636 | let impl_to_trait_substs = self | |
637 | .make_substs_for_receiver_types(&trait_ref, meth); | |
638 | return ImplMethod { | |
639 | method: meth.clone(), | |
640 | substs: impl_to_trait_substs.subst(self, &substs), | |
641 | is_provided: true | |
e9174d1e | 642 | } |
e9174d1e SL |
643 | } |
644 | } | |
e9174d1e SL |
645 | } |
646 | ||
b039eaaf SL |
647 | self.sess.bug(&format!("method {:?} not found in {:?}", |
648 | name, impl_def_id)) | |
e9174d1e SL |
649 | } |
650 | } | |
651 | ||
652 | impl<'tcx> ty::TyS<'tcx> { | |
653 | fn impls_bound<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>, | |
654 | bound: ty::BuiltinBound, | |
655 | span: Span) | |
656 | -> bool | |
657 | { | |
658 | let tcx = param_env.tcx; | |
659 | let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env.clone()), false); | |
660 | ||
661 | let is_impld = traits::type_known_to_meet_builtin_bound(&infcx, | |
662 | self, bound, span); | |
663 | ||
664 | debug!("Ty::impls_bound({:?}, {:?}) = {:?}", | |
665 | self, bound, is_impld); | |
666 | ||
667 | is_impld | |
668 | } | |
669 | ||
670 | // FIXME (@jroesch): I made this public to use it, not sure if should be private | |
671 | pub fn moves_by_default<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>, | |
672 | span: Span) -> bool { | |
673 | if self.flags.get().intersects(TypeFlags::MOVENESS_CACHED) { | |
674 | return self.flags.get().intersects(TypeFlags::MOVES_BY_DEFAULT); | |
675 | } | |
676 | ||
677 | assert!(!self.needs_infer()); | |
678 | ||
679 | // Fast-path for primitive types | |
680 | let result = match self.sty { | |
681 | TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) | | |
682 | TyRawPtr(..) | TyBareFn(..) | TyRef(_, TypeAndMut { | |
683 | mutbl: hir::MutImmutable, .. | |
684 | }) => Some(false), | |
685 | ||
686 | TyStr | TyBox(..) | TyRef(_, TypeAndMut { | |
687 | mutbl: hir::MutMutable, .. | |
688 | }) => Some(true), | |
689 | ||
690 | TyArray(..) | TySlice(_) | TyTrait(..) | TyTuple(..) | | |
691 | TyClosure(..) | TyEnum(..) | TyStruct(..) | | |
692 | TyProjection(..) | TyParam(..) | TyInfer(..) | TyError => None | |
693 | }.unwrap_or_else(|| !self.impls_bound(param_env, ty::BoundCopy, span)); | |
694 | ||
695 | if !self.has_param_types() && !self.has_self_ty() { | |
696 | self.flags.set(self.flags.get() | if result { | |
697 | TypeFlags::MOVENESS_CACHED | TypeFlags::MOVES_BY_DEFAULT | |
698 | } else { | |
699 | TypeFlags::MOVENESS_CACHED | |
700 | }); | |
701 | } | |
702 | ||
703 | result | |
704 | } | |
705 | ||
706 | #[inline] | |
707 | pub fn is_sized<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>, | |
708 | span: Span) -> bool | |
709 | { | |
710 | if self.flags.get().intersects(TypeFlags::SIZEDNESS_CACHED) { | |
711 | return self.flags.get().intersects(TypeFlags::IS_SIZED); | |
712 | } | |
713 | ||
714 | self.is_sized_uncached(param_env, span) | |
715 | } | |
716 | ||
717 | fn is_sized_uncached<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>, | |
718 | span: Span) -> bool { | |
719 | assert!(!self.needs_infer()); | |
720 | ||
721 | // Fast-path for primitive types | |
722 | let result = match self.sty { | |
723 | TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) | | |
724 | TyBox(..) | TyRawPtr(..) | TyRef(..) | TyBareFn(..) | | |
725 | TyArray(..) | TyTuple(..) | TyClosure(..) => Some(true), | |
726 | ||
727 | TyStr | TyTrait(..) | TySlice(_) => Some(false), | |
728 | ||
729 | TyEnum(..) | TyStruct(..) | TyProjection(..) | TyParam(..) | | |
730 | TyInfer(..) | TyError => None | |
731 | }.unwrap_or_else(|| self.impls_bound(param_env, ty::BoundSized, span)); | |
732 | ||
733 | if !self.has_param_types() && !self.has_self_ty() { | |
734 | self.flags.set(self.flags.get() | if result { | |
735 | TypeFlags::SIZEDNESS_CACHED | TypeFlags::IS_SIZED | |
736 | } else { | |
737 | TypeFlags::SIZEDNESS_CACHED | |
738 | }); | |
739 | } | |
740 | ||
741 | result | |
742 | } | |
743 | ||
744 | ||
745 | /// Check whether a type is representable. This means it cannot contain unboxed | |
746 | /// structural recursion. This check is needed for structs and enums. | |
747 | pub fn is_representable(&'tcx self, cx: &ty::ctxt<'tcx>, sp: Span) -> Representability { | |
748 | ||
749 | // Iterate until something non-representable is found | |
750 | fn find_nonrepresentable<'tcx, It: Iterator<Item=Ty<'tcx>>>(cx: &ty::ctxt<'tcx>, | |
751 | sp: Span, | |
752 | seen: &mut Vec<Ty<'tcx>>, | |
753 | iter: It) | |
754 | -> Representability { | |
755 | iter.fold(Representability::Representable, | |
756 | |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty))) | |
757 | } | |
758 | ||
759 | fn are_inner_types_recursive<'tcx>(cx: &ty::ctxt<'tcx>, sp: Span, | |
760 | seen: &mut Vec<Ty<'tcx>>, ty: Ty<'tcx>) | |
761 | -> Representability { | |
762 | match ty.sty { | |
763 | TyTuple(ref ts) => { | |
764 | find_nonrepresentable(cx, sp, seen, ts.iter().cloned()) | |
765 | } | |
766 | // Fixed-length vectors. | |
767 | // FIXME(#11924) Behavior undecided for zero-length vectors. | |
768 | TyArray(ty, _) => { | |
769 | is_type_structurally_recursive(cx, sp, seen, ty) | |
770 | } | |
771 | TyStruct(def, substs) | TyEnum(def, substs) => { | |
772 | find_nonrepresentable(cx, | |
773 | sp, | |
774 | seen, | |
775 | def.all_fields().map(|f| f.ty(cx, substs))) | |
776 | } | |
777 | TyClosure(..) => { | |
778 | // this check is run on type definitions, so we don't expect | |
779 | // to see closure types | |
780 | cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty)) | |
781 | } | |
782 | _ => Representability::Representable, | |
783 | } | |
784 | } | |
785 | ||
786 | fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool { | |
787 | match ty.sty { | |
788 | TyStruct(ty_def, _) | TyEnum(ty_def, _) => { | |
789 | ty_def == def | |
790 | } | |
791 | _ => false | |
792 | } | |
793 | } | |
794 | ||
795 | fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool { | |
796 | match (&a.sty, &b.sty) { | |
797 | (&TyStruct(did_a, ref substs_a), &TyStruct(did_b, ref substs_b)) | | |
798 | (&TyEnum(did_a, ref substs_a), &TyEnum(did_b, ref substs_b)) => { | |
799 | if did_a != did_b { | |
800 | return false; | |
801 | } | |
802 | ||
803 | let types_a = substs_a.types.get_slice(subst::TypeSpace); | |
804 | let types_b = substs_b.types.get_slice(subst::TypeSpace); | |
805 | ||
806 | let mut pairs = types_a.iter().zip(types_b); | |
807 | ||
808 | pairs.all(|(&a, &b)| same_type(a, b)) | |
809 | } | |
810 | _ => { | |
811 | a == b | |
812 | } | |
813 | } | |
814 | } | |
815 | ||
816 | // Does the type `ty` directly (without indirection through a pointer) | |
817 | // contain any types on stack `seen`? | |
818 | fn is_type_structurally_recursive<'tcx>(cx: &ty::ctxt<'tcx>, | |
819 | sp: Span, | |
820 | seen: &mut Vec<Ty<'tcx>>, | |
821 | ty: Ty<'tcx>) -> Representability { | |
822 | debug!("is_type_structurally_recursive: {:?}", ty); | |
823 | ||
824 | match ty.sty { | |
825 | TyStruct(def, _) | TyEnum(def, _) => { | |
826 | { | |
827 | // Iterate through stack of previously seen types. | |
828 | let mut iter = seen.iter(); | |
829 | ||
830 | // The first item in `seen` is the type we are actually curious about. | |
831 | // We want to return SelfRecursive if this type contains itself. | |
832 | // It is important that we DON'T take generic parameters into account | |
833 | // for this check, so that Bar<T> in this example counts as SelfRecursive: | |
834 | // | |
835 | // struct Foo; | |
836 | // struct Bar<T> { x: Bar<Foo> } | |
837 | ||
838 | match iter.next() { | |
839 | Some(&seen_type) => { | |
840 | if same_struct_or_enum(seen_type, def) { | |
841 | debug!("SelfRecursive: {:?} contains {:?}", | |
842 | seen_type, | |
843 | ty); | |
844 | return Representability::SelfRecursive; | |
845 | } | |
846 | } | |
847 | None => {} | |
848 | } | |
849 | ||
850 | // We also need to know whether the first item contains other types | |
851 | // that are structurally recursive. If we don't catch this case, we | |
852 | // will recurse infinitely for some inputs. | |
853 | // | |
854 | // It is important that we DO take generic parameters into account | |
855 | // here, so that code like this is considered SelfRecursive, not | |
856 | // ContainsRecursive: | |
857 | // | |
858 | // struct Foo { Option<Option<Foo>> } | |
859 | ||
860 | for &seen_type in iter { | |
861 | if same_type(ty, seen_type) { | |
862 | debug!("ContainsRecursive: {:?} contains {:?}", | |
863 | seen_type, | |
864 | ty); | |
865 | return Representability::ContainsRecursive; | |
866 | } | |
867 | } | |
868 | } | |
869 | ||
870 | // For structs and enums, track all previously seen types by pushing them | |
871 | // onto the 'seen' stack. | |
872 | seen.push(ty); | |
873 | let out = are_inner_types_recursive(cx, sp, seen, ty); | |
874 | seen.pop(); | |
875 | out | |
876 | } | |
877 | _ => { | |
878 | // No need to push in other cases. | |
879 | are_inner_types_recursive(cx, sp, seen, ty) | |
880 | } | |
881 | } | |
882 | } | |
883 | ||
884 | debug!("is_type_representable: {:?}", self); | |
885 | ||
886 | // To avoid a stack overflow when checking an enum variant or struct that | |
887 | // contains a different, structurally recursive type, maintain a stack | |
888 | // of seen types and check recursion for each of them (issues #3008, #3779). | |
889 | let mut seen: Vec<Ty> = Vec::new(); | |
890 | let r = is_type_structurally_recursive(cx, sp, &mut seen, self); | |
891 | debug!("is_type_representable: {:?} is {:?}", self, r); | |
892 | r | |
893 | } | |
894 | } |