mypy 0.990 crashes with segmentation fault on hydra_zen due to recursive types

[rsokl]

Crash Report

Upgrading from mypy 0.982 to 0.990 leads to a segmentation fault when I run on a file that merely imports hydra_zen:

import hydra_zen

This appears to be related to hydra-zen's use of recursive types and mypy 0.990 enabling these by default. To confirm, I reverted to 0.982 and configured then enable_recursive_aliases = true and confirmed that this also produces a segmentation fault.

This is the recursive type that is creating the issue. Oddly, when I specifically remove Sequence["SupportedPrimitive"] from the union (comment out line 223), the issue goes away. I spent time trying to further isolate the culprit and create a minimal example, but I was unable to decouple the issue from hydra_zen.

Traceback

Segmentation fault

To Reproduce

rsokl@Maxwell:/tmp$ pip install hydra-zen==0.8.0 mypy==0.990
rsokl@Maxwell:/tmp$ echo "import hydra_zen" > foo.py
rsokl@Maxwell:/tmp/hydra-zen$ mypy foo.py
Segmentation fault

Your Environment

• Mypy version used: 0.990
• Mypy command-line flags: (None)
• Mypy configuration options from mypy.ini (and other config files): (None)
• Python version used: python-3.9.13-haa1d7c7_2
• Operating system and version: Ubuntu 20.04.4 LTS (GNU/Linux 5.10.102.1-microsoft-standard-WSL2 x86_64)

[JelleZijlstra]

cc @ilevkivskyi

[ilevkivskyi]

Hm, I have a possible fix for this

--- a/mypy/constraints.py
+++ b/mypy/constraints.py
@@ -177,7 +177,7 @@ def infer_constraints(template: Type, actual: Type, direction: int) -> list[Cons
         for (t, a) in reversed(TypeState.inferring)
     ):
         return []
-    if has_recursive_types(template):
+    if has_recursive_types(template) or isinstance(template, Instance):
         # This case requires special care because it may cause infinite recursion.
         if not has_type_vars(template):
             # Return early on an empty branch.

Now need to find a more compact repro for a regression test. Unfortunately, as with the previous crash I fixed, this will likely cause some performance hit. I will see if I can come up with something better, since this may affect performance of non-recursive types as well.

I can probably give a bit more context on all the crashes. There is a classic algorithm for recursive types subtyping, it is however at least quadratic in number of type components of the recursive type, plus it slows down non-recursive types as well. So I tried to play smart, like "why would we need to push trivial pairs like (int, str) on an assumption stack, right?" It turns out there are various unexpected corner cases that are hard to predict where my optimization breaks (e.g. str is a subclass of Sequence[str], this is what causes issues here).

[ilevkivskyi]

And here is a simple repro:

from typing import Sequence, TypeVar

T = TypeVar("T")
def foo(x: T) -> str:
    return "test"

Nested = str | Sequence[Nested]
x: Nested = foo(1)

[ilevkivskyi]

It turns out the above proposed fix doesn't cause any visible performance regression on self check #14038