extremely slow type checking for constrained `TypeVars` and overloads on generic classes

I'm seeing extremely slow type-checking (around 1–2 minutes) for a very small, self-contained example involving constrained TypeVars, generic subclasses, and many overloads. The code produces no errors but mypy appears to spend a disproportionate amount of time resolving types.

The example defines two TypeVars constrained to ~15 Literal[str] values, a generic base class Pbase[T], several subclasses P1[T] … P14[T], and a generic class Fn[T1, T2] whose call method is overloaded to preserve the concrete subclass while transforming the type parameter. The full reproduction is below.

import typing as t


class LetterT:
    A = t.Literal["a"]
    B = t.Literal["b"]
    C = t.Literal["c"]
    D = t.Literal["d"]
    E = t.Literal["e"]
    F = t.Literal["f"]
    G = t.Literal["g"]
    H = t.Literal["h"]
    I = t.Literal["i"]
    J = t.Literal["j"]
    K = t.Literal["k"]
    L = t.Literal["l"]
    M = t.Literal["m"]
    N = t.Literal["n"]
    O = t.Literal["o"]


T1 = t.TypeVar(
    "T1",
    LetterT.A,
    LetterT.B,
    LetterT.C,
    LetterT.D,
    LetterT.E,
    LetterT.F,
    LetterT.G,
    LetterT.H,
    LetterT.I,
    LetterT.J,
    LetterT.K,
    LetterT.L,
    LetterT.M,
    LetterT.N,
    LetterT.O,
)
T2 = t.TypeVar(
    "T2",
    LetterT.A,
    LetterT.B,
    LetterT.C,
    LetterT.D,
    LetterT.E,
    LetterT.F,
    LetterT.G,
    LetterT.H,
    LetterT.I,
    LetterT.J,
    LetterT.K,
    LetterT.L,
    LetterT.M,
    LetterT.N,
    LetterT.O,
)


class Pbase(t.Generic[T1]):
    def __init__(self, v: T1) -> None:
        self.v: T1 = v


class P1(Pbase[T1]): ...
class P2(Pbase[T1]): ...
class P3(Pbase[T1]): ...
class P4(Pbase[T1]): ...
class P5(Pbase[T1]): ...
class P6(Pbase[T1]): ...
class P7(Pbase[T1]): ...
class P8(Pbase[T1]): ...
class P9(Pbase[T1]): ...
class P10(Pbase[T1]): ...
class P11(Pbase[T1]): ...
class P12(Pbase[T1]): ...
class P13(Pbase[T1]): ...
class P14(Pbase[T1]): ...


class Fn(t.Generic[T1, T2]):
    def __init__(self, a: T1, b: T2) -> None:
        self.a: T1 = a
        self.b: T2 = b

    @t.overload
    def call(self, p: P1[T1]) -> P1[T2]: ...
    @t.overload
    def call(self, p: P2[T1]) -> P2[T2]: ...
    @t.overload
    def call(self, p: P3[T1]) -> P3[T2]: ...
    @t.overload
    def call(self, p: P4[T1]) -> P4[T2]: ...
    @t.overload
    def call(self, p: P5[T1]) -> P5[T2]: ...
    @t.overload
    def call(self, p: P6[T1]) -> P6[T2]: ...
    @t.overload
    def call(self, p: P7[T1]) -> P7[T2]: ...
    @t.overload
    def call(self, p: P8[T1]) -> P8[T2]: ...
    @t.overload
    def call(self, p: P9[T1]) -> P9[T2]: ...
    @t.overload
    def call(self, p: P10[T1]) -> P10[T2]: ...
    @t.overload
    def call(self, p: P11[T1]) -> P11[T2]: ...
    @t.overload
    def call(self, p: P12[T1]) -> P12[T2]: ...
    @t.overload
    def call(self, p: P13[T1]) -> P13[T2]: ...
    @t.overload
    def call(self, p: P14[T1]) -> P14[T2]: ...

    def call(self, p):  # type: ignore[no-untyped-def]
        return Fn(self.b, p.v)

Running mypy repro.py --no-incremental consistently takes on the order of minutes on my machine. Removing any one of the following makes the runtime drop back to normal: the Literal constraints, the number of overloads, or the generic subclass hierarchy. This suggests a combinatorial blow-up in constraint solving and/or overload resolution. While using a bounded TypeVar instead of explicit constraints does improve performance, that is not a viable option in my case, as I need to parameterize these classes with precise, concrete Literal types rather than a common upper bound.

This is primarily a performance report; I'm not sure whether this is a known limitation or an opportunity for optimization, but the scaling behavior seems unexpectedly poor for such a small input.

I also attach the command I used to benchmark type checking time.

$ time mypy repro.py --no-incremental

real    1m44.220s
user    1m44.065s
sys     0m1.409s

Any ideas what might be the issue? How hard would it be to solve it?

Bắt đầu với ví dụ tự chứa repro.py và chạy mypy repro.py --no-incremental, ghi lại thời gian cơ sở. So sánh tác động của việc loại bỏ các ràng buộc Literal, các overload và hệ thống phân cấp lớp con generic để xác định tại đâu khả năng mở rộng trở nên quá mức; được xem là hoàn tất khi vẫn giữ nguyên hành vi định kiểu được báo cáo mà không bị chậm đi một cách không tương xứng.