«

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 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.setrecursionlimit`?

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

--
HTH,
Rob

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

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

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

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_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()]

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

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

Have you considered checking your input for valid values?

Cheers,
John

robert <no-> writes:

> 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

Ben Finney wrote:
> robert <no-> writes:
>
>> 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

On 2006-12-01, robert <no-> wrote:
> Ben Finney wrote:
>> robert <no-> writes:
>>
>>> 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