Skip to content

Commit 93677f0

Browse files
arigoarigo
committed
* 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.
1 parent f414fc4 commit 93677f0

3 files changed

Lines changed: 64 additions & 31 deletions

File tree

‎Include/listobject.h‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -30,9 +30,7 @@ typedef struct {
3030
* 0 <= ob_size <= allocated
3131
* len(list) == ob_size
3232
* ob_item == NULL implies ob_size == allocated == 0
33-
* If ob_item ever becomes non-NULL, it remains non-NULL for the
34-
* life of the list object. The check for mutation in list.sort()
35-
* relies on this odd detail.
33+
* list.sort() temporarily sets allocated to -1 to detect mutations.
3634
*/
3735
int allocated;
3836
} PyListObject;

‎Lib/test/test_sort.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -150,6 +150,23 @@ def test_cmpNone(self):
150150
L.sort(None)
151151
self.assertEqual(L, range(50))
152152

153+
def test_undetected_mutation(self):
154+
# Python 2.4a1 did not always detect mutation
155+
memorywaster = []
156+
for i in range(20):
157+
def mutating_cmp(x, y):
158+
L.append(3)
159+
L.pop()
160+
return cmp(x, y)
161+
L = [1,2]
162+
self.assertRaises(ValueError, L.sort, mutating_cmp)
163+
def mutating_cmp(x, y):
164+
L.append(3)
165+
del L[:]
166+
return cmp(x, y)
167+
self.assertRaises(ValueError, L.sort, mutating_cmp)
168+
memorywaster = [memorywaster]
169+
153170
#==============================================================================
154171

155172
class TestDecorateSortUndecorate(unittest.TestCase):

‎Objects/listobject.c‎

Lines changed: 46 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -485,6 +485,29 @@ list_repeat(PyListObject *a, int n)
485485
return (PyObject *) np;
486486
}
487487

488+
static int
489+
list_clear(PyListObject *a)
490+
{
491+
int i;
492+
PyObject **item = a->ob_item;
493+
if (item != NULL) {
494+
/* Because XDECREF can recursively invoke operations on
495+
this list, we make it empty first. */
496+
i = a->ob_size;
497+
a->ob_size = 0;
498+
a->ob_item = NULL;
499+
a->allocated = 0;
500+
while (--i >= 0) {
501+
Py_XDECREF(item[i]);
502+
}
503+
PyMem_FREE(item);
504+
}
505+
/* Never fails; the return value can be ignored.
506+
Note that there is no guarantee that the list is actually empty
507+
at this point, because XDECREF may have populated it again! */
508+
return 0;
509+
}
510+
488511
static int
489512
list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
490513
{
@@ -530,8 +553,13 @@ list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
530553
ihigh = ilow;
531554
else if (ihigh > a->ob_size)
532555
ihigh = a->ob_size;
533-
item = a->ob_item;
556+
534557
d = n - (ihigh-ilow);
558+
if (a->ob_size + d == 0) {
559+
Py_XDECREF(v_as_SF);
560+
return list_clear(a);
561+
}
562+
item = a->ob_item;
535563
if (ihigh > ilow) {
536564
p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
537565
if (recycle == NULL) {
@@ -576,10 +604,6 @@ list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
576604
Py_XDECREF(*p);
577605
PyMem_DEL(recycle);
578606
}
579-
if (a->ob_size == 0 && a->ob_item != NULL) {
580-
PyMem_FREE(a->ob_item);
581-
a->ob_item = NULL;
582-
}
583607
Py_XDECREF(v_as_SF);
584608
return 0;
585609
#undef b
@@ -609,12 +633,7 @@ list_inplace_repeat(PyListObject *self, int n)
609633
}
610634

611635
if (n < 1) {
612-
items = self->ob_item;
613-
self->ob_item = NULL;
614-
self->ob_size = 0;
615-
for (i = 0; i < size; i++)
616-
Py_XDECREF(items[i]);
617-
PyMem_DEL(items);
636+
(void)list_clear(self);
618637
Py_INCREF(self);
619638
return (PyObject *)self;
620639
}
@@ -1908,6 +1927,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
19081927
int minrun;
19091928
int saved_ob_size, saved_allocated;
19101929
PyObject **saved_ob_item;
1930+
PyObject **final_ob_item;
19111931
PyObject *compare = NULL;
19121932
PyObject *result = NULL; /* guilty until proved innocent */
19131933
int reverse = 0;
@@ -1942,8 +1962,9 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
19421962
saved_ob_size = self->ob_size;
19431963
saved_ob_item = self->ob_item;
19441964
saved_allocated = self->allocated;
1945-
self->ob_size = self->allocated = 0;
1965+
self->ob_size = 0;
19461966
self->ob_item = NULL;
1967+
self->allocated = -1; /* any operation will reset it to >= 0 */
19471968

19481969
if (keyfunc != NULL) {
19491970
for (i=0 ; i < saved_ob_size ; i++) {
@@ -2032,7 +2053,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
20322053
}
20332054
}
20342055

2035-
if (self->ob_item != NULL && result != NULL) {
2056+
if (self->allocated != -1 && result != NULL) {
20362057
/* The user mucked with the list during the sort,
20372058
* and we don't already have another error to report.
20382059
*/
@@ -2046,13 +2067,19 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
20462067
merge_freemem(&ms);
20472068

20482069
dsu_fail:
2049-
if (self->ob_item != NULL) {
2050-
(void)list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL);
2051-
PyMem_FREE(self->ob_item);
2052-
}
2070+
final_ob_item = self->ob_item;
2071+
i = self->ob_size;
20532072
self->ob_size = saved_ob_size;
20542073
self->ob_item = saved_ob_item;
20552074
self->allocated = saved_allocated;
2075+
if (final_ob_item != NULL) {
2076+
/* we cannot use list_clear() for this because it does not
2077+
guarantee that the list is really empty when it returns */
2078+
while (--i >= 0) {
2079+
Py_XDECREF(final_ob_item[i]);
2080+
}
2081+
PyMem_FREE(final_ob_item);
2082+
}
20562083
Py_XDECREF(compare);
20572084
Py_XINCREF(result);
20582085
return result;
@@ -2207,13 +2234,6 @@ list_traverse(PyListObject *o, visitproc visit, void *arg)
22072234
return 0;
22082235
}
22092236

2210-
static int
2211-
list_clear(PyListObject *lp)
2212-
{
2213-
(void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
2214-
return 0;
2215-
}
2216-
22172237
static PyObject *
22182238
list_richcompare(PyObject *v, PyObject *w, int op)
22192239
{
@@ -2295,10 +2315,8 @@ list_init(PyListObject *self, PyObject *args, PyObject *kw)
22952315
if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
22962316
return -1;
22972317
/* Empty previous contents */
2298-
self->allocated = self->ob_size;
2299-
if (self->ob_size != 0) {
2300-
if (list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL) != 0)
2301-
return -1;
2318+
if (self->ob_item != NULL) {
2319+
(void)list_clear(self);
23022320
}
23032321
if (arg != NULL) {
23042322
PyObject *rv = listextend(self, arg);

0 commit comments

Comments
 (0)