Clarify what @overload means

[gvanrossum]

In mypy (at least) overlapping @overload variants are not an error as long as the return types match. Examples where this has been reported or discussed include:

• Overloaded function signatures overlap with incompatible return types, class and Callable mypy#1941
• No error for identical overloaded functions mypy#1879
• Overloads with identical signatures not an error mypy#1612
• Type inference problem with overloaded mkdtemp mypy#1541
• Any incorrectly inferred for a call to an overloaded function mypy#1322
• Ordering matters for @overload mypy#1270
• Make operator overloading overlapping checks more lenient mypy#1264

There are probably more, but the point should be clear. We should either decide that overloads are tried in order of occurrence until a match is found, or that mypy's current philosophy is correct. Once we have decided we should update PEP 484 to clarify the desired behavior and explain the motivation. (And fix mypy, if needed.)

I'm not sure that it's always possible to have one unique match; e.g. in python/mypy#1322 the problem is that we're calling f(*some_list) and this is deemed a match for both variants. Mypy then cannot deduce a precise return type and falls back to Any.

I could also imagine that unions or type variables could make it hard to unambiguously pick a variant.

I'd also like to point out that the algorithm chosen by a type checker doesn't have to be the same as that chosen at run time -- at run time the overload variants are irrelevant and a single implementation does all the work using e.g. *args and isinstance() (or maybe using functools.singledispatch). But mypy's approach to overlapping is clearly causing a lot of confusion and it would be good to discuss this and write up in the PEP what a type checker should do.

@JukkaL, anything else we should consider here? Do you have a preference?

@matthiaskramm, is this relevant to pytype?

@vlasovskikh, any feedback from the PyCharm team?

[vlasovskikh]

We use the first match for these cases in PyCharm and we don't warn about overlapping signatures. If no matches are found, we infer a "weak" union of all the return types (we don't check for isinstance assertions on this union later).

[matthiaskramm]

pytype tries @overload methods in order of occurrence and picks the first one that matches.

We make heavy use of that in (our version of) __builtin__.pyi, haven't seen it much elsewhere.

[matthiaskramm]

Btw. I'm not sure I understand the current mypy approach.

In the mypy's / typeshed's 2.7/__builtin__.pyi, we have:

@overload
def divmod(a: int, b: int) -> Tuple[int, int]: ...
@overload
def divmod(a: float, b: float) -> Tuple[float, float]: ...

Given that the second function is effectively divmod(a: Union[int, float], b: Union[int, float]) (see python/typeshed#270), aren't those signatures overlapping, with different return types, and mypy should report an error?

[gvanrossum]

The reason is mypy's special treatment of the relation between int and float -- int is not a subclass of float, but it is still acceptable as a float.

[JukkaL]

I wrote about how mypy deals with overloads (python/mypy#1941 (comment)). Copied here for convenience:

Mypy lets you vary the return type even if multiple variants match if your signatures are ordered from narrower to more general. For example, this should be fine:

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

f(1)  # this is str
f('x')  # this is object
x = 1  # type: object
f(x)  # this is object, which is okay since str is a subclass of object

This would be a problem, though:

@overload
def f(x: int) -> object: ...
@overload
def f(x: object) -> int: ...  # bad

def g(x: object) -> int:
    return f(x) + 3   # the runtime type of x may be int and return value could be anything

g(1)
f(1) + 3   # an error

[JukkaL]

Also, if multiple, non-overlapping overload variants can match due to Any types in arguments, mypy will infer Any as the return type. Mypy doesn't have weak unions.

[matthiaskramm]

I like the narrow-to-general (topological) ordering approach. That seems to be the primary use case for having overlapping signatures.

(If you have multiple functions matching and an Any is to blame, pytype falls back to return type Any, same as mypy.)

[JukkaL]

Another thing to consider is the exact rules for deciding whether signatures are overlapping. Let's start with single-argument functions like this:

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

Here are some rules that mypy follows:

• If A is a subclass of B or vice versa they are overlapping. Otherwise if they are classes they aren't overlapping.
• Type parameters of generic types don't affect the overlapping check. List[int] is overlapping with List[str] (rationale: empty list).
• Type variables overlap like their upper bounds.
• Union types A and B overlap if any item from A is overlapping with some item from B.
• Any overlaps with everything.

These things are less clear:

• Does Tuple[int] overlap with Tuple[int, str]?
• What does Callable[...] overlap with? I think that mypy currently thinks that it can overlap with anything, since a subclass could define __call__, but this is unclear.

[matthiaskramm]

• Type parameters of generic types don't affect the overlapping check. List[int] is overlapping with List[str] (rationale: empty list).

pytype models empty lists explicitly as List[nothing], so for us, List[int] and List[str] can be treated as non-empty and not overlapping.

[JukkaL]

How does pytype treat code like this:

def f1(n: int) -> List[int]:  # should this return Union[List[int], List[nothing]]?
    return list(range(n))

def f2(n: int) -> List[str]:
    return list(str(x) for x in range(n))

@overload
def g(a: List[str]) -> str: ...
@overload
def g(a: List[int]) -> int: ...

n = int(open('n.txt').read())  # assume that this is 0
g(f1(n))  # int or str?
g(f2(n))  # int or str?

It seems to me that it's generally impossible to infer when a list could be empty if using PEP 484 annotations.

[matthiaskramm]

We treat nothing as ⊥. So List[int] ∪ List[⊥] ≈ List[int ∪ ⊥] = List[int].

Whenever the type parameter of a container "touches" (is joined with) another type, the type parameter will have that type. Only very few special operations (like dict.clear) can set the type parameter back to nothing.

So in the above example, g(f1(n)) will be int, and g(f2(n)) will be str. (And without return type annotations, f1() will be inferred to have return type List[int], and f2() will be inferred to have return type List[str])

I think the real point of contention is

g([])

Should this match the first signature, or generate an error? pytype currently opts for the latter, even if the type parameter for List were covariant. (So that ⊥⊂int, hence List[⊥]⊂List[int], causing the first signature to "match")

[dmoisset]

A possible solution that would be more flexible than the current one but still "symmetrical" (i.e. independent on the order of the overloads and detecting conflicts) would be allow any kind of type definitions, but check the overlap when checking the call. That can also detect the problem of a possible subclass of A and B passed to an overloaded f(x: A) -> int ; f(x: B) -> str which is the current problem with callable.

With this approach, when checking a call, you find all the return types for every matching overload definition, and the return type is the narrower one if that exists, and an error otherwise.

[gvanrossum]

The latest suggestion here is that we should improve mypy's implementation of @overload until we like it and then update the PEP. There's some discussion in python/mypy#4159 (comment).

[czhang03]

So are we settled on going through definition until find a match?

[chadrik]

So are we settled on going through definition until find a match?

As an end-user, I wholeheartedly endorse this approach. It is intuitive to think of overloads as a declarative form of the isinstance checks used within a function body, so it's natural that they should reflect the order found there.

For example, the following seems intuitive to me, but it results in an overlap error:

from typing import overload, Any

class Foo:
    pass

class Bar:
    pass

@overload
def func(a: Foo, b: Bar) -> Bar: ...
@overload
def func(a: Foo, b: Any) -> Foo: ...
@overload
def func(a: Any, b: Any) -> None: ...

def func(a, b):
    if isinstance(a, Foo) and isinstance(b, Bar):
        return b
    elif isinstance(a, Foo):
        return a
    else:
        return None

func(Foo(), 1)

Certainly there are complex considerations which are over my head, but I think that above all the new design should aim to be intuitive -- allowing a developer to approach overloads as a transcription of isinstance/issubclass checks would achieve that goal. If you want users to use overloads without giving up in frustration, the rules that govern them should be digestible within a few short bullet points.

[sproshev]

@Michael0x2a Thank you for the clarification! I agree.

[saulshanabrook]

I also have a WIP branch of mypy that implements these changes that I'll link to some time shortly once I get it working.

@Michael0x2a Sorry if I missed this, but what are the next steps on your work? Do you have a branch with changes in it? I am hitting some overload issues and would like to see if your work could solve them.

[ilevkivskyi]

All the proposed changes landed in mypy several months ago, the next step is to write a mini-PEP for this.

[srittau]

I am closing this for now. From skimming the comments, I believe there needs to be some clarification in documentation on how overloads are handled, but the problem is mostly resolved. Because this issue became overloaded and hard to follow, if there any actionable items still left to do, please open new issues in the appropriate issue trackers.

[jace]

From @Michael0x2a's explanation:

1. If a type checker detects it's impossible for an overload alternative to ever be called (e.g. if a call always matches an earlier alternative), it should report an error.
   Basically, overloads need to be ordered from narrow to broad.
2. Suppose that a call could potentially match two overload alternatives. In that case, the return type of the alternative that appears earlier must be a subtype of the return type of the alternative that appears later.

I was hoping this meant the following would work:

import typing as t
import typing_extensions as te
from collections import abc

@overload
def is_collection(item: str) -> te.Literal[False]:
    ...

@overload
def is_collection(item: bytes) -> te.Literal[False]:
    ...

@overload
def is_collection(item: t.Collection) -> te.Literal[True]:
    ...

def is_collection(item: t.Any) -> bool:
    """Return True if the item is a collection class but not a string."""
    return not isinstance(item, (str, bytes, dict)) and isinstance(item, abc.Collection)

However, mypy thinks definitions 1 and 2 overlap with 3. If I remove the overloads, downstream type narrowing fails:

def is_present(collection: t.Set, item: t.Union[str, t.Collection]) -> bool:
    if is_collection(item):
        # item is still a union here and mypy will flag str as incompatible with `&`
        return bool(collection & item)
    return item in collection

[hauntsaninja]

The overlapping overload check is basically a lint, so type ignore it if you know what you're doing. mypy will still do the right thing most of the time, but obviously it'll get tricked by stuff like x: Collection = "asdf"; is_collection(x)