[Python-checkins] cpython (merge 3.2 -> default): Issue #13496: Merge from 3.2

[mark.dickinson]

http://hg.python.org/cpython/rev/1a9252280f07
changeset:   76324:1a9252280f07
parent:      76321:7eca620feb10
parent:      76323:35a3a7e0d66d
user:        Mark Dickinson <mdickinson at enthought.com>
date:        Sun Apr 15 16:32:04 2012 +0100
summary:
  Issue #13496: Merge from 3.2

files:
  Lib/test/test_bisect.py |   7 +++++++
  Misc/NEWS               |   3 +++
  Modules/_bisectmodule.c |  10 ++++++++--
  3 files changed, 18 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 = range(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 range(n):
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -29,6 +29,9 @@
 Library
 -------
 
+- Issue #13496: Fix potential overflow in bisect.bisect algorithm when applied
+  to a collection of size > sys.maxsize / 2.
+
 - Have importlib take advantage of ImportError's new 'name' and 'path'
   attributes.
 
diff --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c
--- a/Modules/_bisectmodule.c
+++ b/Modules/_bisectmodule.c
@@ -21,7 +21,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;
@@ -123,7 +126,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