How Pyrefly's Three-Phase Type Checking Architecture Works

Pyrefly processes each Python module through a sequential three-phase pipeline—Export, Binding, and Solving—to discover exported symbols, build intermediate representations, and resolve types with placeholder-based recursion handling.

Pyrefly is Meta's experimental Python type checker designed for speed and IDE integration. Its three-phase type checking architecture processes modules atomically rather than incrementally, leveraging Rust's performance to handle large codebases efficiently. This design is documented in ARCHITECTURE.md and implemented across the pyrefly/lib/ source tree.

The Three-Phase Pipeline

Pyrefly's type checker operates on a module-centric model where each Python file moves through three distinct phases before the next module begins. This approach avoids fine-grained incremental recomputation and enables aggressive parallelization.

Phase 1: Export Discovery

The Export phase discovers what symbols a module exports and resolves all import * chains transitively. In pyrefly/lib/export/mod.rs, the type walker traverses the AST to collect def, class, and top-level assignments, building an export table that maps each name to its defining location.

This phase handles re-exports from other modules and propagates these tables transitively. By the end of this phase, Pyrefly knows exactly which module defines every imported name without re-parsing the entire import graph. The export table data structures live in pyrefly/lib/export/exports.rs.

Phase 2: Binding

The Binding phase translates concrete syntax into an intermediate representation that captures static scopes and flow-sensitive information. Located in pyrefly/lib/binding/, this phase creates definition (define) and use (use) keys for each statement.

For example, the assignment x: int = 4 generates a definition key recording the flow type Literal[4], while subsequent references create use keys pointing back to that definition. The binding graph stores class hierarchies, function signatures, and metadata needed for type solving, all using pure data structures without Rust lifetimes—just keys and values.

Phase 3: Solving

The Solving phase resolves type variables, propagates types across the program, and reports errors. Implemented in pyrefly/lib/alt/solve.rs, this phase consumes the binding graph and performs a fixed-point iteration over three sub-phases: overload resolution, generic handling, and residual finalization.

When the solver encounters unknown or recursive information, it introduces Type::Var placeholders. These placeholders are stored in the binding graph and unified to concrete types as more information becomes available. The final solved types are stored in pyrefly/lib/alt/answers.rs.

How the Phases Interact

The three phases form a strict pipeline with clean interfaces between them.

Export to Binding. The binding phase requires exact module references to create correct use entries. Rather than resolving imports on the fly, it consults the export table built in Phase 1, enabling O(1) lookups for any imported name.

Binding to Solving. The solver consumes the immutable binding graph and may request solved bindings from other modules. Because the export phase has already populated all cross-module links, the solver can fetch needed types without re-processing dependencies.

Handling Recursion. When the solver encounters mutually recursive definitions—such as a function referring to its own return type—it creates a fresh Type::Var placeholder. This mechanism allows Pyrefly to handle complex recursive patterns without getting stuck, unifying placeholders once the fixed-point iteration converges.

Module-Centric Processing Design

Unlike Roslyn or TypeScript, which solve individual identifiers incrementally, Pyrefly processes each module completely before moving to the next. This design keeps the implementation simple and leverages Rust's speed for raw, parallel module processing.

Consider this minimal example:

# example.py

x: int = 4
print(x)

The export phase records that x is exported. The binding phase creates keys such as:

define x@1 = 4: int
use    x@2 = x@1

The solving phase resolves x@1 to Literal[4], propagates that to the print call, and validates the program. Integration tests in pyrefly/lib/test/typeform.rs exercise this pipeline on realistic Python snippets.

Summary

• Export phase (pyrefly/lib/export/mod.rs) builds export tables and resolves import * chains transitively.
• Binding phase (pyrefly/lib/binding/) translates AST into a key-based intermediate representation with flow-sensitive types.
• Solving phase (pyrefly/lib/alt/solve.rs) uses fixed-point iteration and Type::Var placeholders to resolve recursive types and report errors.
• The architecture processes modules atomically rather than incrementally, enabling parallel execution and O(1) cross-module lookups.

Frequently Asked Questions

Why does Pyrefly use a three-phase architecture instead of single-pass?

Single-pass type checking struggles with forward references and complex import graphs. By separating export discovery from binding and solving, Pyrefly can resolve all module dependencies before type checking begins, eliminating the need for speculative parsing or multiple re-parses of the same file.

How does Pyrefly handle recursive type definitions across modules?

The solver introduces Type::Var placeholders when it encounters unknown or recursive types. These placeholders act as temporary variables in the binding graph, allowing the fixed-point iteration to proceed until all placeholders can be unified to concrete types, even across module boundaries.

What is the difference between the Binding and Solving phases?

The Binding phase is syntactic: it maps AST nodes to definition and use keys without interpreting type semantics. The Solving phase is semantic: it traverses the binding graph to infer actual types, resolve generics, and check compatibility. This separation allows the binder to remain simple while the solver handles complex type system features.

Where can I find the implementation of the export table?

The export table logic resides in pyrefly/lib/export/mod.rs with data structures defined in pyrefly/lib/export/exports.rs. These files handle the discovery of exported names, resolution of star imports, and transitive propagation of export information across the dependency graph.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}