Query System

The Rust compiler uses a demand-driven query system where compilation work is organized as queries. Each query is a memoized function from a key to a value, with automatic caching and dependency tracking.

Overview

The query system is the heart of the Rust compiler’s architecture:

318+ queries defined in rustc_middle::queries
Demand-driven execution - queries only run when their results are needed
Automatic memoization - results are cached for reuse
Dependency tracking - changes trigger recomputation of affected queries
Incremental compilation - queries enable fine-grained incremental builds

Architecture

Core Components

rustc_middle::queries

Query definitions with key/value types and modifiers (318+ queries)

rustc_query_impl

Query system implementation, caching, and dependency tracking

Providers

Function table containing actual query implementations

TyCtxt

Main compiler context - provides access to all queries

How Queries Work

Basic Structure

Each query is defined with:

query query_name(key: KeyType) -> ValueType {
    desc { "description of what this query does" }
    // Optional modifiers
}

Invocation

Queries are called through the TyCtxt:

let result = tcx.query_name(key);

The query system:

Checks the cache for existing results
If not cached, calls the provider function
Stores the result in the cache
Tracks dependencies in the dependency graph
Returns the result

Query Modifiers

Query modifiers control query behavior. From the query system documentation:

desc - Description (Required)

Sets the human-readable description for diagnostics and profiling.

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

The tcx and query key are available within the block.

arena_cache - Arena Allocation

Use an arena for in-memory caching of the query result.Results are allocated in a typed arena and share the same lifetime as the TyCtxt.Use when: Query results contain references with 'tcx lifetime

cache_on_disk_if - Disk Caching

Cache the query result to disk if the condition evaluates to true.

query mir_built(key: LocalDefId) -> &'tcx mir::Body<'tcx> {
    cache_on_disk_if { true }
}

Enables incremental compilation by persisting results between runs.

cycle_* - Cycle Handling

Controls behavior when a dependency cycle is detected:

cycle_fatal - Abort with fatal error (default)
cycle_delay_bug - Emit delayed bug instead of aborting
cycle_stash - Stash error for later handling

Example: Type checking can encounter cycles in recursive types

no_hash - Skip Hashing

Do not hash the query result for incremental compilation.Instead, mark as dirty if the query is recomputed.Use when: Results are not stable across compilations

anon - Anonymous Queries

Make the query anonymous in the dependency graph (no dep node created).Use when: Query is internal and doesn’t need tracking

eval_always - Always Evaluate

Always evaluate the query, ignoring dependencies and cached results.Use when: Query has side effects or depends on external state

depth_limit - Recursion Limit

Impose a recursion depth limit to prevent stack overflows.Use when: Query can recurse deeply (e.g., trait resolution)

separate_provide_extern - Separate Providers

Use separate provider functions for local and external crates.Allows different implementations for current crate vs dependencies.

feedable - External Input

Allow the query result to be “fed” from another query.Enables setting query results externally without running the provider.

Major Query Categories

The compiler has 318 queries organized by purpose:

Parsing and AST (10+ queries)

AST and Parsing Queries

early_lint_checks - Runs early lint checks on the ASTregistered_tools - Returns registered tool lints (clippy, rustfmt, etc.)resolutions - Returns name resolution resultsresolver_for_lowering_raw - Provides resolver data for AST loweringenv_var_os - Queries environment variables at compile timeThese queries process the raw source code and prepare for HIR generation.

HIR Queries (30+ queries)

HIR Construction and Access

hir_crate - Returns the complete HIR cratehir_crate_items - Returns all items in the cratehir_module_items - Returns items in a specific modulelocal_def_id_to_hir_id - Converts DefId to HirIdhir_owner_parent_q - Returns parent of HIR owneropt_hir_owner_nodes - Returns HIR nodes for an ownerhir_attr_map - Returns attribute map for HIR nodesThese queries provide access to the High-Level Intermediate Representation.

Type System Queries (80+ queries)

Type Queries

type_of - Computes the type of a definitiongenerics_of - Returns generic parameters of an itempredicates_of - Returns trait bounds and where clausestype_of_opaque - Computes concrete type of opaque typesitem_bounds - Returns bounds on associated typesexplicit_item_bounds - Returns explicitly written boundsconst_param_default - Returns default value for const parametersThese queries build and query the type system.

Trait and Impl Queries

trait_def - Returns trait definitiontrait_impls_of - Returns all implementations of a traitimpl_trait_header - Returns trait being implementedinherent_impls - Returns inherent implementations for a typeassociated_items - Returns associated items (methods, types, consts)These queries support trait resolution and method dispatch.

MIR Queries (40+ queries)

MIR Construction and Analysis

mir_keys - Returns all items that need MIRmir_built - Builds unoptimized MIR for a functionmir_const_qualif - Checks if MIR is const-qualifiablemir_promoted - Returns promoted constants from MIRmir_borrowck - Performs borrow checkingoptimized_mir - Returns optimized MIRmir_for_ctfe - Returns MIR for compile-time function evaluationThese queries build and optimize the Mid-level IR.

Const Evaluation Queries (20+ queries)

Compile-Time Evaluation

const_eval_global_id - Evaluates a constanteval_to_allocation_raw - Evaluates to raw memory allocationeval_to_const_value_raw - Evaluates to const valueeval_to_valtree - Evaluates to value tree representationThese queries handle constant evaluation at compile time.

Analysis Queries (50+ queries)

Whole-Crate Analysis

analysis - Main analysis query (runs type checking, etc.)lint_expectations - Tracks expected lintscheck_expectations - Verifies expected lints occurredprivacy_access_levels - Computes privacy/visibilityreachable_set - Computes reachable itemsentry_fn - Finds program entry pointstability_index - Builds stability attribute indexThese queries perform whole-crate analyses.

Codegen Queries (30+ queries)

Code Generation

collect_and_partition_mono_items - Monomorphizationcodegen_unit - Returns items in a codegen unitis_codegened_item - Checks if item needs codegencodegen_fn_attrs - Returns codegen attributesexported_symbols - Returns symbols to exportupstream_monomorphizations - Tracks cross-crate monomorphizationsThese queries support code generation and linking.

Metadata Queries (20+ queries)

Crate Metadata

crate_name - Returns crate namecrate_hash - Returns crate hash for incremental compilationextern_crate - Returns information about external cratesnative_libraries - Returns native libraries to linkforeign_modules - Returns foreign function modulesThese queries handle metadata and cross-crate information.

Incremental Compilation Queries (15+ queries)

Incremental Compilation Support

dep_graph - Dependency graph for incremental compilationfingerprint_style - How to fingerprint query resultstry_mark_green - Attempt to reuse cached resultsencode_query_results - Serialize query results to diskThese queries enable incremental compilation.

Query Execution Flow

Provider Functions

Providers implement the actual logic for queries:

pub struct Providers {
    pub type_of: fn(TyCtxt<'_>, DefId) -> Ty<'_>,
    pub generics_of: fn(TyCtxt<'_>, DefId) -> &Generics,
    // ... 318+ function pointers
}

Providers are registered during compiler initialization:

// From various crates:
rustc_passes::provide(&mut providers);
rustc_hir_analysis::provide(&mut providers);
rustc_mir_build::provide(&mut providers);
// etc.

Query Registration

Queries are defined using the rustc_queries! macro: Location: compiler/rustc_middle/src/queries.rs (6000+ lines) The macro generates:

Methods on TyCtxt for invoking queries
Caching infrastructure
Dependency tracking
Query vtables

Dependency Graph

The query system maintains a dependency graph: Benefits:

Tracks which queries depend on which
Enables incremental compilation
Detects dependency cycles
Provides query stack traces for debugging

Incremental Compilation

Queries enable fine-grained incremental compilation:

Hashing - Query keys and results are hashed
Change Detection - Compare hashes from previous compilation
Reuse - Reuse cached results if inputs haven’t changed
Recomputation - Only recompute affected queries

Disk Caching

Queries with cache_on_disk_if persist results:

query mir_built(key: LocalDefId) -> &'tcx mir::Body<'tcx> {
    desc { |tcx| "building MIR for `{}`", tcx.def_path_str(key) }
    cache_on_disk_if { true }
}

Results are stored in target/debug/incremental/.

Query Implementation Example

Definition

// In rustc_middle/src/queries.rs
query type_of(key: DefId) -> ty::EarlyBinder<'tcx, Ty<'tcx>> {
    desc { |tcx| "computing type of `{}`", tcx.def_path_str(key) }
    cache_on_disk_if { key.is_local() }
    separate_provide_extern
}

Provider Implementation

// In rustc_hir_analysis/src/collect.rs
fn type_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::EarlyBinder<'_, Ty<'_>> {
    // Compute and return the type
    match tcx.def_kind(def_id) {
        DefKind::Struct => compute_struct_type(tcx, def_id),
        DefKind::Fn => compute_fn_type(tcx, def_id),
        // ... other cases
    }
}

// Registration
pub fn provide(providers: &mut Providers) {
    providers.type_of = type_of;
    // ... other providers
}

Usage

let ty = tcx.type_of(def_id).instantiate_identity();

Query Debugging

Compiler Flags

-Z dump-dep-graph - Dump dependency graph
-Z query-dep-graph - Print query dependency graph
-Z time-passes - Show query execution time
-Z self-profile - Generate detailed profiling data

Query Stack Traces

When a query panics or cycles, the compiler prints the query stack:

query stack during panic:
#0 [type_of] computing type of `MyStruct`
#1 [check_item_type] checking item type `MyStruct`  
#2 [analysis] running analysis passes

Performance Considerations

Memoization

Queries are memoized - results are cached and reused.Benefit: Avoid redundant computationCost: Memory to store cached results

Granularity

Fine-grained queries (per-function) vs coarse-grained (whole-crate).Fine-grained:

Better incremental compilation
More cache overhead

Coarse-grained:

Less overhead
Worse incremental compilation

Parallel Execution

Queries can be evaluated in parallel if they don’t depend on each other.The query system automatically parallelizes independent work.

Compiler Passes

See how passes are implemented as queries

Compiler Crates

Learn about rustc_query_impl and rustc_middle

Further Reading: See the rustc dev guide for more details on the query system architecture.

Query System Statistics

Total Queries: 318+
Primary Definition File: compiler/rustc_middle/src/queries.rs (6000+ lines)
Implementation Crate: rustc_query_impl
Query Execution: Demand-driven with automatic memoization
Incremental Support: Query results can be cached to disk
Parallel Execution: Independent queries execute in parallel

Compiler Internals

Build System

Resources

Documentation Index

​Overview

​Architecture

​Core Components

rustc_middle::queries

rustc_query_impl

Providers

TyCtxt

​How Queries Work

​Basic Structure

​Invocation

​Query Modifiers

​Major Query Categories

​Parsing and AST (10+ queries)

​HIR Queries (30+ queries)

​Type System Queries (80+ queries)

​MIR Queries (40+ queries)

​Const Evaluation Queries (20+ queries)

​Analysis Queries (50+ queries)

​Codegen Queries (30+ queries)

​Metadata Queries (20+ queries)

​Incremental Compilation Queries (15+ queries)

​Query Execution Flow

​Provider Functions

​Query Registration

​Dependency Graph

​Incremental Compilation

​Disk Caching

​Query Implementation Example

​Definition

​Provider Implementation

​Usage

​Query Debugging

​Compiler Flags

​Query Stack Traces

​Performance Considerations

​Related Documentation

Compiler Passes

Compiler Crates

​Query System Statistics

Build docs developers (and LLMs) love

Overview

Architecture

Core Components

How Queries Work

Basic Structure

Invocation

Query Modifiers

Major Query Categories

Parsing and AST (10+ queries)

HIR Queries (30+ queries)

Type System Queries (80+ queries)

MIR Queries (40+ queries)

Const Evaluation Queries (20+ queries)

Analysis Queries (50+ queries)

Codegen Queries (30+ queries)

Metadata Queries (20+ queries)

Incremental Compilation Queries (15+ queries)

Query Execution Flow

Provider Functions

Query Registration

Dependency Graph

Incremental Compilation

Disk Caching

Query Implementation Example

Definition

Provider Implementation

Usage

Query Debugging

Compiler Flags

Query Stack Traces

Performance Considerations

Related Documentation

Query System Statistics