// (x) denotes invocation order
```

We also see that often a query result can be read from the cache:
`type_of(bar)` was computed for `type_check_item(foo)` so when
`type_check_item(bar)` needs it, it is already in the cache.

Query results stay cached in the query context as long as the context lives.
So if the compiler driver invoked another query later on, the above graph
would still exist and already executed queries would not have to be re-done.



## Cycles

Earlier we stated that query invocations form a DAG. However, it would be easy
to form a cyclic graph by, for example, having a query provider like the
following:

```rust,ignore
fn cyclic_query_provider(tcx, key) -> u32 {
  // Invoke the same query with the same key again
  tcx.cyclic_query(key)
}
```

Since query providers are regular functions, this would behave much as expected:
Evaluation would get stuck in an infinite recursion. A query like this would not
be very useful either. However, sometimes certain kinds of invalid user input
can result in queries being called in a cyclic way. The query engine includes
a check for cyclic invocations of queries with the same input arguments. 
And, because cycles are an irrecoverable error, will abort execution with a 
"cycle error" message that tries to be human readable.

At some point the compiler had a notion of "cycle recovery", that is, one could
"try" to execute a query and if it ended up causing a cycle, proceed in some
other fashion. However, this was later removed because it is not entirely
clear what the theoretical consequences of this are, especially regarding
incremental compilation.


## "Steal" Queries

Some queries have their result wrapped in a `Steal<T>` struct. These queries
behave exactly the same as regular with one exception: Their result is expected
to be "stolen" out of the cache at some point, meaning some other part of the
program is taking ownership of it and the result cannot be accessed anymore.

This stealing mechanism exists purely as a performance optimization because some
result values are too costly to clone (e.g. the MIR of a function). It seems
like result stealing would violate the condition that query results must be
immutable (after all we are moving the result value out of the cache) but it is
OK as long as the mutation is not observable. This is achieved by two things:

- Before a result is stolen, we make sure to eagerly run all queries that
  might ever need to read that result. This has to be done manually by calling
  those queries.
- Whenever a query tries to access a stolen result, we make an ICE
  (Internal Compiler Error) so that such a condition cannot go unnoticed.

This is not an ideal setup because of the manual intervention needed, so it
should be used sparingly and only when it is well known which queries might
access a given result. In practice, however, stealing has not turned out to be
much of a maintenance burden.

To summarize: "Steal queries" break some of the rules in a controlled way.
There are checks in place that make sure that nothing can go silently wrong.