Reverse dict iterators don't detect keys changing during iteration

[jab]

Bug description:

When a dict is cleared and refilled to the same size while a reverse iterator over it is live, the iterator keeps yielding entries from the new keys. The forward iterator raises RuntimeError: dictionary keys changed during iteration in the same situation. The reverse iterator can then yield more items than the dict had when it was created. After that, its __length_hint__() wraps around to 2**64-1, so a later list(it) raises OverflowError.

d = dict.fromkeys(range(10))
for i in range(7):
    del d[i]
it = reversed(d)
print(next(it))  # 9

d.clear()
d.update(dict.fromkeys(range(10)))
for i in range(3, 10):
    del d[i]
print(d)  # same size as when `it` was created

print(next(it), next(it), next(it))
print(it.__length_hint__())
print(list(it))

Output on main (5eb4ab5) and on 3.11.15, 3.12.13, 3.13.13, 3.14.4 and 3.15.0b3:

9
{0: None, 1: None, 2: None}
2 1 0
18446744073709551615
Traceback (most recent call last):
  File "rev.py", line 15, in <module>
    print(list(it))
          ~~~~^^^^
OverflowError: Python int too large to convert to C ssize_t

it was created on a 3-item dict, and it has yielded 4 items. reversed(d.keys()), reversed(d.values()) and reversed(d.items()) behave the same way.

The forward iterator raises in the equivalent situation:

d = dict.fromkeys(range(10))
for i in range(7):
    del d[i]
it = iter(d)
print(next(it))  # 7

d.clear()
d.update(dict.fromkeys(range(12)))
for i in [*range(8), 11]:
    del d[i]

list(it)  # RuntimeError: dictionary keys changed during iteration

In both examples, the size check (di_used != ma_used) passes because the dict has the same number of items again. The forward iterators have a second check. When they find an entry after di->len has reached 0, they raise "dictionary keys changed during iteration" (dictiter_iternextkey_lock_held, and likewise for values and items). dictreviter_iter_lock_held has no such check. So it keeps yielding and decrements di->len below zero, and dictiter_len returns that value through PyLong_FromSize_t.

gh-154709 is related but different. Its fix (gh-154721) bounded the reverse iterator's index against the current keys table, which stops the out-of-bounds read when the new table is smaller. Here the new table is large enough, so the index stays in bounds and reads live entries of the new keys.

Adding the forward iterators' di->len == 0 check to dictreviter_iter_lock_held, just before di->di_pos = i-1;, fixes this. With that change, the example and all four reverse iterator types raise RuntimeError: dictionary keys changed during iteration, and test_dict passes. I can open a PR with the change and a test.

I found this while testing bidict, whose update() clears and refills its backing dicts.

This report was drafted with the help of Claude Code, an AI assistant. I have reproduced and reviewed it.

CPython versions tested on:

3.11, 3.12, 3.13, 3.14, 3.15, CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-158254: Detect keys changing during reverse dict iteration #158255
• [3.15] gh-158254: Detect keys changing during reverse dict iteration (GH-158255) #158267
• [3.14] gh-158254: Detect keys changing during reverse dict iteration (GH-158255) #158268
• [3.13] gh-158254: Detect keys changing during reverse dict iteration (GH-158255) #158269

[ZeroIntensity]

3.13 and 3.14 backports are on auto-merge, and the 3.15 backport will be merged whenever Hugo gets to it. Thanks for the report and the fix!