1#! /usr/bin/env python3
2"""Find the maximum recursion limit that prevents interpreter termination.
3
4This script finds the maximum safe recursion limit on a particular
5platform.  If you need to change the recursion limit on your system,
6this script will tell you a safe upper bound.  To use the new limit,
7call sys.setrecursionlimit().
8
9This module implements several ways to create infinite recursion in
10Python.  Different implementations end up pushing different numbers of
11C stack frames, depending on how many calls through Python's abstract
12C API occur.
13
14After each round of tests, it prints a message:
15"Limit of NNNN is fine".
16
17The highest printed value of "NNNN" is therefore the highest potentially
18safe limit for your system (which depends on the OS, architecture, but also
19the compilation flags). Please note that it is practically impossible to
20test all possible recursion paths in the interpreter, so the results of
21this test should not be trusted blindly -- although they give a good hint
22of which values are reasonable.
23
24NOTE: When the C stack space allocated by your system is exceeded due
25to excessive recursion, exact behaviour depends on the platform, although
26the interpreter will always fail in a likely brutal way: either a
27segmentation fault, a MemoryError, or just a silent abort.
28
29NB: A program that does not use __methods__ can set a higher limit.
30"""
31
32import sys
33import itertools
34
35class RecursiveBlowup1:
36    def __init__(self):
37        self.__init__()
38
39def test_init():
40    return RecursiveBlowup1()
41
42class RecursiveBlowup2:
43    def __repr__(self):
44        return repr(self)
45
46def test_repr():
47    return repr(RecursiveBlowup2())
48
49class RecursiveBlowup4:
50    def __add__(self, x):
51        return x + self
52
53def test_add():
54    return RecursiveBlowup4() + RecursiveBlowup4()
55
56class RecursiveBlowup5:
57    def __getattr__(self, attr):
58        return getattr(self, attr)
59
60def test_getattr():
61    return RecursiveBlowup5().attr
62
63class RecursiveBlowup6:
64    def __getitem__(self, item):
65        return self[item - 2] + self[item - 1]
66
67def test_getitem():
68    return RecursiveBlowup6()[5]
69
70def test_recurse():
71    return test_recurse()
72
73def test_cpickle(_cache={}):
74    import io
75    try:
76        import _pickle
77    except ImportError:
78        print("cannot import _pickle, skipped!")
79        return
80    k, l = None, None
81    for n in itertools.count():
82        try:
83            l = _cache[n]
84            continue  # Already tried and it works, let's save some time
85        except KeyError:
86            for i in range(100):
87                l = [k, l]
88                k = {i: l}
89        _pickle.Pickler(io.BytesIO(), protocol=-1).dump(l)
90        _cache[n] = l
91
92def test_compiler_recursion():
93    # The compiler uses a scaling factor to support additional levels
94    # of recursion. This is a sanity check of that scaling to ensure
95    # it still raises RecursionError even at higher recursion limits
96    compile("()" * (10 * sys.getrecursionlimit()), "<single>", "single")
97
98def check_limit(n, test_func_name):
99    sys.setrecursionlimit(n)
100    if test_func_name.startswith("test_"):
101        print(test_func_name[5:])
102    else:
103        print(test_func_name)
104    test_func = globals()[test_func_name]
105    try:
106        test_func()
107    # AttributeError can be raised because of the way e.g. PyDict_GetItem()
108    # silences all exceptions and returns NULL, which is usually interpreted
109    # as "missing attribute".
110    except (RecursionError, AttributeError):
111        pass
112    else:
113        print("Yikes!")
114
115if __name__ == '__main__':
116
117    limit = 1000
118    while 1:
119        check_limit(limit, "test_recurse")
120        check_limit(limit, "test_add")
121        check_limit(limit, "test_repr")
122        check_limit(limit, "test_init")
123        check_limit(limit, "test_getattr")
124        check_limit(limit, "test_getitem")
125        check_limit(limit, "test_cpickle")
126        check_limit(limit, "test_compiler_recursion")
127        print("Limit of %d is fine" % limit)
128        limit = limit + 100
129