[Python-Dev] Making sure dictionary adds/deletes during iteration always raise exception

[Max Moroz]

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

[Python-Dev] deque implementation question

[Max Moroz]

What would be the disadvantage of implementing collections.deque as a
circular array (rather than a doubly linked list of blocks)? My naive
thinking was that a circular array would maintain the current O(1) append/pop
from either side, and would improve index lookup in the middle from O(n) to
O(1). What am I missing?

The insertion/removal of an arbitrary item specified by a pointer would
increase from constant time to linear, but since we don't have pointers
this is a moot point.

Of course when the circular array is full, it will need to be reallocated,
but the amortized cost of that is still O(1). (Moreover, for a bounded
deque, there's even an option of preallocation, which would completely
eliminate reallocations.)

Thanks

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