changeset: 76325:709af2d0e862 branch: 2.7 parent: 76322:bf3b77722c9f user: Mark Dickinson date: Sun Apr 15 16:43:19 2012 +0100 files: Lib/test/test_bisect.py Misc/NEWS Modules/_bisectmodule.c description: Issue 13496: Fix bisect.bisect overflow bug for large collections. diff -r bf3b77722c9f -r 709af2d0e862 Lib/test/test_bisect.py --- a/Lib/test/test_bisect.py Sun Apr 15 15:19:06 2012 +0100 +++ b/Lib/test/test_bisect.py Sun Apr 15 16:43:19 2012 +0100 @@ -122,6 +122,13 @@ self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3), self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3), + def test_large_range(self): + # Issue 13496 + mod = self.module + data = xrange(sys.maxsize-1) + self.assertEqual(mod.bisect_left(data, sys.maxsize-3), sys.maxsize-3) + self.assertEqual(mod.bisect_right(data, sys.maxsize-3), sys.maxsize-2) + def test_random(self, n=25): from random import randrange for i in xrange(n): diff -r bf3b77722c9f -r 709af2d0e862 Misc/NEWS --- a/Misc/NEWS Sun Apr 15 15:19:06 2012 +0100 +++ b/Misc/NEWS Sun Apr 15 16:43:19 2012 +0100 @@ -48,6 +48,9 @@ Library ------- +- Issue #13496: Fix potential overflow in bisect.bisect algorithm when applied + to a collection of size > sys.maxsize / 2. + - Issue #14399: zipfile now recognizes that the archive has been modified even if only the comment is changed. As a consequence of this fix, ZipFile is now a new style class. diff -r bf3b77722c9f -r 709af2d0e862 Modules/_bisectmodule.c --- a/Modules/_bisectmodule.c Sun Apr 15 15:19:06 2012 +0100 +++ b/Modules/_bisectmodule.c Sun Apr 15 16:43:19 2012 +0100 @@ -21,7 +21,13 @@ return -1; } while (lo < hi) { - mid = (lo + hi) / 2; + /* The (size_t)cast ensures that the addition and subsequent division + are performed as unsigned operations, avoiding difficulties from + signed overflow. (See issue 13496.) */ + printf("lo: %d\n", lo); + printf("hi: %d\n", hi); + printf("mid: %d\n", mid); + mid = ((size_t)lo + hi) / 2; litem = PySequence_GetItem(list, mid); if (litem == NULL) return -1; @@ -122,7 +128,10 @@ return -1; } while (lo < hi) { - mid = (lo + hi) / 2; + /* The (size_t)cast ensures that the addition and subsequent division + are performed as unsigned operations, avoiding difficulties from + signed overflow. (See issue 13496.) */ + mid = ((size_t)lo + hi) / 2; litem = PySequence_GetItem(list, mid); if (litem == NULL) return -1;