I’m currently in the process of writing my own c++ inspired embedded scripting language for the game engine I’m working on, and the current feature that I’m working is implementing templates. Hopefully it’ll make it so that engine ECS api code is much cleaner. Anyway, while working on this I realized that at some point I’m probably going to need to store a set of variables in a structure defined by a variable argument template, or in other words, something really similar to std::tuple.
Now, while I knew a fair amount of meta-programming for templates, how someone would unroll template argument packs into struct members was beyond me. You can’t exactly just expand the arg pack and expect it to work.
template<typename... Members>
struct Tuple
{
// This would be far too simple, how would we end up telling members apart?
Members... member;
}The thought process
The way that std::templates work is that you define them with an arbitrary number of arguments, then access those arguments using the std::get<index>(tuple) function, so this is the behavior we’re going to try to emulate.
First step is figuring out how to store arguments, so far my experience with variadic templates has mostly been in the realm of functions, and the solution there is almost always recursion. So, let’s just solve this with recursion… for structs!
template<typename... Args>
struct Tuple
{
struct MembersEnd {};
template<size_t index, typename M = void, typename... Membs>
struct TupleMembers
{
M member;
typename std::conditional<sizeof...(Membs) == 0, MembersEnd, TupleMembers<index + 1, Membs...>>::type nextMember;
static constexpr size_t getIndex() {return index;};
};
TupleMembers<0, Args...> members;
}This looks complicated (because it is) but it’s understandable once you know what’s going on. The Tuple struct is just a usable wrapper for the end user, while TupleMembers is where the magic happens. If you’ve coded with recursive template functions before, <typename M, typename… Membs> will look very familiar to you. To put it simply, when another instance of this template is used inside of itself and we pass Membs… to it, one type is always shaved off and stored in M, making it so that each layer of our template inception handles just one of our arguments until there’s not any left.
That’s the easy part to explain, but what is that std::conditional line doing? std::conditional lets you pass in a constexpr expression that returns a bool, and depending on the result the “type” typedef in the struct that it creates will be set to either the second or third template argument. By checking the size of the Membs pack, we can tell if this particular TupleMembers instance is the last member, or if we need to continue going down the rabbit hole. If it is the last member, we just use an empty struct as the last type to end the chain. The result of this is something that looks like a linked list, for example, if we created a Tuple that stores a bool, int, and float the resulting struct would look something like this:
struct Tuple<bool, int, float>
{
struct MembersEnd {};
struct TupleMembers<0, bool, int, float>
{
bool member;
struct TupleMembers<1, int, float>
{
int member;
struct TupleMembers<2, float>
{
float member;
MembersEnd nextMember;
} nextMember;
} nextMember;
} members;
}Now that we have a way to store our members, how do we access them in a user friendly way? The standard library uses the global get function, which I think is dumb, makes much more sense to have a member template function, so that’s what we’re going to do.
template<size_t index, typename Ret, typename T>
Ret& getMemberFromHolder(T& holder)
{
if constexpr(T::getIndex() == index)
return holder.member;
else
return getMemberFromHolder<index, Ret>(holder.nextMember);
};
template<size_t index>
ArgType<index, Args...>::type& getMember()
{
return getMemberFromHolder<index, typename ArgType<index, Args...>::type>(members);
}I decided to go with two functions, the getMember() function is the one that end users should be calling, while getMemberFromHolder should probably be a private function. For this experiment I’m too lazy to fix that. As you can see, this is where the getIndex() function comes into play. The hope is that the compiler will be smart enough to inline all of this and that in the end it’s as efficient as regular struct member access. One problem I ran into while creating this is that we need to know the return type of the function in advance, and we would only naturally find that after recursively searching for the right index, meaning we need another way. This means we get to do more struct recursion! Yay!
static constexpr int maximum(int a, int b)
{
if(a > b)
return a;
return b;
}
template<int index, typename A = void, typename... Args>
struct ArgType
{
using type = typename std::conditional<index == 0, A, typename ArgType<maximum(index - 1, 0), Args...>::type>::type;
};
//Manually define this one so we don't get infinite recursive template instantiation
template<typename T>
struct ArgType<0, T>
{
using type = T;
};We can use this struct to find the type of an arg at a given index. It’s what you wish was just Args[index] but a index operator would, of course, be too easy. It uses a very similar pattern to our member grabbing function. We just recursively reference the ::type defined by each struct instance, until the one instantiated when index equals 1 returns the type of the arg at it’s current index. We also need to make sure that index never goes below 0, or else we get infinite recursion, we also need to define what ArgType looks like when instantiated with only one argument, or the compiler complains for reasons.
Full test program
With all of that written, here’s a test .cpp file with everything in the right order for you to play around with if you want to:
#include <iostream>
static constexpr int maximum(int a, int b)
{
if(a > b)
return a;
return b;
}
template<int index, typename A = void, typename... Args>
struct ArgType
{
using type = typename std::conditional<index == 0, A, typename ArgType<maximum(index - 1, 0), Args...>::type>::type;
};
template<typename T>
struct ArgType<0, T>
{
using type = T;
};
template<typename... Args>
struct Tuple
{
struct MembersEnd {};
template<size_t index, typename M = void, typename... Membs>
struct TupleMembers
{
M member;
typename std::conditional<sizeof...(Membs) == 0, MembersEnd, TupleMembers<index + 1, Membs...>>::type nextMember;
static constexpr size_t getIndex() {return index;};
};
TupleMembers<0, Args...> members;
template<size_t index, typename Ret, typename T>
Ret& getMemberFromHolder(T& holder)
{
if constexpr(T::getIndex() == index)
return holder.member;
else
return getMemberFromHolder<index, Ret>(holder.nextMember);
};
template<size_t index>
ArgType<index, Args...>::type& getMember()
{
return getMemberFromHolder<index, typename ArgType<index, Args...>::type>(members);
}
};
int main() {
Tuple<bool, int, float> tuple;
tuple.getMember<2>() = 2.0f;
return 0;
}Wishful thinking
Imagine if instead c++ just had compile time syntax like “contexpr if” that you could use outside of functions bodies? Sort of like #ifdef statements but integrated directly into the grammar instead of the pre-processing step so they can be used in templates. This would all be so much easier, for example, what if all this could be done with a compile time evaluated unroll statement?
template<typename... Members>
struct Tuple
{
unroll Members(MemberT, index)
{
MemberT member##index;
}
}
void main()
{
Tuple<int, bool> tuple;
tuple.member1 = 5;
tuple.member2 = true;
}I’m honestly thinking about adding stuff like that to BraneScript, it would just make templates so much easier to build and debug. Would need to come up with a better way to generate variable ID’s than this hypothetical for sure tho.
Conclusion
When experimenting with this I wasn’t able to find a good example/tutorial of how this was implemented, I now realize that I could have looked a the standard library .h files, but we all know those were not meant for human eyes. So I hope this can serve that purpose for anyone else experimenting with this stuff. If you are, I wish you the best of luck!
