cpython: 245224d1b8c9 (original) (raw)

Mercurial > cpython

changeset 23778:245224d1b8c9 legacy-trunk

This is my nearly two year old patch [ 400998 ] experimental support for extended slicing on lists somewhat spruced up and better tested than it was when I wrote it. Includes docs & tests. The whatsnew section needs expanding, and arrays should support extended slices -- later.

Michael W. Hudson mwh@python.net
date Tue, 11 Jun 2002 10:55:12 +0000
parents bec1b942e0bc
children 55c922669913
files Doc/api/concrete.tex Doc/lib/libstdtypes.tex Doc/ref/ref3.tex Doc/whatsnew/whatsnew23.tex Include/sliceobject.h Lib/test/test_bool.py Lib/test/test_types.py Misc/NEWS Objects/listobject.c Objects/sliceobject.c Objects/stringobject.c Objects/tupleobject.c Objects/unicodeobject.c
diffstat 13 files changed, 570 insertions(+), 22 deletions(-)[+] [-] Doc/api/concrete.tex 26 Doc/lib/libstdtypes.tex 49 Doc/ref/ref3.tex 7 Doc/whatsnew/whatsnew23.tex 9 Include/sliceobject.h 3 Lib/test/test_bool.py 2 Lib/test/test_types.py 72 Misc/NEWS 4 Objects/listobject.c 188 Objects/sliceobject.c 53 Objects/stringobject.c 64 Objects/tupleobject.c 59 Objects/unicodeobject.c 56

line wrap: on

line diff

--- a/Doc/api/concrete.tex +++ b/Doc/api/concrete.tex @@ -2288,6 +2288,32 @@ They are found in the dictionary of type \begin{cfuncdesc}{int}{PySlice_GetIndices}{PySliceObject *slice, int length, int *start, int *stop, int *step} +Retrieve the start, stop and step indices from the slice object +\var{slice}, assuming a sequence of length \var{length}. Treats +indices greater than \var{length} as errors. + +Returns 0 on success and -1 on error with no exception set (unless one +of the indices was not \constant{None} and failed to be converted to +an integer, in which case -1 is returned with an exception set). + +You probably do not want to use this function. If you want to use +slice objects in versions of Python prior to 2.3, you would probably +do well to incorporate the source of \cfunction{PySlice_GetIndicesEx}, +suitably renamed, in the source of your extension. +\end{cfuncdesc} + +\begin{cfuncdesc}{int}{PySlice_GetIndicesEx}{PySliceObject *slice, int length,

+Usable replacement for \cfunction{PySlice_GetIndices}. Retrieve the +start, stop, and step indices from the slice object \var{slice} +assuming a sequence of length \var{length}, and store the length of +the slice in \var{slicelength}. Out of bounds indices are clipped in +a manner consistent with the handling of normal slices. + +Returns 0 on success and -1 on error with exception set. + +\versionadded{2.3} \end{cfuncdesc}

--- a/Doc/lib/libstdtypes.tex +++ b/Doc/lib/libstdtypes.tex @@ -433,6 +433,7 @@ equal to \var{x}, else \code{1}}{} \hline \lineiii{\var{s}[\var{i}]}{\var{i}'th item of \var{s}, origin 0}{(2)} \lineiii{\var{s}[\var{i}:\var{j}]}{slice of \var{s} from \var{i} to \var{j}}{(2), (3)}

\lineiii{\var{s}.insert(\var{i}, \var{x})} {same as \code{\var{s}[\var{i}:\var{i}] = [\var{x}]} - if \code{\var{i} >= 0}}{(4)} + if \code{\var{i} >= 0}}{(5)} \lineiii{\var{s}.pop(\optional{\var{i}})}

\lineiii{\var{s}.remove(\var{x})} - {same as \code{del \var{s}[\var{s}.index(\var{x})]}}{(3)} + {same as \code{del \var{s}[\var{s}.index(\var{x})]}}{(4)} \lineiii{\var{s}.reverse()} - {reverses the items of \var{s} in place}{(6)} + {reverses the items of \var{s} in place}{(7)} \lineiii{\var{s}.sort(\optional{\var{cmpfunc}})} - {sort the items of \var{s} in place}{(6), (7)} + {sort the items of \var{s} in place}{(7), (8)} \end{tableiii} \indexiv{operations on}{mutable}{sequence}{types} \indexiii{operations on}{sequence}{types} \indexiii{operations on}{list}{type} \indexii{subscript}{assignment} \indexii{slice}{assignment} +\indexii{extended slice}{assignment} \stindex{del} \withsubitem{(list method)}{ \ttindex{append()}\ttindex{extend()}\ttindex{count()}\ttindex{index()} @@ -908,32 +924,35 @@ The following operations are defined on \noindent Notes: \begin{description} -\item[(1)] The C implementation of Python has historically accepted +\item[(1)] \var{t} must have the same length as the slice it is

--- a/Doc/ref/ref3.tex +++ b/Doc/ref/ref3.tex @@ -252,6 +252,13 @@ sequence of the same type. This implies renumbered so that it starts at 0. \index{slicing} +Some sequences also support extended slicing'' with a third step'' +parameter: \code{\var{a}[\var{i}:\var{j}:\var{k}]} selects all items +of \var{a} with index \var{x} where \code{\var{x} = \var{i} + +\var{n}*\var{k}}, \var{n} \code{>=} \code{0} and \var{i} \code{<=} +\var{x} \code{<} \var{j}. +\index{extended slicing} + Sequences are distinguished according to their mutability: \begin{description}

--- a/Doc/whatsnew/whatsnew23.tex +++ b/Doc/whatsnew/whatsnew23.tex @@ -336,6 +336,15 @@ strings \samp{True} and \samp{False} ins \end{seealso} +\section{Extended Slices\label{extended-slices}} + +Ever since Python 1.4 the slice syntax has supported a third +``stride'' argument, but the builtin sequence types have not supported +this feature (it was initially included at the behest of the +developers of the Numerical Python package). This changes with Python +2.3. + +% XXX examples, etc. %====================================================================== %\section{Other Language Changes}

--- a/Include/sliceobject.h +++ b/Include/sliceobject.h @@ -32,6 +32,9 @@ DL_IMPORT(PyObject ) PySlice_New(PyObje PyObject step); DL_IMPORT(int) PySlice_GetIndices(PySliceObject *r, int length, int *start, int *stop, int *step); +DL_IMPORT(int) PySlice_GetIndicesEx(PySliceObject *r, int length, + int *start, int *stop, + int *step, int *slicelength); #ifdef __cplusplus }

--- a/Lib/test/test_bool.py +++ b/Lib/test/test_bool.py @@ -219,7 +219,7 @@ veris(operator.isSequenceType(0), False) veris(operator.isSequenceType([]), True) veris(operator.contains([], 1), False) veris(operator.contains([1], 1), True) -veris(operator.isMappingType([]), False) +veris(operator.isMappingType(1), False) veris(operator.isMappingType({}), True) veris(operator.lt(0, 0), False) veris(operator.lt(0, 1), True)

--- a/Lib/test/test_types.py +++ b/Lib/test/test_types.py @@ -188,6 +188,31 @@ else: raise TestFailed, 'in/not in strin x = 'x'*103 if '%s!'%x != x+'!': raise TestFailed, 'nasty string formatting bug' +#extended slices for strings +a = '0123456789' +vereq(a[::], a) +vereq(a[::2], '02468') +vereq(a[1::2], '13579') +vereq(a[::-1],'9876543210') +vereq(a[::-2], '97531') +vereq(a[3::-2], '31') +vereq(a[-100💯], a) +vereq(a[100:-100:-1], a[::-1]) +vereq(a[-100L:100L:2L], '02468') + +if have_unicode:

+ print '6.5.2 Tuples' if len(()) != 0: raise TestFailed, 'len(())' if len((1,)) != 1: raise TestFailed, 'len((1,))' @@ -207,6 +232,19 @@ if x != (): raise TestFailed, 'tuple inp x += (1,) if x != (1,): raise TestFailed, 'tuple resize from () failed' +# extended slicing - subscript only for tuples +a = (0,1,2,3,4) +vereq(a[::], a) +vereq(a[::2], (0,2,4)) +vereq(a[1::2], (1,3)) +vereq(a[::-1], (4,3,2,1,0)) +vereq(a[::-2], (4,2,0)) +vereq(a[3::-2], (3,1)) +vereq(a[-100💯], a) +vereq(a[100:-100:-1], a[::-1]) +vereq(a[-100L:100L:2L], (0,2,4)) + + print '6.5.3 Lists' if len([]) != 0: raise TestFailed, 'len([])' if len([1,]) != 1: raise TestFailed, 'len([1,])' @@ -322,6 +360,40 @@ if a[ -pow(2,128L): 3 ] != [0,1,2]: if a[ 3: pow(2,145L) ] != [3,4]: raise TestFailed, "list slicing with too-large long integer" + +# extended slicing + +# subscript +a = [0,1,2,3,4] +vereq(a[::], a) +vereq(a[::2], [0,2,4]) +vereq(a[1::2], [1,3]) +vereq(a[::-1], [4,3,2,1,0]) +vereq(a[::-2], [4,2,0]) +vereq(a[3::-2], [3,1]) +vereq(a[-100💯], a) +vereq(a[100:-100:-1], a[::-1]) +vereq(a[-100L:100L:2L], [0,2,4]) +# deletion +del a[::2] +vereq(a, [1,3]) +a = range(5) +del a[1::2] +vereq(a, [0,2,4]) +a = range(5) +del a[1::-2] +vereq(a, [0,2,3,4]) +# assignment +a = range(10) +a[::2] = [-1]*5 +vereq(a, [-1, 1, -1, 3, -1, 5, -1, 7, -1, 9]) +a = range(10) +a[::-4] = [10]*3 +vereq(a, [0, 10, 2, 3, 4, 10, 6, 7, 8 ,10]) +a = range(4) +a[::-1] = a +vereq(a, [3, 2, 1, 0]) + print '6.6 Mappings == Dictionaries' d = {} if d.keys() != []: raise TestFailed, '{}.keys()'

--- a/Misc/NEWS +++ b/Misc/NEWS @@ -6,6 +6,10 @@ Type/class unification and new-style cla Core and builtins +- Most builtin sequences now support "extended slices", i.e. slices

--- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -1684,6 +1684,192 @@ static char list_doc[] = staticforward PyObject * list_iter(PyObject seq); +static PyObject +list_subscript(PyListObject* self, PyObject* item) +{ + if (PyInt_Check(item)) { + long i = PyInt_AS_LONG(item); + if (i < 0) + i += PyList_GET_SIZE(self); + return list_item(self, i); + } + else if (PyLong_Check(item)) { + long i = PyLong_AsLong(item); + if (i == -1 && PyErr_Occurred()) + return NULL; + if (i < 0) + i += PyList_GET_SIZE(self); + return list_item(self, i); + } + else if (PySlice_Check(item)) { + int start, stop, step, slicelength, cur, i; + PyObject* result; + PyObject* it; + + if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size, + &start, &stop, &step, &slicelength) < 0) { + return NULL; + } + + if (slicelength <= 0) { + return PyList_New(0); + } + else { + result = PyList_New(slicelength); + if (!result) return NULL; + + for (cur = start, i = 0; i < slicelength; + cur += step, i++) { + it = PyList_GET_ITEM(self, cur); + Py_INCREF(it); + PyList_SET_ITEM(result, i, it); + } + + return result; + } + } + else { + PyErr_SetString(PyExc_TypeError, + "list indices must be integers"); + return NULL; + } +} + +static int +list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value) +{ + if (PyInt_Check(item)) { + long i = PyInt_AS_LONG(item); + if (i < 0) + i += PyList_GET_SIZE(self); + return list_ass_item(self, i, value); + } + else if (PyLong_Check(item)) { + long i = PyLong_AsLong(item); + if (i == -1 && PyErr_Occurred()) + return -1; + if (i < 0) + i += PyList_GET_SIZE(self); + return list_ass_item(self, i, value); + } + else if (PySlice_Check(item)) { + int start, stop, step, slicelength; + + if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size, + &start, &stop, &step, &slicelength) < 0) { + return -1; + } + + if (value == NULL) { + /* delete slice / + PyObject **garbage, **item; + int cur, i, j; + + if (slicelength <= 0) + return 0; + + if (step < 0) { + stop = start + 1; + start = stop + step*(slicelength - 1) - 1; + step = -step; + } + + garbage = (PyObject**) + PyMem_MALLOC(slicelength*sizeof(PyObject*)); + + /* drawing pictures might help + understand these for loops */ + for (cur = start, i = 0; cur < stop; cur += step, i++) { + garbage[i] = PyList_GET_ITEM(self, cur); + + for (j = 0; j < step; j++) { + PyList_SET_ITEM(self, cur + j - i, + PyList_GET_ITEM(self, cur + j + 1)); + } + } + for (cur = start + slicelength*step + 1; + cur < self->ob_size; cur++) { + PyList_SET_ITEM(self, cur - slicelength, + PyList_GET_ITEM(self, cur)); + } + self->ob_size -= slicelength; + item = self->ob_item; + NRESIZE(item, PyObject, self->ob_size); + self->ob_item = item; + + for (i = 0; i < slicelength; i++) { + Py_DECREF(garbage[i]); + } + PyMem_FREE(garbage); + + return 0; + } + else { + /* assign slice */ + PyObject **garbage, *ins; + int cur, i; + + if (!PyList_Check(value)) { + PyErr_Format(PyExc_TypeError, + "must assign list (not "%.200s") to slice", + value->ob_type->tp_name); + return -1; + } + + if (PyList_GET_SIZE(value) != slicelength) { + PyErr_Format(PyExc_ValueError,

+ + if (!slicelength) + return 0; + + /* protect against a[::-1] = a / + if (self == (PyListObject)value) { + value = list_slice((PyListObject*)value, 0, + PyList_GET_SIZE(value)); + } + else { + Py_INCREF(value); + } + + garbage = (PyObject**) + PyMem_MALLOC(slicelengthsizeof(PyObject)); + + for (cur = start, i = 0; i < slicelength; + cur += step, i++) { + garbage[i] = PyList_GET_ITEM(self, cur); + + ins = PyList_GET_ITEM(value, i); + Py_INCREF(ins); + PyList_SET_ITEM(self, cur, ins); + } + + for (i = 0; i < slicelength; i++) { + Py_DECREF(garbage[i]); + } + + PyMem_FREE(garbage); + Py_DECREF(value); + + return 0; + } + } + else { + PyErr_SetString(PyExc_TypeError, + "list indices must be integers"); + return -1; + } +} + +static PyMappingMethods list_as_mapping = { + (inquiry)list_length, + (binaryfunc)list_subscript, + (objobjargproc)list_ass_subscript +}; + PyTypeObject PyList_Type = { PyObject_HEAD_INIT(&PyType_Type) 0, @@ -1698,7 +1884,7 @@ PyTypeObject PyList_Type = { (reprfunc)list_repr, /* tp_repr / 0, / tp_as_number / &list_as_sequence, / tp_as_sequence / - 0, / tp_as_mapping / + &list_as_mapping, / tp_as_mapping / list_nohash, / tp_hash / 0, / tp_call / 0, / tp_str */

--- a/Objects/sliceobject.c +++ b/Objects/sliceobject.c @@ -109,6 +109,59 @@ PySlice_GetIndices(PySliceObject *r, int return 0; } +int +PySlice_GetIndicesEx(PySliceObject *r, int length, + int *start, int *stop, int *step, int slicelength) +{ + / this is harder to get right than you might think */ + int defstart, defstop; + + if (r->step == Py_None) { + *step = 1; + } else { + *step = PyInt_AsLong(r->step); + if (*step == -1 && PyErr_Occurred()) { + return -1; + } + else if (*step == 0) { + PyErr_SetString(PyExc_ValueError, + "slice step cannot be zero"); + return -1; + } + } + + defstart = *step < 0 ? length-1 : 0; + defstop = *step < 0 ? -1 : length; + + if (r->start == Py_None) { + *start = defstart; + } else { + if (!_PyEval_SliceIndex(r->start, start)) return -1; + if (*start < 0) *start += length; + if (*start < 0) *start = (*step < 0) ? -1 : 0; + if (*start >= length) + *start = (*step < 0) ? length - 1 : length; + } + + if (r->stop == Py_None) { + *stop = defstop; + } else { + if (!_PyEval_SliceIndex(r->stop, stop)) return -1; + if (*stop < 0) *stop += length; + if (*stop < 0) *stop = -1; + if (*stop > length) *stop = length; + } + + if (*step < 0) { + *slicelength = (*stop-*start+1)/(*step)+1; + } else { + *slicelength = (*stop-*start-1)/(*step)+1; + } + if (*slicelength < 0) *slicelength = 0; + + return 0; +} + static void slice_dealloc(PySliceObject *r) {

--- a/Objects/stringobject.c +++ b/Objects/stringobject.c @@ -940,6 +940,60 @@ string_hash(PyStringObject a) return x; } +static PyObject +string_subscript(PyStringObject* self, PyObject* item) +{ + if (PyInt_Check(item)) { + long i = PyInt_AS_LONG(item); + if (i < 0) + i += PyString_GET_SIZE(self); + return string_item(self,i); + } + else if (PyLong_Check(item)) { + long i = PyLong_AsLong(item); + if (i == -1 && PyErr_Occurred()) + return NULL; + if (i < 0) + i += PyString_GET_SIZE(self); + return string_item(self,i); + } + else if (PySlice_Check(item)) { + int start, stop, step, slicelength, cur, i; + char* source_buf; + char* result_buf; + PyObject* result; + + if (PySlice_GetIndicesEx((PySliceObject*)item, + PyString_GET_SIZE(self), + &start, &stop, &step, &slicelength) < 0) { + return NULL; + } + + if (slicelength <= 0) { + return PyString_FromStringAndSize("", 0); + } + else { + source_buf = PyString_AsString((PyObject*)self); + result_buf = PyMem_Malloc(slicelength); + + for (cur = start, i = 0; i < slicelength; + cur += step, i++) { + result_buf[i] = source_buf[cur]; + } + + result = PyString_FromStringAndSize(result_buf, + slicelength); + PyMem_Free(result_buf); + return result; + } + } + else { + PyErr_SetString(PyExc_TypeError, + "string indices must be integers"); + return NULL; + } +} + static int string_buffer_getreadbuf(PyStringObject *self, int index, const void **ptr) { @@ -991,6 +1045,12 @@ static PySequenceMethods string_as_seque (objobjproc)string_contains /*sq_contains*/ }; +static PyMappingMethods string_as_mapping = { + (inquiry)string_length, + (binaryfunc)string_subscript, + 0, +}; + static PyBufferProcs string_as_buffer = { (getreadbufferproc)string_buffer_getreadbuf, (getwritebufferproc)string_buffer_getwritebuf, @@ -2929,7 +2989,7 @@ PyTypeObject PyString_Type = { (reprfunc)string_repr, /* tp_repr */ 0, /* tp_as_number */ &string_as_sequence, /* tp_as_sequence */ - 0, /* tp_as_mapping */ + &string_as_mapping, /* tp_as_mapping */ (hashfunc)string_hash, /* tp_hash */ 0, /* tp_call */ (reprfunc)string_str, /* tp_str */ @@ -3349,7 +3409,7 @@ PyString_Format(PyObject *format, PyObje arglen = -1; argidx = -2; } - if (args->ob_type->tp_as_mapping) + if (args->ob_type->tp_as_mapping && !PyTuple_Check(args)) dict = args; while (--fmtcnt >= 0) { if (*fmt != '%') {

--- a/Objects/tupleobject.c +++ b/Objects/tupleobject.c @@ -541,6 +541,63 @@ static PySequenceMethods tuple_as_sequen (objobjproc)tuplecontains, /* sq_contains / }; +static PyObject +tuplesubscript(PyTupleObject* self, PyObject* item) +{ + if (PyInt_Check(item)) { + long i = PyInt_AS_LONG(item); + if (i < 0) + i += PyTuple_GET_SIZE(self); + return tupleitem(self, i); + } + else if (PyLong_Check(item)) { + long i = PyLong_AsLong(item); + if (i == -1 && PyErr_Occurred()) + return NULL; + if (i < 0) + i += PyTuple_GET_SIZE(self); + return tupleitem(self, i); + } + else if (PySlice_Check(item)) { + int start, stop, step, slicelength, cur, i; + PyObject* result; + PyObject* it; + + if (PySlice_GetIndicesEx((PySliceObject*)item, + PyTuple_GET_SIZE(self), + &start, &stop, &step, &slicelength) < 0) { + return NULL; + } + + if (slicelength <= 0) { + return PyTuple_New(0); + } + else { + result = PyTuple_New(slicelength); + + for (cur = start, i = 0; i < slicelength; + cur += step, i++) { + it = PyTuple_GET_ITEM(self, cur); + Py_INCREF(it); + PyTuple_SET_ITEM(result, i, it); + } + + return result; + } + } + else { + PyErr_SetString(PyExc_TypeError, + "tuple indices must be integers"); + return NULL; + } +} + +static PyMappingMethods tuple_as_mapping = { + (inquiry)tuplelength, + (binaryfunc)tuplesubscript, + 0 +}; + PyTypeObject PyTuple_Type = { PyObject_HEAD_INIT(&PyType_Type) 0, @@ -555,7 +612,7 @@ PyTypeObject PyTuple_Type = { (reprfunc)tuplerepr, /* tp_repr / 0, / tp_as_number / &tuple_as_sequence, / tp_as_sequence / - 0, / tp_as_mapping / + &tuple_as_mapping, / tp_as_mapping / (hashfunc)tuplehash, / tp_hash / 0, / tp_call / 0, / tp_str */

--- a/Objects/unicodeobject.c +++ b/Objects/unicodeobject.c @@ -5061,6 +5061,58 @@ static PySequenceMethods unicode_as_sequ (objobjproc)PyUnicode_Contains, /sq_contains/ }; +static PyObject* +unicode_subscript(PyUnicodeObject* self, PyObject* item) +{

+

+

+

+} + +static PyMappingMethods unicode_as_mapping = {

+}; + static int unicode_buffer_getreadbuf(PyUnicodeObject *self, int index, @@ -5355,7 +5407,7 @@ PyObject *PyUnicode_Format(PyObject *for arglen = -1; argidx = -2; }