Home > Enterprise >  Recursive iteration over type lists and concatenation into a result type list
Recursive iteration over type lists and concatenation into a result type list

Time:04-05

Consider a scenario having various classes/structs, some having complex data members, which can contain more of them itself. In order to setup / initialize, a list of all dependencies is required before instantiantion.

Because the types are known before instantiation, my approach is to define a type list containing involved/relevant types in each class/struct like this:

template<typename...> struct type_list {};

struct a {
    using dependencies = type_list<>;
};

struct b {
    using dependencies = type_list<>;
};

struct c {
    using dependencies = type_list<b>;
    b b_;
};

struct d {
    using dependencies = type_list<a>;
    a a_;
};

struct e {
    using dependencies = type_list<c, a>;
    c c_;
    a a_;
    x x_; // excluded
};

struct f {
    using dependencies = type_list<a,b>;
    a a_;
    b b_;
    y y_; // excluded
};

For example I want to pre-initialize d, e, f.

The next steps are:

  • iterate through the dependencies of d,e,f and concat each item to a result list
  • recursively iterate through each element of every dependencies[n]::dependencies and concat each item to a result list and do the same for each type until type list is empty

The result may contain duplicates. These get reduced and sorted in a later step. I intend to do this using a constexpr hash map using hashes of __FUNCSIG__ / __PRETTY_FUNCTION__ (not part of this).

How can this (iterating, accessing type list elements, concat into result list) be achieved using C 20 metaprogramming?

CodePudding user response:

I'll just look at the metaprogramming part. As always, the solution is to use Boost.Mp11. In this case, it's one of the more involved algorithms: mp_iterate.

This applies a function to a value until failure - that's how we can achieve recursion. We need several steps.

First, a metafunction to get the dependencies for a single type

template <typename T> using dependencies_of = typename T::dependencies;

Then, we need a way to get all the dependencies for a list of types. Importantly, this needs to fail at some point (for mp_iterate's stopping condition), so we force a failure on an empty list:

template <typename L>
using list_dependencies_of = std::enable_if_t<
    not mp_empty<L>::value,
    mp_flatten<mp_transform<dependencies_of, L>>>;

And then we can iterate using those pieces:

template <typename L>
using recursive_dependencies_of = mp_unique<mp_apply<mp_append,
    mp_iterate<
        L,
        mp_identity_t,
        list_dependencies_of
        >>>;

The mp_append concatenates the list of lists that mp_iterate gives you, and then mp_unique on top of that since you don't want to have duplicates.

This takes a list, so can be used like recursive_dependencies_of<mp_list<a>> (which is just mp_list<a>) or recursive_dependencies_of<mp_list<d, e, f>> (which is mp_list<d, e, f, a, c, b>).

Demo.

  • Related