Detecting recursion loops

Discussion in 'Python' started by robert, Nov 29, 2006.

  1. robert

    robert Guest

    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, Nov 29, 2006
    #1
    1. Advertising

  2. robert

    Rob Wolfe Guest

    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
     
    Rob Wolfe, Nov 29, 2006
    #2
    1. Advertising

  3. robert

    Carl Banks Guest

    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
     
    Carl Banks, Nov 29, 2006
    #3
  4. robert

    Bytter Guest

    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
     
    Bytter, Nov 29, 2006
    #4
  5. robert

    robert Guest

    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.
     
    robert, Nov 29, 2006
    #5
  6. robert

    robert Guest

    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, Nov 29, 2006
    #6
  7. robert

    John Machin Guest

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


    Have you considered checking your input for valid values?

    Cheers,
    John
     
    John Machin, Nov 29, 2006
    #7
  8. robert

    Ben Finney Guest

    robert <> 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, Nov 29, 2006
    #8
  9. robert

    robert Guest

    Ben Finney wrote:
    > robert <> 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
     
    robert, Dec 1, 2006
    #9
  10. robert

    Neil Cerutti Guest

    On 2006-12-01, robert <> wrote:
    > Ben Finney wrote:
    >> robert <> 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
     
    Neil Cerutti, Dec 1, 2006
    #10
  11. robert

    fumanchu Guest

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


    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


    [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
     
    fumanchu, Dec 1, 2006
    #11
  12. robert

    robert Guest

    Neil Cerutti wrote:
    > On 2006-12-01, robert <> wrote:
    >> Ben Finney wrote:
    >>> robert <> 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?


    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
     
    robert, Dec 1, 2006
    #12
  13. robert

    Fuzzyman Guest

    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
     
    Fuzzyman, Dec 1, 2006
    #13
  14. robert

    Kay Schluehr Guest

    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.
     
    Kay Schluehr, Dec 2, 2006
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. eismaus4

    to many FOR loops?

    eismaus4, Apr 27, 2004, in forum: VHDL
    Replies:
    1
    Views:
    687
  2. Joerg Lensing

    Debugging: Detecting infinite loops

    Joerg Lensing, Dec 14, 2003, in forum: Java
    Replies:
    2
    Views:
    648
  3. ishamid

    simple loops and recursion

    ishamid, Nov 27, 2006, in forum: Ruby
    Replies:
    9
    Views:
    117
    Doug Kramer
    Nov 27, 2006
  4. Me
    Replies:
    2
    Views:
    246
  5. Replies:
    8
    Views:
    745
    John Reye
    Apr 26, 2012
Loading...

Share This Page