Ciaran McCreesh’s Blag

Now with 17% more caffeine

Runtime Type Checking in C++ without RTTI

A technique I always seem to forget is how to map C++ types to an integer without relying upon RTTI. A variation on this is used in <locale> in standard library, for std::use_facet<>. But let’s take a much simpler, and highly contrived, example.

Let’s say we’ve got some values of different types, and we want to give those types to a library to store somewhere, and then we later want to get them back again. Crucially, the library itself doesn’t know anything about the types in question. So, for a very simple case:

#include <vector>
#include <iostream>
#include <string>

int main(int, char *[])
{
    std::vector<Something> things = { std::string("foo"), 123 };
    /* ... */
    std::cout << things[0].as<std::string>() << " " << things[1].as<int>() << std::endl;
}

Note the gratuitous use of c++0x initialiser lists, just because we can.

Those familiar with Boost might think that Something is like boost::any. However, boost::any uses RTTI, which is slow and completely unnecessary.

A first implementation of Something might look like this:

#include <memory>

class Something
{
    private:
        struct SomethingValueBase
        {
            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            return static_cast<const SomethingValue<T_> &>(*_value).value;
        }
};

This works, but has a major flaw: if you get the types wrong when calling Something.as<>, you’ll get a segfault or something similarly horrible. We’d like to replace that with something safer.

One way to do it is to use runtime type information. The simplest variation on this is to replace the static_cast with a dynamic_cast. However, we can only do this if SomethingValueBase is a polymorphic type, which it isn’t. We can make it so by adding in a virtual destructor:

#include <memory>

class Something
{
    private:
        struct SomethingValueBase
        {
            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            return dynamic_cast<const SomethingValue<T_> &>(*_value).value;
        }
};

Now, if we get the types wrong, a std::bad_cast will be thrown. Alternatively, we can use our own exception type:

class SomethingIsSomethingElse
{
};

class Something
{
    /* snip */

    public:
        template <typename T_>
        const T_ & as() const
        {
            auto value_casted(dynamic_cast<const SomethingValue<T_> *>(_value.get()));
            if (! value_casted)
                throw SomethingIsSomethingElse();
            return value_casted->value;
        }
};

We can also make use of std::dynamic_pointer_cast, which is possibly slightly less ugly syntactically:

class Something
{
    /* snip */

    public:
        template <typename T_>
        const T_ & as() const
        {
            auto value_casted(std::dynamic_pointer_cast<const SomethingValue<T_> >(_value));
            if (! value_casted)
                throw SomethingIsSomethingElse();
            return value_casted->value;
        }
};

All of this is using RTTI, though, and RTTI is a huge amount of overkill for what we need. Before eliminating the RTTI, though, we’ll switch to using it in a different way:

#include <memory>
#include <string>
#include <typeinfo>

class Something
{
    private:
        template <typename T_>
        struct SomethingValueType
        {
            virtual ~SomethingValueBase()
            {
            }
        };

        struct SomethingValueBase
        {
            std::string type_info_name;

            SomethingValueBase(const std::string & t) :
                type_info_name(t)
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                SomethingValueBase(typeid(SomethingValueType<T_>()).name()),
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            if (typeid(SomethingValueType<T_>()).name() != _value->type_info_name)
                throw SomethingIsSomethingElse();
            return std::static_pointer_cast<const SomethingValue<T_> >(_value)->value;
        }
};

Here we make use of typeid explicitly, which is widely considered to be about on par with use of goto. However, it paves the way for our next step. Can we replace typeid(SomethingValueType<T_>()).name() with a different, non-evil expression? Let’s think about what properties the result of that expression must have:

  • We must be able to store it, so it needs to be a regular type.
  • We must be able to compare values of it, and be guaranteed true if and only if the two types used to create the value are the same, and false if and only if they are different. (Note that RTTI doesn’t even provide this guarantee.)

Let’s try this:

#include <memory>
#include <string>

class SomethingIsSomethingElse
{
};

template <typename T_>
struct SomethingTypeTraits;

class Something
{
    private:
        struct SomethingValueBase
        {
            int magic_number;

            SomethingValueBase(const int m) :
                magic_number(m)
            {
            }

            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                SomethingValueBase(SomethingTypeTraits<T_>::magic_number),
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            if (SomethingTypeTraits<T_>::magic_number != _value->magic_number)
                throw SomethingIsSomethingElse();
            return std::static_pointer_cast<const SomethingValue<T_> >(_value)->value;
        }
};

Now, our library user has to provide specialisations of SomethingTypeTraits for every type they wish to use:

#include <string>
#include <iostream>
#include <vector>

template <>
struct SomethingTypeTraits<int>
{
    enum { magic_number = 1 };
};

template <>
struct SomethingTypeTraits<std::string>
{
    enum { magic_number = 2 };
};

int main(int, char *[])
{
    std::vector<Something> things = { std::string("foo"), 123 };
    std::cout << things[0].as<std::string>() << " " << things[1].as<int>() << std::endl;
}

No RTTI at all there, and it is type safe, but it relies upon a lot of boilerplate from the library user, and that boilerplate is very easy to screw up. So, we’ll allocate magic numbers automatically instead:

#include <memory>

class Something
{
    private:
        static int next_magic_number()
        {
            static int magic(0);
            return magic++;
        }

        template <typename T_>
        static int magic_number_for()
        {
            static int result(next_magic_number());
            return result;
        }

        struct SomethingValueBase
        {
            int magic_number;

            SomethingValueBase(const int m) :
                magic_number(m)
            {
            }

            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                SomethingValueBase(magic_number_for<T_>()),
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            if (magic_number_for<T_>() != _value->magic_number)
                throw SomethingIsSomethingElse();
            return std::static_pointer_cast<const SomethingValue<T_> >(_value)->value;
        }
};

How does this work? Each instantiation of the magic_number_for<T_> function needs to return the same magic number every time it is called. The first time any particular instantiation is called, its static int result requests the next magic number. On subsequent calls, the allocated number is remembered. (Note that static values inside a template are not shared between different instantiations of that template.) Finally, next_magic_number just returns a new magic number every time it is called.

And there we have it: fast runtime type checking with no boilerplate and no RTTI. What we’ve done here is more or less useless, but the techniques do have other applications. For the curious, std::use_facet<> is probably the most common, and anyone brave enough to delve into its design will eventually see why this isn’t either pointless wankery or reinventing the wheel. For the rest, if you think that using RTTI can solve your problem adequately, then it probably can, and you don’t need to go into the kind of devious trickery the standard library uses internally.

About these ads

10 responses to “Runtime Type Checking in C++ without RTTI

  1. Ben Craig May 24, 2010 at 4:14 pm

    Since you seem concerned with performance, you should strongly consider using make_shared instead of initializing your shared_ptr with a “new” expression. You avoid a superfluous hit to the heap if you use make_shared, because make_shared can package the ref count with the object being ref counted. Also note that your “as” function will almost never be inlined, because it contains a throw statement.

    I don’t think this solution is thread safe, as your static “magic” isn’t protected in any way. Also, the numbers you are producing are probably not useful for serialization, as the order of object construction could change which magic number each class gets.

    If you want fast and safe type comparisons, you should probably use type_info::operator==. You have an example where you are comparing the type_info names, but that will generally be slower than a direct comparison. Comparing a typeid is roughly on par with a pointer comparison.

    Just the same, you should really profile to see if dynamic_cast is as evil as you seem to think. It’s speed is proportional to the size of your inheritance hierarchy, and since your hierarchy is small, it should go pretty quick.

    • Ciaran McCreesh May 24, 2010 at 5:10 pm

      I was under the impression that packaging the ref count with the object was done using std::enable_shared_from_this. Is there something else clever that I’ve missed? For that matter, for real code I’d probably not use a shared value at all, and copy the value holder when the owning object was copied instead.

      In C++0x static initialisations are required to be done in a thread safe manner. For the current standard there’s no such thing as threads, and cluttering up the example with pthread wrappers or something similarly horrible would be counterproductive.

      I don’t really want to use type_info at all, since it opens a huge can of worms. std::type_info isn’t a regular type, which makes working with it a nuisance.

      dynamic_cast is a lot slower than static_cast. Whether or not that matters is down to the application.

      • Ben Craig May 24, 2010 at 5:23 pm

        enable_shared_from_this just allows safe construction of a shared_ptr, using a this pointer.

        make_shared allows statements like the following:
        _value(make_shared<SomethingValue >(42))

        make_shared will allocate a structure that contains the ref count and the SomethingValue, which it normally can’t do if the client of shared_ptr calls new in their code.

      • Kalon Mills June 1, 2010 at 5:00 pm

        Opps. It appears I don’t know how to deal with angle brackets when commenting. Lets see if I get this right this time. It should have read:

        Thus simultaneous calls to magic_number_for<std::string>() would be guaranteed to be thread safe, but a call to magic_number_for<std::string>() and magic_number_for<int>() would be allowed to run in parallel and could cause problems since they both rely on next_magic_number().

  2. Jared Grubb May 24, 2010 at 11:04 pm

    You must not do:
    std::shared_ptr<SomethingValueBase>
    if SomethingValueBase does not have a virtual destructor.

    As you defined it, the destructor of SomethingValueBase is trivial, and so the compiler will simply do nothing when it is reset; ~T will never get called — no matter how complex T is.

    For example, Something<std::string> will always leak the internal buffer used by the std::string object.

    • Ciaran McCreesh May 25, 2010 at 7:35 am

      Mm, yes. Unfortunately, the example’s stuck between keeping things simple enough that it’s not distracting, and giving a real working example that makes sense. Guess I should update that one since it’s a correctness thing rather than a purpose thing.

  3. Gopalakrishna Palem September 17, 2010 at 1:53 am

    Good article. We really dont need to worry about all the “industrial strength” features for example codes like this.

    However, the point of magic numbers being consistent across serializations is something worth looking into.

    Is it really required that the magic numbers should be same across serializations ?

    What does the “C++ standard” say about serializing / deserializing a class with static variables inside such as the magic number class here?

    Thank you,
    Gopalakrishna Palem

    • Ciaran McCreesh September 23, 2010 at 6:15 pm

      If you want consistent numbers, you have to hard-code them. There’s no way around it; the initialisation order is completely arbitrary.

  4. FF September 14, 2012 at 9:23 pm

    (Note that static values inside a template are not shared between different instantiations of that template.)
    A small note, but because of this fact you solution is useless.
    Or do you create you applications in one big module?

    I separate my projects into several modules, which communicate with clear interfaces.
    So when I create a “Something” instance in Module A and extract its value in Module B I might get a crash. Just think about it.

    That seems to be the reason why boost::any used typeid. q.e.d.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.