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?

Inizia con l’esempio autonomo repro.py ed esegui mypy repro.py --no-incremental, registrando il tempo di riferimento. Confronta l’effetto della rimozione dei vincoli Literal, degli overload e della gerarchia di sottoclassi generiche per identificare dove la scalabilità diventa eccessiva; il lavoro è completato quando il comportamento di tipizzazione riportato viene preservato senza il rallentamento sproporzionato.