]> git.lizzy.rs Git - rust.git/blob - src/librustc/ty/context.rs
Auto merge of #56262 - petrochenkov:nabsedihyg, r=petrochenkov
[rust.git] / 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 session::config::CrateType;
19 use middle;
20 use hir::{TraitCandidate, HirId, ItemKind, ItemLocalId, Node};
21 use hir::def::{Def, Export};
22 use hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE};
23 use hir::map as hir_map;
24 use hir::map::DefPathHash;
25 use lint::{self, Lint};
26 use ich::{StableHashingContext, NodeIdHashingMode};
27 use infer::canonical::{CanonicalVarInfo, CanonicalVarInfos};
28 use infer::outlives::free_region_map::FreeRegionMap;
29 use middle::cstore::CrateStoreDyn;
30 use middle::cstore::EncodedMetadata;
31 use middle::lang_items;
32 use middle::resolve_lifetime::{self, ObjectLifetimeDefault};
33 use middle::stability;
34 use mir::{self, Mir, interpret, ProjectionKind};
35 use mir::interpret::Allocation;
36 use ty::subst::{CanonicalUserSubsts, Kind, Substs, Subst};
37 use ty::ReprOptions;
38 use traits;
39 use traits::{Clause, Clauses, GoalKind, Goal, Goals};
40 use ty::{self, Ty, TypeAndMut};
41 use ty::{TyS, TyKind, List};
42 use ty::{AdtKind, AdtDef, ClosureSubsts, GeneratorSubsts, Region, Const};
43 use ty::{PolyFnSig, InferTy, ParamTy, ProjectionTy, ExistentialPredicate, Predicate};
44 use ty::RegionKind;
45 use ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
46 use ty::TyKind::*;
47 use ty::GenericParamDefKind;
48 use ty::layout::{LayoutDetails, TargetDataLayout, VariantIdx};
49 use ty::query;
50 use ty::steal::Steal;
51 use ty::BindingMode;
52 use ty::CanonicalTy;
53 use ty::CanonicalPolyFnSig;
54 use util::nodemap::{DefIdMap, DefIdSet, ItemLocalMap};
55 use util::nodemap::{FxHashMap, FxHashSet};
56 use smallvec::SmallVec;
57 use rustc_data_structures::stable_hasher::{HashStable, hash_stable_hashmap,
58                                            StableHasher, StableHasherResult,
59                                            StableVec};
60 use arena::{TypedArena, SyncDroplessArena};
61 use rustc_data_structures::indexed_vec::IndexVec;
62 use rustc_data_structures::sync::{self, Lrc, Lock, WorkerLocal};
63 use std::any::Any;
64 use std::borrow::Borrow;
65 use std::cmp::Ordering;
66 use std::collections::hash_map::{self, Entry};
67 use std::hash::{Hash, Hasher};
68 use std::fmt;
69 use std::mem;
70 use std::ops::{Deref, Bound};
71 use std::iter;
72 use std::sync::mpsc;
73 use std::sync::Arc;
74 use rustc_target::spec::abi;
75 use syntax::ast::{self, NodeId};
76 use syntax::attr;
77 use syntax::source_map::MultiSpan;
78 use syntax::edition::Edition;
79 use syntax::feature_gate;
80 use syntax::symbol::{Symbol, keywords, InternedString};
81 use syntax_pos::Span;
82
83 use hir;
84
85 pub struct AllArenas<'tcx> {
86     pub global: WorkerLocal<GlobalArenas<'tcx>>,
87     pub interner: SyncDroplessArena,
88 }
89
90 impl<'tcx> AllArenas<'tcx> {
91     pub fn new() -> Self {
92         AllArenas {
93             global: WorkerLocal::new(|_| GlobalArenas::default()),
94             interner: SyncDroplessArena::default(),
95         }
96     }
97 }
98
99 /// Internal storage
100 #[derive(Default)]
101 pub struct GlobalArenas<'tcx> {
102     // internings
103     layout: TypedArena<LayoutDetails>,
104
105     // references
106     generics: TypedArena<ty::Generics>,
107     trait_def: TypedArena<ty::TraitDef>,
108     adt_def: TypedArena<ty::AdtDef>,
109     steal_mir: TypedArena<Steal<Mir<'tcx>>>,
110     mir: TypedArena<Mir<'tcx>>,
111     tables: TypedArena<ty::TypeckTables<'tcx>>,
112     /// miri allocations
113     const_allocs: TypedArena<interpret::Allocation>,
114 }
115
116 type InternedSet<'tcx, T> = Lock<FxHashSet<Interned<'tcx, T>>>;
117
118 pub struct CtxtInterners<'tcx> {
119     /// The arena that types, regions, etc are allocated from
120     arena: &'tcx SyncDroplessArena,
121
122     /// Specifically use a speedy hash algorithm for these hash sets,
123     /// they're accessed quite often.
124     type_: InternedSet<'tcx, TyS<'tcx>>,
125     type_list: InternedSet<'tcx, List<Ty<'tcx>>>,
126     substs: InternedSet<'tcx, Substs<'tcx>>,
127     canonical_var_infos: InternedSet<'tcx, List<CanonicalVarInfo>>,
128     region: InternedSet<'tcx, RegionKind>,
129     existential_predicates: InternedSet<'tcx, List<ExistentialPredicate<'tcx>>>,
130     predicates: InternedSet<'tcx, List<Predicate<'tcx>>>,
131     const_: InternedSet<'tcx, Const<'tcx>>,
132     clauses: InternedSet<'tcx, List<Clause<'tcx>>>,
133     goal: InternedSet<'tcx, GoalKind<'tcx>>,
134     goal_list: InternedSet<'tcx, List<Goal<'tcx>>>,
135     projs: InternedSet<'tcx, List<ProjectionKind<'tcx>>>,
136 }
137
138 impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
139     fn new(arena: &'tcx SyncDroplessArena) -> CtxtInterners<'tcx> {
140         CtxtInterners {
141             arena,
142             type_: Default::default(),
143             type_list: Default::default(),
144             substs: Default::default(),
145             region: Default::default(),
146             existential_predicates: Default::default(),
147             canonical_var_infos: Default::default(),
148             predicates: Default::default(),
149             const_: Default::default(),
150             clauses: Default::default(),
151             goal: Default::default(),
152             goal_list: Default::default(),
153             projs: Default::default(),
154         }
155     }
156
157     /// Intern a type
158     fn intern_ty(
159         local: &CtxtInterners<'tcx>,
160         global: &CtxtInterners<'gcx>,
161         st: TyKind<'tcx>
162     ) -> Ty<'tcx> {
163         let flags = super::flags::FlagComputation::for_sty(&st);
164
165         // HACK(eddyb) Depend on flags being accurate to
166         // determine that all contents are in the global tcx.
167         // See comments on Lift for why we can't use that.
168         if flags.flags.intersects(ty::TypeFlags::KEEP_IN_LOCAL_TCX) {
169             let mut interner = local.type_.borrow_mut();
170             if let Some(&Interned(ty)) = interner.get(&st) {
171                 return ty;
172             }
173
174             let ty_struct = TyS {
175                 sty: st,
176                 flags: flags.flags,
177                 outer_exclusive_binder: flags.outer_exclusive_binder,
178             };
179
180             // Make sure we don't end up with inference
181             // types/regions in the global interner
182             if local as *const _ as usize == global as *const _ as usize {
183                 bug!("Attempted to intern `{:?}` which contains \
184                       inference types/regions in the global type context",
185                      &ty_struct);
186             }
187
188             // Don't be &mut TyS.
189             let ty: Ty<'tcx> = local.arena.alloc(ty_struct);
190             interner.insert(Interned(ty));
191             ty
192         } else {
193             let mut interner = global.type_.borrow_mut();
194             if let Some(&Interned(ty)) = interner.get(&st) {
195                 return ty;
196             }
197
198             let ty_struct = TyS {
199                 sty: st,
200                 flags: flags.flags,
201                 outer_exclusive_binder: flags.outer_exclusive_binder,
202             };
203
204             // This is safe because all the types the ty_struct can point to
205             // already is in the global arena
206             let ty_struct: TyS<'gcx> = unsafe {
207                 mem::transmute(ty_struct)
208             };
209
210             // Don't be &mut TyS.
211             let ty: Ty<'gcx> = global.arena.alloc(ty_struct);
212             interner.insert(Interned(ty));
213             ty
214         }
215     }
216 }
217
218 pub struct CommonTypes<'tcx> {
219     pub bool: Ty<'tcx>,
220     pub char: Ty<'tcx>,
221     pub isize: Ty<'tcx>,
222     pub i8: Ty<'tcx>,
223     pub i16: Ty<'tcx>,
224     pub i32: Ty<'tcx>,
225     pub i64: Ty<'tcx>,
226     pub i128: Ty<'tcx>,
227     pub usize: Ty<'tcx>,
228     pub u8: Ty<'tcx>,
229     pub u16: Ty<'tcx>,
230     pub u32: Ty<'tcx>,
231     pub u64: Ty<'tcx>,
232     pub u128: Ty<'tcx>,
233     pub f32: Ty<'tcx>,
234     pub f64: Ty<'tcx>,
235     pub never: Ty<'tcx>,
236     pub err: Ty<'tcx>,
237
238     pub re_empty: Region<'tcx>,
239     pub re_static: Region<'tcx>,
240     pub re_erased: Region<'tcx>,
241 }
242
243 pub struct LocalTableInContext<'a, V: 'a> {
244     local_id_root: Option<DefId>,
245     data: &'a ItemLocalMap<V>
246 }
247
248 /// Validate that the given HirId (respectively its `local_id` part) can be
249 /// safely used as a key in the tables of a TypeckTable. For that to be
250 /// the case, the HirId must have the same `owner` as all the other IDs in
251 /// this table (signified by `local_id_root`). Otherwise the HirId
252 /// would be in a different frame of reference and using its `local_id`
253 /// would result in lookup errors, or worse, in silently wrong data being
254 /// stored/returned.
255 fn validate_hir_id_for_typeck_tables(local_id_root: Option<DefId>,
256                                      hir_id: hir::HirId,
257                                      mut_access: bool) {
258     if cfg!(debug_assertions) {
259         if let Some(local_id_root) = local_id_root {
260             if hir_id.owner != local_id_root.index {
261                 ty::tls::with(|tcx| {
262                     let node_id = tcx.hir.hir_to_node_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     /// Resolved field indices for field accesses in expressions (`S { field }`, `obj.field`)
345     /// or patterns (`S { field }`). The index is often useful by itself, but to learn more
346     /// about the field you also need definition of the variant to which the field
347     /// belongs, but it may not exist if it's a tuple field (`tuple.0`).
348     field_indices: ItemLocalMap<usize>,
349
350     /// Stores the types for various nodes in the AST.  Note that this table
351     /// is not guaranteed to be populated until after typeck.  See
352     /// typeck::check::fn_ctxt for details.
353     node_types: ItemLocalMap<Ty<'tcx>>,
354
355     /// Stores the type parameters which were substituted to obtain the type
356     /// of this node.  This only applies to nodes that refer to entities
357     /// parameterized by type parameters, such as generic fns, types, or
358     /// other items.
359     node_substs: ItemLocalMap<&'tcx Substs<'tcx>>,
360
361     /// Stores the canonicalized types provided by the user. See also
362     /// `AscribeUserType` statement in MIR.
363     user_provided_tys: ItemLocalMap<CanonicalTy<'tcx>>,
364
365     /// Stores the canonicalized types provided by the user. See also
366     /// `AscribeUserType` statement in MIR.
367     pub user_provided_sigs: DefIdMap<CanonicalPolyFnSig<'tcx>>,
368
369     /// Stores the substitutions that the user explicitly gave (if any)
370     /// attached to `id`. These will not include any inferred
371     /// values. The canonical form is used to capture things like `_`
372     /// or other unspecified values.
373     ///
374     /// Example:
375     ///
376     /// If the user wrote `foo.collect::<Vec<_>>()`, then the
377     /// canonical substitutions would include only `for<X> { Vec<X>
378     /// }`.
379     user_substs: ItemLocalMap<CanonicalUserSubsts<'tcx>>,
380
381     adjustments: ItemLocalMap<Vec<ty::adjustment::Adjustment<'tcx>>>,
382
383     /// Stores the actual binding mode for all instances of hir::BindingAnnotation.
384     pat_binding_modes: ItemLocalMap<BindingMode>,
385
386     /// Stores the types which were implicitly dereferenced in pattern binding modes
387     /// for later usage in HAIR lowering. For example,
388     ///
389     /// ```
390     /// match &&Some(5i32) {
391     ///     Some(n) => {},
392     ///     _ => {},
393     /// }
394     /// ```
395     /// leads to a `vec![&&Option<i32>, &Option<i32>]`. Empty vectors are not stored.
396     ///
397     /// See:
398     /// https://github.com/rust-lang/rfcs/blob/master/text/2005-match-ergonomics.md#definitions
399     pat_adjustments: ItemLocalMap<Vec<Ty<'tcx>>>,
400
401     /// Borrows
402     pub upvar_capture_map: ty::UpvarCaptureMap<'tcx>,
403
404     /// Records the reasons that we picked the kind of each closure;
405     /// not all closures are present in the map.
406     closure_kind_origins: ItemLocalMap<(Span, ast::Name)>,
407
408     /// For each fn, records the "liberated" types of its arguments
409     /// and return type. Liberated means that all bound regions
410     /// (including late-bound regions) are replaced with free
411     /// equivalents. This table is not used in codegen (since regions
412     /// are erased there) and hence is not serialized to metadata.
413     liberated_fn_sigs: ItemLocalMap<ty::FnSig<'tcx>>,
414
415     /// For each FRU expression, record the normalized types of the fields
416     /// of the struct - this is needed because it is non-trivial to
417     /// normalize while preserving regions. This table is used only in
418     /// MIR construction and hence is not serialized to metadata.
419     fru_field_types: ItemLocalMap<Vec<Ty<'tcx>>>,
420
421     /// Maps a cast expression to its kind. This is keyed on the
422     /// *from* expression of the cast, not the cast itself.
423     cast_kinds: ItemLocalMap<ty::cast::CastKind>,
424
425     /// Set of trait imports actually used in the method resolution.
426     /// This is used for warning unused imports. During type
427     /// checking, this `Lrc` should not be cloned: it must have a ref-count
428     /// of 1 so that we can insert things into the set mutably.
429     pub used_trait_imports: Lrc<DefIdSet>,
430
431     /// If any errors occurred while type-checking this body,
432     /// this field will be set to `true`.
433     pub tainted_by_errors: bool,
434
435     /// Stores the free-region relationships that were deduced from
436     /// its where clauses and parameter types. These are then
437     /// read-again by borrowck.
438     pub free_region_map: FreeRegionMap<'tcx>,
439
440     /// All the existential types that are restricted to concrete types
441     /// by this function
442     pub concrete_existential_types: FxHashMap<DefId, Ty<'tcx>>,
443 }
444
445 impl<'tcx> TypeckTables<'tcx> {
446     pub fn empty(local_id_root: Option<DefId>) -> TypeckTables<'tcx> {
447         TypeckTables {
448             local_id_root,
449             type_dependent_defs: Default::default(),
450             field_indices: Default::default(),
451             user_provided_tys: Default::default(),
452             user_provided_sigs: Default::default(),
453             node_types: Default::default(),
454             node_substs: Default::default(),
455             user_substs: Default::default(),
456             adjustments: Default::default(),
457             pat_binding_modes: Default::default(),
458             pat_adjustments: Default::default(),
459             upvar_capture_map: Default::default(),
460             closure_kind_origins: Default::default(),
461             liberated_fn_sigs: Default::default(),
462             fru_field_types: Default::default(),
463             cast_kinds: Default::default(),
464             used_trait_imports: Lrc::new(Default::default()),
465             tainted_by_errors: false,
466             free_region_map: Default::default(),
467             concrete_existential_types: Default::default(),
468         }
469     }
470
471     /// Returns the final resolution of a `QPath` in an `Expr` or `Pat` node.
472     pub fn qpath_def(&self, qpath: &hir::QPath, id: hir::HirId) -> Def {
473         match *qpath {
474             hir::QPath::Resolved(_, ref path) => path.def,
475             hir::QPath::TypeRelative(..) => {
476                 validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
477                 self.type_dependent_defs.get(&id.local_id).cloned().unwrap_or(Def::Err)
478             }
479         }
480     }
481
482     pub fn type_dependent_defs(&self) -> LocalTableInContext<'_, Def> {
483         LocalTableInContext {
484             local_id_root: self.local_id_root,
485             data: &self.type_dependent_defs
486         }
487     }
488
489     pub fn type_dependent_defs_mut(&mut self) -> LocalTableInContextMut<'_, Def> {
490         LocalTableInContextMut {
491             local_id_root: self.local_id_root,
492             data: &mut self.type_dependent_defs
493         }
494     }
495
496     pub fn field_indices(&self) -> LocalTableInContext<'_, usize> {
497         LocalTableInContext {
498             local_id_root: self.local_id_root,
499             data: &self.field_indices
500         }
501     }
502
503     pub fn field_indices_mut(&mut self) -> LocalTableInContextMut<'_, usize> {
504         LocalTableInContextMut {
505             local_id_root: self.local_id_root,
506             data: &mut self.field_indices
507         }
508     }
509
510     pub fn user_provided_tys(&self) -> LocalTableInContext<'_, CanonicalTy<'tcx>> {
511         LocalTableInContext {
512             local_id_root: self.local_id_root,
513             data: &self.user_provided_tys
514         }
515     }
516
517     pub fn user_provided_tys_mut(&mut self) -> LocalTableInContextMut<'_, CanonicalTy<'tcx>> {
518         LocalTableInContextMut {
519             local_id_root: self.local_id_root,
520             data: &mut self.user_provided_tys
521         }
522     }
523
524     pub fn node_types(&self) -> LocalTableInContext<'_, Ty<'tcx>> {
525         LocalTableInContext {
526             local_id_root: self.local_id_root,
527             data: &self.node_types
528         }
529     }
530
531     pub fn node_types_mut(&mut self) -> LocalTableInContextMut<'_, Ty<'tcx>> {
532         LocalTableInContextMut {
533             local_id_root: self.local_id_root,
534             data: &mut self.node_types
535         }
536     }
537
538     pub fn node_id_to_type(&self, id: hir::HirId) -> Ty<'tcx> {
539         self.node_id_to_type_opt(id).unwrap_or_else(||
540             bug!("node_id_to_type: no type for node `{}`",
541                  tls::with(|tcx| {
542                      let id = tcx.hir.hir_to_node_id(id);
543                      tcx.hir.node_to_string(id)
544                  }))
545         )
546     }
547
548     pub fn node_id_to_type_opt(&self, id: hir::HirId) -> Option<Ty<'tcx>> {
549         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
550         self.node_types.get(&id.local_id).cloned()
551     }
552
553     pub fn node_substs_mut(&mut self) -> LocalTableInContextMut<'_, &'tcx Substs<'tcx>> {
554         LocalTableInContextMut {
555             local_id_root: self.local_id_root,
556             data: &mut self.node_substs
557         }
558     }
559
560     pub fn node_substs(&self, id: hir::HirId) -> &'tcx Substs<'tcx> {
561         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
562         self.node_substs.get(&id.local_id).cloned().unwrap_or_else(|| Substs::empty())
563     }
564
565     pub fn node_substs_opt(&self, id: hir::HirId) -> Option<&'tcx Substs<'tcx>> {
566         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
567         self.node_substs.get(&id.local_id).cloned()
568     }
569
570     pub fn user_substs_mut(&mut self) -> LocalTableInContextMut<'_, CanonicalUserSubsts<'tcx>> {
571         LocalTableInContextMut {
572             local_id_root: self.local_id_root,
573             data: &mut self.user_substs
574         }
575     }
576
577     pub fn user_substs(&self, id: hir::HirId) -> Option<CanonicalUserSubsts<'tcx>> {
578         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
579         self.user_substs.get(&id.local_id).cloned()
580     }
581
582     // Returns the type of a pattern as a monotype. Like @expr_ty, this function
583     // doesn't provide type parameter substitutions.
584     pub fn pat_ty(&self, pat: &hir::Pat) -> Ty<'tcx> {
585         self.node_id_to_type(pat.hir_id)
586     }
587
588     pub fn pat_ty_opt(&self, pat: &hir::Pat) -> Option<Ty<'tcx>> {
589         self.node_id_to_type_opt(pat.hir_id)
590     }
591
592     // Returns the type of an expression as a monotype.
593     //
594     // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression.  That is, in
595     // some cases, we insert `Adjustment` annotations such as auto-deref or
596     // auto-ref.  The type returned by this function does not consider such
597     // adjustments.  See `expr_ty_adjusted()` instead.
598     //
599     // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
600     // ask for the type of "id" in "id(3)", it will return "fn(&isize) -> isize"
601     // instead of "fn(ty) -> T with T = isize".
602     pub fn expr_ty(&self, expr: &hir::Expr) -> Ty<'tcx> {
603         self.node_id_to_type(expr.hir_id)
604     }
605
606     pub fn expr_ty_opt(&self, expr: &hir::Expr) -> Option<Ty<'tcx>> {
607         self.node_id_to_type_opt(expr.hir_id)
608     }
609
610     pub fn adjustments(&self) -> LocalTableInContext<'_, Vec<ty::adjustment::Adjustment<'tcx>>> {
611         LocalTableInContext {
612             local_id_root: self.local_id_root,
613             data: &self.adjustments
614         }
615     }
616
617     pub fn adjustments_mut(&mut self)
618                            -> LocalTableInContextMut<'_, Vec<ty::adjustment::Adjustment<'tcx>>> {
619         LocalTableInContextMut {
620             local_id_root: self.local_id_root,
621             data: &mut self.adjustments
622         }
623     }
624
625     pub fn expr_adjustments(&self, expr: &hir::Expr)
626                             -> &[ty::adjustment::Adjustment<'tcx>] {
627         validate_hir_id_for_typeck_tables(self.local_id_root, expr.hir_id, false);
628         self.adjustments.get(&expr.hir_id.local_id).map_or(&[], |a| &a[..])
629     }
630
631     /// Returns the type of `expr`, considering any `Adjustment`
632     /// entry recorded for that expression.
633     pub fn expr_ty_adjusted(&self, expr: &hir::Expr) -> Ty<'tcx> {
634         self.expr_adjustments(expr)
635             .last()
636             .map_or_else(|| self.expr_ty(expr), |adj| adj.target)
637     }
638
639     pub fn expr_ty_adjusted_opt(&self, expr: &hir::Expr) -> Option<Ty<'tcx>> {
640         self.expr_adjustments(expr)
641             .last()
642             .map(|adj| adj.target)
643             .or_else(|| self.expr_ty_opt(expr))
644     }
645
646     pub fn is_method_call(&self, expr: &hir::Expr) -> bool {
647         // Only paths and method calls/overloaded operators have
648         // entries in type_dependent_defs, ignore the former here.
649         if let hir::ExprKind::Path(_) = expr.node {
650             return false;
651         }
652
653         match self.type_dependent_defs().get(expr.hir_id) {
654             Some(&Def::Method(_)) => true,
655             _ => false
656         }
657     }
658
659     pub fn pat_binding_modes(&self) -> LocalTableInContext<'_, BindingMode> {
660         LocalTableInContext {
661             local_id_root: self.local_id_root,
662             data: &self.pat_binding_modes
663         }
664     }
665
666     pub fn pat_binding_modes_mut(&mut self)
667                            -> LocalTableInContextMut<'_, BindingMode> {
668         LocalTableInContextMut {
669             local_id_root: self.local_id_root,
670             data: &mut self.pat_binding_modes
671         }
672     }
673
674     pub fn pat_adjustments(&self) -> LocalTableInContext<'_, Vec<Ty<'tcx>>> {
675         LocalTableInContext {
676             local_id_root: self.local_id_root,
677             data: &self.pat_adjustments,
678         }
679     }
680
681     pub fn pat_adjustments_mut(&mut self)
682                                -> LocalTableInContextMut<'_, Vec<Ty<'tcx>>> {
683         LocalTableInContextMut {
684             local_id_root: self.local_id_root,
685             data: &mut self.pat_adjustments,
686         }
687     }
688
689     pub fn upvar_capture(&self, upvar_id: ty::UpvarId) -> ty::UpvarCapture<'tcx> {
690         self.upvar_capture_map[&upvar_id]
691     }
692
693     pub fn closure_kind_origins(&self) -> LocalTableInContext<'_, (Span, ast::Name)> {
694         LocalTableInContext {
695             local_id_root: self.local_id_root,
696             data: &self.closure_kind_origins
697         }
698     }
699
700     pub fn closure_kind_origins_mut(&mut self) -> LocalTableInContextMut<'_, (Span, ast::Name)> {
701         LocalTableInContextMut {
702             local_id_root: self.local_id_root,
703             data: &mut self.closure_kind_origins
704         }
705     }
706
707     pub fn liberated_fn_sigs(&self) -> LocalTableInContext<'_, ty::FnSig<'tcx>> {
708         LocalTableInContext {
709             local_id_root: self.local_id_root,
710             data: &self.liberated_fn_sigs
711         }
712     }
713
714     pub fn liberated_fn_sigs_mut(&mut self) -> LocalTableInContextMut<'_, ty::FnSig<'tcx>> {
715         LocalTableInContextMut {
716             local_id_root: self.local_id_root,
717             data: &mut self.liberated_fn_sigs
718         }
719     }
720
721     pub fn fru_field_types(&self) -> LocalTableInContext<'_, Vec<Ty<'tcx>>> {
722         LocalTableInContext {
723             local_id_root: self.local_id_root,
724             data: &self.fru_field_types
725         }
726     }
727
728     pub fn fru_field_types_mut(&mut self) -> LocalTableInContextMut<'_, Vec<Ty<'tcx>>> {
729         LocalTableInContextMut {
730             local_id_root: self.local_id_root,
731             data: &mut self.fru_field_types
732         }
733     }
734
735     pub fn cast_kinds(&self) -> LocalTableInContext<'_, ty::cast::CastKind> {
736         LocalTableInContext {
737             local_id_root: self.local_id_root,
738             data: &self.cast_kinds
739         }
740     }
741
742     pub fn cast_kinds_mut(&mut self) -> LocalTableInContextMut<'_, ty::cast::CastKind> {
743         LocalTableInContextMut {
744             local_id_root: self.local_id_root,
745             data: &mut self.cast_kinds
746         }
747     }
748 }
749
750 impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for TypeckTables<'gcx> {
751     fn hash_stable<W: StableHasherResult>(&self,
752                                           hcx: &mut StableHashingContext<'a>,
753                                           hasher: &mut StableHasher<W>) {
754         let ty::TypeckTables {
755             local_id_root,
756             ref type_dependent_defs,
757             ref field_indices,
758             ref user_provided_tys,
759             ref user_provided_sigs,
760             ref node_types,
761             ref node_substs,
762             ref user_substs,
763             ref adjustments,
764             ref pat_binding_modes,
765             ref pat_adjustments,
766             ref upvar_capture_map,
767             ref closure_kind_origins,
768             ref liberated_fn_sigs,
769             ref fru_field_types,
770
771             ref cast_kinds,
772
773             ref used_trait_imports,
774             tainted_by_errors,
775             ref free_region_map,
776             ref concrete_existential_types,
777         } = *self;
778
779         hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
780             type_dependent_defs.hash_stable(hcx, hasher);
781             field_indices.hash_stable(hcx, hasher);
782             user_provided_tys.hash_stable(hcx, hasher);
783             user_provided_sigs.hash_stable(hcx, hasher);
784             node_types.hash_stable(hcx, hasher);
785             node_substs.hash_stable(hcx, hasher);
786             user_substs.hash_stable(hcx, hasher);
787             adjustments.hash_stable(hcx, hasher);
788             pat_binding_modes.hash_stable(hcx, hasher);
789             pat_adjustments.hash_stable(hcx, hasher);
790             hash_stable_hashmap(hcx, hasher, upvar_capture_map, |up_var_id, hcx| {
791                 let ty::UpvarId {
792                     var_path,
793                     closure_expr_id
794                 } = *up_var_id;
795
796                 let local_id_root =
797                     local_id_root.expect("trying to hash invalid TypeckTables");
798
799                 let var_owner_def_id = DefId {
800                     krate: local_id_root.krate,
801                     index: var_path.hir_id.owner,
802                 };
803                 let closure_def_id = DefId {
804                     krate: local_id_root.krate,
805                     index: closure_expr_id.to_def_id().index,
806                 };
807                 (hcx.def_path_hash(var_owner_def_id),
808                  var_path.hir_id.local_id,
809                  hcx.def_path_hash(closure_def_id))
810             });
811
812             closure_kind_origins.hash_stable(hcx, hasher);
813             liberated_fn_sigs.hash_stable(hcx, hasher);
814             fru_field_types.hash_stable(hcx, hasher);
815             cast_kinds.hash_stable(hcx, hasher);
816             used_trait_imports.hash_stable(hcx, hasher);
817             tainted_by_errors.hash_stable(hcx, hasher);
818             free_region_map.hash_stable(hcx, hasher);
819             concrete_existential_types.hash_stable(hcx, hasher);
820         })
821     }
822 }
823
824 impl<'tcx> CommonTypes<'tcx> {
825     fn new(interners: &CtxtInterners<'tcx>) -> CommonTypes<'tcx> {
826         let mk = |sty| CtxtInterners::intern_ty(interners, interners, sty);
827         let mk_region = |r| {
828             if let Some(r) = interners.region.borrow().get(&r) {
829                 return r.0;
830             }
831             let r = interners.arena.alloc(r);
832             interners.region.borrow_mut().insert(Interned(r));
833             &*r
834         };
835         CommonTypes {
836             bool: mk(Bool),
837             char: mk(Char),
838             never: mk(Never),
839             err: mk(Error),
840             isize: mk(Int(ast::IntTy::Isize)),
841             i8: mk(Int(ast::IntTy::I8)),
842             i16: mk(Int(ast::IntTy::I16)),
843             i32: mk(Int(ast::IntTy::I32)),
844             i64: mk(Int(ast::IntTy::I64)),
845             i128: mk(Int(ast::IntTy::I128)),
846             usize: mk(Uint(ast::UintTy::Usize)),
847             u8: mk(Uint(ast::UintTy::U8)),
848             u16: mk(Uint(ast::UintTy::U16)),
849             u32: mk(Uint(ast::UintTy::U32)),
850             u64: mk(Uint(ast::UintTy::U64)),
851             u128: mk(Uint(ast::UintTy::U128)),
852             f32: mk(Float(ast::FloatTy::F32)),
853             f64: mk(Float(ast::FloatTy::F64)),
854
855             re_empty: mk_region(RegionKind::ReEmpty),
856             re_static: mk_region(RegionKind::ReStatic),
857             re_erased: mk_region(RegionKind::ReErased),
858         }
859     }
860 }
861
862 // This struct contains information regarding the `ReFree(FreeRegion)` corresponding to a lifetime
863 // conflict.
864 #[derive(Debug)]
865 pub struct FreeRegionInfo {
866     // def id corresponding to FreeRegion
867     pub def_id: DefId,
868     // the bound region corresponding to FreeRegion
869     pub boundregion: ty::BoundRegion,
870     // checks if bound region is in Impl Item
871     pub is_impl_item: bool,
872 }
873
874 /// The central data structure of the compiler. It stores references
875 /// to the various **arenas** and also houses the results of the
876 /// various **compiler queries** that have been performed. See the
877 /// [rustc guide] for more details.
878 ///
879 /// [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/ty.html
880 #[derive(Copy, Clone)]
881 pub struct TyCtxt<'a, 'gcx: 'tcx, 'tcx: 'a> {
882     gcx: &'a GlobalCtxt<'gcx>,
883     interners: &'a CtxtInterners<'tcx>
884 }
885
886 impl<'a, 'gcx, 'tcx> Deref for TyCtxt<'a, 'gcx, 'tcx> {
887     type Target = &'a GlobalCtxt<'gcx>;
888     fn deref(&self) -> &Self::Target {
889         &self.gcx
890     }
891 }
892
893 pub struct GlobalCtxt<'tcx> {
894     global_arenas: &'tcx WorkerLocal<GlobalArenas<'tcx>>,
895     global_interners: CtxtInterners<'tcx>,
896
897     cstore: &'tcx CrateStoreDyn,
898
899     pub sess: &'tcx Session,
900
901     pub dep_graph: DepGraph,
902
903     /// Common types, pre-interned for your convenience.
904     pub types: CommonTypes<'tcx>,
905
906     /// Map indicating what traits are in scope for places where this
907     /// is relevant; generated by resolve.
908     trait_map: FxHashMap<DefIndex,
909                          Lrc<FxHashMap<ItemLocalId,
910                                        Lrc<StableVec<TraitCandidate>>>>>,
911
912     /// Export map produced by name resolution.
913     export_map: FxHashMap<DefId, Lrc<Vec<Export>>>,
914
915     pub hir: hir_map::Map<'tcx>,
916
917     /// A map from DefPathHash -> DefId. Includes DefIds from the local crate
918     /// as well as all upstream crates. Only populated in incremental mode.
919     pub def_path_hash_to_def_id: Option<FxHashMap<DefPathHash, DefId>>,
920
921     pub(crate) queries: query::Queries<'tcx>,
922
923     // Records the free variables referenced by every closure
924     // expression. Do not track deps for this, just recompute it from
925     // scratch every time.
926     freevars: FxHashMap<DefId, Lrc<Vec<hir::Freevar>>>,
927
928     maybe_unused_trait_imports: FxHashSet<DefId>,
929     maybe_unused_extern_crates: Vec<(DefId, Span)>,
930     /// Extern prelude entries. The value is `true` if the entry was introduced
931     /// via `extern crate` item and not `--extern` option or compiler built-in.
932     pub extern_prelude: FxHashMap<ast::Name, bool>,
933
934     // Internal cache for metadata decoding. No need to track deps on this.
935     pub rcache: Lock<FxHashMap<ty::CReaderCacheKey, Ty<'tcx>>>,
936
937     /// Caches the results of trait selection. This cache is used
938     /// for things that do not have to do with the parameters in scope.
939     pub selection_cache: traits::SelectionCache<'tcx>,
940
941     /// Caches the results of trait evaluation. This cache is used
942     /// for things that do not have to do with the parameters in scope.
943     /// Merge this with `selection_cache`?
944     pub evaluation_cache: traits::EvaluationCache<'tcx>,
945
946     /// The definite name of the current crate after taking into account
947     /// attributes, commandline parameters, etc.
948     pub crate_name: Symbol,
949
950     /// Data layout specification for the current target.
951     pub data_layout: TargetDataLayout,
952
953     stability_interner: Lock<FxHashSet<&'tcx attr::Stability>>,
954
955     /// Stores the value of constants (and deduplicates the actual memory)
956     allocation_interner: Lock<FxHashSet<&'tcx Allocation>>,
957
958     pub alloc_map: Lock<interpret::AllocMap<'tcx, &'tcx Allocation>>,
959
960     layout_interner: Lock<FxHashSet<&'tcx LayoutDetails>>,
961
962     /// A general purpose channel to throw data out the back towards LLVM worker
963     /// threads.
964     ///
965     /// This is intended to only get used during the codegen phase of the compiler
966     /// when satisfying the query for a particular codegen unit. Internally in
967     /// the query it'll send data along this channel to get processed later.
968     pub tx_to_llvm_workers: Lock<mpsc::Sender<Box<dyn Any + Send>>>,
969
970     output_filenames: Arc<OutputFilenames>,
971 }
972
973 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
974     /// Get the global TyCtxt.
975     #[inline]
976     pub fn global_tcx(self) -> TyCtxt<'a, 'gcx, 'gcx> {
977         TyCtxt {
978             gcx: self.gcx,
979             interners: &self.gcx.global_interners,
980         }
981     }
982
983     pub fn alloc_generics(self, generics: ty::Generics) -> &'gcx ty::Generics {
984         self.global_arenas.generics.alloc(generics)
985     }
986
987     pub fn alloc_steal_mir(self, mir: Mir<'gcx>) -> &'gcx Steal<Mir<'gcx>> {
988         self.global_arenas.steal_mir.alloc(Steal::new(mir))
989     }
990
991     pub fn alloc_mir(self, mir: Mir<'gcx>) -> &'gcx Mir<'gcx> {
992         self.global_arenas.mir.alloc(mir)
993     }
994
995     pub fn alloc_tables(self, tables: ty::TypeckTables<'gcx>) -> &'gcx ty::TypeckTables<'gcx> {
996         self.global_arenas.tables.alloc(tables)
997     }
998
999     pub fn alloc_trait_def(self, def: ty::TraitDef) -> &'gcx ty::TraitDef {
1000         self.global_arenas.trait_def.alloc(def)
1001     }
1002
1003     pub fn alloc_adt_def(self,
1004                          did: DefId,
1005                          kind: AdtKind,
1006                          variants: IndexVec<VariantIdx, ty::VariantDef>,
1007                          repr: ReprOptions)
1008                          -> &'gcx ty::AdtDef {
1009         let def = ty::AdtDef::new(self, did, kind, variants, repr);
1010         self.global_arenas.adt_def.alloc(def)
1011     }
1012
1013     pub fn alloc_byte_array(self, bytes: &[u8]) -> &'gcx [u8] {
1014         if bytes.is_empty() {
1015             &[]
1016         } else {
1017             self.global_interners.arena.alloc_slice(bytes)
1018         }
1019     }
1020
1021     pub fn alloc_const_slice(self, values: &[&'tcx ty::Const<'tcx>])
1022                              -> &'tcx [&'tcx ty::Const<'tcx>] {
1023         if values.is_empty() {
1024             &[]
1025         } else {
1026             self.interners.arena.alloc_slice(values)
1027         }
1028     }
1029
1030     pub fn alloc_name_const_slice(self, values: &[(ast::Name, &'tcx ty::Const<'tcx>)])
1031                                   -> &'tcx [(ast::Name, &'tcx ty::Const<'tcx>)] {
1032         if values.is_empty() {
1033             &[]
1034         } else {
1035             self.interners.arena.alloc_slice(values)
1036         }
1037     }
1038
1039     pub fn intern_const_alloc(
1040         self,
1041         alloc: Allocation,
1042     ) -> &'gcx Allocation {
1043         let allocs = &mut self.allocation_interner.borrow_mut();
1044         if let Some(alloc) = allocs.get(&alloc) {
1045             return alloc;
1046         }
1047
1048         let interned = self.global_arenas.const_allocs.alloc(alloc);
1049         if let Some(prev) = allocs.replace(interned) { // insert into interner
1050             bug!("Tried to overwrite interned Allocation: {:#?}", prev)
1051         }
1052         interned
1053     }
1054
1055     /// Allocates a byte or string literal for `mir::interpret`, read-only
1056     pub fn allocate_bytes(self, bytes: &[u8]) -> interpret::AllocId {
1057         // create an allocation that just contains these bytes
1058         let alloc = interpret::Allocation::from_byte_aligned_bytes(bytes);
1059         let alloc = self.intern_const_alloc(alloc);
1060         self.alloc_map.lock().allocate(alloc)
1061     }
1062
1063     pub fn intern_stability(self, stab: attr::Stability) -> &'gcx attr::Stability {
1064         let mut stability_interner = self.stability_interner.borrow_mut();
1065         if let Some(st) = stability_interner.get(&stab) {
1066             return st;
1067         }
1068
1069         let interned = self.global_interners.arena.alloc(stab);
1070         if let Some(prev) = stability_interner.replace(interned) {
1071             bug!("Tried to overwrite interned Stability: {:?}", prev)
1072         }
1073         interned
1074     }
1075
1076     pub fn intern_layout(self, layout: LayoutDetails) -> &'gcx LayoutDetails {
1077         let mut layout_interner = self.layout_interner.borrow_mut();
1078         if let Some(layout) = layout_interner.get(&layout) {
1079             return layout;
1080         }
1081
1082         let interned = self.global_arenas.layout.alloc(layout);
1083         if let Some(prev) = layout_interner.replace(interned) {
1084             bug!("Tried to overwrite interned Layout: {:?}", prev)
1085         }
1086         interned
1087     }
1088
1089     /// Returns a range of the start/end indices specified with the
1090     /// `rustc_layout_scalar_valid_range` attribute.
1091     pub fn layout_scalar_valid_range(self, def_id: DefId) -> (Bound<u128>, Bound<u128>) {
1092         let attrs = self.get_attrs(def_id);
1093         let get = |name| {
1094             let attr = match attrs.iter().find(|a| a.check_name(name)) {
1095                 Some(attr) => attr,
1096                 None => return Bound::Unbounded,
1097             };
1098             for meta in attr.meta_item_list().expect("rustc_layout_scalar_valid_range takes args") {
1099                 match meta.literal().expect("attribute takes lit").node {
1100                     ast::LitKind::Int(a, _) => return Bound::Included(a),
1101                     _ => span_bug!(attr.span, "rustc_layout_scalar_valid_range expects int arg"),
1102                 }
1103             }
1104             span_bug!(attr.span, "no arguments to `rustc_layout_scalar_valid_range` attribute");
1105         };
1106         (get("rustc_layout_scalar_valid_range_start"), get("rustc_layout_scalar_valid_range_end"))
1107     }
1108
1109     pub fn lift<T: ?Sized + Lift<'tcx>>(self, value: &T) -> Option<T::Lifted> {
1110         value.lift_to_tcx(self)
1111     }
1112
1113     /// Like lift, but only tries in the global tcx.
1114     pub fn lift_to_global<T: ?Sized + Lift<'gcx>>(self, value: &T) -> Option<T::Lifted> {
1115         value.lift_to_tcx(self.global_tcx())
1116     }
1117
1118     /// Returns true if self is the same as self.global_tcx().
1119     fn is_global(self) -> bool {
1120         let local = self.interners as *const _;
1121         let global = &self.global_interners as *const _;
1122         local as usize == global as usize
1123     }
1124
1125     /// Create a type context and call the closure with a `TyCtxt` reference
1126     /// to the context. The closure enforces that the type context and any interned
1127     /// value (types, substs, etc.) can only be used while `ty::tls` has a valid
1128     /// reference to the context, to allow formatting values that need it.
1129     pub fn create_and_enter<F, R>(s: &'tcx Session,
1130                                   cstore: &'tcx CrateStoreDyn,
1131                                   local_providers: ty::query::Providers<'tcx>,
1132                                   extern_providers: ty::query::Providers<'tcx>,
1133                                   arenas: &'tcx AllArenas<'tcx>,
1134                                   resolutions: ty::Resolutions,
1135                                   hir: hir_map::Map<'tcx>,
1136                                   on_disk_query_result_cache: query::OnDiskCache<'tcx>,
1137                                   crate_name: &str,
1138                                   tx: mpsc::Sender<Box<dyn Any + Send>>,
1139                                   output_filenames: &OutputFilenames,
1140                                   f: F) -> R
1141                                   where F: for<'b> FnOnce(TyCtxt<'b, 'tcx, 'tcx>) -> R
1142     {
1143         let data_layout = TargetDataLayout::parse(&s.target.target).unwrap_or_else(|err| {
1144             s.fatal(&err);
1145         });
1146         let interners = CtxtInterners::new(&arenas.interner);
1147         let common_types = CommonTypes::new(&interners);
1148         let dep_graph = hir.dep_graph.clone();
1149         let max_cnum = cstore.crates_untracked().iter().map(|c| c.as_usize()).max().unwrap_or(0);
1150         let mut providers = IndexVec::from_elem_n(extern_providers, max_cnum + 1);
1151         providers[LOCAL_CRATE] = local_providers;
1152
1153         let def_path_hash_to_def_id = if s.opts.build_dep_graph() {
1154             let upstream_def_path_tables: Vec<(CrateNum, Lrc<_>)> = cstore
1155                 .crates_untracked()
1156                 .iter()
1157                 .map(|&cnum| (cnum, cstore.def_path_table(cnum)))
1158                 .collect();
1159
1160             let def_path_tables = || {
1161                 upstream_def_path_tables
1162                     .iter()
1163                     .map(|&(cnum, ref rc)| (cnum, &**rc))
1164                     .chain(iter::once((LOCAL_CRATE, hir.definitions().def_path_table())))
1165             };
1166
1167             // Precompute the capacity of the hashmap so we don't have to
1168             // re-allocate when populating it.
1169             let capacity = def_path_tables().map(|(_, t)| t.size()).sum::<usize>();
1170
1171             let mut map: FxHashMap<_, _> = FxHashMap::with_capacity_and_hasher(
1172                 capacity,
1173                 ::std::default::Default::default()
1174             );
1175
1176             for (cnum, def_path_table) in def_path_tables() {
1177                 def_path_table.add_def_path_hashes_to(cnum, &mut map);
1178             }
1179
1180             Some(map)
1181         } else {
1182             None
1183         };
1184
1185         let mut trait_map: FxHashMap<_, Lrc<FxHashMap<_, _>>> = FxHashMap::default();
1186         for (k, v) in resolutions.trait_map {
1187             let hir_id = hir.node_to_hir_id(k);
1188             let map = trait_map.entry(hir_id.owner).or_default();
1189             Lrc::get_mut(map).unwrap()
1190                              .insert(hir_id.local_id,
1191                                      Lrc::new(StableVec::new(v)));
1192         }
1193
1194         let gcx = &GlobalCtxt {
1195             sess: s,
1196             cstore,
1197             global_arenas: &arenas.global,
1198             global_interners: interners,
1199             dep_graph,
1200             types: common_types,
1201             trait_map,
1202             export_map: resolutions.export_map.into_iter().map(|(k, v)| {
1203                 (k, Lrc::new(v))
1204             }).collect(),
1205             freevars: resolutions.freevars.into_iter().map(|(k, v)| {
1206                 (hir.local_def_id(k), Lrc::new(v))
1207             }).collect(),
1208             maybe_unused_trait_imports:
1209                 resolutions.maybe_unused_trait_imports
1210                     .into_iter()
1211                     .map(|id| hir.local_def_id(id))
1212                     .collect(),
1213             maybe_unused_extern_crates:
1214                 resolutions.maybe_unused_extern_crates
1215                     .into_iter()
1216                     .map(|(id, sp)| (hir.local_def_id(id), sp))
1217                     .collect(),
1218             extern_prelude: resolutions.extern_prelude,
1219             hir,
1220             def_path_hash_to_def_id,
1221             queries: query::Queries::new(
1222                 providers,
1223                 extern_providers,
1224                 on_disk_query_result_cache,
1225             ),
1226             rcache: Default::default(),
1227             selection_cache: Default::default(),
1228             evaluation_cache: Default::default(),
1229             crate_name: Symbol::intern(crate_name),
1230             data_layout,
1231             layout_interner: Default::default(),
1232             stability_interner: Default::default(),
1233             allocation_interner: Default::default(),
1234             alloc_map: Lock::new(interpret::AllocMap::new()),
1235             tx_to_llvm_workers: Lock::new(tx),
1236             output_filenames: Arc::new(output_filenames.clone()),
1237         };
1238
1239         sync::assert_send_val(&gcx);
1240
1241         tls::enter_global(gcx, f)
1242     }
1243
1244     pub fn consider_optimizing<T: Fn() -> String>(&self, msg: T) -> bool {
1245         let cname = self.crate_name(LOCAL_CRATE).as_str();
1246         self.sess.consider_optimizing(&cname, msg)
1247     }
1248
1249     pub fn lib_features(self) -> Lrc<middle::lib_features::LibFeatures> {
1250         self.get_lib_features(LOCAL_CRATE)
1251     }
1252
1253     pub fn lang_items(self) -> Lrc<middle::lang_items::LanguageItems> {
1254         self.get_lang_items(LOCAL_CRATE)
1255     }
1256
1257     /// Due to missing llvm support for lowering 128 bit math to software emulation
1258     /// (on some targets), the lowering can be done in MIR.
1259     ///
1260     /// This function only exists until said support is implemented.
1261     pub fn is_binop_lang_item(&self, def_id: DefId) -> Option<(mir::BinOp, bool)> {
1262         let items = self.lang_items();
1263         let def_id = Some(def_id);
1264         if items.i128_add_fn() == def_id { Some((mir::BinOp::Add, false)) }
1265         else if items.u128_add_fn() == def_id { Some((mir::BinOp::Add, false)) }
1266         else if items.i128_sub_fn() == def_id { Some((mir::BinOp::Sub, false)) }
1267         else if items.u128_sub_fn() == def_id { Some((mir::BinOp::Sub, false)) }
1268         else if items.i128_mul_fn() == def_id { Some((mir::BinOp::Mul, false)) }
1269         else if items.u128_mul_fn() == def_id { Some((mir::BinOp::Mul, false)) }
1270         else if items.i128_div_fn() == def_id { Some((mir::BinOp::Div, false)) }
1271         else if items.u128_div_fn() == def_id { Some((mir::BinOp::Div, false)) }
1272         else if items.i128_rem_fn() == def_id { Some((mir::BinOp::Rem, false)) }
1273         else if items.u128_rem_fn() == def_id { Some((mir::BinOp::Rem, false)) }
1274         else if items.i128_shl_fn() == def_id { Some((mir::BinOp::Shl, false)) }
1275         else if items.u128_shl_fn() == def_id { Some((mir::BinOp::Shl, false)) }
1276         else if items.i128_shr_fn() == def_id { Some((mir::BinOp::Shr, false)) }
1277         else if items.u128_shr_fn() == def_id { Some((mir::BinOp::Shr, false)) }
1278         else if items.i128_addo_fn() == def_id { Some((mir::BinOp::Add, true)) }
1279         else if items.u128_addo_fn() == def_id { Some((mir::BinOp::Add, true)) }
1280         else if items.i128_subo_fn() == def_id { Some((mir::BinOp::Sub, true)) }
1281         else if items.u128_subo_fn() == def_id { Some((mir::BinOp::Sub, true)) }
1282         else if items.i128_mulo_fn() == def_id { Some((mir::BinOp::Mul, true)) }
1283         else if items.u128_mulo_fn() == def_id { Some((mir::BinOp::Mul, true)) }
1284         else if items.i128_shlo_fn() == def_id { Some((mir::BinOp::Shl, true)) }
1285         else if items.u128_shlo_fn() == def_id { Some((mir::BinOp::Shl, true)) }
1286         else if items.i128_shro_fn() == def_id { Some((mir::BinOp::Shr, true)) }
1287         else if items.u128_shro_fn() == def_id { Some((mir::BinOp::Shr, true)) }
1288         else { None }
1289     }
1290
1291     pub fn stability(self) -> Lrc<stability::Index<'tcx>> {
1292         self.stability_index(LOCAL_CRATE)
1293     }
1294
1295     pub fn crates(self) -> Lrc<Vec<CrateNum>> {
1296         self.all_crate_nums(LOCAL_CRATE)
1297     }
1298
1299     pub fn features(self) -> Lrc<feature_gate::Features> {
1300         self.features_query(LOCAL_CRATE)
1301     }
1302
1303     pub fn def_key(self, id: DefId) -> hir_map::DefKey {
1304         if id.is_local() {
1305             self.hir.def_key(id)
1306         } else {
1307             self.cstore.def_key(id)
1308         }
1309     }
1310
1311     /// Convert a `DefId` into its fully expanded `DefPath` (every
1312     /// `DefId` is really just an interned def-path).
1313     ///
1314     /// Note that if `id` is not local to this crate, the result will
1315     ///  be a non-local `DefPath`.
1316     pub fn def_path(self, id: DefId) -> hir_map::DefPath {
1317         if id.is_local() {
1318             self.hir.def_path(id)
1319         } else {
1320             self.cstore.def_path(id)
1321         }
1322     }
1323
1324     #[inline]
1325     pub fn def_path_hash(self, def_id: DefId) -> hir_map::DefPathHash {
1326         if def_id.is_local() {
1327             self.hir.definitions().def_path_hash(def_id.index)
1328         } else {
1329             self.cstore.def_path_hash(def_id)
1330         }
1331     }
1332
1333     pub fn def_path_debug_str(self, def_id: DefId) -> String {
1334         // We are explicitly not going through queries here in order to get
1335         // crate name and disambiguator since this code is called from debug!()
1336         // statements within the query system and we'd run into endless
1337         // recursion otherwise.
1338         let (crate_name, crate_disambiguator) = if def_id.is_local() {
1339             (self.crate_name.clone(),
1340              self.sess.local_crate_disambiguator())
1341         } else {
1342             (self.cstore.crate_name_untracked(def_id.krate),
1343              self.cstore.crate_disambiguator_untracked(def_id.krate))
1344         };
1345
1346         format!("{}[{}]{}",
1347                 crate_name,
1348                 // Don't print the whole crate disambiguator. That's just
1349                 // annoying in debug output.
1350                 &(crate_disambiguator.to_fingerprint().to_hex())[..4],
1351                 self.def_path(def_id).to_string_no_crate())
1352     }
1353
1354     pub fn metadata_encoding_version(self) -> Vec<u8> {
1355         self.cstore.metadata_encoding_version().to_vec()
1356     }
1357
1358     // Note that this is *untracked* and should only be used within the query
1359     // system if the result is otherwise tracked through queries
1360     pub fn crate_data_as_rc_any(self, cnum: CrateNum) -> Lrc<dyn Any> {
1361         self.cstore.crate_data_as_rc_any(cnum)
1362     }
1363
1364     pub fn create_stable_hashing_context(self) -> StableHashingContext<'a> {
1365         let krate = self.dep_graph.with_ignore(|| self.gcx.hir.krate());
1366
1367         StableHashingContext::new(self.sess,
1368                                   krate,
1369                                   self.hir.definitions(),
1370                                   self.cstore)
1371     }
1372
1373     // This method makes sure that we have a DepNode and a Fingerprint for
1374     // every upstream crate. It needs to be called once right after the tcx is
1375     // created.
1376     // With full-fledged red/green, the method will probably become unnecessary
1377     // as this will be done on-demand.
1378     pub fn allocate_metadata_dep_nodes(self) {
1379         // We cannot use the query versions of crates() and crate_hash(), since
1380         // those would need the DepNodes that we are allocating here.
1381         for cnum in self.cstore.crates_untracked() {
1382             let dep_node = DepNode::new(self, DepConstructor::CrateMetadata(cnum));
1383             let crate_hash = self.cstore.crate_hash_untracked(cnum);
1384             self.dep_graph.with_task(dep_node,
1385                                      self,
1386                                      crate_hash,
1387                                      |_, x| x // No transformation needed
1388             );
1389         }
1390     }
1391
1392     // This method exercises the `in_scope_traits_map` query for all possible
1393     // values so that we have their fingerprints available in the DepGraph.
1394     // This is only required as long as we still use the old dependency tracking
1395     // which needs to have the fingerprints of all input nodes beforehand.
1396     pub fn precompute_in_scope_traits_hashes(self) {
1397         for &def_index in self.trait_map.keys() {
1398             self.in_scope_traits_map(def_index);
1399         }
1400     }
1401
1402     pub fn serialize_query_result_cache<E>(self,
1403                                            encoder: &mut E)
1404                                            -> Result<(), E::Error>
1405         where E: ty::codec::TyEncoder
1406     {
1407         self.queries.on_disk_cache.serialize(self.global_tcx(), encoder)
1408     }
1409
1410     /// This checks whether one is allowed to have pattern bindings
1411     /// that bind-by-move on a match arm that has a guard, e.g.:
1412     ///
1413     /// ```rust
1414     /// match foo { A(inner) if { /* something */ } => ..., ... }
1415     /// ```
1416     ///
1417     /// It is separate from check_for_mutation_in_guard_via_ast_walk,
1418     /// because that method has a narrower effect that can be toggled
1419     /// off via a separate `-Z` flag, at least for the short term.
1420     pub fn allow_bind_by_move_patterns_with_guards(self) -> bool {
1421         self.features().bind_by_move_pattern_guards && self.use_mir_borrowck()
1422     }
1423
1424     /// If true, we should use a naive AST walk to determine if match
1425     /// guard could perform bad mutations (or mutable-borrows).
1426     pub fn check_for_mutation_in_guard_via_ast_walk(self) -> bool {
1427         // If someone requests the feature, then be a little more
1428         // careful and ensure that MIR-borrowck is enabled (which can
1429         // happen via edition selection, via `feature(nll)`, or via an
1430         // appropriate `-Z` flag) before disabling the mutation check.
1431         if self.allow_bind_by_move_patterns_with_guards() {
1432             return false;
1433         }
1434
1435         return true;
1436     }
1437
1438     /// If true, we should use the AST-based borrowck (we may *also* use
1439     /// the MIR-based borrowck).
1440     pub fn use_ast_borrowck(self) -> bool {
1441         self.borrowck_mode().use_ast()
1442     }
1443
1444     /// If true, we should use the MIR-based borrowck (we may *also* use
1445     /// the AST-based borrowck).
1446     pub fn use_mir_borrowck(self) -> bool {
1447         self.borrowck_mode().use_mir()
1448     }
1449
1450     /// If true, we should use the MIR-based borrow check, but also
1451     /// fall back on the AST borrow check if the MIR-based one errors.
1452     pub fn migrate_borrowck(self) -> bool {
1453         self.borrowck_mode().migrate()
1454     }
1455
1456     /// If true, make MIR codegen for `match` emit a temp that holds a
1457     /// borrow of the input to the match expression.
1458     pub fn generate_borrow_of_any_match_input(&self) -> bool {
1459         self.emit_read_for_match()
1460     }
1461
1462     /// If true, make MIR codegen for `match` emit FakeRead
1463     /// statements (which simulate the maximal effect of executing the
1464     /// patterns in a match arm).
1465     pub fn emit_read_for_match(&self) -> bool {
1466         self.use_mir_borrowck() && !self.sess.opts.debugging_opts.nll_dont_emit_read_for_match
1467     }
1468
1469     /// If true, pattern variables for use in guards on match arms
1470     /// will be bound as references to the data, and occurrences of
1471     /// those variables in the guard expression will implicitly
1472     /// dereference those bindings. (See rust-lang/rust#27282.)
1473     pub fn all_pat_vars_are_implicit_refs_within_guards(self) -> bool {
1474         self.borrowck_mode().use_mir()
1475     }
1476
1477     /// If true, we should enable two-phase borrows checks. This is
1478     /// done with either: `-Ztwo-phase-borrows`, `#![feature(nll)]`,
1479     /// or by opting into an edition after 2015.
1480     pub fn two_phase_borrows(self) -> bool {
1481         self.sess.rust_2018() || self.features().nll ||
1482         self.sess.opts.debugging_opts.two_phase_borrows
1483     }
1484
1485     /// What mode(s) of borrowck should we run? AST? MIR? both?
1486     /// (Also considers the `#![feature(nll)]` setting.)
1487     pub fn borrowck_mode(&self) -> BorrowckMode {
1488         // Here are the main constraints we need to deal with:
1489         //
1490         // 1. An opts.borrowck_mode of `BorrowckMode::Ast` is
1491         //    synonymous with no `-Z borrowck=...` flag at all.
1492         //    (This is arguably a historical accident.)
1493         //
1494         // 2. `BorrowckMode::Migrate` is the limited migration to
1495         //    NLL that we are deploying with the 2018 edition.
1496         //
1497         // 3. We want to allow developers on the Nightly channel
1498         //    to opt back into the "hard error" mode for NLL,
1499         //    (which they can do via specifying `#![feature(nll)]`
1500         //    explicitly in their crate).
1501         //
1502         // So, this precedence list is how pnkfelix chose to work with
1503         // the above constraints:
1504         //
1505         // * `#![feature(nll)]` *always* means use NLL with hard
1506         //   errors. (To simplify the code here, it now even overrides
1507         //   a user's attempt to specify `-Z borrowck=compare`, which
1508         //   we arguably do not need anymore and should remove.)
1509         //
1510         // * Otherwise, if no `-Z borrowck=...` flag was given (or
1511         //   if `borrowck=ast` was specified), then use the default
1512         //   as required by the edition.
1513         //
1514         // * Otherwise, use the behavior requested via `-Z borrowck=...`
1515
1516         if self.features().nll { return BorrowckMode::Mir; }
1517
1518         match self.sess.opts.borrowck_mode {
1519             mode @ BorrowckMode::Mir |
1520             mode @ BorrowckMode::Compare |
1521             mode @ BorrowckMode::Migrate => mode,
1522
1523             BorrowckMode::Ast => match self.sess.edition() {
1524                 Edition::Edition2015 => BorrowckMode::Ast,
1525                 Edition::Edition2018 => BorrowckMode::Migrate,
1526
1527                 // For now, future editions mean Migrate. (But it
1528                 // would make a lot of sense for it to be changed to
1529                 // `BorrowckMode::Mir`, depending on how we plan to
1530                 // time the forcing of full migration to NLL.)
1531                 _ => BorrowckMode::Migrate,
1532             },
1533         }
1534     }
1535
1536     #[inline]
1537     pub fn local_crate_exports_generics(self) -> bool {
1538         debug_assert!(self.sess.opts.share_generics());
1539
1540         self.sess.crate_types.borrow().iter().any(|crate_type| {
1541             match crate_type {
1542                 CrateType::Executable |
1543                 CrateType::Staticlib  |
1544                 CrateType::ProcMacro  |
1545                 CrateType::Cdylib     => false,
1546                 CrateType::Rlib       |
1547                 CrateType::Dylib      => true,
1548             }
1549         })
1550     }
1551
1552     // This method returns the DefId and the BoundRegion corresponding to the given region.
1553     pub fn is_suitable_region(&self, region: Region<'tcx>) -> Option<FreeRegionInfo> {
1554         let (suitable_region_binding_scope, bound_region) = match *region {
1555             ty::ReFree(ref free_region) => (free_region.scope, free_region.bound_region),
1556             ty::ReEarlyBound(ref ebr) => (
1557                 self.parent_def_id(ebr.def_id).unwrap(),
1558                 ty::BoundRegion::BrNamed(ebr.def_id, ebr.name),
1559             ),
1560             _ => return None, // not a free region
1561         };
1562
1563         let node_id = self.hir
1564             .as_local_node_id(suitable_region_binding_scope)
1565             .unwrap();
1566         let is_impl_item = match self.hir.find(node_id) {
1567             Some(Node::Item(..)) | Some(Node::TraitItem(..)) => false,
1568             Some(Node::ImplItem(..)) => {
1569                 self.is_bound_region_in_impl_item(suitable_region_binding_scope)
1570             }
1571             _ => return None,
1572         };
1573
1574         return Some(FreeRegionInfo {
1575             def_id: suitable_region_binding_scope,
1576             boundregion: bound_region,
1577             is_impl_item: is_impl_item,
1578         });
1579     }
1580
1581     pub fn return_type_impl_trait(
1582         &self,
1583         scope_def_id: DefId,
1584     ) -> Option<Ty<'tcx>> {
1585         // HACK: `type_of_def_id()` will fail on these (#55796), so return None
1586         let node_id = self.hir.as_local_node_id(scope_def_id).unwrap();
1587         match self.hir.get(node_id) {
1588             Node::Item(item) => {
1589                 match item.node {
1590                     ItemKind::Fn(..) => { /* type_of_def_id() will work */ }
1591                     _ => {
1592                         return None;
1593                     }
1594                 }
1595             }
1596             _ => { /* type_of_def_id() will work or panic */ }
1597         }
1598
1599         let ret_ty = self.type_of(scope_def_id);
1600         match ret_ty.sty {
1601             ty::FnDef(_, _) => {
1602                 let sig = ret_ty.fn_sig(*self);
1603                 let output = self.erase_late_bound_regions(&sig.output());
1604                 if output.is_impl_trait() {
1605                     Some(output)
1606                 } else {
1607                     None
1608                 }
1609             }
1610             _ => None
1611         }
1612     }
1613
1614     // Here we check if the bound region is in Impl Item.
1615     pub fn is_bound_region_in_impl_item(
1616         &self,
1617         suitable_region_binding_scope: DefId,
1618     ) -> bool {
1619         let container_id = self.associated_item(suitable_region_binding_scope)
1620             .container
1621             .id();
1622         if self.impl_trait_ref(container_id).is_some() {
1623             // For now, we do not try to target impls of traits. This is
1624             // because this message is going to suggest that the user
1625             // change the fn signature, but they may not be free to do so,
1626             // since the signature must match the trait.
1627             //
1628             // FIXME(#42706) -- in some cases, we could do better here.
1629             return true;
1630         }
1631         false
1632     }
1633 }
1634
1635 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
1636     pub fn encode_metadata(self)
1637         -> EncodedMetadata
1638     {
1639         self.cstore.encode_metadata(self)
1640     }
1641 }
1642
1643 impl<'gcx: 'tcx, 'tcx> GlobalCtxt<'gcx> {
1644     /// Call the closure with a local `TyCtxt` using the given arena.
1645     pub fn enter_local<F, R>(
1646         &self,
1647         arena: &'tcx SyncDroplessArena,
1648         f: F
1649     ) -> R
1650     where
1651         F: for<'a> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
1652     {
1653         let interners = CtxtInterners::new(arena);
1654         let tcx = TyCtxt {
1655             gcx: self,
1656             interners: &interners,
1657         };
1658         ty::tls::with_related_context(tcx.global_tcx(), |icx| {
1659             let new_icx = ty::tls::ImplicitCtxt {
1660                 tcx,
1661                 query: icx.query.clone(),
1662                 layout_depth: icx.layout_depth,
1663                 task: icx.task,
1664             };
1665             ty::tls::enter_context(&new_icx, |new_icx| {
1666                 f(new_icx.tcx)
1667             })
1668         })
1669     }
1670 }
1671
1672 /// A trait implemented for all X<'a> types which can be safely and
1673 /// efficiently converted to X<'tcx> as long as they are part of the
1674 /// provided TyCtxt<'tcx>.
1675 /// This can be done, for example, for Ty<'tcx> or &'tcx Substs<'tcx>
1676 /// by looking them up in their respective interners.
1677 ///
1678 /// However, this is still not the best implementation as it does
1679 /// need to compare the components, even for interned values.
1680 /// It would be more efficient if TypedArena provided a way to
1681 /// determine whether the address is in the allocated range.
1682 ///
1683 /// None is returned if the value or one of the components is not part
1684 /// of the provided context.
1685 /// For Ty, None can be returned if either the type interner doesn't
1686 /// contain the TyKind key or if the address of the interned
1687 /// pointer differs. The latter case is possible if a primitive type,
1688 /// e.g. `()` or `u8`, was interned in a different context.
1689 pub trait Lift<'tcx>: fmt::Debug {
1690     type Lifted: fmt::Debug + 'tcx;
1691     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted>;
1692 }
1693
1694 impl<'a, 'tcx> Lift<'tcx> for Ty<'a> {
1695     type Lifted = Ty<'tcx>;
1696     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Ty<'tcx>> {
1697         if tcx.interners.arena.in_arena(*self as *const _) {
1698             return Some(unsafe { mem::transmute(*self) });
1699         }
1700         // Also try in the global tcx if we're not that.
1701         if !tcx.is_global() {
1702             self.lift_to_tcx(tcx.global_tcx())
1703         } else {
1704             None
1705         }
1706     }
1707 }
1708
1709 impl<'a, 'tcx> Lift<'tcx> for Region<'a> {
1710     type Lifted = Region<'tcx>;
1711     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Region<'tcx>> {
1712         if tcx.interners.arena.in_arena(*self as *const _) {
1713             return Some(unsafe { mem::transmute(*self) });
1714         }
1715         // Also try in the global tcx if we're not that.
1716         if !tcx.is_global() {
1717             self.lift_to_tcx(tcx.global_tcx())
1718         } else {
1719             None
1720         }
1721     }
1722 }
1723
1724 impl<'a, 'tcx> Lift<'tcx> for Goal<'a> {
1725     type Lifted = Goal<'tcx>;
1726     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Goal<'tcx>> {
1727         if tcx.interners.arena.in_arena(*self as *const _) {
1728             return Some(unsafe { mem::transmute(*self) });
1729         }
1730         // Also try in the global tcx if we're not that.
1731         if !tcx.is_global() {
1732             self.lift_to_tcx(tcx.global_tcx())
1733         } else {
1734             None
1735         }
1736     }
1737 }
1738
1739 impl<'a, 'tcx> Lift<'tcx> for &'a List<Goal<'a>> {
1740     type Lifted = &'tcx List<Goal<'tcx>>;
1741     fn lift_to_tcx<'b, 'gcx>(
1742         &self,
1743         tcx: TyCtxt<'b, 'gcx, 'tcx>,
1744     ) -> Option<&'tcx List<Goal<'tcx>>> {
1745         if tcx.interners.arena.in_arena(*self as *const _) {
1746             return Some(unsafe { mem::transmute(*self) });
1747         }
1748         // Also try in the global tcx if we're not that.
1749         if !tcx.is_global() {
1750             self.lift_to_tcx(tcx.global_tcx())
1751         } else {
1752             None
1753         }
1754     }
1755 }
1756
1757 impl<'a, 'tcx> Lift<'tcx> for &'a List<Clause<'a>> {
1758     type Lifted = &'tcx List<Clause<'tcx>>;
1759     fn lift_to_tcx<'b, 'gcx>(
1760         &self,
1761         tcx: TyCtxt<'b, 'gcx, 'tcx>,
1762     ) -> Option<&'tcx List<Clause<'tcx>>> {
1763         if tcx.interners.arena.in_arena(*self as *const _) {
1764             return Some(unsafe { mem::transmute(*self) });
1765         }
1766         // Also try in the global tcx if we're not that.
1767         if !tcx.is_global() {
1768             self.lift_to_tcx(tcx.global_tcx())
1769         } else {
1770             None
1771         }
1772     }
1773 }
1774
1775 impl<'a, 'tcx> Lift<'tcx> for &'a Const<'a> {
1776     type Lifted = &'tcx Const<'tcx>;
1777     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Const<'tcx>> {
1778         if tcx.interners.arena.in_arena(*self as *const _) {
1779             return Some(unsafe { mem::transmute(*self) });
1780         }
1781         // Also try in the global tcx if we're not that.
1782         if !tcx.is_global() {
1783             self.lift_to_tcx(tcx.global_tcx())
1784         } else {
1785             None
1786         }
1787     }
1788 }
1789
1790 impl<'a, 'tcx> Lift<'tcx> for &'a Substs<'a> {
1791     type Lifted = &'tcx Substs<'tcx>;
1792     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Substs<'tcx>> {
1793         if self.len() == 0 {
1794             return Some(List::empty());
1795         }
1796         if tcx.interners.arena.in_arena(&self[..] as *const _) {
1797             return Some(unsafe { mem::transmute(*self) });
1798         }
1799         // Also try in the global tcx if we're not that.
1800         if !tcx.is_global() {
1801             self.lift_to_tcx(tcx.global_tcx())
1802         } else {
1803             None
1804         }
1805     }
1806 }
1807
1808 impl<'a, 'tcx> Lift<'tcx> for &'a List<Ty<'a>> {
1809     type Lifted = &'tcx List<Ty<'tcx>>;
1810     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
1811                              -> Option<&'tcx List<Ty<'tcx>>> {
1812         if self.len() == 0 {
1813             return Some(List::empty());
1814         }
1815         if tcx.interners.arena.in_arena(*self as *const _) {
1816             return Some(unsafe { mem::transmute(*self) });
1817         }
1818         // Also try in the global tcx if we're not that.
1819         if !tcx.is_global() {
1820             self.lift_to_tcx(tcx.global_tcx())
1821         } else {
1822             None
1823         }
1824     }
1825 }
1826
1827 impl<'a, 'tcx> Lift<'tcx> for &'a List<ExistentialPredicate<'a>> {
1828     type Lifted = &'tcx List<ExistentialPredicate<'tcx>>;
1829     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
1830         -> Option<&'tcx List<ExistentialPredicate<'tcx>>> {
1831         if self.is_empty() {
1832             return Some(List::empty());
1833         }
1834         if tcx.interners.arena.in_arena(*self as *const _) {
1835             return Some(unsafe { mem::transmute(*self) });
1836         }
1837         // Also try in the global tcx if we're not that.
1838         if !tcx.is_global() {
1839             self.lift_to_tcx(tcx.global_tcx())
1840         } else {
1841             None
1842         }
1843     }
1844 }
1845
1846 impl<'a, 'tcx> Lift<'tcx> for &'a List<Predicate<'a>> {
1847     type Lifted = &'tcx List<Predicate<'tcx>>;
1848     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
1849         -> Option<&'tcx List<Predicate<'tcx>>> {
1850         if self.is_empty() {
1851             return Some(List::empty());
1852         }
1853         if tcx.interners.arena.in_arena(*self as *const _) {
1854             return Some(unsafe { mem::transmute(*self) });
1855         }
1856         // Also try in the global tcx if we're not that.
1857         if !tcx.is_global() {
1858             self.lift_to_tcx(tcx.global_tcx())
1859         } else {
1860             None
1861         }
1862     }
1863 }
1864
1865 impl<'a, 'tcx> Lift<'tcx> for &'a List<CanonicalVarInfo> {
1866     type Lifted = &'tcx List<CanonicalVarInfo>;
1867     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
1868         if self.len() == 0 {
1869             return Some(List::empty());
1870         }
1871         if tcx.interners.arena.in_arena(*self as *const _) {
1872             return Some(unsafe { mem::transmute(*self) });
1873         }
1874         // Also try in the global tcx if we're not that.
1875         if !tcx.is_global() {
1876             self.lift_to_tcx(tcx.global_tcx())
1877         } else {
1878             None
1879         }
1880     }
1881 }
1882
1883 impl<'a, 'tcx> Lift<'tcx> for &'a List<ProjectionKind<'a>> {
1884     type Lifted = &'tcx List<ProjectionKind<'tcx>>;
1885     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
1886         if self.len() == 0 {
1887             return Some(List::empty());
1888         }
1889         if tcx.interners.arena.in_arena(*self as *const _) {
1890             return Some(unsafe { mem::transmute(*self) });
1891         }
1892         // Also try in the global tcx if we're not that.
1893         if !tcx.is_global() {
1894             self.lift_to_tcx(tcx.global_tcx())
1895         } else {
1896             None
1897         }
1898     }
1899 }
1900
1901 pub mod tls {
1902     use super::{GlobalCtxt, TyCtxt};
1903
1904     use std::fmt;
1905     use std::mem;
1906     use syntax_pos;
1907     use ty::query;
1908     use errors::{Diagnostic, TRACK_DIAGNOSTICS};
1909     use rustc_data_structures::OnDrop;
1910     use rustc_data_structures::sync::{self, Lrc, Lock};
1911     use dep_graph::OpenTask;
1912
1913     #[cfg(not(parallel_queries))]
1914     use std::cell::Cell;
1915
1916     #[cfg(parallel_queries)]
1917     use rayon_core;
1918
1919     /// This is the implicit state of rustc. It contains the current
1920     /// TyCtxt and query. It is updated when creating a local interner or
1921     /// executing a new query. Whenever there's a TyCtxt value available
1922     /// you should also have access to an ImplicitCtxt through the functions
1923     /// in this module.
1924     #[derive(Clone)]
1925     pub struct ImplicitCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
1926         /// The current TyCtxt. Initially created by `enter_global` and updated
1927         /// by `enter_local` with a new local interner
1928         pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
1929
1930         /// The current query job, if any. This is updated by start_job in
1931         /// ty::query::plumbing when executing a query
1932         pub query: Option<Lrc<query::QueryJob<'gcx>>>,
1933
1934         /// Used to prevent layout from recursing too deeply.
1935         pub layout_depth: usize,
1936
1937         /// The current dep graph task. This is used to add dependencies to queries
1938         /// when executing them
1939         pub task: &'a OpenTask,
1940     }
1941
1942     /// Sets Rayon's thread local variable which is preserved for Rayon jobs
1943     /// to `value` during the call to `f`. It is restored to its previous value after.
1944     /// This is used to set the pointer to the new ImplicitCtxt.
1945     #[cfg(parallel_queries)]
1946     fn set_tlv<F: FnOnce() -> R, R>(value: usize, f: F) -> R {
1947         rayon_core::tlv::with(value, f)
1948     }
1949
1950     /// Gets Rayon's thread local variable which is preserved for Rayon jobs.
1951     /// This is used to get the pointer to the current ImplicitCtxt.
1952     #[cfg(parallel_queries)]
1953     fn get_tlv() -> usize {
1954         rayon_core::tlv::get()
1955     }
1956
1957     /// A thread local variable which stores a pointer to the current ImplicitCtxt
1958     #[cfg(not(parallel_queries))]
1959     thread_local!(static TLV: Cell<usize> = Cell::new(0));
1960
1961     /// Sets TLV to `value` during the call to `f`.
1962     /// It is restored to its previous value after.
1963     /// This is used to set the pointer to the new ImplicitCtxt.
1964     #[cfg(not(parallel_queries))]
1965     fn set_tlv<F: FnOnce() -> R, R>(value: usize, f: F) -> R {
1966         let old = get_tlv();
1967         let _reset = OnDrop(move || TLV.with(|tlv| tlv.set(old)));
1968         TLV.with(|tlv| tlv.set(value));
1969         f()
1970     }
1971
1972     /// This is used to get the pointer to the current ImplicitCtxt.
1973     #[cfg(not(parallel_queries))]
1974     fn get_tlv() -> usize {
1975         TLV.with(|tlv| tlv.get())
1976     }
1977
1978     /// This is a callback from libsyntax as it cannot access the implicit state
1979     /// in librustc otherwise
1980     fn span_debug(span: syntax_pos::Span, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1981         with(|tcx| {
1982             write!(f, "{}", tcx.sess.source_map().span_to_string(span))
1983         })
1984     }
1985
1986     /// This is a callback from libsyntax as it cannot access the implicit state
1987     /// in librustc otherwise. It is used to when diagnostic messages are
1988     /// emitted and stores them in the current query, if there is one.
1989     fn track_diagnostic(diagnostic: &Diagnostic) {
1990         with_context_opt(|icx| {
1991             if let Some(icx) = icx {
1992                 if let Some(ref query) = icx.query {
1993                     query.diagnostics.lock().push(diagnostic.clone());
1994                 }
1995             }
1996         })
1997     }
1998
1999     /// Sets up the callbacks from libsyntax on the current thread
2000     pub fn with_thread_locals<F, R>(f: F) -> R
2001         where F: FnOnce() -> R
2002     {
2003         syntax_pos::SPAN_DEBUG.with(|span_dbg| {
2004             let original_span_debug = span_dbg.get();
2005             span_dbg.set(span_debug);
2006
2007             let _on_drop = OnDrop(move || {
2008                 span_dbg.set(original_span_debug);
2009             });
2010
2011             TRACK_DIAGNOSTICS.with(|current| {
2012                 let original = current.get();
2013                 current.set(track_diagnostic);
2014
2015                 let _on_drop = OnDrop(move || {
2016                     current.set(original);
2017                 });
2018
2019                 f()
2020             })
2021         })
2022     }
2023
2024     /// Sets `context` as the new current ImplicitCtxt for the duration of the function `f`
2025     pub fn enter_context<'a, 'gcx: 'tcx, 'tcx, F, R>(context: &ImplicitCtxt<'a, 'gcx, 'tcx>,
2026                                                      f: F) -> R
2027         where F: FnOnce(&ImplicitCtxt<'a, 'gcx, 'tcx>) -> R
2028     {
2029         set_tlv(context as *const _ as usize, || {
2030             f(&context)
2031         })
2032     }
2033
2034     /// Enters GlobalCtxt by setting up libsyntax callbacks and
2035     /// creating a initial TyCtxt and ImplicitCtxt.
2036     /// This happens once per rustc session and TyCtxts only exists
2037     /// inside the `f` function.
2038     pub fn enter_global<'gcx, F, R>(gcx: &GlobalCtxt<'gcx>, f: F) -> R
2039         where F: for<'a> FnOnce(TyCtxt<'a, 'gcx, 'gcx>) -> R
2040     {
2041         with_thread_locals(|| {
2042             // Update GCX_PTR to indicate there's a GlobalCtxt available
2043             GCX_PTR.with(|lock| {
2044                 *lock.lock() = gcx as *const _ as usize;
2045             });
2046             // Set GCX_PTR back to 0 when we exit
2047             let _on_drop = OnDrop(move || {
2048                 GCX_PTR.with(|lock| *lock.lock() = 0);
2049             });
2050
2051             let tcx = TyCtxt {
2052                 gcx,
2053                 interners: &gcx.global_interners,
2054             };
2055             let icx = ImplicitCtxt {
2056                 tcx,
2057                 query: None,
2058                 layout_depth: 0,
2059                 task: &OpenTask::Ignore,
2060             };
2061             enter_context(&icx, |_| {
2062                 f(tcx)
2063             })
2064         })
2065     }
2066
2067     /// Stores a pointer to the GlobalCtxt if one is available.
2068     /// This is used to access the GlobalCtxt in the deadlock handler
2069     /// given to Rayon.
2070     scoped_thread_local!(pub static GCX_PTR: Lock<usize>);
2071
2072     /// Creates a TyCtxt and ImplicitCtxt based on the GCX_PTR thread local.
2073     /// This is used in the deadlock handler.
2074     pub unsafe fn with_global<F, R>(f: F) -> R
2075         where F: for<'a, 'gcx, 'tcx> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
2076     {
2077         let gcx = GCX_PTR.with(|lock| *lock.lock());
2078         assert!(gcx != 0);
2079         let gcx = &*(gcx as *const GlobalCtxt<'_>);
2080         let tcx = TyCtxt {
2081             gcx,
2082             interners: &gcx.global_interners,
2083         };
2084         let icx = ImplicitCtxt {
2085             query: None,
2086             tcx,
2087             layout_depth: 0,
2088             task: &OpenTask::Ignore,
2089         };
2090         enter_context(&icx, |_| f(tcx))
2091     }
2092
2093     /// Allows access to the current ImplicitCtxt in a closure if one is available
2094     pub fn with_context_opt<F, R>(f: F) -> R
2095         where F: for<'a, 'gcx, 'tcx> FnOnce(Option<&ImplicitCtxt<'a, 'gcx, 'tcx>>) -> R
2096     {
2097         let context = get_tlv();
2098         if context == 0 {
2099             f(None)
2100         } else {
2101             // We could get a ImplicitCtxt pointer from another thread.
2102             // Ensure that ImplicitCtxt is Sync
2103             sync::assert_sync::<ImplicitCtxt<'_, '_, '_>>();
2104
2105             unsafe { f(Some(&*(context as *const ImplicitCtxt<'_, '_, '_>))) }
2106         }
2107     }
2108
2109     /// Allows access to the current ImplicitCtxt.
2110     /// Panics if there is no ImplicitCtxt available
2111     pub fn with_context<F, R>(f: F) -> R
2112         where F: for<'a, 'gcx, 'tcx> FnOnce(&ImplicitCtxt<'a, 'gcx, 'tcx>) -> R
2113     {
2114         with_context_opt(|opt_context| f(opt_context.expect("no ImplicitCtxt stored in tls")))
2115     }
2116
2117     /// Allows access to the current ImplicitCtxt whose tcx field has the same global
2118     /// interner as the tcx argument passed in. This means the closure is given an ImplicitCtxt
2119     /// with the same 'gcx lifetime as the TyCtxt passed in.
2120     /// This will panic if you pass it a TyCtxt which has a different global interner from
2121     /// the current ImplicitCtxt's tcx field.
2122     pub fn with_related_context<'a, 'gcx, 'tcx1, F, R>(tcx: TyCtxt<'a, 'gcx, 'tcx1>, f: F) -> R
2123         where F: for<'b, 'tcx2> FnOnce(&ImplicitCtxt<'b, 'gcx, 'tcx2>) -> R
2124     {
2125         with_context(|context| {
2126             unsafe {
2127                 let gcx = tcx.gcx as *const _ as usize;
2128                 assert!(context.tcx.gcx as *const _ as usize == gcx);
2129                 let context: &ImplicitCtxt<'_, '_, '_> = mem::transmute(context);
2130                 f(context)
2131             }
2132         })
2133     }
2134
2135     /// Allows access to the current ImplicitCtxt whose tcx field has the same global
2136     /// interner and local interner as the tcx argument passed in. This means the closure
2137     /// is given an ImplicitCtxt with the same 'tcx and 'gcx lifetimes as the TyCtxt passed in.
2138     /// This will panic if you pass it a TyCtxt which has a different global interner or
2139     /// a different local interner from the current ImplicitCtxt's tcx field.
2140     pub fn with_fully_related_context<'a, 'gcx, 'tcx, F, R>(tcx: TyCtxt<'a, 'gcx, 'tcx>, f: F) -> R
2141         where F: for<'b> FnOnce(&ImplicitCtxt<'b, 'gcx, 'tcx>) -> R
2142     {
2143         with_context(|context| {
2144             unsafe {
2145                 let gcx = tcx.gcx as *const _ as usize;
2146                 let interners = tcx.interners as *const _ as usize;
2147                 assert!(context.tcx.gcx as *const _ as usize == gcx);
2148                 assert!(context.tcx.interners as *const _ as usize == interners);
2149                 let context: &ImplicitCtxt<'_, '_, '_> = mem::transmute(context);
2150                 f(context)
2151             }
2152         })
2153     }
2154
2155     /// Allows access to the TyCtxt in the current ImplicitCtxt.
2156     /// Panics if there is no ImplicitCtxt available
2157     pub fn with<F, R>(f: F) -> R
2158         where F: for<'a, 'gcx, 'tcx> FnOnce(TyCtxt<'a, 'gcx, 'tcx>) -> R
2159     {
2160         with_context(|context| f(context.tcx))
2161     }
2162
2163     /// Allows access to the TyCtxt in the current ImplicitCtxt.
2164     /// The closure is passed None if there is no ImplicitCtxt available
2165     pub fn with_opt<F, R>(f: F) -> R
2166         where F: for<'a, 'gcx, 'tcx> FnOnce(Option<TyCtxt<'a, 'gcx, 'tcx>>) -> R
2167     {
2168         with_context_opt(|opt_context| f(opt_context.map(|context| context.tcx)))
2169     }
2170 }
2171
2172 macro_rules! sty_debug_print {
2173     ($ctxt: expr, $($variant: ident),*) => {{
2174         // curious inner module to allow variant names to be used as
2175         // variable names.
2176         #[allow(non_snake_case)]
2177         mod inner {
2178             use ty::{self, TyCtxt};
2179             use ty::context::Interned;
2180
2181             #[derive(Copy, Clone)]
2182             struct DebugStat {
2183                 total: usize,
2184                 region_infer: usize,
2185                 ty_infer: usize,
2186                 both_infer: usize,
2187             }
2188
2189             pub fn go(tcx: TyCtxt<'_, '_, '_>) {
2190                 let mut total = DebugStat {
2191                     total: 0,
2192                     region_infer: 0, ty_infer: 0, both_infer: 0,
2193                 };
2194                 $(let mut $variant = total;)*
2195
2196                 for &Interned(t) in tcx.interners.type_.borrow().iter() {
2197                     let variant = match t.sty {
2198                         ty::Bool | ty::Char | ty::Int(..) | ty::Uint(..) |
2199                             ty::Float(..) | ty::Str | ty::Never => continue,
2200                         ty::Error => /* unimportant */ continue,
2201                         $(ty::$variant(..) => &mut $variant,)*
2202                     };
2203                     let region = t.flags.intersects(ty::TypeFlags::HAS_RE_INFER);
2204                     let ty = t.flags.intersects(ty::TypeFlags::HAS_TY_INFER);
2205
2206                     variant.total += 1;
2207                     total.total += 1;
2208                     if region { total.region_infer += 1; variant.region_infer += 1 }
2209                     if ty { total.ty_infer += 1; variant.ty_infer += 1 }
2210                     if region && ty { total.both_infer += 1; variant.both_infer += 1 }
2211                 }
2212                 println!("Ty interner             total           ty region  both");
2213                 $(println!("    {:18}: {uses:6} {usespc:4.1}%, \
2214                             {ty:4.1}% {region:5.1}% {both:4.1}%",
2215                            stringify!($variant),
2216                            uses = $variant.total,
2217                            usespc = $variant.total as f64 * 100.0 / total.total as f64,
2218                            ty = $variant.ty_infer as f64 * 100.0  / total.total as f64,
2219                            region = $variant.region_infer as f64 * 100.0  / total.total as f64,
2220                            both = $variant.both_infer as f64 * 100.0  / total.total as f64);
2221                   )*
2222                 println!("                  total {uses:6}        \
2223                           {ty:4.1}% {region:5.1}% {both:4.1}%",
2224                          uses = total.total,
2225                          ty = total.ty_infer as f64 * 100.0  / total.total as f64,
2226                          region = total.region_infer as f64 * 100.0  / total.total as f64,
2227                          both = total.both_infer as f64 * 100.0  / total.total as f64)
2228             }
2229         }
2230
2231         inner::go($ctxt)
2232     }}
2233 }
2234
2235 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
2236     pub fn print_debug_stats(self) {
2237         sty_debug_print!(
2238             self,
2239             Adt, Array, Slice, RawPtr, Ref, FnDef, FnPtr, Placeholder,
2240             Generator, GeneratorWitness, Dynamic, Closure, Tuple, Bound,
2241             Param, Infer, UnnormalizedProjection, Projection, Opaque, Foreign);
2242
2243         println!("Substs interner: #{}", self.interners.substs.borrow().len());
2244         println!("Region interner: #{}", self.interners.region.borrow().len());
2245         println!("Stability interner: #{}", self.stability_interner.borrow().len());
2246         println!("Allocation interner: #{}", self.allocation_interner.borrow().len());
2247         println!("Layout interner: #{}", self.layout_interner.borrow().len());
2248     }
2249 }
2250
2251
2252 /// An entry in an interner.
2253 struct Interned<'tcx, T: 'tcx+?Sized>(&'tcx T);
2254
2255 // NB: An Interned<Ty> compares and hashes as a sty.
2256 impl<'tcx> PartialEq for Interned<'tcx, TyS<'tcx>> {
2257     fn eq(&self, other: &Interned<'tcx, TyS<'tcx>>) -> bool {
2258         self.0.sty == other.0.sty
2259     }
2260 }
2261
2262 impl<'tcx> Eq for Interned<'tcx, TyS<'tcx>> {}
2263
2264 impl<'tcx> Hash for Interned<'tcx, TyS<'tcx>> {
2265     fn hash<H: Hasher>(&self, s: &mut H) {
2266         self.0.sty.hash(s)
2267     }
2268 }
2269
2270 impl<'tcx: 'lcx, 'lcx> Borrow<TyKind<'lcx>> for Interned<'tcx, TyS<'tcx>> {
2271     fn borrow<'a>(&'a self) -> &'a TyKind<'lcx> {
2272         &self.0.sty
2273     }
2274 }
2275
2276 // NB: An Interned<List<T>> compares and hashes as its elements.
2277 impl<'tcx, T: PartialEq> PartialEq for Interned<'tcx, List<T>> {
2278     fn eq(&self, other: &Interned<'tcx, List<T>>) -> bool {
2279         self.0[..] == other.0[..]
2280     }
2281 }
2282
2283 impl<'tcx, T: Eq> Eq for Interned<'tcx, List<T>> {}
2284
2285 impl<'tcx, T: Hash> Hash for Interned<'tcx, List<T>> {
2286     fn hash<H: Hasher>(&self, s: &mut H) {
2287         self.0[..].hash(s)
2288     }
2289 }
2290
2291 impl<'tcx: 'lcx, 'lcx> Borrow<[Ty<'lcx>]> for Interned<'tcx, List<Ty<'tcx>>> {
2292     fn borrow<'a>(&'a self) -> &'a [Ty<'lcx>] {
2293         &self.0[..]
2294     }
2295 }
2296
2297 impl<'tcx: 'lcx, 'lcx> Borrow<[CanonicalVarInfo]> for Interned<'tcx, List<CanonicalVarInfo>> {
2298     fn borrow<'a>(&'a self) -> &'a [CanonicalVarInfo] {
2299         &self.0[..]
2300     }
2301 }
2302
2303 impl<'tcx: 'lcx, 'lcx> Borrow<[Kind<'lcx>]> for Interned<'tcx, Substs<'tcx>> {
2304     fn borrow<'a>(&'a self) -> &'a [Kind<'lcx>] {
2305         &self.0[..]
2306     }
2307 }
2308
2309 impl<'tcx: 'lcx, 'lcx> Borrow<[ProjectionKind<'lcx>]>
2310     for Interned<'tcx, List<ProjectionKind<'tcx>>> {
2311     fn borrow<'a>(&'a self) -> &'a [ProjectionKind<'lcx>] {
2312         &self.0[..]
2313     }
2314 }
2315
2316 impl<'tcx> Borrow<RegionKind> for Interned<'tcx, RegionKind> {
2317     fn borrow<'a>(&'a self) -> &'a RegionKind {
2318         &self.0
2319     }
2320 }
2321
2322 impl<'tcx: 'lcx, 'lcx> Borrow<GoalKind<'lcx>> for Interned<'tcx, GoalKind<'tcx>> {
2323     fn borrow<'a>(&'a self) -> &'a GoalKind<'lcx> {
2324         &self.0
2325     }
2326 }
2327
2328 impl<'tcx: 'lcx, 'lcx> Borrow<[ExistentialPredicate<'lcx>]>
2329     for Interned<'tcx, List<ExistentialPredicate<'tcx>>> {
2330     fn borrow<'a>(&'a self) -> &'a [ExistentialPredicate<'lcx>] {
2331         &self.0[..]
2332     }
2333 }
2334
2335 impl<'tcx: 'lcx, 'lcx> Borrow<[Predicate<'lcx>]>
2336     for Interned<'tcx, List<Predicate<'tcx>>> {
2337     fn borrow<'a>(&'a self) -> &'a [Predicate<'lcx>] {
2338         &self.0[..]
2339     }
2340 }
2341
2342 impl<'tcx: 'lcx, 'lcx> Borrow<Const<'lcx>> for Interned<'tcx, Const<'tcx>> {
2343     fn borrow<'a>(&'a self) -> &'a Const<'lcx> {
2344         &self.0
2345     }
2346 }
2347
2348 impl<'tcx: 'lcx, 'lcx> Borrow<[Clause<'lcx>]>
2349 for Interned<'tcx, List<Clause<'tcx>>> {
2350     fn borrow<'a>(&'a self) -> &'a [Clause<'lcx>] {
2351         &self.0[..]
2352     }
2353 }
2354
2355 impl<'tcx: 'lcx, 'lcx> Borrow<[Goal<'lcx>]>
2356 for Interned<'tcx, List<Goal<'tcx>>> {
2357     fn borrow<'a>(&'a self) -> &'a [Goal<'lcx>] {
2358         &self.0[..]
2359     }
2360 }
2361
2362 macro_rules! intern_method {
2363     ($lt_tcx:tt, $name:ident: $method:ident($alloc:ty,
2364                                             $alloc_method:expr,
2365                                             $alloc_to_key:expr,
2366                                             $keep_in_local_tcx:expr) -> $ty:ty) => {
2367         impl<'a, 'gcx, $lt_tcx> TyCtxt<'a, 'gcx, $lt_tcx> {
2368             pub fn $method(self, v: $alloc) -> &$lt_tcx $ty {
2369                 let key = ($alloc_to_key)(&v);
2370
2371                 // HACK(eddyb) Depend on flags being accurate to
2372                 // determine that all contents are in the global tcx.
2373                 // See comments on Lift for why we can't use that.
2374                 if ($keep_in_local_tcx)(&v) {
2375                     let mut interner = self.interners.$name.borrow_mut();
2376                     if let Some(&Interned(v)) = interner.get(key) {
2377                         return v;
2378                     }
2379
2380                     // Make sure we don't end up with inference
2381                     // types/regions in the global tcx.
2382                     if self.is_global() {
2383                         bug!("Attempted to intern `{:?}` which contains \
2384                               inference types/regions in the global type context",
2385                              v);
2386                     }
2387
2388                     let i = $alloc_method(&self.interners.arena, v);
2389                     interner.insert(Interned(i));
2390                     i
2391                 } else {
2392                     let mut interner = self.global_interners.$name.borrow_mut();
2393                     if let Some(&Interned(v)) = interner.get(key) {
2394                         return v;
2395                     }
2396
2397                     // This transmutes $alloc<'tcx> to $alloc<'gcx>
2398                     let v = unsafe {
2399                         mem::transmute(v)
2400                     };
2401                     let i: &$lt_tcx $ty = $alloc_method(&self.global_interners.arena, v);
2402                     // Cast to 'gcx
2403                     let i = unsafe { mem::transmute(i) };
2404                     interner.insert(Interned(i));
2405                     i
2406                 }
2407             }
2408         }
2409     }
2410 }
2411
2412 macro_rules! direct_interners {
2413     ($lt_tcx:tt, $($name:ident: $method:ident($keep_in_local_tcx:expr) -> $ty:ty),+) => {
2414         $(impl<$lt_tcx> PartialEq for Interned<$lt_tcx, $ty> {
2415             fn eq(&self, other: &Self) -> bool {
2416                 self.0 == other.0
2417             }
2418         }
2419
2420         impl<$lt_tcx> Eq for Interned<$lt_tcx, $ty> {}
2421
2422         impl<$lt_tcx> Hash for Interned<$lt_tcx, $ty> {
2423             fn hash<H: Hasher>(&self, s: &mut H) {
2424                 self.0.hash(s)
2425             }
2426         }
2427
2428         intern_method!(
2429             $lt_tcx,
2430             $name: $method($ty,
2431                            |a: &$lt_tcx SyncDroplessArena, v| -> &$lt_tcx $ty { a.alloc(v) },
2432                            |x| x,
2433                            $keep_in_local_tcx) -> $ty);)+
2434     }
2435 }
2436
2437 pub fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
2438     x.has_type_flags(ty::TypeFlags::KEEP_IN_LOCAL_TCX)
2439 }
2440
2441 direct_interners!('tcx,
2442     region: mk_region(|r: &RegionKind| r.keep_in_local_tcx()) -> RegionKind,
2443     const_: mk_const(|c: &Const<'_>| keep_local(&c.ty) || keep_local(&c.val)) -> Const<'tcx>,
2444     goal: mk_goal(|c: &GoalKind<'_>| keep_local(c)) -> GoalKind<'tcx>
2445 );
2446
2447 macro_rules! slice_interners {
2448     ($($field:ident: $method:ident($ty:ident)),+) => (
2449         $(intern_method!( 'tcx, $field: $method(
2450             &[$ty<'tcx>],
2451             |a, v| List::from_arena(a, v),
2452             Deref::deref,
2453             |xs: &[$ty<'_>]| xs.iter().any(keep_local)) -> List<$ty<'tcx>>);)+
2454     )
2455 }
2456
2457 slice_interners!(
2458     existential_predicates: _intern_existential_predicates(ExistentialPredicate),
2459     predicates: _intern_predicates(Predicate),
2460     type_list: _intern_type_list(Ty),
2461     substs: _intern_substs(Kind),
2462     clauses: _intern_clauses(Clause),
2463     goal_list: _intern_goals(Goal),
2464     projs: _intern_projs(ProjectionKind)
2465 );
2466
2467 // This isn't a perfect fit: CanonicalVarInfo slices are always
2468 // allocated in the global arena, so this `intern_method!` macro is
2469 // overly general.  But we just return false for the code that checks
2470 // whether they belong in the thread-local arena, so no harm done, and
2471 // seems better than open-coding the rest.
2472 intern_method! {
2473     'tcx,
2474     canonical_var_infos: _intern_canonical_var_infos(
2475         &[CanonicalVarInfo],
2476         |a, v| List::from_arena(a, v),
2477         Deref::deref,
2478         |_xs: &[CanonicalVarInfo]| -> bool { false }
2479     ) -> List<CanonicalVarInfo>
2480 }
2481
2482 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
2483     /// Given a `fn` type, returns an equivalent `unsafe fn` type;
2484     /// that is, a `fn` type that is equivalent in every way for being
2485     /// unsafe.
2486     pub fn safe_to_unsafe_fn_ty(self, sig: PolyFnSig<'tcx>) -> Ty<'tcx> {
2487         assert_eq!(sig.unsafety(), hir::Unsafety::Normal);
2488         self.mk_fn_ptr(sig.map_bound(|sig| ty::FnSig {
2489             unsafety: hir::Unsafety::Unsafe,
2490             ..sig
2491         }))
2492     }
2493
2494     /// Given a closure signature `sig`, returns an equivalent `fn`
2495     /// type with the same signature. Detuples and so forth -- so
2496     /// e.g. if we have a sig with `Fn<(u32, i32)>` then you would get
2497     /// a `fn(u32, i32)`.
2498     pub fn coerce_closure_fn_ty(self, sig: PolyFnSig<'tcx>) -> Ty<'tcx> {
2499         let converted_sig = sig.map_bound(|s| {
2500             let params_iter = match s.inputs()[0].sty {
2501                 ty::Tuple(params) => {
2502                     params.into_iter().cloned()
2503                 }
2504                 _ => bug!(),
2505             };
2506             self.mk_fn_sig(
2507                 params_iter,
2508                 s.output(),
2509                 s.variadic,
2510                 hir::Unsafety::Normal,
2511                 abi::Abi::Rust,
2512             )
2513         });
2514
2515         self.mk_fn_ptr(converted_sig)
2516     }
2517
2518     pub fn mk_ty(&self, st: TyKind<'tcx>) -> Ty<'tcx> {
2519         CtxtInterners::intern_ty(&self.interners, &self.global_interners, st)
2520     }
2521
2522     pub fn mk_mach_int(self, tm: ast::IntTy) -> Ty<'tcx> {
2523         match tm {
2524             ast::IntTy::Isize   => self.types.isize,
2525             ast::IntTy::I8   => self.types.i8,
2526             ast::IntTy::I16  => self.types.i16,
2527             ast::IntTy::I32  => self.types.i32,
2528             ast::IntTy::I64  => self.types.i64,
2529             ast::IntTy::I128  => self.types.i128,
2530         }
2531     }
2532
2533     pub fn mk_mach_uint(self, tm: ast::UintTy) -> Ty<'tcx> {
2534         match tm {
2535             ast::UintTy::Usize   => self.types.usize,
2536             ast::UintTy::U8   => self.types.u8,
2537             ast::UintTy::U16  => self.types.u16,
2538             ast::UintTy::U32  => self.types.u32,
2539             ast::UintTy::U64  => self.types.u64,
2540             ast::UintTy::U128  => self.types.u128,
2541         }
2542     }
2543
2544     pub fn mk_mach_float(self, tm: ast::FloatTy) -> Ty<'tcx> {
2545         match tm {
2546             ast::FloatTy::F32  => self.types.f32,
2547             ast::FloatTy::F64  => self.types.f64,
2548         }
2549     }
2550
2551     pub fn mk_str(self) -> Ty<'tcx> {
2552         self.mk_ty(Str)
2553     }
2554
2555     pub fn mk_static_str(self) -> Ty<'tcx> {
2556         self.mk_imm_ref(self.types.re_static, self.mk_str())
2557     }
2558
2559     pub fn mk_adt(self, def: &'tcx AdtDef, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
2560         // take a copy of substs so that we own the vectors inside
2561         self.mk_ty(Adt(def, substs))
2562     }
2563
2564     pub fn mk_foreign(self, def_id: DefId) -> Ty<'tcx> {
2565         self.mk_ty(Foreign(def_id))
2566     }
2567
2568     pub fn mk_box(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2569         let def_id = self.require_lang_item(lang_items::OwnedBoxLangItem);
2570         let adt_def = self.adt_def(def_id);
2571         let substs = Substs::for_item(self, def_id, |param, substs| {
2572             match param.kind {
2573                 GenericParamDefKind::Lifetime => bug!(),
2574                 GenericParamDefKind::Type { has_default, .. } => {
2575                     if param.index == 0 {
2576                         ty.into()
2577                     } else {
2578                         assert!(has_default);
2579                         self.type_of(param.def_id).subst(self, substs).into()
2580                     }
2581                 }
2582             }
2583         });
2584         self.mk_ty(Adt(adt_def, substs))
2585     }
2586
2587     pub fn mk_ptr(self, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
2588         self.mk_ty(RawPtr(tm))
2589     }
2590
2591     pub fn mk_ref(self, r: Region<'tcx>, tm: TypeAndMut<'tcx>) -> Ty<'tcx> {
2592         self.mk_ty(Ref(r, tm.ty, tm.mutbl))
2593     }
2594
2595     pub fn mk_mut_ref(self, r: Region<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
2596         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutMutable})
2597     }
2598
2599     pub fn mk_imm_ref(self, r: Region<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
2600         self.mk_ref(r, TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
2601     }
2602
2603     pub fn mk_mut_ptr(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2604         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutMutable})
2605     }
2606
2607     pub fn mk_imm_ptr(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2608         self.mk_ptr(TypeAndMut {ty: ty, mutbl: hir::MutImmutable})
2609     }
2610
2611     pub fn mk_nil_ptr(self) -> Ty<'tcx> {
2612         self.mk_imm_ptr(self.mk_unit())
2613     }
2614
2615     pub fn mk_array(self, ty: Ty<'tcx>, n: u64) -> Ty<'tcx> {
2616         self.mk_ty(Array(ty, ty::Const::from_usize(self, n)))
2617     }
2618
2619     pub fn mk_slice(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2620         self.mk_ty(Slice(ty))
2621     }
2622
2623     pub fn intern_tup(self, ts: &[Ty<'tcx>]) -> Ty<'tcx> {
2624         self.mk_ty(Tuple(self.intern_type_list(ts)))
2625     }
2626
2627     pub fn mk_tup<I: InternAs<[Ty<'tcx>], Ty<'tcx>>>(self, iter: I) -> I::Output {
2628         iter.intern_with(|ts| self.mk_ty(Tuple(self.intern_type_list(ts))))
2629     }
2630
2631     pub fn mk_unit(self) -> Ty<'tcx> {
2632         self.intern_tup(&[])
2633     }
2634
2635     pub fn mk_diverging_default(self) -> Ty<'tcx> {
2636         if self.features().never_type {
2637             self.types.never
2638         } else {
2639             self.intern_tup(&[])
2640         }
2641     }
2642
2643     pub fn mk_bool(self) -> Ty<'tcx> {
2644         self.mk_ty(Bool)
2645     }
2646
2647     pub fn mk_fn_def(self, def_id: DefId,
2648                      substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
2649         self.mk_ty(FnDef(def_id, substs))
2650     }
2651
2652     pub fn mk_fn_ptr(self, fty: PolyFnSig<'tcx>) -> Ty<'tcx> {
2653         self.mk_ty(FnPtr(fty))
2654     }
2655
2656     pub fn mk_dynamic(
2657         self,
2658         obj: ty::Binder<&'tcx List<ExistentialPredicate<'tcx>>>,
2659         reg: ty::Region<'tcx>
2660     ) -> Ty<'tcx> {
2661         self.mk_ty(Dynamic(obj, reg))
2662     }
2663
2664     pub fn mk_projection(self,
2665                          item_def_id: DefId,
2666                          substs: &'tcx Substs<'tcx>)
2667         -> Ty<'tcx> {
2668             self.mk_ty(Projection(ProjectionTy {
2669                 item_def_id,
2670                 substs,
2671             }))
2672         }
2673
2674     pub fn mk_closure(self, closure_id: DefId, closure_substs: ClosureSubsts<'tcx>)
2675                       -> Ty<'tcx> {
2676         self.mk_ty(Closure(closure_id, closure_substs))
2677     }
2678
2679     pub fn mk_generator(self,
2680                         id: DefId,
2681                         generator_substs: GeneratorSubsts<'tcx>,
2682                         movability: hir::GeneratorMovability)
2683                         -> Ty<'tcx> {
2684         self.mk_ty(Generator(id, generator_substs, movability))
2685     }
2686
2687     pub fn mk_generator_witness(self, types: ty::Binder<&'tcx List<Ty<'tcx>>>) -> Ty<'tcx> {
2688         self.mk_ty(GeneratorWitness(types))
2689     }
2690
2691     pub fn mk_var(self, v: TyVid) -> Ty<'tcx> {
2692         self.mk_infer(TyVar(v))
2693     }
2694
2695     pub fn mk_int_var(self, v: IntVid) -> Ty<'tcx> {
2696         self.mk_infer(IntVar(v))
2697     }
2698
2699     pub fn mk_float_var(self, v: FloatVid) -> Ty<'tcx> {
2700         self.mk_infer(FloatVar(v))
2701     }
2702
2703     pub fn mk_infer(self, it: InferTy) -> Ty<'tcx> {
2704         self.mk_ty(Infer(it))
2705     }
2706
2707     pub fn mk_ty_param(self,
2708                        index: u32,
2709                        name: InternedString) -> Ty<'tcx> {
2710         self.mk_ty(Param(ParamTy { idx: index, name: name }))
2711     }
2712
2713     pub fn mk_self_type(self) -> Ty<'tcx> {
2714         self.mk_ty_param(0, keywords::SelfType.name().as_interned_str())
2715     }
2716
2717     pub fn mk_param_from_def(self, param: &ty::GenericParamDef) -> Kind<'tcx> {
2718         match param.kind {
2719             GenericParamDefKind::Lifetime => {
2720                 self.mk_region(ty::ReEarlyBound(param.to_early_bound_region_data())).into()
2721             }
2722             GenericParamDefKind::Type {..} => self.mk_ty_param(param.index, param.name).into(),
2723         }
2724     }
2725
2726     pub fn mk_opaque(self, def_id: DefId, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
2727         self.mk_ty(Opaque(def_id, substs))
2728     }
2729
2730     pub fn intern_existential_predicates(self, eps: &[ExistentialPredicate<'tcx>])
2731         -> &'tcx List<ExistentialPredicate<'tcx>> {
2732         assert!(!eps.is_empty());
2733         assert!(eps.windows(2).all(|w| w[0].stable_cmp(self, &w[1]) != Ordering::Greater));
2734         self._intern_existential_predicates(eps)
2735     }
2736
2737     pub fn intern_predicates(self, preds: &[Predicate<'tcx>])
2738         -> &'tcx List<Predicate<'tcx>> {
2739         // FIXME consider asking the input slice to be sorted to avoid
2740         // re-interning permutations, in which case that would be asserted
2741         // here.
2742         if preds.len() == 0 {
2743             // The macro-generated method below asserts we don't intern an empty slice.
2744             List::empty()
2745         } else {
2746             self._intern_predicates(preds)
2747         }
2748     }
2749
2750     pub fn intern_type_list(self, ts: &[Ty<'tcx>]) -> &'tcx List<Ty<'tcx>> {
2751         if ts.len() == 0 {
2752             List::empty()
2753         } else {
2754             self._intern_type_list(ts)
2755         }
2756     }
2757
2758     pub fn intern_substs(self, ts: &[Kind<'tcx>]) -> &'tcx List<Kind<'tcx>> {
2759         if ts.len() == 0 {
2760             List::empty()
2761         } else {
2762             self._intern_substs(ts)
2763         }
2764     }
2765
2766     pub fn intern_projs(self, ps: &[ProjectionKind<'tcx>]) -> &'tcx List<ProjectionKind<'tcx>> {
2767         if ps.len() == 0 {
2768             List::empty()
2769         } else {
2770             self._intern_projs(ps)
2771         }
2772     }
2773
2774     pub fn intern_canonical_var_infos(self, ts: &[CanonicalVarInfo]) -> CanonicalVarInfos<'gcx> {
2775         if ts.len() == 0 {
2776             List::empty()
2777         } else {
2778             self.global_tcx()._intern_canonical_var_infos(ts)
2779         }
2780     }
2781
2782     pub fn intern_clauses(self, ts: &[Clause<'tcx>]) -> Clauses<'tcx> {
2783         if ts.len() == 0 {
2784             List::empty()
2785         } else {
2786             self._intern_clauses(ts)
2787         }
2788     }
2789
2790     pub fn intern_goals(self, ts: &[Goal<'tcx>]) -> Goals<'tcx> {
2791         if ts.len() == 0 {
2792             List::empty()
2793         } else {
2794             self._intern_goals(ts)
2795         }
2796     }
2797
2798     pub fn mk_fn_sig<I>(self,
2799                         inputs: I,
2800                         output: I::Item,
2801                         variadic: bool,
2802                         unsafety: hir::Unsafety,
2803                         abi: abi::Abi)
2804         -> <I::Item as InternIteratorElement<Ty<'tcx>, ty::FnSig<'tcx>>>::Output
2805         where I: Iterator,
2806               I::Item: InternIteratorElement<Ty<'tcx>, ty::FnSig<'tcx>>
2807     {
2808         inputs.chain(iter::once(output)).intern_with(|xs| ty::FnSig {
2809             inputs_and_output: self.intern_type_list(xs),
2810             variadic, unsafety, abi
2811         })
2812     }
2813
2814     pub fn mk_existential_predicates<I: InternAs<[ExistentialPredicate<'tcx>],
2815                                      &'tcx List<ExistentialPredicate<'tcx>>>>(self, iter: I)
2816                                      -> I::Output {
2817         iter.intern_with(|xs| self.intern_existential_predicates(xs))
2818     }
2819
2820     pub fn mk_predicates<I: InternAs<[Predicate<'tcx>],
2821                                      &'tcx List<Predicate<'tcx>>>>(self, iter: I)
2822                                      -> I::Output {
2823         iter.intern_with(|xs| self.intern_predicates(xs))
2824     }
2825
2826     pub fn mk_type_list<I: InternAs<[Ty<'tcx>],
2827                         &'tcx List<Ty<'tcx>>>>(self, iter: I) -> I::Output {
2828         iter.intern_with(|xs| self.intern_type_list(xs))
2829     }
2830
2831     pub fn mk_substs<I: InternAs<[Kind<'tcx>],
2832                      &'tcx List<Kind<'tcx>>>>(self, iter: I) -> I::Output {
2833         iter.intern_with(|xs| self.intern_substs(xs))
2834     }
2835
2836     pub fn mk_substs_trait(self,
2837                      self_ty: Ty<'tcx>,
2838                      rest: &[Kind<'tcx>])
2839                     -> &'tcx Substs<'tcx>
2840     {
2841         self.mk_substs(iter::once(self_ty.into()).chain(rest.iter().cloned()))
2842     }
2843
2844     pub fn mk_clauses<I: InternAs<[Clause<'tcx>], Clauses<'tcx>>>(self, iter: I) -> I::Output {
2845         iter.intern_with(|xs| self.intern_clauses(xs))
2846     }
2847
2848     pub fn mk_goals<I: InternAs<[Goal<'tcx>], Goals<'tcx>>>(self, iter: I) -> I::Output {
2849         iter.intern_with(|xs| self.intern_goals(xs))
2850     }
2851
2852     pub fn lint_hir<S: Into<MultiSpan>>(self,
2853                                         lint: &'static Lint,
2854                                         hir_id: HirId,
2855                                         span: S,
2856                                         msg: &str) {
2857         self.struct_span_lint_hir(lint, hir_id, span.into(), msg).emit()
2858     }
2859
2860     pub fn lint_node<S: Into<MultiSpan>>(self,
2861                                          lint: &'static Lint,
2862                                          id: NodeId,
2863                                          span: S,
2864                                          msg: &str) {
2865         self.struct_span_lint_node(lint, id, span.into(), msg).emit()
2866     }
2867
2868     pub fn lint_hir_note<S: Into<MultiSpan>>(self,
2869                                               lint: &'static Lint,
2870                                               hir_id: HirId,
2871                                               span: S,
2872                                               msg: &str,
2873                                               note: &str) {
2874         let mut err = self.struct_span_lint_hir(lint, hir_id, span.into(), msg);
2875         err.note(note);
2876         err.emit()
2877     }
2878
2879     pub fn lint_node_note<S: Into<MultiSpan>>(self,
2880                                               lint: &'static Lint,
2881                                               id: NodeId,
2882                                               span: S,
2883                                               msg: &str,
2884                                               note: &str) {
2885         let mut err = self.struct_span_lint_node(lint, id, span.into(), msg);
2886         err.note(note);
2887         err.emit()
2888     }
2889
2890     pub fn lint_level_at_node(self, lint: &'static Lint, mut id: NodeId)
2891         -> (lint::Level, lint::LintSource)
2892     {
2893         // Right now we insert a `with_ignore` node in the dep graph here to
2894         // ignore the fact that `lint_levels` below depends on the entire crate.
2895         // For now this'll prevent false positives of recompiling too much when
2896         // anything changes.
2897         //
2898         // Once red/green incremental compilation lands we should be able to
2899         // remove this because while the crate changes often the lint level map
2900         // will change rarely.
2901         self.dep_graph.with_ignore(|| {
2902             let sets = self.lint_levels(LOCAL_CRATE);
2903             loop {
2904                 let hir_id = self.hir.definitions().node_to_hir_id(id);
2905                 if let Some(pair) = sets.level_and_source(lint, hir_id, self.sess) {
2906                     return pair
2907                 }
2908                 let next = self.hir.get_parent_node(id);
2909                 if next == id {
2910                     bug!("lint traversal reached the root of the crate");
2911                 }
2912                 id = next;
2913             }
2914         })
2915     }
2916
2917     pub fn struct_span_lint_hir<S: Into<MultiSpan>>(self,
2918                                                     lint: &'static Lint,
2919                                                     hir_id: HirId,
2920                                                     span: S,
2921                                                     msg: &str)
2922         -> DiagnosticBuilder<'tcx>
2923     {
2924         let node_id = self.hir.hir_to_node_id(hir_id);
2925         let (level, src) = self.lint_level_at_node(lint, node_id);
2926         lint::struct_lint_level(self.sess, lint, level, src, Some(span.into()), msg)
2927     }
2928
2929     pub fn struct_span_lint_node<S: Into<MultiSpan>>(self,
2930                                                      lint: &'static Lint,
2931                                                      id: NodeId,
2932                                                      span: S,
2933                                                      msg: &str)
2934         -> DiagnosticBuilder<'tcx>
2935     {
2936         let (level, src) = self.lint_level_at_node(lint, id);
2937         lint::struct_lint_level(self.sess, lint, level, src, Some(span.into()), msg)
2938     }
2939
2940     pub fn struct_lint_node(self, lint: &'static Lint, id: NodeId, msg: &str)
2941         -> DiagnosticBuilder<'tcx>
2942     {
2943         let (level, src) = self.lint_level_at_node(lint, id);
2944         lint::struct_lint_level(self.sess, lint, level, src, None, msg)
2945     }
2946
2947     pub fn in_scope_traits(self, id: HirId) -> Option<Lrc<StableVec<TraitCandidate>>> {
2948         self.in_scope_traits_map(id.owner)
2949             .and_then(|map| map.get(&id.local_id).cloned())
2950     }
2951
2952     pub fn named_region(self, id: HirId) -> Option<resolve_lifetime::Region> {
2953         self.named_region_map(id.owner)
2954             .and_then(|map| map.get(&id.local_id).cloned())
2955     }
2956
2957     pub fn is_late_bound(self, id: HirId) -> bool {
2958         self.is_late_bound_map(id.owner)
2959             .map(|set| set.contains(&id.local_id))
2960             .unwrap_or(false)
2961     }
2962
2963     pub fn object_lifetime_defaults(self, id: HirId)
2964         -> Option<Lrc<Vec<ObjectLifetimeDefault>>>
2965     {
2966         self.object_lifetime_defaults_map(id.owner)
2967             .and_then(|map| map.get(&id.local_id).cloned())
2968     }
2969 }
2970
2971 pub trait InternAs<T: ?Sized, R> {
2972     type Output;
2973     fn intern_with<F>(self, f: F) -> Self::Output
2974         where F: FnOnce(&T) -> R;
2975 }
2976
2977 impl<I, T, R, E> InternAs<[T], R> for I
2978     where E: InternIteratorElement<T, R>,
2979           I: Iterator<Item=E> {
2980     type Output = E::Output;
2981     fn intern_with<F>(self, f: F) -> Self::Output
2982         where F: FnOnce(&[T]) -> R {
2983         E::intern_with(self, f)
2984     }
2985 }
2986
2987 pub trait InternIteratorElement<T, R>: Sized {
2988     type Output;
2989     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output;
2990 }
2991
2992 impl<T, R> InternIteratorElement<T, R> for T {
2993     type Output = R;
2994     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
2995         f(&iter.collect::<SmallVec<[_; 8]>>())
2996     }
2997 }
2998
2999 impl<'a, T, R> InternIteratorElement<T, R> for &'a T
3000     where T: Clone + 'a
3001 {
3002     type Output = R;
3003     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
3004         f(&iter.cloned().collect::<SmallVec<[_; 8]>>())
3005     }
3006 }
3007
3008 impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> {
3009     type Output = Result<R, E>;
3010     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
3011         Ok(f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?))
3012     }
3013 }
3014
3015 pub fn provide(providers: &mut ty::query::Providers<'_>) {
3016     // FIXME(#44234) - almost all of these queries have no sub-queries and
3017     // therefore no actual inputs, they're just reading tables calculated in
3018     // resolve! Does this work? Unsure! That's what the issue is about
3019     providers.in_scope_traits_map = |tcx, id| tcx.gcx.trait_map.get(&id).cloned();
3020     providers.module_exports = |tcx, id| tcx.gcx.export_map.get(&id).cloned();
3021     providers.crate_name = |tcx, id| {
3022         assert_eq!(id, LOCAL_CRATE);
3023         tcx.crate_name
3024     };
3025     providers.get_lib_features = |tcx, id| {
3026         assert_eq!(id, LOCAL_CRATE);
3027         Lrc::new(middle::lib_features::collect(tcx))
3028     };
3029     providers.get_lang_items = |tcx, id| {
3030         assert_eq!(id, LOCAL_CRATE);
3031         Lrc::new(middle::lang_items::collect(tcx))
3032     };
3033     providers.freevars = |tcx, id| tcx.gcx.freevars.get(&id).cloned();
3034     providers.maybe_unused_trait_import = |tcx, id| {
3035         tcx.maybe_unused_trait_imports.contains(&id)
3036     };
3037     providers.maybe_unused_extern_crates = |tcx, cnum| {
3038         assert_eq!(cnum, LOCAL_CRATE);
3039         Lrc::new(tcx.maybe_unused_extern_crates.clone())
3040     };
3041
3042     providers.stability_index = |tcx, cnum| {
3043         assert_eq!(cnum, LOCAL_CRATE);
3044         Lrc::new(stability::Index::new(tcx))
3045     };
3046     providers.lookup_stability = |tcx, id| {
3047         assert_eq!(id.krate, LOCAL_CRATE);
3048         let id = tcx.hir.definitions().def_index_to_hir_id(id.index);
3049         tcx.stability().local_stability(id)
3050     };
3051     providers.lookup_deprecation_entry = |tcx, id| {
3052         assert_eq!(id.krate, LOCAL_CRATE);
3053         let id = tcx.hir.definitions().def_index_to_hir_id(id.index);
3054         tcx.stability().local_deprecation_entry(id)
3055     };
3056     providers.extern_mod_stmt_cnum = |tcx, id| {
3057         let id = tcx.hir.as_local_node_id(id).unwrap();
3058         tcx.cstore.extern_mod_stmt_cnum_untracked(id)
3059     };
3060     providers.all_crate_nums = |tcx, cnum| {
3061         assert_eq!(cnum, LOCAL_CRATE);
3062         Lrc::new(tcx.cstore.crates_untracked())
3063     };
3064     providers.postorder_cnums = |tcx, cnum| {
3065         assert_eq!(cnum, LOCAL_CRATE);
3066         Lrc::new(tcx.cstore.postorder_cnums_untracked())
3067     };
3068     providers.output_filenames = |tcx, cnum| {
3069         assert_eq!(cnum, LOCAL_CRATE);
3070         tcx.output_filenames.clone()
3071     };
3072     providers.features_query = |tcx, cnum| {
3073         assert_eq!(cnum, LOCAL_CRATE);
3074         Lrc::new(tcx.sess.features_untracked().clone())
3075     };
3076     providers.is_panic_runtime = |tcx, cnum| {
3077         assert_eq!(cnum, LOCAL_CRATE);
3078         attr::contains_name(tcx.hir.krate_attrs(), "panic_runtime")
3079     };
3080     providers.is_compiler_builtins = |tcx, cnum| {
3081         assert_eq!(cnum, LOCAL_CRATE);
3082         attr::contains_name(tcx.hir.krate_attrs(), "compiler_builtins")
3083     };
3084 }