classification
Title: Cannot pickle self-referencing sets
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.4
process
Status: closed Resolution: duplicate
Dependencies: Superseder: Implement PEP 3154 (pickle protocol 4)
View: 17810
Assigned To: alexandre.vassalotti Nosy List: alex, alexandre.vassalotti, bcroq, belopolsky, eric.araujo, grubert, jackdied, jcea, mstefanro, pitrou, rhettinger, schmir, zzzeek
Priority: low Keywords: patch

Created on 2010-07-15 23:01 by belopolsky, last changed 2013-11-30 05:07 by alexandre.vassalotti. This issue is now closed.

Files
File name Uploaded Description Edit
cycle.py belopolsky, 2010-07-15 23:05 Script reproducing the bug
self_referential-sets.patch mstefanro, 2012-07-26 23:57 Adds support for self-referential sets
sets-test.patch mstefanro, 2012-07-27 14:26 Adds testing of pickling/unpickling sets
Messages (11)
msg110397 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-07-15 23:01
Attached script, cycle.py demonstrates a simplification of the behavior reported by mike bayer in msg77200.

Essentially, the script attempts to pickle a set that contains a class instance that has an attribute referring back to the set:

class C:
    pass
c = C()
cycle = set([c])
c.foo = cycle

An attempt to pickle the *cycle* object triggers an assertion error in 2.7 or in 3.2 with disabled _pickle acceleration and produces a broken cycle in 3.2 or if cPickle is used instead of pickle in 2.7.

$ python3 cycle.py
FAIILURE
..

$ python2 cycle.py
Traceback (most recent call last):
  ..
  File ".../pickle.py", line 244, in memoize
    assert id(obj) not in self.memo
AssertionError

If you run cycle.py with an argument, it uses a dict instead of set to create the cycle and shows that the cycles with dict can be pickled correctly:

$ python3 cycle.py dict
SUCCESS
..

After reporting success or failure, cycle.py, prints a disassembly of the pickle stream which makes it clear what happens:

In case of dict, we see the following:

$ python3 cycle.py dict
SUCCESS
 ..
    2: }    EMPTY_DICT
    3: q    BINPUT     0
 ..
   26: X    BINUNICODE 'foo'
..
   36: h    BINGET     0
   38: s    SETITEM
..
   40: N    NONE
   41: s    SETITEM

An empty dict is created and saved in the memo.  Then a C object is built with foo attribute is set to the dict retrieved from the memo. Finally, the same dict is updated with (C object, None) key-value pair.  The result is the cycle identical to the one we built in python code.

The sets, however, are built differently.  There is no pickle opcode to add items to a set, so all set items must exist by the time set is built.  So here is what we see:  

$ python3 cycle.py
FAIILURE
    2: c    GLOBAL     'builtins set'
   16: q    BINPUT     0
.. instead of empty set the constructor is saved in memo
   42: X    BINUNICODE 'foo'
   52: h    BINGET     0
..
   63: R    REDUCE
.. a set object containing c is constructed 
   66: s    SETITEM  
.. and assigned to c.foo
   72: R    REDUCE
.. another set object is constructed containing c
 
As a result, we have

cycle = {c}
c.foo = {c}

Instead of 

c.foo = cycle
msg110402 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-07-16 00:16
I am reclassifying this as an RFE because as a bug, this is a duplicate of issue1062277.  The later contains an excellent description of the problem by Dima Dorfman:

     Our pickle implementations don't check for reduce
     cycles. This is somewhat cosmetic except that stack
     overflow protection is imperfect (for cPickle), causing
     crashes, and some kinds of cycles trigger asserts (in
     pickle).  [msg47267]

This is undeniably a bug and the solution offered in issue1062277 is quite reasonable: detect reduce cycles and bail out with an informative message.  This will not solve the problem of pickling self-referencing sets, but at least once documented can be defended as expected behavior.

What remains after issue1062277 is a feature request to allow pickling of self-referencing sets.  I would argue that this is really a pathological case.  Sets are not supposed to contain mutable items and immutable objects cannot create reference cycles among themselves.

The test case in cycle.py tricks set into accepting mutable objects by creating a class with default __hash__.  This falls into a category of "don't do it".

I am lowering the priority and adding #1062277 as a dependency.  Once #1062277 is fixed, I would not mind closing this as "won't fix".
msg110403 - (view) Author: mike bayer (zzzeek) Date: 2010-07-16 00:26
where is it defined that sets are not "supposed" to contain mutable items?   such a requirement vastly limits the usefulness of sets.

Consider that relational database rows are mutable.  A result set containing multiple rows which each have a primary key comprises a set, hashed on primary key.  But other attributes of each row can be updated.   Surely this is not controversial ?  What Python data structure should I (and a whole bunch of Python ORMs) be using to represent mutable, relational database rows, unordered and unique on primary key, in memory ?
msg110407 - (view) Author: Jack Diederich (jackdied) * (Python committer) Date: 2010-07-16 00:52
Mike, it is better to think of database rows as immutable tuples.  During the course of a query the contents of the database are considered static - hence all that locking and kvetching about this or that database not having "true" foreign key support.  If database rows were mutable the results of a JOIN could be nonsensical.
msg110408 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-07-16 00:57
On Thu, Jul 15, 2010 at 8:26 PM, mike bayer <report@bugs.python.org> wrote:
..
> where is it defined that sets are not "supposed" to contain mutable items?   such a requirement vastly limits the usefulness of sets.
>

Well, there is no such requirement. The actual requirement is that
they should be hashable.  For built-in types, however hashable is the
same as immutable.  Arguably, user-defined classes should emulate
that.

> Consider that relational database rows are mutable.  A result set containing multiple rows which each have a primary key comprises a set, hashed on primary key.  But other attributes of each row can be updated.   Surely this is not controversial ?  What Python data structure should I (and a whole bunch of Python ORMs) be using to represent mutable, relational database rows, unordered and unique on primary key, in memory ?

Why wouldn't you represent a result set as a dict mapping primary key
(tuple) to list of column values?
msg110409 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-07-16 00:59
On Thu, Jul 15, 2010 at 8:52 PM, Jack Diederich <report@bugs.python.org> wrote:
..
>   If database rows were mutable the results of a JOIN could be nonsensical.

And if your result set is self-referential you have a bigger problem
on your hands than not being able to pickle it. :-)
msg110410 - (view) Author: mike bayer (zzzeek) Date: 2010-07-16 02:05
OK, more specifically, here's the kind of situation where items in a set are mutable:

company = Session.query(Company).first()

# company.employees is a set()
company.employees

# each employee references the parent company
for e in company.employees:
    assert e.company is company

So nothing is mutated relationally in this case.   It's just a plain old bidirectional structure.    If two objects are related via many-to-many, then you might have a set in both directions.   I'm not sure if this specific situation produces the pickle bug, however, it's been awhile since I've seen which specific case causes the problem.   But there are mutable items in a set in these examples and it doesn't seem unreasonable to me.
msg110423 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-07-16 09:51
> The test case in cycle.py tricks set into accepting mutable objects by > creating a class with default __hash__.  This falls into a category of > "don't do it".

I beg to differ. There is a reason we allow people to define __hash__ and that's to define arbitrary hashable types (not only immutable ones).
Furthermore, the default __hash__ (equivalent to id()) is also perfectly useful in some cases.
And in object-oriented designs it is very common to have reference cycles.
msg110617 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-07-17 23:43
Upon further investigation, I am no longer convinced that "reduce cycles" are necessarily fatal to pickling.  I am attaching a script testcycle.py that allows creating cycles using various containers. It takes the name of container class as an argument and prints SUCCESS/FAILURE followed by annotated pickle disassembly.  It turns out that self-referential tuples are pickled successfully even though being immutable, they must receive their state through arguments:


$ ./python.exe testcycle.py tuple
SUCCESS
    0: \x80 PROTO      3              Protocol version indicator.
    2: c    GLOBAL     '__main__ C'   Push a global object (module.attr) on the stack.
   14: )    EMPTY_TUPLE               Push an empty tuple.
   15: \x81 NEWOBJ                    Build an object instance.
   16: q    BINPUT     1              Store the stack top into the memo.  The stack is not popped.
   18: }    EMPTY_DICT                Push an empty dict.
   19: X    BINUNICODE 'foo'          Push a Python Unicode string object.
   27: h    BINGET     1              Read an object from the memo and push it on the stack.
   29: \x85 TUPLE1                    Build a one-tuple out of the topmost item on the stack.
   30: q    BINPUT     4              Store the stack top into the memo.  The stack is not popped.
   32: s    SETITEM                   Add a key+value pair to an existing dict.
   33: b    BUILD                     Finish building an object, via __setstate__ or dict update.
   34: 0    POP                       Discard the top stack item, shrinking the stack by one item.
   35: h    BINGET     4              Read an object from the memo and push it on the stack.
   37: .    STOP                      Stop the unpickling machine.
highest protocol among opcodes = 2

There is a comment in save_tuple() that explains how it works:

            # Subtle.  d was not in memo when we entered save_tuple(), so                                                           
            # the process of saving the tuple's elements must have saved                                                            
            # the tuple itself:  the tuple is recursive.  The proper action                                                         
            # now is to throw away everything we put on the stack, and                                                              
            # simply GET the tuple (it's already constructed).  This check                                                          
            # could have been done in the "for element" loop instead, but                                                           
            # recursive tuples are a rare thing.        


I wonder if the same trick could be used in save_reduce() to resolve #1062277 by pickling "reduce cycles" correctly instead of bailing out when they are encountered.
msg166530 - (view) Author: Stefan Mihaila (mstefanro) * Date: 2012-07-26 23:57
I have attached a fix to this issue (and implicitly issue1062277).

This patch allows pickling self-referential sets by implementing a set.__reduce__ which uses states as opposed to ctor parameters.

Before:
>>> s=set([1,2,3])
>>> s.__reduce__()
(<class 'set'>, ([1, 2, 3],), None)
>>> len(pickle.dumps(s,1))
38

After:
>>> s=set([1,2,3])
>>> s.__reduce__()
(<class 'set'>, (), [1, 2, 3])
>>> len(pickle.dumps(s,1))
36

Basically what this does is: instead of unpickling the set by doing set([1,2,3]) it does s=set(); s.__setstate__([1,2,3]).
States are supported in all versions of pickle so this shouldn't break anything.
Creating empty data structures and then filling them is the way pickle does it for all mutable containers in order to allow self-references (with the exception of sets, of course).

Since memoization is performed after the object is created but before its state is set, pickling an object's state can contain references to oneself.

    class A:
        pass

    a=A()
    s=set([a])
    a.s=s

    s_=loads(dumps(s,1))
    next(iter(s_)).s is s_ # True

Note that this fix only applies for sets, not frozensets. Frozensets are a different matter, because their immutability makes it impossible to set their state. Self-referential frozensets are currently supported in my implementation of pickle4 using a trick similar to what tuples use. But the trick works more easily there because frozensets have their own opcodes, like tuples.

Also note that applying this patch makes Lib/test/pickletester.py:test_pickle_to_2x fail (DATA3 and DATA6 there contain pickled data of sets, which naturally have changed).
I'll upload a patch fixing this as well as adding one or more test for sets soon.
msg166570 - (view) Author: Stefan Mihaila (mstefanro) * Date: 2012-07-27 14:26
Attaching patch for fixing a test and adding better testing of sets.
History
Date User Action Args
2013-11-30 05:07:31alexandre.vassalottisetstatus: open -> closed
assignee: alexandre.vassalotti
superseder: Implement PEP 3154 (pickle protocol 4)
resolution: duplicate
stage: patch review -> resolved
2012-07-27 14:37:38pitrousetassignee: belopolsky -> (no value)
dependencies: - Pickle breakage with reduction of recursive structures
stage: needs patch -> patch review
versions: + Python 3.4, - Python 3.2
2012-07-27 14:26:48mstefanrosetfiles: + sets-test.patch

messages: + msg166570
2012-07-26 23:57:26mstefanrosetfiles: + self_referential-sets.patch

nosy: + mstefanro
messages: + msg166530

keywords: + patch
2011-12-11 01:23:51jceasetnosy: + jcea
2011-04-24 03:56:22alexsetnosy: + alex
2011-03-08 12:58:13bcroqsetnosy: + bcroq
2010-12-14 14:45:33belopolskylinkissue10700 superseder
2010-09-02 00:38:32rhettingersetpriority: normal -> low
2010-08-09 19:01:01terry.reedysetnosy: rhettinger, belopolsky, grubert, pitrou, jackdied, alexandre.vassalotti, schmir, eric.araujo, zzzeek
components: + Library (Lib), - Interpreter Core
versions: - Python 2.7
2010-07-20 05:38:29belopolskylinkissue1062277 superseder
2010-07-17 23:43:15belopolskysetpriority: low -> normal

messages: + msg110617
2010-07-16 09:51:51pitrousetnosy: + pitrou
messages: + msg110423
2010-07-16 02:05:31zzzeeksetmessages: + msg110410
2010-07-16 00:59:47belopolskysetmessages: + msg110409
2010-07-16 00:57:03belopolskysetmessages: + msg110408
2010-07-16 00:52:48jackdiedsetnosy: + jackdied
messages: + msg110407
2010-07-16 00:26:37zzzeeksetmessages: + msg110403
2010-07-16 00:16:58belopolskysetpriority: normal -> low
type: behavior -> enhancement
dependencies: + Pickle breakage with reduction of recursive structures
messages: + msg110402
2010-07-15 23:32:23eric.araujosetnosy: + eric.araujo
2010-07-15 23:10:13belopolskylinkissue998998 superseder
2010-07-15 23:05:29belopolskysetfiles: - cycle.py
2010-07-15 23:05:18belopolskysetfiles: + cycle.py
2010-07-15 23:03:44belopolskysetnosy: + rhettinger, grubert, alexandre.vassalotti, schmir, zzzeek
2010-07-15 23:01:40belopolskycreate