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) {
 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.get_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, i.e. whether it being
 570     /// safe for destruction requires it to be alive
 571     pub fn is_adt_dtorck(&self, adt: ty::AdtDef<'tcx>) -> bool {
 572         let dtor_method = match adt.destructor() {
 573             Some(dtor) => dtor,
 574             None => return false
 575         };
 576         let impl_did = self.impl_of_method(dtor_method).unwrap_or_else(|| {
 577             self.sess.bug(&format!("no Drop impl for the dtor of `{:?}`", adt))
 578         });
 579         let generics = adt.type_scheme(self).generics;
 580
 581         // In `impl<'a> Drop ...`, we automatically assume
 582         // `'a` is meaningful and thus represents a bound
 583         // through which we could reach borrowed data.
 584         //
 585         // FIXME (pnkfelix): In the future it would be good to
 586         // extend the language to allow the user to express,
 587         // in the impl signature, that a lifetime is not
 588         // actually used (something like `where 'a: ?Live`).
 589         if generics.has_region_params(subst::TypeSpace) {
 590             debug!("typ: {:?} has interesting dtor due to region params",
 591                    adt);
 592             return true;
 593         }
 594
 595         let mut seen_items = Vec::new();
 596         let mut items_to_inspect = vec![impl_did];
 597         while let Some(item_def_id) = items_to_inspect.pop() {
 598             if seen_items.contains(&item_def_id) {
 599                 continue;
 600             }
 601
 602             for pred in self.lookup_predicates(item_def_id).predicates {
 603                 let result = match pred {
 604                     ty::Predicate::Equate(..) |
 605                     ty::Predicate::RegionOutlives(..) |
 606                     ty::Predicate::TypeOutlives(..) |
 607                     ty::Predicate::WellFormed(..) |
 608                     ty::Predicate::ObjectSafe(..) |
 609                     ty::Predicate::Projection(..) => {
 610                         // For now, assume all these where-clauses
 611                         // may give drop implementation capabilty
 612                         // to access borrowed data.
 613                         true
 614                     }
 615
 616                     ty::Predicate::Trait(ty::Binder(ref t_pred)) => {
 617                         let def_id = t_pred.trait_ref.def_id;
 618                         if self.trait_items(def_id).len() != 0 {
 619                             // If trait has items, assume it adds
 620                             // capability to access borrowed data.
 621                             true
 622                         } else {
 623                             // Trait without items is itself
 624                             // uninteresting from POV of dropck.
 625                             //
 626                             // However, may have parent w/ items;
 627                             // so schedule checking of predicates,
 628                             items_to_inspect.push(def_id);
 629                             // and say "no capability found" for now.
 630                             false
 631                         }
 632                     }
 633                 };
 634
 635                 if result {
 636                     debug!("typ: {:?} has interesting dtor due to generic preds, e.g. {:?}",
 637                            adt, pred);
 638                     return true;
 639                 }
 640             }
 641
 642             seen_items.push(item_def_id);
 643         }
 644
 645         debug!("typ: {:?} is dtorck-safe", adt);
 646         false
 647     }
 648 }
 649
 650 #[derive(Debug)]
 651 pub struct ImplMethod<'tcx> {
 652     pub method: Rc<ty::Method<'tcx>>,
 653     pub substs: Substs<'tcx>,
 654     pub is_provided: bool
 655 }
 656
 657 impl<'tcx> ty::ctxt<'tcx> {
 658     #[inline(never)] // is this perfy enough?
 659     pub fn get_impl_method(&self,
 660                            impl_def_id: DefId,
 661                            substs: Substs<'tcx>,
 662                            name: Name)
 663                            -> ImplMethod<'tcx>
 664     {
 665         // there don't seem to be nicer accessors to these:
 666         let impl_or_trait_items_map = self.impl_or_trait_items.borrow();
 667
 668         for impl_item in &self.impl_items.borrow()[&impl_def_id] {
 669             if let ty::MethodTraitItem(ref meth) =
 670                 impl_or_trait_items_map[&impl_item.def_id()] {
 671                 if meth.name == name {
 672                     return ImplMethod {
 673                         method: meth.clone(),
 674                         substs: substs,
 675                         is_provided: false
 676                     }
 677                 }
 678             }
 679         }
 680
 681         // It is not in the impl - get the default from the trait.
 682         let trait_ref = self.impl_trait_ref(impl_def_id).unwrap();
 683         for trait_item in self.trait_items(trait_ref.def_id).iter() {
 684             if let &ty::MethodTraitItem(ref meth) = trait_item {
 685                 if meth.name == name {
 686                     let impl_to_trait_substs = self
 687                         .make_substs_for_receiver_types(&trait_ref, meth);
 688                     return ImplMethod {
 689                         method: meth.clone(),
 690                         substs: impl_to_trait_substs.subst(self, &substs),
 691                         is_provided: true
 692                     }
 693                 }
 694             }
 695         }
 696
 697         self.sess.bug(&format!("method {:?} not found in {:?}",
 698                                name, impl_def_id))
 699     }
 700 }
 701
 702 impl<'tcx> ty::TyS<'tcx> {
 703     fn impls_bound<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 704                        bound: ty::BuiltinBound,
 705                        span: Span)
 706                        -> bool
 707     {
 708         let tcx = param_env.tcx;
 709         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env.clone()), false);
 710
 711         let is_impld = traits::type_known_to_meet_builtin_bound(&infcx,
 712                                                                 self, bound, span);
 713
 714         debug!("Ty::impls_bound({:?}, {:?}) = {:?}",
 715                self, bound, is_impld);
 716
 717         is_impld
 718     }
 719
 720     // FIXME (@jroesch): I made this public to use it, not sure if should be private
 721     pub fn moves_by_default<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 722                            span: Span) -> bool {
 723         if self.flags.get().intersects(TypeFlags::MOVENESS_CACHED) {
 724             return self.flags.get().intersects(TypeFlags::MOVES_BY_DEFAULT);
 725         }
 726
 727         assert!(!self.needs_infer());
 728
 729         // Fast-path for primitive types
 730         let result = match self.sty {
 731             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
 732             TyRawPtr(..) | TyBareFn(..) | TyRef(_, TypeAndMut {
 733                 mutbl: hir::MutImmutable, ..
 734             }) => Some(false),
 735
 736             TyStr | TyBox(..) | TyRef(_, TypeAndMut {
 737                 mutbl: hir::MutMutable, ..
 738             }) => Some(true),
 739
 740             TyArray(..) | TySlice(_) | TyTrait(..) | TyTuple(..) |
 741             TyClosure(..) | TyEnum(..) | TyStruct(..) |
 742             TyProjection(..) | TyParam(..) | TyInfer(..) | TyError => None
 743         }.unwrap_or_else(|| !self.impls_bound(param_env, ty::BoundCopy, span));
 744
 745         if !self.has_param_types() && !self.has_self_ty() {
 746             self.flags.set(self.flags.get() | if result {
 747                 TypeFlags::MOVENESS_CACHED | TypeFlags::MOVES_BY_DEFAULT
 748             } else {
 749                 TypeFlags::MOVENESS_CACHED
 750             });
 751         }
 752
 753         result
 754     }
 755
 756     #[inline]
 757     pub fn is_sized<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 758                         span: Span) -> bool
 759     {
 760         if self.flags.get().intersects(TypeFlags::SIZEDNESS_CACHED) {
 761             return self.flags.get().intersects(TypeFlags::IS_SIZED);
 762         }
 763
 764         self.is_sized_uncached(param_env, span)
 765     }
 766
 767     fn is_sized_uncached<'a>(&'tcx self, param_env: &ParameterEnvironment<'a,'tcx>,
 768                              span: Span) -> bool {
 769         assert!(!self.needs_infer());
 770
 771         // Fast-path for primitive types
 772         let result = match self.sty {
 773             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
 774             TyBox(..) | TyRawPtr(..) | TyRef(..) | TyBareFn(..) |
 775             TyArray(..) | TyTuple(..) | TyClosure(..) => Some(true),
 776
 777             TyStr | TyTrait(..) | TySlice(_) => Some(false),
 778
 779             TyEnum(..) | TyStruct(..) | TyProjection(..) | TyParam(..) |
 780             TyInfer(..) | TyError => None
 781         }.unwrap_or_else(|| self.impls_bound(param_env, ty::BoundSized, span));
 782
 783         if !self.has_param_types() && !self.has_self_ty() {
 784             self.flags.set(self.flags.get() | if result {
 785                 TypeFlags::SIZEDNESS_CACHED | TypeFlags::IS_SIZED
 786             } else {
 787                 TypeFlags::SIZEDNESS_CACHED
 788             });
 789         }
 790
 791         result
 792     }
 793
 794
 795     /// Check whether a type is representable. This means it cannot contain unboxed
 796     /// structural recursion. This check is needed for structs and enums.
 797     pub fn is_representable(&'tcx self, cx: &ty::ctxt<'tcx>, sp: Span) -> Representability {
 798
 799         // Iterate until something non-representable is found
 800         fn find_nonrepresentable<'tcx, It: Iterator<Item=Ty<'tcx>>>(cx: &ty::ctxt<'tcx>,
 801                                                                     sp: Span,
 802                                                                     seen: &mut Vec<Ty<'tcx>>,
 803                                                                     iter: It)
 804                                                                     -> Representability {
 805             iter.fold(Representability::Representable,
 806                       |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty)))
 807         }
 808
 809         fn are_inner_types_recursive<'tcx>(cx: &ty::ctxt<'tcx>, sp: Span,
 810                                            seen: &mut Vec<Ty<'tcx>>, ty: Ty<'tcx>)
 811                                            -> Representability {
 812             match ty.sty {
 813                 TyTuple(ref ts) => {
 814                     find_nonrepresentable(cx, sp, seen, ts.iter().cloned())
 815                 }
 816                 // Fixed-length vectors.
 817                 // FIXME(#11924) Behavior undecided for zero-length vectors.
 818                 TyArray(ty, _) => {
 819                     is_type_structurally_recursive(cx, sp, seen, ty)
 820                 }
 821                 TyStruct(def, substs) | TyEnum(def, substs) => {
 822                     find_nonrepresentable(cx,
 823                                           sp,
 824                                           seen,
 825                                           def.all_fields().map(|f| f.ty(cx, substs)))
 826                 }
 827                 TyClosure(..) => {
 828                     // this check is run on type definitions, so we don't expect
 829                     // to see closure types
 830                     cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty))
 831                 }
 832                 _ => Representability::Representable,
 833             }
 834         }
 835
 836         fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool {
 837             match ty.sty {
 838                 TyStruct(ty_def, _) | TyEnum(ty_def, _) => {
 839                      ty_def == def
 840                 }
 841                 _ => false
 842             }
 843         }
 844
 845         fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 846             match (&a.sty, &b.sty) {
 847                 (&TyStruct(did_a, ref substs_a), &TyStruct(did_b, ref substs_b)) |
 848                 (&TyEnum(did_a, ref substs_a), &TyEnum(did_b, ref substs_b)) => {
 849                     if did_a != did_b {
 850                         return false;
 851                     }
 852
 853                     let types_a = substs_a.types.get_slice(subst::TypeSpace);
 854                     let types_b = substs_b.types.get_slice(subst::TypeSpace);
 855
 856                     let mut pairs = types_a.iter().zip(types_b);
 857
 858                     pairs.all(|(&a, &b)| same_type(a, b))
 859                 }
 860                 _ => {
 861                     a == b
 862                 }
 863             }
 864         }
 865
 866         // Does the type `ty` directly (without indirection through a pointer)
 867         // contain any types on stack `seen`?
 868         fn is_type_structurally_recursive<'tcx>(cx: &ty::ctxt<'tcx>,
 869                                                 sp: Span,
 870                                                 seen: &mut Vec<Ty<'tcx>>,
 871                                                 ty: Ty<'tcx>) -> Representability {
 872             debug!("is_type_structurally_recursive: {:?}", ty);
 873
 874             match ty.sty {
 875                 TyStruct(def, _) | TyEnum(def, _) => {
 876                     {
 877                         // Iterate through stack of previously seen types.
 878                         let mut iter = seen.iter();
 879
 880                         // The first item in `seen` is the type we are actually curious about.
 881                         // We want to return SelfRecursive if this type contains itself.
 882                         // It is important that we DON'T take generic parameters into account
 883                         // for this check, so that Bar<T> in this example counts as SelfRecursive:
 884                         //
 885                         // struct Foo;
 886                         // struct Bar<T> { x: Bar<Foo> }
 887
 888                         match iter.next() {
 889                             Some(&seen_type) => {
 890                                 if same_struct_or_enum(seen_type, def) {
 891                                     debug!("SelfRecursive: {:?} contains {:?}",
 892                                            seen_type,
 893                                            ty);
 894                                     return Representability::SelfRecursive;
 895                                 }
 896                             }
 897                             None => {}
 898                         }
 899
 900                         // We also need to know whether the first item contains other types
 901                         // that are structurally recursive. If we don't catch this case, we
 902                         // will recurse infinitely for some inputs.
 903                         //
 904                         // It is important that we DO take generic parameters into account
 905                         // here, so that code like this is considered SelfRecursive, not
 906                         // ContainsRecursive:
 907                         //
 908                         // struct Foo { Option<Option<Foo>> }
 909
 910                         for &seen_type in iter {
 911                             if same_type(ty, seen_type) {
 912                                 debug!("ContainsRecursive: {:?} contains {:?}",
 913                                        seen_type,
 914                                        ty);
 915                                 return Representability::ContainsRecursive;
 916                             }
 917                         }
 918                     }
 919
 920                     // For structs and enums, track all previously seen types by pushing them
 921                     // onto the 'seen' stack.
 922                     seen.push(ty);
 923                     let out = are_inner_types_recursive(cx, sp, seen, ty);
 924                     seen.pop();
 925                     out
 926                 }
 927                 _ => {
 928                     // No need to push in other cases.
 929                     are_inner_types_recursive(cx, sp, seen, ty)
 930                 }
 931             }
 932         }
 933
 934         debug!("is_type_representable: {:?}", self);
 935
 936         // To avoid a stack overflow when checking an enum variant or struct that
 937         // contains a different, structurally recursive type, maintain a stack
 938         // of seen types and check recursion for each of them (issues #3008, #3779).
 939         let mut seen: Vec<Ty> = Vec::new();
 940         let r = is_type_structurally_recursive(cx, sp, &mut seen, self);
 941         debug!("is_type_representable: {:?} is {:?}", self, r);
 942         r
 943     }
 944 }