Repository navigation
extremely slow type checking for constrained TypeVars and overloads on generic classes #20439
Description
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.409sAny ideas what might be the issue? How hard would it be to solve it?
Activity
A5rocks commentedon Dec 18, 2025
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 commentedon Dec 19, 2025
Thanks for the great repro! Looks like the slowdown is when checking if any of the overloads overlap
hauntsaninja commentedon Dec 19, 2025
Something like this will fix and might not be too bad:
cc @ilevkivskyi for advice as author of #17392
A5rocks commentedon Dec 19, 2025
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 commentedon Dec 20, 2025
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, likeperf-limitedor similar).quczer commentedon Dec 22, 2025
Just to clarify, the original code in this example was not generated. I’m happy to explain the rationale behind this construct, and there may be a way to rewrite it so that it works efficiently with the current version of
mypy. However, that discussion seems out of scope for this issue, and I’d prefer not to dilute the focus here. Would it be better to raise this elsewhere? If so, where would you recommend?quczer commentedon Jan 22, 2026
Hi @A5rocks @hauntsaninja @ilevkivskyi,
are there any plans to address this issue? Do you have a sense of whether it might be fixed in the near future?
ilevkivskyi commentedon Jan 22, 2026
It is hard to tell. It is relatively high on my personal list of priorities, but there are a lot of things going on now. I would guess on order of few weeks to few months (but no promises).