How Pyrefly Performs Type Inference for Empty Containers: Placeholder Variables and Lazy Unification

Pyrefly represents empty lists and tuples as placeholder containers with unknown element types, deferring concrete type resolution until the container is actually used, at which point the placeholder is unified and pinned to the inferred element type.

When analyzing Python code, the facebook/pyrefly type checker must handle empty container literals like [] and () without immediate element type information. Instead of defaulting to overly broad types or throwing errors, Pyrefly employs a sophisticated placeholder variable system that tracks these containers through the binding phase and resolves them via unification in the solver. This approach ensures deterministic type inference for empty containers while maintaining type safety across the codebase.

Placeholder Creation on First Assignment

The process begins when the binder encounters a name being assigned to an empty container for the first time. Rather than inferring a concrete element type immediately, Pyrefly inserts a placeholder type variable.

Tracking First-Use in ensure_name_impl

In pyrefly/lib/binding/expr.rs, the ensure_name_impl function handles this initialization. According to the source comments at lines 20–24, the binder specifically "tracks first-use to get deterministic inference of placeholder types like empty list" by inserting a Var marked as a placeholder instead of a concrete type argument. This creates a provisional type such as list[Var] or tuple[Var] that acts as a stand-in until more information becomes available.

Binding Empty Container Literals

When the binder processes the actual literal expression, it distinguishes between empty and non-empty containers to determine whether to apply placeholder logic.

Distinguishing Empty from Non-Empty Containers

The helper function is_definitely_nonempty_iterable in pyrefly/lib/binding/stmt.rs (lines 104–110) performs this check by simply verifying !elts.is_empty(). For non-empty containers, the element type is inferred directly from the provided expressions. However, when the literal is empty, the binder skips concrete element inference and records the container with a placeholder variable, resulting in types like list[Var] or tuple[Var] that signal "unknown element type pending."

Unification and Pinning

The placeholder type remains provisional until the code provides concrete element information through subsequent assignments or method calls.

When the same variable appears in a context that supplies element types—such as x = [1, 2] or x.extend([3])—the solver unifies the placeholder Var with the concrete type (int in these examples). This unification propagates through the type graph, and the solver eventually pins the placeholder type to finalize the inference.

In pyrefly/lib/solver/solver.rs around line 596, the pin_placeholder_type function performs this final pinning operation, transforming the provisional list[Var] into a definitive list[int] once sufficient constraints have been collected.

Special Case Handling

While the placeholder mechanism handles general cases, Pyrefly includes specific logic for certain idiomatic Python patterns that require different treatment.

The __all__ Export List Exception

Python modules often use __all__ to define their public API. An empty list assigned to __all__ is considered Specified rather than Unresolvable, because an empty export list represents a valid, concrete declaration that the module exports nothing.

The test test_all_empty_list_is_specified in pyrefly/lib/export/definitions.rs (lines 73–84) verifies this behavior. When Pyrefly encounters __all__ = [], it treats the empty list as a concrete Specified entry with type list[str], avoiding the placeholder mechanism used for general empty containers.

Tensor Shape DSL Interpretation

Pyrefly's internal "shape DSL" for tensor type inference interprets empty list literals differently than standard Python code. In this domain-specific language, an empty list represents a dimension list rather than a generic container.

In pyrefly/crates/pyrefly_types/src/meta_shape_dsl.rs (lines 1560–1662), the infer_expr function handles this case separately from infer_list_elem_type (which asserts non-empty lists). For an empty literal, it returns DslType::List(Box::new(dim_type())), treating [] as a List[Dim] type suitable for shape specifications.

Code Examples in Practice

The following examples demonstrate how Pyrefly's placeholder mechanism operates in practice:

# Example 1 – Empty list, later gets a concrete type

x = []                     # ← placeholder list[?]

reveal_type(x)             # -> list[object]  (placeholder)

x = [1, 2, 3]              # concrete elements seen

reveal_type(x)             # -> list[int]    (placeholder pinned)

# Example 2 – Empty tuple, later gets a concrete type

t = ()                     # ← placeholder tuple[?]

reveal_type(t)             # -> tuple[()] (placeholder tuple)

t = (True, False)          # concrete elements

reveal_type(t)             # -> tuple[bool, bool]

# Example 3 – Empty __all__ export list is considered specified

__all__ = []               # → DunderAllKind::Specified, entries = []

reveal_type(__all__)       # -> list[str] (the expected export list type)

# Example 4 – Shape DSL empty list becomes a dimension list

# In a .pyrefly DSL file:

shape = []                 # → List[Dim] in the internal DSL

Summary

• Placeholder variables: Empty containers instantiate as list[Var] or tuple[Var] via ensure_name_impl in pyrefly/lib/binding/expr.rs, creating type variables marked as placeholders.
• Deferred binding: The is_definitely_nonempty_iterable check in pyrefly/lib/binding/stmt.rs (lines 104–110) skips concrete element inference for empty literals.
• Lazy unification: Placeholder types unify with concrete types when the container is actually used, then get pinned via pin_placeholder_type in pyrefly/lib/solver/solver.rs.
• Special-cased patterns: Empty __all__ lists are treated as concrete Specified exports in pyrefly/lib/export/definitions.rs, while empty lists in the shape DSL become List[Dim] types in pyrefly/crates/pyrefly_types/src/meta_shape_dsl.rs.

Frequently Asked Questions

How does Pyrefly's placeholder mechanism differ from other Python type checkers?

Many type checkers immediately assign list[Any] or list[object] to empty containers, losing type safety. According to the facebook/pyrefly source code, Pyrefly instead uses placeholder type variables that preserve the unknown element status until unification occurs, allowing for more precise inference when the container is eventually populated.

What happens if a placeholder container is never assigned concrete elements?

If an empty container remains unused or is only used in contexts that provide no element type constraints, the placeholder variable remains unbound until the solver pins it. In practice, this typically results in the placeholder being resolved to object or the tightest upper bound available from the usage context, though the specific fallback depends on the constraint set collected during analysis.

Why does Pyrefly treat __all__ differently from other empty lists?

The binder recognizes that __all__ serves a specific semantic purpose in Python modules. As implemented in pyrefly/lib/export/definitions.rs (lines 73–84), an empty __all__ explicitly declares that the module exports nothing, which is a valid concrete state rather than an unknown type. Therefore, it bypasses the placeholder mechanism and is immediately categorized as Specified with an empty entry list.

Does Pyrefly use the same placeholder approach for empty dictionaries and sets?

The analysis focuses on lists and tuples, but Pyrefly's architecture suggests similar placeholder mechanisms likely apply to other container types. The is_definitely_nonempty_iterable check in pyrefly/lib/binding/stmt.rs specifically handles iterable literals, while dictionaries and sets would follow analogous patterns in their respective binding logic, though they may utilize different placeholder variable implementations based on their key/value or element structure.

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