Static C++ code analysis tool: finding the diamonds in a big source code

Question

(Related SO question.)

Consider there is a very large class hierarchy, from tens or even hunderds of classes. The inheritance diagram is also very complex (doxygen can't render it without half-page size arrows :-) ). And, here comes the dreaded diamond problem. I am looking for a way to find all of the diamonds.

Around so:

Here the red penciled inheritance arrows need to be virtual. In such a simple structure it is easy to find all of them, but not in a much larger.

Finding all of the diamonds seems an easily automatizable graph walking problem. I would be surprised if a solution for the task already wouldn't exist.

The question is a tool already existing for a task?

Answer 1

You have two problems to solve:

• Getting the inheritance graph across a large C++ application
• Discovering the diamonds

The first part is complex because parsing C++ to obtain this inheritance information accurately is hard (C++ itself is insanely hard to parse, then you have the complications of preprocessor conditionals, include files, macros and templates). You need a full C++ front end to do this, and an organized attack to collect the inheritance information.

Our DMS Software Reengineering Toolkit with its C++ front end can be used to extract this kind of information. You can configure DMS to parse all of your compilation units and perform name/type resolution; this handles all the preprocessing/template resolution and produces, for each compilation unit, both ASTs for the program (which you don't need for this task) as well as accessible symbol tables, which contain declarations of classes and and desired A-inherits-from-B information. A simple symbol-table scan can produce the inheritance information for each compilation unit.

You then need to assemble that information to get an inheritance graph for your system. It should be obvious that you literally want to construct the inherits-graph.

With that graph, diamond discovery is basically easy:

1. For each node, build an empty hash-set of children that stores path-to-child
2. Enumerate and record all paths from each node to its children using a bottom-up enumeration of inheritance paths (easily implemented using a depth first search)
3. Anytime you encounter a child twice from a node, the hash-set will contain the paths to that child; two paths --> diamond
4. Mark that node as having a diamond to avoid re-enumerating all sub-paths

You can implement that diamond-finder in using software other than DMS, but you could implement using DMS's internal procedural programming language, too, which would avoid the step that exports the inheritance information.

Summary:

• DMS with C++ front end parses code accurately
• Raw inheritance information per compilation unit can be collected
• Sets of such data provide inheritance graph
• Algorithm to find diamonds is pretty easy to code.

Since DMS is my company's product, don't take this as a recommendation, merely a note that DMS exists and can do OP's task.

Answer 2

You can also try CppDepend Which provides many features concerning the dependencies and a code query language to create easily your dependencies rules.