# How Pyrefly Implements Type Narrowing and Refinement in Its Flow Type System > Discover how Pyrefly implements type narrowing and refinement in its flow type system. Learn about parsing guard expressions, composing predicates, and attaching flow state for precise type refinement across branches. - Repository: [Meta/pyrefly](https://github.com/facebook/pyrefly) - Tags: internals - Published: 2026-05-21 --- **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`](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/binding/narrow.rs), then propagates these constraints through variable scope tracking in [`pyrefly/lib/binding/scope.rs`](https://github.com/facebook/pyrefly/blob/main/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)](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/binding/narrow.rs). This enum represents every possible primitive check that can narrow a type: ```rust 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: ```rust // 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, AtomicNarrowOp)`** – A primitive check that may apply to a variable or its facets (e.g., `x.attr` or `x["key"]`) - **`And(Vec)`** – Logical conjunction combining multiple constraints - **`Or(Vec)`** – 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: ```rust pub struct NarrowOps(pub SmallMap); ``` 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)](https://github.com/facebook/pyrefly/blob/main/pyrefly/lib/binding/scope.rs): ```rust struct FlowInfo { value: Option, // The most recent definition narrow: Option, // The most recent narrow tree narrow_depth: usize, // Limit to prevent infinite recursion loop_prior: Idx, // 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: ```python 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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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`](https://github.com/facebook/pyrefly/blob/main/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.