rust-lang/rust

Query system and incremental compilation

The query system is the engine that runs the compiler. Almost everything you'd think of as a "compiler pass" is actually a query — a memoized function from a key to a value, evaluated on demand and cached across compilations.

Why queries

The pre-query rustc was structured as a sequence of distinct phases, each operating on the entire crate. Adding incremental compilation, parallel work, and cleaner modular dependencies prompted a redesign: each compilation is now a demand-driven graph of query invocations, with explicit dependency tracking.

Two things fall out for free:

Incremental compilation — query results are persisted to disk. On the next compile, queries whose inputs haven't changed reuse the cached result.
Parallel compilation — independent queries can run on separate threads (rustc_thread_pool, rustc's fork of Rayon).

Pieces

Crate	Role
`rustc_query_system`	Generic query engine: dependency graph, caching, on-disk format
`rustc_query_impl`	Query-specific logic generated by the macros
`rustc_middle::query`	Query definitions — names, key/value types, providers
`rustc_incremental`	On-disk incremental cache lifecycle

How a query works

sequenceDiagram
    participant Caller
    participant TyCtxt
    participant Cache
    participant DepGraph
    participant Provider

    Caller->>TyCtxt: tcx.type_of(def_id)
    TyCtxt->>Cache: lookup(def_id)
    alt cache hit
        Cache-->>TyCtxt: cached value
        TyCtxt-->>Caller: value
    else cache miss
        TyCtxt->>DepGraph: start tracking deps
        TyCtxt->>Provider: provider_for_type_of(def_id)
        Provider->>TyCtxt: tcx.predicates_of(...)
        Note over TyCtxt: nested queries record edges
        Provider-->>TyCtxt: computed value
        TyCtxt->>DepGraph: finish; commit edges
        TyCtxt->>Cache: insert(def_id → value)
        TyCtxt-->>Caller: value
    end

On a re-compilation, the system loads the previous run's dep graph and result cache. For each query you ask:

Look up its dependency edges in the previous graph
Re-evaluate any input that has changed (HirIds that point to changed source, command-line flags, etc.)
If no input changed transitively, mark the result as green (reusable)
Otherwise, red (must re-run)

Green results are reused without recomputation. Red results re-run, and the dep graph updates.

Query definitions

Queries are declared in compiler/rustc_middle/src/query/mod.rs with a macro:

rustc_queries! {
    query type_of(key: DefId) -> Ty<'tcx> {
        desc { |tcx| "computing type of `{}`", tcx.def_path_str(key) }
        cache_on_disk_if { key.is_local() }
    }

    query predicates_of(key: DefId) -> ty::GenericPredicates<'tcx> {
        desc { |tcx| "computing predicates of `{}`", tcx.def_path_str(key) }
    }

    // ... hundreds more
}

Each query has:

A name (becomes a method on TyCtxt)
A key type (DefId, (DefId, DefId), LocalDefId, …)
A value type
A description for diagnostic and dump output
Optional flags (cache_on_disk_if, eval_always, feedable, …)

The macro generates the storage, the TyCtxt method, the dep-graph hooks, and the on-disk encoding.

Providers

A provider is the function that computes a query's value when the cache misses. Providers are organized by area of the compiler:

rustc_ty_utils::provide — type-related queries (type_of, predicates_of, fn_sig, …)
rustc_hir_analysis::provide — well-formedness, coherence
rustc_hir_typeck::provide — typeck_results
rustc_borrowck::provide — mir_borrowck
rustc_mir_transform::provide — mir_built, optimized_mir
… and so on

Each crate registers its providers via tcx.providers.<query_name> = my_function; during compiler startup. When tcx.type_of(def_id) is called and the cache misses, the registered provider runs.

Why `rustc_query_impl` is a separate crate

Compilation of rustc_query_impl is heavy because of all the macro-generated code. By extracting it from rustc_middle, the rest of the compiler can edit query definitions and recompile only rustc_query_impl, instead of recompiling the whole compiler. The pattern of *_impl crates exists for similar reasons elsewhere (rustc_driver_impl).

On-disk cache layout

Per compilation invocation, rustc writes:

target/.../incremental/<crate-hash>/work-products/... — .o, .rmeta outputs
target/.../incremental/<crate-hash>/dep-graph.bin — serialized dep graph
target/.../incremental/<crate-hash>/query-cache.bin — cached query results

Layout details and serialization live in rustc_query_system and rustc_incremental. The format isn't stable — between rustc versions, the cache is invalidated.

`eval_always` and `feedable`

Two interesting flags on queries:

eval_always — never cached, always re-runs. Used for queries that depend on global state we can't easily fingerprint (e.g., environment-derived configuration).
feedable — the result can be fed in by an external caller. Used during rustc_interface to pre-populate certain queries (the result of parsing, for example).

Parallel queries

rustc_thread_pool (a fork of Rayon with deadlock detection) lets the query system run independent queries on multiple threads. The cache is sharded for low-contention parallel access. Most contributors don't have to think about parallelism — the query layer handles synchronization — but some queries (those mutating shared state via Steal<T> or OnceLock<T>) need care.

Stable hashing

For incremental compilation to detect "did this input change?", the dep graph hashes inputs. Hashing must be stable across compiler runs and machines, so it's done with rustc_data_structures::stable_hasher::StableHasher, which uses HashStable impls that are deterministic under any HashMap iteration order.

The compiler maintains a discipline of "anything that could be a query input has a HashStable impl that captures all relevant state." rustc_macros provides a #[derive(HashStable)] for the common case.

Common cycle errors

If a user-visible cycle appears (e.g., type Foo = Foo;), the query system catches it and reports a diagnostic with the involved queries. Internally, query cycles are bugs to be fixed; user-visible cycles get nice diagnostics in rustc_query_system::query::cycle_check.

Entry points for modification

Add a query: add a definition in compiler/rustc_middle/src/query/mod.rs, then provide it in the relevant crate's provide function
Make a query incremental-friendly: ensure its inputs implement HashStable; consider cache_on_disk_if
Investigate a perf regression: -Zself-profile, then rendering with summarize or crox
Bug in incremental cache: RUSTC_INCR_VERIFY=1 validates more aggressively