[Python-Dev] RE: test_sort.py failure (original) (raw)

Guido van Rossum guido at python.org
Thu Jul 29 02:00:59 CEST 2004

[Guido van Rossum] > I had testsort.py fail once on line 143 (in testbug453523).

How did it fail? By not raising any exception, or by raising an exception other than ValueError?

I deleted the Emacs hsell buffer where it happened, but I believe it complained that ValueError wasn't raised.

> Later it wouldn't fail. The code in question uses a random > generator. Could I have been unlucky enough that the particular > random sequence it used this time didn't create the intended > failure condition?

No: every call to lt mutates the list, the code checking for list mutation should be impossible to fool, the code checking for list mutation raises ValueError at the end of list.sort() iff mutation occurred during the sort, and since the list has more than 1 element lt will be called at least once. It's possible that the code checking for list mutation became less than bulletproof after list object internals were reworked, though -- don't know about that. While it was bulletproof before (according to both Armin and me), it was delicate (as evidence, it took both Armin and me to come up with it ).

Looking at the code, it does roughly this:

saved_ob_size = self->ob_size;
saved_ob_item = self->ob_item;
saved_allocated = self->allocated;
self->ob_size = 0;
self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0);
self->allocated = 0;

...sort the saved_ob_item array...

if (self->ob_item != empty_ob_item || self->ob_size) {
    /* The user mucked with the list during the sort. */
    ...cause an exception...
}
...else restore self->ob_* from saved_*...

Mucking with the list causes realloc() calls to the memory block initially pointed to by empty_ob_item. This is likely to move the block. But it could be that there's enough space following the block that it doesn't have to be moved, and if the array also happens to be empty after the sort (there's a certain probability that this is so), the test will pass despite the mucking.

I guess this is unavoidable given how it is coded; I guess all I can ask for is a comment in test_sort.py explaining that there's a small probability that it gives a false positive. Rerunning the test repeatedly should satisfy one's confidence that sort isn't broken.

--Guido van Rossum (home page: http://www.python.org/~guido/)

More information about the Python-Dev mailing list