Regression with covariant type through built-in function

[daveah]

Bug Report

Regression from 1.6.1 to 1.7: when passing a simple covariant type through a builtin (like sorted) the return type becomes a wider generic based type.

To Reproduce

def foo(a: list[int] | list[str]) -> list[int] | list[str]:
    return sorted(a)

Expected Behavior

running mypy on the simple code above produces no error in 1.6.1.

Actual Behavior

error: Incompatible return value type (got "list[SupportsDunderLT[Any] | SupportsDunderGT[Any]]", expected "list[int] | list[str]")  [return-value]

Your Environment

Regression from 1.6.1 to 1.7.0. Seen on multiple python versions (3.10, 3.11)

[AlexWaygood]

Here's a self-contained repro that doesn't depend on typeshed's (complicated!) stubs for the builtin sorted() function:

from typing import Any, Callable, Iterable, Protocol, TypeVar, overload
from typing_extensions import TypeAlias

T = TypeVar("T")
T_contra = TypeVar("T_contra", contravariant=True)

class SupportsDunderLT(Protocol[T_contra]):
    def __lt__(self, __other: T_contra) -> bool: ...

class SupportsDunderGT(Protocol[T_contra]):
    def __gt__(self, __other: T_contra) -> bool: ...
    
SupportsRichComparison: TypeAlias = SupportsDunderLT[Any] | SupportsDunderGT[Any]
SupportsRichComparisonT = TypeVar("SupportsRichComparisonT", bound=SupportsRichComparison)

@overload
def sorted(iterable: Iterable[SupportsRichComparisonT], *, key: None = None) -> list[SupportsRichComparisonT]: ...
@overload
def sorted(iterable: Iterable[T], *, key: Callable[[T], SupportsRichComparison]) -> list[T]: ...
def sorted(iterable: Iterable[object], *, key: Callable[[Any], Any] | None = None) -> list[Any]:
    return list(iterable)

def foo(a: list[int] | list[str]) -> list[int] | list[str]:
    return sorted(a)

Mypy 1.6: passes.

Mypy 1.7:

main.py:24: error: Incompatible return value type (got "list[SupportsDunderLT[Any] | SupportsDunderGT[Any]]", expected "list[int] | list[str]")  [return-value]

The following snippet, however, is simplified even further, and seems to be improved on mypy 1.7:

from typing import Any, Iterable, Protocol, TypeVar
from typing_extensions import TypeAlias

T = TypeVar("T")
T_contra = TypeVar("T_contra", contravariant=True)

class SupportsDunderLT(Protocol[T_contra]):
    def __lt__(self, __other: T_contra) -> bool: ...

class SupportsDunderGT(Protocol[T_contra]):
    def __gt__(self, __other: T_contra) -> bool: ...
    
SupportsRichComparison: TypeAlias = SupportsDunderLT[Any] | SupportsDunderGT[Any]
SupportsRichComparisonT = TypeVar("SupportsRichComparisonT", bound=SupportsRichComparison)

def sorted(iterable: Iterable[SupportsRichComparisonT]) -> list[SupportsRichComparisonT]:
    return list(iterable)

def foo(a: list[int] | list[str]) -> list[int] | list[str]:
    return sorted(a)

Mypy 1.6:

main.py:20: error: Value of type variable "SupportsRichComparisonT" of "sorted" cannot be "object"  [type-var]
main.py:20: error: Incompatible return value type (got "list[object]", expected "list[int] | list[str]")  [return-value]

Mypy 1.7:

main.py:20: error: Incompatible return value type (got "list[SupportsDunderLT[Any] | SupportsDunderGT[Any]]", expected "list[int] | list[str]")  [return-value]

[AlexWaygood]

5f6961b38acd7381ff3f8071f1f31db192cba368 is the first bad commit
commit 5f6961b38acd7381ff3f8071f1f31db192cba368
Author: Ivan Levkivskyi <levkivskyi@gmail.com>
Date:   Wed Sep 27 23:34:50 2023 +0100

    Use upper bounds as fallback solutions for inference (#16184)

    Fixes https://github.com/python/mypy/issues/13220

    This looks a bit ad-hoc, but it is probably the least disruptive
    solution possible.

 mypy/solve.py                       | 35 +++++++++++++++++++++++++++++++++++
 test-data/unit/check-inference.test |  8 ++++++++
 2 files changed, 43 insertions(+)

The change in behaviour bisects to 5f6961b (cc. @ilevkivskyi)

[ilevkivskyi]

OK, this one is non-trivial. Mypy has this thing called overload union math that infers good types when an overload is called on union type(s). But it is always used as a fallback, i.e. it is not used if a single overload matched. Now mypy is smart enough to infer a value for type variable that will make first overload match the whole union. So there are two options:

• Pipe skip_unsatisfied flag that would restore the old behavior on an initial overload call attempt, to force using union math in this case. This is ugly because this will add a very niche flag to a dozen functions
• Always use union math when it gives a better inferred type. This is a simple but significant change, and may have unforeseen consequences, so we should not include this in a patch release.

I am not sure what to do here. Any opinions? cc @JukkaL

[JukkaL]

Random thought: What about always using union math if the type context has a union type? This would be a smaller change than always using union math.