Improve extended slicing support in builtin types and classes. Specifically:

 - Specialcase extended slices that amount to a shallow copy the same way as
   is done for simple slices, in the tuple, string and unicode case.

 - Specialcase step-1 extended slices to optimize the common case for all
   involved types.

 - For lists, allow extended slice assignment of differing lengths as long
   as the step is 1. (Previously, 'l[:2:1] = []' failed even though
   'l[:2] = []' and 'l[:2:None] = []' do not.)

 - Implement extended slicing for buffer, array, structseq, mmap and
   UserString.UserString.

 - Implement slice-object support (but not non-step-1 slice assignment) for
   UserString.MutableString.

 - Add tests for all new functionality.

6 files changed, 261 insertions, 15 deletions

diff --git a/Objects/bufferobject.c b/Objects/bufferobject.c
index 98be771..13442c9 100644
--- a/Objects/bufferobject.c
+++ b/Objects/bufferobject.c
@@ -472,6 +472,61 @@ buffer_slice(PyBufferObject *self, Py_ssize_t left, Py_ssize_t right)
 					  right - left);
 }
 
+static PyObject *
+buffer_subscript(PyBufferObject *self, PyObject *item)
+{
+	void *p;
+	Py_ssize_t size;
+	
+	if (!get_buf(self, &p, &size, ANY_BUFFER))
+		return NULL;
+	if (PyIndex_Check(item)) {
+		Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
+		if (i == -1 && PyErr_Occurred())
+			return NULL;
+		if (i < 0)
+			i += size;
+		return buffer_item(self, i);
+	}
+	else if (PySlice_Check(item)) {
+		Py_ssize_t start, stop, step, slicelength, cur, i;
+
+		if (PySlice_GetIndicesEx((PySliceObject*)item, size,
+				 &start, &stop, &step, &slicelength) < 0) {
+			return NULL;
+		}
+
+		if (slicelength <= 0)
+			return PyString_FromStringAndSize("", 0);
+		else if (step == 1)
+			return PyString_FromStringAndSize((char *)p + start,
+							  stop - start);
+		else {
+			PyObject *result;
+			char *source_buf = (char *)p;
+			char *result_buf = (char *)PyMem_Malloc(slicelength);
+
+			if (result_buf == NULL)
+				return PyErr_NoMemory();
+
+			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,
+				"sequence index must be integer");
+		return NULL;
+	}
+}
+
 static int
 buffer_ass_item(PyBufferObject *self, Py_ssize_t idx, PyObject *other)
 {
@@ -581,6 +636,98 @@ buffer_ass_slice(PyBufferObject *self, Py_ssize_t left, Py_ssize_t right, PyObje
 	return 0;
 }
 
+static int
+buffer_ass_subscript(PyBufferObject *self, PyObject *item, PyObject *value)
+{
+	PyBufferProcs *pb;
+	void *ptr1, *ptr2;
+	Py_ssize_t selfsize;
+	Py_ssize_t othersize;
+
+	if ( self->b_readonly ) {
+		PyErr_SetString(PyExc_TypeError,
+				"buffer is read-only");
+		return -1;
+	}
+
+	pb = value ? value->ob_type->tp_as_buffer : NULL;
+	if ( pb == NULL ||
+	     pb->bf_getreadbuffer == NULL ||
+	     pb->bf_getsegcount == NULL )
+	{
+		PyErr_BadArgument();
+		return -1;
+	}
+	if ( (*pb->bf_getsegcount)(value, NULL) != 1 )
+	{
+		/* ### use a different exception type/message? */
+		PyErr_SetString(PyExc_TypeError,
+				"single-segment buffer object expected");
+		return -1;
+	}
+	if (!get_buf(self, &ptr1, &selfsize, ANY_BUFFER))
+		return -1;
+	if (PyIndex_Check(item)) {
+		Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
+		if (i == -1 && PyErr_Occurred())
+			return -1;
+		if (i < 0)
+			i += selfsize;
+		return buffer_ass_item(self, i, value);
+	}
+	else if (PySlice_Check(item)) {
+		Py_ssize_t start, stop, step, slicelength;
+		
+		if (PySlice_GetIndicesEx((PySliceObject *)item, selfsize,
+				&start, &stop, &step, &slicelength) < 0)
+			return -1;
+
+		pb = value ? value->ob_type->tp_as_buffer : NULL;
+		if (pb == NULL ||
+		    pb->bf_getreadbuffer == NULL ||
+		    pb->bf_getsegcount == NULL) {
+			PyErr_BadArgument();
+			return -1;
+		}
+		if ((*pb->bf_getsegcount)(value, NULL) != 1) {
+			/* ### use a different exception type/message? */
+			PyErr_SetString(PyExc_TypeError,
+					"single-segment buffer object expected");
+			return -1;
+		}
+		if ((othersize = (*pb->bf_getreadbuffer)(value, 0, &ptr2)) < 0)
+			return -1;
+
+		if (othersize != slicelength) {
+			PyErr_SetString(
+				PyExc_TypeError,
+				"right operand length must match slice length");
+			return -1;
+		}
+
+		if (slicelength == 0)
+			return 0;
+		else if (step == 1) {
+			memcpy((char *)ptr1 + start, ptr2, slicelength);
+			return 0;
+		}
+		else {
+			Py_ssize_t cur, i;
+			
+			for (cur = start, i = 0; i < slicelength;
+			     cur += step, i++) {
+				((char *)ptr1)[cur] = ((char *)ptr2)[i];
+			}
+
+			return 0;
+		}
+	} else {
+		PyErr_SetString(PyExc_TypeError,
+				"buffer indices must be integers");
+		return -1;
+	}
+}
+
 /* Buffer methods */
 
 static Py_ssize_t
@@ -656,6 +803,12 @@ static PySequenceMethods buffer_as_sequence = {
 	(ssizessizeobjargproc)buffer_ass_slice, /*sq_ass_slice*/
 };
 
+static PyMappingMethods buffer_as_mapping = {
+	(lenfunc)buffer_length,
+	(binaryfunc)buffer_subscript,
+	(objobjargproc)buffer_ass_subscript,
+};
+
 static PyBufferProcs buffer_as_buffer = {
 	(readbufferproc)buffer_getreadbuf,
 	(writebufferproc)buffer_getwritebuf,
@@ -676,7 +829,7 @@ PyTypeObject PyBuffer_Type = {
 	(reprfunc)buffer_repr,			/* tp_repr */
 	0,					/* tp_as_number */
 	&buffer_as_sequence,			/* tp_as_sequence */
-	0,					/* tp_as_mapping */
+	&buffer_as_mapping,			/* tp_as_mapping */
 	(hashfunc)buffer_hash,			/* tp_hash */
 	0,					/* tp_call */
 	(reprfunc)buffer_str,			/* tp_str */
diff --git a/Objects/listobject.c b/Objects/listobject.c
index ac0d018..c0621dc 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -2473,6 +2473,9 @@ list_subscript(PyListObject* self, PyObject* item)
 		if (slicelength <= 0) {
 			return PyList_New(0);
 		}
+		else if (step == 1) {
+			return list_slice(self, start, stop);
+		}
 		else {
 			result = PyList_New(slicelength);
 			if (!result) return NULL;
@@ -2516,10 +2519,15 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
 			return -1;
 		}
 
-		/* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
-		if (step == 1 && ((PySliceObject*)item)->step == Py_None)
+		if (step == 1)
 			return list_ass_slice(self, start, stop, value);
 
+		/* Make sure s[5:2] = [..] inserts at the right place:
+		   before 5, not before 2. */
+		if ((step < 0 && start < stop) ||
+		    (step > 0 && start > stop))
+			stop = start;
+
 		if (value == NULL) {
 			/* delete slice */
 			PyObject **garbage;
@@ -2541,12 +2549,16 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
 				return -1;
 			}
 
-			/* drawing pictures might help
-			   understand these for loops */
+			/* drawing pictures might help understand these for
+			   loops. Basically, we memmove the parts of the
+			   list that are *not* part of the slice: step-1
+			   items for each item that is part of the slice,
+			   and then tail end of the list that was not
+			   covered by the slice */
 			for (cur = start, i = 0;
 			     cur < stop;
 			     cur += step, i++) {
-				Py_ssize_t lim = step;
+				Py_ssize_t lim = step - 1;
 
 				garbage[i] = PyList_GET_ITEM(self, cur);
 
@@ -2558,11 +2570,12 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
 					self->ob_item + cur + 1,
 					lim * sizeof(PyObject *));
 			}
-
-			for (cur = start + slicelength*step + 1;
-			     cur < Py_Size(self); cur++) {
-				PyList_SET_ITEM(self, cur - slicelength,
-						PyList_GET_ITEM(self, cur));
+			cur = start + slicelength*step;
+			if (cur < Py_Size(self)) {
+				memmove(self->ob_item + cur - slicelength,
+					self->ob_item + cur,
+					(Py_Size(self) - cur) * 
+					 sizeof(PyObject *));
 			}
 
 			Py_Size(self) -= slicelength;
@@ -2577,7 +2590,8 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
 		}
 		else {
 			/* assign slice */
-			PyObject **garbage, *ins, *seq, **seqitems, **selfitems;
+			PyObject *ins, *seq;
+			PyObject **garbage, **seqitems, **selfitems;
 			Py_ssize_t cur, i;
 
 			/* protect against a[::-1] = a */
@@ -2587,14 +2601,17 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
 			}
 			else {
 				seq = PySequence_Fast(value,
-					"must assign iterable to extended slice");
+						      "must assign iterable "
+						      "to extended slice");
 			}
 			if (!seq)
 				return -1;
 
 			if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
 				PyErr_Format(PyExc_ValueError,
-            "attempt to assign sequence of size %zd to extended slice of size %zd",
+					"attempt to assign sequence of "
+					"size %zd to extended slice of "
+					"size %zd",
 					     PySequence_Fast_GET_SIZE(seq),
 					     slicelength);
 				Py_DECREF(seq);
diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index 4dd64f8..fb7548d 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -1222,6 +1222,17 @@ string_subscript(PyStringObject* self, PyObject* item)
 		if (slicelength <= 0) {
 			return PyString_FromStringAndSize("", 0);
 		}
+		else if (start == 0 && step == 1 &&
+			 slicelength == PyString_GET_SIZE(self) &&
+			 PyString_CheckExact(self)) {
+			Py_INCREF(self);
+			return (PyObject *)self;
+		}
+		else if (step == 1) {
+			return PyString_FromStringAndSize(
+				PyString_AS_STRING(self) + start,
+				slicelength);
+		}
 		else {
 			source_buf = PyString_AsString((PyObject*)self);
 			result_buf = (char *)PyMem_Malloc(slicelength);
diff --git a/Objects/structseq.c b/Objects/structseq.c
index 1d5ce87..fb6b96d 100644
--- a/Objects/structseq.c
+++ b/Objects/structseq.c
@@ -90,6 +90,54 @@ structseq_slice(PyStructSequence *obj, Py_ssize_t low, Py_ssize_t high)
 }
 
 static PyObject *
+structseq_subscript(PyStructSequence *self, PyObject *item)
+{
+	if (PyIndex_Check(item)) {
+		Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
+		if (i == -1 && PyErr_Occurred())
+			return NULL;
+
+		if (i < 0)
+			i += VISIBLE_SIZE(self);
+
+		if (i < 0 || i >= VISIBLE_SIZE(self)) {
+			PyErr_SetString(PyExc_IndexError,
+				"tuple index out of range");
+			return NULL;
+		}
+		Py_INCREF(self->ob_item[i]);
+		return self->ob_item[i];
+	}
+	else if (PySlice_Check(item)) {
+		Py_ssize_t start, stop, step, slicelen, cur, i;
+		PyObject *result;
+		
+		if (PySlice_GetIndicesEx((PySliceObject *)item,
+					 VISIBLE_SIZE(self), &start, &stop,
+					 &step, &slicelen) < 0) {
+			return NULL;
+		}
+		if (slicelen <= 0)
+			return PyTuple_New(0);
+		result = PyTuple_New(slicelen);
+		if (result == NULL)
+			return NULL;
+		for (cur = start, i = 0; i < slicelen;
+		     cur += step, i++) {
+			PyObject *v = self->ob_item[cur];
+			Py_INCREF(v);
+			PyTuple_SET_ITEM(result, i, v);
+		}
+		return result;
+	}
+	else {
+		PyErr_SetString(PyExc_TypeError,
+				"structseq index must be integer");
+		return NULL;
+	}
+}
+
+static PyObject *
 structseq_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 {
 	PyObject *arg = NULL;
@@ -298,6 +346,11 @@ static PySequenceMethods structseq_as_sequence = {
 	(objobjproc)structseq_contains,	        /* sq_contains */
 };
 
+static PyMappingMethods structseq_as_mapping = {
+	(lenfunc)structseq_length,
+	(binaryfunc)structseq_subscript,
+};
+
 static PyMethodDef structseq_methods[] = {
 	{"__reduce__", (PyCFunction)structseq_reduce, 
 	 METH_NOARGS, NULL},
@@ -317,7 +370,7 @@ static PyTypeObject _struct_sequence_template = {
 	(reprfunc)structseq_repr,             	/* tp_repr */
 	0,					/* tp_as_number */
 	&structseq_as_sequence,			/* tp_as_sequence */
-	0,					/* tp_as_mapping */
+	&structseq_as_mapping,			/* tp_as_mapping */
 	structseq_hash,				/* tp_hash */
 	0,              			/* tp_call */
 	0,					/* tp_str */
diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index 4d4a9ad..f1e3aee 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -603,6 +603,12 @@ tuplesubscript(PyTupleObject* self, PyObject* item)
 		if (slicelength <= 0) {
 			return PyTuple_New(0);
 		}
+		else if (start == 0 && step == 1 &&
+			 slicelength == PyTuple_GET_SIZE(self) &&
+			 PyTuple_CheckExact(self)) {
+			Py_INCREF(self);
+			return (PyObject *)self;
+		}
 		else {
 			result = PyTuple_New(slicelength);
 			if (!result) return NULL;
diff --git a/Objects/unicodeobject.c b/Objects/unicodeobject.c
index e3c5d04..db1e43d 100644
--- a/Objects/unicodeobject.c
+++ b/Objects/unicodeobject.c
@@ -7385,6 +7385,12 @@ unicode_subscript(PyUnicodeObject* self, PyObject* item)
 
         if (slicelength <= 0) {
             return PyUnicode_FromUnicode(NULL, 0);
+        } else if (start == 0 && step == 1 && slicelength == self->length &&
+                   PyUnicode_CheckExact(self)) {
+            Py_INCREF(self);
+            return (PyObject *)self;
+        } else if (step == 1) {
+            return PyUnicode_FromUnicode(self->str + start, slicelength);
         } else {
             source_buf = PyUnicode_AS_UNICODE((PyObject*)self);
             result_buf = (Py_UNICODE *)PyMem_MALLOC(slicelength*