How to define a variant extracting subtypes of a template parameter

Question

I am building a state-machine where state transitions are described as a variant, i.e.:

using table = std::variant<
/*             state        event               followup-state    */
    transition<start,       success<sock>,      connecting>,
    transition<start,       exception,          failed>,
    transition<connecting,  success<>,          connected>,
    transition<connecting,  exception,          failed>,
    transition<connected,   exception,          failed>
    >;

and transition being a simple type:

template <typename ENTRY_STATE, typename EVENT, typename NEXT_STATE>
struct transition {
    using entry_state = ENTRY_STATE;
    using event = EVENT;
    using next_state = NEXT_STATE;
};

The state classes are non-polymorphic (and shall not be). My question now is how to define another variant that is able to store all possible states found in the table type (best without duplicates). The type is needed to store the actual state in a type-safe and non-polymorphic way.

From the above table, we have a unique set of entry states:

entry_states = <start,connecting,connected>

and a set of follow-up states:

followup_states = <connecting, connected, failed>

so the resulting variant definition shall be a:

using states = std::variant<entry_states JOINT followup_states>;

=>  using states = std::variant<start,connecting,connected, failed>

I know how to extract type information from the table and access type information of a particular transition, but have no idea how to transfer possible states into a variant definition (without duplicate types).

Any idea is appreciated. However, polymorphism is not a valid solution. Also saving the current state inside a lambda is not an option.

Thanks and best!

PS: the state-machine signature looks like that (I am not posting the full code since it is not meaningful for the question, imo):

template <typename TransitionTable, typename Context>
class state_machine {
public:
    template <typename State, typename Event>
    auto push(State & state, Event & event) {
    ...
    }
protected:
    *using states = std::variant<???>;*
    states current_state;
};

Answer 1

There are two separate tasks:

1. Extracting the states from the transition-table. This is easily done with pattern-matching.
2. Removing duplicates. This can be done with O(log n) depth, the complexity comes from std::tuple_cat which uses std::index_sequence, and additionally directly from the latter.

Code for merging type-lists thrown in as a bonus:

#include <tuple>
#include <utility>
#include <type_traits>

namespace detail {
    template <template <class...> class TT, template <class...> class UU, class... Us>
    auto pack(UU<Us...>)
    -> std::tuple<TT<Us>...>;

    template <template <class...> class TT, class... Ts>
    auto unpack(std::tuple<TT<Ts>...>)
    -> TT<Ts...>;

    template <std::size_t N, class T>
    using TET = std::tuple_element_t<N, T>;

    template <std::size_t N, class T, std::size_t... Is>
    auto remove_duplicates_pack_first(T, std::index_sequence<Is...>)
    -> std::conditional_t<(... || (N > Is && std::is_same_v<TET<N, T>, TET<Is, T>>)), std::tuple<>, std::tuple<TET<N, T>>>;

    template <template <class...> class TT, class... Ts, std::size_t... Is>
    auto remove_duplicates(std::tuple<TT<Ts>...> t, std::index_sequence<Is...> is)
    -> decltype(std::tuple_cat(remove_duplicates_pack_first<Is>(t, is)...));

    template <template <class...> class TT, class... Ts>
    auto remove_duplicates(TT<Ts...> t)
    -> decltype(unpack<TT>(remove_duplicates<TT>(pack<TT>(t), std::make_index_sequence<sizeof...(Ts)>())));
}

template <template <class...> class TT, class... Ts>
using merge_t = decltype(detail::unpack<TT>(std::tuple_cat(detail::pack<TT>(std::declval<Ts>())...)));

template <class T>
using remove_duplicates_t = decltype(detail::remove_duplicates(std::declval<T>()));

Applying it to your transitions-table:

template <template <class...> class TT, class ... Ts>
auto extract_states(TT<Ts...>)
-> TT<typename Ts::entry_state..., typename Ts::next_state...>;

using extracted = decltype(extract_states(std::declval<table>()));
using states = remove_duplicates_t<extracted>;

See it live on coliru.

Answer 2

Taking inspiration from this answer

// ===================================================
// is_in < type, variant<...> >
//     is true_type if type is in the variant
//     is false_type if type is not in the variant

// Assume TElement is not in the list unless proven otherwise
template < typename TElement, typename TList >
struct is_in : public std::false_type {};

// If it matches the first type, it is definitely in the list
template < typename TElement, typename... TTail >
struct is_in < TElement, std::variant< TElement, TTail... > > : public std::true_type {};

// If it is not the first element, check the remaining list
template < typename TElement, typename THead, typename... TTail >
struct is_in < TElement, std::variant< THead, TTail... > > : public is_in < TElement, std::variant< TTail... > > {};

// ===================================================
// add_unique < TNew, typelist<...> >::type
//     is typelist < TNew, ... > if TNew is not already in the list
//     is typelist <...> otherwise

// Append a type to a type_list unless it already exists
template < typename TNew, typename TList,
  bool is_duplicate = is_in < TNew, TList >::value
  >
struct add_unique;

template < typename TNew, typename TList,
  bool is_duplicate = is_in < TNew, TList >::value
  >
using add_unique_t = typename add_unique<TNew, TList, is_duplicate>::type;

// If TNew is in the list, return the list unmodified
template < typename TNew, typename... TList >
struct add_unique < TNew, std::variant< TList... >, true >
{
  using type = std::variant< TList... >;
};

// If TNew is not in the list, append it
template < typename TNew, typename... TList >
struct add_unique < TNew, std::variant< TList... >, false >
{
  using type = std::variant< TNew, TList... >;
};

// ===================================================
// process_arguments < Args... >::type
//     returns a variant of types to be inherited from.
//
// It performs the following actions:
// a) Unpack variant <...> arguments
// b) Ignore values that are already in the list

template < typename... Args >
struct process_arguments;

template < typename... Args >
using process_arguments_t = typename process_arguments<Args...>::type;

// Unpack a variant in the first argument
template < typename... VArgs, typename... Args >
struct process_arguments < std::variant < VArgs... >, Args... >
{
  using type = process_arguments_t < VArgs..., Args... >;
};

// End the recursion if the list is empty
template < >
struct process_arguments < >
{
  using type = std::variant<>;
};

// Construct the list of unique types by appending them one by one
template < typename THead, typename... TTail >
struct process_arguments < THead, TTail... >
{
  using type = add_unique_t < THead, process_arguments_t < TTail... > >;
};

We can then apply process_arguments to TransitionTable's arguments

template<typename Table>
struct transition_traits;

template<typename... Transitions>
struct transition_traits<std::variant<Transitions...>>
{
  using entry_states = process_arguments_t <typename Transitions::entry_state...>;
  using next_states = process_arguments_t <typename Transitions::next_state...>;
  using states = process_arguments_t <typename Transitions::entry_state..., typename Transitions::next_state...>;
};