State Machines
From IGSTK
Notes for Oct 19 Meeting
Some parts of this page are old, and some are new.
New items:
Items from Aug 25, 2005 meeting (see minutes):
- State Machines in Base Class vs. Derived Class
- Error Handling and the State Machines
- Exceptions and State Machines
- Events and State Machines
Definition
Taken from the Wikipedia
http://en.wikipedia.org/wiki/State_machine
A finite state machine (FSM) or finite automaton is a model of behaviour composed of states, transitions and actions. A state stores information about the past, i.e. it reflects the input changes from the system start to the present moment. A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition. An action is a description of an activity that is to be performed at a given moment. There are several action types:
- Entry action: execute the action when entering the state
- Exit action: execute the action when exiting the state
- Input action: execute the action dependant on present state and input conditions
- Transition action: execute the action when performing a certain transition
Purpose of State Machines in IGSTK
IGSTK uses Finite State Machines (FSM) that hereafter are referred simply as State Machines (SM).
The use of State Machines (SM) in IGSTK design is motivated by
- Safety and Reliability:
- SM will ensure that the behaviour of IGSTK classes will be deterministic
- That all classes will be in a known and error-free state at any given moment.
- Encourage cleaner design
- Since developers must anticipate all possible inputs, states and transitions, a SM formalism encourages and enforces a cleaner and more robust design, free of untested assumptions.
- The correct implementation of the design can be exhaustively tested at run time and compared to the intended design.
- Code Quality Control
- SM facilitates to enforce code coverage in the sense of lines of code tested
- SM make possible to enforce code coverage in the sense of all possible combinations of order of execution. Since a Finite State Machine has a limited (finite) number of inputs and states, and therefore all possible combinations of execution order can be tested at run time.
From the Computational Theory point of view, all computers ARE state machines, and all computer programs ARE state machines regardless of whether the developers used the SM formalism or not. The difference between using the SM formalism or not at the design phase is that programs that are not using it will be State Machines with very large numbers of states, inputs and transitions, and for which only a vanishingly small subset of possible transitions has actually been considered by the developer, and an even smaller set will have been actually tested. Using code that is not based on a SM formalism results in applications that exhibit unpredictable and unreliable behavior, because at run time, they can easily enter in any of the thousands or millions of states that were never explored by the developer, such states will mostly lead to error conditions that may or may not become visible to the users of the application.
If we think about the State Machine as represented by a graph of states and transitions, (also know as a State Diagram), we can visualize the execution of a program as being equivalent to a walk through this graph. Typical programs have very large state machines and developers explore only a handful of the millions of possible walks through the graph. Users, who are unaware or untrained on the develpers assumptions will walk many of the never-before tested paths and easily will put the program in an error state.
[DG comments 08/24/2005]
The biggest advantage of state machines is that they can be submitted to formal analysis procedures, both at the design stage and at the testing stage. Unfortunately, we aren't taking advantage of this! Do we have the necessary resources?
State Machines in Base Class vs. Derived Class
[Discussion started by AE on August 18, 2005]
Overview
The architectural decision of the state machines in IGSTK boils down to the question of whether to integrate the state machines in the base classes or derived classes or in both ( hierarchical class design). Adding state machines into the base class will help to streamline and enforce derived classes to use the same states and transition conditions . On the other hand, adding state machines into the derived classes will create a more flexible and extendable architecture to integrate new features (states, transitions) in the future which might not have been anticipated during the base class design. For example, if we would like to handle trackers from a different manufacturer, we might be having difficulties with the current state machine design in the Tacker classes.
The third option is the hierarchical state machine (HSM) design . Base classes will capture the common states, inputs and transitions. While dervied class-specific conditions are handled by the derived class state machines themselves. A presenation on HSM by Miro Samek would be a good reference to read.
Design Criteria
Additional consideration points here are that the design that we choose should be such that:
- It scales to many derivation levels. That is, if we have a hierarchy that is four or five levels deep, the states machine of the base classe and/or the derived classes will interact consistently.
- It should not break the encapsulation of the base class, because encapsulation is critical for ensuring safety. The mechanism should not open options for additional risk to the patient.
- It facilitates the validation and quality control of the code. If the solution selected makes harder to evaluate the correctness of a class, it will make it prone to error, and will result in exposing the patient to unecessary risk.
Certain programming guidelines must be put in the perspective of the critical applications for which IGSTK is being used. IGSTK will be used in systems that are directly responsible for the survival of a patient. In most minimally invasive interventions, an IGSTK-based software application will the the main, if not the only, guidance available to a surgeon. A failure or malfunction in the application, can easily result in putting the patient in a life-threatening situation.
The creation of C++ base classes is motivated by engineering guidelines of
- Code reuse
- Simplification of code maintenance
- Unification of the API
The use of State Machines is motivated by enforcing principles of
- Safety and robustness in the application.
- Making possible to fully test the code before an intervention
- Ensure that the application will always be in an error-free state
Whenever the engineering guidlines conflict with the principles of patient-safety we must give priority to patient safety. If replicating state machines results in safer applications, we should prefer this options despite the violation of the engineering principles of code reuse. In other words, we should never put the convenience of the software developers before the safety of the patient.
Error Handling and the State Machines
[Discussion started by DG on Aug 18, 2005]
Catching Errors
Whenever an IGSTK object attempts to perform an operation, and that operation fails, the IGSTK object must set an input to its state machine to indicate the error. This implies that whenever an IGSTK object makes a call to a function that might raise an exception, any and all exceptions must be caught, and the appropriate state machine input must be set. (Luis: agree)
Generating Errors
Furthermore, if an IGSTK object needs to generate exceptions or Events, then those events should be generated by code that is called when the state machine receives an input that indicates that something event-worthy or exception-worthy has occurred. There should never be code that reads "if (condition) then (generate exception or event)" because the use of such code defeats the purpose of the state machine. When an Event is generated, it should be generated directly as a result of a state machine transition without any other conditions imposed. (Luis comment: fully agree with avoiding the if() statements, but still insist in that IGSTK classes should not throw exceptions, because the recovery from those exceptions will be left on the hands of the application developer).
Error Recovery
An IGSTK object might, as a result of an error that it encounters, enter a state that it needs help to get out of. For instance, a resource that it requires might go offline (e.g. someone unplugs a network cable).
When something like this occurs, the IGSTK object must generate an error that indicates what problem has occurred, and must then enter a state in which it is ready to receive an input from the application to indicate that the problem has passed.
(Luis comment: Agree on the principle, but just to clarify: IGSTK classes shouldn't have 'error states', they should always be in an valid state. However, their inputs may encode error conditions, e.g. like the disconnection of a network cable, such event should be converted into a input to the state machine of the relevant classes, and they should have anticipated a state transition for this input. Additionally, our 100% code coverage policy should enforce that all possible error situation must be tested. That is, our testing framework should create on purpose the error conditions and verify that the classes behave correctly in response to the inputs that encode error conditions).
What Should Happen When No Transition Is Defined For An Input
Currently, if the state machine receives an input, but is in a state for which there is no transition defined for that input, it prints the state and input to "cerr".
In production code, the state machine should never receive an input that it can't handle. It stands to reason, then, that a bad input should result in either an assert() or an exception so that all instances of bad inputs are encountered and dealt with during the testing phase of the code.
(Luis comment: Agree. We should change the current internal representation of the transition table to for the application developer to use a dense matrix where all cells are full. That is, the application developer must define state transition for every combination of (state,input). The SetReadyToRun() method in the State Machine should verify that the matrix is full before accepting to run).
DG Follow-up: Using a dense transition table will not make the problem go away, because all inputs are not meaningful for all states. Are we going to make dense transition tables by simply setting "NoAction" transitions for meaningless state/input combinations? Or are we going to flag an error when meaningless state/input combinations occur?
I honestly can't forsee us being able to design objects where every single state/input combination is meaningful.
LI Follow-up: It depends on what we understand by "meaningful". The interest of having a dense transition table is that the developer will have to go through the exercise of considering every possible combination of input and state. It may be that many of those combination should neve occur, and therefore, if they appear at run-time, they should be flagged as an error situation. It is likely that many of the combinations will simply lead to NoAction and to remain in the same state, but it is up to the designed of the class to specify that this should be the case. A no-dense transition table leave us with the uncertainty of whether a missing transition is not there because it was considered to be an impossible case... or because the developer overlooked that case, and it is actually an implementation error.
KG $.02: I can understand both sides of this argument, but agree with Luis' principle that developers should be forced to consider all inputs. I wonder what will happen if one of our state machines defines a large number of inputs? I also wonder if this policy will really force developers to examine what will happen, or if many will simply "cut-and-paste" a no-op like solution anyway. Finally, will a lot of no-ops make our code bloated? I think automated testing would actually reveal whether a developer has not considered any input s/he should have considered.
Exceptions and State Machines
[Discussion started by DG on Aug 23, 2005]
The IGSTK Style Guide states the following:
C++ Exceptions will not be used since they make difficult to guarantee that the state of the classes is valid after recovering from an exceptions.
My goal is to demonstrate that it is not difficult at all to safely use exceptions with state machines. Only one rule must be followed:
- IGSTK object must catch any exceptions that are thrown by any methods or functions that it calls, and depending on the exception that is caught, must push the appropriate input to its state machine
Object::AttemptSomething()
{
try
{
do_something;
m_StateMachine.PushInput(m_SomethingSuccessInput);
}
catch (...)
{
m_StateMachine.PushInput(m_SomethingFailureInput);
}
}
Note that the exception is not re-thrown. The only result of the exception is that m_SomethingFailureInput has been sent to the state machine. So we must make sure that we execute as a result of the m_SomethingFailureInput will do everything that is necessary to recover from the error.
What if the error has left our object in an "error state" of some sort that its caller (i.e. the application or another object) will have to get us out of? One might ask, can we re-throw the exception inside the "catch"?
Object::AttemptSomething()
{
try
{
do_something;
m_StateMachine.PushInput(m_SomethingSuccessInput);
}
catch (...)
{
m_StateMachine.PushInput(m_SomethingFailureInput);
m_StateMachine.ProcessInputs();
throw;
}
}
The call to ProcessInputs() is necessary because we definitely don't want to re-throw the exception until the state machine has done all failure processing. The only danger is, what happens if the call to ProcessInputs() results in the execution of code that generates another exception? If we could guarantee that would never occur, then the above code would be completely safe.
Can we guarantee that? Actually, yes we can, because the only code that is executed is that code that we specifically wrote to be executed when m_SomethingFailureInput is processed.
However, all is not roses! The AttemptSomething() function was itself called as a result of an input to the state machine. That means that ProcessInputs() is currently being executed, and we are calling ProcessInputs() again from inside of itself! Before we can do that, we need to be sure that the code in igstkStateMachine.txx can handle this situation.
The following chunk of code at the end of StateMachine::ProcessInput() is going to break if ProcessInputs() ends up calling itself:
if( transition.GetAction() )
{
((*m_This).*(transition.GetAction()))();
}
m_State = transition.GetStateIdentifier();
}
The Action() function is the transition function that is called as a result of the state machine receiving a particular input while it is in a particular state.
The problem is that if Action() is called before m_State is set, and if Action() calls ProcessInputs(), then we start processing the next input before we have set the state that results from the current input.
The solution is fortunately very simple. If Action() is the last thing called in ProcessInput(), the problem goes away:
m_State = transition.GetStateIdentifier();
if( transition.GetAction() )
{
((*m_This).*(transition.GetAction()))();
}
}
In fact, setting the new state before calling the Action() function is a good idea regardless. Consider the following state machine transition from igstkSerialCommunication.cxx:
m_StateMachine.AddTransition( m_IdleState,
m_OpenPortInput,
m_AttemptingToOpenPortState,
&SerialCommunication::AttemptToOpenPort);
It makes intuitive sense that the Communication object is set to the AttemptingToOpenPortState before AttemptToOpenPort() is called. After all, AttemptToOpenPort() is going to set a OpenPortSuccessInput or OpenPortFailure input, and those inputs can only be processed from the AttemptingToOpenPortState.
Wasn't StateMachine::PushInput() written specifically written to address this? Perhaps adding PushInput() was the wrong solution, and setting m_State before calling the Action() function is the right solution.
Luis Comments
Fully agree with the policy that IGSTK classes should catch potential Exceptions thrown by the execution of the action methods or the validation methods, and convert those situations into inputs to the state machine. In that way the integrity of the state machine is preserved and the management of error conditions are built-in the logic of the normal state transitions.
Still strongly disagree with rethrowing the exceptions, or throwing new exceptions from IGSTK classes. The only situation that will justify such action is a terminal condition, that is, an error situation that is so severe that the only option is to stop the application and ask the surgeon to continue without the assistance of the computer. In any other case, the risk with throwing exceptions is that there is no safe and reliable way to reset the state machine for continue working. In other words, there is no way to resume the execution of the IGSTK class that throwed the exception, because the encapsulation of the state machine will make imposible for the application developer to purposely put the state machnine in a particular state. The only option, as David pointed out, will be to change the policy of the State Machine for passing first to the next state, and then invoke the action method.
Changing the policy of the State Machine is certainly an option. As the definition of the State Machine describes, and as KG pointed out early in the design stage, we could have actions that are executed when leaving a state, or when entering a state, or in the middle of a transition. We have opted so far, by using the Action in the middle of the transition. We should reconsider that decision, if that helps to adapt the State Machine to our needs, we could even have all three options, that is, functions to be executed when leaving a state, when entering a state, and in the middle of a transition.
For the sake of patient safety I would rather see a design where the classes are such that instead of taking actions that leave them in states from which they don't know how to move and the only option is to throw an exception asking for help, they will avoid stepping into such situations.
In our discussion with Andinet we were comparing this with walking on the ice. The Exception-throwing approach is equivalent to walking in the ice by making jumps to the next position, and if the ice breaks and we fall in the water, then we cry for help. A safer way to walk in the ice is to use sticks or rocks to probe the next position, and only move there when it has proven to be safe. Translating this into C++, we may want to have pre-condition methods, just like the boolean functions, that evaluate the validity of executing the action required by the application developer. If the accion is not viable, the State Machine does not move from its current safe state, and it notifies the user via an Event() (not an exception) that we have declined to performed the requested action. It is explicit in any case, in our API with the application developer that ALL her/his requests are just "requests" and that they may or may not be satisfied depending on the conditions of the State Machine.
David's Follow Up
There are always going to be instances where we can never know if a function call is going to be successful until we try it. The most obvious example of this is any IO operation. When we try to read a data file from across the network, we can't know ahead of time that the network connection won't be broken halfway through.
There are also going to be instances where asking the user for assistance is unavoidable. Don't forget that a software application is not a closed system, the user and any peripheral devices must also be considered. And if that user is a surgeon, then he/she is definitely not going to want to be left out of the loop. There are going to be times when the surgeon has knowledge or abilities that the application does not have. A trivial instance is that if a cable is unplugged (or heaven forbid, tripped over), it is the user that must plug it back in.
I think that your "thin ice" analogy is more of an appeal to emotion than a valid argument. We're talking computers here. If an error occurs, in many cases we _can_ restore the program to exactly the same state as before the error occurred, except that know we know that the last time we made an attempt we encountered an error. In fact, exceptions are designed for exactly this purpose. Our program does not end up "cold and wet".
However, even though I don't think there are any strong disadvantages to using exceptions, I don't see any great advantages either.
The two big advantages of using exceptions in most software design are as follows:
- exceptions allow error checking to be done at few positions in the code (i.e. you no longer need to check for an error every single time you call a function that might fail).
- exceptions provide valuable debugging information during the testing phase of the code.
The first advantage does not apply to IGSTK, because the state machine _is_ going to have to check for errors with every attempted function call in order to protect its own integrity.
The second advantage does apply, but note that it is something that might speed up code development a bit, but it is unlikely to have any impact (positive or negative) on the quality of the released code.
=== Luis Followup 2 === I would insist in the ice analogy, because the point here is that an IGSTK program shouldn't move into a state until it is considered to be valid. If a transition depend on the reading of a file throught the network to be successful, then the file must be read first as a precondition and the status of the read result used as an input to the state machine for triggering the transition. In other words, transitions should only happened on the basis of accomplished facts. The alternative option of "undoing" is quite hard to implement, specially when we are dealing with external devices that do not have reversible operations. A closer analysis of our error management problem seems to indicate that we haven break up the actions of the SM-based classed in appropriate pieces. In principle any action that an SM-based class request to an external device or to a helper class, and that is succeptible of failure, should be done in the form of a "request" to that device or helper class, and the SM class should move in to a waiting-state. Whenever the device or helper class answers, its response should be converted to a SM input into the current class. It seems that part of the difficulty that we are facing with the error management is due to the fact that we are attempting to conglomerate many of this operations in a single method.
David Followup 2
If you read the following, you will see that the use of an "AttemptState" ensures that the transition to the following state only occurs after we have validated the result. And the code is definitely more compact than if Events are used for this.
- an "AttemptInput" is sent to our state machine
- the state machine enters the the AttemptState
- the state machine executes the AttemptFunction
- the AttemptFunction calls an I/O function and does a try/catch as shown in the above code
- the appropriate input is set depending on the result (i.e. the try/catch is used for result validation)
- the state machine enters the state defined by the transition table (validation has been done, so this is safe)
- the transition function defined in the transition table is executed
KG: It sure sounds like you guys are vehemently agreeing with one another. When I reviewed the code it seemed strange to me to have one request cause two "jumps" in the state machine, but based on these arguments it makes more sense. I will say that it seemed to me there were function calls in various places (on transitions, within states, outside of the state machine) in the code. I would like to see more example code and best practices around exactly where in the call sequence certain logic belongs. It may make sense to introduce explicit State classes just to make this call sequence more explicit.
Events and State Machines
[Discussion started by DG on Aug 23, 2005]
Events and Exceptions
Events don't behave like exceptions, and they are not generally used for the same kind of things that an exception would be used for.
Generating an exception within a function is similar to calling "return", except that instead of continuing execution from the point at which the function was called, the exception keeps on falling through until it gets caught. And if it never gets caught, the program crashes.
When an exception is generated, code execution continues from where the exception was caught. When an Event is generated, the Event's Observer is called, and then code execution continues from where the Event was generated.
Clearly, you do not want to confuse Events and exceptions with each other! They behave completely different from one another.
Events are very useful in IGSTK. For example, the SpatialObject observes the TrackerTool's TransformModifiedEvent, and sets m_TrackerTransformInput whenever it occurs. This is very clean and elegant. One object generates an Event as a result of one if its state transitions, and another object observes the event and sets an input to its own state machine.
(Luis comment: Fully agree. In fact, David points out here very clearly why we shouldn't throw Exceptions: because the execution of code continues from where the Exception is caught, and therefore, resuming the execution of the State Machine that throwed the exception is left on the hands of the Application Developer with hope that she/he is a very skillful C++ programmer. IGSTK should rather be designed on the assumption that the application developer is rather dummy or at least suffering from a strong case of sleep deprivation).
Events and Error Handling: a How-Not-To Example
Events can also be used for error handling, but first let's look at an example of how not to do this. Consider a Tracker object that is calling SerialCommunication:Write() so that it can communicate across the serial port:
m_Communication.Write();
The Write() function can generate two events: a WriteSuccess event and a WriteFailure event. The Tracker class will have to add observers for those events:
m_Communication->AddObserver( WriteSuccessEvent(), m_WriteSuccessObserver ); m_Communication->AddObserver( WriteFailureEvent(), m_WriteFailureObserver );
And we need to set callback functions for these observers:
m_WriteSuccessObserver->SetCallbackFunction( this, &Tracker::WriteSuccessMethod); m_WriteFailureObserver->SetCallbackFunction( this, &Tracker::WriteFailureMethod);
And we need to define the callback functions:
void Tracker::WriteSuccessMethod( void )
{
m_StateMachine.PushInput( m_WriteSuccessInput );
}
void Tracker::WriteFailureMethod( void )
{
m_StateMachine.PushInput( m_WriteFailedInput );
}
In addition, we have to declare m_WriteSuccessObserver, m_WriteFailureObserver, WriteSuccessMethod, and WriteFailureMethod in the header file.
Compare the above with the tiny amount of code that is necessary to do the same thing if we use a return value to indicate that an error has occurred:
bool successful = m_Communication.Write();
m_StateMachine.PushInputBoolean( successful,
m_WriteSuccessInput,
m_WriteFailureInput );
Or, even if exceptions are used, the amount of code is still fairly small:
try
{
m_Communication.Write();
m_StateMachine.PushInput(m_WriteSuccessInput);
}
catch (...)
{
m_StateMachine.PushInput(m_WriteFailureInput);
}
Events and Error Handling: a How-To Example
As we can see from the previous example, Events are a very tedious way of checking whether a particular function call was successful or not.
Events are, however, a very useful way for connected components to inform each other when they go offline or come back online.
Consider the interaction between a SpatialObject and a TrackerTool, or between a TrackerTool and a Tracker. The TrackerTool does not constantly ask the Tracker for new Transforms. Instead, the TrackerTool waits for tracker to call its SetTransform() method.
So what should happen if the Tracker goes offline? Of course, the SpatialObject must be notified. So the Tracker will call a method of the TrackerTool that will put the TrackerTool into its "NotAvailable" state. As a result of this, the TrackerTool will generate an event to indicate that it has gone offline. The SpatialObject will observe that event and respond accordingly.
Comparing this example to the one in the previous section is like comparing apples and oranges. The SpatialObject passively waits for the TrackerTool to send information to it. The Tracker, on the other hand, is always actively calling its Communication object, and with each call, it needs to know whether the Communication object succeeded or failed.
Depending on the situation, we need to use the appropriate error handling mechanism.
Luis Comments
Agree with most of David's presentation. In particular with the use of the boolean macro for converting error conditions of helper classes into input to the current state machine. The only issue that breaks the IGSTK style in that case is that the communication class has to have a Write() method return a boolean. In the original dialog of the state machine from the point of view of the Communication class, this should have been separated into
- A method called: void RequestWriting( string )
- A method called: bool GetWrittingResult() const
From the point of view of the Tracker this is a minor annoyance because two methods must be called instead of one, but it makes clear that the Requests made to a class may or may not be satisfied.
[DG: splitting this into two functions provides absolutely no benefit as compared to using a well-documented return value for the function]
The concerns about the use of Events for error notification can be addressed by appropriate macros that will take care of converting received events into error-condition inputs to the state machine. We don't really need to create an observer per event, nor a callback per event, just a translation table with pairs :(Event,erroInput), given that the code will be always the same.
A catch(...) is a good idea in the sense that it captures all possible Exceptions, but it is risky in the sense that we don't really know what actually happened. In general we should first try catching knonw exceptions, and then as last resort use the catch-all options. Fortunately, the syntax of the try/catch allows to put any number of catchs in cascade.
try
{
m_Communication.Write();
m_StateMachine.PushInput(m_WriteSuccessInput);
}
catch ( itk::ExceptionObject & excp )
{
m_StateMachine.PushInput(m_WriteFailureInputDueToITK);
}
catch ( std::exception & excp )
{
m_StateMachine.PushInput(m_WriteFailureInputDueToSTD);
}
catch (...) // Last resort option
{
m_StateMachine.PushInput(m_WriteFailureInput);
}
[DG: using a catch like this is a very good idea, and we should definitely catch events according to type when we use third-party libraries (ITK for example) that throw exceptions]
State Machine to Call Sequences
KG: I have traced through the call sequences of four of the classes that use State Machines to get a feel for whether they are being applied in the same way. The short answer is they are not, though the long answer is that they are not too different and each has some good ideas. Below are links to JPEGs of the sequence diagrams and some short comments for discussion. It might be useful to have the .dot files up in GraphViz at the same time.
NOTE: Each of these covers one common request to the component typically initiated from its test program. Each sequence assumes the success, or happy day scenario.
| Sequence Diagram | Comments |
|---|---|
 | I think this is the best example of a SM. The use of attempting states with boolean results mapped to inputs works well. We could even generalize this so the component developer maps results to input types via a standard data structure with the benefit that the state machine is responsible for the conditional. It does not get rid of it, but it moves it to one place. I still do not like that the component developer has to be so aware of the sequence that subsequent PushInput calls after the first do not require ProcessInputs. This mistake is made below in DICOMImageReader. This component is also interesting in how it incorporates subclass behavior on transitions via the Internal methods. This delegates behaviors to subclasses, even though those subclasses do not have state machines. Not sure why the Internal methods cannot be defined in a separate interface-style class hierarchy, but no big deal. |
 | This code was updated after previous comments regarding the setting of a success state before the actual action was performed. This was handled by introducing an Attempt state, and this helps, though the second PushInput call happens in the middle of application code. The bigger issue though, is a second call to ProcessInputs that is not needed since there is already a ProcessInputs loop ongoing from step 3. This may not break anything in this particular sequence, but is an example of how understanding of the input processing machinery is required on the part of the component developer, and I do not think that is a good thing. |
 | We discussed the PulseGenerator in the October 6 tcon. It is still unintuitive to me to have 4 separate PulseGenerators, one per view, but David convinced me that since we are single-threaded it all works out, if sub-optimally. |
 | Tick sequence is referenced from the above PulseGenerator. |
 | This is an interesting example of a base class and derived class both having state machines and there being communication between the two. It works well too, as the subclass has to use the request method of the superclass as the desired behavior is private. So there are two state machines working in concert here, which is doable this way when the SMs are disjoint and govern disjoint behavior. A couple issues. One is that there are class variables at the base and derived class levels holding a reference to the same object (the spatial object itself), which may be caused by the desire to leave the state machines disjoint. Second, this SM does not have Attempt states, so there are potential issues where if the transition action is not successful then there could be a problem. This particular SM though, has only set behavior and so would not expect to have such an issue. |
 | This is the Do we need a state machine for Get methods? example. We discussed this to some extent in the October 6 tcon. I think the use of the SM is fine, it is the strange way the Get information is returned that bothers me. There is a thread on the mailing list that addresses this example in more detail, but I think it is a side issue that still needs to be resolved. |
Example State Machines
[DG] Here are the state machines for the classes, as generated from the C++ code on Oct 19th.
Note that the only inputs on these diagrams are the ones that lead to a state transition. Any input that does not result in a state transition is not shown. As a result, the SpatialObject, ObjectRepresentation, and View diagrams look overly simplistic.
 |
 |
 |
   |
 |
  |
Recurring Patterns in State Machine Design
Certain state machine pieces appear over and over again in the design of IGSTK classes. Several of those pieces are described below.
Request for a State Transitions That Might Fail
If the actions that are performed during a state transition might fail, an additional "Attempt" state must be added.
This pattern occurs throughout the Tracker and SerialCommunication code.
For example, when Tracker::RequestStartTracking() is called, the StartTrackingInput is sent to the state machine.
- The state machine validates that StartTrackingInput is a valid input for its current state.
- The state machine transits to the AttemptingToTrackState
- The state machine executes the AttemptToStartTrackingProcessing() method (not shown)
- If the attempt was successful, the Attempt method must set the SuccessInput, otherwise it must set the FailureInput
- The SuccessInput leads to the TrackingState, and StartTrackingSuccessProcessing() (not shown) is called
- The FailureInput leads back to the initial (since the attempt to reach the tracking state failed)
- The FailureInput also results in the generation of some sort of error indicator
The sequence is:
- Check that input is valid for current state (automatically done by state machine)
- Attempt an action
- If action succeeded, transit to final state
- If action failed, go back to initial state and generate an error
Requests Leading to an Action That Might Fail
This pattern occurs in the RequestRead() and RequestWrite() methods of SerialCommunication, and in the RequestUpdateStatus() method of the tracker. Depending on whether the action was successful or not, different processing and event generation is done on the way back to the ActiveState.
The SerialCommunication class also has a TimeoutInput that leads back from the AttemptState, which indicates that the more than a preset amount of time had passed before it could be determined whether the attempt was successful. The TimeoutInput is just another kind of failure input.
Requests Requiring Parameter Validation Before a Transition
This is like the very first example, except that no "Attempt" processing is necessary. The only things that needs to be done is that the method parameters must be checked.
This example code is from igstk::ObjectRepresentation, it checks to make sure that the SpatialObject is not a null pointer before it sets the ValidSpatialObjectInput.
/** Set the Spatial Object */
void ObjectRepresentation::RequestSetSpatialObject( const SpatialObjectType * spatialObject )
{
m_SpatialObjectToAdd = spatialObject;
if( !m_SpatialObjectToAdd )
{
m_StateMachine.PushInput( m_NullSpatialObjectInput );
m_StateMachine.ProcessInputs();
}
else
{
m_StateMachine.PushInput( m_ValidSpatialObjectInput );
m_StateMachine.ProcessInputs();
}
}
Combination of Validation and Attempt
This pattern combines a validation step with an attempt step. If an error occurs at the parameter validation stage, then an InvalidInput will be set. If an error occurs at the attempt stage, then a FailureInput will be set.
Simple Parameter Validation (No Transition)
This very simple pattern can be used to verify that a RequestSetValue(v) method is providing a valid parameter, when the setting of the parameter is not resulting in a state change in the state machine. The InvalidInput can be used to generate an error indicator.
Request For a State Transition That is Guaranteed to Succeed
This pattern applies when the transition requested by a particular input is guaranteed to succeed.
Request for an Action That is Guaranteed to Succeed
This pattern is used when the only purpose of the input is to drive some action to be performed. It can only be used if the action is guaranteed to always be successful. Note that the action that is performed depends on the combination of Input and State. The same input will not necessarily result in the same action for all states.
Inputs Received While In The Wrong State
One of the primary functions of any state machine is to keep things from happening when they're not supposed to. If a Communication object is requested to communicate with a device before the port is opened, the proper action to take is to generate an error.
In many situations, the correct action for a particular Input/State combination is to take no action at all.
