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.

5 files changed, 414 insertions, 6 deletions

diff --git a/Objects/listobject.c b/Objects/listobject.c
index bd391af..3ddf032 100644
--- 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,
+            "attempt to assign list of size %d to extended slice of size %d",
+					     PyList_Size(value), slicelength);
+				return -1;
+			}
+
+			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(slicelength*sizeof(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 */
diff --git a/Objects/sliceobject.c b/Objects/sliceobject.c
index 7562d34..7499d31 100644
--- a/Objects/sliceobject.c
+++ b/Objects/sliceobject.c
@@ -109,6 +109,59 @@ PySlice_GetIndices(PySliceObject *r, int length,
 	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)
 {
diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index 89e414a..b88778e 100644
--- 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_sequence = {
 	(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, PyObject *args)
 		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 != '%') {
diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index 581ccf9..203801e 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -541,6 +541,63 @@ static PySequenceMethods tuple_as_sequence = {
 	(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 */
diff --git a/Objects/unicodeobject.c b/Objects/unicodeobject.c
index 2cb97bc..6e0fd9f 100644
--- a/Objects/unicodeobject.c
+++ b/Objects/unicodeobject.c
@@ -5061,6 +5061,58 @@ static PySequenceMethods unicode_as_sequence = {
     (objobjproc)PyUnicode_Contains, 	/*sq_contains*/
 };
 
+static PyObject*
+unicode_subscript(PyUnicodeObject* self, PyObject* item)
+{
+    if (PyInt_Check(item)) {
+        long i = PyInt_AS_LONG(item);
+        if (i < 0)
+            i += PyString_GET_SIZE(self);
+        return unicode_getitem(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 unicode_getitem(self, i);
+    } else if (PySlice_Check(item)) {
+        int start, stop, step, slicelength, cur, i;
+        Py_UNICODE* source_buf;
+        Py_UNICODE* result_buf;
+        PyObject* result;
+
+        if (PySlice_GetIndicesEx((PySliceObject*)item, PyString_GET_SIZE(self),
+				 &start, &stop, &step, &slicelength) < 0) {
+            return NULL;
+        }
+
+        if (slicelength <= 0) {
+            return PyUnicode_FromUnicode(NULL, 0);
+        } else {
+            source_buf = PyUnicode_AS_UNICODE((PyObject*)self);
+            result_buf = PyMem_MALLOC(slicelength*sizeof(Py_UNICODE));
+
+            for (cur = start, i = 0; i < slicelength; cur += step, i++) {
+                result_buf[i] = source_buf[cur];
+            }
+            
+            result = PyUnicode_FromUnicode(result_buf, slicelength);
+            PyMem_FREE(result_buf);
+            return result;
+        }
+    } else {
+        PyErr_SetString(PyExc_TypeError, "string indices must be integers");
+        return NULL;
+    }
+}
+
+static PyMappingMethods unicode_as_mapping = {
+    (inquiry)unicode_length,		/* mp_length */
+    (binaryfunc)unicode_subscript,	/* mp_subscript */
+    (objobjargproc)0,			/* mp_ass_subscript */
+};
+
 static int
 unicode_buffer_getreadbuf(PyUnicodeObject *self,
 			  int index,
@@ -5355,7 +5407,7 @@ PyObject *PyUnicode_Format(PyObject *format,
 	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) {
@@ -5817,7 +5869,7 @@ PyTypeObject PyUnicode_Type = {
     (reprfunc) unicode_repr, 		/* tp_repr */
     0, 					/* tp_as_number */
     &unicode_as_sequence, 		/* tp_as_sequence */
-    0, 					/* tp_as_mapping */
+    &unicode_as_mapping, 		/* tp_as_mapping */
     (hashfunc) unicode_hash, 		/* tp_hash*/
     0, 					/* tp_call*/
     (reprfunc) unicode_str,	 	/* tp_str */