python versions of bisect_right and bisect_left can fail guarantees

[mike-neergaard]

Bug report

Bug description:

The documentation for bisect.bisect_right and bisect.bisect_left states in both cases that

The returned insertion point ip partitions the array a into two slices such that
all(elem <= x for elem in a[lo : ip]) is true for the left slice and
all(elem > x for elem in a[ip : hi]) is true for the right slice.

But in the python version of bisect, that guarantee can fail:

import sys
import _bisect as c_bisect
sys.modules['_bisect'] = None
import bisect as py_bisect

def check_guarantees(bisect_func, a, x, lo, hi):
    ip = bisect_func(a, x, lo, hi)
    check_pass = True 
    if not all(elem <= x for elem in a[lo : ip]): 
        print("\tFAIL. Elements of",a[lo:ip]," are not <=",x)
        check_pass = False
    if not all(elem > x for elem in a[ip : hi]):
        print("\tFAIL. Elements of",a[ip:hi]," are not >",x)
        check_pass = False
    if  check_pass: print("\tOk")

#print(c_bisect.bisect_right) # <built-in function bisect_right>
#print(py_bisect.bisect_right) # <function bisect_right at 0x0000023164AE7C40>

a = [0,1,2,3,4]
x = 8
lo = 3
hi = -1

print("bisect_left from C")
check_guarantees(c_bisect.bisect_left, a, x, lo, hi)

print("bisect_left from python")
check_guarantees(py_bisect.bisect_left, a, x, lo, hi)

print("bisect_right from C")
check_guarantees(c_bisect.bisect_right, a, x, lo, hi)

print("bisect_right from python")
check_guarantees(py_bisect.bisect_right, a, x, lo, hi)

Attempt this online
Outputs :

bisect_left from C
	Ok
bisect_left from python
	FAIL. Elements of [3]  are not > 8
bisect_right from C
	Ok
bisect_right from python
	FAIL. Elements of [3]  are not > 8

I think there is an extra check in the C version for hi < 0.

CPython versions tested on:

3.13

Operating systems tested on:

Linux

Linked PRs

• gh-125889: Fix bounds check of hi argument in bisect_left|right functions #125915

[tomasr8]

I think neither the Python nor the C implementation are actually meant to work with a negative hi argument. The C implementation does special case hi == -1 but that's only because it is the default value produced by argument clinic when you omit hi (same for the Python case when hi is None).

We could either make it an error to pass a negative value as is the case with lo currently, or fix it to work with negative values.

cc @rhettinger since you last worked on this module

[mike-neergaard]

Bounds checking sounds great to me.

[rruuaanng]

If there are no other objections, I will initiate a PR that will synchronize the hi check with lo.

diff --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c
index 56322c48b7c..668e475cb5c 100644
--- a/Modules/_bisectmodule.c
+++ b/Modules/_bisectmodule.c
@@ -61,7 +61,7 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
         PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
         return -1;
     }
-    if (hi == -1) {
+    if (hi < 0) {
         hi = PySequence_Size(list);
         if (hi < 0)
             return -1;
@@ -245,7 +245,7 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
         PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
         return -1;
     }
-    if (hi == -1) {
+    if (hi < 0) {
         hi = PySequence_Size(list);
         if (hi < 0)
             return -1;

Alternatively, negative numbers are not allowed, consistent with lo.

[rruuaanng]

For the two solutions mentioned by

1. We could either make it an error to pass a negative value as is the case with lo currently.
2. fix it to work with negative values.

I chose the latter because almost all test functions in the test assume that when hi is a negative number, there will be a default processing. But I don't want to refactor this test on a large scale, so I chose the latter, and in the test, it mainly judges that when its hi is a negative number, it can automatically handle it. Is negative and it is not negative 1, it can be negative infinity.

[tomasr8]

I appreciate your enthusiasm @rruuaanng but for future reference, I think it'd be better to wait a bit before opening a PR as this issue is relatively recent and many people probably haven't had the time to comment on it yet. For instance, it is still not clear which of the two options I suggested we should go for (or some other option I didn't think of).

[rruuaanng]

I'm looking forward to the final result of the discussion. Maybe we can put PR on hold for the time being and wait for the result of the discussion.

[picnixz]

My 2 cents:

• Idea 1: reject negative values for hi and change the sentinel value in both the Python and the C implementation.
• Idea 2: make it work with negative values. It does not make sense however to only make negative hi work so we'll need to change the behaviour of a negative lo.
• Idea 3: do nothing and document that the values should be non-negative. This is in between the status quo and idea 1. The Python implementation is generally not used because it's slower and I don't know when we cannot have the C implementation.

Personally, I think it should be fine with idea 1. By the way, we can ask AC to use a different sentinel value with some c_default IIRC.

[rruuaanng]

I agree with Bénédikt. However, if you make the hi argument consistent with the check for lo, you may need to refactor test_bisect.py, as it seems that many of the tests there already assume that hi can be negative and ignore the check for it (I've tried it)

[picnixz]

It's not an issue to refactor tests since consistency is usually preferred. However, before implementing anything, let us first decide whether we want to reject or accept negative values first.