Brian Kearns avatar Brian Kearns committed 1ac9a04

avoid overflow in _bisect (cpython issue13496)

Comments (0)

Files changed (2)

pypy/module/_bisect/interp_bisect.py

 from pypy.interpreter.error import OperationError
 from pypy.interpreter.gateway import unwrap_spec
+from rpython.rlib.rarithmetic import intmask, r_uint
 
 
 @unwrap_spec(lo=int, hi=int)
     if hi == -1:
         hi = space.len_w(w_a)
     while lo < hi:
-        mid = (lo + hi) >> 1
+        mid = intmask((r_uint(lo) + r_uint(hi)) >> 1)
         w_litem = space.getitem(w_a, space.wrap(mid))
         if space.is_true(space.lt(w_litem, w_x)):
             lo = mid + 1
     if hi == -1:
         hi = space.len_w(w_a)
     while lo < hi:
-        mid = (lo + hi) >> 1
+        mid = intmask((r_uint(lo) + r_uint(hi)) >> 1)
         w_litem = space.getitem(w_a, space.wrap(mid))
         if space.is_true(space.lt(w_x, w_litem)):
             hi = mid

pypy/module/_bisect/test/test_bisect.py

         insort_right(a, 6.0)
         assert a == [0, 5, 6, 6, 6, 6.0, 7]
         assert map(type, a) == [int, int, int, int, int, float, int]
+
+    def test_bisect_overflow(self):
+        from _bisect import bisect_left, bisect_right
+        import sys
+
+        size = sys.maxsize
+        data = xrange(size - 1)
+        assert bisect_left(data, size - 3) == size - 3
+        assert bisect_right(data, size - 3) == size - 2
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.