The mid index computation in _bisectmodule.c in both internal_bisect_right and internal_bisect_left is done with:

mid = (lo + hi) / 2; // all three variables Py_ssize_t

which is  susceptible to overflows for large arrays, which would lead to undefined behavior (and in practice almost certainly a crash with a negative index)

The fix is trivial - mid = lo + (hi - lo) / 2; - but since I'm just starting to look into the code base I may be missing some undocumented assertions that guarantee this can't happen.

This looks like a reasonable suggestion.

FWIW, I doubt there's a real issue here.  Objects in Python consume a lot more than a byte or two of memory, so the index range of a Python list is generally a lot less than ssize_t allows for.  In other words, quantify "large" in "large arrays".  How large can a Python list actually be, relative to ssize_t?  Similar reasoning accounts for why we never worry about overflow when mucking with refcounts:  the size of a refcount member  exceeds the maximum number of references that could exist.

TBH I saw this more as an opportunity to get used to the whole system, how to create a patch, etc. :) Should've made it clearer at the start that this is unlikely to ever be a problem, sorry (didn't see a way to set priority to low myself).


If my math isn't completely off, the highest possible value here is 
hi + (hi - 1) so this only occurs if hi > (MAX_SSIZE_T + 1) / 2. So this would only work out if we had such an array containing only a handful different objects. And then that's me assuming that a list is actually a thin wrapper around an array of PyObject*.

Given that we typically need at least 4 bytes just for the PyObject * pointer for each item in a list, I guess real lists are safe.

But how about list-like objects, implementing __len__ and __getitem__?  The following appears to run forever on my machine:



class SquaresList(object):
    def __init__(self, length):
        self._length = length

    def __len__(self):
        return self._length

    def __getitem__(self, index):
        if not 0 <= index <= self._length:
            raise IndexError
        return index**2


import bisect, sys

squareslist = SquaresList(sys.maxsize)
print bisect.bisect(squareslist, (sys.maxsize - 3)**2)

Very good point, Mark.

[x]range is enough to trigger the bug::
   bisect.bisect(range(sys.maxsize), sys.maxsize-3)

The fix is trivial.  I'll do it soonish.

Related bug in Java: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Do not consider any change as trivial: http://www.solipsys.co.uk/new/BinarySearchReconsidered.html (the author ran "binary search" coding challenge about 10 years ago http://www.solipsys.co.uk/b_search/ )

Here's a patch.

I think the patch is *NOT* correct. Does it work with http://bugs.python.org/msg148567, in a 32 bits python?

> I think the patch is *NOT* correct.

Can you elaborate?  It works fine for that example on a 64-bit build;  not sure why 32-bit would be any different.

The idea is just that the single cast forces the addition to be done as an addition of integers of type size_t.  Since the integers being added are (a) nonnegative and (b) both fit into a Py_ssize_t, the sum fits into a size_t without overflow, and the result of dividing the sum by 2 fits into a size_t.

(This is all assuming that 2*Py_SSIZE_T_MAX fits into a size_t, but that's a fairly safe assumption in practice.)

> Does it work with http://bugs.python.org/msg148567, in a 32 bits python?

Yes.

Perhaps adding a comment before those two lines would make the reason for the cast clearer.

Updated patch, with comment.

Thanks for the updated patch.

LGTM

New changeset 35a3a7e0d66d by Mark Dickinson in branch '3.2':
Issue 13496: Fix bisect.bisect overflow bug for large collections.
http://hg.python.org/cpython/rev/35a3a7e0d66d

New changeset 1a9252280f07 by Mark Dickinson in branch 'default':
Issue #13496: Merge from 3.2
http://hg.python.org/cpython/rev/1a9252280f07

New changeset 709af2d0e862 by Mark Dickinson in branch '2.7':
Issue 13496: Fix bisect.bisect overflow bug for large collections.
http://hg.python.org/cpython/rev/709af2d0e862