How Pyrefly Handles Type Aliases and Recursive Resolution

Pyrefly resolves type aliases through a two-phase architecture that separates binding from solving, using TypeAliasData variants to defer recursive lookup until the solver phase where get_type_alias dereferences Ref pointers until reaching a concrete Value.

The facebook/pyrefly codebase implements Python type checking in Rust, requiring careful handling of forward references and cyclic definitions. Understanding how Pyrefly handles type aliases and their recursive resolution reveals the internal machinery that supports modern Python syntax like type Tree = int | list[Tree] while maintaining type safety.

Core Data Structures for Type Aliases

Pyrefly models type aliases in the pyrefly_types crate using three interconnected structures defined in crates/pyrefly_types/src/type_alias.rs.

The TypeAlias struct stores the alias name, its declaration style (PEP 695 type syntax versus legacy implicit or explicit forms), and the underlying type definition. When a type contains an alias, it uses the variant Type::TypeAlias(Box<TypeAliasData>) or Type::UntypedAlias for legacy untyped aliases.

The TypeAliasData enum distinguishes between two states:

• Value: Contains the actual TypeAlias definition when immediately available.
• Ref: Contains a TypeAliasRef used when the alias is encountered before its definition, enabling forward and recursive references.

The TypeAliasRef struct captures the reference metadata including the alias name, specialized type arguments (TArgs), the containing module, and a TypeAliasIndex that uniquely identifies the alias within the file.

Building the Alias Graph During Export and Binding

During the export phase, Pyrefly scans for type statements and legacy assignments that behave as aliases. For each discovery, it creates a TypeAlias value and registers a TypeAliasIndex in the module’s export table.

When the binder processes a name reference, it consults the export table:

• If the name resolves to a Value, the binder immediately substitutes alias.as_type() into the AST.
• If the name resolves to a Ref, the binder records a TypeAliasRef carrying the index and any type arguments without immediate substitution.

This separation allows the binder to construct forward references without requiring complete definitions upfront, deferring full resolution to the solving phase.

Recursive Resolution in the Solver

The solving phase, located in pyrefly/lib/alt, operates on the normalized type graph. The key routine solve::untype_alias in pyrefly/lib/alt/answers_solver.rs (lines 2944-2960) handles the dereferencing logic.

For a TypeAliasData::Value, the solver clones the stored type:

TypeAliasData::Value(ta) => Arc::new(ta.clone())

For a TypeAliasData::Ref, the solver calls get_type_alias to look up the target by its TypeAliasIndex, retrieves that target’s value, and substitutes any stored type arguments. Because the target may itself be a Ref, the function recurses naturally until reaching a concrete Value:

TypeAliasData::Ref(r) => {
    let alias = self.get_type_alias(r);   // resolve the index
    // substitute args and recurse if needed
}

The subset logic in pyrefly/lib/solver/subset.rs also inspects aliases using the helper as_type_alias (lines 66-78), which extracts TypeAliasData from both Type::TypeAlias and Type::Forall variants to perform structural comparisons.

LSP Protocol Integration

When serializing types for the Language Server Protocol, pyrefly/lib/tsp/type_conversion.rs (lines 30-36) preserves alias provenance. The conversion logic checks if a PyreflyType is an alias:

PyreflyType::TypeAlias(ta) | PyreflyType::UntypedAlias(ta) => match ta.as_ref() {
    TypeAliasData::Value(alias) => self.convert(&alias.as_type()),
    TypeAliasData::Ref(r) => builtin(r.name.as_str()),
},

For Value variants, it emits the concrete underlying type; for Ref variants, it emits the alias name. This allows editors to display meaningful alias names while internal analysis uses the resolved types.

Cycle Detection and Safety Mechanisms

Pyrefly permits recursive aliases like type X = list[X] but guards against infinite loops. The solver tracks visited TypeAliasIndex values using an internal type-alias heap. If resolution encounters a cycle without reaching a terminating concrete type, it produces Type::any_error() to allow analysis to continue safely while reporting the error.

Practical Code Examples

The following examples demonstrate the alias resolution pipeline.

Simple Type Alias

# test_alias.py

type MyInt = int

def foo(x: MyInt) -> MyInt:
    return x

When querying this module, Pyrefly registers MyInt as a Value variant containing int. The binder records the name, and solver queries return the underlying int type immediately.

Recursive Alias

# rec_alias.py

type Tree = int | list[Tree]

def height(t: Tree) -> int:
    ...

The exporter creates a TypeAlias for Tree containing a union that references Tree via a Ref variant. During solving, get_type_alias detects the recursion, substitutes the partially resolved type, and yields a finitely expanded representation such as int | list[int | list[...]] with appropriate recursion limits.

Generic Alias

# generic_alias.py

type Pair[T, U] = tuple[T, U]

def swap(p: Pair[int, str]) -> Pair[str, int]:
    ...

Here the TypeAliasRef stores the arguments [int, str]. The solver retrieves the Pair definition tuple[T, U] and performs substitution, resolving the return type internally to tuple[str, int] while preserving the alias name for display purposes.

Summary

• Pyrefly uses TypeAlias, TypeAliasData, and TypeAliasRef in crates/pyrefly_types/src/type_alias.rs to represent aliases with support for forward references.
• The binder creates Ref variants for unresolved aliases and Value variants for immediate definitions, storing indices in module export tables.
• The solver resolves Ref pointers recursively via get_type_alias in pyrefly/lib/alt/answers_solver.rs, substituting type arguments until reaching a concrete Value.
• Cycle detection prevents infinite recursion by tracking visited indices and falling back to Type::any_error() for malformed cycles.
• The TSP protocol converter in pyrefly/lib/tsp/type_conversion.rs preserves alias names for IDE display while using resolved types for analysis.

Frequently Asked Questions

How does Pyrefly represent recursive type aliases internally?

Pyrefly represents recursive aliases using the TypeAliasData::Ref variant, which stores a TypeAliasRef containing the index and type arguments rather than the full definition. This allows the alias definition to contain a reference to itself before the complete type is known. When the solver encounters this Ref, it looks up the target by index and recursively resolves it, naturally handling cycles by tracking visited indices.

What happens when the solver encounters a forward reference to a type alias?

When the solver encounters a forward reference, it finds a TypeAliasData::Ref rather than a Value. It calls get_type_alias to fetch the target definition using the stored TypeAliasIndex, applies any stored type arguments through substitution, and returns the concrete type. If the target itself contains a Ref, the function recurses until it reaches a Value variant containing the actual TypeAlias definition.

How does Pyrefly prevent infinite loops with cyclic type aliases?

Pyrefly prevents infinite loops by tracking visited TypeAliasIndex values during resolution. The solver maintains an internal heap of visited aliases. If resolution attempts to visit an index already in the current recursion stack without finding a terminating concrete Value, the solver stops and returns Type::any_error(), allowing type checking to continue while reporting the cyclic definition error to the user.

Can Pyrefly handle generic type aliases with recursive bounds?

Yes, Pyrefly handles generic recursive aliases by storing the type arguments (TArgs) in the TypeAliasRef struct. During resolution in answers_solver.rs, the solver substitutes these arguments into the target alias's definition. For a recursive generic alias like type Container[T] = T | list[Container[T]], the solver substitutes T and then recursively resolves the resulting Ref, managing the generic parameters through each recursive step.

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