Fix problems related to reduce cycles during pickling. A
"reduce cycle" is what happens when a __reduce__
implementation returns an args that cycles back through the
object it tried to reduce. This can't work because the
unpickler has to call the constructor with those args, but
it doesn't yet have that object to be able to place inside
the args. There are two problems related to this:

  1. The standard reduce implementation for proto < 2 in
     copy_reg (_reduce_ex) doesn't correctly deal with
     recursive structures. reduce_2 in typeobject.c does the
     right thing by using listitems and dictitems. Fix
     _reduce_ex by making it do the same thing. This is okay
     for proto < 2 because those arguments are a pickler-
     side feature. Tested in test_stdreducecycle.

  2. 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). Fixed in pickle and cPickle by introducing a
     reducing_now set; on entering save_reduce, the object
     id being saved must not be in that set or we've been
     called recursively while saving the callable or
     arguments. Tested in test_reduce_cycle.

This shouldn't change any semantics. That reduce shouldn't
introduce cycles through args isn't documented, but it can't
work any other way.

Possible improvement: If we want to support reducing of real
immutable containers we might have to relax the reduction
cycle test to give the cycle a chance of resolving itself
normally (by constructing a partial object to pass to the
constructor and filling it in later). I'm not sure if this
trouble is worth it just to avoid writing a
frozenset.__setstate__.

See also: http://mail.python.
org/pipermail/python-dev/2004-October/049714.html

It would be very good if someone familiar with pickle
reviewed this; I am still not very confident that I
completely understand all the issues.

Logged In: YES 
user_id=80475

IMO, this is more of a feature request than a bug.  Also, it
needs to be fully thought-out and discussed.  Putting this
sort of thing in just before the Py2.4 release candidate is
probably not wise.

Logged In: YES 
user_id=908995

Triggering assertions (pickle) and producing incorrect output
(cPickle) are certainly bugs, and being able to pickle a
recursive structure is not a feature request. The copy_reg
part of the patch is the real fix, and as it's almost a
translation of what reduce_2 already does, it should be safe
for 2.4. I agree that the rest of the patch--to check for
cycles during pickling--should wait until 2.5.

Patch has test, can someone try it? I think it might be fixed already.

The issue is still present in py3k.  Attaching an updated patch with tests only.  Is this the same as issue998998?

As I explained in msg110617 under issue9269, it is possible that we can do better than simply detect reduce cycles and bail out.

I am torn between two options:

1. Reject this patch and wait until a proper solution is found.

2. Admit that better is the enemy of good and start with proper error reporting on reduce cycles by accepting this patch.

My only concern about this patch is that it is likely to affect performance because pickling will have to maintain the "reducing_now" dictionary that is parallel to the memo dictionary.