Probably Dance

So I’ve been working on the serialization code for our engine. And I’m finally understanding the more complex aspects of template metaprogramming, and it turns out that there are some neat things you can do with it that aren’t directly related to serialization.

OK let’s say you have an editor in your game, and in this editor you have a button “Add Component” which adds a new component to an entity. That button would open a pop-up menu, where you can select from all your component types and after selecting one, a new instance of that component-class is created and added to the entity. How do you populate that list? My solution using template metaprogramming and reflection is after the jump:

Assuming that all your components are C++ classes, my first solution would be to have a map with the names of all components and pointers to a factory. Which you would have to keep up to date. And that actually isn’t too much work by itself. You probably already have a macro to register types for serialization or scripting or both. Just write a second version of that macro that also registers the type in the map I mentioned.

But what if you also want a similar button just for spells? Or for AI behaviors? Or for any other C++ class that you want to create instances of in the editor? What if classes have to be in multiple maps? Shouldn’t there be a way for C++ to figure that out for you?

Template metaprogramming is your friend here. Let’s say your meta-type class looks something like this:

template
struct RegisteredType : public Type
{
    string name;
    virtual void * create() const { return new T(); }
};

It probably has more stuff in it, but this gets the idea across. This is your factory, and this is what you create when you register your type for serialization or scripting languages. My solution to the described problem used to be to extend this to have functions that test for whatever base class I want to test for:

template
struct RegisteredType : public Type
{
    string name;
    virtual void * create() const { return new T(); }
    virtual bool isComponent() const
    {
        T * toTest = new T();
        Component * result = dynamic_cast(toTest);
        delete toTest;
        return result;
    }
    virtual bool isAIBehavior() const
    {
        //...
    }
    //...
};

This works: you no longer have to maintain many lists. Just iterate over all Types and ask them if they are a Component or an AIBehavior. It’s a bit slow but this needs to run rarely, so that’s fine. But it has one major disadvantage: Suddenly all your base classes’ header files need to be included in this file. And this file is probably in your precompiled header. Which is fine for something as generic as a Component, but as I started using this more, I added some pretty obscure stuff to this. And then compile time got really annoying because it seemed like I had to start from the precompiled header way too often.

And here is where template metaprogramming comes in. First, let’s improve the previous code by a lot:

//...
    virtual bool isComponent() const
    {
        return is_base_of::value;
    }
//...

Ok this is awesome and this is standard in C++0x: Now this is evaluated at compile time. (you can also do this with boost type traits in older compilers) I’ll kind of explain how that is possible in a second. With this we unfortunately still have the problem of having to include all the header files, because is_base_of doesn’t work for incomplete types. (as in it doesn’t work for types whose header files we haven’t included)

Now here’s the solution to our problem: Component will only be an incomplete type if our type T is not derived from it. Whenever this RegisteredType<T> struct is created, T will not be an incomplete type, and thus if T is derived from Component, Component will not be an incomplete type.

So what we need is a version of is_base_of that returns false if the base type is incomplete rather than giving us a compiler error. (I think the Visual Studio 2010 implementation already does that, but I can’t rely on that because the standard doesn’t say that it should do that) For that we need to figure out if a type is incomplete. My implementation looks like this: (explanation afterwards)

template
struct isIncompleteType
{
typedef char (&yes) [1];
typedef char (&no)  [2];

template
static yes check(...);
template
static no check(decltype(static_cast(0)->~U()) *);

static const bool value = sizeof(check(0)) == sizeof(yes);
};

Ok what is this? I can tell you that it works, and isIncompleteType<Component>::value is true or false depending on whether Component is only forward declared or if the header file is actually included. The concept I use here is called SFINAE, which stands for “Substitution failure is not an error” and means that if your template method fails to compile in certain ways, the compiler is fine with that and just tries to compile the next function. Let’s go through this line by line.

So for those typedefs: yes is typedeffed to be a reference to a char array of size 1, and no is typedeffed to be a reference to a char array of size 2. The only thing that is important is that sizeof(yes) != sizeof(no). For readability I could have typedeffed them to be char and int, but that could possibly fail on some obscure platform.

Then the check functions: The overload that returns yes will always compile. The overload that returns no is more complicated. Let’s read this from the inside out. There is this statement:

static_cast(0)->~U()

This doesn’t make any sense. I create a null pointer of type U* and then call ~U() on that. Why would I do that? Well this just happens to be a line that would compile for complete types and wouldn’t for incomplete types. That’s all I was thinking about. The cool thing is, that this never gets executed or even compiled because I put a decltype() around it. decltype is a new statement in C++0x and just means “whatever the return type of this statement is.” It’s like sizeof() in it’s behavior. And the type of static_cast<U*>(0)->~U() happens to just be void. If you untangle everything, the line will read

static no check(void *);

for types that are not incomplete, and it will fail to compile for types that are incomplete.

So now it’s time for that final line:

static const bool value = sizeof(check(0)) == sizeof(yes);

This asks the compiler “if I were to run check<T> with a null pointer, what would the size of the return type be?” If the size happens to be sizeof(yes) the statement evaluates to true. If the compiler was able to compile both lines, it will pick the one that returns no, because it fits better. If the compiler was not able to return the line that returns no, then it will pick the line that returns yes, and this is an incomplete type.

So with this we can write our function to work correctly for incomplete types, which would free us from the need to include the header files:

//...
    virtual bool isComponent() const
    {
        return !isIncompleteType::value
                && is_base_of::value;
    }
//...

Done. This works except for one tiny exception. (if the base type has a private or protected destructor the isIncompleteType returns true, even though it shouldn’t. But I don’t have a problem with that)

With some more very simple macros (that I won’t explain because I feel like this post is long enough) I now have it that if I want to know all types that inherit from one base type, all I have to do is add one line. And I don’t have to include that base type’s header file in the entire project.

I’m rather happy with myself for that.