Recursive structures

[Scott David Daniels]

Thomas Guettler wrote:
> code to do the test

The following transformation of his code shows how exceptions
can be used to make code read more clearly.  There are a few
issues (such as AVOIDITER) to decide on, and usually you are
inquiring about your own data structures (which you'll know
more about).  Recursive data structures, like deepcopy, are
matters of interpretation of data, and cannot really be answered
without knowing what you mean by your data (and possibly why you
are inquiring).  I have also done a few things to speed up the
code (my premature optimization sin) such as lifting constant
expressions to module load time.


from types import *
MethodWrapperType = type([].__delattr__)

LEAVES = set([NoneType, TypeType, BooleanType, IntType, LongType,
     FloatType, ComplexType, StringType, UnicodeType, FunctionType,
     CodeType, ClassType, MethodType, UnboundMethodType,
     BuiltinMethodType, BuiltinFunctionType, ModuleType, FileType,
     XRangeType, EllipsisType, TracebackType, FrameType, BufferType,
     StringType, MethodWrapperType, MethodWrapperType])

FORCELIST = set([GeneratorType, SliceType])
         # these are dicey: can cause lots of side-effects
AVOIDITER = set()
         # Here go things like itertools.count -- infinite generators

class RecursionFoundError(Exception): pass

def walks(obj, seen):
     identity = id(obj)
     if identity in seen:
         raise RecursionFoundError, obj
     mytype = type(obj)
     if mytype in LEAVES:
         return
     seen = seen.copy()  # (obj, obj) is not recursive, so new copy
     seen.add(identity)
     if mytype in FORCELIST:
         obj = list(obj) # this is a new obj, so not in the structure
         mytype = ListType
     for attr in dir(obj):
         walks(getattr(obj, attr), seen)

     if mytype not in AVOIDITER:
         try:
             for item in obj:
                 walks(item, seen)
         except TypeError:
             pass
     try:
         for key, value in obj.items():
             walks(key, seen)  # Key might be object w/ hash method
             walks(value, seen)
     except AttributeError:
         pass


def isrecursive(obj):
     try:
         walks(obj, set())
     except RecursionFoundError, err:
         return True    # err.args[0] is the looping object
     return False


--Scott David Daniels
Scott.Daniels at Acm.Org