src/librustc/ty/context.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 //! type context book-keeping
  12
  13 use dep_graph::{DepGraph, DepTrackingMap};
  14 use session::Session;
  15 use middle;
  16 use middle::cstore::LOCAL_CRATE;
  17 use hir::def::DefMap;
  18 use hir::def_id::{DefId, DefIndex};
  19 use hir::map as ast_map;
  20 use hir::map::{DefKey, DefPath, DefPathData, DisambiguatedDefPathData};
  21 use middle::free_region::FreeRegionMap;
  22 use middle::region::RegionMaps;
  23 use middle::resolve_lifetime;
  24 use middle::stability;
  25 use ty::subst::{self, Substs};
  26 use traits;
  27 use ty::{self, TraitRef, Ty, TypeAndMut};
  28 use ty::{TyS, TypeVariants};
  29 use ty::{AdtDef, ClosureSubsts, ExistentialBounds, Region};
  30 use hir::FreevarMap;
  31 use ty::{BareFnTy, InferTy, ParamTy, ProjectionTy, TraitTy};
  32 use ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
  33 use ty::TypeVariants::*;
  34 use ty::layout::{Layout, TargetDataLayout};
  35 use ty::maps;
  36 use util::common::MemoizationMap;
  37 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet};
  38 use util::nodemap::{FnvHashMap, FnvHashSet};
  39
  40 use arena::TypedArena;
  41 use std::borrow::Borrow;
  42 use std::cell::{Cell, RefCell, Ref};
  43 use std::hash::{Hash, Hasher};
  44 use std::mem;
  45 use std::ops::Deref;
  46 use std::rc::Rc;
  47 use syntax::ast::{self, Name, NodeId};
  48 use syntax::attr;
  49 use syntax::parse::token::{self, keywords};
  50
  51 use hir;
  52
  53 /// Internal storage
  54 pub struct CtxtArenas<'tcx> {
  55     // internings
  56     type_: TypedArena<TyS<'tcx>>,
  57     type_list: TypedArena<Vec<Ty<'tcx>>>,
  58     substs: TypedArena<Substs<'tcx>>,
  59     bare_fn: TypedArena<BareFnTy<'tcx>>,
  60     region: TypedArena<Region>,
  61     stability: TypedArena<attr::Stability>,
  62     layout: TypedArena<Layout>,
  63
  64     // references
  65     trait_defs: TypedArena<ty::TraitDef<'tcx>>,
  66     adt_defs: TypedArena<ty::AdtDefData<'tcx, 'tcx>>,
  67 }
  68
  69 impl<'tcx> CtxtArenas<'tcx> {
  70     pub fn new() -> CtxtArenas<'tcx> {
  71         CtxtArenas {
  72             type_: TypedArena::new(),
  73             type_list: TypedArena::new(),
  74             substs: TypedArena::new(),
  75             bare_fn: TypedArena::new(),
  76             region: TypedArena::new(),
  77             stability: TypedArena::new(),
  78             layout: TypedArena::new(),
  79
  80             trait_defs: TypedArena::new(),
  81             adt_defs: TypedArena::new()
  82         }
  83     }
  84 }
  85
  86 pub struct CtxtInterners<'tcx> {
  87     /// The arenas that types etc are allocated from.
  88     arenas: &'tcx CtxtArenas<'tcx>,
  89
  90     /// Specifically use a speedy hash algorithm for these hash sets,
  91     /// they're accessed quite often.
  92     type_: RefCell<FnvHashSet<Interned<'tcx, TyS<'tcx>>>>,
  93     type_list: RefCell<FnvHashSet<Interned<'tcx, [Ty<'tcx>]>>>,
  94     substs: RefCell<FnvHashSet<Interned<'tcx, Substs<'tcx>>>>,
  95     bare_fn: RefCell<FnvHashSet<Interned<'tcx, BareFnTy<'tcx>>>>,
  96     region: RefCell<FnvHashSet<Interned<'tcx, Region>>>,
  97     stability: RefCell<FnvHashSet<&'tcx attr::Stability>>,
  98     layout: RefCell<FnvHashSet<&'tcx Layout>>,
  99 }
 100
 101 impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
 102     fn new(arenas: &'tcx CtxtArenas<'tcx>) -> CtxtInterners<'tcx> {
 103         CtxtInterners {
 104             arenas: arenas,
 105             type_: RefCell::new(FnvHashSet()),
 106             type_list: RefCell::new(FnvHashSet()),
 107             substs: RefCell::new(FnvHashSet()),
 108             bare_fn: RefCell::new(FnvHashSet()),
 109             region: RefCell::new(FnvHashSet()),
 110             stability: RefCell::new(FnvHashSet()),
 111             layout: RefCell::new(FnvHashSet())
 112         }
 113     }
 114
 115     /// Intern a type. global_interners is Some only if this is
 116     /// a local interner and global_interners is its counterpart.
 117     fn intern_ty(&self, st: TypeVariants<'tcx>,
 118                  global_interners: Option<&CtxtInterners<'gcx>>)
 119                  -> Ty<'tcx> {
 120         let ty = {
 121             let mut interner = self.type_.borrow_mut();
 122             let global_interner = global_interners.map(|interners| {
 123                 interners.type_.borrow_mut()
 124             });
 125             if let Some(&Interned(ty)) = interner.get(&st) {
 126                 return ty;
 127             }
 128             if let Some(ref interner) = global_interner {
 129                 if let Some(&Interned(ty)) = interner.get(&st) {
 130                     return ty;
 131                 }
 132             }
 133
 134             let flags = super::flags::FlagComputation::for_sty(&st);
 135             let ty_struct = TyS {
 136                 sty: st,
 137                 flags: Cell::new(flags.flags),
 138                 region_depth: flags.depth,
 139             };
 140
 141             // HACK(eddyb) Depend on flags being accurate to
 142             // determine that all contents are in the global tcx.
 143             // See comments on Lift for why we can't use that.
 144             if !flags.flags.intersects(ty::TypeFlags::KEEP_IN_LOCAL_TCX) {
 145                 if let Some(interner) = global_interners {
 146                     let ty_struct: TyS<'gcx> = unsafe {
 147                         mem::transmute(ty_struct)
 148                     };
 149                     let ty: Ty<'gcx> = interner.arenas.type_.alloc(ty_struct);
 150                     global_interner.unwrap().insert(Interned(ty));
 151                     return ty;
 152                 }
 153             } else {
 154                 // Make sure we don't end up with inference
 155                 // types/regions in the global tcx.
 156                 if global_interners.is_none() {
 157                     drop(interner);
 158                     bug!("Attempted to intern `{:?}` which contains \
 159                           inference types/regions in the global type context",
 160                          &ty_struct);
 161                 }
 162             }
 163
 164             // Don't be &mut TyS.
 165             let ty: Ty<'tcx> = self.arenas.type_.alloc(ty_struct);
 166             interner.insert(Interned(ty));
 167             ty
 168         };
 169
 170         debug!("Interned type: {:?} Pointer: {:?}",
 171             ty, ty as *const TyS);
 172         ty
 173     }
 174
 175 }
 176
 177 pub struct CommonTypes<'tcx> {
 178     pub bool: Ty<'tcx>,
 179     pub char: Ty<'tcx>,
 180     pub isize: Ty<'tcx>,
 181     pub i8: Ty<'tcx>,
 182     pub i16: Ty<'tcx>,
 183     pub i32: Ty<'tcx>,
 184     pub i64: Ty<'tcx>,
 185     pub usize: Ty<'tcx>,
 186     pub u8: Ty<'tcx>,
 187     pub u16: Ty<'tcx>,
 188     pub u32: Ty<'tcx>,
 189     pub u64: Ty<'tcx>,
 190     pub f32: Ty<'tcx>,
 191     pub f64: Ty<'tcx>,
 192     pub err: Ty<'tcx>,
 193 }
 194
 195 pub struct Tables<'tcx> {
 196     /// Stores the types for various nodes in the AST.  Note that this table
 197     /// is not guaranteed to be populated until after typeck.  See
 198     /// typeck::check::fn_ctxt for details.
 199     pub node_types: NodeMap<Ty<'tcx>>,
 200
 201     /// Stores the type parameters which were substituted to obtain the type
 202     /// of this node.  This only applies to nodes that refer to entities
 203     /// parameterized by type parameters, such as generic fns, types, or
 204     /// other items.
 205     pub item_substs: NodeMap<ty::ItemSubsts<'tcx>>,
 206
 207     pub adjustments: NodeMap<ty::adjustment::AutoAdjustment<'tcx>>,
 208
 209     pub method_map: ty::MethodMap<'tcx>,
 210
 211     /// Borrows
 212     pub upvar_capture_map: ty::UpvarCaptureMap,
 213
 214     /// Records the type of each closure. The def ID is the ID of the
 215     /// expression defining the closure.
 216     pub closure_tys: DefIdMap<ty::ClosureTy<'tcx>>,
 217
 218     /// Records the type of each closure. The def ID is the ID of the
 219     /// expression defining the closure.
 220     pub closure_kinds: DefIdMap<ty::ClosureKind>,
 221
 222     /// For each fn, records the "liberated" types of its arguments
 223     /// and return type. Liberated means that all bound regions
 224     /// (including late-bound regions) are replaced with free
 225     /// equivalents. This table is not used in trans (since regions
 226     /// are erased there) and hence is not serialized to metadata.
 227     pub liberated_fn_sigs: NodeMap<ty::FnSig<'tcx>>,
 228
 229     /// For each FRU expression, record the normalized types of the fields
 230     /// of the struct - this is needed because it is non-trivial to
 231     /// normalize while preserving regions. This table is used only in
 232     /// MIR construction and hence is not serialized to metadata.
 233     pub fru_field_types: NodeMap<Vec<Ty<'tcx>>>
 234 }
 235
 236 impl<'a, 'gcx, 'tcx> Tables<'tcx> {
 237     pub fn empty() -> Tables<'tcx> {
 238         Tables {
 239             node_types: FnvHashMap(),
 240             item_substs: NodeMap(),
 241             adjustments: NodeMap(),
 242             method_map: FnvHashMap(),
 243             upvar_capture_map: FnvHashMap(),
 244             closure_tys: DefIdMap(),
 245             closure_kinds: DefIdMap(),
 246             liberated_fn_sigs: NodeMap(),
 247             fru_field_types: NodeMap()
 248         }
 249     }
 250 }
 251
 252 impl<'tcx> CommonTypes<'tcx> {
 253     fn new(interners: &CtxtInterners<'tcx>) -> CommonTypes<'tcx> {
 254         let mk = |sty| interners.intern_ty(sty, None);
 255         CommonTypes {
 256             bool: mk(TyBool),
 257             char: mk(TyChar),
 258             err: mk(TyError),
 259             isize: mk(TyInt(ast::IntTy::Is)),
 260             i8: mk(TyInt(ast::IntTy::I8)),
 261             i16: mk(TyInt(ast::IntTy::I16)),
 262             i32: mk(TyInt(ast::IntTy::I32)),
 263             i64: mk(TyInt(ast::IntTy::I64)),
 264             usize: mk(TyUint(ast::UintTy::Us)),
 265             u8: mk(TyUint(ast::UintTy::U8)),
 266             u16: mk(TyUint(ast::UintTy::U16)),
 267             u32: mk(TyUint(ast::UintTy::U32)),
 268             u64: mk(TyUint(ast::UintTy::U64)),
 269             f32: mk(TyFloat(ast::FloatTy::F32)),
 270             f64: mk(TyFloat(ast::FloatTy::F64)),
 271         }
 272     }
 273 }
 274
 275 /// The data structure to keep track of all the information that typechecker
 276 /// generates so that so that it can be reused and doesn't have to be redone
 277 /// later on.
 278 #[derive(Copy, Clone)]
 279 pub struct TyCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 280     gcx: &'a GlobalCtxt<'gcx>,
 281     interners: &'a CtxtInterners<'tcx>
 282 }
 283
 284 impl<'a, 'gcx, 'tcx> Deref for TyCtxt<'a, 'gcx, 'tcx> {
 285     type Target = &'a GlobalCtxt<'gcx>;
 286     fn deref(&self) -> &Self::Target {
 287         &self.gcx
 288     }
 289 }
 290
 291 pub struct GlobalCtxt<'tcx> {
 292     global_interners: CtxtInterners<'tcx>,
 293
 294     pub specializes_cache: RefCell<traits::SpecializesCache>,
 295
 296     pub dep_graph: DepGraph,
 297
 298     /// Common types, pre-interned for your convenience.
 299     pub types: CommonTypes<'tcx>,
 300
 301     pub sess: &'tcx Session,
 302     pub def_map: RefCell<DefMap>,
 303
 304     pub named_region_map: resolve_lifetime::NamedRegionMap,
 305
 306     pub region_maps: RegionMaps,
 307
 308     // For each fn declared in the local crate, type check stores the
 309     // free-region relationships that were deduced from its where
 310     // clauses and parameter types. These are then read-again by
 311     // borrowck. (They are not used during trans, and hence are not
 312     // serialized or needed for cross-crate fns.)
 313     free_region_maps: RefCell<NodeMap<FreeRegionMap>>,
 314     // FIXME: jroesch make this a refcell
 315
 316     pub tables: RefCell<Tables<'tcx>>,
 317
 318     /// Maps from a trait item to the trait item "descriptor"
 319     pub impl_or_trait_items: RefCell<DepTrackingMap<maps::ImplOrTraitItems<'tcx>>>,
 320
 321     /// Maps from a trait def-id to a list of the def-ids of its trait items
 322     pub trait_item_def_ids: RefCell<DepTrackingMap<maps::TraitItemDefIds<'tcx>>>,
 323
 324     /// A cache for the trait_items() routine; note that the routine
 325     /// itself pushes the `TraitItems` dependency node.
 326     trait_items_cache: RefCell<DepTrackingMap<maps::TraitItems<'tcx>>>,
 327
 328     pub impl_trait_refs: RefCell<DepTrackingMap<maps::ImplTraitRefs<'tcx>>>,
 329     pub trait_defs: RefCell<DepTrackingMap<maps::TraitDefs<'tcx>>>,
 330     pub adt_defs: RefCell<DepTrackingMap<maps::AdtDefs<'tcx>>>,
 331
 332     /// Maps from the def-id of an item (trait/struct/enum/fn) to its
 333     /// associated predicates.
 334     pub predicates: RefCell<DepTrackingMap<maps::Predicates<'tcx>>>,
 335
 336     /// Maps from the def-id of a trait to the list of
 337     /// super-predicates. This is a subset of the full list of
 338     /// predicates. We store these in a separate map because we must
 339     /// evaluate them even during type conversion, often before the
 340     /// full predicates are available (note that supertraits have
 341     /// additional acyclicity requirements).
 342     pub super_predicates: RefCell<DepTrackingMap<maps::Predicates<'tcx>>>,
 343
 344     pub map: ast_map::Map<'tcx>,
 345
 346     // Records the free variables refrenced by every closure
 347     // expression. Do not track deps for this, just recompute it from
 348     // scratch every time.
 349     pub freevars: RefCell<FreevarMap>,
 350
 351     pub maybe_unused_trait_imports: NodeSet,
 352
 353     // Records the type of every item.
 354     pub tcache: RefCell<DepTrackingMap<maps::Tcache<'tcx>>>,
 355
 356     // Internal cache for metadata decoding. No need to track deps on this.
 357     pub rcache: RefCell<FnvHashMap<ty::CReaderCacheKey, Ty<'tcx>>>,
 358
 359     // Cache for the type-contents routine. FIXME -- track deps?
 360     pub tc_cache: RefCell<FnvHashMap<Ty<'tcx>, ty::contents::TypeContents>>,
 361
 362     // FIXME no dep tracking, but we should be able to remove this
 363     pub ty_param_defs: RefCell<NodeMap<ty::TypeParameterDef<'tcx>>>,
 364
 365     // FIXME dep tracking -- should be harmless enough
 366     pub normalized_cache: RefCell<FnvHashMap<Ty<'tcx>, Ty<'tcx>>>,
 367
 368     pub lang_items: middle::lang_items::LanguageItems,
 369
 370     /// Maps from def-id of a type or region parameter to its
 371     /// (inferred) variance.
 372     pub item_variance_map: RefCell<DepTrackingMap<maps::ItemVariances<'tcx>>>,
 373
 374     /// True if the variance has been computed yet; false otherwise.
 375     pub variance_computed: Cell<bool>,
 376
 377     /// Maps a DefId of a type to a list of its inherent impls.
 378     /// Contains implementations of methods that are inherent to a type.
 379     /// Methods in these implementations don't need to be exported.
 380     pub inherent_impls: RefCell<DepTrackingMap<maps::InherentImpls<'tcx>>>,
 381
 382     /// Maps a DefId of an impl to a list of its items.
 383     /// Note that this contains all of the impls that we know about,
 384     /// including ones in other crates. It's not clear that this is the best
 385     /// way to do it.
 386     pub impl_items: RefCell<DepTrackingMap<maps::ImplItems<'tcx>>>,
 387
 388     /// Set of used unsafe nodes (functions or blocks). Unsafe nodes not
 389     /// present in this set can be warned about.
 390     pub used_unsafe: RefCell<NodeSet>,
 391
 392     /// Set of nodes which mark locals as mutable which end up getting used at
 393     /// some point. Local variable definitions not in this set can be warned
 394     /// about.
 395     pub used_mut_nodes: RefCell<NodeSet>,
 396
 397     /// Set of trait imports actually used in the method resolution.
 398     /// This is used for warning unused imports.
 399     pub used_trait_imports: RefCell<NodeSet>,
 400
 401     /// The set of external nominal types whose implementations have been read.
 402     /// This is used for lazy resolution of methods.
 403     pub populated_external_types: RefCell<DefIdSet>,
 404
 405     /// The set of external primitive types whose implementations have been read.
 406     /// FIXME(arielb1): why is this separate from populated_external_types?
 407     pub populated_external_primitive_impls: RefCell<DefIdSet>,
 408
 409     /// Cache used by const_eval when decoding external constants.
 410     /// Contains `None` when the constant has been fetched but doesn't exist.
 411     /// Constains `Some(expr_id, type)` otherwise.
 412     /// `type` is `None` in case it's not a primitive type
 413     pub extern_const_statics: RefCell<DefIdMap<Option<(NodeId, Option<Ty<'tcx>>)>>>,
 414     /// Cache used by const_eval when decoding extern const fns
 415     pub extern_const_fns: RefCell<DefIdMap<NodeId>>,
 416
 417     /// Maps any item's def-id to its stability index.
 418     pub stability: RefCell<stability::Index<'tcx>>,
 419
 420     /// Caches the results of trait selection. This cache is used
 421     /// for things that do not have to do with the parameters in scope.
 422     pub selection_cache: traits::SelectionCache<'tcx>,
 423
 424     /// Caches the results of trait evaluation. This cache is used
 425     /// for things that do not have to do with the parameters in scope.
 426     /// Merge this with `selection_cache`?
 427     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 428
 429     /// A set of predicates that have been fulfilled *somewhere*.
 430     /// This is used to avoid duplicate work. Predicates are only
 431     /// added to this set when they mention only "global" names
 432     /// (i.e., no type or lifetime parameters).
 433     pub fulfilled_predicates: RefCell<traits::GlobalFulfilledPredicates<'tcx>>,
 434
 435     /// Caches the representation hints for struct definitions.
 436     repr_hint_cache: RefCell<DepTrackingMap<maps::ReprHints<'tcx>>>,
 437
 438     /// Maps Expr NodeId's to their constant qualification.
 439     pub const_qualif_map: RefCell<NodeMap<middle::const_qualif::ConstQualif>>,
 440
 441     /// Caches CoerceUnsized kinds for impls on custom types.
 442     pub custom_coerce_unsized_kinds: RefCell<DefIdMap<ty::adjustment::CustomCoerceUnsized>>,
 443
 444     /// Maps a cast expression to its kind. This is keyed on the
 445     /// *from* expression of the cast, not the cast itself.
 446     pub cast_kinds: RefCell<NodeMap<ty::cast::CastKind>>,
 447
 448     /// Maps Fn items to a collection of fragment infos.
 449     ///
 450     /// The main goal is to identify data (each of which may be moved
 451     /// or assigned) whose subparts are not moved nor assigned
 452     /// (i.e. their state is *unfragmented*) and corresponding ast
 453     /// nodes where the path to that data is moved or assigned.
 454     ///
 455     /// In the long term, unfragmented values will have their
 456     /// destructor entirely driven by a single stack-local drop-flag,
 457     /// and their parents, the collections of the unfragmented values
 458     /// (or more simply, "fragmented values"), are mapped to the
 459     /// corresponding collections of stack-local drop-flags.
 460     ///
 461     /// (However, in the short term that is not the case; e.g. some
 462     /// unfragmented paths still need to be zeroed, namely when they
 463     /// reference parent data from an outer scope that was not
 464     /// entirely moved, and therefore that needs to be zeroed so that
 465     /// we do not get double-drop when we hit the end of the parent
 466     /// scope.)
 467     ///
 468     /// Also: currently the table solely holds keys for node-ids of
 469     /// unfragmented values (see `FragmentInfo` enum definition), but
 470     /// longer-term we will need to also store mappings from
 471     /// fragmented data to the set of unfragmented pieces that
 472     /// constitute it.
 473     pub fragment_infos: RefCell<DefIdMap<Vec<ty::FragmentInfo>>>,
 474
 475     /// The definite name of the current crate after taking into account
 476     /// attributes, commandline parameters, etc.
 477     pub crate_name: token::InternedString,
 478
 479     /// Data layout specification for the current target.
 480     pub data_layout: TargetDataLayout,
 481
 482     /// Cache for layouts computed from types.
 483     pub layout_cache: RefCell<FnvHashMap<Ty<'tcx>, &'tcx Layout>>,
 484 }
 485
 486 impl<'tcx> GlobalCtxt<'tcx> {
 487     /// Get the global TyCtxt.
 488     pub fn global_tcx<'a>(&'a self) -> TyCtxt<'a, 'tcx, 'tcx> {
 489         TyCtxt {
 490             gcx: self,
 491             interners: &self.global_interners
 492         }
 493     }
 494 }
 495
 496 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 497     pub fn crate_name(self, cnum: ast::CrateNum) -> token::InternedString {
 498         if cnum == LOCAL_CRATE {
 499             self.crate_name.clone()
 500         } else {
 501             self.sess.cstore.crate_name(cnum)
 502         }
 503     }
 504
 505     pub fn crate_disambiguator(self, cnum: ast::CrateNum) -> token::InternedString {
 506         if cnum == LOCAL_CRATE {
 507             self.sess.local_crate_disambiguator()
 508         } else {
 509             self.sess.cstore.crate_disambiguator(cnum)
 510         }
 511     }
 512
 513     /// Given a def-key `key` and a crate `krate`, finds the def-index
 514     /// that `krate` assigned to `key`. This `DefIndex` will always be
 515     /// relative to `krate`.
 516     ///
 517     /// Returns `None` if there is no `DefIndex` with that key.
 518     pub fn def_index_for_def_key(self, krate: ast::CrateNum, key: DefKey)
 519                                  -> Option<DefIndex> {
 520         if krate == LOCAL_CRATE {
 521             self.map.def_index_for_def_key(key)
 522         } else {
 523             self.sess.cstore.def_index_for_def_key(krate, key)
 524         }
 525     }
 526
 527     pub fn retrace_path(self, path: &DefPath) -> Option<DefId> {
 528         debug!("retrace_path(path={:?})", path);
 529
 530         let root_key = DefKey {
 531             parent: None,
 532             disambiguated_data: DisambiguatedDefPathData {
 533                 data: DefPathData::CrateRoot,
 534                 disambiguator: 0,
 535             },
 536         };
 537
 538         let root_index = self.def_index_for_def_key(path.krate, root_key)
 539                              .expect("no root key?");
 540
 541         debug!("retrace_path: root_index={:?}", root_index);
 542
 543         let mut index = root_index;
 544         for data in &path.data {
 545             let key = DefKey { parent: Some(index), disambiguated_data: data.clone() };
 546             debug!("retrace_path: key={:?}", key);
 547             match self.def_index_for_def_key(path.krate, key) {
 548                 Some(i) => index = i,
 549                 None => return None,
 550             }
 551         }
 552
 553         Some(DefId { krate: path.krate, index: index })
 554     }
 555
 556     pub fn type_parameter_def(self,
 557                               node_id: NodeId)
 558                               -> ty::TypeParameterDef<'tcx>
 559     {
 560         self.ty_param_defs.borrow().get(&node_id).unwrap().clone()
 561     }
 562
 563     pub fn node_types(self) -> Ref<'a, NodeMap<Ty<'tcx>>> {
 564         fn projection<'a, 'tcx>(tables: &'a Tables<'tcx>) -> &'a NodeMap<Ty<'tcx>> {
 565             &tables.node_types
 566         }
 567
 568         Ref::map(self.tables.borrow(), projection)
 569     }
 570
 571     pub fn node_type_insert(self, id: NodeId, ty: Ty<'gcx>) {
 572         self.tables.borrow_mut().node_types.insert(id, ty);
 573     }
 574
 575     pub fn intern_trait_def(self, def: ty::TraitDef<'gcx>)
 576                             -> &'gcx ty::TraitDef<'gcx> {
 577         let did = def.trait_ref.def_id;
 578         let interned = self.global_interners.arenas.trait_defs.alloc(def);
 579         if let Some(prev) = self.trait_defs.borrow_mut().insert(did, interned) {
 580             bug!("Tried to overwrite interned TraitDef: {:?}", prev)
 581         }
 582         interned
 583     }
 584
 585     pub fn alloc_trait_def(self, def: ty::TraitDef<'gcx>)
 586                            -> &'gcx ty::TraitDef<'gcx> {
 587         self.global_interners.arenas.trait_defs.alloc(def)
 588     }
 589
 590     pub fn insert_adt_def(self, did: DefId, adt_def: ty::AdtDefMaster<'gcx>) {
 591         // this will need a transmute when reverse-variance is removed
 592         if let Some(prev) = self.adt_defs.borrow_mut().insert(did, adt_def) {
 593             bug!("Tried to overwrite interned AdtDef: {:?}", prev)
 594         }
 595     }
 596
 597     pub fn intern_adt_def(self,
 598                           did: DefId,
 599                           kind: ty::AdtKind,
 600                           variants: Vec<ty::VariantDefData<'gcx, 'gcx>>)
 601                           -> ty::AdtDefMaster<'gcx> {
 602         let def = ty::AdtDefData::new(self, did, kind, variants);
 603         let interned = self.global_interners.arenas.adt_defs.alloc(def);
 604         self.insert_adt_def(did, interned);
 605         interned
 606     }
 607
 608     pub fn intern_stability(self, stab: attr::Stability) -> &'gcx attr::Stability {
 609         if let Some(st) = self.global_interners.stability.borrow().get(&stab) {
 610             return st;
 611         }
 612
 613         let interned = self.global_interners.arenas.stability.alloc(stab);
 614         if let Some(prev) = self.global_interners.stability
 615                                 .borrow_mut()
 616                                 .replace(interned) {
 617             bug!("Tried to overwrite interned Stability: {:?}", prev)
 618         }
 619         interned
 620     }
 621
 622     pub fn intern_layout(self, layout: Layout) -> &'gcx Layout {
 623         if let Some(layout) = self.global_interners.layout.borrow().get(&layout) {
 624             return layout;
 625         }
 626
 627         let interned = self.global_interners.arenas.layout.alloc(layout);
 628         if let Some(prev) = self.global_interners.layout
 629                                 .borrow_mut()
 630                                 .replace(interned) {
 631             bug!("Tried to overwrite interned Layout: {:?}", prev)
 632         }
 633         interned
 634     }
 635
 636     pub fn store_free_region_map(self, id: NodeId, map: FreeRegionMap) {
 637         if self.free_region_maps.borrow_mut().insert(id, map).is_some() {
 638             bug!("Tried to overwrite interned FreeRegionMap for NodeId {:?}", id)
 639         }
 640     }
 641
 642     pub fn free_region_map(self, id: NodeId) -> FreeRegionMap {
 643         self.free_region_maps.borrow()[&id].clone()
 644     }
 645
 646     pub fn lift<T: ?Sized + Lift<'tcx>>(self, value: &T) -> Option<T::Lifted> {
 647         value.lift_to_tcx(self)
 648     }
 649
 650     /// Like lift, but only tries in the global tcx.
 651     pub fn lift_to_global<T: ?Sized + Lift<'gcx>>(self, value: &T) -> Option<T::Lifted> {
 652         value.lift_to_tcx(self.global_tcx())
 653     }
 654
 655     /// Returns true if self is the same as self.global_tcx().
 656     fn is_global(self) -> bool {
 657         let local = self.interners as *const _;
 658         let global = &self.global_interners as *const _;
 659         local as usize == global as usize
 660     }
 661
 662     /// Create a type context and call the closure with a `TyCtxt` reference
 663     /// to the context. The closure enforces that the type context and any interned
 664     /// value (types, substs, etc.) can only be used while `ty::tls` has a valid
 665     /// reference to the context, to allow formatting values that need it.
 666     pub fn create_and_enter<F, R>(s: &'tcx Session,
 667                                   arenas: &'tcx CtxtArenas<'tcx>,
 668                                   def_map: DefMap,
 669                                   named_region_map: resolve_lifetime::NamedRegionMap,
 670                                   map: ast_map::Map<'tcx>,
 671                                   freevars: FreevarMap,
 672                                  maybe_unused_trait_imports: NodeSet,
 673                                   region_maps: RegionMaps,
 674                                   lang_items: middle::lang_items::LanguageItems,
 675                                   stability: stability::Index<'tcx>,
 676                                  crate_name: &str,
 677                                   f: F) -> R
 678                                   where F: for<'b> FnOnce(TyCtxt<'b, 'tcx, 'tcx>) -> R
 679     {
 680         let data_layout = TargetDataLayout::parse(s);
 681         let interners = CtxtInterners::new(arenas);
 682         let common_types = CommonTypes::new(&interners);
 683         let dep_graph = map.dep_graph.clone();
 684         let fulfilled_predicates = traits::GlobalFulfilledPredicates::new(dep_graph.clone());
 685         tls::enter_global(GlobalCtxt {
 686             specializes_cache: RefCell::new(traits::SpecializesCache::new()),
 687             global_interners: interners,
 688             dep_graph: dep_graph.clone(),
 689             types: common_types,
 690             named_region_map: named_region_map,
 691             region_maps: region_maps,
 692             free_region_maps: RefCell::new(FnvHashMap()),
 693             item_variance_map: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 694             variance_computed: Cell::new(false),
 695             sess: s,
 696             def_map: RefCell::new(def_map),
 697             tables: RefCell::new(Tables::empty()),
 698             impl_trait_refs: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 699             trait_defs: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 700             adt_defs: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 701             predicates: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 702             super_predicates: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 703             fulfilled_predicates: RefCell::new(fulfilled_predicates),
 704             map: map,
 705             freevars: RefCell::new(freevars),
 706             maybe_unused_trait_imports: maybe_unused_trait_imports,
 707             tcache: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 708             rcache: RefCell::new(FnvHashMap()),
 709             tc_cache: RefCell::new(FnvHashMap()),
 710             impl_or_trait_items: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 711             trait_item_def_ids: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 712             trait_items_cache: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 713             ty_param_defs: RefCell::new(NodeMap()),
 714             normalized_cache: RefCell::new(FnvHashMap()),
 715             lang_items: lang_items,
 716             inherent_impls: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 717             impl_items: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 718             used_unsafe: RefCell::new(NodeSet()),
 719             used_mut_nodes: RefCell::new(NodeSet()),
 720             used_trait_imports: RefCell::new(NodeSet()),
 721             populated_external_types: RefCell::new(DefIdSet()),
 722             populated_external_primitive_impls: RefCell::new(DefIdSet()),
 723             extern_const_statics: RefCell::new(DefIdMap()),
 724             extern_const_fns: RefCell::new(DefIdMap()),
 725             stability: RefCell::new(stability),
 726             selection_cache: traits::SelectionCache::new(),
 727             evaluation_cache: traits::EvaluationCache::new(),
 728             repr_hint_cache: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 729             const_qualif_map: RefCell::new(NodeMap()),
 730             custom_coerce_unsized_kinds: RefCell::new(DefIdMap()),
 731             cast_kinds: RefCell::new(NodeMap()),
 732             fragment_infos: RefCell::new(DefIdMap()),
 733             crate_name: token::intern_and_get_ident(crate_name),
 734             data_layout: data_layout,
 735             layout_cache: RefCell::new(FnvHashMap()),
 736        }, f)
 737     }
 738 }
 739
 740 impl<'gcx: 'tcx, 'tcx> GlobalCtxt<'gcx> {
 741     /// Call the closure with a local `TyCtxt` using the given arenas.
 742     pub fn enter_local<F, R>(&self, arenas: &'tcx CtxtArenas<'tcx>, f: F) -> R
 743         where F: for<'a> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
 744     {
 745         let interners = CtxtInterners::new(arenas);
 746         tls::enter(self, &interners, f)
 747     }
 748 }
 749
 750 /// A trait implemented for all X<'a> types which can be safely and
 751 /// efficiently converted to X<'tcx> as long as they are part of the
 752 /// provided TyCtxt<'tcx>.
 753 /// This can be done, for example, for Ty<'tcx> or &'tcx Substs<'tcx>
 754 /// by looking them up in their respective interners.
 755 ///
 756 /// However, this is still not the best implementation as it does
 757 /// need to compare the components, even for interned values.
 758 /// It would be more efficient if TypedArena provided a way to
 759 /// determine whether the address is in the allocated range.
 760 ///
 761 /// None is returned if the value or one of the components is not part
 762 /// of the provided context.
 763 /// For Ty, None can be returned if either the type interner doesn't
 764 /// contain the TypeVariants key or if the address of the interned
 765 /// pointer differs. The latter case is possible if a primitive type,
 766 /// e.g. `()` or `u8`, was interned in a different context.
 767 pub trait Lift<'tcx> {
 768     type Lifted;
 769     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted>;
 770 }
 771
 772 impl<'a, 'tcx> Lift<'tcx> for Ty<'a> {
 773     type Lifted = Ty<'tcx>;
 774     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Ty<'tcx>> {
 775         if let Some(&Interned(ty)) = tcx.interners.type_.borrow().get(&self.sty) {
 776             if *self as *const _ == ty as *const _ {
 777                 return Some(ty);
 778             }
 779         }
 780         // Also try in the global tcx if we're not that.
 781         if !tcx.is_global() {
 782             self.lift_to_tcx(tcx.global_tcx())
 783         } else {
 784             None
 785         }
 786     }
 787 }
 788
 789 impl<'a, 'tcx> Lift<'tcx> for &'a Substs<'a> {
 790     type Lifted = &'tcx Substs<'tcx>;
 791     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Substs<'tcx>> {
 792         if let Some(&Interned(substs)) = tcx.interners.substs.borrow().get(*self) {
 793             if *self as *const _ == substs as *const _ {
 794                 return Some(substs);
 795             }
 796         }
 797         // Also try in the global tcx if we're not that.
 798         if !tcx.is_global() {
 799             self.lift_to_tcx(tcx.global_tcx())
 800         } else {
 801             None
 802         }
 803     }
 804 }
 805
 806 impl<'a, 'tcx> Lift<'tcx> for &'a Region {
 807     type Lifted = &'tcx Region;
 808     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Region> {
 809         if let Some(&Interned(region)) = tcx.interners.region.borrow().get(*self) {
 810             if *self as *const _ == region as *const _ {
 811                 return Some(region);
 812             }
 813         }
 814         // Also try in the global tcx if we're not that.
 815         if !tcx.is_global() {
 816             self.lift_to_tcx(tcx.global_tcx())
 817         } else {
 818             None
 819         }
 820     }
 821 }
 822
 823 impl<'a, 'tcx> Lift<'tcx> for &'a [Ty<'a>] {
 824     type Lifted = &'tcx [Ty<'tcx>];
 825     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx [Ty<'tcx>]> {
 826         if let Some(&Interned(list)) = tcx.interners.type_list.borrow().get(*self) {
 827             if *self as *const _ == list as *const _ {
 828                 return Some(list);
 829             }
 830         }
 831         // Also try in the global tcx if we're not that.
 832         if !tcx.is_global() {
 833             self.lift_to_tcx(tcx.global_tcx())
 834         } else {
 835             None
 836         }
 837     }
 838 }
 839
 840 impl<'a, 'tcx> Lift<'tcx> for &'a BareFnTy<'a> {
 841     type Lifted = &'tcx BareFnTy<'tcx>;
 842     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
 843                              -> Option<&'tcx BareFnTy<'tcx>> {
 844         if let Some(&Interned(fty)) = tcx.interners.bare_fn.borrow().get(*self) {
 845             if *self as *const _ == fty as *const _ {
 846                 return Some(fty);
 847             }
 848         }
 849         // Also try in the global tcx if we're not that.
 850         if !tcx.is_global() {
 851             self.lift_to_tcx(tcx.global_tcx())
 852         } else {
 853             None
 854         }
 855     }
 856 }
 857
 858
 859 pub mod tls {
 860     use super::{CtxtInterners, GlobalCtxt, TyCtxt};
 861
 862     use std::cell::Cell;
 863     use std::fmt;
 864     use syntax_pos;
 865
 866     /// Marker types used for the scoped TLS slot.
 867     /// The type context cannot be used directly because the scoped TLS
 868     /// in libstd doesn't allow types generic over lifetimes.
 869     enum ThreadLocalGlobalCtxt {}
 870     enum ThreadLocalInterners {}
 871
 872     thread_local! {
 873         static TLS_TCX: Cell<Option<(*const ThreadLocalGlobalCtxt,
 874                                      *const ThreadLocalInterners)>> = Cell::new(None)
 875     }
 876
 877     fn span_debug(span: syntax_pos::Span, f: &mut fmt::Formatter) -> fmt::Result {
 878         with(|tcx| {
 879             write!(f, "{}", tcx.sess.codemap().span_to_string(span))
 880         })
 881     }
 882
 883     pub fn enter_global<'gcx, F, R>(gcx: GlobalCtxt<'gcx>, f: F) -> R
 884         where F: for<'a> FnOnce(TyCtxt<'a, 'gcx, 'gcx>) -> R
 885     {
 886         syntax_pos::SPAN_DEBUG.with(|span_dbg| {
 887             let original_span_debug = span_dbg.get();
 888             span_dbg.set(span_debug);
 889             let result = enter(&gcx, &gcx.global_interners, f);
 890             span_dbg.set(original_span_debug);
 891             result
 892         })
 893     }
 894
 895     pub fn enter<'a, 'gcx: 'tcx, 'tcx, F, R>(gcx: &'a GlobalCtxt<'gcx>,
 896                                              interners: &'a CtxtInterners<'tcx>,
 897                                              f: F) -> R
 898         where F: FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
 899     {
 900         let gcx_ptr = gcx as *const _ as *const ThreadLocalGlobalCtxt;
 901         let interners_ptr = interners as *const _ as *const ThreadLocalInterners;
 902         TLS_TCX.with(|tls| {
 903             let prev = tls.get();
 904             tls.set(Some((gcx_ptr, interners_ptr)));
 905             let ret = f(TyCtxt {
 906                 gcx: gcx,
 907                 interners: interners
 908             });
 909             tls.set(prev);
 910             ret
 911         })
 912     }
 913
 914     pub fn with<F, R>(f: F) -> R
 915         where F: for<'a, 'gcx, 'tcx> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
 916     {
 917         TLS_TCX.with(|tcx| {
 918             let (gcx, interners) = tcx.get().unwrap();
 919             let gcx = unsafe { &*(gcx as *const GlobalCtxt) };
 920             let interners = unsafe { &*(interners as *const CtxtInterners) };
 921             f(TyCtxt {
 922                 gcx: gcx,
 923                 interners: interners
 924             })
 925         })
 926     }
 927
 928     pub fn with_opt<F, R>(f: F) -> R
 929         where F: for<'a, 'gcx, 'tcx> FnOnce(Option<TyCtxt<'a, 'gcx, 'tcx>>) -> R
 930     {
 931         if TLS_TCX.with(|tcx| tcx.get().is_some()) {
 932             with(|v| f(Some(v)))
 933         } else {
 934             f(None)
 935         }
 936     }
 937 }
 938
 939 macro_rules! sty_debug_print {
 940     ($ctxt: expr, $($variant: ident),*) => {{
 941         // curious inner module to allow variant names to be used as
 942         // variable names.
 943         #[allow(non_snake_case)]
 944         mod inner {
 945             use ty::{self, TyCtxt};
 946             use ty::context::Interned;
 947
 948             #[derive(Copy, Clone)]
 949             struct DebugStat {
 950                 total: usize,
 951                 region_infer: usize,
 952                 ty_infer: usize,
 953                 both_infer: usize,
 954             }
 955
 956             pub fn go(tcx: TyCtxt) {
 957                 let mut total = DebugStat {
 958                     total: 0,
 959                     region_infer: 0, ty_infer: 0, both_infer: 0,
 960                 };
 961                 $(let mut $variant = total;)*
 962
 963
 964                 for &Interned(t) in tcx.interners.type_.borrow().iter() {
 965                     let variant = match t.sty {
 966                         ty::TyBool | ty::TyChar | ty::TyInt(..) | ty::TyUint(..) |
 967                             ty::TyFloat(..) | ty::TyStr => continue,
 968                         ty::TyError => /* unimportant */ continue,
 969                         $(ty::$variant(..) => &mut $variant,)*
 970                     };
 971                     let region = t.flags.get().intersects(ty::TypeFlags::HAS_RE_INFER);
 972                     let ty = t.flags.get().intersects(ty::TypeFlags::HAS_TY_INFER);
 973
 974                     variant.total += 1;
 975                     total.total += 1;
 976                     if region { total.region_infer += 1; variant.region_infer += 1 }
 977                     if ty { total.ty_infer += 1; variant.ty_infer += 1 }
 978                     if region && ty { total.both_infer += 1; variant.both_infer += 1 }
 979                 }
 980                 println!("Ty interner             total           ty region  both");
 981                 $(println!("    {:18}: {uses:6} {usespc:4.1}%, \
 982 {ty:4.1}% {region:5.1}% {both:4.1}%",
 983                            stringify!($variant),
 984                            uses = $variant.total,
 985                            usespc = $variant.total as f64 * 100.0 / total.total as f64,
 986                            ty = $variant.ty_infer as f64 * 100.0  / total.total as f64,
 987                            region = $variant.region_infer as f64 * 100.0  / total.total as f64,
 988                            both = $variant.both_infer as f64 * 100.0  / total.total as f64);
 989                   )*
 990                 println!("                  total {uses:6}        \
 991 {ty:4.1}% {region:5.1}% {both:4.1}%",
 992                          uses = total.total,
 993                          ty = total.ty_infer as f64 * 100.0  / total.total as f64,
 994                          region = total.region_infer as f64 * 100.0  / total.total as f64,
 995                          both = total.both_infer as f64 * 100.0  / total.total as f64)
 996             }
 997         }
 998
 999         inner::go($ctxt)
1000     }}
1001 }
1002
1003 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
1004     pub fn print_debug_stats(self) {
1005         sty_debug_print!(
1006             self,
1007             TyEnum, TyBox, TyArray, TySlice, TyRawPtr, TyRef, TyFnDef, TyFnPtr,
1008             TyTrait, TyStruct, TyClosure, TyTuple, TyParam, TyInfer, TyProjection);
1009
1010         println!("Substs interner: #{}", self.interners.substs.borrow().len());
1011         println!("BareFnTy interner: #{}", self.interners.bare_fn.borrow().len());
1012         println!("Region interner: #{}", self.interners.region.borrow().len());
1013         println!("Stability interner: #{}", self.interners.stability.borrow().len());
1014         println!("Layout interner: #{}", self.interners.layout.borrow().len());
1015     }
1016 }
1017
1018
1019 /// An entry in an interner.
1020 struct Interned<'tcx, T: 'tcx+?Sized>(&'tcx T);
1021
1022 // NB: An Interned<Ty> compares and hashes as a sty.
1023 impl<'tcx> PartialEq for Interned<'tcx, TyS<'tcx>> {
1024     fn eq(&self, other: &Interned<'tcx, TyS<'tcx>>) -> bool {
1025         self.0.sty == other.0.sty
1026     }
1027 }
1028
1029 impl<'tcx> Eq for Interned<'tcx, TyS<'tcx>> {}
1030
1031 impl<'tcx> Hash for Interned<'tcx, TyS<'tcx>> {
1032     fn hash<H: Hasher>(&self, s: &mut H) {
1033         self.0.sty.hash(s)
1034     }
1035 }
1036
1037 impl<'tcx: 'lcx, 'lcx> Borrow<TypeVariants<'lcx>> for Interned<'tcx, TyS<'tcx>> {
1038     fn borrow<'a>(&'a self) -> &'a TypeVariants<'lcx> {
1039         &self.0.sty
1040     }
1041 }
1042
1043 impl<'tcx: 'lcx, 'lcx> Borrow<[Ty<'lcx>]> for Interned<'tcx, [Ty<'tcx>]> {
1044     fn borrow<'a>(&'a self) -> &'a [Ty<'lcx>] {
1045         self.0
1046     }
1047 }
1048
1049 impl<'tcx: 'lcx, 'lcx> Borrow<Substs<'lcx>> for Interned<'tcx, Substs<'tcx>> {
1050     fn borrow<'a>(&'a self) -> &'a Substs<'lcx> {
1051         self.0
1052     }
1053 }
1054
1055 impl<'tcx: 'lcx, 'lcx> Borrow<BareFnTy<'lcx>> for Interned<'tcx, BareFnTy<'tcx>> {
1056     fn borrow<'a>(&'a self) -> &'a BareFnTy<'lcx> {
1057         self.0
1058     }
1059 }
1060
1061 impl<'tcx> Borrow<Region> for Interned<'tcx, Region> {
1062     fn borrow<'a>(&'a self) -> &'a Region {
1063         self.0
1064     }
1065 }
1066
1067 macro_rules! items { ($($item:item)+) => ($($item)+) }
1068 macro_rules! impl_interners {
1069     ($lt_tcx:tt, $($name:ident: $method:ident($alloc:ty, $needs_infer:expr)-> $ty:ty),+) => {
1070         items!($(impl<$lt_tcx> PartialEq for Interned<$lt_tcx, $ty> {
1071             fn eq(&self, other: &Self) -> bool {
1072                 self.0 == other.0
1073             }
1074         }
1075
1076         impl<$lt_tcx> Eq for Interned<$lt_tcx, $ty> {}
1077
1078         impl<$lt_tcx> Hash for Interned<$lt_tcx, $ty> {
1079             fn hash<H: Hasher>(&self, s: &mut H) {
1080                 self.0.hash(s)
1081             }
1082         }
1083
1084         impl<'a, 'gcx, $lt_tcx> TyCtxt<'a, 'gcx, $lt_tcx> {
1085             pub fn $method(self, v: $alloc) -> &$lt_tcx $ty {
1086                 if let Some(i) = self.interners.$name.borrow().get::<$ty>(&v) {
1087                     return i.0;
1088                 }
1089                 if !self.is_global() {
1090                     if let Some(i) = self.global_interners.$name.borrow().get::<$ty>(&v) {
1091                         return i.0;
1092                     }
1093                 }
1094
1095                 // HACK(eddyb) Depend on flags being accurate to
1096                 // determine that all contents are in the global tcx.
1097                 // See comments on Lift for why we can't use that.
1098                 if !($needs_infer)(&v) {
1099                     if !self.is_global() {
1100                         let v = unsafe {
1101                             mem::transmute(v)
1102                         };
1103                         let i = self.global_interners.arenas.$name.alloc(v);
1104                         self.global_interners.$name.borrow_mut().insert(Interned(i));
1105                         return i;
1106                     }
1107                 } else {
1108                     // Make sure we don't end up with inference
1109                     // types/regions in the global tcx.
1110                     if self.is_global() {
1111                         bug!("Attempted to intern `{:?}` which contains \
1112                               inference types/regions in the global type context",
1113                              v);
1114                     }
1115                 }
1116
1117                 let i = self.interners.arenas.$name.alloc(v);
1118                 self.interners.$name.borrow_mut().insert(Interned(i));
1119                 i
1120             }
1121         })+);
1122     }
1123 }
1124
1125 fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
1126     x.has_type_flags(ty::TypeFlags::KEEP_IN_LOCAL_TCX)
1127 }
1128
1129 impl_interners!('tcx,
1130     type_list: mk_type_list(Vec<Ty<'tcx>>, keep_local) -> [Ty<'tcx>],
1131     substs: mk_substs(Substs<'tcx>, |substs: &Substs| {
1132         keep_local(&substs.types) || keep_local(&substs.regions)
1133     }) -> Substs<'tcx>,
1134     bare_fn: mk_bare_fn(BareFnTy<'tcx>, |fty: &BareFnTy| {
1135         keep_local(&fty.sig)
1136     }) -> BareFnTy<'tcx>,
1137     region: mk_region(Region, keep_local) -> Region
1138 );
1139
1140 fn bound_list_is_sorted(bounds: &[ty::PolyProjectionPredicate]) -> bool {
1141     bounds.is_empty() ||
1142         bounds[1..].iter().enumerate().all(
1143             |(index, bound)| bounds[index].sort_key() <= bound.sort_key())
1144 }
1145
1146 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
1147     /// Create an unsafe fn ty based on a safe fn ty.
1148     pub fn safe_to_unsafe_fn_ty(self, bare_fn: &BareFnTy<'tcx>) -> Ty<'tcx> {
1149         assert_eq!(bare_fn.unsafety, hir::Unsafety::Normal);
1150         self.mk_fn_ptr(self.mk_bare_fn(ty::BareFnTy {
1151             unsafety: hir::Unsafety::Unsafe,
1152             abi: bare_fn.abi,
1153             sig: bare_fn.sig.clone()
1154         }))
1155     }
1156
1157     // Interns a type/name combination, stores the resulting box in cx.interners,
1158     // and returns the box as cast to an unsafe ptr (see comments for Ty above).
1159     pub fn mk_ty(self, st: TypeVariants<'tcx>) -> Ty<'tcx> {
1160         let global_interners = if !self.is_global() {
1161             Some(&self.global_interners)
1162         } else {
1163             None
1164         };
1165         self.interners.intern_ty(st, global_interners)
1166     }
1167
1168     pub fn mk_mach_int(self, tm: ast::IntTy) -> Ty<'tcx> {
1169         match tm {
1170             ast::IntTy::Is   => self.types.isize,
1171             ast::IntTy::I8   => self.types.i8,
1172             ast::IntTy::I16  => self.types.i16,
1173             ast::IntTy::I32  => self.types.i32,
1174             ast::IntTy::I64  => self.types.i64,
1175         }
1176     }
1177
1178     pub fn mk_mach_uint(self, tm: ast::UintTy) -> Ty<'tcx> {
1179         match tm {
1180             ast::UintTy::Us   => self.types.usize,
1181             ast::UintTy::U8   => self.types.u8,
1182             ast::UintTy::U16  => self.types.u16,
1183             ast::UintTy::U32  => self.types.u32,
1184             ast::UintTy::U64  => self.types.u64,
1185         }
1186     }
1187
1188     pub fn mk_mach_float(self, tm: ast::FloatTy) -> Ty<'tcx> {
1189         match tm {
1190             ast::FloatTy::F32  => self.types.f32,
1191             ast::FloatTy::F64  => self.types.f64,
1192         }
1193     }
1194
1195     pub fn mk_str(self) -> Ty<'tcx> {
1196         self.mk_ty(TyStr)
1197     }
1198
1199     pub fn mk_static_str(self) -> Ty<'tcx> {
1200         self.mk_imm_ref(self.mk_region(ty::ReStatic), self.mk_str())
1201     }
1202
1203     pub fn mk_enum(self, def: AdtDef<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
1204         // take a copy of substs so that we own the vectors inside
1205         self.mk_ty(TyEnum(def, substs))
1206     }
1207
1208     pub fn mk_box(self, ty: Ty<'tcx>) -> Ty<'tcx> {
1209         self.mk_ty(TyBox(ty))
1210     }
1211
1212     pub fn mk_ptr(self, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
1213         self.mk_ty(TyRawPtr(tm))
1214     }
1215
1216     pub fn mk_ref(self, r: &'tcx Region, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
1217         self.mk_ty(TyRef(r, tm))
1218     }
1219
1220     pub fn mk_mut_ref(self, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
1221         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutMutable})
1222     }
1223
1224     pub fn mk_imm_ref(self, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
1225         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
1226     }
1227
1228     pub fn mk_mut_ptr(self, ty: Ty<'tcx>) -> Ty<'tcx> {
1229         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutMutable})
1230     }
1231
1232     pub fn mk_imm_ptr(self, ty: Ty<'tcx>) -> Ty<'tcx> {
1233         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
1234     }
1235
1236     pub fn mk_nil_ptr(self) -> Ty<'tcx> {
1237         self.mk_imm_ptr(self.mk_nil())
1238     }
1239
1240     pub fn mk_array(self, ty: Ty<'tcx>, n: usize) -> Ty<'tcx> {
1241         self.mk_ty(TyArray(ty, n))
1242     }
1243
1244     pub fn mk_slice(self, ty: Ty<'tcx>) -> Ty<'tcx> {
1245         self.mk_ty(TySlice(ty))
1246     }
1247
1248     pub fn mk_tup(self, ts: Vec<Ty<'tcx>>) -> Ty<'tcx> {
1249         self.mk_ty(TyTuple(self.mk_type_list(ts)))
1250     }
1251
1252     pub fn mk_nil(self) -> Ty<'tcx> {
1253         self.mk_tup(Vec::new())
1254     }
1255
1256     pub fn mk_bool(self) -> Ty<'tcx> {
1257         self.mk_ty(TyBool)
1258     }
1259
1260     pub fn mk_fn_def(self, def_id: DefId,
1261                      substs: &'tcx Substs<'tcx>,
1262                      fty: &'tcx BareFnTy<'tcx>) -> Ty<'tcx> {
1263         self.mk_ty(TyFnDef(def_id, substs, fty))
1264     }
1265
1266     pub fn mk_fn_ptr(self, fty: &'tcx BareFnTy<'tcx>) -> Ty<'tcx> {
1267         self.mk_ty(TyFnPtr(fty))
1268     }
1269
1270     pub fn mk_trait(self,
1271                     principal: ty::PolyTraitRef<'tcx>,
1272                     bounds: ExistentialBounds<'tcx>)
1273                     -> Ty<'tcx>
1274     {
1275         assert!(bound_list_is_sorted(&bounds.projection_bounds));
1276
1277         let inner = box TraitTy {
1278             principal: principal,
1279             bounds: bounds
1280         };
1281         self.mk_ty(TyTrait(inner))
1282     }
1283
1284     pub fn mk_projection(self,
1285                          trait_ref: TraitRef<'tcx>,
1286                          item_name: Name)
1287                          -> Ty<'tcx> {
1288         // take a copy of substs so that we own the vectors inside
1289         let inner = ProjectionTy { trait_ref: trait_ref, item_name: item_name };
1290         self.mk_ty(TyProjection(inner))
1291     }
1292
1293     pub fn mk_struct(self, def: AdtDef<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
1294         // take a copy of substs so that we own the vectors inside
1295         self.mk_ty(TyStruct(def, substs))
1296     }
1297
1298     pub fn mk_closure(self,
1299                       closure_id: DefId,
1300                       substs: &'tcx Substs<'tcx>,
1301                       tys: Vec<Ty<'tcx>>)
1302                       -> Ty<'tcx> {
1303         self.mk_closure_from_closure_substs(closure_id, ClosureSubsts {
1304             func_substs: substs,
1305             upvar_tys: self.mk_type_list(tys)
1306         })
1307     }
1308
1309     pub fn mk_closure_from_closure_substs(self,
1310                                           closure_id: DefId,
1311                                           closure_substs: ClosureSubsts<'tcx>)
1312                                           -> Ty<'tcx> {
1313         self.mk_ty(TyClosure(closure_id, closure_substs))
1314     }
1315
1316     pub fn mk_var(self, v: TyVid) -> Ty<'tcx> {
1317         self.mk_infer(TyVar(v))
1318     }
1319
1320     pub fn mk_int_var(self, v: IntVid) -> Ty<'tcx> {
1321         self.mk_infer(IntVar(v))
1322     }
1323
1324     pub fn mk_float_var(self, v: FloatVid) -> Ty<'tcx> {
1325         self.mk_infer(FloatVar(v))
1326     }
1327
1328     pub fn mk_infer(self, it: InferTy) -> Ty<'tcx> {
1329         self.mk_ty(TyInfer(it))
1330     }
1331
1332     pub fn mk_param(self,
1333                     space: subst::ParamSpace,
1334                     index: u32,
1335                     name: Name) -> Ty<'tcx> {
1336         self.mk_ty(TyParam(ParamTy { space: space, idx: index, name: name }))
1337     }
1338
1339     pub fn mk_self_type(self) -> Ty<'tcx> {
1340         self.mk_param(subst::SelfSpace, 0, keywords::SelfType.name())
1341     }
1342
1343     pub fn mk_param_from_def(self, def: &ty::TypeParameterDef) -> Ty<'tcx> {
1344         self.mk_param(def.space, def.index, def.name)
1345     }
1346
1347     pub fn trait_items(self, trait_did: DefId) -> Rc<Vec<ty::ImplOrTraitItem<'gcx>>> {
1348         self.trait_items_cache.memoize(trait_did, || {
1349             let def_ids = self.trait_item_def_ids(trait_did);
1350             Rc::new(def_ids.iter()
1351                            .map(|d| self.impl_or_trait_item(d.def_id()))
1352                            .collect())
1353         })
1354     }
1355
1356     /// Obtain the representation annotation for a struct definition.
1357     pub fn lookup_repr_hints(self, did: DefId) -> Rc<Vec<attr::ReprAttr>> {
1358         self.repr_hint_cache.memoize(did, || {
1359             Rc::new(if did.is_local() {
1360                 self.get_attrs(did).iter().flat_map(|meta| {
1361                     attr::find_repr_attrs(self.sess.diagnostic(), meta).into_iter()
1362                 }).collect()
1363             } else {
1364                 self.sess.cstore.repr_attrs(did)
1365             })
1366         })
1367     }
1368 }