Issues #16029, #16030: Fix pickling and repr of large xranges.

3 files changed, 110 insertions, 5 deletions

diff --git a/Lib/test/test_xrange.py b/Lib/test/test_xrange.py
index e3c799e822..83c0e415b7 100644
--- a/Lib/test/test_xrange.py
+++ b/Lib/test/test_xrange.py
@@ -46,6 +46,28 @@ class XrangeTest(unittest.TestCase):
                 self.fail('{}: wrong element at position {};'
                           'expected {}, got {}'.format(test_id, i, y, x))
 
+    def assert_xranges_equivalent(self, x, y):
+        # Check that two xrange objects are equivalent, in the sense of the
+        # associated sequences being the same.  We want to use this for large
+        # xrange objects, so instead of converting to lists and comparing
+        # directly we do a number of indirect checks.
+        if len(x) != len(y):
+            self.fail('{} and {} have different '
+                      'lengths: {} and {} '.format(x, y, len(x), len(y)))
+        if len(x) >= 1:
+            if x[0] != y[0]:
+                self.fail('{} and {} have different initial '
+                          'elements: {} and {} '.format(x, y, x[0], y[0]))
+            if x[-1] != y[-1]:
+                self.fail('{} and {} have different final '
+                          'elements: {} and {} '.format(x, y, x[-1], y[-1]))
+        if len(x) >= 2:
+            x_step = x[1] - x[0]
+            y_step = y[1] - y[0]
+            if x_step != y_step:
+                self.fail('{} and {} have different step: '
+                          '{} and {} '.format(x, y, x_step, y_step))
+
     def test_xrange(self):
         self.assertEqual(list(xrange(3)), [0, 1, 2])
         self.assertEqual(list(xrange(1, 5)), [1, 2, 3, 4])
@@ -104,6 +126,59 @@ class XrangeTest(unittest.TestCase):
                 self.assertEqual(list(pickle.loads(pickle.dumps(r, proto))),
                                  list(r))
 
+        M = min(sys.maxint, sys.maxsize)
+        large_testcases = testcases + [
+            (0, M, 1),
+            (M, 0, -1),
+            (0, M, M - 1),
+            (M // 2, M, 1),
+            (0, -M, -1),
+            (0, -M, 1 - M),
+            (-M, M, 2),
+            (-M, M, 1024),
+            (-M, M, 10585),
+            (M, -M, -2),
+            (M, -M, -1024),
+            (M, -M, -10585),
+            ]
+        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
+            for t in large_testcases:
+                r = xrange(*t)
+                r_out = pickle.loads(pickle.dumps(r, proto))
+                self.assert_xranges_equivalent(r_out, r)
+
+    def test_repr(self):
+        # Check that repr of an xrange is a valid representation
+        # of that xrange.
+
+        # Valid xranges have at most min(sys.maxint, sys.maxsize) elements.
+        M = min(sys.maxint, sys.maxsize)
+
+        testcases = [
+            (13,),
+            (0, 11),
+            (-22, 10),
+            (20, 3, -1),
+            (13, 21, 3),
+            (-2, 2, 2),
+            (0, M, 1),
+            (M, 0, -1),
+            (0, M, M - 1),
+            (M // 2, M, 1),
+            (0, -M, -1),
+            (0, -M, 1 - M),
+            (-M, M, 2),
+            (-M, M, 1024),
+            (-M, M, 10585),
+            (M, -M, -2),
+            (M, -M, -1024),
+            (M, -M, -10585),
+            ]
+        for t in testcases:
+            r = xrange(*t)
+            r_out = eval(repr(r))
+            self.assert_xranges_equivalent(r, r_out)
+
     def test_range_iterators(self):
         # see issue 7298
         limits = [base + jiggle
diff --git a/Misc/NEWS b/Misc/NEWS
index 00ec44b93b..d6aa34b736 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -9,6 +9,12 @@ What's New in Python 2.7.4
 Core and Builtins
 -----------------
 
+- Issue #16030: Fix overflow bug in computing the `repr` of an xrange object
+  with large start, step or length.
+
+- Issue #16029: Fix overflow bug occurring when pickling xranges with large
+  start, step or length.
+
 - Issue #16037: Limit httplib's _read_status() function to work around broken
   HTTP servers and reduce memory usage. It's actually a backport of a Python
   3.2 fix. Thanks to Adrien Kunysz.
diff --git a/Objects/rangeobject.c b/Objects/rangeobject.c
index 4e64dbab39..c602e7dcfd 100644
--- a/Objects/rangeobject.c
+++ b/Objects/rangeobject.c
@@ -37,6 +37,30 @@ get_len_of_range(long lo, long hi, long step)
     return 0UL;
 }
 
+/* Return a stop value suitable for reconstructing the xrange from
+ * a (start, stop, step) triple.  Used in range_repr and range_reduce.
+ * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX].
+ */
+static long
+get_stop_for_range(rangeobject *r)
+{
+    long last;
+
+    if (r->len == 0)
+        return r->start;
+
+    /* The tricky bit is avoiding overflow.  We first compute the last entry in
+       the xrange, start + (len - 1) * step, which is guaranteed to lie within
+       the range of a long, and then add step to it.  See the range_reverse
+       comments for an explanation of the casts below.
+    */
+    last = (long)(r->start + (unsigned long)(r->len - 1) * r->step);
+    if (r->step > 0)
+        return last > LONG_MAX - r->step ? LONG_MAX : last + r->step;
+    else
+        return last < LONG_MIN - r->step ? LONG_MIN : last + r->step;
+}
+
 static PyObject *
 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
 {
@@ -112,17 +136,17 @@ range_repr(rangeobject *r)
 
     if (r->start == 0 && r->step == 1)
         rtn = PyString_FromFormat("xrange(%ld)",
-                                  r->start + r->len * r->step);
+                                  get_stop_for_range(r));
 
     else if (r->step == 1)
         rtn = PyString_FromFormat("xrange(%ld, %ld)",
                                   r->start,
-                                  r->start + r->len * r->step);
+                                  get_stop_for_range(r));
 
     else
         rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",
                                   r->start,
-                                  r->start + r->len * r->step,
+                                  get_stop_for_range(r),
                                   r->step);
     return rtn;
 }
@@ -131,9 +155,9 @@ range_repr(rangeobject *r)
 static PyObject *
 range_reduce(rangeobject *r, PyObject *args)
 {
-    return Py_BuildValue("(O(iii))", Py_TYPE(r),
+    return Py_BuildValue("(O(lll))", Py_TYPE(r),
                          r->start,
-                         r->start + r->len * r->step,
+                         get_stop_for_range(r),
                          r->step);
 }