microsoft / microsoft/pyright

Recursive TypeAlias expansion causes non-terminating single-core CPU saturation

Open
#11,316 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
15.6k
Forks
1.8k
Avg merge
12h 13m
Merged PRs (30d)
52

Description

## Steps to reproduce

Run the following command:

`pyright main.py`

the `main.py` file:

```python
from __future__ import annotations

from typing import TYPE_CHECKING, Generic, TypeAlias, TypeVar, cast

class LeafA: ...
class LeafB: ...
class LeafC: ...
class LeafD: ...

L1 = TypeVar("L1")
L2 = TypeVar("L2")
R1 = TypeVar("R1")
R2 = TypeVar("R2")

class Branch(Generic[L1, L2, R1, R2]): ...

A0: TypeAlias = LeafA
B0: TypeAlias = LeafB
C0: TypeAlias = LeafC
D0: TypeAlias = LeafD

A1: TypeAlias = Branch[A0, B0, C0, D0]
B1: TypeAlias = Branch[B0, C0, D0, A0]
C1: TypeAlias = Branch[C0, D0, A0, B0]
D1: TypeAlias = Branch[D0, A0, B0, C0]

A2: TypeAlias = Branch[A1, B1, C1, D1]
B2: TypeAlias = Branch[B1, C1, D1, A1]
C2: TypeAlias = Branch[C1, D1, A1, B1]
D2: TypeAlias = Branch[D1, A1, B1, C1]

A3: TypeAlias = Branch[A2, B2, C2, D2]
B3: TypeAlias = Branch[B2, C2, D2, A2]
C3: TypeAlias = Branch[C2, D2, A2, B2]
D3: TypeAlias = Branch[D2, A2, B2, C2]

A4: TypeAlias = Branch[A3, B3, C3, D3]
B4: TypeAlias = Branch[B3, C3, D3, A3]
C4: TypeAlias = Branch[C3, D3, A3, B3]
D4: TypeAlias = Branch[D3, A3, B3, C3]

A5: TypeAlias = Branch[A4, B4, C4, D4]
B5: TypeAlias = Branch[B4, C4, D4, A4]
C5: TypeAlias = Branch[C4, D4, A4, B4]
D5: TypeAlias = Branch[D4, A4, B4, C4]

A6: TypeAlias = Branch[A5, B5, C5, D5]
B6: TypeAlias = Branch[B5, C5, D5, A5]
C6: TypeAlias = Branch[C5, D5, A5, B5]
D6: TypeAlias = Branch[D5, A5, B5, C5]

A7: TypeAlias = Branch[A6, B6, C6, D6]
B7: TypeAlias = Branch[B6, C6, D6, A6]
C7: TypeAlias = Branch[C6, D6, A6, B6]
D7: TypeAlias = Branch[D6, A6, B6, C6]

A8: TypeAlias = Branch[A7, B7, C7, D7]
B8: TypeAlias = Branch[B7, C7, D7, A7]
C8: TypeAlias = Branch[C7, D7, A7, B7]
D8: TypeAlias = Branch[D7, A7, B7, C7]

A9: TypeAlias = Branch[A8, B8, C8, D8]
B9: TypeAlias = Branch[B8, C8, D8, A8]
C9: TypeAlias = Branch[C8, D8, A8, B8]
D9: TypeAlias = Branch[D8, A8, B8, C8]

A10: TypeAlias = Branch[A9, B9, C9, D9]
B10: TypeAlias = Branch[B9, C9, D9, A9]
C10: TypeAlias = Branch[C9, D9, A9, B9]
D10: TypeAlias = Branch[D9, A9, B9, C9]

A11: TypeAlias = Branch[A10, B10, C10, D10]
B11: TypeAlias = Branch[B10, C10, D10, A10]
C11: TypeAlias = Branch[C10, D10, A10, B10]
D11: TypeAlias = Branch[D10, A10, B10, C10]

A12: TypeAlias = Branch[A11, B11, C11, D11]
B12: TypeAlias = Branch[B11, C11, D11, A11]
C12: TypeAlias = Branch[C11, D11, A11, B11]
D12: TypeAlias = Branch[D11, A11, B11, C11]

A13: TypeAlias = Branch[A12, B12, C12, D12]
B13: TypeAlias = Branch[B12, C12, D12, A12]
C13: TypeAlias = Branch[C12, D12, A12, B12]
D13: TypeAlias = Branch[D12, A12, B12, C12]

A14: TypeAlias = Branch[A13, B13, C13, D13]
B14: TypeAlias = Branch[B13, C13, D13, A13]
C14: TypeAlias = Branch[C13, D13, A13, B13]
D14: TypeAlias = Branch[D13, A13, B13, C13]

A15: TypeAlias = Branch[A14, B14, C14, D14]
B15: TypeAlias = Branch[B14, C14, D14, A14]
C15: TypeAlias = Branch[C14, D14, A14, B14]
D15: TypeAlias = Branch[D14, A14, B14, C14]

ResultType: TypeAlias = A15

def force(x: ResultType) -> None:
reveal_type(x)

if TYPE_CHECKING:
force(cast(ResultType, None))
```

## Observed behavior

With N=4, pyright completes in under a second. With N=15, it never terminates and saturates a single CPU core at 100%. Each level references 4 aliases from the previous level, so the type tree grows as O(4^N) — at N=15 this is ~10^9 nodes, eagerly expanded without memoization.

Since pyright is used as analysis engine in VS Code, opening a file containing this pattern may causes the Pylance language server to saturate one CPU core indefinitely.

Contributor guide

Open the contributing guide

Research direction

Start by running `pyright main.py` with the reproducer in the issue and inspect the type-alias expansion path responsible for eagerly building the recursive structure. Done means the command terminates for the provided example without indefinite single-core saturation, while preserving the expected type-analysis behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
devtools
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.