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]

Re: Detecting recursion loops


robert wrote:

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.setrecursi onlimit`?

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

--
HTH,
Rob

[Carl Banks]

Re: Detecting recursion loops

robert wrote:

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_r ecursion()
....
_call_count[parse_something] -= 1

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

The check_invalid_r ecursion() 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]

Re: Detecting recursion loops

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 :)

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

[robert]

Re: Detecting recursion loops

Rob Wolfe wrote:

robert wrote:

>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.setrecursi onlimit`?
>
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]

Re: Detecting recursion loops

Carl Banks wrote:

robert wrote:

>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.

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_r ecursion()
....
_call_count[parse_something] -= 1
>
(You could define a decorator to do this more easily; that's left as an
excercise.)
>
The check_invalid_r ecursion() 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_iden t()]

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

[John Machin]

Re: Detecting recursion loops


robert wrote:

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

Have you considered checking your input for valid values?

Cheers,
John

[Ben Finney]

Re: Detecting recursion loops

robert <no-spam@no-spam-no-spam.invalidwri tes:

Carl Banks wrote:

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.

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.

--
\ "People's Front To Reunite Gondwanaland: Stop the Laurasian |
`\ Separatist Movement!" -- wiredog, http://kuro5hin.org/ |
_o__) |
Ben Finney

[robert]

Re: Detecting recursion loops

Ben Finney wrote:

robert <no-spam@no-spam-no-spam.invalidwri tes:
>

>Carl Banks wrote:

>>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.

>
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]

Re: Detecting recursion loops

On 2006-12-01, robert <no-spam@no-spam-no-spam.invalidwro te:

Ben Finney wrote:

>robert <no-spam@no-spam-no-spam.invalidwri tes:
>>

>>Carl Banks wrote:
>>>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.

>>
>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.

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

--
Neil Cerutti
Customers who consider our waitresses uncivil ought to see the manager --sign
at New York restaurant

[fumanchu]

Re: Detecting recursion loops

robert wrote:

Ben Finney wrote:

robert <no-spam@no-spam-no-spam.invalidwri tes:

Carl Banks wrote:
>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.

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.

You might find some engineering inspiration in CherryPy's
InternalRedirec t 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
fumanchu@amor.o rg

[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]

Re: Detecting recursion loops

Neil Cerutti wrote:

On 2006-12-01, robert <no-spam@no-spam-no-spam.invalidwro te:

>Ben Finney wrote:

>>robert <no-spam@no-spam-no-spam.invalidwri tes:
>>>
>>>Carl Banks wrote:
>>>>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.
>>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.

>
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]

Re: Detecting recursion loops


robert wrote:

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

Robert

[Kay Schluehr]

Re: Detecting recursion loops

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.