In article <68**************************@posting.google.com >,
or******@yahoo.se (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
mi************@microfocus.com
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)