Generic function type argument inference sometimes commits too early

[rwbarton]

This was an example designed as a test case for another issue, but also happens to be plausible code.

from typing import TypeVar, Union, List
T = TypeVar('T')
U = TypeVar('U')
def interleave(x: List[T], y: List[U]) -> List[Union[T, U]]: pass

x = [1]
y = ['a']
z = interleave(x, y) # type: List[Union[int, str]]

Obviously we intend to call interleave with T = int and U = str. Without the type annotation on z, mypy correctly infers these type arguments and accepts the program.

But with the type annotation, mypy reasons that in order for interleave(x, y) to be a subtype of List[Union[int, str]], both T and U will need to be subtypes of Union[int, str]. (And it's true that this is necessary, though not sufficient.) Then check_call substitutes this upper bound for T and U before considering the types of the arguments, resulting in the errors

interleave.py:8: error: Argument 1 to "interleave" has incompatible type List[int]; expected List[Union[int, str]]
interleave.py:8: error: Argument 2 to "interleave" has incompatible type List[str]; expected List[Union[int, str]]

In a real program the context for interleave(x, y) might be provided by a surrounding function call rather than a type annotation.

Here's another example not involving unions:

from typing import TypeVar, List, Tuple
T = TypeVar('T')
def f(x: List[T]) -> Tuple[str, T]: pass
x = [1]
y = f(x) # type: Tuple[str, float]

This program should be valid because we can choose T = int (as Tuple[str, int] is a subtype of Tuple[str, float]), but mypy tries to choose T = float and therefore errors.

[rwbarton]

There's also a special case in infer_function_type_arguments_using_context that refuses to infer generic function type arguments when the declared return type of the function is a bare type variable T. I think this is to avoid the kind of situation in this issue where we would infer that T is the type of the context when, in fact, any subtype of the context would also be possible (this is bad if, for example, the generic function has type def f(xs: List[T]) -> T, the argument has type List[int] and the context has type Float).

A strategy that seems promising is to only commit to values of type arguments in infer_function_type_arguments_using_context which are determined uniquely by the generated constraints; and then take the context into account again when generating constraints in infer_function_type_arguments. This is approximately what that special case does anyways, because constraint generation currently treats most type constructors as invariant.

[rwbarton]

I tried the strategy mentioned above a while ago, but it turned out not to work as well as I hoped. I no longer recall why exactly.

[ilevkivskyi]

Closing as a duplicate of #5874 (it is rather another way around, but the other issue has a wider scope).