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