# How Pyrefly Handles Type Variable Resolution With Recursive Types

> Pyrefly resolves type variables in recursive types using a co-inductive solver. Discover how it prevents infinite loops and caches subset checks for efficient expansion.

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

---

**Pyrefly resolves type variables in recursive types using a co-inductive solver that creates fresh placeholder variables, caches subset checks to prevent infinite loops, and records final concrete types after expansion.**

Type variable resolution with recursive types is a critical challenge for modern Python type checkers. In the `facebook/pyrefly` repository, the solver phase of the three-stage pipeline (*exports → binding → solving*) implements a sophisticated co-inductive reasoning engine to handle self-referential constructs without stack overflow or exponential blow-up.

## Fresh Recursive Variables

When Pyrefly encounters a recursive type definition, the solver first generates a placeholder for the self-referential occurrence. In [`pyrefly/lib/solver/solver.rs`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/solver/solver.rs), the `fresh_recursive` method creates a new `Var` marked specifically as `Variable::Recursive`:

```rust
pub fn fresh_recursive(&self, uniques: &UniqueFactory) -> Var {
    let v = Var::new(uniques);
    self.variables.lock().insert_fresh(v, Variable::Recursive);
    v
}

```

This fresh variable acts as a temporary stand-in while the solver explores the recursive structure. By marking it as recursive upfront, Pyrefly ensures that subsequent operations recognize this variable as part of a potentially cyclic definition.

## Detecting Recursive Structures

Before performing expensive subset checks, Pyrefly determines whether a comparison might involve recursion. The `can_be_recursive` function in [`pyrefly/lib/solver/subset.rs`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/solver/subset.rs) identifies cases requiring co-inductive handling:

```rust
fn can_be_recursive(&self, t1: &Type, t2: &Type) -> bool {
    match (t1, t2) {
        // Protocols are the main source of recursion on the RHS
        (_, Type::ClassType(cls)) => self.type_order.is_protocol(cls.class_object()),
        (Type::UntypedAlias(_), _) | (_, Type::UntypedAlias(_)) => true,
        _ => false,
    }
}

```

This detection covers **recursive type aliases** (like `type Tree = int | list[Tree]`), **self-referential protocols** (classes inheriting from `Protocol` that reference themselves), and classes containing fields of their own type.

## Co-Inductive Caching

To prevent infinite loops during subset checking, Pyrefly maintains a cache of in-progress assumptions. When `can_be_recursive` returns true, the solver stores an `InProgress` entry in the subset cache before descending into the type structure. If the same `(got, want)` pair appears again during the check, the solver treats the pending entry as successful and continues.

From [`pyrefly/lib/solver/subset.rs`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/solver/subset.rs) (lines 1384-1402):

```rust
let cache_key = if self.can_be_recursive(got, want) {
    let key = (got.clone(), want.clone(), context_key);
    if let Some(entry) = self.subset_cache.get(&key) {
        return match entry {
            SubsetCacheEntry::InProgress => { self.coinductive_assumptions_used = true; Ok(()) }
            SubsetCacheEntry::Ok => Ok(()),
            SubsetCacheEntry::Err(err) => Err(err.clone()),
        };
    }
    Some(key)
} else {
    None
};

```

This **co-inductive assumption** allows the solver to assume that a recursive variable satisfies its own definition temporarily, then verify that assumption holds once the full structure is explored.

## Recording Resolved Types

After expanding a recursive type—unfolding unions, eliminating direct self-references, and re-unioning the remaining components—the solver commits the final concrete type. The `record_recursive` method in [`pyrefly/lib/solver/solver.rs`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/solver/solver.rs) updates the variable binding from `Variable::Recursive` to `Variable::Answer`:

```rust
pub fn record_recursive(&self, var: Var, ty: Type) -> Type {
    // … expand the type, drop any direct reference to `var`, then
    // unify the remaining possibilities and store them as the answer.
    let ty = unions(res, &self.heap);
    lock.update(var, Variable::Answer(ty.clone()));
    ty
}

```

This transformation converts the temporary placeholder into a concrete type that can be used in subsequent type checking operations.

## Rollback on Failure

If a recursive subset check ultimately fails, Pyrefly preserves soundness by removing the speculative cache entries inserted during the walk. This rollback mechanism, implemented in [`pyrefly/lib/solver/subset.rs`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/solver/subset.rs) (lines 1411-1429), ensures that failed assumptions do not pollute future checks. The solver cleans up `InProgress` entries and any intermediate results, allowing the type checker to backtrack cleanly.

## Practical Examples

The following examples demonstrate how Pyrefly handles type variable resolution with recursive types in real Python code.

### Recursive Type Alias

```python

# file: recursive_alias.py

from __future__ import annotations
from typing import List, Union

# Recursive alias: a tree of integers

Tree = Union[int, List[Tree]]

def sum_tree(t: Tree) -> int:
    if isinstance(t, int):
        return t
    return sum(sum_tree(x) for x in t)

```

Run the checker:

```bash
$ pyrefly check recursive_alias.py

```

Pyrefly expands the `Tree` alias recursively without stack overflow, correctly inferring that `sum_tree` returns `int` and that the recursive call accepts arguments of type `Tree`.

### Self-Referential Protocol

```python

# file: recursive_protocol.py

from typing import Protocol, runtime_checkable

@runtime_checkable
class Node(Protocol):
    def children(self) -> list[Node]: ...

def walk(node: Node) -> None:
    for child in node.children():
        walk(child)

```

Checker invocation:

```bash
$ pyrefly check recursive_protocol.py

```

The solver recognizes `Node` as a recursive protocol, creates a fresh recursive variable for the return type of `children()`, and validates that `walk` can be called recursively on any implementation of `Node`.

### Class with Recursive Field

```python

# file: recursive_class.py

from __future__ import annotations
from dataclasses import dataclass
from typing import List

@dataclass
class Node:
    children: List[Node]

def leaf_count(node: Node) -> int:
    return 1 + sum(leaf_count(c) for c in node.children)

```

Run:

```bash
$ pyrefly check recursive_class.py

```

Pyrefly resolves the type of `Node.children` by treating the self-reference as a recursive variable, then validates that `leaf_count` maintains the expected return type throughout the recursive descent.

## Summary

- **Fresh placeholders**: The `fresh_recursive` method in [`solver.rs`](https://github.com/facebook/pyrefly/blob/main/solver.rs) creates marked variables for recursive occurrences.
- **Recursion detection**: The `can_be_recursive` function in [`subset.rs`](https://github.com/facebook/pyrefly/blob/main/subset.rs) identifies when co-inductive reasoning is required.
- **Cycle prevention**: Co-inductive caching stores `InProgress` assumptions to avoid infinite loops during subset checks.
- **Final resolution**: The `record_recursive` method converts placeholders into concrete `Answer` types after expansion.
- **Soundness preservation**: Rollback mechanisms remove failed cache entries to prevent incorrect assumptions from persisting.

## Frequently Asked Questions

### What is co-inductive type checking?

Co-inductive type checking is a proof technique where the type checker assumes that a recursive type satisfies its definition while verifying that assumption, rather than attempting to fully expand the type upfront. Pyrefly uses this approach in [`subset.rs`](https://github.com/facebook/pyrefly/blob/main/subset.rs) to handle protocols and recursive aliases that would otherwise cause infinite descent.

### How does Pyrefly prevent stack overflow with recursive type aliases?

Pyrefly prevents stack overflow by using fresh recursive variables (`fresh_recursive` in [`solver.rs`](https://github.com/facebook/pyrefly/blob/main/solver.rs)) and caching subset checks (`subset_cache` in [`subset.rs`](https://github.com/facebook/pyrefly/blob/main/subset.rs)). When the solver encounters the same type pair twice, it returns success immediately using the `InProgress` cache entry, breaking the recursion cycle safely.

### Can Pyrefly handle mutually recursive types?

Yes, the same mechanisms that handle direct recursion—fresh variables, co-inductive caching, and rollback—apply to mutually recursive types. The solver treats each occurrence in the mutual cycle as a separate recursive variable and resolves them collectively during the final recording phase.

### Where does the actual type variable binding occur?

The binding occurs in [`pyrefly/lib/solver/solver.rs`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/solver/solver.rs) through the `record_recursive` method, which updates the variable state from `Variable::Recursive` to `Variable::Answer` with the concrete resolved type. This happens after the solver has fully expanded the recursive structure and eliminated self-references.