The documentation[1] says:

  Trying to pickle a highly recursive data structure may exceed the
  maximum recursion depth, a RuntimeError will be raised in this
  case. You can carefully raise this limit with sys.setrecursionlimit().

The lightweight pickle module handles this problem correctly (in that it
raises a RuntimeError), but cPickle sometimes raises KeyError instead,
or just silently terminates the interpreter (=crashes). (I have not been
able to pinpoint what it depends on. In the attached example I get
silent termination, but if instead of lists I use sets to describe the
connections, I get the RuntimeError.)

This was mentioned in issue 2480, but that has now been changed to a
feature request to eliminate recursion altogether. That may have a lower
priority, but this crash can be hard to diagnose in a complex
application, and I am not sure if sys.setrecursionlimit() affects
cPickle behavior (I guess not).

[1]: http://docs.python.org/lib/node317.html

What operating system and compiler are you using?

Python 2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit
(Intel)] on win32

(Windows XP Professional 32 bits)

Could you please tell me if this problem arises with this test?

I have just quickly pasted it into an interpreter.

Python 2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit
(Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> class Node(object):
...     pass
...
>>> nodes = [Node() for i in range(500)]
>>> for n in nodes:
...     n.connections = list(nodes)
...     n.connections.remove(n)
...
>>> import cPickle
>>> s = cPickle.dumps( n )

After this line, the interpreter terminated without any further output
(no Python exception and no Windows "General Exception" message box either).

Is it sufficient, or would you prefer me to run the test properly?

Daniel, it'd be great, because it does not crash in linux, so I can not
test it... and I have a patch to apply (see issue 3165), so I wanted to
test it that way.

It works for me as a test case too:

test_deep_recursive (__main__.cPickleDeepRecursive) ... ERROR

======================================================================
ERROR: test_deep_recursive (__main__.cPickleDeepRecursive)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "c:\devel\Python25\Lib\test\test_cpickle.py", line 107, in
test_deep_recursive
    self.assertRaises(RuntimeError, cPickle.dumps, n)
  File "C:\devel\Python25\lib\unittest.py", line 320, in failUnlessRaises
    callableObj(*args, **kwargs)
KeyError: 13352688

Commited this patch to the test cases, and the patch from #3165 to fix
the problem, thank you all!

I reverted the patch, because of #3179, so I'm reopening this.

Note that I left the test in the suite, but commented out (if you find a
patch that solves this, activate the test again).

It seems that each self->nesting++ should be balanced with
self->nesting--. Attached patch enables all tests and corrects the issue

Another version of the patch, that removes the self->nesting member and
uses the Py_EnterRecursiveCall machinery.
I prefer it because it takes into account the depth of the current
python call stack.

The tests pass on my machine (64 bit debian testing) with cpickle2.patch.

Great, Amaury, I applied your second patch... it make all tests pass ok, :)

Commited in 64595.

Thank you all!!

Please check issue #3338 for a dup of this issue with a testcase that
continues to fail after the application of r64595

Thanks Darryl.

We'll continue in that issue, as the patched commited in this one did
not introduce a regression (it just didn't fix the other bug also).