Enum Filter

I have recently encountered code that is structurally similar to the following:

enum class number {
    zero,
    one,
    two,
    three,
    four,
    five,
    six,
    seven,
    end
};

…

if (value == number::two ||
    value == number::three ||
    value == number::five ||
    value == number::seven) {
    …
}

This does not look good to me. So the natural questions comes: How can we make the code ‘better’?

While this is a fake example, I hope you can see the point that enumerators have specific properties (which I will call ‘traits’ in this article, as per common C++ traditions), and I want the code to express the intent as expressed by traits.

However, let us get rid of ‘value ==’ first. Any repetitions are bad, right?

My first take is something as follows:

template <typename T>
bool is_in(const T& value,
           std::initializer_list<T> value_list)
{
    for (const auto& item : value_list) {
        if (value == item) {
            return true;
        }
    }
    return false;
}

Very simply and straightforward, but not good enough. How can we generate the list, given some criteria?

If you are familiar with the concept of template metaprogramming, you know that this is a compile-time programming topic: compile-time filtering.

In order to filter on the enumerators, we need to describe them with traits. The following code could be good enough for our current purpose:

template <number n>
struct number_traits;

template <>
struct number_traits<number::zero> {
    constexpr bool is_prime = false;
}

template <>
struct number_traits<number::one> {
    constexpr bool is_prime = false;
}

template <>
struct number_traits<number::two> {
    constexpr bool is_prime = true;
}

template <>
struct number_traits<number::three> {
    constexpr bool is_prime = true;
}

template <>
struct number_traits<number::four> {
    constexpr bool is_prime = false;
}

template <>
struct number_traits<number::five> {
    constexpr bool is_prime = true;
}

template <>
struct number_traits<number::six> {
    constexpr bool is_prime = false;
}

template <>
struct number_traits<number::seven> {
    constexpr bool is_prime = true;
}

So, let us try figuring out a way to generate such a list.

After some study, you will know that initializer_list is not fit for such manipulations. tuple is a better utility. The main reason is that we had better manipulate types, instead of values, in template metaprogramming. An initializer_list is not capable of doing that, whereas C++ already provides a facility to convert compile-time integral constants into types, its name being exactly integral_constant.

Its approximate definition is as follows, in case you are not familiar with it:

template<class T, T v>
struct integral_constant {
    static constexpr T value = v;
    using value_type = T;
    using type = integral_constant;
    constexpr operator value_type() const noexcept
    {
        return value;
    }
    constexpr value_type operator()() const noexcept
    {
        return value;
    }
};

Such a definition is already provided by the standard library. So, instead of having an initializer_list like {number::two, number::three, number::five}, we would have something like the following:

std::make_tuple(
    std::integral_constant<number, number::two>{},
    std::integral_constant<number, number::three>{},
    std::integral_constant<number, number::five>{})

It would be safe to pass such ‘arguments’ for compile-time programming, as only their types matter. We would not need their values, as each type has exactly one unique value.

The next questions are:

  1. How can we generate the constants for all possible enumerators? —I.e. compile-time iteration.
  2. How can we filter only the values we want? —I.e. compile-time filtering.

The answer to the first question is that we need to generate a sequence, and we need to know what the last enumerator is. As far as I know, there is currently no way in C++ to enumerate all the enumerators of an enum type. I have to resort to an agreement to mark the end of a continuous enumeration, and my choice is that we use end to mark the end, as in the enum class listed in the very beginning of this article. That is, I need to generate the sequence from integral_constant<number, number{0}> to integral_constant<number, number::end>, exclusive.

This job can be easily done with the following code, using the standard tuple and index_sequence technique:

template <typename E, size_t... ints>
constexpr auto make_all_enum_consts_impl(
    std::index_sequence<int...>)
{
    return std::make_tuple(std::integral_constant<
        E, E(ints)>{}...);
}

template <typename E>
constexpr auto make_all_enum_consts()
{
    return make_all_enum_consts_impl<E>(
        std::make_index_sequence<size_t(E::end)>{});
}

Now we have come to the really difficult part: how can we filter the values to get only those we need?

The answer is apply, tuple_cat, and conditional_t, three important tools in the C++ template metaprogramming world:

  • With apply, we can call a function with all elements of a tuple as arguments. I.e. apply(f, make_tuple(42, "answer")) would be equivalent to f(42, "answer").
  • With tuple_cat, we can concatenate elements of tuples into a new tuple. I.e. tuple_cat(make_tuple(42, "answer"), make_tuple("of", "everything")) would result in the tuple {42, "answer", "of", "everything"}.
  • With conditional_t, we can get one of the given types based on a compile-time Boolean expression. I.e. conditional_t<true, int, string> would result in int, but conditional_t<false, int, string> would result in string.

Each tool may look trivial individually, but they can be combined together to work wonders. Specifically, it can do what we now need.

This is the final form I use (mainly inspired by this Stack Overflow answer):

#define ENUM_FILTER_FROM(E, T, tup)                      \
    std::apply(                                          \
        [](auto... ts) {                                 \
            return std::tuple_cat(                       \
                std::conditional_t<                      \
                    E##_traits<decltype(ts)::value>::T,  \
                    std::tuple<decltype(ts)>,            \
                    std::tuple<>>{}...);                 \
        },                                               \
        tup)

Let me explain what it does:

  • The macro takes an enumeration type, a trait name, and a tuple of enumerator constants, which are created by make_all_enum_consts above. The reason why a tuple of constants are used is that the result of calling ENUM_FILTER_FROM can be filtered again.
  • std::apply invokes the generic lambda with the tuple of arguments
  • The generic lambda does the compile-time computation of concatenating (tuple_cat) the arguments into a new tuple
  • The arguments of tuple_cat is either a tuple of one enumerator constant, if the type satisfies the trait, or an empty tuple otherwise
  • So the end result of executing the code in the macro is a tuple of enumerator constants that satisfy the trait

Finally, we can define the function is_prime:

constexpr bool is_prime(number n)
{
    return is_in(n,
                 make_values_from_consts(ENUM_FILTER_FROM(
                     number, is_prime,
                     make_all_enum_consts<number>())));
}

More interestingly, the result of invoking ENUM_FILTER_FROM can be passed to ENUM_FILTER_FROM again. If we defined the trait is_even as well as is_prime, we would be able to write:

ENUM_FILTER_FROM(number, is_even, \
    ENUM_FILTER_FROM(number, is_prime, …)

Is that nice?

Do note that there is an asymmetry here. It is trivial to implement make_values_from_consts, but it seems impossible to implement its inverse constexpr function make_consts_from_values. This is because there are no constexpr arguments in C++. No arguments are regarded constexpr, even in a constexpr function. You can work around the problem in a cumbersome way, but for this post I am sticking to using types as long as possible.

That’s it, my experience of using compile-time filtering. I wish you could find the technique described here useful.

One thought on “Enum Filter

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s