Compile time type id with templates (C++)
Tags: cpp, templates, programming, tutorial
Published: 2020-12-28 02:17:38

##The issue:

Another day while developing my game engine I had to handle events (which inherited from a common interface). The problem was that handling different event types with RTTI is not good in this case, as it is expensive. If-else statements were quite convoluted, so switch statement to the rescue.

The problem is that a switch statement requires all values to be known at compile time. Enums could be a solution, but IMO they are messy and have a wide margin for errors.

I ended up with a solution that uses TypeLists and CRTP to attribute different ids for the listed types.

##A solution:

First, let's define our TypeList (create a file called TypeList.h):

```cpp
//Typelist.h
#include <cstddef>
using id_type = int;
template <typename... Ts> class TypeList;

template <> class TypeList<> {
public:
    //This will be useful later
    static constexpr id_type id = -1; // -1 means invalid 
    template <typename T> static constexpr id_type index_of() { return id; }
};

template <typename T, typename... Ts> class TypeList<T, Ts...> {
    using remaining_types = TypeList<Ts...>;  
    static constexpr id_type id = sizeof...(Ts);

    template<typename U, bool dummy> 
    struct Helper {
        static constexpr id_type value = remaining_types::template index_of<U>();  
    };

    template<bool dummy>
    struct Helper<T, dummy> {
        static constexpr id_type value = id;
    };

public:

  // Returns -1 when the type is not found
  template <typename F> static constexpr id_type index_of() {
      return Helper<F, true>::value;
  };

};
```

We leverage variadic templates here. The empty parameter specialization is easy (and will prove useful later). An empty type list can't return a valid id for a type as it doesn't list anything.

The second specialization is not complicated either. A type id is the count of the remaining parameters. The trick here is in the function index_of<F>(). When F and T are of the same type, the specialized struct Helper will be instantiated, thus it's value will be equal to the current type id. When different, it will query the next level for the type id. If not found, the last level is our empty specialization, which returns an invalid id.

The standard doesn't allow full specialization of class templates inside other classes, but allows partial specialization, hence the use of the dummy bool parameter.

It's crucial that all values and expressions are available at compile time, thus the use of constexpr (it also allows us to define the value inside the class).

A nice thing about templates is that we can offer some guarantees for the user. One that I find useful is guaranteeing one id per type. If the user tries to insert the same type twice, static_assert will be triggered.

Let's implement our "parameter checker" helper:

```cpp
//Typelist.h
/* Headers included before */
#include <type_traits>
/* ... declarations ... */

template <typename... Ts> class HasRepeatedParameter;

template <typename T, typename... Ts> class HasRepeatedParameter<T, T, Ts...> {
public:
  static constexpr bool value = true;
};

template <typename T1, typename T2, typename... Ts> class HasRepeatedParameter<T1, T2, Ts...> {
public:
  static constexpr bool value = HasRepeatedParameter<T1, Ts...>::value || HasRepeatedParameter<T2, Ts...>::value;
};

template <typename T> class HasRepeatedParameter<T> {
public:
  static constexpr bool value = false;
};
```
It works by instantiating recursively itself and the specializations do the job for us.

Notice that it doesn't check against a qualified (const, volatile) types. It's out of the scope of this article and would add unnecessary complexity for our goal. Maybe the reader can try to tweak it to check for qualified types as an exercise.

Back to our TypeList class:

```cpp
//Typelist.h
/* ... Headers and declarations/definitions... */

template <typename T, typename... Ts> class TypeList<T, Ts...> {
    // Here we have our check
    static_assert(!HasRepeatedParameter<T, Ts...>::value, "TypeList can't have repeated parameters");
    /* ... Definition ...*/
};
```

I mentioned that I have used it on my game engine Event system, so the example I'll give will be in the same line.

Let's define our Event classes (create a file called Events.h):

```cpp
//Events.h
#include <iostream>
#include "TypeList.h"

class MouseEvent;
class KeyboardEvent;
class JoystickEvent;

using EngineEvents = TypeList<MouseEvent, KeyboardEvent, JoystickEvent>;
```

Nothing too special. We just defined our TypeList. The forward declarations above are required, but they come with something cool. If you ever need to erase one type you can substitute it for a mock type and the other ones after it will still have the same id.

Still on the same file:

```cpp
//Events.h
/* ... */
// Our interface

class IEvent {
  protected:
  IEvent() = default;
  public:
  virtual ~IEvent() = default;
  virtual const id_type get_id() const = 0;
};

// Here is where the magic happens.
template<typename Event>
class EngineEvent : public IEvent {
  static_assert(EngineEvents::index_of<Event>() != -1, "Event not at the EngineEvents list");
  EngineEvent() = default;
  virtual ~EngineEvent() = default;
  
// Incorrect inheritance will cause the compilation to fail, thus avoiding two events with the same id.
  friend Event;
public:

  const id_type get_id() const override {
    return id;
  }

  static constexpr id_type id = EngineEvents::index_of<Event>();
};

//Our different Events.
class MouseEvent : public EngineEvent<MouseEvent> {
  public:
  void do_mouse_event_stuff() const {
    std::cout << "Doing MouseEvent stuff\n";
  };
};

class KeyboardEvent : public EngineEvent<KeyboardEvent> {
  public:
  void do_keyboard_event_stuff() const {
    std::cout << "Doing KeyboardEvent stuff\n";
  };
};

class JoystickEvent : public EngineEvent<JoystickEvent> {
  public:
  void do_joystick_event_stuff() const {
    std::cout << "Doing JoystickEvent stuff\n";
  };
};
```

The class IEvent is the interface. A const reference to a IEvent is what our handler function will have as a parameter, thus not knowing anything beforehand about the object.

The template class EngineEvent is where the magic happens. It defines an id value which is simply the index of our Event type on the EngineEvents list. This value will be available on our Event classes, as they will inherit from it. Note that in case a given event is not listed on the EngineEvents list a static_assert will be triggered, failing compilation.

The remaining classes are our Event classes. They simply inherit from EngineEvent giving themselves as a template parameter (CRTP).

##Usage:

Now define a file called main.cpp with the following content:

```cpp
#include "Events.h"

void handle_event(const IEvent& e) {
  switch(e.get_id()) {
    case MouseEvent::id:
      static_cast<const MouseEvent&>(e).do_mouse_event_stuff();
      break;
    case KeyboardEvent::id:
      static_cast<const KeyboardEvent&>(e).do_keyboard_event_stuff();
      break;
    case JoystickEvent::id:
      static_cast<const JoystickEvent&>(e).do_joystick_event_stuff();
      break;
    default:
      std::cout << "Event not recognized.\n";
  }
}

int main() {
  MouseEvent m;
  KeyboardEvent k;
  JoystickEvent j;

  handle_event(m);
  handle_event(k);
  handle_event(j);
  
  return 0;
}
```

If you did everything right you should have the following output:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/f2qccuflk33kx3pz01rj.png)

##Conclusion:

This is just one of the many possible solutions for the given problem. I like it because it is simple, doesn't introduce dependencies and is less prone to errors than Enums (different values for the same type being the main one).

The full code is available at [GitHub](https://github.com/heliobatimarqui/CompileTimeTypeID).

It's worthy noting that I tested it on G++ version 10.2.1 with the option -std=c++11. 

I hope you that you enjoyed it and learned something today. This is my first time posting something related to programming, so any feedback (positive or negative) would be really appreciated. Thank you!