Title: ABC Recursion Error on isinstance() with less than recursion limit class hierarchy depth
Type: behavior Stage:
Components: Library (Lib) Versions: Python 3.7, Python 3.6, Python 3.5, Python 2.7
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: AstraLuma, rhettinger, scopatz, serhiy.storchaka
Priority: normal Keywords:

Created on 2017-01-10 04:18 by scopatz, last changed 2017-01-12 18:59 by AstraLuma.

File name Uploaded Description Edit scopatz, 2017-01-10 04:18 Fails at depth 245 rhettinger, 2017-01-11 04:52 Fails at depth 166.
fibo.png scopatz, 2017-01-11 05:49 cache scaling
Messages (4)
msg285090 - (view) Author: Anthony Scopatz (scopatz) * Date: 2017-01-10 04:18
Classes that have an abstract base class somewhere in their hierarchy have a significantly reduced depth with respect to the recursion limit. In the attached minimal example, the class hierarchy is only able to be 245 deep past the ABC before a recursion error, rather than the expected 1000. 

Also disconcerting is that this recursion error is triggered by unrelated objects, namely an isinstance() check. This means that the error can happen at any point in the interpreter simply because the offending class exists. You don't need to call isinstance() with the offending class.

This is likely due to the way the way that ABCMeta.__subclasscheck__(). This issue can be avoided by either:

1. Not having a deep-ish hierarchy, or 
2. Calling the trigger, isinstance(), each time a new class is created (inside of the loop).

Option (2) works because it tricks ABCMeta into putting each subclass class into its internal cache of subclasses. This fix is undesirable in general because what triggers the error, in general may not be known and can cross package boundaries.

Note: I only tested this on Python v3.4 and v3.5, but it presumably affects all currently supported versions of Python.
msg285185 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-01-11 04:51
Not sure if this is related, but I have a simple Cache class that gets a recursion error at a depth of about 166 calls (a sixth of the expected 1000).  I suspect that the reason is the many of the steps individually add to the recursion depth causing the recursion limit to be reached at some integer multiple faster than would be expected.
msg285189 - (view) Author: Anthony Scopatz (scopatz) * Date: 2017-01-11 05:49
It certainly seems related. Attached is an image that displays the scaling of the cache example.  The full notebook that generated this image is at [1]. The notebook shows that it does seem to converge towards a value of 1/6th. 

msg285342 - (view) Author: Jamie Bliss (AstraLuma) Date: 2017-01-12 18:59
I consider it debatable as to if this is a bug in ABC (for using recursion in a way that limits class tree depth) or in CPython (for accounting recursion in such a way you can get significantly shallower stacks).
Date User Action Args
2017-01-12 18:59:07AstraLumasetmessages: + msg285342
2017-01-12 17:55:02AstraLumasetnosy: + AstraLuma
2017-01-11 05:49:16scopatzsetfiles: + fibo.png

messages: + msg285189
2017-01-11 04:52:14rhettingersetfiles: +
2017-01-11 04:51:31rhettingersetnosy: + rhettinger
messages: + msg285185
2017-01-10 05:53:47serhiy.storchakasetnosy: + serhiy.storchaka

versions: - Python 3.3, Python 3.4
2017-01-10 04:18:47scopatzcreate