How Pyrefly Handles Variance Inference for Generic Classes: A Deep Dive into the Algorithm

Pyrefly infers the variance of type parameters in generic classes through a three-phase constraint-solving process that analyzes usage patterns across class hierarchies, method signatures, and field definitions to determine whether each type variable is covariant, contravariant, invariant, or bivariant.

Variance inference automatically determines the substitutability relationships for generic types without explicit TypeVar declarations. In the Pyrefly type checker, this analysis is implemented in pyrefly/lib/alt/class/variance_inference.rs and operates through a sophisticated fix-point algorithm that propagates constraints until convergence.

The Three-Phase Variance Inference Process

Pyrefly splits variance inference into discrete phases, each implemented as specific functions within the variance_inference.rs module.

Phase 1: Building the Variance Environment

For each generic class C, Pyrefly initializes a VarianceEnv map that tracks the inference state for every type parameter. This environment stores:

• The inferred variance discovered during analysis
• Whether variance has been inferred yet for this type variable
• Any declared variance from explicit TypeVar(..., covariant=True) syntax

The initialization logic resides in initialize_environment and initialize_environment_impl (lines 57-84). This phase establishes the starting constraints before the iterative solving begins.

Phase 2: Monotonic Fix-Point Constraint Solving

Starting from the initial environment, Pyrefly executes a fix-point algorithm implemented in the fixpoint function (lines 24-63). The algorithm repeatedly walks the class hierarchy, fields, and method signatures, unioning new constraints into the current variance states using Variance::union.

Because the variance lattice has height 3—where Bivariant < {Covariant, Contravariant} < Invariant—the algorithm converges quickly. Each iteration refines the constraints until no new information can be discovered, guaranteeing termination due to the finite lattice height.

Phase 3: Producing the Final Variance Map

After convergence, compute_variance and compute_variance_env (lines 94-103) transform the environment into a final VarianceMap (mapping type variable names to their computed Variance values). If check_violations is enabled, Pyrefly performs additional validation by walking base classes deeply and methods shallowly to detect mismatches between declared and inferred variances.

How Pyrefly Analyzes Type Usage Patterns

The core variance inference logic examines specific syntactic positions where type variables appear, assigning appropriate variance constraints based on position polarity.

Recursive Type Descent and Callable Positions

The on_type visitor recursively descends into Type structures. For callable signatures, Pyrefly applies covariant constraints to return types and contravariant constraints to parameter types using Variance::inv().

When encountering ClassType arguments, Pyrefly zips them with the environment map. The effective variance for a type argument combines declared and inferred information:

effective_variance = status.specified_variance.unwrap_or(status.inferred_variance)

This logic appears in lines 92-100 of variance_inference.rs.

Base Class Traversal

Base classes are traversed at bivariant position, meaning their variances flow unchanged into the subclass (acting as the identity for compose). This treatment recognizes that inheritance relationships should not introduce additional constraints beyond those already present in the parent class definitions (lines 86-92).

Field Variance Constraints

Fields contribute variance constraints based on their mutability and visibility:

• Covariant constraints apply when the field is a callable or a private attribute (prefixed with _)
• Invariant constraints apply to mutable fields, forcing the entire class toward invariance when mutable attributes appear

This distinction appears in lines 15-20 of the implementation.

Method Signature Checking

Method bodies are intentionally not visited to prevent infinite recursion through nested callables. Instead, Pyrefly performs a shallow check of method signatures, examining only direct Quantified type variables. The check_method_shallow function (lines 57-84) handles this verification, ensuring that variance constraints from method parameters and return types are captured without descending into implementation details.

Practical Examples of Variance Inference

The following examples demonstrate how Pyrefly applies these rules to real Python code. Each can be checked using pyrefly check <filename>.py.

Covariance from Return Types

Type variables appearing only in return positions are inferred as covariant:

from typing import Sequence, Generic, TypeVar

T = TypeVar("T", infer_variance=True)

class MySeq(Generic[T], Sequence[T]):
    pass

# Valid: MySeq[float] is a subtype of MySeq[int] due to covariance

ok: MySeq[int] = MySeq[float]()

Contravariance from Parameter Types

Type variables appearing in method parameters infer as contravariant:

from typing import Generic, TypeVar

T = TypeVar("T", infer_variance=True)

class Handler(Generic[T]):
    def handle(self, value: T) -> None:
        pass

Here T appears contravariantly in the handle parameter, leading Pyrefly to infer Contravariant for the class.

Invariance from Mixed Usage

When a type variable appears in both covariant and contravariant positions, Variance::union promotes the result to Invariant:

from typing import Generic, TypeVar

T = TypeVar("T", infer_variance=True)

class Box(Generic[T]):
    def get(self) -> T: ...          # Covariant position

    def set(self, v: T) -> None: ... # Contravariant position

The union of covariant and contravariant constraints yields Invariant, preventing unsafe substitutions in either direction.

Key Implementation Files

Understanding variance inference requires familiarity with these specific modules:

• pyrefly/lib/alt/class/variance_inference.rs — Core algorithm containing VarianceMap, VarianceResult, environment construction, the fix-point loop, and violation checking via check_typevar (lines 31-45)
• pyrefly/lib/alt/solve.rs — Public entry points solve_variance_binding and solve_variance_check used by the type checker to compute variances for specific classes
• pyrefly/types/variance.rs — Definition of the Variance enum and lattice operations including union, compose, and inv
• pyrefly/lib/test/variance_inference.rs — Comprehensive test suite containing canonical examples including test_infer_variance_and_private_field

Summary

• Pyrefly implements variance inference through a three-phase algorithm: environment initialization, fix-point constraint solving, and variance map production
• The algorithm converges quickly due to the height-3 variance lattice (Bivariant → Covariant/Contravariant → Invariant)
• Type usage analysis applies covariant constraints to returns, contravariant to parameters, and invariant to mutable fields
• Method bodies are skipped during inference; only signatures are checked shallowly to prevent infinite recursion
• The Variance::union operation promotes type variables toward Invariant when contradictory constraints are detected
• Implementation spans variance_inference.rs, solve.rs, and the pyrefly_types crate's variance definitions

Frequently Asked Questions

How does Pyrefly handle mutable fields in variance inference?

Pyrefly treats mutable fields as invariant (lines 15-20 in variance_inference.rs). If a generic class contains a mutable attribute whose type involves a type variable T, the inference system forces T to Invariant regardless of other usage patterns. This safety measure prevents unsound substitutions that could allow type-unsafe mutations through the mutable field.

What is the difference between declared and inferred variance in Pyrefly?

Declared variance comes from explicit TypeVar declarations like TypeVar("T", covariant=True), while inferred variance is computed by analyzing how the type variable appears in class definitions. During analysis, effective_variance = status.specified_variance.unwrap_or(status.inferred_variance) (lines 92-100) gives priority to declared variance when present, but the violation checker can flag cases where declared variance conflicts with actual usage patterns.

Why does Pyrefly use a fix-point algorithm instead of single-pass inference?

Variance relationships in generic classes can be mutually recursive through base classes and nested type constructors. The fix-point algorithm in fixpoint (lines 24-63) handles these cycles by iteratively refining variance constraints until reaching a stable state. The monotonic nature of Variance::union guarantees convergence because the lattice has finite height (3 levels), ensuring the algorithm terminates with the most permissive variance that satisfies all constraints.

Where does Pyrefly report variance violation errors?

Variance violations are detected in check_typevar (lines 31-45 of variance_inference.rs) and reported during the deep base-class check and shallow method check phases. When check_violations is enabled, Pyrefly compares inferred variances against declared variances, producing diagnostic messages such as "Type variable T is covariant but is used in contravariant position" when usage contradicts declarations.

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