1

I noticed that the sorted builtin function has the following type hints:

@overload
def sorted(
    iterable: Iterable[SupportsRichComparisonT], # [...]
) -> list[SupportsRichComparisonT]: ...

However, if we try to write a similar sorted function with the same hints, both mypy and pyright report an error:

from __future__ import annotations
from typing import TYPE_CHECKING, Iterable

if TYPE_CHECKING:
    from _typeshed import SupportsRichComparisonT


def my_sorted_implementation(
    it: Iterable[SupportsRichComparisonT],
) -> list[SupportsRichComparisonT]:
    xs = list(it)
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            if xs[j] < xs[i]:  # Mypy/Pyright error here
                xs[i], xs[j] = xs[j], xs[i]
    return xs


assert my_sorted_implementation([3, 1, 2]) == [1, 2, 3]

The mypy error is :

report2.py:15: error: Unsupported left operand type for < (some union)  [operator]

And the pyright error:

report.py:15:16 - error: Operator "<" not supported for types "SupportsRichComparisonT@my_sorted_implementation" and "SupportsRichComparisonT@my_sorted_implementation"
    Operator "<" not supported for types "SupportsDunderGT[Any]*" and "SupportsDunderLT[Any]*" (reportOperatorIssue)

I’d like to report this somewhere but I’m not sure what the problem is in the first place. Did anyone run into this issue before?

1 Like
2

Also, note that the issue disappears if we use SupportsDunderLT instead:

from __future__ import annotations
from typing import TYPE_CHECKING, Iterable, TypeVar

if TYPE_CHECKING:
    from _typeshed import SupportsDunderLT

T = TypeVar("T", bound=SupportsDunderLT)


def my_sorted_implementation(it: Iterable[T]) -> list[T]:
    xs = list(it)
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            if xs[j] < xs[i]:
                xs[i], xs[j] = xs[j], xs[i]
    return xs


assert my_sorted_implementation([3, 1, 2]) == [1, 2, 3]

No error here, both mypy and pyright are fine with this.

3

That would be typeshed

4

Unfortunately expressing whether or not two types are comparable generically as an upper bound is really difficult with the current type system, since the runtime model is very complex. SupportsRichComparison is a trade-off that avoids most false positives at call-sites, hence why it’s used in stubs, where the implementation does not matter.

But as you point out, it’s not great in implementations, since the union leads to false positives when you actually try to compare variables of that type, since they either have to all implement __lt__ or all __gt__, it can’t be a mix.

There’s unfortunately not really a great solution to this problem. As you’ve demonstrated you can be more restrictive and use SupportsDunderLT, since that is generally what sorted wants to use under the hood anyways, but then you’re rejecting some objects that would be valid.

We would need something akin to a XOR with type unions, so the type checker knows that it doesn’t have to check all possible permutations when union members operate on each other and instead each union member just has to check whether its compatible with itself.

It might also be possible to accomplish something similar by adding support for NotRequired to Protocol, so this type can be expressed in a single Protocol, rather than a Union.

4 Likes
5

Thanks for the explanation, it’s very instructive.

It allowed me to understand the underlying issue that I couldn’t see before: when we write Iterable[SupportsRichComparison], it corresponds to Iterable[SupportsDunderLT | SupportsDunderGT]. However, if this iterable contains one element x of type SupportsDunderLT and one element y of type SupportsDunderGT , then the operations y < x and x > y will fail with a TypeError. Hence, it makes sense for the type checker to complain about it.

In order to type this properly, we would need a way to indicate that what’s provided is either an iterable containing SupportsDunderGT, or an iterator that contains SupportsDunderLT, something like:

T1 = TypeVar("T1", bound=SupportsDunderLT)
T2 = TypeVar("T2", bound=SupportsDunderGT)

@overload
def my_sorted_implementation(it: Iterable[T1]) -> list[T1]: ...

@overload
def my_sorted_implementation(it: Iterable[T2]) -> list[T2]: ...

and then have the type checker check the implementation using this information, which it cannot do at the moment. Did I get this right?

1 Like
6

Pretty much, yes.

While overloads describes this constraint more accurately, it’s a lot more verbose and it doesn’t help you with the type error in the actual implementation. Although you could always type the implementation as Iterable[Any], if you don’t want to use a type: ignore, although you might miss actual mistakes in the implementation that way, so I personally would just live with the type: ignore or settle for a more restrictive interface that requires __lt__, if the code is mostly for internal use.

For typeshed SupportsRichComparison is definitely the right trade-off, since they don’t want their stubs to provide false positives where possible or clutter their stubs with tons of overloads with only minor type safety benefits, but for your own code a different trade-off can make sense.

2 Likes