[Python-Dev] Re: Sets: elt in dict, lst.include

[Tim Peters]

[Finn Bock]
> Changing the type of a type? Yuck!

No, it temporarily changes the type of the single list being sorted, like
so, where "self" is a pointer to a PyListObject (which is a list, not a list
*type* object):

	self->ob_type = &immutable_list_type;
	err = samplesortslice(self->ob_item,
			      self->ob_item + self->ob_size,
			      compare);
	self->ob_type = &PyList_Type;

immutable_list_type is "just like" PyList_Type, except that the slots for
mutating methods point to a function that raises a TypeError.

Before this drastic step came years of increasingly ugly hacks trying to
stop core dumps when people mutated a list during the sort.  Python's sort
is very complex, and lots of pointers are tucked away -- having the size of
the array, or its position in memory, or the set of objects it contains,
change as a side effect of doing a compare, would be difficult and expensive
to recover from -- and by "difficult" read "nobody ever managed to get it
right before this" <0.5 wink>.

> I might very likely be reading the CPython sources wrongly, but it seems
> this trick will cause an BadInternalCall if some other C extension are
> trying to modify a list while it is freezed by the type switching trick.
> I imagine this would happen if the extension called:
>
>   PyList_SetItem(myList, 0, aValue);

Well, in CPython it's not "legal" for any other thread to use the C API
while the sort is in progress, because the thread doing the sort holds the
global interpreter lock for the duration.  So this could happen "legally"
only if a comparison function called by the sort called out to a C extension
attempting to mutate the list.  In that case, fine, it *is* a bad call:
mutation is not allowed during list sorting, so they deserve whatever they
get -- and far better a "bad internal call" than a core dump.

If the immutable_list_type were used more generally, it would require more
general support (but I see Thomas already talked about that -- thanks).