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;
  14 use dep_graph::{DepNode, DepConstructor};
  15 use errors::DiagnosticBuilder;
  16 use session::Session;
  17 use session::config::{BorrowckMode, OutputFilenames};
  18 use middle;
  19 use hir::{TraitCandidate, HirId, ItemLocalId};
  20 use hir::def::{Def, Export};
  21 use hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE};
  22 use hir::map as hir_map;
  23 use hir::map::DefPathHash;
  24 use lint::{self, Lint};
  25 use ich::{StableHashingContext, NodeIdHashingMode};
  26 use infer::outlives::free_region_map::FreeRegionMap;
  27 use middle::const_val::ConstVal;
  28 use middle::cstore::{CrateStore, LinkMeta};
  29 use middle::cstore::EncodedMetadata;
  30 use middle::lang_items;
  31 use middle::resolve_lifetime::{self, ObjectLifetimeDefault};
  32 use middle::stability;
  33 use mir::{Mir, interpret};
  34 use ty::subst::{Kind, Substs};
  35 use ty::ReprOptions;
  36 use ty::Instance;
  37 use traits;
  38 use ty::{self, Ty, TypeAndMut};
  39 use ty::{TyS, TypeVariants, Slice};
  40 use ty::{AdtKind, AdtDef, ClosureSubsts, GeneratorInterior, Region, Const};
  41 use ty::{PolyFnSig, InferTy, ParamTy, ProjectionTy, ExistentialPredicate, Predicate};
  42 use ty::RegionKind;
  43 use ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
  44 use ty::TypeVariants::*;
  45 use ty::layout::{LayoutDetails, TargetDataLayout};
  46 use ty::maps;
  47 use ty::steal::Steal;
  48 use ty::BindingMode;
  49 use util::nodemap::{NodeMap, DefIdSet, ItemLocalMap};
  50 use util::nodemap::{FxHashMap, FxHashSet};
  51 use rustc_data_structures::accumulate_vec::AccumulateVec;
  52 use rustc_data_structures::stable_hasher::{HashStable, hash_stable_hashmap,
  53                                            StableHasher, StableHasherResult,
  54                                            StableVec};
  55 use arena::{TypedArena, DroplessArena};
  56 use rustc_const_math::{ConstInt, ConstUsize};
  57 use rustc_data_structures::indexed_vec::IndexVec;
  58 use rustc_data_structures::sync::Lrc;
  59 use std::any::Any;
  60 use std::borrow::Borrow;
  61 use std::cell::{Cell, RefCell};
  62 use std::cmp::Ordering;
  63 use std::collections::hash_map::{self, Entry};
  64 use std::hash::{Hash, Hasher};
  65 use std::mem;
  66 use std::ops::Deref;
  67 use std::iter;
  68 use std::sync::mpsc;
  69 use std::sync::Arc;
  70 use syntax::abi;
  71 use syntax::ast::{self, Name, NodeId};
  72 use syntax::attr;
  73 use syntax::codemap::MultiSpan;
  74 use syntax::feature_gate;
  75 use syntax::symbol::{Symbol, keywords};
  76 use syntax_pos::Span;
  77
  78 use hir;
  79
  80 pub struct AllArenas<'tcx> {
  81     pub global: GlobalArenas<'tcx>,
  82     pub interner: DroplessArena,
  83 }
  84
  85 impl<'tcx> AllArenas<'tcx> {
  86     pub fn new() -> Self {
  87         AllArenas {
  88             global: GlobalArenas::new(),
  89             interner: DroplessArena::new(),
  90         }
  91     }
  92 }
  93
  94 /// Internal storage
  95 pub struct GlobalArenas<'tcx> {
  96     // internings
  97     layout: TypedArena<LayoutDetails>,
  98
  99     // references
 100     generics: TypedArena<ty::Generics>,
 101     trait_def: TypedArena<ty::TraitDef>,
 102     adt_def: TypedArena<ty::AdtDef>,
 103     steal_mir: TypedArena<Steal<Mir<'tcx>>>,
 104     mir: TypedArena<Mir<'tcx>>,
 105     tables: TypedArena<ty::TypeckTables<'tcx>>,
 106     /// miri allocations
 107     const_allocs: TypedArena<interpret::Allocation>,
 108 }
 109
 110 impl<'tcx> GlobalArenas<'tcx> {
 111     pub fn new() -> GlobalArenas<'tcx> {
 112         GlobalArenas {
 113             layout: TypedArena::new(),
 114             generics: TypedArena::new(),
 115             trait_def: TypedArena::new(),
 116             adt_def: TypedArena::new(),
 117             steal_mir: TypedArena::new(),
 118             mir: TypedArena::new(),
 119             tables: TypedArena::new(),
 120             const_allocs: TypedArena::new(),
 121         }
 122     }
 123 }
 124
 125 pub struct CtxtInterners<'tcx> {
 126     /// The arena that types, regions, etc are allocated from
 127     arena: &'tcx DroplessArena,
 128
 129     /// Specifically use a speedy hash algorithm for these hash sets,
 130     /// they're accessed quite often.
 131     type_: RefCell<FxHashSet<Interned<'tcx, TyS<'tcx>>>>,
 132     type_list: RefCell<FxHashSet<Interned<'tcx, Slice<Ty<'tcx>>>>>,
 133     substs: RefCell<FxHashSet<Interned<'tcx, Substs<'tcx>>>>,
 134     region: RefCell<FxHashSet<Interned<'tcx, RegionKind>>>,
 135     existential_predicates: RefCell<FxHashSet<Interned<'tcx, Slice<ExistentialPredicate<'tcx>>>>>,
 136     predicates: RefCell<FxHashSet<Interned<'tcx, Slice<Predicate<'tcx>>>>>,
 137     const_: RefCell<FxHashSet<Interned<'tcx, Const<'tcx>>>>,
 138 }
 139
 140 impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
 141     fn new(arena: &'tcx DroplessArena) -> CtxtInterners<'tcx> {
 142         CtxtInterners {
 143             arena,
 144             type_: RefCell::new(FxHashSet()),
 145             type_list: RefCell::new(FxHashSet()),
 146             substs: RefCell::new(FxHashSet()),
 147             region: RefCell::new(FxHashSet()),
 148             existential_predicates: RefCell::new(FxHashSet()),
 149             predicates: RefCell::new(FxHashSet()),
 150             const_: RefCell::new(FxHashSet()),
 151         }
 152     }
 153
 154     /// Intern a type. global_interners is Some only if this is
 155     /// a local interner and global_interners is its counterpart.
 156     fn intern_ty(&self, st: TypeVariants<'tcx>,
 157                  global_interners: Option<&CtxtInterners<'gcx>>)
 158                  -> Ty<'tcx> {
 159         let ty = {
 160             let mut interner = self.type_.borrow_mut();
 161             let global_interner = global_interners.map(|interners| {
 162                 interners.type_.borrow_mut()
 163             });
 164             if let Some(&Interned(ty)) = interner.get(&st) {
 165                 return ty;
 166             }
 167             if let Some(ref interner) = global_interner {
 168                 if let Some(&Interned(ty)) = interner.get(&st) {
 169                     return ty;
 170                 }
 171             }
 172
 173             let flags = super::flags::FlagComputation::for_sty(&st);
 174             let ty_struct = TyS {
 175                 sty: st,
 176                 flags: flags.flags,
 177                 region_depth: flags.depth,
 178             };
 179
 180             // HACK(eddyb) Depend on flags being accurate to
 181             // determine that all contents are in the global tcx.
 182             // See comments on Lift for why we can't use that.
 183             if !flags.flags.intersects(ty::TypeFlags::KEEP_IN_LOCAL_TCX) {
 184                 if let Some(interner) = global_interners {
 185                     let ty_struct: TyS<'gcx> = unsafe {
 186                         mem::transmute(ty_struct)
 187                     };
 188                     let ty: Ty<'gcx> = interner.arena.alloc(ty_struct);
 189                     global_interner.unwrap().insert(Interned(ty));
 190                     return ty;
 191                 }
 192             } else {
 193                 // Make sure we don't end up with inference
 194                 // types/regions in the global tcx.
 195                 if global_interners.is_none() {
 196                     drop(interner);
 197                     bug!("Attempted to intern `{:?}` which contains \
 198                           inference types/regions in the global type context",
 199                          &ty_struct);
 200                 }
 201             }
 202
 203             // Don't be &mut TyS.
 204             let ty: Ty<'tcx> = self.arena.alloc(ty_struct);
 205             interner.insert(Interned(ty));
 206             ty
 207         };
 208
 209         debug!("Interned type: {:?} Pointer: {:?}",
 210             ty, ty as *const TyS);
 211         ty
 212     }
 213
 214 }
 215
 216 pub struct CommonTypes<'tcx> {
 217     pub bool: Ty<'tcx>,
 218     pub char: Ty<'tcx>,
 219     pub isize: Ty<'tcx>,
 220     pub i8: Ty<'tcx>,
 221     pub i16: Ty<'tcx>,
 222     pub i32: Ty<'tcx>,
 223     pub i64: Ty<'tcx>,
 224     pub i128: Ty<'tcx>,
 225     pub usize: Ty<'tcx>,
 226     pub u8: Ty<'tcx>,
 227     pub u16: Ty<'tcx>,
 228     pub u32: Ty<'tcx>,
 229     pub u64: Ty<'tcx>,
 230     pub u128: Ty<'tcx>,
 231     pub f32: Ty<'tcx>,
 232     pub f64: Ty<'tcx>,
 233     pub never: Ty<'tcx>,
 234     pub err: Ty<'tcx>,
 235
 236     pub re_empty: Region<'tcx>,
 237     pub re_static: Region<'tcx>,
 238     pub re_erased: Region<'tcx>,
 239 }
 240
 241 pub struct LocalTableInContext<'a, V: 'a> {
 242     local_id_root: Option<DefId>,
 243     data: &'a ItemLocalMap<V>
 244 }
 245
 246 /// Validate that the given HirId (respectively its `local_id` part) can be
 247 /// safely used as a key in the tables of a TypeckTable. For that to be
 248 /// the case, the HirId must have the same `owner` as all the other IDs in
 249 /// this table (signified by `local_id_root`). Otherwise the HirId
 250 /// would be in a different frame of reference and using its `local_id`
 251 /// would result in lookup errors, or worse, in silently wrong data being
 252 /// stored/returned.
 253 fn validate_hir_id_for_typeck_tables(local_id_root: Option<DefId>,
 254                                      hir_id: hir::HirId,
 255                                      mut_access: bool) {
 256     if cfg!(debug_assertions) {
 257         if let Some(local_id_root) = local_id_root {
 258             if hir_id.owner != local_id_root.index {
 259                 ty::tls::with(|tcx| {
 260                     let node_id = tcx.hir
 261                                      .definitions()
 262                                      .find_node_for_hir_id(hir_id);
 263
 264                     bug!("node {} with HirId::owner {:?} cannot be placed in \
 265                           TypeckTables with local_id_root {:?}",
 266                           tcx.hir.node_to_string(node_id),
 267                           DefId::local(hir_id.owner),
 268                           local_id_root)
 269                 });
 270             }
 271         } else {
 272             // We use "Null Object" TypeckTables in some of the analysis passes.
 273             // These are just expected to be empty and their `local_id_root` is
 274             // `None`. Therefore we cannot verify whether a given `HirId` would
 275             // be a valid key for the given table. Instead we make sure that
 276             // nobody tries to write to such a Null Object table.
 277             if mut_access {
 278                 bug!("access to invalid TypeckTables")
 279             }
 280         }
 281     }
 282 }
 283
 284 impl<'a, V> LocalTableInContext<'a, V> {
 285     pub fn contains_key(&self, id: hir::HirId) -> bool {
 286         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
 287         self.data.contains_key(&id.local_id)
 288     }
 289
 290     pub fn get(&self, id: hir::HirId) -> Option<&V> {
 291         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
 292         self.data.get(&id.local_id)
 293     }
 294
 295     pub fn iter(&self) -> hash_map::Iter<hir::ItemLocalId, V> {
 296         self.data.iter()
 297     }
 298 }
 299
 300 impl<'a, V> ::std::ops::Index<hir::HirId> for LocalTableInContext<'a, V> {
 301     type Output = V;
 302
 303     fn index(&self, key: hir::HirId) -> &V {
 304         self.get(key).expect("LocalTableInContext: key not found")
 305     }
 306 }
 307
 308 pub struct LocalTableInContextMut<'a, V: 'a> {
 309     local_id_root: Option<DefId>,
 310     data: &'a mut ItemLocalMap<V>
 311 }
 312
 313 impl<'a, V> LocalTableInContextMut<'a, V> {
 314     pub fn get_mut(&mut self, id: hir::HirId) -> Option<&mut V> {
 315         validate_hir_id_for_typeck_tables(self.local_id_root, id, true);
 316         self.data.get_mut(&id.local_id)
 317     }
 318
 319     pub fn entry(&mut self, id: hir::HirId) -> Entry<hir::ItemLocalId, V> {
 320         validate_hir_id_for_typeck_tables(self.local_id_root, id, true);
 321         self.data.entry(id.local_id)
 322     }
 323
 324     pub fn insert(&mut self, id: hir::HirId, val: V) -> Option<V> {
 325         validate_hir_id_for_typeck_tables(self.local_id_root, id, true);
 326         self.data.insert(id.local_id, val)
 327     }
 328
 329     pub fn remove(&mut self, id: hir::HirId) -> Option<V> {
 330         validate_hir_id_for_typeck_tables(self.local_id_root, id, true);
 331         self.data.remove(&id.local_id)
 332     }
 333 }
 334
 335 #[derive(RustcEncodable, RustcDecodable, Debug)]
 336 pub struct TypeckTables<'tcx> {
 337     /// The HirId::owner all ItemLocalIds in this table are relative to.
 338     pub local_id_root: Option<DefId>,
 339
 340     /// Resolved definitions for `<T>::X` associated paths and
 341     /// method calls, including those of overloaded operators.
 342     type_dependent_defs: ItemLocalMap<Def>,
 343
 344     /// Stores the types for various nodes in the AST.  Note that this table
 345     /// is not guaranteed to be populated until after typeck.  See
 346     /// typeck::check::fn_ctxt for details.
 347     node_types: ItemLocalMap<Ty<'tcx>>,
 348
 349     /// Stores the type parameters which were substituted to obtain the type
 350     /// of this node.  This only applies to nodes that refer to entities
 351     /// parameterized by type parameters, such as generic fns, types, or
 352     /// other items.
 353     node_substs: ItemLocalMap<&'tcx Substs<'tcx>>,
 354
 355     adjustments: ItemLocalMap<Vec<ty::adjustment::Adjustment<'tcx>>>,
 356
 357     /// Stores the actual binding mode for all instances of hir::BindingAnnotation.
 358     pat_binding_modes: ItemLocalMap<BindingMode>,
 359
 360     /// Stores the types which were implicitly dereferenced in pattern binding modes
 361     /// for later usage in HAIR lowering. For example,
 362     ///
 363     /// ```
 364     /// match &&Some(5i32) {
 365     ///     Some(n) => {},
 366     ///     _ => {},
 367     /// }
 368     /// ```
 369     /// leads to a `vec![&&Option<i32>, &Option<i32>]`. Empty vectors are not stored.
 370     ///
 371     /// See:
 372     /// https://github.com/rust-lang/rfcs/blob/master/text/2005-match-ergonomics.md#definitions
 373     pat_adjustments: ItemLocalMap<Vec<Ty<'tcx>>>,
 374
 375     /// Borrows
 376     pub upvar_capture_map: ty::UpvarCaptureMap<'tcx>,
 377
 378     /// Records the reasons that we picked the kind of each closure;
 379     /// not all closures are present in the map.
 380     closure_kind_origins: ItemLocalMap<(Span, ast::Name)>,
 381
 382     /// For each fn, records the "liberated" types of its arguments
 383     /// and return type. Liberated means that all bound regions
 384     /// (including late-bound regions) are replaced with free
 385     /// equivalents. This table is not used in trans (since regions
 386     /// are erased there) and hence is not serialized to metadata.
 387     liberated_fn_sigs: ItemLocalMap<ty::FnSig<'tcx>>,
 388
 389     /// For each FRU expression, record the normalized types of the fields
 390     /// of the struct - this is needed because it is non-trivial to
 391     /// normalize while preserving regions. This table is used only in
 392     /// MIR construction and hence is not serialized to metadata.
 393     fru_field_types: ItemLocalMap<Vec<Ty<'tcx>>>,
 394
 395     /// Maps a cast expression to its kind. This is keyed on the
 396     /// *from* expression of the cast, not the cast itself.
 397     cast_kinds: ItemLocalMap<ty::cast::CastKind>,
 398
 399     /// Set of trait imports actually used in the method resolution.
 400     /// This is used for warning unused imports. During type
 401     /// checking, this `Lrc` should not be cloned: it must have a ref-count
 402     /// of 1 so that we can insert things into the set mutably.
 403     pub used_trait_imports: Lrc<DefIdSet>,
 404
 405     /// If any errors occurred while type-checking this body,
 406     /// this field will be set to `true`.
 407     pub tainted_by_errors: bool,
 408
 409     /// Stores the free-region relationships that were deduced from
 410     /// its where clauses and parameter types. These are then
 411     /// read-again by borrowck.
 412     pub free_region_map: FreeRegionMap<'tcx>,
 413 }
 414
 415 impl<'tcx> TypeckTables<'tcx> {
 416     pub fn empty(local_id_root: Option<DefId>) -> TypeckTables<'tcx> {
 417         TypeckTables {
 418             local_id_root,
 419             type_dependent_defs: ItemLocalMap(),
 420             node_types: ItemLocalMap(),
 421             node_substs: ItemLocalMap(),
 422             adjustments: ItemLocalMap(),
 423             pat_binding_modes: ItemLocalMap(),
 424             pat_adjustments: ItemLocalMap(),
 425             upvar_capture_map: FxHashMap(),
 426             closure_kind_origins: ItemLocalMap(),
 427             liberated_fn_sigs: ItemLocalMap(),
 428             fru_field_types: ItemLocalMap(),
 429             cast_kinds: ItemLocalMap(),
 430             used_trait_imports: Lrc::new(DefIdSet()),
 431             tainted_by_errors: false,
 432             free_region_map: FreeRegionMap::new(),
 433         }
 434     }
 435
 436     /// Returns the final resolution of a `QPath` in an `Expr` or `Pat` node.
 437     pub fn qpath_def(&self, qpath: &hir::QPath, id: hir::HirId) -> Def {
 438         match *qpath {
 439             hir::QPath::Resolved(_, ref path) => path.def,
 440             hir::QPath::TypeRelative(..) => {
 441                 validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
 442                 self.type_dependent_defs.get(&id.local_id).cloned().unwrap_or(Def::Err)
 443             }
 444         }
 445     }
 446
 447     pub fn type_dependent_defs(&self) -> LocalTableInContext<Def> {
 448         LocalTableInContext {
 449             local_id_root: self.local_id_root,
 450             data: &self.type_dependent_defs
 451         }
 452     }
 453
 454     pub fn type_dependent_defs_mut(&mut self) -> LocalTableInContextMut<Def> {
 455         LocalTableInContextMut {
 456             local_id_root: self.local_id_root,
 457             data: &mut self.type_dependent_defs
 458         }
 459     }
 460
 461     pub fn node_types(&self) -> LocalTableInContext<Ty<'tcx>> {
 462         LocalTableInContext {
 463             local_id_root: self.local_id_root,
 464             data: &self.node_types
 465         }
 466     }
 467
 468     pub fn node_types_mut(&mut self) -> LocalTableInContextMut<Ty<'tcx>> {
 469         LocalTableInContextMut {
 470             local_id_root: self.local_id_root,
 471             data: &mut self.node_types
 472         }
 473     }
 474
 475     pub fn node_id_to_type(&self, id: hir::HirId) -> Ty<'tcx> {
 476         match self.node_id_to_type_opt(id) {
 477             Some(ty) => ty,
 478             None => {
 479                 bug!("node_id_to_type: no type for node `{}`",
 480                     tls::with(|tcx| {
 481                         let id = tcx.hir.definitions().find_node_for_hir_id(id);
 482                         tcx.hir.node_to_string(id)
 483                     }))
 484             }
 485         }
 486     }
 487
 488     pub fn node_id_to_type_opt(&self, id: hir::HirId) -> Option<Ty<'tcx>> {
 489         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
 490         self.node_types.get(&id.local_id).cloned()
 491     }
 492
 493     pub fn node_substs_mut(&mut self) -> LocalTableInContextMut<&'tcx Substs<'tcx>> {
 494         LocalTableInContextMut {
 495             local_id_root: self.local_id_root,
 496             data: &mut self.node_substs
 497         }
 498     }
 499
 500     pub fn node_substs(&self, id: hir::HirId) -> &'tcx Substs<'tcx> {
 501         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
 502         self.node_substs.get(&id.local_id).cloned().unwrap_or(Substs::empty())
 503     }
 504
 505     pub fn node_substs_opt(&self, id: hir::HirId) -> Option<&'tcx Substs<'tcx>> {
 506         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
 507         self.node_substs.get(&id.local_id).cloned()
 508     }
 509
 510     // Returns the type of a pattern as a monotype. Like @expr_ty, this function
 511     // doesn't provide type parameter substitutions.
 512     pub fn pat_ty(&self, pat: &hir::Pat) -> Ty<'tcx> {
 513         self.node_id_to_type(pat.hir_id)
 514     }
 515
 516     pub fn pat_ty_opt(&self, pat: &hir::Pat) -> Option<Ty<'tcx>> {
 517         self.node_id_to_type_opt(pat.hir_id)
 518     }
 519
 520     // Returns the type of an expression as a monotype.
 521     //
 522     // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression.  That is, in
 523     // some cases, we insert `Adjustment` annotations such as auto-deref or
 524     // auto-ref.  The type returned by this function does not consider such
 525     // adjustments.  See `expr_ty_adjusted()` instead.
 526     //
 527     // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
 528     // ask for the type of "id" in "id(3)", it will return "fn(&isize) -> isize"
 529     // instead of "fn(ty) -> T with T = isize".
 530     pub fn expr_ty(&self, expr: &hir::Expr) -> Ty<'tcx> {
 531         self.node_id_to_type(expr.hir_id)
 532     }
 533
 534     pub fn expr_ty_opt(&self, expr: &hir::Expr) -> Option<Ty<'tcx>> {
 535         self.node_id_to_type_opt(expr.hir_id)
 536     }
 537
 538     pub fn adjustments(&self) -> LocalTableInContext<Vec<ty::adjustment::Adjustment<'tcx>>> {
 539         LocalTableInContext {
 540             local_id_root: self.local_id_root,
 541             data: &self.adjustments
 542         }
 543     }
 544
 545     pub fn adjustments_mut(&mut self)
 546                            -> LocalTableInContextMut<Vec<ty::adjustment::Adjustment<'tcx>>> {
 547         LocalTableInContextMut {
 548             local_id_root: self.local_id_root,
 549             data: &mut self.adjustments
 550         }
 551     }
 552
 553     pub fn expr_adjustments(&self, expr: &hir::Expr)
 554                             -> &[ty::adjustment::Adjustment<'tcx>] {
 555         validate_hir_id_for_typeck_tables(self.local_id_root, expr.hir_id, false);
 556         self.adjustments.get(&expr.hir_id.local_id).map_or(&[], |a| &a[..])
 557     }
 558
 559     /// Returns the type of `expr`, considering any `Adjustment`
 560     /// entry recorded for that expression.
 561     pub fn expr_ty_adjusted(&self, expr: &hir::Expr) -> Ty<'tcx> {
 562         self.expr_adjustments(expr)
 563             .last()
 564             .map_or_else(|| self.expr_ty(expr), |adj| adj.target)
 565     }
 566
 567     pub fn expr_ty_adjusted_opt(&self, expr: &hir::Expr) -> Option<Ty<'tcx>> {
 568         self.expr_adjustments(expr)
 569             .last()
 570             .map(|adj| adj.target)
 571             .or_else(|| self.expr_ty_opt(expr))
 572     }
 573
 574     pub fn is_method_call(&self, expr: &hir::Expr) -> bool {
 575         // Only paths and method calls/overloaded operators have
 576         // entries in type_dependent_defs, ignore the former here.
 577         if let hir::ExprPath(_) = expr.node {
 578             return false;
 579         }
 580
 581         match self.type_dependent_defs().get(expr.hir_id) {
 582             Some(&Def::Method(_)) => true,
 583             _ => false
 584         }
 585     }
 586
 587     pub fn pat_binding_modes(&self) -> LocalTableInContext<BindingMode> {
 588         LocalTableInContext {
 589             local_id_root: self.local_id_root,
 590             data: &self.pat_binding_modes
 591         }
 592     }
 593
 594     pub fn pat_binding_modes_mut(&mut self)
 595                            -> LocalTableInContextMut<BindingMode> {
 596         LocalTableInContextMut {
 597             local_id_root: self.local_id_root,
 598             data: &mut self.pat_binding_modes
 599         }
 600     }
 601
 602     pub fn pat_adjustments(&self) -> LocalTableInContext<Vec<Ty<'tcx>>> {
 603         LocalTableInContext {
 604             local_id_root: self.local_id_root,
 605             data: &self.pat_adjustments,
 606         }
 607     }
 608
 609     pub fn pat_adjustments_mut(&mut self)
 610                            -> LocalTableInContextMut<Vec<Ty<'tcx>>> {
 611         LocalTableInContextMut {
 612             local_id_root: self.local_id_root,
 613             data: &mut self.pat_adjustments,
 614         }
 615     }
 616
 617     pub fn upvar_capture(&self, upvar_id: ty::UpvarId) -> ty::UpvarCapture<'tcx> {
 618         self.upvar_capture_map[&upvar_id]
 619     }
 620
 621     pub fn closure_kind_origins(&self) -> LocalTableInContext<(Span, ast::Name)> {
 622         LocalTableInContext {
 623             local_id_root: self.local_id_root,
 624             data: &self.closure_kind_origins
 625         }
 626     }
 627
 628     pub fn closure_kind_origins_mut(&mut self) -> LocalTableInContextMut<(Span, ast::Name)> {
 629         LocalTableInContextMut {
 630             local_id_root: self.local_id_root,
 631             data: &mut self.closure_kind_origins
 632         }
 633     }
 634
 635     pub fn liberated_fn_sigs(&self) -> LocalTableInContext<ty::FnSig<'tcx>> {
 636         LocalTableInContext {
 637             local_id_root: self.local_id_root,
 638             data: &self.liberated_fn_sigs
 639         }
 640     }
 641
 642     pub fn liberated_fn_sigs_mut(&mut self) -> LocalTableInContextMut<ty::FnSig<'tcx>> {
 643         LocalTableInContextMut {
 644             local_id_root: self.local_id_root,
 645             data: &mut self.liberated_fn_sigs
 646         }
 647     }
 648
 649     pub fn fru_field_types(&self) -> LocalTableInContext<Vec<Ty<'tcx>>> {
 650         LocalTableInContext {
 651             local_id_root: self.local_id_root,
 652             data: &self.fru_field_types
 653         }
 654     }
 655
 656     pub fn fru_field_types_mut(&mut self) -> LocalTableInContextMut<Vec<Ty<'tcx>>> {
 657         LocalTableInContextMut {
 658             local_id_root: self.local_id_root,
 659             data: &mut self.fru_field_types
 660         }
 661     }
 662
 663     pub fn cast_kinds(&self) -> LocalTableInContext<ty::cast::CastKind> {
 664         LocalTableInContext {
 665             local_id_root: self.local_id_root,
 666             data: &self.cast_kinds
 667         }
 668     }
 669
 670     pub fn cast_kinds_mut(&mut self) -> LocalTableInContextMut<ty::cast::CastKind> {
 671         LocalTableInContextMut {
 672             local_id_root: self.local_id_root,
 673             data: &mut self.cast_kinds
 674         }
 675     }
 676 }
 677
 678 impl<'gcx> HashStable<StableHashingContext<'gcx>> for TypeckTables<'gcx> {
 679     fn hash_stable<W: StableHasherResult>(&self,
 680                                           hcx: &mut StableHashingContext<'gcx>,
 681                                           hasher: &mut StableHasher<W>) {
 682         let ty::TypeckTables {
 683             local_id_root,
 684             ref type_dependent_defs,
 685             ref node_types,
 686             ref node_substs,
 687             ref adjustments,
 688             ref pat_binding_modes,
 689             ref pat_adjustments,
 690             ref upvar_capture_map,
 691             ref closure_kind_origins,
 692             ref liberated_fn_sigs,
 693             ref fru_field_types,
 694
 695             ref cast_kinds,
 696
 697             ref used_trait_imports,
 698             tainted_by_errors,
 699             ref free_region_map,
 700         } = *self;
 701
 702         hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
 703             type_dependent_defs.hash_stable(hcx, hasher);
 704             node_types.hash_stable(hcx, hasher);
 705             node_substs.hash_stable(hcx, hasher);
 706             adjustments.hash_stable(hcx, hasher);
 707             pat_binding_modes.hash_stable(hcx, hasher);
 708             pat_adjustments.hash_stable(hcx, hasher);
 709             hash_stable_hashmap(hcx, hasher, upvar_capture_map, |up_var_id, hcx| {
 710                 let ty::UpvarId {
 711                     var_id,
 712                     closure_expr_id
 713                 } = *up_var_id;
 714
 715                 let local_id_root =
 716                     local_id_root.expect("trying to hash invalid TypeckTables");
 717
 718                 let var_owner_def_id = DefId {
 719                     krate: local_id_root.krate,
 720                     index: var_id.owner,
 721                 };
 722                 let closure_def_id = DefId {
 723                     krate: local_id_root.krate,
 724                     index: closure_expr_id.to_def_id().index,
 725                 };
 726                 (hcx.def_path_hash(var_owner_def_id),
 727                  var_id.local_id,
 728                  hcx.def_path_hash(closure_def_id))
 729             });
 730
 731             closure_kind_origins.hash_stable(hcx, hasher);
 732             liberated_fn_sigs.hash_stable(hcx, hasher);
 733             fru_field_types.hash_stable(hcx, hasher);
 734             cast_kinds.hash_stable(hcx, hasher);
 735             used_trait_imports.hash_stable(hcx, hasher);
 736             tainted_by_errors.hash_stable(hcx, hasher);
 737             free_region_map.hash_stable(hcx, hasher);
 738         })
 739     }
 740 }
 741
 742 impl<'tcx> CommonTypes<'tcx> {
 743     fn new(interners: &CtxtInterners<'tcx>) -> CommonTypes<'tcx> {
 744         let mk = |sty| interners.intern_ty(sty, None);
 745         let mk_region = |r| {
 746             if let Some(r) = interners.region.borrow().get(&r) {
 747                 return r.0;
 748             }
 749             let r = interners.arena.alloc(r);
 750             interners.region.borrow_mut().insert(Interned(r));
 751             &*r
 752         };
 753         CommonTypes {
 754             bool: mk(TyBool),
 755             char: mk(TyChar),
 756             never: mk(TyNever),
 757             err: mk(TyError),
 758             isize: mk(TyInt(ast::IntTy::Isize)),
 759             i8: mk(TyInt(ast::IntTy::I8)),
 760             i16: mk(TyInt(ast::IntTy::I16)),
 761             i32: mk(TyInt(ast::IntTy::I32)),
 762             i64: mk(TyInt(ast::IntTy::I64)),
 763             i128: mk(TyInt(ast::IntTy::I128)),
 764             usize: mk(TyUint(ast::UintTy::Usize)),
 765             u8: mk(TyUint(ast::UintTy::U8)),
 766             u16: mk(TyUint(ast::UintTy::U16)),
 767             u32: mk(TyUint(ast::UintTy::U32)),
 768             u64: mk(TyUint(ast::UintTy::U64)),
 769             u128: mk(TyUint(ast::UintTy::U128)),
 770             f32: mk(TyFloat(ast::FloatTy::F32)),
 771             f64: mk(TyFloat(ast::FloatTy::F64)),
 772
 773             re_empty: mk_region(RegionKind::ReEmpty),
 774             re_static: mk_region(RegionKind::ReStatic),
 775             re_erased: mk_region(RegionKind::ReErased),
 776         }
 777     }
 778 }
 779
 780 /// The central data structure of the compiler. It stores references
 781 /// to the various **arenas** and also houses the results of the
 782 /// various **compiler queries** that have been performed. See the
 783 /// [rustc guide] for more details.
 784 ///
 785 /// [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/ty.html
 786 #[derive(Copy, Clone)]
 787 pub struct TyCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 788     gcx: &'a GlobalCtxt<'gcx>,
 789     interners: &'a CtxtInterners<'tcx>
 790 }
 791
 792 impl<'a, 'gcx, 'tcx> Deref for TyCtxt<'a, 'gcx, 'tcx> {
 793     type Target = &'a GlobalCtxt<'gcx>;
 794     fn deref(&self) -> &Self::Target {
 795         &self.gcx
 796     }
 797 }
 798
 799 pub struct GlobalCtxt<'tcx> {
 800     global_arenas: &'tcx GlobalArenas<'tcx>,
 801     global_interners: CtxtInterners<'tcx>,
 802
 803     cstore: &'tcx dyn CrateStore,
 804
 805     pub sess: &'tcx Session,
 806
 807     pub dep_graph: DepGraph,
 808
 809     /// This provides access to the incr. comp. on-disk cache for query results.
 810     /// Do not access this directly. It is only meant to be used by
 811     /// `DepGraph::try_mark_green()` and the query infrastructure in `ty::maps`.
 812     pub(crate) on_disk_query_result_cache: maps::OnDiskCache<'tcx>,
 813
 814     /// Common types, pre-interned for your convenience.
 815     pub types: CommonTypes<'tcx>,
 816
 817     /// Map indicating what traits are in scope for places where this
 818     /// is relevant; generated by resolve.
 819     trait_map: FxHashMap<DefIndex,
 820                          Lrc<FxHashMap<ItemLocalId,
 821                                        Lrc<StableVec<TraitCandidate>>>>>,
 822
 823     /// Export map produced by name resolution.
 824     export_map: FxHashMap<DefId, Lrc<Vec<Export>>>,
 825
 826     pub hir: hir_map::Map<'tcx>,
 827
 828     /// A map from DefPathHash -> DefId. Includes DefIds from the local crate
 829     /// as well as all upstream crates. Only populated in incremental mode.
 830     pub def_path_hash_to_def_id: Option<FxHashMap<DefPathHash, DefId>>,
 831
 832     pub maps: maps::Maps<'tcx>,
 833
 834     // Records the free variables refrenced by every closure
 835     // expression. Do not track deps for this, just recompute it from
 836     // scratch every time.
 837     freevars: FxHashMap<DefId, Lrc<Vec<hir::Freevar>>>,
 838
 839     maybe_unused_trait_imports: FxHashSet<DefId>,
 840
 841     maybe_unused_extern_crates: Vec<(DefId, Span)>,
 842
 843     // Internal cache for metadata decoding. No need to track deps on this.
 844     pub rcache: RefCell<FxHashMap<ty::CReaderCacheKey, Ty<'tcx>>>,
 845
 846     /// Caches the results of trait selection. This cache is used
 847     /// for things that do not have to do with the parameters in scope.
 848     pub selection_cache: traits::SelectionCache<'tcx>,
 849
 850     /// Caches the results of trait evaluation. This cache is used
 851     /// for things that do not have to do with the parameters in scope.
 852     /// Merge this with `selection_cache`?
 853     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 854
 855     /// The definite name of the current crate after taking into account
 856     /// attributes, commandline parameters, etc.
 857     pub crate_name: Symbol,
 858
 859     /// Data layout specification for the current target.
 860     pub data_layout: TargetDataLayout,
 861
 862     /// Used to prevent layout from recursing too deeply.
 863     pub layout_depth: Cell<usize>,
 864
 865     /// Map from function to the `#[derive]` mode that it's defining. Only used
 866     /// by `proc-macro` crates.
 867     pub derive_macros: RefCell<NodeMap<Symbol>>,
 868
 869     stability_interner: RefCell<FxHashSet<&'tcx attr::Stability>>,
 870
 871     pub interpret_interner: RefCell<InterpretInterner<'tcx>>,
 872
 873     layout_interner: RefCell<FxHashSet<&'tcx LayoutDetails>>,
 874
 875     /// A vector of every trait accessible in the whole crate
 876     /// (i.e. including those from subcrates). This is used only for
 877     /// error reporting, and so is lazily initialized and generally
 878     /// shouldn't taint the common path (hence the RefCell).
 879     pub all_traits: RefCell<Option<Vec<DefId>>>,
 880
 881     /// A general purpose channel to throw data out the back towards LLVM worker
 882     /// threads.
 883     ///
 884     /// This is intended to only get used during the trans phase of the compiler
 885     /// when satisfying the query for a particular codegen unit. Internally in
 886     /// the query it'll send data along this channel to get processed later.
 887     pub tx_to_llvm_workers: mpsc::Sender<Box<dyn Any + Send>>,
 888
 889     output_filenames: Arc<OutputFilenames>,
 890 }
 891
 892 /// Everything needed to efficiently work with interned allocations
 893 #[derive(Debug, Default)]
 894 pub struct InterpretInterner<'tcx> {
 895     /// Stores the value of constants (and deduplicates the actual memory)
 896     allocs: FxHashSet<&'tcx interpret::Allocation>,
 897
 898     /// Allows obtaining function instance handles via a unique identifier
 899     functions: FxHashMap<interpret::AllocId, Instance<'tcx>>,
 900
 901     /// Inverse map of `interpret_functions`.
 902     /// Used so we don't allocate a new pointer every time we need one
 903     function_cache: FxHashMap<Instance<'tcx>, interpret::AllocId>,
 904
 905     /// Allows obtaining const allocs via a unique identifier
 906     alloc_by_id: FxHashMap<interpret::AllocId, &'tcx interpret::Allocation>,
 907
 908     /// The AllocId to assign to the next new regular allocation.
 909     /// Always incremented, never gets smaller.
 910     next_id: interpret::AllocId,
 911
 912     /// Allows checking whether a constant already has an allocation
 913     alloc_cache: FxHashMap<interpret::GlobalId<'tcx>, interpret::AllocId>,
 914
 915     /// A cache for basic byte allocations keyed by their contents. This is used to deduplicate
 916     /// allocations for string and bytestring literals.
 917     literal_alloc_cache: FxHashMap<Vec<u8>, interpret::AllocId>,
 918 }
 919
 920 impl<'tcx> InterpretInterner<'tcx> {
 921     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> interpret::AllocId {
 922         if let Some(&alloc_id) = self.function_cache.get(&instance) {
 923             return alloc_id;
 924         }
 925         let id = self.reserve();
 926         debug!("creating fn ptr: {}", id);
 927         self.functions.insert(id, instance);
 928         self.function_cache.insert(instance, id);
 929         id
 930     }
 931
 932     pub fn get_fn(
 933         &self,
 934         id: interpret::AllocId,
 935     ) -> Option<Instance<'tcx>> {
 936         self.functions.get(&id).cloned()
 937     }
 938
 939     pub fn get_alloc(
 940         &self,
 941         id: interpret::AllocId,
 942     ) -> Option<&'tcx interpret::Allocation> {
 943         self.alloc_by_id.get(&id).cloned()
 944     }
 945
 946     pub fn get_cached(
 947         &self,
 948         global_id: interpret::GlobalId<'tcx>,
 949     ) -> Option<interpret::AllocId> {
 950         self.alloc_cache.get(&global_id).cloned()
 951     }
 952
 953     pub fn cache(
 954         &mut self,
 955         global_id: interpret::GlobalId<'tcx>,
 956         ptr: interpret::AllocId,
 957     ) {
 958         if let Some(old) = self.alloc_cache.insert(global_id, ptr) {
 959             bug!("tried to cache {:?}, but was already existing as {:#?}", global_id, old);
 960         }
 961     }
 962
 963     pub fn intern_at_reserved(
 964         &mut self,
 965         id: interpret::AllocId,
 966         alloc: &'tcx interpret::Allocation,
 967     ) {
 968         if let Some(old) = self.alloc_by_id.insert(id, alloc) {
 969             bug!("tried to intern allocation at {}, but was already existing as {:#?}", id, old);
 970         }
 971     }
 972
 973     /// obtains a new allocation ID that can be referenced but does not
 974     /// yet have an allocation backing it.
 975     pub fn reserve(
 976         &mut self,
 977     ) -> interpret::AllocId {
 978         let next = self.next_id;
 979         self.next_id.0 = self.next_id.0
 980             .checked_add(1)
 981             .expect("You overflowed a u64 by incrementing by 1... \
 982                      You've just earned yourself a free drink if we ever meet. \
 983                      Seriously, how did you do that?!");
 984         next
 985     }
 986 }
 987
 988 impl<'tcx> GlobalCtxt<'tcx> {
 989     /// Get the global TyCtxt.
 990     pub fn global_tcx<'a>(&'a self) -> TyCtxt<'a, 'tcx, 'tcx> {
 991         TyCtxt {
 992             gcx: self,
 993             interners: &self.global_interners
 994         }
 995     }
 996 }
 997
 998 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 999     pub fn alloc_generics(self, generics: ty::Generics) -> &'gcx ty::Generics {
1000         self.global_arenas.generics.alloc(generics)
1001     }
1002
1003     pub fn alloc_steal_mir(self, mir: Mir<'gcx>) -> &'gcx Steal<Mir<'gcx>> {
1004         self.global_arenas.steal_mir.alloc(Steal::new(mir))
1005     }
1006
1007     pub fn alloc_mir(self, mir: Mir<'gcx>) -> &'gcx Mir<'gcx> {
1008         self.global_arenas.mir.alloc(mir)
1009     }
1010
1011     pub fn alloc_tables(self, tables: ty::TypeckTables<'gcx>) -> &'gcx ty::TypeckTables<'gcx> {
1012         self.global_arenas.tables.alloc(tables)
1013     }
1014
1015     pub fn alloc_trait_def(self, def: ty::TraitDef) -> &'gcx ty::TraitDef {
1016         self.global_arenas.trait_def.alloc(def)
1017     }
1018
1019     pub fn alloc_adt_def(self,
1020                          did: DefId,
1021                          kind: AdtKind,
1022                          variants: Vec<ty::VariantDef>,
1023                          repr: ReprOptions)
1024                          -> &'gcx ty::AdtDef {
1025         let def = ty::AdtDef::new(self, did, kind, variants, repr);
1026         self.global_arenas.adt_def.alloc(def)
1027     }
1028
1029     pub fn alloc_byte_array(self, bytes: &[u8]) -> &'gcx [u8] {
1030         if bytes.is_empty() {
1031             &[]
1032         } else {
1033             self.global_interners.arena.alloc_slice(bytes)
1034         }
1035     }
1036
1037     pub fn alloc_const_slice(self, values: &[&'tcx ty::Const<'tcx>])
1038                              -> &'tcx [&'tcx ty::Const<'tcx>] {
1039         if values.is_empty() {
1040             &[]
1041         } else {
1042             self.interners.arena.alloc_slice(values)
1043         }
1044     }
1045
1046     pub fn alloc_name_const_slice(self, values: &[(ast::Name, &'tcx ty::Const<'tcx>)])
1047                                   -> &'tcx [(ast::Name, &'tcx ty::Const<'tcx>)] {
1048         if values.is_empty() {
1049             &[]
1050         } else {
1051             self.interners.arena.alloc_slice(values)
1052         }
1053     }
1054
1055     pub fn intern_const_alloc(
1056         self,
1057         alloc: interpret::Allocation,
1058     ) -> &'gcx interpret::Allocation {
1059         if let Some(alloc) = self.interpret_interner.borrow().allocs.get(&alloc) {
1060             return alloc;
1061         }
1062
1063         let interned = self.global_arenas.const_allocs.alloc(alloc);
1064         if let Some(prev) = self.interpret_interner.borrow_mut().allocs.replace(interned) {
1065             bug!("Tried to overwrite interned Allocation: {:#?}", prev)
1066         }
1067         interned
1068     }
1069
1070     /// Allocates a byte or string literal for `mir::interpret`
1071     pub fn allocate_cached(self, bytes: &[u8]) -> interpret::AllocId {
1072         // check whether we already allocated this literal or a constant with the same memory
1073         if let Some(&alloc_id) = self.interpret_interner.borrow().literal_alloc_cache.get(bytes) {
1074             return alloc_id;
1075         }
1076         // create an allocation that just contains these bytes
1077         let alloc = interpret::Allocation::from_bytes(bytes);
1078         let alloc = self.intern_const_alloc(alloc);
1079
1080         let mut int = self.interpret_interner.borrow_mut();
1081         // the next unique id
1082         let id = int.reserve();
1083         // make the allocation identifiable
1084         int.alloc_by_id.insert(id, alloc);
1085         // cache it for the future
1086         int.literal_alloc_cache.insert(bytes.to_owned(), id);
1087         id
1088     }
1089
1090     pub fn intern_stability(self, stab: attr::Stability) -> &'gcx attr::Stability {
1091         if let Some(st) = self.stability_interner.borrow().get(&stab) {
1092             return st;
1093         }
1094
1095         let interned = self.global_interners.arena.alloc(stab);
1096         if let Some(prev) = self.stability_interner.borrow_mut().replace(interned) {
1097             bug!("Tried to overwrite interned Stability: {:?}", prev)
1098         }
1099         interned
1100     }
1101
1102     pub fn intern_layout(self, layout: LayoutDetails) -> &'gcx LayoutDetails {
1103         if let Some(layout) = self.layout_interner.borrow().get(&layout) {
1104             return layout;
1105         }
1106
1107         let interned = self.global_arenas.layout.alloc(layout);
1108         if let Some(prev) = self.layout_interner.borrow_mut().replace(interned) {
1109             bug!("Tried to overwrite interned Layout: {:?}", prev)
1110         }
1111         interned
1112     }
1113
1114     pub fn lift<T: ?Sized + Lift<'tcx>>(self, value: &T) -> Option<T::Lifted> {
1115         value.lift_to_tcx(self)
1116     }
1117
1118     /// Like lift, but only tries in the global tcx.
1119     pub fn lift_to_global<T: ?Sized + Lift<'gcx>>(self, value: &T) -> Option<T::Lifted> {
1120         value.lift_to_tcx(self.global_tcx())
1121     }
1122
1123     /// Returns true if self is the same as self.global_tcx().
1124     fn is_global(self) -> bool {
1125         let local = self.interners as *const _;
1126         let global = &self.global_interners as *const _;
1127         local as usize == global as usize
1128     }
1129
1130     /// Create a type context and call the closure with a `TyCtxt` reference
1131     /// to the context. The closure enforces that the type context and any interned
1132     /// value (types, substs, etc.) can only be used while `ty::tls` has a valid
1133     /// reference to the context, to allow formatting values that need it.
1134     pub fn create_and_enter<F, R>(s: &'tcx Session,
1135                                   cstore: &'tcx dyn CrateStore,
1136                                   local_providers: ty::maps::Providers<'tcx>,
1137                                   extern_providers: ty::maps::Providers<'tcx>,
1138                                   arenas: &'tcx AllArenas<'tcx>,
1139                                   resolutions: ty::Resolutions,
1140                                   hir: hir_map::Map<'tcx>,
1141                                   on_disk_query_result_cache: maps::OnDiskCache<'tcx>,
1142                                   crate_name: &str,
1143                                   tx: mpsc::Sender<Box<dyn Any + Send>>,
1144                                   output_filenames: &OutputFilenames,
1145                                   f: F) -> R
1146                                   where F: for<'b> FnOnce(TyCtxt<'b, 'tcx, 'tcx>) -> R
1147     {
1148         let data_layout = TargetDataLayout::parse(s);
1149         let interners = CtxtInterners::new(&arenas.interner);
1150         let common_types = CommonTypes::new(&interners);
1151         let dep_graph = hir.dep_graph.clone();
1152         let max_cnum = cstore.crates_untracked().iter().map(|c| c.as_usize()).max().unwrap_or(0);
1153         let mut providers = IndexVec::from_elem_n(extern_providers, max_cnum + 1);
1154         providers[LOCAL_CRATE] = local_providers;
1155
1156         let def_path_hash_to_def_id = if s.opts.build_dep_graph() {
1157             let upstream_def_path_tables: Vec<(CrateNum, Lrc<_>)> = cstore
1158                 .crates_untracked()
1159                 .iter()
1160                 .map(|&cnum| (cnum, cstore.def_path_table(cnum)))
1161                 .collect();
1162
1163             let def_path_tables = || {
1164                 upstream_def_path_tables
1165                     .iter()
1166                     .map(|&(cnum, ref rc)| (cnum, &**rc))
1167                     .chain(iter::once((LOCAL_CRATE, hir.definitions().def_path_table())))
1168             };
1169
1170             // Precompute the capacity of the hashmap so we don't have to
1171             // re-allocate when populating it.
1172             let capacity = def_path_tables().map(|(_, t)| t.size()).sum::<usize>();
1173
1174             let mut map: FxHashMap<_, _> = FxHashMap::with_capacity_and_hasher(
1175                 capacity,
1176                 ::std::default::Default::default()
1177             );
1178
1179             for (cnum, def_path_table) in def_path_tables() {
1180                 def_path_table.add_def_path_hashes_to(cnum, &mut map);
1181             }
1182
1183             Some(map)
1184         } else {
1185             None
1186         };
1187
1188         let mut trait_map = FxHashMap();
1189         for (k, v) in resolutions.trait_map {
1190             let hir_id = hir.node_to_hir_id(k);
1191             let map = trait_map.entry(hir_id.owner)
1192                 .or_insert_with(|| Lrc::new(FxHashMap()));
1193             Lrc::get_mut(map).unwrap()
1194                             .insert(hir_id.local_id,
1195                                     Lrc::new(StableVec::new(v)));
1196         }
1197
1198         tls::enter_global(GlobalCtxt {
1199             sess: s,
1200             cstore,
1201             global_arenas: &arenas.global,
1202             global_interners: interners,
1203             dep_graph: dep_graph.clone(),
1204             on_disk_query_result_cache,
1205             types: common_types,
1206             trait_map,
1207             export_map: resolutions.export_map.into_iter().map(|(k, v)| {
1208                 (k, Lrc::new(v))
1209             }).collect(),
1210             freevars: resolutions.freevars.into_iter().map(|(k, v)| {
1211                 (hir.local_def_id(k), Lrc::new(v))
1212             }).collect(),
1213             maybe_unused_trait_imports:
1214                 resolutions.maybe_unused_trait_imports
1215                     .into_iter()
1216                     .map(|id| hir.local_def_id(id))
1217                     .collect(),
1218             maybe_unused_extern_crates:
1219                 resolutions.maybe_unused_extern_crates
1220                     .into_iter()
1221                     .map(|(id, sp)| (hir.local_def_id(id), sp))
1222                     .collect(),
1223             hir,
1224             def_path_hash_to_def_id,
1225             maps: maps::Maps::new(providers),
1226             rcache: RefCell::new(FxHashMap()),
1227             selection_cache: traits::SelectionCache::new(),
1228             evaluation_cache: traits::EvaluationCache::new(),
1229             crate_name: Symbol::intern(crate_name),
1230             data_layout,
1231             layout_interner: RefCell::new(FxHashSet()),
1232             layout_depth: Cell::new(0),
1233             derive_macros: RefCell::new(NodeMap()),
1234             stability_interner: RefCell::new(FxHashSet()),
1235             interpret_interner: Default::default(),
1236             all_traits: RefCell::new(None),
1237             tx_to_llvm_workers: tx,
1238             output_filenames: Arc::new(output_filenames.clone()),
1239        }, f)
1240     }
1241
1242     pub fn consider_optimizing<T: Fn() -> String>(&self, msg: T) -> bool {
1243         let cname = self.crate_name(LOCAL_CRATE).as_str();
1244         self.sess.consider_optimizing(&cname, msg)
1245     }
1246
1247     pub fn lang_items(self) -> Lrc<middle::lang_items::LanguageItems> {
1248         self.get_lang_items(LOCAL_CRATE)
1249     }
1250
1251     pub fn stability(self) -> Lrc<stability::Index<'tcx>> {
1252         self.stability_index(LOCAL_CRATE)
1253     }
1254
1255     pub fn crates(self) -> Lrc<Vec<CrateNum>> {
1256         self.all_crate_nums(LOCAL_CRATE)
1257     }
1258
1259     pub fn features(self) -> Lrc<feature_gate::Features> {
1260         self.features_query(LOCAL_CRATE)
1261     }
1262
1263     pub fn def_key(self, id: DefId) -> hir_map::DefKey {
1264         if id.is_local() {
1265             self.hir.def_key(id)
1266         } else {
1267             self.cstore.def_key(id)
1268         }
1269     }
1270
1271     /// Convert a `DefId` into its fully expanded `DefPath` (every
1272     /// `DefId` is really just an interned def-path).
1273     ///
1274     /// Note that if `id` is not local to this crate, the result will
1275     ///  be a non-local `DefPath`.
1276     pub fn def_path(self, id: DefId) -> hir_map::DefPath {
1277         if id.is_local() {
1278             self.hir.def_path(id)
1279         } else {
1280             self.cstore.def_path(id)
1281         }
1282     }
1283
1284     #[inline]
1285     pub fn def_path_hash(self, def_id: DefId) -> hir_map::DefPathHash {
1286         if def_id.is_local() {
1287             self.hir.definitions().def_path_hash(def_id.index)
1288         } else {
1289             self.cstore.def_path_hash(def_id)
1290         }
1291     }
1292
1293     pub fn def_path_debug_str(self, def_id: DefId) -> String {
1294         // We are explicitly not going through queries here in order to get
1295         // crate name and disambiguator since this code is called from debug!()
1296         // statements within the query system and we'd run into endless
1297         // recursion otherwise.
1298         let (crate_name, crate_disambiguator) = if def_id.is_local() {
1299             (self.crate_name.clone(),
1300              self.sess.local_crate_disambiguator())
1301         } else {
1302             (self.cstore.crate_name_untracked(def_id.krate),
1303              self.cstore.crate_disambiguator_untracked(def_id.krate))
1304         };
1305
1306         format!("{}[{}]{}",
1307                 crate_name,
1308                 // Don't print the whole crate disambiguator. That's just
1309                 // annoying in debug output.
1310                 &(crate_disambiguator.to_fingerprint().to_hex())[..4],
1311                 self.def_path(def_id).to_string_no_crate())
1312     }
1313
1314     pub fn metadata_encoding_version(self) -> Vec<u8> {
1315         self.cstore.metadata_encoding_version().to_vec()
1316     }
1317
1318     // Note that this is *untracked* and should only be used within the query
1319     // system if the result is otherwise tracked through queries
1320     pub fn crate_data_as_rc_any(self, cnum: CrateNum) -> Lrc<dyn Any> {
1321         self.cstore.crate_data_as_rc_any(cnum)
1322     }
1323
1324     pub fn create_stable_hashing_context(self) -> StableHashingContext<'gcx> {
1325         let krate = self.dep_graph.with_ignore(|| self.gcx.hir.krate());
1326
1327         StableHashingContext::new(self.sess,
1328                                   krate,
1329                                   self.hir.definitions(),
1330                                   self.cstore)
1331     }
1332
1333     // This method makes sure that we have a DepNode and a Fingerprint for
1334     // every upstream crate. It needs to be called once right after the tcx is
1335     // created.
1336     // With full-fledged red/green, the method will probably become unnecessary
1337     // as this will be done on-demand.
1338     pub fn allocate_metadata_dep_nodes(self) {
1339         // We cannot use the query versions of crates() and crate_hash(), since
1340         // those would need the DepNodes that we are allocating here.
1341         for cnum in self.cstore.crates_untracked() {
1342             let dep_node = DepNode::new(self, DepConstructor::CrateMetadata(cnum));
1343             let crate_hash = self.cstore.crate_hash_untracked(cnum);
1344             self.dep_graph.with_task(dep_node,
1345                                      self,
1346                                      crate_hash,
1347                                      |_, x| x // No transformation needed
1348             );
1349         }
1350     }
1351
1352     // This method exercises the `in_scope_traits_map` query for all possible
1353     // values so that we have their fingerprints available in the DepGraph.
1354     // This is only required as long as we still use the old dependency tracking
1355     // which needs to have the fingerprints of all input nodes beforehand.
1356     pub fn precompute_in_scope_traits_hashes(self) {
1357         for &def_index in self.trait_map.keys() {
1358             self.in_scope_traits_map(def_index);
1359         }
1360     }
1361
1362     pub fn serialize_query_result_cache<E>(self,
1363                                            encoder: &mut E)
1364                                            -> Result<(), E::Error>
1365         where E: ty::codec::TyEncoder
1366     {
1367         self.on_disk_query_result_cache.serialize(self.global_tcx(), encoder)
1368     }
1369
1370     /// If true, we should use NLL-style region checking instead of
1371     /// lexical style.
1372     pub fn nll(self) -> bool {
1373         self.features().nll || self.sess.opts.debugging_opts.nll
1374     }
1375
1376     /// If true, we should use the MIR-based borrowck (we may *also* use
1377     /// the AST-based borrowck).
1378     pub fn use_mir(self) -> bool {
1379         self.borrowck_mode().use_mir()
1380     }
1381
1382     /// If true, we should enable two-phase borrows checks. This is
1383     /// done with either `-Ztwo-phase-borrows` or with
1384     /// `#![feature(nll)]`.
1385     pub fn two_phase_borrows(self) -> bool {
1386         self.features().nll || self.sess.opts.debugging_opts.two_phase_borrows
1387     }
1388
1389     /// What mode(s) of borrowck should we run? AST? MIR? both?
1390     /// (Also considers the `#![feature(nll)]` setting.)
1391     pub fn borrowck_mode(&self) -> BorrowckMode {
1392         match self.sess.opts.borrowck_mode {
1393             mode @ BorrowckMode::Mir |
1394             mode @ BorrowckMode::Compare => mode,
1395
1396             mode @ BorrowckMode::Ast => {
1397                 if self.nll() {
1398                     BorrowckMode::Mir
1399                 } else {
1400                     mode
1401                 }
1402             }
1403
1404         }
1405     }
1406
1407     /// Should we emit EndRegion MIR statements? These are consumed by
1408     /// MIR borrowck, but not when NLL is used. They are also consumed
1409     /// by the validation stuff.
1410     pub fn emit_end_regions(self) -> bool {
1411         // FIXME(#46875) -- we should not emit end regions when NLL is enabled,
1412         // but for now we can't stop doing so because it causes false positives
1413         self.sess.opts.debugging_opts.emit_end_regions ||
1414             self.sess.opts.debugging_opts.mir_emit_validate > 0 ||
1415             self.use_mir()
1416     }
1417 }
1418
1419 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
1420     pub fn encode_metadata(self, link_meta: &LinkMeta)
1421         -> EncodedMetadata
1422     {
1423         self.cstore.encode_metadata(self, link_meta)
1424     }
1425 }
1426
1427 impl<'gcx: 'tcx, 'tcx> GlobalCtxt<'gcx> {
1428     /// Call the closure with a local `TyCtxt` using the given arena.
1429     pub fn enter_local<F, R>(&self, arena: &'tcx DroplessArena, f: F) -> R
1430         where F: for<'a> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
1431     {
1432         let interners = CtxtInterners::new(arena);
1433         tls::enter(self, &interners, f)
1434     }
1435 }
1436
1437 /// A trait implemented for all X<'a> types which can be safely and
1438 /// efficiently converted to X<'tcx> as long as they are part of the
1439 /// provided TyCtxt<'tcx>.
1440 /// This can be done, for example, for Ty<'tcx> or &'tcx Substs<'tcx>
1441 /// by looking them up in their respective interners.
1442 ///
1443 /// However, this is still not the best implementation as it does
1444 /// need to compare the components, even for interned values.
1445 /// It would be more efficient if TypedArena provided a way to
1446 /// determine whether the address is in the allocated range.
1447 ///
1448 /// None is returned if the value or one of the components is not part
1449 /// of the provided context.
1450 /// For Ty, None can be returned if either the type interner doesn't
1451 /// contain the TypeVariants key or if the address of the interned
1452 /// pointer differs. The latter case is possible if a primitive type,
1453 /// e.g. `()` or `u8`, was interned in a different context.
1454 pub trait Lift<'tcx> {
1455     type Lifted;
1456     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted>;
1457 }
1458
1459 impl<'a, 'tcx> Lift<'tcx> for Ty<'a> {
1460     type Lifted = Ty<'tcx>;
1461     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Ty<'tcx>> {
1462         if tcx.interners.arena.in_arena(*self as *const _) {
1463             return Some(unsafe { mem::transmute(*self) });
1464         }
1465         // Also try in the global tcx if we're not that.
1466         if !tcx.is_global() {
1467             self.lift_to_tcx(tcx.global_tcx())
1468         } else {
1469             None
1470         }
1471     }
1472 }
1473
1474 impl<'a, 'tcx> Lift<'tcx> for Region<'a> {
1475     type Lifted = Region<'tcx>;
1476     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Region<'tcx>> {
1477         if tcx.interners.arena.in_arena(*self as *const _) {
1478             return Some(unsafe { mem::transmute(*self) });
1479         }
1480         // Also try in the global tcx if we're not that.
1481         if !tcx.is_global() {
1482             self.lift_to_tcx(tcx.global_tcx())
1483         } else {
1484             None
1485         }
1486     }
1487 }
1488
1489 impl<'a, 'tcx> Lift<'tcx> for &'a Const<'a> {
1490     type Lifted = &'tcx Const<'tcx>;
1491     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Const<'tcx>> {
1492         if tcx.interners.arena.in_arena(*self as *const _) {
1493             return Some(unsafe { mem::transmute(*self) });
1494         }
1495         // Also try in the global tcx if we're not that.
1496         if !tcx.is_global() {
1497             self.lift_to_tcx(tcx.global_tcx())
1498         } else {
1499             None
1500         }
1501     }
1502 }
1503
1504 impl<'a, 'tcx> Lift<'tcx> for &'a Substs<'a> {
1505     type Lifted = &'tcx Substs<'tcx>;
1506     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Substs<'tcx>> {
1507         if self.len() == 0 {
1508             return Some(Slice::empty());
1509         }
1510         if tcx.interners.arena.in_arena(&self[..] as *const _) {
1511             return Some(unsafe { mem::transmute(*self) });
1512         }
1513         // Also try in the global tcx if we're not that.
1514         if !tcx.is_global() {
1515             self.lift_to_tcx(tcx.global_tcx())
1516         } else {
1517             None
1518         }
1519     }
1520 }
1521
1522 impl<'a, 'tcx> Lift<'tcx> for &'a Slice<Ty<'a>> {
1523     type Lifted = &'tcx Slice<Ty<'tcx>>;
1524     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
1525                              -> Option<&'tcx Slice<Ty<'tcx>>> {
1526         if self.len() == 0 {
1527             return Some(Slice::empty());
1528         }
1529         if tcx.interners.arena.in_arena(*self as *const _) {
1530             return Some(unsafe { mem::transmute(*self) });
1531         }
1532         // Also try in the global tcx if we're not that.
1533         if !tcx.is_global() {
1534             self.lift_to_tcx(tcx.global_tcx())
1535         } else {
1536             None
1537         }
1538     }
1539 }
1540
1541 impl<'a, 'tcx> Lift<'tcx> for &'a Slice<ExistentialPredicate<'a>> {
1542     type Lifted = &'tcx Slice<ExistentialPredicate<'tcx>>;
1543     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
1544         -> Option<&'tcx Slice<ExistentialPredicate<'tcx>>> {
1545         if self.is_empty() {
1546             return Some(Slice::empty());
1547         }
1548         if tcx.interners.arena.in_arena(*self as *const _) {
1549             return Some(unsafe { mem::transmute(*self) });
1550         }
1551         // Also try in the global tcx if we're not that.
1552         if !tcx.is_global() {
1553             self.lift_to_tcx(tcx.global_tcx())
1554         } else {
1555             None
1556         }
1557     }
1558 }
1559
1560 impl<'a, 'tcx> Lift<'tcx> for &'a Slice<Predicate<'a>> {
1561     type Lifted = &'tcx Slice<Predicate<'tcx>>;
1562     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
1563         -> Option<&'tcx Slice<Predicate<'tcx>>> {
1564         if self.is_empty() {
1565             return Some(Slice::empty());
1566         }
1567         if tcx.interners.arena.in_arena(*self as *const _) {
1568             return Some(unsafe { mem::transmute(*self) });
1569         }
1570         // Also try in the global tcx if we're not that.
1571         if !tcx.is_global() {
1572             self.lift_to_tcx(tcx.global_tcx())
1573         } else {
1574             None
1575         }
1576     }
1577 }
1578
1579 pub mod tls {
1580     use super::{CtxtInterners, GlobalCtxt, TyCtxt};
1581
1582     use std::cell::Cell;
1583     use std::fmt;
1584     use syntax_pos;
1585
1586     /// Marker types used for the scoped TLS slot.
1587     /// The type context cannot be used directly because the scoped TLS
1588     /// in libstd doesn't allow types generic over lifetimes.
1589     enum ThreadLocalGlobalCtxt {}
1590     enum ThreadLocalInterners {}
1591
1592     thread_local! {
1593         static TLS_TCX: Cell<Option<(*const ThreadLocalGlobalCtxt,
1594                                      *const ThreadLocalInterners)>> = Cell::new(None)
1595     }
1596
1597     fn span_debug(span: syntax_pos::Span, f: &mut fmt::Formatter) -> fmt::Result {
1598         with(|tcx| {
1599             write!(f, "{}", tcx.sess.codemap().span_to_string(span))
1600         })
1601     }
1602
1603     pub fn enter_global<'gcx, F, R>(gcx: GlobalCtxt<'gcx>, f: F) -> R
1604         where F: for<'a> FnOnce(TyCtxt<'a, 'gcx, 'gcx>) -> R
1605     {
1606         syntax_pos::SPAN_DEBUG.with(|span_dbg| {
1607             let original_span_debug = span_dbg.get();
1608             span_dbg.set(span_debug);
1609             let result = enter(&gcx, &gcx.global_interners, f);
1610             span_dbg.set(original_span_debug);
1611             result
1612         })
1613     }
1614
1615     pub fn enter<'a, 'gcx: 'tcx, 'tcx, F, R>(gcx: &'a GlobalCtxt<'gcx>,
1616                                              interners: &'a CtxtInterners<'tcx>,
1617                                              f: F) -> R
1618         where F: FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
1619     {
1620         let gcx_ptr = gcx as *const _ as *const ThreadLocalGlobalCtxt;
1621         let interners_ptr = interners as *const _ as *const ThreadLocalInterners;
1622         TLS_TCX.with(|tls| {
1623             let prev = tls.get();
1624             tls.set(Some((gcx_ptr, interners_ptr)));
1625             let ret = f(TyCtxt {
1626                 gcx,
1627                 interners,
1628             });
1629             tls.set(prev);
1630             ret
1631         })
1632     }
1633
1634     pub fn with<F, R>(f: F) -> R
1635         where F: for<'a, 'gcx, 'tcx> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
1636     {
1637         TLS_TCX.with(|tcx| {
1638             let (gcx, interners) = tcx.get().unwrap();
1639             let gcx = unsafe { &*(gcx as *const GlobalCtxt) };
1640             let interners = unsafe { &*(interners as *const CtxtInterners) };
1641             f(TyCtxt {
1642                 gcx,
1643                 interners,
1644             })
1645         })
1646     }
1647
1648     pub fn with_opt<F, R>(f: F) -> R
1649         where F: for<'a, 'gcx, 'tcx> FnOnce(Option<TyCtxt<'a, 'gcx, 'tcx>>) -> R
1650     {
1651         if TLS_TCX.with(|tcx| tcx.get().is_some()) {
1652             with(|v| f(Some(v)))
1653         } else {
1654             f(None)
1655         }
1656     }
1657 }
1658
1659 macro_rules! sty_debug_print {
1660     ($ctxt: expr, $($variant: ident),*) => {{
1661         // curious inner module to allow variant names to be used as
1662         // variable names.
1663         #[allow(non_snake_case)]
1664         mod inner {
1665             use ty::{self, TyCtxt};
1666             use ty::context::Interned;
1667
1668             #[derive(Copy, Clone)]
1669             struct DebugStat {
1670                 total: usize,
1671                 region_infer: usize,
1672                 ty_infer: usize,
1673                 both_infer: usize,
1674             }
1675
1676             pub fn go(tcx: TyCtxt) {
1677                 let mut total = DebugStat {
1678                     total: 0,
1679                     region_infer: 0, ty_infer: 0, both_infer: 0,
1680                 };
1681                 $(let mut $variant = total;)*
1682
1683
1684                 for &Interned(t) in tcx.interners.type_.borrow().iter() {
1685                     let variant = match t.sty {
1686                         ty::TyBool | ty::TyChar | ty::TyInt(..) | ty::TyUint(..) |
1687                             ty::TyFloat(..) | ty::TyStr | ty::TyNever => continue,
1688                         ty::TyError => /* unimportant */ continue,
1689                         $(ty::$variant(..) => &mut $variant,)*
1690                     };
1691                     let region = t.flags.intersects(ty::TypeFlags::HAS_RE_INFER);
1692                     let ty = t.flags.intersects(ty::TypeFlags::HAS_TY_INFER);
1693
1694                     variant.total += 1;
1695                     total.total += 1;
1696                     if region { total.region_infer += 1; variant.region_infer += 1 }
1697                     if ty { total.ty_infer += 1; variant.ty_infer += 1 }
1698                     if region && ty { total.both_infer += 1; variant.both_infer += 1 }
1699                 }
1700                 println!("Ty interner             total           ty region  both");
1701                 $(println!("    {:18}: {uses:6} {usespc:4.1}%, \
1702 {ty:4.1}% {region:5.1}% {both:4.1}%",
1703                            stringify!($variant),
1704                            uses = $variant.total,
1705                            usespc = $variant.total as f64 * 100.0 / total.total as f64,
1706                            ty = $variant.ty_infer as f64 * 100.0  / total.total as f64,
1707                            region = $variant.region_infer as f64 * 100.0  / total.total as f64,
1708                            both = $variant.both_infer as f64 * 100.0  / total.total as f64);
1709                   )*
1710                 println!("                  total {uses:6}        \
1711 {ty:4.1}% {region:5.1}% {both:4.1}%",
1712                          uses = total.total,
1713                          ty = total.ty_infer as f64 * 100.0  / total.total as f64,
1714                          region = total.region_infer as f64 * 100.0  / total.total as f64,
1715                          both = total.both_infer as f64 * 100.0  / total.total as f64)
1716             }
1717         }
1718
1719         inner::go($ctxt)
1720     }}
1721 }
1722
1723 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
1724     pub fn print_debug_stats(self) {
1725         sty_debug_print!(
1726             self,
1727             TyAdt, TyArray, TySlice, TyRawPtr, TyRef, TyFnDef, TyFnPtr,
1728             TyGenerator, TyGeneratorWitness, TyDynamic, TyClosure, TyTuple,
1729             TyParam, TyInfer, TyProjection, TyAnon, TyForeign);
1730
1731         println!("Substs interner: #{}", self.interners.substs.borrow().len());
1732         println!("Region interner: #{}", self.interners.region.borrow().len());
1733         println!("Stability interner: #{}", self.stability_interner.borrow().len());
1734         println!("Interpret interner: #{}", self.interpret_interner.borrow().allocs.len());
1735         println!("Layout interner: #{}", self.layout_interner.borrow().len());
1736     }
1737 }
1738
1739
1740 /// An entry in an interner.
1741 struct Interned<'tcx, T: 'tcx+?Sized>(&'tcx T);
1742
1743 // NB: An Interned<Ty> compares and hashes as a sty.
1744 impl<'tcx> PartialEq for Interned<'tcx, TyS<'tcx>> {
1745     fn eq(&self, other: &Interned<'tcx, TyS<'tcx>>) -> bool {
1746         self.0.sty == other.0.sty
1747     }
1748 }
1749
1750 impl<'tcx> Eq for Interned<'tcx, TyS<'tcx>> {}
1751
1752 impl<'tcx> Hash for Interned<'tcx, TyS<'tcx>> {
1753     fn hash<H: Hasher>(&self, s: &mut H) {
1754         self.0.sty.hash(s)
1755     }
1756 }
1757
1758 impl<'tcx: 'lcx, 'lcx> Borrow<TypeVariants<'lcx>> for Interned<'tcx, TyS<'tcx>> {
1759     fn borrow<'a>(&'a self) -> &'a TypeVariants<'lcx> {
1760         &self.0.sty
1761     }
1762 }
1763
1764 // NB: An Interned<Slice<T>> compares and hashes as its elements.
1765 impl<'tcx, T: PartialEq> PartialEq for Interned<'tcx, Slice<T>> {
1766     fn eq(&self, other: &Interned<'tcx, Slice<T>>) -> bool {
1767         self.0[..] == other.0[..]
1768     }
1769 }
1770
1771 impl<'tcx, T: Eq> Eq for Interned<'tcx, Slice<T>> {}
1772
1773 impl<'tcx, T: Hash> Hash for Interned<'tcx, Slice<T>> {
1774     fn hash<H: Hasher>(&self, s: &mut H) {
1775         self.0[..].hash(s)
1776     }
1777 }
1778
1779 impl<'tcx: 'lcx, 'lcx> Borrow<[Ty<'lcx>]> for Interned<'tcx, Slice<Ty<'tcx>>> {
1780     fn borrow<'a>(&'a self) -> &'a [Ty<'lcx>] {
1781         &self.0[..]
1782     }
1783 }
1784
1785 impl<'tcx: 'lcx, 'lcx> Borrow<[Kind<'lcx>]> for Interned<'tcx, Substs<'tcx>> {
1786     fn borrow<'a>(&'a self) -> &'a [Kind<'lcx>] {
1787         &self.0[..]
1788     }
1789 }
1790
1791 impl<'tcx> Borrow<RegionKind> for Interned<'tcx, RegionKind> {
1792     fn borrow<'a>(&'a self) -> &'a RegionKind {
1793         &self.0
1794     }
1795 }
1796
1797 impl<'tcx: 'lcx, 'lcx> Borrow<[ExistentialPredicate<'lcx>]>
1798     for Interned<'tcx, Slice<ExistentialPredicate<'tcx>>> {
1799     fn borrow<'a>(&'a self) -> &'a [ExistentialPredicate<'lcx>] {
1800         &self.0[..]
1801     }
1802 }
1803
1804 impl<'tcx: 'lcx, 'lcx> Borrow<[Predicate<'lcx>]>
1805     for Interned<'tcx, Slice<Predicate<'tcx>>> {
1806     fn borrow<'a>(&'a self) -> &'a [Predicate<'lcx>] {
1807         &self.0[..]
1808     }
1809 }
1810
1811 impl<'tcx: 'lcx, 'lcx> Borrow<Const<'lcx>> for Interned<'tcx, Const<'tcx>> {
1812     fn borrow<'a>(&'a self) -> &'a Const<'lcx> {
1813         &self.0
1814     }
1815 }
1816
1817 macro_rules! intern_method {
1818     ($lt_tcx:tt, $name:ident: $method:ident($alloc:ty,
1819                                             $alloc_method:ident,
1820                                             $alloc_to_key:expr,
1821                                             $alloc_to_ret:expr,
1822                                             $needs_infer:expr) -> $ty:ty) => {
1823         impl<'a, 'gcx, $lt_tcx> TyCtxt<'a, 'gcx, $lt_tcx> {
1824             pub fn $method(self, v: $alloc) -> &$lt_tcx $ty {
1825                 {
1826                     let key = ($alloc_to_key)(&v);
1827                     if let Some(i) = self.interners.$name.borrow().get(key) {
1828                         return i.0;
1829                     }
1830                     if !self.is_global() {
1831                         if let Some(i) = self.global_interners.$name.borrow().get(key) {
1832                             return i.0;
1833                         }
1834                     }
1835                 }
1836
1837                 // HACK(eddyb) Depend on flags being accurate to
1838                 // determine that all contents are in the global tcx.
1839                 // See comments on Lift for why we can't use that.
1840                 if !($needs_infer)(&v) {
1841                     if !self.is_global() {
1842                         let v = unsafe {
1843                             mem::transmute(v)
1844                         };
1845                         let i = ($alloc_to_ret)(self.global_interners.arena.$alloc_method(v));
1846                         self.global_interners.$name.borrow_mut().insert(Interned(i));
1847                         return i;
1848                     }
1849                 } else {
1850                     // Make sure we don't end up with inference
1851                     // types/regions in the global tcx.
1852                     if self.is_global() {
1853                         bug!("Attempted to intern `{:?}` which contains \
1854                               inference types/regions in the global type context",
1855                              v);
1856                     }
1857                 }
1858
1859                 let i = ($alloc_to_ret)(self.interners.arena.$alloc_method(v));
1860                 self.interners.$name.borrow_mut().insert(Interned(i));
1861                 i
1862             }
1863         }
1864     }
1865 }
1866
1867 macro_rules! direct_interners {
1868     ($lt_tcx:tt, $($name:ident: $method:ident($needs_infer:expr) -> $ty:ty),+) => {
1869         $(impl<$lt_tcx> PartialEq for Interned<$lt_tcx, $ty> {
1870             fn eq(&self, other: &Self) -> bool {
1871                 self.0 == other.0
1872             }
1873         }
1874
1875         impl<$lt_tcx> Eq for Interned<$lt_tcx, $ty> {}
1876
1877         impl<$lt_tcx> Hash for Interned<$lt_tcx, $ty> {
1878             fn hash<H: Hasher>(&self, s: &mut H) {
1879                 self.0.hash(s)
1880             }
1881         }
1882
1883         intern_method!($lt_tcx, $name: $method($ty, alloc, |x| x, |x| x, $needs_infer) -> $ty);)+
1884     }
1885 }
1886
1887 pub fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
1888     x.has_type_flags(ty::TypeFlags::KEEP_IN_LOCAL_TCX)
1889 }
1890
1891 direct_interners!('tcx,
1892     region: mk_region(|r| {
1893         match r {
1894             &ty::ReVar(_) | &ty::ReSkolemized(..) => true,
1895             _ => false
1896         }
1897     }) -> RegionKind,
1898     const_: mk_const(|c: &Const| keep_local(&c.ty) || keep_local(&c.val)) -> Const<'tcx>
1899 );
1900
1901 macro_rules! slice_interners {
1902     ($($field:ident: $method:ident($ty:ident)),+) => (
1903         $(intern_method!('tcx, $field: $method(&[$ty<'tcx>], alloc_slice, Deref::deref,
1904                                                |xs: &[$ty]| -> &Slice<$ty> {
1905             unsafe { mem::transmute(xs) }
1906         }, |xs: &[$ty]| xs.iter().any(keep_local)) -> Slice<$ty<'tcx>>);)+
1907     )
1908 }
1909
1910 slice_interners!(
1911     existential_predicates: _intern_existential_predicates(ExistentialPredicate),
1912     predicates: _intern_predicates(Predicate),
1913     type_list: _intern_type_list(Ty),
1914     substs: _intern_substs(Kind)
1915 );
1916
1917 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
1918     /// Given a `fn` type, returns an equivalent `unsafe fn` type;
1919     /// that is, a `fn` type that is equivalent in every way for being
1920     /// unsafe.
1921     pub fn safe_to_unsafe_fn_ty(self, sig: PolyFnSig<'tcx>) -> Ty<'tcx> {
1922         assert_eq!(sig.unsafety(), hir::Unsafety::Normal);
1923         self.mk_fn_ptr(sig.map_bound(|sig| ty::FnSig {
1924             unsafety: hir::Unsafety::Unsafe,
1925             ..sig
1926         }))
1927     }
1928
1929     /// Given a closure signature `sig`, returns an equivalent `fn`
1930     /// type with the same signature. Detuples and so forth -- so
1931     /// e.g. if we have a sig with `Fn<(u32, i32)>` then you would get
1932     /// a `fn(u32, i32)`.
1933     pub fn coerce_closure_fn_ty(self, sig: PolyFnSig<'tcx>) -> Ty<'tcx> {
1934         let converted_sig = sig.map_bound(|s| {
1935             let params_iter = match s.inputs()[0].sty {
1936                 ty::TyTuple(params, _) => {
1937                     params.into_iter().cloned()
1938                 }
1939                 _ => bug!(),
1940             };
1941             self.mk_fn_sig(
1942                 params_iter,
1943                 s.output(),
1944                 s.variadic,
1945                 hir::Unsafety::Normal,
1946                 abi::Abi::Rust,
1947             )
1948         });
1949
1950         self.mk_fn_ptr(converted_sig)
1951     }
1952
1953     // Interns a type/name combination, stores the resulting box in cx.interners,
1954     // and returns the box as cast to an unsafe ptr (see comments for Ty above).
1955     pub fn mk_ty(self, st: TypeVariants<'tcx>) -> Ty<'tcx> {
1956         let global_interners = if !self.is_global() {
1957             Some(&self.global_interners)
1958         } else {
1959             None
1960         };
1961         self.interners.intern_ty(st, global_interners)
1962     }
1963
1964     pub fn mk_mach_int(self, tm: ast::IntTy) -> Ty<'tcx> {
1965         match tm {
1966             ast::IntTy::Isize   => self.types.isize,
1967             ast::IntTy::I8   => self.types.i8,
1968             ast::IntTy::I16  => self.types.i16,
1969             ast::IntTy::I32  => self.types.i32,
1970             ast::IntTy::I64  => self.types.i64,
1971             ast::IntTy::I128  => self.types.i128,
1972         }
1973     }
1974
1975     pub fn mk_mach_uint(self, tm: ast::UintTy) -> Ty<'tcx> {
1976         match tm {
1977             ast::UintTy::Usize   => self.types.usize,
1978             ast::UintTy::U8   => self.types.u8,
1979             ast::UintTy::U16  => self.types.u16,
1980             ast::UintTy::U32  => self.types.u32,
1981             ast::UintTy::U64  => self.types.u64,
1982             ast::UintTy::U128  => self.types.u128,
1983         }
1984     }
1985
1986     pub fn mk_mach_float(self, tm: ast::FloatTy) -> Ty<'tcx> {
1987         match tm {
1988             ast::FloatTy::F32  => self.types.f32,
1989             ast::FloatTy::F64  => self.types.f64,
1990         }
1991     }
1992
1993     pub fn mk_str(self) -> Ty<'tcx> {
1994         self.mk_ty(TyStr)
1995     }
1996
1997     pub fn mk_static_str(self) -> Ty<'tcx> {
1998         self.mk_imm_ref(self.types.re_static, self.mk_str())
1999     }
2000
2001     pub fn mk_adt(self, def: &'tcx AdtDef, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
2002         // take a copy of substs so that we own the vectors inside
2003         self.mk_ty(TyAdt(def, substs))
2004     }
2005
2006     pub fn mk_foreign(self, def_id: DefId) -> Ty<'tcx> {
2007         self.mk_ty(TyForeign(def_id))
2008     }
2009
2010     pub fn mk_box(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2011         let def_id = self.require_lang_item(lang_items::OwnedBoxLangItem);
2012         let adt_def = self.adt_def(def_id);
2013         let substs = self.mk_substs(iter::once(Kind::from(ty)));
2014         self.mk_ty(TyAdt(adt_def, substs))
2015     }
2016
2017     pub fn mk_ptr(self, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
2018         self.mk_ty(TyRawPtr(tm))
2019     }
2020
2021     pub fn mk_ref(self, r: Region<'tcx>, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
2022         self.mk_ty(TyRef(r, tm))
2023     }
2024
2025     pub fn mk_mut_ref(self, r: Region<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
2026         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutMutable})
2027     }
2028
2029     pub fn mk_imm_ref(self, r: Region<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
2030         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
2031     }
2032
2033     pub fn mk_mut_ptr(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2034         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutMutable})
2035     }
2036
2037     pub fn mk_imm_ptr(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2038         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
2039     }
2040
2041     pub fn mk_nil_ptr(self) -> Ty<'tcx> {
2042         self.mk_imm_ptr(self.mk_nil())
2043     }
2044
2045     pub fn mk_array(self, ty: Ty<'tcx>, n: u64) -> Ty<'tcx> {
2046         let n = ConstUsize::new(n, self.sess.target.usize_ty).unwrap();
2047         self.mk_array_const_usize(ty, n)
2048     }
2049
2050     pub fn mk_array_const_usize(self, ty: Ty<'tcx>, n: ConstUsize) -> Ty<'tcx> {
2051         self.mk_ty(TyArray(ty, self.mk_const(ty::Const {
2052             val: ConstVal::Integral(ConstInt::Usize(n)),
2053             ty: self.types.usize
2054         })))
2055     }
2056
2057     pub fn mk_slice(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2058         self.mk_ty(TySlice(ty))
2059     }
2060
2061     pub fn intern_tup(self, ts: &[Ty<'tcx>], defaulted: bool) -> Ty<'tcx> {
2062         self.mk_ty(TyTuple(self.intern_type_list(ts), defaulted))
2063     }
2064
2065     pub fn mk_tup<I: InternAs<[Ty<'tcx>], Ty<'tcx>>>(self, iter: I,
2066                                                      defaulted: bool) -> I::Output {
2067         iter.intern_with(|ts| self.mk_ty(TyTuple(self.intern_type_list(ts), defaulted)))
2068     }
2069
2070     pub fn mk_nil(self) -> Ty<'tcx> {
2071         self.intern_tup(&[], false)
2072     }
2073
2074     pub fn mk_diverging_default(self) -> Ty<'tcx> {
2075         if self.features().never_type {
2076             self.types.never
2077         } else {
2078             self.intern_tup(&[], true)
2079         }
2080     }
2081
2082     pub fn mk_bool(self) -> Ty<'tcx> {
2083         self.mk_ty(TyBool)
2084     }
2085
2086     pub fn mk_fn_def(self, def_id: DefId,
2087                      substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
2088         self.mk_ty(TyFnDef(def_id, substs))
2089     }
2090
2091     pub fn mk_fn_ptr(self, fty: PolyFnSig<'tcx>) -> Ty<'tcx> {
2092         self.mk_ty(TyFnPtr(fty))
2093     }
2094
2095     pub fn mk_dynamic(
2096         self,
2097         obj: ty::Binder<&'tcx Slice<ExistentialPredicate<'tcx>>>,
2098         reg: ty::Region<'tcx>
2099     ) -> Ty<'tcx> {
2100         self.mk_ty(TyDynamic(obj, reg))
2101     }
2102
2103     pub fn mk_projection(self,
2104                          item_def_id: DefId,
2105                          substs: &'tcx Substs<'tcx>)
2106         -> Ty<'tcx> {
2107             self.mk_ty(TyProjection(ProjectionTy {
2108                 item_def_id,
2109                 substs,
2110             }))
2111         }
2112
2113     pub fn mk_closure(self,
2114                       closure_id: DefId,
2115                       substs: ClosureSubsts<'tcx>)
2116                       -> Ty<'tcx> {
2117         self.mk_closure_from_closure_substs(closure_id, substs)
2118     }
2119
2120     pub fn mk_closure_from_closure_substs(self,
2121                                           closure_id: DefId,
2122                                           closure_substs: ClosureSubsts<'tcx>)
2123                                           -> Ty<'tcx> {
2124         self.mk_ty(TyClosure(closure_id, closure_substs))
2125     }
2126
2127     pub fn mk_generator(self,
2128                         id: DefId,
2129                         closure_substs: ClosureSubsts<'tcx>,
2130                         interior: GeneratorInterior<'tcx>)
2131                         -> Ty<'tcx> {
2132         self.mk_ty(TyGenerator(id, closure_substs, interior))
2133     }
2134
2135     pub fn mk_generator_witness(self, types: ty::Binder<&'tcx Slice<Ty<'tcx>>>) -> Ty<'tcx> {
2136         self.mk_ty(TyGeneratorWitness(types))
2137     }
2138
2139     pub fn mk_var(self, v: TyVid) -> Ty<'tcx> {
2140         self.mk_infer(TyVar(v))
2141     }
2142
2143     pub fn mk_int_var(self, v: IntVid) -> Ty<'tcx> {
2144         self.mk_infer(IntVar(v))
2145     }
2146
2147     pub fn mk_float_var(self, v: FloatVid) -> Ty<'tcx> {
2148         self.mk_infer(FloatVar(v))
2149     }
2150
2151     pub fn mk_infer(self, it: InferTy) -> Ty<'tcx> {
2152         self.mk_ty(TyInfer(it))
2153     }
2154
2155     pub fn mk_param(self,
2156                     index: u32,
2157                     name: Name) -> Ty<'tcx> {
2158         self.mk_ty(TyParam(ParamTy { idx: index, name: name }))
2159     }
2160
2161     pub fn mk_self_type(self) -> Ty<'tcx> {
2162         self.mk_param(0, keywords::SelfType.name())
2163     }
2164
2165     pub fn mk_param_from_def(self, def: &ty::TypeParameterDef) -> Ty<'tcx> {
2166         self.mk_param(def.index, def.name)
2167     }
2168
2169     pub fn mk_anon(self, def_id: DefId, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
2170         self.mk_ty(TyAnon(def_id, substs))
2171     }
2172
2173     pub fn intern_existential_predicates(self, eps: &[ExistentialPredicate<'tcx>])
2174         -> &'tcx Slice<ExistentialPredicate<'tcx>> {
2175         assert!(!eps.is_empty());
2176         assert!(eps.windows(2).all(|w| w[0].cmp(self, &w[1]) != Ordering::Greater));
2177         self._intern_existential_predicates(eps)
2178     }
2179
2180     pub fn intern_predicates(self, preds: &[Predicate<'tcx>])
2181         -> &'tcx Slice<Predicate<'tcx>> {
2182         // FIXME consider asking the input slice to be sorted to avoid
2183         // re-interning permutations, in which case that would be asserted
2184         // here.
2185         if preds.len() == 0 {
2186             // The macro-generated method below asserts we don't intern an empty slice.
2187             Slice::empty()
2188         } else {
2189             self._intern_predicates(preds)
2190         }
2191     }
2192
2193     pub fn intern_type_list(self, ts: &[Ty<'tcx>]) -> &'tcx Slice<Ty<'tcx>> {
2194         if ts.len() == 0 {
2195             Slice::empty()
2196         } else {
2197             self._intern_type_list(ts)
2198         }
2199     }
2200
2201     pub fn intern_substs(self, ts: &[Kind<'tcx>]) -> &'tcx Slice<Kind<'tcx>> {
2202         if ts.len() == 0 {
2203             Slice::empty()
2204         } else {
2205             self._intern_substs(ts)
2206         }
2207     }
2208
2209     pub fn mk_fn_sig<I>(self,
2210                         inputs: I,
2211                         output: I::Item,
2212                         variadic: bool,
2213                         unsafety: hir::Unsafety,
2214                         abi: abi::Abi)
2215         -> <I::Item as InternIteratorElement<Ty<'tcx>, ty::FnSig<'tcx>>>::Output
2216         where I: Iterator,
2217               I::Item: InternIteratorElement<Ty<'tcx>, ty::FnSig<'tcx>>
2218     {
2219         inputs.chain(iter::once(output)).intern_with(|xs| ty::FnSig {
2220             inputs_and_output: self.intern_type_list(xs),
2221             variadic, unsafety, abi
2222         })
2223     }
2224
2225     pub fn mk_existential_predicates<I: InternAs<[ExistentialPredicate<'tcx>],
2226                                      &'tcx Slice<ExistentialPredicate<'tcx>>>>(self, iter: I)
2227                                      -> I::Output {
2228         iter.intern_with(|xs| self.intern_existential_predicates(xs))
2229     }
2230
2231     pub fn mk_predicates<I: InternAs<[Predicate<'tcx>],
2232                                      &'tcx Slice<Predicate<'tcx>>>>(self, iter: I)
2233                                      -> I::Output {
2234         iter.intern_with(|xs| self.intern_predicates(xs))
2235     }
2236
2237     pub fn mk_type_list<I: InternAs<[Ty<'tcx>],
2238                         &'tcx Slice<Ty<'tcx>>>>(self, iter: I) -> I::Output {
2239         iter.intern_with(|xs| self.intern_type_list(xs))
2240     }
2241
2242     pub fn mk_substs<I: InternAs<[Kind<'tcx>],
2243                      &'tcx Slice<Kind<'tcx>>>>(self, iter: I) -> I::Output {
2244         iter.intern_with(|xs| self.intern_substs(xs))
2245     }
2246
2247     pub fn mk_substs_trait(self,
2248                      s: Ty<'tcx>,
2249                      t: &[Ty<'tcx>])
2250                     -> &'tcx Substs<'tcx>
2251     {
2252         self.mk_substs(iter::once(s).chain(t.into_iter().cloned()).map(Kind::from))
2253     }
2254
2255     pub fn lint_node<S: Into<MultiSpan>>(self,
2256                                          lint: &'static Lint,
2257                                          id: NodeId,
2258                                          span: S,
2259                                          msg: &str) {
2260         self.struct_span_lint_node(lint, id, span.into(), msg).emit()
2261     }
2262
2263     pub fn lint_node_note<S: Into<MultiSpan>>(self,
2264                                               lint: &'static Lint,
2265                                               id: NodeId,
2266                                               span: S,
2267                                               msg: &str,
2268                                               note: &str) {
2269         let mut err = self.struct_span_lint_node(lint, id, span.into(), msg);
2270         err.note(note);
2271         err.emit()
2272     }
2273
2274     pub fn lint_level_at_node(self, lint: &'static Lint, mut id: NodeId)
2275         -> (lint::Level, lint::LintSource)
2276     {
2277         // Right now we insert a `with_ignore` node in the dep graph here to
2278         // ignore the fact that `lint_levels` below depends on the entire crate.
2279         // For now this'll prevent false positives of recompiling too much when
2280         // anything changes.
2281         //
2282         // Once red/green incremental compilation lands we should be able to
2283         // remove this because while the crate changes often the lint level map
2284         // will change rarely.
2285         self.dep_graph.with_ignore(|| {
2286             let sets = self.lint_levels(LOCAL_CRATE);
2287             loop {
2288                 let hir_id = self.hir.definitions().node_to_hir_id(id);
2289                 if let Some(pair) = sets.level_and_source(lint, hir_id, self.sess) {
2290                     return pair
2291                 }
2292                 let next = self.hir.get_parent_node(id);
2293                 if next == id {
2294                     bug!("lint traversal reached the root of the crate");
2295                 }
2296                 id = next;
2297             }
2298         })
2299     }
2300
2301     pub fn struct_span_lint_node<S: Into<MultiSpan>>(self,
2302                                                      lint: &'static Lint,
2303                                                      id: NodeId,
2304                                                      span: S,
2305                                                      msg: &str)
2306         -> DiagnosticBuilder<'tcx>
2307     {
2308         let (level, src) = self.lint_level_at_node(lint, id);
2309         lint::struct_lint_level(self.sess, lint, level, src, Some(span.into()), msg)
2310     }
2311
2312     pub fn struct_lint_node(self, lint: &'static Lint, id: NodeId, msg: &str)
2313         -> DiagnosticBuilder<'tcx>
2314     {
2315         let (level, src) = self.lint_level_at_node(lint, id);
2316         lint::struct_lint_level(self.sess, lint, level, src, None, msg)
2317     }
2318
2319     pub fn in_scope_traits(self, id: HirId) -> Option<Lrc<StableVec<TraitCandidate>>> {
2320         self.in_scope_traits_map(id.owner)
2321             .and_then(|map| map.get(&id.local_id).cloned())
2322     }
2323
2324     pub fn named_region(self, id: HirId) -> Option<resolve_lifetime::Region> {
2325         self.named_region_map(id.owner)
2326             .and_then(|map| map.get(&id.local_id).cloned())
2327     }
2328
2329     pub fn is_late_bound(self, id: HirId) -> bool {
2330         self.is_late_bound_map(id.owner)
2331             .map(|set| set.contains(&id.local_id))
2332             .unwrap_or(false)
2333     }
2334
2335     pub fn object_lifetime_defaults(self, id: HirId)
2336         -> Option<Lrc<Vec<ObjectLifetimeDefault>>>
2337     {
2338         self.object_lifetime_defaults_map(id.owner)
2339             .and_then(|map| map.get(&id.local_id).cloned())
2340     }
2341 }
2342
2343 pub trait InternAs<T: ?Sized, R> {
2344     type Output;
2345     fn intern_with<F>(self, f: F) -> Self::Output
2346         where F: FnOnce(&T) -> R;
2347 }
2348
2349 impl<I, T, R, E> InternAs<[T], R> for I
2350     where E: InternIteratorElement<T, R>,
2351           I: Iterator<Item=E> {
2352     type Output = E::Output;
2353     fn intern_with<F>(self, f: F) -> Self::Output
2354         where F: FnOnce(&[T]) -> R {
2355         E::intern_with(self, f)
2356     }
2357 }
2358
2359 pub trait InternIteratorElement<T, R>: Sized {
2360     type Output;
2361     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output;
2362 }
2363
2364 impl<T, R> InternIteratorElement<T, R> for T {
2365     type Output = R;
2366     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
2367         f(&iter.collect::<AccumulateVec<[_; 8]>>())
2368     }
2369 }
2370
2371 impl<'a, T, R> InternIteratorElement<T, R> for &'a T
2372     where T: Clone + 'a
2373 {
2374     type Output = R;
2375     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
2376         f(&iter.cloned().collect::<AccumulateVec<[_; 8]>>())
2377     }
2378 }
2379
2380 impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> {
2381     type Output = Result<R, E>;
2382     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
2383         Ok(f(&iter.collect::<Result<AccumulateVec<[_; 8]>, _>>()?))
2384     }
2385 }
2386
2387 pub fn provide(providers: &mut ty::maps::Providers) {
2388     // FIXME(#44234) - almost all of these queries have no sub-queries and
2389     // therefore no actual inputs, they're just reading tables calculated in
2390     // resolve! Does this work? Unsure! That's what the issue is about
2391     providers.in_scope_traits_map = |tcx, id| tcx.gcx.trait_map.get(&id).cloned();
2392     providers.module_exports = |tcx, id| tcx.gcx.export_map.get(&id).cloned();
2393     providers.crate_name = |tcx, id| {
2394         assert_eq!(id, LOCAL_CRATE);
2395         tcx.crate_name
2396     };
2397     providers.get_lang_items = |tcx, id| {
2398         assert_eq!(id, LOCAL_CRATE);
2399         // FIXME(#42293) Right now we insert a `with_ignore` node in the dep
2400         // graph here to ignore the fact that `get_lang_items` below depends on
2401         // the entire crate.  For now this'll prevent false positives of
2402         // recompiling too much when anything changes.
2403         //
2404         // Once red/green incremental compilation lands we should be able to
2405         // remove this because while the crate changes often the lint level map
2406         // will change rarely.
2407         tcx.dep_graph.with_ignore(|| Lrc::new(middle::lang_items::collect(tcx)))
2408     };
2409     providers.freevars = |tcx, id| tcx.gcx.freevars.get(&id).cloned();
2410     providers.maybe_unused_trait_import = |tcx, id| {
2411         tcx.maybe_unused_trait_imports.contains(&id)
2412     };
2413     providers.maybe_unused_extern_crates = |tcx, cnum| {
2414         assert_eq!(cnum, LOCAL_CRATE);
2415         Lrc::new(tcx.maybe_unused_extern_crates.clone())
2416     };
2417
2418     providers.stability_index = |tcx, cnum| {
2419         assert_eq!(cnum, LOCAL_CRATE);
2420         Lrc::new(stability::Index::new(tcx))
2421     };
2422     providers.lookup_stability = |tcx, id| {
2423         assert_eq!(id.krate, LOCAL_CRATE);
2424         let id = tcx.hir.definitions().def_index_to_hir_id(id.index);
2425         tcx.stability().local_stability(id)
2426     };
2427     providers.lookup_deprecation_entry = |tcx, id| {
2428         assert_eq!(id.krate, LOCAL_CRATE);
2429         let id = tcx.hir.definitions().def_index_to_hir_id(id.index);
2430         tcx.stability().local_deprecation_entry(id)
2431     };
2432     providers.extern_mod_stmt_cnum = |tcx, id| {
2433         let id = tcx.hir.as_local_node_id(id).unwrap();
2434         tcx.cstore.extern_mod_stmt_cnum_untracked(id)
2435     };
2436     providers.all_crate_nums = |tcx, cnum| {
2437         assert_eq!(cnum, LOCAL_CRATE);
2438         Lrc::new(tcx.cstore.crates_untracked())
2439     };
2440     providers.postorder_cnums = |tcx, cnum| {
2441         assert_eq!(cnum, LOCAL_CRATE);
2442         Lrc::new(tcx.cstore.postorder_cnums_untracked())
2443     };
2444     providers.output_filenames = |tcx, cnum| {
2445         assert_eq!(cnum, LOCAL_CRATE);
2446         tcx.output_filenames.clone()
2447     };
2448     providers.has_copy_closures = |tcx, cnum| {
2449         assert_eq!(cnum, LOCAL_CRATE);
2450         tcx.features().copy_closures
2451     };
2452     providers.has_clone_closures = |tcx, cnum| {
2453         assert_eq!(cnum, LOCAL_CRATE);
2454         tcx.features().clone_closures
2455     };
2456     providers.fully_normalize_monormophic_ty = |tcx, ty| {
2457         tcx.fully_normalize_associated_types_in(&ty)
2458     };
2459     providers.features_query = |tcx, cnum| {
2460         assert_eq!(cnum, LOCAL_CRATE);
2461         Lrc::new(tcx.sess.features_untracked().clone())
2462     };
2463     providers.is_panic_runtime = |tcx, cnum| {
2464         assert_eq!(cnum, LOCAL_CRATE);
2465         attr::contains_name(tcx.hir.krate_attrs(), "panic_runtime")
2466     };
2467     providers.is_compiler_builtins = |tcx, cnum| {
2468         assert_eq!(cnum, LOCAL_CRATE);
2469         attr::contains_name(tcx.hir.krate_attrs(), "compiler_builtins")
2470     };
2471 }