14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#! /usr/bin/env python 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"""Find the maximum recursion limit that prevents interpreter termination. 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThis script finds the maximum safe recursion limit on a particular 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmplatform. If you need to change the recursion limit on your system, 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmthis script will tell you a safe upper bound. To use the new limit, 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmcall sys.setrecursionlimit(). 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThis module implements several ways to create infinite recursion in 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmPython. Different implementations end up pushing different numbers of 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmC stack frames, depending on how many calls through Python's abstract 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmC API occur. 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmAfter each round of tests, it prints a message: 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"Limit of NNNN is fine". 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmThe highest printed value of "NNNN" is therefore the highest potentially 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmsafe limit for your system (which depends on the OS, architecture, but also 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmthe compilation flags). Please note that it is practically impossible to 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtest all possible recursion paths in the interpreter, so the results of 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmthis test should not be trusted blindly -- although they give a good hint 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmof which values are reasonable. 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmNOTE: When the C stack space allocated by your system is exceeded due 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmto excessive recursion, exact behaviour depends on the platform, although 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmthe interpreter will always fail in a likely brutal way: either a 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmsegmentation fault, a MemoryError, or just a silent abort. 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmNB: A program that does not use __methods__ can set a higher limit. 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm""" 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport sys 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport itertools 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass RecursiveBlowup1: 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __init__(self): 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.__init__() 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_init(): 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return RecursiveBlowup1() 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass RecursiveBlowup2: 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __repr__(self): 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return repr(self) 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_repr(): 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return repr(RecursiveBlowup2()) 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass RecursiveBlowup4: 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __add__(self, x): 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return x + self 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_add(): 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return RecursiveBlowup4() + RecursiveBlowup4() 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass RecursiveBlowup5: 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __getattr__(self, attr): 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return getattr(self, attr) 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_getattr(): 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return RecursiveBlowup5().attr 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass RecursiveBlowup6: 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __getitem__(self, item): 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self[item - 2] + self[item - 1] 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_getitem(): 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return RecursiveBlowup6()[5] 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_recurse(): 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return test_recurse() 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef test_cpickle(_cache={}): 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm import cPickle 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm except ImportError: 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print "cannot import cPickle, skipped!" 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm l = None 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for n in itertools.count(): 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm l = _cache[n] 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm continue # Already tried and it works, let's save some time 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm except KeyError: 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i in range(100): 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm l = [l] 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm cPickle.dumps(l, protocol=-1) 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm _cache[n] = l 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef check_limit(n, test_func_name): 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sys.setrecursionlimit(n) 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if test_func_name.startswith("test_"): 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print test_func_name[5:] 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print test_func_name 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_func = globals()[test_func_name] 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm test_func() 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # AttributeError can be raised because of the way e.g. PyDict_GetItem() 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # silences all exceptions and returns NULL, which is usually interpreted 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # as "missing attribute". 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm except (RuntimeError, AttributeError): 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pass 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print "Yikes!" 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmlimit = 1000 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmwhile 1: 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_recurse") 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_add") 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_repr") 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_init") 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_getattr") 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_getitem") 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm check_limit(limit, "test_cpickle") 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print "Limit of %d is fine" % limit 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm limit = limit + 100 118