How Pyrefly Implements Type Narrowing and Refinement in Its Flow Type System

Pyrefly implements type narrowing and refinement by parsing guard expressions into atomic predicates (AtomicNarrowOp), composing them into logical trees (NarrowOp), and attaching these to per-variable flow state (FlowInfo) to refine types across control-flow branches.

Pyrefly, Meta's open-source Python type checker, achieves flow-sensitive type narrowing through a sophisticated system that tracks refinement constraints across the control-flow graph. The implementation captures conditional checks like isinstance(x, T), x is None, and len(x) == 3 as structured operations in pyrefly/lib/binding/narrow.rs, then propagates these constraints through variable scope tracking in pyrefly/lib/binding/scope.rs.

Primitive Narrowing Predicates in AtomicNarrowOp

At the core of Pyrefly's narrowing system lies the AtomicNarrowOp enum, defined in [pyrefly/lib/binding/narrow.rs](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/binding/narrow.rs). This enum represents every possible primitive check that can narrow a type:

pub enum AtomicNarrowOp {
    Is(Expr),               // `x is y`
    IsNot(Expr),            // `x is not y`
    Eq(Expr),               // `x == y`
    NotEq(Expr),            // `x != y`
    IsInstance(Expr, NarrowSource), // `isinstance(x, T)`
    HasAttr(Name),          // `hasattr(x, "attr")`
    LenEq(Expr),            // `len(x) == N`
    // … additional variants …
}

Each variant stores the AST node (Expr) supplying the constant part of the test. The IsInstance variant additionally records a NarrowSource distinguishing between call sites and pattern matches. This design allows the type checker to validate narrowing operations and generate precise hover information while maintaining the semantic origin of each refinement.

Logical Composition of Narrow Operations

Single primitive checks rarely exist in isolation. Pyrefly combines predicates using the NarrowOp enum, which supports logical composition through AND, OR, and negation operators:

// Example: `x is not None and isinstance(x, Foo)`
let op = NarrowOp::And(vec![
    NarrowOp::Atomic(None, AtomicNarrowOp::IsNot(expr_none)),
    NarrowOp::Atomic(None, AtomicNarrowOp::IsInstance(expr_foo, NarrowSource::Call)),
]);

The NarrowOp enum provides three variants:

• Atomic(Option<FacetSubject>, AtomicNarrowOp) – A primitive check that may apply to a variable or its facets (e.g., x.attr or x["key"])
• And(Vec<NarrowOp>) – Logical conjunction combining multiple constraints
• Or(Vec<NarrowOp>) – Logical disjunction for union-type narrowing

Several helper methods enable sophisticated tree manipulation:

• negate() – Inverts the predicate (used when processing not … branches or else clauses)
• for_subject() – Rewrites the tree to apply to a different subject variable (critical for pattern aliases like case Foo() as y:)
• rebase_onto_subject() – Projects a narrow onto an already-narrowed expression (e.g., turning self.a != "A" into a constraint on the projection self.a)

Flow-Sensitive State via FlowInfo and NarrowOps

Storing and retrieving narrows requires coordination between the binding analysis and flow tracking. During the binding phase, the NarrowOps struct maps variable names to their narrowing expressions:

pub struct NarrowOps(pub SmallMap<Name, (NarrowOp, TextRange)>);

This map provides essential operations:

• from_expr(builder, test_expr) – Parses guard expressions (the test part of if statements or match cases) into appropriate AtomicNarrowOp instances via the from_expr_helper function (approximately 800 lines of logic handling built-ins like len, type, getattr, and hasattr)
• and_all – Merges two NarrowOps maps with logical AND, inserting placeholders where names appear on only one side
• or_all – Merges maps with logical OR for control-flow joins
• strip_placeholders – Removes spurious placeholder operations after proving a pattern irrefutable

The actual flow-sensitive state lives in FlowInfo, defined in [pyrefly/lib/binding/scope.rs](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/binding/scope.rs):

struct FlowInfo {
    value: Option<FlowValue>,       // The most recent definition
    narrow: Option<FlowNarrow>,     // The most recent narrow tree
    narrow_depth: usize,           // Limit to prevent infinite recursion
    loop_prior: Idx<Key>,           // Approximation for loop variable analysis
}

When the analyzer encounters a definition, FlowInfo::updated_value creates a new state clearing previous narrows (since assignment invalidates earlier constraints). When encountering a narrow (e.g., an if guard), FlowInfo::updated_narrow preserves the existing value while attaching the new FlowNarrow pointing to the NarrowOp tree.

The Type Narrowing Pipeline

Consider this Python example demonstrating flow-sensitive refinement:

def f(x: object):
    if isinstance(x, str):
        reveal_type(x)   # -> str

    else:
        reveal_type(x)   # -> object

Pyrefly processes this through a six-stage pipeline:

1. Parse the guard expression – The from_expr_helper function recognizes isinstance(x, str) and creates AtomicNarrowOp::IsInstance(expr_str, Call)
2. Build the narrow tree – Wraps the atomic operation in NarrowOp::Atomic(None, …) and stores it in a temporary NarrowOps map
3. Update flow state – FlowInfo::updated_narrow records that variable x now carries a narrow pointing to the IsInstance operation
4. Apply in the positive branch – When analyzing the then branch, the solver queries FlowNarrow and treats x as str
5. Negate for the negative branch – On the else branch, the system applies NarrowOp::negate(), producing an IsNotInstance constraint that excludes str from the original object annotation
6. Merge at join points – If control flow reconverges, and_all or or_all combine the narrow maps from each branch, using placeholders to preserve soundness

This architecture supports complex scenarios including pattern-matching guards, length checks (len(x) == 3), attribute existence tests (hasattr(x, "y")), and custom user-defined type guards (TypeGuard, TypeIs).

Summary

• Primitive operations live in AtomicNarrowOp within binding/narrow.rs, capturing every possible type-check predicate from identity comparisons to isinstance calls
• Logical composition uses NarrowOp trees supporting AND, OR, and negation, with helper methods for subject rebasing and projection
• Flow tracking stores narrows per-variable via FlowInfo in binding/scope.rs, clearing narrows on assignment and updating them at conditional guards
• Guard parsing happens in NarrowOps::from_expr_helper, which recognizes built-in Python functions and translates them into atomic narrowing operations
• Branch handling applies negate() for else-clauses and merges narrow maps using and_all/or_all when control flow joins

Frequently Asked Questions

How does Pyrefly handle complex conditional expressions with multiple type checks?

Pyrefly composes multiple predicates using the NarrowOp::And and NarrowOp::Or variants. When analyzing an expression like x is not None and isinstance(x, Foo), the from_expr_helper function creates separate AtomicNarrowOp instances for each check, then combines them into a single NarrowOp::And tree. During control-flow analysis, these composite trees are attached to the variable's FlowInfo and refined by the solver.

What happens to type narrows when a variable is reassigned?

When the binding analyzer encounters a new assignment, it calls FlowInfo::updated_value, which creates a fresh FlowInfo instance preserving the new definition but clearing the previous narrow field. This invalidation ensures that refinements from previous branches do not incorrectly apply to the newly assigned value, maintaining soundness in the type system.

Where does Pyrefly implement the logic for builtin type narrowing functions like len() and hasattr()?

The recognition logic for built-in narrowing functions resides in the from_expr_helper function within pyrefly/lib/binding/narrow.rs. This approximately 800-line function special-cases calls to len, type, getattr, hasattr, and similar functions, translating them into appropriate AtomicNarrowOp variants such as LenEq or HasAttr based on the specific comparison pattern detected.

How does Pyrefly support type narrowing in pattern matching with aliases?

Pyrefly handles pattern aliases (e.g., case Foo() as y:) using the for_subject() method on NarrowOp. When a pattern match introduces a new variable name that references an already-narrowed expression, this method rewrites the entire narrow tree so that the constraints apply to the new variable. This allows the type refinement to propagate correctly to the aliased name while maintaining the original constraints.

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