Issue #14794: slice.indices no longer returns OverflowError for out-of-range start, stop, step or length.

3 files changed, 291 insertions, 9 deletions

diff --git a/Lib/test/test_slice.py b/Lib/test/test_slice.py
index 2df9271..9203d5e 100644
--- a/Lib/test/test_slice.py
+++ b/Lib/test/test_slice.py
@@ -4,8 +4,70 @@ import unittest
 from test import support
 from pickle import loads, dumps
 
+import itertools
+import operator
 import sys
 
+
+def evaluate_slice_index(arg):
+    """
+    Helper function to convert a slice argument to an integer, and raise
+    TypeError with a suitable message on failure.
+
+    """
+    if hasattr(arg, '__index__'):
+        return operator.index(arg)
+    else:
+        raise TypeError(
+            "slice indices must be integers or "
+            "None or have an __index__ method")
+
+def slice_indices(slice, length):
+    """
+    Reference implementation for the slice.indices method.
+
+    """
+    # Compute step and length as integers.
+    length = operator.index(length)
+    step = 1 if slice.step is None else evaluate_slice_index(slice.step)
+
+    # Raise ValueError for negative length or zero step.
+    if length < 0:
+        raise ValueError("length should not be negative")
+    if step == 0:
+        raise ValueError("slice step cannot be zero")
+
+    # Find lower and upper bounds for start and stop.
+    lower = -1 if step < 0 else 0
+    upper = length - 1 if step < 0 else length
+
+    # Compute start.
+    if slice.start is None:
+        start = upper if step < 0 else lower
+    else:
+        start = evaluate_slice_index(slice.start)
+        start = max(start + length, lower) if start < 0 else min(start, upper)
+
+    # Compute stop.
+    if slice.stop is None:
+        stop = lower if step < 0 else upper
+    else:
+        stop = evaluate_slice_index(slice.stop)
+        stop = max(stop + length, lower) if stop < 0 else min(stop, upper)
+
+    return start, stop, step
+
+
+# Class providing an __index__ method.  Used for testing slice.indices.
+
+class MyIndexable(object):
+    def __init__(self, value):
+        self.value = value
+
+    def __index__(self):
+        return self.value
+
+
 class SliceTest(unittest.TestCase):
 
     def test_constructor(self):
@@ -75,6 +137,22 @@ class SliceTest(unittest.TestCase):
         s = slice(obj)
         self.assertTrue(s.stop is obj)
 
+    def check_indices(self, slice, length):
+        try:
+            actual = slice.indices(length)
+        except ValueError:
+            actual = "valueerror"
+        try:
+            expected = slice_indices(slice, length)
+        except ValueError:
+            expected = "valueerror"
+        self.assertEqual(actual, expected)
+
+        if length >= 0 and slice.step != 0:
+            actual = range(*slice.indices(length))
+            expected = range(length)[slice]
+            self.assertEqual(actual, expected)
+
     def test_indices(self):
         self.assertEqual(slice(None           ).indices(10), (0, 10,  1))
         self.assertEqual(slice(None,  None,  2).indices(10), (0, 10,  2))
@@ -108,7 +186,41 @@ class SliceTest(unittest.TestCase):
 
         self.assertEqual(list(range(10))[::sys.maxsize - 1], [0])
 
-        self.assertRaises(OverflowError, slice(None).indices, 1<<100)
+        # Check a variety of start, stop, step and length values, including
+        # values exceeding sys.maxsize (see issue #14794).
+        vals = [None, -2**100, -2**30, -53, -7, -1, 0, 1, 7, 53, 2**30, 2**100]
+        lengths = [0, 1, 7, 53, 2**30, 2**100]
+        for slice_args in itertools.product(vals, repeat=3):
+            s = slice(*slice_args)
+            for length in lengths:
+                self.check_indices(s, length)
+        self.check_indices(slice(0, 10, 1), -3)
+
+        # Negative length should raise ValueError
+        with self.assertRaises(ValueError):
+            slice(None).indices(-1)
+
+        # Zero step should raise ValueError
+        with self.assertRaises(ValueError):
+            slice(0, 10, 0).indices(5)
+
+        # Using a start, stop or step or length that can't be interpreted as an
+        # integer should give a TypeError ...
+        with self.assertRaises(TypeError):
+            slice(0.0, 10, 1).indices(5)
+        with self.assertRaises(TypeError):
+            slice(0, 10.0, 1).indices(5)
+        with self.assertRaises(TypeError):
+            slice(0, 10, 1.0).indices(5)
+        with self.assertRaises(TypeError):
+            slice(0, 10, 1).indices(5.0)
+
+        # ... but it should be fine to use a custom class that provides index.
+        self.assertEqual(slice(0, 10, 1).indices(5), (0, 5, 1))
+        self.assertEqual(slice(MyIndexable(0), 10, 1).indices(5), (0, 5, 1))
+        self.assertEqual(slice(0, MyIndexable(10), 1).indices(5), (0, 5, 1))
+        self.assertEqual(slice(0, 10, MyIndexable(1)).indices(5), (0, 5, 1))
+        self.assertEqual(slice(0, 10, 1).indices(MyIndexable(5)), (0, 5, 1))
 
     def test_setslice_without_getslice(self):
         tmp = []
diff --git a/Misc/NEWS b/Misc/NEWS
index a99ecc6..727663c 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,9 @@ What's New in Python 3.4.0 Alpha 1?
 Core and Builtins
 -----------------
 
+- Issue #14794: Fix slice.indices to return correct results for huge values,
+  rather than raising OverflowError.
+
 - Issue #15001: fix segfault on "del sys.module['__main__']". Patch by Victor
   Stinner.
 
diff --git a/Objects/sliceobject.c b/Objects/sliceobject.c
index 1593335..4b31f23 100644
--- a/Objects/sliceobject.c
+++ b/Objects/sliceobject.c
@@ -299,25 +299,192 @@ static PyMemberDef slice_members[] = {
     {0}
 };
 
+/* Helper function to convert a slice argument to a PyLong, and raise TypeError
+   with a suitable message on failure. */
+
 static PyObject*
-slice_indices(PySliceObject* self, PyObject* len)
+evaluate_slice_index(PyObject *v)
 {
-    Py_ssize_t ilen, start, stop, step, slicelength;
+    if (PyIndex_Check(v)) {
+        return PyNumber_Index(v);
+    }
+    else {
+        PyErr_SetString(PyExc_TypeError,
+                        "slice indices must be integers or "
+                        "None or have an __index__ method");
+        return NULL;
+    }
+}
 
-    ilen = PyNumber_AsSsize_t(len, PyExc_OverflowError);
+/* Implementation of slice.indices. */
+
+static PyObject*
+slice_indices(PySliceObject* self, PyObject* len)
+{
+    PyObject *start=NULL, *stop=NULL, *step=NULL;
+    PyObject *length=NULL, *upper=NULL, *lower=NULL, *zero=NULL;
+    int step_is_negative, cmp;
 
-    if (ilen == -1 && PyErr_Occurred()) {
+    zero = PyLong_FromLong(0L);
+    if (zero == NULL)
         return NULL;
+
+    /* Compute step and length as integers. */
+    length = PyNumber_Index(len);
+    if (length == NULL)
+        goto error;
+
+    if (self->step == Py_None)
+        step = PyLong_FromLong(1L);
+    else
+        step = evaluate_slice_index(self->step);
+    if (step == NULL)
+        goto error;
+
+    /* Raise ValueError for negative length or zero step. */
+    cmp = PyObject_RichCompareBool(length, zero, Py_LT);
+    if (cmp < 0) {
+        goto error;
+    }
+    if (cmp) {
+        PyErr_SetString(PyExc_ValueError,
+                        "length should not be negative");
+        goto error;
     }
 
-    if (PySlice_GetIndicesEx((PyObject*)self, ilen, &start, &stop,
-                             &step, &slicelength) < 0) {
-        return NULL;
+    cmp = PyObject_RichCompareBool(step, zero, Py_EQ);
+    if (cmp < 0) {
+        goto error;
+    }
+    if (cmp) {
+        PyErr_SetString(PyExc_ValueError,
+                        "slice step cannot be zero");
+        goto error;
     }
 
-    return Py_BuildValue("(nnn)", start, stop, step);
+    /* Find lower and upper bounds for start and stop. */
+    step_is_negative = PyObject_RichCompareBool(step, zero, Py_LT);
+    if (step_is_negative < 0) {
+        goto error;
+    }
+    if (step_is_negative) {
+        lower = PyLong_FromLong(-1L);
+        if (lower == NULL)
+            goto error;
+
+        upper = PyNumber_Add(length, lower);
+        if (upper == NULL)
+            goto error;
+    }
+    else {
+        lower = zero;
+        Py_INCREF(lower);
+        upper = length;
+        Py_INCREF(upper);
+    }
+
+    /* Compute start. */
+    if (self->start == Py_None) {
+        start = step_is_negative ? upper : lower;
+        Py_INCREF(start);
+    }
+    else {
+        start = evaluate_slice_index(self->start);
+        if (start == NULL)
+            goto error;
+
+        cmp = PyObject_RichCompareBool(start, zero, Py_LT);
+        if (cmp < 0)
+            goto error;
+        if (cmp) {
+            /* start += length */
+            PyObject *tmp = PyNumber_Add(start, length);
+            Py_DECREF(start);
+            start = tmp;
+            if (start == NULL)
+                goto error;
+
+            cmp = PyObject_RichCompareBool(start, lower, Py_LT);
+            if (cmp < 0)
+                goto error;
+            if (cmp) {
+                Py_INCREF(lower);
+                Py_DECREF(start);
+                start = lower;
+            }
+        }
+        else {
+            cmp = PyObject_RichCompareBool(start, upper, Py_GT);
+            if (cmp < 0)
+                goto error;
+            if (cmp) {
+                Py_INCREF(upper);
+                Py_DECREF(start);
+                start = upper;
+            }
+        }
+    }
+
+    /* Compute stop. */
+    if (self->stop == Py_None) {
+        stop = step_is_negative ? lower : upper;
+        Py_INCREF(stop);
+    }
+    else {
+        stop = evaluate_slice_index(self->stop);
+        if (stop == NULL)
+            goto error;
+
+        cmp = PyObject_RichCompareBool(stop, zero, Py_LT);
+        if (cmp < 0)
+            goto error;
+        if (cmp) {
+            /* stop += length */
+            PyObject *tmp = PyNumber_Add(stop, length);
+            Py_DECREF(stop);
+            stop = tmp;
+            if (stop == NULL)
+                goto error;
+
+            cmp = PyObject_RichCompareBool(stop, lower, Py_LT);
+            if (cmp < 0)
+                goto error;
+            if (cmp) {
+                Py_INCREF(lower);
+                Py_DECREF(stop);
+                stop = lower;
+            }
+        }
+        else {
+            cmp = PyObject_RichCompareBool(stop, upper, Py_GT);
+            if (cmp < 0)
+                goto error;
+            if (cmp) {
+                Py_INCREF(upper);
+                Py_DECREF(stop);
+                stop = upper;
+            }
+        }
+    }
+
+    Py_DECREF(upper);
+    Py_DECREF(lower);
+    Py_DECREF(length);
+    Py_DECREF(zero);
+    return Py_BuildValue("(NNN)", start, stop, step);
+
+  error:
+    Py_XDECREF(start);
+    Py_XDECREF(stop);
+    Py_XDECREF(step);
+    Py_XDECREF(upper);
+    Py_XDECREF(lower);
+    Py_XDECREF(length);
+    Py_XDECREF(zero);
+    return NULL;
 }
 
+
 PyDoc_STRVAR(slice_indices_doc,
 "S.indices(len) -> (start, stop, stride)\n\
 \n\