The Query System — Demand-Driven Compilation and Incremental Reuse

If Part 1 showed you the shape of the Rust compiler, this article reveals its operating principle. The query system is the single most important architectural decision in rustc — it replaced a traditional sequential pipeline with a network of demand-driven, memoized computations. Every non-trivial piece of information the compiler computes (the type of an expression, the MIR of a function, whether a trait implementation is valid) is a query.

Understanding the query system is not optional. It's the connective tissue that binds the 75 compiler crates together, and it's the foundation for incremental compilation — the feature that makes cargo check fast on subsequent runs.

Why Demand-Driven? From Sequential Pipeline to Queries

A traditional compiler runs in phases: parse → type-check → optimize → emit code. Each phase consumes the entire output of the previous one. This has two problems. First, it forces the compiler to do all work up front, even for portions of the program that might not need it. Second, changing a single function forces recomputation of everything downstream.

The query architecture inverts this. Instead of pushing data through a pipeline, consumers pull results as needed. When you ask for optimized_mir(def_id), the query system checks whether the result is already cached. If not, it invokes the provider function, which may itself trigger other queries (type checking, borrow checking, etc.), forming a directed acyclic graph of computations.

flowchart TD
    A["optimized_mir(fn_a)"] --> B["mir_drops_elaborated(fn_a)"]
    B --> C["mir_borrowck(fn_a)"]
    B --> D["mir_promoted(fn_a)"]
    D --> E["mir_built(fn_a)"]
    C --> D
    C --> F["typeck(fn_a)"]
    F --> G["type_of(struct_s)"]
    F --> H["predicates_of(trait_t)"]
    
    style A fill:#f96,stroke:#333
    style C fill:#9cf,stroke:#333
    style F fill:#9f9,stroke:#333

This gives three benefits: (1) only the queries needed are evaluated, (2) results are memoized across invocations within a session, and (3) a dependency graph records which queries depend on which inputs, enabling incremental recompilation by invalidating only what changed.

Defining Queries: The rustc_queries! Macro

All queries are defined in a single file using the rustc_queries! macro:

compiler/rustc_middle/src/queries.rs#L138

The file's module-level documentation (lines 1–44) is unusually thorough and worth reading in full. It explains the entire expansion pipeline and all available modifiers.

Each query declaration specifies a key type and a return type, plus optional modifiers:

rustc_queries! {
    query type_of(key: DefId) -> ty::EarlyBinder<'tcx, Ty<'tcx>> {
        desc { "computing type of `{}`", tcx.def_path_str(key) }
        cache_on_disk_if { key.is_local() }
    }
    
    query optimized_mir(key: DefId) -> &'tcx Body<'tcx> {
        desc { "optimizing MIR for `{}`", tcx.def_path_str(key) }
        cache_on_disk_if { key.is_local() }
    }
}

The key modifiers to understand:

Modifier	Meaning
eval_always	Never reuse cached results — always re-evaluate
cache_on_disk_if { .. }	Persist results to disk for incremental compilation
arena_cache	Allocate results in the arena instead of cloning
separate_provide_extern	External (cross-crate) providers are registered separately
desc { .. }	Human-readable description shown in cycle errors and profiling

The rustc_macros::rustc_queries proc macro expands each declaration into: a method on TyCtxt for invoking the query, a field in the Providers struct for registering the implementation, and all the caching and dependency-tracking plumbing.

Tip: When reading queries.rs, focus on the key type to understand the granularity. Queries keyed by DefId work per-item. Queries keyed by () (the unit type) are crate-global. Queries keyed by LocalDefId only apply to items defined in the current crate.

TyCtxt and GlobalCtxt: The Query Execution Engine

As we saw in Part 1, TyCtxt<'tcx> is the central hub of the compiler. Structurally, it's a single-pointer wrapper around GlobalCtxt:

compiler/rustc_middle/src/ty/context.rs#L745-L747

pub struct TyCtxt<'tcx> {
    gcx: &'tcx GlobalCtxt<'tcx>,
}

GlobalCtxt is the "god struct" — it holds everything:

compiler/rustc_middle/src/ty/context.rs#L768-L839

classDiagram
    class TyCtxt~tcx~ {
        gcx: &GlobalCtxt
    }
    class GlobalCtxt~tcx~ {
        arena: &WorkerLocal~Arena~
        hir_arena: &WorkerLocal~hir::Arena~
        interners: CtxtInterners
        sess: &Session
        dep_graph: DepGraph
        query_system: QuerySystem
        types: CommonTypes
        lifetimes: CommonLifetimes
        consts: CommonConsts
    }
    TyCtxt --> GlobalCtxt : wraps
    GlobalCtxt --> Session : holds
    GlobalCtxt --> DepGraph : tracks dependencies
    GlobalCtxt --> QuerySystem : memoizes results

When you call tcx.type_of(def_id), the generated method:

1. Looks up the result in the query cache (inside query_system)
2. If cached, records a dependency edge and returns the cached result
3. If not cached, looks up the provider function from Providers
4. Calls the provider, records the result, and returns it

The 'tcx lifetime ties everything allocated during compilation to the GlobalCtxt. When the global context is dropped, all arenas are freed in one shot — no individual deallocation needed.

Provider Registration: Wiring 20 Crates to the Query System

The Providers struct is a table of function pointers — one for each query. During compiler startup, ~20 crates register their implementations:

compiler/rustc_interface/src/passes.rs#L880-L919

pub static DEFAULT_QUERY_PROVIDERS: LazyLock<Providers> = LazyLock::new(|| {
    let providers = &mut Providers::default();
    providers.queries.analysis = analysis;
    providers.queries.hir_crate = rustc_ast_lowering::lower_to_hir;
    // ...
    rustc_hir_analysis::provide(&mut providers.queries);
    rustc_borrowck::provide(&mut providers.queries);
    rustc_mir_transform::provide(providers);
    rustc_monomorphize::provide(providers);
    rustc_codegen_ssa::provide(providers);
    // ...20+ more crates
    *providers
});

flowchart TD
    LP["LazyLock: DEFAULT_QUERY_PROVIDERS"] --> P["Providers struct"]
    P --> |"analysis"| PASSES["rustc_interface::passes"]
    P --> |"hir_crate"| LOWER["rustc_ast_lowering"]
    P --> |"typeck"| HTA["rustc_hir_analysis"]
    P --> |"mir_borrowck"| BORROW["rustc_borrowck"]
    P --> |"optimized_mir"| MIR["rustc_mir_transform"]
    P --> |"collect_and_partition_mono_items"| MONO["rustc_monomorphize"]
    P --> |"codegen_fn_attrs"| CODEGEN["rustc_codegen_ssa"]
    
    style LP fill:#f96

After all crate providers are registered, the codegen backend gets a chance to provide its own queries (line 966), and then the override_queries callback (from Config) is applied. This is how clippy-driver and rust-analyzer inject their custom behavior — they swap out specific query implementations after the defaults are set up.

This is a brilliant architectural pattern: each crate only knows about rustc_middle types (not about the other crates), and the wiring happens at the integration layer in rustc_interface. It keeps the dependency graph manageable.

The Steal Pattern: Linear Consumption of Query Results

There's a tension in the query system: queries should be pure functions that return immutable values (so caching works correctly), but some intermediate results (particularly MIR bodies) need to be iteratively transformed in place. Cloning a full MIR body for each transformation would be prohibitively expensive.

The solution is Steal<T>:

compiler/rustc_data_structures/src/steal.rs#L4-L27

sequenceDiagram
    participant Q1 as mir_built query
    participant Steal as Steal~Body~
    participant Q2 as mir_promoted query
    
    Q1->>Steal: new(body) → &'tcx Steal<Body>
    Note over Steal: value = Some(body)
    Q2->>Steal: borrow() → read access
    Q2->>Steal: steal() → takes ownership
    Note over Steal: value = None
    Note over Steal: Any future borrow() panics!

Steal<T> wraps a value in an RwLock<Option<T>>. You can borrow() it as many times as you want (returning a read guard), but once you steal() it, the value is gone. Any subsequent borrow() panics with a clear message: "attempted to read from stolen value".

This enforces a linear consumption discipline: mir_promoted steals the result of mir_built, transforms it, and produces a new Steal-wrapped result. Nobody else can accidentally read the pre-promotion MIR afterward.

The risky_hack_borrow_mut() method (line 48) is an escape hatch for custom drivers — it provides mutable access while the value hasn't been stolen. The name is deliberately alarming because using it breaks incremental compilation assumptions.

Dependency Tracking and Incremental Compilation

Every query invocation is tracked. When query A reads from query B, the system records an edge in the dependency graph. On the next compilation, if the inputs to B haven't changed, B's cached result is still valid — and so is A's, transitively.

The dependency graph is managed through the dep_graph field on GlobalCtxt. The cache_on_disk_if modifier on a query determines whether its result is serialized to disk between compilations. Not all queries are persisted — only those where serialization cost is less than recomputation cost.

flowchart TD
    subgraph "Compilation N"
        A1["type_of(Foo)"] --> B1["predicates_of(Bar)"]
        A1 --> C1["generics_of(Foo)"]
        B1 --> D1["source file hash"]
    end
    
    subgraph "Compilation N+1"
        D2["source file hash"] -->|"changed?"| CHECK{Hash differs?}
        CHECK -->|"No"| REUSE["Reuse B, A, C from cache"]
        CHECK -->|"Yes"| RECOMPUTE["Recompute B → re-verify A, C"]
    end

The general flow for incremental compilation:

1. Load the previous session's dependency graph and query results from disk
2. For each "green" node (unchanged inputs), try to reuse the cached result
3. For each "red" node (changed inputs), recompute and check if the output changed
4. If a recomputed node produces the same output, downstream nodes remain green

This "try to mark green" approach means that even when a source file changes, if the change doesn't affect the public API (say, you only changed a function body), downstream queries that only depend on signatures can still be reused.

The analysis Query: Root of the Query Cascade

The analysis query is the root that kicks off all semantic checking. It's invoked as tcx.ensure_ok().analysis(()) from the driver (as we saw in Part 1), and it fans out to trigger dozens of sub-queries:

compiler/rustc_interface/src/passes.rs#L1180-L1257

The analysis function calls run_required_analyses(tcx) first, which orchestrates:

compiler/rustc_interface/src/passes.rs#L1056-L1176

flowchart TD
    ANALYSIS["analysis(())"] --> RRA["run_required_analyses()"]
    RRA --> CC["check_crate() — type checking"]
    RRA --> BORROWCK["par_hir_body_owners → mir_borrowck"]
    RRA --> UNSAFE["check_unsafety"]
    RRA --> LIVENESS["check_liveness"]
    RRA --> DROPS["mir_drops_elaborated_and_const_checked"]
    
    ANALYSIS --> PRIVACY["check_mod_privacy"]
    ANALYSIS --> DEATH["check_mod_deathness"]
    ANALYSIS --> LINT["rustc_lint::check_crate"]
    ANALYSIS --> EXPECT["check_expectations"]
    
    CC --> COHERENCE["coherence checking"]
    CC --> TYPECK["typeck(def_id) per item"]
    CC --> WF["check_type_wf"]

Notice the use of par_hir_body_owners (line 1138) — this iterates over all items in parallel when parallel compilation is enabled. Each item independently triggers its own cascade of queries (mir_borrowck, check_unsafety, etc.), and the query system's memoization ensures no work is duplicated.

The ensure_ok() method is worth noting — it's a variant of query invocation that doesn't return the result, only ensures the query runs successfully. This is used when we want to trigger side effects (like error reporting) without needing the computed value.

Tip: When debugging a compilation issue, knowing the query DAG helps immensely. Use RUSTC_LOG=rustc_query_impl=trace to see every query invocation. For a specific query, -Z dump-dep-graph will write the dependency graph to disk for inspection.

What's Next

Now that you understand the demand-driven architecture, we can trace what these queries actually compute. In Part 3, we'll follow a Rust program through the compiler's four intermediate representations: from the token-oriented AST produced by the parser, through the desugared HIR, the typed THIR, and finally into MIR — the control-flow graph IR where borrow checking and optimizations happen.