Mypy errors out for deeply nested dictionaries

[hima1701]

Bug Report
mypy fails on analyzing a deeply nested OrderedDict data file. My project contains huge test data files which are used for testing purposes. running mypy on few of the files just hangs up . When I tried to run it on playground, I got a 500 status.

To Reproduce

test data in this mypy playground fails with Error: Request failed with status code 500

Expected Behavior

type check the data

Actual Behavior

Error: Request failed with status code 500

Your Environment

• Mypy version used:1.0.0
• Mypy command-line flags: None
• Mypy configuration options from mypy.ini (and other config files):
• Python version used: 3.10

[Drache91]

This problem also applies to depply nested recursive types.

Example:

from typing import TypeVar, List

T = TypeVar('T')
R = List[T | 'R[T]']

a: R[int] = [[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]

One more nesting and it will trigger the 500 response from mypy playground.
This also applies to my localy running mypy (mypy-version 1.0.1, Python-version 3.11.2), where it gets seemingly exponantially slower with each nesting.

While giving a the Any type makes it a bit faster, it will still slow down with a deeper nesting and result in a 500 on the mypy playground with about two more nesting levels.

[vors]

Here is a simple repro. This is a regression tested on 1.3.0 compare to v0.780

I think it took 3 minutes to analyse this file.
I remember there was this commit e145ba8

maybe we regressed somewhere in analogous quadratic way

from collections import OrderedDict

def test_foo() -> None:
    type_json = OrderedDict(
        [
            (
                "type",
                (
                    "Dataclass",
                    OrderedDict(
                        [
                            ("dataclass_ref", {"import": ("B", "test_enum2")}),
                            (
                                "equivalent_struct",
                                {
                                    "type": (
                                        "Struct",
                                        OrderedDict(
                                            [
                                                (
                                                    "fields",
                                                    [
                                                        [
                                                            {"value": "b"},
                                                            {
                                                                "type": (
                                                                    "Enum",
                                                                    OrderedDict(
                                                                        [
                                                                            (
                                                                                "value_type",
                                                                                {
                                                                                    "type": (
                                                                                        "Integer",
                                                                                        None,
                                                                                    )
                                                                                },
                                                                            ),
                                                                            (
                                                                                "values_by_name",
                                                                                {
                                                                                    "value": {
                                                                                        "ONE": 1,
                                                                                        "TWO": 2,
                                                                                        "THREE": 3,
                                                                                    }
                                                                                },
                                                                            ),
                                                                        ]
                                                                    ),
                                                                )
                                                            },
                                                            {"value": None},
                                                        ],
                                                        [
                                                            {"value": "c"},
                                                            {
                                                                "type": (
                                                                    "Enum",
                                                                    OrderedDict(
                                                                        [
                                                                            (
                                                                                "value_type",
                                                                                {
                                                                                    "type": (
                                                                                        "Text",
                                                                                        None,
                                                                                    )
                                                                                },
                                                                            ),
                                                                            (
                                                                                "values_by_name",
                                                                                {
                                                                                    "value": {
                                                                                        "A": "A",
                                                                                        "B": "B",
                                                                                        "C": "C",
                                                                                    }
                                                                                },
                                                                            ),
                                                                        ]
                                                                    ),
                                                                )
                                                            },
                                                            {"value": None},
                                                        ],
                                                    ],
                                                )
                                            ]
                                        ),
                                    )
                                },
                            ),
                        ]
                    ),
                ),
            ),
            ("registry", {"Integer": [], "Enum": [], "Text": [], "Struct": [], "Dataclass": []}),
        ]
    )
    

[Pastromhaug]

I'm seeing the same thing. We have a codegened file containing a TypedDict for each of our DB tables. The file is is 4000 lines long, and the TypedDicts in the file reference each other a lot. When we import one of the dicts anywhere mypy just hangs forever. Pyright and pyre seem to work fine.