]>
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 | ||
abe05a73 | 13 | use hir::def::Def; |
ff7c6d11 | 14 | use hir::def_id::DefId; |
abe05a73 XL |
15 | use hir::map::{DefPathData, Node}; |
16 | use hir; | |
ea8adc8c XL |
17 | use ich::NodeIdHashingMode; |
18 | use middle::const_val::ConstVal; | |
5bcae85e | 19 | use traits::{self, Reveal}; |
7cac9316 | 20 | use ty::{self, Ty, TyCtxt, TypeFoldable}; |
5bcae85e | 21 | use ty::fold::TypeVisitor; |
cc61c64b | 22 | use ty::subst::{Subst, Kind}; |
54a0048b | 23 | use ty::TypeVariants::*; |
8bb4bdeb | 24 | use util::common::ErrorReported; |
476ff2be | 25 | use middle::lang_items; |
54a0048b SL |
26 | |
27 | use rustc_const_math::{ConstInt, ConstIsize, ConstUsize}; | |
cc61c64b XL |
28 | use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult, |
29 | HashStable}; | |
041b39d2 | 30 | use rustc_data_structures::fx::FxHashMap; |
e9174d1e | 31 | use std::cmp; |
ea8adc8c | 32 | use std::iter; |
476ff2be | 33 | use std::hash::Hash; |
5bcae85e | 34 | use std::intrinsics; |
b039eaaf | 35 | use syntax::ast::{self, Name}; |
a7813a04 | 36 | use syntax::attr::{self, SignedInt, UnsignedInt}; |
8bb4bdeb | 37 | use syntax_pos::{Span, DUMMY_SP}; |
e9174d1e | 38 | |
8bb4bdeb XL |
39 | type Disr = ConstInt; |
40 | ||
cc61c64b | 41 | pub trait IntTypeExt { |
8bb4bdeb | 42 | fn to_ty<'a, 'gcx, 'tcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx>; |
a7813a04 XL |
43 | fn disr_incr<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, val: Option<Disr>) |
44 | -> Option<Disr>; | |
54a0048b | 45 | fn assert_ty_matches(&self, val: Disr); |
a7813a04 | 46 | fn initial_discriminant<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Disr; |
cc61c64b | 47 | } |
8bb4bdeb XL |
48 | |
49 | ||
50 | macro_rules! typed_literal { | |
51 | ($tcx:expr, $ty:expr, $lit:expr) => { | |
52 | match $ty { | |
53 | SignedInt(ast::IntTy::I8) => ConstInt::I8($lit), | |
54 | SignedInt(ast::IntTy::I16) => ConstInt::I16($lit), | |
55 | SignedInt(ast::IntTy::I32) => ConstInt::I32($lit), | |
56 | SignedInt(ast::IntTy::I64) => ConstInt::I64($lit), | |
57 | SignedInt(ast::IntTy::I128) => ConstInt::I128($lit), | |
ea8adc8c | 58 | SignedInt(ast::IntTy::Is) => match $tcx.sess.target.isize_ty { |
8bb4bdeb XL |
59 | ast::IntTy::I16 => ConstInt::Isize(ConstIsize::Is16($lit)), |
60 | ast::IntTy::I32 => ConstInt::Isize(ConstIsize::Is32($lit)), | |
61 | ast::IntTy::I64 => ConstInt::Isize(ConstIsize::Is64($lit)), | |
62 | _ => bug!(), | |
63 | }, | |
64 | UnsignedInt(ast::UintTy::U8) => ConstInt::U8($lit), | |
65 | UnsignedInt(ast::UintTy::U16) => ConstInt::U16($lit), | |
66 | UnsignedInt(ast::UintTy::U32) => ConstInt::U32($lit), | |
67 | UnsignedInt(ast::UintTy::U64) => ConstInt::U64($lit), | |
68 | UnsignedInt(ast::UintTy::U128) => ConstInt::U128($lit), | |
ea8adc8c | 69 | UnsignedInt(ast::UintTy::Us) => match $tcx.sess.target.usize_ty { |
8bb4bdeb XL |
70 | ast::UintTy::U16 => ConstInt::Usize(ConstUsize::Us16($lit)), |
71 | ast::UintTy::U32 => ConstInt::Usize(ConstUsize::Us32($lit)), | |
72 | ast::UintTy::U64 => ConstInt::Usize(ConstUsize::Us64($lit)), | |
73 | _ => bug!(), | |
74 | }, | |
75 | } | |
76 | } | |
e9174d1e SL |
77 | } |
78 | ||
79 | impl IntTypeExt for attr::IntType { | |
8bb4bdeb | 80 | fn to_ty<'a, 'gcx, 'tcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx> { |
e9174d1e | 81 | match *self { |
a7813a04 XL |
82 | SignedInt(ast::IntTy::I8) => tcx.types.i8, |
83 | SignedInt(ast::IntTy::I16) => tcx.types.i16, | |
84 | SignedInt(ast::IntTy::I32) => tcx.types.i32, | |
85 | SignedInt(ast::IntTy::I64) => tcx.types.i64, | |
32a655c1 | 86 | SignedInt(ast::IntTy::I128) => tcx.types.i128, |
a7813a04 XL |
87 | SignedInt(ast::IntTy::Is) => tcx.types.isize, |
88 | UnsignedInt(ast::UintTy::U8) => tcx.types.u8, | |
89 | UnsignedInt(ast::UintTy::U16) => tcx.types.u16, | |
90 | UnsignedInt(ast::UintTy::U32) => tcx.types.u32, | |
91 | UnsignedInt(ast::UintTy::U64) => tcx.types.u64, | |
32a655c1 | 92 | UnsignedInt(ast::UintTy::U128) => tcx.types.u128, |
a7813a04 | 93 | UnsignedInt(ast::UintTy::Us) => tcx.types.usize, |
e9174d1e SL |
94 | } |
95 | } | |
96 | ||
a7813a04 | 97 | fn initial_discriminant<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Disr { |
8bb4bdeb | 98 | typed_literal!(tcx, *self, 0) |
e9174d1e SL |
99 | } |
100 | ||
54a0048b SL |
101 | fn assert_ty_matches(&self, val: Disr) { |
102 | match (*self, val) { | |
103 | (SignedInt(ast::IntTy::I8), ConstInt::I8(_)) => {}, | |
104 | (SignedInt(ast::IntTy::I16), ConstInt::I16(_)) => {}, | |
105 | (SignedInt(ast::IntTy::I32), ConstInt::I32(_)) => {}, | |
106 | (SignedInt(ast::IntTy::I64), ConstInt::I64(_)) => {}, | |
32a655c1 | 107 | (SignedInt(ast::IntTy::I128), ConstInt::I128(_)) => {}, |
54a0048b SL |
108 | (SignedInt(ast::IntTy::Is), ConstInt::Isize(_)) => {}, |
109 | (UnsignedInt(ast::UintTy::U8), ConstInt::U8(_)) => {}, | |
110 | (UnsignedInt(ast::UintTy::U16), ConstInt::U16(_)) => {}, | |
111 | (UnsignedInt(ast::UintTy::U32), ConstInt::U32(_)) => {}, | |
112 | (UnsignedInt(ast::UintTy::U64), ConstInt::U64(_)) => {}, | |
32a655c1 | 113 | (UnsignedInt(ast::UintTy::U128), ConstInt::U128(_)) => {}, |
54a0048b SL |
114 | (UnsignedInt(ast::UintTy::Us), ConstInt::Usize(_)) => {}, |
115 | _ => bug!("disr type mismatch: {:?} vs {:?}", self, val), | |
e9174d1e SL |
116 | } |
117 | } | |
118 | ||
a7813a04 XL |
119 | fn disr_incr<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, val: Option<Disr>) |
120 | -> Option<Disr> { | |
121 | if let Some(val) = val { | |
122 | self.assert_ty_matches(val); | |
8bb4bdeb | 123 | (val + typed_literal!(tcx, *self, 1)).ok() |
a7813a04 XL |
124 | } else { |
125 | Some(self.initial_discriminant(tcx)) | |
126 | } | |
e9174d1e SL |
127 | } |
128 | } | |
129 | ||
130 | ||
131 | #[derive(Copy, Clone)] | |
32a655c1 SL |
132 | pub enum CopyImplementationError<'tcx> { |
133 | InfrigingField(&'tcx ty::FieldDef), | |
e9174d1e | 134 | NotAnAdt, |
cc61c64b | 135 | HasDestructor, |
e9174d1e SL |
136 | } |
137 | ||
138 | /// Describes whether a type is representable. For types that are not | |
139 | /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to | |
140 | /// distinguish between types that are recursive with themselves and types that | |
141 | /// contain a different recursive type. These cases can therefore be treated | |
142 | /// differently when reporting errors. | |
143 | /// | |
144 | /// The ordering of the cases is significant. They are sorted so that cmp::max | |
145 | /// will keep the "more erroneous" of two values. | |
7cac9316 | 146 | #[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)] |
e9174d1e SL |
147 | pub enum Representability { |
148 | Representable, | |
149 | ContainsRecursive, | |
7cac9316 | 150 | SelfRecursive(Vec<Span>), |
e9174d1e SL |
151 | } |
152 | ||
7cac9316 XL |
153 | impl<'tcx> ty::ParamEnv<'tcx> { |
154 | /// Construct a trait environment suitable for contexts where | |
155 | /// there are no where clauses in scope. | |
156 | pub fn empty(reveal: Reveal) -> Self { | |
157 | Self::new(ty::Slice::empty(), reveal) | |
158 | } | |
159 | ||
160 | /// Construct a trait environment with the given set of predicates. | |
161 | pub fn new(caller_bounds: &'tcx ty::Slice<ty::Predicate<'tcx>>, | |
162 | reveal: Reveal) | |
163 | -> Self { | |
164 | ty::ParamEnv { caller_bounds, reveal } | |
165 | } | |
166 | ||
167 | /// Returns a new parameter environment with the same clauses, but | |
168 | /// which "reveals" the true results of projections in all cases | |
169 | /// (even for associated types that are specializable). This is | |
170 | /// the desired behavior during trans and certain other special | |
171 | /// contexts; normally though we want to use `Reveal::UserFacing`, | |
172 | /// which is the default. | |
173 | pub fn reveal_all(self) -> Self { | |
174 | ty::ParamEnv { reveal: Reveal::All, ..self } | |
175 | } | |
176 | ||
177 | pub fn can_type_implement_copy<'a>(self, | |
178 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
a7813a04 | 179 | self_type: Ty<'tcx>, span: Span) |
7cac9316 | 180 | -> Result<(), CopyImplementationError<'tcx>> { |
e9174d1e | 181 | // FIXME: (@jroesch) float this code up |
041b39d2 | 182 | tcx.infer_ctxt().enter(|infcx| { |
32a655c1 SL |
183 | let (adt, substs) = match self_type.sty { |
184 | ty::TyAdt(adt, substs) => (adt, substs), | |
cc61c64b | 185 | _ => return Err(CopyImplementationError::NotAnAdt), |
a7813a04 | 186 | }; |
e9174d1e | 187 | |
32a655c1 SL |
188 | let field_implements_copy = |field: &ty::FieldDef| { |
189 | let cause = traits::ObligationCause::dummy(); | |
7cac9316 XL |
190 | match traits::fully_normalize(&infcx, cause, self, &field.ty(tcx, substs)) { |
191 | Ok(ty) => !infcx.type_moves_by_default(self, ty, span), | |
cc61c64b | 192 | Err(..) => false, |
32a655c1 SL |
193 | } |
194 | }; | |
195 | ||
196 | for variant in &adt.variants { | |
197 | for field in &variant.fields { | |
198 | if !field_implements_copy(field) { | |
199 | return Err(CopyImplementationError::InfrigingField(field)); | |
200 | } | |
201 | } | |
202 | } | |
203 | ||
8bb4bdeb | 204 | if adt.has_dtor(tcx) { |
a7813a04 XL |
205 | return Err(CopyImplementationError::HasDestructor); |
206 | } | |
e9174d1e | 207 | |
a7813a04 XL |
208 | Ok(()) |
209 | }) | |
e9174d1e SL |
210 | } |
211 | } | |
212 | ||
cc61c64b XL |
213 | impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> { |
214 | /// Creates a hash of the type `Ty` which will be the same no matter what crate | |
215 | /// context it's calculated within. This is used by the `type_id` intrinsic. | |
216 | pub fn type_id_hash(self, ty: Ty<'tcx>) -> u64 { | |
217 | let mut hasher = StableHasher::new(); | |
ea8adc8c | 218 | let mut hcx = self.create_stable_hashing_context(); |
cc61c64b | 219 | |
3b2f2976 XL |
220 | // We want the type_id be independent of the types free regions, so we |
221 | // erase them. The erase_regions() call will also anonymize bound | |
222 | // regions, which is desirable too. | |
223 | let ty = self.erase_regions(&ty); | |
224 | ||
cc61c64b XL |
225 | hcx.while_hashing_spans(false, |hcx| { |
226 | hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| { | |
227 | ty.hash_stable(hcx, &mut hasher); | |
228 | }); | |
229 | }); | |
230 | hasher.finish() | |
231 | } | |
232 | } | |
233 | ||
a7813a04 | 234 | impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { |
5bcae85e SL |
235 | pub fn has_error_field(self, ty: Ty<'tcx>) -> bool { |
236 | match ty.sty { | |
9e0c209e | 237 | ty::TyAdt(def, substs) => { |
5bcae85e SL |
238 | for field in def.all_fields() { |
239 | let field_ty = field.ty(self, substs); | |
240 | if let TyError = field_ty.sty { | |
241 | return true; | |
242 | } | |
243 | } | |
244 | } | |
cc61c64b | 245 | _ => (), |
5bcae85e SL |
246 | } |
247 | false | |
248 | } | |
249 | ||
e9174d1e SL |
250 | /// Returns the type of element at index `i` in tuple or tuple-like type `t`. |
251 | /// For an enum `t`, `variant` is None only if `t` is a univariant enum. | |
a7813a04 | 252 | pub fn positional_element_ty(self, |
e9174d1e SL |
253 | ty: Ty<'tcx>, |
254 | i: usize, | |
255 | variant: Option<DefId>) -> Option<Ty<'tcx>> { | |
256 | match (&ty.sty, variant) { | |
9e0c209e SL |
257 | (&TyAdt(adt, substs), Some(vid)) => { |
258 | adt.variant_with_id(vid).fields.get(i).map(|f| f.ty(self, substs)) | |
e9174d1e | 259 | } |
9e0c209e SL |
260 | (&TyAdt(adt, substs), None) => { |
261 | // Don't use `struct_variant`, this may be a univariant enum. | |
262 | adt.variants[0].fields.get(i).map(|f| f.ty(self, substs)) | |
e9174d1e | 263 | } |
8bb4bdeb | 264 | (&TyTuple(ref v, _), None) => v.get(i).cloned(), |
cc61c64b | 265 | _ => None, |
e9174d1e SL |
266 | } |
267 | } | |
268 | ||
269 | /// Returns the type of element at field `n` in struct or struct-like type `t`. | |
270 | /// For an enum `t`, `variant` must be some def id. | |
a7813a04 | 271 | pub fn named_element_ty(self, |
e9174d1e SL |
272 | ty: Ty<'tcx>, |
273 | n: Name, | |
274 | variant: Option<DefId>) -> Option<Ty<'tcx>> { | |
275 | match (&ty.sty, variant) { | |
9e0c209e SL |
276 | (&TyAdt(adt, substs), Some(vid)) => { |
277 | adt.variant_with_id(vid).find_field_named(n).map(|f| f.ty(self, substs)) | |
e9174d1e | 278 | } |
9e0c209e SL |
279 | (&TyAdt(adt, substs), None) => { |
280 | adt.struct_variant().find_field_named(n).map(|f| f.ty(self, substs)) | |
e9174d1e SL |
281 | } |
282 | _ => return None | |
283 | } | |
284 | } | |
285 | ||
e9174d1e SL |
286 | /// Returns the deeply last field of nested structures, or the same type, |
287 | /// if not a structure at all. Corresponds to the only possible unsized | |
288 | /// field, and its type can be used to determine unsizing strategy. | |
a7813a04 | 289 | pub fn struct_tail(self, mut ty: Ty<'tcx>) -> Ty<'tcx> { |
7cac9316 XL |
290 | loop { |
291 | match ty.sty { | |
292 | ty::TyAdt(def, substs) => { | |
293 | if !def.is_struct() { | |
294 | break; | |
295 | } | |
296 | match def.struct_variant().fields.last() { | |
297 | Some(f) => ty = f.ty(self, substs), | |
298 | None => break, | |
299 | } | |
300 | } | |
301 | ||
302 | ty::TyTuple(tys, _) => { | |
303 | if let Some((&last_ty, _)) = tys.split_last() { | |
304 | ty = last_ty; | |
305 | } else { | |
306 | break; | |
307 | } | |
308 | } | |
309 | ||
310 | _ => { | |
311 | break; | |
312 | } | |
e9174d1e SL |
313 | } |
314 | } | |
315 | ty | |
316 | } | |
317 | ||
318 | /// Same as applying struct_tail on `source` and `target`, but only | |
319 | /// keeps going as long as the two types are instances of the same | |
320 | /// structure definitions. | |
321 | /// For `(Foo<Foo<T>>, Foo<Trait>)`, the result will be `(Foo<T>, Trait)`, | |
322 | /// whereas struct_tail produces `T`, and `Trait`, respectively. | |
a7813a04 | 323 | pub fn struct_lockstep_tails(self, |
e9174d1e SL |
324 | source: Ty<'tcx>, |
325 | target: Ty<'tcx>) | |
326 | -> (Ty<'tcx>, Ty<'tcx>) { | |
327 | let (mut a, mut b) = (source, target); | |
041b39d2 XL |
328 | loop { |
329 | match (&a.sty, &b.sty) { | |
330 | (&TyAdt(a_def, a_substs), &TyAdt(b_def, b_substs)) | |
331 | if a_def == b_def && a_def.is_struct() => { | |
332 | if let Some(f) = a_def.struct_variant().fields.last() { | |
333 | a = f.ty(self, a_substs); | |
334 | b = f.ty(self, b_substs); | |
335 | } else { | |
336 | break; | |
337 | } | |
338 | }, | |
339 | (&TyTuple(a_tys, _), &TyTuple(b_tys, _)) | |
340 | if a_tys.len() == b_tys.len() => { | |
341 | if let Some(a_last) = a_tys.last() { | |
342 | a = a_last; | |
343 | b = b_tys.last().unwrap(); | |
344 | } else { | |
345 | break; | |
346 | } | |
347 | }, | |
cc61c64b | 348 | _ => break, |
e9174d1e SL |
349 | } |
350 | } | |
351 | (a, b) | |
352 | } | |
353 | ||
e9174d1e SL |
354 | /// Given a set of predicates that apply to an object type, returns |
355 | /// the region bounds that the (erased) `Self` type must | |
356 | /// outlive. Precisely *because* the `Self` type is erased, the | |
357 | /// parameter `erased_self_ty` must be supplied to indicate what type | |
358 | /// has been used to represent `Self` in the predicates | |
359 | /// themselves. This should really be a unique type; `FreshTy(0)` is a | |
360 | /// popular choice. | |
361 | /// | |
362 | /// NB: in some cases, particularly around higher-ranked bounds, | |
363 | /// this function returns a kind of conservative approximation. | |
364 | /// That is, all regions returned by this function are definitely | |
365 | /// required, but there may be other region bounds that are not | |
366 | /// returned, as well as requirements like `for<'a> T: 'a`. | |
367 | /// | |
368 | /// Requires that trait definitions have been processed so that we can | |
369 | /// elaborate predicates and walk supertraits. | |
7cac9316 XL |
370 | /// |
371 | /// FIXME callers may only have a &[Predicate], not a Vec, so that's | |
372 | /// what this code should accept. | |
a7813a04 | 373 | pub fn required_region_bounds(self, |
e9174d1e SL |
374 | erased_self_ty: Ty<'tcx>, |
375 | predicates: Vec<ty::Predicate<'tcx>>) | |
7cac9316 | 376 | -> Vec<ty::Region<'tcx>> { |
e9174d1e SL |
377 | debug!("required_region_bounds(erased_self_ty={:?}, predicates={:?})", |
378 | erased_self_ty, | |
379 | predicates); | |
380 | ||
381 | assert!(!erased_self_ty.has_escaping_regions()); | |
382 | ||
383 | traits::elaborate_predicates(self, predicates) | |
384 | .filter_map(|predicate| { | |
385 | match predicate { | |
386 | ty::Predicate::Projection(..) | | |
387 | ty::Predicate::Trait(..) | | |
388 | ty::Predicate::Equate(..) | | |
cc61c64b | 389 | ty::Predicate::Subtype(..) | |
e9174d1e SL |
390 | ty::Predicate::WellFormed(..) | |
391 | ty::Predicate::ObjectSafe(..) | | |
a7813a04 | 392 | ty::Predicate::ClosureKind(..) | |
ea8adc8c XL |
393 | ty::Predicate::RegionOutlives(..) | |
394 | ty::Predicate::ConstEvaluatable(..) => { | |
e9174d1e SL |
395 | None |
396 | } | |
397 | ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(t, r))) => { | |
398 | // Search for a bound of the form `erased_self_ty | |
399 | // : 'a`, but be wary of something like `for<'a> | |
400 | // erased_self_ty : 'a` (we interpret a | |
401 | // higher-ranked bound like that as 'static, | |
402 | // though at present the code in `fulfill.rs` | |
403 | // considers such bounds to be unsatisfiable, so | |
404 | // it's kind of a moot point since you could never | |
405 | // construct such an object, but this seems | |
406 | // correct even if that code changes). | |
407 | if t == erased_self_ty && !r.has_escaping_regions() { | |
408 | Some(r) | |
409 | } else { | |
410 | None | |
411 | } | |
412 | } | |
413 | } | |
414 | }) | |
415 | .collect() | |
416 | } | |
417 | ||
8bb4bdeb XL |
418 | /// Calculate the destructor of a given type. |
419 | pub fn calculate_dtor( | |
420 | self, | |
421 | adt_did: DefId, | |
422 | validate: &mut FnMut(Self, DefId) -> Result<(), ErrorReported> | |
423 | ) -> Option<ty::Destructor> { | |
ea8adc8c | 424 | let drop_trait = if let Some(def_id) = self.lang_items().drop_trait() { |
8bb4bdeb XL |
425 | def_id |
426 | } else { | |
427 | return None; | |
428 | }; | |
429 | ||
ff7c6d11 | 430 | ty::maps::queries::coherent_trait::ensure(self, drop_trait); |
8bb4bdeb XL |
431 | |
432 | let mut dtor_did = None; | |
7cac9316 | 433 | let ty = self.type_of(adt_did); |
041b39d2 | 434 | self.for_each_relevant_impl(drop_trait, ty, |impl_did| { |
8bb4bdeb XL |
435 | if let Some(item) = self.associated_items(impl_did).next() { |
436 | if let Ok(()) = validate(self, impl_did) { | |
437 | dtor_did = Some(item.def_id); | |
438 | } | |
439 | } | |
440 | }); | |
441 | ||
ff7c6d11 | 442 | Some(ty::Destructor { did: dtor_did? }) |
cc61c64b XL |
443 | } |
444 | ||
445 | /// Return the set of types that are required to be alive in | |
446 | /// order to run the destructor of `def` (see RFCs 769 and | |
447 | /// 1238). | |
448 | /// | |
449 | /// Note that this returns only the constraints for the | |
450 | /// destructor of `def` itself. For the destructors of the | |
451 | /// contents, you need `adt_dtorck_constraint`. | |
452 | pub fn destructor_constraints(self, def: &'tcx ty::AdtDef) | |
453 | -> Vec<ty::subst::Kind<'tcx>> | |
454 | { | |
455 | let dtor = match def.destructor(self) { | |
456 | None => { | |
457 | debug!("destructor_constraints({:?}) - no dtor", def.did); | |
458 | return vec![] | |
459 | } | |
460 | Some(dtor) => dtor.did | |
e9174d1e | 461 | }; |
b039eaaf SL |
462 | |
463 | // RFC 1238: if the destructor method is tagged with the | |
464 | // attribute `unsafe_destructor_blind_to_params`, then the | |
465 | // compiler is being instructed to *assume* that the | |
466 | // destructor will not access borrowed data, | |
467 | // even if such data is otherwise reachable. | |
e9174d1e | 468 | // |
b039eaaf SL |
469 | // Such access can be in plain sight (e.g. dereferencing |
470 | // `*foo.0` of `Foo<'a>(&'a u32)`) or indirectly hidden | |
471 | // (e.g. calling `foo.0.clone()` of `Foo<T:Clone>`). | |
cc61c64b XL |
472 | if self.has_attr(dtor, "unsafe_destructor_blind_to_params") { |
473 | debug!("destructor_constraint({:?}) - blind", def.did); | |
474 | return vec![]; | |
475 | } | |
476 | ||
477 | let impl_def_id = self.associated_item(dtor).container.id(); | |
7cac9316 | 478 | let impl_generics = self.generics_of(impl_def_id); |
cc61c64b XL |
479 | |
480 | // We have a destructor - all the parameters that are not | |
481 | // pure_wrt_drop (i.e, don't have a #[may_dangle] attribute) | |
482 | // must be live. | |
483 | ||
484 | // We need to return the list of parameters from the ADTs | |
485 | // generics/substs that correspond to impure parameters on the | |
486 | // impl's generics. This is a bit ugly, but conceptually simple: | |
487 | // | |
488 | // Suppose our ADT looks like the following | |
489 | // | |
490 | // struct S<X, Y, Z>(X, Y, Z); | |
491 | // | |
492 | // and the impl is | |
493 | // | |
494 | // impl<#[may_dangle] P0, P1, P2> Drop for S<P1, P2, P0> | |
495 | // | |
496 | // We want to return the parameters (X, Y). For that, we match | |
497 | // up the item-substs <X, Y, Z> with the substs on the impl ADT, | |
498 | // <P1, P2, P0>, and then look up which of the impl substs refer to | |
499 | // parameters marked as pure. | |
500 | ||
7cac9316 | 501 | let impl_substs = match self.type_of(impl_def_id).sty { |
cc61c64b XL |
502 | ty::TyAdt(def_, substs) if def_ == def => substs, |
503 | _ => bug!() | |
504 | }; | |
505 | ||
7cac9316 | 506 | let item_substs = match self.type_of(def.did).sty { |
cc61c64b XL |
507 | ty::TyAdt(def_, substs) if def_ == def => substs, |
508 | _ => bug!() | |
509 | }; | |
510 | ||
511 | let result = item_substs.iter().zip(impl_substs.iter()) | |
512 | .filter(|&(_, &k)| { | |
7cac9316 | 513 | if let Some(&ty::RegionKind::ReEarlyBound(ref ebr)) = k.as_region() { |
ea8adc8c | 514 | !impl_generics.region_param(ebr, self).pure_wrt_drop |
cc61c64b XL |
515 | } else if let Some(&ty::TyS { |
516 | sty: ty::TypeVariants::TyParam(ref pt), .. | |
517 | }) = k.as_type() { | |
ea8adc8c | 518 | !impl_generics.type_param(pt, self).pure_wrt_drop |
cc61c64b XL |
519 | } else { |
520 | // not a type or region param - this should be reported | |
521 | // as an error. | |
522 | false | |
523 | } | |
524 | }).map(|(&item_param, _)| item_param).collect(); | |
525 | debug!("destructor_constraint({:?}) = {:?}", def.did, result); | |
526 | result | |
b039eaaf | 527 | } |
9e0c209e | 528 | |
cc61c64b XL |
529 | /// Return a set of constraints that needs to be satisfied in |
530 | /// order for `ty` to be valid for destruction. | |
531 | pub fn dtorck_constraint_for_ty(self, | |
532 | span: Span, | |
533 | for_ty: Ty<'tcx>, | |
534 | depth: usize, | |
535 | ty: Ty<'tcx>) | |
536 | -> Result<ty::DtorckConstraint<'tcx>, ErrorReported> | |
537 | { | |
538 | debug!("dtorck_constraint_for_ty({:?}, {:?}, {:?}, {:?})", | |
539 | span, for_ty, depth, ty); | |
540 | ||
541 | if depth >= self.sess.recursion_limit.get() { | |
542 | let mut err = struct_span_err!( | |
543 | self.sess, span, E0320, | |
544 | "overflow while adding drop-check rules for {}", for_ty); | |
545 | err.note(&format!("overflowed on {}", ty)); | |
546 | err.emit(); | |
547 | return Err(ErrorReported); | |
548 | } | |
549 | ||
550 | let result = match ty.sty { | |
551 | ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | | |
abe05a73 | 552 | ty::TyFloat(_) | ty::TyStr | ty::TyNever | ty::TyForeign(..) | |
cc61c64b XL |
553 | ty::TyRawPtr(..) | ty::TyRef(..) | ty::TyFnDef(..) | ty::TyFnPtr(_) => { |
554 | // these types never have a destructor | |
555 | Ok(ty::DtorckConstraint::empty()) | |
556 | } | |
557 | ||
558 | ty::TyArray(ety, _) | ty::TySlice(ety) => { | |
559 | // single-element containers, behave like their element | |
560 | self.dtorck_constraint_for_ty(span, for_ty, depth+1, ety) | |
561 | } | |
562 | ||
563 | ty::TyTuple(tys, _) => { | |
564 | tys.iter().map(|ty| { | |
565 | self.dtorck_constraint_for_ty(span, for_ty, depth+1, ty) | |
566 | }).collect() | |
567 | } | |
568 | ||
569 | ty::TyClosure(def_id, substs) => { | |
570 | substs.upvar_tys(def_id, self).map(|ty| { | |
571 | self.dtorck_constraint_for_ty(span, for_ty, depth+1, ty) | |
572 | }).collect() | |
573 | } | |
574 | ||
ea8adc8c XL |
575 | ty::TyGenerator(def_id, substs, interior) => { |
576 | substs.upvar_tys(def_id, self).chain(iter::once(interior.witness)).map(|ty| { | |
577 | self.dtorck_constraint_for_ty(span, for_ty, depth+1, ty) | |
578 | }).collect() | |
579 | } | |
580 | ||
cc61c64b XL |
581 | ty::TyAdt(def, substs) => { |
582 | let ty::DtorckConstraint { | |
583 | dtorck_types, outlives | |
7cac9316 | 584 | } = self.at(span).adt_dtorck_constraint(def.did); |
cc61c64b XL |
585 | Ok(ty::DtorckConstraint { |
586 | // FIXME: we can try to recursively `dtorck_constraint_on_ty` | |
587 | // there, but that needs some way to handle cycles. | |
588 | dtorck_types: dtorck_types.subst(self, substs), | |
589 | outlives: outlives.subst(self, substs) | |
590 | }) | |
591 | } | |
592 | ||
593 | // Objects must be alive in order for their destructor | |
594 | // to be called. | |
595 | ty::TyDynamic(..) => Ok(ty::DtorckConstraint { | |
596 | outlives: vec![Kind::from(ty)], | |
597 | dtorck_types: vec![], | |
598 | }), | |
599 | ||
600 | // Types that can't be resolved. Pass them forward. | |
601 | ty::TyProjection(..) | ty::TyAnon(..) | ty::TyParam(..) => { | |
602 | Ok(ty::DtorckConstraint { | |
603 | outlives: vec![], | |
604 | dtorck_types: vec![ty], | |
605 | }) | |
606 | } | |
607 | ||
608 | ty::TyInfer(..) | ty::TyError => { | |
609 | self.sess.delay_span_bug(span, "unresolved type in dtorck"); | |
610 | Err(ErrorReported) | |
611 | } | |
612 | }; | |
613 | ||
614 | debug!("dtorck_constraint_for_ty({:?}) = {:?}", ty, result); | |
615 | result | |
616 | } | |
617 | ||
abe05a73 XL |
618 | pub fn is_closure(self, def_id: DefId) -> bool { |
619 | self.def_key(def_id).disambiguated_data.data == DefPathData::ClosureExpr | |
620 | } | |
621 | ||
ff7c6d11 XL |
622 | /// Given the `DefId` of a fn or closure, returns the `DefId` of |
623 | /// the innermost fn item that the closure is contained within. | |
624 | /// This is a significant def-id because, when we do | |
625 | /// type-checking, we type-check this fn item and all of its | |
626 | /// (transitive) closures together. Therefore, when we fetch the | |
627 | /// `typeck_tables_of` the closure, for example, we really wind up | |
628 | /// fetching the `typeck_tables_of` the enclosing fn item. | |
cc61c64b | 629 | pub fn closure_base_def_id(self, def_id: DefId) -> DefId { |
476ff2be | 630 | let mut def_id = def_id; |
abe05a73 | 631 | while self.is_closure(def_id) { |
476ff2be SL |
632 | def_id = self.parent_def_id(def_id).unwrap_or_else(|| { |
633 | bug!("closure {:?} has no parent", def_id); | |
634 | }); | |
635 | } | |
636 | def_id | |
9e0c209e | 637 | } |
cc61c64b | 638 | |
ff7c6d11 XL |
639 | /// Given the def-id and substs a closure, creates the type of |
640 | /// `self` argument that the closure expects. For example, for a | |
641 | /// `Fn` closure, this would return a reference type `&T` where | |
642 | /// `T=closure_ty`. | |
643 | /// | |
644 | /// Returns `None` if this closure's kind has not yet been inferred. | |
645 | /// This should only be possible during type checking. | |
646 | /// | |
647 | /// Note that the return value is a late-bound region and hence | |
648 | /// wrapped in a binder. | |
649 | pub fn closure_env_ty(self, | |
650 | closure_def_id: DefId, | |
651 | closure_substs: ty::ClosureSubsts<'tcx>) | |
652 | -> Option<ty::Binder<Ty<'tcx>>> | |
653 | { | |
654 | let closure_ty = self.mk_closure(closure_def_id, closure_substs); | |
655 | let env_region = ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrEnv); | |
656 | let closure_kind_ty = closure_substs.closure_kind_ty(closure_def_id, self); | |
657 | let closure_kind = closure_kind_ty.to_opt_closure_kind()?; | |
658 | let env_ty = match closure_kind { | |
659 | ty::ClosureKind::Fn => self.mk_imm_ref(self.mk_region(env_region), closure_ty), | |
660 | ty::ClosureKind::FnMut => self.mk_mut_ref(self.mk_region(env_region), closure_ty), | |
661 | ty::ClosureKind::FnOnce => closure_ty, | |
662 | }; | |
663 | Some(ty::Binder(env_ty)) | |
664 | } | |
665 | ||
cc61c64b XL |
666 | /// Given the def-id of some item that has no type parameters, make |
667 | /// a suitable "empty substs" for it. | |
668 | pub fn empty_substs_for_def_id(self, item_def_id: DefId) -> &'tcx ty::Substs<'tcx> { | |
669 | ty::Substs::for_item(self, item_def_id, | |
670 | |_, _| self.types.re_erased, | |
671 | |_, _| { | |
672 | bug!("empty_substs_for_def_id: {:?} has type parameters", item_def_id) | |
673 | }) | |
674 | } | |
7cac9316 XL |
675 | |
676 | pub fn const_usize(&self, val: u16) -> ConstInt { | |
ea8adc8c | 677 | match self.sess.target.usize_ty { |
7cac9316 XL |
678 | ast::UintTy::U16 => ConstInt::Usize(ConstUsize::Us16(val as u16)), |
679 | ast::UintTy::U32 => ConstInt::Usize(ConstUsize::Us32(val as u32)), | |
680 | ast::UintTy::U64 => ConstInt::Usize(ConstUsize::Us64(val as u64)), | |
681 | _ => bug!(), | |
682 | } | |
683 | } | |
abe05a73 XL |
684 | |
685 | /// Check if the node pointed to by def_id is a mutable static item | |
686 | pub fn is_static_mut(&self, def_id: DefId) -> bool { | |
687 | if let Some(node) = self.hir.get_if_local(def_id) { | |
688 | match node { | |
689 | Node::NodeItem(&hir::Item { | |
690 | node: hir::ItemStatic(_, hir::MutMutable, _), .. | |
691 | }) => true, | |
692 | Node::NodeForeignItem(&hir::ForeignItem { | |
693 | node: hir::ForeignItemStatic(_, mutbl), .. | |
694 | }) => mutbl, | |
695 | _ => false | |
696 | } | |
697 | } else { | |
698 | match self.describe_def(def_id) { | |
699 | Some(Def::Static(_, mutbl)) => mutbl, | |
700 | _ => false | |
701 | } | |
702 | } | |
703 | } | |
9e0c209e SL |
704 | } |
705 | ||
476ff2be | 706 | pub struct TypeIdHasher<'a, 'gcx: 'a+'tcx, 'tcx: 'a, W> { |
5bcae85e | 707 | tcx: TyCtxt<'a, 'gcx, 'tcx>, |
476ff2be | 708 | state: StableHasher<W>, |
5bcae85e SL |
709 | } |
710 | ||
476ff2be SL |
711 | impl<'a, 'gcx, 'tcx, W> TypeIdHasher<'a, 'gcx, 'tcx, W> |
712 | where W: StableHasherResult | |
713 | { | |
714 | pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Self { | |
715 | TypeIdHasher { tcx: tcx, state: StableHasher::new() } | |
9e0c209e SL |
716 | } |
717 | ||
476ff2be SL |
718 | pub fn finish(self) -> W { |
719 | self.state.finish() | |
5bcae85e SL |
720 | } |
721 | ||
476ff2be SL |
722 | pub fn hash<T: Hash>(&mut self, x: T) { |
723 | x.hash(&mut self.state); | |
9e0c209e SL |
724 | } |
725 | ||
5bcae85e SL |
726 | fn hash_discriminant_u8<T>(&mut self, x: &T) { |
727 | let v = unsafe { | |
728 | intrinsics::discriminant_value(x) | |
729 | }; | |
730 | let b = v as u8; | |
731 | assert_eq!(v, b as u64); | |
732 | self.hash(b) | |
733 | } | |
734 | ||
735 | fn def_id(&mut self, did: DefId) { | |
9e0c209e | 736 | // Hash the DefPath corresponding to the DefId, which is independent |
cc61c64b XL |
737 | // of compiler internal state. We already have a stable hash value of |
738 | // all DefPaths available via tcx.def_path_hash(), so we just feed that | |
739 | // into the hasher. | |
740 | let hash = self.tcx.def_path_hash(did); | |
741 | self.hash(hash); | |
5bcae85e SL |
742 | } |
743 | } | |
744 | ||
476ff2be SL |
745 | impl<'a, 'gcx, 'tcx, W> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx, W> |
746 | where W: StableHasherResult | |
747 | { | |
5bcae85e SL |
748 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool { |
749 | // Distinguish between the Ty variants uniformly. | |
750 | self.hash_discriminant_u8(&ty.sty); | |
751 | ||
752 | match ty.sty { | |
753 | TyInt(i) => self.hash(i), | |
754 | TyUint(u) => self.hash(u), | |
755 | TyFloat(f) => self.hash(f), | |
ea8adc8c XL |
756 | TyArray(_, n) => { |
757 | self.hash_discriminant_u8(&n.val); | |
758 | match n.val { | |
759 | ConstVal::Integral(x) => self.hash(x.to_u64().unwrap()), | |
760 | ConstVal::Unevaluated(def_id, _) => self.def_id(def_id), | |
761 | _ => bug!("arrays should not have {:?} as length", n) | |
762 | } | |
763 | } | |
5bcae85e SL |
764 | TyRawPtr(m) | |
765 | TyRef(_, m) => self.hash(m.mutbl), | |
766 | TyClosure(def_id, _) | | |
ea8adc8c | 767 | TyGenerator(def_id, _, _) | |
5bcae85e | 768 | TyAnon(def_id, _) | |
041b39d2 | 769 | TyFnDef(def_id, _) => self.def_id(def_id), |
9e0c209e | 770 | TyAdt(d, _) => self.def_id(d.did), |
abe05a73 | 771 | TyForeign(def_id) => self.def_id(def_id), |
5bcae85e | 772 | TyFnPtr(f) => { |
8bb4bdeb XL |
773 | self.hash(f.unsafety()); |
774 | self.hash(f.abi()); | |
775 | self.hash(f.variadic()); | |
776 | self.hash(f.inputs().skip_binder().len()); | |
5bcae85e | 777 | } |
476ff2be SL |
778 | TyDynamic(ref data, ..) => { |
779 | if let Some(p) = data.principal() { | |
780 | self.def_id(p.def_id()); | |
781 | } | |
782 | for d in data.auto_traits() { | |
783 | self.def_id(d); | |
784 | } | |
5bcae85e | 785 | } |
8bb4bdeb | 786 | TyTuple(tys, defaulted) => { |
5bcae85e | 787 | self.hash(tys.len()); |
8bb4bdeb | 788 | self.hash(defaulted); |
5bcae85e SL |
789 | } |
790 | TyParam(p) => { | |
5bcae85e SL |
791 | self.hash(p.idx); |
792 | self.hash(p.name.as_str()); | |
793 | } | |
794 | TyProjection(ref data) => { | |
7cac9316 | 795 | self.def_id(data.item_def_id); |
5bcae85e SL |
796 | } |
797 | TyNever | | |
798 | TyBool | | |
799 | TyChar | | |
800 | TyStr | | |
9e0c209e SL |
801 | TySlice(_) => {} |
802 | ||
803 | TyError | | |
804 | TyInfer(_) => bug!("TypeIdHasher: unexpected type {}", ty) | |
5bcae85e SL |
805 | } |
806 | ||
807 | ty.super_visit_with(self) | |
808 | } | |
809 | ||
7cac9316 | 810 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool { |
cc61c64b | 811 | self.hash_discriminant_u8(r); |
9e0c209e | 812 | match *r { |
cc61c64b XL |
813 | ty::ReErased | |
814 | ty::ReStatic | | |
815 | ty::ReEmpty => { | |
816 | // No variant fields to hash for these ... | |
5bcae85e SL |
817 | } |
818 | ty::ReLateBound(db, ty::BrAnon(i)) => { | |
cc61c64b | 819 | self.hash(db.depth); |
5bcae85e SL |
820 | self.hash(i); |
821 | } | |
7cac9316 XL |
822 | ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, .. }) => { |
823 | self.def_id(def_id); | |
cc61c64b | 824 | } |
ff7c6d11 XL |
825 | |
826 | ty::ReClosureBound(..) | | |
5bcae85e SL |
827 | ty::ReLateBound(..) | |
828 | ty::ReFree(..) | | |
829 | ty::ReScope(..) | | |
830 | ty::ReVar(..) | | |
831 | ty::ReSkolemized(..) => { | |
9e0c209e | 832 | bug!("TypeIdHasher: unexpected region {:?}", r) |
5bcae85e SL |
833 | } |
834 | } | |
835 | false | |
836 | } | |
837 | ||
838 | fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, x: &ty::Binder<T>) -> bool { | |
839 | // Anonymize late-bound regions so that, for example: | |
840 | // `for<'a, b> fn(&'a &'b T)` and `for<'a, b> fn(&'b &'a T)` | |
841 | // result in the same TypeId (the two types are equivalent). | |
842 | self.tcx.anonymize_late_bound_regions(x).super_visit_with(self) | |
843 | } | |
844 | } | |
845 | ||
a7813a04 | 846 | impl<'a, 'tcx> ty::TyS<'tcx> { |
7cac9316 XL |
847 | pub fn moves_by_default(&'tcx self, |
848 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
849 | param_env: ty::ParamEnv<'tcx>, | |
850 | span: Span) | |
851 | -> bool { | |
852 | !tcx.at(span).is_copy_raw(param_env.and(self)) | |
e9174d1e SL |
853 | } |
854 | ||
7cac9316 XL |
855 | pub fn is_sized(&'tcx self, |
856 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
857 | param_env: ty::ParamEnv<'tcx>, | |
858 | span: Span)-> bool | |
e9174d1e | 859 | { |
7cac9316 | 860 | tcx.at(span).is_sized_raw(param_env.and(self)) |
e9174d1e SL |
861 | } |
862 | ||
7cac9316 XL |
863 | pub fn is_freeze(&'tcx self, |
864 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
865 | param_env: ty::ParamEnv<'tcx>, | |
866 | span: Span)-> bool | |
cc61c64b | 867 | { |
7cac9316 | 868 | tcx.at(span).is_freeze_raw(param_env.and(self)) |
cc61c64b XL |
869 | } |
870 | ||
871 | /// If `ty.needs_drop(...)` returns `true`, then `ty` is definitely | |
872 | /// non-copy and *might* have a destructor attached; if it returns | |
873 | /// `false`, then `ty` definitely has no destructor (i.e. no drop glue). | |
874 | /// | |
875 | /// (Note that this implies that if `ty` has a destructor attached, | |
876 | /// then `needs_drop` will definitely return `true` for `ty`.) | |
877 | #[inline] | |
7cac9316 XL |
878 | pub fn needs_drop(&'tcx self, |
879 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
880 | param_env: ty::ParamEnv<'tcx>) | |
881 | -> bool { | |
882 | tcx.needs_drop_raw(param_env.and(self)) | |
cc61c64b XL |
883 | } |
884 | ||
e9174d1e SL |
885 | /// Check whether a type is representable. This means it cannot contain unboxed |
886 | /// structural recursion. This check is needed for structs and enums. | |
7cac9316 XL |
887 | pub fn is_representable(&'tcx self, |
888 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
889 | sp: Span) | |
a7813a04 | 890 | -> Representability { |
e9174d1e SL |
891 | |
892 | // Iterate until something non-representable is found | |
7cac9316 XL |
893 | fn fold_repr<It: Iterator<Item=Representability>>(iter: It) -> Representability { |
894 | iter.fold(Representability::Representable, |r1, r2| { | |
895 | match (r1, r2) { | |
896 | (Representability::SelfRecursive(v1), | |
897 | Representability::SelfRecursive(v2)) => { | |
898 | Representability::SelfRecursive(v1.iter().map(|s| *s).chain(v2).collect()) | |
899 | } | |
900 | (r1, r2) => cmp::max(r1, r2) | |
901 | } | |
902 | }) | |
e9174d1e SL |
903 | } |
904 | ||
041b39d2 XL |
905 | fn are_inner_types_recursive<'a, 'tcx>( |
906 | tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span, | |
907 | seen: &mut Vec<Ty<'tcx>>, | |
908 | representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, | |
909 | ty: Ty<'tcx>) | |
910 | -> Representability | |
911 | { | |
e9174d1e | 912 | match ty.sty { |
8bb4bdeb | 913 | TyTuple(ref ts, _) => { |
7cac9316 XL |
914 | // Find non representable |
915 | fold_repr(ts.iter().map(|ty| { | |
041b39d2 | 916 | is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty) |
7cac9316 | 917 | })) |
e9174d1e SL |
918 | } |
919 | // Fixed-length vectors. | |
920 | // FIXME(#11924) Behavior undecided for zero-length vectors. | |
921 | TyArray(ty, _) => { | |
041b39d2 | 922 | is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty) |
e9174d1e | 923 | } |
9e0c209e | 924 | TyAdt(def, substs) => { |
7cac9316 XL |
925 | // Find non representable fields with their spans |
926 | fold_repr(def.all_fields().map(|field| { | |
927 | let ty = field.ty(tcx, substs); | |
928 | let span = tcx.hir.span_if_local(field.did).unwrap_or(sp); | |
041b39d2 XL |
929 | match is_type_structurally_recursive(tcx, span, seen, |
930 | representable_cache, ty) | |
931 | { | |
7cac9316 XL |
932 | Representability::SelfRecursive(_) => { |
933 | Representability::SelfRecursive(vec![span]) | |
934 | } | |
935 | x => x, | |
936 | } | |
937 | })) | |
e9174d1e SL |
938 | } |
939 | TyClosure(..) => { | |
940 | // this check is run on type definitions, so we don't expect | |
941 | // to see closure types | |
54a0048b | 942 | bug!("requires check invoked on inapplicable type: {:?}", ty) |
e9174d1e SL |
943 | } |
944 | _ => Representability::Representable, | |
945 | } | |
946 | } | |
947 | ||
476ff2be | 948 | fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool { |
e9174d1e | 949 | match ty.sty { |
9e0c209e | 950 | TyAdt(ty_def, _) => { |
e9174d1e SL |
951 | ty_def == def |
952 | } | |
953 | _ => false | |
954 | } | |
955 | } | |
956 | ||
957 | fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool { | |
958 | match (&a.sty, &b.sty) { | |
9e0c209e | 959 | (&TyAdt(did_a, substs_a), &TyAdt(did_b, substs_b)) => { |
e9174d1e SL |
960 | if did_a != did_b { |
961 | return false; | |
962 | } | |
963 | ||
9e0c209e | 964 | substs_a.types().zip(substs_b.types()).all(|(a, b)| same_type(a, b)) |
e9174d1e | 965 | } |
cc61c64b | 966 | _ => a == b, |
e9174d1e SL |
967 | } |
968 | } | |
969 | ||
970 | // Does the type `ty` directly (without indirection through a pointer) | |
971 | // contain any types on stack `seen`? | |
041b39d2 XL |
972 | fn is_type_structurally_recursive<'a, 'tcx>( |
973 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
974 | sp: Span, | |
975 | seen: &mut Vec<Ty<'tcx>>, | |
976 | representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, | |
977 | ty: Ty<'tcx>) -> Representability | |
978 | { | |
7cac9316 | 979 | debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp); |
041b39d2 XL |
980 | if let Some(representability) = representable_cache.get(ty) { |
981 | debug!("is_type_structurally_recursive: {:?} {:?} - (cached) {:?}", | |
982 | ty, sp, representability); | |
983 | return representability.clone(); | |
984 | } | |
985 | ||
986 | let representability = is_type_structurally_recursive_inner( | |
987 | tcx, sp, seen, representable_cache, ty); | |
988 | ||
989 | representable_cache.insert(ty, representability.clone()); | |
990 | representability | |
991 | } | |
e9174d1e | 992 | |
041b39d2 XL |
993 | fn is_type_structurally_recursive_inner<'a, 'tcx>( |
994 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
995 | sp: Span, | |
996 | seen: &mut Vec<Ty<'tcx>>, | |
997 | representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, | |
998 | ty: Ty<'tcx>) -> Representability | |
999 | { | |
e9174d1e | 1000 | match ty.sty { |
9e0c209e | 1001 | TyAdt(def, _) => { |
e9174d1e SL |
1002 | { |
1003 | // Iterate through stack of previously seen types. | |
1004 | let mut iter = seen.iter(); | |
1005 | ||
1006 | // The first item in `seen` is the type we are actually curious about. | |
1007 | // We want to return SelfRecursive if this type contains itself. | |
1008 | // It is important that we DON'T take generic parameters into account | |
1009 | // for this check, so that Bar<T> in this example counts as SelfRecursive: | |
1010 | // | |
1011 | // struct Foo; | |
1012 | // struct Bar<T> { x: Bar<Foo> } | |
1013 | ||
3157f602 XL |
1014 | if let Some(&seen_type) = iter.next() { |
1015 | if same_struct_or_enum(seen_type, def) { | |
1016 | debug!("SelfRecursive: {:?} contains {:?}", | |
1017 | seen_type, | |
1018 | ty); | |
7cac9316 | 1019 | return Representability::SelfRecursive(vec![sp]); |
e9174d1e | 1020 | } |
e9174d1e SL |
1021 | } |
1022 | ||
1023 | // We also need to know whether the first item contains other types | |
1024 | // that are structurally recursive. If we don't catch this case, we | |
1025 | // will recurse infinitely for some inputs. | |
1026 | // | |
1027 | // It is important that we DO take generic parameters into account | |
1028 | // here, so that code like this is considered SelfRecursive, not | |
1029 | // ContainsRecursive: | |
1030 | // | |
1031 | // struct Foo { Option<Option<Foo>> } | |
1032 | ||
1033 | for &seen_type in iter { | |
1034 | if same_type(ty, seen_type) { | |
1035 | debug!("ContainsRecursive: {:?} contains {:?}", | |
1036 | seen_type, | |
1037 | ty); | |
1038 | return Representability::ContainsRecursive; | |
1039 | } | |
1040 | } | |
1041 | } | |
1042 | ||
1043 | // For structs and enums, track all previously seen types by pushing them | |
1044 | // onto the 'seen' stack. | |
1045 | seen.push(ty); | |
041b39d2 | 1046 | let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty); |
e9174d1e SL |
1047 | seen.pop(); |
1048 | out | |
1049 | } | |
1050 | _ => { | |
1051 | // No need to push in other cases. | |
041b39d2 | 1052 | are_inner_types_recursive(tcx, sp, seen, representable_cache, ty) |
e9174d1e SL |
1053 | } |
1054 | } | |
1055 | } | |
1056 | ||
1057 | debug!("is_type_representable: {:?}", self); | |
1058 | ||
1059 | // To avoid a stack overflow when checking an enum variant or struct that | |
1060 | // contains a different, structurally recursive type, maintain a stack | |
1061 | // of seen types and check recursion for each of them (issues #3008, #3779). | |
1062 | let mut seen: Vec<Ty> = Vec::new(); | |
041b39d2 XL |
1063 | let mut representable_cache = FxHashMap(); |
1064 | let r = is_type_structurally_recursive( | |
1065 | tcx, sp, &mut seen, &mut representable_cache, self); | |
e9174d1e SL |
1066 | debug!("is_type_representable: {:?} is {:?}", self, r); |
1067 | r | |
1068 | } | |
1069 | } | |
7cac9316 XL |
1070 | |
1071 | fn is_copy_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1072 | query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) | |
1073 | -> bool | |
1074 | { | |
1075 | let (param_env, ty) = query.into_parts(); | |
1076 | let trait_def_id = tcx.require_lang_item(lang_items::CopyTraitLangItem); | |
041b39d2 | 1077 | tcx.infer_ctxt() |
7cac9316 XL |
1078 | .enter(|infcx| traits::type_known_to_meet_bound(&infcx, |
1079 | param_env, | |
1080 | ty, | |
1081 | trait_def_id, | |
1082 | DUMMY_SP)) | |
1083 | } | |
1084 | ||
1085 | fn is_sized_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1086 | query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) | |
1087 | -> bool | |
1088 | { | |
1089 | let (param_env, ty) = query.into_parts(); | |
1090 | let trait_def_id = tcx.require_lang_item(lang_items::SizedTraitLangItem); | |
041b39d2 | 1091 | tcx.infer_ctxt() |
7cac9316 XL |
1092 | .enter(|infcx| traits::type_known_to_meet_bound(&infcx, |
1093 | param_env, | |
1094 | ty, | |
1095 | trait_def_id, | |
1096 | DUMMY_SP)) | |
1097 | } | |
1098 | ||
1099 | fn is_freeze_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1100 | query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) | |
1101 | -> bool | |
1102 | { | |
1103 | let (param_env, ty) = query.into_parts(); | |
1104 | let trait_def_id = tcx.require_lang_item(lang_items::FreezeTraitLangItem); | |
041b39d2 | 1105 | tcx.infer_ctxt() |
7cac9316 XL |
1106 | .enter(|infcx| traits::type_known_to_meet_bound(&infcx, |
1107 | param_env, | |
1108 | ty, | |
1109 | trait_def_id, | |
1110 | DUMMY_SP)) | |
1111 | } | |
1112 | ||
1113 | fn needs_drop_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1114 | query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) | |
1115 | -> bool | |
1116 | { | |
1117 | let (param_env, ty) = query.into_parts(); | |
1118 | ||
1119 | let needs_drop = |ty: Ty<'tcx>| -> bool { | |
1120 | match ty::queries::needs_drop_raw::try_get(tcx, DUMMY_SP, param_env.and(ty)) { | |
1121 | Ok(v) => v, | |
3b2f2976 | 1122 | Err(mut bug) => { |
7cac9316 XL |
1123 | // Cycles should be reported as an error by `check_representable`. |
1124 | // | |
3b2f2976 XL |
1125 | // Consider the type as not needing drop in the meanwhile to |
1126 | // avoid further errors. | |
1127 | // | |
1128 | // In case we forgot to emit a bug elsewhere, delay our | |
1129 | // diagnostic to get emitted as a compiler bug. | |
1130 | bug.delay_as_bug(); | |
7cac9316 XL |
1131 | false |
1132 | } | |
1133 | } | |
1134 | }; | |
1135 | ||
1136 | assert!(!ty.needs_infer()); | |
1137 | ||
1138 | match ty.sty { | |
1139 | // Fast-path for primitive types | |
1140 | ty::TyInfer(ty::FreshIntTy(_)) | ty::TyInfer(ty::FreshFloatTy(_)) | | |
1141 | ty::TyBool | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) | ty::TyNever | | |
1142 | ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar | | |
1143 | ty::TyRawPtr(_) | ty::TyRef(..) | ty::TyStr => false, | |
1144 | ||
abe05a73 XL |
1145 | // Foreign types can never have destructors |
1146 | ty::TyForeign(..) => false, | |
1147 | ||
7cac9316 XL |
1148 | // Issue #22536: We first query type_moves_by_default. It sees a |
1149 | // normalized version of the type, and therefore will definitely | |
1150 | // know whether the type implements Copy (and thus needs no | |
1151 | // cleanup/drop/zeroing) ... | |
1152 | _ if !ty.moves_by_default(tcx, param_env, DUMMY_SP) => false, | |
1153 | ||
1154 | // ... (issue #22536 continued) but as an optimization, still use | |
1155 | // prior logic of asking for the structural "may drop". | |
1156 | ||
1157 | // FIXME(#22815): Note that this is a conservative heuristic; | |
1158 | // it may report that the type "may drop" when actual type does | |
1159 | // not actually have a destructor associated with it. But since | |
1160 | // the type absolutely did not have the `Copy` bound attached | |
1161 | // (see above), it is sound to treat it as having a destructor. | |
1162 | ||
1163 | // User destructors are the only way to have concrete drop types. | |
1164 | ty::TyAdt(def, _) if def.has_dtor(tcx) => true, | |
1165 | ||
1166 | // Can refer to a type which may drop. | |
1167 | // FIXME(eddyb) check this against a ParamEnv. | |
1168 | ty::TyDynamic(..) | ty::TyProjection(..) | ty::TyParam(_) | | |
1169 | ty::TyAnon(..) | ty::TyInfer(_) | ty::TyError => true, | |
1170 | ||
1171 | // Structural recursion. | |
1172 | ty::TyArray(ty, _) | ty::TySlice(ty) => needs_drop(ty), | |
1173 | ||
1174 | ty::TyClosure(def_id, ref substs) => substs.upvar_tys(def_id, tcx).any(needs_drop), | |
1175 | ||
ea8adc8c XL |
1176 | // Pessimistically assume that all generators will require destructors |
1177 | // as we don't know if a destructor is a noop or not until after the MIR | |
1178 | // state transformation pass | |
1179 | ty::TyGenerator(..) => true, | |
1180 | ||
7cac9316 XL |
1181 | ty::TyTuple(ref tys, _) => tys.iter().cloned().any(needs_drop), |
1182 | ||
1183 | // unions don't have destructors regardless of the child types | |
1184 | ty::TyAdt(def, _) if def.is_union() => false, | |
1185 | ||
1186 | ty::TyAdt(def, substs) => | |
1187 | def.variants.iter().any( | |
1188 | |variant| variant.fields.iter().any( | |
1189 | |field| needs_drop(field.ty(tcx, substs)))), | |
1190 | } | |
1191 | } | |
1192 | ||
abe05a73 XL |
1193 | pub enum ExplicitSelf<'tcx> { |
1194 | ByValue, | |
1195 | ByReference(ty::Region<'tcx>, hir::Mutability), | |
ff7c6d11 | 1196 | ByRawPointer(hir::Mutability), |
abe05a73 XL |
1197 | ByBox, |
1198 | Other | |
1199 | } | |
1200 | ||
1201 | impl<'tcx> ExplicitSelf<'tcx> { | |
1202 | /// Categorizes an explicit self declaration like `self: SomeType` | |
1203 | /// into either `self`, `&self`, `&mut self`, `Box<self>`, or | |
1204 | /// `Other`. | |
1205 | /// This is mainly used to require the arbitrary_self_types feature | |
1206 | /// in the case of `Other`, to improve error messages in the common cases, | |
1207 | /// and to make `Other` non-object-safe. | |
1208 | /// | |
1209 | /// Examples: | |
1210 | /// | |
1211 | /// ``` | |
1212 | /// impl<'a> Foo for &'a T { | |
1213 | /// // Legal declarations: | |
1214 | /// fn method1(self: &&'a T); // ExplicitSelf::ByReference | |
1215 | /// fn method2(self: &'a T); // ExplicitSelf::ByValue | |
1216 | /// fn method3(self: Box<&'a T>); // ExplicitSelf::ByBox | |
1217 | /// fn method4(self: Rc<&'a T>); // ExplicitSelf::Other | |
1218 | /// | |
1219 | /// // Invalid cases will be caught by `check_method_receiver`: | |
1220 | /// fn method_err1(self: &'a mut T); // ExplicitSelf::Other | |
1221 | /// fn method_err2(self: &'static T) // ExplicitSelf::ByValue | |
1222 | /// fn method_err3(self: &&T) // ExplicitSelf::ByReference | |
1223 | /// } | |
1224 | /// ``` | |
1225 | /// | |
1226 | pub fn determine<P>( | |
1227 | self_arg_ty: Ty<'tcx>, | |
1228 | is_self_ty: P | |
1229 | ) -> ExplicitSelf<'tcx> | |
1230 | where | |
1231 | P: Fn(Ty<'tcx>) -> bool | |
1232 | { | |
1233 | use self::ExplicitSelf::*; | |
1234 | ||
1235 | match self_arg_ty.sty { | |
1236 | _ if is_self_ty(self_arg_ty) => ByValue, | |
ff7c6d11 | 1237 | ty::TyRef(region, ty::TypeAndMut { ty, mutbl }) if is_self_ty(ty) => { |
abe05a73 XL |
1238 | ByReference(region, mutbl) |
1239 | } | |
ff7c6d11 XL |
1240 | ty::TyRawPtr(ty::TypeAndMut { ty, mutbl }) if is_self_ty(ty) => { |
1241 | ByRawPointer(mutbl) | |
1242 | } | |
1243 | ty::TyAdt(def, _) if def.is_box() && is_self_ty(self_arg_ty.boxed_ty()) => { | |
1244 | ByBox | |
1245 | } | |
abe05a73 XL |
1246 | _ => Other |
1247 | } | |
1248 | } | |
1249 | } | |
1250 | ||
7cac9316 XL |
1251 | pub fn provide(providers: &mut ty::maps::Providers) { |
1252 | *providers = ty::maps::Providers { | |
1253 | is_copy_raw, | |
1254 | is_sized_raw, | |
1255 | is_freeze_raw, | |
1256 | needs_drop_raw, | |
7cac9316 XL |
1257 | ..*providers |
1258 | }; | |
1259 | } |