Any incorrectly inferred for a call to an overloaded function

[JukkaL]

This was reported by Alex Allain.

Mypy doesn't give an error for this program even though it should:

from typing import TypeVar, overload, List

T = TypeVar('T')

@overload
def f(x: T) -> List[T]: ...
@overload
def f(x: T, y: int) -> int: pass

def not_checked(text):
    # type: (str) -> str
    return f(*[])  # no error reported!

Mypy infers type List[None] for [] (which is arguably okay, though a little confusing), and this results in all overload variants matching, which is again okay. Now since multiple overload variants match, mypy incorrectly gives up and infers Any as the return type of f(*[]), even though in this case we could infer a more precise type: a union of all return types of all overload variants, i.e. Union[List[None], int]. Alternatively, mypy could give up and say that the return type is ambiguous, but it's less clear when this would be an okay thing to do (if ever).

[gvanrossum]

Why is it okay if multiple overloads match? I thought mypy had some check that warns if overlaps are possible when the overload is defined, so I'd expect that that would produce an error (and I commend Alex for having found an example that matches multiple overloads).

Given that you generally don't like unions I'm a little surprised you propose one here. But I suppose if both variants were to return the same type we should at least infer that type.

Also, once we implement strict Optional checking, List[None] no longer would match all overload variants, right?

[JukkaL]

Originally the idea was that overloads shouldn't be overlapping, but this got abandoned since it relied on multiple inheritance from built-in types being restricted so that you can't subclass int and str, for example. If almost any pair of classes can be subclassed, almost all pairs of types are potentially overlapping. Currently mypy doesn't keep track of which classes are built-in / extension classes so it can't do this sort of enforcement easily. Besides, this also seemed to be too restrictive, and the ambiguity due to overlapping overload variants doesn't seem to be a significant problem most of the time. The story is a bit more complex than this, as some forms of overlapping are always okay. Maybe I should write some more detailed docs about how overloaded functions works.

I still don't like union types, but here they just might be justified. However, let's start with an example where union types are plausible but problematic. Consider this fragment:

# stub for m
@overload
def f(x: str) -> str: ...
@overload
def f(x: str, y: str) -> int: ...

# program
from m import f
a = <something> # type: Iterable[str]
f(*a)  # Is this valid? What's the type?

Mypy currently assumes that either variant of f could be invoked on the last line -- we can't predict the number of items in an Iterable, and the call could target either of the variants. There are a few things we could do here:

1. Disallow the call, because the return type is ambiguous. It would have to rewritten, perhaps like this:

   a = <something> # type: Iterable[str]
   x, y = a
   f(x, y)
   

2. Disallow the call, because the length of *args argument cannot be determined, and the call could fail at runtime if the length is not 1 or 2. The workaround would be the same as above.

3. Infer type Union[int, str] for the result, as either variant could be called. I don't like this very much because the programmer might know that a particular variant will always be called, and the union type would require a cast or similar.

4. Infer type Any for the result -- this is what mypy does right now, though unintentionally. This is bad because it can produce Any types from seemingly annotated code.

The above example is pretty academic and unlikely to happen often in the wild. The case of zip is more realistic. Let's forget about List[None] for a while, as that should be fixed once None is no longer special as you mentioned. A similar thing can happen without it:

a = <something> # type: Iterable[List[int]]
zip(*a)  # What's the type of this?

zip is defined as an overloaded function, as variadic type variables aren't supported. The correct type for zip(*a) would be Iterator[Tuple[int, ...]], but the stub file makes it hard to come up with this type, since it only supports cases with up to four arguments. If we'd added an extra overload variant that accepts and arbitrary number of iterables (via *args), we could have something like this (I'm simplifying a bit by only including 3 variants):

@overload
def zip(iter1: Iterable[_T1]) -> Iterator[Tuple[_T1]]: ...
@overload
def zip(iter1: Iterable[_T1], iter2: Iterable[_T2]) -> Iterator[Tuple[_T1, _T2]]: ...
@overload
def zip(iter1: Iterable[_T], 
        iter2: Iterable[_T], 
        iter3: Iterable[_T], 
        *iter: Iterable[_T]) -> Iterator[Tuple[_T, ...]]: ...
# The last variant is not included in the current stub

Now the call to zip(*a) could still match all of the variants, and the return type is ambiguous. However, if we'd use a union for the return type, we could actually simplify the union to just Iterator[Tuple[_T, ...]] which would be good. So here using union types would actually work.

A suitable rule to cover both of the above examples might be something like this:

If multiple overload variants match [+ some extra conditions that I'm leaving out for simplicity], the type of the call is the union of the return types of the matching variants, assuming this union can be simplified to a non-union type (if one the variants returns a union, then a union is fine after simplification). If the result would be a union, generate a error and ask the code to be refactored.

[gvanrossum]

OK, as long as the decision that multiple variants match happens rarely
enough, and as long as the zip(*a) example actually works as expected.

[JukkaL]

I'm not sure whether my proposal would work in practice, but it wouldn't too hard to run an experiment.

[ilevkivskyi]

This also affects protocols, I think we might want to raise priority of this to high.

[Michael0x2a]

The original example now fails with an Incompatible return value type (got "List[<nothing>]", expected "str") error (almost certainly after f61c2ba landed). It's admittedly a bit more cryptic then I would like, but I think that's an unavoidable consequence of misusing generics and it at least indicates to the user that something is wrong. We've also worked out semantics I think we're reasonably happy with (though it ended up being less strict overall then what Jukka was proposing up above).

So, I'm thinking we can close this issue? Feel free to reopen if anybody disagrees.