Adding elements to arrays and changing variables during compilation – imperative meta-metaprogramming in C++
C++ metaprogramming is a purely functional programming language. The outputs of functions depend only on their inputs and calling functions never changes anything, only create output. This lack of side effects significantly reduces the chance that errors are made, to the point where code that compiles usually does what it is supposed to do. However, there is a catch: all these statements are false.
Around 2014, Alexandr Poltavsky has found a loophole that allows using side effects in C++. He used it to add reflection to C++14, something that isn’t possible otherwise without structured binding in C++17 combined with an extremely repetitive header. Because of his article‘s brevity in explaining such an advanced problem, I have written a more detailed description. This is known as Defect Report 2118: Stateful metaprogramming via friend injection, and as its name suggests, it’s not meant to be a part of C++, just like Turing-complete metaprogramming was not meant to be. However, since 2015, no mechanism of prohibiting it was discussed.
This shows that merely saving one constant variable and accessing it later is enough to achieve what is otherwise impossible. But I decided to go further. How about making an expandable array? How about making the values mutable?
How does stateful metaprogramming via friend injection work?
This part is a summary of the article linked in the introduction for the case if you are lazy to read it.
The basic idea is to declare a function and then define it as a friend function of a template class. The definition of the declared function will depend on the template arguments of the class.
// Declaration
constexpr int whatIsHere();
// Helper class
template <int result>
struct Setter {
// Definition depending on the template argument
friend constexpr int whatIsHere() {
return result;
}
// Accessing this will instantiate the template
constexpr static int assign = whatIsHere();
};
Then we can define the function as we want by instantiating the class with the intended template arguments:
Setter<3>::assign;
If it’s not set, the function is only forward-declared and causes linker errors. If it’s set more than once, multiple definition errors are produced. Accessing it is easy:
std::cout << whatIsHere() << std::endl;
However, just one global variable isn’t very useful. We can make it better. We can use function overloading for different argument types to create an associative array. In this case, forward declaration has to be done in a class and ADL (Argument-dependent lookup) is needed to find it when it’s not declared in global scope.
template <int index>
struct Tag {
// Forward declaration in a template class
constexpr friend int whatIsHere(Tag<index>);
};
// No significant changes to the definition
template <int index, int result>
struct Setter {
friend constexpr int whatIsHere(Tag<index>) {
return result;
}
constexpr static int assign = whatIsHere(Tag<index>());
};
The usage changes only a little:
Setter<1, 3>::assign; // In a completely different place std::cout << whatIsHere(tag<1>()) << std::endl;
Here is a more detailed description.
Okay, how can we do imperative programming with this?
First, we need a way to determine if a variable was set or not. This can be done with SFINAE, if the tested expression always suceeds with a defined function and is incorrect with a function that is only forward declared.
template <int index, typename SFINAE = void>
struct IsSet : std::false_type {};
template <int index>
struct IsSet<index, std::enable_if_t< (whatIsHere(Tag<index>()) * 0 == 0) >>
: std::true_type {};
If you start experimenting with this, you’ll find that the execution order is not linear, but depends on the way the templates are evaluated. It can be useful for learning how the evaluation is done, and its counterintuitiveness creates a risk of making errors. Here is a trap for the unwary:
std::cout << IsSet<3>::value << std::endl; Setter<3, 7>::assign; std::cout << IsSet<3>::value << std::endl;
It should output false and then true, right? Well, it doesn’t. Templates are evaluated only once, when they are first instantiated. That means the state is imprinted the first time it’s used and the imprint will be used when it’s used again. So it outputs false in both cases.
We need to add an extra template argument that would differ between invocations:
struct LocationMain; std::cout << IsSet<LocationMain, 3>::value << std::endl; // Assuming IsSet is changed accordingly
Checking if something was compiled
The code above will not work if some of the functions is not a template or not declared in a class as a friend. Either the condition will be an error (not compile-time evaluable) or it will be always false (detected as only forward declared too early).
We only need one template argument in this case, and it can be the struct used to identify what is being checked.
// The functionality
template <typename Occasion>
struct ForwardDeclarer {
constexpr friend bool canYouSeeMe(ForwardDeclarer<Occasion>*);
};
template <typename Occasion>
struct IsCompiled {
friend constexpr bool canYouSeeMe(ForwardDeclarer<Occasion>*) {
return true;
}
constexpr static int set =
canYouSeeMe(static_cast<ForwardDeclarer<Occasion>*>(nullptr));
};
template <typename Occasion, typename SFINAE = void>
struct IsDefined : std::false_type {};
template <typename Occasion>
struct IsDefined<Occasion, std::enable_if_t<
canYouSeeMe(static_cast<ForwardDeclarer<Occasion>*>(nullptr)) >>
: std::true_type {};
// Some common include
struct TurboencabulatorContext;
// Set as used (will warn about unused variable)
IsCompiled<TurboencabulatorContext>::set
// Check if used
std::cout << IsDefined<OccasionMain>::value << std::endl;
It can be used to verify if a header was included, which can be useful if there is a header with additional template specialisations that have heavy dependencies and the compiler outputs a large volume of vague errors if it’s needed but not included. There are easier ways to do it, though.
A niche use case can be when the executable size is constrained and some template overloads are heavy with a slower but lighter alternative, so a part of the code can use a cheaper version of the function if the heavier one isn’t already compiled.
An expanding array
This has to be implemented using recursion and typical functional programming. A class has a template specialisation that is active if a value at its index exists and contains the size of a specialisation with a greater index if that one also has a value at its index, otherwise it contains the index.
A critical functionality is learning its size.
template <int index = 0, typename SFINAE = void>
struct Sizer {
// This overload is selected if there is no value
// at this index, so it's just above the last
static constexpr int size = index;
};
template <int index>
struct Sizer<index, std::enable_if_t< (whatIsHere(Tag<index>()) * 0 == 0) >> {
// This overload is selected if there is a value at the index
static constexpr int size = Sizer<index + 1>::size;
};
Again, the result is imprinted from the first time it’s used, so it will need extra template arguments if it’s supposed to work multiple times. So let’s add some extra template arguments to make it more usable.
template <typename Context, int index = 0, typename SFINAE = void>
struct Sizer {
static constexpr int size = index;
};
template <typename Context, int index>
struct Sizer<Context, index, std::enable_if_t<
(whatIsHere(Tag<index>()) * 0 == 0) >> {
static constexpr int size = Sizer<Context, index + 1>::size;
};
Then, we need a push back operation. It’s quite trivial, because the previous code can find the free element with lowest index.
template <typename Context, int value>
constexpr int pushBack() {
return Setter<Sizer<Context>::size, value>::assign;
}
Iterating through elements has to be done through recursion. Although this can be done without C++17, if constexpr will help avoid some nasty syntax here. A lambda can be conveniently used as the loop’s block:
template <typename Context, typename Func, int position = 0>
void Iterate(const Func& function) {
if constexpr(position == Sizer<Context>::size) {
return;
} else {
function(whatIsHere(Tag<position>()));
Iterate<Context, Func, position + 1>(function);
}
};
Here’s how it can be used:
// Create a set of unique types to force new evaluations
template <auto Arg>
struct UsedInMain;
// Insertion
// Using the __LINE__ macro to easily get unique types
pushBack<UsedInMain<__LINE__>, 9>();
pushBack<UsedInMain<__LINE__>, 13>();
// Access
std::cout << Sizer<UsedInMain<__LINE__>, 0>::size << std::endl;
Iterate<UsedInMain<__LINE__>>([] (int number) {
std::cout << "There is: " << number << std::endl;});
Its output is:
2 There is: 9 There is: 13
What else can it do?
It doesn’t need to work only with integers. It’s based on C++ metaprogramming, so it can also work with types. The trick is to declare the return values of the whatIsHere functions auto and use the Setter‘s template to add an implementation that returns the type it’s supposed to store. However, although it works on GCC, Clang 8 and later seems to have problems with it. It can be worked around by always also storing a number in a similar function and checking for that one’s presence and using type erasure to make the functions wrap above the specific types, but it’s impractical.
Mutable variables can be implemented through expandable arrays. After a push back operation, there is a new last element. Accessing the last element is like reading the mutable variable, adding a new value to the back is like changing the variable.
template <typename Context>
constexpr int lastStored() {
return whatIsHere(Tag<Sizer<Context>::size - 1>());
}
Practical application
Most of these operations can be done during the program’s initialisation, because since C++17, template classes can have static inline variables whose initialisation can have side effects. Such an approach also works across compilation units and runs at the speed of C++. Most type arithmetic can be done by doing the type-specific parts using usual generics and then using type erasure so that some finishing touches could be done in runtime. The runtime cost may be a problem on embedded platforms with memory constraints. That is why the example is a compile-time self-registering factory.
#include <iostream>
#include <typeinfo>
// LIBRARY CODE
template <typename Base, int index>
struct SubclassIdentifier {
// Forward declarations findable through Argument Dependent Lookup
friend constexpr Base* getSubclass(SubclassIdentifier<Base, index>);
constexpr friend int getSubclassNumber(SubclassIdentifier<Base, index>);
};
// Class whose instantiations define the forward declared functions
// The pairs of functions represent an array of pairs of number and subclass creators
template <typename Base, int index, typename Subclass, int number>
struct SubclassSaver {
friend constexpr Base* getSubclass(SubclassIdentifier<Base, index>) {
return new Subclass;
}
// Due to being entirely constexpr, it can be used to check if it was actually defined
friend constexpr int getSubclassNumber(SubclassIdentifier<Base, index>) {
return number;
}
constexpr static int instantiator =
getSubclassNumber(SubclassIdentifier<Base, index>());
};
// Instantiates SubclassSaver with the right template parametres
template <typename Base, int index, typename Subclass,
int number, typename SFINAE>
struct SubclassAdder {
constexpr static int newSize = index +
0 * SubclassSaver<Base, index, Subclass, number>::instantiator;
};
// Template specialisation for indexes where the function is already defined
template <typename Base, int index, typename Subclass, int number>
struct SubclassAdder<Base, index, Subclass, number, std::enable_if_t<
(getSubclassNumber(SubclassIdentifier<Base, index>()) * 0 == 0) >> {
constexpr static int newSize = SubclassAdder<Base, index + 1,
Subclass, number, void>::newSize;
};
// Template class and specialisation for counting the instantiated functions
// Imprinted on first use and will keep returning the same value even if new
// ones are added later
template <typename Base, int index = 0, typename SFINAE = void>
struct SubclassCounter {
constexpr static int count = index;
};
template <typename Base, int index>
struct SubclassCounter<Base, index, std::enable_if_t<
(getSubclassNumber(SubclassIdentifier<Base, index>()) * 0 == 0) >> {
constexpr static int count = SubclassCounter<Base, index + 1>::count;
};
// Inheriting from this class calls SubclassAdder
template <typename Base, typename Subclass, int identifier, std::enable_if_t<
(SubclassAdder<Base, 0, Subclass, identifier, void>::newSize >= 0)
>* = nullptr>
struct Constructed {};
// Iterates through created functions and finds one where the number fits
// After the first call, no new definitions will be considered
template <typename Base, int index = 0>
Base* construct(int identifier) {
if constexpr(index == SubclassCounter<Base>::count) {
return nullptr;
} else {
if (getSubclassNumber(SubclassIdentifier<Base, index>())==identifier) {
return getSubclass(SubclassIdentifier<Base, index>());
} else {
return construct<Base, index + 1>(identifier);
}
}
}
// USAGE OF THE LIBRARY
struct Component {
virtual void tick() = 0;
virtual ~Component() = default;
};
class VoltageSensor : public Component,
Constructed<Component, VoltageSensor, 7> {
void tick() override {
std::cout << "I am a voltage sensor" << std::endl;
}
};
class SerialInput : public Component, Constructed<Component, SerialInput, 3> {
void tick() override {
std::cout << "I am a serial input" << std::endl;
}
};
int main() {
construct<Component>(3)->tick(); // SerialInput had number 3
construct<Component>(7)->tick(); // VoltageSensor is created
}
When inspecting this code through Godbolt with O3, it’s clear that only the results of the templates were used and the generated assembler code is very short. In the case of Clang, it’s even shorter than the C++ code.
Gotchas
This isn’t the way C++ was meant to be used, so it’s a even greater minefield than JavaScript. There are many places where it can surprise anyone:
- When a template is instantiated, instantiating it again with the same parametres will yield the same result even if the state has changed
- Clang 8 and newer causes a new group of problems,
autoreturn values are not allowed in the saved functions, references and const references cause SFINAE to fail - Only integers and types can be compared in SFINAE, other types like functions or string pointers can’t, causing it to fail
- The code has to be actually used for the functions to be instantiated, defining
constexprvariables is not enough, reliable usage is always-succeedig SFINAE or inconsequential additions to function results - Any non-template functions are compiled at the place where they are defined, compiling with old state if they are defined before changes are made, so any helper functions must be templates (unless the imprinting is intentional)
- The state is local to each compilation unit and becomes global only when used in non-template functions, so all content meant to be indexed this way has to be included to the source file with function where it’s used
