Detect dict iteration "overflow" when changing keys

[thp]

BPO	36452
Nosy	@rhettinger, @methane, @thp
PRs	bpo-36452: dictiter: track maximum iteration count #12596 bpo-36473: add maximum iteration check for dict .values() and .items() #12619
Files	0001-dictiterobject-Track-maximum-iteration-count-via-di-.patch: Git patch: dictiterobject: Track maximum iteration count via di->len

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2019-03-28.06:04:44.348>
created_at = <Date 2019-03-27.23:41:18.021>
labels = ['interpreter-core', 'type-bug', '3.8']
title = 'Detect dict iteration "overflow" when changing keys'
updated_at = <Date 2019-03-29.14:19:55.370>
user = 'https://github.com/thp'

bugs.python.org fields:

activity = <Date 2019-03-29.14:19:55.370>
actor = 'thomas.perl'
assignee = 'none'
closed = True
closed_date = <Date 2019-03-28.06:04:44.348>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2019-03-27.23:41:18.021>
creator = 'thomas.perl'
dependencies = []
files = ['48234']
hgrepos = []
issue_num = 36452
keywords = ['patch']
message_count = 3.0
messages = ['338997', '339015', '339016']
nosy_count = 3.0
nosy_names = ['rhettinger', 'methane', 'thomas.perl']
pr_nums = ['12596', '12619']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue36452'
versions = ['Python 3.8']

[thp]

Using: Python 3.8 (git commit ID: d5a5a33), the following code snippet:

=====

a = {0: 0}

for i in a:
    del a[i]
    a[i+1] = 0
    print(i)

=====

Prints the following output:

=====
0
1
2
3
4
=====

The reason for this seems to be the way the internal key list is managed and the "next" value in this list is retrieved. The amount of items seems to be related to USABLE_FRACTION(PyDict_MINSIZE).

Since cases where the dictionary size changes are detected with a RuntimeError, I would expect the invariant to be "the number of iterations is the len() of the dict at the time the iterator is created to be enforced. Whether to raise a StopIteration instead or raising a RuntimeError is up for debate.

Attached is a patch that tries to detect this corner case and raise a RuntimeError instead (plus a unit test).

Note also that without the patch, the __length_hint__() of the iterator actually underflows:

=====

a = {0: 0}
it = iter(a)
print('Length hint:', it.__length_hint__())
next(it)
print('Length hint:', it.__length_hint__())
del a[0]
a[1] = 0
next(it)
print('Length hint:', it.__length_hint__())

=====

[methane]

New changeset 796cc6e by Inada Naoki (Thomas Perl) in branch 'master':
bpo-36452: dictiter: track maximum iteration count (GH-12596)
796cc6e

[methane]

Thank you. I like your patch.