Too restrictive types for bisect.bisect_left

[lmoureaux]

I'm not sure if this is a MyPy issue or a typeshed issue, but I think it's more likely to be in typeshed.

Consider the following minimal working example:

import bisect
from typing import Union

class MyInteger:
    def __init__(self, x: int):
        self._x = x
    def __lt__(self, other: Union[int, "MyInteger"]) -> bool:
        if isinstance(other, MyInteger):
            return self._x < other._x
        return self._x < other

integers = [MyInteger(0), MyInteger(1), MyInteger(2)]
bisect.bisect_left(integers, 1) 

The MyInteger class can be compared to itself and to normal integers. I'm using this to bisect the correct value from the list. Admittedly the bisect documentation isn't super clear regarding whether the function checks int < MyInteger or MyInteger < int. CPython, PyPy, and Jython all do the second comparison.

MyPy reports the following:

test.py:13: error: Value of type variable "SupportsRichComparisonT" of "bisect_left" cannot be "object"  [type-var]

The relevant overload for Python >= 3.10 is as follows:

    @overload
    def bisect_left(
        a: SupportsLenAndGetItem[SupportsRichComparisonT],
        x: SupportsRichComparisonT,
        lo: int = 0,
        hi: int | None = None,
        *,
        key: None = None,
    ) -> int: ...

I think x needs not be of the same type as the items in a. What matters is that a[i] < x is a valid comparison.

When a key function is provided, we have a similar case where key(a[i]) < x must be valid.

Encountered in sphinx-contrib/doxylink#63.

[Daverball]

This is one of the things of Python's object model that is nearly impossible to model correctly with generics and protocols in the type system. The framing of SupportsRichComparison is already incredibly loose and has lots of opportunities for false negatives, it just so happens, that it's extremely rare for a type to not be comparable with itself, if it's comparable at all.

You would probably need something like HKTs and/or conditional types (and multiple overloads to try both directions of the comparison) to make this work somewhat reliably.

In this case it might be fine to just change the SupportsRichComparisonT to SupportsRichComparison to get rid of the false positives, although you'd end up with a lot more false negatives, since it's rare that types are comparable to anything other than themselves or a comparable sub/supertype.

You might be better off making MyInteger a subclass of int in cases like that, so the solver can pick int as a solution. Or just type ignore the rare cases where this actually comes up as a false positive.

[lmoureaux]

Thanks @Daverball for looking into this! I just tried the following, which worked and seems more specific than the current signature:

    @overload
    def bisect_left(
        a: SupportsLenAndGetItem[SupportsDunderLT[_T]],
        x: _T,
        lo: int = 0,
        hi: int | None = None,
        *,
        key: None = None,
    ) -> int: ...

I don't understand the type system very well so I'm not sure if this introduces false positives.

The overload with a key function would look like this:

    @overload
    def bisect_left(
        a: SupportsLenAndGetItem[_T],
        x: _U,
        lo: int = 0,
        hi: int | None = None,
        *,
        key: Callable[[_T], SupportsDunderLT[_U]],
    ) -> int: ...

This works with the following code (which breaks with the current definition):

more_integers = [0, 1, 2]
bisect.bisect_left(more_integers, 1, key=lambda i: MyInteger(i))

[Daverball]

That seems like a reasonable solution, although you'd either have to change it to SupportsDunderLT[_T] | SupportsDunderGT[_T] or add separate overloads for the SupportsDunderGT case, since you only need one of them.

[Daverball]

Also if you wanted to fully support every possible case you would also need to add overloads for the reverse case, where x is comparable against the items of a or the output of the key function.

[lmoureaux]

The bisect module guarantees to only use __lt__. Existing implementations of bisect_left all do key(a[i]) < x which calls __lt__ on the output of key. Technically one could implement them with x < key(a[i]), but since no implementation seems to do that it's probably more useful to be more restrictive.

bisect_right uses the opposite comparison, x < key(a[i]), again in all implementations I checked (Cython, PyPy, rpython, Jython).

[Daverball]

That's not how < is implemented in CPython, it does not simply try to invoke __lt__ and call it a day, if the method isn't there.

It will try the most specific dunder first and if it can't find it it will try to calculate it based on the other dunders, so __lt__ and __eq__ are enough for it to be able to use < , > <= and >=, they just will not be as efficient, since it potentially involves also calling __eq__ and inverting the result.

[lmoureaux]

Hmm this is annoying. I guess the following should be fixed in the bisect documentation?

Accordingly, the functions never call an eq() method to determine whether a value has been found. Instead, the functions only call the lt() method and will return an insertion point between values in an array.

[Daverball]

That sentence is indeed a bit misleading, it should probably be framed using < and == rather than explain it using the dunders, but I wouldn't go as far as detailing the semantics of comparisons in Python's object model.

Although to be fair, you'll probably find almost no examples of classes that only implement __gt__, so for most people this will not be a relevant difference.

[lmoureaux]

Thanks for taking the time to explain this. It makes a difference for the lazy programmer who needs to use a key function and support Python 3.8 (then your only choice is to override __lt__). But I'll just swallow the type:ignore.

It took me a long time to understand that this part of the docs means that __gt__ is attempted when __lt__ is not implemented:

There are no swapped-argument versions of these methods (to be used when the left argument does not support the operation but the right argument does); rather, lt() and gt() are each other’s reflection, le() and ge() are each other’s reflection, and eq() and ne() are their own reflection. If the operands are of different types...

I guess one could insert "When a method is not implemented, its reflection is called with swapped arguments." before the "If". But I disgress.