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