ceph/src/boost/boost/msm/back/metafunctions.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_METAFUNCTIONS_H
  12 #define BOOST_MSM_BACK_METAFUNCTIONS_H
  13
  14 #include <boost/mpl/set.hpp>
  15 #include <boost/mpl/at.hpp>
  16 #include <boost/mpl/pair.hpp>
  17 #include <boost/mpl/map.hpp>
  18 #include <boost/mpl/int.hpp>
  19 #include <boost/mpl/has_xxx.hpp>
  20 #include <boost/mpl/find.hpp>
  21 #include <boost/mpl/count_if.hpp>
  22 #include <boost/mpl/fold.hpp>
  23 #include <boost/mpl/if.hpp>
  24 #include <boost/mpl/has_key.hpp>
  25 #include <boost/mpl/insert.hpp>
  26 #include <boost/mpl/next_prior.hpp>
  27 #include <boost/mpl/map.hpp>
  28 #include <boost/mpl/push_back.hpp>
  29 #include <boost/mpl/vector.hpp>
  30 #include <boost/mpl/is_sequence.hpp>
  31 #include <boost/mpl/size.hpp>
  32 #include <boost/mpl/transform.hpp>
  33 #include <boost/mpl/begin_end.hpp>
  34 #include <boost/mpl/bool.hpp>
  35 #include <boost/mpl/empty.hpp>
  36 #include <boost/mpl/identity.hpp>
  37 #include <boost/mpl/eval_if.hpp>
  38 #include <boost/mpl/insert_range.hpp>
  39 #include <boost/mpl/front.hpp>
  40 #include <boost/mpl/logical.hpp>
  41 #include <boost/mpl/plus.hpp>
  42 #include <boost/mpl/copy_if.hpp>
  43 #include <boost/mpl/back_inserter.hpp>
  44 #include <boost/mpl/transform.hpp>
  45
  46 #include <boost/type_traits/is_same.hpp>
  47 #include <boost/utility/enable_if.hpp>
  48
  49 #include <boost/msm/row_tags.hpp>
  50
  51 // mpl_graph graph implementation and depth first search
  52 #include <boost/msm/mpl_graph/incidence_list_graph.hpp>
  53 #include <boost/msm/mpl_graph/depth_first_search.hpp>
  54
  55 BOOST_MPL_HAS_XXX_TRAIT_DEF(explicit_creation)
  56 BOOST_MPL_HAS_XXX_TRAIT_DEF(pseudo_entry)
  57 BOOST_MPL_HAS_XXX_TRAIT_DEF(pseudo_exit)
  58 BOOST_MPL_HAS_XXX_TRAIT_DEF(concrete_exit_state)
  59 BOOST_MPL_HAS_XXX_TRAIT_DEF(composite_tag)
  60 BOOST_MPL_HAS_XXX_TRAIT_DEF(not_real_row_tag)
  61 BOOST_MPL_HAS_XXX_TRAIT_DEF(event_blocking_flag)
  62 BOOST_MPL_HAS_XXX_TRAIT_DEF(explicit_entry_state)
  63 BOOST_MPL_HAS_XXX_TRAIT_DEF(completion_event)
  64 BOOST_MPL_HAS_XXX_TRAIT_DEF(no_exception_thrown)
  65 BOOST_MPL_HAS_XXX_TRAIT_DEF(no_message_queue)
  66 BOOST_MPL_HAS_XXX_TRAIT_DEF(activate_deferred_events)
  67 BOOST_MPL_HAS_XXX_TRAIT_DEF(wrapped_entry)
  68 BOOST_MPL_HAS_XXX_TRAIT_DEF(active_state_switch_policy)
  69
  70 namespace boost { namespace msm { namespace back
  71 {
  72 template <typename Sequence, typename Range>
  73 struct set_insert_range
  74 {
  75     typedef typename ::boost::mpl::fold<
  76         Range,Sequence,
  77         ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2 >
  78     >::type type;
  79 };
  80
  81 // returns the current state type of a transition
  82 template <class Transition>
  83 struct transition_source_type
  84 {
  85     typedef typename Transition::current_state_type type;
  86 };
  87
  88 // returns the target state type of a transition
  89 template <class Transition>
  90 struct transition_target_type
  91 {
  92     typedef typename Transition::next_state_type type;
  93 };
  94
  95 // helper functions for generate_state_ids
  96 // create a pair of a state and a passed id for source and target states
  97 template <class Id,class Transition>
  98 struct make_pair_source_state_id
  99 {
 100     typedef typename ::boost::mpl::pair<typename Transition::current_state_type,Id> type;
 101 };
 102 template <class Id,class Transition>
 103 struct make_pair_target_state_id
 104 {
 105     typedef typename ::boost::mpl::pair<typename Transition::next_state_type,Id> type;
 106 };
 107
 108 // iterates through a transition table and automatically generates ids starting at 0
 109 // first the source states, transition up to down
 110 // then the target states, up to down
 111 template <class stt>
 112 struct generate_state_ids
 113 {
 114     typedef typename
 115         ::boost::mpl::fold<
 116         stt,::boost::mpl::pair< ::boost::mpl::map< >, ::boost::mpl::int_<0> >,
 117         ::boost::mpl::pair<
 118             ::boost::mpl::if_<
 119                      ::boost::mpl::has_key< ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 120                                             transition_source_type< ::boost::mpl::placeholders::_2> >,
 121                      ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 122                      ::boost::mpl::insert< ::boost::mpl::first<mpl::placeholders::_1>,
 123                                 make_pair_source_state_id< ::boost::mpl::second< ::boost::mpl::placeholders::_1 >,
 124                                                            ::boost::mpl::placeholders::_2> >
 125                       >,
 126             ::boost::mpl::if_<
 127                     ::boost::mpl::has_key< ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 128                                            transition_source_type< ::boost::mpl::placeholders::_2> >,
 129                     ::boost::mpl::second< ::boost::mpl::placeholders::_1 >,
 130                     ::boost::mpl::next< ::boost::mpl::second<mpl::placeholders::_1 > >
 131                     >
 132         > //pair
 133         >::type source_state_ids;
 134     typedef typename ::boost::mpl::first<source_state_ids>::type source_state_map;
 135     typedef typename ::boost::mpl::second<source_state_ids>::type highest_state_id;
 136
 137
 138     typedef typename
 139         ::boost::mpl::fold<
 140         stt,::boost::mpl::pair<source_state_map,highest_state_id >,
 141         ::boost::mpl::pair<
 142             ::boost::mpl::if_<
 143                      ::boost::mpl::has_key< ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 144                                             transition_target_type< ::boost::mpl::placeholders::_2> >,
 145                      ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 146                      ::boost::mpl::insert< ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 147                                 make_pair_target_state_id< ::boost::mpl::second< ::boost::mpl::placeholders::_1 >,
 148                                 ::boost::mpl::placeholders::_2> >
 149                      >,
 150             ::boost::mpl::if_<
 151                     ::boost::mpl::has_key< ::boost::mpl::first< ::boost::mpl::placeholders::_1>,
 152                                            transition_target_type< ::boost::mpl::placeholders::_2> >,
 153                     ::boost::mpl::second< ::boost::mpl::placeholders::_1 >,
 154                     ::boost::mpl::next< ::boost::mpl::second< ::boost::mpl::placeholders::_1 > >
 155                     >
 156         > //pair
 157         >::type all_state_ids;
 158     typedef typename ::boost::mpl::first<all_state_ids>::type type;
 159 };
 160
 161 template <class Fsm>
 162 struct get_active_state_switch_policy_helper
 163 {
 164     typedef typename Fsm::active_state_switch_policy type;
 165 };
 166 template <class Iter>
 167 struct get_active_state_switch_policy_helper2
 168 {
 169     typedef typename boost::mpl::deref<Iter>::type Fsm;
 170     typedef typename Fsm::active_state_switch_policy type;
 171 };
 172 // returns the active state switching policy
 173 template <class Fsm>
 174 struct get_active_state_switch_policy
 175 {
 176     typedef typename ::boost::mpl::find_if<
 177         typename Fsm::configuration,
 178         has_active_state_switch_policy< ::boost::mpl::placeholders::_1 > >::type iter;
 179
 180     typedef typename ::boost::mpl::eval_if<
 181         typename ::boost::is_same<
 182             iter,
 183             typename ::boost::mpl::end<typename Fsm::configuration>::type
 184         >::type,
 185         get_active_state_switch_policy_helper<Fsm>,
 186         get_active_state_switch_policy_helper2< iter >
 187     >::type type;
 188 };
 189
 190 // returns the id of a given state
 191 template <class stt,class State>
 192 struct get_state_id
 193 {
 194     typedef typename ::boost::mpl::at<typename generate_state_ids<stt>::type,State>::type type;
 195     enum {value = type::value};
 196 };
 197
 198 // returns a mpl::vector containing the init states of a state machine
 199 template <class States>
 200 struct get_initial_states
 201 {
 202     typedef typename ::boost::mpl::if_<
 203         ::boost::mpl::is_sequence<States>,
 204         States,
 205         typename ::boost::mpl::push_back< ::boost::mpl::vector0<>,States>::type >::type type;
 206 };
 207 // returns a mpl::int_ containing the size of a region. If the argument is not a sequence, returns 1
 208 template <class region>
 209 struct get_number_of_regions
 210 {
 211     typedef typename mpl::if_<
 212         ::boost::mpl::is_sequence<region>,
 213         ::boost::mpl::size<region>,
 214         ::boost::mpl::int_<1> >::type type;
 215 };
 216
 217 // builds a mpl::vector of initial states
 218 //TODO remove duplicate from get_initial_states
 219 template <class region>
 220 struct get_regions_as_sequence
 221 {
 222     typedef typename ::boost::mpl::if_<
 223         ::boost::mpl::is_sequence<region>,
 224         region,
 225         typename ::boost::mpl::push_back< ::boost::mpl::vector0<>,region>::type >::type type;
 226 };
 227
 228 template <class ToCreateSeq>
 229 struct get_explicit_creation_as_sequence
 230 {
 231     typedef typename ::boost::mpl::if_<
 232         ::boost::mpl::is_sequence<ToCreateSeq>,
 233         ToCreateSeq,
 234         typename ::boost::mpl::push_back< ::boost::mpl::vector0<>,ToCreateSeq>::type >::type type;
 235 };
 236
 237 // returns true if 2 transitions have the same source (used to remove duplicates in search of composite states)
 238 template <class stt,class Transition1,class Transition2>
 239 struct have_same_source
 240 {
 241     enum {current_state1 = get_state_id<stt,typename Transition1::current_state_type >::type::value};
 242     enum {current_state2 = get_state_id<stt,typename Transition2::current_state_type >::type::value};
 243     enum {value = ((int)current_state1 == (int)current_state2) };
 244 };
 245
 246
 247 // A metafunction that returns the Event associated with a transition.
 248 template <class Transition>
 249 struct transition_event
 250 {
 251     typedef typename Transition::transition_event type;
 252 };
 253
 254 // returns true for composite states
 255 template <class State>
 256 struct is_composite_state
 257 {
 258     enum {value = has_composite_tag<State>::type::value};
 259     typedef typename has_composite_tag<State>::type type;
 260 };
 261
 262 // transform a transition table in a container of source states
 263 template <class stt>
 264 struct keep_source_names
 265 {
 266     // instead of the rows we want only the names of the states (from source)
 267     typedef typename
 268         ::boost::mpl::transform<
 269         stt,transition_source_type< ::boost::mpl::placeholders::_1> >::type type;
 270 };
 271
 272 // transform a transition table in a container of target states
 273 template <class stt>
 274 struct keep_target_names
 275 {
 276     // instead of the rows we want only the names of the states (from source)
 277     typedef typename
 278         ::boost::mpl::transform<
 279         stt,transition_target_type< ::boost::mpl::placeholders::_1> >::type type;
 280 };
 281
 282 template <class stt>
 283 struct generate_state_set
 284 {
 285     // keep in the original transition table only the source/target state types
 286     typedef typename keep_source_names<stt>::type sources;
 287     typedef typename keep_target_names<stt>::type targets;
 288     typedef typename
 289         ::boost::mpl::fold<
 290         sources, ::boost::mpl::set<>,
 291         ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
 292         >::type source_set;
 293     typedef typename
 294         ::boost::mpl::fold<
 295         targets,source_set,
 296         ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
 297         >::type type;
 298 };
 299
 300 // iterates through the transition table and generate a mpl::set<> containing all the events
 301 template <class stt>
 302 struct generate_event_set
 303 {
 304     typedef typename
 305         ::boost::mpl::fold<
 306             stt, ::boost::mpl::set<>,
 307             ::boost::mpl::if_<
 308                 ::boost::mpl::has_key< ::boost::mpl::placeholders::_1,
 309                                        transition_event< ::boost::mpl::placeholders::_2> >,
 310                 ::boost::mpl::placeholders::_1,
 311                 ::boost::mpl::insert< ::boost::mpl::placeholders::_1,
 312                                       transition_event< ::boost::mpl::placeholders::_2> > >
 313         >::type type;
 314 };
 315
 316 // returns a mpl::bool_<true> if State has Event as deferred event
 317 template <class State, class Event>
 318 struct has_state_delayed_event
 319 {
 320     typedef typename ::boost::mpl::find<typename State::deferred_events,Event>::type found;
 321     typedef typename ::boost::mpl::if_<
 322         ::boost::is_same<found,typename ::boost::mpl::end<typename State::deferred_events>::type >,
 323         ::boost::mpl::bool_<false>,
 324         ::boost::mpl::bool_<true> >::type type;
 325 };
 326 // returns a mpl::bool_<true> if State has any deferred event
 327 template <class State>
 328 struct has_state_delayed_events
 329 {
 330     typedef typename ::boost::mpl::if_<
 331         ::boost::mpl::empty<typename State::deferred_events>,
 332         ::boost::mpl::bool_<false>,
 333         ::boost::mpl::bool_<true> >::type type;
 334 };
 335
 336 // Template used to create dummy entries for initial states not found in the stt.
 337 template< typename T1 >
 338 struct not_a_row
 339 {
 340     typedef int not_real_row_tag;
 341     struct dummy_event
 342     {
 343     };
 344     typedef T1                  current_state_type;
 345     typedef T1                  next_state_type;
 346     typedef dummy_event         transition_event;
 347 };
 348
 349 // metafunctions used to find out if a state is entry, exit or something else
 350 template <class State>
 351 struct is_pseudo_entry
 352 {
 353     typedef typename ::boost::mpl::if_< typename has_pseudo_entry<State>::type,
 354         ::boost::mpl::bool_<true>,::boost::mpl::bool_<false>
 355     >::type type;
 356 };
 357 // says if a state is an exit pseudo state
 358 template <class State>
 359 struct is_pseudo_exit
 360 {
 361     typedef typename ::boost::mpl::if_< typename has_pseudo_exit<State>::type,
 362         ::boost::mpl::bool_<true>, ::boost::mpl::bool_<false>
 363     >::type type;
 364 };
 365 // says if a state is an entry pseudo state or an explicit entry
 366 template <class State>
 367 struct is_direct_entry
 368 {
 369     typedef typename ::boost::mpl::if_< typename has_explicit_entry_state<State>::type,
 370         ::boost::mpl::bool_<true>, ::boost::mpl::bool_<false>
 371     >::type type;
 372 };
 373
 374 //converts a "fake" (simulated in a state_machine_ description )state into one which will really get created
 375 template <class StateType,class CompositeType>
 376 struct convert_fake_state
 377 {
 378     // converts a state (explicit entry) into the state we really are going to create (explicit<>)
 379     typedef typename ::boost::mpl::if_<
 380         typename is_direct_entry<StateType>::type,
 381         typename CompositeType::template direct<StateType>,
 382         typename ::boost::mpl::identity<StateType>::type
 383     >::type type;
 384 };
 385
 386 template <class StateType>
 387 struct get_explicit_creation
 388 {
 389     typedef typename StateType::explicit_creation type;
 390 };
 391
 392 template <class StateType>
 393 struct get_wrapped_entry
 394 {
 395     typedef typename StateType::wrapped_entry type;
 396 };
 397 // used for states created with explicit_creation
 398 // if the state is an explicit entry, we reach for the wrapped state
 399 // otherwise, this returns the state itself
 400 template <class StateType>
 401 struct get_wrapped_state
 402 {
 403     typedef typename ::boost::mpl::eval_if<
 404                 typename has_wrapped_entry<StateType>::type,
 405                 get_wrapped_entry<StateType>,
 406                 ::boost::mpl::identity<StateType> >::type type;
 407 };
 408
 409 template <class Derived>
 410 struct create_stt
 411 {
 412     //typedef typename Derived::transition_table stt;
 413     typedef typename Derived::real_transition_table Stt;
 414     // get the state set
 415     typedef typename generate_state_set<Stt>::type states;
 416     // transform the initial region(s) in a sequence
 417     typedef typename get_regions_as_sequence<typename Derived::initial_state>::type init_states;
 418     // iterate through the initial states and add them in the stt if not already there
 419     typedef typename
 420         ::boost::mpl::fold<
 421         init_states,Stt,
 422         ::boost::mpl::if_<
 423                  ::boost::mpl::has_key<states, ::boost::mpl::placeholders::_2>,
 424                  ::boost::mpl::placeholders::_1,
 425                  ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::end< ::boost::mpl::placeholders::_1>,
 426                              not_a_row< get_wrapped_state< ::boost::mpl::placeholders::_2> > >
 427                   >
 428         >::type with_init;
 429     // do the same for states marked as explicitly created
 430     typedef typename get_explicit_creation_as_sequence<
 431        typename ::boost::mpl::eval_if<
 432             typename has_explicit_creation<Derived>::type,
 433             get_explicit_creation<Derived>,
 434             ::boost::mpl::vector0<> >::type
 435         >::type fake_explicit_created;
 436
 437     typedef typename
 438         ::boost::mpl::transform<
 439         fake_explicit_created,convert_fake_state< ::boost::mpl::placeholders::_1,Derived> >::type explicit_created;
 440
 441     typedef typename
 442         ::boost::mpl::fold<
 443         explicit_created,with_init,
 444         ::boost::mpl::if_<
 445                  ::boost::mpl::has_key<states, ::boost::mpl::placeholders::_2>,
 446                  ::boost::mpl::placeholders::_1,
 447                  ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::end<mpl::placeholders::_1>,
 448                              not_a_row< get_wrapped_state< ::boost::mpl::placeholders::_2> > >
 449                   >
 450         >::type type;
 451 };
 452
 453 // returns the transition table of a Composite state
 454 template <class Composite>
 455 struct get_transition_table
 456 {
 457     typedef typename create_stt<Composite>::type type;
 458 };
 459
 460 // recursively builds an internal table including those of substates, sub-substates etc.
 461 // variant for submachines
 462 template <class StateType,class IsComposite>
 463 struct recursive_get_internal_transition_table
 464 {
 465     // get the composite's internal table
 466     typedef typename StateType::internal_transition_table composite_table;
 467     // and for every substate (state of submachine), recursively get the internal transition table
 468     typedef typename generate_state_set<typename StateType::stt>::type composite_states;
 469     typedef typename ::boost::mpl::fold<
 470             composite_states, composite_table,
 471             ::boost::mpl::insert_range< ::boost::mpl::placeholders::_1, ::boost::mpl::end< ::boost::mpl::placeholders::_1>,
 472              recursive_get_internal_transition_table< ::boost::mpl::placeholders::_2, is_composite_state< ::boost::mpl::placeholders::_2> >
 473              >
 474     >::type type;
 475 };
 476 // stop iterating on leafs (simple states)
 477 template <class StateType>
 478 struct recursive_get_internal_transition_table<StateType, ::boost::mpl::false_ >
 479 {
 480     typedef typename StateType::internal_transition_table type;
 481 };
 482 // recursively get a transition table for a given composite state.
 483 // returns the transition table for this state + the tables of all composite sub states recursively
 484 template <class Composite>
 485 struct recursive_get_transition_table
 486 {
 487     // get the transition table of the state if it's a state machine
 488     typedef typename ::boost::mpl::eval_if<typename is_composite_state<Composite>::type,
 489         get_transition_table<Composite>,
 490         ::boost::mpl::vector0<>
 491     >::type org_table;
 492
 493     typedef typename generate_state_set<org_table>::type states;
 494
 495     // and for every substate, recursively get the transition table if it's a state machine
 496     typedef typename ::boost::mpl::fold<
 497         states,org_table,
 498         ::boost::mpl::insert_range< ::boost::mpl::placeholders::_1, ::boost::mpl::end<mpl::placeholders::_1>,
 499         recursive_get_transition_table< ::boost::mpl::placeholders::_2 > >
 500     >::type type;
 501
 502 };
 503
 504 // metafunction used to say if a SM has pseudo exit states
 505 template <class Derived>
 506 struct has_fsm_deferred_events
 507 {
 508     typedef typename create_stt<Derived>::type Stt;
 509     typedef typename generate_state_set<Stt>::type state_list;
 510
 511     typedef typename ::boost::mpl::or_<
 512         typename has_activate_deferred_events<Derived>::type,
 513         ::boost::mpl::bool_< ::boost::mpl::count_if<
 514                 typename Derived::configuration,
 515                 has_activate_deferred_events< ::boost::mpl::placeholders::_1 > >::value != 0>
 516     >::type found_in_fsm;
 517
 518     typedef typename ::boost::mpl::or_<
 519             found_in_fsm,
 520             ::boost::mpl::bool_< ::boost::mpl::count_if<
 521                 state_list,has_state_delayed_events<
 522                     ::boost::mpl::placeholders::_1 > >::value != 0>
 523             >::type type;
 524 };
 525
 526 // returns a mpl::bool_<true> if State has any delayed event
 527 template <class Event>
 528 struct is_completion_event
 529 {
 530     typedef typename ::boost::mpl::if_<
 531         has_completion_event<Event>,
 532         ::boost::mpl::bool_<true>,
 533         ::boost::mpl::bool_<false> >::type type;
 534 };
 535 // metafunction used to say if a SM has eventless transitions
 536 template <class Derived>
 537 struct has_fsm_eventless_transition
 538 {
 539     typedef typename create_stt<Derived>::type Stt;
 540     typedef typename generate_event_set<Stt>::type event_list;
 541
 542     typedef ::boost::mpl::bool_< ::boost::mpl::count_if<
 543         event_list,is_completion_event< ::boost::mpl::placeholders::_1 > >::value != 0> type;
 544 };
 545 template <class Derived>
 546 struct find_completion_events
 547 {
 548     typedef typename create_stt<Derived>::type Stt;
 549     typedef typename generate_event_set<Stt>::type event_list;
 550
 551     typedef typename ::boost::mpl::fold<
 552         event_list, ::boost::mpl::set<>,
 553         ::boost::mpl::if_<
 554                  is_completion_event< ::boost::mpl::placeholders::_2>,
 555                  ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2 >,
 556                  ::boost::mpl::placeholders::_1 >
 557     >::type type;
 558 };
 559
 560 template <class Transition>
 561 struct make_vector
 562 {
 563     typedef ::boost::mpl::vector<Transition> type;
 564 };
 565 template< typename Entry >
 566 struct get_first_element_pair_second
 567 {
 568     typedef typename ::boost::mpl::front<typename Entry::second>::type type;
 569 };
 570
 571  //returns the owner of an explicit_entry state
 572  //which is the containing SM if the transition originates from outside the containing SM
 573  //or else the explicit_entry state itself
 574 template <class State,class ContainingSM>
 575 struct get_owner
 576 {
 577     typedef typename ::boost::mpl::if_<
 578         typename ::boost::mpl::not_<typename ::boost::is_same<typename State::owner,
 579                                                               ContainingSM >::type>::type,
 580         typename State::owner,
 581         State >::type type;
 582 };
 583
 584 template <class Sequence,class ContainingSM>
 585 struct get_fork_owner
 586 {
 587     typedef typename ::boost::mpl::front<Sequence>::type seq_front;
 588     typedef typename ::boost::mpl::if_<
 589                     typename ::boost::mpl::not_<
 590                         typename ::boost::is_same<typename seq_front::owner,ContainingSM>::type>::type,
 591                     typename seq_front::owner,
 592                     seq_front >::type type;
 593 };
 594
 595 template <class StateType,class ContainingSM>
 596 struct make_exit
 597 {
 598     typedef typename ::boost::mpl::if_<
 599              typename is_pseudo_exit<StateType>::type ,
 600              typename ContainingSM::template exit_pt<StateType>,
 601              typename ::boost::mpl::identity<StateType>::type
 602             >::type type;
 603 };
 604
 605 template <class StateType,class ContainingSM>
 606 struct make_entry
 607 {
 608     typedef typename ::boost::mpl::if_<
 609         typename is_pseudo_entry<StateType>::type ,
 610         typename ContainingSM::template entry_pt<StateType>,
 611         typename ::boost::mpl::if_<
 612                 typename is_direct_entry<StateType>::type,
 613                 typename ContainingSM::template direct<StateType>,
 614                 typename ::boost::mpl::identity<StateType>::type
 615                 >::type
 616         >::type type;
 617 };
 618 // metafunction used to say if a SM has pseudo exit states
 619 template <class StateType>
 620 struct has_exit_pseudo_states_helper
 621 {
 622     typedef typename StateType::stt Stt;
 623     typedef typename generate_state_set<Stt>::type state_list;
 624
 625     typedef ::boost::mpl::bool_< ::boost::mpl::count_if<
 626                 state_list,is_pseudo_exit< ::boost::mpl::placeholders::_1> >::value != 0> type;
 627 };
 628 template <class StateType>
 629 struct has_exit_pseudo_states
 630 {
 631     typedef typename ::boost::mpl::eval_if<typename is_composite_state<StateType>::type,
 632         has_exit_pseudo_states_helper<StateType>,
 633         ::boost::mpl::bool_<false> >::type type;
 634 };
 635
 636 // builds flags (add internal_flag_list and flag_list). internal_flag_list is used for terminate/interrupt states
 637 template <class StateType>
 638 struct get_flag_list
 639 {
 640     typedef typename ::boost::mpl::insert_range<
 641         typename StateType::flag_list,
 642         typename ::boost::mpl::end< typename StateType::flag_list >::type,
 643         typename StateType::internal_flag_list
 644     >::type type;
 645 };
 646
 647 template <class StateType>
 648 struct is_state_blocking
 649 {
 650     typedef typename ::boost::mpl::fold<
 651         typename get_flag_list<StateType>::type, ::boost::mpl::set<>,
 652         ::boost::mpl::if_<
 653                  has_event_blocking_flag< ::boost::mpl::placeholders::_2>,
 654                  ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2 >,
 655                  ::boost::mpl::placeholders::_1 >
 656     >::type blocking_flags;
 657
 658     typedef typename ::boost::mpl::if_<
 659         ::boost::mpl::empty<blocking_flags>,
 660         ::boost::mpl::bool_<false>,
 661         ::boost::mpl::bool_<true> >::type type;
 662 };
 663 // returns a mpl::bool_<true> if fsm has an event blocking flag in one of its substates
 664 template <class StateType>
 665 struct has_fsm_blocking_states
 666 {
 667     typedef typename create_stt<StateType>::type Stt;
 668     typedef typename generate_state_set<Stt>::type state_list;
 669
 670     typedef typename ::boost::mpl::fold<
 671         state_list, ::boost::mpl::set<>,
 672         ::boost::mpl::if_<
 673                  is_state_blocking< ::boost::mpl::placeholders::_2>,
 674                  ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2 >,
 675                  ::boost::mpl::placeholders::_1 >
 676     >::type blocking_states;
 677
 678     typedef typename ::boost::mpl::if_<
 679         ::boost::mpl::empty<blocking_states>,
 680         ::boost::mpl::bool_<false>,
 681         ::boost::mpl::bool_<true> >::type type;
 682 };
 683
 684 template <class StateType>
 685 struct is_no_exception_thrown
 686 {
 687     typedef ::boost::mpl::bool_< ::boost::mpl::count_if<
 688         typename StateType::configuration,
 689         has_no_exception_thrown< ::boost::mpl::placeholders::_1 > >::value != 0> found;
 690
 691     typedef typename ::boost::mpl::or_<
 692         typename has_no_exception_thrown<StateType>::type,
 693         found
 694     >::type type;
 695 };
 696
 697 template <class StateType>
 698 struct is_no_message_queue
 699 {
 700     typedef ::boost::mpl::bool_< ::boost::mpl::count_if<
 701         typename StateType::configuration,
 702         has_no_message_queue< ::boost::mpl::placeholders::_1 > >::value != 0> found;
 703
 704     typedef typename ::boost::mpl::or_<
 705         typename has_no_message_queue<StateType>::type,
 706         found
 707     >::type type;
 708 };
 709
 710 template <class StateType>
 711 struct is_active_state_switch_policy
 712 {
 713     typedef ::boost::mpl::bool_< ::boost::mpl::count_if<
 714         typename StateType::configuration,
 715         has_active_state_switch_policy< ::boost::mpl::placeholders::_1 > >::value != 0> found;
 716
 717     typedef typename ::boost::mpl::or_<
 718         typename has_active_state_switch_policy<StateType>::type,
 719         found
 720     >::type type;
 721 };
 722
 723 template <class StateType>
 724 struct get_initial_event
 725 {
 726     typedef typename StateType::initial_event type;
 727 };
 728
 729 template <class StateType>
 730 struct get_final_event
 731 {
 732     typedef typename StateType::final_event type;
 733 };
 734
 735 template <class TransitionTable, class InitState>
 736 struct build_one_orthogonal_region
 737 {
 738      template<typename Row>
 739      struct row_to_incidence :
 740          ::boost::mpl::vector<
 741                 ::boost::mpl::pair<
 742                     typename Row::next_state_type,
 743                     typename Row::transition_event>,
 744                 typename Row::current_state_type,
 745                 typename Row::next_state_type
 746          > {};
 747
 748      template <class Seq, class Elt>
 749      struct transition_incidence_list_helper
 750      {
 751          typedef typename ::boost::mpl::push_back< Seq, row_to_incidence< Elt > >::type type;
 752      };
 753
 754      typedef typename ::boost::mpl::fold<
 755          TransitionTable,
 756          ::boost::mpl::vector<>,
 757          transition_incidence_list_helper< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
 758      >::type transition_incidence_list;
 759
 760      typedef ::boost::msm::mpl_graph::incidence_list_graph<transition_incidence_list>
 761          transition_graph;
 762
 763      struct preordering_dfs_visitor :
 764          ::boost::msm::mpl_graph::dfs_default_visitor_operations
 765      {
 766          template<typename Node, typename Graph, typename State>
 767          struct discover_vertex :
 768              ::boost::mpl::insert<State, Node>
 769          {};
 770      };
 771
 772      typedef typename mpl::first<
 773          typename ::boost::msm::mpl_graph::depth_first_search<
 774             transition_graph,
 775             preordering_dfs_visitor,
 776             ::boost::mpl::set<>,
 777             InitState
 778          >::type
 779      >::type type;
 780 };
 781
 782 template <class Fsm>
 783 struct find_entry_states
 784 {
 785     typedef typename ::boost::mpl::copy<
 786         typename Fsm::substate_list,
 787         ::boost::mpl::inserter<
 788             ::boost::mpl::set0<>,
 789             ::boost::mpl::if_<
 790                 has_explicit_entry_state< ::boost::mpl::placeholders::_2 >,
 791                 ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
 792                 ::boost::mpl::placeholders::_1
 793             >
 794         >
 795     >::type type;
 796 };
 797
 798 template <class Set1, class Set2>
 799 struct is_common_element
 800 {
 801     typedef typename ::boost::mpl::fold<
 802         Set1, ::boost::mpl::false_,
 803         ::boost::mpl::if_<
 804             ::boost::mpl::has_key<
 805                 Set2,
 806                 ::boost::mpl::placeholders::_2
 807             >,
 808             ::boost::mpl::true_,
 809             ::boost::mpl::placeholders::_1
 810         >
 811     >::type type;
 812 };
 813
 814 template <class EntryRegion, class AllRegions>
 815 struct add_entry_region
 816 {
 817     typedef typename ::boost::mpl::transform<
 818         AllRegions,
 819         ::boost::mpl::if_<
 820             is_common_element<EntryRegion, ::boost::mpl::placeholders::_1>,
 821             set_insert_range< ::boost::mpl::placeholders::_1, EntryRegion>,
 822             ::boost::mpl::placeholders::_1
 823         >
 824     >::type type;
 825 };
 826
 827 // build a vector of regions states (as a set)
 828 // one set of states for every region
 829 template <class Fsm, class InitStates>
 830 struct build_orthogonal_regions
 831 {
 832     typedef typename
 833         ::boost::mpl::fold<
 834             InitStates, ::boost::mpl::vector0<>,
 835             ::boost::mpl::push_back<
 836                 ::boost::mpl::placeholders::_1,
 837                 build_one_orthogonal_region< typename Fsm::stt, ::boost::mpl::placeholders::_2 > >
 838         >::type without_entries;
 839
 840     typedef typename
 841         ::boost::mpl::fold<
 842         typename find_entry_states<Fsm>::type, ::boost::mpl::vector0<>,
 843             ::boost::mpl::push_back<
 844                 ::boost::mpl::placeholders::_1,
 845                 build_one_orthogonal_region< typename Fsm::stt, ::boost::mpl::placeholders::_2 > >
 846         >::type only_entries;
 847
 848     typedef typename ::boost::mpl::fold<
 849         only_entries , without_entries,
 850         add_entry_region< ::boost::mpl::placeholders::_2, ::boost::mpl::placeholders::_1>
 851     >::type type;
 852 };
 853
 854 template <class GraphAsSeqOfSets, class StateType>
 855 struct find_region_index
 856 {
 857     typedef typename
 858         ::boost::mpl::fold<
 859             GraphAsSeqOfSets, ::boost::mpl::pair< ::boost::mpl::int_< -1 > /*res*/, ::boost::mpl::int_<0> /*counter*/ >,
 860             ::boost::mpl::if_<
 861                 ::boost::mpl::has_key< ::boost::mpl::placeholders::_2, StateType >,
 862                 ::boost::mpl::pair<
 863                     ::boost::mpl::second< ::boost::mpl::placeholders::_1 >,
 864                     ::boost::mpl::next< ::boost::mpl::second< ::boost::mpl::placeholders::_1 > >
 865                 >,
 866                 ::boost::mpl::pair<
 867                     ::boost::mpl::first< ::boost::mpl::placeholders::_1 >,
 868                     ::boost::mpl::next< ::boost::mpl::second< ::boost::mpl::placeholders::_1 > >
 869                 >
 870             >
 871         >::type result_pair;
 872     typedef typename ::boost::mpl::first<result_pair>::type type;
 873     enum {value = type::value};
 874 };
 875
 876 template <class Fsm>
 877 struct check_regions_orthogonality
 878 {
 879     typedef typename build_orthogonal_regions< Fsm,typename Fsm::initial_states>::type regions;
 880
 881     typedef typename ::boost::mpl::fold<
 882         regions, ::boost::mpl::int_<0>,
 883         ::boost::mpl::plus< ::boost::mpl::placeholders::_1 , ::boost::mpl::size< ::boost::mpl::placeholders::_2> >
 884     >::type number_of_states_in_regions;
 885
 886     typedef typename ::boost::mpl::fold<
 887             regions,mpl::set0<>,
 888             set_insert_range<
 889                     ::boost::mpl::placeholders::_1,
 890                     ::boost::mpl::placeholders::_2 >
 891     >::type one_big_states_set;
 892
 893     enum {states_in_regions_raw = number_of_states_in_regions::value};
 894     enum {cumulated_states_in_regions_raw = ::boost::mpl::size<one_big_states_set>::value};
 895 };
 896
 897 template <class Fsm>
 898 struct check_no_unreachable_state
 899 {
 900     typedef typename check_regions_orthogonality<Fsm>::one_big_states_set states_in_regions;
 901
 902     typedef typename set_insert_range<
 903         states_in_regions,
 904         typename ::boost::mpl::eval_if<
 905             typename has_explicit_creation<Fsm>::type,
 906             get_explicit_creation<Fsm>,
 907             ::boost::mpl::vector0<>
 908         >::type
 909     >::type with_explicit_creation;
 910
 911     enum {states_in_fsm = ::boost::mpl::size< typename Fsm::substate_list >::value};
 912     enum {cumulated_states_in_regions = ::boost::mpl::size< with_explicit_creation >::value};
 913 };
 914
 915 // helper to find out if a SM has an active exit state and is therefore waiting for exiting
 916 template <class StateType,class OwnerFct,class FSM>
 917 inline
 918 typename ::boost::enable_if<typename ::boost::mpl::and_<typename is_composite_state<FSM>::type,
 919                                                         typename is_pseudo_exit<StateType>::type>,bool >::type
 920 is_exit_state_active(FSM& fsm)
 921 {
 922     typedef typename OwnerFct::type Composite;
 923     //typedef typename create_stt<Composite>::type stt;
 924     typedef typename Composite::stt stt;
 925     int state_id = get_state_id<stt,StateType>::type::value;
 926     Composite& comp = fsm.template get_state<Composite&>();
 927     return (std::find(comp.current_state(),comp.current_state()+Composite::nr_regions::value,state_id)
 928                             !=comp.current_state()+Composite::nr_regions::value);
 929 }
 930 template <class StateType,class OwnerFct,class FSM>
 931 inline
 932 typename ::boost::disable_if<typename ::boost::mpl::and_<typename is_composite_state<FSM>::type,
 933                                                          typename is_pseudo_exit<StateType>::type>,bool >::type
 934 is_exit_state_active(FSM&)
 935 {
 936     return false;
 937 }
 938
 939 // transformation metafunction to end interrupt flags
 940 template <class Event>
 941 struct transform_to_end_interrupt
 942 {
 943     typedef boost::msm::EndInterruptFlag<Event> type;
 944 };
 945 // transform a sequence of events into another one of EndInterruptFlag<Event>
 946 template <class Events>
 947 struct apply_end_interrupt_flag
 948 {
 949     typedef typename
 950         ::boost::mpl::transform<
 951         Events,transform_to_end_interrupt< ::boost::mpl::placeholders::_1> >::type type;
 952 };
 953 // returns a mpl vector containing all end interrupt events if sequence, otherwise the same event
 954 template <class Event>
 955 struct get_interrupt_events
 956 {
 957     typedef typename ::boost::mpl::eval_if<
 958         ::boost::mpl::is_sequence<Event>,
 959         boost::msm::back::apply_end_interrupt_flag<Event>,
 960         boost::mpl::vector1<boost::msm::EndInterruptFlag<Event> > >::type type;
 961 };
 962
 963 template <class Events>
 964 struct build_interrupt_state_flag_list
 965 {
 966     typedef ::boost::mpl::vector<boost::msm::InterruptedFlag> first_part;
 967     typedef typename ::boost::mpl::insert_range<
 968         first_part,
 969         typename ::boost::mpl::end< first_part >::type,
 970         Events
 971     >::type type;
 972 };
 973
 974 } } }//boost::msm::back
 975
 976 #endif // BOOST_MSM_BACK_METAFUNCTIONS_H
 977