Crash in lambda expression as generic argument

[ilevkivskyi]

This test crashes on current master (and causes troubles internally):

[case testFilterIn]
from typing import List, TypeVar, Callable

T = TypeVar('T')
def filter(f: Callable[[T], bool], it: List[T]) -> List[T]: ...

xs: List[int]
filter(lambda x: x in [1, 2] and bool(), [3, 4])
[builtins fixtures/list.pyi]

with a traceback that ends in

  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 942, in check_callable_call
    callee, args, arg_kinds, formal_to_actual, context)
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 1145, in infer_function_type_arguments
    callee_type, args, arg_kinds, formal_to_actual)
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 1043, in infer_arg_types_in_context
    res[ai] = self.accept(args[ai], callee.arg_types[i])
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 3723, in accept
    typ = node.accept(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/nodes.py", line 1852, in accept
    return visitor.visit_lambda_expr(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 3334, in visit_lambda_expr
    self.chk.check_func_item(e, type_override=type_override)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 790, in check_func_item
    self.check_func_def(defn, typ, name)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 973, in check_func_def
    self.accept(item.body)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 399, in accept
    stmt.accept(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/nodes.py", line 1004, in accept
    return visitor.visit_block(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 1970, in visit_block
    self.accept(s)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 399, in accept
    stmt.accept(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/nodes.py", line 1140, in accept
    return visitor.visit_return_stmt(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 3090, in visit_return_stmt
    self.check_return_stmt(s)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 3123, in check_return_stmt
    s.expr, return_type, allow_none_return=allow_none_func_call))
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 3723, in accept
    typ = node.accept(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/nodes.py", line 1736, in accept
    return visitor.visit_op_expr(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 2077, in visit_op_expr
    return self.check_boolean_op(e, e)
  File "/Users/ilevkivskyi/src/mypy/mypy/checkexpr.py", line 2703, in check_boolean_op
    right_map, left_map = self.chk.find_isinstance_check(e.left)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 3811, in find_isinstance_check
    if_map, else_map = self.find_isinstance_check_helper(node)
  File "/Users/ilevkivskyi/src/mypy/mypy/checker.py", line 3926, in find_isinstance_check_helper
    if is_overlapping_erased_types(item_type, collection_item_type):
  File "/Users/ilevkivskyi/src/mypy/mypy/meet.py", line 361, in is_overlapping_erased_types
    return is_overlapping_types(erase_type(left), erase_type(right),
  File "/Users/ilevkivskyi/src/mypy/mypy/erasetype.py", line 25, in erase_type
    return typ.accept(EraseTypeVisitor())
  File "/Users/ilevkivskyi/src/mypy/mypy/types.py", line 694, in accept
    return visitor.visit_erased_type(self)
  File "/Users/ilevkivskyi/src/mypy/mypy/erasetype.py", line 45, in visit_erased_type
    raise RuntimeError()
RuntimeError: 

This may be related to #8148, also note there is a weird pass here (it should probably be continue).

cc @Michael0x2a

[Michael0x2a]

Whoops, I think that's the bug, yeah.

I can send a PR with that fix in a minute (unless you're already working on one).

[ilevkivskyi]

I didn't start working on a fix yet, you can submit a PR with a quick fix, otherwise I will do this tomorrow.

I am wondering if there is a deeper logical problem: ErasedType() should never "escape" type inference, this is why some type visitors raise when encounter it. However, it looks like an ErasedType() can appear in a return of a lambda (which can be an arbitrary expression), thus potentially triggering various crashes.

[Michael0x2a]

I am wondering if there is a deeper logical problem

Yeah, I was just about to suggest this -- after I made the change, I tried adjusting the test case so filter accepts a Callable[[Optional[T], bool]]. That bypasses the check and ends up triggering the crash again, both on latest master and on a random commit from a month ago.

[Michael0x2a]

So, I think what's happening is this:

1. Since filter has a TypeVar, we at some point call infer_function_type_arguments when type checking the call. This will try inferring the argument types in multiple passes.
2. During the first pass, we enter visit_lambda_expr which promptly calls infer_lambda_type_using_context.
3. Since the lambda callable type currently still contains a meta var, we replace it with ErasedType in https://github.com/python/mypy/blob/master/mypy/checkexpr.py#L3372, generating a final type of (<erased>) -> bool.
4. Back up in visit_lambda_expr, we type check the body of the lambda using this new signature and end up stumbling down a code path that can't handle ErasedTypes, causing a crash.

And of course, if we get lucky and hit a code path that doesn't trigger a crash, the subsequent passes eventually end up doing the right thing.

I'm not really sure what the correct fix is though. Some tentative ideas I had were:

1. Just skip checking the lambda body during these earlier passes. I suspect this would unacceptably compromise the quality of the type inference though?
2. Instead of replacing typevars with ErasedType, replace them with PartialType and take advantage of the existing multiple-passes machinery in some way. Not sure what this would look like/if it'd actually work though.
3. Abandon the assumption that type checking code can't encounter ErasedTypes. In this specific case, that would mean updating EraseTypeVisitor so it handles ErasedType in the same way it handles TypeVars -- replace them with a special Any type. The downside is that removing this assumption would add a pretty inconvenient maintenance burden moving forward.

The discussion on overhauling how mypy infers generics in #5738 is maybe related/could address this?

[ilevkivskyi]

The discussion on overhauling how mypy infers generics in #5738 is maybe related/could address this?

Yes, this is indeed related, but unlike many other related issues, this causes a crash, not a leaked type variable etc. I would therefore prefer to track this separately. I will re-title the issue accordingly.

[AlexWaygood]

I am wondering if there is a deeper logical problem

Yeah, I was just about to suggest this -- after I made the change, I tried adjusting the test case so filter accepts a Callable[[Optional[T], bool]]. That bypasses the check and ends up triggering the crash again, both on latest master and on a random commit from a month ago.

To update on this issue: while the original crash was fixed ages ago in #8232, a second crash identified by @Michael0x2a in #8230 (comment) lingered for a while. A full repro for this crash was:

from typing import List, TypeVar, Callable, Optional

T = TypeVar('T')
def filter(f: Callable[[Optional[T]], bool], it: List[T]) -> List[T]: ...

xs: List[int]
filter(lambda x: x in [1, 2] and bool(), [3, 4])

This crashed on mypy <=0.930, but doesn't crash on 0.931+. The crash was fixed by commit a0f27b1 (@sobolevn's #11924).

Weirdly, while I can reproduce this crash with v0.930 checked out by pasting it into a crash.py file and running mypy on it, I'm having trouble reproducing it on v0.930 in the context of the test suite. So idk if we want to bother adding a test to the test suite, or if we should just close this now.

@JelleZijlstra, @JukkaL -- thoughts?

[JelleZijlstra]

Let's just close it. The issue hasn't received attention in two years; if somebody else has a similar problem we'll hear about it.