Heavily nested structures are very slow to proceed

[yedpodtrzitko]

Hi, the dictionary below takes more than 30s to be processed. If the codebase contains more of such structures, it takes painfully long time to check it.

For now we use #3789 as a workaround to skip such slow parts.

Cheers, yed_

testing env: MB Pro 2013 Python 3.6 Mypy 0.521

testing file:

input = {
    'body': {
        'token': {
            'type': 'string',
            'required': False
        },
        'payloads': {
            'type': 'list',
            'required': True,
            'schema': {
                'type': 'dict',
                'schema': {
                    'message': {
                        'type': 'string',
                        'required': True
                    },
                    'notification': {
                        'type': 'dict',
                        'required': True,
                        'schema': {
                            'body': {
                                'type': 'dict',
                                'schema': {
                                    'type': {
                                        'type': 'string',
                                        'required': True
                                    },
                                    'data': {
                                        'type': 'dict',
                                        'required': True,
                                        'schema': {
                                            'bid': {
                                                'type': 'string',
                                                'required': False
                                            },
                                            'url': {
                                                'type': 'string',
                                                'required': False
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

[gvanrossum]

Wow. Confirmed -- on my Mac it takes 21s to process that file.

[refi64]

I wonder if this is somehow similar to:

https://spin.atomicobject.com/2016/04/26/swift-long-compile-time/

[refi64]

(I mean algorithm-wise.)

[ilevkivskyi]

It looks like we have two problems here. This code typechecks quickly:

def f(x: int) -> int:
    return x

y = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1))))))))))))))))))

while this takes around 41 seconds on my desktop:

@overload
def f(x: str) -> str: ...
@overload
def f(x: int) -> int: ...
def f(x):
    return x

y = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1))))))))))))))))))

Independently, this takes even more, around 1 minute 12 seconds:

T = TypeVar('T')
def f(x: T) -> T:
    return x

y = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1))))))))))))))))))

Taking into account that dict translates into an overloaded generic function, it looks like both problems combine in the original example.

[JukkaL]

Yeah, there clearly are various scenarios in which type checking is exponential in time. This is basically a known problem, but I doubt anybody has done a careful analysis of potential sources of exponential behavior. A potential simple fix is to use caching for the inferred type of an expression. I think that the tuple (identity of an expression, type context) could be used as a cache key, as long as as the cache is cleared at certain points -- for example, after leaving a scope or after each statement. I'm not 100% sure though.

[hauntsaninja]

The example in the original report is fixed by #9477