Detecting infinite recursion

Question

I'm creating a macro for Trac, and one of the things it does is to render a bit of wiki text, that can in turn use the same macro.

This can give rise to an infinite recursion if the inner macro is invoked with the same arguments (i.e., renders the same bit of wiki text). I thought of trying to stop the user from shooting his own foot like this by inspecting the call stack and breaking the recursion if the function that expands the macro was already invoked with exactly the same set of arguments.

I've been looking at the inspect module, which definitely seems like the way to go, but still couldn't figure out how to discover the argument values of the previous function on the stack. How can I do this?

score 7 · Accepted Answer · edited Apr 12 '13 at 11:35

Catching the recursion exception is the better approach, but you could also add a decorator on the functions you wanted to 'protect':

from functools import wraps
from threading import local

def recursion_detector(func):
    func._thread_locals = local()

    @wraps(func)
    def wrapper(*args, **kwargs):
        params = tuple(args) + tuple(kwargs.items())

        if not hasattr(func._thread_locals, 'seen'):
            func._thread_locals.seen = set()
        if params in func._thread_locals.seen:
            raise RuntimeError('Already called this function with the same arguments')

        func._thread_locals.seen.add(params)
        try:
            res = func(*args, **kwargs)
        finally:
            func._thread_locals.seen.remove(params)

        return res

    return wrapper

then apply that decorator to the macro render function.

A simple demo:

>>> @recursion_detector
... def foo(bar):
...     return foo(not bar)
... 
>>> foo(True)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 10, in wrapper
  File "<stdin>", line 3, in foo
  File "<stdin>", line 10, in wrapper
  File "<stdin>", line 3, in foo
  File "<stdin>", line 7, in wrapper
RuntimeError: Already called this function with the same arguments
>>> foo(False)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 10, in wrapper
  File "<stdin>", line 3, in foo
  File "<stdin>", line 10, in wrapper
  File "<stdin>", line 3, in foo
  File "<stdin>", line 7, in wrapper
RuntimeError: Already called this function with the same arguments

Great, thanks! For future readers, [this post](http://stackoverflow.com/a/1894371/684253) provides a nice explanation and example of how ``threading.local`` works. — Filipe Correia, Apr 12 '13 at 10:13

score 3 · Answer 2 · answered Apr 11 '13 at 17:57

3

It's easier to just catch the recursion error when it happens, than trying to catch it before it happens, in runtime.

If that's not an option, analyzing the template before rendering could be a way forward as well.

answered Apr 11 '13 at 17:57

Lennart Regebro

167,292
41
224
251

3

Provided the code doesn't take too long to get a stack overflow. If it does, this may be impractical. (+1) – NPE Apr 11 '13 at 17:58
@NPE: Sure, if it is a very slow process. But rendering a template shouldn't be. – Lennart Regebro Apr 11 '13 at 17:58
That was my first try, but for some reason that I still can't understand, no exception is being raised when this happens. When I provoke this when running trac through {{tracd}}, the process just... stops. No debug message. No exception. Nothing. – Filipe Correia Apr 11 '13 at 18:00
@LennartRegebro surely... although I was able to determine it was failing on the 97th iteration, and used a debugger to step through the code to see where it was failing. Strangely, this is when a function returns (I was expecting it was on a call), and it doesn't stop in a breakpoint I have in the closest ``try .. except`` block. – Filipe Correia Apr 11 '13 at 18:08

score 0 · Answer 3 · answered Apr 11 '13 at 17:59

0

Equally simple would be to pass dictionary to keep track of used arguments and at the beginning check if argument has already been tried.

answered Apr 11 '13 at 17:59

Adrian

1,166
6
15

1

It's not that simple, because I'm using trac's API. To add the macro, I need to override the method ``expand_macro(self, formatter, name, content)``, that is provided by ``IWikiMacroProvider``. It's not this method that calls itself directly, but somewhere inside a call I do to ``Chrome(self.env).render_template(...)``. – Filipe Correia Apr 11 '13 at 18:04
I guess @MartijnPieters's answers is close to what you were suggesting. – Filipe Correia Apr 11 '13 at 18:18

Detecting infinite recursion

3 Answers3

Linked