[Python-Dev] RE: test_sort.py failure

[Guido van Rossum]

> [Guido van Rossum]
> > I had test_sort.py fail once on line 143 (in test_bug453523).
> 
> 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 <wink>).

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/)