Typing: Clarify what @overload means

Created on 26 Jul 2016  Â·  27Comments  Â·  Source: python/typing

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:

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 https://github.com/python/mypy/issues/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?

enhancement help wanted question

Most helpful comment

Context: I was working on fixing some overload related bugs in mypy a little while back. One thing led to another, and @ilevkivskyi recommended that I just work on pinning down a specification for how overloads are supposed to work and add that to PEP 484 first.

Request: I've already talked to most of the mypy team in person at the Pycon sprints, and we all seem to more or less be in consensus with these clarifications (barring any miscommunications on my part). However, it'd be nice to get some feedback from non-mypy people and see if they also agree.

If there are no objections, I'll work on adding these clarifications to PEP 484.

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.

tl;dr

Currently, PEP 484 isn't very clear on how overloads should work. In a nutshell, our proposal is that typecheckers should be fairly restrictive on how overloads are defined and fairly flexible in how they're called. This should hopefully strike a good balance between having overloads be typesafe vs expressive. Summary:

  1. There shouldn't be any type erasure when picking an overload. (This is probably a mypy-specific clarification.)

  2. All overload alternatives must follow these rules:

    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.

    3. We special-case descriptors and the __get__() method: we do not perform the previous check (2.ii) when __get__() is overloaded.

  3. If an implementation of an overload exists, its return and parameter types need to be supertypes of the corresponding types of every alternative.

  4. When calling an overloaded function, we pick the first alternative that matches unless...

    1. There are multiple matches due to an 'Any' type. In this case, the inferred type is 'Any'.

    2. There are multiple matches due to a 'Union' type. In this case, the inferred type is the union of the matching return types (or an error if a type checker is unable to figure this case out).

This is mostly a synthesis of the opinions that appeared above in this thread -- the main changes I made was clarifying how overloads and unions interact and special-casing descriptors. In particular, I think it would be useful if overloads could support basic "union math" -- see https://github.com/python/mypy/issues/1943 and https://github.com/python/mypy/issues/4576 for examples of where this would be useful.

Definitions:

To help make the specification more concise, here are some definitions:

  1. Overlapping arity: Two functions have overlapping arity if the number of arguments they could accept potentially overlap.

    For example, consider the following overload. The first overload alternative could accept as few as 1 parameter and as many as 3. The second alternative could accept between 3 to 4.

    These two ranges of values overlap, so we say both alternatives have overlapping arity.

    @overload
    def f(a: int, b: int = 4, c: int = 4) -> str: ...
    @overload
    def f(a: int, b: int, c: int, d: int = 4) -> str: ...
    

    Here's an example where there is no overlap in arity: The first alternative accepts 1 parameter, the second accepts 3.

    @overload
    def g(a: int) -> str: ...
    @overload
    def g(a: int, b: int, c: int) -> str: ...
    
  2. Partially overlapping: Two types T and S are partially overlapping if some but not all subtypes of T are also subtypes of S and vice-versa, ignoring the possibility of multiple-inheritance.

    For example:

    • If A and B represent two distinct classes with no common base class other than object, the two classes would be considered not partially overlapping. It's possible that somebody could define some class that inherits from both A and B, but we ignore that possibility.

      (If we did not, every single pair of types would be partially overlapping, which isn't very useful.)

    • The types Union[A, B] and Union[B, C] are partially overlapping. Some but not all members of Union[A, B] belong in Union[B, C] and vice-versa.

    To the best of my knowledge, unions are the only way to construct partially overlapping types (ignoring multiple inheritance).

  3. More specific: Given two types T and S, type T is considered more specific than S if T (and all subtypes of T) could potentially be subtypes of S.

    This relation is almost identical to the subtype relationship except for a few cases:

    • Suppose we have some arbitrary concrete type C and an unrestricted TypeVar T. We considered C more specific than T, since the TypeVar could in principle be bound to T when called.

    • Similarly, if T is bounded by some base class B, C would be more specific than T if C is a subtype of B.

    • All types are more specific than Any, but Any is more specific than only Any or object.

Specific details and examples

  1. Erasure: Overloads should be picked using their full types, with no type erasure.

    (I'm not sure how other type checkers work, but mypy currently erases types before trying to find a matching overload due to historical reasons.)

  2. Overload alternatives: Let 'alt1' and 'alt2' be two overload alternatives with overlapping arity, where 'alt1' appears earlier in the definition. (If the two alternatives do not have overlapping arity, there's no possibility that they'll conflict, so the following rules would not apply).

    Every such pair of alternatives must respect the following rules:

    1. Ordering overload alternatives: If every single parameter type in alt2 is more specific than the corresponding parameter types in alt1, then a type checker should report an error.

      For example, a type checker should throw an error given the following:

      @overload
      def f(x: Parent) -> str: ...
      @overload
      def f(x: Child) -> int: ...  # Error: will never be selected
      

      If we select the first matching overload, the second alternative will never be called, which is most likely an error. The user should swap the order of the two alternatives.

      We disallow duplicate parameter definitions as a natural consequence of this rule. For example, the following snippet is invalid:

      @overload
      def f(x: int) -> str: ...
      @overload
      def f(x: int) -> bool: ...
      
    2. Matching overloads and return types: If every single parameter type in alt1 is either more specific than or is partially overlapping with the corresponding parameter types in alt2, then alt1's return type must be a subtype of alt2's return type.

      If alt1's return type was not a subtype of alt2's, we could potentially construct an unsafe overload. For example, suppose the following was allowed:

      @overload
      def f(x: int) -> str: ...
      @overload
      def f(x: object) -> bool: ...
      
      var: object = 1
      reveal_type(f(var))  # 'bool' at compile-time but 'str' at runtime?
      

      Here, 'var' is of type 'object' and the first matching overload is the second one, which returns 'bool'. So a type checker infers that the return type of 'f' is bool in this case. However, since 'var' is actually an int, the true type of 'f(var)' is str!

      This is no longer an issue if the return type is a subtype:

      class Animal: pass
      class Dog(Animal): pass
      
      @overload
      def f(x: int) -> Dog: ...
      @overload
      def f(x: object) -> Animal: ...
      
      var: object = 1
      reveal_type(f(var))  # 'Dog' is a valid subtype of 'Animal':
      

      Inferring that f(var) is of type Animal is ok in this case: after all, a dog is a kind of animal.

      We run into similar issues if there's a partial overlap:

      # Not ok:
      @overload
      def f(x: Union[A, B]) -> str: ...
      @overload
      def f(x: Union[B, C]) -> bool: ...   
      
      reveal_type(f(B()))  # is this 'str', or 'bool'?
      
      # Ok (though sloppy):
      @overload
      def g(x: Union[A, B]) -> Dog: ...
      @overload
      def g(x: Union[B, C]) -> Animal: ...   
      
      reveal_type(f(g()))  # Dog is a kind of Animal
      

      (Note: while the second example directly above is typesafe, it's also sort of sloppy: there's no reason why both overload alternatives ought to accept B. A type checker may optionally raise an error or a warning in cases like these.)

      If only some of the parameters are more specific or are partial overlaps, the two alternatives are fine as they are. We also don't care what how the two return types are related in this case. For example, the following two definitions are fine:

      # Ok:
      @overload
      def f(x: int, y: float) -> str: ...
      @overload
      def f(x: float, y: int) -> bool: ...
      
      # Also ok: second argument lets us always disambiguate
      @overload
      def g(x: Union[A, B], y: str) -> str: ...
      @overload
      def g(x: Union[B, C], y: int) -> bool: ...
      
    3. Special-casing descriptors: Finally, when the __get__() method in descriptors is overloaded, we skip the previous check.

      This special case exists because it would otherwise be impossible to type a lot of useful descriptors. For example, suppose we want to re-implement a simplified version of @property using descriptors. We would use such a class like so:

      class SomeObject(object):
          def __init__(self) -> None:
              self._x: int = 3
      
          @MyProperty
          def x(self) -> int:
              return self._x
      
          # Note: the above is equivalent to doing:
          # x = MyProperty(x)
      
          @x.setter
          def setx(self, val: int) -> None:
              self._x = val
      
          # Note: the above is equivalent to doing
          # x = x.__get__(None, SomeObject).setter(setx)
      

      We would then implement MyProperty like so. (Some details are omitted for brevity):

      TValue = TypeVar('TValue')
      TObject = TypeVar('TObject')
      
      class MyProperty(Generic[TObject, TValue]):
          def __init__(self, 
                       fget: Callable[[TObject], TValue],
                       fset: Optional[Callable[[TObject, TValue], None]] = None) -> None:
              self.fget = fget
              self.fset = fset
      
          @overload
          def __get__(self, obj: None, objtype: Type[TObject]) -> 'MyProperty': ...
          @overload
          def __get__(self, obj: TObject, objtype: Optional[Type[TObject]]) -> TValue: ...
          def __get__(self, 
                      obj: Optional[TObject], 
                      objtype: Optional[Type[TOBject]] = None) -> Union['MyProperty', TValue]:
              assert obj is not None or objtype is not None
              return self if obj is None else self.fget(obj)
      
          def __set__(self, obj: TObject, value: TValue) -> None:
              assert set.fset is not None
              self.fset(obj, value)
      
          def setter(self, fset: Callable[[TObject, TValue], None]) -> 'MyProperty':
              return MyProperty(self.fget, fset)
      

      If we did not special-case how we handle None, we would be unable to provide working type hints for the __get__ method. Under normal rules, None is more specific than TObject and Type[TObject] is more specific than Optional[Type[TObject]]. Therefore, the type checker mandates that MyProperty is a subtype of TValue. However, we have no way of determining whether this will actually be the case!

      This is a shame, because it would be very useful to type descriptors like these. The easiest way of accomplishing this is to just waive the rule for checking return types for descriptors altogether.

      (Of course, a type checker may optionally perform additional checks if they want to handle descriptors more precisely.)

  3. Overload implementations: If an overload implementation exists, its parameter and return types must be all be supertypes of the corresponding types in each overload alternative.

  4. Calling overloads: When an overloaded function is called, the type checker will find all matching overload alternatives, based on the call arguments.

    If there are no matches, the type checker will report an error -- otherwise, it will select the first matching alternative.

    There are two exceptions to this rule:

    1. Ambiguity due to Any: If there are multiple matches due to the presence of an 'Any' type within the call arguments, the inferred type of the call expression will also be 'Any'. For example:

      @overload
      def foo(x: int) -> int: ...
      @overload
      def foo(x: str) -> str: ...
      @overload
      def foo(x: bool) -> bool: ...
      
      y: Any = 3
      reveal_type(foo(y))  # Revealed type is 'Any'
      
    2. Ambiguity due to Unions: If there are multiple matches due to the presence of a 'Union' type within the call arguments, the inferred type of the call expression will be the union of all of the inferred return types.

      For example, the inferred type of foo(y) below should be Union[int, str]:

      @overload
      def foo(x: int) -> int: ...
      @overload
      def foo(x: str) -> str: ...
      @overload
      def foo(x: bool) -> bool: ...
      
      y: Union[int, str] = 3
      reveal_type(foo(y))  # Revealed type is 'Union[int, str]'
      

      A type checker should be conservative when performing this union math. For example, the call to foo(arg, arg) should be a type error in the example below since there's no guarantee that the types of arg1 and arg2 will match one of the two overloads at runtime -- for example, if they were both of type A.

      class A: pass
      class B: pass
      
      @overload
      def foo(x: A, y: B) -> int: ...
      @overload
      def foo(x: B, y: A) -> str: ...
      def foo(x, y): ...
      
      arg1: Union[A, B] = A()
      arg2: Union[A, B] = A()
      foo(arg1, arg2)  # Should be a type-error, not 'Union[int, str]'
      

Additional commentary

  • Should we perform stricter checks on overload implementations?

    One weakness of this proposal is that it's very possible for users to write overload implementations that do not match all of the overload alternatives. For example, the following overload definition would typecheck under the above proposed rules despite not being typesafe:

    @overload 
    def foo(x: int) -> int: ...
    @overload
    def foo(x: str) -> str: ...
    def foo(x: Union[int, str]) -> Union[int, str]:
        return "x"
    

    However, I believe this is already the status quo with existing type checker implementations, mostly because it's hard to check the correctness of the implementation in the general case?

    I don't want to raise the implementation burden, so I propose that we don't require type checkers to try and handle this case: they can add extra checks if they feel it's worth handling this case.

  • Does removing type erasure make implementation more complicated?

    This is sort of related to the above: removing type erasure could potentially make implementing overloads more tricky. This is easier to explain with an example:

    @overload
    def foo(x: List[int]) -> A: ...
    @overload
    def foo(x: List[str]) -> B: ...
    def foo(x: Union[List[int], List[str]]) -> Union[A, B]:
        # How do we cleanly determine if 'x' is a List[int] or a List[str]?
        # Doing isinstance(x, List[str]) or the like won't work.
    

    Here, we allow the types to distinguish between List[int] and List[str] even though it's a bit challenging to concisely do that at runtime. This is maybe not that big of a deal though?

  • Why ignore multiple inheritance?

    The above proposal basically entirely ignores the possibility of multiple inheritance. One counter-proposal might be to alter the how we pick overload alternatives on function calls to mirror what we do with Unions: if we match multiple alternatives due to multiple inheritance, return the union of the return types. For example:

    class A: ...
    class B: ...
    class Both(A, B): ...
    
    @overload
    def f(x: A) -> int: ...
    @overload
    def f(x: B) -> str: ...
    
    reveal_type(f(Both()))  # Revealed type is 'Union[int, str]'?
    

    However, I don't think this counter-proposal really improves how we handle overloads. Both the original proposal and the counter-proposal fail in the same way in the following case:

    class A: ...
    class B: ...
    class Both(A, B): ...
    
    @overload
    def f(x: A) -> int: ...
    @overload
    def f(x: B) -> str: ...
    
    def g(y: B) -> str:
        # There's no way to tell that 'y' subclasses A here!
        return f(y)
    
    g(Both())  # Type checker thinks this is str, but at runtime it's int!
    

    I don't think there's really a clean way of handling this case, so I think it's best to avoid making false promises and just not try and handle multiple inheritance at all.

All 27 comments

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).

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.

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 https://github.com/python/typeshed/issues/270), aren't those signatures overlapping, with different return types, and mypy should report an error?

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.

I wrote about how mypy deals with overloads (https://github.com/python/mypy/issues/1941#issuecomment-235357559). 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

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.

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.)

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.
  • 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.

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.

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")

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.

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 https://github.com/python/mypy/issues/4159#issuecomment-339814841.

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

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.

@chadrik I totally agree with you. I am trying to implement strong typed finite parameter currying. If we don't loosen the restriction on overload, I have to implement curry2, curry3, curry4, which can be really annoying when used in real world usage.

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

I don't think that any single, simple rule is sufficient to describe the desired overload semantics. I assume that everybody agrees that the way mypy deals with overloads right now is not optimal, but I expect that reaching agreement on what's the right way to do it won't be easy and requires a fair amount of thought and discussion.

Here is an example about why your suggestion is not without problems:

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

def g(a: Any) -> Any:
    return f(a) + 'a'  # Should be okay?

g('x')

In the above example, the type of f(a) would be int if we just pick the first signature that matches, but the correct type would be Any, in my opinion.

Context: I was working on fixing some overload related bugs in mypy a little while back. One thing led to another, and @ilevkivskyi recommended that I just work on pinning down a specification for how overloads are supposed to work and add that to PEP 484 first.

Request: I've already talked to most of the mypy team in person at the Pycon sprints, and we all seem to more or less be in consensus with these clarifications (barring any miscommunications on my part). However, it'd be nice to get some feedback from non-mypy people and see if they also agree.

If there are no objections, I'll work on adding these clarifications to PEP 484.

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.

tl;dr

Currently, PEP 484 isn't very clear on how overloads should work. In a nutshell, our proposal is that typecheckers should be fairly restrictive on how overloads are defined and fairly flexible in how they're called. This should hopefully strike a good balance between having overloads be typesafe vs expressive. Summary:

  1. There shouldn't be any type erasure when picking an overload. (This is probably a mypy-specific clarification.)

  2. All overload alternatives must follow these rules:

    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.

    3. We special-case descriptors and the __get__() method: we do not perform the previous check (2.ii) when __get__() is overloaded.

  3. If an implementation of an overload exists, its return and parameter types need to be supertypes of the corresponding types of every alternative.

  4. When calling an overloaded function, we pick the first alternative that matches unless...

    1. There are multiple matches due to an 'Any' type. In this case, the inferred type is 'Any'.

    2. There are multiple matches due to a 'Union' type. In this case, the inferred type is the union of the matching return types (or an error if a type checker is unable to figure this case out).

This is mostly a synthesis of the opinions that appeared above in this thread -- the main changes I made was clarifying how overloads and unions interact and special-casing descriptors. In particular, I think it would be useful if overloads could support basic "union math" -- see https://github.com/python/mypy/issues/1943 and https://github.com/python/mypy/issues/4576 for examples of where this would be useful.

Definitions:

To help make the specification more concise, here are some definitions:

  1. Overlapping arity: Two functions have overlapping arity if the number of arguments they could accept potentially overlap.

    For example, consider the following overload. The first overload alternative could accept as few as 1 parameter and as many as 3. The second alternative could accept between 3 to 4.

    These two ranges of values overlap, so we say both alternatives have overlapping arity.

    @overload
    def f(a: int, b: int = 4, c: int = 4) -> str: ...
    @overload
    def f(a: int, b: int, c: int, d: int = 4) -> str: ...
    

    Here's an example where there is no overlap in arity: The first alternative accepts 1 parameter, the second accepts 3.

    @overload
    def g(a: int) -> str: ...
    @overload
    def g(a: int, b: int, c: int) -> str: ...
    
  2. Partially overlapping: Two types T and S are partially overlapping if some but not all subtypes of T are also subtypes of S and vice-versa, ignoring the possibility of multiple-inheritance.

    For example:

    • If A and B represent two distinct classes with no common base class other than object, the two classes would be considered not partially overlapping. It's possible that somebody could define some class that inherits from both A and B, but we ignore that possibility.

      (If we did not, every single pair of types would be partially overlapping, which isn't very useful.)

    • The types Union[A, B] and Union[B, C] are partially overlapping. Some but not all members of Union[A, B] belong in Union[B, C] and vice-versa.

    To the best of my knowledge, unions are the only way to construct partially overlapping types (ignoring multiple inheritance).

  3. More specific: Given two types T and S, type T is considered more specific than S if T (and all subtypes of T) could potentially be subtypes of S.

    This relation is almost identical to the subtype relationship except for a few cases:

    • Suppose we have some arbitrary concrete type C and an unrestricted TypeVar T. We considered C more specific than T, since the TypeVar could in principle be bound to T when called.

    • Similarly, if T is bounded by some base class B, C would be more specific than T if C is a subtype of B.

    • All types are more specific than Any, but Any is more specific than only Any or object.

Specific details and examples

  1. Erasure: Overloads should be picked using their full types, with no type erasure.

    (I'm not sure how other type checkers work, but mypy currently erases types before trying to find a matching overload due to historical reasons.)

  2. Overload alternatives: Let 'alt1' and 'alt2' be two overload alternatives with overlapping arity, where 'alt1' appears earlier in the definition. (If the two alternatives do not have overlapping arity, there's no possibility that they'll conflict, so the following rules would not apply).

    Every such pair of alternatives must respect the following rules:

    1. Ordering overload alternatives: If every single parameter type in alt2 is more specific than the corresponding parameter types in alt1, then a type checker should report an error.

      For example, a type checker should throw an error given the following:

      @overload
      def f(x: Parent) -> str: ...
      @overload
      def f(x: Child) -> int: ...  # Error: will never be selected
      

      If we select the first matching overload, the second alternative will never be called, which is most likely an error. The user should swap the order of the two alternatives.

      We disallow duplicate parameter definitions as a natural consequence of this rule. For example, the following snippet is invalid:

      @overload
      def f(x: int) -> str: ...
      @overload
      def f(x: int) -> bool: ...
      
    2. Matching overloads and return types: If every single parameter type in alt1 is either more specific than or is partially overlapping with the corresponding parameter types in alt2, then alt1's return type must be a subtype of alt2's return type.

      If alt1's return type was not a subtype of alt2's, we could potentially construct an unsafe overload. For example, suppose the following was allowed:

      @overload
      def f(x: int) -> str: ...
      @overload
      def f(x: object) -> bool: ...
      
      var: object = 1
      reveal_type(f(var))  # 'bool' at compile-time but 'str' at runtime?
      

      Here, 'var' is of type 'object' and the first matching overload is the second one, which returns 'bool'. So a type checker infers that the return type of 'f' is bool in this case. However, since 'var' is actually an int, the true type of 'f(var)' is str!

      This is no longer an issue if the return type is a subtype:

      class Animal: pass
      class Dog(Animal): pass
      
      @overload
      def f(x: int) -> Dog: ...
      @overload
      def f(x: object) -> Animal: ...
      
      var: object = 1
      reveal_type(f(var))  # 'Dog' is a valid subtype of 'Animal':
      

      Inferring that f(var) is of type Animal is ok in this case: after all, a dog is a kind of animal.

      We run into similar issues if there's a partial overlap:

      # Not ok:
      @overload
      def f(x: Union[A, B]) -> str: ...
      @overload
      def f(x: Union[B, C]) -> bool: ...   
      
      reveal_type(f(B()))  # is this 'str', or 'bool'?
      
      # Ok (though sloppy):
      @overload
      def g(x: Union[A, B]) -> Dog: ...
      @overload
      def g(x: Union[B, C]) -> Animal: ...   
      
      reveal_type(f(g()))  # Dog is a kind of Animal
      

      (Note: while the second example directly above is typesafe, it's also sort of sloppy: there's no reason why both overload alternatives ought to accept B. A type checker may optionally raise an error or a warning in cases like these.)

      If only some of the parameters are more specific or are partial overlaps, the two alternatives are fine as they are. We also don't care what how the two return types are related in this case. For example, the following two definitions are fine:

      # Ok:
      @overload
      def f(x: int, y: float) -> str: ...
      @overload
      def f(x: float, y: int) -> bool: ...
      
      # Also ok: second argument lets us always disambiguate
      @overload
      def g(x: Union[A, B], y: str) -> str: ...
      @overload
      def g(x: Union[B, C], y: int) -> bool: ...
      
    3. Special-casing descriptors: Finally, when the __get__() method in descriptors is overloaded, we skip the previous check.

      This special case exists because it would otherwise be impossible to type a lot of useful descriptors. For example, suppose we want to re-implement a simplified version of @property using descriptors. We would use such a class like so:

      class SomeObject(object):
          def __init__(self) -> None:
              self._x: int = 3
      
          @MyProperty
          def x(self) -> int:
              return self._x
      
          # Note: the above is equivalent to doing:
          # x = MyProperty(x)
      
          @x.setter
          def setx(self, val: int) -> None:
              self._x = val
      
          # Note: the above is equivalent to doing
          # x = x.__get__(None, SomeObject).setter(setx)
      

      We would then implement MyProperty like so. (Some details are omitted for brevity):

      TValue = TypeVar('TValue')
      TObject = TypeVar('TObject')
      
      class MyProperty(Generic[TObject, TValue]):
          def __init__(self, 
                       fget: Callable[[TObject], TValue],
                       fset: Optional[Callable[[TObject, TValue], None]] = None) -> None:
              self.fget = fget
              self.fset = fset
      
          @overload
          def __get__(self, obj: None, objtype: Type[TObject]) -> 'MyProperty': ...
          @overload
          def __get__(self, obj: TObject, objtype: Optional[Type[TObject]]) -> TValue: ...
          def __get__(self, 
                      obj: Optional[TObject], 
                      objtype: Optional[Type[TOBject]] = None) -> Union['MyProperty', TValue]:
              assert obj is not None or objtype is not None
              return self if obj is None else self.fget(obj)
      
          def __set__(self, obj: TObject, value: TValue) -> None:
              assert set.fset is not None
              self.fset(obj, value)
      
          def setter(self, fset: Callable[[TObject, TValue], None]) -> 'MyProperty':
              return MyProperty(self.fget, fset)
      

      If we did not special-case how we handle None, we would be unable to provide working type hints for the __get__ method. Under normal rules, None is more specific than TObject and Type[TObject] is more specific than Optional[Type[TObject]]. Therefore, the type checker mandates that MyProperty is a subtype of TValue. However, we have no way of determining whether this will actually be the case!

      This is a shame, because it would be very useful to type descriptors like these. The easiest way of accomplishing this is to just waive the rule for checking return types for descriptors altogether.

      (Of course, a type checker may optionally perform additional checks if they want to handle descriptors more precisely.)

  3. Overload implementations: If an overload implementation exists, its parameter and return types must be all be supertypes of the corresponding types in each overload alternative.

  4. Calling overloads: When an overloaded function is called, the type checker will find all matching overload alternatives, based on the call arguments.

    If there are no matches, the type checker will report an error -- otherwise, it will select the first matching alternative.

    There are two exceptions to this rule:

    1. Ambiguity due to Any: If there are multiple matches due to the presence of an 'Any' type within the call arguments, the inferred type of the call expression will also be 'Any'. For example:

      @overload
      def foo(x: int) -> int: ...
      @overload
      def foo(x: str) -> str: ...
      @overload
      def foo(x: bool) -> bool: ...
      
      y: Any = 3
      reveal_type(foo(y))  # Revealed type is 'Any'
      
    2. Ambiguity due to Unions: If there are multiple matches due to the presence of a 'Union' type within the call arguments, the inferred type of the call expression will be the union of all of the inferred return types.

      For example, the inferred type of foo(y) below should be Union[int, str]:

      @overload
      def foo(x: int) -> int: ...
      @overload
      def foo(x: str) -> str: ...
      @overload
      def foo(x: bool) -> bool: ...
      
      y: Union[int, str] = 3
      reveal_type(foo(y))  # Revealed type is 'Union[int, str]'
      

      A type checker should be conservative when performing this union math. For example, the call to foo(arg, arg) should be a type error in the example below since there's no guarantee that the types of arg1 and arg2 will match one of the two overloads at runtime -- for example, if they were both of type A.

      class A: pass
      class B: pass
      
      @overload
      def foo(x: A, y: B) -> int: ...
      @overload
      def foo(x: B, y: A) -> str: ...
      def foo(x, y): ...
      
      arg1: Union[A, B] = A()
      arg2: Union[A, B] = A()
      foo(arg1, arg2)  # Should be a type-error, not 'Union[int, str]'
      

Additional commentary

  • Should we perform stricter checks on overload implementations?

    One weakness of this proposal is that it's very possible for users to write overload implementations that do not match all of the overload alternatives. For example, the following overload definition would typecheck under the above proposed rules despite not being typesafe:

    @overload 
    def foo(x: int) -> int: ...
    @overload
    def foo(x: str) -> str: ...
    def foo(x: Union[int, str]) -> Union[int, str]:
        return "x"
    

    However, I believe this is already the status quo with existing type checker implementations, mostly because it's hard to check the correctness of the implementation in the general case?

    I don't want to raise the implementation burden, so I propose that we don't require type checkers to try and handle this case: they can add extra checks if they feel it's worth handling this case.

  • Does removing type erasure make implementation more complicated?

    This is sort of related to the above: removing type erasure could potentially make implementing overloads more tricky. This is easier to explain with an example:

    @overload
    def foo(x: List[int]) -> A: ...
    @overload
    def foo(x: List[str]) -> B: ...
    def foo(x: Union[List[int], List[str]]) -> Union[A, B]:
        # How do we cleanly determine if 'x' is a List[int] or a List[str]?
        # Doing isinstance(x, List[str]) or the like won't work.
    

    Here, we allow the types to distinguish between List[int] and List[str] even though it's a bit challenging to concisely do that at runtime. This is maybe not that big of a deal though?

  • Why ignore multiple inheritance?

    The above proposal basically entirely ignores the possibility of multiple inheritance. One counter-proposal might be to alter the how we pick overload alternatives on function calls to mirror what we do with Unions: if we match multiple alternatives due to multiple inheritance, return the union of the return types. For example:

    class A: ...
    class B: ...
    class Both(A, B): ...
    
    @overload
    def f(x: A) -> int: ...
    @overload
    def f(x: B) -> str: ...
    
    reveal_type(f(Both()))  # Revealed type is 'Union[int, str]'?
    

    However, I don't think this counter-proposal really improves how we handle overloads. Both the original proposal and the counter-proposal fail in the same way in the following case:

    class A: ...
    class B: ...
    class Both(A, B): ...
    
    @overload
    def f(x: A) -> int: ...
    @overload
    def f(x: B) -> str: ...
    
    def g(y: B) -> str:
        # There's no way to tell that 'y' subclasses A here!
        return f(y)
    
    g(Both())  # Type checker thinks this is str, but at runtime it's int!
    

    I don't think there's really a clean way of handling this case, so I think it's best to avoid making false promises and just not try and handle multiple inheritance at all.

cc @dkgi from Pyre team

I like this write-up. This is a good starting point for the PEP 484 update (which should be more terse while preserving the logic). It leaves a bit of freedom for type checkers regarding strictness in tricky cases, but I am fine with this.

Generally I'm OK with the proposed changes.
The only question is why type checker could not ignore unknown relation between MyProperty and TValue (see Special-casing descriptors section)? This disregard could help to overcome special processing for descriptors.

@sproshev -- Just to make sure I understand, you're proposing that we enforce 2.i (ordering overload alternatives) and ignore 2.ii (matching overloads and return types) for descriptors, instead of ignoring both?

If so, that's a good point. My original reasoning was that since descriptors are typically used only for complicated things, I didn't want to break a potential use case by accident by being too prescriptive. But on second thought, I think I agree that enforcing just 2.i would likely be fine.

I'll edit my comment.

@Michael0x2a Almost, my idea was to have as less as possible special cases so I thought that if type checker could not determine if one type is subtype of another or not, it could be considered as satisfaction for 2.ii.
In such a way descriptors would follow the rules and there would be no need to do exclusions for them.

@sproshev -- oh, I see. I'm worried that would open up too big of a hole in the type system though. For example, making that change would mean that the Wrapper class in the example below typechecks even though we can make unsafe calls:

class Wrapper(Generic[T]):
    @overload
    def foo(x: Child) -> int: ...
    @overload
    def foo(x: Parent) -> T: ...

val: Parent = Child()     

unsafe_wrapper: Wrapper[str] = Wrapper()
reveal_type(unsafe_wrapper.foo(val))   # Inferred type is 'str'; actual type is 'int'

@Michael0x2a Thank you for the clarification! I agree.

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.

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

Was this page helpful?
0 / 5 - 0 ratings

Related issues

saulshanabrook picture saulshanabrook  Â·  6Comments

zsluedem picture zsluedem  Â·  3Comments

mjr129 picture mjr129  Â·  3Comments

Phlogistique picture Phlogistique  Â·  4Comments

gvanrossum picture gvanrossum  Â·  8Comments