Document query internals

[jyn514]

rustc_query_impl and rustc_query_system are complicated. We should have a document somewhere that explains how they work internally.

We used to have a very short sketch of that in the dev-guide, but it was removed in rust-lang/rustc-dev-guide@552de58 because it wasn't clear that it was an implementation detail and not user-facing.

My short summary (I'll try and update this later):

• Queries are defined in

  rust/compiler/rustc_middle/src/query/mod.rs

  Lines 1 to 5 in b0f3940

  	//! Defines the various compiler queries.
  	//!
  	//! For more information on the query system, see
  	//! ["Queries: demand-driven compilation"](https://rustc-dev-guide.rust-lang.org/query.html).
  	//! This chapter includes instructions for adding new queries.

  using the rustc_queries macro.
• rustc_queries is defined in

  rust/compiler/rustc_macros/src/query.rs

  Line 293 in b0f3940

  pub fn rustc_queries(input: TokenStream) -> TokenStream {

  It outputs another rustc_query_append macro, as well as two modules:

  rust/compiler/rustc_macros/src/query.rs

  Lines 357 to 374 in b0f3940

  	#[macro_export]
  	macro_rules! rustc_query_append {
  	($macro:ident! $( [$($other:tt)*] )?) => {
  	$macro! {
  	$( $($other)* )?
  	#query_stream
  	}
  	}
  	}
  	pub mod descs {
  	use super::*;
  	#query_description_stream
  	}
  	pub mod cached {
  	use super::*;
  	#query_cached_stream
  	}

• rustc_query_append is called in various places around the compiler. It takes another macro as its input, then calls that macro with the token stream emitted by rustc_queries. This emulates eager expansion.
• The primary callers of rustc_query_append are rustc_middle::define_callbacks

  rust/compiler/rustc_middle/src/ty/query.rs

  Line 177 in d933092

  macro_rules! define_callbacks {

  and rustc_query_impl::define_queries

  rust/compiler/rustc_query_impl/src/plumbing.rs

  Line 444 in 24ce4cf

  macro_rules! define_queries {

There are 3 main crates involved in defining queries, other than rustc_macros.

1. rustc_query_system comes earliest in the dependency graph. It defines various traits along with some helper functions. It is very fast to compile. We may want to rename this to rustc_query_traits at some point.
2. rustc_middle comes next and depends on query_system. It defines TyCtxt and various helper functions that are used elsewhere in the compiler; this is the first place we can invoke rustc_queries, since before this we don't have access to TyCtxt. This is slow to compile but not because of the query system, it's just big.
3. rustc_query_impl depends on rustc_middle. It implements the traits in rustc_query_system for the queries declared in rustc_middle. It takes an extremely long time to compile.

Because query_impl takes so long to compile, we don't depend on it anywhere except for rustc_interface. In particular, we use function pointers and dynamic dispatch as necessary so that rustc_middle and later crates don't need to depend on query internals.

cc @cjgillot @Nilstrieb