Detecting recursion loops

[robert]

My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs?

Robert

 

[Rob Wolfe]

My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs?

What about `sys.setrecursionlimit`?

http://docs.python.org/lib/module-sys.html

 

[Carl Banks]

My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs?

1. You could catch RuntimeError at the top, check whether it's
recursion depth exception, and raise a user exception if it is.

2. Consider whether you're unwittingly trying to cover up a bug. ISTM
no matter how problematic the input is, you should at least be able to
make progress on it. Are you getting this error because, say, you're
not incrementing a counter somewhere, and thus recalling a function
with the same arguments again?

3. Also consider whether you could rewrite the code to be
non-recursive. Usually when I process input recursively, the input is
allowed to be arbitrarily deeply nested. (In that case I think it
would be a mistake to arbitrarily limit depth.) But it sounds to me
like your input might be inherently non-nestable. If that's the case,
it might be possible to get rid of the recursion altogether, or at
least to put in error checking that detects when input is at an invalid
depth.

4. If those concerns don't apply, and you do need to detect recursion,
I'd suggest using a global dictionary to track function calls. If you
have a function parse_something that you want to track, you could
define a dict like this:

_call_count = { parse_something: 0 }

And change parse_something to adjust its own counter:

def parse_something():
_call_count[parse_something] += 1
check_invalid_recursion()
....
_call_count[parse_something] -= 1

(You could define a decorator to do this more easily; that's left as an
excercise.)

The check_invalid_recursion() function would inspect _call_count and
raise an exception based on any criteria you want.

5. In CPython, you could just inpect the stack frame and look for
duplicated function calls. See the documentation for sys._getframe.


Carl Banks

 

[Bytter]

Hi!

I hope you are not trying to find infinite loops and I simply
misunderstood your question. Because if you are, then forget it (Turing
anyone?)... Infinite loops are impossible to find (minus some few, very
specific situations).

Cf. http://en.wikipedia.org/wiki/Halting_problem

Cheers,

Hugo Ferreira

P.S. Hmmm... It seems I really read it wrong since you define that you
want to stop "(after N passes or some complex criteria)". Anyway I
leave the warning for future generations

 

[robert]

What about `sys.setrecursionlimit`?

http://docs.python.org/lib/module-sys.html

That is a low level barrier. I just want to limit a certain recursion call chain.

 

[robert]

1. You could catch RuntimeError at the top, check whether it's
recursion depth exception, and raise a user exception if it is.

thats what happens now anyway. need to limit this kind of recursion.

2. Consider whether you're unwittingly trying to cover up a bug. ISTM
no matter how problematic the input is, you should at least be able to
make progress on it. Are you getting this error because, say, you're
not incrementing a counter somewhere, and thus recalling a function
with the same arguments again?

the "bug" comes in from the I/O input. its about to stop it in non-simple recursion (through more functions calls)

3. Also consider whether you could rewrite the code to be
non-recursive. Usually when I process input recursively, the input is
allowed to be arbitrarily deeply nested. (In that case I think it
would be a mistake to arbitrarily limit depth.) But it sounds to me
like your input might be inherently non-nestable. If that's the case,
it might be possible to get rid of the recursion altogether, or at
least to put in error checking that detects when input is at an invalid
depth.

4. If those concerns don't apply, and you do need to detect recursion,
I'd suggest using a global dictionary to track function calls. If you
have a function parse_something that you want to track, you could
define a dict like this:

_call_count = { parse_something: 0 }

And change parse_something to adjust its own counter:

def parse_something():
_call_count[parse_something] += 1
check_invalid_recursion()
....
_call_count[parse_something] -= 1

(You could define a decorator to do this more easily; that's left as an
excercise.)

The check_invalid_recursion() function would inspect _call_count and
raise an exception based on any criteria you want.

thats possibly the right practical/fast possibility, I end so far with. As its threaded, a try-finally protected counter on a TLS _func_recccount[thread.get_ident()]

 

[John Machin]

the "bug" comes in from the I/O input.

Have you considered checking your input for valid values?

Cheers,
John

 

[Ben Finney]

the "bug" comes in from the I/O input.

If a program doesn't gracefully deal with bad input, that's a bug in
the program. You should be designing your input handler so that it
will do something helpful (even if that's to stop immediately with an
informative error message) in the event of bad input, rather than
allowing that bad data to send your program into an endless loop.

 

[robert]

If a program doesn't gracefully deal with bad input, that's a bug in
the program. You should be designing your input handler so that it
will do something helpful (even if that's to stop immediately with an
informative error message) in the event of bad input, rather than
allowing that bad data to send your program into an endless loop.

Yet that detection is what the asked alg should do. Example: When a HTML-(content)-relaying sends you around in a circle through a complex handler chain.

Robert

 

[Neil Cerutti]

Yet that detection is what the asked alg should do. Example:
When a HTML-(content)-relaying sends you around in a circle
through a complex handler chain.

Being in a cycle doesn't actually prove your program will never
halt for that particular input, does it?

 

[fumanchu]

Yet that detection is what the asked alg should do.
Example: When a HTML-(content)-relaying sends
you around in a circle through a complex handler chain.

You might find some engineering inspiration in CherryPy's
InternalRedirect handler [1], which simply raises an error if you visit
the same state twice. Another option is to periodically check a
timeout, which CherryPy does via an Engine.monitor thread [2] (that
runs Response.check_timeout [3]). Note that either approach requires
some alteration to the code being inspected.


Robert Brewer
System Architect
Amor Ministries
(e-mail address removed)

[1]
http://www.cherrypy.org/browser/tags/cherrypy-3.0.0RC1/cherrypy/_cpwsgi.py
[2]
http://www.cherrypy.org/browser/tags/cherrypy-3.0.0RC1/cherrypy/_cpengine.py#L240
[3]
http://www.cherrypy.org/browser/tags/cherrypy-3.0.0RC1/cherrypy/_cprequest.py#L565

 

[robert]

Being in a cycle doesn't actually prove your program will never
halt for that particular input, does it?

not. but its not about a theoretical prove. in practice with same state it goes through the same function here.. I had simply had situations where a server looped my client on to a Python (long through a couple of func-calls) recursion error .

thus, either I fiddle a recursion/counter parameter through my calls, or I do complex state detection as e.g. to copy that of cherrypy was recommend in other post.
Or: I simply throw a hammer at an n-th recursion, wereby I programm the counter locally as simple counter in a "global" thread-local-storage as I wrote.(also possible to use the same counter/limit in multiple functions!)
There were just 2 lines of code to add.


Robert

 

[Fuzzyman]

My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs?

Could you not store a set/list of nodes/points already visited and do
an early return if they recur ?

Fuzzyman
http://www.voidspace.org.uk/python/index.shtml

 

[Kay Schluehr]

Instead of threading a counter ( or an accumulator as for
tail-recursive functions ) you can monitor the behaviour of the mutual
recusive function call using an external stack and wrap the
contributing functions using a decorator s.t. pushing and popping to
and from the stack are pre- and postprocessing steps. Since the
external stack is under your control you can define fine grained limits
and actions.