Extending State Pattern - Example Code
This is an example toy implementation of state pattern extended with secondary transition stimuli. We dicussed in the last post that a context is more than a wrapper here, and thus it provides an interface to states to raise secondary events. As handling of the secondary events would vary from concrete context to concrete context, state is provided with an interface of an abstract context, as shown below:
class AbstractContext
{
public:
typedef std::map
InstanceTable_t;
virtual ~AbstractContext();
virtual void
raiseSecondaryEvent(
const SecondaryEvent::SecondaryEvent_t&
) = 0;
void activateState(const AbstractState::State_t& stateType);
void onEvent_1();
void onEvent_2();
void onEvent_3();
protected:
AbstractContext();
AbstractState* getStateInstance(
const AbstractState::State_t& type);
virtual AbstractState*
createStateInstance(
const AbstractState::State_t& type
)const = 0;
AbstractState::State_t getCurrentStateType() const;
private:
AbstractState* state_;
InstanceTable_t instances_;
};
A concrete context will have an implementation of the transition table mapping (current state, secondary event) -> next state; naturally a simple representation of the table would be an stl::map. Notice that states were instantiated with a factory method createStateInstance(), which is defined in concreteContext and used from AbstractContext::getStateInstance(); to use this on demand instantiation pattern properly we always have to use this accessor function getStateInstance() to get any state instance.
#include <map>
#include "AbstractContext.hpp"
class ConcreteContext : public AbstractContext
{
public:
typedef
std::map,
AbstractState::State_t> TransitionTable_t;
ConcreteContext();
virtual void
raiseSecondaryEvent(
const SecondaryEvent::SecondaryEvent_t& event
);
protected:
void populateTransitions();
AbstractState* createStateInstance
(const AbstractState::State_t& type) const;
private:
TransitionTable_t transitionTable;
};
Abstract state interface is typical. See concreteState classes to check how we are raising secondary events.
class AbstractContext;
class AbstractState
{
public:
enum State_t
{
State_1 = 1,
State_2 = 2
};
virtual ~AbstractState(){}
virtual void onEvent_1(AbstractContext* context) = 0;
virtual void onEvent_2(AbstractContext* context) = 0;
virtual void onEvent_3(AbstractContext* context) = 0;
virtual State_t stateType() const = 0;
protected:
AbstractState(){}
};
class ConcreteState_1 : public AbstractState
{
public:
ConcreteState_1(){}
virtual void onEvent_1(AbstractContext* context)
{
std::cout << "Process primary event-1 in ConcreteState-1";
std::cout << std::endl;
}
virtual void onEvent_2(AbstractContext* context)
{
std::cout << "Process primary event-2 in ConcreteState-1";
std::cout << std::endl;
}
virtual void onEvent_3(AbstractContext* context)
{
std::cout << "Process primary event-3 in ConcreteState-1";
std::cout << std::endl;
context->raiseSecondaryEvent(SecondaryEvent::Trigger_1);
}
virtual AbstractState::State_t stateType() const
{
return AbstractState::State_1;
}
};
class ConcreteState_2 : public AbstractState
{
public:
ConcreteState_2(){}
virtual void onEvent_1(AbstractContext* context)
{
std::cout << "Process primary event-1 in ConcreteState-2";
std::cout << std::endl;
}
virtual void onEvent_2(AbstractContext* context)
{
std::cout << "Process primary event-2 in ConcreteState-2";
std::cout << std::endl;
}
virtual void onEvent_3(AbstractContext* context)
{
std::cout << "Process primary event-3 in ConcreteState-2";
std::cout << std::endl;
context->raiseSecondaryEvent(SecondaryEvent::Trigger_2);
}
virtual AbstractState::State_t stateType() const
{
return AbstractState::State_2;
}
};
Now the cpp definitions for AbstractContext and its concrete derived class -
AbstractContext.cpp :
AbstractContext::AbstractContext() : state_(NULL)
{
}
AbstractContext::~AbstractContext()
{
InstanceTable_t::iterator it = instances_.begin();
InstanceTable_t::iterator itEnd = instances_.end();
while(it != itEnd)
{
delete it->second;
++it;
}
instances_.clear();
}
void AbstractContext::onEvent_1()
{
state_->onEvent_1(this);
}
void AbstractContext::onEvent_2()
{
state_->onEvent_2(this);
}
void AbstractContext::onEvent_3()
{
state_->onEvent_3(this);
}
void
AbstractContext::activateState(
const AbstractState::State_t& stateType)
{
state_ = getStateInstance(stateType);
assert(state_ != NULL);
}
AbstractState*
AbstractContext::getStateInstance(const AbstractState::State_t& type)
{
AbstractState* stateInstance = NULL;
InstanceTable_t::const_iterator it =
instances_.find(type);
if(it != instances_.end())
{
stateInstance = it->second;
}
else
{
stateInstance = createStateInstance(type);
instances_[type] = stateInstance;
}
return stateInstance;
}
AbstractState::State_t AbstractContext::getCurrentStateType() const
{
assert(state_ != NULL);
return state_->stateType();
}
ConcreteContext.cpp :
ConcreteContext::ConcreteContext()
{
populateTransitions();
}
void ConcreteContext::raiseSecondaryEvent(
const SecondaryEvent::SecondaryEvent_t& event)
{
TransitionTable_t::iterator it =
transitionTable.find(
std::make_pair(getCurrentStateType(), event));
if(it != transitionTable.end())
{
activateState(it->second);
}
}
void ConcreteContext::populateTransitions()
{
transitionTable[std::make_pair(AbstractState::State_1,
SecondaryEvent::Trigger_1)] = AbstractState::State_2;
transitionTable[std::make_pair(AbstractState::State_2,
SecondaryEvent::Trigger_2)] = AbstractState::State_1;
}
AbstractState*
ConcreteContext::createStateInstance(
const AbstractState::State_t& type) const
{
AbstractState* state = NULL;
switch(type)
{
case AbstractState::State_1:
state = new ConcreteState_1();
break;
case AbstractState::State_2:
state = new ConcreteState_2();
break;
default:
assert(false);
break;
}
return state;
}
Now client code would just create a ConcreteContext, activate initial state and expose itself to primary events - that’s it.
Extending State Pattern with Secondary Transition Stimuli
State machine in procedural programming and corresponding state pattern in OOP has been there and served us well to implement event driven scenarios for some time now. To be accurate, state machine is an architectural pattern which was there even before OO, while ’state pattern’ is really the OO implementation of State Machine. The intent and benefit are clear for the basic state pattern. The state pattern lets you implement state specific behaviour without cluttering your code with conditionals. State pattern is based on OO principle of delegation to a polymorphic base class - and it is very clean that way ( yes, just like strategy pattern ). A ‘context’-wrapper delegates all requests to the ConcreteState class through an abstract state interface. Naturally, ‘the context’ is also responsible for presenting an interface of the state machine to its client.
Now - the most important question - what does this really solve ?
Well, as GOF stated it succinctly, it “localizes state specific behaviour” - that says it all .
So when you want to modify the behaviour of the system when it is in a particular state, you just have to modify the implementation of that particular concreateState class; your changes are going to be ‘contained’. It is also easier now to add a new state : create a new class for the new state and give flesh to all the abstract methods defined in State interface and have the new state in your context … but unfortunately in this case that is not the end of it, in most implementations you have to change other states as well for transitions to your new state. And this leads us to the next section.
Though state pattern is the perfect solution for a number of problems, a definite weakness of the state pattern is that it does not specify a clean solution to implement state transitions.
About transitions GOF says :
“Either Context or the ConcreteState subclasses can decide which state succeeds another and under what circumstances.”
and
“The State pattern does not specify which participant defines the criteria for state transitions. If the criteria are fixed, then they can be implemented entirely in the Context. It is generally more flexible and appropriate, however, to let the State subclasses themselves specify their successor state and when to make the transition. This requires adding an interface to the Context that lets State objects set the Context’s current state explicitly”.
So GOF’s suggestion is to let subclasses specify transitions and the sample code from GOF looks like this :
class TCPConnection {
…
void ChangeState(TCPState*);
private:
TCPState* _state;
};
Here TCPConnection is the context object which has the state changing interface ChangeState(TCPState*) and TCPState is the state interface. ChangeState() has been implemented as :
void TCPConnection::ChangeState (TCPState* s) {
_state = s;
}
TCPConnection::ChangeState() is invoked by TCPState::ChangeState() which looks like :
class TCPState {
…
void ChangeState(TCPConnection*, TCPState*);
};
void TCPState::ChangeState (TCPConnection* t, TCPState* s) {
t->ChangeState(s);
}
Now a concreteState implementation would change the state when necessary as shown below :
void TCPEstablished::Close (TCPConnection* t) {
// send FIN, receive ACK of FIN
ChangeState(t, TCPListen::Instance());
}
Here TCPEstablished is a concreteState.
The problem :
The main weakness of the above approach is that there is coupling among states - to quote GOF : ” A disadvantage of decentralization is that one State subclass will have knowledge of at least one other, which introduces implementation dependencies between subclasses.”
Though this is a known problem, in certain scenarios where each state object may represent a complex component from the problem space rather than just a state, this is a huge price to pay .
Let us take an example a GUI state machine that delegates behaviour to subelements according to current user state. Each subelement in our example is complex, has its own model, and may have sub-subelements. Each subelement behaves in a certain way with user events. And some of these events may trigger transitions to other other subelements. The stimuli-subelements-transition map is context dependent and the context may change dynamically.
Now let us check the forces we are dealing with here :
I. It should be easy to add, modify and even delete subelements without modifying other subelements. In a real world development team the responsibility of implementing these subelements may lie with multiple developers, so it could be a real necessity to have minimum possible coupling among them.
II. The stimuli-subelements-transition map is context dependent.
III. Contexts change dynamically.
The solution :
Reactions to events are sub-element specific, and we need sub-elements to be independent of each other. So, a la classic state pattern each subelement must have a concrete derivation with a ‘context’ talking to an abstract ’subelement’ interface. Now, if we let each subelement decide its successor we not only have strong coupling among subelements but we can not also support the requirement of having multiple, dynamically changing contexts. The dirty subelement implementation to support such a scenario with multiple contexts may look something like :
if(context.type == Context::Navigation)
{
ChangeState(Subelement::BreadCrumb);
}
else if (context.type == Context::ShortCut)
{
ChangeState(Subelement::ShortCutMenu);
}
So how do we solve this problem ? The essential core of the proposed solution can be stated as : “distribute reactions among subelements but centralize the transition-stimuli map”. The basic problem with traditional state pattern is that the State Transition Table is scattered across all the states. To balance all the forces mentioned above a ‘context’ now may actually have to act its role and take the responsibility of centralizing the State Transition Table, which makes perfect sense because after all a transition table is the characteristic of a ‘context’ not a state! Note that in traditional state pattern a ‘context’ was just a wrapper that delegated everything to current state. So now if you need to change the state transition table, you just need to change your context - states/subelements are not affected by changing the context. This is also very clean since the transition table is in one place and not ‘contaminated with the implementation of the actions’ (I picked this phrase from Robert C Martin, though he came up with a different solution to the same problem).
Implementation :
To implement this design we need to define a protocol between the context and states. This protocol is defined with events and secondary transition stimuli. Events are generated externally and are handled by states, while states generate secondary transition stimuli towards the context upon receiving/processing a ’significant event’. A context defines a transition table that has mapping from [current state, secondary transition stimulus] to [next state]. To check this implementation with our example, subelements process, consume and react internally to most of the user events. A subset of those user events may trigger a transition from one subelement to another. While processing such a user event a subelement generates a secondary transition stimulus towards the context. Note that subelements responsibility ends at generating the secondary stimulus, it does not care about how that may effect a state transition.
A very common question is so how is it different from a straight forward table driven state machine ? Or, why dont we have everything in a table like the pre-OO implementation of state machine where we have a two dimensional table of states, events and function pointers?
Because the designing in terms of ’state’s, where states are decoupled from each other, and where each state reacts to events in an independent fashion is much cleaner design. We needed the current solution because though each state reacts to event and ‘reaction’ is state specific, only some events trigger transitions and transitions are context specific.
I am going to publish a toy example implementation in my next post.
The Monitor pattern vs the Monitor programming construct
Though, the monitor programming construct is always there to support the monitor pattern, it is important to understand the programming construct separately from the pattern. This is necessary because the pattern can be used with all modern threading libraries even if the ’specific programming language’ being used does not have any specific keyword for that.
Monitor as a programming language construct :
Basically, when supported, ‘monitor’ as a programming language construct is there to hide mutual exclusion. So if a procedure is defined to be a monitor then by definition that piece of code is taken to be a critical region. A critical region is a piece of code which can only be executed by one thread at a time. In case of a monitor the programmer himself does not have to put the critical region inside lock-mutex and unlock-mutex, the programming language would take care of it.
[ But this is not there in C++:
For example java has 'synchronized' keyword for monitors, java virtual machine has corresponding monitorentry and monitorexit opcodes, and when java virtual machine encounters monitorentry it acquires a lock, and similarly it releases the lock when encounters monitorexit - the opcodes are not used for monitor procedures but ultimately jvm works with the same principle of locking and unlocking ]
On the other hand the monitor pattern is something like (mutex for critical section) + (wait) + (notify) - the language that has a monitor-like keyword would have all the facilities but the programming language construct is not necessary to implement the pattern.
In C++, with boost 1.34 – replacing the monitor keyword would be as simple as having a scoped mutex :
#include <boost/thread/mutex.hpp>
boost::mutex someMutex;
void someMethod()
{
boost::mutex::scoped_lock lock(someMutex);
// more code
}