Strange reversed dict behavior

[ivb]

BPO	38525
Nosy	@ned-deily, @methane, @serhiy-storchaka, @corona10, @pablogsal, @miss-islington, @Harmon758, @remilapeyre, @tirkarthi
PRs	bpo-38525: Fix a segmentation fault when using reverse iterators of empty dict #16846 bpo-38525: Fix segfault when using reverse iterators of empty dict literals #16847 [3.8] bpo-38525: Fix a segmentation fault when using reverse iterators of empty dict (GH-16846) #16853

^{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-10-19.20:23:30.477>
created_at = <Date 2019-10-19.08:00:52.660>
labels = ['interpreter-core', '3.8', '3.9', 'type-crash']
title = 'Strange reversed dict behavior'
updated_at = <Date 2019-11-14.10:48:55.574>
user = 'https://bugs.python.org/ivb'

bugs.python.org fields:

activity = <Date 2019-11-14.10:48:55.574>
actor = 'Harmon758'
assignee = 'none'
closed = True
closed_date = <Date 2019-10-19.20:23:30.477>
closer = 'pablogsal'
components = ['Interpreter Core']
creation = <Date 2019-10-19.08:00:52.660>
creator = 'ivb'
dependencies = []
files = []
hgrepos = []
issue_num = 38525
keywords = ['patch']
message_count = 15.0
messages = ['354931', '354932', '354933', '354938', '354939', '354940', '354944', '354945', '354946', '354947', '354948', '354949', '354961', '354962', '354963']
nosy_count = 10.0
nosy_names = ['ned.deily', 'methane', 'ivb', 'serhiy.storchaka', 'corona10', 'pablogsal', 'miss-islington', 'Harmon758', 'remi.lapeyre', 'xtreak']
pr_nums = ['16846', '16847', '16853']
priority = 'critical'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue38525'
versions = ['Python 3.8', 'Python 3.9']

[ivb]

Python 3.8.0 (tags/v3.8.0:fa919fd, Oct 14 2019, 19:37:50) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> list(reversed({1: 1}))
[1]
>>> list(reversed({}))

================================ RESTART: Shell ================================

>>

[ned-deily]

Outside of IDLE, the example causes a segfault. With debug build of current master HEAD:

Assertion failed: (value != NULL), function dictreviter_iternext, file ../../source/Objects/dictobject.c, line 3834.

    if (d->ma_values) {
        if (i < 0) {
            goto fail;
        }
        key = DK_ENTRIES(k)[i].me_key;
        value = d->ma_values[i];
        assert (value != NULL);
    }

[ned-deily]

Thanks for the report, by the way!

[corona10]

This issue is related to reversed dict iter.

>>> a = reversed({})
>>> next(a)
Assertion failed: (value != NULL), function dictreviter_iternext, file Objects/dictobject.c, line 3834.
[1]    1366 abort      ./python.exe

[corona10]

>>> reversed({}.items())
<dict_reverseitemiterator object at 0x106a2bc50>
>>> a = reversed({}.items())
>>> next(a)
Assertion failed: (value != NULL), function dictreviter_iternext, file Objects/dictobject.c, line 3834.
[1]    4106 abort      ./python.exe

[corona10]

Can I take look at this issue?

[pablogsal]

Wops, we made a PR at the same time, Dong-hee Na.

I will close mine :)

[corona10]

Wops, we made a PR at the same time, Dong-hee Na.

lol

I will close mine :)

Oh.. thank you for giving me a chance.

[serhiy-storchaka]

The proposed fix fixes a crash, but there is other bug in iterating shared dicts.

class A:
    def __init__(self, x, y):
        if x: self.x = x
        if y: self.y = y

a = A(1, 2)
print(list(iter(a.__dict__)))
print(list(reversed(a.__dict__)))
b = A(1, 0)
print(list(iter(b.__dict__)))
print(list(reversed(b.__dict__)))

With PR 16846 the last print outputs [] instead of expected ['x']. It crashes without PR 16846, so this issue is not only about empty dicts.

[corona10]

The proposed fix fixes a crash, but there is other bug in iterating shared dicts.

Yes, you are right.
But I can not work on this issue today.
(I have to finalize my paperwork by today :-()
since priority is critical if other core developers finalize this issue today. It will be okay for me.

[corona10]

FYI

c = A(0, 1)
print(type(c.__dict__))
print(list(iter(c.__dict__)))
print(list(reversed(c.__dict__)))

works as we expected.

[methane]

When dict is empty, di_pos of reverse iterator must be -1, not 0.
Additionally, di_pos must be initialized from ma_used when dict is key sharing dict.

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 64876e0519..6c4b41700b 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -3452,10 +3452,15 @@ dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
     di->di_dict = dict;
     di->di_used = dict->ma_used;
     di->len = dict->ma_used;
-    if ((itertype == &PyDictRevIterKey_Type ||
-         itertype == &PyDictRevIterItem_Type ||
-         itertype == &PyDictRevIterValue_Type) && dict->ma_used) {
+    if (itertype == &PyDictRevIterKey_Type ||
+            itertype == &PyDictRevIterItem_Type ||
+            itertype == &PyDictRevIterValue_Type) {
+        if (dict->ma_values) {
+            di->di_pos = dict->ma_used - 1;
+        }
+        else {
             di->di_pos = dict->ma_keys->dk_nentries - 1;
+        }
     }
     else {

[pablogsal]

New changeset 24dc2f8 by Pablo Galindo (Dong-hee Na) in branch 'master':
bpo-38525: Fix a segmentation fault when using reverse iterators of empty dict (GH-16846)
24dc2f8

[miss-islington]

New changeset d73205d by Miss Islington (bot) in branch '3.8':
bpo-38525: Fix a segmentation fault when using reverse iterators of empty dict (GH-16846)
d73205d

[pablogsal]

Closing this.

Thanks, Dong-hee Na and everyone involved in the issue!