|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
<html>
|
|
Packit |
58578d |
<head>
|
|
Packit |
58578d |
<meta http-equiv="Content-Language" content="en-us">
|
|
Packit |
58578d |
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
|
|
Packit |
58578d |
<meta name="GENERATOR" content="Microsoft FrontPage 6.0">
|
|
Packit |
58578d |
<meta name="ProgId" content="FrontPage.Editor.Document">
|
|
Packit |
58578d |
<link rel="stylesheet" type="text/css" href="../../../boost.css">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
<title>The Boost Statechart Library - Rationale</title>
|
|
Packit |
58578d |
</head>
|
|
Packit |
58578d |
|
|
Packit |
58578d |
<body link="#0000FF" vlink="#800080">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"header">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"../../../boost.png" border="0" width="277" height="86">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The Boost Statechart Library
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Rationale
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Introduction
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Why yet another state
|
|
Packit |
58578d |
machine framework
|
|
Packit |
58578d |
|
|
Packit |
58578d |
State-local storage
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Dynamic configurability
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Error handling
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Asynchronous state
|
|
Packit |
58578d |
machines
|
|
Packit |
58578d |
|
|
Packit |
58578d |
User actions: Member
|
|
Packit |
58578d |
functions vs. function objects
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Limitations
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Most of the design decisions made during the development of this library
|
|
Packit |
58578d |
are the result of the following requirements.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Boost.Statechart should ...
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
be fully type-safe. Whenever possible, type mismatches should be
|
|
Packit |
58578d |
flagged with an error at compile-time
|
|
Packit |
58578d |
|
|
Packit |
58578d |
not require the use of a code generator. A lot of the existing FSM
|
|
Packit |
58578d |
solutions force the developer to design the state machine either
|
|
Packit |
58578d |
graphically or in a specialized language. All or part of the code is then
|
|
Packit |
58578d |
generated
|
|
Packit |
58578d |
|
|
Packit |
58578d |
allow for easy transformation of a UML statechart (defined in
|
|
Packit |
58578d |
http://www.omg.org/cgi-bin/doc?formal/03-03-01)
|
|
Packit |
58578d |
into a working state machine. Vice versa, an existing C++
|
|
Packit |
58578d |
implementation of a state machine should be fairly trivial to transform
|
|
Packit |
58578d |
into a UML statechart. Specifically, the following state machine
|
|
Packit |
58578d |
features should be supported:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Hierarchical (composite, nested) states
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Orthogonal (concurrent) states
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Entry-, exit- and transition-actions
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Guards
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Shallow/deep history
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
produce a customizable reaction when a C++ exception is propagated
|
|
Packit |
58578d |
from user code
|
|
Packit |
58578d |
|
|
Packit |
58578d |
support synchronous and asynchronous state machines and leave it to
|
|
Packit |
58578d |
the user which thread an asynchronous state machine will run in. Users
|
|
Packit |
58578d |
should also be able to use the threading library of their choice
|
|
Packit |
58578d |
|
|
Packit |
58578d |
support the development of arbitrarily large and complex state
|
|
Packit |
58578d |
machines. Multiple developers should be able to work on the same state
|
|
Packit |
58578d |
machine simultaneously
|
|
Packit |
58578d |
|
|
Packit |
58578d |
allow the user to customize all resource management so that the
|
|
Packit |
58578d |
library could be used for applications with hard real-time
|
|
Packit |
58578d |
requirements
|
|
Packit |
58578d |
|
|
Packit |
58578d |
enforce as much as possible at compile time. Specifically, invalid
|
|
Packit |
58578d |
state machines should not compile
|
|
Packit |
58578d |
|
|
Packit |
58578d |
offer reasonable performance for a wide range of applications
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"WhyYetAnotherStateMachineFramework">Why yet another state machine
|
|
Packit |
58578d |
framework?
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Before I started to develop this library I had a look at the following
|
|
Packit |
58578d |
frameworks:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The framework accompanying the book "Practical Statecharts in C/C++"
|
|
Packit |
58578d |
by Miro Samek, CMP Books, ISBN: 1-57820-110-1
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"http://www.quantum-leaps.com">http://www.quantum-leaps.com Fails
|
|
Packit |
58578d |
to satisfy at least the requirements 1, 3, 4, 6, 8.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The framework accompanying "Rhapsody in C++" by ILogix (a code
|
|
Packit |
58578d |
generator solution)
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"http://www.ilogix.com/sublevel.aspx?id=53">http://www.ilogix.com/sublevel.aspx?id=53
|
|
Packit |
58578d |
This might look like comparing apples with oranges. However, there
|
|
Packit |
58578d |
is no inherent reason why a code generator couldn't produce code that can
|
|
Packit |
58578d |
easily be understood and modified by humans. Fails to satisfy at least
|
|
Packit |
58578d |
the requirements 2, 4, 5, 6, 8 (there is quite a bit of error checking
|
|
Packit |
58578d |
before code generation, though).
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The framework accompanying the article "State Machine Design in
|
|
Packit |
58578d |
C++"
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"http://www.ddj.com/184401236?pgno=1">http://www.ddj.com/184401236?pgno=1
|
|
Packit |
58578d |
Fails to satisfy at least the requirements 1, 3, 4, 5 (there is no
|
|
Packit |
58578d |
direct threading support), 6, 8.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
I believe Boost.Statechart satisfies all requirements.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
storage
|
|
Packit |
58578d |
|
|
Packit |
58578d |
This not yet widely known state machine feature is enabled by the fact
|
|
Packit |
58578d |
that every state is represented by a class. Upon state-entry, an object of
|
|
Packit |
58578d |
the class is constructed and the object is later destructed when the state
|
|
Packit |
58578d |
machine exits the state. Any data that is useful only as long as the
|
|
Packit |
58578d |
machine resides in the state can (and should) thus be a member of the
|
|
Packit |
58578d |
state. This feature paired with the ability to spread a state machine over
|
|
Packit |
58578d |
several translation units makes possible virtually unlimited
|
|
Packit |
58578d |
scalability.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
In most existing FSM frameworks the whole state machine runs in one
|
|
Packit |
58578d |
environment (context). That is, all resource handles and variables local to
|
|
Packit |
58578d |
the state machine are stored in one place (normally as members of the class
|
|
Packit |
58578d |
that also derives from some state machine base class). For large state
|
|
Packit |
58578d |
machines this often leads to the class having a huge number of data members
|
|
Packit |
58578d |
most of which are needed only briefly in a tiny part of the machine. The
|
|
Packit |
58578d |
state machine class therefore often becomes a change hotspot what leads to
|
|
Packit |
58578d |
frequent recompilations of the whole state machine.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The FAQ item "What's so cool about
|
|
Packit |
58578d |
state-local storage?" further explains this by comparing the tutorial
|
|
Packit |
58578d |
StopWatch to a behaviorally equivalent version that does not use
|
|
Packit |
58578d |
state-local storage.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
configurability
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Two types of state machine frameworks
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
A state machine framework supports dynamic configurability if the
|
|
Packit |
58578d |
whole layout of a state machine can be defined at runtime ("layout"
|
|
Packit |
58578d |
refers to states and transitions, actions are still specified with normal
|
|
Packit |
58578d |
C++ code). That is, data only available at runtime can be used to build
|
|
Packit |
58578d |
arbitrarily large machines. See "A Multiple Substring Search Algorithm"
|
|
Packit |
58578d |
by Moishe Halibard and Moshe Rubin in June 2002 issue of CUJ for a good
|
|
Packit |
58578d |
example (unfortunately not available online).
|
|
Packit |
58578d |
|
|
Packit |
58578d |
On the other side are state machine frameworks which require the
|
|
Packit |
58578d |
layout to be specified at compile time
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
State machines that are built at runtime almost always get away with a
|
|
Packit |
58578d |
simple state model (no hierarchical states, no orthogonal states, no entry
|
|
Packit |
58578d |
and exit actions, no history) because the layout is very often computed
|
|
Packit |
58578d |
by an algorithm. On the other hand, machine layouts that are fixed at
|
|
Packit |
58578d |
compile time are almost always designed by humans, who frequently need/want
|
|
Packit |
58578d |
a sophisticated state model in order to keep the complexity at acceptable
|
|
Packit |
58578d |
levels. Dynamically configurable FSM frameworks are therefore often
|
|
Packit |
58578d |
optimized for simple flat machines while incarnations of the static variant
|
|
Packit |
58578d |
tend to offer more features for abstraction.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
However, fully-featured dynamic FSM libraries do exist. So, the question
|
|
Packit |
58578d |
is:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Why not use a dynamically configurable FSM library for all state
|
|
Packit |
58578d |
machines?
|
|
Packit |
58578d |
|
|
Packit |
58578d |
One might argue that a dynamically configurable FSM framework is all one
|
|
Packit |
58578d |
ever needs because any state machine can be implemented with it.
|
|
Packit |
58578d |
However, due to its nature such a framework has a number of disadvantages
|
|
Packit |
58578d |
when used to implement static machines:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
No compile-time optimizations and validations can be made. For
|
|
Packit |
58578d |
example, Boost.Statechart determines the
|
|
Packit |
58578d |
"definitions.html#InnermostCommonContext">innermost common context of
|
|
Packit |
58578d |
the transition-source and destination state at compile time. Moreover,
|
|
Packit |
58578d |
compile time checks ensure that the state machine is valid (e.g. that
|
|
Packit |
58578d |
there are no transitions between orthogonal states).
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Double dispatch must inevitably be implemented with some kind of a
|
|
Packit |
58578d |
table. As argued under Double
|
|
Packit |
58578d |
dispatch, this scales badly.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
To warrant fast table lookup, states and events must be represented
|
|
Packit |
58578d |
with an integer. To keep the table as small as possible, the numbering
|
|
Packit |
58578d |
should be continuous, e.g. if there are ten states, it's best to use the
|
|
Packit |
58578d |
ids 0-9. To ensure continuity of ids, all states are best defined in the
|
|
Packit |
58578d |
same header file. The same applies to events. Again, this does not
|
|
Packit |
58578d |
scale.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Because events carrying parameters are not represented by a type,
|
|
Packit |
58578d |
some sort of a generic event with a property map must be used and
|
|
Packit |
58578d |
type-safety is enforced at runtime rather than at compile time.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
It is for these reasons, that Boost.Statechart was built from ground up
|
|
Packit |
58578d |
to not support dynamic configurability. However, this does not mean
|
|
Packit |
58578d |
that it's impossible to dynamically shape a machine implemented with this
|
|
Packit |
58578d |
library. For example, guards can be used to make different transitions
|
|
Packit |
58578d |
depending on input only available at runtime. However, such layout changes
|
|
Packit |
58578d |
will always be limited to what can be foreseen before compilation. A
|
|
Packit |
58578d |
somewhat related library, the boost::spirit parser framework, allows for
|
|
Packit |
58578d |
roughly the same runtime configurability.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
There is not a single word about error handling in the UML state machine
|
|
Packit |
58578d |
semantics specifications. Moreover, most existing FSM solutions also seem
|
|
Packit |
58578d |
to ignore the issue.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Why an FSM library should support error handling
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Consider the following state configuration:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Both states define entry actions (x() and y()). Whenever state A becomes
|
|
Packit |
58578d |
active, a call to x() will immediately be followed by a call to y(). y()
|
|
Packit |
58578d |
could depend on the side-effects of x(). Therefore, executing y() does not
|
|
Packit |
58578d |
make sense if x() fails. This is not an esoteric corner case but happens in
|
|
Packit |
58578d |
every-day state machines all the time. For example, x() could acquire
|
|
Packit |
58578d |
memory the contents of which is later modified by y(). There is a different
|
|
Packit |
58578d |
but in terms of error handling equally critical situation in the Tutorial
|
|
Packit |
58578d |
under
|
|
Packit |
58578d |
"tutorial.html#GettingStateInformationOutOfTheMachine">Getting state
|
|
Packit |
58578d |
information out of the machine when Running::~Running()
|
|
Packit |
58578d |
accesses its outer state Active . Had the entry action of
|
|
Packit |
58578d |
Active failed and had Running been entered anyway
|
|
Packit |
58578d |
then Running 's exit action would have invoked undefined
|
|
Packit |
58578d |
behavior. The error handling situation with outer and inner states
|
|
Packit |
58578d |
resembles the one with base and derived classes: If a base class
|
|
Packit |
58578d |
constructor fails (by throwing an exception) the construction is aborted,
|
|
Packit |
58578d |
the derived class constructor is not called and the object never comes to
|
|
Packit |
58578d |
life.
|
|
Packit |
58578d |
In most traditional FSM frameworks such an error situation is relatively
|
|
Packit |
58578d |
easy to tackle as long as the error can be propagated to the state
|
|
Packit |
58578d |
machine client. In this case a failed action simply propagates a C++
|
|
Packit |
58578d |
exception into the framework. The framework usually does not catch the
|
|
Packit |
58578d |
exception so that the state machine client can handle it. Note that, after
|
|
Packit |
58578d |
doing so, the client can no longer use the state machine object because it
|
|
Packit |
58578d |
is either in an unknown state or the framework has already reset the state
|
|
Packit |
58578d |
because of the exception (e.g. with a scope guard). That is, by their
|
|
Packit |
58578d |
nature, state machines typically only offer basic exception safety.
|
|
Packit |
58578d |
However, error handling with traditional FSM frameworks becomes
|
|
Packit |
58578d |
surprisingly cumbersome as soon as a lot of actions can fail and the state
|
|
Packit |
58578d |
machine itself needs to gracefully handle these errors. Usually, a
|
|
Packit |
58578d |
failing action (e.g. x()) then posts an appropriate error event and sets a
|
|
Packit |
58578d |
global error variable to true. Every following action (e.g. y()) first has
|
|
Packit |
58578d |
to check the error variable before doing anything. After all actions have
|
|
Packit |
58578d |
completed (by doing nothing!), the previously posted error event has to be
|
|
Packit |
58578d |
processed what leads to the execution of the remedy action. Please note
|
|
Packit |
58578d |
that it is not sufficient to simply queue the error event as other events
|
|
Packit |
58578d |
could still be pending. Instead, the error event has absolute priority and
|
|
Packit |
58578d |
has to be dealt with immediately. There are slightly less cumbersome
|
|
Packit |
58578d |
approaches to FSM error handling but these usually necessitate a change of
|
|
Packit |
58578d |
the statechart layout and thus obscure the normal behavior. No matter what
|
|
Packit |
58578d |
approach is used, programmers are normally forced to write a lot of code
|
|
Packit |
58578d |
that deals with errors and most of that code is not devoted to error
|
|
Packit |
58578d |
handling but to error propagation.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Error handling support in Boost.Statechart
|
|
Packit |
58578d |
|
|
Packit |
58578d |
C++ exceptions may be propagated from any action to signal a failure.
|
|
Packit |
58578d |
Depending on how the state machine is configured, such an exception is
|
|
Packit |
58578d |
either immediately propagated to the state machine client or caught and
|
|
Packit |
58578d |
converted into a special event that is dispatched immediately. For more
|
|
Packit |
58578d |
information see the Exception
|
|
Packit |
58578d |
handling chapter in the Tutorial.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Two stage exit
|
|
Packit |
58578d |
|
|
Packit |
58578d |
An exit action can be implemented by adding a destructor to a state. Due
|
|
Packit |
58578d |
to the nature of destructors, there are two disadvantages to this
|
|
Packit |
58578d |
approach:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Since C++ destructors should virtually never throw, one cannot simply
|
|
Packit |
58578d |
propagate an exception from an exit action as one does when any of the
|
|
Packit |
58578d |
other actions fails
|
|
Packit |
58578d |
|
|
Packit |
58578d |
When a state_machine<> object is destructed then
|
|
Packit |
58578d |
all currently active states are inevitably also destructed. That is,
|
|
Packit |
58578d |
state machine termination is tied to the destruction of the state machine
|
|
Packit |
58578d |
object
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
In my experience, neither of the above points is usually problem in
|
|
Packit |
58578d |
practice since ...
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
exit actions cannot often fail. If they can, such a failure is
|
|
Packit |
58578d |
usually either
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
not of interest to the outside world, i.e. the failure can simply
|
|
Packit |
58578d |
be ignored
|
|
Packit |
58578d |
|
|
Packit |
58578d |
so severe, that the application needs to be terminated anyway. In
|
|
Packit |
58578d |
such a situation stack unwind is almost never desirable and the
|
|
Packit |
58578d |
failure is better signaled through other mechanisms (e.g.
|
|
Packit |
58578d |
abort())
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
to clean up properly, often exit actions must be executed when
|
|
Packit |
58578d |
a state machine object is destructed, even if it is destructed as a
|
|
Packit |
58578d |
result of a stack unwind
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
However, several people have put forward theoretical arguments and
|
|
Packit |
58578d |
real-world scenarios, which show that the exit action to destructor mapping
|
|
Packit |
58578d |
can be a problem and that workarounds are overly cumbersome. That's
|
|
Packit |
58578d |
why two stage exit is now
|
|
Packit |
58578d |
supported.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"AsynchronousStateMachines">Asynchronous state machines
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Requirements
|
|
Packit |
58578d |
|
|
Packit |
58578d |
For asynchronous state machines different applications have rather
|
|
Packit |
58578d |
varied requirements:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
In some applications each state machine needs to run in its own
|
|
Packit |
58578d |
thread, other applications are single-threaded and run all machines in
|
|
Packit |
58578d |
the same thread
|
|
Packit |
58578d |
|
|
Packit |
58578d |
For some applications a FIFO scheduler is perfect, others need
|
|
Packit |
58578d |
priority- or EDF-schedulers
|
|
Packit |
58578d |
|
|
Packit |
58578d |
For some applications the boost::thread library is just fine, others
|
|
Packit |
58578d |
might want to use another threading library, yet other applications run
|
|
Packit |
58578d |
on OS-less platforms where ISRs are the only mode of (apparently)
|
|
Packit |
58578d |
concurrent execution
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Out of the box behavior
|
|
Packit |
58578d |
|
|
Packit |
58578d |
By default, asynchronous_state_machine<> subtype
|
|
Packit |
58578d |
objects are serviced by a fifo_scheduler<> object.
|
|
Packit |
58578d |
fifo_scheduler<> does not lock or wait in
|
|
Packit |
58578d |
single-threaded applications and uses boost::thread primitives to do so in
|
|
Packit |
58578d |
multi-threaded programs. Moreover, a fifo_scheduler<>
|
|
Packit |
58578d |
object can service an arbitrary number of
|
|
Packit |
58578d |
asynchronous_state_machine<> subtype objects. Under the
|
|
Packit |
58578d |
hood, fifo_scheduler<> is just a thin wrapper around an
|
|
Packit |
58578d |
object of its FifoWorker template parameter (which manages the
|
|
Packit |
58578d |
queue and ensures thread safety) and a
|
|
Packit |
58578d |
processor_container<> (which manages the lifetime of the
|
|
Packit |
58578d |
state machines).
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The UML standard mandates that an event not triggering a reaction in a
|
|
Packit |
58578d |
state machine should be silently discarded. Since a
|
|
Packit |
58578d |
fifo_scheduler<> object is itself also a state machine,
|
|
Packit |
58578d |
events destined to no longer existing
|
|
Packit |
58578d |
asynchronous_state_machine<> subtype objects are also
|
|
Packit |
58578d |
silently discarded. This is enabled by the fact that
|
|
Packit |
58578d |
asynchronous_state_machine<> subtype objects cannot be
|
|
Packit |
58578d |
constructed or destructed directly. Instead, this must be done through
|
|
Packit |
58578d |
fifo_scheduler<>::create_processor<>() and
|
|
Packit |
58578d |
fifo_scheduler<>::destroy_processor()
|
|
Packit |
58578d |
(processor refers to the fact that
|
|
Packit |
58578d |
fifo_scheduler<> can only host
|
|
Packit |
58578d |
event_processor<> subtype objects;
|
|
Packit |
58578d |
asynchronous_state_machine<> is just one way to
|
|
Packit |
58578d |
implement such a processor). Moreover,
|
|
Packit |
58578d |
create_processor<>() only returns a
|
|
Packit |
58578d |
processor_handle object. This must henceforth be used to
|
|
Packit |
58578d |
initiate, queue events for, terminate and destroy the state machine through
|
|
Packit |
58578d |
the scheduler.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Customization
|
|
Packit |
58578d |
|
|
Packit |
58578d |
If a user needs to customize the scheduler behavior she can do so by
|
|
Packit |
58578d |
instantiating fifo_scheduler<> with her own class
|
|
Packit |
58578d |
modeling the FifoWorker concept. I considered a much more
|
|
Packit |
58578d |
generic design where locking and waiting is implemented in a policy but I
|
|
Packit |
58578d |
have so far failed to come up with a clean and simple interface for it.
|
|
Packit |
58578d |
Especially the waiting is a bit difficult to model as some platforms have
|
|
Packit |
58578d |
condition variables, others have events and yet others don't have any
|
|
Packit |
58578d |
notion of waiting whatsoever (they instead loop until a new event arrives,
|
|
Packit |
58578d |
presumably via an ISR). Given the relatively few lines of code required to
|
|
Packit |
58578d |
implement a custom FifoWorker type and the fact that almost
|
|
Packit |
58578d |
all applications will implement at most one such class, it does not seem to
|
|
Packit |
58578d |
be worthwhile anyway. Applications requiring a less or more sophisticated
|
|
Packit |
58578d |
event processor lifetime management can customize the behavior at a more
|
|
Packit |
58578d |
coarse level, by using a custom Scheduler type. This is
|
|
Packit |
58578d |
currently also true for applications requiring non-FIFO queuing schemes.
|
|
Packit |
58578d |
However, Boost.Statechart will probably provide a
|
|
Packit |
58578d |
priority_scheduler in the future so that custom schedulers
|
|
Packit |
58578d |
need to be implemented only in rare cases.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"MemberFunctionsVsFunctionObjects">User actions: Member functions vs.
|
|
Packit |
58578d |
function objects
|
|
Packit |
58578d |
|
|
Packit |
58578d |
All user-supplied functions (react member functions,
|
|
Packit |
58578d |
entry-, exit- and transition-actions) must be class members. The reasons
|
|
Packit |
58578d |
for this are as follows:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The concept of state-local storage mandates that state-entry and
|
|
Packit |
58578d |
state-exit actions are implemented as members
|
|
Packit |
58578d |
|
|
Packit |
58578d |
react member functions and transition actions often
|
|
Packit |
58578d |
access state-local data. So, it is most natural to implement these
|
|
Packit |
58578d |
functions as members of the class the data of which the functions will
|
|
Packit |
58578d |
operate on anyway
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Junction points
|
|
Packit |
58578d |
|
|
Packit |
58578d |
UML junction points are not supported because arbitrarily complex guard
|
|
Packit |
58578d |
expressions can easily be implemented with
|
|
Packit |
58578d |
custom_reaction<> s.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Dynamic choice points
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Currently there is no direct support for this UML element because its
|
|
Packit |
58578d |
behavior can often be implemented with
|
|
Packit |
58578d |
custom_reaction<> s. In rare cases this is not possible,
|
|
Packit |
58578d |
namely when a choice point happens to be the initial state. Then, the
|
|
Packit |
58578d |
behavior can easily be implemented as follows:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
struct make_choice : sc::event< make_choice > {};
|
|
Packit |
58578d |
|
|
Packit |
58578d |
// universal choice point base class template
|
|
Packit |
58578d |
template< class MostDerived, class Context >
|
|
Packit |
58578d |
struct choice_point : sc::state< MostDerived, Context >
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
typedef sc::state< MostDerived, Context > base_type;
|
|
Packit |
58578d |
typedef typename base_type::my_context my_context;
|
|
Packit |
58578d |
typedef choice_point my_base;
|
|
Packit |
58578d |
|
|
Packit |
58578d |
choice_point( my_context ctx ) : base_type( ctx )
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
this->post_event( boost::intrusive_ptr< make_choice >(
|
|
Packit |
58578d |
new make_choice() ) );
|
|
Packit |
58578d |
}
|
|
Packit |
58578d |
};
|
|
Packit |
58578d |
|
|
Packit |
58578d |
// ...
|
|
Packit |
58578d |
|
|
Packit |
58578d |
struct MyChoicePoint;
|
|
Packit |
58578d |
struct Machine : sc::state_machine< Machine, MyChoicePoint > {};
|
|
Packit |
58578d |
|
|
Packit |
58578d |
struct Dest1 : sc::simple_state< Dest1, Machine > {};
|
|
Packit |
58578d |
struct Dest2 : sc::simple_state< Dest2, Machine > {};
|
|
Packit |
58578d |
struct Dest3 : sc::simple_state< Dest3, Machine > {};
|
|
Packit |
58578d |
|
|
Packit |
58578d |
struct MyChoicePoint : choice_point< MyChoicePoint, Machine >
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
MyChoicePoint( my_context ctx ) : my_base( ctx ) {}
|
|
Packit |
58578d |
|
|
Packit |
58578d |
sc::result react( const make_choice & )
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
if ( /* ... */ )
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
return transit< Dest1 >();
|
|
Packit |
58578d |
}
|
|
Packit |
58578d |
else if ( /* ... */ )
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
return transit< Dest2 >();
|
|
Packit |
58578d |
}
|
|
Packit |
58578d |
else
|
|
Packit |
58578d |
{
|
|
Packit |
58578d |
return transit< Dest3 >();
|
|
Packit |
58578d |
}
|
|
Packit |
58578d |
}
|
|
Packit |
58578d |
};
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
choice_point<> is not currently part of
|
|
Packit |
58578d |
Boost.Statechart, mainly because I fear that beginners could use it in
|
|
Packit |
58578d |
places where they would be better off with
|
|
Packit |
58578d |
custom_reaction<> . If the demand is high enough I will
|
|
Packit |
58578d |
add it to the library.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Deep history of orthogonal regions
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Deep history of states with orthogonal regions is currently not
|
|
Packit |
58578d |
supported:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
border="0" width="331" height="346">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Attempts to implement this statechart will lead to a compile-time error
|
|
Packit |
58578d |
because B has orthogonal regions and its direct or indirect outer state
|
|
Packit |
58578d |
contains a deep history pseudo state. In other words, a state containing a
|
|
Packit |
58578d |
deep history pseudo state must not have any direct or indirect inner states
|
|
Packit |
58578d |
which themselves have orthogonal regions. This limitation stems from the
|
|
Packit |
58578d |
fact that full deep history support would be more complicated to implement
|
|
Packit |
58578d |
and would consume more resources than the currently implemented limited
|
|
Packit |
58578d |
deep history support. Moreover, full deep history behavior can easily be
|
|
Packit |
58578d |
implemented with shallow history:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
border="0" width="332" height="347">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Of course, this only works if C, D, E or any of their direct or indirect
|
|
Packit |
58578d |
inner states do not have orthogonal regions. If not so then this pattern
|
|
Packit |
58578d |
has to be applied recursively.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Synchronization (join and fork) bars
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
height="301">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Synchronization bars are not supported, that is, a transition always
|
|
Packit |
58578d |
originates at exactly one state and always ends at exactly one state. Join
|
|
Packit |
58578d |
bars are sometimes useful but their behavior can easily be emulated with
|
|
Packit |
58578d |
guards. The support of fork bars would make the implementation much
|
|
Packit |
58578d |
more complex and they are only needed rarely.
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Event dispatch to orthogonal regions
|
|
Packit |
58578d |
|
|
Packit |
58578d |
The Boost.Statechart event dispatch algorithm is different to the one
|
|
Packit |
58578d |
specified in
|
|
Packit |
58578d |
"http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf">David
|
|
Packit |
58578d |
Harel's original paper and in the
|
|
Packit |
58578d |
"http://www.omg.org/cgi-bin/doc?formal/03-03-01">UML standard. Both
|
|
Packit |
58578d |
mandate that each event is dispatched to all orthogonal regions of a state
|
|
Packit |
58578d |
machine. Example:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
height="211">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Here the Harel/UML dispatch algorithm specifies that the machine must
|
|
Packit |
58578d |
transition from (B,D) to (C,E) when an EvX event is processed. Because of
|
|
Packit |
58578d |
the subtleties that Harel describes in chapter 7 of
|
|
Packit |
58578d |
"http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf">his
|
|
Packit |
58578d |
paper, an implementation of this algorithm is not only quite complex
|
|
Packit |
58578d |
but also much slower than the simplified version employed by
|
|
Packit |
58578d |
Boost.Statechart, which stops searching for
|
|
Packit |
58578d |
"definitions.html#Reaction">reactions as soon as it has found one
|
|
Packit |
58578d |
suitable for the current event. That is, had the example been implemented
|
|
Packit |
58578d |
with this library, the machine would have transitioned
|
|
Packit |
58578d |
non-deterministically from (B,D) to either (C,D) or (B,E). This version was
|
|
Packit |
58578d |
chosen because, in my experience, in real-world machines different
|
|
Packit |
58578d |
orthogonal regions often do not specify transitions for the same events.
|
|
Packit |
58578d |
For the rare cases when they do, the UML behavior can easily be emulated as
|
|
Packit |
58578d |
follows:
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
width="466" height="226">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Transitions across orthogonal regions
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
border="0" width="226" height="271">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Transitions across orthogonal regions are currently flagged with an
|
|
Packit |
58578d |
error at compile time (the UML specifications explicitly allow them while
|
|
Packit |
58578d |
Harel does not mention them at all). I decided to not support them because
|
|
Packit |
58578d |
I have erroneously tried to implement such a transition several times but
|
|
Packit |
58578d |
have never come across a situation where it would make any sense. If you
|
|
Packit |
58578d |
need to make such transitions, please do let me know!
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
|
|
Packit |
58578d |
"../../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
|
|
Packit |
58578d |
height="31" width="88">
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Revised
|
|
Packit |
58578d |
03 December, 2006
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Copyright © 2003-2006
|
|
Packit |
58578d |
Andreas Huber Dönni
|
|
Packit |
58578d |
|
|
Packit |
58578d |
Distributed under the Boost Software License, Version 1.0. (See
|
|
Packit |
58578d |
accompanying file LICENSE_1_0.txt or
|
|
Packit |
58578d |
copy at
|
|
Packit |
58578d |
"http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt)
|
|
Packit |
58578d |
</body>
|
|
Packit |
58578d |
</html>
|