Is there a tool in either Linux/Windows that would enable us to determine if a logic of the particular function in C is same as that of a particular function in C++ ?
views:
148answers:
5
+11
A:
In general, the equivalence of Turing machines is undecidable, so no.
FredOverflow
2010-06-26 15:59:33
That the problem is impossible in general does not prove that a useful tool (i.e. one that can get the easy cases) is not possible...
dmckee
2010-06-26 20:48:07
In fact, dmckee points out that matching ASTs for code gives an approximation of the answer, at least for copy-and-pasted code.
Ira Baxter
2010-06-28 15:52:11
+1
A:
If you are just talking of control structures, if/else, blocks of code, swtich/case, while, for, etc AND if you are willing to be able to accept "gettign a good feel for it", rather than 100% accuray, then a picture may be work a thousand words, and you might look at a code to flowchart program.
I won't recommend any, as I don't know them well enough (but have always wanted to try them out, espcially if round trip. It might not be easy to find something free. In general, you will see something like this ... 
is that what you have is mind? Do it for both C and C++ versions, and you can get a rough feel for similarity of logic.
Perhaps you can tell us a little more what exactly you are looking for? Help us to help you? Thanks.
LeonixSolutions
2010-06-26 16:19:14
A more sophisticated approach than "looking at flowcharts" is constructing Program Dependence Graphs (with/without static single assignment) and attempting a Graph Match. This paper used this idea to find code clones: Jens Krinke: Identifying Similar Code with Program Dependence Graphs. WCRE 2001: 301-309 The good news is that it works to some degree; the bad news is that it doesn't scale to really big systems. More scalable approaches have used matching of lexical tokens or AST matching.
Ira Baxter
2010-06-29 01:06:44
+1
A:
You can imagine a tool that compares the structure of ASTs after the compiler has done the initial conversion to abstract representation or after one of more optimization passes.
This would probably
- Miss some real matches (i.e. generate false negatives)
- Identify some bogus matches (i.e. generate false positives)
With tuning you could force the second case to be more common. I have no feel for how good it would have to be to be useful as a front end to a vgrep process.
But it get worse, because you've asking for a cross-language implementation, and that will make it harder. Still, gcc uses the same abstract representation for everything, so it is not beyond imagining.
That said, I know of no such tool.
dmckee
2010-06-26 20:38:40
There is a tool that does *exactly* this. It is called the CloneDR (http://www.semanticdesigns.com/Products/Clone) This compares the ASTs of source code to verify "similarity". CloneDR handles many langauges including C and C++ You pretty much don't need a cross-langauge implementation; C is generally close enough to be swallowed by a C++ parser, and its easier to make slight changes to the C code rather than invent such a cross language tool.
Ira Baxter
2010-06-28 15:50:42
@Ira: Thanks...and wow! The website makes some pretty strong claims. Does anyone know how well it works in real life?
dmckee
2010-06-28 15:58:43
@dmckee: I'm the author. I think it works pretty well. You'll have to form you own opinion. You can download a evaluation version to do so.
Ira Baxter
2010-06-28 19:30:44
@dmckee: You appear to be a physicist. I can put you in contact with FermiLab people that have looked at CloneDR for application on their C++ modelling codes. My email address can be found at my SO icon.
Ira Baxter
2010-06-28 19:33:50