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

> Discover how Pyrefly's unique type solving engine, built in Rust, provides faster and more consistent Python type checking than other tools. See its groundbreaking performance.

- Repository: [Meta/pyrefly](https://github.com/facebook/pyrefly)
- Tags: deep-dive
- Published: 2026-05-21

---

**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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/alt/answers_solver.rs) file handles answer lookup and caching for this overload resolution process.

Consider this overloaded function:

```python
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`](https://github.com/facebook/pyrefly/blob/main/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:

```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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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.