2

(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:

The red penciled inheritance arrows need to be virtual. Finding the diamonds is easy for the first spot.

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?

3
  • My bet would be that it's possible with CppDepend, but I work in a new company and don't have a license any more. Furthermore I don't have a code base to test with. Certainly there's no built-in function to find diamonds (I hear about it the first time), but CppDepends supports CQLinq, a query language which made it possible to solve any task I had. Get the 14 days trial. Maybe ask [email protected] whether such a query would be possible. It's commercial @ 500 USD. Jul 8, 2016 at 22:12
  • How do you define a diamond in this context - a single class derived from multiple classes that in turn derive from a single class, at how many removes? Can it also inherit from other classes? Conceptually all class objects derive from a single class (i.e.: class or object). Jul 9, 2016 at 17:03
  • @SteveBarnes The class inheritance diagram is a DAG (directed acyclic graph). A diamond is a multiply connected minimal sub-graph of this DAG. For example, BS-BCA-BCS-T4-BT4-BI4 is a diamond. In C++, there is no "highest class" (conceptionally). An object is in c++ an instance of a class, they are unrelated to this problem, it is only about the classes.
    – peterh
    Jul 9, 2016 at 17:09

2 Answers 2

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.

3
  • I think you are a good man. The SO is doing this because if it wouldn't, they would be overflown by spam. Although I am an opensource-fan, it is not against the programmers trying to sell their really wonderful products, it is against the power misuses of the Big Companies. I hope the softwarerecs SE is lighter in this sense.
    – peterh
    Aug 14, 2016 at 23:29
  • Did you ever thought to make eclipse/msvs/anything plugins from your tools?
    – peterh
    Aug 14, 2016 at 23:31
  • @peterh: (Thank you for the vote of confidence). Regarding eclipse plugins: we do; presently they are available as specialized COBOL analysis plugins in IBM's bent version of eclipse called "RDz"; we did this for very complicated business reasons including so-called "eclipse compatibility" and weren't too pleased when IBM told us how RDz was different than mainstream eclipse. We expect someday to plug in the broader set of machinery to eclipse but it won't happen this year.
    – Ira Baxter
    Aug 15, 2016 at 0:30
1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.