classification
Title: Detect dict iteration "overflow" when changing keys
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: inada.naoki, rhettinger, thomas.perl
Priority: normal Keywords: patch

Created on 2019-03-27 23:41 by thomas.perl, last changed 2019-03-29 14:19 by thomas.perl. This issue is now closed.

Files
File name Uploaded Description Edit
0001-dictiterobject-Track-maximum-iteration-count-via-di-.patch thomas.perl, 2019-03-27 23:41 Git patch: dictiterobject: Track maximum iteration count via di->len
Pull Requests
URL Status Linked Edit
PR 12596 merged python-dev, 2019-03-27 23:45
PR 12619 open thomas.perl, 2019-03-29 14:19
Messages (3)
msg338997 - (view) Author: Thomas Perl (thomas.perl) * Date: 2019-03-27 23:41
Using: Python 3.8 (git commit ID: d5a5a33f12b60129d57f9b423b77d2fcba506834), 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__())
=====
msg339015 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-03-28 06:03
New changeset 796cc6e3ad3617c1ea9e528663aac1a206230a28 by Inada Naoki (Thomas Perl) in branch 'master':
bpo-36452: dictiter: track maximum iteration count (GH-12596)
https://github.com/python/cpython/commit/796cc6e3ad3617c1ea9e528663aac1a206230a28
msg339016 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-03-28 06:04
Thank you.  I like your patch.
History
Date User Action Args
2019-03-29 14:19:55thomas.perlsetpull_requests: + pull_request12555
2019-03-28 06:04:44inada.naokisetstatus: open -> closed
messages: + msg339016

components: + Interpreter Core
resolution: fixed
stage: patch review -> resolved
2019-03-28 06:03:27inada.naokisetmessages: + msg339015
2019-03-27 23:51:32xtreaksetnosy: + rhettinger, inada.naoki
2019-03-27 23:45:40python-devsetstage: patch review
pull_requests: + pull_request12539
2019-03-27 23:41:18thomas.perlcreate