boost/msm/back/dispatch_table.hpp

   1 // Copyright 2008 Christophe Henry
   2 // henry UNDERSCORE christophe AT hotmail DOT com
   3 // This is an extended version of the state machine available in the boost::mpl library
   4 // Distributed under the same license as the original.
   5 // Copyright for the original version:
   6 // Copyright 2005 David Abrahams and Aleksey Gurtovoy. Distributed
   7 // under the Boost Software License, Version 1.0. (See accompanying
   8 // file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_MSM_BACK_DISPATCH_TABLE_H
  12 #define BOOST_MSM_BACK_DISPATCH_TABLE_H
  13
  14 #include <utility>
  15
  16 #include <boost/mpl/reverse_fold.hpp>
  17 #include <boost/mpl/greater.hpp>
  18 #include <boost/mpl/filter_view.hpp>
  19 #include <boost/mpl/pop_front.hpp>
  20 #include <boost/mpl/for_each.hpp>
  21 #include <boost/mpl/advance.hpp>
  22
  23 #include <boost/type_traits/is_base_of.hpp>
  24 #include <boost/type_traits/is_same.hpp>
  25
  26 #include <boost/msm/event_traits.hpp>
  27 #include <boost/msm/back/metafunctions.hpp>
  28 #include <boost/msm/back/common_types.hpp>
  29
  30 BOOST_MPL_HAS_XXX_TRAIT_DEF(is_frow)
  31
  32 namespace boost { namespace msm { namespace back
  33 {
  34
  35 // Generates a singleton runtime lookup table that maps current state
  36 // to a function that makes the SM take its transition on the given
  37 // Event type.
  38 template <class Fsm,class Stt, class Event,class CompilePolicy>
  39 struct dispatch_table
  40 {
  41  private:
  42     // This is a table of these function pointers.
  43     typedef HandledEnum (*cell)(Fsm&, int,int,Event const&);
  44     typedef bool (*guard)(Fsm&, Event const&);
  45
  46     // class used to build a chain (or sequence) of transitions for a given event and start state
  47     // (like an UML diamond). Allows transition conflicts.
  48     template< typename Seq,typename AnEvent,typename State >
  49     struct chain_row
  50     {
  51         typedef State   current_state_type;
  52         typedef AnEvent transition_event;
  53
  54         // helper for building a disable/enable_if-controlled execute function
  55         struct execute_helper
  56         {
  57             template <class Sequence>
  58             static
  59             HandledEnum
  60             execute(Fsm& , int, int, Event const& , ::boost::mpl::true_ const & )
  61             {
  62                 // if at least one guard rejected, this will be ignored, otherwise will generate an error
  63                 return HANDLED_FALSE;
  64             }
  65
  66             template <class Sequence>
  67             static
  68             HandledEnum
  69             execute(Fsm& fsm, int region_index , int state, Event const& evt,
  70                     ::boost::mpl::false_ const & )
  71             {
  72                  // try the first guard
  73                  typedef typename ::boost::mpl::front<Sequence>::type first_row;
  74                  HandledEnum res = first_row::execute(fsm,region_index,state,evt);
  75                  if (HANDLED_TRUE!=res && HANDLED_DEFERRED!=res)
  76                  {
  77                     // if the first rejected, move on to the next one
  78                     HandledEnum sub_res =
  79                          execute<typename ::boost::mpl::pop_front<Sequence>::type>(fsm,region_index,state,evt,
  80                             ::boost::mpl::bool_<
  81                                 ::boost::mpl::empty<typename ::boost::mpl::pop_front<Sequence>::type>::type::value>());
  82                     // if at least one guards rejects, the event will not generate a call to no_transition
  83                     if ((HANDLED_FALSE==sub_res) && (HANDLED_GUARD_REJECT==res) )
  84                         return HANDLED_GUARD_REJECT;
  85                     else
  86                         return sub_res;
  87                  }
  88                  return res;
  89             }
  90         };
  91         // Take the transition action and return the next state.
  92         static HandledEnum execute(Fsm& fsm, int region_index, int state, Event const& evt)
  93         {
  94             // forward to helper
  95             return execute_helper::template execute<Seq>(fsm,region_index,state,evt,
  96                 ::boost::mpl::bool_< ::boost::mpl::empty<Seq>::type::value>());
  97         }
  98     };
  99     // nullary metafunction whose only job is to prevent early evaluation of _1
 100     template< typename Entry >
 101     struct make_chain_row_from_map_entry
 102     {
 103         // if we have more than one frow with the same state as source, remove the ones extra
 104         // note: we know the frow's are located at the beginning so we remove at the beginning (number of frows - 1) elements
 105         enum {number_frows = ::boost::mpl::count_if< typename Entry::second,has_is_frow< ::boost::mpl::placeholders::_1> >::value};
 106
 107         //erases the first NumberToDelete rows
 108         template<class Sequence, int NumberToDelete>
 109         struct erase_first_rows
 110         {
 111             typedef typename ::boost::mpl::erase<
 112                 typename Entry::second,
 113                 typename ::boost::mpl::begin<Sequence>::type,
 114                 typename ::boost::mpl::advance<
 115                         typename ::boost::mpl::begin<Sequence>::type,
 116                         ::boost::mpl::int_<NumberToDelete> >::type
 117             >::type type;
 118         };
 119         // if we have more than 1 frow with this event (not allowed), delete the spare
 120         typedef typename ::boost::mpl::eval_if<
 121             typename ::boost::mpl::bool_< number_frows >= 2 >::type,
 122             erase_first_rows<typename Entry::second,number_frows-1>,
 123             ::boost::mpl::identity<typename Entry::second>
 124         >::type filtered_stt;
 125
 126         typedef chain_row<filtered_stt,Event,
 127             typename Entry::first > type;
 128     };
 129     // helper for lazy evaluation in eval_if of change_frow_event
 130     template <class Transition,class NewEvent>
 131     struct replace_event
 132     {
 133         typedef typename Transition::template replace_event<NewEvent>::type type;
 134     };
 135     // changes the event type for a frow to the event we are dispatching
 136     // this helps ensure that an event does not get processed more than once because of frows and base events.
 137     template <class FrowTransition>
 138     struct change_frow_event
 139     {
 140         typedef typename ::boost::mpl::eval_if<
 141             typename has_is_frow<FrowTransition>::type,
 142             replace_event<FrowTransition,Event>,
 143             boost::mpl::identity<FrowTransition>
 144         >::type type;
 145     };
 146     // Compute the maximum state value in the sm so we know how big
 147     // to make the table
 148     typedef typename generate_state_set<Stt>::type state_list;
 149     BOOST_STATIC_CONSTANT(int, max_state = ( ::boost::mpl::size<state_list>::value));
 150
 151     template <class Transition>
 152     struct convert_event_and_forward
 153     {
 154         static HandledEnum execute(Fsm& fsm, int region_index, int state, Event const& evt)
 155         {
 156             typename Transition::transition_event forwarded(evt);
 157             return Transition::execute(fsm,region_index,state,forwarded);
 158         }
 159     };
 160
 161     // A function object for use with mpl::for_each that stuffs
 162     // transitions into cells.
 163     struct init_cell
 164     {
 165         init_cell(dispatch_table* self_)
 166           : self(self_)
 167         {}
 168         // version for transition event not base of our event
 169         // first for all transitions, then for internal ones of a fsm
 170         template <class Transition>
 171         typename ::boost::disable_if<
 172             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 173         ,void>::type
 174         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::false_ const &) const
 175         {
 176             typedef typename create_stt<Fsm>::type stt;
 177             BOOST_STATIC_CONSTANT(int, state_id =
 178                 (get_state_id<stt,typename Transition::current_state_type>::value));
 179             self->entries[state_id+1] = reinterpret_cast<cell>(&Transition::execute);
 180         }
 181         template <class Transition>
 182         typename ::boost::enable_if<
 183             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 184         ,void>::type
 185         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::false_ const &) const
 186         {
 187             self->entries[0] = reinterpret_cast<cell>(&Transition::execute);
 188         }
 189
 190         // version for transition event is boost::any
 191         // first for all transitions, then for internal ones of a fsm
 192         template <class Transition>
 193         typename ::boost::disable_if<
 194             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 195         ,void>::type
 196         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::true_ const &) const
 197         {
 198             typedef typename create_stt<Fsm>::type stt;
 199             BOOST_STATIC_CONSTANT(int, state_id =
 200                 (get_state_id<stt,typename Transition::current_state_type>::value));
 201             self->entries[state_id+1] = &convert_event_and_forward<Transition>::execute;
 202         }
 203         template <class Transition>
 204         typename ::boost::enable_if<
 205             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 206         ,void>::type
 207         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::true_ const &) const
 208         {
 209             self->entries[0] = &convert_event_and_forward<Transition>::execute;
 210         }
 211         template <class Transition>
 212         typename ::boost::disable_if<
 213             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 214         ,void>::type
 215         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::true_ const &) const
 216         {
 217             typedef typename create_stt<Fsm>::type stt;
 218             BOOST_STATIC_CONSTANT(int, state_id =
 219                 (get_state_id<stt,typename Transition::current_state_type>::value));
 220             self->entries[state_id+1] = &convert_event_and_forward<Transition>::execute;
 221         }
 222         template <class Transition>
 223         typename ::boost::enable_if<
 224             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 225         ,void>::type
 226         init_event_base_case(Transition const&, ::boost::mpl::true_ const &, ::boost::mpl::true_ const &) const
 227         {
 228             self->entries[0] = &convert_event_and_forward<Transition>::execute;
 229         }
 230         // end version for kleene
 231
 232         // version for transition event base of our event
 233         // first for all transitions, then for internal ones of a fsm
 234         template <class Transition>
 235         typename ::boost::disable_if<
 236             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 237         ,void>::type
 238         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::false_ const &) const
 239         {
 240             typedef typename create_stt<Fsm>::type stt;
 241             BOOST_STATIC_CONSTANT(int, state_id =
 242                 (get_state_id<stt,typename Transition::current_state_type>::value));
 243             self->entries[state_id+1] = &Transition::execute;
 244         }
 245         template <class Transition>
 246         typename ::boost::enable_if<
 247             typename ::boost::is_same<typename Transition::current_state_type,Fsm>::type
 248         ,void>::type
 249         init_event_base_case(Transition const&, ::boost::mpl::false_ const &, ::boost::mpl::false_ const &) const
 250         {
 251             self->entries[0] = &Transition::execute;
 252         }
 253         // Cell initializer function object, used with mpl::for_each
 254         template <class Transition>
 255         typename ::boost::enable_if<typename has_not_real_row_tag<Transition>::type,void >::type
 256             operator()(Transition const&,boost::msm::back::dummy<0> = 0) const
 257         {
 258             // version for not real rows. No problem because irrelevant for process_event
 259         }
 260         template <class Transition>
 261         typename ::boost::disable_if<typename has_not_real_row_tag<Transition>::type,void >::type
 262         operator()(Transition const& tr,boost::msm::back::dummy<1> = 0) const
 263         {
 264             //only if the transition event is a base of our event is the reinterpret_case safe
 265             init_event_base_case(tr,
 266                 ::boost::mpl::bool_<
 267                     ::boost::is_base_of<typename Transition::transition_event,Event>::type::value>(),
 268                 ::boost::mpl::bool_<
 269                     ::boost::msm::is_kleene_event<typename Transition::transition_event>::type::value>());
 270         }
 271
 272         dispatch_table* self;
 273     };
 274
 275     // Cell default-initializer function object, used with mpl::for_each
 276     // initializes with call_no_transition, defer_transition or default_eventless_transition
 277     // variant for non-anonymous transitions
 278     template <class EventType,class Enable=void>
 279     struct default_init_cell
 280     {
 281         default_init_cell(dispatch_table* self_,cell* tofill_entries_)
 282             : self(self_),tofill_entries(tofill_entries_)
 283         {}
 284         template <class State>
 285         typename ::boost::enable_if<typename has_state_delayed_event<State,Event>::type,void>::type
 286         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<0> = 0)
 287         {
 288             typedef typename create_stt<Fsm>::type stt;
 289             BOOST_STATIC_CONSTANT(int, state_id = (get_state_id<stt,State>::value));
 290             cell call_no_transition = &Fsm::defer_transition;
 291             tofill_entries[state_id+1] = call_no_transition;
 292         }
 293         template <class State>
 294         typename ::boost::disable_if<
 295             typename ::boost::mpl::or_<
 296                 typename has_state_delayed_event<State,Event>::type,
 297                 typename ::boost::is_same<State,Fsm>::type
 298             >::type
 299         ,void >::type
 300         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<1> = 0)
 301         {
 302             typedef typename create_stt<Fsm>::type stt;
 303             BOOST_STATIC_CONSTANT(int, state_id = (get_state_id<stt,State>::value));
 304             cell call_no_transition = &Fsm::call_no_transition;
 305             tofill_entries[state_id+1] = call_no_transition;
 306         }
 307         // case for internal transitions of this fsm
 308         template <class State>
 309         typename ::boost::enable_if<
 310             typename ::boost::mpl::and_<
 311                 typename ::boost::mpl::not_<typename has_state_delayed_event<State,Event>::type>::type,
 312                 typename ::boost::is_same<State,Fsm>::type
 313             >::type
 314         ,void>::type
 315         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<2> = 0)
 316         {
 317             cell call_no_transition = &Fsm::call_no_transition_internal;
 318             tofill_entries[0] = call_no_transition;
 319         }
 320         dispatch_table* self;
 321         cell* tofill_entries;
 322     };
 323
 324     // variant for anonymous transitions
 325     template <class EventType>
 326     struct default_init_cell<EventType,
 327                              typename ::boost::enable_if<
 328                                 typename is_completion_event<EventType>::type>::type>
 329     {
 330         default_init_cell(dispatch_table* self_,cell* tofill_entries_)
 331             : self(self_),tofill_entries(tofill_entries_)
 332         {}
 333
 334         // this event is a compound one (not a real one, just one for use in event-less transitions)
 335         // Note this event cannot be used as deferred!
 336         // case for internal transitions of this fsm
 337         template <class State>
 338         typename ::boost::disable_if<
 339             typename ::boost::is_same<State,Fsm>::type
 340         ,void>::type
 341         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<0> = 0)
 342         {
 343             typedef typename create_stt<Fsm>::type stt;
 344             BOOST_STATIC_CONSTANT(int, state_id = (get_state_id<stt,State>::value));
 345             cell call_no_transition = &Fsm::default_eventless_transition;
 346             tofill_entries[state_id+1] = call_no_transition;
 347         }
 348
 349         template <class State>
 350         typename ::boost::enable_if<
 351             typename ::boost::is_same<State,Fsm>::type
 352         ,void>::type
 353         operator()(boost::msm::wrap<State> const&,boost::msm::back::dummy<1> = 0)
 354         {
 355             cell call_no_transition = &Fsm::default_eventless_transition;
 356             tofill_entries[0] = call_no_transition;
 357         }
 358         dispatch_table* self;
 359         cell* tofill_entries;
 360     };
 361
 362  public:
 363     // initialize the dispatch table for a given Event and Fsm
 364     dispatch_table()
 365     {
 366         // Initialize cells for no transition
 367         ::boost::mpl::for_each<typename generate_state_set<Stt>::type,
 368                                boost::msm::wrap< ::boost::mpl::placeholders::_1> >
 369                         (default_init_cell<Event>(this,entries));
 370
 371         // build chaining rows for rows coming from the same state and the current event
 372         // first we build a map of sequence for every source
 373         // in reverse order so that the frow's are handled first (UML priority)
 374         typedef typename ::boost::mpl::reverse_fold<
 375                         // filter on event
 376                         ::boost::mpl::filter_view
 377                             <Stt, boost::mpl::or_<
 378                                     ::boost::is_base_of<transition_event< ::boost::mpl::placeholders::_>, Event>,
 379                                     ::boost::msm::is_kleene_event<transition_event< ::boost::mpl::placeholders::_> >
 380                                     >
 381                             >,
 382                         // build a map
 383                         ::boost::mpl::map<>,
 384                         ::boost::mpl::if_<
 385                             // if we already have a row on this source state
 386                             ::boost::mpl::has_key< ::boost::mpl::placeholders::_1,
 387                                                    transition_source_type< ::boost::mpl::placeholders::_2> >,
 388                             // insert a new element in the value type
 389                             ::boost::mpl::insert<
 390                                 ::boost::mpl::placeholders::_1,
 391                                 ::boost::mpl::pair<transition_source_type< ::boost::mpl::placeholders::_2>,
 392                                                    ::boost::mpl::push_back<
 393                                                         ::boost::mpl::at< ::boost::mpl::placeholders::_1,
 394                                                         transition_source_type< ::boost::mpl::placeholders::_2> >,
 395                                                         change_frow_event< ::boost::mpl::placeholders::_2 > >
 396                                                    > >,
 397                             // first row on this source state, make a vector with 1 element
 398                             ::boost::mpl::insert<
 399                                         ::boost::mpl::placeholders::_1,
 400                                         ::boost::mpl::pair<transition_source_type< ::boost::mpl::placeholders::_2>,
 401                                         make_vector< change_frow_event< ::boost::mpl::placeholders::_2> > > >
 402                                >
 403                        >::type map_of_row_seq;
 404         // and then build chaining rows for all source states having more than 1 row
 405         typedef typename ::boost::mpl::fold<
 406             map_of_row_seq,::boost::mpl::vector0<>,
 407             ::boost::mpl::if_<
 408                      ::boost::mpl::greater< ::boost::mpl::size<
 409                                                     ::boost::mpl::second< ::boost::mpl::placeholders::_2> >,
 410                                             ::boost::mpl::int_<1> >,
 411                      // we need row chaining
 412                      ::boost::mpl::push_back< ::boost::mpl::placeholders::_1,
 413                                     make_chain_row_from_map_entry< ::boost::mpl::placeholders::_2> >,
 414                      // just one row, no chaining, we rebuild the row like it was before
 415                      ::boost::mpl::push_back< ::boost::mpl::placeholders::_1,
 416                                               get_first_element_pair_second< ::boost::mpl::placeholders::_2> >
 417              > >::type chained_rows;
 418         // Go back and fill in cells for matching transitions.
 419         ::boost::mpl::for_each<chained_rows>(init_cell(this));
 420     }
 421
 422     // The singleton instance.
 423     static const dispatch_table instance;
 424
 425  public: // data members
 426      // +1 => 0 is reserved for this fsm (internal transitions)
 427     cell entries[max_state+1];
 428 };
 429
 430 }}} // boost::msm::back
 431
 432
 433 #endif //BOOST_MSM_BACK_DISPATCH_TABLE_H
 434