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