[Python-Dev] RE: test_sort.py failure

[Tim Peters]

[Armin Rigo]
> I think Tim is right: the code used to be correct, but the list internals
> reorganization might have broken that.  As far as I remember, the reason it
> used to be fine is that lists with zero elements were always deallocated, so
> that empty lists never had an allocated ob_items array.  If user code
> populated and then emptied again the list during the sort, it couldn't end up
> again in the special state list_sort() puts it in, which is ob_size == 0 but
> ob_items allocated.

Exactly right.

>  Apparently, this can occur now.

Ditto.  List objects grew another member, to record the number of list
slots allocated, which may be larger than the number currently in use.
 And the new (since 2.3) internal list_resize() never sets ob_item to
NULL on a list shrink anymore.  Indeed, even if ob_item is NULL on
entry to list_resize, and the new size requested is 0, ob_item is made
non-NULL (unless malloc(3*sizeof(PyObject*)) returns NULL, in which
case ob_item remains NULL but MemoryError is raised).

So it looks like a new delicate scheme for list_sort would be to set
ob_item to NULL at the start.  As soon as mutation adds an element,
ob_item will become non-NULL (or raise MemoryError), and it looks like
it will remain non-NULL forever after.

Alas, test_sort never fails on my box now, so I can't test this.  I
bet it would fail a lot more often on boxes where it does fail if the
test case used a 3-element list instead of a 50-element list.

> Looks like another review of list_sort() is needed.  (Some time ago, after
> staring at it for some time, I wondered and couldn't figure out if there was a
> memory leak or not, too)

Don't spread FUD <wink>.