rust-lang/rust

Type system and trait solving

The Rust type system is implemented as a set of cooperating crates centered on rustc_middle. This page covers the shape of the type system; type checking (the algorithm that runs on user code) is in Type checking.

The center: `rustc_middle::ty`

Ty<'tcx> is the compiler's representation of a Rust type. It is a thin wrapper around Interned<'tcx, WithCachedTypeInfo<TyKind<'tcx>>> — i.e., types are interned in the TyCtxt's arena, and equality is pointer equality.

// Simplified
pub struct Ty<'tcx>(Interned<'tcx, WithCachedTypeInfo<TyKind<'tcx>>>);

pub enum TyKind<'tcx> {
    Bool,
    Char,
    Int(IntTy),
    Uint(UintTy),
    Float(FloatTy),
    Adt(AdtDef<'tcx>, GenericArgsRef<'tcx>),
    Foreign(DefId),
    Str,
    Array(Ty<'tcx>, ty::Const<'tcx>),
    Slice(Ty<'tcx>),
    RawPtr(TypeAndMut<'tcx>),
    Ref(Region<'tcx>, Ty<'tcx>, Mutability),
    FnDef(DefId, GenericArgsRef<'tcx>),
    FnPtr(Binder<'tcx, FnSig<'tcx>>),
    Dynamic(&'tcx List<PolyExistentialPredicate<'tcx>>, Region<'tcx>, DynKind),
    Closure(DefId, GenericArgsRef<'tcx>),
    Coroutine(DefId, GenericArgsRef<'tcx>),
    Never,
    Tuple(&'tcx List<Ty<'tcx>>),
    Alias(AliasKind, AliasTy<'tcx>), // associated types, opaque (RPIT/TAIT), inherent impls
    Param(ParamTy),    // generic type parameter
    Bound(DebruijnIndex, BoundTy),  // bound by `for<…>`
    Placeholder(PlaceholderType),
    Infer(InferTy),    // ?T inference variable
    Error(ErrorGuaranteed),
}

Find the real definition in compiler/rustc_middle/src/ty/sty.rs.

TyKind reflects every shape a Rust type can take, including inference-time scaffolding (Infer, Bound, Placeholder). Most algorithms work on Ty<'tcx> and pattern-match on ty.kind().

`TyCtxt<'tcx>`

TyCtxt is the central handle to global compiler state. It's Copy, threadable, and exposes:

Arenas for interning types, regions, consts, lists, …
The query system (tcx.type_of(def_id), tcx.predicates_of(def_id), …)
Session and command-line options
Hooks for codegen, lints, etc.

Almost every compiler function takes tcx: TyCtxt<'tcx> somewhere in its signature.

Generics: `GenericArgs`

A "substitution" — the actual arguments to a generic type/function — is a GenericArgsRef<'tcx>, an interned slice of GenericArg<'tcx>. Each element is one of:

A Ty<'tcx> (type argument)
A Region<'tcx> (lifetime argument)
A Const<'tcx> (const-generic argument)

When you see Adt(my_struct_def, args), the args carry [T = i32, 'a = '_, N = 4] for MyStruct::<i32, '_, 4>.

Lifetimes: `Region<'tcx>`

Region<'tcx> is also interned. Its kinds:

ReEarlyParam — a named lifetime parameter ('a on the impl/fn)
ReLateParam — a late-bound lifetime, promoted to a parameter
ReBound — bound by for<'a>
ReVar — inference variable ('?0)
RePlaceholder — universally-introduced for higher-ranked checks
ReStatic / ReErased — 'static and the codegen-time placeholder

The trait solver

Trait solving is the core algorithmic problem of Rust's type system. There are two solvers in tree:

Old solver in rustc_trait_selection — the historical implementation. Type-class-style proof search with confirmation, evaluation, and projection separated.
New solver in rustc_next_trait_solver + rustc_type_ir — a from-scratch reimplementation using a unified search algorithm with explicit canonicalization. Shipped behind -Znext-solver. Designed to handle coherence checking inside the solver and to be sound by construction.

The old solver is still default; the new solver is being incrementally enabled. Cross-cutting work that affects "trait selection" usually has to be done in both.

Type-system support crates

Crate	Role
`rustc_type_ir`	Generic type-system traits (`Interner`, `TypeFolder`, `TypeVisitor`) — abstract enough to be implemented by both rustc and tools
`rustc_type_ir_macros`	proc-macros for the above (e.g., `#[derive(TypeFoldable)]`)
`rustc_infer`	Inference engine: unification, constraint solving, region inference
`rustc_traits`	Glue exposing trait queries to the rest of the compiler
`rustc_ty_utils`	Provider implementations for many type-related queries (`type_of`, `predicates_of`, `fn_sig`)
`rustc_transmute`	Validity checking for `core::mem::transmute`

Inference

rustc_infer does Hindley-Milner-style unification with extensions for traits, regions, const generics, and higher-ranked types:

InferCtxt — a per-inference-session context that contains all inference variables
InferTy — placeholder for an unknown type (?T)
Region inference is bottom-up: collect outlives constraints, then solve them
Type inference is on-demand: variables are unified eagerly as constraints arrive
The unifier uses union-find tables (rustc_data_structures::unify) for O(α(n)) lookup

Folders, visitors, and `TypeFoldable`

To walk types and substitute generics, the compiler uses the visitor pattern via the TypeFolder and TypeVisitor traits, with TypeFoldable and TypeVisitable implementations on every type-tree-shaped struct (auto-derived by #[derive(TypeFoldable, TypeVisitable)]). This is how instantiate(args) works: a folder visits a type and replaces every Param with the corresponding argument.

Coherence

rustc_hir_analysis::coherence checks that no two impl blocks overlap. The "orphan rule" is enforced here. The new trait solver moves coherence into the solver itself for a cleaner design.

Const generics and CTFE

Const expressions in types ([T; N], MyStruct<T, const N: usize>) are evaluated through rustc_const_eval, the MIR interpreter. The boundary is conceptually clean — types reference Const<'tcx> values that may be Unevaluated, and queries demand-evaluate them — but in practice this area has been some of the trickiest design work in modern rustc.

See MIR for const-eval mechanics.

Entry points for modification

Adding a new TyKind variant — touches rustc_middle::ty::sty, rustc_type_ir, every TypeFoldable/TypeVisitable impl, the trait solver, codegen, pretty-printing, and serialization. Don't do this lightly.
Changing how generics flow through queries — the relevant query providers live in rustc_ty_utils
Trait-solver fixes — pick old or new solver depending on which is reproducing the bug
Inference improvements — rustc_infer, frequently in the relate / eq machinery
Region/borrow interactions — see also MIR / borrowck