[Python-checkins] cpython (2.7): Issue 13496: Fix bisect.bisect overflow bug for large collections.
mark.dickinson
python-checkins at python.org
Sun Apr 15 17:43:47 CEST 2012
http://hg.python.org/cpython/rev/709af2d0e862
changeset: 76325:709af2d0e862
branch: 2.7
parent: 76322:bf3b77722c9f
user: Mark Dickinson <mdickinson at enthought.com>
date: Sun Apr 15 16:43:19 2012 +0100
summary:
Issue 13496: Fix bisect.bisect overflow bug for large collections.
files:
Lib/test/test_bisect.py | 7 +++++++
Misc/NEWS | 3 +++
Modules/_bisectmodule.c | 13 +++++++++++--
3 files changed, 21 insertions(+), 2 deletions(-)
diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -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 --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -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 --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c
--- a/Modules/_bisectmodule.c
+++ b/Modules/_bisectmodule.c
@@ -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;
--
Repository URL: http://hg.python.org/cpython
More information about the Python-checkins
mailing list