How Pyrefly Handles Type Variable Resolution With Recursive Types

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, the fresh_recursive method creates a new Var marked specifically as Variable::Recursive:

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 identifies cases requiring co-inductive handling:

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 (lines 1384-1402):

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 updates the variable binding from Variable::Recursive to Variable::Answer:

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 (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

# 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:

$ 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

# 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:

$ 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

# 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:

$ 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 creates marked variables for recursive occurrences.
• Recursion detection: The can_be_recursive function in 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 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) and caching subset checks (subset_cache in 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 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.

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