2024.10.24
I was working on my game engine, and I had a number of systems with Act() functions that would be called as the game ran.
struct GameSystem { virtual void Act() const; };
struct PhysicsSystem : GameSystem { virtual void Act() const; }
struct GraphicsSystem : GameSystem { virtual void Act() const; }
struct HealthSystem : GameSystem { virtual void Act() const; }
// Register systems
// ...
void RunGame() {
for(GameSystem& system : systems) {
system->Act();
}
}
Act would modify the game's data using functions like this:
void PhysicsSystem::Act() {
for(size_t id : GetPhysicsEntities()) {
const Velocity& vel = GetComponent<const Velocity>(id);
Position& pos = GetComponent<Position>(id);
pos = pos + vel;
}
}
void GraphicsSystem::Act() const {
for (size_t id : GetGraphicsEntities()) {
Render(
GetComponent<const Position>(id),
GetComponent<const Mesh>(id)
);
}
}
void HealthSystem::Act() const {
for (size_t id : GetHealthEntities()) {
HitPoints& hitPoints = GetComponent<HitPoints>(id);
const Damage& damage = GetComponent<const Damage>(id);
hitPoints -= damage;
RemoveComponent<Damage>(id);
}
}
I wanted to be able to run these systems in parallel, without the systems worrying about synchronizing data access. Without any guards in place, data races could easily happen.
I realized I could safely run systems in parallel if I knew all the data each of these systems would touch. The question was, how could I track this? I started with a gatekeeper system, where I could specify the types used ahead of time, and validate at compile time that only the specified types were used:
struct PhysicsSystem : AllowedTypes<const Velocity, Position>;
This approach worked, but I didn't like the disadvantages it brought with it.
Because of this, I started looking into automatic ways to track function calls. I considered letting the data access functions track what was used.
template <typename T>
void GetComponent<T> {
MarkAccess<T>();
}
void GameSystem::TrackDataAccess() {
Act();
dataAccessed = GetNewDataAccesses();
}
However, I worried about how branching code wouldn't get tracked:
void HealthSystem::Act() {
// Give everyone a second after game start before taking damage.
if(GetFramesSinceSpawn() < 60) {
return;
}
// Won't get tracked at startup.
for(size_t id : GetHealthEntities()) {
const Damage& damage = GetComponent<const Damage>(id);
Health& health = GetComponent<Health>(id);
health.hp -= damage.totalDamage;
}
}
This led me to decide I wanted to try getting this information at compile-time.
One possible approach would have been to use a code generator that searched for all instances of GetComponent(), and generated a .cpp with the types used.
// ***physics_system.gen.cpp***
// Auto-generated; do not modify.
std::vector<TypeId> PhysicsSystem::GetAccessedTypes {
return std::vector {
GetTypeId<const Velocity>(),
GetTypeId<Position>()
};
}
While this approach seems ideal for a large project with a more refined build system, I didn't want to complicate the simple build process of my small game. On top of this, I worried about edge cases that might be hard for a codegen parser to catch. This is the option I understand the least though, so if you've had success with it, please let me know!
This left me with the solution I'll be sharing here: A compile-time, pure C++ way to track template instantiations. Adapting a game system to use this is trivial: just inherit from TemplateTracker, and add a function that reads the the auto-generated typelist.
// ***physics_system.h***
struct PhysicsSystem :
public GameSystem,
// Added inheritance to TemplateTracker
protected TemplateTracker<PhysicsSystem>
{
virtual void Act() const override;
// Added function to get accessed types.
virtual std::vector<ID> GetAccessedTypeIDs() const override;
};
// ***physics_system.cpp***
// PhysicsSystem::Act() stays exactly the same.
// New function that accesses auto-generated typelist.
std::vector<ID> PhysicsSystem::GetAccessedTypeIDs() const {
// TUs that call GetComponent() have compile-time info that lists all instances called.
static_assert(std::is_same<Info<>::GetComponentTypes, Typelist<const Velocity, Position>>::value, "");
// Run-time info can be returned for other TUs to use.
return GetTypeIDs(Info<>::GetComponentTypes{});
}
I stumbled a lot trying to get this to work, so I'll be building up the solution gradually in hopes that it helps someone else who might be trying to solve the same problems. I'll be focusing on the practical ("This won't compile until...") over the theoretical ("The standard states that...") for a few reasons.
This implementation supports C++14 or later. MSVC 16.3+ is supported with /W4 /WX flags. Clang 12+ and GCC 7+ are supported with -Wall -Wextra -pedantic -Werror flags.
Before we can automatically track types, we need a way to represent types. I'll be using a simple typelist implementation. Any implementation will do, as long as it does the following:
Here's the simple typelist implementation we'll be using:
#include <stddef.h> // size_t
#include <type_traits> // std::is_same
template <typename... Ts>
struct Typelist {
template <typename... Us>
auto append(Typelist<Us...>) {
return Typelist<Ts..., Us...>{};
}
};
static_assert(
std::is_same<
decltype(Typelist<int, float>{}.append(Typelist<double, void>{})),
Typelist<int, float, double, void>
> ::value, ""
);
The first challenge we face is sharing compile-time information between two different functions. Let's start with a simple setup. We have a header file declaring a runtime setter and checker and a source file implementing them. How can we edit the bodies of these functions so SetterFunction() can create a compile-time bool and GetterFunction() can read it?
void SetterFunction() {
// set bool here
}
void GetterFunction() {
static_assert(/*get bool here*/ == true, "");
}
Our options seem limited. The only way to expose a constexpr bool, class, or lambda created in SetterFunction() would be to return it, but we're stuck with a void function. What can we do?
The function signatures are already set for us, so we can't return anything.
Within a function, any constexpr bools, classes, or lambdas won't be accessible outside the function, unless we return them.
The solution surprised me. It's possible to define previously-declared functions in classes, by defining a friend function.
constexpr bool GetBool();
struct BoolSetter {
friend constexpr bool GetBool() { return true; }
};
static_assert(GetBool() == true, ""); // Passes
This is called friend injection, and this article is a great resource for understanding how the standard permits all of this, if you're interested.
Things get really interesting when we use template parameters to control what the friend-injected function does.
constexpr bool GetBool();
template <bool value>
struct BoolSetter {
friend constexpr bool GetBool() { return value; }
};
auto obj = BoolSetter<true>{};
static_assert(GetBool() == true, ""); // Passes
With this new tool, it's now possible to complete the challenge!
constexpr bool GetBool();
template <bool value>
struct BoolSetter {
friend constexpr bool GetBool() { return value; }
};
void SetterFunction() {
auto obj = BoolSetter<true>{};
(void) obj; // Avoid unused warning.
}
void GetterFunction() {
static_assert(GetBool() == true, "");
}
Bringing this back to type information, we can modify our previous code to pass around types. Recall that our typelist is trivial to construct, so we can change our injector code code to return a typelist based on the template type. Since the type is no longer known at function declaration, we need to make the return type auto. On the GetterFunction() side, we can extract the type from the GetType() by calling declspec on it.
constexpr auto GetType();
template <typename T>
struct TypeSetter {
friend constexpr auto GetType() { return Typelist<T>{}; }
};
void SetterFunction() {
auto obj = TypeSetter<float>{};
(void) obj; // Avoid unused warning.
}
void GetterFunction() {
static_assert(std::is_same<decltype(GetType()), Typelist<float>>::value, "");
}
The next challenge we have is storing multiple types. Our solution would not be very extensible if we had to declare a separate GetTypeN() function for each type.
constexpr auto GetType0();
constexpr auto GetType1();
// etc
template <typename T>
struct TypeSetter0 {
friend constexpr auto GetType0() { return Typelist<T>{}; }
};
template <typename T>
struct TypeSetter1 {
friend constexpr auto GetType1() { return Typelist<T>{}; }
};
//etc
How can we offer N functions without manually declaring them all? There's a second part to the friend injection trick: free functions can also be declared as friends. These functions will live in the space of the class that declares them.
// Explicitly NO GetType() declared before here
template <size_t n, typename T>
struct TypeSetter {
friend constexpr auto GetType() { return Typelist<T>{}; }
};
This technique is called a "hidden friend", and it's important to note that GetType() is neither in global scope, nor accessible via the use of TypeSetter<n, T>::.
// Error: GetType does not exist in this scope.
GetType();
// Error: GetType is not a member of TypeSetter.
TypeSetter<0, float>::GetType();
Instead, we can access these functions by adding a parameter that will force the Argument-Dependent Lookup (ADL) to look in the TypeSetter space.
template <size_t n, typename T>
struct TypeSetter {
friend constexpr auto GetType(TypeSetter) { return Typelist<T>{}; }
};
void GetterFunction() {
// This works!
GetType(TypeSetter<0, float>{});
}
This introduces a new question though: in GetterFunction(), how can we access GetType() without specifying float like we did in the example above? The answer is by keeping the declaration and definition of the function separate, just like we did before! By adding an Index type that just declares GetType(), we can access or even friend-inject this function using Index<n> as a parameter!
template<size_t n>
struct Index {
friend constexpr auto GetType(Index);
};
template <size_t n, typename T>
struct TypeSetter {
friend constexpr auto GetType(Index<n>) { return Typelist<T>{}; }
};
GetType() is now declared in the Index space. TypeSetter is defining GetType(), but since it uses Index as a parameter, the Index-space declaration will happen first, then TypeSetter is just defining the pre-declared GetType(). Note that each different instance of Index is declaring a different GetType() function.
With this, we've now cleared our second challenge!
void SetterFunction() {
auto obj0 = TypeSetter<0, float>{};
auto obj1 = TypeSetter<1, bool>{};
(void) obj0;
(void) obj1;
}
void GetterFunction() {
static_assert(std::is_same<
decltype(GetType(Index<0>{})),
Typelist<float>
>::value, "");
static_assert(std::is_same<
decltype(GetType(Index<1>{})),
Typelist<bool>
>::value, "");
}
We know we're going to need to declare independent typelists for each service, so we can go ahead and prepare for that now. This is one of the easier parts--all we need to do is add a Tag type to the Index and TypeSetter template parameters, so GetType(Index<Tag1, 3>) returns a different typelist than GetType(Index<Tag2, 3>).
template<typename Tag, size_t n>
struct Index {
friend constexpr auto GetType(Index);
};
template <typename Tag, size_t n, typename T>
struct TypeSetter
{
friend constexpr auto GetType(Index<Tag, n>) { return Typelist<T>{}; }
};
And with this, Index and TypeSetter are in their final form! From here, we'll now be using these as core building blocks for the rest of our code.
So far, we can declare a set of typelists in a function, and have them show up in another, which is already exciting. However, we're still missing some functionality to make this easy to use. Using the type indices directly is error-prone. Ideally, on the setting side, we would set our first type to index 0, then our next type to 1, and so on. On the getting side, we would like to automatically generate the full typelist, without having to know how many types have been tracked.
void BadSetterFunction() {
auto obj0 = TypeSetter<BadTag, 0, float>{};
auto obj1 = TypeSetter<BadTag, 1, bool>{};
// Accidentally set index 3! This is error prone.
auto obj2 = TypeSetter<BadTag, 3, int>{};
}
void BadGetterFunction() {
using AllTypes = decltype(
// We forgot to track all 3 types! This is hard to maintain.
GetType(Index<BadTag, 0>{})
.append(GetType(Index<BadTag, 1>{}))
);
}
void GoodSetterFunction() {
// No indices to get wrong!
auto obj0 = AddType<GoodTag, float>{};
auto obj1 = AddType<GoodTag, bool>{};
auto obj2 = AddType<GoodTag, int>{};
}
void GoodGetterFunction() {
// Automatically know all types set!
using AllTypes = GetAllTypes<GoodTag>;
}
This all starts with checking if an index is set yet. Let's simplify the problem. Ignoring C++14 compatibility for a moment, how can we check if a function overload exists? We might consider a simple function template with a requires expression to see if a function exists.
template <typename Tag, size_t n>
constexpr bool IndexIsSet() {
return requires {GetType(Index<Tag, n>{});};
}
struct TestTag;
auto obj0 = TypeSetter<TestTag, 0, float>{};
static_assert(IndexIsSet<TestTag, 0>() == true, "");
static_assert(IndexIsSet<TestTag, 1>() == false, "");
Can you see the major problem with this though? Once a function template is instantiated, that specific function template instance will always return the same result.
auto obj0 = TypeSetter<TestTag, 0, float>{};
static_assert(IndexIsSet<TestTag, 0>() == true, "");
static_assert(IndexIsSet<TestTag, 1>() == false, "");
auto obj1 = TypeSetter<TestTag, 1, int>{};
// Assert fails; test will always return false!
static_assert(IndexIsSet<TestTag, 1>() == true, "");
How can we work around this? One approach is to use SFINAE.
constexpr bool IndexIsSet(...) {
return false;
}
template <typename IndexType>
constexpr std::enable_if_t<
requires {GetType(IndexType{});},
bool
> IndexIsSet(IndexType) {
return true;
}
struct TestTag;
auto obj0 = TypeSetter<TestTag, 0, float>{};
static_assert(IndexIsSet(Index<TestTag, 0>{}) == true, "");
static_assert(IndexIsSet(Index<TestTag, 1>{}) == false, "");
auto obj1 = TypeSetter<TestTag, 1, int>{};
// Test will now update to true.
static_assert(IndexIsSet(Index<TestTag, 1>{}) == true, "");
This may seem like we're opening ourselves up to the same problem, but we're not. Instead of using a template instance every time, our code now checks overload candidates every time. If the type is not set at that index, the function template candidate would fail to compile, and SFINAE skips that candidate. Importantly, this means the template will not be instantiated. On the other hand, once the type is set, the function template can be compiled, so it's instantiated, and it always returns true from now on.
Finally, we can re-enter the C++14 world by avoiding using requires in our SFINAE.
constexpr bool IndexIsSet(...) {
return false;
}
template <typename IndexType>
constexpr auto IndexIsSet(IndexType) -> decltype(GetType(IndexType{}), bool{}) {
return true;
}
The next goal is easily stated: We want to know the next type index available. This way, we can use that index when adding a new type, or list all the types up to that index.
This can be done with under 20 lines of code, but the reasoning behind these lines is dense. I personally consider this to be the most complicated part of the implementation.
Before we work on the solution, let's figure out more specifically what we want. Like with IndexIsSet, we want a constexpr template that returns a value, and updates as indices are changed. Unlike IndexIsSet, we can't just pick between a true or false-returning overload. Instead, we have an infinite number of overloads to choose from. This makes SFINAE much less viable.
Not all hope is lost, though. How else can we re-evaluate our state every time our function template is called, instead of once in the body of the function template?
The answer lies in the template parameters. By having a default template parameter, the expression for that template will be evaluated every time. We're still only having one "state" per template instance, we just now have more instances.
template <typename Tag, typename Unique = MagicUniqueTypePerIndexState>
size_t GetMaxIndex() {
// Calculate and return max index
}
size_t index0 = GetMaxIndex<TestTag>();
auto obj0 = TypeSetter<TestTag, 0, float>{};
// Will be different from index0.
size_t index1 = GetMaxIndex<TestTag>();
Since we didn't specify the Unique parameter, its default argument will be reevaluated for index1. Since the default will be a new type, the call uses a new instance, which means the template is reevaluated and a new result is returned.
So, in C++14, how can we have an auto-deduced unique parameter for each index? What if we used recursion? There are 3 obstacles to making this possible.
These examples wouldn't work, for instance:
template <
typename Tag,
size_t n = 0,
bool isSet = IndexIsSet(Index<Tag, N>{})
>
struct BadMaxIndex {
static constexpr size_t value = BadMaxIndex<Tag, n + 1>::value;
};
template <typename Tag, size_t n>
struct BadMaxIndex<Tag, n, false> {
static constexpr size_t value = n;
};
struct DummyTag;
static_assert(BadMaxIndex<DummyTag>::value == 0, ""); // Passes: value is 0.
auto obj0 = TypeSetter<DummyTag, 0, int>{};
static_assert(BadMaxIndex<DummyTag>::value == 1, ""); // Passes: value is 1.
auto obj1 = TypeSetter<DummyTag, 0, float>{};
static_assert(BadMaxIndex<DummyTag>::value == 2, ""); // Fails: value is 1.
Yes, BadMaxIndex<DummyTag, 0, false> will upgrade to BadMaxIndex<DummyTag, 0, true> once a type is set at index 0. However, BadMaxIndex<DummyTag, 0, true> will now always return 1, since that's encoded into the instance body.
This isn't too bad. Ignoring the upcoming obstacles, we can generate the appropriate unique instances by including the next checker as a type in the default argument.
template <
typename Tag,
size_t n = 0,
bool isSet = IndexIsSet(Index<Tag, n>{})
typename Next = GoodMaxIndex<Tag, n + 1>
>
struct GoodMaxIndex {
static constexpr size_t value = BadMaxIndex<Tag, n + 1>::value;
};
template <typename Tag, size_t n>
struct GoodMaxIndex<Tag, n, false> {
static constexpr size_t value = n;
};
This will make GoodMaxIndex<Tag, 0> upgrade past 1 once index 1 is set, since it's actually 2 different types--GoodMaxIndex<Tag, 0, true, GoodMaxIndex<Tag, 1, false, void>> and GoodMaxIndex<Tag, 0, true, GoodChecker<Tag, 1, true, GoodMaxIndex<Tag, 2, false, void>>>.
The recursion name and the default template arguments have to be declared before we set the default template arguments. This is easier said than done.
// RecurseInfinitely1 isn't declared yet, so we can't use it as a default.
template <typename Next = RecurseInfinitely1<>>
struct RecurseInfinitely1 {};
template <typename Next>
struct RecurseInfinitely2;
// RecurseInfinitely2's template is declared without default arguments, so we can't leave the template parameters blank.
template <typename Next = RecurseInfinitely2<>>
struct RecurseInfinitely2 {};
However, by making a default template argument depend on a previous template parameter, we can postpone needing the recursion name until we actually instantiate the template. One of the simplest ways I found to structure this is by wrapping the template in an outer struct, and using that struct as a template parameter.
struct Outer {
template <
typename OuterType = Outer,
typename Next = typename OuterType::template RecurseInfinitely<>
>
struct RecurseInfinitely{};
};
One last major obstacle to solve! we still somehow need to have a termination condition within the template parameter's default arguments. std::conditional_t might seem like a useful option here, since it selects a type based on a condition, but it isn't enough.
struct Outer {
template <
typename OuterType = Outer,
bool keepRecursing = true,
typename Next = std::conditional_t<
keepRecursing,
// Forces endless recursion.
typename OuterType::template RecurseOnce<OuterType, false>,
void
>
>
struct RecurseOnce {};
};
auto obj = Outer::RecurseOnce<>{};
Even though the discarded type won't be used, it's still evaluated. This means we infinitely evaluate nested RecurseOnce types, which won't compile.
Ideally, what we'd like to do is use two different sets of template parameters depending on whether we want to recurse or not.
// Pick this set of parameters when keepRecursing is false
template <
typename OuterType = Outer,
bool keepRecursing = false,
typename Next = void
>
struct RecurseOnce {};
// Pick this set of parameters when keepRecursing is true
template <
typename OuterType = Outer,
bool keepRecursing = true,
typename Next = typename OuterType::template RecurseOnce<OuterType, false>
>
struct RecurseOnce {};
The good news is, we can do this by splitting the template in 2! Outer can be templated to now serve the additional purpose of offering different definitions of RecurseOnce, depending on whether the recursion condition is still met or not.
template<bool keepRecursing = true>
struct Outer {
template <typename = void> // Still need some template to keep signature consistent.
struct RecurseOnce {};
};
template<>
struct Outer<true> {
template <
typename NextOuterType = Outer<false>,
typename Next = typename NextOuterType::template RecurseOnce<>
>
struct RecurseOnce {};
};
auto obj = Outer<>::RecurseOnce<>{};
With all our major obstacles cleared, we're ready to implement MaxIndex! To start with, let's re-add the tag and base keepRecursing on if that index is set.
template<
typename Tag,
size_t n = 0,
bool keepRecursing = IndexIsSet(Index<Tag, n>{})
>
struct Outer {
template <typename = void>
struct Recurse {};
};
template<typename Tag, size_t n>
struct Outer<Tag, n, true> {
template <
typename NextOuterType = Outer<Tag, n + 1>,
typename Next = typename NextOuterType::template Recurse<>
>
struct Recurse{};
};
Next, let's actually get information out of the template parameters, by changing our Recurse struct to a value constexpr that returns n if we've hit the max, or recurses upwards if the max has not yet been hit. We'll also rename Outer to the more descriptive MaxIndex.
template<
typename Tag,
size_t n = 0,
bool keepRecursing = IndexIsSet(Index<Tag, n>{})
>
struct MaxIndex {
template <typename = void>
static constexpr size_t value = n;
};
template<typename Tag, size_t n>
struct MaxIndex<Tag, n, true> {
template <
typename NextType = MaxIndex<Tag, n + 1>,
size_t maxValue = NextType::template value<>
>
static constexpr size_t value = maxValue;
};
Note that typename Next has changed to size_t maxValue, but that's okay--we're still generating new templates every time the stateful typelist is changed, since maxValue will increment each time.
We can now finally test our struct, and we're in for a surprise: GCC and MSVC work correctly, but Clang fails!
struct DummyTag;
static_assert(MaxIndex<DummyTag>::value<> == 0, "");
auto obj0 = TypeSetter<DummyTag, 0, int>{};
static_assert(MaxIndex<DummyTag>::value<> == 1, "");
auto obj1 = TypeSetter<DummyTag, 1, int>{};
static_assert(MaxIndex<DummyTag>::value<> == 2, ""); // Clang returns 1 instead of 2.
This comes down to a difference in the way the compilers evaluate our defaulted NextType. GCC and MSVC will re-evaluate NextType's default type every time the template is instantiated. Clang will evaluate the default type for NextType the first time the enclosing MaxIndex is instantiated, then keep using that type every time value is instantiated with default arguments. Fortunately, we can force NextType to be evaluated every time by having it depend on an earlier default template argument. Even better, the whole reason we had NextType in the first place was to force maxValue to be reevaluated every time. By adding a different, safe-for-Clang-to-keep-constant first parameter that maxValue will depend on, we can eliminate NextType entirely.
template<
typename Tag,
size_t n = 0,
bool keepRecursing = IndexIsSet(Index<Tag, N>{})
>
struct MaxIndex {
template <typename = void>
static constexpr size_t value = n;
};
template<typename Tag, size_t n>
struct MaxIndex<Tag, n, true> {
template <
size_t m = n + 1,
size_t maxValue = MaxIndex<Tag, m>::template value<>
>
static constexpr size_t value = maxValue;
};
We're finally done! Due to the tricky rules of re-evaluating default parameters, these 19 lines of code have the most involved logic behind them. From here, things will be way easier.
With the utility structures done, we're now ready to write the code to append and retrieve the stateful typelist!
We'll start with appending to the typelist, which feels trivial compared to the gauntlet we just ran with MaxIndex.
template<
typename Tag,
typename T,
size_t n = MaxIndex<Tag>::template value<>,
typename = decltype(TypeSetter<Tag, n, T >{})
>
void AddType() {}
A few things might stand out here. First, since we know the n will make each parameter unique, why not move TypeSetter into the body of the function? This is because for function templates, the compiler is allowed to implement the body of the function any time, from the point the instance is first used, to the end of the translation unit. This means that the side-effects of instantiating TypeSetter could be delayed until way later, which is not what we want--we need to be able to rely on the side effects being visible right away. By moving TypeSetter from the function body to a default parameter, we ensure it will be instantiated right after AddType is called.
Second, the decltype around the constructed TypeSetter might seem superfluous, but it's actually necessary. As a template, TypeSetter doesn't get instantiated until there's a context that needs the completely-defined type. Just using typename = TypeSetter<Tag, n, T> wouldn't hit this context, so we need to construct the type to force the context, then decltype the constructed object to bring the expression back to a type.
Finally, why make AddType a function template instead of a class template? This goes back to the previous explanation. If AddType were a type, we would add more layers of classes that might accidentally not be instantiated, so keeping AddType as a function makes it harder to misuse.
Getting the stateful typelist is not too complicated either.
template<typename Tag, size_t n>
struct ListGetter {
using type = decltype(
typename ListGetter<Tag, n - 1>::type{}.
append(GetType(Index<Tag, n - 1>{}))
);
};
template<typename Tag>
struct ListGetter<Tag, 0> {
using type = Typelist<>;
};
template <typename Tag, size_t n = MaxIndex<Tag>::template value<>>
using ListGetter_t = typename ListGetter<Tag, n>::type;
Note that unlike AddType, ListGetter is a class template. This is because ListGetter doesn't have any side-effects, so we don't need to ensure the type gets instantiated in unevaluated contexts.
By taking in n as a template parameter, we don't need to do any of the fancy re-evaluation MaxIndex did. We just always have ListGetter<Tag, 3> append to ListGetter<Tag, 2> and so on. This also makes it easy to terminate the recursion by specializing ListGetter<Tag, 0> to return a blank typelist. Finally, we add a convenience alias to get the type, and make sure we default n to MaxIndex<Tag> so all the user has to do is type ListGetter_t<Tag> to get an up-to-date stateful typelist.
With this, we finally have a complete stateful typelist implementation! Next, let's showcase it by using it in the template tracker.
The end is in sight--we're finally writing the class we used in the example!
Starting with the easy part, we can have unique types for each system and each operation by making a class template with nested classes to represent the operation types. We don't even need to define the nested classes, since we're just using them as identifiers.
template <typename Identifier>
struct TemplateTracker {
private:
struct GetComponentTag;
struct RemoveComponentTag;
};
Now for the actual functions.
struct TemplateTracker {
// ...
public:
template <typename Component, typename = decltype(AddType<GetComponentTag, Component>())>
static Component& GetComponent(size_t /*entityIndex*/) {
// Return a dummy component to illustrate example.
static Component component;
return component;
}
template <typename Component, typename = decltype(AddType<RemoveComponentTag, Component>())>
static void RemoveComponent(size_t /*entityIndex*/) {}
};
Just like with AddType, we need to make sure our side-effects happen in the default template arguments, otherwise we might not see the changes to our stateful typelist until it's too late!
Since these are demo functions, they don't do much, but there are no limitations. The parameters, template parameters, and body can be extended however needed.
And with this, we're 99% of the way there! All that's left now is to add a type alias to get the stateful typelists, and our final piece of the puzzle, the TemplateTracker, is complete.
struct TemplateTracker {
// ...
template <
typename GetComponentTagType = GetComponentTag,
typename RemoveComponentTagType = RemoveComponentTag,
size_t getComponentTypesN = MaxIndex<GetComponentTagType>::template value<>,
size_t removeComponentTypesN = MaxIndex<RemoveComponentTagType>::template value<>
>
struct Info {
using GetComponentTypes = ListGetter_t<GetComponentTag, getComponentTypesN>;
using RemoveComponentTypes = ListGetter_t<RemoveComponentTag, removeComponentTypesN>;
};
};
Like before, the max indices for stateful typelist must be default template arguments, so the template instances can be different as new types are appended. GetComponentTagType and RemoveComponentTagType are there so that getComponentTypesN and removeComponentTypesN depend on them. Otherwise, like with MaxIndex, Clang will reuse the previous default arguments, making getComponentTypesN and removeComponentTypesN fail to update as the stateful typelists change.
Having both GetComponentTagType and removeComponentTagType might seem excessive. Maybe we could just have TemplateTrackerType, and do something like this?
template <
typename TemplateTrackerType = TemplateTracker,
size_t getComponentTypesN = MaxIndex<TemplateTracker::GetComponentTag>::template value<>,
size_t removeComponentTypesN = MaxIndex<TemplateTracker::RemoveComponentTag>::template value<>
>
struct Info {/*...*/};
Unfortunately, GCC does not allow dependent default arguments to access private members, so the main choices we have are to either take in all the private types as default arguments, or make the types public.
Finally, we're done. Everything is implemented, and we can now track templates!
So how should we use TemplateTracker? I prefer keeping all the template calls for a particular tracker in one function, as this makes it easy to know when to get the stateful typelist: after the function is declared. If possible, having that function be defined in a .cpp means there's no risk anyone can accidentally define the function twice and duplicate insertions.
A consequence of this is that the compile-time type list is only available to that .cpp. If other code wants to know what types were being accessed, the tracking .cpp will have to convert the compile-time types to some kind of run-time information, like a type ID.
// ***physics_system.h***
struct PhysicsSystem : public GameSystem {
// Templates will be tracked in the .cpp, but unavailable to anyone including the header.
virtual void Act() const override;
// Use functions to let the .cpp convert compile-time type info to run-time type info.
virtual std::vector<ID> GetAccessedTypeIDs() const override;
};
For using the template tracker, we could just declare and use it in the function. This prevents the template tracker from even being exposed in the header.
// ***physics_system.cpp***
namespace{ using Tracker = TemplateTracker<PhysicsSystem>; }
void PhysicsSystem::Act() const {
for (size_t id : GetPhysicsEntities()) {
const Velocity& velocity = Tracker::GetComponent<const Velocity>(id);
Position& position = Tracker::GetComponent<Position>(id);
position += velocity;
}
}
// Compile-time info on which types were used with each function.
static_assert(std::is_same<
Tracker::Info<>::GetComponentTypes,
Typelist<const Velocity, Position>
>::value, "");
std::vector<ID> PhysicsSystem::GetAccessedTypeIDs() const {
// Outputs vector with Velocity and Position type IDs.
return GetTypeIDs(Info<>::GetComponentTypes{});
}
Alternatively, we could inherit PhysicsSystem from TemplateTracker. This has the advantage of making the class declaration be the only place that considers the template tracker. Everywhere else, the code being used looks like regular function templates and type aliases. Protected inheritance would stop any code outside of PhysicsSystem from accessing the stateful typelist.
// ***physics_system.h***
struct PhysicsSystem :
public GameSystem,
protected TemplateTracker<PhysicsSystem> // Added inheritance
{
// ...
friend void Check();
};
// ***physics_system.cpp***
void PhysicsSystem::Act() {
for (size_t id : GetPhysicsEntities()) {
const Velocity& velocity = GetComponent<const Velocity>(id);
Position& position = GetComponent<Position>(id);
position += velocity;
}
}
std::vector<const char*> PhysicsSystem::GetAddedComponents() {
return GetTypeNames(Info<>::GetComponentTypes{});
}
// ...
// Can only use PhysicsSystem::Info<> from within PhysicsSystem or friends now.
void Check() {
static_assert(std::is_same<
PhysicsSystem::Info<>::GetComponentTypes,
Typelist<const Velocity, Position>
>::value, "");
}
Just as TemplateTracker is trivial to use, so too is it easy to misuse! The main risk is creating an ambiguous stateful typelist. This can happen in a few ways:
template <typename Tag, typename T>
void BlankOutComponent(size_t id) {
TemplateTracker<Tag>::GetComponent<T>(id) = T{};
}
void ZeroVelocity(size_t id) {
BlankOutComponent<Physics, Velocity>(id);
}
// Ambiguous! May or may not have added Velocity to PhysicsInfo,
// since BlankOutComponent<Physics, Velocity> could have a point of instantiation after this line.
using PhysicsInfo = TemplateTracker<Physics>::Info<>
// ***a.h***
inline DampenVelocity(size_t id) {
TemplateTracker<Physics>::GetComponent<Velocity>(id) *= 0.995f;
}
// ***b.h***
inline std::vector<ID> GetPhysicsTypeIDs() const {
return GetTypeIDs(TemplateTracker<Physics>::Info<>::GetComponentTypes{});
}
// ***ab.cpp***
#include <a.h>
#include <b.h>
// Ambiguity #1: GetPhysicsTypeIDs() is a function that returns Typelist<Velocity>.
auto ids = GetPhysicsTypeIDs();
// ***b.cpp***
#include <b.h>
// Ambiguity #2: GetPhysicsTypeIDs() is a function that returns Typelist<>.
auto ids = GetPhysicsTypeIDs();
The safest way I've found to avoid these pitfalls is to:
(3) Can be worked around using a variety of tricks, but given how hacky this can be, I'll save that explanation for another article if people are interested.
Given that different projects have different risk tolerances, I can't really tell you whether it's safe to use these techniques in your project. I can, however, offer some details that can help you decide whether you want use this code:
TemplateTracker::Info<> in headers. However, if a new engineer isn't aware of these rules, it's easy for them to do so accidentally. Worse, since some misuses of TemplateTracker result in Ill-Formed, No Diagnostics Needed (IFNDR) programs, it's possible for a new dev to sneak in ill-formed code without anyone realizing.Thanks again!
Here is the full implementation, with a use-case. It should work unedited with any compiler / flags listed in the intro.
#include <stddef.h> // size_t
template <typename... Ts>
struct Typelist {
template <typename... Us>
auto Append(Typelist<Us...>) {
return Typelist<Ts..., Us...>{};
}
};
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 4514 ) // Unreferenced inline function
#endif
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnon-template-friend"
#endif
template<typename Tag, size_t n>
struct Index {
friend constexpr auto GetType(Index);
};
template<typename Tag, size_t n, typename T>
struct TypeSetter {
friend constexpr auto GetType(Index<Tag, n>) {
return Typelist<T>{};
}
};
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
constexpr bool IndexIsSet(...) {
return false;
}
template <typename IndexType>
constexpr auto IndexIsSet(IndexType) -> decltype(GetType(IndexType{}), bool{}) {
return true;
}
#ifdef _MSC_VER
#pragma warning( pop )
#endif
template<
typename Tag,
size_t n = 0,
bool keepRecursing = IndexIsSet(Index<Tag, n>{})
>
struct MaxIndex {
template <typename = void>
static constexpr size_t value = n;
};
template<typename Tag, size_t n>
struct MaxIndex<Tag, n, true> {
template <
size_t m = n + 1,
size_t maxValue = MaxIndex<Tag, m>::template value<>
>
static constexpr size_t value = maxValue;
};
template<
typename Tag,
typename T,
size_t n = MaxIndex<Tag>::template value<>,
typename = decltype(TypeSetter<Tag, n, T >{})
>
void AddType() {}
template<typename Tag, size_t n>
struct ListGetter {
using type = decltype(
typename ListGetter<Tag, n - 1>::type{}.
Append(GetType(Index<Tag, n - 1>{}))
);
};
template<typename Tag>
struct ListGetter<Tag, 0> {
using type = Typelist<>;
};
template <typename Tag, size_t n = MaxIndex<Tag>::template value<>>
using ListGetter_t = typename ListGetter<Tag, n>::type;
template <typename Identifier>
struct TemplateTracker {
private:
struct GetComponentTag;
struct RemoveComponentTag;
public:
template <typename Component, typename = decltype(AddType<GetComponentTag, Component>())>
static Component& GetComponent(size_t /*entityIndex*/)
{
// Return a dummy component to illustrate example.
static Component component;
return component;
}
template <typename Component, typename = decltype(AddType<RemoveComponentTag, Component>())>
static void RemoveComponent(size_t /*entityIndex*/) {}
template <
typename GetComponentTagType = GetComponentTag,
typename RemoveComponentTagType = RemoveComponentTag,
size_t getComponentTypesN = MaxIndex<GetComponentTagType>::template value<>,
size_t removeComponentTypesN = MaxIndex<RemoveComponentTagType>::template value<>
>
struct Info {
using GetComponentTypes = ListGetter_t<GetComponentTag, getComponentTypesN>;
using RemoveComponentTypes = ListGetter_t<RemoveComponentTag, removeComponentTypesN>;
};
};
// ***misc.h***
#include <vector>
// Dummy structs and operators.
struct Velocity {};
struct Position {};
struct Mesh {};
struct Damage {};
struct HitPoints {};
Position& operator += (Position& lhs, const Velocity&) { return lhs; }
HitPoints& operator -= (HitPoints& lhs, const Damage&) { return lhs; }
// Dummy functions for getting entity IDs.
std::vector<size_t> GetPhysicsEntities()
{
return std::vector<size_t>{0, 1, 2};
}
std::vector<size_t> GetGraphicsEntities()
{
return std::vector<size_t>{0, 1, 2};
}
std::vector<size_t> GetHealthEntities()
{
return std::vector<size_t>{0, 1, 2};
}
// Dummy global functions.
void Render(const Position&, const Mesh&) {}
enum class ID : size_t
{
UNKNOWN = 0,
VELOCITY,
POSITION,
MESH,
DAMAGE,
HIT_POINTS
};
template <typename T>
constexpr ID TypeID = ID::UNKNOWN;
template <typename T>
constexpr ID TypeID<const T> = TypeID<T>;
template <>
constexpr ID TypeID<Velocity> = ID::VELOCITY;
template <>
constexpr ID TypeID<Position> = ID::POSITION;
template <>
constexpr ID TypeID<Damage> = ID::DAMAGE;
template <>
constexpr ID TypeID<HitPoints> = ID::HIT_POINTS;
template <typename... Ts>
std::vector<ID> GetTypeIDs(Typelist<Ts...>) {
return std::vector<ID>{ TypeID<Ts>... };
}
// ***game_system.h***
struct GameSystem
{
virtual ~GameSystem() = default;
virtual const char* GetName() const = 0;
virtual void Act() const = 0;
virtual std::vector<ID> GetAccessedTypeIDs() const = 0;
};
// ***physics_system.h***
struct PhysicsSystem : public GameSystem, protected TemplateTracker<PhysicsSystem>
{
virtual const char* GetName() const override { return "physics"; }
virtual void Act() const override;
virtual std::vector<ID> GetAccessedTypeIDs() const override;
};
// ***physics_system.cpp***
void PhysicsSystem::Act() const
{
for (size_t id : GetPhysicsEntities())
{
const Velocity& velocity = GetComponent<const Velocity>(id);
Position& position = GetComponent<Position>(id);
position += velocity;
}
}
std::vector<ID> PhysicsSystem::GetAccessedTypeIDs() const
{
// TUs that call GetComponent() have compile-time info that lists all instances called.
static_assert(std::is_same<Info<>::GetComponentTypes, Typelist<const Velocity, Position>>::value, "");
// Run-time info can be returned for other TUs to use.
return GetTypeIDs(Info<>::GetComponentTypes{});
}
// ***graphics_system.h***
struct GraphicsSystem : public GameSystem, protected TemplateTracker<GraphicsSystem>
{
virtual const char* GetName() const override { return "graphics"; }
virtual void Act() const override;
virtual std::vector<ID> GetAccessedTypeIDs() const override;
};
// ***graphics_system.cpp***
void GraphicsSystem::Act() const
{
for (size_t id : GetGraphicsEntities())
{
Render(
GetComponent<const Position>(id),
GetComponent<const Mesh>(id)
);
}
}
std::vector<ID> GraphicsSystem::GetAccessedTypeIDs() const
{
static_assert(std::is_same<Info<>::GetComponentTypes, Typelist<const Position, const Mesh>>::value, "");
return GetTypeIDs(Info<>::GetComponentTypes{});
}
// ***health_system.h***
struct HealthSystem : public GameSystem, protected TemplateTracker<HealthSystem>
{
virtual const char* GetName() const override { return "health"; }
virtual void Act() const override;
virtual std::vector<ID> GetAccessedTypeIDs() const override;
};
// ***health_system.cpp***
void HealthSystem::Act() const
{
for (size_t id : GetHealthEntities())
{
HitPoints& hitPoints = GetComponent<HitPoints>(id);
const Damage& damage = GetComponent<const Damage>(id);
hitPoints -= damage;
RemoveComponent<Damage>(id);
}
}
std::vector<ID> HealthSystem::GetAccessedTypeIDs() const
{
static_assert(std::is_same<Info<>::GetComponentTypes, Typelist<HitPoints, const Damage>>::value, "");
static_assert(std::is_same<Info<>::RemoveComponentTypes, Typelist<Damage>>::value, "");
return GetTypeIDs(Info<>::GetComponentTypes{});
}
// ***main.cpp***
#include <iostream>
bool SystemsShareResources(const GameSystem& system1, const GameSystem& system2)
{
// Quick-and-dirty overlap check.
for(ID id1 : system1.GetAccessedTypeIDs())
{
for (ID id2 : system2.GetAccessedTypeIDs())
{
if(id1 == id2)
{
return true;
}
}
}
return false;
}
void PrintSystemOverlapState(const GameSystem& system1, const GameSystem& system2)
{
const char* result = SystemsShareResources(system1, system2) ? " CANNOT" : " CAN";
std::cout << system1.GetName() << " and " << system2.GetName() << result << " call Act() at the same time." << std::endl;
}
int main()
{
PhysicsSystem physicsSystem;
GraphicsSystem graphicsSystem;
HealthSystem healthSystem;
// Runtime checks for TUs that don't observe calls to GetComponent().
PrintSystemOverlapState(physicsSystem, graphicsSystem); // Cannot overlap.
PrintSystemOverlapState(physicsSystem, healthSystem); // Can overlap.
PrintSystemOverlapState(healthSystem, graphicsSystem); // Can overlap.
}