I've seen the problem on Windows only. test_doctest fails and the
problem also causes test_gc to fail when it is run after test_doctest.
W/o a prior run of test_doctest test_gc doesn't fail.

File "c:\dev\python\py3k\lib\test\test_doctest.py", line 1570, in
test.test_doct
est.test_debug
Failed example:
    try: doctest.debug_src(s)
    finally: sys.stdin = real_stdin
Expected:
    > <string>(1)<module>()
    (Pdb) next
    12
    --Return--
    > <string>(1)<module>()->None
    (Pdb) print(x)
    12
    (Pdb) continue
Got:
    > c:\dev\python\py3k\lib\io.py(281)__del__()
    -> try:
    (Pdb) next
    > c:\dev\python\py3k\lib\io.py(282)__del__()
    -> self.close()
    (Pdb) print(x)
    *** NameError: NameError("name 'x' is not defined",)
    (Pdb) continue
    12
**********************************************************************
1 items had failures:
   1 of   4 in test.test_doctest.test_debug
***Test Failed*** 1 failures.
test test_doctest failed -- 1 of 418 doctests failed
test_gc
test test_gc failed -- Traceback (most recent call last):
  File "c:\dev\python\py3k\lib\test\test_gc.py", line 193, in test_saveall
    self.assertEqual(gc.garbage, [])
AssertionError: [<io.BytesIO object at 0x01237968>] != []

2 tests failed:
    test_doctest test_gc

After some hard debugging:
- doctest.debug_src() is unlucky enough to trigger a garbage collection
just when compiling the given code.
- gc collects unreachable objects, among them is an instance of the
class doctest._SpoofOut, which derives from io.StringIO.
- The debugger steps into io.IOBase.__del__

Some possible directions:
- Change the gc thresholds. A very temporary workaround to make the test
pass.
- Find the cycle involving the SpoofOut object, and try to break it in
doctest.py.
- Find a way to disable pdb tracing when the gc is running finalizers.
(this is what happens in 2.5: pdb does not step into a C function)
- Forget everything, and wait for the io.py object to be rewritten in C.

Finally I found a potential problem with the garbage collector in a
specific case:
- Some object C participates in a reference cycle, and contains a
reference to another object X.
- X.__del__ 'resurrect' the object, by saving its 'self' somewhere else.
- X contains a reference to Y, which has a __del__ method.
When collecting all this, gc.garbage == [Y] !
This is not true garbage: if you clean gc.garbage, then the next
gc.collect() clears everything.


Now, try to follow my explanation (if I correctly understand the gc
internals):
- When the cycle is garbage collected, X and Y are detected as
'unreachable with finalizers', and put in a specific 'finalizers' list.
- the cycle is broken, C is deallocated. 
- This correctly triggers X.__del__. X is removed from the 'finalizers'
list.
- when X is resurrected, it comes back to the normal gc tracking list.
- At the end, 'finalizers' contains 3 objects: X.__dict__, Y and Y.__dict__.
- Y is then considered as garbage.

I join a script which reproduces the behaviour. Note that 2.4 and 2.5
are affected too.
In py3k, the 'resurrect' seems to be caused by a (caught) exception in
TextIOWrapper.close(): the exception contains a reference to the frame,
which references the self variable.

Hoping to draw Tim into this... He's the only one I know who truly
understands these issues...

I'm trying to figure out the attached script.  If I run Python 3.0, the script doesn't run because of the undefined gc.DEBUG_OBJECTS.  If I just remove that, the script runs without error.  Does that mean the problem is fixed?  Or is running without an error an example of the problem?

If I add gc.DEBUG_SAVEALL, it fails--but that seems obvious because DEBUG_SAVEALL adds all objects with finalizers to gc.garbage.

The attached script does not "fail". The weird thing is that after gc.collect(), gc.garbage is not empty.
This happens even when gc.set_debug() is not called.

I spent some time to understand the example script today.  The specific issue is that a set of objects get put into the list of unreachable objects with finalizers (both Immutable and Finalizer instances).  When Cycle's __dict__ is cleared, it also decrefs Immutable which resurrects it and Finalizer.  The garbage collector is not prepared for an unreachable finalizer object to become reachable again.  More generally, it's hard to assume anything about the state of the finalizers after unreachable trash is collected.  I'll think more about what to do, but I don't see any easy solutions.

One last thought on this bug.  The problem is that after we try to delete garbage, we really can't know much about the state of the objects in the finalizers list.  If any of the objects that are cleared end up causing a finalizer to run, then any of the objects in the finalizers list may be reachable again.  One possibility is to do nothing with the objects in the finalizers list if there was any garbage to delete.  That means objects with finalizers would be harder to get to gc.collect()--for example, you'd need to call gc.collect() twice in a row.  The first time to clear garbage, the second time to handle unreachable objects with finalizers.  Or the GC could run a second time if garbage was cleared and finalizers was non-empty.

A more complicated possibility would be to track some object state about when a finalizer was run.  If any of the objects in finalizers had a finalizer that ran while garbage was cleared, we could skip the finalizers list.  I don't know how to implement this, since an arbitrary C type could run Python code in tp_dealloc without notifying GC.

What if we simply run another collection on the finalizers list?
after move_finalizers(), set young=finalizers, and start again at update_refs().
This is the "garbage" list anyway, so it's empty most of the time and should not cause any slowdown.

Amaury-- I think that will work.  I put together a small patch that seems to pass all the tests, but it too messy.  We need some care to make sure we don't spin forever if there's some degenerate case where we never escape GC.

The code is still in no shape to submit.  It has lots of debugging prints in it, etc. but the basic structure might work.  Do you want to let me know if it makes sense?

Can we have an update on this please as it seems important.