Forem: Christian Daley

Virtual function templates with stateful metaprogramming in C++ 20: Part 2

Christian Daley — Sun, 25 Feb 2024 20:14:57 +0000

This post can also be read on my github blog

In part 1 of this series we learned how to implement a virtual function template with a variadic parameter pack. In this post we're going to expand on our code to allow for an arbitrary number of virtual function templates with different return types. And we'll do it all with one single vtable!

Generalizing the vtable functions

Our current vtable_func implementation looks like this:

template <typename... Args>
struct vtable_func
{
    template <typename Derived>
    static void run(Printer* printer, void* argsTuplePtr)
    {
        const auto bound = [&](Args&&... args)
        {
            static_cast<Derived*>(printer)->print(std::forward<Args>(args)...);
        };

        auto& argsTuple = *static_cast<std::tuple<Args&&...>*>(argsTuplePtr);

        std::apply(bound, std::move(argsTuple));
    }
};

Right now it's limited to calling the print function on the target object, but with some straightfoward changes we can make it able to call any member function. To start off we're going to rename the template parameter pack onvtable_func from Args to a more generic name Ts. The reason is because Ts is now going to represent the types of the template arguments for whatever function we're calling, and those are not necessarily the same thing as the types of the arguments to the function. For example:

template <typename... Ts>
void f(int i, double d, Ts&&... ts);

template <typename... Ts>
void g();

Here we have two different functions with template parameter packs Ts. The function f takes arguments of type (int, double, Ts&&...) and the function g takes no arguments. We need to be able to handle virtual functions like these where the types of the template arguments don't necessarily correspond to the types of the function arguments.

The second thing we'll do is add a new run_impl function to vtable_func that will help us generalize run. We can even make this new function private as a matter of good practice. run will pass its arguments to run_impl, but will additionally pass a pointer-to-member-function that is intended to be called. The return type R and parameter types Args of the member function can be deduced by the compiler.

template <typename Derived, typename R, typename... Args>
static void run_impl(R(Derived::* func)(Args...), Printer* printer, void* argsTuplePtr)
{
    const auto bound = std::bind_front(func, static_cast<Derived*>(printer));

    auto& argsTuple = *static_cast<std::tuple<Args&&...>*>(argsTuplePtr);

    std::apply(bound, std::move(argsTuple));
}

run_impl looks very similar to our original run function except for the extra R(Derived::* func)(Args...) parameter. This is a parameter named func that is a pointer to a member function of the Derived class. It takes arguments of type Args... and has return type R. The compiler is able to deduce Derived, Args and R based on whatever function we give to run_impl. For simplicity I've replaced the bound lambda with std::bind_front which does the same thing in only one line of code. Everything else is the same as before: we cast argsTuplePtr to the correct tuple type and then use std::apply to call bound with the arguments.

The run function itself becomes simple and our whole vtable_func struct looks like this:

template <typename... Ts>
struct vtable_func
{
private:
    template <typename Derived, typename R, typename... Args>
    static void run_impl(R(Derived::* func)(Args...), Printer* printer, void* argsTuplePtr)
    {
        const auto bound = std::bind_front(func, static_cast<Derived*>(printer));

        auto& argsTuple = *static_cast<std::tuple<Args&&...>*>(argsTuplePtr);

        std::apply(bound, std::move(argsTuple));
    }

public:
    template <typename Derived>
    static void run(Printer* printer, void* argsTuplePtr)
    {
        run_impl(&Derived::template print<Ts...>, printer, argsTuplePtr);
    }
};

run passes a pointer to whatever member function we want to call (currently just Derived::print<Ts...>) along with the pointer to the Printer and the pointer to the arguments tuple. run_impl is then responsible for invoking that function on the printer.

Adding a new virtual function template

Now we're able to run any arbitrary member function we want by passing it to run_impl. We already have a print function that prints the arguments to std::cout. Let's add a new print_to_stream function that will let us print to any std::ostream. First we'll add the implementation to PrinterImpl.

template <typename... Args>
void print_to_stream(std::ostream& stream, Args&&... args)
{
    ((stream << args << '\n'), ...);
}

Inside vtable_func::run we can invoke this new function just like we invoked print.

run_impl(&Derived::template print_to_stream<Ts...>, printer, argsTuplePtr);

But wait a minute! How is the run function supposed to know what function to call? It currently doesn't have enough information to know whether it should run print or print_to_stream. How do we fix this? With another template parameter of course!

Let's define an enum:

enum class Function
{
    Print,
    PrintToStream,
};

vtable_func will take a Function as a non-type template parameter in addition to the Ts parameter pack.

template <Function F, typename... Ts>
struct vtable_func

run uses it to determine which member function pointer it needs to pass to run_impl.

template <typename Derived>
static void run(Printer* printer, void* argsTuplePtr)
{
    if constexpr (F == Function::Print)
    {
        run_impl(&Derived::template print<Ts...>, printer, argsTuplePtr);
    }
    else if constexpr (F == Function::PrintToStream)
    {
        run_impl(&Derived::template print_to_stream<Ts...>, printer, argsTuplePtr);
    }
}

The final step is to use the correct Function case when pushing the vtable_func into the stateful_type_list. The original Printer::print function will now look like this:

template <typename... Args,
          size_t Index = stateful_type_list::try_push<vtable_func<Function::Print, Args...>>()>
void print(Args&&... args)

And Printer::print_to_stream is implemented like so:

template <typename... Args,
          size_t Index = stateful_type_list::try_push<vtable_func<Function::PrintToStream, Args...>>()>
void print_to_stream(std::ostream& stream, Args&&... args)
{
    auto argsTuple = std::forward_as_tuple(stream, std::forward<Args>(args)...);

    m_vtable[Index](this, &argsTuple);
}

Testing it out

Let's try out our new virtual function template! In main we'll call print_to_stream instead of print and see what happens.

auto p = make_printer();

double d = 2.5;
const std::string s = "Hello, world!";

p->print_to_stream(std::cerr, 5, d, s);

The output prints to cerr like we expect.

5
2.5
Hello, world!

Any number of virtual function templates can be supported by adding a new Function case and using it accodingly.

Supporting return values

We can have as many virtual function templates as we want, so let's figure out how to support returning values from these functions. We'll add a third function to our PrinterImpl class called print_to_string. We also need to add a corresponding PrintToString case to the Function enum.

template <typename... Args>
std::string print_to_string(Args&&... args)
{
    std::stringstream stream;

    ((stream << args << '\n'), ...);

    return stream.str();
}

We want to return a std::string from Printer::print_to_string but this is complicated by the fact that we use a single vtable for all of our functions and, in general, each function might have a different return type. One solution could be to have vtable_func::run return a std::variant of all the possible return types (using std::monostate to represent void) and then use std::get to grab the correct type in our Printer implementation. This would work just fine but it is potentially inefficient. Let's say that we have 10 virtual function templates and nine of them return small types like int or char but one of them returns a std::array<int, 1000>. Because std::variant must have a size that is at least as big as its largest possible type, this will force all of our functions to have a large return type and lead to unnecessay copying of data.

The more efficient solution is to have the caller of the vtable function provide the storage for the return type and then pass a pointer to that storage into the vtable function. We'll add a void* ret parameter to vtable_func::run and pass that through to run_impl.

template <typename Derived>
static void run(Printer* printer, void* argsTuplePtr, void* ret)
{
    if constexpr (F == Function::Print)
    {
        run_impl(&Derived::template print<Ts...>, printer, argsTuplePtr, ret);
    }
    else if constexpr (F == Function::PrintToStream)
    {
        run_impl(&Derived::template print_to_stream<Ts...>, printer, argsTuplePtr, ret);
    }
    else if constexpr (F == Function::PrintToString)
    {
        run_impl(&Derived::template print_to_string<Ts...>, printer, argsTuplePtr, ret);
    }
}

Inside run_impl we need to move the result of calling func into the storge provided by ret. We'll use a std::optional for the storage, so run_impl will cast ret from a void* to a std::optional<R>* and assign to it. We also need to have special logic for the case where the return type is void because we can't assign void to anything or create a std::optional<void>.

template <typename Derived, typename R, typename... Args>
static void run_impl(R(Derived::* func)(Args...), Printer* printer, void* argsTuplePtr, void* ret)
{
    const auto bound = std::bind_front(func, static_cast<Derived*>(printer));

    auto& argsTuple = *static_cast<std::tuple<Args&&...>*>(argsTuplePtr);

    if constexpr (std::is_same_v<R, void>)
    {
        std::apply(bound, std::move(argsTuple));
    }
    else
    {
        *static_cast<std::optional<R>*>(ret) = std::apply(bound, std::move(argsTuple));
    }
}

Printer::print and Printer::print_to_stream will be updated to pass a nullptr as the ret argument to the vtable function. This is safe because both of these functions return void so vtable_func::run_impl won't attempt to use the pointer. Printer::print_to_string is implemented like so:

template <typename... Args,
          size_t Index = stateful_type_list::try_push<vtable_func<Function::PrintToString, Args...>>()>
std::string print_to_string(Args&&... args)
{
    auto argsTuple = std::forward_as_tuple(std::forward<Args>(args)...);

    std::optional<std::string> ret;

    m_vtable[Index](this, &argsTuple, &ret);

    return std::move(*ret);
}

Let's verify that it works.

auto p = make_printer();

double d = 2.5;
const std::string s = "Hello, world!";

const auto str = p->print_to_string(5, d, s);

std::cout << str;

The output is what we expect.

5
2.5
Hello, world!

Play around with the code here: https://godbolt.org/z/Gsr1EKavz

View it on my github: https://github.com/christiandaley/examples/blob/main/cpp/virtual_function_templates-part-2/main.cpp

Final remarks

We've seen that supporting an arbitrary number of virtual function templates and different return types is quite straightforward. The amount of new code we added was pretty small and the only new type introduced was the Function enum.

It should be noted that our existing implementation does not support returning reference types because std::optional cannot contain a reference. This limitation is easily overcome by having an additional if constexpr case in run_impl and using a raw pointer instead of a std::optional to temporarily store the return value. The implementation of this is left as an exercise for the reader.

What's next?

At the end of part one I mentioned that these virtual function templates are unsafe to use across translation units because of ODR violations that result from stateful metaprogramming. I also teased that it may be possible to get around this limitation, and in part 3 that's exactly what we'll do.

Virtual function templates with stateful metaprogramming in C++ 20

Christian Daley — Mon, 19 Feb 2024 03:24:41 +0000

This post can also be read on my github blog: https://christiandaley.github.io/2024/02/18/virtual-function-templates-with-stateful-metaprogramming-in-c++-20.html

Virtual function templates are not possible in C++. Go ahead, try it yourself. No compiler will accept the following code:



struct Base
{
    template <typename T>
    virtual void do_something(T arg) = 0;

    virtual ~Base() = default;
};

struct Derived : Base
{
    template <typename T>
    void do_something(T arg) override
    {
        // do something
    }
};

The reason for this is simple: do_something is not a function, it is a function template. Because the compiler operates on translation units (source files) independently of each other, there's no possible way for it to know which specializations of print need to be instantiated and included in the vtable of Base and Derived. Assume that these structs are declared in some header file header.h, then consider the following code:



// foo.h
#include "header.h"
void foo(Base& base);



// foo.cpp
#include "foo.h"

void foo(Base& base)
{
    base.do_something(5);
}



// main.cpp
#include "foo.h"

int main()
{
    Derived derived{};
    foo(derived);
}

Here we attempt to create an instance of Derived in our main.cpp file and pass it to a function that's implemented in foo.cpp. In foo.cpp we invoke do_something<int>. The issue is that when derived is constructed in main.cpp the compiler must know exactly which specializations of do_something are needed so that they can be included in derived's vtable. But in order to get that information the compiler would need to look at foo.cpp while in the middle of compiling main.cpp (and, in general, would also need to examine every single other source file in the program) to see that do_something<int> is needed. C++ compilers cannot do this, and thus virtual function templates are not allowed.

It would be more accurate to say that virtual function templates are not part of the C++ standard and thus compilers don't need to do that sort of thing that would definitely be horrendous for compile times. My point is that there is no way to create virtual function templates in C++.

...

Or is there?

The goal

Forget trying to make virtual function templates work across translation units. In this post we're going to focus on achieving virtual function templates within the scope of a single source file. By the end of this post I'll show you that implementing the following code is completely possible by using some C++ black magic:



#include <iostream>

class Printer
{
public:
    template <typename... Args>
    void print(Args&&... args)
    {
        // ???
    }

    virtual ~Printer() = default;
};

class PrinterImpl : Printer
{
public:
    template <typename... Args>
    void print(Args&&... args)
    {
        ((std::cout << args << '\n'), ...);
    }
};

std::unique_ptr<Printer> make_printer()
{
    return std::make_unique<PrinterImpl>();
}

int main()
{
    auto p = make_printer();

    double d = 2.5;
    const std::string s = "Hello, world!";

    // calls PrinterImpl::print<int, double&, const std::string&> !!
    p->print(5, d, s);
}

Where to start?

If the compiler is unwilling to build a vtable for us, then we'll just have to do it ourselves.

But what should our vtable entries look like? I propose the following function signature:

void(*)(Printer*, void*)

In short, a vtable entry will be a function that takes a pointer to a Printer (the object that print is being called on) and a pointer to the arguments in the form of a void*. The vtable itself needs to be a collection of such functions, so our Printer class will have a member:

const std::span<void(*)(Printer*, void*)> m_vtable;

With that in mind, our implementation of Printer::print will look something like this:



template <typename... Args>
void print(Args&&... args)
{
    auto argsTuple = std::forward_as_tuple(std::forward<Args>(args)...);

    size_t vtableIndex = ???

    m_vtable[vtableIndex](this, &argsTuple);
}

All of the arguments are combined into a std::tuple so that they can be passed into the vtable function via a single void pointer. std::forward_as_tuple is used to preserve the reference type of each argument. Of course, this still leaves three massive questions that need to be answered:

Where are these vtable functions defined?
How is the index into the vtable for each specialization of Printer::print determined?
How is the m_vtable member created?

Defining the vtable functions

To start off we'll implement the vtable functions we need.



template <typename... Args>
struct vtable_func
{
    template <typename Derived>
    static void run(Printer* printer, void* argsTuplePtr)
    {
        const auto bound = [&](Args&&... args)
        {
            static_cast<Derived*>(printer)->print(std::forward<Args>(args)...);
        };

        auto& argsTuple = *static_cast<std::tuple<Args&&...>*>(argsTuplePtr);

        std::apply(bound, std::move(argsTuple));
    }
};

Let's go through this line by line:

We start off by declaring a new struct template called vtable_func that is templated on a parameter pack Args. As you can probably guess, Args corresponds to the types of arguments passed to Printer::print. It's not shown here but the definition of vtable_func exists within the scope of the Printer class.
vtable_func has a static function template called run. The Derived type parameter here represents the concrete, underlying type of the Printer object. In our code this will end up being PrinterImpl.
Inside run we create a lambda called bound. This lambda takes the expected arguments and forwards them to the implementation of print for the Derived type. We could have also used std::bind_front here.
We cast argsTuplePtr to a reference to its underlying type std::tuple<Args&&...>
We use std::apply to apply all of the arguments to our bound lambda, thus calling the desired print function with all of the expected arguments.

When Printer::print is called with some set of arguments of type Args&&... on some object of type Derived that inherits from Printer, we need to invoke the corresponding vtable_func<Args...>::run<Derived> function.

You may be wondering why I chose to have the Args parameter pack be defined on a struct template while the Derived template parameter is defined on the inner run function. Why not just get rid of the struct and have a function that looks like this:



template <typename Derived, typename... Args>
void run(Printer* printer, void* argsTuple)
{...

The need for separating the Args and Derived template parameters will become clear soon.

Getting the vtable index

So, we've written our vtable functions. On to the next challenge: how do we determine what index in the vtable corresponds to any particular specialization of Printer::print? After all, Printer::print<int, double> will need to have a different vtable entry than Printer::print<double, int> and we need to make sure that every specialization will end up calling the correct function.

Enter stateful metaprogramming.

Stateful metaprogramming

I could write multiple posts entirely about how stateful metaprogramming works, but there are already quite a few such articles scattered across the internet. If you're not already familiar with stateful metaprogramming I suggest you start by reading these excellent articles:

With that said, I'd like to introduce a very simple type_list implementation:



template <typename... Ts>
struct type_list
{
    template <typename... Us>
    constexpr auto operator+(type_list<Us...>) const noexcept
    {
        return type_list<Ts..., Us...>{};
    }

    template <typename... Us>
    constexpr bool operator==(type_list<Us...>) const noexcept
    {
        return std::is_same_v<type_list<Ts...>, type_list<Us...>>;
    }
};

It's just a simple struct that's templated on a parameter pack Ts. It serves one purpose and that is to "store" a list of types. type_list has a + operator that allows for concatenation of lists, and I also went ahead and defined a == operator that is able to conveniently tell us if two lists are equal. We can use these operators like so:



static_assert(type_list<int>{} + type_list<char>{} == type_list<int, char>{});

static_assert(type_list<>{} + type_list<double>{} == type_list<double>{});

static_assert(type_list<int, double>{} != type_list<double, int>{});

Now we'll use our type_list struct to implement a stateful type list:



struct stateful_type_list
{
private:
    template <size_t N>
    struct getter
    {
        friend consteval auto flag(getter);
    };

    template <typename T, size_t N>
    struct setter
    {
        friend consteval auto flag(getter<N>)
        {
            return type_list<T>{};
        }

        static constexpr size_t value = N;
    };

public:

    template <typename T, size_t N = 0>
    consteval static size_t try_push()
    {
        if constexpr (requires { flag(getter<N>{}); })
        {
            return try_push<T, N + 1>();
        }
        else
        {
            return setter<T, N>::value;
        }
    }

    template <typename Unique, size_t N = 0>
    consteval static auto get()
    {
        if constexpr (requires { flag(getter<N>{}); })
        {
            return flag(getter<N>{}) + get<Unique, N + 1>();
        }
        else
        {
            return type_list{};
        }
    }
};

And we can use it like so:



static_assert(stateful_type_list::get<decltype([]{})>() == type_list{});

static_assert(stateful_type_list::try_push<int>() == 0);

static_assert(stateful_type_list::try_push<double>() == 1);

static_assert(stateful_type_list::get<decltype([]{})>() == type_list<int, double>{});

I'm not going to fully explain how this code allows for state to be stored and retrieved at compile time as I'm assuming that you’ve already made yourself familiar with the posts I linked above. I will however explain several peculiarities in my implementation:

The try_push function returns the index in the list at which the new type was added. Types are always added at the end of the list.
We are unable to push the same type more than once. You can play around with it yourself to verify. This is because compilers memoize the results of consteval functions. We could get around this by also requiring an additional "Unique" template parameter each time we use the try_push function, but as it turns out we don't need to be able to push the same type more than once for our vtable implementation.
The get function requires a unique type to be supplied as a template argument each time it's called in order to avoid the aforementioned memoization. It forces the compiler to re-evaluate the get function each time we use it. That is what the decltype([]{}) in the above code is doing, as each lambda declaration is guaranteed to be a unique type.

Lambdas as NTTPs

I'd like to mention something important with regards to point number 3 above. It may be tempting to do something like this in order to alleviate the need to manually supply a new type each time you call get:



template <auto Unique = []{}, size_t N = 0>
static consteval auto get()

This actually works in practice (msvc, clang, and gcc all compile this as of 2/18/2024), but after some research I've found that the status of lambdas as non-type template parameters in C++20 and C++23 is a bit murky. Additionally it's not at all clear that the C++ standard would require this default template parameter to be re-evaluated at each call site. For example, a default template parameter of auto Line = std::source_location::current().line() will always be the line number of the template declaration, whereas an identical default argument will always be the line number of the call site. This suggests that a default template parameter is not required to behave as if it was explicitly provided at the call site. I want to avoid any sort of implementation defined behavior for the purpose of this post so I won't be using this trick.

Finishing the `Printer::print` implementation

With the help of our stateful_type_list we can finally finish implementing Printer::print.



template <typename... Args, 
          size_t Index = stateful_type_list::try_push<vtable_func<Args...>>()>
void print(Args&&... args)
{
    auto argsTuple = std::forward_as_tuple(std::forward<Args>(args)...);

    m_vtable[Index](this, &argsTuple);
}

vtable_func<Args...> is pushed into our stateful_type_list and the returned Index is used to lookup the corresponding function in the vtable. It's critically important that Index appears as a default template argument rather than being computed as part of the function body because this forces the compiler to compute the value of Index (and hence store vtable_func<Args...> in our stateful list) at the call site of Printer::print. The actual code generation of any particular specialization of Printer::print could happen at a later time in the compilation phase but we want our vtable_func pushed into our stateful_type_list ASAP.

We've accomplished two out of our three goals. The last thing we need to do is initialize the m_vtable member of our Printer class.

Creating the vtable

In order to initialize our vtable we'll start by writing a function that is capable of creating it. It will be a static function template that exists within the Printer class.



template <typename Derived, typename... Funcs> 
static auto create_vtable(type_list<Funcs...>)
{
    static constinit std::array vtable { Funcs::template run<Derived>... };

    return std::span{ vtable };
}

Let's break this down:

The template parameter Derived, as in other cases, corresponds to the underlying type of the Printer.
The parameter pack Funcs... will be our vtable_funcs that we pushed into our stateful_type_list in the Printer::print implementation.
The parameter of type type_list<Funcs...> is not named and not used. It exists so that the compiler can deduce the Funcs... parameter pack.
We create a static std::array of vtable entries, using CTAD so that we don't need to write std::array<void(*)(Printer*, void*)>, sizeof...(Funcs)>.
The vtable array is initialized with the function pointers run<Derived> for each vtable_func in Funcs. The template keyword is needed here to make the compiler happy.
We return a std::span that points to the array. This is safe because the array is static and will exist for the duration of the program.

For any index i, the function m_vtable[i] will be the correct function to handle the arguments passed to it by the Printer::print specialization that pushed a vtable_func at index i in the stateful_type_list. We can now utilize create_vtable within a protected constructor of Printer.



    template <typename Derived>
    Printer(Derived*) :
        m_vtable{ create_vtable<Derived>(stateful_type_list::get<Derived>()) }
    {}

The constructor has a template parameter Derived because the Printer needs to know its underlying type when it's creating the vtable. An unnamed dummy parameter of type Derived* is required so that the compiler can deduce the Derived type.
The type_list<Funcs...> argument passed to create_vtable is obtained by calling stateful_type_list::get to get the list of vtable functions. Derived is passed as the dummy "Unique" template argument to get to ensure that the compiler always re-evaluates get for each different child class of Printer that is used.

And that's it! The Printer class now has a constructor that initializes the vtable. The very last thing we need to do is call this constructor from our PrinterImpl default constructor.



PrinterImpl() :
    Printer{ this }
{}

Whew! We did it!

Does it work?

After all that effort we'd like to know if our code works! Let's run the following code that I showed at the beginning of this post:



std::unique_ptr<Printer> make_printer()
{
    return std::make_unique<PrinterImpl>();
}

int main()
{
    auto p = make_printer();

    double d = 2.5;
    const std::string s = "Hello, world!";

    p->print(5, d, s);

    return 0;
}

The output of the program when compiled with gcc 13.2, clang 17.01, and msvc 19.39 (all in c++ 20 mode) is:



5
2.5
Hello, world!

I'll leave it as an exercise for the reader to verify that all the arguments have their reference types preserved when being passed through the vtable function and into PrinterImpl::print. You can play around with the code here: https://godbolt.org/z/jPbe3hnh4

You can also find the code on my github: https://github.com/christiandaley/examples/blob/main/cpp/virtual_function_templates/main.cpp

To the best of my knowledge, the code shown here is well formed and does not contain any undefined or implementation defined behavior. That being said, I am not an expert when it comes to the C++ standard so it's entirely possible that I'm wrong about that, and if I am I would love if someone was able to point that out. Regardless, this code should be seen as a curiosity and a learning experience and I absolutely do not recommend using this in any production code.

Moving forward

We've shown that, with some boilerplate, virtual function templates are indeed possible in C++ as long as we confine ourselves to a single source file. It's easy to see that our current implementation is pretty limited: we support only a single function template that doesn't return anything. What if we wanted to allow for an arbitrary number of virtual function templates to be declared and implemented? And what if each of those returns a potentially different type? It'd be great if we were able to do something like this:



struct Base
{
    template <typename... Args>
    int virtual_func_one(Args&&...)
    {
        // ...
    }

    template <typename... Args>
    std::string virtual_func_two(Args&&...)
    {
        // ...
    }

    template <typename... Args>
    std::vector<double> virtual_func_three(Args&&...)
    {
        // ...
    }
};

You might think that we'd need a separate vtable for each of them, but as it turns out we don't! In a future post we'll explore how we can enable this functionality by modifying our existing code.

Some notes about ODR

C++ has something called the One Definition Rule, which basically says that non-inline classes, functions, and variables can have exactly one definition throughout the entire program. Variables/functions marked inline and class/function templates can be defined more than once as long as each definition occurs in a different translation unit and all definitions are identical. Any violation of this rule results in the program being ill formed, and there is no guarantee that the compiler will issue any sort of error. Consider the following function declared in some file f.h:



template <typename T = ::Tag>
int f()
{
    return 1;
}

This function template f has a default template parameter of type ::Tag, but this type isn't defined in f.h. Now consider the following two source files:



// A.cpp
namespace
{
    struct Tag {};
}

#include "f.h"



// B.cpp
namespace
{
    struct Tag {};
}

#include "f.h"

Both A.cpp and B.cpp declare a struct Tag within an anonymous namespace prior to including f.h. This means that the two versions of f that end up being defined in our program will "see" different types as their default template parameter and therefore have different definitions. This violates the ODR rule and such a program is ill formed regardless of whether any existing compiler implementation is willing to compile it. What does this mean for us?

I mentioned earlier that our code only works within a single source file. It should be fairly straightforward to understand the most obvious issue with putting our Printer class in a header file and attempting to use any given Printer instance across source files. A PrinterImpl object constructed in some file A.cpp will contain a vtable that is capable of handling only the specific specializations of Printer::print that are needed in that one file. Casting it to a Printer* and passing it to a function defined in some other source file B.cpp is a recipe for disaster. Unless both A.cpp and B.cpp use the exact same specializations of Printer::print in the exact same order, we're going to run into problems when B.cpp expects a different vtable than the one constructed in A.cpp.

We might think to remedy this issue by replacing our array based implementation of the vtable with a std::unordered_map<std::type_index, void(*)(Printer*, void*)>. In Printer::print we would no longer need to worry about the index returned from stateful_type_list::try_push and instead we could use typeid(vtable_func<Args...>) to lookup the correct function in the map. Likewise in create_vtable we would initialize this map with {{ typeid(Funcs), Funcs::template run<Derived> }...}. This would make it so that the order in which Printer::print specializations are used no longer matters, and would also allow us to detect when we've been given a Printer that isn't capable of handing a particular set of arguments. In Printer::print we could verify that the corresponding entry exists in the map before attempting to call the function and if it doesn't we can do something like throw an exception that could be handled by the caller. This should work great, right?

Wrong.

I don’t know exactly what any particular compiler will do when given such a program, but I can show that such a program violates the ODR and is ill formed.

Going back to the implementation details of stateful_type_list let's consider what happens when print(5) is called on some Printer object. Let's also assume that this is the first and only use of Printer::print within this source file. When vtable_func<int> is added to the stateful list it results in a declaration of flag(getter<0>) being instantiated by the compiler with a deduced return type of type_list<vtable_func<int>>. Later, this function is called by get in stateful_type_list. Friend functions exist at the namespace scope even if they are defined within a struct/class. That means that the compiler sees a free function named flag that accepts a parameter of type getter<0> and returns a type_list<vtable_func<int>>.

Now what happens if we do the same thing in another source file, but instead we call print(5.0). Following the same logic as before, the result will be the declaration of a free function named flag that accepts a parameter of type getter<0> and returns a type_list<vtable_func<double>>. C++ functions cannot be overloaded solely on their return type, so this is in fact a conflicting definition of flag(getter<0>). ODR is violated and the program is ill formed.

This isn't the only ODR violation that could happen. For example, let's say that both our Printer and PrinterImpl classes are placed in a header file printer.h. Remember that the Printer constructor will call create_vtable which is a function template. The specialization of create_vtable that is invoked will depend on the current state of stateful_type_list. If two different source files both construct a PrinterImpl and call different specializations of Printer::print then the constructor Printer::Printer<PrinterImpl> will call different specializations of create_vtable depending on which source file it's being called in. The result would be two conflicting definitions of the constructor. Again, ODR is violated.

What can we conclude from all this? First of all it's plain to see that stateful metaprogramming is a (potentially) very dangerous practice that can easily lead to ill formed programs and undefined behavior. We can also see that our Printer and PrinterImpl classes are not safe to use outside of a single source file, and I don't know how useful it is to have virtual function templates that are confined to a single source file. It'd be awesome if we could use this technique across many source files within a single program but the need for meta state will necessarily lead to ODR violations because different state is needed in different translation units. Our code is an interesting novelty but is forever limited by the ODR imposed on us by the C++ standard.

Sadly, there is no way to make our virtual function templates safe to use across translation units.

...