Cool Boys Do Metaprogramming

#cpp #metaprogramming #templates

For a while I have been wanting to start posting about programming in general. Until now I really had nothing I thought were interesting to post. However last semester I took a course in which I had to use C++ as main tool for the final project. I had very little understading of C++ until taking this course. In the few weeks I took it, I learned some interesting features of C++ and I want to share them through some posts.

The Problem

My project was to design some cellular automata in C++ and simulate them. A cellular automata is, roughly speaking, a bunch of objects (named cells) that update themselves based on global rules. At each timestamp a cell will update itself based on the global rules and on its neighbours cells. These cells are, usually, represented as a matrix of cells. For the sake of simplicity this matrix will be only a std::array in the examples below. That said, a cell could be anything, could be any type of object that makes sense to be a cell. When comes to C++, this situation usually leads to the usage of templates. But more importantly than the "this could be anything" thing is that this thing must implement some general behaviour. In special the to_string method. I needed it in order to write the current state of each cell to a file. The very beginning of CellularAutomaton class could be:

template<uint32_t rows, uint32_t cols>
class CellularAutomaton {

    std::array<???, rows * cols> cells;
};

But what is the type of ???.

A First Solution

Every cell, it doesn't matter its type, should implement some general behaviour. We can use inheritance here. Lets create a CellBase class and all the cells will inherit from it. CellBase is purely an interface and can't be instantiated since it has one virtual method with no implementation.

class CellBase {
 public:

    CellBase() = default;
    virtual std::string to_string() const = 0;
};

Now the implementation of the Automaton class will be:

template<uint32_t rows, uint32_t cols>
class CellularAutomaton {

    std::array<std::unique_ptr<CellBase>, rows * cols> cells;

 public:

    std::unique_ptr<CellBase>& getCell(uint32_t row, uint32_t col) {
        return cells[row * cols + col];
    }

};

Few notes:

We must use pointers to store the cells since CellBase can't be instantiated.
There will be one vtable for every class that inherits from CellBase.
Every time we need to fetch a cell from the automaton we must return a std::unique_ptr<>& since unique pointers can't be copied.
This solution becomes impossible when we introduce third-party libraries.

The Second Solution

We simply use a template:

template<typename T, uint32_t rows, uint32_t cols>
class CellularAutomatonV2 {
 public:

    T& getCell(uint32_t row, uint32_t col) {
        return cells[row * cols + col];
    }

    std::array<T, rows * cols> cells;
};

Now our goal is to assert somehow that T implements a std::string to_string() const {} method with the same signature.
Lets start simple defining a struct, in fact, a trait that receives a type and a signature. It will store a static member value that tells whether or not the type T implements has_string method with the S signature. A trait is essencially that: a thing that tells us a fact about a type.
The code below is the starting point for this trait. It receives a type T and a function signature S which is a type too. It has a value static member that holds the answers for the question "Does this Type have a method called to_string with this specific signature". From T we can capture the method via &T::method_name and compare (if this name exists) its signature with S. But how?

template<typename T, typename S>
struct trait_has_to_string {
    static bool constexpr value = ...;
};

SFINAE To The Rescue

SFINAE stands for substitution failure is not an error. In practice, when the compiler sees a template function, it will try to generate code according to the types passed to the function. For example:

template<typename T, typename U>
auto add(const T& a, const U& b) -> decltype(a + b) {
    std::cout << "Calling general template" << std::endl;
    return a + b;
}

template<typename U>
auto add(const std::string& a, const U& b) -> std::string {
    std::cout << "Calling specialization const std::string&" << std::endl;
    return a + std::to_string(b);
}

template<typename U>
auto add(const char* a, const U& b) -> std::string {
    std::cout << "Calling specialization for const char*" << std::endl;
    return std::string(a) + std::to_string(b);
}

For every call of add, the compiler will have three template functions to choose. The following calls:

    const std::string test = "testing";
    std::cout << add(2, 2) << std::endl;
    std::cout << add("testing ", 1) << std::endl;
    std::cout << add(test, 1) << std::endl;

Result in:

Calling general template
4
Calling specialization for const char*
testing 1
Calling specialization const std::string&
testing 1

The first call will fail to use the templates functions with add(const std::string&, const U&) and add(const char*, const U&) signatures, but substituion failure is not an error as long as at least one version can be called with the passed types. For the first call it will choose the most generic version. The second call fits two templates functions (add(const T&, const U&) and add(const std::string&, const U&)). It will choose add(std::string&, const U&) because it is more specific. Compiler will always try the most specific fit. The third call will choose add(const char*, const U&) as expected. With that, we can detect whether or not a method exists in a class!

But before moving forward, a note: The first template function has the template<typename T, typename U> auto add(const T& a, const U& b) -> decltype(a + b) signature. The decltype keyword is used to query the type of a expression
and in the declaration above, it just means that the functions returns the same type as the expression a+b.

Getting Back To The Problem

The following code does the trick we want:

template<typename T, typename S>
struct trait_has_to_string {
    using True = std::true_type;
    using False = std::false_type;

    template<typename U, U> struct Model;

    template<typename U> static True Check(Model<S, &U::to_string> *);
    template<typename U> static False Check(...);

    static bool constexpr value = std::is_same<True, decltype(Check<T>(0))>();
};

And we can call like this:

trait_has_to_string<T, std::string(T::*)() const>::value;

Turning into a function:

template<typename T>
struct has_to_string {
    static bool constexpr value = trait_has_to_string<T, std::string(T::*)() const>::value;
};

The type of to_string method is its own signature. The static method True Check(Model<S, &U::to_string> has two versions. The first one will be called whenever it is possible to instantiate the Model (i.e there is a &U::to_string and its signature matches S exactly). The 0 being passed to Check<T>(0) is just a nullptr. The most generic version will be called when the first fails. The rest of the code is pretty straightforward:

std::true_type and std::true_type are types for the values true and false, respectively.
We could have written the two versions of Check returning true for the first version and false for the second. But they always return the same value. It does make sense to specialize these return types to std::true_type and std::false_type, respectively. And more, we don't need even call the Check because the instantiated version will carry its returning value as the return type of the method.

Now the final version of automaton:

class CellularAutomaton {
 static_assert(has_to_string<T>::value, "T does not implement std::string to_string() const;");
 public:

    T& getCell(uint32_t row, uint32_t col) {
        return cells[row * cols + col];
    }

    std::array<T, rows * cols> cells;
};

And two different cell types:

struct CellTypeOne {
    std::string to_string();
};

struct CellTypeTwo {
    std::string to_string() const;
};

And finally, the main:

CellularAutomaton<CellTypeOne,2, 2> automaton1;
CellularAutomaton<CellTypeTwo,2, 2> automaton2;

Now, the static_assert will fail for automaton1 because the const modifier is not present in the method signature. This trait allows us to detect the existence and throw the error before we attemp to call to_string in a type that doesn't have this method. More than that, we can specify a default return for those types that don't implement the method.