I've been able to reliably trigger dict.pop to raise a system error: 

See https://github.com/pytest-dev/pytest/issues/1925


I have issues getting a small test-case that triggers it, though by changing the pop method of dict to print the returned value:

PyObject *
_PyDict_Pop(PyDictObject *mp, PyObject *key, PyObject *deflt){
...
    printf("\nreturn End value %x\n", old_value );
    return old_value;

}

I've been able to see that the last return sometime return Null:

[snip]

return End value 0
Fatal Python error: a function returned NULL without setting an error
SystemError: <built-in method pop of dict object at 0x10473f238> returned NULL without setting an error

Current thread 0x00007fff77139300 (most recent call first):
  File "/usr/local/lib/python3.6/site-packages/_pytest/capture.py", line 83 in reset_capturings
  File "/usr/local/lib/python3.6/site-packages/_pytest/config.py", line 869 in _ensure_unconfigure
  File "/usr/local/lib/python3.6/site-packages/_pytest/main.py", line 121 in wrap_session
  File "/usr/local/lib/python3.6/site-packages/_pytest/main.py", line 125 in pytest_cmdline_main
  File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 596 in execute
  File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 333 in <lambda>
  File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 338 in _hookexec
  File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 724 in __call__
  File "/usr/local/lib/python3.6/site-packages/_pytest/config.py", line 57 in main
  File "/usr/local/lib/python3.6/site-packages/pytest.py", line 17 in <module>
  File "/Users/bussonniermatthias/dev/git-cpython/Lib/runpy.py", line 85 in _run_code
  File "/Users/bussonniermatthias/dev/git-cpython/Lib/runpy.py", line 193 in _run_module_as_main

Aborted

Which I suppose is not desirable.

I'm quite uncomfortable with C so I'm far from being able to propose a patch or describe why this would happen...

Victor Stinner seem to have made the last changes to these methods in http://bugs.python.org/issue27350 . Not sure if the etiquette is to add them to the nosy list in this case. 

Discovered because of nightly continuous integration with travis on github.com/xonsh/xonsh

Oh, also I've bisect it to the compact-dict commit,
and the exact instance of __dict__.pop that fails depends on the machine.

Reliable same location on travis-ci and locally, but travis-ci location and local differ on where it triggers this.

I've forgot to convert split table into combined table when del and .pop().
I'm sorry, and thanks to finding it.

Are you sure INADA? The previous dict implementation has the same constraint but does merge in dict_pop.

does should be does not. Sorry.

> Xiang Zhang added the comment:
>
> Are you sure INADA? The previous dict implementation has the same constraint but does merge in dict_pop.
>

Yes.  New dict implementation preserves insertion order.

class A:
    ...

a, b = A(), A()
a.a, a.b, a.c = 1, 2, 3
b.a, b.b, b.c = 4, 5, 6
del a.b  # or a.pop('b')
a.b = 7

assert list(a.__dict__) == ["a", "c", "b"]
assert list(b.__dict__) == ["a", "b", "c"]

This is difficult for key-sharing dict (aka. split table).

We may be able to allow some simple del and pop operation for split table.
But we should keep best balance between simplicity and efficiency.
And we don't have enough time before 3.6b1.

> I'm sorry, and thanks to finding it.

No worries, that's what nightly are for right ? And I only dug up a failing tests :-) Thanks to you for writing this !

> [snip]
> This is difficult for key-sharing dict (aka. split table).

I'm not going to pretend I understand the details, though I applied the latest patch: 
fix-compact-dict-deletion.patch	methane, 2016-09-09 04:11

And it does fix this issue for me (at least on my local machine)

Looking at the code the only thing I see is that you seem to return NULL in Pop and -1 in Clear. Not sure if this what you meant, I'm un familar with all this; but thanks a lot again for the your work and the quick response.

I would really appreciate if someone can write an unit test.

I'm not confident to fix a bug without unit test, on such tricky part of Python internals (splitted/combined dict).

Added test which reproduce the issue on current master.

New changeset 4a5b61b0d090 by Victor Stinner in branch 'default':
Fix SystemError in compact dict
https://hg.python.org/cpython/rev/4a5b61b0d090

> Added test which reproduce the issue on current master.

Oh, great :-) Thanks for the quick fix AND test.

I pushed your latest change.

I'd like to reopen this one since I still don't think this change is needed and suggest to revert since this change make split table combined on deletion.

Deletion will not alter split dict's order. Only insertion after deletion will. But this case is already handled in insertdict[0]. So I think we don't have to combine once an item is deleted from split dict.

The example INADA gives works well with the previous implementation(before this change). The problem there is a SystemError I think is dict.pop() doesn't handle pending state (del dict does, so you can produce the same failure when try del dict[]). We only add `|| *value_addr == NULL` as delitem does.

poc.patch reverts the change (preserve the tests, eliminating the size compare part) and add pending state handling in dict.pop(). It passes. And if you remove the pending state handling, you can product the SystemError.

I'd like to know if my idea is totally wrong. :)

[0] https://hg.python.org/cpython/file/tip/Objects/dictobject.c#l1057

Ohh, mistakes.

> so you can produce
can should be can not

> We only add
We only need to add

> you can product the
product should be produce

Xiang:
Preserving insertion order in shared-key dict is possible, but it's hard.
If we allow it, we should add tons of test for shared-key dict.

I'll describe why it's harder than you think.

Current implementation allow insertion to split table only when:

    /* When insertion order is different from shared key, we can't share
     * the key anymore.  Convert this instance to combine table.
     */
    if (_PyDict_HasSplitTable(mp) &&
        ((ix >= 0 && *value_addr == NULL && mp->ma_used != ix) ||
         (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
        if (insertion_resize(mp) < 0) {

`ix >= 0 && *value_addr == NULL` means it's pending slot.
`mp->ma_used == ix` ensure insertion order.  And if we allow deletion, this check will be broken.

For example:

a, b = C()
a.a, a.b, a.c = 1, 2, 3  # shared-key order
b.a, b.b, b.c = 1, 2, 3  # same order, no problem

del b.a  # mp->ma_used = 2
del b.b  # mp->ma_used = 1

b.b = 42  # It's OK because mp->ma_used == ix == 1. Keep sharing.

assert(list(b.__dict__.keys()) == ["c", "b"])  # AssertionError! Actual order is [(PENDING "a",) "b", "c"]

> add tons of test for shared-key dict

So what if we delete mp->ma_used == ix or use mp->ma_keys->dk_nentries == ix? Do we still have any case breaking the order?

Xiang: I will remove the now useless check, but after beta 1.

This issue is about SystemError and you now want to reuse the issue to
implement an optimization. Please open a new issue for supporting deletion
on split table if you consider that it's possible and that it would be a
good idea.

The Blaze test suite segfaults with 4a5b61b0d090.

> The Blaze test suite segfaults with 4a5b61b0d090.

What is the Blaze test suite?

Are you sure that you really recompiled Python from scratch? Try:

make distclean && ./configure --with-pydebug && make

Yes, I'm sure. I even cloned a fresh repo. Also, I tested in
release mode (not --with-pydebug).


https://github.com/blaze/blaze

The immediate question is: is this serious enough to block 3.6.0b1 or can it wait for b2?   The b1 bits are just about ready to be published.

I'm not sure. In the Blaze test suite, 1e7b636b6009 has the SystemError.
4a5b61b0d090 segfaults.

Blaze is pushing Python's dynamic capabilities to absolute limits,
so perhaps this is specific to a few applications only.


For Blaze *itself* there is no difference whether this is fixed now
or in the next beta.  So releasing 3.6.0b1  now and setting this back
to blocker afterwards sounds good to me.

OK, thanks, Stefan!  OK with you, Victor?

If Victor can't reply now (it's getting late in Europe), I'd just release.  Pretend that I set it to deferred blocker. :)

Yes, he's had a *long* day.  I'll take your advice, Stefan.  Thanks.

I didn't see any segfault on the Python test suite on buildbots. It's
either a bug in Blaze (Python C API change like METH_CALL) or a real bug in
CPython. It's a beta, we can fix bugs later :-)

It could still be a stack overflow, but on the surface it does
not look like one. It's definitely related to the aforementioned
revision:

==3442== Invalid read of size 8
==3442==    at 0x49DBD8: _PyDict_Pop (dictobject.c:1743)
==3442==    by 0x4A0BE2: dict_pop (dictobject.c:2732)
==3442==    by 0x4AA5F8: _PyCFunction_FastCallDict (methodobject.c:229)
==3442==    by 0x4AA70B: _PyCFunction_FastCallKeywords (methodobject.c:267)
==3442==    by 0x55FE63: call_function (ceval.c:4794)
==3442==    by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267)
==3442==    by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718)
==3442==    by 0x560123: _PyFunction_FastCall (ceval.c:4876)
==3442==    by 0x56023B: fast_function (ceval.c:4906)
==3442==    by 0x55FF91: call_function (ceval.c:4815)
==3442==    by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267)
==3442==    by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718)
==3442==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==3442== 
==3442== 
==3442== Process terminating with default action of signal 11 (SIGSEGV)
==3442==  Access not within mapped region at address 0x0
==3442==    at 0x49DBD8: _PyDict_Pop (dictobject.c:1743)
==3442==    by 0x4A0BE2: dict_pop (dictobject.c:2732)
==3442==    by 0x4AA5F8: _PyCFunction_FastCallDict (methodobject.c:229)
==3442==    by 0x4AA70B: _PyCFunction_FastCallKeywords (methodobject.c:267)
==3442==    by 0x55FE63: call_function (ceval.c:4794)
==3442==    by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267)
==3442==    by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718)
==3442==    by 0x560123: _PyFunction_FastCall (ceval.c:4876)
==3442==    by 0x56023B: fast_function (ceval.c:4906)
==3442==    by 0x55FF91: call_function (ceval.c:4815)
==3442==    by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267)
==3442==    by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718)

> So what if we delete mp->ma_used == ix or use mp->ma_keys->dk_nentries == ix? Do we still have any case breaking the order?

Yes.  `mp->ma_used == ix` means no more guard about key ordering.

class C:
    ...

a, b = C()
a.a, a.b = 1, 2  # shared key order is [a, b]

# b has [a, b] pending slot too, and no guard when inserting  pending slot.
b.b, b.a = 3, 4  # continue to using sharing key

assert list(b.__dict__.keys()) == ['b', 'a'])  # AssertionError!

---
`mp->ma_keys->dk_nentries == ix` is nonsense.  It prohibits to inserting pending slot:

a, b = C()
a.a, a.b = 1, 2  # shared key order is [a, b]

# Since ma_keys is shared, b's dk_nentries == 2
b.a = 3  # ix = 0, dk_nentries = 2; stop using sharing keys.

---

To keep using sharing key, my idea is adding one more member to dict: mp->ma_values_end.

When inserting to pending or empty slot, check that `ix >= mp_ma_values_end` to ensure ordering
and `set mp->ma_values_end = ix+1` if it's OK.

a, b = C()  # Both of ma_values_end = 0
a.a, a.b = 1, 2  # shared key order is [a, b], a's ma_values_end = 2
b.b = 3          # ma_values_end (=0) <= ix (=1); OK; set ma_values_end = 2
b.a = 4          # ma_values_end (=2) >  ix (=0); NG; convert to combined table

But testing such an implementation detail is hard from pure Python. (No API for checking ma_values_end,
the dict is split or combined, and two dict share keys).

I don't know adding such hack is worth enough.
Dict is made by tons of hacks, you know.

I think new OrderedDict implementation based on new dict implementation is more worth.
If dict is far more efficient than OrderedDict, people may use dict even when OrderedDict should be used.
But I don't know it can be done after beta1.

> assert list(b.__dict__.keys()) == ['b', 'a'])  # AssertionError!

No, there is no error. Once an pending slot is encountered it is combined. But inserting pending slots is prohibited and it's far from ideal. 

We need to know if the pending slot is the last entry or not. But it seems we can't achieve it using the current implementation. Sad. :(

In short, I give up. Sorry for the noise.

New changeset 579141d6e353 by Victor Stinner in branch 'default':
Issue #28040: Cleanup find_empty_slot()
https://hg.python.org/cpython/rev/579141d6e353

Stefan Krah: "It could still be a stack overflow, but on the surface it does not look like one. It's definitely related to the aforementioned
revision: (...)"

The initial bug reported in this issue is now fixed. Even if the Blaze issue is related, I would really prefer to discuss it in a different issue, so I created #28120: "The Blaze test suite segfaults with 4a5b61b0d090".

@Xiang: I simplified find_empty_slot() to remove code to support split table. Again, if you want to support deletion in split table, please open a new issue.

I now close this issue. Thanks for the report Matthias! Thanks for the quick fix and the unit test Naoki!

I don't understand how the original issue is fixed if 1e7b636b6009
exhibits the SystemError and the very next revision 4a5b61b0d090
(the fix) segfaults.  And the test suite works with the previous
dict.

Sure, it can be a third party issue, but this constellation
*does* seem pretty strange.

Happy to discuss it in another issue though.

Stefan Krah: "I don't understand how the original issue is fixed if 1e7b636b6009
exhibits the SystemError"

"SystemError: returned NULL without setting an error" is a generic error, basically it says that a C function has bug :-) It's hard to know exactly which C function has the issue.


"and the very next revision 4a5b61b0d090 (the fix) segfaults"

A segfault is not a SystemError: it's a new bug.


"Sure, it can be a third party issue, but this constellation *does* seem pretty strange."

In case of doubt, I prefer to open a new issue. Please let's continue in the issue #28120 (see my questions there!).

New changeset 3c7456e28777 by Victor Stinner in branch '3.6':
Issue #28040: Cleanup find_empty_slot()
https://hg.python.org/cpython/rev/3c7456e28777