blaubart.com

Why C++ (is fun to me): template metaprogramming

Jul 1, 2017
/assets/images/blog/blog-post-0.jpg
Gilfoyle in "Two Days of the Condor" (S02E10, Silicon Valley)

If you need to expose a number of functions in C++ to an interface, template metaprogramming may be of tremendous help. This post outlines one such case. Here is the entire working code example (GCC’s optimizer is good enough to optimize all of the program away, that’s why the compiled version is blank!)

After having had the pleasure of programming in a variety of languages in very different projects, I can safely say that C++ is the one that strikes me the most.

This post will be about one of my favorite practical examples of the usefulness of template metaprogramming; if you’ve never heard of that before, I suggest reading up on the topic or watching these videos if you have some C++ experience already (part1, part2)

The problem

Imagine the following: you’re the author of an application server, written in C++, whose behaviour is supposed to be customized by its users via scripts. You’ve decided for a scripting language (that could be LUA, Ruby, …). Naturally you will want to expose a set of functions and data specific to your application to that scripting language, so your users can fully leverage the awesome stuff you’ve been working on for so long.

Depending on the actual scripting language, the way to do just that varies. Let’s focus on functions for now and assume you can register a function with the following C interface with the ScriptEngine:

/* 
   se is the instance of the script engine the user is using
   params is an array, the first member being a string that 
   uniquely identifies the function, the remaining members 
   being the parameters the user has passed into the call
*/
result_type MyFunction(ScriptEngine* se, const data_type* params) noexcept;

The call to actually register this function could look something like this:

ScriptEngine* se;

/*
  Register MyFunction with the name "MyFunction"
  (this will be the first member in the "params" array, see above)
*/
se->registerFunction(MyFunction, "MyFunction");

And the actual implementation of that function:

result_type MyFunction(ScriptEngine* se, const data_type* params) noexcept
{
  /*
    Now you will have to transform the parameters in "params"
    in a way that your actual implementation can accept them
  */
  auto result = MyFunctionImpl(params[1], params[2], params[3]);
  return static_cast<result_type>(result);
}

That doesn’t look too bad for now - but now imagine there are about 300 functions you’d like to register this way. You’d need to write 300 wrapper functions (just like MyFunction), possibly list them in a static array together with their unique string identifiers, eventually registering them one by one at runtime in a loop. This is not only tedious and boring but also terribly error-prone.

Possible approaches

Here’s a number of possible solutions you may come up with.

switch-statement

Instead of writing one wrapper function for each function you’d like to expose, you register a single wrapper function that contains a massive switch-statement, like this:

result_type MyFunction(ScriptEngine* se, const data_type* params) noexcept
{
  const char* str = params[0]; // taking the name of the function

  unsigned int hash_val = hash(str); // for easy switching

  switch (hash_val)
  {
    case hash("MyFunction"): // hash is a constexpr function

    {
      // implementation like above

    }
    case hash("OtherFunction"):
      // ...and so on

  }
}

This doesn’t solve the problem; you just moved all the annoying wrapper logic somewhere else and added some overhead with the switch-logic along the way.

The “hacker” way

Again, you only write a single wrapper function, in which you will take the parameters and push them onto the stack one by one (according to the calling convention in place), taking the corresponding function address (that you picked from a table using the string identifier as an index) and calling it. Obviously it only works if the data types passed through params are so trivial that they need no conversion logic, so you also need not be aware of the implementation function’s signature. It also requires that the params array is (null)-terminated.

This is plain bad (but still fun to implement, nevertheless) and due to the very platform-dependent nature of this, there’s not much point in providing a code example. You’ll probably have to fiddle with assembly and you will lose all of the safety a static function call provides as well.

Solution using TMP

And here’s how to do it the most elegant way (in my opinion): by creating a set of generic function templates that the compiler will use to instantiate a wrapper function for each script function you’d like to expose.

The entire solution is, due to the nature of templates in C++, rather verbose, so I will try to break it down to the most essential parts (without explaining all of the intricate details).

Some preparation

First off, we will need some way to reflect on our code - more specifically, the script functions we’d like to expose. To instantiate a wrapper function, we need the following information about it: its function address, its parameter types as well as its return value type. Here’s the structures and helper templates that will be used to capture this information:

template<typename T> struct sizeof_void { enum { value = sizeof(T) }; };
template<> struct sizeof_void<void> { enum { value = 0 }; };

template<typename T, size_t t> struct TypeChar { static_assert(!t, "Unsupported type in variadic type list"); };
template<typename T> struct TypeChar<T, sizeof(int)> { enum { value = 'i' }; };
template<> struct TypeChar<double, sizeof(double)> { enum { value = 'f' }; };
template<> struct TypeChar<char*, sizeof(char*)> { enum { value = 's' }; };
template<> struct TypeChar<void, sizeof_void<void>::value> { enum { value = 'v' }; };

template<typename... Types>
struct TypeString {
	static constexpr char value[sizeof...(Types) + 1] = {
		TypeChar<Types, sizeof(Types)>::value...
	};
};

template<typename R, typename... Types>
using Function = R(*)(Types...);

struct ScriptIdentity
{
	Function<void> addr;
	const char* types;
	const char ret;
	const unsigned int numargs;

	template<typename R, typename... Types>
	constexpr ScriptIdentity(Function<R, Types...> addr) : addr(reinterpret_cast<Function<void>>(addr)), types(TypeString<Types...>::value), ret(TypeChar<R, sizeof_void<R>::value>::value), numargs(sizeof(TypeString<Types...>::value) - 1) {}
};

struct ScriptFunction
{
	const char* name;
	const ScriptIdentity func;

	constexpr ScriptFunction(const char* name, ScriptIdentity func) : name(name), func(func) {}
};

Note that all of this data will exist only at compile-time; it will be instantiated so the compiler can use it in the wrapper function template later on.

There may be other or even better ways to do it, but I decided to encode the above-mentioned information as simple character values. TypeChar is the template that maps a type to a (unique) character that we can use later on. Every possible type that you are using in your script functions should have a TypeChar mapping. Provided above are examples for int, double, char* and void.

TypeString is an array of TypeChar - given a parameter pack Types, it will determine the character for each of the types provided.

ScriptIdentity holds all the information we need: types will contain the characters corresponding to the parameter types of the function, ret is a single character indicating the return type, and numargs is simply the number of parameters. The constructor of ScriptIdentity is templated so to allow extracting the parameter types and return type of a function passed to it as an argument.

And lastly, ScriptFunction adds some meta info about the function to it all that we will provide ourselves - for now, this is just a descriptive name.

Given this implementation, we can declare an array referencing all our script functions:

static constexpr ScriptFunction functions[] {
	{"MyFunction", MyFunction},
	{"OtherFunction", OtherFunction},
// ...

};

The glorious prospect: the only thing that will be necessary to create wrapper functions for any (or at least, the large majority) of your script functions will be to add them to the array above (and recompile). Isn’t that exciting?

(More) implementation

Given the structures defined in the previous section, we can now write a templated function that will be the basis for the compiler to generate a wrapper for each function we’d like to expose to the script engine. The signature of this function needs to be exactly the same as the one of MyFunction declared in the previous post.

Inside it, we need to perform the following essential steps:

  • Transform all the parameters we receive from the script engine from const data_type* to the types we need to call the script function
  • Call the script function with these transformed values
  • Receive the return value of this call and transform it to result_type

Let’s start off by defining a function template for converting a single parameter from the data_type array to a given type R. It can look like this:

// I is the index into params

template<typename R, unsigned int I>
struct extract_ {
	inline static R extract(ScriptEngine*&&, const data_type*&& params) noexcept {
		return static_cast<R>(forward<const data_type*>(params)[I]);
	}
};

Most likely, you will want to specialize this template for various R in case the conversion takes more than just a simple static_cast.

With this building block in place, we can move on to implementing the centerpiece: a templated function performing the call to the script function. Since the call will involve passing an arbitrary number of arguments of arbitrary types, we will be employing a variadic template. Variadic templates are one of the major new features of modern C++ you have to know!

template<unsigned int I, unsigned int F>
struct dispatch_ {
	template<typename R, typename... Args>
	inline static R dispatch(ScriptEngine*&& se, const data_type*&& params, Args&&... args) noexcept {
		constexpr ScriptFunction const& F_ = functions[F];
		return dispatch_<I - 1, F>::template dispatch<R>(forward<ScriptEngine*>(se),
		                                                 forward<const data_type*>(params),
		                                                 extract_<typename CharType<F_.func.types[I - 1]>::type, I>::extract(forward<ScriptEngine*>(se),
		                                                                                                                     forward<const data_type*>(params)),
		                                                 forward<Args>(args)...);
	}
};

template<unsigned int F>
struct dispatch_<0, F> {
	template<typename R, typename... Args>
	inline static R dispatch(ScriptEngine*&&, const data_type*&&, Args&&... args) noexcept {
		constexpr ScriptFunction const& F_ = functions[F];
		return reinterpret_cast<R(*)(...)>(F_.func.addr)(forward<Args>(args)...);
	}
};

The dispatch_ struct will be instantiated with I, which is the index of the next argument we will extract, and F which is the index into the constant expression functions array we declared earlier indicating which script function we will be calling in the end. The dispatch function contained within makes use of R which is the return type of the script function and Args, which is the parameter pack we are going to build by processing each argument recursively.

Initially, Args will be empty: while I is greater than zero, we will extract a single argument using extract, decrease I by one and instantiate dispatch_ again until we have extracted all arguments and I reaches zero. A specialization for dispatch_ exists for this particular case, effectively terminating the recursion; a pattern which is commonly used when programming with templates. In it, the actual call to the script function is performed and the return value of it given back to the caller.

Note that the arguments are extracted in reverse order: we start using the last (“rightmost”) one and stop with the first (“leftmost”). The script function is then, however, called with the arguments in the expected order.

CharType is a template which is essentially TypeChar with its mapping reversed: it is being used to map the argument type (which we encoded as a character) back into an actual type which will be forwarded to extract.

(side note: one major improvement I’d like to see in this implementation is replacing the ellipsis in the reinterpret_cast with a proper type. I believe it should be possible to instantiate this function type using the information we encoded in the ScriptFunction structure, but I haven’t attempted it yet)

Now we can wrap it up and specify a function having the MyFunction signature which I mentioned initially: quite simple now!

template<unsigned int F>
static result_type wrapper(ScriptEngine* se, const data_type* params) noexcept {
	auto result = dispatch_<functions[F].func.numargs, F>::template dispatch<typename CharType<functions[F].func.ret>::type>(forward<ScriptEngine*>(se), forward<const data_type*>(params));
	return static_cast<result_type>(result);
}

You may want to implement a template similar to extract which is performing a proper conversion from the type of result to result_type if necessary.

A gotcha, then: this will fail to compile if the script function’s return type is void. You can specialize this template with the help of enable_if / SFINAE to work around this.

Conclusion

I mentioned we’d end up only having to add a single line per script function to the functions array and recompile to be done. We didn’t achieve this yet! For automatically instantiating all the wrappers, we will let the compiler create another array containing them.

typedef result_type (*function_type)(ScriptEngine*, const data_type*);
constexpr auto functions_num = sizeof(functions) / sizeof(functions[0]);
using functions_seq = make_index_sequence<functions_num>;

struct ScriptWrapper
{
	const char* name;
	const function_type func;

	constexpr ScriptWrapper(const char* name, function_type func) : name(name), func(func) {}
};

template<size_t... Is>
static const ScriptWrapper* wrappers(index_sequence<Is...>) {
	static constexpr ScriptWrapper wrappers_[] {
		{functions[Is].name, wrapper<Is>}...
	};

	constexpr auto wrapped_num = sizeof(wrappers_) / sizeof(wrappers_[0]);
	static_assert(functions_num == wrapped_num, "Not all functions wrapped");
    
	return wrappers_;
}

We are using integer_sequence (C++14) to generate a series of indices based on the number of entries in functions, turning the sequence into a parameter pack Is and expanding it into a static array containing the wrapped functions. To retrieve this array at runtime (to register the contained wrapped functions with the script engine), you’d call wrappers(functions_seq()). It should be possible to implement this array without using a function returning it too if necessary.

This is it! Here is a full working implementation of everything described. It should compile fine using any C++14 compiler (I tried Clang 3.9). If you can suggest any improvements or have questions/comments, feel free to let me know on the GitHub repository. Thanks for reading!