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.
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.
11 //! misc. type-system utilities too small to deserve their own file
14 use middle
::const_eval
::{self, ConstVal, ErrKind}
;
15 use middle
::const_eval
::EvalHint
::UncheckedExprHint
;
16 use middle
::def_id
::DefId
;
17 use middle
::subst
::{self, Subst, Substs}
;
21 use middle
::ty
::{self, Ty, TypeAndMut, TypeFlags, TypeFoldable}
;
22 use middle
::ty
::{Disr, ParameterEnvironment}
;
23 use middle
::ty
::TypeVariants
::*;
24 use util
::num
::ToPrimitive
;
27 use std
::hash
::{Hash, SipHasher, Hasher}
;
29 use syntax
::ast
::{self, Name}
;
30 use syntax
::attr
::{self, AttrMetaMethods, SignedInt, UnsignedInt}
;
31 use syntax
::codemap
::Span
;
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
;
44 impl IntTypeExt
for attr
::IntType
{
45 fn to_ty
<'tcx
>(&self, cx
: &ty
::ctxt
<'tcx
>) -> Ty
<'tcx
> {
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,
60 fn i64_to_disr(&self, val
: i64) -> Option
<Disr
> {
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
),
71 UnsignedInt(ast
::UintTy
::Us
) |
72 SignedInt(ast
::IntTy
::Is
) => unreachable
!(),
76 fn u64_to_disr(&self, val
: u64) -> Option
<Disr
> {
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
),
87 UnsignedInt(ast
::UintTy
::Us
) |
88 SignedInt(ast
::IntTy
::Is
) => unreachable
!(),
92 fn disr_incr(&self, val
: Disr
) -> Option
<Disr
> {
94 ($e
:expr
) => { $e.and_then(|v|v.checked_add(1)).map(|v| v as Disr) }
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.
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)),
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
)),
110 UnsignedInt(ast
::UintTy
::Us
) |
111 SignedInt(ast
::IntTy
::Is
) => unreachable
!(),
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
{
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),
129 UnsignedInt(ast
::UintTy
::Us
) |
130 SignedInt(ast
::IntTy
::Is
) => unreachable
!(),
134 fn disr_wrap_incr(&self, val
: Option
<Disr
>) -> Disr
{
136 ($e
:expr
) => { ($e).wrapping_add(1) as Disr }
138 let val
= val
.unwrap_or(ty
::INITIAL_DISCRIMINANT_VALUE
);
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),
149 UnsignedInt(ast
::UintTy
::Us
) |
150 SignedInt(ast
::IntTy
::Is
) => unreachable
!(),
156 #[derive(Copy, Clone)]
157 pub enum CopyImplementationError
{
158 InfrigingField(Name
),
159 InfrigingVariant(Name
),
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.
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
{
179 impl<'a
, 'tcx
> ParameterEnvironment
<'a
, 'tcx
> {
180 pub fn can_type_implement_copy(&self, self_type
: Ty
<'tcx
>, span
: Span
)
181 -> Result
<(),CopyImplementationError
> {
184 // FIXME: (@jroesch) float this code up
185 let infcx
= infer
::new_infer_ctxt(tcx
, &tcx
.tables
, Some(self.clone()));
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(
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(
210 _
=> return Err(CopyImplementationError
::NotAnAdt
),
214 return Err(CopyImplementationError
::HasDestructor
)
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
)
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
)
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,
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
))
240 (&TyEnum(def
, substs
), Some(vid
)) => {
241 def
.variant_with_id(vid
).fields
.get(i
).map(|f
| f
.ty(self, substs
))
243 (&TyEnum(def
, substs
), None
) => {
244 assert
!(def
.is_univariant());
245 def
.variants
[0].fields
.get(i
).map(|f
| f
.ty(self, substs
))
247 (&TyTuple(ref v
), None
) => v
.get(i
).cloned(),
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,
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
))
262 (&TyEnum(def
, substs
), Some(vid
)) => {
263 def
.variant_with_id(vid
).find_field_named(n
).map(|f
| f
.ty(self, substs
))
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
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
280 // NB. Historically `fn enum_variants` generate i64 here, while
281 // rustc_typeck::check would generate isize.
282 _
=> SignedInt(ast
::IntTy
::Is
),
285 let repr_type_ty
= repr_type
.to_ty(self);
286 let repr_type
= match repr_type
{
287 SignedInt(ast
::IntTy
::Is
) =>
288 SignedInt(self.sess
.target
.int_type
),
289 UnsignedInt(ast
::UintTy
::Us
) =>
290 UnsignedInt(self.sess
.target
.uint_type
),
294 (repr_type
, repr_type_ty
)
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
),
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,
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
) {
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
);
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);
337 match const_eval
::eval_const_expr_partial(self, count_expr
, hint
, None
) {
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(),
344 span_err
!(self.sess
, count_expr
.span
, E0306
,
345 "expected positive integer for repeat count, found {}",
349 let err_msg
= match count_expr
.node
{
350 hir
::ExprPath(None
, hir
::Path
{
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())
361 span_err
!(self.sess
, count_expr
.span
, E0307
,
362 "expected constant integer for repeat count, {}", err_msg
);
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
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`.
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
>>)
388 debug
!("required_region_bounds(erased_self_ty={:?}, predicates={:?})",
392 assert
!(!erased_self_ty
.has_escaping_regions());
394 traits
::elaborate_predicates(self, predicates
)
395 .filter_map(|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(..) => {
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() {
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();
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) }
}
438 let region
= |state
: &mut SipHasher
, r
: ty
::Region
| {
441 ty
::ReLateBound(db
, ty
::BrAnon(i
)) => {
446 ty
::ReEarlyBound(..) |
447 ty
::ReLateBound(..) |
451 ty
::ReSkolemized(..) => {
452 tcx
.sess
.bug("unexpected region found when hashing a type")
456 let did
= |state
: &mut SipHasher
, did
: DefId
| {
457 let h
= if did
.is_local() {
460 tcx
.sess
.cstore
.crate_hash(did
.krate
)
462 h
.as_str().hash(state
);
463 did
.index
.hash(state
);
465 let mt
= |state
: &mut SipHasher
, mt
: TypeAndMut
| {
466 mt
.mutbl
.hash(state
);
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
);
517 TyBareFn(opt_def_id
, ref b
) => {
522 fn_sig(state
, &b
.sig
);
525 TyTrait(ref data
) => {
527 did(state
, data
.principal_def_id());
530 let principal
= tcx
.anonymize_late_bound_regions(&data
.principal
).0;
531 for subty
in &principal
.substs
.types
{
532 helper(tcx
, subty
, svh
, state
);
541 TyTuple(ref inner
) => {
549 hash
!(p
.name
.as_str());
551 TyInfer(_
) => unreachable
!(),
552 TyError
=> byte
!(21),
557 TyProjection(ref data
) => {
559 did(state
, data
.trait_ref
.def_id
);
560 hash
!(data
.item_name
.as_str());
568 /// Returns true if this ADT is a dtorck type.
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.
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).
580 pub fn is_adt_dtorck(&self, adt
: ty
::AdtDef
<'tcx
>) -> bool
{
581 let dtor_method
= match adt
.destructor() {
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.
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");
600 pub struct ImplMethod
<'tcx
> {
601 pub method
: Rc
<ty
::Method
<'tcx
>>,
602 pub substs
: Substs
<'tcx
>,
603 pub is_provided
: bool
606 impl<'tcx
> ty
::ctxt
<'tcx
> {
607 pub fn get_impl_method(&self,
609 substs
: Substs
<'tcx
>,
613 // there don't seem to be nicer accessors to these:
614 let impl_or_trait_items_map
= self.impl_or_trait_items
.borrow();
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
{
621 method
: meth
.clone(),
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
);
637 method
: meth
.clone(),
638 substs
: impl_to_trait_substs
.subst(self, &substs
),
645 self.sess
.bug(&format
!("method {:?} not found in {:?}",
650 impl<'tcx
> ty
::TyS
<'tcx
> {
651 fn impls_bound
<'a
>(&'tcx
self, param_env
: &ParameterEnvironment
<'a
,'tcx
>,
652 bound
: ty
::BuiltinBound
,
656 let tcx
= param_env
.tcx
;
657 let infcx
= infer
::new_infer_ctxt(tcx
, &tcx
.tables
, Some(param_env
.clone()));
659 let is_impld
= traits
::type_known_to_meet_builtin_bound(&infcx
,
662 debug
!("Ty::impls_bound({:?}, {:?}) = {:?}",
663 self, bound
, is_impld
);
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
);
675 assert
!(!self.needs_infer());
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
, ..
684 TyStr
| TyBox(..) | TyRef(_
, TypeAndMut
{
685 mutbl
: hir
::MutMutable
, ..
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
));
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
697 TypeFlags
::MOVENESS_CACHED
705 pub fn is_sized
<'a
>(&'tcx
self, param_env
: &ParameterEnvironment
<'a
,'tcx
>,
708 if self.flags
.get().intersects(TypeFlags
::SIZEDNESS_CACHED
) {
709 return self.flags
.get().intersects(TypeFlags
::IS_SIZED
);
712 self.is_sized_uncached(param_env
, span
)
715 fn is_sized_uncached
<'a
>(&'tcx
self, param_env
: &ParameterEnvironment
<'a
,'tcx
>,
716 span
: Span
) -> bool
{
717 assert
!(!self.needs_infer());
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),
725 TyStr
| TyTrait(..) | TySlice(_
) => Some(false),
727 TyEnum(..) | TyStruct(..) | TyProjection(..) | TyParam(..) |
728 TyInfer(..) | TyError
=> None
729 }.unwrap_or_else(|| self.impls_bound(param_env
, ty
::BoundSized
, span
));
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
735 TypeFlags
::SIZEDNESS_CACHED
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
{
747 // Iterate until something non-representable is found
748 fn find_nonrepresentable
<'tcx
, It
: Iterator
<Item
=Ty
<'tcx
>>>(cx
: &ty
::ctxt
<'tcx
>,
750 seen
: &mut Vec
<Ty
<'tcx
>>,
752 -> Representability
{
753 iter
.fold(Representability
::Representable
,
754 |r
, ty
| cmp
::max(r
, is_type_structurally_recursive(cx
, sp
, seen
, ty
)))
757 fn are_inner_types_recursive
<'tcx
>(cx
: &ty
::ctxt
<'tcx
>, sp
: Span
,
758 seen
: &mut Vec
<Ty
<'tcx
>>, ty
: Ty
<'tcx
>)
759 -> Representability
{
762 find_nonrepresentable(cx
, sp
, seen
, ts
.iter().cloned())
764 // Fixed-length vectors.
765 // FIXME(#11924) Behavior undecided for zero-length vectors.
767 is_type_structurally_recursive(cx
, sp
, seen
, ty
)
769 TyStruct(def
, substs
) | TyEnum(def
, substs
) => {
770 find_nonrepresentable(cx
,
773 def
.all_fields().map(|f
| f
.ty(cx
, substs
)))
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
))
780 _
=> Representability
::Representable
,
784 fn same_struct_or_enum
<'tcx
>(ty
: Ty
<'tcx
>, def
: ty
::AdtDef
<'tcx
>) -> bool
{
786 TyStruct(ty_def
, _
) | TyEnum(ty_def
, _
) => {
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
)) => {
801 let types_a
= substs_a
.types
.get_slice(subst
::TypeSpace
);
802 let types_b
= substs_b
.types
.get_slice(subst
::TypeSpace
);
804 let mut pairs
= types_a
.iter().zip(types_b
);
806 pairs
.all(|(&a
, &b
)| same_type(a
, b
))
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
>,
818 seen
: &mut Vec
<Ty
<'tcx
>>,
819 ty
: Ty
<'tcx
>) -> Representability
{
820 debug
!("is_type_structurally_recursive: {:?}", ty
);
823 TyStruct(def
, _
) | TyEnum(def
, _
) => {
825 // Iterate through stack of previously seen types.
826 let mut iter
= seen
.iter();
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:
834 // struct Bar<T> { x: Bar<Foo> }
837 Some(&seen_type
) => {
838 if same_struct_or_enum(seen_type
, def
) {
839 debug
!("SelfRecursive: {:?} contains {:?}",
842 return Representability
::SelfRecursive
;
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.
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:
856 // struct Foo { Option<Option<Foo>> }
858 for &seen_type
in iter
{
859 if same_type(ty
, seen_type
) {
860 debug
!("ContainsRecursive: {:?} contains {:?}",
863 return Representability
::ContainsRecursive
;
868 // For structs and enums, track all previously seen types by pushing them
869 // onto the 'seen' stack.
871 let out
= are_inner_types_recursive(cx
, sp
, seen
, ty
);
876 // No need to push in other cases.
877 are_inner_types_recursive(cx
, sp
, seen
, ty
)
882 debug
!("is_type_representable: {:?}", self);
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
);