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?

Commencez par l’exemple autonome repro.py et exécutez mypy repro.py --no-incremental, en consignant le temps de référence. Comparez l’effet de la suppression des contraintes Literal, des surcharges et de la hiérarchie de sous-classes génériques afin d’identifier à partir de quel point la mise à l’échelle devient excessive ; le travail est considéré comme terminé si le comportement de typage rapporté est préservé sans le ralentissement disproportionné.