functions. If calling a provider function could yield different results for
each invocation (because it accesses some global mutable state) then we could
not memoize the result.



## Input data

When the query context is created, it is still empty: No queries have been
executed, no results are cached. But the context already provides access to
"input" data, i.e. pieces of immutable data that were computed before the
context was created and that queries can access to do their computations.

As of <!-- date-check --> January 2021, this input data consists mainly of
the HIR map, upstream crate metadata, and the command-line options the compiler
was invoked with; but in the future inputs will just consist of command-line
options and a list of source files -- the HIR map will itself be provided by a
query which processes these source files.

Without inputs, queries would live in a void without anything to compute their
result from (remember, query providers only have access to other queries and
the context but not any other outside state or information).

For a query provider, input data and results of other queries look exactly the
same: It just tells the context "give me the value of X". Because input data
is immutable, the provider can rely on it being the same across
different query invocations, just as is the case for query results.



## An example execution trace of some queries

How does this DAG of query invocations come into existence? At some point
the compiler driver will create the, as yet empty, query context. It will then,
from outside of the query system, invoke the queries it needs to perform its
task. This looks something like the following:

```rust,ignore
fn compile_crate() {
    let cli_options = ...;
    let hir_map = ...;

    // Create the query context `tcx`
    let tcx = TyCtxt::new(cli_options, hir_map);

    // Do type checking by invoking the type check query
    tcx.type_check_crate();
}
```

The `type_check_crate` query provider would look something like the following:

```rust,ignore
fn type_check_crate_provider(tcx, _key: ()) {
    let list_of_hir_items = tcx.hir_map.list_of_items();

    for item_def_id in list_of_hir_items {
        tcx.type_check_item(item_def_id);
    }
}
```

We see that the `type_check_crate` query accesses input data
(`tcx.hir_map.list_of_items()`) and invokes other queries
(`type_check_item`). The `type_check_item`
invocations will themselves access input data and/or invoke other queries,
so that in the end the DAG of query invocations will be built up backwards
from the node that was initially executed:

```ignore
         (2)                                                 (1)
  list_of_all_hir_items <----------------------------- type_check_crate()
                                                               |
    (5)             (4)                  (3)                   |
  Hir(foo) <--- type_of(foo) <--- type_check_item(foo) <-------+
                                      |                        |
                    +-----------------+                        |
                    |                                          |
    (7)             v  (6)                  (8)                |