split maps into submodules, document

7 files changed, 1521 insertions, 1117 deletions

diff --git a/src/librustc/README.md b/src/librustc/README.md
index a5a184ed48c..99fc94a80f7 100644
--- a/src/librustc/README.md
+++ b/src/librustc/README.md
@@ -224,7 +224,10 @@ pointers for understanding them better.
 - MIR -- the **Mid-level IR** that is created after type-checking for use by borrowck and trans.
   Defined in the `src/librustc/mir/` module, but much of the code that manipulates it is
   found in `src/librustc_mir`.
-- obligation -- something that must be proven by the trait system.
+- obligation -- something that must be proven by the trait system; see `librustc/traits`.
+- local crate -- the crate currently being compiled.
+- query -- perhaps some sub-computation during compilation; see `librustc/maps`.
+- provider -- the function that executes a query; see `librustc/maps`.
 - sess -- the **compiler session**, which stores global data used throughout compilation
 - substs -- the **substitutions** for a given generic type or item
   (e.g., the `i32, u32` in `HashMap<i32, u32>`)
diff --git a/src/librustc/ty/maps/README.md b/src/librustc/ty/maps/README.md
new file mode 100644
index 00000000000..8abc68d431a
--- /dev/null
+++ b/src/librustc/ty/maps/README.md
@@ -0,0 +1,302 @@
+# The Rust Compiler Query System
+
+The Compiler Query System is the key to our new demand-driven
+organization.  The idea is pretty simple. You have various queries
+that compute things about the input -- for example, there is a query
+called `type_of(def_id)` that, given the def-id of some item, will
+compute the type of that item and return it to you.
+
+Query execution is **memoized** -- so the first time you invoke a
+query, it will go do the computation, but the next time, the result is
+returned from a hashtable. Moreover, query execution fits nicely into
+**incremental computation**; the idea is roughly that, when you do a
+query, the result **may** be returned to you by loading stored data
+from disk (but that's a separate topic we won't discuss further here).
+
+The overall vision is that, eventually, the entire compiler
+control-flow will be query driven. There will effectively be one
+top-level query ("compile") that will run compilation on a crate; this
+will in turn demand information about that crate, starting from the
+*end*.  For example:
+
+- This "compile" query might demand to get a list of codegen-units
+  (i.e., modules that need to be compiled by LLVM).
+- But computing the list of codegen-units would invoke some subquery
+  that returns the list of all modules defined in the Rust source.
+- That query in turn would invoke something asking for the HIR.
+- This keeps going further and further back until we wind up doing the
+  actual parsing.
+
+However, that vision is not fully realized. Still, big chunks of the
+compiler (for example, generating MIR) work exactly like this.
+
+### Invoking queries
+
+To invoke a query is simple. The tcx ("type context") offers a method
+for each defined query. So, for example, to invoke the `type_of`
+query, you would just do this:
+
+```rust
+let ty = tcx.type_of(some_def_id);
+```
+
+### Cycles between queries
+
+Currently, cycles during query execution should always result in a
+compilation error. Typically, they arise because of illegal programs
+that contain cyclic references they shouldn't (though sometimes they
+arise because of compiler bugs, in which case we need to factor our
+queries in a more fine-grained fashion to avoid them).
+
+However, it is nonetheless often useful to *recover* from a cycle
+(after reporting an error, say) and try to soldier on, so as to give a
+better user experience. In order to recover from a cycle, you don't
+get to use the nice method-call-style syntax. Instead, you invoke
+using the `try_get` method, which looks roughly like this:
+
+```rust
+use ty::maps::queries;
+...
+match queries::type_of::try_get(tcx, DUMMY_SP, self.did) {
+  Ok(result) => {
+    // no cycle occurred! You can use `result`
+  }
+  Err(err) => {
+    // A cycle occurred! The error value `err` is a `DiagnosticBuilder`,
+    // meaning essentially an "in-progress", not-yet-reported error message.
+    // See below for more details on what to do here.
+  }
+}
+```
+
+So, if you get back an `Err` from `try_get`, then a cycle *did* occur. This means that
+you must ensure that a compiler error message is reported. You can do that in two ways:
+
+The simplest is to invoke `err.emit()`. This will emit the cycle error to the user.
+
+However, often cycles happen because of an illegal program, and you
+know at that point that an error either already has been reported or
+will be reported due to this cycle by some other bit of code. In that
+case, you can invoke `err.cancel()` to not emit any error. It is
+traditional to then invoke:
+
+```
+tcx.sess.delay_span_bug(some_span, "some message")
+```
+
+`delay_span_bug()` is a helper that says: we expect a compilation
+error to have happened or to happen in the future; so, if compilation
+ultimately succeeds, make an ICE with the message `"some
+message"`. This is basically just a precaution in case you are wrong.
+
+### How the compiler executes a query
+
+So you may be wondering what happens when you invoke a query
+method. The answer is that, for each query, the compiler maintains a
+cache -- if your query has already been executed, then, the answer is
+simple: we clone the return value out of the cache and return it
+(therefore, you should try to ensure that the return types of queries
+are cheaply cloneable; insert a `Rc` if necessary).
+
+#### Providers
+
+If, however, the query is *not* in the cache, then the compiler will
+try to find a suitable **provider**. A provider is a function that has
+been defined and linked into the compiler somewhere that contains the
+code to compute the result of the query.
+
+**Providers are defined per-crate.** The compiler maintains,
+internally, a table of providers for every crate, at least
+conceptually. Right now, there are really two sets: the providers for
+queries about the **local crate** (that is, the one being compiled)
+and providers for queries about **external crates** (that is,
+dependencies of the local crate). Note that what determines the crate
+that a query is targeting is not the *kind* of query, but the *key*.
+For example, when you invoke `tcx.type_of(def_id)`, that could be a
+local query or an external query, depending on what crate the `def_id`
+is referring to (see the `self::keys::Key` trait for more information
+on how that works).
+
+Providers always have the same signature:
+
+```rust
+fn provider<'cx, 'tcx>(tcx: TyCtxt<'cx, 'tcx, 'tcx>,
+                       key: QUERY_KEY)
+                       -> QUERY_RESULT
+{
+    ...
+}
+```
+
+Providers take two arguments: the `tcx` and the query key. Note also
+that they take the *global* tcx (i.e., they use the `'tcx` lifetime
+twice), rather than taking a tcx with some active inference context.
+They return the result of the query.
+
+####  How providers are setup
+
+When the tcx is created, it is given the providers by its creator using
+the `Providers` struct. This struct is generate by the macros here, but it
+is basically a big list of function pointers:
+
+```rust
+struct Providers {
+    type_of: for<'cx, 'tcx> fn(TyCtxt<'cx, 'tcx, 'tcx>, DefId) -> Ty<'tcx>,
+    ...
+}
+```
+
+At present, we have one copy of the struct for local crates, and one
+for external crates, though the plan is that we may eventually have
+one per crate.
+
+These `Provider` structs are ultimately created and populated by
+`librustc_driver`, but it does this by distributing the work
+throughout the other `rustc_*` crates. This is done by invoking
+various `provide` functions. These functions tend to look something
+like this:
+
+```rust
+pub fn provide(providers: &mut Providers) {
+    *providers = Providers {
+        type_of,
+        ..*providers
+    };
+}
+```
+
+That is, they take an `&mut Providers` and mutate it in place. Usually
+we use the formulation above just because it looks nice, but you could
+as well do `providers.type_of = type_of`, which would be equivalent.
+(Here, `type_of` would be a top-level function, defined as we saw
+before.) So, if we wanted to have add a provider for some other query,
+let's call it `fubar`, into the crate above, we might modify the `provide()`
+function like so:
+
+```rust
+pub fn provide(providers: &mut Providers) {
+    *providers = Providers {
+        type_of,
+        fubar,
+        ..*providers
+    };
+}
+
+fn fubar<'cx, 'tcx>(tcx: TyCtxt<'cx, 'tcx>, key: DefId) -> Fubar<'tcx> { .. }
+```
+
+NB. Most of the `rustc_*` crate only provide **local
+providers**. Almost all **extern providers** wind up going through the
+`rustc_metadata` crate, which loads the information from the crate
+metadata.  But in some cases there are crates that provide queries for
+*both* local and external crates, in which case they define both a
+`provide` and a `provide_extern` function that `rustc_driver` can
+invoke.
+
+### Adding a new kind of query
+
+So suppose you want to add a new kind of query, how do you do so?
+Well, defining a query takes place in two steps:
+
+1. first, you have to specify the query name and arguments; and then,
+2. you have to supply query providers where needed.
+
+The specify the query name and arguments, you simply add an entry
+to the big macro invocation in `mod.rs`. This will probably have changed
+by the time you read this README, but at present it looks something
+like:
+
+```
+define_maps! { <'tcx>
+    /// Records the type of every item.
+    [] fn type_of: TypeOfItem(DefId) -> Ty<'tcx>,
+
+    ...
+}
+```
+
+Each line of the macro defines one query. The name is broken up like this:
+
+```
+[] fn type_of: TypeOfItem(DefId) -> Ty<'tcx>,
+^^    ^^^^^^^  ^^^^^^^^^^ ^^^^^     ^^^^^^^^
+|     |        |          |         |
+|     |        |          |         result type of query
+|     |        |          query key type
+|     |        dep-node constructor
+|     name of query
+query flags
+```
+
+Let's go over them one by one:
+
+- **Query flags:** these are largely unused right now, but the intention
+  is that we'll be able to customize various aspects of how the query is
+  processed.
+- **Name of query:** the name of the query method
+  (`tcx.type_of(..)`). Also used as the name of a struct
+  (`ty::maps::queries::type_of`) that will be generated to represent
+  this query.
+- **Dep-node constructor:** indicates the constructor function that
+  connects this query to incremental compilation. Typically, this is a
+  `DepNode` variant, which can be added by modifying the
+  `define_dep_nodes!` macro invocation in
+  `librustc/dep_graph/dep_node.rs`.
+  - However, sometimes we use a custom function, in which case the
+    name will be in snake case and the function will be defined at the
+    bottom of the file. This is typically used when the query key is
+    not a def-id, or just not the type that the dep-node expects.
+- **Query key type:** the type of the argument to this query.
+  This type must implement the `ty::maps::keys::Key` trait, which
+  defines (for example) how to map it to a crate, and so forth.
+- **Result type of query:** the type produced by this query. This type
+  should (a) not use `RefCell` or other interior mutability and (b) be
+  cheaply cloneable. Interning or using `Rc` or `Arc` is recommended for
+  non-trivial data types.
+  - The one exception to those rules is the `ty::steal::Steal` type,
+    which is used to cheaply modify MIR in place. See the definition
+    of `Steal` for more details. New uses of `Steal` should **not** be
+    added without alerting `@rust-lang/compiler`.
+
+So, to add a query:
+
+- Add an entry to `define_maps!` using the format above.
+- Possibly add a corresponding entry to the dep-node macro.
+- Link the provider by modifying the appropriate `provide` method;
+  or add a new one if needed and ensure that `rustc_driver` is invoking it.
+
+#### Query structs and descriptions
+
+For each kind, the `define_maps` macro will generate a "query struct"
+named after the query. This struct is a kind of a place-holder
+describing the query. Each such struct implements the
+`self::config::QueryConfig` trait, which has associated types for the
+key/value of that particular query. Basically the code generated looks something
+like this:
+
+```rust
+// Dummy struct representing a particular kind of query:
+pub struct type_of<'tcx> { phantom: PhantomData<&'tcx ()> }
+
+impl<'tcx> QueryConfig for type_of<'tcx> {
+  type Key = DefId;
+  type Value = Ty<'tcx>;
+}
+```
+
+There is an additional trait that you may wish to implement called
+`self::config::QueryDescription`. This trait is used during cycle
+errors to give a "human readable" name for the query, so that we can
+summarize what was happening when the cycle occurred. Implementing
+this trait is optional if the query key is `DefId`, but if you *don't*
+implement it, you get a pretty generic error ("processing `foo`...").
+You can put new impls into the `config` module. They look something like this:
+
+```rust
+impl<'tcx> QueryDescription for queries::type_of<'tcx> {
+    fn describe(tcx: TyCtxt, key: DefId) -> String {
+        format!("computing the type of `{}`", tcx.item_path_str(key))
+    }
+}
+```
+
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
new file mode 100644
index 00000000000..461b81a5c05
--- /dev/null
+++ b/src/librustc/ty/maps/config.rs
@@ -0,0 +1,492 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use hir::def_id::{CrateNum, DefId, DefIndex};
+use ty::{self, Ty, TyCtxt};
+use ty::maps::queries;
+use ty::subst::Substs;
+
+use std::hash::Hash;
+use syntax_pos::symbol::InternedString;
+
+/// Query configuration and description traits.
+
+pub trait QueryConfig {
+    type Key: Eq + Hash + Clone;
+    type Value;
+}
+
+pub(super) trait QueryDescription: QueryConfig {
+    fn describe(tcx: TyCtxt, key: Self::Key) -> String;
+}
+
+impl<M: QueryConfig<Key=DefId>> QueryDescription for M {
+    default fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("processing `{}`", tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_copy_raw<'tcx> {
+    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
+        format!("computing whether `{}` is `Copy`", env.value)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_sized_raw<'tcx> {
+    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
+        format!("computing whether `{}` is `Sized`", env.value)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_freeze_raw<'tcx> {
+    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
+        format!("computing whether `{}` is freeze", env.value)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::needs_drop_raw<'tcx> {
+    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
+        format!("computing whether `{}` needs drop", env.value)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::layout_raw<'tcx> {
+    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
+        format!("computing layout of `{}`", env.value)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::super_predicates_of<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("computing the supertraits of `{}`",
+                tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::type_param_predicates<'tcx> {
+    fn describe(tcx: TyCtxt, (_, def_id): (DefId, DefId)) -> String {
+        let id = tcx.hir.as_local_node_id(def_id).unwrap();
+        format!("computing the bounds for type parameter `{}`",
+                tcx.hir.ty_param_name(id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::coherent_trait<'tcx> {
+    fn describe(tcx: TyCtxt, (_, def_id): (CrateNum, DefId)) -> String {
+        format!("coherence checking all impls of trait `{}`",
+                tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::crate_inherent_impls<'tcx> {
+    fn describe(_: TyCtxt, k: CrateNum) -> String {
+        format!("all inherent impls defined in crate `{:?}`", k)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::crate_inherent_impls_overlap_check<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        format!("check for overlap between inherent impls defined in this crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::crate_variances<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("computing the variances for items in this crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::mir_shims<'tcx> {
+    fn describe(tcx: TyCtxt, def: ty::InstanceDef<'tcx>) -> String {
+        format!("generating MIR shim for `{}`",
+                tcx.item_path_str(def.def_id()))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::privacy_access_levels<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        format!("privacy access levels")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::typeck_item_bodies<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        format!("type-checking all item bodies")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::reachable_set<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        format!("reachability")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::const_eval<'tcx> {
+    fn describe(tcx: TyCtxt, key: ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>) -> String {
+        format!("const-evaluating `{}`", tcx.item_path_str(key.value.0))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::mir_keys<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        format!("getting a list of all mir_keys")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::symbol_name<'tcx> {
+    fn describe(_tcx: TyCtxt, instance: ty::Instance<'tcx>) -> String {
+        format!("computing the symbol for `{}`", instance)
+    }
+}
+
+impl<'tcx> QueryDescription for queries::describe_def<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("describe_def")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::def_span<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("def_span")
+    }
+}
+
+
+impl<'tcx> QueryDescription for queries::lookup_stability<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("stability")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::lookup_deprecation_entry<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("deprecation")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::item_attrs<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("item_attrs")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_exported_symbol<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("is_exported_symbol")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::fn_arg_names<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("fn_arg_names")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::impl_parent<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("impl_parent")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::trait_of_item<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        bug!("trait_of_item")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::item_body_nested_bodies<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("nested item bodies of `{}`", tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::const_is_rvalue_promotable_to_static<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("const checking if rvalue is promotable to static `{}`",
+            tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_mir_available<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("checking if item is mir available: `{}`",
+            tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::trait_impls_of<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("trait impls of `{}`", tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_object_safe<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("determine object safety of trait `{}`", tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_const_fn<'tcx> {
+    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
+        format!("checking if item is const fn: `{}`", tcx.item_path_str(def_id))
+    }
+}
+
+impl<'tcx> QueryDescription for queries::dylib_dependency_formats<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        "dylib dependency formats of crate".to_string()
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_panic_runtime<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        "checking if the crate is_panic_runtime".to_string()
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_compiler_builtins<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        "checking if the crate is_compiler_builtins".to_string()
+    }
+}
+
+impl<'tcx> QueryDescription for queries::has_global_allocator<'tcx> {
+    fn describe(_: TyCtxt, _: CrateNum) -> String {
+        "checking if the crate has_global_allocator".to_string()
+    }
+}
+
+impl<'tcx> QueryDescription for queries::extern_crate<'tcx> {
+    fn describe(_: TyCtxt, _: DefId) -> String {
+        "getting crate's ExternCrateData".to_string()
+    }
+}
+
+impl<'tcx> QueryDescription for queries::lint_levels<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("computing the lint levels for items in this crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::specializes<'tcx> {
+    fn describe(_tcx: TyCtxt, _: (DefId, DefId)) -> String {
+        format!("computing whether impls specialize one another")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::in_scope_traits_map<'tcx> {
+    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
+        format!("traits in scope at a block")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_no_builtins<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("test whether a crate has #![no_builtins]")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::panic_strategy<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("query a crate's configured panic strategy")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_profiler_runtime<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("query a crate is #![profiler_runtime]")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_sanitizer_runtime<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("query a crate is #![sanitizer_runtime]")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::exported_symbol_ids<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the exported symbols of a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::native_libraries<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the native libraries of a linked crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::plugin_registrar_fn<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the plugin registrar for a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::derive_registrar_fn<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the derive registrar for a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::crate_disambiguator<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the disambiguator a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::crate_hash<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the hash a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::original_crate_name<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up the original name a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::implementations_of_trait<'tcx> {
+    fn describe(_tcx: TyCtxt, _: (CrateNum, DefId)) -> String {
+        format!("looking up implementations of a trait in a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::all_trait_implementations<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up all (?) trait implementations")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::link_args<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up link arguments for a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::named_region_map<'tcx> {
+    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
+        format!("looking up a named region")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::is_late_bound_map<'tcx> {
+    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
+        format!("testing if a region is late boudn")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::object_lifetime_defaults_map<'tcx> {
+    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
+        format!("looking up lifetime defaults for a region")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::dep_kind<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("fetching what a dependency looks like")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::crate_name<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("fetching what a crate is named")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::get_lang_items<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("calculating the lang items map")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::defined_lang_items<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("calculating the lang items defined in a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::missing_lang_items<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("calculating the missing lang items in a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::visible_parent_map<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("calculating the visible parent map")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::missing_extern_crate_item<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("seeing if we're missing an `extern crate` item for this crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::used_crate_source<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking at the source for a crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::postorder_cnums<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("generating a postorder list of CrateNums")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::maybe_unused_extern_crates<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("looking up all possibly unused extern crates")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::stability_index<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("calculating the stability index for the local crate")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::all_crate_nums<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("fetching all foreign CrateNum instances")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::exported_symbols<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("exported_symbols")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::collect_and_partition_translation_items<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("collect_and_partition_translation_items")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::codegen_unit<'tcx> {
+    fn describe(_tcx: TyCtxt, _: InternedString) -> String {
+        format!("codegen_unit")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::compile_codegen_unit<'tcx> {
+    fn describe(_tcx: TyCtxt, _: InternedString) -> String {
+        format!("compile_codegen_unit")
+    }
+}
+
+impl<'tcx> QueryDescription for queries::output_filenames<'tcx> {
+    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
+        format!("output_filenames")
+    }
+}
diff --git a/src/librustc/ty/maps/keys.rs b/src/librustc/ty/maps/keys.rs
new file mode 100644
index 00000000000..e37cf669797
--- /dev/null
+++ b/src/librustc/ty/maps/keys.rs
@@ -0,0 +1,162 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Defines the set of legal keys that can be used in queries.
+
+use hir::def_id::{CrateNum, DefId, LOCAL_CRATE, DefIndex};
+use mir::transform::{MirSuite, MirPassIndex};
+use ty::{self, Ty, TyCtxt};
+use ty::subst::Substs;
+use ty::fast_reject::SimplifiedType;
+
+use std::fmt::Debug;
+use std::hash::Hash;
+use syntax_pos::{Span, DUMMY_SP};
+use syntax_pos::symbol::InternedString;
+
+/// The `Key` trait controls what types can legally be used as the key
+/// for a query.
+pub trait Key: Clone + Hash + Eq + Debug {
+    /// Given an instance of this key, what crate is it referring to?
+    /// This is used to find the provider.
+    fn map_crate(&self) -> CrateNum;
+
+    /// In the event that a cycle occurs, if no explicit span has been
+    /// given for a query with key `self`, what span should we use?
+    fn default_span(&self, tcx: TyCtxt) -> Span;
+}
+
+impl<'tcx> Key for ty::InstanceDef<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        tcx.def_span(self.def_id())
+    }
+}
+
+impl<'tcx> Key for ty::Instance<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        tcx.def_span(self.def_id())
+    }
+}
+
+impl Key for CrateNum {
+    fn map_crate(&self) -> CrateNum {
+        *self
+    }
+    fn default_span(&self, _: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl Key for DefIndex {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _tcx: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl Key for DefId {
+    fn map_crate(&self) -> CrateNum {
+        self.krate
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        tcx.def_span(*self)
+    }
+}
+
+impl Key for (DefId, DefId) {
+    fn map_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (CrateNum, DefId) {
+    fn map_crate(&self) -> CrateNum {
+        self.0
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (DefId, SimplifiedType) {
+    fn map_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key for (DefId, &'tcx Substs<'tcx>) {
+    fn map_crate(&self) -> CrateNum {
+        self.0.krate
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
+impl Key for (MirSuite, DefId) {
+    fn map_crate(&self) -> CrateNum {
+        self.1.map_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.1.default_span(tcx)
+    }
+}
+
+impl Key for (MirSuite, MirPassIndex, DefId) {
+    fn map_crate(&self) -> CrateNum {
+        self.2.map_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.2.default_span(tcx)
+    }
+}
+
+impl<'tcx> Key for Ty<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
+
+impl<'tcx, T: Key> Key for ty::ParamEnvAnd<'tcx, T> {
+    fn map_crate(&self) -> CrateNum {
+        self.value.map_crate()
+    }
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        self.value.default_span(tcx)
+    }
+}
+
+impl Key for InternedString {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _tcx: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index c0045483ced..c08ad68eddd 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -8,9 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use dep_graph::{DepConstructor, DepNode, DepNodeIndex};
-use errors::{Diagnostic, DiagnosticBuilder};
-use hir::def_id::{CrateNum, DefId, LOCAL_CRATE, DefIndex};
+use dep_graph::{DepConstructor, DepNode};
+use errors::DiagnosticBuilder;
+use hir::def_id::{CrateNum, DefId, DefIndex};
 use hir::def::{Def, Export};
 use hir::{self, TraitCandidate, ItemLocalId};
 use hir::svh::Svh;
@@ -28,16 +28,13 @@ use middle::lang_items::{LanguageItems, LangItem};
 use middle::exported_symbols::SymbolExportLevel;
 use middle::trans::{CodegenUnit, Stats};
 use mir;
-use mir::transform::{MirSuite, MirPassIndex};
 use session::CompileResult;
 use session::config::OutputFilenames;
 use traits::specialization_graph;
 use ty::{self, CrateInherentImpls, Ty, TyCtxt};
 use ty::layout::{Layout, LayoutError};
-use ty::item_path;
 use ty::steal::Steal;
 use ty::subst::Substs;
-use ty::fast_reject::SimplifiedType;
 use util::nodemap::{DefIdSet, DefIdMap};
 use util::common::{profq_msg, ProfileQueriesMsg};
 
@@ -45,12 +42,8 @@ use rustc_data_structures::indexed_set::IdxSetBuf;
 use rustc_back::PanicStrategy;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
-use std::cell::{RefCell, RefMut, Cell};
+use std::cell::{RefCell, Cell};
 
-use std::fmt::Debug;
-use std::hash::Hash;
-use std::marker::PhantomData;
-use std::mem;
 use std::ops::Deref;
 use std::rc::Rc;
 use std::sync::Arc;
@@ -60,1114 +53,19 @@ use syntax::attr;
 use syntax::ast;
 use syntax::symbol::Symbol;
 
-pub trait Key: Clone + Hash + Eq + Debug {
-    fn map_crate(&self) -> CrateNum;
-    fn default_span(&self, tcx: TyCtxt) -> Span;
-}
-
-impl<'tcx> Key for ty::InstanceDef<'tcx> {
-    fn map_crate(&self) -> CrateNum {
-        LOCAL_CRATE
-    }
-
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        tcx.def_span(self.def_id())
-    }
-}
-
-impl<'tcx> Key for ty::Instance<'tcx> {
-    fn map_crate(&self) -> CrateNum {
-        LOCAL_CRATE
-    }
-
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        tcx.def_span(self.def_id())
-    }
-}
-
-impl Key for CrateNum {
-    fn map_crate(&self) -> CrateNum {
-        *self
-    }
-    fn default_span(&self, _: TyCtxt) -> Span {
-        DUMMY_SP
-    }
-}
-
-impl Key for DefIndex {
-    fn map_crate(&self) -> CrateNum {
-        LOCAL_CRATE
-    }
-    fn default_span(&self, _tcx: TyCtxt) -> Span {
-        DUMMY_SP
-    }
-}
-
-impl Key for DefId {
-    fn map_crate(&self) -> CrateNum {
-        self.krate
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        tcx.def_span(*self)
-    }
-}
-
-impl Key for (DefId, DefId) {
-    fn map_crate(&self) -> CrateNum {
-        self.0.krate
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.1.default_span(tcx)
-    }
-}
-
-impl Key for (CrateNum, DefId) {
-    fn map_crate(&self) -> CrateNum {
-        self.0
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.1.default_span(tcx)
-    }
-}
-
-impl Key for (DefId, SimplifiedType) {
-    fn map_crate(&self) -> CrateNum {
-        self.0.krate
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.0.default_span(tcx)
-    }
-}
-
-impl<'tcx> Key for (DefId, &'tcx Substs<'tcx>) {
-    fn map_crate(&self) -> CrateNum {
-        self.0.krate
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.0.default_span(tcx)
-    }
-}
-
-impl Key for (MirSuite, DefId) {
-    fn map_crate(&self) -> CrateNum {
-        self.1.map_crate()
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.1.default_span(tcx)
-    }
-}
-
-impl Key for (MirSuite, MirPassIndex, DefId) {
-    fn map_crate(&self) -> CrateNum {
-        self.2.map_crate()
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.2.default_span(tcx)
-    }
-}
-
-impl<'tcx> Key for Ty<'tcx> {
-    fn map_crate(&self) -> CrateNum {
-        LOCAL_CRATE
-    }
-    fn default_span(&self, _: TyCtxt) -> Span {
-        DUMMY_SP
-    }
-}
-
-impl<'tcx, T: Key> Key for ty::ParamEnvAnd<'tcx, T> {
-    fn map_crate(&self) -> CrateNum {
-        self.value.map_crate()
-    }
-    fn default_span(&self, tcx: TyCtxt) -> Span {
-        self.value.default_span(tcx)
-    }
-}
-
-impl Key for InternedString {
-    fn map_crate(&self) -> CrateNum {
-        LOCAL_CRATE
-    }
-    fn default_span(&self, _tcx: TyCtxt) -> Span {
-        DUMMY_SP
-    }
-}
-
-trait Value<'tcx>: Sized {
-    fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self;
-}
-
-impl<'tcx, T> Value<'tcx> for T {
-    default fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> T {
-        tcx.sess.abort_if_errors();
-        bug!("Value::from_cycle_error called without errors");
-    }
-}
-
-impl<'tcx, T: Default> Value<'tcx> for T {
-    default fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> T {
-        T::default()
-    }
-}
-
-impl<'tcx> Value<'tcx> for Ty<'tcx> {
-    fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> {
-        tcx.types.err
-    }
-}
-
-impl<'tcx> Value<'tcx> for ty::DtorckConstraint<'tcx> {
-    fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
-        Self::empty()
-    }
-}
-
-impl<'tcx> Value<'tcx> for ty::SymbolName {
-    fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
-        ty::SymbolName { name: Symbol::intern("<error>").as_str() }
-    }
-}
-
-struct QueryMap<D: QueryDescription> {
-    phantom: PhantomData<D>,
-    map: FxHashMap<D::Key, QueryValue<D::Value>>,
-}
-
-struct QueryValue<T> {
-    value: T,
-    index: DepNodeIndex,
-    diagnostics: Option<Box<QueryDiagnostics>>,
-}
-
-struct QueryDiagnostics {
-    diagnostics: Vec<Diagnostic>,
-    emitted_diagnostics: Cell<bool>,
-}
-
-impl<M: QueryDescription> QueryMap<M> {
-    fn new() -> QueryMap<M> {
-        QueryMap {
-            phantom: PhantomData,
-            map: FxHashMap(),
-        }
-    }
-}
-
-struct CycleError<'a, 'tcx: 'a> {
-    span: Span,
-    cycle: RefMut<'a, [(Span, Query<'tcx>)]>,
-}
-
-impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
-    fn report_cycle(self, CycleError { span, cycle }: CycleError)
-        -> DiagnosticBuilder<'a>
-    {
-        // Subtle: release the refcell lock before invoking `describe()`
-        // below by dropping `cycle`.
-        let stack = cycle.to_vec();
-        mem::drop(cycle);
-
-        assert!(!stack.is_empty());
-
-        // Disable naming impls with types in this path, since that
-        // sometimes cycles itself, leading to extra cycle errors.
-        // (And cycle errors around impls tend to occur during the
-        // collect/coherence phases anyhow.)
-        item_path::with_forced_impl_filename_line(|| {
-            let mut err =
-                struct_span_err!(self.sess, span, E0391,
-                                 "unsupported cyclic reference between types/traits detected");
-            err.span_label(span, "cyclic reference");
-
-            err.span_note(stack[0].0, &format!("the cycle begins when {}...",
-                                               stack[0].1.describe(self)));
-
-            for &(span, ref query) in &stack[1..] {
-                err.span_note(span, &format!("...which then requires {}...",
-                                             query.describe(self)));
-            }
-
-            err.note(&format!("...which then again requires {}, completing the cycle.",
-                              stack[0].1.describe(self)));
-
-            return err
-        })
-    }
-
-    fn cycle_check<F, R>(self, span: Span, query: Query<'gcx>, compute: F)
-                         -> Result<R, CycleError<'a, 'gcx>>
-        where F: FnOnce() -> R
-    {
-        {
-            let mut stack = self.maps.query_stack.borrow_mut();
-            if let Some((i, _)) = stack.iter().enumerate().rev()
-                                       .find(|&(_, &(_, ref q))| *q == query) {
-                return Err(CycleError {
-                    span,
-                    cycle: RefMut::map(stack, |stack| &mut stack[i..])
-                });
-            }
-            stack.push((span, query));
-        }
-
-        let result = compute();
-
-        self.maps.query_stack.borrow_mut().pop();
-
-        Ok(result)
-    }
-}
-
-pub trait QueryConfig {
-    type Key: Eq + Hash + Clone;
-    type Value;
-}
-
-trait QueryDescription: QueryConfig {
-    fn describe(tcx: TyCtxt, key: Self::Key) -> String;
-}
-
-impl<M: QueryConfig<Key=DefId>> QueryDescription for M {
-    default fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("processing `{}`", tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_copy_raw<'tcx> {
-    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
-        format!("computing whether `{}` is `Copy`", env.value)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_sized_raw<'tcx> {
-    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
-        format!("computing whether `{}` is `Sized`", env.value)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_freeze_raw<'tcx> {
-    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
-        format!("computing whether `{}` is freeze", env.value)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::needs_drop_raw<'tcx> {
-    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
-        format!("computing whether `{}` needs drop", env.value)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::layout_raw<'tcx> {
-    fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
-        format!("computing layout of `{}`", env.value)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::super_predicates_of<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("computing the supertraits of `{}`",
-                tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::type_param_predicates<'tcx> {
-    fn describe(tcx: TyCtxt, (_, def_id): (DefId, DefId)) -> String {
-        let id = tcx.hir.as_local_node_id(def_id).unwrap();
-        format!("computing the bounds for type parameter `{}`",
-                tcx.hir.ty_param_name(id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::coherent_trait<'tcx> {
-    fn describe(tcx: TyCtxt, (_, def_id): (CrateNum, DefId)) -> String {
-        format!("coherence checking all impls of trait `{}`",
-                tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::crate_inherent_impls<'tcx> {
-    fn describe(_: TyCtxt, k: CrateNum) -> String {
-        format!("all inherent impls defined in crate `{:?}`", k)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::crate_inherent_impls_overlap_check<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        format!("check for overlap between inherent impls defined in this crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::crate_variances<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("computing the variances for items in this crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::mir_shims<'tcx> {
-    fn describe(tcx: TyCtxt, def: ty::InstanceDef<'tcx>) -> String {
-        format!("generating MIR shim for `{}`",
-                tcx.item_path_str(def.def_id()))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::privacy_access_levels<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        format!("privacy access levels")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::typeck_item_bodies<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        format!("type-checking all item bodies")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::reachable_set<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        format!("reachability")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::const_eval<'tcx> {
-    fn describe(tcx: TyCtxt, key: ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>) -> String {
-        format!("const-evaluating `{}`", tcx.item_path_str(key.value.0))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::mir_keys<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        format!("getting a list of all mir_keys")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::symbol_name<'tcx> {
-    fn describe(_tcx: TyCtxt, instance: ty::Instance<'tcx>) -> String {
-        format!("computing the symbol for `{}`", instance)
-    }
-}
-
-impl<'tcx> QueryDescription for queries::describe_def<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("describe_def")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::def_span<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("def_span")
-    }
-}
-
-
-impl<'tcx> QueryDescription for queries::lookup_stability<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("stability")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::lookup_deprecation_entry<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("deprecation")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::item_attrs<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("item_attrs")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_exported_symbol<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("is_exported_symbol")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::fn_arg_names<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("fn_arg_names")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::impl_parent<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("impl_parent")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::trait_of_item<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("trait_of_item")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::item_body_nested_bodies<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("nested item bodies of `{}`", tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::const_is_rvalue_promotable_to_static<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("const checking if rvalue is promotable to static `{}`",
-            tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_mir_available<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("checking if item is mir available: `{}`",
-            tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::trait_impls_of<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("trait impls of `{}`", tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_object_safe<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("determine object safety of trait `{}`", tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_const_fn<'tcx> {
-    fn describe(tcx: TyCtxt, def_id: DefId) -> String {
-        format!("checking if item is const fn: `{}`", tcx.item_path_str(def_id))
-    }
-}
-
-impl<'tcx> QueryDescription for queries::dylib_dependency_formats<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        "dylib dependency formats of crate".to_string()
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_panic_runtime<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        "checking if the crate is_panic_runtime".to_string()
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_compiler_builtins<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        "checking if the crate is_compiler_builtins".to_string()
-    }
-}
-
-impl<'tcx> QueryDescription for queries::has_global_allocator<'tcx> {
-    fn describe(_: TyCtxt, _: CrateNum) -> String {
-        "checking if the crate has_global_allocator".to_string()
-    }
-}
-
-impl<'tcx> QueryDescription for queries::extern_crate<'tcx> {
-    fn describe(_: TyCtxt, _: DefId) -> String {
-        "getting crate's ExternCrateData".to_string()
-    }
-}
-
-impl<'tcx> QueryDescription for queries::lint_levels<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("computing the lint levels for items in this crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::specializes<'tcx> {
-    fn describe(_tcx: TyCtxt, _: (DefId, DefId)) -> String {
-        format!("computing whether impls specialize one another")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::in_scope_traits_map<'tcx> {
-    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
-        format!("traits in scope at a block")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_no_builtins<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("test whether a crate has #![no_builtins]")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::panic_strategy<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("query a crate's configured panic strategy")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_profiler_runtime<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("query a crate is #![profiler_runtime]")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_sanitizer_runtime<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("query a crate is #![sanitizer_runtime]")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::exported_symbol_ids<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the exported symbols of a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::native_libraries<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the native libraries of a linked crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::plugin_registrar_fn<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the plugin registrar for a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::derive_registrar_fn<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the derive registrar for a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::crate_disambiguator<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the disambiguator a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::crate_hash<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the hash a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::original_crate_name<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up the original name a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::implementations_of_trait<'tcx> {
-    fn describe(_tcx: TyCtxt, _: (CrateNum, DefId)) -> String {
-        format!("looking up implementations of a trait in a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::all_trait_implementations<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up all (?) trait implementations")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::link_args<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up link arguments for a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::named_region_map<'tcx> {
-    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
-        format!("looking up a named region")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::is_late_bound_map<'tcx> {
-    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
-        format!("testing if a region is late boudn")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::object_lifetime_defaults_map<'tcx> {
-    fn describe(_tcx: TyCtxt, _: DefIndex) -> String {
-        format!("looking up lifetime defaults for a region")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::dep_kind<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("fetching what a dependency looks like")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::crate_name<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("fetching what a crate is named")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::get_lang_items<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("calculating the lang items map")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::defined_lang_items<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("calculating the lang items defined in a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::missing_lang_items<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("calculating the missing lang items in a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::visible_parent_map<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("calculating the visible parent map")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::missing_extern_crate_item<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("seeing if we're missing an `extern crate` item for this crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::used_crate_source<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking at the source for a crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::postorder_cnums<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("generating a postorder list of CrateNums")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::maybe_unused_extern_crates<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("looking up all possibly unused extern crates")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::stability_index<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("calculating the stability index for the local crate")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::all_crate_nums<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("fetching all foreign CrateNum instances")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::exported_symbols<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("exported_symbols")
-    }
-}
-
-impl<'tcx> QueryDescription for queries::collect_and_partition_translation_items<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("collect_and_partition_translation_items")
-    }
-}
+#[macro_use]
+mod plumbing;
+use self::plumbing::*;
 
-impl<'tcx> QueryDescription for queries::codegen_unit<'tcx> {
-    fn describe(_tcx: TyCtxt, _: InternedString) -> String {
-        format!("codegen_unit")
-    }
-}
+mod keys;
+pub use self::keys::Key;
 
-impl<'tcx> QueryDescription for queries::compile_codegen_unit<'tcx> {
-    fn describe(_tcx: TyCtxt, _: InternedString) -> String {
-        format!("compile_codegen_unit")
-    }
-}
+mod values;
+use self::values::Value;
 
-impl<'tcx> QueryDescription for queries::output_filenames<'tcx> {
-    fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
-        format!("output_filenames")
-    }
-}
-
-// If enabled, send a message to the profile-queries thread
-macro_rules! profq_msg {
-    ($tcx:expr, $msg:expr) => {
-        if cfg!(debug_assertions) {
-            if  $tcx.sess.profile_queries() {
-                profq_msg($msg)
-            }
-        }
-    }
-}
-
-// If enabled, format a key using its debug string, which can be
-// expensive to compute (in terms of time).
-macro_rules! profq_key {
-    ($tcx:expr, $key:expr) => {
-        if cfg!(debug_assertions) {
-            if $tcx.sess.profile_queries_and_keys() {
-                Some(format!("{:?}", $key))
-            } else { None }
-        } else { None }
-    }
-}
-
-macro_rules! define_maps {
-    (<$tcx:tt>
-     $($(#[$attr:meta])*
-       [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*) => {
-        define_map_struct! {
-            tcx: $tcx,
-            input: ($(([$($modifiers)*] [$($attr)*] [$name]))*)
-        }
-
-        impl<$tcx> Maps<$tcx> {
-            pub fn new(providers: IndexVec<CrateNum, Providers<$tcx>>)
-                       -> Self {
-                Maps {
-                    providers,
-                    query_stack: RefCell::new(vec![]),
-                    $($name: RefCell::new(QueryMap::new())),*
-                }
-            }
-        }
-
-        #[allow(bad_style)]
-        #[derive(Copy, Clone, Debug, PartialEq, Eq)]
-        pub enum Query<$tcx> {
-            $($(#[$attr])* $name($K)),*
-        }
-
-        #[allow(bad_style)]
-        #[derive(Clone, Debug, PartialEq, Eq)]
-        pub enum QueryMsg {
-            $($name(Option<String>)),*
-        }
-
-        impl<$tcx> Query<$tcx> {
-            pub fn describe(&self, tcx: TyCtxt) -> String {
-                let (r, name) = match *self {
-                    $(Query::$name(key) => {
-                        (queries::$name::describe(tcx, key), stringify!($name))
-                    })*
-                };
-                if tcx.sess.verbose() {
-                    format!("{} [{}]", r, name)
-                } else {
-                    r
-                }
-            }
-        }
-
-        pub mod queries {
-            use std::marker::PhantomData;
-
-            $(#[allow(bad_style)]
-            pub struct $name<$tcx> {
-                data: PhantomData<&$tcx ()>
-            })*
-        }
-
-        $(impl<$tcx> QueryConfig for queries::$name<$tcx> {
-            type Key = $K;
-            type Value = $V;
-        }
-
-        impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
-            #[allow(unused)]
-            fn to_dep_node(tcx: TyCtxt<'a, $tcx, 'lcx>, key: &$K) -> DepNode {
-                use dep_graph::DepConstructor::*;
-
-                DepNode::new(tcx, $node(*key))
-            }
-
-            fn try_get_with<F, R>(tcx: TyCtxt<'a, $tcx, 'lcx>,
-                                  mut span: Span,
-                                  key: $K,
-                                  f: F)
-                                  -> Result<R, CycleError<'a, $tcx>>
-                where F: FnOnce(&$V) -> R
-            {
-                debug!("ty::queries::{}::try_get_with(key={:?}, span={:?})",
-                       stringify!($name),
-                       key,
-                       span);
-
-                profq_msg!(tcx,
-                    ProfileQueriesMsg::QueryBegin(
-                        span.clone(),
-                        QueryMsg::$name(profq_key!(tcx, key))
-                    )
-                );
-
-                if let Some(value) = tcx.maps.$name.borrow().map.get(&key) {
-                    if let Some(ref d) = value.diagnostics {
-                        if !d.emitted_diagnostics.get() {
-                            d.emitted_diagnostics.set(true);
-                            let handle = tcx.sess.diagnostic();
-                            for diagnostic in d.diagnostics.iter() {
-                                DiagnosticBuilder::new_diagnostic(handle, diagnostic.clone())
-                                    .emit();
-                            }
-                        }
-                    }
-                    profq_msg!(tcx, ProfileQueriesMsg::CacheHit);
-                    tcx.dep_graph.read_index(value.index);
-                    return Ok(f(&value.value));
-                }
-                // else, we are going to run the provider:
-                profq_msg!(tcx, ProfileQueriesMsg::ProviderBegin);
-
-                // FIXME(eddyb) Get more valid Span's on queries.
-                // def_span guard is necessary to prevent a recursive loop,
-                // default_span calls def_span query internally.
-                if span == DUMMY_SP && stringify!($name) != "def_span" {
-                    span = key.default_span(tcx)
-                }
-
-                let dep_node = Self::to_dep_node(tcx, &key);
-                let res = tcx.cycle_check(span, Query::$name(key), || {
-                    tcx.sess.diagnostic().track_diagnostics(|| {
-                        if dep_node.kind.is_anon() {
-                            tcx.dep_graph.with_anon_task(dep_node.kind, || {
-                                let provider = tcx.maps.providers[key.map_crate()].$name;
-                                provider(tcx.global_tcx(), key)
-                            })
-                        } else {
-                            fn run_provider<'a, 'tcx, 'lcx>(tcx: TyCtxt<'a, 'tcx, 'lcx>,
-                                                            key: $K)
-                                                            -> $V {
-                                let provider = tcx.maps.providers[key.map_crate()].$name;
-                                provider(tcx.global_tcx(), key)
-                            }
-
-                            tcx.dep_graph.with_task(dep_node, tcx, key, run_provider)
-                        }
-                    })
-                })?;
-                profq_msg!(tcx, ProfileQueriesMsg::ProviderEnd);
-                let ((result, dep_node_index), diagnostics) = res;
-
-                tcx.dep_graph.read_index(dep_node_index);
-
-                let value = QueryValue {
-                    value: result,
-                    index: dep_node_index,
-                    diagnostics: if diagnostics.len() == 0 {
-                        None
-                    } else {
-                        Some(Box::new(QueryDiagnostics {
-                            diagnostics,
-                            emitted_diagnostics: Cell::new(true),
-                        }))
-                    },
-                };
-
-                Ok(f(&tcx.maps
-                         .$name
-                         .borrow_mut()
-                         .map
-                         .entry(key)
-                         .or_insert(value)
-                         .value))
-            }
-
-            pub fn try_get(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K)
-                           -> Result<$V, DiagnosticBuilder<'a>> {
-                match Self::try_get_with(tcx, span, key, Clone::clone) {
-                    Ok(e) => Ok(e),
-                    Err(e) => Err(tcx.report_cycle(e)),
-                }
-            }
-
-            pub fn force(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K) {
-                // Ignore dependencies, since we not reading the computed value
-                let _task = tcx.dep_graph.in_ignore();
-
-                match Self::try_get_with(tcx, span, key, |_| ()) {
-                    Ok(()) => {}
-                    Err(e) => tcx.report_cycle(e).emit(),
-                }
-            }
-        })*
-
-        #[derive(Copy, Clone)]
-        pub struct TyCtxtAt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
-            pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
-            pub span: Span,
-        }
-
-        impl<'a, 'gcx, 'tcx> Deref for TyCtxtAt<'a, 'gcx, 'tcx> {
-            type Target = TyCtxt<'a, 'gcx, 'tcx>;
-            fn deref(&self) -> &Self::Target {
-                &self.tcx
-            }
-        }
-
-        impl<'a, $tcx, 'lcx> TyCtxt<'a, $tcx, 'lcx> {
-            /// Return a transparent wrapper for `TyCtxt` which uses
-            /// `span` as the location of queries performed through it.
-            pub fn at(self, span: Span) -> TyCtxtAt<'a, $tcx, 'lcx> {
-                TyCtxtAt {
-                    tcx: self,
-                    span
-                }
-            }
-
-            $($(#[$attr])*
-            pub fn $name(self, key: $K) -> $V {
-                self.at(DUMMY_SP).$name(key)
-            })*
-        }
-
-        impl<'a, $tcx, 'lcx> TyCtxtAt<'a, $tcx, 'lcx> {
-            $($(#[$attr])*
-            pub fn $name(self, key: $K) -> $V {
-                queries::$name::try_get(self.tcx, self.span, key).unwrap_or_else(|mut e| {
-                    e.emit();
-                    Value::from_cycle_error(self.global_tcx())
-                })
-            })*
-        }
-
-        define_provider_struct! {
-            tcx: $tcx,
-            input: ($(([$($modifiers)*] [$name] [$K] [$V]))*),
-            output: ()
-        }
-
-        impl<$tcx> Copy for Providers<$tcx> {}
-        impl<$tcx> Clone for Providers<$tcx> {
-            fn clone(&self) -> Self { *self }
-        }
-    }
-}
-
-macro_rules! define_map_struct {
-    // Initial state
-    (tcx: $tcx:tt,
-     input: $input:tt) => {
-        define_map_struct! {
-            tcx: $tcx,
-            input: $input,
-            output: ()
-        }
-    };
-
-    // Final output
-    (tcx: $tcx:tt,
-     input: (),
-     output: ($($output:tt)*)) => {
-        pub struct Maps<$tcx> {
-            providers: IndexVec<CrateNum, Providers<$tcx>>,
-            query_stack: RefCell<Vec<(Span, Query<$tcx>)>>,
-            $($output)*
-        }
-    };
-
-    // Field recognized and ready to shift into the output
-    (tcx: $tcx:tt,
-     ready: ([$($pub:tt)*] [$($attr:tt)*] [$name:ident]),
-     input: $input:tt,
-     output: ($($output:tt)*)) => {
-        define_map_struct! {
-            tcx: $tcx,
-            input: $input,
-            output: ($($output)*
-                     $(#[$attr])* $($pub)* $name: RefCell<QueryMap<queries::$name<$tcx>>>,)
-        }
-    };
-
-    // No modifiers left? This is a private item.
-    (tcx: $tcx:tt,
-     input: (([] $attrs:tt $name:tt) $($input:tt)*),
-     output: $output:tt) => {
-        define_map_struct! {
-            tcx: $tcx,
-            ready: ([] $attrs $name),
-            input: ($($input)*),
-            output: $output
-        }
-    };
-
-    // Skip other modifiers
-    (tcx: $tcx:tt,
-     input: (([$other_modifier:tt $($modifiers:tt)*] $($fields:tt)*) $($input:tt)*),
-     output: $output:tt) => {
-        define_map_struct! {
-            tcx: $tcx,
-            input: (([$($modifiers)*] $($fields)*) $($input)*),
-            output: $output
-        }
-    };
-}
-
-macro_rules! define_provider_struct {
-    // Initial state:
-    (tcx: $tcx:tt, input: $input:tt) => {
-        define_provider_struct! {
-            tcx: $tcx,
-            input: $input,
-            output: ()
-        }
-    };
-
-    // Final state:
-    (tcx: $tcx:tt,
-     input: (),
-     output: ($(([$name:ident] [$K:ty] [$R:ty]))*)) => {
-        pub struct Providers<$tcx> {
-            $(pub $name: for<'a> fn(TyCtxt<'a, $tcx, $tcx>, $K) -> $R,)*
-        }
-
-        impl<$tcx> Default for Providers<$tcx> {
-            fn default() -> Self {
-                $(fn $name<'a, $tcx>(_: TyCtxt<'a, $tcx, $tcx>, key: $K) -> $R {
-                    bug!("tcx.maps.{}({:?}) unsupported by its crate",
-                         stringify!($name), key);
-                })*
-                Providers { $($name),* }
-            }
-        }
-    };
-
-    // Something ready to shift:
-    (tcx: $tcx:tt,
-     ready: ($name:tt $K:tt $V:tt),
-     input: $input:tt,
-     output: ($($output:tt)*)) => {
-        define_provider_struct! {
-            tcx: $tcx,
-            input: $input,
-            output: ($($output)* ($name $K $V))
-        }
-    };
-
-    // Regular queries produce a `V` only.
-    (tcx: $tcx:tt,
-     input: (([] $name:tt $K:tt $V:tt) $($input:tt)*),
-     output: $output:tt) => {
-        define_provider_struct! {
-            tcx: $tcx,
-            ready: ($name $K $V),
-            input: ($($input)*),
-            output: $output
-        }
-    };
-
-    // Skip modifiers.
-    (tcx: $tcx:tt,
-     input: (([$other_modifier:tt $($modifiers:tt)*] $($fields:tt)*) $($input:tt)*),
-     output: $output:tt) => {
-        define_provider_struct! {
-            tcx: $tcx,
-            input: (([$($modifiers)*] $($fields)*) $($input)*),
-            output: $output
-        }
-    };
-}
+mod config;
+pub use self::config::QueryConfig;
+use self::config::QueryDescription;
 
 // Each of these maps also corresponds to a method on a
 // `Provider` trait for requesting a value of that type,
@@ -1430,6 +328,10 @@ define_maps! { <'tcx>
         -> Arc<OutputFilenames>,
 }
 
+//////////////////////////////////////////////////////////////////////
+// These functions are little shims used to find the dep-node for a
+// given query when there is not a *direct* mapping:
+
 fn type_param_predicates<'tcx>((item_id, param_id): (DefId, DefId)) -> DepConstructor<'tcx> {
     DepConstructor::TypeParamPredicates {
         item_id,
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
new file mode 100644
index 00000000000..87a9eef0de5
--- /dev/null
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -0,0 +1,494 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! The implementation of the query system itself. Defines the macros
+//! that generate the actual methods on tcx which find and execute the
+//! provider, manage the caches, and so forth.
+
+use dep_graph::{DepNodeIndex};
+use errors::{Diagnostic, DiagnosticBuilder};
+use ty::{TyCtxt};
+use ty::maps::Query; // NB: actually generated by the macros in this file
+use ty::maps::config::QueryDescription;
+use ty::item_path;
+
+use rustc_data_structures::fx::{FxHashMap};
+use std::cell::{RefMut, Cell};
+use std::marker::PhantomData;
+use std::mem;
+use syntax_pos::Span;
+
+pub(super) struct QueryMap<D: QueryDescription> {
+    phantom: PhantomData<D>,
+    pub(super) map: FxHashMap<D::Key, QueryValue<D::Value>>,
+}
+
+pub(super) struct QueryValue<T> {
+    pub(super) value: T,
+    pub(super) index: DepNodeIndex,
+    pub(super) diagnostics: Option<Box<QueryDiagnostics>>,
+}
+
+pub(super) struct QueryDiagnostics {
+    pub(super) diagnostics: Vec<Diagnostic>,
+    pub(super) emitted_diagnostics: Cell<bool>,
+}
+
+impl<M: QueryDescription> QueryMap<M> {
+    pub(super) fn new() -> QueryMap<M> {
+        QueryMap {
+            phantom: PhantomData,
+            map: FxHashMap(),
+        }
+    }
+}
+
+pub(super) struct CycleError<'a, 'tcx: 'a> {
+    span: Span,
+    cycle: RefMut<'a, [(Span, Query<'tcx>)]>,
+}
+
+impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
+    pub(super) fn report_cycle(self, CycleError { span, cycle }: CycleError)
+        -> DiagnosticBuilder<'a>
+    {
+        // Subtle: release the refcell lock before invoking `describe()`
+        // below by dropping `cycle`.
+        let stack = cycle.to_vec();
+        mem::drop(cycle);
+
+        assert!(!stack.is_empty());
+
+        // Disable naming impls with types in this path, since that
+        // sometimes cycles itself, leading to extra cycle errors.
+        // (And cycle errors around impls tend to occur during the
+        // collect/coherence phases anyhow.)
+        item_path::with_forced_impl_filename_line(|| {
+            let mut err =
+                struct_span_err!(self.sess, span, E0391,
+                                 "unsupported cyclic reference between types/traits detected");
+            err.span_label(span, "cyclic reference");
+
+            err.span_note(stack[0].0, &format!("the cycle begins when {}...",
+                                               stack[0].1.describe(self)));
+
+            for &(span, ref query) in &stack[1..] {
+                err.span_note(span, &format!("...which then requires {}...",
+                                             query.describe(self)));
+            }
+
+            err.note(&format!("...which then again requires {}, completing the cycle.",
+                              stack[0].1.describe(self)));
+
+            return err
+        })
+    }
+
+    pub(super) fn cycle_check<F, R>(self, span: Span, query: Query<'gcx>, compute: F)
+                                    -> Result<R, CycleError<'a, 'gcx>>
+        where F: FnOnce() -> R
+    {
+        {
+            let mut stack = self.maps.query_stack.borrow_mut();
+            if let Some((i, _)) = stack.iter().enumerate().rev()
+                                       .find(|&(_, &(_, ref q))| *q == query) {
+                return Err(CycleError {
+                    span,
+                    cycle: RefMut::map(stack, |stack| &mut stack[i..])
+                });
+            }
+            stack.push((span, query));
+        }
+
+        let result = compute();
+
+        self.maps.query_stack.borrow_mut().pop();
+
+        Ok(result)
+    }
+}
+
+// If enabled, send a message to the profile-queries thread
+macro_rules! profq_msg {
+    ($tcx:expr, $msg:expr) => {
+        if cfg!(debug_assertions) {
+            if  $tcx.sess.profile_queries() {
+                profq_msg($msg)
+            }
+        }
+    }
+}
+
+// If enabled, format a key using its debug string, which can be
+// expensive to compute (in terms of time).
+macro_rules! profq_key {
+    ($tcx:expr, $key:expr) => {
+        if cfg!(debug_assertions) {
+            if $tcx.sess.profile_queries_and_keys() {
+                Some(format!("{:?}", $key))
+            } else { None }
+        } else { None }
+    }
+}
+
+macro_rules! define_maps {
+    (<$tcx:tt>
+     $($(#[$attr:meta])*
+       [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*) => {
+        define_map_struct! {
+            tcx: $tcx,
+            input: ($(([$($modifiers)*] [$($attr)*] [$name]))*)
+        }
+
+        impl<$tcx> Maps<$tcx> {
+            pub fn new(providers: IndexVec<CrateNum, Providers<$tcx>>)
+                       -> Self {
+                Maps {
+                    providers,
+                    query_stack: RefCell::new(vec![]),
+                    $($name: RefCell::new(QueryMap::new())),*
+                }
+            }
+        }
+
+        #[allow(bad_style)]
+        #[derive(Copy, Clone, Debug, PartialEq, Eq)]
+        pub enum Query<$tcx> {
+            $($(#[$attr])* $name($K)),*
+        }
+
+        #[allow(bad_style)]
+        #[derive(Clone, Debug, PartialEq, Eq)]
+        pub enum QueryMsg {
+            $($name(Option<String>)),*
+        }
+
+        impl<$tcx> Query<$tcx> {
+            pub fn describe(&self, tcx: TyCtxt) -> String {
+                let (r, name) = match *self {
+                    $(Query::$name(key) => {
+                        (queries::$name::describe(tcx, key), stringify!($name))
+                    })*
+                };
+                if tcx.sess.verbose() {
+                    format!("{} [{}]", r, name)
+                } else {
+                    r
+                }
+            }
+        }
+
+        pub mod queries {
+            use std::marker::PhantomData;
+
+            $(#[allow(bad_style)]
+            pub struct $name<$tcx> {
+                data: PhantomData<&$tcx ()>
+            })*
+        }
+
+        $(impl<$tcx> QueryConfig for queries::$name<$tcx> {
+            type Key = $K;
+            type Value = $V;
+        }
+
+        impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
+            #[allow(unused)]
+            fn to_dep_node(tcx: TyCtxt<'a, $tcx, 'lcx>, key: &$K) -> DepNode {
+                use dep_graph::DepConstructor::*;
+
+                DepNode::new(tcx, $node(*key))
+            }
+
+            fn try_get_with<F, R>(tcx: TyCtxt<'a, $tcx, 'lcx>,
+                                  mut span: Span,
+                                  key: $K,
+                                  f: F)
+                                  -> Result<R, CycleError<'a, $tcx>>
+                where F: FnOnce(&$V) -> R
+            {
+                debug!("ty::queries::{}::try_get_with(key={:?}, span={:?})",
+                       stringify!($name),
+                       key,
+                       span);
+
+                profq_msg!(tcx,
+                    ProfileQueriesMsg::QueryBegin(
+                        span.clone(),
+                        QueryMsg::$name(profq_key!(tcx, key))
+                    )
+                );
+
+                if let Some(value) = tcx.maps.$name.borrow().map.get(&key) {
+                    if let Some(ref d) = value.diagnostics {
+                        if !d.emitted_diagnostics.get() {
+                            d.emitted_diagnostics.set(true);
+                            let handle = tcx.sess.diagnostic();
+                            for diagnostic in d.diagnostics.iter() {
+                                DiagnosticBuilder::new_diagnostic(handle, diagnostic.clone())
+                                    .emit();
+                            }
+                        }
+                    }
+                    profq_msg!(tcx, ProfileQueriesMsg::CacheHit);
+                    tcx.dep_graph.read_index(value.index);
+                    return Ok(f(&value.value));
+                }
+                // else, we are going to run the provider:
+                profq_msg!(tcx, ProfileQueriesMsg::ProviderBegin);
+
+                // FIXME(eddyb) Get more valid Span's on queries.
+                // def_span guard is necessary to prevent a recursive loop,
+                // default_span calls def_span query internally.
+                if span == DUMMY_SP && stringify!($name) != "def_span" {
+                    span = key.default_span(tcx)
+                }
+
+                let dep_node = Self::to_dep_node(tcx, &key);
+                let res = tcx.cycle_check(span, Query::$name(key), || {
+                    tcx.sess.diagnostic().track_diagnostics(|| {
+                        if dep_node.kind.is_anon() {
+                            tcx.dep_graph.with_anon_task(dep_node.kind, || {
+                                let provider = tcx.maps.providers[key.map_crate()].$name;
+                                provider(tcx.global_tcx(), key)
+                            })
+                        } else {
+                            fn run_provider<'a, 'tcx, 'lcx>(tcx: TyCtxt<'a, 'tcx, 'lcx>,
+                                                            key: $K)
+                                                            -> $V {
+                                let provider = tcx.maps.providers[key.map_crate()].$name;
+                                provider(tcx.global_tcx(), key)
+                            }
+
+                            tcx.dep_graph.with_task(dep_node, tcx, key, run_provider)
+                        }
+                    })
+                })?;
+                profq_msg!(tcx, ProfileQueriesMsg::ProviderEnd);
+                let ((result, dep_node_index), diagnostics) = res;
+
+                tcx.dep_graph.read_index(dep_node_index);
+
+                let value = QueryValue {
+                    value: result,
+                    index: dep_node_index,
+                    diagnostics: if diagnostics.len() == 0 {
+                        None
+                    } else {
+                        Some(Box::new(QueryDiagnostics {
+                            diagnostics,
+                            emitted_diagnostics: Cell::new(true),
+                        }))
+                    },
+                };
+
+                Ok(f(&tcx.maps
+                         .$name
+                         .borrow_mut()
+                         .map
+                         .entry(key)
+                         .or_insert(value)
+                         .value))
+            }
+
+            pub fn try_get(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K)
+                           -> Result<$V, DiagnosticBuilder<'a>> {
+                match Self::try_get_with(tcx, span, key, Clone::clone) {
+                    Ok(e) => Ok(e),
+                    Err(e) => Err(tcx.report_cycle(e)),
+                }
+            }
+
+            pub fn force(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K) {
+                // Ignore dependencies, since we not reading the computed value
+                let _task = tcx.dep_graph.in_ignore();
+
+                match Self::try_get_with(tcx, span, key, |_| ()) {
+                    Ok(()) => {}
+                    Err(e) => tcx.report_cycle(e).emit(),
+                }
+            }
+        })*
+
+        #[derive(Copy, Clone)]
+        pub struct TyCtxtAt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
+            pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
+            pub span: Span,
+        }
+
+        impl<'a, 'gcx, 'tcx> Deref for TyCtxtAt<'a, 'gcx, 'tcx> {
+            type Target = TyCtxt<'a, 'gcx, 'tcx>;
+            fn deref(&self) -> &Self::Target {
+                &self.tcx
+            }
+        }
+
+        impl<'a, $tcx, 'lcx> TyCtxt<'a, $tcx, 'lcx> {
+            /// Return a transparent wrapper for `TyCtxt` which uses
+            /// `span` as the location of queries performed through it.
+            pub fn at(self, span: Span) -> TyCtxtAt<'a, $tcx, 'lcx> {
+                TyCtxtAt {
+                    tcx: self,
+                    span
+                }
+            }
+
+            $($(#[$attr])*
+            pub fn $name(self, key: $K) -> $V {
+                self.at(DUMMY_SP).$name(key)
+            })*
+        }
+
+        impl<'a, $tcx, 'lcx> TyCtxtAt<'a, $tcx, 'lcx> {
+            $($(#[$attr])*
+            pub fn $name(self, key: $K) -> $V {
+                queries::$name::try_get(self.tcx, self.span, key).unwrap_or_else(|mut e| {
+                    e.emit();
+                    Value::from_cycle_error(self.global_tcx())
+                })
+            })*
+        }
+
+        define_provider_struct! {
+            tcx: $tcx,
+            input: ($(([$($modifiers)*] [$name] [$K] [$V]))*),
+            output: ()
+        }
+
+        impl<$tcx> Copy for Providers<$tcx> {}
+        impl<$tcx> Clone for Providers<$tcx> {
+            fn clone(&self) -> Self { *self }
+        }
+    }
+}
+
+macro_rules! define_map_struct {
+    // Initial state
+    (tcx: $tcx:tt,
+     input: $input:tt) => {
+        define_map_struct! {
+            tcx: $tcx,
+            input: $input,
+            output: ()
+        }
+    };
+
+    // Final output
+    (tcx: $tcx:tt,
+     input: (),
+     output: ($($output:tt)*)) => {
+        pub struct Maps<$tcx> {
+            providers: IndexVec<CrateNum, Providers<$tcx>>,
+            query_stack: RefCell<Vec<(Span, Query<$tcx>)>>,
+            $($output)*
+        }
+    };
+
+    // Field recognized and ready to shift into the output
+    (tcx: $tcx:tt,
+     ready: ([$($pub:tt)*] [$($attr:tt)*] [$name:ident]),
+     input: $input:tt,
+     output: ($($output:tt)*)) => {
+        define_map_struct! {
+            tcx: $tcx,
+            input: $input,
+            output: ($($output)*
+                     $(#[$attr])* $($pub)* $name: RefCell<QueryMap<queries::$name<$tcx>>>,)
+        }
+    };
+
+    // No modifiers left? This is a private item.
+    (tcx: $tcx:tt,
+     input: (([] $attrs:tt $name:tt) $($input:tt)*),
+     output: $output:tt) => {
+        define_map_struct! {
+            tcx: $tcx,
+            ready: ([] $attrs $name),
+            input: ($($input)*),
+            output: $output
+        }
+    };
+
+    // Skip other modifiers
+    (tcx: $tcx:tt,
+     input: (([$other_modifier:tt $($modifiers:tt)*] $($fields:tt)*) $($input:tt)*),
+     output: $output:tt) => {
+        define_map_struct! {
+            tcx: $tcx,
+            input: (([$($modifiers)*] $($fields)*) $($input)*),
+            output: $output
+        }
+    };
+}
+
+macro_rules! define_provider_struct {
+    // Initial state:
+    (tcx: $tcx:tt, input: $input:tt) => {
+        define_provider_struct! {
+            tcx: $tcx,
+            input: $input,
+            output: ()
+        }
+    };
+
+    // Final state:
+    (tcx: $tcx:tt,
+     input: (),
+     output: ($(([$name:ident] [$K:ty] [$R:ty]))*)) => {
+        pub struct Providers<$tcx> {
+            $(pub $name: for<'a> fn(TyCtxt<'a, $tcx, $tcx>, $K) -> $R,)*
+        }
+
+        impl<$tcx> Default for Providers<$tcx> {
+            fn default() -> Self {
+                $(fn $name<'a, $tcx>(_: TyCtxt<'a, $tcx, $tcx>, key: $K) -> $R {
+                    bug!("tcx.maps.{}({:?}) unsupported by its crate",
+                         stringify!($name), key);
+                })*
+                Providers { $($name),* }
+            }
+        }
+    };
+
+    // Something ready to shift:
+    (tcx: $tcx:tt,
+     ready: ($name:tt $K:tt $V:tt),
+     input: $input:tt,
+     output: ($($output:tt)*)) => {
+        define_provider_struct! {
+            tcx: $tcx,
+            input: $input,
+            output: ($($output)* ($name $K $V))
+        }
+    };
+
+    // Regular queries produce a `V` only.
+    (tcx: $tcx:tt,
+     input: (([] $name:tt $K:tt $V:tt) $($input:tt)*),
+     output: $output:tt) => {
+        define_provider_struct! {
+            tcx: $tcx,
+            ready: ($name $K $V),
+            input: ($($input)*),
+            output: $output
+        }
+    };
+
+    // Skip modifiers.
+    (tcx: $tcx:tt,
+     input: (([$other_modifier:tt $($modifiers:tt)*] $($fields:tt)*) $($input:tt)*),
+     output: $output:tt) => {
+        define_provider_struct! {
+            tcx: $tcx,
+            input: (([$($modifiers)*] $($fields)*) $($input)*),
+            output: $output
+        }
+    };
+}
diff --git a/src/librustc/ty/maps/values.rs b/src/librustc/ty/maps/values.rs
new file mode 100644
index 00000000000..165798d19f1
--- /dev/null
+++ b/src/librustc/ty/maps/values.rs
@@ -0,0 +1,49 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use ty::{self, Ty, TyCtxt};
+
+use syntax::symbol::Symbol;
+
+pub(super) trait Value<'tcx>: Sized {
+    fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self;
+}
+
+impl<'tcx, T> Value<'tcx> for T {
+    default fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> T {
+        tcx.sess.abort_if_errors();
+        bug!("Value::from_cycle_error called without errors");
+    }
+}
+
+impl<'tcx, T: Default> Value<'tcx> for T {
+    default fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> T {
+        T::default()
+    }
+}
+
+impl<'tcx> Value<'tcx> for Ty<'tcx> {
+    fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> {
+        tcx.types.err
+    }
+}
+
+impl<'tcx> Value<'tcx> for ty::DtorckConstraint<'tcx> {
+    fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
+        Self::empty()
+    }
+}
+
+impl<'tcx> Value<'tcx> for ty::SymbolName {
+    fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
+        ty::SymbolName { name: Symbol::intern("<error>").as_str() }
+    }
+}
+