Skip to content

Pyrefly hang / OOM during type checking of many conditional tuple appends #3743

Closed

Description

@QEDady

Describe the Bug

During type checking of code containing a sequence of conditional tuple additions, Pyrefly hangs indefinitely (CPU pinned at 100%) and eventually runs out of memory (OOM).

Reproduction

Checking the following Python code using pyrefly check hangs and times out:

class D0: pass
class D1: pass
class D2: pass
class D3: pass
# ... (up to D29)

def repro(conds: list[bool]):
  z = ()
  if conds[0]: z += (D0(),)
  if conds[1]: z += (D1(),)
  # ... (up to D29)
  return z

Root Cause

At each control-flow join, Pyrefly computes the union of the incoming types of z. Since each addition can either happen or not, this leads to an exponential combination of concrete tuple types in the union.

For $N$ conditional additions of distinct class types, the simplifier ends up processing a union containing up to $2^N$ concrete tuple variants. As the size of the union grows, the type simplifier stalls attempting to sort, de-duplicate, and check subtyping/intersections on this massive list, resulting in exponential $O(2^N)$ CPU time and memory exhaustion.

Proposed Fix

A suggested solution is to widen/collapse wide tuple unions during type simplification.
If a union contains more than a threshold (e.g., 8) of tuple variants, we collapse them into a single unbounded tuple variant:
tuple[E, ...]
where E is the union of all element types extracted from the constituent tuples.

For example, the union of concrete tuples:
tuple[D0] | tuple[D0, D1] | tuple[D1, D2] | ...
will be collapsed to:
tuple[D0 | D1 | D2 | ..., ...]

This is a sound over-approximation that bounds the type complexity at control-flow joins to $O(N)$ instead of $O(2^N)$. I have an implementation ready for this fix and will be sending a PR shortly. Let me know what you think of this idea or if you have any feedback on the threshold choice!

Sandbox Link

No response

(Only applicable for extension issues) IDE Information

No response

Activity

  1. added this to the v1.1 milestone on Jun 10, 2026
  2. mikeleppane commented on Jun 11, 2026

    @mikeleppane
    Contributor

    I can take this.

  3. yangdanny97 commented on Jun 11, 2026

    @yangdanny97
    Collaborator

    @mikeleppane there's already an in-progress PR for this

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

Type

Projects

No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions