SF patch 637176: list.sort crasher

Armin Rigo's Draconian but effective fix for

SF bug 453523: list.sort crasher

slightly fiddled to catch more cases of list mutation.  The dreaded
internal "immutable list type" is gone!  OTOH, if you look at a list
*while* it's being sorted now, it will appear to be empty.  Better
than a core dump.

1 files changed, 29 insertions, 96 deletions

diff --git a/Objects/listobject.c b/Objects/listobject.c
index bee284d..3e3b4d7 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -1634,8 +1634,6 @@ merge_compute_minrun(int n)
 	return n + r;
 }
 
-static PyTypeObject immutable_list_type;
-
 /* An adaptive, stable, natural mergesort.  See listsort.txt.
  * Returns Py_None on success, NULL on error.  Even in case of error, the
  * list will be some permutation of its input state (nothing is lost or
@@ -1648,7 +1646,9 @@ listsort(PyListObject *self, PyObject *args)
 	PyObject **lo, **hi;
 	int nremaining;
 	int minrun;
-	PyTypeObject *savetype;
+	int saved_ob_size;
+	PyObject **saved_ob_item;
+	PyObject **empty_ob_item;
 	PyObject *compare = NULL;
 	PyObject *result = NULL;	/* guilty until proved innocent */
 
@@ -1659,17 +1659,24 @@ listsort(PyListObject *self, PyObject *args)
 	}
 	merge_init(&ms, compare);
 
-	savetype = self->ob_type;
-	self->ob_type = &immutable_list_type;
+	/* The list is temporarily made empty, so that mutations performed
+	 * by comparison functions can't affect the slice of memory we're
+	 * sorting (allowing mutations during sorting is a core-dump
+	 * factory, since ob_item may change).
+	 */
+	saved_ob_size = self->ob_size;
+	saved_ob_item = self->ob_item;
+	self->ob_size = 0;
+	self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0);
 
-	nremaining = self->ob_size;
+	nremaining = saved_ob_size;
 	if (nremaining < 2)
 		goto succeed;
 
 	/* March over the array once, left to right, finding natural runs,
 	 * and extending short natural runs to minrun elements.
 	 */
-	lo = self->ob_item;
+	lo = saved_ob_item;
 	hi = lo + nremaining;
 	minrun = merge_compute_minrun(nremaining);
 	do {
@@ -1706,13 +1713,25 @@ listsort(PyListObject *self, PyObject *args)
 	if (merge_force_collapse(&ms) < 0)
 		goto fail;
 	assert(ms.n == 1);
-	assert(ms.pending[0].base == self->ob_item);
-	assert(ms.pending[0].len == self->ob_size);
+	assert(ms.pending[0].base == saved_ob_item);
+	assert(ms.pending[0].len == saved_ob_size);
 
 succeed:
 	result = Py_None;
 fail:
- 	self->ob_type = savetype;
+	if (self->ob_item != empty_ob_item || self->ob_size) {
+		/* The user mucked with the list during the sort. */
+		(void)list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL);
+		if (result != NULL) {
+			PyErr_SetString(PyExc_ValueError,
+					"list modified during sort");
+			result = NULL;
+		}
+	}
+	if (self->ob_item == empty_ob_item)
+		PyMem_FREE(empty_ob_item);
+	self->ob_size = saved_ob_size;
+	self->ob_item = saved_ob_item;
 	merge_freemem(&ms);
 	Py_XINCREF(result);
 	return result;
@@ -2328,92 +2347,6 @@ PyTypeObject PyList_Type = {
 };
 
 
-/* During a sort, we really can't have anyone modifying the list; it could
-   cause core dumps.  Thus, we substitute a dummy type that raises an
-   explanatory exception when a modifying operation is used.  Caveat:
-   comparisons may behave differently; but I guess it's a bad idea anyway to
-   compare a list that's being sorted... */
-
-static PyObject *
-immutable_list_op(void)
-{
-	PyErr_SetString(PyExc_TypeError,
-			"a list cannot be modified while it is being sorted");
-	return NULL;
-}
-
-static PyMethodDef immutable_list_methods[] = {
-	{"append",	(PyCFunction)immutable_list_op, METH_VARARGS},
-	{"insert",	(PyCFunction)immutable_list_op, METH_VARARGS},
-	{"extend",      (PyCFunction)immutable_list_op,  METH_O},
-	{"pop",		(PyCFunction)immutable_list_op, METH_VARARGS},
-	{"remove",	(PyCFunction)immutable_list_op, METH_VARARGS},
-	{"index",	(PyCFunction)listindex,         METH_O},
-	{"count",	(PyCFunction)listcount,         METH_O},
-	{"reverse",	(PyCFunction)immutable_list_op, METH_VARARGS},
-	{"sort",	(PyCFunction)immutable_list_op, METH_VARARGS},
-	{NULL,		NULL}		/* sentinel */
-};
-
-static int
-immutable_list_ass(void)
-{
-	immutable_list_op();
-	return -1;
-}
-
-static PySequenceMethods immutable_list_as_sequence = {
-	(inquiry)list_length,			/* sq_length */
-	(binaryfunc)list_concat,		/* sq_concat */
-	(intargfunc)list_repeat,		/* sq_repeat */
-	(intargfunc)list_item,			/* sq_item */
-	(intintargfunc)list_slice,		/* sq_slice */
-	(intobjargproc)immutable_list_ass,	/* sq_ass_item */
-	(intintobjargproc)immutable_list_ass,	/* sq_ass_slice */
-	(objobjproc)list_contains,		/* sq_contains */
-};
-
-static PyTypeObject immutable_list_type = {
-	PyObject_HEAD_INIT(&PyType_Type)
-	0,
-	"list (immutable, during sort)",
-	sizeof(PyListObject),
-	0,
-	0, /* Cannot happen */			/* tp_dealloc */
-	(printfunc)list_print,			/* tp_print */
-	0,					/* tp_getattr */
-	0,					/* tp_setattr */
-	0, /* Won't be called */		/* tp_compare */
-	(reprfunc)list_repr,			/* tp_repr */
-	0,					/* tp_as_number */
-	&immutable_list_as_sequence,		/* tp_as_sequence */
-	0,					/* tp_as_mapping */
-	list_nohash,				/* tp_hash */
-	0,					/* tp_call */
-	0,					/* tp_str */
-	PyObject_GenericGetAttr,		/* tp_getattro */
-	0,					/* tp_setattro */
-	0,					/* tp_as_buffer */
-	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
- 	list_doc,				/* tp_doc */
- 	(traverseproc)list_traverse,		/* tp_traverse */
-	0,					/* tp_clear */
-	list_richcompare,			/* tp_richcompare */
-	0,					/* tp_weaklistoffset */
-	0,					/* tp_iter */
-	0,					/* tp_iternext */
-	immutable_list_methods,			/* tp_methods */
-	0,					/* tp_members */
-	0,					/* tp_getset */
-	0,					/* tp_base */
-	0,					/* tp_dict */
-	0,					/* tp_descr_get */
-	0,					/* tp_descr_set */
-	0,					/* tp_init */
-	/* NOTE: This is *not* the standard list_type struct! */
-};
-
-
 /*********************** List Iterator **************************/
 
 typedef struct {