Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Detect dict iteration "overflow" when changing keys #80633

Closed
thp mannequin opened this issue Mar 27, 2019 · 3 comments
Closed

Detect dict iteration "overflow" when changing keys #80633

thp mannequin opened this issue Mar 27, 2019 · 3 comments
Labels
3.8 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error

Comments

@thp
Copy link
Mannequin

thp mannequin commented Mar 27, 2019

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
    Copy link
    Mannequin Author

    thp mannequin commented Mar 27, 2019

    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__())

    =====

    @thp thp mannequin added 3.8 only security fixes type-bug An unexpected behavior, bug, or error labels Mar 27, 2019
    @methane
    Copy link
    Member

    methane commented Mar 28, 2019

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

    @methane
    Copy link
    Member

    methane commented Mar 28, 2019

    Thank you. I like your patch.

    @methane methane added the interpreter-core (Objects, Python, Grammar, and Parser dirs) label Mar 28, 2019
    @methane methane closed this as completed Mar 28, 2019
    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    lsh-0 added a commit to elifesciences/builder that referenced this issue Jul 8, 2022
    @lsh-0
    fixes issue in buildercore.utils.nested_dictmap raising a runtime err…
    066a224 
    …or while modifying the keys of dict during iteration.

probably this issue: python/cpython#80633
    @lsh-0 lsh-0 mentioned this issue Jul 8, 2022
    Merged
    lsh-0 added a commit to elifesciences/builder that referenced this issue Jul 8, 2022
    @lsh-0
    fixes issue in buildercore.utils.nested_dictmap raising a runtime err…
    58d6745 
    …or while modifying the keys of dict during iteration. (#976)

probably this issue: python/cpython#80633
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees
    No one assigned
    Labels
    3.8 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    1 participant
    @methane