Как определить вариант<x, y, z> извлечения подтипов параметра шаблона

Question

Я строю конечный автомат, где переходы состояний описываются как вариант, то есть:

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>
    >;

и переход, являющийся простым типом:

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

Классы состояния не являются полиморфными (и не должны быть). Мой вопрос теперь состоит в том, как определить другой вариант, который может хранить все возможные состояния, найденные в табличном типе (лучше всего без дубликатов). Тип необходим для хранения фактического состояния безопасным и неполиморфным способом.

Из приведенной выше таблицы у нас есть уникальный набор состояний входа:

entry_states = <start,connecting,connected>

и набор последующих состояний:

followup_states = <connecting, connected, failed>

итоговое определение варианта должно быть:

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

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

Я знаю, как извлечь информацию о типе из таблицы и информацию о типе доступа конкретного перехода, но не знаю, как перенести возможные состояния в определение варианта (без дублирующих типов).

Любая идея приветствуется. Тем не менее, полиморфизм не является допустимым решением. Также сохранение текущего состояния внутри лямбды не вариант.

Спасибо и всего наилучшего!

PS: подпись конечного автомата выглядит так (я не публикую полный код, поскольку он не имеет значения для вопроса, 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

Есть две отдельные задачи:

1. Извлечение состояний из таблицы переходов. Это легко сделать с помощью сопоставления с образцом.
2. Удаление дубликатов. Это может быть сделано с O(log n) глубиной, сложность исходит от std::tuple_cat который использует std::index_sequenceи дополнительно непосредственно от последнего.

Код для объединения списков типов, добавленных в качестве бонуса:

#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>()));

Применяя его к вашей таблице переходов:

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>;

Посмотри вживую на колиру.

Answer 2

Черпая вдохновение из этого ответа

// ===================================================
// 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... > >;
};

Затем мы можем подать заявку process_arguments в TransitionTableаргументы

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...>;
};