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

[caomingpei]

Steps to reproduce

Run the following command:

mypy main.py

the main.py file:

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, mypy 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.