* drop the unreasonable list invariant that ob_item should never come back

  to NULL during the lifetime of the object.

* listobject.c nevertheless did not conform to the other invariants,
  either; fixed.

* listobject.c now uses list_clear() as the obvious internal way to clear
  a list, instead of abusing list_ass_slice() for that.  It makes it easier
  to enforce the invariant about ob_item == NULL.

* listsort() sets allocated to -1 during sort; any mutation will set it
  to a value >= 0, so it is a safe way to detect mutation.  A negative
  value for allocated does not cause a problem elsewhere currently.
  test_sort.py has a new test for this fix.

* listsort() leak: if items were added to the list during the sort, AND if
  these items had a __del__ that puts still more stuff into the list,
  then this more stuff (and the PyObject** array to hold them) were
  overridden at the end of listsort() and never released.

3 files changed, 64 insertions, 31 deletions

diff --git a/Include/listobject.h b/Include/listobject.h
index ffce029..43048d3 100644
--- a/Include/listobject.h
+++ b/Include/listobject.h
@@ -30,9 +30,7 @@ typedef struct {
      *     0 <= ob_size <= allocated
      *     len(list) == ob_size
      *     ob_item == NULL implies ob_size == allocated == 0
-     *     If ob_item ever becomes non-NULL, it remains non-NULL for the
-     *         life of the list object.  The check for mutation in list.sort()
-     *         relies on this odd detail.
+     * list.sort() temporarily sets allocated to -1 to detect mutations.
      */
     int allocated;
 } PyListObject;
diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py
index 5d670a8..09dc649 100644
--- a/Lib/test/test_sort.py
+++ b/Lib/test/test_sort.py
@@ -150,6 +150,23 @@ class TestBugs(unittest.TestCase):
         L.sort(None)
         self.assertEqual(L, range(50))
 
+    def test_undetected_mutation(self):
+        # Python 2.4a1 did not always detect mutation
+        memorywaster = []
+        for i in range(20):
+            def mutating_cmp(x, y):
+                L.append(3)
+                L.pop()
+                return cmp(x, y)
+            L = [1,2]
+            self.assertRaises(ValueError, L.sort, mutating_cmp)
+            def mutating_cmp(x, y):
+                L.append(3)
+                del L[:]
+                return cmp(x, y)
+            self.assertRaises(ValueError, L.sort, mutating_cmp)
+            memorywaster = [memorywaster]
+
 #==============================================================================
 
 class TestDecorateSortUndecorate(unittest.TestCase):
diff --git a/Objects/listobject.c b/Objects/listobject.c
index ab8cc1f..452ffe5 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -486,6 +486,29 @@ list_repeat(PyListObject *a, int n)
 }
 
 static int
+list_clear(PyListObject *a)
+{
+	int i;
+	PyObject **item = a->ob_item;
+	if (item != NULL) {
+		/* Because XDECREF can recursively invoke operations on
+		   this list, we make it empty first. */
+		i = a->ob_size;
+		a->ob_size = 0;
+		a->ob_item = NULL;
+		a->allocated = 0;
+		while (--i >= 0) {
+			Py_XDECREF(item[i]);
+		}
+		PyMem_FREE(item);
+	}
+	/* Never fails; the return value can be ignored.
+	   Note that there is no guarantee that the list is actually empty
+	   at this point, because XDECREF may have populated it again! */
+	return 0;
+}
+
+static int
 list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
 {
 	/* Because [X]DECREF can recursively invoke list operations on
@@ -530,8 +553,13 @@ list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
 		ihigh = ilow;
 	else if (ihigh > a->ob_size)
 		ihigh = a->ob_size;
-	item = a->ob_item;
+
 	d = n - (ihigh-ilow);
+	if (a->ob_size + d == 0) {
+		Py_XDECREF(v_as_SF);
+		return list_clear(a);
+	}
+	item = a->ob_item;
 	if (ihigh > ilow) {
 		p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
 		if (recycle == NULL) {
@@ -576,10 +604,6 @@ list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
 			Py_XDECREF(*p);
 		PyMem_DEL(recycle);
 	}
-	if (a->ob_size == 0 && a->ob_item != NULL) {
-		PyMem_FREE(a->ob_item);
-		a->ob_item = NULL;
-	}
 	Py_XDECREF(v_as_SF);
 	return 0;
 #undef b
@@ -609,12 +633,7 @@ list_inplace_repeat(PyListObject *self, int n)
 	}
 
 	if (n < 1) {
-		items = self->ob_item;
-		self->ob_item = NULL;
-		self->ob_size = 0;
-		for (i = 0; i < size; i++)
-			Py_XDECREF(items[i]);
-		PyMem_DEL(items);
+		(void)list_clear(self);
 		Py_INCREF(self);
 		return (PyObject *)self;
 	}
@@ -1908,6 +1927,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
 	int minrun;
 	int saved_ob_size, saved_allocated;
 	PyObject **saved_ob_item;
+	PyObject **final_ob_item;
 	PyObject *compare = NULL;
 	PyObject *result = NULL;	/* guilty until proved innocent */
 	int reverse = 0;
@@ -1942,8 +1962,9 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
 	saved_ob_size = self->ob_size;
 	saved_ob_item = self->ob_item;
 	saved_allocated = self->allocated;
-	self->ob_size = self->allocated = 0;
+	self->ob_size = 0;
 	self->ob_item = NULL;
+	self->allocated = -1; /* any operation will reset it to >= 0 */
 
 	if (keyfunc != NULL) {
 		for (i=0 ; i < saved_ob_size ; i++) {
@@ -2032,7 +2053,7 @@ fail:
 		}
 	}
 
-	if (self->ob_item != NULL && result != NULL) {
+	if (self->allocated != -1 && result != NULL) {
 		/* The user mucked with the list during the sort,
 		 * and we don't already have another error to report.
 		 */
@@ -2046,13 +2067,19 @@ fail:
 	merge_freemem(&ms);
 
 dsu_fail:
-	if (self->ob_item != NULL) {
-		(void)list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL);
-		PyMem_FREE(self->ob_item);
-	}
+	final_ob_item = self->ob_item;
+	i = self->ob_size;
 	self->ob_size = saved_ob_size;
 	self->ob_item = saved_ob_item;
 	self->allocated = saved_allocated;
+	if (final_ob_item != NULL) {
+		/* we cannot use list_clear() for this because it does not
+		   guarantee that the list is really empty when it returns */
+		while (--i >= 0) {
+			Py_XDECREF(final_ob_item[i]);
+		}
+		PyMem_FREE(final_ob_item);
+	}
 	Py_XDECREF(compare);
 	Py_XINCREF(result);
 	return result;
@@ -2207,13 +2234,6 @@ list_traverse(PyListObject *o, visitproc visit, void *arg)
 	return 0;
 }
 
-static int
-list_clear(PyListObject *lp)
-{
-	(void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
-	return 0;
-}
-
 static PyObject *
 list_richcompare(PyObject *v, PyObject *w, int op)
 {
@@ -2295,10 +2315,8 @@ list_init(PyListObject *self, PyObject *args, PyObject *kw)
 	if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
 		return -1;
 	/* Empty previous contents */
-	self->allocated = self->ob_size;
-	if (self->ob_size != 0) {
-		if (list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL) != 0)
-			return -1;
+	if (self->ob_item != NULL) {
+		(void)list_clear(self);
 	}
 	if (arg != NULL) {
 		PyObject *rv = listextend(self, arg);