Improving overloads with intersections

Typing
1

(hopefully last lead up discussion topic on intersections needed)

Right now, overload resolution rules allow producing mostly good results, but to get those, there’s a significant amount of verbosity. I expect this to get in some ways better, and in other ways worse if intersections are accepted as currently being drafted.

Something I was considering which would reduce the amount of manual expansions users need to write themselves which could improve both existing cases and some new cases that could arise with intersections, is the ability to specify a small extra bit of overload resolution behavior.

This would be accomplished by adding a keyword argument to the overload decorator. It would have a default that is equivalent to the existing behavior.

The proposed behaviors:

  • Match one (default, existing behavior)
  • First non-gradual match (new, implies negating all prior paramter overloads)
  • Intersecting match (new, implies intersecting return types for overlapping matches)

The behavior of “match one” remains as the current behavior specifies, including the existing union expansion behavior that means when a union is the input, if each union member matches an overload, the union of the returns of matching return. This includes keeping the existing warning for ambiguously overlapping overloads.

The behavior of “First non-gradual match” is that the first overload that matches wins when the parameters passed are not gradual. In the case of gradual parameters (such as Any), this automatically degrades to matching gradually to preserve the gradual guarantee.

This is an improvement in cases of overlapping types, but the implementation prefers dispatching on a specific type. With intersections and negation, cases like this can be expressed without such a rule, but the verbosity involved is significant. Consider the below case, keeping in mind that real numeric libraries have their own types like this, and that expanding this without first match behavior would involve overlapping overloads, while at runtime, the interior of such functions can be written as a series (in order) of type checks.

from typing import overload, SupportsFloat, TypeVar

OurNumericsT = TypeVar("OurNumericsT", OurFloat, OurI32, OurI64)  # # etc

@overload(kind="first_match")
def foo(x: OurNumericsT) -> OurNumericsT:
    ...
@overload(kind="first_match")
def foo(x: float) -> float:
    ...
@overload(kind="first_match")
def foo(x: SupportsFloat) -> OurFloat:
    ...

The “First wins” nature here can also be checked by typecheckers that recognize narrowing patterns that match the parameters, whether by case match or isinstance chaining, allowing checking that return types match those declared. While I won’t propose this as required, it’s a possible quality of life improvement typecheckers can implement using this.

The last kind for intersecting_match is an improvement for use with intersections, but also simplifies existing cases for correctness with multiple inheritance or composition of protocols


class AIn(Protocol):
    ...

class BIn(Protocol):
    ...

class AOut(Protocol):
    ...

class BOut(Protocol):
    ...


class A(Protocol):
    def foo(self, x: AIn, /) -> AOut:  ...

class B(Protocol):
    def foo(self, x: BIn, /) -> BOut:  ...

With these, there is no way to write a unified C without either intersections + negation, ambiguous overloads, or returning a wider interface that might not be reasonable (eg. what if one of these has a property that only makes sense with A, and B doesn’t provide the info needed)

With intersections and negation, you can write:

A & B, but implementing A & B as C is difficult and verbose in cases where A & B may not be disjoint over parameters of methods, and the verbosity expands with parameters.

Without intersections and negation, and without the “intersecting match” option, it’s not possible to return the minimal interface unambiguously if the parameter sets are not disjoint.

Without the “intersecting_match” overload, but with intersections and negation, implementing the minimal interface is possible for that case.

For comparison in verbosity, this is without the intersecting match for a single parameter:

class C:
    @overload
    def foo(self, x: AIn & BIn, /) -> AOut & BOut:  ...
    @overload
    def foo(self, x: AIn & ~BIn, /) -> AOut:  ...
    @overload
    def foo(self, x: ~AIn & BIn, /) -> BOut:  ...
    def foo(self, x: Ain | BIn) -> AOut | BOut:  ...

With multiple parameters, this quickly gets out of hand in the same way that overloads already get out of hand for mixes of flags controlling behavior of functions does, as there needs to be an overload for “This but not that, that but not this, and both this and that”. The last one can be excluded for disjoint types, though use cases involving protocols are rarely disjoint.

With intersecting match, intended for exactly the cases of multiple inheritence, composition of protocols via intersections, and other cases where intersections involve overloads, the overload count does not increase combinatorically, but instead linearly.

The rules for this are almost the same as the existing overload rules, except that

  1. It’s not erroneous to have overlapping overloads
  2. When overlapping overloads are matched, the resulting type is the intersection of the overlapping matches.
  3. In the case of gradual parameters and matching, the existing union expansion rules are triggered to retain the gradual match.

The type of a concrete implementation of A & B as C with this then looks like the below:

class C:
    @overload(kind="intersecting_match")
    def foo(self, x: AIn, /) -> AOut:  ...
    @overload(kind="intersecting_match")
    def foo(self, x: BIn, /) -> BOut:  ...
    def foo(self, x: AIn | BIn, /) -> AOut | BOut:
        ...

This generally scales linearly with the number of composed classes/protocols for what users need to write.

There is still some complexity this can’t cut out if intersecting two protocols that themselves have differing overloads that are either of the other modes, but that is expected to be a significantly rare case (Intersections discussion has no sample use cases that have this), and those who have it now already can’t fully express their interface.

1 Like
2

Any tooling to help weed out the overgrowth of overloads is most welcome.
This does add some complexity. How would one teach which overload kind to employ?
It also adds some verbosity. The typing isn’t the problem, control-C control-V work, as do (LMM-supported) IDEs. Reading, though, is still human, i.e. the reading I care about, so how can we help people there? Also to avoid (assumed illegal) mixing of kinds.
Finally, how would this work at runtime? E.g. get_overloads()

3

If you’re using overloads to implement something needed for an intersection, use intersecting match.

If you’re doing isinstance or match case on types, use first match ordered the same as your checks.

Existing overloads continue to behave as they do, and will remain a reasonable default. Those that aren’t ambiguous also don’t benefit from changing, so it doesn’t introduce churn.

Some existing ambiguous overloads that can’t be made non-ambiguous currently can be fixed by switching them to first match (this comes up with protocol overlaps with concrete types), so typecheckers could reasonably implement a heuristic to point to using these when potentially needed.

Reading being the more important part is why I think this is worth proposing as part of the set of changes to come with intersections, rather than just assuming people will write out and then expect someone else to read large overload expansions with explicit negation and/or intersections. It’s manageable with small parameter counts, but it explodes beyond reasonable review very quickly. Having a way to say “let the type system handle the expansions, and do it in this way” simplifies what users need to read.

That said, I’m asking for feedback because this is ultimately just a way to make the experience nicer, and there is no functionality here that is not already covered by core parts of the intersections draft in terms of functionality.

make it a type error to mix kinds. Can be a runtime error if people want too since the decorator stores that info.

typing.get_overloads is documented as returning a sequence containing the function objects, and it does. The fact that it happens to be a list currently doesn’t mean it can’t be something else that is still a sequence, but has an attribute/property indicating the kind.

1 Like
4

Could in theory add an attribute to the function objects, too, though that might be more invasive a change than necessary

5

What about this case?

@overload(kind="first_match")
def g(x: int) -> str: ...
@overload(kind="first_match")
def g(x: object) -> bytes: ...
def g(x): ...

def caller(v: object):
    g(v)

The problem is that at runtime, v could be an int, so I don’t think we can naively say, “the first one we match is object, so the return type is bytes”.

If we consider this instead:

@overload
def g(x: int) -> str: ...
@overload
def g(x: object & ~int) -> bytes: ...
def g(x): ...

def caller(v: object):
    g(v)

Then I think a type checker would split up v: object into v: int | (object & ~int) and then using the union resolution rules of overloads, would return str | bytes, which seems more correct than just returning bytes.

I suspect “first match” might also sometimes give surprising results for functions with multiple arguments.

1 Like
6

It feels kind of redundant having to spell out x: object & ~int explicitly, because an implementation of g usually would look something like:

def g(x):
    if isinstance(x, int):
        return <some_string>
    return <some_bytes>

For me @overload always only made sense with the POV that every overload implictly removes its domain from the remaining overloads. So mathematically:

\operatorname{Overload}\bigl[f₁\colon X₁ →Y₁, f₂\colon X₂ →Y₂, \dots, fₙ\colon Xₙ→Yₙ\bigr]

defines a function that maps

  • X₁ → Y₁
  • X₂∖X₁ → Y₂
  • X₃∖(X₁∪X₂) → Y₃
  • \dots
  • Xₙ∖(X₁∪X₂∪ \dots ∪Xₙ₋₁) → Yₙ

Only when we have gradual types involved we cannot fall back to just picking the first overload, since then, we do not know which overload would get taken. But in this case one can just infer Any, or more precisely the AnyOf of the return types of all matching overloads.

I’ll admit this argument has some holes as it becomes invalid if g 's implementation does something unusual like deciding based on value rather than type what to return, like:

def g(x):
    if x == 42:
         return bytes()
    if isinstance(x, int):
         return str()
    return bytes()

But to me it seems like 99.9% of overloaded code will branch based on type and not based on value (except for boolean / string flags, but then the argument type is constant), so how valuable is it really to go all this extra mile to support this edge case? Or is it a common pattern in certain use-cases?

2 Likes
7

This is the intuition behind the “first match”. The value of this increases when trying to write out correct overloads that follow this pattern with multiple parameters, as there is no way to type a group of parameters as being negated by another group. This is a place where there would be significant blowup of overloads to manually write.

8

This is a case I didn’t include an example for here, but I agree with the conclusion in theory.

This case as presented only applies where A <: B for two possible overload choices, and the match is for B. If A and B are unrelated, but not neccessarily disjoint, then the first match behavior better mirrors what would happen with repeated type check if things like isinstance.

There are still other issues with unrelated A and B here, so I think I need to revisit how exactly first match would need to behave.

9

I wonder if this is the right direction. Maybe an alternative to consider is having

and then doing stuff like

class C:
    foo: ((self, x: AIn, /) -> AOut) & ((self, x: BIn, /) -> BOut)
    def foo(self, x: AIn | BIn, /) -> AOut | BOut: ...

or even, with typing.TypeOf (https://github.com/python/typing/issues/769),

class C:
    foo: TypeOf[A.foo] & TypeOf[B.foo]
    def foo(self, x: AIn | BIn, /) -> AOut | BOut: ...

and in more complex cases:

class C:
    foo: Overloaded[
        ((self, x: AIn, /) -> AOut) & ((self, x: BIn, /) -> BOut),
        # other overloads
        (self, x: object, *, extra_arg: object) -> object,
    ]
    def foo(*args, **kwargs): ...  # implementation

The ability to directly manipulate function types this way seems like the more holistic solution to this issue.

1 Like
10

Looking at current typechecker behavior for the following:

from typing import overload, Any, reveal_type


class A:
    ...

class B:
    ...

class X:
    ...

class Y:
    ...

class AX(A, X):
    ...

@overload
def f(x: A) -> B:  ...
@overload
def f(x: X) -> Y:  ...
def f(x: A | X) -> B | Y:
    z: Any = object()
    return z


reveal_type(f(AX()))

All of pyright, mypy, ty, and pyrefly select the first overload (revealed type of B) rather than deciding that this is ambiguous and either requiring it match both (B & Y), or be unknown which one it matches (B | Y) based on the implementation.

This holds when this is placed in a stub file as well, it’s not related to the Any use there being used to silence “no return” errors that I didn’t want to go configure for each typechecker.

So, there are some existing shortcomings in overload selection that indicate that typecheckers already rely on the checking that overloads aren’t overlapping in definitions, to (incorrectly) assume all possible callers may only match one and only select the first match.

This line of questions probably matters a lot more with intersections, but I figured it’s worth pointing out where the status quo also fails at that.

2 Likes