`sorted` overload resolving incorrectly with generic types

[Zac-HD]

Using Hypothesis, the following code is expected to type-check - we can in fact call sorted on a list of integers - but mypy instead complains of incompatible overloads for sorted (https://github.com/HypothesisWorks/hypothesis/issues/3296).

from hypothesis import strategies as st

st.lists(st.integers()).map(sorted)
# error: Argument to "map" of "SearchStrategy" has incompatible type overloaded function;
#        expected "Callable[[List[int]], List[SupportsRichComparisonT]]"

To ensure that this isn't just something weird in the Hypothesis internals, I've written a short reproducer on which mypy gives the same error. In both cases, the types make sense to me and pyright is satisfied, so I'm pretty sure that this is actually a mypy bug.

from typing import Callable, Generic, TypeVar
Ex = TypeVar("Ex")
T = TypeVar("T")

class Strategy(Generic[Ex]):
    def __init__(self, example: Ex) -> None:
        self.example = example

    def map(self, transform: Callable[[Ex], T]) -> "Strategy[T]":
        return Strategy(transform(self.example))

def lists(elements: Strategy[Ex]) -> Strategy[list[Ex]]:
    return Strategy([elements.example, elements.example])

s = lists(Strategy(0)).map(sorted)
# error: Argument to "map" of "Strategy" has incompatible type overloaded function;
#        expected "Callable[[List[int]], List[SupportsRichComparisonT]]"
reveal_type(s)
# Should be Strategy[list[int]], got Strategy[list[SupportsRichComparisonT`-1]]

[tmke8]

This is the type stub for sorted: https://github.com/python/typeshed/blob/master/stdlib/builtins.pyi#L1503

[isac322]

Found another reproducible exmaple.

pyright succeed to check.

from collections.abc import Callable
from typing import Protocol, TypeVar

V_contra = TypeVar("V_contra", contravariant=True)
R_co = TypeVar("R_co", covariant=True)

class Callback(Protocol[V_contra, R_co]):
    def __call__(self, __v: V_contra) -> R_co:
        ...

V = TypeVar("V")
K = TypeVar("K")
R = TypeVar("R")

def valmap(
    f: Callback[V, R],
    d: dict[K, V],
) -> dict[K, R]:
    return dict(zip(d.keys(), map(f, d.values())))

d1 = valmap(sum, {"Alice": (20, 15, 30), "Bob": (10, 35)})  # ERROR
reveal_type(d1)

d3 = valmap(lambda v: sum(v), {"Alice": (20, 15, 30), "Bob": (10, 35)})  # OK
reveal_type(d3)

def valmap2(
    f: Callable[[V], R],
    d: dict[K, V],
) -> dict[K, R]:
    return dict(zip(d.keys(), map(f, d.values())))

d12 = valmap2(sum, {"Alice": (20, 15, 30), "Bob": (10, 35)})  # ERROR
reveal_type(d12)

https://mypy-play.net/?mypy=0.961&python=3.10&gist=394f3924483c9c7ce713e5c4d6671f3e&flags=show-error-context%2Cshow-error-codes

[MarkValadez]

Just another I have just run into:

from typing import Literal, TypeVar

K = TypeVar('K')
V = TypeVar('V')

def invSortDict(d: dict[K, V], axis: Union[int, str]) -> OrderedDict[V, K]:
    if isinstance(axis, int):
        _axis: Literal[0, 1]
        if axis in (0, 1):
            _axis = axis
        else:
            raise KeyError('Int "axis" must be one of (0,1).')
    elif isinstance(axis, str):
        if axis in ('k', 'key'):
            _axis = 0
        elif axis in ('v', 'val', 'value'):
            _axis = 1
        else:
            raise KeyError('Str "axis" must be one of (k,v)')

    return OrderedDict({
        val: key for key, val in sorted(d.items(), key=lambda item: item[_axis])
    })

This is equally reported through Pylance, currently using Python 3.12.5 and mypy 1.11.2. Given the timeline of the issues I wonder if this is more likely a Standard library/ core python issue?

[erictraut]

@MarkValadez, the reason your code sample doesn't type check is that type variables K and V do not meet the requirements for sort. It requires values that support the SupportsRichComparison protocol. If you add an upper bound of SupportsRichComparison for both K and V, it will type check without error in pyright / pylance. You'll need to copy the definition of the SupportsRichComparison protocol from typeshed or import it from the useful_types library.

from useful_types import SupportsRichComparison

K = TypeVar("K", bound=SupportsRichComparison)
V = TypeVar("V", bound=SupportsRichComparison)
...