Pathological performance on big list and dict literals

[Phlogistique]

• Are you reporting a bug, or opening a feature request?

Reporting a performance issue

• Please insert below the code you are checking with mypy,
  or a mock-up repro if the source is private. We would appreciate
  if you try to simplify your case to a minimal repro.

a.py:

a = [[[[[[[[[[[[[[[[[[[[
    0
]]]]]]]]]]]]]]]]]]]]

time mypy a.py

• What is the actual behavior/output?

Mypy type-checks the file successfully

• What is the behavior/output you expect?

Mypy takes an inordinate amount of time to type-check the file.

On my laptop, it takes 13 seconds with 18 levels of nesting, 32 seconds with 19 levels, and 9 minutes 53 seconds with 20 levels of nesting.

• What are the versions of mypy and Python you are using?
  Do you see the same issue after installing mypy from Git master?

I am able to reproduce the issue with mypy 0.750 and with mypy master.

• What are the mypy flags you are using? (For example --strict-optional)

No particular flags. I am able to reproduce the issue with and without --no-incremental.

• Additional notes:

I experience the same problem with dictionaries:

a = {0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:{0:
    0
}}}}}}}}}}}}}}}}}}}}

My actual use-case involves embedding JSON schemas in Python files, with mypy taking over a minute type-checking a single Python file.

[msullivan]

Yeah, ugh. This is a known behavior that stems from our algorithm for inferring type variables, where we, for each function invocation (which we treat dict and list literals as), we try two different methods of inferring type variables, and this involves a recursive check of the arguments.

This ends up with a pretty clear exponential algorithm. Still a little surprising that it goes from 32 seconds to 10 minutes--maybe it is triggering the GC a lot at that point?

Fixing this properly would require some major rewrites to the inference system but fixing it well enough to work could probably be done by tracking nesting levels and skipping one of the inference forms.