sorted() does not enforce comparable items in an iterable of tuples

[jcmacdon]

sorted() does not enforce that every item in the tuple must be comparable:

items: list[tuple[int, object]] = [(1, object()), (1, object())]
sorted(items)

typeshed/stdlib/builtins.pyi

Lines 1762 to 1767 in e5c5318

	@overload
	def sorted(
	iterable: Iterable[SupportsRichComparisonT], /, *, key: None = None, reverse: bool = False
	) -> list[SupportsRichComparisonT]: ...
	@overload
	def sorted(iterable: Iterable[_T], /, *, key: Callable[[_T], SupportsRichComparison], reverse: bool = False) -> list[_T]: ...

[ajaya0]

Hi @jcmacdon ,
Can you explain the issue in more detail so that I can resolve it?

[jcmacdon]

In my example items: list[tuple[int, object]] should not be sortable because it is a tuple which contains object which is not comparable.

I think the main issue here is actually not sorted() in particular but the fact that any tuple appears to be compatible with SupportsRichComparison.

This code typechecks ok:

from _typeshed import SupportsRichComparison

tuple1: SupportsRichComparison = (1, object())
tuple2: SupportsRichComparison = (1, object())

items = [tuple1, tuple2]
sorted(items)

but if you run it, you will get a runtime error:

TypeError: '<' not supported between instances of 'object' and 'object'

[ajaya0]

Hi @jcmacdon,

Thanks for the clarification! I see the issue now. The sorted() function was allowing tuples containing non-comparable types to be sorted, which caused the TypeError at runtime.

[Daverball]

This is a problem with the SupportsRichComparison protocol in general, it's difficult to frame comparability purely as a type, so I don't think it will be possible to get rid of this false negative without type inversion.

You'd need something like this recursive type definition with type intersection and type inversion to handle this case properly

type Comparable = (SupportsRichComparison & Not[tuple[Any, ...]) | tuple[Comparable, ...]

[srittau]

I agree that type checkers should complain about the example and the example given by @KotlinIsland in #13499:

sorted(["a", 1]) 

But per @Daverball, I don't think there is anything that we can do to improve the situation without changes to type system. So I'm closing this as inexpressible for now. If you have any ideas that we have overlooked, please send an exploratory PR.