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

[quczer]

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?

[A5rocks]

Constrained typevars are unfortunately impossible to type check quickly :/

We run a type check for every possible thing they could be (in this case that would mean type checking the function like 15^2 times). I guess we can add a special case to avoid doing that for overloads? I don't know...

[hauntsaninja]

Thanks for the great repro! Looks like the slowdown is when checking if any of the overloads overlap

[hauntsaninja]

Something like this will fix and might not be too bad:

--- a/mypy/checker.py
+++ b/mypy/checker.py
@@ -8726,7 +8726,10 @@ def expand_callable_variants(c: CallableType) -> list[CallableType]:
     tvar_values = []
     for tvar in c.variables:
         if isinstance(tvar, TypeVarType) and tvar.values:
-            tvar_values.append(tvar.values)
+            if len(tvar.values) < 5:
+                tvar_values.append(tvar.values)
+            else:
+                tvar_values.append([join.join_type_list(tvar.values)])
         else:
             tvar_values.append([tvar.upper_bound])

cc @ilevkivskyi for advice as author of #17392

[A5rocks]

I've been tempted by that before, but note that it isn't the same behavior.

However, maybe it's strictly more strict? I'm not quite sure.

[ilevkivskyi]

I think this may be the same problem that is causing nipunn1313/mypy-protobuf#707. Unfortunately neither a join nor a union of values are valid in this context. I think the only possible thing to do here is to generalize #15865 to account for this: instead of limiting number of overload variants we need to limit the total number of expanded variants (and probably make the limit a bit larger, like 200).

Most of this is probably from generated code. Then the code generator can acknowledge responsibility for correctness e.g. by adding a # type: ignore (btw maybe it is worth adding a new error code for this and too many unions situations, like perf-limited or similar).