Author: Brian Kearns <[email protected]>
Branch:
Changeset: r60708:1ac9a04e31c4
Date: 2013-01-30 02:02 -0500
http://bitbucket.org/pypy/pypy/changeset/1ac9a04e31c4/
Log: avoid overflow in _bisect (cpython issue13496)
diff --git a/pypy/module/_bisect/interp_bisect.py
b/pypy/module/_bisect/interp_bisect.py
--- a/pypy/module/_bisect/interp_bisect.py
+++ b/pypy/module/_bisect/interp_bisect.py
@@ -1,5 +1,6 @@
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)
@@ -18,7 +19,7 @@
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
@@ -43,7 +44,7 @@
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
diff --git a/pypy/module/_bisect/test/test_bisect.py
b/pypy/module/_bisect/test/test_bisect.py
--- a/pypy/module/_bisect/test/test_bisect.py
+++ b/pypy/module/_bisect/test/test_bisect.py
@@ -89,3 +89,12 @@
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
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
