|
|
11.5. ImplementationNow that we've begun to touch on the details of state_machine's implementation, we may as well dive in head first. You're probably asking yourself, "How the heck are we going to make this thing work?" Mostly the answer comes down to implementing process_event, which after all is entirely responsible for the FSM's runtime behavior (aside from the transition actions, supplied by the derived FSM's author). The process_event member function presents a classic "double dispatch" problem: Given a start state and an event, we need to select a target state and a transition action to perform. In general, implementing double dispatch can be quite challenging, but in our case we have a distinct advantage: We know the event type at compile time, which allows us to capitalize on the compiler's overload resolution capability. If we were going to write an FSM implementation by hand instead of letting the library generate it, we'd have a separate overloaded implementation of process_event for each event type, looking something like this:
// "play" event processor
void process_event(play const& e)
{
switch (this->state)
{
case Stopped:
this->start_playback(e);
this->state = Playing;
break;
case Paused:
this->resume_playback(e);
this->state = Playing;
break;
default:
this->state = no_transition(this->state, e);
}
}
// "stop" event processor
void process_event(stop const& e)
{
...
}
// etc...
Ideally, to do the same thing automatically, we'd just instantiate some templates parameterized on the current states, actions, and target states involved, and containing switch statements. Just looking at the play event processor, we can already see a problem. There may be an arbitrary number of cases in that switch statement, one for each transition on the event, and C++ doesn't give us a way to generate such an arbitrarily sized switch statement directly. To create one from the information in our transition table, which will be processed row by row, we need to build up the switch semantics from similar-looking bite-sized pieces. The smallest unit of code that we can generate with C++ templates is a function call, so these pieces will have to be functions. Breaking each case into a separate function yields something more like this for the play event processor:
// "play" event processor
void process_event(play const& e)
{
this->state = case_Stopped(e);
}
int case_Stopped(play const& e)
{
if (this->state == Stopped)
{
this->start_playback(e);
return Playing;
}
else return this->case_Paused(e);
}
int case_Paused(play const& e)
{
if (this->state == Paused)
{
this->resume_playback(e);
return Playing;
}
else return this->case_default(e);
}
int case_default(play const& e)
{
return this->no_transition(this->state, e);
}
Here, process_event(play const&) forwards its implementation to case_Stopped. case_Stopped first checks to see if the current state is Stopped, and if so, takes the corresponding transition action (start_playback) and returns Playing as the new state. Otherwise, case_Paused checks to see if the state is Paused, and if so, resumes playback and again returns Playing. Otherwise, case_default calls no_transition to handle the states that have no outgoing transition on a play event.[5]
As you can see, these semantics are identical to those of the switch statement above. If we can generate a case_State function for each transition on a given event, we can build the right behavior incrementally, by traversing the rows of the transition table. Of course, we're not home free yet, because we can't generate case_State functions, the problem being the variable part of the name, represented by State. A template metaprogram simply can't generate new identifiers. We can, however, associate a separate function with each state as follows:
template <int State>
struct case_
{
static int dispatch(player& fsm, int state, play const& e)
{ ... }
};
Provided that we could fill the braces appropriately, case_<Stopped>::dispatch would be equivalent to case_Stopped, and case<Paused>::dispatch would be equivalent to case_Paused. To generate bodies for these functions, we'll need State (to check against), a transition action (to execute), and a next state (to move to). We could pass each of these in a separate template parameter, but it's probably simpler to pass an entire row of the transition table, since the members of row provide access to all of that information and more. If case_ isn't taking a state value as its sole template argument, though, it seems badly named. Let's call it event_dispatcher instead:
template<class Transition> // a row of the transition table
struct event_dispatcher
{
typedef typename Transition::fsm_t fsm_t;
typedef typename Transition::event event;
static int dispatch(
fsm_t& fsm, int state, event const& e)
{
if (state == Transition::current_state)
{
Transition::execute(fsm, e);
return Transition::next_state;
}
else { ... }
}
};
Conveniently, each row provides us with the identity of the state machine (::fsm_t) and of the event being dispatched (::event). That allows event_dispatcher to be more generic than case_, which was tied to a specific state machine and event. To complete event_dispatcher we must fill in its else clause, which, in the usual case, just needs to call the next case's dispatch function. That's easy enough if the event_dispatcher for the next case is a template parameter:
template<
class Transition
, class Next
>
struct event_dispatcher
{
typedef typename Transition::fsm_t fsm_t;
typedef typename Transition::event event;
static int dispatch(
fsm_t& fsm, int state, event const& e)
{
if (state == Transition::current_state)
{
Transition::execute(fsm, e);
return Transition::next_state;
}
else // move on to the next node in the chain.
{
return Next::dispatch(fsm, state, e);
}
}
};
To handle the default case, we'll introduce a default_event_dispatcher with a dispatch function that invokes the FSM's no_transition handler. Because the derived FSM class is only granting friendship to state_machine<FSM> and not to default_event_dispatcher, the handler must be called indirectly through a member of state_machine:
struct default_event_dispatcher
{
template<class FSM, class Event>
static int dispatch(
state_machine<FSM>& m, int state, Event const& e)
{
return m.call_no_transition(state, e);
}
};
template <class Derived>
class state_machine
{
...
template <class Event>
int call_no_transition(int state, Event const& e)
{
return static_cast<Derived*>(this) // CRTP downcast
->no_transition(state, e);
}
...
};
Now, to process the play event, we just have to assemble the following type and call its dispatch function:
event_dispatcher<
row<Stopped, play, Playing, &player::start_playback>
, event_dispatcher<
row<Paused, play, Playing, &player::resume_playback>
, default_event_dispatcher
>
>
If you look carefully at the structure of that type, you can see that it mirrors the execution pattern of the fold algorithm, beginning with default_event_dispatcher and "folding" it into successive event_dispatcher specializations. To generate it, we just have to run fold over the rows of our table that contain the event we're dispatching:
// get the Event associated with a transition
template <class Transition>
struct transition_event
{
typedef typename Transition::event type;
};
template<class Table, class Event>
struct generate_dispatcher
: mpl::fold<
mpl::filter_view< // select rows triggered by Event
Table
, boost::is_same<Event, transition_event<_1< >
>
, default_event_dispatcher
, event_dispatcher<_2,_1>
>
{};
Finally, we're ready to write state_machine's process_event function! Rather than writing overloads for each event type, we'll use a member function templated on the event type, that merely generates the dispatcher and invokes its ::dispatch member:
template<class Event>
int process_event(Event const& evt)
{
// generate the dispatcher type
typedef typename generate_dispatcher<
typename Derived::transition_table, Event
>::type dispatcher;
// dispatch the event
this->state = dispatcher::dispatch(
*static_cast<Derived*>(this) // CRTP downcast
, this->state
, evt
);
// return the new state
return this->state;
}
Note that once again we are taking advantage of the Curiously Recurring Template Pattern to supply functionality that relies on knowing the full type of the derived class in the member functions of the base class. The static_cast above allows the dispatcher to apply the Derived member function pointers in the TRansition_table to *this. There's very little else to state_machine. We need a state member, and a constructor to initialize it:
...
protected:
state_machine()
: state(Derived::initial_state)
{}
private:
int state;
...
It would be nice to supply a default no_transition handler; after all, a user who wants different behavior can always write a no_transition function in her derived class:
...
public:
template <class Event>
int no_transition(Event const& e)
{
assert(false);
return state;
}
...
In your Boost installation, libs/mpl/book/chapter10/player.cpp contains a complete implementation of what we've explored here.  |
|
|