detect recursive C code

Discussion in 'C Programming' started by Einar ?rn, Oct 28, 2004.

  1. Einar ?rn

    Einar ?rn Guest

    Hi all,

    is there a good way to detect recursive C code in large systems? A
    method or a free tool?

    Best regards,
    E
    Einar ?rn, Oct 28, 2004
    #1
    1. Advertising

  2. In article <>,
    Einar ?rn <> wrote:

    >is there a good way to detect recursive C code in large systems? A
    >method or a free tool?


    I don't know of anything specifically for that purpose, but many
    profilers indicate recursive cycles in their output. This will only
    detect recursive functions that are actually called of course.

    -- Richard
    Richard Tobin, Oct 28, 2004
    #2
    1. Advertising

  3. Einar ?rn

    Mark Piffer Guest

    On 28 Oct 2004 07:22:53 -0700, (Einar ?rn) wrote:

    >Hi all,
    >
    >is there a good way to detect recursive C code in large systems? A
    >method or a free tool?
    >
    >Best regards,
    >E


    I don't know if it meets the exact purpose, but I think GLOBAL is a
    suitable tool to reverse engineer C source code and caller/callee
    dependencies (http://www.gnu.org/software/global). You can of course
    try doxygen (http://www.doxygen.org), it can create call-trees and
    therefore should find recursions (although I never tried that)

    Mark
    Mark Piffer, Oct 28, 2004
    #3
  4. In article <>, (Einar ?rn) writes:
    >
    > is there a good way to detect recursive C code in large systems? A
    > method or a free tool?


    There are a number of static-analysis tools that generate call graphs
    from C source. Loops in the call graph indicate recursion. They're
    not guaranteed, though:

    - If the recursion only occurs in dead code which is never actually
    executed, you may have a false positive (depending on how you define
    "recursive C code" for your purposes).

    - It's hard for analyzers to detect recursion through function
    pointers, since they'd have to check every value such a pointer can
    be set to by the program; so if the code uses function pointers you
    could get false negatives.

    Dynamic (runtime) analysis obviously suffers from flow coverage
    issues - you can't rule out recursion until you've tested all
    possible flow paths through the code.

    In short, it's very difficult (maybe impossible, though I don't
    offhand see a proof of that; this doesn't look to me like it's
    isomorphic to the halting problem) to algorithmically determine that
    a given body of C code is not recursive.

    A program could detect recursion at runtime (given sufficient
    resources) by maintaining its own stack of tokens identifying which
    functions have been called in the current path; each function on
    entry checks the stack to see if it's already there, and then adds
    itself to the top. The repetitive code can be hidden in macros, but
    this is still not particularly fun to implement. And, of course, you
    have to decide what the program does if it detects recursion.

    --
    Michael Wojcik

    When most of what you do is a bit of a fraud, the word "profession"
    starts to look like the Berlin Wall. -- Tawada Yoko (t. M. Mitsutani)
    Michael Wojcik, Oct 29, 2004
    #4
  5. (Michael Wojcik) wrote in message news:<>...
    > (...) this doesn't look to me like it's
    > isomorphic to the halting problem) to algorithmically determine that
    > a given body of C code is not recursive.



    Actually, it is. Informally, you need to determine that the program
    can reach another particular point in the code (which is trivially
    equivalent to the halting problem), given a particular starting point
    before reaching another point (eg. the next line), which is an
    additional complication.


    > A program could detect recursion at runtime (given sufficient
    > resources) by maintaining its own stack of tokens identifying which
    > functions have been called in the current path; each function on
    > entry checks the stack to see if it's already there, and then adds
    > itself to the top. The repetitive code can be hidden in macros, but
    > this is still not particularly fun to implement. And, of course, you
    > have to decide what the program does if it detects recursion.



    While quite implementation dependant (and using very undefined
    behavior), if you can, on your implementation, walk the stack of
    activation records, it's usually pretty easy to write a routine that
    saves the callers address in an auto, and then looks through all the
    stack frames looking for a duplicate. All you need in each routine is
    something like "{void *RecurseTest; CheckRecursion(&RecurseTest,
    __LINE__);}"
    Robert Wessel, Oct 30, 2004
    #5
  6. Einar ?rn

    Einar ?rn Guest

    Einar ?rn, Nov 4, 2004
    #6
  7. On 29 Oct 2004 15:48:59 GMT, (Michael Wojcik)
    wrote:
    <snip>
    > A program could detect recursion at runtime (given sufficient
    > resources) by maintaining its own stack of tokens identifying which
    > functions have been called in the current path; each function on
    > entry checks the stack to see if it's already there, and then adds
    > itself to the top. The repetitive code can be hidden in macros, but
    > this is still not particularly fun to implement. And, of course, you
    > have to decide what the program does if it detects recursion.


    Or a static flag, (as little as) one bit, for each function.

    With somewhat simpler code; but still worth hiding, and also
    automating which helps prevent cut&paste or other editing errors.


    - David.Thompson1 at worldnet.att.net
    Dave Thompson, Nov 10, 2004
    #7
    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. Einar ?rn

    detect recursive C code

    Einar ?rn, Oct 28, 2004, in forum: C Programming
    Replies:
    0
    Views:
    316
    Einar ?rn
    Oct 28, 2004
  2. n00m
    Replies:
    12
    Views:
    1,113
  3. Recursive Code

    , Jun 18, 2008, in forum: C++
    Replies:
    27
    Views:
    891
  4. vamsi
    Replies:
    21
    Views:
    2,073
    Keith Thompson
    Mar 9, 2009
  5. capitan
    Replies:
    3
    Views:
    1,999
    capitan
    Sep 25, 2011
Loading...

Share This Page