[Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
Would it be worth ensuring that an exception is ALWAYS raised if a key
is added to or deleted from a dictionary during iteration?
Currently, dict.__iter__ only raises "RuntimeError" when "dictionary
changed size during iteration". I managed to add 1 key and delete 1
key from the dictionary in the same iteration of the loop (the code
was in a callback function invoked in the loop) - of course without
any exception. (I hope I'm right in assuming that adding and deleting
entries in the loop is unsafe whether or not number of adds equals
number of deletes.)
I suspect the cost of a more comprehensive error reporting is not
worth the benefit, but I thought I'd ask anyway.
Here's a pure python prototype that would always raise on unsafe
add/delete. The main cost is the addition of a counter keeping track
of the number of modifications made to the dictionary (the work done
inside __iter__ is probably not adding any runtime cost because it
replaces roughly equivalent code that currently verifies that the
length didn't change):
class SafeKeyIter:
def __init__(self, iterator, container):
self.iterator = iterator
self.container = container
try:
self.n_modifications = container.n_modifications
except AttributeError:
raise RuntimeError('container does not support safe iteration')
def __next__(self):
if self.n_modifications != self.container.n_modifications:
raise RuntimeError('container entries added or deleted
during iteration')
return next(self.iterator)
class SafeView:
def __init__(self, view, container):
self.view = view
self.container = container
def __iter__(self):
return SafeKeyIter(self.view.__iter__(), self.container)
class SafeDict(dict):
def __init__(self, *args, **kwargs):
self.n_modifications = 0
super().__init__(*args, **kwargs)
def __setitem__(self, key, value):
if key not in self:
self.n_modifications += 1
super().__setitem__(key, value)
def __delitem__(self, key):
self.n_modifications += 1
super().__delitem__(key)
def __iter__(self):
return SafeKeyIter(super().__iter__(), self)
def keys(self):
return SafeView(super().keys(), self)
def values(self):
return SafeView(super().values(), self)
def items(self):
return SafeView(super().items(), self)
# this raises RuntimeError:
d = SafeDict({1: 2})
for k in d:
d[k * 100] = 100
del d[k]
# while it wouldn't raise for a built-in dict
d = {1: 2}
for k in d:
d[k * 100] = 100
del d[k]
There was a brief discussion on SO after I asked a question about this
behavior, and later answered it:
http://stackoverflow.com/questions/40955786/why-modifying-dict-during-iteration-doesnt-always-raise-exception.
Max
___
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
> On Dec 13, 2016, at 1:51 AM, Max Moroz wrote: > > Would it be worth ensuring that an exception is ALWAYS raised if a key > is added to or deleted from a dictionary during iteration? > > I suspect the cost of a more comprehensive error reporting is not > worth the benefit, but I thought I'd ask anyway. I think what we have has proven itself to be good enough to detect the common cases, and it isn't worth it to have dicts grow an extra field which has to be checked or updated on every operation. Raymond ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
> On Dec 13, 2016, at 8:42 AM, Raymond Hettinger > wrote: > >> On Dec 13, 2016, at 1:51 AM, Max Moroz wrote: >> >> Would it be worth ensuring that an exception is ALWAYS raised if a key >> is added to or deleted from a dictionary during iteration? >> >> I suspect the cost of a more comprehensive error reporting is not >> worth the benefit, but I thought I'd ask anyway. > > I think what we have has proven itself to be good enough to detect the common > cases, and it isn't worth it to have dicts grow an extra field which has to > be checked or updated on every operation. Hmm, I just looked at the latest dictobject.h and remembered that Victor already added a version tag to track state changes. Raymond ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
> On Dec 13, 2016, at 11:42 AM, Raymond Hettinger > wrote: > > >> On Dec 13, 2016, at 1:51 AM, Max Moroz wrote: >> >> Would it be worth ensuring that an exception is ALWAYS raised if a key >> is added to or deleted from a dictionary during iteration? >> >> I suspect the cost of a more comprehensive error reporting is not >> worth the benefit, but I thought I'd ask anyway. > > I think what we have has proven itself to be good enough to detect the common > cases, and it isn't worth it to have dicts grow an extra field which has to > be checked or updated on every operation. > I agree that we shouldn't complicate things, but wouldn't PEP 509 be a cheap way to check this? Eric. ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
On Tue, Dec 13, 2016 at 8:52 AM, Eric V. Smith wrote: > > > On Dec 13, 2016, at 11:42 AM, Raymond Hettinger < > raymond.hettin...@gmail.com> wrote: > > > >> On Dec 13, 2016, at 1:51 AM, Max Moroz wrote: > >> > >> Would it be worth ensuring that an exception is ALWAYS raised if a key > >> is added to or deleted from a dictionary during iteration? > >> > >> I suspect the cost of a more comprehensive error reporting is not > >> worth the benefit, but I thought I'd ask anyway. > > > > I think what we have has proven itself to be good enough to detect the > common cases, and it isn't worth it to have dicts grow an extra field which > has to be checked or updated on every operation. > > > > I agree that we shouldn't complicate things, but wouldn't PEP 509 be a > cheap way to check this? > IIUC the private version gets updated every time the dict gets modified -- but what we need here should only trigger when a key is added or removed, not when a value is updated. (It's a guarantee that updating the value doesn't change the iteration order -- though perhaps it isn't spelled out, it's implicit.) I agree with Raymond that we should not change anything. -- --Guido van Rossum (python.org/~guido) ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
On Wed, Dec 14, 2016 at 4:48 AM, Guido van Rossum wrote: > IIUC the private version gets updated every time the dict gets modified -- > but what we need here should only trigger when a key is added or removed, > not when a value is updated. Is it possible to add a key, triggering a resize of the dict, then remove one, and continue iterating through the old (deallocated) memory? If so, that could potentially cause a crash. ChrisA ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
> On Dec 13, 2016, at 12:48 PM, Guido van Rossum wrote: > >> On Tue, Dec 13, 2016 at 8:52 AM, Eric V. Smith wrote: >> >> > On Dec 13, 2016, at 11:42 AM, Raymond Hettinger >> > wrote: >> > >> >> On Dec 13, 2016, at 1:51 AM, Max Moroz wrote: >> >> >> >> Would it be worth ensuring that an exception is ALWAYS raised if a key >> >> is added to or deleted from a dictionary during iteration? >> >> >> >> I suspect the cost of a more comprehensive error reporting is not >> >> worth the benefit, but I thought I'd ask anyway. >> > >> > I think what we have has proven itself to be good enough to detect the >> > common cases, and it isn't worth it to have dicts grow an extra field >> > which has to be checked or updated on every operation. >> > >> >> I agree that we shouldn't complicate things, but wouldn't PEP 509 be a cheap >> way to check this? > > IIUC the private version gets updated every time the dict gets modified -- > but what we need here should only trigger when a key is added or removed, not > when a value is updated. (It's a guarantee that updating the value doesn't > change the iteration order -- though perhaps it isn't spelled out, it's > implicit.) > Ah, yes. That's over-zealous for this case. > I agree with Raymond that we should not change anything. Agreed. Eric. ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
On Wed, Dec 14, 2016 at 5:13 AM, Joe Jevnik wrote: >> Is it possible to add a key, triggering a resize of the dict, then > remove one, and continue iterating through the old (deallocated) > memory? > > You can add and remove keys between calling next which would resize the > dictionary; however, it will not iterate through uninitialized memory. The > dictiter holds the current index and each time next is called it goes > directly to ma_keys->dk_entries[saved_index] or ma_values[saved_index] Okay, so it's fine then. Cool. Thanks for the info. ChrisA ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
On 13.12.16 11:51, Max Moroz wrote: Would it be worth ensuring that an exception is ALWAYS raised if a key is added to or deleted from a dictionary during iteration? Currently, dict.__iter__ only raises "RuntimeError" when "dictionary changed size during iteration". I managed to add 1 key and delete 1 key from the dictionary in the same iteration of the loop (the code was in a callback function invoked in the loop) - of course without any exception. (I hope I'm right in assuming that adding and deleting entries in the loop is unsafe whether or not number of adds equals number of deletes.) I suspect the cost of a more comprehensive error reporting is not worth the benefit, but I thought I'd ask anyway. The patch implementing this was rejected. http://bugs.python.org/issue19332 ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
When adding new key, dk_usable is decremented. When removing key, dk_usable is not decremented. So I think dk_usable & ma_used pair can be used to detect dict size modification. On Wed, Dec 14, 2016 at 8:02 AM, Serhiy Storchaka wrote: > On 13.12.16 11:51, Max Moroz wrote: >> >> Would it be worth ensuring that an exception is ALWAYS raised if a key >> is added to or deleted from a dictionary during iteration? >> >> Currently, dict.__iter__ only raises "RuntimeError" when "dictionary >> changed size during iteration". I managed to add 1 key and delete 1 >> key from the dictionary in the same iteration of the loop (the code >> was in a callback function invoked in the loop) - of course without >> any exception. (I hope I'm right in assuming that adding and deleting >> entries in the loop is unsafe whether or not number of adds equals >> number of deletes.) >> >> I suspect the cost of a more comprehensive error reporting is not >> worth the benefit, but I thought I'd ask anyway. > > > The patch implementing this was rejected. > > http://bugs.python.org/issue19332 > > > > ___ > Python-Dev mailing list > Python-Dev@python.org > https://mail.python.org/mailman/listinfo/python-dev > Unsubscribe: > https://mail.python.org/mailman/options/python-dev/songofacandy%40gmail.com -- INADA Naoki ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
> On 13 Dec 2016, at 17:52, Eric V. Smith wrote: > > >> On Dec 13, 2016, at 11:42 AM, Raymond Hettinger >> wrote: >> >> >>> On Dec 13, 2016, at 1:51 AM, Max Moroz wrote: >>> >>> Would it be worth ensuring that an exception is ALWAYS raised if a key >>> is added to or deleted from a dictionary during iteration? >>> >>> I suspect the cost of a more comprehensive error reporting is not >>> worth the benefit, but I thought I'd ask anyway. >> >> I think what we have has proven itself to be good enough to detect the >> common cases, and it isn't worth it to have dicts grow an extra field which >> has to be checked or updated on every operation. >> > > I agree that we shouldn't complicate things, but wouldn't PEP 509 be a cheap > way to check this? Doesn’t that update the version with every change to a dict instance? That is, not just when the set of keys for the dict changes. Ronald ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception
> Is it possible to add a key, triggering a resize of the dict, then remove one, and continue iterating through the old (deallocated) memory? You can add and remove keys between calling next which would resize the dictionary; however, it will not iterate through uninitialized memory. The dictiter holds the current index and each time next is called it goes directly to ma_keys->dk_entries[saved_index] or ma_values[saved_index] On Tue, Dec 13, 2016 at 12:55 PM, Chris Angelico wrote: > On Wed, Dec 14, 2016 at 4:48 AM, Guido van Rossum > wrote: > > IIUC the private version gets updated every time the dict gets modified > -- > > but what we need here should only trigger when a key is added or removed, > > not when a value is updated. > > Is it possible to add a key, triggering a resize of the dict, then > remove one, and continue iterating through the old (deallocated) > memory? If so, that could potentially cause a crash. > > ChrisA > ___ > Python-Dev mailing list > Python-Dev@python.org > https://mail.python.org/mailman/listinfo/python-dev > Unsubscribe: https://mail.python.org/mailman/options/python-dev/ > joe%40quantopian.com > ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
