Credit: Hackday.com

Counting the number of fields in an aggregate in C++20

Using the properties of aggregate types to figure out the number of fields in an aggregate data structure

If you want to go straight to the working solution, just click here to be taken to the GodBolt page!

In the programming world, reflection refers to the capability of a program to introspect its own structure and take decisions based on it. One example is to automatically generate serialization routines, inspect a data type (like a struct or class in C#) and build a string (or JSON!) representation of it, parse such representations and reconstruct the original data, and so on. While prevalent and robust in many other languages, it is surprisingly lacking in C++; within reason, since C++ is all about working with raw data and systems.

However, a form of reflection that would be extremely useful in C++ is compile-time (or static) reflection, which would enable the compiler (via template meta-programming tricks) to take decisions and implement functions based on the individual fields of a data type. This would be especially interesting a number of reasons:

• Writing serialization functions (for example, void serialize(const T& data) that automatically serializes each field of a structure);
• Generating automatic pipeline layouts and vertex attribute formats in graphics libraries such as Vulkan and OpenGL;
• “Automatic” generation of debugging views, that inspect each field.

With C++17 came a new language feature called structured bindings, which bring the ability of binding each field of a struct to a reference and/or a variable name, which would enable to “introspect” (in a limited way) on the fields of a struct:

struct MyStruct final
{
    int a;
    float b;
    std::string c;
};
template <typename T> requires std::is_aggregate_v<T>
void serialize(const T& data)
{
    auto [a1, a2, a3] = data;
    serialize(a1);
    serialize(a2);
    serialize(a3);
}

If we call, for example, serialize(MyStruct{}), we see that a1, a2 and a3 are correctly bound to MyStruct::a, MyStruct::b and MyStruct::c respectively, and will call the correct serialize overloads, provided they have been provided (note: also, possibly the correct way of doing it is by using customization point objects, like in C++20’s ranges library, but this is not the point of this post).

Similarly, any struct with 3 fields can be passed to serialize, and it will do its job correctly. But what if we pass a struct with 5 fields? Only the first 3 fields will be written. What about 2? Then it’s a hard compile error. So, somehow, we would like to instrument our function, so it can use the correct structured binding to treat the data object. Something like:

template <typename T> requires std::is_aggregate_v<T>
void serialize(const T& data)
{
    constexpr std::size_t NumFields = /* something */;
    if constexpr (NumFields == 1)
    {
        auto [a1] = data;
        serialize(a1);
    }
    else if constexpr (NumFields == 2)
    {
        auto [a1, a2] = data;
        serialize(a1);
        serialize(a2);
    }
    else // ... a long list of cases that will be probably generated
         // by a script, since C++ doesn't allow yet the use of
         // variadic structured bindings
}

However, as a matter of fact, there is no structure on the type_traits library that allows you to get the number of fields in an aggregate structure. I will show in this blog post a way of doing that.

Previous Literature and Known Work

This is based on Antony Polukhin’s work on magic_get (which is the basis of Boost’s pfr library), which he goes in details in CppCon2016 and CppCon2018. He constructed a few versions of his library, using C++14 and C++17 features (including one that uses the infamous unconstexpr misfeature, which seems to have been fixed in recent compilers). On its core, though, lies two important things:

1. The ability to tell how many fields an aggregate structure has;
2. The ability to tell what is the type of the i-th field given a certain i.

Point 2 will be surely provided by the structured binding, but we still need point 1 in order to apply the “correct” binding to our code.

Aggregate Initialization and its Properties

First, the functionality described here only works for aggregates, so I shall restrict all the structures that I’ll be working on with the appropriate concept:

template <typename T> concept aggregate = std::is_aggregate_v<T>;

The crucial property of aggregates for the mechanisms that I’ll explain in this post is the ability to perform aggregate initialization, i.e. initialize the structure using initializer clauses inside curly braces:

MyStruct myValues{2, 3.0f, "my string"};
// myValues.a == 2
// myValues.b == 3.0f
// myValues.c == "my string"

According to the C++ Standard, providing more clauses than members of the structure is a hard compiler error (which can be detected by SFINAE), and providing fewer clauses will default-initialize the remaining members. Polukhin then devised a way to use a “universally-convertible” structure in order to detect whether an aggregate can be initialized with a certain number of arguments. Let’s see how it works; first we define a concept to “detect” if an aggregate T can be initialized with a certain set of parameters:

template <typename T, typename... Args>
concept aggregate_initializable = aggregate<T> 
    && requires { T{std::declval<Args>()...}; };

(note: the original method by Polukhin doesn’t use requires, since it’s part of C++20; rather, it uses SFINAE in another way)

Now, we define this universal structure that can be converted to any other; which could be used repeatedly in order to test the “signature” of T’s initialization:

namespace detail
{
    struct any
    { 
        template <typename T> 
        constexpr operator T() const noexcept;
    };
}
static_assert(aggregate_initializable<MyStruct, detail::any>);
static_assert(aggregate_initializable<MyStruct, detail::any, detail::any>);
static_assert(aggregate_initializable<MyStruct, detail::any, detail::any, detail::any>); // 3 arguments is the max
static_assert(!aggregate_initializable<MyStruct, detail::any, detail::any, detail::any, detail::any>);

The special property of the structure any is that it has a user-provided templated conversion operator to any type available, as described by its signature. We don’t need to provide an implementation, we won’t be calling it anyway (and it prevents misuse of this structure for other uses).

Counting Clauses, Dynamically

Here lies the problem: how can we instruct the compiler to generate an arbitrarily sized list of detail::any in order to test our structure? The solution is std::index_sequence. We can make an “indexed type” that is essentially the same type, but templated with a std::size_t , so we can apply the std::index_sequence’s parameter pack to get a repeated list of types. We then use std::make_index_sequence to generate the index sequence and, thus, the type list. Here is how it works:

namespace detail
{
    template <std::size_t I>
    using indexed_any = any;
    template <aggregate T, typename Indices>
    struct aggregate_initializable_from_indices;
    template <aggregate T, std::size_t... Indices>
    struct aggregate_initializable_from_indices<T,
        std::index_sequence<Indices...>>
        : std::bool_constant<aggregate_initializable<T,
            indexed_any<Indices>...>> {};
}
template <typename T, std::size_t N>
concept aggregate_initializable_with_n_args = aggregate<T>
    && detail::aggregate_initializable_from_indices<T,
        std::make_index_sequence<N>>::value;
static_assert(aggregate_initializable_with_n_args<MyStruct, 0>);
static_assert(aggregate_initializable_with_n_args<MyStruct, 1>);
static_assert(aggregate_initializable_with_n_args<MyStruct, 2>);
static_assert(aggregate_initializable_with_n_args<MyStruct, 3>);
static_assert(!aggregate_initializable_with_n_args<MyStruct, 4>);

Here, we can see the “type replication” machinery working std::make_index_sequence<N> generates a std::index_sequence<0, 1, 2, ..., N-1>, and those values are passed to the parameter pack Indices..., which is used in the expression indexed_any<Indices>... to generate the list of N types any, since indexed_any<I> just drops the index.

This concept can already be used to check whether a specific aggregate can be initialized with a certain number of arguments, which provides a lower bound for its number of fields. However, what we want is to find the exact number of fields, so a recursive strategy to do so is: we start with N = 0; test whether the aggregate can be initialized with N args; if so, we repeat the test for N+1, but if not, we know the number of fields in the aggregate is N-1. “Translating” to C++, we have this:

namespace detail
{
    template <aggregate T, std::size_t N, bool CanInitialize>
    struct aggregate_field_count : aggregate_field_count<T, N+1,
        aggregate_initializable_with_n_args<T, N+1>> {};
    template <aggregate T, std::size_t N>
    struct aggregate_field_count<T, N, false>
        : std::integral_constant<std::size_t, N-1> {};
}
template <aggregate T>
struct num_aggregate_fields
    : detail::aggregate_field_count<T, 0, true> {};
template <aggregate T>
constexpr std::size_t num_aggregate_fields_v
    = num_aggregate_fields<T>::value;

With that, we have already our method of finding the number of fields within an aggregate!

static_assert(num_aggregate_fields_v<MyStruct> == 3);

You can see it working here.

Going O(log n)

There’s a catch with this approach, though. The problem is that, if the number of fields starts getting extremely high (you can see why this can be the case in a bit), it will generate a great number of nested template instantiations, will slow down the compiler to a crawl and may even exceed the template instantiation depth. So, we should try a way to reduce this number of instantiations. Since we have a “partition” of whether an aggregate can be initialized with a number of clauses or not (if it can with N, then it can with any M < N), a better strategy is to use binary search. For that, I am going to define a “generic” binary search template struct:

template <template<std::size_t> typename Predicate,
    std::size_t Beg, std::size_t End>
struct binary_search;
template <template<std::size_t> typename Predicate,
    std::size_t Beg, std::size_t End>
using binary_search_base = 
    std::conditional_t<(End - Beg <= 1),
    std::integral_constant<std::size_t, Beg>,
    std::conditional_t<Predicate<(Beg + End) / 2>::value,
        binary_search<Predicate, (Beg + End) / 2, End>,
        binary_search<Predicate, Beg, (Beg + End) / 2>>>;
template <template<std::size_t> typename Predicate,
    std::size_t Beg, std::size_t End>
struct binary_search : binary_search_base<Predicate, Beg, End> {};
template <template<std::size_t> typename Predicate,
    std::size_t Beg, std::size_t End>
constexpr std::size_t binary_search_v
    = binary_search<Predicate, Beg, End>::value;

This structure uses a not widely know feature of C++: the template template parameter. The binary_search structure takes a Predicate which takes a parameter of std::size_t (and should ideally be a std::bool_constant), and a range, and applies binary search on it, returning the last N on this range for which Predicate<N>::value is true. This can reduce the number of instantiations (and compiler time) to a manageable O(log N) on the number of fields.

But now we need a proper upper bound on the number of fields! How do we do that? Ignoring [[no_unique_address]] marked fields and other zero-size shenanigans, we can assume that each field takes at least one byte in the structure. However, with bit-fields, we can have as much as one bit per field (or 1/8 of a byte), so we are guaranteed (again, ignoring zero-size fields) to have at most 8 * sizeof(T) fields on the structure, and with that we can input our upper bound for the binary search:

namespace detail
{
    template <aggregate T:
    struct aggregate_inquiry
    {
        template <std::size_t N>
        struct initializable : std::bool_constant<
            aggregate_initializable_with_n_args<T, N>> {};
    };
}
template <aggregate T>
struct num_aggregate_fields : binary_search<
    detail::aggregate_inquiry<T>::template initializable,
        0, 8 * sizeof(T) + 1> {};

What’s going on here? First, we cannot just pretend it’s Haskell and use a partially-instantiated template à la aggregate_initializable_with_n_args<T, ???> in C++, so we need to construct a “wrapper” around it. detail::aggregate_inquiry<T> is our template. The quirk here is template initializable at the end of the declaration. Why? By default, since C++ doesn’t know anything beforehand about detail::aggregate_inquity<T>::initializable (we say initializable is a dependent name), it will assume it’s not an instantiable template, so we put template in front of the name to tell C++ about it. You can see the entire thing working here.

With that, we finally have our aggregate number of fields detector, and now we can go home and implement all the functions that depend on it! Right?

Well, Yes, But Actually No!

Let’s go back to the working example. Try to play with MyStruct a little. Try to see what’s going on when, for example, you add an array to the structure. Let’s see:

struct MyStruct2
{
    int a;
    float b;
    std::string c;
    int arr[5];
};
int main()
{
    printf("%zu\n", num_aggregate_fields_v<MyStruct2>);
}

It should output 4, but as you can see here, it outputs 8! What’s the problem here? Well, it comes down again to how aggregate initialization works. When you have an array (and, for some reason, not a nested aggregate), you actually can initialize the individual array’s elements in the same brace-initializer, eliding that array’s braces. That makes each individual element of the array (even a multidimensional array) count for the number of “fields” this aggregate contains.

This, however, doesn’t agree with the structured binding definition of “number of fields”. Each array will count as a single element to form the bindings, and, as such, if we rely on the mechanism above, our methods will pick the wrong structured binding, as it can be seen here:

static_assert(num_aggregate_fields_v<MyStruct2> == 8);
// It has 8 fields, so can I decompose it into 8 elements?
auto [a1, a2, a3, a4, a5, a6, a7, a8] = MyStruct3{};
// No, I can't

The error is pretty self-explanatory: type ‘MyStruct2’ decomposes into 4 elements, but 8 names were provided.

So, is this the end of the line?

As far as I am informed, this is where Antony Polukhin stopped, and I have no clue whether he was able to solve it (I’m willing to guess he was, since I’m 3 years late to the problem). So what I will explain next is, as far I know, unpublished (not claiming I’m the sole implementer, only that I don’t know any other one).

The idea to try to find the number of “unique fields”, then, is to figure out how many “fields” each actual field of aggregate contribute to the count above. This can be done, again, by the rules of aggregate initialization!

Nested Aggregate Abuse and Counting Inner Fields

So, what’s the strategy? Observe that each array that “bloats” our aggregate count is an aggregate in itself and, thus, can be inspected about its number of fields. How can we do that? We’re going to write a function to test whether the “field” N of our aggregate can be initialized with M clauses by testing whether the following initialization is valid:

T{any, any, ..., any, {any, any, ... any}};
//  N clauses here     M clauses here

How we do that? With a clever “abuse” of std::index_sequence and parameter packs again!

namespace detail
{
    template <aggregate T, typename Indices, typename FieldIndices>
    struct aggregate_with_indices_initializable_with;
    template <aggregate T, std::size_t... Indices,
        std::size_t... FieldIndices>
    struct aggregate_with_indices_initializable_with<T, 
        std::index_sequence<Indices...>,
        std::index_sequence<FieldIndices...>
    > : std::bool_constant<requires
        { 
            T{std::declval<indexed_any<Indices>>()...,
                {std::declval<indexed_any<FieldIndices>>()...}};
        }> {};
}
template <typename T, std::size_t N, std::size_t M>
concept aggregate_field_n_initializable_with_m_args = aggregate<T>
    && detail::aggregate_with_indices_initializable_with<T>,
        std::make_index_sequence<N>,
        std::make_index_sequence<M>>::value;
static_assert(aggregate_field_n_initializable_with_m_args
    <MyStruct2, 3, 5>);
static_assert(!aggregate_field_n_initializable_with_m_args
    <MyStruct2, 3, 6>);

This really long-named concept takes an aggregate and two numbers N and M, and it outputs whether the field a position N is an aggregate that can be brace-initialized with M arguments. The interesting thing here, and that will be exploited in the next section, is that every field can be initialized with 1 brace-argument anyway (and, unless it’s the first field of an array, that is the only number of arguments (besides 0) it can be initialized with).

(note: at the date this post was written, MSVC still could not accept requires clauses outside of concept declarations, so the above code is not valid. A workaround, however, is to use a “classical SFINAE” sequence, using function template overloads, as it can be seen on this full example here, line 86)

Armed with that concept, we can proceed to make our “number of fields for aggregate N” structure. We are going to use the same binary-search struct we implemented:

namespace detail
{
    template <aggregate T, std::size_t N>
    struct aggregate_field_inquiry
    {
        template <std::size_t M>
        struct initializable : std::bool_constant<
            aggregate_field_n_initializable_with_m_args<T, N, M>>
        {};
    };
}
template <aggregate T, std::size_t N>
struct num_fields_on_aggregate_field : binary_search<
    detail::aggregate_field_inquiry<T, N>::template initializable,
    0, 8 * sizeof(T) + 1> {};
template <aggregate T, std::size_t N>
constexpr std::size_t num_fields_on_aggregate_field_v
    = num_fields_on_aggregate_field<T, N>::value;
static_assert(num_fields_on_aggregate_field_v<MyStruct2, 0> == 1);
static_assert(num_fields_on_aggregate_field_v<MyStruct2, 3> == 5);

The whole idea about detail::aggregate_field_inquiry<T, N> was explained above, and the template initializable as well.

There’s a catch, though: If the field in question isn’t an array, but actually an object that is constructible with an std::initializer_list of any type, we will see that the condition on it will always return true, which means num_fields_on_aggregate_field_v will return the maximum value for that type (which is 8 * sizeof(T)). We will be able detect such types on the next section, though, because they have this high value.

So, now, we have a struct that can tell us how many fields that specific aggregate field “spans”. How can we use that information to count the number of “unique” fields and, thus, agree with the structured binding idea?

The Bunny-Hopping Counting Technique

Now, for the last part of my field counting method. Suppose we now know the field N of the aggregate is an array that actually has M “fields”. Then, we know that the next actual field of the aggregate actually lies M fields ahead; so then we “hop” to the field N+M and count how many “fields” it has (1 if it’s not an array, more if it is); if, however, we fall within one of those “special” types in which M is greater than the total number of fields, we only hop 1, since we know it’s a “special” type.

We stop “hopping” when we reach the number of fields previously given by the original method. Each time we “hop” a number of fields, we increase another counter in 1, which effectively will end up counting the actual number of fields in the aggregate. The code that does the job is this one:

namespace detail
{
    template <std::size_t Val, std::size_t TotalFields>
    constexpr auto detect_special_type =
        Val > TotalFields ? 1 : Val;
    template <aggregate T, std::size_t CurField,
        std::size_t TotalFields, std::size_t CountUniqueFields>
    struct unique_field_counter : unique_field_counter<T,
        CurField + detect_special_type<
            num_fields_on_aggregate_field_v<T, CurField>,
            TotalFields>, TotalFields, CountUniqueFields + 1> {};
    template <aggregate T, std::size_t Fields,
        std::size_t UniqueFields>
    struct unique_field_counter<T, Fields, Fields, UniqueFields>
        : std::integral_constant<std::size_t, UniqueFields> {};
}
template <aggregate T>
struct num_aggregate_unique_fields
    : detail::unique_field_counter<T, 0, num_aggregate_fields_v<T>, 
        0> {};
template <aggregate T>
constexpr std::size_t num_aggregate_unique_fields_v
    = num_aggregate_unique_fields<T>::value;
static_assert(num_aggregate_unique_fields_v<MyStruct2> == 4);

The unique_field_counter structure does all the job of bunny-hopping according to the number of fields that each field spans, and also employs the detect_special_type template variable to check whether this type is a type for which num_fields_on_aggregate_field would fail to provide the actual number of fields (because of the std::initializer_list constructor).

And voilà! With this last technique, we finally are able to count the number of actual fields in an aggregate in a way that agrees with the structured binding count of members. This (hopefully) solves the problem with arrays and (possibly) enables a whole new form of compile-time reflection based on structured bindings.

You can find the full working code by clicking on this link, alongside a small implementation of a tie_as_tuple function.

And here it is, again, the working version on MSVC, because of the quirk I stated above.

Conclusion and Caveats

That was a long article, for sure. I had some days to explore this problem, and I tried my best to get somewhere on it. I think this solution is “as best” as it can get, given the lack of a proper compile-time reflection feature (other than preprocessing headers with a custom utility that needs to be integrated on a build system, but then it isn’t “pure” C++ anymore).

However, a disclaimer must be made. This will require an intense amount of template instantiations, even with the binary search optimizations up there, and thus will pressure the compilers and make the compilation times increase by a lot. Yes, nasty template magic like the one presented here is cool, and having this ability of “abusing” the compiler to give us what we need is also interesting, but some care should be taken on whether this should really be used in production code. I haven’t tested a lot on its scalability, and this is yet very fragile (I was accustomed to writing algorithmic code for contests, though), so I advise using this code with caution.

And there it is, quite long for a “first” blog post, but I hope I managed to convey the technique I found. I suppose this will have some interesting applications in the hands of the library designers and the rest of the C++ community.