src/librustc/middle/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 // FIXME: (@jroesch) @eddyb should remove this when he renames ctxt
  14 #![allow(non_camel_case_types)]
  15
  16 use dep_graph::{DepGraph, DepTrackingMap};
  17 use front::map as ast_map;
  18 use session::Session;
  19 use lint;
  20 use middle;
  21 use middle::cstore::CrateStore;
  22 use middle::def::DefMap;
  23 use middle::def_id::DefId;
  24 use middle::free_region::FreeRegionMap;
  25 use middle::region::RegionMaps;
  26 use middle::resolve_lifetime;
  27 use middle::stability;
  28 use middle::subst::{self, Subst, Substs};
  29 use middle::traits;
  30 use middle::ty::{self, TraitRef, Ty, TypeAndMut};
  31 use middle::ty::{TyS, TypeVariants};
  32 use middle::ty::{AdtDef, ClosureSubsts, ExistentialBounds, Region};
  33 use middle::ty::{FreevarMap};
  34 use middle::ty::{BareFnTy, InferTy, ParamTy, ProjectionTy, TraitTy};
  35 use middle::ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
  36 use middle::ty::TypeVariants::*;
  37 use middle::ty::maps;
  38 use util::common::MemoizationMap;
  39 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet};
  40 use util::nodemap::FnvHashMap;
  41
  42 use arena::TypedArena;
  43 use std::borrow::Borrow;
  44 use std::cell::{Cell, RefCell, Ref};
  45 use std::hash::{Hash, Hasher};
  46 use std::rc::Rc;
  47 use syntax::abi;
  48 use syntax::ast::{self, Name, NodeId};
  49 use syntax::attr;
  50 use syntax::parse::token::special_idents;
  51
  52 use rustc_front::hir;
  53
  54 /// Internal storage
  55 pub struct CtxtArenas<'tcx> {
  56     // internings
  57     type_: TypedArena<TyS<'tcx>>,
  58     substs: TypedArena<Substs<'tcx>>,
  59     bare_fn: TypedArena<BareFnTy<'tcx>>,
  60     region: TypedArena<Region>,
  61     stability: TypedArena<attr::Stability>,
  62
  63     // references
  64     trait_defs: TypedArena<ty::TraitDef<'tcx>>,
  65     adt_defs: TypedArena<ty::AdtDefData<'tcx, 'tcx>>,
  66 }
  67
  68 impl<'tcx> CtxtArenas<'tcx> {
  69     pub fn new() -> CtxtArenas<'tcx> {
  70         CtxtArenas {
  71             type_: TypedArena::new(),
  72             substs: TypedArena::new(),
  73             bare_fn: TypedArena::new(),
  74             region: TypedArena::new(),
  75             stability: TypedArena::new(),
  76
  77             trait_defs: TypedArena::new(),
  78             adt_defs: TypedArena::new()
  79         }
  80     }
  81 }
  82
  83 pub struct CommonTypes<'tcx> {
  84     pub bool: Ty<'tcx>,
  85     pub char: Ty<'tcx>,
  86     pub isize: Ty<'tcx>,
  87     pub i8: Ty<'tcx>,
  88     pub i16: Ty<'tcx>,
  89     pub i32: Ty<'tcx>,
  90     pub i64: Ty<'tcx>,
  91     pub usize: Ty<'tcx>,
  92     pub u8: Ty<'tcx>,
  93     pub u16: Ty<'tcx>,
  94     pub u32: Ty<'tcx>,
  95     pub u64: Ty<'tcx>,
  96     pub f32: Ty<'tcx>,
  97     pub f64: Ty<'tcx>,
  98     pub err: Ty<'tcx>,
  99 }
 100
 101 pub struct Tables<'tcx> {
 102     /// Stores the types for various nodes in the AST.  Note that this table
 103     /// is not guaranteed to be populated until after typeck.  See
 104     /// typeck::check::fn_ctxt for details.
 105     pub node_types: NodeMap<Ty<'tcx>>,
 106
 107     /// Stores the type parameters which were substituted to obtain the type
 108     /// of this node.  This only applies to nodes that refer to entities
 109     /// parameterized by type parameters, such as generic fns, types, or
 110     /// other items.
 111     pub item_substs: NodeMap<ty::ItemSubsts<'tcx>>,
 112
 113     pub adjustments: NodeMap<ty::adjustment::AutoAdjustment<'tcx>>,
 114
 115     pub method_map: ty::MethodMap<'tcx>,
 116
 117     /// Borrows
 118     pub upvar_capture_map: ty::UpvarCaptureMap,
 119
 120     /// Records the type of each closure. The def ID is the ID of the
 121     /// expression defining the closure.
 122     pub closure_tys: DefIdMap<ty::ClosureTy<'tcx>>,
 123
 124     /// Records the type of each closure. The def ID is the ID of the
 125     /// expression defining the closure.
 126     pub closure_kinds: DefIdMap<ty::ClosureKind>,
 127
 128     /// For each fn, records the "liberated" types of its arguments
 129     /// and return type. Liberated means that all bound regions
 130     /// (including late-bound regions) are replaced with free
 131     /// equivalents. This table is not used in trans (since regions
 132     /// are erased there) and hence is not serialized to metadata.
 133     pub liberated_fn_sigs: NodeMap<ty::FnSig<'tcx>>,
 134 }
 135
 136 impl<'tcx> Tables<'tcx> {
 137     pub fn empty() -> Tables<'tcx> {
 138         Tables {
 139             node_types: FnvHashMap(),
 140             item_substs: NodeMap(),
 141             adjustments: NodeMap(),
 142             method_map: FnvHashMap(),
 143             upvar_capture_map: FnvHashMap(),
 144             closure_tys: DefIdMap(),
 145             closure_kinds: DefIdMap(),
 146             liberated_fn_sigs: NodeMap(),
 147         }
 148     }
 149
 150     pub fn closure_kind(this: &RefCell<Self>,
 151                         tcx: &ty::ctxt<'tcx>,
 152                         def_id: DefId)
 153                         -> ty::ClosureKind {
 154         // If this is a local def-id, it should be inserted into the
 155         // tables by typeck; else, it will be retreived from
 156         // the external crate metadata.
 157         if let Some(&kind) = this.borrow().closure_kinds.get(&def_id) {
 158             return kind;
 159         }
 160
 161         let kind = tcx.sess.cstore.closure_kind(tcx, def_id);
 162         this.borrow_mut().closure_kinds.insert(def_id, kind);
 163         kind
 164     }
 165
 166     pub fn closure_type(this: &RefCell<Self>,
 167                         tcx: &ty::ctxt<'tcx>,
 168                         def_id: DefId,
 169                         substs: &ClosureSubsts<'tcx>)
 170                         -> ty::ClosureTy<'tcx>
 171     {
 172         // If this is a local def-id, it should be inserted into the
 173         // tables by typeck; else, it will be retreived from
 174         // the external crate metadata.
 175         if let Some(ty) = this.borrow().closure_tys.get(&def_id) {
 176             return ty.subst(tcx, &substs.func_substs);
 177         }
 178
 179         let ty = tcx.sess.cstore.closure_ty(tcx, def_id);
 180         this.borrow_mut().closure_tys.insert(def_id, ty.clone());
 181         ty.subst(tcx, &substs.func_substs)
 182     }
 183 }
 184
 185 impl<'tcx> CommonTypes<'tcx> {
 186     fn new(arena: &'tcx TypedArena<TyS<'tcx>>,
 187            interner: &RefCell<FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>>)
 188            -> CommonTypes<'tcx>
 189     {
 190         let mk = |sty| ctxt::intern_ty(arena, interner, sty);
 191         CommonTypes {
 192             bool: mk(TyBool),
 193             char: mk(TyChar),
 194             err: mk(TyError),
 195             isize: mk(TyInt(ast::TyIs)),
 196             i8: mk(TyInt(ast::TyI8)),
 197             i16: mk(TyInt(ast::TyI16)),
 198             i32: mk(TyInt(ast::TyI32)),
 199             i64: mk(TyInt(ast::TyI64)),
 200             usize: mk(TyUint(ast::TyUs)),
 201             u8: mk(TyUint(ast::TyU8)),
 202             u16: mk(TyUint(ast::TyU16)),
 203             u32: mk(TyUint(ast::TyU32)),
 204             u64: mk(TyUint(ast::TyU64)),
 205             f32: mk(TyFloat(ast::TyF32)),
 206             f64: mk(TyFloat(ast::TyF64)),
 207         }
 208     }
 209 }
 210
 211 /// The data structure to keep track of all the information that typechecker
 212 /// generates so that so that it can be reused and doesn't have to be redone
 213 /// later on.
 214 pub struct ctxt<'tcx> {
 215     /// The arenas that types etc are allocated from.
 216     arenas: &'tcx CtxtArenas<'tcx>,
 217
 218     /// Specifically use a speedy hash algorithm for this hash map, it's used
 219     /// quite often.
 220     // FIXME(eddyb) use a FnvHashSet<InternedTy<'tcx>> when equivalent keys can
 221     // queried from a HashSet.
 222     interner: RefCell<FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>>,
 223
 224     // FIXME as above, use a hashset if equivalent elements can be queried.
 225     substs_interner: RefCell<FnvHashMap<&'tcx Substs<'tcx>, &'tcx Substs<'tcx>>>,
 226     bare_fn_interner: RefCell<FnvHashMap<&'tcx BareFnTy<'tcx>, &'tcx BareFnTy<'tcx>>>,
 227     region_interner: RefCell<FnvHashMap<&'tcx Region, &'tcx Region>>,
 228     stability_interner: RefCell<FnvHashMap<&'tcx attr::Stability, &'tcx attr::Stability>>,
 229
 230     pub dep_graph: DepGraph,
 231
 232     /// Common types, pre-interned for your convenience.
 233     pub types: CommonTypes<'tcx>,
 234
 235     pub sess: &'tcx Session,
 236     pub def_map: RefCell<DefMap>,
 237
 238     pub named_region_map: resolve_lifetime::NamedRegionMap,
 239
 240     pub region_maps: RegionMaps,
 241
 242     // For each fn declared in the local crate, type check stores the
 243     // free-region relationships that were deduced from its where
 244     // clauses and parameter types. These are then read-again by
 245     // borrowck. (They are not used during trans, and hence are not
 246     // serialized or needed for cross-crate fns.)
 247     free_region_maps: RefCell<NodeMap<FreeRegionMap>>,
 248     // FIXME: jroesch make this a refcell
 249
 250     pub tables: RefCell<Tables<'tcx>>,
 251
 252     /// Maps from a trait item to the trait item "descriptor"
 253     pub impl_or_trait_items: RefCell<DepTrackingMap<maps::ImplOrTraitItems<'tcx>>>,
 254
 255     /// Maps from a trait def-id to a list of the def-ids of its trait items
 256     pub trait_item_def_ids: RefCell<DepTrackingMap<maps::TraitItemDefIds<'tcx>>>,
 257
 258     /// A cache for the trait_items() routine; note that the routine
 259     /// itself pushes the `TraitItems` dependency node.
 260     trait_items_cache: RefCell<DepTrackingMap<maps::TraitItems<'tcx>>>,
 261
 262     pub impl_trait_refs: RefCell<DepTrackingMap<maps::ImplTraitRefs<'tcx>>>,
 263     pub trait_defs: RefCell<DepTrackingMap<maps::TraitDefs<'tcx>>>,
 264     pub adt_defs: RefCell<DepTrackingMap<maps::AdtDefs<'tcx>>>,
 265
 266     /// Maps from the def-id of an item (trait/struct/enum/fn) to its
 267     /// associated predicates.
 268     pub predicates: RefCell<DepTrackingMap<maps::Predicates<'tcx>>>,
 269
 270     /// Maps from the def-id of a trait to the list of
 271     /// super-predicates. This is a subset of the full list of
 272     /// predicates. We store these in a separate map because we must
 273     /// evaluate them even during type conversion, often before the
 274     /// full predicates are available (note that supertraits have
 275     /// additional acyclicity requirements).
 276     pub super_predicates: RefCell<DepTrackingMap<maps::Predicates<'tcx>>>,
 277
 278     pub map: ast_map::Map<'tcx>,
 279
 280     // Records the free variables refrenced by every closure
 281     // expression. Do not track deps for this, just recompute it from
 282     // scratch every time.
 283     pub freevars: RefCell<FreevarMap>,
 284
 285     // Records the type of every item.
 286     pub tcache: RefCell<DepTrackingMap<maps::Tcache<'tcx>>>,
 287
 288     // Internal cache for metadata decoding. No need to track deps on this.
 289     pub rcache: RefCell<FnvHashMap<ty::CReaderCacheKey, Ty<'tcx>>>,
 290
 291     // Cache for the type-contents routine. FIXME -- track deps?
 292     pub tc_cache: RefCell<FnvHashMap<Ty<'tcx>, ty::contents::TypeContents>>,
 293
 294     // Cache for various types within a method body and so forth.
 295     //
 296     // FIXME this should be made local to typeck, but it is currently used by one lint
 297     pub ast_ty_to_ty_cache: RefCell<NodeMap<Ty<'tcx>>>,
 298
 299     // FIXME no dep tracking, but we should be able to remove this
 300     pub ty_param_defs: RefCell<NodeMap<ty::TypeParameterDef<'tcx>>>,
 301
 302     // FIXME dep tracking -- should be harmless enough
 303     pub normalized_cache: RefCell<FnvHashMap<Ty<'tcx>, Ty<'tcx>>>,
 304
 305     pub lang_items: middle::lang_items::LanguageItems,
 306
 307     /// Maps from def-id of a type or region parameter to its
 308     /// (inferred) variance.
 309     pub item_variance_map: RefCell<DepTrackingMap<maps::ItemVariances<'tcx>>>,
 310
 311     /// True if the variance has been computed yet; false otherwise.
 312     pub variance_computed: Cell<bool>,
 313
 314     /// Maps a DefId of a type to a list of its inherent impls.
 315     /// Contains implementations of methods that are inherent to a type.
 316     /// Methods in these implementations don't need to be exported.
 317     pub inherent_impls: RefCell<DepTrackingMap<maps::InherentImpls<'tcx>>>,
 318
 319     /// Maps a DefId of an impl to a list of its items.
 320     /// Note that this contains all of the impls that we know about,
 321     /// including ones in other crates. It's not clear that this is the best
 322     /// way to do it.
 323     pub impl_items: RefCell<DepTrackingMap<maps::ImplItems<'tcx>>>,
 324
 325     /// Set of used unsafe nodes (functions or blocks). Unsafe nodes not
 326     /// present in this set can be warned about.
 327     pub used_unsafe: RefCell<NodeSet>,
 328
 329     /// Set of nodes which mark locals as mutable which end up getting used at
 330     /// some point. Local variable definitions not in this set can be warned
 331     /// about.
 332     pub used_mut_nodes: RefCell<NodeSet>,
 333
 334     /// The set of external nominal types whose implementations have been read.
 335     /// This is used for lazy resolution of methods.
 336     pub populated_external_types: RefCell<DefIdSet>,
 337
 338     /// The set of external primitive types whose implementations have been read.
 339     /// FIXME(arielb1): why is this separate from populated_external_types?
 340     pub populated_external_primitive_impls: RefCell<DefIdSet>,
 341
 342     /// These caches are used by const_eval when decoding external constants.
 343     pub extern_const_statics: RefCell<DefIdMap<NodeId>>,
 344     pub extern_const_fns: RefCell<DefIdMap<NodeId>>,
 345
 346     pub node_lint_levels: RefCell<FnvHashMap<(NodeId, lint::LintId),
 347                                               lint::LevelSource>>,
 348
 349     /// The types that must be asserted to be the same size for `transmute`
 350     /// to be valid. We gather up these restrictions in the intrinsicck pass
 351     /// and check them in trans.
 352     pub transmute_restrictions: RefCell<Vec<ty::TransmuteRestriction<'tcx>>>,
 353
 354     /// Maps any item's def-id to its stability index.
 355     pub stability: RefCell<stability::Index<'tcx>>,
 356
 357     /// Caches the results of trait selection. This cache is used
 358     /// for things that do not have to do with the parameters in scope.
 359     pub selection_cache: traits::SelectionCache<'tcx>,
 360
 361     /// Caches the results of trait evaluation. This cache is used
 362     /// for things that do not have to do with the parameters in scope.
 363     /// Merge this with `selection_cache`?
 364     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 365
 366     /// A set of predicates that have been fulfilled *somewhere*.
 367     /// This is used to avoid duplicate work. Predicates are only
 368     /// added to this set when they mention only "global" names
 369     /// (i.e., no type or lifetime parameters).
 370     pub fulfilled_predicates: RefCell<traits::GlobalFulfilledPredicates<'tcx>>,
 371
 372     /// Caches the representation hints for struct definitions.
 373     repr_hint_cache: RefCell<DepTrackingMap<maps::ReprHints<'tcx>>>,
 374
 375     /// Maps Expr NodeId's to their constant qualification.
 376     pub const_qualif_map: RefCell<NodeMap<middle::const_qualif::ConstQualif>>,
 377
 378     /// Caches CoerceUnsized kinds for impls on custom types.
 379     pub custom_coerce_unsized_kinds: RefCell<DefIdMap<ty::adjustment::CustomCoerceUnsized>>,
 380
 381     /// Maps a cast expression to its kind. This is keyed on the
 382     /// *from* expression of the cast, not the cast itself.
 383     pub cast_kinds: RefCell<NodeMap<ty::cast::CastKind>>,
 384
 385     /// Maps Fn items to a collection of fragment infos.
 386     ///
 387     /// The main goal is to identify data (each of which may be moved
 388     /// or assigned) whose subparts are not moved nor assigned
 389     /// (i.e. their state is *unfragmented*) and corresponding ast
 390     /// nodes where the path to that data is moved or assigned.
 391     ///
 392     /// In the long term, unfragmented values will have their
 393     /// destructor entirely driven by a single stack-local drop-flag,
 394     /// and their parents, the collections of the unfragmented values
 395     /// (or more simply, "fragmented values"), are mapped to the
 396     /// corresponding collections of stack-local drop-flags.
 397     ///
 398     /// (However, in the short term that is not the case; e.g. some
 399     /// unfragmented paths still need to be zeroed, namely when they
 400     /// reference parent data from an outer scope that was not
 401     /// entirely moved, and therefore that needs to be zeroed so that
 402     /// we do not get double-drop when we hit the end of the parent
 403     /// scope.)
 404     ///
 405     /// Also: currently the table solely holds keys for node-ids of
 406     /// unfragmented values (see `FragmentInfo` enum definition), but
 407     /// longer-term we will need to also store mappings from
 408     /// fragmented data to the set of unfragmented pieces that
 409     /// constitute it.
 410     pub fragment_infos: RefCell<DefIdMap<Vec<ty::FragmentInfo>>>,
 411 }
 412
 413 impl<'tcx> ctxt<'tcx> {
 414     pub fn type_parameter_def(&self,
 415                               node_id: NodeId)
 416                               -> ty::TypeParameterDef<'tcx>
 417     {
 418         self.ty_param_defs.borrow().get(&node_id).unwrap().clone()
 419     }
 420
 421     pub fn node_types(&self) -> Ref<NodeMap<Ty<'tcx>>> {
 422         fn projection<'a, 'tcx>(tables: &'a Tables<'tcx>) -> &'a NodeMap<Ty<'tcx>> {
 423             &tables.node_types
 424         }
 425
 426         Ref::map(self.tables.borrow(), projection)
 427     }
 428
 429     pub fn node_type_insert(&self, id: NodeId, ty: Ty<'tcx>) {
 430         self.tables.borrow_mut().node_types.insert(id, ty);
 431     }
 432
 433     pub fn intern_trait_def(&self, def: ty::TraitDef<'tcx>)
 434                             -> &'tcx ty::TraitDef<'tcx> {
 435         let did = def.trait_ref.def_id;
 436         let interned = self.arenas.trait_defs.alloc(def);
 437         if let Some(prev) = self.trait_defs.borrow_mut().insert(did, interned) {
 438             self.sess.bug(&format!("Tried to overwrite interned TraitDef: {:?}",
 439                                    prev))
 440         }
 441         interned
 442     }
 443
 444     pub fn alloc_trait_def(&self, def: ty::TraitDef<'tcx>)
 445                            -> &'tcx ty::TraitDef<'tcx> {
 446         self.arenas.trait_defs.alloc(def)
 447     }
 448
 449     pub fn intern_adt_def(&self,
 450                           did: DefId,
 451                           kind: ty::AdtKind,
 452                           variants: Vec<ty::VariantDefData<'tcx, 'tcx>>)
 453                           -> ty::AdtDefMaster<'tcx> {
 454         let def = ty::AdtDefData::new(self, did, kind, variants);
 455         let interned = self.arenas.adt_defs.alloc(def);
 456         // this will need a transmute when reverse-variance is removed
 457         if let Some(prev) = self.adt_defs.borrow_mut().insert(did, interned) {
 458             self.sess.bug(&format!("Tried to overwrite interned AdtDef: {:?}",
 459                                    prev))
 460         }
 461         interned
 462     }
 463
 464     pub fn intern_stability(&self, stab: attr::Stability) -> &'tcx attr::Stability {
 465         if let Some(st) = self.stability_interner.borrow().get(&stab) {
 466             return st;
 467         }
 468
 469         let interned = self.arenas.stability.alloc(stab);
 470         if let Some(prev) = self.stability_interner
 471                                 .borrow_mut()
 472                                 .insert(interned, interned) {
 473             self.sess.bug(&format!("Tried to overwrite interned Stability: {:?}",
 474                                    prev))
 475         }
 476         interned
 477     }
 478
 479     pub fn store_free_region_map(&self, id: NodeId, map: FreeRegionMap) {
 480         if self.free_region_maps.borrow_mut().insert(id, map).is_some() {
 481             self.sess.bug(&format!("Tried to overwrite interned FreeRegionMap for NodeId {:?}",
 482                                    id))
 483         }
 484     }
 485
 486     pub fn free_region_map(&self, id: NodeId) -> FreeRegionMap {
 487         self.free_region_maps.borrow()[&id].clone()
 488     }
 489
 490     pub fn lift<T: ?Sized + Lift<'tcx>>(&self, value: &T) -> Option<T::Lifted> {
 491         value.lift_to_tcx(self)
 492     }
 493
 494     /// Create a type context and call the closure with a `&ty::ctxt` reference
 495     /// to the context. The closure enforces that the type context and any interned
 496     /// value (types, substs, etc.) can only be used while `ty::tls` has a valid
 497     /// reference to the context, to allow formatting values that need it.
 498     pub fn create_and_enter<F, R>(s: &'tcx Session,
 499                                  arenas: &'tcx CtxtArenas<'tcx>,
 500                                  def_map: RefCell<DefMap>,
 501                                  named_region_map: resolve_lifetime::NamedRegionMap,
 502                                  map: ast_map::Map<'tcx>,
 503                                  freevars: FreevarMap,
 504                                  region_maps: RegionMaps,
 505                                  lang_items: middle::lang_items::LanguageItems,
 506                                  stability: stability::Index<'tcx>,
 507                                  f: F) -> R
 508                                  where F: FnOnce(&ctxt<'tcx>) -> R
 509     {
 510         let interner = RefCell::new(FnvHashMap());
 511         let common_types = CommonTypes::new(&arenas.type_, &interner);
 512         let dep_graph = DepGraph::new(s.opts.incremental_compilation);
 513         let fulfilled_predicates = traits::GlobalFulfilledPredicates::new(dep_graph.clone());
 514         tls::enter(ctxt {
 515             arenas: arenas,
 516             interner: interner,
 517             substs_interner: RefCell::new(FnvHashMap()),
 518             bare_fn_interner: RefCell::new(FnvHashMap()),
 519             region_interner: RefCell::new(FnvHashMap()),
 520             stability_interner: RefCell::new(FnvHashMap()),
 521             dep_graph: dep_graph.clone(),
 522             types: common_types,
 523             named_region_map: named_region_map,
 524             region_maps: region_maps,
 525             free_region_maps: RefCell::new(FnvHashMap()),
 526             item_variance_map: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 527             variance_computed: Cell::new(false),
 528             sess: s,
 529             def_map: def_map,
 530             tables: RefCell::new(Tables::empty()),
 531             impl_trait_refs: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 532             trait_defs: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 533             adt_defs: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 534             predicates: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 535             super_predicates: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 536             fulfilled_predicates: RefCell::new(fulfilled_predicates),
 537             map: map,
 538             freevars: RefCell::new(freevars),
 539             tcache: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 540             rcache: RefCell::new(FnvHashMap()),
 541             tc_cache: RefCell::new(FnvHashMap()),
 542             ast_ty_to_ty_cache: RefCell::new(NodeMap()),
 543             impl_or_trait_items: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 544             trait_item_def_ids: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 545             trait_items_cache: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 546             ty_param_defs: RefCell::new(NodeMap()),
 547             normalized_cache: RefCell::new(FnvHashMap()),
 548             lang_items: lang_items,
 549             inherent_impls: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 550             impl_items: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 551             used_unsafe: RefCell::new(NodeSet()),
 552             used_mut_nodes: RefCell::new(NodeSet()),
 553             populated_external_types: RefCell::new(DefIdSet()),
 554             populated_external_primitive_impls: RefCell::new(DefIdSet()),
 555             extern_const_statics: RefCell::new(DefIdMap()),
 556             extern_const_fns: RefCell::new(DefIdMap()),
 557             node_lint_levels: RefCell::new(FnvHashMap()),
 558             transmute_restrictions: RefCell::new(Vec::new()),
 559             stability: RefCell::new(stability),
 560             selection_cache: traits::SelectionCache::new(),
 561             evaluation_cache: traits::EvaluationCache::new(),
 562             repr_hint_cache: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
 563             const_qualif_map: RefCell::new(NodeMap()),
 564             custom_coerce_unsized_kinds: RefCell::new(DefIdMap()),
 565             cast_kinds: RefCell::new(NodeMap()),
 566             fragment_infos: RefCell::new(DefIdMap()),
 567        }, f)
 568     }
 569 }
 570
 571 /// A trait implemented for all X<'a> types which can be safely and
 572 /// efficiently converted to X<'tcx> as long as they are part of the
 573 /// provided ty::ctxt<'tcx>.
 574 /// This can be done, for example, for Ty<'tcx> or &'tcx Substs<'tcx>
 575 /// by looking them up in their respective interners.
 576 /// None is returned if the value or one of the components is not part
 577 /// of the provided context.
 578 /// For Ty, None can be returned if either the type interner doesn't
 579 /// contain the TypeVariants key or if the address of the interned
 580 /// pointer differs. The latter case is possible if a primitive type,
 581 /// e.g. `()` or `u8`, was interned in a different context.
 582 pub trait Lift<'tcx> {
 583     type Lifted;
 584     fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Self::Lifted>;
 585 }
 586
 587 impl<'a, 'tcx> Lift<'tcx> for Ty<'a> {
 588     type Lifted = Ty<'tcx>;
 589     fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Ty<'tcx>> {
 590         if let Some(&ty) = tcx.interner.borrow().get(&self.sty) {
 591             if *self as *const _ == ty as *const _ {
 592                 return Some(ty);
 593             }
 594         }
 595         None
 596     }
 597 }
 598
 599 impl<'a, 'tcx> Lift<'tcx> for &'a Substs<'a> {
 600     type Lifted = &'tcx Substs<'tcx>;
 601     fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<&'tcx Substs<'tcx>> {
 602         if let Some(&substs) = tcx.substs_interner.borrow().get(*self) {
 603             if *self as *const _ == substs as *const _ {
 604                 return Some(substs);
 605             }
 606         }
 607         None
 608     }
 609 }
 610
 611
 612 pub mod tls {
 613     use middle::ty;
 614
 615     use std::fmt;
 616     use syntax::codemap;
 617
 618     /// Marker type used for the scoped TLS slot.
 619     /// The type context cannot be used directly because the scoped TLS
 620     /// in libstd doesn't allow types generic over lifetimes.
 621     struct ThreadLocalTyCx;
 622
 623     scoped_thread_local!(static TLS_TCX: ThreadLocalTyCx);
 624
 625     fn span_debug(span: codemap::Span, f: &mut fmt::Formatter) -> fmt::Result {
 626         with(|tcx| {
 627             write!(f, "{}", tcx.sess.codemap().span_to_string(span))
 628         })
 629     }
 630
 631     pub fn enter<'tcx, F: FnOnce(&ty::ctxt<'tcx>) -> R, R>(tcx: ty::ctxt<'tcx>, f: F) -> R {
 632         codemap::SPAN_DEBUG.with(|span_dbg| {
 633             let original_span_debug = span_dbg.get();
 634             span_dbg.set(span_debug);
 635             let tls_ptr = &tcx as *const _ as *const ThreadLocalTyCx;
 636             let result = TLS_TCX.set(unsafe { &*tls_ptr }, || f(&tcx));
 637             span_dbg.set(original_span_debug);
 638             result
 639         })
 640     }
 641
 642     pub fn with<F: FnOnce(&ty::ctxt) -> R, R>(f: F) -> R {
 643         TLS_TCX.with(|tcx| f(unsafe { &*(tcx as *const _ as *const ty::ctxt) }))
 644     }
 645
 646     pub fn with_opt<F: FnOnce(Option<&ty::ctxt>) -> R, R>(f: F) -> R {
 647         if TLS_TCX.is_set() {
 648             with(|v| f(Some(v)))
 649         } else {
 650             f(None)
 651         }
 652     }
 653 }
 654
 655 macro_rules! sty_debug_print {
 656     ($ctxt: expr, $($variant: ident),*) => {{
 657         // curious inner module to allow variant names to be used as
 658         // variable names.
 659         #[allow(non_snake_case)]
 660         mod inner {
 661             use middle::ty;
 662             #[derive(Copy, Clone)]
 663             struct DebugStat {
 664                 total: usize,
 665                 region_infer: usize,
 666                 ty_infer: usize,
 667                 both_infer: usize,
 668             }
 669
 670             pub fn go(tcx: &ty::ctxt) {
 671                 let mut total = DebugStat {
 672                     total: 0,
 673                     region_infer: 0, ty_infer: 0, both_infer: 0,
 674                 };
 675                 $(let mut $variant = total;)*
 676
 677
 678                 for (_, t) in tcx.interner.borrow().iter() {
 679                     let variant = match t.sty {
 680                         ty::TyBool | ty::TyChar | ty::TyInt(..) | ty::TyUint(..) |
 681                             ty::TyFloat(..) | ty::TyStr => continue,
 682                         ty::TyError => /* unimportant */ continue,
 683                         $(ty::$variant(..) => &mut $variant,)*
 684                     };
 685                     let region = t.flags.get().intersects(ty::TypeFlags::HAS_RE_INFER);
 686                     let ty = t.flags.get().intersects(ty::TypeFlags::HAS_TY_INFER);
 687
 688                     variant.total += 1;
 689                     total.total += 1;
 690                     if region { total.region_infer += 1; variant.region_infer += 1 }
 691                     if ty { total.ty_infer += 1; variant.ty_infer += 1 }
 692                     if region && ty { total.both_infer += 1; variant.both_infer += 1 }
 693                 }
 694                 println!("Ty interner             total           ty region  both");
 695                 $(println!("    {:18}: {uses:6} {usespc:4.1}%, \
 696 {ty:4.1}% {region:5.1}% {both:4.1}%",
 697                            stringify!($variant),
 698                            uses = $variant.total,
 699                            usespc = $variant.total as f64 * 100.0 / total.total as f64,
 700                            ty = $variant.ty_infer as f64 * 100.0  / total.total as f64,
 701                            region = $variant.region_infer as f64 * 100.0  / total.total as f64,
 702                            both = $variant.both_infer as f64 * 100.0  / total.total as f64);
 703                   )*
 704                 println!("                  total {uses:6}        \
 705 {ty:4.1}% {region:5.1}% {both:4.1}%",
 706                          uses = total.total,
 707                          ty = total.ty_infer as f64 * 100.0  / total.total as f64,
 708                          region = total.region_infer as f64 * 100.0  / total.total as f64,
 709                          both = total.both_infer as f64 * 100.0  / total.total as f64)
 710             }
 711         }
 712
 713         inner::go($ctxt)
 714     }}
 715 }
 716
 717 impl<'tcx> ctxt<'tcx> {
 718     pub fn print_debug_stats(&self) {
 719         sty_debug_print!(
 720             self,
 721             TyEnum, TyBox, TyArray, TySlice, TyRawPtr, TyRef, TyBareFn, TyTrait,
 722             TyStruct, TyClosure, TyTuple, TyParam, TyInfer, TyProjection);
 723
 724         println!("Substs interner: #{}", self.substs_interner.borrow().len());
 725         println!("BareFnTy interner: #{}", self.bare_fn_interner.borrow().len());
 726         println!("Region interner: #{}", self.region_interner.borrow().len());
 727         println!("Stability interner: #{}", self.stability_interner.borrow().len());
 728     }
 729 }
 730
 731
 732 /// An entry in the type interner.
 733 pub struct InternedTy<'tcx> {
 734     ty: Ty<'tcx>
 735 }
 736
 737 // NB: An InternedTy compares and hashes as a sty.
 738 impl<'tcx> PartialEq for InternedTy<'tcx> {
 739     fn eq(&self, other: &InternedTy<'tcx>) -> bool {
 740         self.ty.sty == other.ty.sty
 741     }
 742 }
 743
 744 impl<'tcx> Eq for InternedTy<'tcx> {}
 745
 746 impl<'tcx> Hash for InternedTy<'tcx> {
 747     fn hash<H: Hasher>(&self, s: &mut H) {
 748         self.ty.sty.hash(s)
 749     }
 750 }
 751
 752 impl<'tcx> Borrow<TypeVariants<'tcx>> for InternedTy<'tcx> {
 753     fn borrow<'a>(&'a self) -> &'a TypeVariants<'tcx> {
 754         &self.ty.sty
 755     }
 756 }
 757
 758 fn bound_list_is_sorted(bounds: &[ty::PolyProjectionPredicate]) -> bool {
 759     bounds.is_empty() ||
 760         bounds[1..].iter().enumerate().all(
 761             |(index, bound)| bounds[index].sort_key() <= bound.sort_key())
 762 }
 763
 764 impl<'tcx> ctxt<'tcx> {
 765     // Type constructors
 766     pub fn mk_substs(&self, substs: Substs<'tcx>) -> &'tcx Substs<'tcx> {
 767         if let Some(substs) = self.substs_interner.borrow().get(&substs) {
 768             return *substs;
 769         }
 770
 771         let substs = self.arenas.substs.alloc(substs);
 772         self.substs_interner.borrow_mut().insert(substs, substs);
 773         substs
 774     }
 775
 776     /// Create an unsafe fn ty based on a safe fn ty.
 777     pub fn safe_to_unsafe_fn_ty(&self, bare_fn: &BareFnTy<'tcx>) -> Ty<'tcx> {
 778         assert_eq!(bare_fn.unsafety, hir::Unsafety::Normal);
 779         let unsafe_fn_ty_a = self.mk_bare_fn(ty::BareFnTy {
 780             unsafety: hir::Unsafety::Unsafe,
 781             abi: bare_fn.abi,
 782             sig: bare_fn.sig.clone()
 783         });
 784         self.mk_fn(None, unsafe_fn_ty_a)
 785     }
 786
 787     pub fn mk_bare_fn(&self, bare_fn: BareFnTy<'tcx>) -> &'tcx BareFnTy<'tcx> {
 788         if let Some(bare_fn) = self.bare_fn_interner.borrow().get(&bare_fn) {
 789             return *bare_fn;
 790         }
 791
 792         let bare_fn = self.arenas.bare_fn.alloc(bare_fn);
 793         self.bare_fn_interner.borrow_mut().insert(bare_fn, bare_fn);
 794         bare_fn
 795     }
 796
 797     pub fn mk_region(&self, region: Region) -> &'tcx Region {
 798         if let Some(region) = self.region_interner.borrow().get(&region) {
 799             return *region;
 800         }
 801
 802         let region = self.arenas.region.alloc(region);
 803         self.region_interner.borrow_mut().insert(region, region);
 804         region
 805     }
 806
 807     fn intern_ty(type_arena: &'tcx TypedArena<TyS<'tcx>>,
 808                  interner: &RefCell<FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>>,
 809                  st: TypeVariants<'tcx>)
 810                  -> Ty<'tcx> {
 811         let ty: Ty /* don't be &mut TyS */ = {
 812             let mut interner = interner.borrow_mut();
 813             match interner.get(&st) {
 814                 Some(ty) => return *ty,
 815                 _ => ()
 816             }
 817
 818             let flags = super::flags::FlagComputation::for_sty(&st);
 819
 820             let ty = match () {
 821                 () => type_arena.alloc(TyS { sty: st,
 822                                              flags: Cell::new(flags.flags),
 823                                              region_depth: flags.depth, }),
 824             };
 825
 826             interner.insert(InternedTy { ty: ty }, ty);
 827             ty
 828         };
 829
 830         debug!("Interned type: {:?} Pointer: {:?}",
 831             ty, ty as *const TyS);
 832         ty
 833     }
 834
 835     // Interns a type/name combination, stores the resulting box in cx.interner,
 836     // and returns the box as cast to an unsafe ptr (see comments for Ty above).
 837     pub fn mk_ty(&self, st: TypeVariants<'tcx>) -> Ty<'tcx> {
 838         ctxt::intern_ty(&self.arenas.type_, &self.interner, st)
 839     }
 840
 841     pub fn mk_mach_int(&self, tm: ast::IntTy) -> Ty<'tcx> {
 842         match tm {
 843             ast::TyIs   => self.types.isize,
 844             ast::TyI8   => self.types.i8,
 845             ast::TyI16  => self.types.i16,
 846             ast::TyI32  => self.types.i32,
 847             ast::TyI64  => self.types.i64,
 848         }
 849     }
 850
 851     pub fn mk_mach_uint(&self, tm: ast::UintTy) -> Ty<'tcx> {
 852         match tm {
 853             ast::TyUs   => self.types.usize,
 854             ast::TyU8   => self.types.u8,
 855             ast::TyU16  => self.types.u16,
 856             ast::TyU32  => self.types.u32,
 857             ast::TyU64  => self.types.u64,
 858         }
 859     }
 860
 861     pub fn mk_mach_float(&self, tm: ast::FloatTy) -> Ty<'tcx> {
 862         match tm {
 863             ast::TyF32  => self.types.f32,
 864             ast::TyF64  => self.types.f64,
 865         }
 866     }
 867
 868     pub fn mk_str(&self) -> Ty<'tcx> {
 869         self.mk_ty(TyStr)
 870     }
 871
 872     pub fn mk_static_str(&self) -> Ty<'tcx> {
 873         self.mk_imm_ref(self.mk_region(ty::ReStatic), self.mk_str())
 874     }
 875
 876     pub fn mk_enum(&self, def: AdtDef<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
 877         // take a copy of substs so that we own the vectors inside
 878         self.mk_ty(TyEnum(def, substs))
 879     }
 880
 881     pub fn mk_box(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 882         self.mk_ty(TyBox(ty))
 883     }
 884
 885     pub fn mk_ptr(&self, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
 886         self.mk_ty(TyRawPtr(tm))
 887     }
 888
 889     pub fn mk_ref(&self, r: &'tcx Region, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
 890         self.mk_ty(TyRef(r, tm))
 891     }
 892
 893     pub fn mk_mut_ref(&self, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
 894         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutMutable})
 895     }
 896
 897     pub fn mk_imm_ref(&self, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
 898         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
 899     }
 900
 901     pub fn mk_mut_ptr(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 902         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutMutable})
 903     }
 904
 905     pub fn mk_imm_ptr(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 906         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
 907     }
 908
 909     pub fn mk_nil_ptr(&self) -> Ty<'tcx> {
 910         self.mk_imm_ptr(self.mk_nil())
 911     }
 912
 913     pub fn mk_array(&self, ty: Ty<'tcx>, n: usize) -> Ty<'tcx> {
 914         self.mk_ty(TyArray(ty, n))
 915     }
 916
 917     pub fn mk_slice(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 918         self.mk_ty(TySlice(ty))
 919     }
 920
 921     pub fn mk_tup(&self, ts: Vec<Ty<'tcx>>) -> Ty<'tcx> {
 922         self.mk_ty(TyTuple(ts))
 923     }
 924
 925     pub fn mk_nil(&self) -> Ty<'tcx> {
 926         self.mk_tup(Vec::new())
 927     }
 928
 929     pub fn mk_bool(&self) -> Ty<'tcx> {
 930         self.mk_ty(TyBool)
 931     }
 932
 933     pub fn mk_fn(&self,
 934                  opt_def_id: Option<DefId>,
 935                  fty: &'tcx BareFnTy<'tcx>) -> Ty<'tcx> {
 936         self.mk_ty(TyBareFn(opt_def_id, fty))
 937     }
 938
 939     pub fn mk_ctor_fn(&self,
 940                       def_id: DefId,
 941                       input_tys: &[Ty<'tcx>],
 942                       output: Ty<'tcx>) -> Ty<'tcx> {
 943         let input_args = input_tys.iter().cloned().collect();
 944         self.mk_fn(Some(def_id), self.mk_bare_fn(BareFnTy {
 945             unsafety: hir::Unsafety::Normal,
 946             abi: abi::Rust,
 947             sig: ty::Binder(ty::FnSig {
 948                 inputs: input_args,
 949                 output: ty::FnConverging(output),
 950                 variadic: false
 951             })
 952         }))
 953     }
 954
 955     pub fn mk_trait(&self,
 956                     principal: ty::PolyTraitRef<'tcx>,
 957                     bounds: ExistentialBounds<'tcx>)
 958                     -> Ty<'tcx>
 959     {
 960         assert!(bound_list_is_sorted(&bounds.projection_bounds));
 961
 962         let inner = box TraitTy {
 963             principal: principal,
 964             bounds: bounds
 965         };
 966         self.mk_ty(TyTrait(inner))
 967     }
 968
 969     pub fn mk_projection(&self,
 970                          trait_ref: TraitRef<'tcx>,
 971                          item_name: Name)
 972                          -> Ty<'tcx> {
 973         // take a copy of substs so that we own the vectors inside
 974         let inner = ProjectionTy { trait_ref: trait_ref, item_name: item_name };
 975         self.mk_ty(TyProjection(inner))
 976     }
 977
 978     pub fn mk_struct(&self, def: AdtDef<'tcx>, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
 979         // take a copy of substs so that we own the vectors inside
 980         self.mk_ty(TyStruct(def, substs))
 981     }
 982
 983     pub fn mk_closure(&self,
 984                       closure_id: DefId,
 985                       substs: &'tcx Substs<'tcx>,
 986                       tys: Vec<Ty<'tcx>>)
 987                       -> Ty<'tcx> {
 988         self.mk_closure_from_closure_substs(closure_id, Box::new(ClosureSubsts {
 989             func_substs: substs,
 990             upvar_tys: tys
 991         }))
 992     }
 993
 994     pub fn mk_closure_from_closure_substs(&self,
 995                                           closure_id: DefId,
 996                                           closure_substs: Box<ClosureSubsts<'tcx>>)
 997                                           -> Ty<'tcx> {
 998         self.mk_ty(TyClosure(closure_id, closure_substs))
 999     }
1000
1001     pub fn mk_var(&self, v: TyVid) -> Ty<'tcx> {
1002         self.mk_infer(TyVar(v))
1003     }
1004
1005     pub fn mk_int_var(&self, v: IntVid) -> Ty<'tcx> {
1006         self.mk_infer(IntVar(v))
1007     }
1008
1009     pub fn mk_float_var(&self, v: FloatVid) -> Ty<'tcx> {
1010         self.mk_infer(FloatVar(v))
1011     }
1012
1013     pub fn mk_infer(&self, it: InferTy) -> Ty<'tcx> {
1014         self.mk_ty(TyInfer(it))
1015     }
1016
1017     pub fn mk_param(&self,
1018                     space: subst::ParamSpace,
1019                     index: u32,
1020                     name: Name) -> Ty<'tcx> {
1021         self.mk_ty(TyParam(ParamTy { space: space, idx: index, name: name }))
1022     }
1023
1024     pub fn mk_self_type(&self) -> Ty<'tcx> {
1025         self.mk_param(subst::SelfSpace, 0, special_idents::type_self.name)
1026     }
1027
1028     pub fn mk_param_from_def(&self, def: &ty::TypeParameterDef) -> Ty<'tcx> {
1029         self.mk_param(def.space, def.index, def.name)
1030     }
1031
1032     pub fn trait_items(&self, trait_did: DefId) -> Rc<Vec<ty::ImplOrTraitItem<'tcx>>> {
1033         self.trait_items_cache.memoize(trait_did, || {
1034             let def_ids = self.trait_item_def_ids(trait_did);
1035             Rc::new(def_ids.iter()
1036                            .map(|d| self.impl_or_trait_item(d.def_id()))
1037                            .collect())
1038         })
1039     }
1040
1041     /// Obtain the representation annotation for a struct definition.
1042     pub fn lookup_repr_hints(&self, did: DefId) -> Rc<Vec<attr::ReprAttr>> {
1043         self.repr_hint_cache.memoize(did, || {
1044             Rc::new(if did.is_local() {
1045                 self.get_attrs(did).iter().flat_map(|meta| {
1046                     attr::find_repr_attrs(self.sess.diagnostic(), meta).into_iter()
1047                 }).collect()
1048             } else {
1049                 self.sess.cstore.repr_attrs(did)
1050             })
1051         })
1052     }
1053 }