From c8a6967ea8d983358e5e5e4965b6071daede62b3 Mon Sep 17 00:00:00 2001 From: Mark Dickinson Date: Sat, 10 Nov 2012 14:52:10 +0000 Subject: Issue #14794: slice.indices no longer returns OverflowError for out-of-range start, stop, step or length. --- Lib/test/test_slice.py | 114 +++++++++++++++++++++++++++++- Misc/NEWS | 3 + Objects/sliceobject.c | 183 ++++++++++++++++++++++++++++++++++++++++++++++--- 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\ -- cgit v0.12