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.
diff --git a/Doc/lib/libstdtypes.tex b/Doc/lib/libstdtypes.tex
index 49cb67b..3e788bb 100644
--- a/Doc/lib/libstdtypes.tex
+++ b/Doc/lib/libstdtypes.tex
@@ -922,7 +922,7 @@
\lineiii{\var{s}.reverse()}
{reverses the items of \var{s} in place}{(6)}
\lineiii{\var{s}.sort(\optional{\var{cmpfunc}})}
- {sort the items of \var{s} in place}{(6), (7), (8)}
+ {sort the items of \var{s} in place}{(6), (7), (8), (9)}
\end{tableiii}
\indexiv{operations on}{mutable}{sequence}{types}
\indexiii{operations on}{sequence}{types}
@@ -980,6 +980,12 @@
Python 2.2. The C implementation of Python 2.3 introduced a stable
\method{sort()} method, but code that intends to be portable across
implementations and versions must not rely on stability.
+
+\item[(9)] While a list is being sorted, the effect of attempting to
+ mutate, or even inspect, the list is undefined. The C implementation
+ of Python 2.3 makes the list appear empty for the duration, and raises
+ \exception{ValueError} if it can detect that the list has been
+ mutated during a sort.
\end{description}
diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py
index 9b31052..5c7ae88 100644
--- a/Lib/test/test_sort.py
+++ b/Lib/test/test_sort.py
@@ -116,6 +116,35 @@
x = [e for e, i in augmented] # a stable sort of s
check("stability", x, s)
+def bug453523():
+ global nerrors
+ from random import random
+
+ # If this fails, the most likely outcome is a core dump.
+ if verbose:
+ print "Testing bug 453523 -- list.sort() crasher."
+
+ class C:
+ def __lt__(self, other):
+ if L and random() < 0.75:
+ pop()
+ else:
+ push(3)
+ return random() < 0.5
+
+ L = [C() for i in range(50)]
+ pop = L.pop
+ push = L.append
+ try:
+ L.sort()
+ except ValueError:
+ pass
+ else:
+ print " Mutation during list.sort() wasn't caught."
+ nerrors += 1
+
+bug453523()
+
if nerrors:
print "Test failed", nerrors
elif verbose:
diff --git a/Lib/test/test_types.py b/Lib/test/test_types.py
index 9777e83..d075d94 100644
--- a/Lib/test/test_types.py
+++ b/Lib/test/test_types.py
@@ -367,10 +367,10 @@
else: raise TestFailed, 'list sort compare function is not callable'
def selfmodifyingComparison(x,y):
- z[0] = 1
+ z.append(1)
return cmp(x, y)
try: z.sort(selfmodifyingComparison)
-except TypeError: pass
+except ValueError: pass
else: raise TestFailed, 'modifying list during sort'
try: z.sort(lambda x, y: 's')
diff --git a/Misc/NEWS b/Misc/NEWS
index addd5ae..334a1b3 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -66,6 +66,16 @@
Core and builtins
-----------------
+- Thanks to Armin Rigo, the last known way to provoke a system crash
+ by cleverly arranging for a comparison function to mutate a list
+ during a list.sort() operation has been fixed. The effect of
+ attempting to mutate a list, or even to inspect its contents or
+ length, while a sort is in progress, is not defined by the language.
+ The C implementation of Python 2.3 attempts to detect mutations,
+ and raise ValueError if one occurs, but there's no guarantee that
+ all mutations will be caught, or that any will be caught across
+ releases or implementations.
+
- Unicode file name processing for Windows (PEP 277) is implemented.
All platforms now have an os.path.supports_unicode_filenames attribute,
which is set to True on Windows NT/2000/XP, and False elsewhere.
@@ -428,7 +438,7 @@
- Added operator.pow(a,b) which is equivalent to a**b.
- Added random.sample(population,k) for random sampling without replacement.
- Returns a k length list of unique elements chosen from the population.
+ Returns a k length list of unique elements chosen from the population.
- random.randrange(-sys.maxint-1, sys.maxint) no longer raises
OverflowError. That is, it now accepts any combination of 'start'
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 @@
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 @@
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 @@
}
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 @@
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 @@
};
-/* 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 {