How Pyrefly's Type Solving Differs from Other Python Type Checkers

Pyrefly's type solving engine uses a hand-crafted constraint solver written in Rust that tracks overload residuals and bounds with gas-bounded recursion, delivering consistent results across CLI and IDE environments at speeds exceeding 1.8 million lines per second.

Pyrefly is Meta's open-source Python type checker built to handle massive codebases. Unlike traditional tools that rely on graph-based inference, Pyrefly's type solving implements a constraint-solving model that fundamentally changes how Python types are analyzed and resolved.

Constraint-Solving vs. Inference-Based Architectures

Traditional Python type checkers like MyPy and Pyright rely on graph-based inference that propagates type information through an AST via fixed-point iteration over dependency graphs. Pyrefly abandons this eager propagation model for a systematic constraint-solving approach.

Pyrefly's Hand-Crafted Constraint Solver

In pyrefly/lib/solver/solver.rs, the engine operates on a unified Type enum from the pyrefly_types crate. Rather than propagating types through the graph, the solver incrementally builds and simplifies constraints. The central loop repeatedly calls is_subset_eq to validate subtype relationships, using the partial order (⊆) defined in pyrefly/lib/solver/type_order.rs.

This separation of constraint generation from resolution allows Pyrefly to handle complex type relationships through systematic simplification. When new constraints appear, the solver merges them into existing bounds rather than re-running the entire analysis, enabling the sub-10 millisecond incremental rechecks observed in Meta's 20 million-line Python repository.

Variable Isolation and Bounds Management

Strict Module-Scoped Variable Tracking

Pyrefly enforces strict variable isolation through unique module-scoped identifiers. Each type variable receives a unique Var identifier that is strictly confined to its module through the VAR_LEAK constant guards.

This prevents cross-module variable leakage, a source of subtle unsoundness in other checkers where variables are often simple symbols without explicit isolation boundaries. The approach ensures that type variables from different modules cannot accidentally pollute each other's constraint sets during incremental updates.

Lazy Bounds Merging

The Bounds struct (lines 101-107 in solver.rs) stores lower and upper constraints per variable. Pyrefly merges these bounds lazily to avoid re-solving from scratch when files change. This contrasts with the eager recomputation typical of graph-based systems.

Advanced Resolution Features

Overload Residuals and Witness Tracking

Where other type checkers use first-match heuristics for overload resolution, Pyrefly implements overload residuals that enable precise branch pruning while maintaining backtracking capability.

In solver.rs, the OverloadBranchCapture struct (lines 138-142) captures each overload candidate, while OverloadResidualWitness (lines 145-150) maintains a witness hash for residual tracking. Rather than discarding rejected candidates immediately, Pyrefly residualizes them—preserving information about why a branch failed so the solver can prune impossible paths while retaining the ability to reconsider branches when new constraints emerge. The pyrefly/lib/alt/answers_solver.rs file handles answer lookup and caching for this overload resolution process.

Consider this overloaded function:

from typing import overload

@overload
def greet(name: str) -> str: ...

@overload
def greet(name: int) -> int: ...

def greet(name):
    return f"Hello {name}"

Pyrefly's solver captures both branches and their failure conditions, enabling precise overload-aware completions in IDEs that match the CLI's exact resolution logic.

Gas-Bounded Recursion Prevention

Pyrefly prevents infinite recursion and stack overflows through an explicit Gas budgeting system rather than relying on native call-stack limits. The solver initializes with INITIAL_GAS = Gas::new(200) and decrements this counter during deep subset checks. When the gas exhausts, the solver stops exploring that branch, guaranteeing termination even with pathological recursive type definitions. This contrasts with other checkers that depend on host language limits and can crash on deeply nested type expressions.

Memory and Performance Architecture

Lock-Free Data Structures and Arena Allocation

The architecture uses lock-free data structures to minimize overhead. The pyrefly_util::uniques::UniqueFactory and synchronization primitives from pyrefly_util::lock::{Mutex,RwLock} enable thread-safe constraint solving without garbage collection pauses.

Type storage uses pyrefly_types::heap::TypeHeap for arena-style allocation, keeping memory overhead low during incremental recomputation. This design avoids the per-AST-node heap allocation common in other checkers, which creates GC pressure and slows incremental updates.

Scale Performance

These architectural choices enable Pyrefly to type-check Meta's 20 million-line Python repository at speeds exceeding 1.8 million lines per second. The constraint-solving model, combined with efficient memory management, delivers sub-10 millisecond rechecks after file modifications.

Unified Developer Experience

Shared Solver for CLI and LSP

Pyrefly exposes the same solver through its Language Server Protocol (LSP) implementation in the tsp module. Unlike other tools that run simplified "fast path" analysis for IDEs, Pyrefly's solver.rs powers both command-line checks and editor features identically.

This guarantees that overload-aware completions, hover types, and diagnostics in your editor match exactly what pyrefly check reports. You can also access the solver programmatically in Rust:

use pyrefly::lib::solver::Solver;
use pyrefly::lib::types::Type;

let mut solver = Solver::new();
solver.add_module(parse_file("example.py"));
let results = solver.solve().expect("solving succeeded");
let greet_type = results.get(&"greet".to_string()).unwrap();

Running this Rust snippet yields the same overload resolution errors as the CLI, confirming identical behavior across interfaces.

Summary

• Constraint-solving model: Pyrefly uses a hand-crafted Rust solver with incremental constraint simplification in solver.rs rather than graph-based inference.
• Overload residuals: Systematic tracking via OverloadBranchCapture and OverloadResidualWitness enables precise pruning of impossible overload branches.
• Gas-bounded recursion: The Gas::new(200) counter prevents stack overflows through explicit budgeting in is_subset_eq checks.
• Strict variable isolation: Unique Var identifiers per module with VAR_LEAK guards prevent cross-module pollution.
• Unified implementation: The same solver powers both CLI checks and LSP features via the tsp module, ensuring consistent IDE and command-line results.
• Performance: Lock-free data structures and arena allocation enable >1.8 M LOC/s checking speeds.

Frequently Asked Questions

How does Pyrefly handle recursive type definitions without crashing?

Pyrefly uses a Gas budgeting system with INITIAL_GAS = Gas::new(200) to bound recursion depth during subset checks. Each recursive call to is_subset_eq consumes gas, and when the budget exhausts, the solver stops exploring that branch. This guarantees termination even with pathological recursive types, unlike other checkers that rely on native stack limits and may overflow.

Why does Pyrefly use constraint solving instead of type inference?

The constraint-solving model separates constraint generation from resolution, enabling lazy merging of Bounds (lines 101-107 in solver.rs) and incremental updates. This approach avoids the fixed-point iteration over dependency graphs used by MyPy and Pyright, allowing Pyrefly to recheck files in under 10 milliseconds and achieve speeds of 1.8 million LOC/s on massive codebases.

How does Pyrefly ensure IDE and CLI results are identical?

Pyrefly exposes the same Solver from pyrefly/lib/solver/solver.rs through both the command-line interface and the LSP implementation in the tsp module. Unlike tools that run simplified "fast path" analysis for editors, Pyrefly routes all requests through the full constraint solver, guaranteeing that overload resolution and type errors match exactly between your editor and CI pipeline.

What makes Pyrefly's overload resolution more precise than other checkers?

Pyrefly implements overload residuals using OverloadBranchCapture (lines 138-142) and OverloadResidualWitness (lines 145-150) to track why specific overload branches fail. Rather than using first-match heuristics that discard rejected candidates, Pyrefly residualizes them—preserving failure information for precise pruning while maintaining the ability to backtrack when new constraints emerge.

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