msm/back11/dispatch_table.hpp

0001 // Copyright 2008 Christophe Henry
0002 // henry UNDERSCORE christophe AT hotmail DOT com
0003 // This is an extended version of the state machine available in the boost::mpl library
0004 // Distributed under the same license as the original.
0005 // Copyright for the original version:
0006 // Copyright 2005 David Abrahams and Aleksey Gurtovoy. Distributed
0007 // under the Boost Software License, Version 1.0. (See accompanying
0008 // file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010
0011 #ifndef BOOST_MSM_BACK11_DISPATCH_TABLE_H
0012 #define BOOST_MSM_BACK11_DISPATCH_TABLE_H
0013
0014 #include <cstdint>
0015
0016 #include <utility>
0017
0018 #include <boost/mpl/reverse_fold.hpp>
0019 #include <boost/mpl/greater.hpp>
0020 #include <boost/mpl/filter_view.hpp>
0021 #include <boost/mpl/pop_front.hpp>
0022 #include <boost/mpl/for_each.hpp>
0023 #include <boost/mpl/advance.hpp>
0024
0025 #include <boost/fusion/container/vector.hpp>
0026 #include <boost/fusion/container/map.hpp>
0027 #include <boost/fusion/include/push_back.hpp>
0028 #include <boost/fusion/include/make_vector.hpp>
0029
0030 #include <boost/type_traits/is_base_of.hpp>
0031 #include <boost/type_traits/is_same.hpp>
0032
0033 #include <boost/msm/event_traits.hpp>
0034 #include <boost/msm/back11/metafunctions.hpp>
0035 #include <boost/msm/back/common_types.hpp>
0036
0037 BOOST_MPL_HAS_XXX_TRAIT_DEF(is_frow)
0038
0039 namespace boost { namespace msm { namespace back11
0040 {
0041
0042 // Generates a singleton runtime lookup table that maps current state
0043 // to a function that makes the SM take its transition on the given
0044 // Event type.
0045 template <class Fsm,class Stt, class Event,class CompilePolicy>
0046 struct dispatch_table
0047 {
0048  private:
0049     // This is a table of these function pointers.
0050     typedef boost::msm::back::HandledEnum (*cell)(Fsm&, int,int,Event&);
0051     typedef bool (*guard)(Fsm&, Event&);
0052
0053     // class used to build a chain (or sequence) of transitions for a given event and start state
0054     // (like an UML diamond). Allows transition conflicts.
0055     template< typename Seq,typename AnEvent,typename State >
0056     struct chain_row
0057     {
0058         typedef State   current_state_type;
0059         typedef AnEvent transition_event;
0060
0061         // helper for building a disable/enable_if-controlled execute function
0062         struct execute_helper
0063         {
0064             template <class Sequence>
0065             static
0066             boost::msm::back::HandledEnum
0067             execute(Fsm& , int, int, Event& , ::boost::mpl::true_ const & )
0068             {
0069                 // if at least one guard rejected, this will be ignored, otherwise will generate an error
0070                 return ::boost::msm::back::HANDLED_FALSE;
0071             }
0072
0073             template <class Sequence>
0074             static
0075             boost::msm::back::HandledEnum
0076             execute(Fsm& fsm, int region_index , int state, Event& evt,
0077                     ::boost::mpl::false_ const & )
0078             {
0079                  // try the first guard
0080                  typedef typename ::boost::mpl::front<Sequence>::type first_row;
0081                  boost::msm::back::HandledEnum res = first_row::execute(fsm,region_index,state,evt);
0082                  if (::boost::msm::back::HANDLED_TRUE!=res && ::boost::msm::back::HANDLED_DEFERRED!=res)
0083                  {
0084                     // if the first rejected, move on to the next one
0085                     boost::msm::back::HandledEnum sub_res =
0086                          execute<typename ::boost::mpl::pop_front<Sequence>::type>(fsm,region_index,state,evt,
0087                             ::boost::mpl::bool_<
0088                                 ::boost::mpl::empty<typename ::boost::mpl::pop_front<Sequence>::type>::type::value>());
0089                     // if at least one guards rejects, the event will not generate a call to no_transition
0090                     if ((::boost::msm::back::HANDLED_FALSE==sub_res) && (::boost::msm::back::HANDLED_GUARD_REJECT==res) )
0091                         return ::boost::msm::back::HANDLED_GUARD_REJECT;
0092                     else
0093                         return sub_res;
0094                  }
0095                  return res;
0096             }
0097         };
0098         // Take the transition action and return the next state.
0099         static boost::msm::back::HandledEnum execute(Fsm& fsm, int region_index, int state, Event& evt)
0100         {
0101             // forward to helper
0102             return execute_helper::template execute<Seq>(fsm,region_index,state,evt,
0103                 ::boost::mpl::bool_< ::boost::mpl::empty<Seq>::type::value>());
0104         }
0105     };
0106     // nullary metafunction whose only job is to prevent early evaluation of _1
0107     template< typename Entry >
0108     struct make_chain_row_from_map_entry
0109     {
0110         // if we have more than one frow with the same state as source, remove the ones extra
0111         // note: we know the frow's are located at the beginning so we remove at the beginning (number of frows - 1) elements
0112         enum {number_frows = ::boost::mpl::count_if< typename Entry::second,has_is_frow< ::boost::mpl::placeholders::_1> >::value};
0113
0114         //erases the first NumberToDelete rows
0115         template<class Sequence, int NumberToDelete>
0116         struct erase_first_rows
0117         {
0118             typedef typename ::boost::mpl::erase<
0119                 typename Entry::second,
0120                 typename ::boost::mpl::begin<Sequence>::type,
0121                 typename ::boost::mpl::advance<
0122                         typename ::boost::mpl::begin<Sequence>::type,
0123                         ::boost::mpl::int_<NumberToDelete> >::type
0124             >::type type;
0125         };
0126         // if we have more than 1 frow with this event (not allowed), delete the spare
0127         typedef typename ::boost::mpl::eval_if<
0128             typename ::boost::mpl::bool_< number_frows >= 2 >::type,
0129             erase_first_rows<typename Entry::second,number_frows-1>,
0130             ::boost::mpl::identity<typename Entry::second>
0131         >::type filtered_stt;
0132
0133         typedef chain_row<filtered_stt,Event,
0134             typename Entry::first > type;
0135     };
0136     template< typename Entry >
0137     struct make_chain_row_from_map_entry2
0138     {
0139         // if we have more than one frow with the same state as source, remove the ones extra
0140         // note: we know the frow's are located at the beginning so we remove at the beginning (number of frows - 1) elements
0141         typedef typename boost::fusion::result_of::first<Entry>::type entry_vec_first;
0142         typedef typename boost::fusion::result_of::second<Entry>::type entry_vec_second;
0143         //typedef typename Entry::second_type entry_vec_second;
0144
0145         enum {number_frows = ::boost::mpl::count_if<entry_vec_second,has_is_frow< ::boost::mpl::placeholders::_1> >::value};
0146
0147         //erases the first NumberToDelete rows
0148         template<class Sequence, int NumberToDelete>
0149         struct erase_first_rows
0150         {
0151             typedef typename ::boost::mpl::erase<
0152                 typename Entry::second,
0153                 typename ::boost::mpl::begin<Sequence>::type,
0154                 typename ::boost::mpl::advance<
0155                         typename ::boost::mpl::begin<Sequence>::type,
0156                         ::boost::mpl::int_<NumberToDelete> >::type
0157             >::type type;
0158         };
0159         // if we have more than 1 frow with this event (not allowed), delete the spare
0160         typedef typename ::boost::mpl::eval_if<
0161             typename ::boost::mpl::bool_< number_frows >= 2 >::type,
0162             erase_first_rows<entry_vec_second,number_frows-1>,
0163             ::boost::mpl::identity<entry_vec_second>
0164         >::type filtered_stt;
0165
0166         typedef chain_row<filtered_stt,Event,entry_vec_first > type;
0167     };
0168
0169     // helper for lazy evaluation in eval_if of change_frow_event
0170     template <class Transition,class NewEvent>
0171     struct replace_event
0172     {
0173         typedef typename Transition::template replace_event<NewEvent>::type type;
0174     };
0175     // changes the event type for a frow to the event we are dispatching
0176     // this helps ensure that an event does not get processed more than once because of frows and base events.
0177     template <class FrowTransition>
0178     struct change_frow_event
0179     {
0180         typedef typename ::boost::mpl::eval_if<
0181             typename has_is_frow<FrowTransition>::type,
0182             replace_event<FrowTransition,Event>,
0183             boost::mpl::identity<FrowTransition>
0184         >::type type;
0185     };
0186     // Compute the maximum state value in the sm so we know how big
0187     // to make the table
0188     typedef typename generate_state_set<Stt>::type state_list;
0189     BOOST_STATIC_CONSTANT(int, max_state = ( ::boost::mpl::size<state_list>::value));
0190
0191     template <class Transition>
0192     struct convert_event_and_forward
0193     {
0194         static boost::msm::back::HandledEnum execute(Fsm& fsm, int region_index, int state, Event& evt)
0195         {
0196             typename Transition::transition_event forwarded(evt);
0197             return Transition::execute(fsm,region_index,state,forwarded);
0198         }
0199     };
0200
0201     template <class T, class Map>
0202     struct push_to_map_of_vec
0203     {
0204         typedef typename
0205         boost::fusion::result_of::as_map<
0206             typename boost::fusion::result_of::make_vector<
0207                 typename ::boost::fusion::result_of::make_pair<
0208                     typename transition_source_type<T>::type,
0209                     typename ::boost::mpl::push_back<
0210                         typename ::boost::fusion::result_of::value_at_key<
0211                             Map,
0212                             typename transition_source_type<T>::type
0213                         >::type,
0214                         typename change_frow_event<T>::type
0215                     >::type
0216                 >::type
0217             >::type
0218         >::type type;
0219     };
0220
0221     // A function object for use with mpl::for_each that stuffs
0222     // transitions into cells.
0223     struct init_cell
0224     {
0225         init_cell(dispatch_table* self_)
0226           : self(self_)
0227         {}
0228         // version for transition event not base of our event
0229         // first for all transitions, then for internal ones of a fsm
0230         template <class Transition>
0231         typename ::boost::disable_if<
0232             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0233         ,void>::type
0234         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::false_ const &) const
0235         {
0236             typedef typename create_stt<Fsm>::type stt;
0237             BOOST_STATIC_CONSTANT(int, state_id =
0238                 (get_state_id<stt,typename Transition::current_state_type>::value));
0239             // reinterpret_cast to uintptr_t to suppress gcc-11 warning
0240             self->entries[state_id+1] = reinterpret_cast<cell>(
0241                 reinterpret_cast<std::uintptr_t>(&Transition::execute));
0242         }
0243         template <class Transition>
0244         typename ::boost::enable_if<
0245             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0246         ,void>::type
0247         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::false_ const &) const
0248         {
0249             self->entries[0] = reinterpret_cast<cell>(&Transition::execute);
0250         }
0251
0252         // version for transition event is boost::any
0253         // first for all transitions, then for internal ones of a fsm
0254         template <class Transition>
0255         typename ::boost::disable_if<
0256             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0257         ,void>::type
0258         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::true_ const &) const
0259         {
0260             typedef typename create_stt<Fsm>::type stt;
0261             BOOST_STATIC_CONSTANT(int, state_id =
0262                 (get_state_id<stt,typename Transition::current_state_type>::value));
0263             self->entries[state_id+1] = &convert_event_and_forward<Transition>::execute;
0264         }
0265         template <class Transition>
0266         typename ::boost::enable_if<
0267             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0268         ,void>::type
0269         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::true_ const &) const
0270         {
0271             self->entries[0] = &convert_event_and_forward<Transition>::execute;
0272         }
0273         template <class Transition>
0274         typename ::boost::disable_if<
0275             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0276         ,void>::type
0277         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::true_ const &) const
0278         {
0279             typedef typename create_stt<Fsm>::type stt;
0280             BOOST_STATIC_CONSTANT(int, state_id =
0281                 (get_state_id<stt,typename Transition::current_state_type>::value));
0282             self->entries[state_id+1] = &convert_event_and_forward<Transition>::execute;
0283         }
0284         template <class Transition>
0285         typename ::boost::enable_if<
0286             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0287         ,void>::type
0288         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::true_ const &) const
0289         {
0290             self->entries[0] = &convert_event_and_forward<Transition>::execute;
0291         }
0292         // end version for kleene
0293
0294         // version for transition event base of our event
0295         // first for all transitions, then for internal ones of a fsm
0296         template <class Transition>
0297         typename ::boost::disable_if<
0298             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0299         ,void>::type
0300         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::false_ const &) const
0301         {
0302             typedef typename create_stt<Fsm>::type stt;
0303             BOOST_STATIC_CONSTANT(int, state_id =
0304                 (get_state_id<stt,typename Transition::current_state_type>::value));
0305             self->entries[state_id+1] = &Transition::execute;
0306         }
0307         template <class Transition>
0308         typename ::boost::enable_if<
0309             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
0310         ,void>::type
0311         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::false_ const &) const
0312         {
0313             self->entries[0] = &Transition::execute;
0314         }
0315         // Cell initializer function object, used with mpl::for_each
0316         template <class Transition>
0317         typename ::boost::enable_if<typename has_not_real_row_tag<Transition>::type,void >::type
0318             operator()(Transition const&,boost::msm::back::dummy<0> = 0) const
0319         {
0320             // version for not real rows. No problem because irrelevant for process_event
0321         }
0322         template <class Transition>
0323         typename ::boost::disable_if<typename has_not_real_row_tag<Transition>::type,void >::type
0324         operator()(Transition const& tr,boost::msm::back::dummy<1> = 0) const
0325         {
0326             //only if the transition event is a base of our event is the reinterpret_case safe
0327             init_event_base_case(tr,
0328                 ::boost::mpl::bool_<
0329                     ::boost::is_base_of<typename Transition::transition_event,Event>::type::value>(),
0330                 ::boost::mpl::bool_<
0331                     ::boost::msm::is_kleene_event<typename Transition::transition_event>::type::value>());
0332         }
0333
0334         dispatch_table* self;
0335     };
0336
0337     // Cell default-initializer function object, used with mpl::for_each
0338     // initializes with call_no_transition, defer_transition or default_eventless_transition
0339     // variant for non-anonymous transitions
0340     template <class EventType,class Enable=void>
0341     struct default_init_cell
0342     {
0343         default_init_cell(dispatch_table* self_,cell* tofill_entries_)
0344             : self(self_),tofill_entries(tofill_entries_)
0345         {}
0346         template <class State>
0347         typename ::boost::enable_if<typename has_state_delayed_event<State,Event>::type,void>::type
0348         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<0> = 0)
0349         {
0350             typedef typename create_stt<Fsm>::type stt;
0351             BOOST_STATIC_CONSTANT(int, state_id = (get_state_id<stt,State>::value));
0352             cell call_no_transition = &Fsm::defer_transition;
0353             tofill_entries[state_id+1] = call_no_transition;
0354         }
0355         template <class State>
0356         typename ::boost::disable_if<
0357             typename ::boost::mpl::or_<
0358                 typename has_state_delayed_event<State,Event>::type,
0359                 typename ::boost::is_same<State,Fsm>::type
0360             >::type
0361         ,void >::type
0362         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<1> = 0)
0363         {
0364             typedef typename create_stt<Fsm>::type stt;
0365             BOOST_STATIC_CONSTANT(int, state_id = (get_state_id<stt,State>::value));
0366             cell call_no_transition = &Fsm::call_no_transition;
0367             tofill_entries[state_id+1] = call_no_transition;
0368         }
0369         // case for internal transitions of this fsm
0370         template <class State>
0371         typename ::boost::enable_if<
0372             typename ::boost::mpl::and_<
0373                 typename ::boost::mpl::not_<typename has_state_delayed_event<State,Event>::type>::type,
0374                 typename ::boost::is_same<State,Fsm>::type
0375             >::type
0376         ,void>::type
0377         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<2> = 0)
0378         {
0379             cell call_no_transition = &Fsm::call_no_transition_internal;
0380             tofill_entries[0] = call_no_transition;
0381         }
0382         dispatch_table* self;
0383         cell* tofill_entries;
0384     };
0385
0386     // variant for anonymous transitions
0387     template <class EventType>
0388     struct default_init_cell<EventType,
0389                              typename ::boost::enable_if<
0390                                 typename is_completion_event<EventType>::type>::type>
0391     {
0392         default_init_cell(dispatch_table* self_,cell* tofill_entries_)
0393             : self(self_),tofill_entries(tofill_entries_)
0394         {}
0395
0396         // this event is a compound one (not a real one, just one for use in event-less transitions)
0397         // Note this event cannot be used as deferred!
0398         // case for internal transitions of this fsm
0399         template <class State>
0400         typename ::boost::disable_if<
0401             typename ::boost::is_same<State,Fsm>::type
0402         ,void>::type
0403         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<0> = 0)
0404         {
0405             typedef typename create_stt<Fsm>::type stt;
0406             BOOST_STATIC_CONSTANT(int, state_id = (get_state_id<stt,State>::value));
0407             cell call_no_transition = &Fsm::default_eventless_transition;
0408             tofill_entries[state_id+1] = call_no_transition;
0409         }
0410
0411         template <class State>
0412         typename ::boost::enable_if<
0413             typename ::boost::is_same<State,Fsm>::type
0414         ,void>::type
0415         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<1> = 0)
0416         {
0417             cell call_no_transition = &Fsm::default_eventless_transition;
0418             tofill_entries[0] = call_no_transition;
0419         }
0420         dispatch_table* self;
0421         cell* tofill_entries;
0422     };
0423
0424  public:
0425     // initialize the dispatch table for a given Event and Fsm
0426     dispatch_table()
0427     {
0428         // Initialize cells for no transition
0429         ::boost::mpl::for_each<typename generate_state_set<Stt>::type,
0430                                boost::msm::wrap< ::boost::mpl::placeholders::_1> >
0431                         (default_init_cell<Event>(this,entries));
0432
0433         typedef typename ::boost::mpl::reverse_fold<
0434                         // filter on event
0435                         ::boost::mpl::filter_view
0436                             <Stt, boost::mpl::or_<
0437                                     ::boost::is_base_of<transition_event< ::boost::mpl::placeholders::_>, Event>,
0438                                     ::boost::msm::is_kleene_event<transition_event< ::boost::mpl::placeholders::_> >
0439                                     >
0440                             >,
0441                         // build a map
0442                         ::boost::fusion::map<>,
0443                         ::boost::mpl::if_<
0444                             // if we already have a row on this source state
0445                             ::boost::fusion::result_of::has_key< ::boost::mpl::placeholders::_1,
0446                                                    transition_source_type< ::boost::mpl::placeholders::_2> >,
0447                             // insert a new element in the value type
0448                             push_to_map_of_vec<::boost::mpl::placeholders::_2, ::boost::mpl::placeholders::_1>,
0449                             // first row on this source state, make a vector with 1 element
0450                             boost::fusion::result_of::as_map<boost::fusion::result_of::push_back<
0451                                         ::boost::mpl::placeholders::_1,
0452                                         ::boost::fusion::result_of::make_pair<transition_source_type< ::boost::mpl::placeholders::_2>,
0453                                         boost::msm::back11::make_vector< change_frow_event< ::boost::mpl::placeholders::_2> > > > >
0454                                >
0455                        >::type map_of_row_seq;
0456
0457         // and then build chaining rows for all source states having more than 1 row
0458         typedef typename ::boost::mpl::fold<
0459             map_of_row_seq,::boost::fusion::vector<>,
0460             ::boost::mpl::if_<
0461                      ::boost::mpl::greater< ::boost::mpl::size<
0462                                                     ::boost::fusion::result_of::second< ::boost::mpl::placeholders::_2> >,
0463                                             ::boost::mpl::int_<1> >,
0464                      // we need row chaining
0465                      ::boost::mpl::push_back< ::boost::mpl::placeholders::_1,
0466                                     make_chain_row_from_map_entry2< ::boost::mpl::placeholders::_2> >,
0467                      // just one row, no chaining, we rebuild the row like it was before
0468                      ::boost::mpl::push_back< ::boost::mpl::placeholders::_1,
0469                                               get_first_element_pair_second2< ::boost::mpl::placeholders::_2> >
0470              > >::type chained_rows;
0471
0472         // Go back and fill in cells for matching transitions.
0473         ::boost::mpl::for_each<chained_rows>(init_cell(this));
0474
0475     }
0476
0477     // The singleton instance.
0478     static const dispatch_table& instance() {
0479         static dispatch_table table;
0480         return table;
0481     }
0482  public: // data members
0483      // +1 => 0 is reserved for this fsm (internal transitions)
0484     cell entries[max_state+1];
0485 };
0486
0487 }}} // boost::msm::back11
0488
0489
0490 #endif //BOOST_MSM_BACK11_DISPATCH_TABLE_H
0491