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