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