diff options
| -rw-r--r-- | Lib/test/test_sort.py | 45 | ||||
| -rw-r--r-- | Objects/listobject.c | 81 |
2 files changed, 91 insertions, 35 deletions
diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py index 2659a90..74f3bb5 100644 --- a/Lib/test/test_sort.py +++ b/Lib/test/test_sort.py @@ -193,6 +193,51 @@ class TestDecorateSortUndecorate(unittest.TestCase): self.assertRaises(ZeroDivisionError, data.sort, None, lambda x: 1/x) self.assertEqual(data, dup) + def test_key_with_mutation(self): + data = range(10) + def k(x): + del data[:] + data[:] = range(20) + return x + self.assertRaises(ValueError, data.sort, key=k) + + def test_key_with_mutating_del(self): + data = range(10) + class SortKiller(object): + def __init__(self, x): + pass + def __del__(self): + del data[:] + data[:] = range(20) + self.assertRaises(ValueError, data.sort, key=SortKiller) + + def test_key_with_mutating_del_and_exception(self): + data = range(10) + ## dup = data[:] + class SortKiller(object): + def __init__(self, x): + if x > 2: + raise RuntimeError + def __del__(self): + del data[:] + data[:] = range(20) + self.assertRaises(RuntimeError, data.sort, key=SortKiller) + ## major honking subtlety: we *can't* do: + ## + ## self.assertEqual(data, dup) + ## + ## because there is a reference to a SortKiller in the + ## traceback and by the time it dies we're outside the call to + ## .sort() and so the list protection gimmicks are out of + ## date (this cost some brain cells to figure out...). + + def test_key_with_exception(self): + # Verify that the wrapper has been removed + data = range(-2,2) + dup = data[:] + self.assertRaises(ZeroDivisionError, data.sort, None, lambda x: 1/x) + self.assertEqual(data, dup) + def test_reverse(self): data = range(100) random.shuffle(data) diff --git a/Objects/listobject.c b/Objects/listobject.c index 95aa484..ce3ac6d 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -1848,7 +1848,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds) PyObject *result = NULL; /* guilty until proved innocent */ int reverse = 0; PyObject *keyfunc = NULL; - int i, len = 0; + int i; PyObject *key, *value, *kvpair; static char *kwlist[] = {"cmp", "key", "reverse", 0}; @@ -1870,45 +1870,56 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds) } else Py_XINCREF(compare); + /* 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); + if (keyfunc != NULL) { - len = PyList_GET_SIZE(self); - for (i=0 ; i < len ; i++) { - value = PyList_GET_ITEM(self, i); + for (i=0 ; i < saved_ob_size ; i++) { + value = saved_ob_item[i]; key = PyObject_CallFunctionObjArgs(keyfunc, value, NULL); if (key == NULL) { for (i=i-1 ; i>=0 ; i--) { - kvpair = PyList_GET_ITEM(self, i); + kvpair = saved_ob_item[i]; value = sortwrapper_getvalue(kvpair); - PyList_SET_ITEM(self, i, value); + saved_ob_item[i] = value; Py_DECREF(kvpair); } + if (self->ob_item != empty_ob_item + || self->ob_size) { + /* If the list changed *as well* we + have two errors. We let the first + one "win", but we shouldn't let + what's in the list currently + leak. */ + (void)list_ass_slice( + self, 0, self->ob_size, + (PyObject *)NULL); + } + goto dsu_fail; } kvpair = build_sortwrapper(key, value); if (kvpair == NULL) goto dsu_fail; - PyList_SET_ITEM(self, i, kvpair); + saved_ob_item[i] = kvpair; } } /* Reverse sort stability achieved by initially reversing the list, applying a stable forward sort, then reversing the final result. */ - if (reverse && self->ob_size > 1) - reverse_slice(self->ob_item, self->ob_item + self->ob_size); + if (reverse && saved_ob_size > 1) + reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); merge_init(&ms, compare); - /* 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 = saved_ob_size; if (nremaining < 2) goto succeed; @@ -1959,6 +1970,15 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds) succeed: result = Py_None; fail: + if (keyfunc != NULL) { + for (i=0 ; i < saved_ob_size ; i++) { + kvpair = saved_ob_item[i]; + value = sortwrapper_getvalue(kvpair); + saved_ob_item[i] = value; + Py_DECREF(kvpair); + } + } + 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); @@ -1968,26 +1988,17 @@ fail: 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); - if (keyfunc != NULL) { - len = PyList_GET_SIZE(self); - for (i=0 ; i < len ; i++) { - kvpair = PyList_GET_ITEM(self, i); - value = sortwrapper_getvalue(kvpair); - PyList_SET_ITEM(self, i, value); - Py_DECREF(kvpair); - } - } + if (reverse && saved_ob_size > 1) + reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); - if (reverse && self->ob_size > 1) - reverse_slice(self->ob_item, self->ob_item + self->ob_size); + merge_freemem(&ms); dsu_fail: + if (self->ob_item == empty_ob_item) + PyMem_FREE(empty_ob_item); + self->ob_size = saved_ob_size; + self->ob_item = saved_ob_item; Py_XDECREF(compare); Py_XINCREF(result); return result; |