Manually translated from: 基于 C++26 静态反射实现零样板代码、零额外开销的分派表.

As compile-time reflection is finally adopted to C++26 standard, developers are enabled to fetch and operate on the metadata of the C++ program itself. Metadata of various C++ entities (variables, functions, classes, templates, namespaces, etc.) can be obtained from reflection API in C++26 standard library, the most frequently used of which is getting an entity’s name, type, list of members or list of base classes. Reflection is incredibly helpful to support more elegant and more efficient C++ code by utilizing the metadata properly. In this blog we dive into dispatch table, which is a common pattern in real-world C++ code, demonstrating how the great power and expressiveness of C++26 reflection helps with eliminating boilerplate code and runtime overhead that are inevitable in pre-C++26 dispatch table implementation, and then, how the API design of our reflection-based dispatch table can be further improved step-by-step.

The contents shown by this blog has full implementation in my rbox library. Source code is available in GitHub.

How It Works Finally

We start from the following example to demonstrate the expressiveness of C++26 reflection. All the constexpr evaluations of building the dispatch_table are encapsulated into the API macro RBOX_FUNCTION_FIXED_MAP. The first parameter ops is the namespace whose members are to be traversed. The second parameter "do_*" is the identifier pattern which the members of namespace ops are expected to follow. Each function in namespace ops is added to the dispatch table if and only if its identifier matches the pattern "do_*". The dispatch_table returned is an associative array whose value type is auto-deduced as int (*)(int, int) and the internal data structure is selected adaptively according to the input (typically a hash table, or a linear table as fallback when the number of entries is few).

More examples are provided in the examples of rbox library.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
namespace ops {
int do_add(int x, int y);
int do_sub(int x, int y);
int do_mul(int x, int y);
int do_div(int x, int y);
int do_mod(int x, int y);
int do_and(int x, int y);
int do_or(int x, int y);
int do_xor(int x, int y);
int do_shl(int x, int y);
int do_shr(int x, int y);
int do_ashr(int x, int y);
}  // namespace ops

// Creates a fixed map from name to function pointer:
//   "add" -> &ops::do_add
//   "sub" -> &ops::do_sub
//   "mul" -> &ops::do_mul
//   ... and all other functions in namespace ops
// No boilerplate code! The underlying data structure is likely a hash map.
constexpr auto dispatch_table = RBOX_FUNCTION_FIXED_MAP(ops, "do_*");

bool do_binary_arithmetic(const char* op_name, int* dest, int x, int y)
{
    if (op_name == nullptr || dest == nullptr) {
        return false;
    }
    int (*op_func)(int, int) = dispatch_table[op_name];
    if (op_func != nullptr) {
        *dest = op_func(x, y);
        return true;
    }
    return false;
}

int dest = 0, x = 42, y = 31;
assert(do_binary_arithmetic("sub", &dest, x, y));
assert(dest == 11);
assert(!do_binary_arithmetic("rsub", &dest, x, y));  // Filtered out

Background: Drawbacks of Traditional Dispatch Tables

Before static reflection being introduced to C++, dispatch tables are usually implemented by the following 3 approaches:

  1. if-else chain: The most brute-force approach that is acceptable only when the number of entries is fairly small. When the number of entries goes larger, such code can be a disaster of maintenance, as developers will probably suffer from hidden bugs from wrongly inserted/removed entries or typo in keys.
  2. X-macros: As shown in the example below. X-macros perform for-each operation during code preprocessing. They are much cleaner and more maintainable than lengthy if-else chains, yet boilerplate code like the #define and #undef pair is still required. Furthermore, the expressiveness of X-macros drops sharply when the relation of entries grows more complex. Though it works fine in the following example where there are only two sets (OP_BIT_FUNCS as subset of OP_FUNCS), it is still facing challenge as more and more subsets may be involved in the future, forcing the developer to either create scattered X-macro partitions or create duplicated entries in multiple X-macros.
  3. Static or global containers: As shown in the example below. Dispatch table entries are inserted during runtime to a container like std::unordered_map, which is initialized as a static or global instance. Developers can benefit from lower time complexity for each query with proper data structure, yet the overhead of dispatch table initialization is delayed to runtime, and in some cases developers may encounter trouble with static or global objects (initialization order, error handling during initialization, etc.).

A brand new approach is provided by C++26 reflection. The entry list can be obtained via reflection APIs like std::meta::members_of(), thus manual work of listing all the entries in if-else chains or X-macros are no more needed. The underlying data structure of dispatch table can be selected & constructed in compile-time with flexible constexpr evaluations assisted by reflection mechanism.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define OP_BIT_FUNCS(X) \
    X(and)              \
    X(or)               \
    X(xor)              \
    X(shl)              \
    X(shr)              \
    X(ashr)

#define OP_FUNCS(X)    \
    X(add)             \
    X(sub)             \
    X(mul)             \
    X(div)             \
    X(mod)             \
    OP_BIT_FUNCS(X)

auto build_dispatch_table() /* -> decltype(result) */
{
    auto result = std::unordered_map<std::string_view, int (*)(int, int)>{};
#define OP_CASE(which) result.emplace(#which, &ops::do_##which);
    OP_FUNCS(OP_CASE)
#undef OP_CASE
    return result;
}

bool do_binary_arithmetic(const char* op_name, int* dest, int x, int y)
{
    static const auto dispatch_table = build_dispatch_table();
    if (op_name == nullptr || dest == nullptr) {
        return false;
    }
    if (auto it = dispatch_table.find(op_name); it != dispatch_table.end()) {
        *dest = (it->second)(x, y);
        return true;
    }
    return false;
}

Prior Knowledge: C++26 Compile-time Reflection & Data Promotion

For the sake of brevity, this blog is neither a comprehensive tutorial of C++26 reflection nor attempting to cover every of its details. You can refer to the draft of C++26 reflection (a.k.a. the p2996 paper) and other blogs in C++ community for more information.

The C++26 standard library provides std::define_static_array() which allows us to define an array of constants during constexpr evaluation, promoting all the values in the input range to static storage. It is powerful but not powerful enough for our dispatch table implementation. rbox::to_static_storage() is an extension which supports promoting data of more complicated types like nested ranges. You can read my previous blog for the rationale of data promotion and the details of rbox::to_static_storage(): Extension to std::define_static_array() - More Powerful Compile-time Data Promotion.

Diving into Implementation

In the following contents we will finish the implementation of dispatch tables in an incremental manner. The full implementation will be decomposed to three steps:

  1. Basic functionality;
  2. Adaptive data structure;
  3. Auto-deducing the target type.

Step 1: Basic Functionality

We start with implementing the following dispatch table API which is a simplified version: ns is the namespace whose members are to be traversed. prefix specifies the identifier pattern which the filtered members shall follow. The target type T of filtered members (which can be either an object type or a function type) should be provided explicitly by the user as a template parameter. All the members in namespace ops that match the given identifier pattern and type will be added to the dispatch table. This simplified API returns a linear list of key-value pairs, where keys are sorted by lexicographical order so that binary search is supported. The linear list is promoted to static storage via rbox::to_static_storage() and this API returns the promotion result of type Span<Pair<StringView, const T*>>.

Note: std::span and std::string_view from C++ standard library are not available in this case. They are not structural (the same constraint to non-type template parameters, namely NTTP) due to their private data members. Span and StringView are their respective replacements whose data members are exposed as public for the sake of structuralness. My previous blog has provided a detailed analysis on why structuralness is required during data promotion.

1
2
3
template <class T>
consteval auto make_dispatch_table(std::meta::info ns, std::string_view prefix)
    /* -> Span<Pair<StringView, const T*>> */

This simplified version can be implemented easily with the help of C++26 standard library of reflection. Given a reflection of a class or namespace, std::meta::members_of() returns a list of its members. For each member in the returned list:

  • std::meta::type_of(member) obtains its type;
  • std::meta::is_same_type(A, B) tests whether A and B are exactly the same type (the same semantics as std::is_same since C++11);
  • std::meta::has_identifier(member) tests whether member is not an anonymous member;
  • std::meta::identifier_of(member) obtains its identifier. A compile-time exception of type std::meta::exception will be thrown if member is anonymous;
  • When the exact target type T of member is known, std::meta::extract<T*>(member) obtains a pointer to the variable or function member reflects. A compile-time exception of type std::meta::exception will be thrown on target type mismatch.

Important notes:

  1. Argument-dependent lookup (ADL) is useful for less typing (11 characters std::meta:: per invocation) and cleaner code. All the C++ standard library components in namespace std::meta with at least one std::meta::info argument can be found via ADL.
  2. std::meta::members_of(), as well as other reflection API for member list query, returns the direct members of the given class or namespace. Members in base classes, nested classes, parent or child namespaces are not covered, and additional recursive work is required to cover these non-direct members. In this blog parent or child namespaces are not in our consideration.
  3. std::meta::members_of(), as well as other reflection API for member list query, takes another argument ctx of type std::meta::access_context besides the reflection of class or namespace. ctx affects access control of each member. For class members, protected and private members are added to the returned list only if they are accessible in given access context. For namespace members, the effects of ctx are negligible.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template <class T>
consteval auto make_dispatch_table(std::meta::info ns, std::string_view prefix)
    -> rbox::meta_span<rbox::meta_pair<rbox::meta_string_view, const T*>>
{
    auto entries = std::vector<std::pair<std::string_view, const T*>>{};
    // std::meta::members_of via ADL
    for (std::meta::info member : members_of(ns, std::meta::access_context::current())) {
        // std::meta::{is_same_type, has_identifier} via ADL
        if (!is_same_type(type_of(member), ^^T) || !has_identifier(member)) {
            continue;
        }
        // std::meta::identifier_of via ADL
        std::string_view name = identifier_of(member);
        if (!name.starts_with(prefix)) {
            continue;
        }
        name.remove_prefix(prefix.length());
        entries.emplace_back(name, extract<T*>(member));
    }

    // rbox::get_first is a generic helper functor which gets the first tuple element.
    std::ranges::sort(entries, {}, rbox::get_first);
    // See: https://github.com/NoqtaBeda/rbox/blob/main/include/rbox/to_static_storage.hpp
    return rbox::to_static_storage(entries);
}

// Sorted key-value pair list. Enables binary search
constexpr auto dispatch_table = make_dispatch_table<int(int, int)>(^^ops, "do_");

bool do_binary_arithmetic(const char* op_name, int* dest, int x, int y)
{
    if (op_name == nullptr || dest == nullptr) {
        return false;
    }
    auto iter = std::ranges::lower_bound(dispatch_table, op_name, {}, rbox::get_first);
    if (iter == dispatch_table.end() || iter->first != op_name) {
        return false;
    }
    *dest = (iter->second)(x, y);
    return true;
}

Step 2: Adaptive Data Structure

In the previous section, we have implemented a simplified dispatch table whose data structure is fixed as sorted linear list, enabling binary search with O(log n) complexity. In this section we will proceed towards the ability of adaptive data structure. The first problem we will meet is which return type should make_dispatch_table() take when multiple data structures coexist as candidates. The following pseudocode is a skeleton with three candidate data structures, neither of which can be selected as the return type alone. Combining all of them with a union or std::variant is a bad idea that ruins all the expected advantages of dispatch tables. Not only the additional runtime overhead is a headache, using such a dispatch table also requires lots of boilerplate code for each invocation. if constexpr is not available in this case either as the arguments ns and prefix are not constant expressions.

Though the full definition of constant expressions (see cppreference for details) is quite complicated and verbose, constant expressions can be interpreted informally as those which can be evaluated in compile-time and then used as template parameters, size of C-style arrays, case value in switch statements, constexpr variable initializer, etc.

In the following code pattern:

  • The function arguments ns and prefix are not constant expressions (even though they are arguments of a consteval function);
  • The template parameter T can be used in constant expressions. In step 3 where we will implement auto-deduction of the target type, T will become a variable of type std::meta::info evaluated inside make_dispatch_table() function body, in which case T is no more a constant expression.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T>
consteval auto make_dispatch_table(std::meta::info ns, std::string_view prefix) /* -> ??? */
{
    std::vector<std::meta::info> members = members_of(ns, std::meta::access_context::current());
    /* Filtering by T and prefix */

    if (uses_hash_table_without_collision(members)) {
        return hash_table_without_collision_t{ /* ... */ };
    }
    if (uses_hash_table_with_collision(members)) {
        return hash_table_with_collision_t{ /* ... */ };
    }
    return naive_linear_table_t{ /* ... */ };
}

C++26 provides a solution for this problem. std::meta::reflect_constant() takes any value of structural type as argument and returns a std::meta::info reflecting its value, which is useful during constexpr evaluation when we need to unify the type of various values to std::meta::info. In this case we wrap the returned instance of each data structure with std::meta::reflect_constant(). Then the make_dispatch_table() API returns std::meta::info reflecting the instance of the selected data structure.

Generally, there are two approaches to extract the reflected value from a std::meta::info:

  1. Using splice specifiers: Given R which is a constant expression of type std::meta::info, [: R :] is evaluated to its reflected value;
  2. Using std::meta::extract(): Given the exact value type T and the reflection r, std::meta::extract<T>(r) is evaluated to r‘s reflected value. This approach does not require r to be a constant expression but as a cost T must be known.

The first approach fits in this case where we can extract the dispatch table instance by applying splice specifier to the std::meta::info returned by make_dispatch_table(). A wrapper macro MAKE_DISPATCH_TABLE() acts as a friendlier API design for C++ developers unfamiliar with C++26 reflection syntax ^^ and [: :].

p.s. Aesthetics is another minor concern as I dislike the weird syntax [: :] appearing everywhere :(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class T>
consteval auto make_dispatch_table(std::meta::info ns, std::string_view prefix) -> std::meta::info
{
    std::vector<std::meta::info> members = members_of(ns, std::meta::access_context::current());
    /* Filtering by T and prefix */

    if (uses_hash_table_without_collision(members)) {
        auto result = hash_table_without_collision_t{ /* ... */ };
        return std::meta::reflect_constant(result);
    }
    if (uses_hash_table_with_collision(members)) {
        auto result = hash_table_with_collision_t{ /* ... */ };
        return std::meta::reflect_constant(result);
    }
    auto result = naive_linear_table_t{ /* ... */ };
    return std::meta::reflect_constant(result);
}

#define MAKE_DISPATCH_TABLE(T, ns, prefix) [: make_dispatch_table<T>(^^ns, prefix) :]

constexpr auto dispatch_table = MAKE_DISPATCH_TABLE(int(int, int), ops, "do_");

bool do_binary_arithmetic(const char* op_name, int* dest, int x, int y)
{
    if (op_name == nullptr || dest == nullptr) {
        return false;
    }
    // Suppose each candidate provides operator[](std::string_view) -> int (*)(int, int)
    int (*fptr)(int, int) = dispatch_table[op_name];
    if (fptr == nullptr) {
        return false;
    }
    *dest = fptr(x, y);
    return true;
}

Step 3: Auto-deduced Target Type

The mighty power of C++26 reflection is still not fully exploited. A demanding user of our dispatch table API still complains that the target type T has to be typed manually, which is indeed a burden considering the fact that typical call signatures are fairly long in real-world codebase. C++26 has helped us to obtain the member list of namespace ns and build the underlying data structure in an adaptive manner. Can it be even more helpful such that the target type T can be auto-deduced from the filtered member list? The answer is fortunately yes, but more tricks are necessary for this goal. In the following code pattern we attempt to get rid of template <class T>. Reflection of the target type rT is obtained from the filtered members via std::meta::info. Type consistency check is performed to ensure all the filtered members share exactly the same type. Then we face another bottleneck of implementation: rT is no more a constant expression, as a result both splicing specifier and std::meta::info fails to work.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// No more explicitly specified T
consteval auto make_dispatch_table(std::meta::info ns, std::string_view prefix) /* -> ??? */
{
    // Note: we have no knowledge of T here.
    auto entries = std::vector<std::pair<std::string_view, std::meta::info>>{};
    for (std::meta::info member : members_of(ns, std::meta::access_context::current())) {
        // ... filtering omitted here
        std::string_view name = identifier_of(member);
        name.remove_prefix(prefix.length());
        // Note: we have no knowledge of T here, thus std::meta::extract<T>() is unavailable.
        entries.emplace_back(name, member);
    }
    if (entries.empty()) {
        // ... Returns an empty dispatch table. T can be deduced to any placeholder type (like void*)
    }
    // std::meta::type_of via ADL
    std::meta::info rT = type_of(entries[0].second);
    // Type consistency check
    for (size_t i = 1, n = entries.size(); i < n; i++) {
        std::meta::info rU = type_of(entries[i].second);
        // std::meta::is_same_type via ADL
        if (!is_same_type(rT, rU)) {
            // ... triggers compile error for deduced type conflict
        }
    }
    // ... rT  ->  T
}

Here is the useful trick: Reflection of a type or a value can be promoted to template parameter via std::meta::substitute() and std::meta::extract() combined, where it becomes a constant expression. The trick can be generalized as the following code pattern. make_something() is expected to return an instance of type SomethingWith<T> where T is deduced from the argument entity and its reflection rT, which is not a constant expression, is accessible inside the function body of make_something(). A helper function make_something_impl<T>() taking T as template parameter is needed which builds and returns the SomethingWith<T> instance. The helper function template is instantiated via std::meta::substitute() inside make_something() function body, then the corresponding function pointer is extracted by std::meta::extract(). Since the helper function template has fixed call_signature = std::meta::info(std::meta::info) (the result type is unified as std::meta::info with the help of std::meta::reflect_constant), std::meta::extract<call_signature>() works in this case and the instantiated helper function can be invoked by make_something() via the extracted function pointer.

The substitute + extract pattern serves as a practical bridge on the huge gap between non-constant expressions during consteval evaluation and constant expressions as template parameters, allowing us to go back and forth, benefiting from both the power of constant expressions and the flexibility & compile-time performance (compared to traditional template metaprogramming) of consteval functions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class T>
consteval auto make_something_impl(std::meta::info entity) -> std::meta::info
{
    // std::meta::extract() works with the knowledge of T
    auto result = SomethingWith<T>{ /* ... */ };
    return std::meta::reflect_constant(result);
}

consteval auto make_something(std::meta::info entity) -> std::meta::info
{
    std::meta::info rT = /* reflection of T */;

    using call_signature = std::meta::info(std::meta::info);
    // std::meta::{substitute, extract} via ADL
    std::meta::info impl_instance = substitute(^^make_something_impl, {rT});
    // make_something_impl<T> instantiated
    call_signature* impl_fn = extract<call_signature*>(impl_instance);
    return impl_fn(entity);
}

Now we finish implementing auto-deduction of the target type with the substitute + extract pattern shown above. A helper function template is needed for each data structure which builds its instance. The following code contains one of them as example. The deduced target type will be promoted as template <class T> of the helper function template make_binary_search_dispatch_table(). Reflection of the deduced type rT will be promoted to the template parameter with std::meta::substitute, then the instantiated helper function will be extracted by std::meta::extract<call_signature>() and immediately invoked. As a result of our work till now, the MAKE_DISPATCH_TABLE() API is finally minimized after eliminating the explicit target type T, only ns and prefix are necessary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
template <class T>
consteval auto make_binary_search_dispatch_table(
    std::span<const std::pair<std::string_view, std::meta::info>> meta_entries) -> std::meta::info
{
    auto entries = std::vector<std::pair<std::string_view, const T*>>{};
    for (auto [key, meta_value] : meta_entries) {
        entries.emplace_back(key, extract<T*>(meta_value));
    }
    // Sorts by key
    std::ranges::sort(entries, {}, rbox::get_first);
    // See: https://github.com/NoqtaBeda/rbox/blob/main/include/rbox/to_static_storage.hpp
    auto result = rbox::to_static_storage(entries);
    return std::meta::reflect_constant(result);
}

consteval auto make_dispatch_table(std::meta::info ns, std::string_view prefix) -> std::meta::info
{
    auto entries = std::vector<std::pair<std::string_view, std::meta::info>>{};
    for (std::meta::info member : members_of(ns, std::meta::access_context::current())) {
        // ... filtering omitted here
        std::string_view name = identifier_of(member);
        name.remove_prefix(prefix.length());
        entries.emplace_back(name, member);
    }
    if (entries.empty()) {
        auto empty_table = /* ... */;
        return std::meta::reflect_constant(empty_table);
    }
    // std::meta::type_of via ADL
    std::meta::info rT = type_of(entries[0].second);
    // ... Type consistency check

    if (uses_binary_search(entries)) {
        using call_signature =
            std::meta::info(std::span<const std::pair<std::string_view, std::meta::info>>);

        std::meta::info impl_instance = substitute(^^make_binary_search_dispatch_table, {rT});
        call_signature* impl_fn = extract<call_signature*>(impl_instance);
        return impl_fn(entries);
    }
    // ... Other candidate data structures
}

// Before:   #define MAKE_DISPATCH_TABLE(T, ns, prefix) [: make_dispatch_table<T>(^^ns, prefix) :]
/* After: */ #define MAKE_DISPATCH_TABLE(ns, prefix) [: make_dispatch_table(^^ns, prefix) :]

// Before:   constexpr auto dispatch_table = MAKE_DISPATCH_TABLE(int(int, int), ops, "do_");
/* After: */ constexpr auto dispatch_table = MAKE_DISPATCH_TABLE(ops, "do_");

bool do_binary_arithmetic(const char* op_name, int* dest, int x, int y)
{
    if (op_name == nullptr || dest == nullptr) {
        return false;
    }
    // Suppose each candidate provides operator[](std::string_view) -> int (*)(int, int)
    int (*fptr)(int, int) = dispatch_table[op_name];
    if (fptr == nullptr) {
        return false;
    }
    *dest = fptr(x, y);
    return true;
}

Conclusion & Discussion: Reflection as Game Changer in C++ Code Design

We have managed to implement a dispatch table API in a step-by-step manner, zero boilerplate & zero runtime overhead based on the great power of C++26 reflection. Further extensions to its functionality and more use cases (class member lookup, recursive traversal of base classes, multiple target types, etc.) are omitted in this blog due to space limitations. See the rbox implementation for their details.

In the end of this blog, let us think deeper about compile-time reflection. Considering the fact that identifiers of C++ entities are able to be obtained by std::meta::identifier_of() and then participate in constexpr evaluations, enabling more string parsing and dispatching work in compile-time, C++ identifiers themselves get the potential to play an active role in code design models. Similarly, classes and namespaces are ready for a new role as “grids” or “drawers”, partitioning the traversal range of std::meta::members_of() etc. The power of reflection will not be limited to elaborating existing code patterns (like a more fancy dispatch table). It is a game changer on how we think and how we design new C++ code.

The code pattern below is a brief showcase of reflection-based C++ code design. namespace events represents the full set of events. Event keys are encoded into the names of handler functions and key registry is done automatically. The design is elegant, self-explaining, free from boilerplates and much more maintainable than traditional code patterns. The only risk is compile-time overhead bloating due to extensive constexpr evaluations diffused to multiple irrelevant translation units via #include chains, which can be prevented by careful design of source file structure.

1
2
3
4
5
6
7
8
9
10
/*
 * Please add new event handlers to namespace events and
 * name the handler function as "on_{key}_{variant}".
 */
namespace events {
status_t on_foo(const args_t& args);
status_t on_bar(const args_t& args);
// ...
status_t on_event(const char* key, const args_t& args);
}  // namespace events