January 14, 2012

C++, generic wrappers, and CRTP, oh MI!

Reading some of the original traits papers, I got to the part where they mention the conceptual difficulties inherent in multiple inheritance (MI), one of which is "factoring out generic wrappers". [*]

There's a footnote clarifying that, in practice, languages with MI actually do have other ways of accomplishing the factoring, and in reading that I remembered that the first time I actually understood CRTP (Curiously Recurring Template Pattern) was because I needed some generic wrappers.

Some folks were asking about CRTP on our IRC channel this past week, so I figured I'd share a quick walk-though.

Sometimes you want to be able to shove a method implementation onto a class, given that it has a few buiding blocks for you to work with. Let's say that there's some generic and formulaic way of making a delicious cake.

class CakeMaker
{
  public:
    Cake makeCake() {
        Ingredients ingredients = fetchIngredients();
        if (ingredients.spoiled())
            return Cake::Fail;

        BatterAndWhatnot batter = mixAndStuff(ingredients);
        Cake result = bake(batter);
        if (cake.burned())
            return Cake::Fail;

        return cake;
    }
};

This is supposed to be a reusable component for shoving a makeCake method onto another class that already has the necessary methods, fetchIngredients, mixAndStuff, and bake.

Great. So now let's say that we have two different cake makers, CakeFactory and PersonalChef — we want to just implement the necessary methods for CakeMaker in those and somehow shove the makeCake method onto their class definition as well. Maybe we can inherit from CakeMaker or something?

But here's the rub: CakeMaker can't exist. It is an invalid class definition that will not compile, because it refers to methods that it does not have.

cdleary@stretch:~$ g++ -c crtp.cpp
crtp.cpp: In member function ‘Cake CakeMaker::makeCake()’:
crtp.cpp:17:56: error: ‘fetchIngredients’ was not declared in this scope
crtp.cpp:21:62: error: ‘mixAndStuff’ was not declared in this scope
crtp.cpp:22:38: error: ‘bake’ was not declared in this scope

Luckily, C++ templates have this nice lazy instantiation property, where the code goes mostly unchecked by the compiler until you actually try to use it. So, if we just change our definition to:

template <typename T>
class CakeMaker
{
    // ...
};

GCC will accept it if we ask it to shut up a little bit (with -fpermissive), because we're thinking.

So now we take a look at our close friend, PersonalChef:

class PersonalChef
{
    Ingredients fetchIngredients();
    BatterAndWhatnot mixAndStuff(Ingredients);
    Cake bake(BatterAndWhatnot);
};

We want to shove the CakeMaker method onto his/her class definition. We could inherit from the CakeMaker and just pass it an arbitrary type T, like so:

class PersonalChef : public CakeMaker<int>
{
    // ...
};

But we need a way to wire up the methods that CakeMaker needs to the methods that PersonalChef actually has. And this is where we take the final step — via a stroke of intuition, let's pass in the type that actually has the methods on it, and use that type to refer to the method implementations within CakeMaker:

template <class Wrapped>
class CakeMaker
{
  public:
    Cake makeCake() {
        Wrapped *self = static_cast<Wrapped *>(this);
        Ingredients ingredients = self->fetchIngredients();
        if (ingredients.spoiled())
            return Cake::Fail;

        BatterAndWhatnot batter = self->mixAndStuff(ingredients);
        Cake result = self->bake(batter);
        if (result.burned())
            return Cake::Fail;

        return result;
    }
};

class PersonalChef : public CakeMaker<PersonalChef>
{
    Ingredients fetchIngredients();
    BatterAndWhatnot mixAndStuff(Ingredients);
    Cake bake(BatterAndWhatnot);

    friend class CakeMaker;
};

int main()
{
    PersonalChef chef;
    chef.makeCake();
    return 0;
}

Bam! Now it compiles normally. The CakeMaker is given PersonalChef as the template type argument, and the CakeMaker converts its this pointer for use as the PersonalChef type (which is valid in this case, since PersonalChef is a CakeMaker), which does implement the required methods!

This can also be used to enforce minimum interface requirements at compile time (as in the cross-platform macro assembler) without the use of virtual functions, which have a tendency to thwart inlining optimization.

Fun fact: it looks like we have about 90 virtual function declarations in the 190k lines of engine-related C/C++ code that cloc tells me are in the js/src directory.

Footnotes

[*]

Fun concept from the papers: the conceptual issue with MI is that classes are overloaded in their purpose: they are intended to serve both as units of code (implementation) reuse and for instantiation of actual objects.