Saturday, 3 October 2015

How to get a type_index without RTTI

Have you ever wondered why the typeid operator only works when run-time type information (RTTI) is enabled?  Sure, RTTI is necessary when deducing the concrete types of polymorphic objects at runtime, but why should typeid(T) require RTTI when T is known at compile time?  Surely something as simple as converting T to unique integer ID should be possible?  Here I will show how to create your own CTTI (compile time type information) type_id function.
Note: The Boost libraries project offers a more comprehensive solution in Boost.TypeIndex, which not only provides an RTTI-less type_index, but also type names in string form (I assume they are using some compiler-specific Voodoo magic).  If you are unable or unwilling to use Boost, or are just interested for academic reasons, then continue reading!

Roll your own type_index


We want to be able to do something like this.

auto id = type_id<int>();

Our task is to produce a distinct value for each and every type.  One solution is to use a static local variable within a function template.

template<typename T>
int* type_id()
{
    static int id;
    return &id;
};

Thanks to the One Definition Rule, the linker must ensure that there is a single definition of each function template instance across all translation units, and since memory addresses must be unique, we now have a unique identifier for every possible type! This is the same principle that is used to implement the singleton pattern (though I wouldn't recommend it).

However, ideally we would like the same ID for regular, const, volatile and reference versions of a type (this is what typeid does).  We can use the relevant type traits templates to strip these off.

template<typename T>
int* type_id()
{
    using t = std::remove_cv_t<std::remove_reference_t<T>>;
    return type_id_with_cvr<t>();
};

template<typename T>
int* type_id_with_cvr()
{
    static int id;
    return &id;
};

But we aren't quite finished. Using the int* directly as a type index is less than ideal, the main problem being that arbitrary pointers cannot be compared using operator< and company. We can address this by creating a nice type-safe type_index wrapper class. And while we're at it, let's also add a specialization for std::hash so that we can use type_index objects as keys in unordered associative containers.

#include <functional>
#include <type_traits>

class type_index
{
private:
    int* id;
    type_index(int* id) : id(id) {}

public:
    bool operator==(type_index const& t) const
    { return id == t.id; }
    bool operator!=(type_index const& t) const
    { return id != t.id; }
    bool operator<(type_index const& t) const
    { return std::less<int*>()(id, t.id); }
    bool operator<=(type_index const& t) const
    { return !(t > *this); }
    bool operator>(type_index const& t) const
    { return t < *this; }
    bool operator>=(type_index const& t) const
    { return !(*this < t); }

    std::size_t hash_code() const { return std::hash<int*>()(id); }

    template<typename T>
    friend type_index type_id()
    {
        using t = std::remove_cv_t<std::remove_reference_t<T>>;
        return type_id_with_cvr<t>();
    };

    template<typename T>
    friend type_index type_id_with_cvr()
    {
        static int id;
        return &id;
    };
};

namespace std
{
    template<>
    struct hash<type_index>
    {
        std::size_t operator()(type_index const& t) const
        {
            return t.hash_code();
        }
    };
}

Now we're ready to roll! Keep in mind that the type_index for a given type will only be unique within the current program. Sharing type_index objects over shared library boundaries is not possible.
Note: If you do not have C++14, you will have to implement your own type traits helper types (remove_cv_t and remove_reference_t).  If you do not have C++11, you will have to implement your own type traits constructs from scratch (or find an existing implementation).