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