Cool Boys Do Metaprogramming
Tags: cpp, metaprogramming, templates
Published: 2021-01-02 01:28:52

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:

```cpp
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.

```cpp
class CellBase {
 public:

    CellBase() = default;
    virtual std::string to_string() const = 0;
};
```
Now the implementation of the Automaton class will be:

```cpp
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: 
1. We must use pointers to store the cells since `CellBase` can't be instantiated.
2. There will be one `vtable` for every class that inherits from `CellBase`.
3. 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.
4. This solution becomes impossible when we introduce third-party libraries.

# The Second Solution
We simply use a template:
```cpp
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?

```cpp
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:

```cpp
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:
```cpp
    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:

```console
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:

```cpp
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:

```cpp
trait_has_to_string<T, std::string(T::*)() const>::value;
```
Turning into a function:

```cpp
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:
1. `std::true_type` and `std::true_type` are types for the values `true` and `false`, respectively.
2. 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:
```cpp
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:

```cpp
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.