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?

从自包含的 repro.py 示例开始，运行 mypy repro.py --no-incremental，记录基准耗时。比较移除 Literal 约束、重载和泛型子类层次结构的影响，以确定从哪里开始扩展会变得过度；在保留报告中的类型检查行为且没有不成比例的变慢时，即视为完成。