Using RTTI to determine inheritance graph in C++?

Question

What, if any, c++ constructs are there for listing the ancestors of a class at runtime?

Basically, I have a class which stores a pointer to any object, including possibly a primitive type (somewhat like boost::any, which I don't want to use because I need to retain ownership of my objects). Internally, this pointer is a void*, but the goal of this class is to wrap the void* with runtime type-safety. The assignment operator is templated, so at assignment time I take the typeid() of the incoming pointer and store it. Then when I cast back later, I can check the typeid() of the cast type against the stored type_info. If it mismatches, the cast will throw an exception.

But there's a problem: It seems I lose polymorphism. Let's say B is a base of D. If I store a pointer to D in my class, then the stored type_info will also be of D. Then later on, I might want to retrieve a B pointer. If I use my class's method to cast to B*, then typeid(B) == typeid(D) fails, and the cast raises an exception, even though D->B conversion is safe. Dynamic_cast<>() doesn't apply here, since I'm operating on a void* and not an ancestor of B or D.

What I would like to be able to do is check is_ancestor(typeid(B), typeid(D)). Is this possible? (And isn't this what dynamic_cast<> is doing behind the scenes?)

If not, then I am thinking of taking a second approach anyway: implement a a class TypeInfo, whose derived classes are templated singletons. I can then store whatever information I like in these classes, and then keep pointers to them in my AnyPointer class. This would allow me to generate/store the ancestor information at compile time in a more accessible way. So failing option #1 (a built-in way of listing ancestors given only information available at runtime), is there a construct/procedure I can use which will allow the ancestor information to be generated and stored automatically at compile-time, preferably without having to explicitly input that "class A derives from B and C; C derives from D" etc.? Once I have this, is there a safe way to actually perform that cast?

Walrus

I don't know the answer but boost::any seems to manage it. Why not take a look at their code? – Groot

John: As far as I can tell, boost::any actually suffers from the same problem. It also uses typeid(A) == typeid(B); in fact, that's where I got the idea! – Walrus

Boost.Any uses a placeholder and a template<class ValueType> holder : placeholder with pure virtual functions to store the actual type. That's why there solution is able to handle polymorphism. – Kally

@pmr: Boost.Any does not seem to handle polymorphism. – Notus

@Matthieu: You are right. Took me a moment to understand what the OP is trying to do and I don't see any way to do it. – Kally

@pmr: Solely exploiting typeinfo et virtuality ? Neither do I. Encoding the base classes (somehow) in the derived class, I do, but it gets cumbersome. – Notus

@trbabb: I know this will seem weird, seeing as you just accepted the answer... but Cassio Neri's answer is just spot on and solves your issue. He does not use type_info, but he does handle polymorphism! You should probably be accepting his. – Notus

@MatthieuM. You are right; I did not read through this thread thoroughly enough after noticing that I'd never accepted an answer. – Walrus

Answer 1

I had a similar problem which I solved through exceptions! I wrote an article about that:

Part 1, Part 2 and code

Ok. Following Peter's advise the outline of the idea follows. It relies on the fact that if D derives from B and a pointer to D is thrown, then a catch clause expecting a pointer to B will be activated.

One can then write a class (in my article I've called it any_ptr) whose template constructor accepts a T* and stores a copy of it as a void*. The class implements a mechanism that statically cast the void* to its original type T* and throws the result. A catch clause expecting U* where U = T or U is a base of T will be activated and this strategy is the key to implementing a test as in the original question.

EDIT: (by Matthieu M. for answers are best self-contained, please refer to Dr Dobbs for the full answer)

class any_ptr {

    void* ptr_;
    void (*thr_)(void*);

    template <typename T>
    static void thrower(void* ptr) { throw static_cast<T*>(ptr); }

public:

    template <typename T>
    any_ptr(T* ptr) : ptr_(ptr), thr_(&thrower<T>) {}

    template <typename U>
    U* cast() const {
        try { thr_(ptr_); }
        catch (U* ptr) { return ptr; }
        catch (...) {}
        return 0;
    }
};

Jeunesse

Wow, I wish I had seen this answer sooner. I don't know whether to label this as a stroke of genius or a feat of madness; I guess it's both. I much prefer not involving shared_ptr here, and instead making any_ptr behave like unique_ptr provided the OP uses C++11... but the core mechanism remains striking. – Notus

@Matthieu M.: Thanks for improving my post. I agree that sometimes unique_ptr is preferable but at the time I wrote the article unique_ptr was neither standardized nor broadly available. The implementation in my code base uses a traits class that allows users to customize the inner smart pointer. – Jeunesse

Answer 2

The information is (often) there within the implementation. There's no standard C++ way to access it though, it's not exposed. If you're willing to tie yourself to specific implementations or sets of implementations you can play a dirty game to find the information still.

An example for gcc, using the Itanium ABI is:

#include <cassert>
#include <typeinfo>
#include <cxxabi.h>
#include <iostream>

bool is_ancestor(const std::type_info& a, const std::type_info& b);

namespace {
  bool walk_tree(const __cxxabiv1::__si_class_type_info *si, const std::type_info& a) {
    return si->__base_type == &a ? true : is_ancestor(a, *si->__base_type);
  }

  bool walk_tree(const __cxxabiv1::__vmi_class_type_info *mi, const std::type_info& a) {
    for (unsigned int i = 0; i < mi->__base_count; ++i) {
      if (is_ancestor(a, *mi->__base_info[i].__base_type))
        return true;
    }
    return false;
  }
}

bool is_ancestor(const std::type_info& a, const std::type_info& b) {
  if (a==b)
    return true;
  const __cxxabiv1::__si_class_type_info *si = dynamic_cast<const __cxxabiv1::__si_class_type_info*>(&b);
  if (si)
    return walk_tree(si, a);
  const __cxxabiv1::__vmi_class_type_info *mi = dynamic_cast<const __cxxabiv1::__vmi_class_type_info*>(&b);
  if (mi)
    return walk_tree(mi, a);
  return false;
}

struct foo {};

struct bar : foo {};

struct baz {};

struct crazy : virtual foo, virtual bar, virtual baz {};

int main() {
  std::cout << is_ancestor(typeid(foo), typeid(bar)) << "\n";
  std::cout << is_ancestor(typeid(foo), typeid(baz)) << "\n";
  std::cout << is_ancestor(typeid(foo), typeid(int)) << "\n";
  std::cout << is_ancestor(typeid(foo), typeid(crazy)) << "\n";
}

Where I cast the type_info to the real type that's used internally and then recursively used that to walk the inheritance tree.

I wouldn't recommend doing this in real code, but as an exercise in implementation details it's not impossible.

Tenatenable

I believe your solution is fine, and probably more efficient than Cassio Neri's one. One could use your approach wherever available, and Cassio Neri's one as a generic (and quite clever!) fallback. Thanks to both of you for your contribution! – Technician

Answer 3

First, what you are asking for cannot be implemented just on top of type_info.

In C++, for a cast to occur from one object to another, you need more than blindly assuming a type can be used as another, you also need to adjust the pointer, because of multi-inheritance (compile-time offset) and virtual inheritance (runtime offset).

The only way to safely cast a value from a type into another, is to use static_cast (works for single or multi-inheritance) and dynamic_cast (also works for virtual inheritance and actually checks the runtime values).

Unfortunately, this is actually incompatible with type erasure (the old template-virtual incompatibility).

If you limit yourself to non-virtual inheritance, I think it should be possible to achieve this by storing the offsets of conversions to various bases in some Configuration data (the singletons you are talking about).

For virtual inheritance, I can only think of a map of pairs of type_info to a void* (*caster)(void*).

And all this requires enumerating the possible casts manually :(

Notus

Answer 4

It is not possible using std::type_info since it does not provide a way to query inheritance information or to convert a std::type_info object to its corresponding type so that you could do the cast.

If you do have a list of all possible types you need to store in your any objects use boost::variant and its visitor.

Forster

Answer 5

While I can't think of any way to implement option #1, option #2 should be feasible if you can generate a compile-time list of the classes you would like to use. Filter this type list with boost::MPL and the is_base_of metafunction to get a list of valid-cast typeids, which can be compared to the saved typeid.

Danforth