[Python-Dev] Issue 19332: Guard against changing dict during iteration

[Serhiy Storchaka]

06.11.13 21:12, Eric Snow написав(ла):
> Just to clarify, do you mean we should only guard against
> modifications to the dict's keys during its iterator's __next__()?
> Changes to the values during __next__() would be okay, as would
> changes to the keys if they happen outside __next__()?

Dict iteration order can be changed after adding or deleting a key so 
continue iterating after this is not well defined. __next__() is invalid 
if dict keys was modified after iterators creation. This is common 
assertion for hashtables in many programming languages. The raising an 
exception in such situation just helps a programmer to find his mistake. 
Java raises an exception, in C++ this is an undefined behavior.

> Presumably the above restriction also applies to the iterators of the
> dict's views.

Yes. The proposed patch have tests for these cases.

> OrderedDict would also need to be changed, meaning this counter would
> have to be accessible to and incrementable by subclasses.  OrderedDict
> makes use of the MappingView classes in collections.abc, so those
> would also have be adjusted to check this counter.

Perhaps issue19414 is related. OrderedDict not needs such behavior 
because it's iteration order is well defined and we can implement 
another reasonable behavior (for example deleted keys are skipped and 
newly added keys are always iterated, because they added at the end of 
iteration order).

> Would MutableMapping also need to be adjusted to accommodate the
> counter?  Given that the MappingView classes would rely on the
> counter, I'd expect MutableMapping to need some method or variable
> that the views can rely on.  How would we make sure custom methods,
> particularly __setitem__() and __delitem__(), increment the counter?

MutableMapping doesn't implement neither __iter__() nor __setitem__(). 
Concrete implementation is responsible of this, either provide reliable 
__iter__() which have predictable behavior after __setitem__(), or 
detect such modification and raise an exception, or just ignore the problem.

The MappingView classes would get this for free because their iterators 
iterate over mapping itself.

> A strictly monotonic counter, right?  Every mutation method of dict
> would have to increment this counter.  So would that put a limit
> (albeit a high one) on the number of mutations that can be made to a
> dict?  Would there be conditions under which we'd reset the counter?
> If so, how would existing iterators cope?

It is very unlikely that unintentional causes exact 2**32 or 2**64 
mutations between dict iterations. If this will happen the programmer 
should use other methods to find his mistakes.

> Because the iterators (and views) already have a pointer to the dict, right?

Currently the PyDictObject object contains 3 words and adding yet one 
word unlikely change actually allocated size. Dict iterators already 
contain a field for dict's size, it will be replaced by a field for 
dict's counter.