src/librustc/middle/ty/util.rs

   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;
  17 use middle::subst;
  18 use middle::infer;
  19 use middle::pat_util;
  20 use middle::traits;
  21 use middle::ty::{self, Ty, TypeAndMut, TypeFlags};
  22 use middle::ty::{Disr, ParameterEnvironment};
  23 use middle::ty::{HasTypeFlags, RegionEscape};
  24 use middle::ty::TypeVariants::*;
  25 use util::num::ToPrimitive;
  26
  27 use std::cmp;
  28 use std::hash::{Hash, SipHasher, Hasher};
  29 use syntax::ast::Name;
  30 use syntax::codemap::Span;
  31
  32 use rustc_front::hir;
  33 use rustc_front::attr::{self, AttrMetaMethods, SignedInt, UnsignedInt};
  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 {
  47             SignedInt(hir::TyI8)      => cx.types.i8,
  48             SignedInt(hir::TyI16)     => cx.types.i16,
  49             SignedInt(hir::TyI32)     => cx.types.i32,
  50             SignedInt(hir::TyI64)     => cx.types.i64,
  51             SignedInt(hir::TyIs)   => cx.types.isize,
  52             UnsignedInt(hir::TyU8)    => cx.types.u8,
  53             UnsignedInt(hir::TyU16)   => cx.types.u16,
  54             UnsignedInt(hir::TyU32)   => cx.types.u32,
  55             UnsignedInt(hir::TyU64)   => cx.types.u64,
  56             UnsignedInt(hir::TyUs) => cx.types.usize,
  57         }
  58     }
  59
  60     fn i64_to_disr(&self, val: i64) -> Option<Disr> {
  61         match *self {
  62             SignedInt(hir::TyI8)    => val.to_i8()  .map(|v| v as Disr),
  63             SignedInt(hir::TyI16)   => val.to_i16() .map(|v| v as Disr),
  64             SignedInt(hir::TyI32)   => val.to_i32() .map(|v| v as Disr),
  65             SignedInt(hir::TyI64)   => val.to_i64() .map(|v| v as Disr),
  66             UnsignedInt(hir::TyU8)  => val.to_u8()  .map(|v| v as Disr),
  67             UnsignedInt(hir::TyU16) => val.to_u16() .map(|v| v as Disr),
  68             UnsignedInt(hir::TyU32) => val.to_u32() .map(|v| v as Disr),
  69             UnsignedInt(hir::TyU64) => val.to_u64() .map(|v| v as Disr),
  70
  71             UnsignedInt(hir::TyUs) |
  72             SignedInt(hir::TyIs) => unreachable!(),
  73         }
  74     }
  75
  76     fn u64_to_disr(&self, val: u64) -> Option<Disr> {
  77         match *self {
  78             SignedInt(hir::TyI8)    => val.to_i8()  .map(|v| v as Disr),
  79             SignedInt(hir::TyI16)   => val.to_i16() .map(|v| v as Disr),
  80             SignedInt(hir::TyI32)   => val.to_i32() .map(|v| v as Disr),
  81             SignedInt(hir::TyI64)   => val.to_i64() .map(|v| v as Disr),
  82             UnsignedInt(hir::TyU8)  => val.to_u8()  .map(|v| v as Disr),
  83             UnsignedInt(hir::TyU16) => val.to_u16() .map(|v| v as Disr),
  84             UnsignedInt(hir::TyU32) => val.to_u32() .map(|v| v as Disr),
  85             UnsignedInt(hir::TyU64) => val.to_u64() .map(|v| v as Disr),
  86
  87             UnsignedInt(hir::TyUs) |
  88             SignedInt(hir::TyIs) => unreachable!(),
  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.
 100             SignedInt(hir::TyI8)    => add1!((val as i64).to_i8()),
 101             SignedInt(hir::TyI16)   => add1!((val as i64).to_i16()),
 102             SignedInt(hir::TyI32)   => add1!((val as i64).to_i32()),
 103             SignedInt(hir::TyI64)   => add1!(Some(val as i64)),
 104
 105             UnsignedInt(hir::TyU8)  => add1!(val.to_u8()),
 106             UnsignedInt(hir::TyU16) => add1!(val.to_u16()),
 107             UnsignedInt(hir::TyU32) => add1!(val.to_u32()),
 108             UnsignedInt(hir::TyU64) => add1!(Some(val)),
 109
 110             UnsignedInt(hir::TyUs) |
 111             SignedInt(hir::TyIs) => unreachable!(),
 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 {
 120             SignedInt(hir::TyI8)    => format!("{}", val as i8 ),
 121             SignedInt(hir::TyI16)   => format!("{}", val as i16),
 122             SignedInt(hir::TyI32)   => format!("{}", val as i32),
 123             SignedInt(hir::TyI64)   => format!("{}", val as i64),
 124             UnsignedInt(hir::TyU8)  => format!("{}", val as u8 ),
 125             UnsignedInt(hir::TyU16) => format!("{}", val as u16),
 126             UnsignedInt(hir::TyU32) => format!("{}", val as u32),
 127             UnsignedInt(hir::TyU64) => format!("{}", val as u64),
 128
 129             UnsignedInt(hir::TyUs) |
 130             SignedInt(hir::TyIs) => unreachable!(),
 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 {
 140             SignedInt(hir::TyI8)    => add1!(val as i8 ),
 141             SignedInt(hir::TyI16)   => add1!(val as i16),
 142             SignedInt(hir::TyI32)   => add1!(val as i32),
 143             SignedInt(hir::TyI64)   => add1!(val as i64),
 144             UnsignedInt(hir::TyU8)  => add1!(val as u8 ),
 145             UnsignedInt(hir::TyU16) => add1!(val as u16),
 146             UnsignedInt(hir::TyU32) => add1!(val as u32),
 147             UnsignedInt(hir::TyU64) => add1!(val as u64),
 148
 149             UnsignedInt(hir::TyUs) |
 150             SignedInt(hir::TyIs) => unreachable!(),
 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
 185         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(self.clone()), false);
 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.
 282             _ => SignedInt(hir::TyIs),
 283         };
 284
 285         let repr_type_ty = repr_type.to_ty(self);
 286         let repr_type = match repr_type {
 287             SignedInt(hir::TyIs) =>
 288                 SignedInt(self.sess.target.int_type),
 289             UnsignedInt(hir::TyUs) =>
 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);
 337         match const_eval::eval_const_expr_partial(self, count_expr, hint) {
 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 {
 460                     tcx.sess.cstore.get_crate_hash(did.krate)
 461                 };
 462                 h.as_str().hash(state);
 463                 did.node.hash(state);
 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
 568     /// Returns true if this ADT is a dtorck type, i.e. whether it being
 569     /// safe for destruction requires it to be alive
 570     pub fn is_adt_dtorck(&self, adt: ty::AdtDef<'tcx>) -> bool {
 571         let dtor_method = match adt.destructor() {
 572             Some(dtor) => dtor,
 573             None => return false
 574         };
 575         let impl_did = self.impl_of_method(dtor_method).unwrap_or_else(|| {
 576             self.sess.bug(&format!("no Drop impl for the dtor of `{:?}`", adt))
 577         });
 578         let generics = adt.type_scheme(self).generics;
 579
 580         // In `impl<'a> Drop ...`, we automatically assume
 581         // `'a` is meaningful and thus represents a bound
 582         // through which we could reach borrowed data.
 583         //
 584         // FIXME (pnkfelix): In the future it would be good to
 585         // extend the language to allow the user to express,
 586         // in the impl signature, that a lifetime is not
 587         // actually used (something like `where 'a: ?Live`).
 588         if generics.has_region_params(subst::TypeSpace) {
 589             debug!("typ: {:?} has interesting dtor due to region params",
 590                    adt);
 591             return true;
 592         }
 593
 594         let mut seen_items = Vec::new();
 595         let mut items_to_inspect = vec![impl_did];
 596         while let Some(item_def_id) = items_to_inspect.pop() {
 597             if seen_items.contains(&item_def_id) {
 598                 continue;
 599             }
 600
 601             for pred in self.lookup_predicates(item_def_id).predicates {
 602                 let result = match pred {
 603                     ty::Predicate::Equate(..) |
 604                     ty::Predicate::RegionOutlives(..) |
 605                     ty::Predicate::TypeOutlives(..) |
 606                     ty::Predicate::WellFormed(..) |
 607                     ty::Predicate::ObjectSafe(..) |
 608                     ty::Predicate::Projection(..) => {
 609                         // For now, assume all these where-clauses
 610                         // may give drop implementation capabilty
 611                         // to access borrowed data.
 612                         true
 613                     }
 614
 615                     ty::Predicate::Trait(ty::Binder(ref t_pred)) => {
 616                         let def_id = t_pred.trait_ref.def_id;
 617                         if self.trait_items(def_id).len() != 0 {
 618                             // If trait has items, assume it adds
 619                             // capability to access borrowed data.
 620                             true
 621                         } else {
 622                             // Trait without items is itself
 623                             // uninteresting from POV of dropck.
 624                             //
 625                             // However, may have parent w/ items;
 626                             // so schedule checking of predicates,
 627                             items_to_inspect.push(def_id);
 628                             // and say "no capability found" for now.
 629                             false
 630                         }
 631                     }
 632                 };
 633
 634                 if result {
 635                     debug!("typ: {:?} has interesting dtor due to generic preds, e.g. {:?}",
 636                            adt, pred);
 637                     return true;
 638                 }
 639             }
 640
 641             seen_items.push(item_def_id);
 642         }
 643
 644         debug!("typ: {:?} is dtorck-safe", adt);
 645         false
 646     }
 647 }
 648
 649 impl<'tcx> ty::TyS<'tcx> {
 650     fn impls_bound<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 651                        bound: ty::BuiltinBound,
 652                        span: Span)
 653                        -> bool
 654     {
 655         let tcx = param_env.tcx;
 656         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env.clone()), false);
 657
 658         let is_impld = traits::type_known_to_meet_builtin_bound(&infcx,
 659                                                                 self, bound, span);
 660
 661         debug!("Ty::impls_bound({:?}, {:?}) = {:?}",
 662                self, bound, is_impld);
 663
 664         is_impld
 665     }
 666
 667     // FIXME (@jroesch): I made this public to use it, not sure if should be private
 668     pub fn moves_by_default<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 669                            span: Span) -> bool {
 670         if self.flags.get().intersects(TypeFlags::MOVENESS_CACHED) {
 671             return self.flags.get().intersects(TypeFlags::MOVES_BY_DEFAULT);
 672         }
 673
 674         assert!(!self.needs_infer());
 675
 676         // Fast-path for primitive types
 677         let result = match self.sty {
 678             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
 679             TyRawPtr(..) | TyBareFn(..) | TyRef(_, TypeAndMut {
 680                 mutbl: hir::MutImmutable, ..
 681             }) => Some(false),
 682
 683             TyStr | TyBox(..) | TyRef(_, TypeAndMut {
 684                 mutbl: hir::MutMutable, ..
 685             }) => Some(true),
 686
 687             TyArray(..) | TySlice(_) | TyTrait(..) | TyTuple(..) |
 688             TyClosure(..) | TyEnum(..) | TyStruct(..) |
 689             TyProjection(..) | TyParam(..) | TyInfer(..) | TyError => None
 690         }.unwrap_or_else(|| !self.impls_bound(param_env, ty::BoundCopy, span));
 691
 692         if !self.has_param_types() && !self.has_self_ty() {
 693             self.flags.set(self.flags.get() | if result {
 694                 TypeFlags::MOVENESS_CACHED | TypeFlags::MOVES_BY_DEFAULT
 695             } else {
 696                 TypeFlags::MOVENESS_CACHED
 697             });
 698         }
 699
 700         result
 701     }
 702
 703     #[inline]
 704     pub fn is_sized<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 705                         span: Span) -> bool
 706     {
 707         if self.flags.get().intersects(TypeFlags::SIZEDNESS_CACHED) {
 708             return self.flags.get().intersects(TypeFlags::IS_SIZED);
 709         }
 710
 711         self.is_sized_uncached(param_env, span)
 712     }
 713
 714     fn is_sized_uncached<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 715                              span: Span) -> bool {
 716         assert!(!self.needs_infer());
 717
 718         // Fast-path for primitive types
 719         let result = match self.sty {
 720             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
 721             TyBox(..) | TyRawPtr(..) | TyRef(..) | TyBareFn(..) |
 722             TyArray(..) | TyTuple(..) | TyClosure(..) => Some(true),
 723
 724             TyStr | TyTrait(..) | TySlice(_) => Some(false),
 725
 726             TyEnum(..) | TyStruct(..) | TyProjection(..) | TyParam(..) |
 727             TyInfer(..) | TyError => None
 728         }.unwrap_or_else(|| self.impls_bound(param_env, ty::BoundSized, span));
 729
 730         if !self.has_param_types() && !self.has_self_ty() {
 731             self.flags.set(self.flags.get() | if result {
 732                 TypeFlags::SIZEDNESS_CACHED | TypeFlags::IS_SIZED
 733             } else {
 734                 TypeFlags::SIZEDNESS_CACHED
 735             });
 736         }
 737
 738         result
 739     }
 740
 741
 742     /// Check whether a type is representable. This means it cannot contain unboxed
 743     /// structural recursion. This check is needed for structs and enums.
 744     pub fn is_representable(&'tcx self, cx: &ty::ctxt<'tcx>, sp: Span) -> Representability {
 745
 746         // Iterate until something non-representable is found
 747         fn find_nonrepresentable<'tcx, It: Iterator<Item=Ty<'tcx>>>(cx: &ty::ctxt<'tcx>,
 748                                                                     sp: Span,
 749                                                                     seen: &mut Vec<Ty<'tcx>>,
 750                                                                     iter: It)
 751                                                                     -> Representability {
 752             iter.fold(Representability::Representable,
 753                       |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty)))
 754         }
 755
 756         fn are_inner_types_recursive<'tcx>(cx: &ty::ctxt<'tcx>, sp: Span,
 757                                            seen: &mut Vec<Ty<'tcx>>, ty: Ty<'tcx>)
 758                                            -> Representability {
 759             match ty.sty {
 760                 TyTuple(ref ts) => {
 761                     find_nonrepresentable(cx, sp, seen, ts.iter().cloned())
 762                 }
 763                 // Fixed-length vectors.
 764                 // FIXME(#11924) Behavior undecided for zero-length vectors.
 765                 TyArray(ty, _) => {
 766                     is_type_structurally_recursive(cx, sp, seen, ty)
 767                 }
 768                 TyStruct(def, substs) | TyEnum(def, substs) => {
 769                     find_nonrepresentable(cx,
 770                                           sp,
 771                                           seen,
 772                                           def.all_fields().map(|f| f.ty(cx, substs)))
 773                 }
 774                 TyClosure(..) => {
 775                     // this check is run on type definitions, so we don't expect
 776                     // to see closure types
 777                     cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty))
 778                 }
 779                 _ => Representability::Representable,
 780             }
 781         }
 782
 783         fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool {
 784             match ty.sty {
 785                 TyStruct(ty_def, _) | TyEnum(ty_def, _) => {
 786                      ty_def == def
 787                 }
 788                 _ => false
 789             }
 790         }
 791
 792         fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 793             match (&a.sty, &b.sty) {
 794                 (&TyStruct(did_a, ref substs_a), &TyStruct(did_b, ref substs_b)) |
 795                 (&TyEnum(did_a, ref substs_a), &TyEnum(did_b, ref substs_b)) => {
 796                     if did_a != did_b {
 797                         return false;
 798                     }
 799
 800                     let types_a = substs_a.types.get_slice(subst::TypeSpace);
 801                     let types_b = substs_b.types.get_slice(subst::TypeSpace);
 802
 803                     let mut pairs = types_a.iter().zip(types_b);
 804
 805                     pairs.all(|(&a, &b)| same_type(a, b))
 806                 }
 807                 _ => {
 808                     a == b
 809                 }
 810             }
 811         }
 812
 813         // Does the type `ty` directly (without indirection through a pointer)
 814         // contain any types on stack `seen`?
 815         fn is_type_structurally_recursive<'tcx>(cx: &ty::ctxt<'tcx>,
 816                                                 sp: Span,
 817                                                 seen: &mut Vec<Ty<'tcx>>,
 818                                                 ty: Ty<'tcx>) -> Representability {
 819             debug!("is_type_structurally_recursive: {:?}", ty);
 820
 821             match ty.sty {
 822                 TyStruct(def, _) | TyEnum(def, _) => {
 823                     {
 824                         // Iterate through stack of previously seen types.
 825                         let mut iter = seen.iter();
 826
 827                         // The first item in `seen` is the type we are actually curious about.
 828                         // We want to return SelfRecursive if this type contains itself.
 829                         // It is important that we DON'T take generic parameters into account
 830                         // for this check, so that Bar<T> in this example counts as SelfRecursive:
 831                         //
 832                         // struct Foo;
 833                         // struct Bar<T> { x: Bar<Foo> }
 834
 835                         match iter.next() {
 836                             Some(&seen_type) => {
 837                                 if same_struct_or_enum(seen_type, def) {
 838                                     debug!("SelfRecursive: {:?} contains {:?}",
 839                                            seen_type,
 840                                            ty);
 841                                     return Representability::SelfRecursive;
 842                                 }
 843                             }
 844                             None => {}
 845                         }
 846
 847                         // We also need to know whether the first item contains other types
 848                         // that are structurally recursive. If we don't catch this case, we
 849                         // will recurse infinitely for some inputs.
 850                         //
 851                         // It is important that we DO take generic parameters into account
 852                         // here, so that code like this is considered SelfRecursive, not
 853                         // ContainsRecursive:
 854                         //
 855                         // struct Foo { Option<Option<Foo>> }
 856
 857                         for &seen_type in iter {
 858                             if same_type(ty, seen_type) {
 859                                 debug!("ContainsRecursive: {:?} contains {:?}",
 860                                        seen_type,
 861                                        ty);
 862                                 return Representability::ContainsRecursive;
 863                             }
 864                         }
 865                     }
 866
 867                     // For structs and enums, track all previously seen types by pushing them
 868                     // onto the 'seen' stack.
 869                     seen.push(ty);
 870                     let out = are_inner_types_recursive(cx, sp, seen, ty);
 871                     seen.pop();
 872                     out
 873                 }
 874                 _ => {
 875                     // No need to push in other cases.
 876                     are_inner_types_recursive(cx, sp, seen, ty)
 877                 }
 878             }
 879         }
 880
 881         debug!("is_type_representable: {:?}", self);
 882
 883         // To avoid a stack overflow when checking an enum variant or struct that
 884         // contains a different, structurally recursive type, maintain a stack
 885         // of seen types and check recursion for each of them (issues #3008, #3779).
 886         let mut seen: Vec<Ty> = Vec::new();
 887         let r = is_type_structurally_recursive(cx, sp, &mut seen, self);
 888         debug!("is_type_representable: {:?} is {:?}", self, r);
 889         r
 890     }
 891 }