backmp11/detail/favor_runtime_speed.hpp

0001 // Copyright 2025 Christian Granzin
0002 // Copyright 2008 Christophe Henry
0003 // henry UNDERSCORE christophe AT hotmail DOT com
0004 // This is an extended version of the state machine available in the boost::mpl library
0005 // Distributed under the same license as the original.
0006 // Copyright for the original version:
0007 // Copyright 2005 David Abrahams and Aleksey Gurtovoy. Distributed
0008 // under the Boost Software License, Version 1.0. (See accompanying
0009 // file LICENSE_1_0.txt or copy at
0010 // http://www.boost.org/LICENSE_1_0.txt)
0011
0012 #ifndef BOOST_MSM_BACKMP11_FAVOR_RUNTIME_SPEED_H
0013 #define BOOST_MSM_BACKMP11_FAVOR_RUNTIME_SPEED_H
0014
0015 #include <boost/msm/backmp11/detail/metafunctions.hpp>
0016 #include <boost/msm/backmp11/detail/dispatch_table.hpp>
0017 #include <boost/msm/backmp11/event_traits.hpp>
0018
0019 #include <boost/mpl/advance.hpp>
0020 #include <boost/mpl/begin.hpp>
0021 #include <boost/mpl/bool.hpp>
0022 #include <boost/mpl/empty.hpp>
0023 #include <boost/mpl/erase.hpp>
0024 #include <boost/mpl/eval_if.hpp>
0025 #include <boost/mpl/front.hpp>
0026 #include <boost/mpl/identity.hpp>
0027 #include <boost/mpl/int.hpp>
0028 #include <boost/mpl/pair.hpp>
0029 #include <boost/mpl/pop_front.hpp>
0030
0031
0032 namespace boost { namespace msm { namespace backmp11
0033 {
0034
0035 struct favor_runtime_speed {};
0036
0037 namespace detail
0038 {
0039
0040 template <typename Policy>
0041 struct compile_policy_impl;
0042 template <>
0043 struct compile_policy_impl<favor_runtime_speed>
0044 {
0045     using add_forwarding_rows = mp11::mp_true;
0046
0047     template <typename Event>
0048     static constexpr bool is_completion_event(const Event&)
0049     {
0050         return has_completion_event<Event>::value;
0051     }
0052
0053     template <typename StateMachine, typename Event>
0054     static bool is_end_interrupt_event(StateMachine& sm, const Event&)
0055     {
0056         return sm.template is_flag_active<EndInterruptFlag<Event>>();
0057     }
0058
0059     template <typename StateMachine, typename Event>
0060     static process_result process_event_internal(StateMachine& sm, const Event& event, EventSource source)
0061     {
0062         return sm.process_event_internal_impl(event, source);
0063     }
0064
0065     template <typename Event, typename StateMachine>
0066     static bool is_event_deferred(StateMachine& sm)
0067     {
0068         bool result = false;
0069         auto visitor = [&result](auto& state)
0070         {
0071             using State = std::decay_t<decltype(state)>;
0072             result |= has_state_deferred_event<State, Event>::value;
0073         };
0074         sm.template visit<visit_mode::active_non_recursive>(visitor);
0075         return result;
0076     }
0077     template <typename StateMachine, typename Event>
0078     static bool is_event_deferred(StateMachine& sm, const Event&)
0079     {
0080         return is_event_deferred<Event>(sm);
0081     }
0082
0083     template <typename StateMachine, typename Event>
0084     static void defer_event(StateMachine& sm, Event const& event)
0085     {
0086         if constexpr (is_kleene_event<Event>::value)
0087         {
0088             using event_list = typename StateMachine::event_set_mp11;
0089             bool found =
0090                 for_each_until<mp11::mp_transform<mp11::mp_identity, event_list>>(
0091                     [&sm, &event](auto event_identity)
0092                     {
0093                         using KnownEvent = typename decltype(event_identity)::type;
0094                         if (event.type() == typeid(KnownEvent))
0095                         {
0096                             do_defer_event(sm, *any_cast<KnownEvent>(&event));
0097                             return true;
0098                         }
0099                         return false;
0100                     }
0101             );
0102             if (!found)
0103             {
0104                 for (const auto state_id : sm.get_active_state_ids())
0105                 {
0106                     sm.no_transition(event, sm.get_fsm_argument(), state_id);
0107                 }
0108             }
0109         }
0110         else
0111         {
0112             do_defer_event(sm, event);
0113         }
0114     }
0115
0116     template <typename StateMachine, class Event>
0117     static void do_defer_event(StateMachine& sm, const Event& event)
0118     {
0119         auto& deferred_events = sm.get_deferred_events();
0120         deferred_events.queue.push_back(
0121             {
0122                 [&sm, event]()
0123                 {
0124                     return process_event_internal(
0125                         sm,
0126                         event,
0127                         EventSource::EVENT_SOURCE_DEFERRED);
0128                 },
0129                 [&sm]()
0130                 {
0131                     return is_event_deferred<Event>(sm);
0132                 },
0133                 deferred_events.cur_seq_cnt
0134             }
0135         );
0136     }
0137
0138     struct cell_initializer
0139     {
0140         static void init(generic_cell* entries, const generic_init_cell_value* array, size_t size)
0141         {
0142             for (size_t i=0; i<size; i++)
0143             {
0144                 const auto& item = array[i];
0145                 entries[item.index] = item.address;
0146             }
0147         }
0148     };
0149
0150     // returns a mp11::mp_bool<true> if State has Event as deferred event
0151     template <class State, class Event>
0152     using has_state_deferred_event = mp11::mp_contains<
0153         to_mp_list_t<typename State::deferred_events>,
0154         Event
0155         >;
0156
0157     template<typename Fsm, typename State>
0158     struct table_index
0159     {
0160         using type = mp11::mp_if<
0161             mp11::mp_not<is_same<State, Fsm>>,
0162             mp11::mp_size_t<Fsm::template get_state_id<State>() + 1>,
0163             mp11::mp_size_t<0>
0164             >;
0165     };
0166     template<typename Fsm, typename State>
0167     using get_table_index = typename table_index<Fsm, State>::type;
0168
0169     // Generates a singleton runtime lookup table that maps current state
0170     // to a function that makes the SM take its transition on the given
0171     // Event type.
0172     template<class Fsm>
0173     class dispatch_table
0174     {
0175         using Stt = typename Fsm::complete_table;
0176     public:
0177         // Dispatch function for a specific event.
0178         template<class Event>
0179         using cell = HandledEnum (*)(Fsm&, int,int,Event const&);
0180
0181         // Dispatch an event.
0182         template<class Event>
0183         static HandledEnum dispatch(Fsm& fsm, int region_id, int state_id, const Event& event)
0184         {
0185             return event_dispatch_table<Event>::instance().entries[state_id+1](fsm, region_id, state_id, event);
0186         }
0187
0188         // Dispatch an event to the FSM's internal table.
0189         template<class Event>
0190         static HandledEnum dispatch_internal(Fsm& fsm, int region_id, int state_id, const Event& event)
0191         {
0192             return event_dispatch_table<Event>::instance().entries[0](fsm, region_id, state_id, event);
0193         }
0194
0195     private:
0196         // Compute the maximum state value in the sm so we know how big
0197         // to make the tables
0198         typedef typename generate_state_set<Stt>::state_set state_set;
0199         BOOST_STATIC_CONSTANT(int, max_state = (mp11::mp_size<state_set>::value));
0200
0201         // Dispatch table for a specific event.
0202         template<class Event>
0203         class event_dispatch_table
0204         {
0205         public:
0206             using event_cell = cell<Event>;
0207
0208             // The singleton instance.
0209             static const event_dispatch_table& instance() {
0210                 static event_dispatch_table table;
0211                 return table;
0212             }
0213
0214         private:
0215             // A function object for use with mp11::mp_for_each that stuffs transitions into cells.
0216             class row_init_helper
0217             {
0218             public:
0219                 row_init_helper(event_cell* entries)
0220                     : m_entries(entries) {}
0221
0222                 template<typename Row>
0223                 typename ::boost::disable_if<typename is_kleene_event<typename Row::transition_event>::type, void>::type
0224                     operator()(Row)
0225                 {
0226                     m_entries[get_table_index<Fsm, typename Row::current_state_type>::value] =
0227                         &Row::execute;
0228                 }
0229
0230                 template<typename Row>
0231                 typename ::boost::enable_if<typename is_kleene_event<typename Row::transition_event>::type, void>::type
0232                     operator()(Row)
0233                 {
0234                     m_entries[get_table_index<Fsm, typename Row::current_state_type>::value] =
0235                         &convert_event_and_forward<Row>::execute;
0236                 }
0237
0238             private:
0239                 event_cell* m_entries;
0240             };
0241
0242             static process_result execute_no_transition(Fsm&, int, int, const Event&)
0243             {
0244                 return process_result::HANDLED_FALSE;
0245             }
0246
0247             // initialize the dispatch table for a given Event and Fsm
0248             event_dispatch_table()
0249             {
0250                 // Initialize cells for no transition
0251                 for (size_t i=0;i<max_state+1; i++)
0252                 {
0253                     entries[i] = &execute_no_transition;
0254                 }
0255
0256                 // build chaining rows for rows coming from the same state and the current event
0257                 // first we build a map of sequence for every source
0258                 // in reverse order so that the frow's are handled first (UML priority)
0259                 typedef mp11::mp_fold<
0260                     mp11::mp_copy_if<
0261                         to_mp_list_t<Stt>,
0262                         event_filter_predicate
0263                         >,
0264                     mp11::mp_list<>,
0265                     map_updater
0266                     > map_of_row_seq;
0267                 // and then build chaining rows for all source states having more than 1 row
0268                 typedef mp11::mp_transform<
0269                     row_chainer,
0270                     map_of_row_seq
0271                     > chained_rows;
0272
0273                 // Go back and fill in cells for matching transitions.
0274 // MSVC crashes when using get_init_cells.
0275 #if !defined(_MSC_VER)
0276                 typedef mp11::mp_transform<
0277                     preprocess_row,
0278                     chained_rows
0279                     > chained_and_preprocessed_rows;
0280                 event_cell_initializer::init(
0281                     reinterpret_cast<generic_cell*>(entries),
0282                     get_init_cells<event_cell, chained_and_preprocessed_rows>(),
0283                     mp11::mp_size<chained_and_preprocessed_rows>::value
0284                     );
0285 #else
0286                 mp11::mp_for_each<chained_rows>(row_init_helper{entries});
0287 #endif
0288             }
0289
0290             // class used to build a chain (or sequence) of transitions for a given event and start state
0291             // (like an UML diamond). Allows transition conflicts.
0292             template< typename Seq,typename AnEvent,typename State >
0293             struct chain_row
0294             {
0295                 typedef State   current_state_type;
0296                 typedef AnEvent transition_event;
0297
0298                 // helper for building a disable/enable_if-controlled execute function
0299                 struct execute_helper
0300                 {
0301                     template <class Sequence>
0302                     static
0303                     HandledEnum
0304                     execute(Fsm& , int, int, Event const& , ::boost::mpl::true_ const & )
0305                     {
0306                         // if at least one guard rejected, this will be ignored, otherwise will generate an error
0307                         return HandledEnum::HANDLED_FALSE;
0308                     }
0309
0310                     template <class Sequence>
0311                     static
0312                     HandledEnum
0313                     execute(Fsm& fsm, int region_index , int state, Event const& evt,
0314                             ::boost::mpl::false_ const & )
0315                     {
0316                         // try the first guard
0317                         typedef typename ::boost::mpl::front<Sequence>::type first_row;
0318                         HandledEnum res = first_row::execute(fsm,region_index,state,evt);
0319                         if (HandledEnum::HANDLED_TRUE!=res && HandledEnum::HANDLED_DEFERRED!=res)
0320                         {
0321                             // if the first rejected, move on to the next one
0322                             HandledEnum sub_res =
0323                                 execute<typename ::boost::mpl::pop_front<Sequence>::type>(fsm,region_index,state,evt,
0324                                     ::boost::mpl::bool_<
0325                                         ::boost::mpl::empty<typename ::boost::mpl::pop_front<Sequence>::type>::type::value>());
0326                             // if at least one guards rejects, the event will not generate a call to no_transition
0327                             if ((HandledEnum::HANDLED_FALSE==sub_res) && (HandledEnum::HANDLED_GUARD_REJECT==res) )
0328                                 return HandledEnum::HANDLED_GUARD_REJECT;
0329                             else
0330                                 return sub_res;
0331                         }
0332                         return res;
0333                     }
0334                 };
0335                 // Take the transition action and return the next state.
0336                 static HandledEnum execute(Fsm& fsm, int region_index, int state, Event const& evt)
0337                 {
0338                     // forward to helper
0339                     return execute_helper::template execute<Seq>(fsm,region_index,state,evt,
0340                         ::boost::mpl::bool_< ::boost::mpl::empty<Seq>::type::value>());
0341                 }
0342             };
0343             // nullary metafunction whose only job is to prevent early evaluation of _1
0344             template< typename Entry >
0345             struct make_chain_row_from_map_entry
0346             {
0347                 // if we have more than one frow with the same state as source, remove the ones extra
0348                 // note: we know the frow's are located at the beginning so we remove at the beginning (number of frows - 1) elements
0349                 enum { number_frows = boost::mp11::mp_count_if<typename Entry::second, has_is_frow>::value };
0350
0351                 //erases the first NumberToDelete rows
0352                 template<class Sequence, int NumberToDelete>
0353                 struct erase_first_rows
0354                 {
0355                     typedef typename ::boost::mpl::erase<
0356                         typename Entry::second,
0357                         typename ::boost::mpl::begin<Sequence>::type,
0358                         typename ::boost::mpl::advance<
0359                                 typename ::boost::mpl::begin<Sequence>::type,
0360                                 ::boost::mpl::int_<NumberToDelete> >::type
0361                     >::type type;
0362                 };
0363                 // if we have more than 1 frow with this event (not allowed), delete the spare
0364                 typedef typename ::boost::mpl::eval_if<
0365                     typename ::boost::mpl::bool_< number_frows >= 2 >::type,
0366                     erase_first_rows<typename Entry::second,number_frows-1>,
0367                     ::boost::mpl::identity<typename Entry::second>
0368                 >::type filtered_stt;
0369
0370                 typedef chain_row<filtered_stt,Event,
0371                     typename Entry::first > type;
0372             };
0373             // helper for lazy evaluation in eval_if of change_frow_event
0374             template <class Transition,class NewEvent>
0375             struct replace_event
0376             {
0377                 typedef typename Transition::template replace_event<NewEvent>::type type;
0378             };
0379             // changes the event type for a frow to the event we are dispatching
0380             // this helps ensure that an event does not get processed more than once because of frows and base events.
0381             template <class FrowTransition>
0382             struct change_frow_event
0383             {
0384                 typedef typename ::boost::mp11::mp_if_c<
0385                     has_is_frow<FrowTransition>::type::value,
0386                     replace_event<FrowTransition,Event>,
0387                     boost::mp11::mp_identity<FrowTransition>
0388                 >::type type;
0389             };
0390
0391             template <class Row>
0392             struct convert_event_and_forward
0393             {
0394                 static HandledEnum execute(Fsm& fsm, int region_index, int state, Event const& evt)
0395                 {
0396                     typename Row::transition_event forwarded(evt);
0397                     return Row::execute(fsm,region_index,state,forwarded);
0398                 }
0399             };
0400
0401             using event_init_cell_value = init_cell_value<event_cell>;
0402
0403             template<size_t v1, event_cell v2>
0404             using init_cell_constant = init_cell_constant<v1, event_cell, v2>;
0405
0406             template<event_cell v>
0407             using cell_constant = std::integral_constant<event_cell, v>;
0408
0409             using event_cell_initializer = cell_initializer;
0410
0411             // Helpers for row processing
0412             // First operation (fold)
0413             template <typename T>
0414             using event_filter_predicate = mp11::mp_and<
0415                 mp11::mp_not<has_not_real_row_tag<T>>,
0416                 mp11::mp_or<
0417                     std::is_base_of<typename T::transition_event, Event>,
0418                     typename is_kleene_event<typename T::transition_event>::type
0419                     >
0420                 >;
0421             template <typename M, typename Key, typename Value>
0422             using push_map_value = mp11::mp_push_front<
0423                 mp11::mp_second<mp11::mp_map_find<M, Key>>,
0424                 Value>;
0425             template<typename M, typename T>
0426             using map_updater = mp11::mp_map_replace<
0427                 M,
0428                 mp11::mp_list<
0429                     typename T::current_state_type,
0430                     mp11::mp_eval_if_c<
0431                         !mp11::mp_map_contains<M, typename T::current_state_type>::value,
0432                         // first row on this source state, make a list with 1 element
0433                         mp11::mp_list<typename change_frow_event<T>::type>,
0434                         // list already exists, add the row
0435                         push_map_value,
0436                         M,
0437                         typename T::current_state_type,
0438                         typename change_frow_event<T>::type
0439                         >
0440                     >
0441                 >;
0442             // Second operation (transform)
0443             template<typename T>
0444             using to_mpl_map_entry = mpl::pair<
0445                 mp11::mp_first<T>,
0446                 mp11::mp_second<T>
0447                 >;
0448             template<typename T>
0449             using row_chainer = mp11::mp_if_c<
0450                 (mp11::mp_size<to_mp_list_t<mp11::mp_second<T>>>::value > 1),
0451                 // we need row chaining
0452                 typename make_chain_row_from_map_entry<to_mpl_map_entry<T>>::type,
0453                 // just one row, no chaining, we rebuild the row like it was before
0454                 mp11::mp_front<mp11::mp_second<T>>
0455                 >;
0456             template<typename Row>
0457             using preprocess_row_helper = cell_constant<&Row::execute>;
0458             template<typename Row>
0459             using preprocess_row = init_cell_constant<
0460                 // Offset into the entries array
0461                 get_table_index<Fsm, typename Row::current_state_type>::value,
0462                 // Address of the execute function
0463                 mp11::mp_eval_if_c<
0464                     is_kleene_event<typename Row::transition_event>::type::value,
0465                     cell_constant<
0466                         &convert_event_and_forward<Row>::execute
0467                         >,
0468                     preprocess_row_helper,
0469                     Row
0470                     >::value
0471                 >;
0472
0473         // data members
0474         public:
0475             // max_state+1, because 0 is reserved for this fsm (internal transitions)
0476             event_cell entries[max_state+1];
0477         };
0478     };
0479 };
0480
0481 } // detail
0482
0483 }}} // boost::msm::backmp11
0484
0485
0486 #endif //BOOST_MSM_BACKMP11_FAVOR_RUNTIME_SPEED_H