How to deduce, at compile time, the root of an inheritance tree common to two types if one exists?

Question

I have a problem where I need to discover the common ancestor of two types (with one or zero base classes) if it exists. Is it possible to build a type trait to solve this problem? In code:

template<typename T1, typename T2>
  struct closest_common_ancestor
{
  typedef XXX type;  // what goes here?
};

Given the following types:

struct root {};
struct child1 : root {};
struct child2 : root {};
struct child3 : child2 {};
struct unrelated {};

closest_common_ancestor would result in the following types:

closest_common_ancestor<root, child1>::type == root
closest_common_ancestor<child1, child2>::type == root
closest_common_ancestor<child3, child1>::type == root
closest_common_ancestor<child3, child2>::type == child2
closest_common_ancestor<unrelated, child1>::type == error

I believe I can solve this problem if I can inspect whether a type has zero or one base class, and if so, the name of that type. Is this possible?

Answer 1

As K-ballo mentionned it's unfortunately impossible to obtain the list of bases a class has (too bad...).

If you manually annotate your classes (say, define a simple std::tuple<> listing the bases), then you can use this information. The simpler, of course, would be to use a trait:

template <typename> struct list_bases { typedef std::tuple<> type; };

Then you can specialize this trait for your types:

template <> struct list_bases<child1> { typedef std::tuple<root> type; };

And starting from there, you can begin experiment with finding an ancestor... however it might not be immediate. Apart from the implementation details (getting the bases recursively, implementing the "distance" selection), I expect an issue with "weird" cases.

The distance selection can, in usual (linear) inheritance hierarchy be solved by using a combination of is_base_of and is_same, however consider the following hierarchy:

struct root1 {}; struct root2 {};

struct child1: root1 {}; struct child2: root2 {};

struct child12: root1, child2 {}; struct child21: root2, child1 {};

Now, child12 and child21 have two common ancestors: root1 and root2... which is the closest ?

They are equivalent. Consider that I add:

struct root3 {}; struct child31: root3, child1 {};

Then root1 is a common ancestor to child12, child21 and child31.

However if I skirted on the definition of closest_common_ancestor and arbitrarily defined that closest_common_ancesotr<child12, child21> is root2, then I could not find any common ancestor with child31.

My proposal is therefore to list all closest ancestors, and use tuple to implement set operations.