src/librustc/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 hir::def::Def;
  14 use hir::def_id::DefId;
  15 use hir::map::{DefPathData, Node};
  16 use hir;
  17 use ich::NodeIdHashingMode;
  18 use middle::const_val::ConstVal;
  19 use traits;
  20 use ty::{self, Ty, TyCtxt, TypeFoldable};
  21 use ty::fold::TypeVisitor;
  22 use ty::subst::UnpackedKind;
  23 use ty::maps::TyCtxtAt;
  24 use ty::TypeVariants::*;
  25 use ty::layout::{Integer, IntegerExt};
  26 use util::common::ErrorReported;
  27 use middle::lang_items;
  28 use mir::interpret::{Value, PrimVal};
  29
  30 use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
  31                                            HashStable};
  32 use rustc_data_structures::fx::FxHashMap;
  33 use std::{cmp, fmt};
  34 use std::hash::Hash;
  35 use std::intrinsics;
  36 use syntax::ast;
  37 use syntax::attr::{self, SignedInt, UnsignedInt};
  38 use syntax_pos::{Span, DUMMY_SP};
  39
  40 #[derive(Copy, Clone, Debug)]
  41 pub struct Discr<'tcx> {
  42     /// bit representation of the discriminant, so `-128i8` is `0xFF_u128`
  43     pub val: u128,
  44     pub ty: Ty<'tcx>
  45 }
  46
  47 impl<'tcx> fmt::Display for Discr<'tcx> {
  48     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
  49         match self.ty.sty {
  50             ty::TyInt(ity) => {
  51                 let bits = ty::tls::with(|tcx| {
  52                     Integer::from_attr(tcx, SignedInt(ity)).size().bits()
  53                 });
  54                 let x = self.val as i128;
  55                 // sign extend the raw representation to be an i128
  56                 let x = (x << (128 - bits)) >> (128 - bits);
  57                 write!(fmt, "{}", x)
  58             },
  59             _ => write!(fmt, "{}", self.val),
  60         }
  61     }
  62 }
  63
  64 impl<'tcx> Discr<'tcx> {
  65     /// Adds 1 to the value and wraps around if the maximum for the type is reached
  66     pub fn wrap_incr<'a, 'gcx>(self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Self {
  67         self.checked_add(tcx, 1).0
  68     }
  69     pub fn checked_add<'a, 'gcx>(self, tcx: TyCtxt<'a, 'gcx, 'tcx>, n: u128) -> (Self, bool) {
  70         let (int, signed) = match self.ty.sty {
  71             TyInt(ity) => (Integer::from_attr(tcx, SignedInt(ity)), true),
  72             TyUint(uty) => (Integer::from_attr(tcx, UnsignedInt(uty)), false),
  73             _ => bug!("non integer discriminant"),
  74         };
  75
  76         let bit_size = int.size().bits();
  77         let amt = 128 - bit_size;
  78         if signed {
  79             let sext = |u| {
  80                 let i = u as i128;
  81                 (i << amt) >> amt
  82             };
  83             let min = sext(1_u128 << (bit_size - 1));
  84             let max = i128::max_value() >> amt;
  85             let val = sext(self.val);
  86             assert!(n < (i128::max_value() as u128));
  87             let n = n as i128;
  88             let oflo = val > max - n;
  89             let val = if oflo {
  90                 min + (n - (max - val) - 1)
  91             } else {
  92                 val + n
  93             };
  94             // zero the upper bits
  95             let val = val as u128;
  96             let val = (val << amt) >> amt;
  97             (Self {
  98                 val: val as u128,
  99                 ty: self.ty,
 100             }, oflo)
 101         } else {
 102             let max = u128::max_value() >> amt;
 103             let val = self.val;
 104             let oflo = val > max - n;
 105             let val = if oflo {
 106                 n - (max - val) - 1
 107             } else {
 108                 val + n
 109             };
 110             (Self {
 111                 val: val,
 112                 ty: self.ty,
 113             }, oflo)
 114         }
 115     }
 116 }
 117
 118 pub trait IntTypeExt {
 119     fn to_ty<'a, 'gcx, 'tcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx>;
 120     fn disr_incr<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, val: Option<Discr<'tcx>>)
 121                            -> Option<Discr<'tcx>>;
 122     fn initial_discriminant<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Discr<'tcx>;
 123 }
 124
 125 impl IntTypeExt for attr::IntType {
 126     fn to_ty<'a, 'gcx, 'tcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx> {
 127         match *self {
 128             SignedInt(ast::IntTy::I8)      => tcx.types.i8,
 129             SignedInt(ast::IntTy::I16)     => tcx.types.i16,
 130             SignedInt(ast::IntTy::I32)     => tcx.types.i32,
 131             SignedInt(ast::IntTy::I64)     => tcx.types.i64,
 132             SignedInt(ast::IntTy::I128)     => tcx.types.i128,
 133             SignedInt(ast::IntTy::Isize)   => tcx.types.isize,
 134             UnsignedInt(ast::UintTy::U8)    => tcx.types.u8,
 135             UnsignedInt(ast::UintTy::U16)   => tcx.types.u16,
 136             UnsignedInt(ast::UintTy::U32)   => tcx.types.u32,
 137             UnsignedInt(ast::UintTy::U64)   => tcx.types.u64,
 138             UnsignedInt(ast::UintTy::U128)   => tcx.types.u128,
 139             UnsignedInt(ast::UintTy::Usize) => tcx.types.usize,
 140         }
 141     }
 142
 143     fn initial_discriminant<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Discr<'tcx> {
 144         Discr {
 145             val: 0,
 146             ty: self.to_ty(tcx)
 147         }
 148     }
 149
 150     fn disr_incr<'a, 'tcx>(
 151         &self,
 152         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 153         val: Option<Discr<'tcx>>,
 154     ) -> Option<Discr<'tcx>> {
 155         if let Some(val) = val {
 156             assert_eq!(self.to_ty(tcx), val.ty);
 157             let (new, oflo) = val.checked_add(tcx, 1);
 158             if oflo {
 159                 None
 160             } else {
 161                 Some(new)
 162             }
 163         } else {
 164             Some(self.initial_discriminant(tcx))
 165         }
 166     }
 167 }
 168
 169
 170 #[derive(Copy, Clone)]
 171 pub enum CopyImplementationError<'tcx> {
 172     InfrigingField(&'tcx ty::FieldDef),
 173     NotAnAdt,
 174     HasDestructor,
 175 }
 176
 177 /// Describes whether a type is representable. For types that are not
 178 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
 179 /// distinguish between types that are recursive with themselves and types that
 180 /// contain a different recursive type. These cases can therefore be treated
 181 /// differently when reporting errors.
 182 ///
 183 /// The ordering of the cases is significant. They are sorted so that cmp::max
 184 /// will keep the "more erroneous" of two values.
 185 #[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
 186 pub enum Representability {
 187     Representable,
 188     ContainsRecursive,
 189     SelfRecursive(Vec<Span>),
 190 }
 191
 192 impl<'tcx> ty::ParamEnv<'tcx> {
 193     pub fn can_type_implement_copy<'a>(self,
 194                                        tcx: TyCtxt<'a, 'tcx, 'tcx>,
 195                                        self_type: Ty<'tcx>, span: Span)
 196                                        -> Result<(), CopyImplementationError<'tcx>> {
 197         // FIXME: (@jroesch) float this code up
 198         tcx.infer_ctxt().enter(|infcx| {
 199             let (adt, substs) = match self_type.sty {
 200                 // These types used to have a builtin impl.
 201                 // Now libcore provides that impl.
 202                 ty::TyUint(_) | ty::TyInt(_) | ty::TyBool | ty::TyFloat(_) |
 203                 ty::TyChar | ty::TyRawPtr(..) | ty::TyNever |
 204                 ty::TyRef(_, ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => return Ok(()),
 205
 206                 ty::TyAdt(adt, substs) => (adt, substs),
 207
 208                 _ => return Err(CopyImplementationError::NotAnAdt),
 209             };
 210
 211             let field_implements_copy = |field: &ty::FieldDef| {
 212                 let cause = traits::ObligationCause::dummy();
 213                 match traits::fully_normalize(&infcx, cause, self, &field.ty(tcx, substs)) {
 214                     Ok(ty) => !infcx.type_moves_by_default(self, ty, span),
 215                     Err(..) => false,
 216                 }
 217             };
 218
 219             for variant in &adt.variants {
 220                 for field in &variant.fields {
 221                     if !field_implements_copy(field) {
 222                         return Err(CopyImplementationError::InfrigingField(field));
 223                     }
 224                 }
 225             }
 226
 227             if adt.has_dtor(tcx) {
 228                 return Err(CopyImplementationError::HasDestructor);
 229             }
 230
 231             Ok(())
 232         })
 233     }
 234 }
 235
 236 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
 237     /// Creates a hash of the type `Ty` which will be the same no matter what crate
 238     /// context it's calculated within. This is used by the `type_id` intrinsic.
 239     pub fn type_id_hash(self, ty: Ty<'tcx>) -> u64 {
 240         let mut hasher = StableHasher::new();
 241         let mut hcx = self.create_stable_hashing_context();
 242
 243         // We want the type_id be independent of the types free regions, so we
 244         // erase them. The erase_regions() call will also anonymize bound
 245         // regions, which is desirable too.
 246         let ty = self.erase_regions(&ty);
 247
 248         hcx.while_hashing_spans(false, |hcx| {
 249             hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
 250                 ty.hash_stable(hcx, &mut hasher);
 251             });
 252         });
 253         hasher.finish()
 254     }
 255 }
 256
 257 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 258     pub fn has_error_field(self, ty: Ty<'tcx>) -> bool {
 259         match ty.sty {
 260             ty::TyAdt(def, substs) => {
 261                 for field in def.all_fields() {
 262                     let field_ty = field.ty(self, substs);
 263                     if let TyError = field_ty.sty {
 264                         return true;
 265                     }
 266                 }
 267             }
 268             _ => (),
 269         }
 270         false
 271     }
 272
 273     /// Returns the deeply last field of nested structures, or the same type,
 274     /// if not a structure at all. Corresponds to the only possible unsized
 275     /// field, and its type can be used to determine unsizing strategy.
 276     pub fn struct_tail(self, mut ty: Ty<'tcx>) -> Ty<'tcx> {
 277         loop {
 278             match ty.sty {
 279                 ty::TyAdt(def, substs) => {
 280                     if !def.is_struct() {
 281                         break;
 282                     }
 283                     match def.non_enum_variant().fields.last() {
 284                         Some(f) => ty = f.ty(self, substs),
 285                         None => break,
 286                     }
 287                 }
 288
 289                 ty::TyTuple(tys) => {
 290                     if let Some((&last_ty, _)) = tys.split_last() {
 291                         ty = last_ty;
 292                     } else {
 293                         break;
 294                     }
 295                 }
 296
 297                 _ => {
 298                     break;
 299                 }
 300             }
 301         }
 302         ty
 303     }
 304
 305     /// Same as applying struct_tail on `source` and `target`, but only
 306     /// keeps going as long as the two types are instances of the same
 307     /// structure definitions.
 308     /// For `(Foo<Foo<T>>, Foo<Trait>)`, the result will be `(Foo<T>, Trait)`,
 309     /// whereas struct_tail produces `T`, and `Trait`, respectively.
 310     pub fn struct_lockstep_tails(self,
 311                                  source: Ty<'tcx>,
 312                                  target: Ty<'tcx>)
 313                                  -> (Ty<'tcx>, Ty<'tcx>) {
 314         let (mut a, mut b) = (source, target);
 315         loop {
 316             match (&a.sty, &b.sty) {
 317                 (&TyAdt(a_def, a_substs), &TyAdt(b_def, b_substs))
 318                         if a_def == b_def && a_def.is_struct() => {
 319                     if let Some(f) = a_def.non_enum_variant().fields.last() {
 320                         a = f.ty(self, a_substs);
 321                         b = f.ty(self, b_substs);
 322                     } else {
 323                         break;
 324                     }
 325                 },
 326                 (&TyTuple(a_tys), &TyTuple(b_tys))
 327                         if a_tys.len() == b_tys.len() => {
 328                     if let Some(a_last) = a_tys.last() {
 329                         a = a_last;
 330                         b = b_tys.last().unwrap();
 331                     } else {
 332                         break;
 333                     }
 334                 },
 335                 _ => break,
 336             }
 337         }
 338         (a, b)
 339     }
 340
 341     /// Given a set of predicates that apply to an object type, returns
 342     /// the region bounds that the (erased) `Self` type must
 343     /// outlive. Precisely *because* the `Self` type is erased, the
 344     /// parameter `erased_self_ty` must be supplied to indicate what type
 345     /// has been used to represent `Self` in the predicates
 346     /// themselves. This should really be a unique type; `FreshTy(0)` is a
 347     /// popular choice.
 348     ///
 349     /// NB: in some cases, particularly around higher-ranked bounds,
 350     /// this function returns a kind of conservative approximation.
 351     /// That is, all regions returned by this function are definitely
 352     /// required, but there may be other region bounds that are not
 353     /// returned, as well as requirements like `for<'a> T: 'a`.
 354     ///
 355     /// Requires that trait definitions have been processed so that we can
 356     /// elaborate predicates and walk supertraits.
 357     ///
 358     /// FIXME callers may only have a &[Predicate], not a Vec, so that's
 359     /// what this code should accept.
 360     pub fn required_region_bounds(self,
 361                                   erased_self_ty: Ty<'tcx>,
 362                                   predicates: Vec<ty::Predicate<'tcx>>)
 363                                   -> Vec<ty::Region<'tcx>>    {
 364         debug!("required_region_bounds(erased_self_ty={:?}, predicates={:?})",
 365                erased_self_ty,
 366                predicates);
 367
 368         assert!(!erased_self_ty.has_escaping_regions());
 369
 370         traits::elaborate_predicates(self, predicates)
 371             .filter_map(|predicate| {
 372                 match predicate {
 373                     ty::Predicate::Projection(..) |
 374                     ty::Predicate::Trait(..) |
 375                     ty::Predicate::Subtype(..) |
 376                     ty::Predicate::WellFormed(..) |
 377                     ty::Predicate::ObjectSafe(..) |
 378                     ty::Predicate::ClosureKind(..) |
 379                     ty::Predicate::RegionOutlives(..) |
 380                     ty::Predicate::ConstEvaluatable(..) => {
 381                         None
 382                     }
 383                     ty::Predicate::TypeOutlives(predicate) => {
 384                         // Search for a bound of the form `erased_self_ty
 385                         // : 'a`, but be wary of something like `for<'a>
 386                         // erased_self_ty : 'a` (we interpret a
 387                         // higher-ranked bound like that as 'static,
 388                         // though at present the code in `fulfill.rs`
 389                         // considers such bounds to be unsatisfiable, so
 390                         // it's kind of a moot point since you could never
 391                         // construct such an object, but this seems
 392                         // correct even if that code changes).
 393                         let ty::OutlivesPredicate(ref t, ref r) = predicate.skip_binder();
 394                         if t == &erased_self_ty && !r.has_escaping_regions() {
 395                             Some(*r)
 396                         } else {
 397                             None
 398                         }
 399                     }
 400                 }
 401             })
 402             .collect()
 403     }
 404
 405     /// Calculate the destructor of a given type.
 406     pub fn calculate_dtor(
 407         self,
 408         adt_did: DefId,
 409         validate: &mut dyn FnMut(Self, DefId) -> Result<(), ErrorReported>
 410     ) -> Option<ty::Destructor> {
 411         let drop_trait = if let Some(def_id) = self.lang_items().drop_trait() {
 412             def_id
 413         } else {
 414             return None;
 415         };
 416
 417         ty::maps::queries::coherent_trait::ensure(self, drop_trait);
 418
 419         let mut dtor_did = None;
 420         let ty = self.type_of(adt_did);
 421         self.for_each_relevant_impl(drop_trait, ty, |impl_did| {
 422             if let Some(item) = self.associated_items(impl_did).next() {
 423                 if let Ok(()) = validate(self, impl_did) {
 424                     dtor_did = Some(item.def_id);
 425                 }
 426             }
 427         });
 428
 429         Some(ty::Destructor { did: dtor_did? })
 430     }
 431
 432     /// Return the set of types that are required to be alive in
 433     /// order to run the destructor of `def` (see RFCs 769 and
 434     /// 1238).
 435     ///
 436     /// Note that this returns only the constraints for the
 437     /// destructor of `def` itself. For the destructors of the
 438     /// contents, you need `adt_dtorck_constraint`.
 439     pub fn destructor_constraints(self, def: &'tcx ty::AdtDef)
 440                                   -> Vec<ty::subst::Kind<'tcx>>
 441     {
 442         let dtor = match def.destructor(self) {
 443             None => {
 444                 debug!("destructor_constraints({:?}) - no dtor", def.did);
 445                 return vec![]
 446             }
 447             Some(dtor) => dtor.did
 448         };
 449
 450         // RFC 1238: if the destructor method is tagged with the
 451         // attribute `unsafe_destructor_blind_to_params`, then the
 452         // compiler is being instructed to *assume* that the
 453         // destructor will not access borrowed data,
 454         // even if such data is otherwise reachable.
 455         //
 456         // Such access can be in plain sight (e.g. dereferencing
 457         // `*foo.0` of `Foo<'a>(&'a u32)`) or indirectly hidden
 458         // (e.g. calling `foo.0.clone()` of `Foo<T:Clone>`).
 459         if self.has_attr(dtor, "unsafe_destructor_blind_to_params") {
 460             debug!("destructor_constraint({:?}) - blind", def.did);
 461             return vec![];
 462         }
 463
 464         let impl_def_id = self.associated_item(dtor).container.id();
 465         let impl_generics = self.generics_of(impl_def_id);
 466
 467         // We have a destructor - all the parameters that are not
 468         // pure_wrt_drop (i.e, don't have a #[may_dangle] attribute)
 469         // must be live.
 470
 471         // We need to return the list of parameters from the ADTs
 472         // generics/substs that correspond to impure parameters on the
 473         // impl's generics. This is a bit ugly, but conceptually simple:
 474         //
 475         // Suppose our ADT looks like the following
 476         //
 477         //     struct S<X, Y, Z>(X, Y, Z);
 478         //
 479         // and the impl is
 480         //
 481         //     impl<#[may_dangle] P0, P1, P2> Drop for S<P1, P2, P0>
 482         //
 483         // We want to return the parameters (X, Y). For that, we match
 484         // up the item-substs <X, Y, Z> with the substs on the impl ADT,
 485         // <P1, P2, P0>, and then look up which of the impl substs refer to
 486         // parameters marked as pure.
 487
 488         let impl_substs = match self.type_of(impl_def_id).sty {
 489             ty::TyAdt(def_, substs) if def_ == def => substs,
 490             _ => bug!()
 491         };
 492
 493         let item_substs = match self.type_of(def.did).sty {
 494             ty::TyAdt(def_, substs) if def_ == def => substs,
 495             _ => bug!()
 496         };
 497
 498         let result = item_substs.iter().zip(impl_substs.iter())
 499             .filter(|&(_, &k)| {
 500                 match k.unpack() {
 501                     UnpackedKind::Lifetime(&ty::RegionKind::ReEarlyBound(ref ebr)) => {
 502                         !impl_generics.region_param(ebr, self).pure_wrt_drop
 503                     }
 504                     UnpackedKind::Type(&ty::TyS {
 505                         sty: ty::TypeVariants::TyParam(ref pt), ..
 506                     }) => {
 507                         !impl_generics.type_param(pt, self).pure_wrt_drop
 508                     }
 509                     UnpackedKind::Lifetime(_) | UnpackedKind::Type(_) => {
 510                         // not a type or region param - this should be reported
 511                         // as an error.
 512                         false
 513                     }
 514                 }
 515             }).map(|(&item_param, _)| item_param).collect();
 516         debug!("destructor_constraint({:?}) = {:?}", def.did, result);
 517         result
 518     }
 519
 520     pub fn is_closure(self, def_id: DefId) -> bool {
 521         self.def_key(def_id).disambiguated_data.data == DefPathData::ClosureExpr
 522     }
 523
 524     /// Given the `DefId` of a fn or closure, returns the `DefId` of
 525     /// the innermost fn item that the closure is contained within.
 526     /// This is a significant def-id because, when we do
 527     /// type-checking, we type-check this fn item and all of its
 528     /// (transitive) closures together.  Therefore, when we fetch the
 529     /// `typeck_tables_of` the closure, for example, we really wind up
 530     /// fetching the `typeck_tables_of` the enclosing fn item.
 531     pub fn closure_base_def_id(self, def_id: DefId) -> DefId {
 532         let mut def_id = def_id;
 533         while self.is_closure(def_id) {
 534             def_id = self.parent_def_id(def_id).unwrap_or_else(|| {
 535                 bug!("closure {:?} has no parent", def_id);
 536             });
 537         }
 538         def_id
 539     }
 540
 541     /// Given the def-id and substs a closure, creates the type of
 542     /// `self` argument that the closure expects. For example, for a
 543     /// `Fn` closure, this would return a reference type `&T` where
 544     /// `T=closure_ty`.
 545     ///
 546     /// Returns `None` if this closure's kind has not yet been inferred.
 547     /// This should only be possible during type checking.
 548     ///
 549     /// Note that the return value is a late-bound region and hence
 550     /// wrapped in a binder.
 551     pub fn closure_env_ty(self,
 552                           closure_def_id: DefId,
 553                           closure_substs: ty::ClosureSubsts<'tcx>)
 554                           -> Option<ty::Binder<Ty<'tcx>>>
 555     {
 556         let closure_ty = self.mk_closure(closure_def_id, closure_substs);
 557         let env_region = ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrEnv);
 558         let closure_kind_ty = closure_substs.closure_kind_ty(closure_def_id, self);
 559         let closure_kind = closure_kind_ty.to_opt_closure_kind()?;
 560         let env_ty = match closure_kind {
 561             ty::ClosureKind::Fn => self.mk_imm_ref(self.mk_region(env_region), closure_ty),
 562             ty::ClosureKind::FnMut => self.mk_mut_ref(self.mk_region(env_region), closure_ty),
 563             ty::ClosureKind::FnOnce => closure_ty,
 564         };
 565         Some(ty::Binder::bind(env_ty))
 566     }
 567
 568     /// Given the def-id of some item that has no type parameters, make
 569     /// a suitable "empty substs" for it.
 570     pub fn empty_substs_for_def_id(self, item_def_id: DefId) -> &'tcx ty::Substs<'tcx> {
 571         ty::Substs::for_item(self, item_def_id,
 572                              |_, _| self.types.re_erased,
 573                              |_, _| {
 574             bug!("empty_substs_for_def_id: {:?} has type parameters", item_def_id)
 575         })
 576     }
 577
 578     /// Return whether the node pointed to by def_id is a static item, and its mutability
 579     pub fn is_static(&self, def_id: DefId) -> Option<hir::Mutability> {
 580         if let Some(node) = self.hir.get_if_local(def_id) {
 581             match node {
 582                 Node::NodeItem(&hir::Item {
 583                     node: hir::ItemStatic(_, mutbl, _), ..
 584                 }) => Some(mutbl),
 585                 Node::NodeForeignItem(&hir::ForeignItem {
 586                     node: hir::ForeignItemStatic(_, is_mutbl), ..
 587                 }) =>
 588                     Some(if is_mutbl {
 589                         hir::Mutability::MutMutable
 590                     } else {
 591                         hir::Mutability::MutImmutable
 592                     }),
 593                 _ => None
 594             }
 595         } else {
 596             match self.describe_def(def_id) {
 597                 Some(Def::Static(_, is_mutbl)) =>
 598                     Some(if is_mutbl {
 599                         hir::Mutability::MutMutable
 600                     } else {
 601                         hir::Mutability::MutImmutable
 602                     }),
 603                 _ => None
 604             }
 605         }
 606     }
 607 }
 608
 609 pub struct TypeIdHasher<'a, 'gcx: 'a+'tcx, 'tcx: 'a, W> {
 610     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 611     state: StableHasher<W>,
 612 }
 613
 614 impl<'a, 'gcx, 'tcx, W> TypeIdHasher<'a, 'gcx, 'tcx, W>
 615     where W: StableHasherResult
 616 {
 617     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Self {
 618         TypeIdHasher { tcx: tcx, state: StableHasher::new() }
 619     }
 620
 621     pub fn finish(self) -> W {
 622         self.state.finish()
 623     }
 624
 625     pub fn hash<T: Hash>(&mut self, x: T) {
 626         x.hash(&mut self.state);
 627     }
 628
 629     fn hash_discriminant_u8<T>(&mut self, x: &T) {
 630         let v = unsafe {
 631             intrinsics::discriminant_value(x)
 632         };
 633         let b = v as u8;
 634         assert_eq!(v, b as u64);
 635         self.hash(b)
 636     }
 637
 638     fn def_id(&mut self, did: DefId) {
 639         // Hash the DefPath corresponding to the DefId, which is independent
 640         // of compiler internal state. We already have a stable hash value of
 641         // all DefPaths available via tcx.def_path_hash(), so we just feed that
 642         // into the hasher.
 643         let hash = self.tcx.def_path_hash(did);
 644         self.hash(hash);
 645     }
 646 }
 647
 648 impl<'a, 'gcx, 'tcx, W> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx, W>
 649     where W: StableHasherResult
 650 {
 651     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 652         // Distinguish between the Ty variants uniformly.
 653         self.hash_discriminant_u8(&ty.sty);
 654
 655         match ty.sty {
 656             TyInt(i) => self.hash(i),
 657             TyUint(u) => self.hash(u),
 658             TyFloat(f) => self.hash(f),
 659             TyArray(_, n) => {
 660                 self.hash_discriminant_u8(&n.val);
 661                 match n.val {
 662                     ConstVal::Value(Value::ByVal(PrimVal::Bytes(b))) => self.hash(b),
 663                     ConstVal::Unevaluated(def_id, _) => self.def_id(def_id),
 664                     _ => bug!("arrays should not have {:?} as length", n)
 665                 }
 666             }
 667             TyRawPtr(m) |
 668             TyRef(_, m) => self.hash(m.mutbl),
 669             TyClosure(def_id, _) |
 670             TyGenerator(def_id, _, _) |
 671             TyAnon(def_id, _) |
 672             TyFnDef(def_id, _) => self.def_id(def_id),
 673             TyAdt(d, _) => self.def_id(d.did),
 674             TyForeign(def_id) => self.def_id(def_id),
 675             TyFnPtr(f) => {
 676                 self.hash(f.unsafety());
 677                 self.hash(f.abi());
 678                 self.hash(f.variadic());
 679                 self.hash(f.inputs().skip_binder().len());
 680             }
 681             TyDynamic(ref data, ..) => {
 682                 if let Some(p) = data.principal() {
 683                     self.def_id(p.def_id());
 684                 }
 685                 for d in data.auto_traits() {
 686                     self.def_id(d);
 687                 }
 688             }
 689             TyGeneratorWitness(tys) => {
 690                 self.hash(tys.skip_binder().len());
 691             }
 692             TyTuple(tys) => {
 693                 self.hash(tys.len());
 694             }
 695             TyParam(p) => {
 696                 self.hash(p.idx);
 697                 self.hash(p.name);
 698             }
 699             TyProjection(ref data) => {
 700                 self.def_id(data.item_def_id);
 701             }
 702             TyNever |
 703             TyBool |
 704             TyChar |
 705             TyStr |
 706             TySlice(_) => {}
 707
 708             TyError |
 709             TyInfer(_) => bug!("TypeIdHasher: unexpected type {}", ty)
 710         }
 711
 712         ty.super_visit_with(self)
 713     }
 714
 715     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 716         self.hash_discriminant_u8(r);
 717         match *r {
 718             ty::ReErased |
 719             ty::ReStatic |
 720             ty::ReEmpty => {
 721                 // No variant fields to hash for these ...
 722             }
 723             ty::ReCanonical(c) => {
 724                 self.hash(c);
 725             }
 726             ty::ReLateBound(db, ty::BrAnon(i)) => {
 727                 self.hash(db.depth);
 728                 self.hash(i);
 729             }
 730             ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, .. }) => {
 731                 self.def_id(def_id);
 732             }
 733
 734             ty::ReClosureBound(..) |
 735             ty::ReLateBound(..) |
 736             ty::ReFree(..) |
 737             ty::ReScope(..) |
 738             ty::ReVar(..) |
 739             ty::ReSkolemized(..) => {
 740                 bug!("TypeIdHasher: unexpected region {:?}", r)
 741             }
 742         }
 743         false
 744     }
 745
 746     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, x: &ty::Binder<T>) -> bool {
 747         // Anonymize late-bound regions so that, for example:
 748         // `for<'a, b> fn(&'a &'b T)` and `for<'a, b> fn(&'b &'a T)`
 749         // result in the same TypeId (the two types are equivalent).
 750         self.tcx.anonymize_late_bound_regions(x).super_visit_with(self)
 751     }
 752 }
 753
 754 impl<'a, 'tcx> ty::TyS<'tcx> {
 755     pub fn moves_by_default(&'tcx self,
 756                             tcx: TyCtxt<'a, 'tcx, 'tcx>,
 757                             param_env: ty::ParamEnv<'tcx>,
 758                             span: Span)
 759                             -> bool {
 760         !tcx.at(span).is_copy_raw(param_env.and(self))
 761     }
 762
 763     pub fn is_sized(&'tcx self,
 764                     tcx_at: TyCtxtAt<'a, 'tcx, 'tcx>,
 765                     param_env: ty::ParamEnv<'tcx>)-> bool
 766     {
 767         tcx_at.is_sized_raw(param_env.and(self))
 768     }
 769
 770     pub fn is_freeze(&'tcx self,
 771                      tcx: TyCtxt<'a, 'tcx, 'tcx>,
 772                      param_env: ty::ParamEnv<'tcx>,
 773                      span: Span)-> bool
 774     {
 775         tcx.at(span).is_freeze_raw(param_env.and(self))
 776     }
 777
 778     /// If `ty.needs_drop(...)` returns `true`, then `ty` is definitely
 779     /// non-copy and *might* have a destructor attached; if it returns
 780     /// `false`, then `ty` definitely has no destructor (i.e. no drop glue).
 781     ///
 782     /// (Note that this implies that if `ty` has a destructor attached,
 783     /// then `needs_drop` will definitely return `true` for `ty`.)
 784     #[inline]
 785     pub fn needs_drop(&'tcx self,
 786                       tcx: TyCtxt<'a, 'tcx, 'tcx>,
 787                       param_env: ty::ParamEnv<'tcx>)
 788                       -> bool {
 789         tcx.needs_drop_raw(param_env.and(self))
 790     }
 791
 792     /// Check whether a type is representable. This means it cannot contain unboxed
 793     /// structural recursion. This check is needed for structs and enums.
 794     pub fn is_representable(&'tcx self,
 795                             tcx: TyCtxt<'a, 'tcx, 'tcx>,
 796                             sp: Span)
 797                             -> Representability {
 798
 799         // Iterate until something non-representable is found
 800         fn fold_repr<It: Iterator<Item=Representability>>(iter: It) -> Representability {
 801             iter.fold(Representability::Representable, |r1, r2| {
 802                 match (r1, r2) {
 803                     (Representability::SelfRecursive(v1),
 804                      Representability::SelfRecursive(v2)) => {
 805                         Representability::SelfRecursive(v1.iter().map(|s| *s).chain(v2).collect())
 806                     }
 807                     (r1, r2) => cmp::max(r1, r2)
 808                 }
 809             })
 810         }
 811
 812         fn are_inner_types_recursive<'a, 'tcx>(
 813             tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span,
 814             seen: &mut Vec<Ty<'tcx>>,
 815             representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
 816             ty: Ty<'tcx>)
 817             -> Representability
 818         {
 819             match ty.sty {
 820                 TyTuple(ref ts) => {
 821                     // Find non representable
 822                     fold_repr(ts.iter().map(|ty| {
 823                         is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
 824                     }))
 825                 }
 826                 // Fixed-length vectors.
 827                 // FIXME(#11924) Behavior undecided for zero-length vectors.
 828                 TyArray(ty, _) => {
 829                     is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
 830                 }
 831                 TyAdt(def, substs) => {
 832                     // Find non representable fields with their spans
 833                     fold_repr(def.all_fields().map(|field| {
 834                         let ty = field.ty(tcx, substs);
 835                         let span = tcx.hir.span_if_local(field.did).unwrap_or(sp);
 836                         match is_type_structurally_recursive(tcx, span, seen,
 837                                                              representable_cache, ty)
 838                         {
 839                             Representability::SelfRecursive(_) => {
 840                                 Representability::SelfRecursive(vec![span])
 841                             }
 842                             x => x,
 843                         }
 844                     }))
 845                 }
 846                 TyClosure(..) => {
 847                     // this check is run on type definitions, so we don't expect
 848                     // to see closure types
 849                     bug!("requires check invoked on inapplicable type: {:?}", ty)
 850                 }
 851                 _ => Representability::Representable,
 852             }
 853         }
 854
 855         fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
 856             match ty.sty {
 857                 TyAdt(ty_def, _) => {
 858                      ty_def == def
 859                 }
 860                 _ => false
 861             }
 862         }
 863
 864         fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 865             match (&a.sty, &b.sty) {
 866                 (&TyAdt(did_a, substs_a), &TyAdt(did_b, substs_b)) => {
 867                     if did_a != did_b {
 868                         return false;
 869                     }
 870
 871                     substs_a.types().zip(substs_b.types()).all(|(a, b)| same_type(a, b))
 872                 }
 873                 _ => a == b,
 874             }
 875         }
 876
 877         // Does the type `ty` directly (without indirection through a pointer)
 878         // contain any types on stack `seen`?
 879         fn is_type_structurally_recursive<'a, 'tcx>(
 880             tcx: TyCtxt<'a, 'tcx, 'tcx>,
 881             sp: Span,
 882             seen: &mut Vec<Ty<'tcx>>,
 883             representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
 884             ty: Ty<'tcx>) -> Representability
 885         {
 886             debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
 887             if let Some(representability) = representable_cache.get(ty) {
 888                 debug!("is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
 889                        ty, sp, representability);
 890                 return representability.clone();
 891             }
 892
 893             let representability = is_type_structurally_recursive_inner(
 894                 tcx, sp, seen, representable_cache, ty);
 895
 896             representable_cache.insert(ty, representability.clone());
 897             representability
 898         }
 899
 900         fn is_type_structurally_recursive_inner<'a, 'tcx>(
 901             tcx: TyCtxt<'a, 'tcx, 'tcx>,
 902             sp: Span,
 903             seen: &mut Vec<Ty<'tcx>>,
 904             representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
 905             ty: Ty<'tcx>) -> Representability
 906         {
 907             match ty.sty {
 908                 TyAdt(def, _) => {
 909                     {
 910                         // Iterate through stack of previously seen types.
 911                         let mut iter = seen.iter();
 912
 913                         // The first item in `seen` is the type we are actually curious about.
 914                         // We want to return SelfRecursive if this type contains itself.
 915                         // It is important that we DON'T take generic parameters into account
 916                         // for this check, so that Bar<T> in this example counts as SelfRecursive:
 917                         //
 918                         // struct Foo;
 919                         // struct Bar<T> { x: Bar<Foo> }
 920
 921                         if let Some(&seen_type) = iter.next() {
 922                             if same_struct_or_enum(seen_type, def) {
 923                                 debug!("SelfRecursive: {:?} contains {:?}",
 924                                        seen_type,
 925                                        ty);
 926                                 return Representability::SelfRecursive(vec![sp]);
 927                             }
 928                         }
 929
 930                         // We also need to know whether the first item contains other types
 931                         // that are structurally recursive. If we don't catch this case, we
 932                         // will recurse infinitely for some inputs.
 933                         //
 934                         // It is important that we DO take generic parameters into account
 935                         // here, so that code like this is considered SelfRecursive, not
 936                         // ContainsRecursive:
 937                         //
 938                         // struct Foo { Option<Option<Foo>> }
 939
 940                         for &seen_type in iter {
 941                             if same_type(ty, seen_type) {
 942                                 debug!("ContainsRecursive: {:?} contains {:?}",
 943                                        seen_type,
 944                                        ty);
 945                                 return Representability::ContainsRecursive;
 946                             }
 947                         }
 948                     }
 949
 950                     // For structs and enums, track all previously seen types by pushing them
 951                     // onto the 'seen' stack.
 952                     seen.push(ty);
 953                     let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
 954                     seen.pop();
 955                     out
 956                 }
 957                 _ => {
 958                     // No need to push in other cases.
 959                     are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)
 960                 }
 961             }
 962         }
 963
 964         debug!("is_type_representable: {:?}", self);
 965
 966         // To avoid a stack overflow when checking an enum variant or struct that
 967         // contains a different, structurally recursive type, maintain a stack
 968         // of seen types and check recursion for each of them (issues #3008, #3779).
 969         let mut seen: Vec<Ty> = Vec::new();
 970         let mut representable_cache = FxHashMap();
 971         let r = is_type_structurally_recursive(
 972             tcx, sp, &mut seen, &mut representable_cache, self);
 973         debug!("is_type_representable: {:?} is {:?}", self, r);
 974         r
 975     }
 976 }
 977
 978 fn is_copy_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 979                          query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
 980                          -> bool
 981 {
 982     let (param_env, ty) = query.into_parts();
 983     let trait_def_id = tcx.require_lang_item(lang_items::CopyTraitLangItem);
 984     tcx.infer_ctxt()
 985        .enter(|infcx| traits::type_known_to_meet_bound(&infcx,
 986                                                        param_env,
 987                                                        ty,
 988                                                        trait_def_id,
 989                                                        DUMMY_SP))
 990 }
 991
 992 fn is_sized_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 993                           query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
 994                           -> bool
 995 {
 996     let (param_env, ty) = query.into_parts();
 997     let trait_def_id = tcx.require_lang_item(lang_items::SizedTraitLangItem);
 998     tcx.infer_ctxt()
 999        .enter(|infcx| traits::type_known_to_meet_bound(&infcx,
1000                                                        param_env,
1001                                                        ty,
1002                                                        trait_def_id,
1003                                                        DUMMY_SP))
1004 }
1005
1006 fn is_freeze_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1007                            query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
1008                            -> bool
1009 {
1010     let (param_env, ty) = query.into_parts();
1011     let trait_def_id = tcx.require_lang_item(lang_items::FreezeTraitLangItem);
1012     tcx.infer_ctxt()
1013        .enter(|infcx| traits::type_known_to_meet_bound(&infcx,
1014                                                        param_env,
1015                                                        ty,
1016                                                        trait_def_id,
1017                                                        DUMMY_SP))
1018 }
1019
1020 fn needs_drop_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1021                             query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
1022                             -> bool
1023 {
1024     let (param_env, ty) = query.into_parts();
1025
1026     let needs_drop = |ty: Ty<'tcx>| -> bool {
1027         match tcx.try_get_query::<ty::queries::needs_drop_raw>(DUMMY_SP, param_env.and(ty)) {
1028             Ok(v) => v,
1029             Err(mut bug) => {
1030                 // Cycles should be reported as an error by `check_representable`.
1031                 //
1032                 // Consider the type as not needing drop in the meanwhile to
1033                 // avoid further errors.
1034                 //
1035                 // In case we forgot to emit a bug elsewhere, delay our
1036                 // diagnostic to get emitted as a compiler bug.
1037                 bug.delay_as_bug();
1038                 false
1039             }
1040         }
1041     };
1042
1043     assert!(!ty.needs_infer());
1044
1045     match ty.sty {
1046         // Fast-path for primitive types
1047         ty::TyInfer(ty::FreshIntTy(_)) | ty::TyInfer(ty::FreshFloatTy(_)) |
1048         ty::TyBool | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) | ty::TyNever |
1049         ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar | ty::TyGeneratorWitness(..) |
1050         ty::TyRawPtr(_) | ty::TyRef(..) | ty::TyStr => false,
1051
1052         // Foreign types can never have destructors
1053         ty::TyForeign(..) => false,
1054
1055         // Issue #22536: We first query type_moves_by_default.  It sees a
1056         // normalized version of the type, and therefore will definitely
1057         // know whether the type implements Copy (and thus needs no
1058         // cleanup/drop/zeroing) ...
1059         _ if !ty.moves_by_default(tcx, param_env, DUMMY_SP) => false,
1060
1061         // ... (issue #22536 continued) but as an optimization, still use
1062         // prior logic of asking for the structural "may drop".
1063
1064         // FIXME(#22815): Note that this is a conservative heuristic;
1065         // it may report that the type "may drop" when actual type does
1066         // not actually have a destructor associated with it. But since
1067         // the type absolutely did not have the `Copy` bound attached
1068         // (see above), it is sound to treat it as having a destructor.
1069
1070         // User destructors are the only way to have concrete drop types.
1071         ty::TyAdt(def, _) if def.has_dtor(tcx) => true,
1072
1073         // Can refer to a type which may drop.
1074         // FIXME(eddyb) check this against a ParamEnv.
1075         ty::TyDynamic(..) | ty::TyProjection(..) | ty::TyParam(_) |
1076         ty::TyAnon(..) | ty::TyInfer(_) | ty::TyError => true,
1077
1078         // Structural recursion.
1079         ty::TyArray(ty, _) | ty::TySlice(ty) => needs_drop(ty),
1080
1081         ty::TyClosure(def_id, ref substs) => substs.upvar_tys(def_id, tcx).any(needs_drop),
1082
1083         // Pessimistically assume that all generators will require destructors
1084         // as we don't know if a destructor is a noop or not until after the MIR
1085         // state transformation pass
1086         ty::TyGenerator(..) => true,
1087
1088         ty::TyTuple(ref tys) => tys.iter().cloned().any(needs_drop),
1089
1090         // unions don't have destructors regardless of the child types
1091         ty::TyAdt(def, _) if def.is_union() => false,
1092
1093         ty::TyAdt(def, substs) =>
1094             def.variants.iter().any(
1095                 |variant| variant.fields.iter().any(
1096                     |field| needs_drop(field.ty(tcx, substs)))),
1097     }
1098 }
1099
1100 pub enum ExplicitSelf<'tcx> {
1101     ByValue,
1102     ByReference(ty::Region<'tcx>, hir::Mutability),
1103     ByRawPointer(hir::Mutability),
1104     ByBox,
1105     Other
1106 }
1107
1108 impl<'tcx> ExplicitSelf<'tcx> {
1109     /// Categorizes an explicit self declaration like `self: SomeType`
1110     /// into either `self`, `&self`, `&mut self`, `Box<self>`, or
1111     /// `Other`.
1112     /// This is mainly used to require the arbitrary_self_types feature
1113     /// in the case of `Other`, to improve error messages in the common cases,
1114     /// and to make `Other` non-object-safe.
1115     ///
1116     /// Examples:
1117     ///
1118     /// ```
1119     /// impl<'a> Foo for &'a T {
1120     ///     // Legal declarations:
1121     ///     fn method1(self: &&'a T); // ExplicitSelf::ByReference
1122     ///     fn method2(self: &'a T); // ExplicitSelf::ByValue
1123     ///     fn method3(self: Box<&'a T>); // ExplicitSelf::ByBox
1124     ///     fn method4(self: Rc<&'a T>); // ExplicitSelf::Other
1125     ///
1126     ///     // Invalid cases will be caught by `check_method_receiver`:
1127     ///     fn method_err1(self: &'a mut T); // ExplicitSelf::Other
1128     ///     fn method_err2(self: &'static T) // ExplicitSelf::ByValue
1129     ///     fn method_err3(self: &&T) // ExplicitSelf::ByReference
1130     /// }
1131     /// ```
1132     ///
1133     pub fn determine<P>(
1134         self_arg_ty: Ty<'tcx>,
1135         is_self_ty: P
1136     ) -> ExplicitSelf<'tcx>
1137     where
1138         P: Fn(Ty<'tcx>) -> bool
1139     {
1140         use self::ExplicitSelf::*;
1141
1142         match self_arg_ty.sty {
1143             _ if is_self_ty(self_arg_ty) => ByValue,
1144             ty::TyRef(region, ty::TypeAndMut { ty, mutbl }) if is_self_ty(ty) => {
1145                 ByReference(region, mutbl)
1146             }
1147             ty::TyRawPtr(ty::TypeAndMut { ty, mutbl }) if is_self_ty(ty) => {
1148                 ByRawPointer(mutbl)
1149             }
1150             ty::TyAdt(def, _) if def.is_box() && is_self_ty(self_arg_ty.boxed_ty()) => {
1151                 ByBox
1152             }
1153             _ => Other
1154         }
1155     }
1156 }
1157
1158 pub fn provide(providers: &mut ty::maps::Providers) {
1159     *providers = ty::maps::Providers {
1160         is_copy_raw,
1161         is_sized_raw,
1162         is_freeze_raw,
1163         needs_drop_raw,
1164         ..*providers
1165     };
1166 }