]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
2 | ||
3 | <html> | |
4 | <head> | |
5 | <meta http-equiv="Content-Language" content="en-us"> | |
6 | <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> | |
7 | <meta name="GENERATOR" content="Microsoft FrontPage 6.0"> | |
8 | <meta name="ProgId" content="FrontPage.Editor.Document"> | |
9 | <link rel="stylesheet" type="text/css" href="../../../boost.css"> | |
10 | ||
11 | <title>The Boost Statechart Library - Rationale</title> | |
12 | </head> | |
13 | ||
14 | <body link="#0000FF" vlink="#800080"> | |
15 | <table border="0" cellpadding="7" cellspacing="0" width="100%" summary= | |
16 | "header"> | |
17 | <tr> | |
18 | <td valign="top" width="300"> | |
19 | <h3><a href="../../../index.htm"><img alt="C++ Boost" src= | |
20 | "../../../boost.png" border="0" width="277" height="86"></a></h3> | |
21 | </td> | |
22 | ||
23 | <td valign="top"> | |
24 | <h1 align="center">The Boost Statechart Library</h1> | |
25 | ||
26 | <h2 align="center">Rationale</h2> | |
27 | </td> | |
28 | </tr> | |
29 | </table> | |
30 | <hr> | |
31 | ||
32 | <dl class="index"> | |
33 | <dt><a href="#Introduction">Introduction</a></dt> | |
34 | ||
35 | <dt><a href="#WhyYetAnotherStateMachineFramework">Why yet another state | |
36 | machine framework</a></dt> | |
37 | ||
38 | <dt><a href="#StateLocalStorage">State-local storage</a></dt> | |
39 | ||
40 | <dt><a href="#DynamicConfigurability">Dynamic configurability</a></dt> | |
41 | ||
42 | <dt><a href="#ErrorHandling">Error handling</a></dt> | |
43 | ||
44 | <dt><a href="#AsynchronousStateMachines">Asynchronous state | |
45 | machines</a></dt> | |
46 | ||
47 | <dt><a href="#MemberFunctionsVsFunctionObjects">User actions: Member | |
48 | functions vs. function objects</a></dt> | |
49 | ||
50 | <dt><a href="#Limitations">Limitations</a></dt> | |
51 | </dl> | |
52 | ||
53 | <h2><a name="Introduction" id="Introduction">Introduction</a></h2> | |
54 | ||
55 | <p>Most of the design decisions made during the development of this library | |
56 | are the result of the following requirements.</p> | |
57 | ||
58 | <p>Boost.Statechart should ...</p> | |
59 | ||
60 | <ol> | |
61 | <li>be fully type-safe. Whenever possible, type mismatches should be | |
62 | flagged with an error at compile-time</li> | |
63 | ||
64 | <li>not require the use of a code generator. A lot of the existing FSM | |
65 | solutions force the developer to design the state machine either | |
66 | graphically or in a specialized language. All or part of the code is then | |
67 | generated</li> | |
68 | ||
69 | <li>allow for easy transformation of a UML statechart (defined in | |
70 | <a href="http://www.omg.org/cgi-bin/doc?formal/03-03-01">http://www.omg.org/cgi-bin/doc?formal/03-03-01</a>) | |
71 | into a working state machine. Vice versa, an existing C++ | |
72 | implementation of a state machine should be fairly trivial to transform | |
73 | into a UML statechart. Specifically, the following state machine | |
74 | features should be supported: | |
75 | ||
76 | <ul> | |
77 | <li>Hierarchical (composite, nested) states</li> | |
78 | ||
79 | <li>Orthogonal (concurrent) states</li> | |
80 | ||
81 | <li>Entry-, exit- and transition-actions</li> | |
82 | ||
83 | <li>Guards</li> | |
84 | ||
85 | <li>Shallow/deep history</li> | |
86 | </ul> | |
87 | </li> | |
88 | ||
89 | <li>produce a customizable reaction when a C++ exception is propagated | |
90 | from user code</li> | |
91 | ||
92 | <li>support synchronous and asynchronous state machines and leave it to | |
93 | the user which thread an asynchronous state machine will run in. Users | |
94 | should also be able to use the threading library of their choice</li> | |
95 | ||
96 | <li>support the development of arbitrarily large and complex state | |
97 | machines. Multiple developers should be able to work on the same state | |
98 | machine simultaneously</li> | |
99 | ||
100 | <li>allow the user to customize all resource management so that the | |
101 | library could be used for applications with hard real-time | |
102 | requirements</li> | |
103 | ||
104 | <li>enforce as much as possible at compile time. Specifically, invalid | |
105 | state machines should not compile</li> | |
106 | ||
107 | <li>offer reasonable performance for a wide range of applications</li> | |
108 | </ol> | |
109 | ||
110 | <h2><a name="WhyYetAnotherStateMachineFramework" id= | |
111 | "WhyYetAnotherStateMachineFramework">Why yet another state machine | |
112 | framework?</a></h2> | |
113 | ||
114 | <p>Before I started to develop this library I had a look at the following | |
115 | frameworks:</p> | |
116 | ||
117 | <ul> | |
118 | <li>The framework accompanying the book "Practical Statecharts in C/C++" | |
119 | by Miro Samek, CMP Books, ISBN: 1-57820-110-1<br> | |
120 | <a href= | |
121 | "http://www.quantum-leaps.com">http://www.quantum-leaps.com<br></a> Fails | |
122 | to satisfy at least the requirements 1, 3, 4, 6, 8.</li> | |
123 | ||
124 | <li>The framework accompanying "Rhapsody in C++" by ILogix (a code | |
125 | generator solution)<br> | |
126 | <a href= | |
127 | "http://www.ilogix.com/sublevel.aspx?id=53">http://www.ilogix.com/sublevel.aspx?id=53<br> | |
128 | </a> This might look like comparing apples with oranges. However, there | |
129 | is no inherent reason why a code generator couldn't produce code that can | |
130 | easily be understood and modified by humans. Fails to satisfy at least | |
131 | the requirements 2, 4, 5, 6, 8 (there is quite a bit of error checking | |
132 | before code generation, though).</li> | |
133 | ||
134 | <li>The framework accompanying the article "State Machine Design in | |
135 | C++"<br> | |
136 | <a href= | |
137 | "http://www.ddj.com/184401236?pgno=1">http://www.ddj.com/184401236?pgno=1<br> | |
138 | </a> Fails to satisfy at least the requirements 1, 3, 4, 5 (there is no | |
139 | direct threading support), 6, 8.</li> | |
140 | </ul> | |
141 | ||
142 | <p>I believe Boost.Statechart satisfies all requirements.</p> | |
143 | ||
144 | <h2><a name="StateLocalStorage" id="StateLocalStorage">State-local | |
145 | storage</a></h2> | |
146 | ||
147 | <p>This not yet widely known state machine feature is enabled by the fact | |
148 | that every state is represented by a class. Upon state-entry, an object of | |
149 | the class is constructed and the object is later destructed when the state | |
150 | machine exits the state. Any data that is useful only as long as the | |
151 | machine resides in the state can (and should) thus be a member of the | |
152 | state. This feature paired with the ability to spread a state machine over | |
153 | several translation units makes possible virtually unlimited | |
154 | scalability. </p> | |
155 | ||
156 | <p>In most existing FSM frameworks the whole state machine runs in one | |
157 | environment (context). That is, all resource handles and variables local to | |
158 | the state machine are stored in one place (normally as members of the class | |
159 | that also derives from some state machine base class). For large state | |
160 | machines this often leads to the class having a huge number of data members | |
161 | most of which are needed only briefly in a tiny part of the machine. The | |
162 | state machine class therefore often becomes a change hotspot what leads to | |
163 | frequent recompilations of the whole state machine.</p> | |
164 | ||
165 | <p>The FAQ item "<a href="faq.html#StateLocalStorage">What's so cool about | |
166 | state-local storage?</a>" further explains this by comparing the tutorial | |
167 | StopWatch to a behaviorally equivalent version that does not use | |
168 | state-local storage.</p> | |
169 | ||
170 | <h2><a name="DynamicConfigurability" id="DynamicConfigurability">Dynamic | |
171 | configurability</a></h2> | |
172 | ||
173 | <h3>Two types of state machine frameworks</h3> | |
174 | ||
175 | <ul> | |
176 | <li>A state machine framework supports dynamic configurability if the | |
177 | whole layout of a state machine can be defined at runtime ("layout" | |
178 | refers to states and transitions, actions are still specified with normal | |
179 | C++ code). That is, data only available at runtime can be used to build | |
180 | arbitrarily large machines. See "A Multiple Substring Search Algorithm" | |
181 | by Moishe Halibard and Moshe Rubin in June 2002 issue of CUJ for a good | |
182 | example (unfortunately not available online).</li> | |
183 | ||
184 | <li>On the other side are state machine frameworks which require the | |
185 | layout to be specified at compile time</li> | |
186 | </ul> | |
187 | ||
188 | <p>State machines that are built at runtime almost always get away with a | |
189 | simple state model (no hierarchical states, no orthogonal states, no entry | |
190 | and exit actions, no history) because the layout is very often <b>computed | |
191 | by an algorithm</b>. On the other hand, machine layouts that are fixed at | |
192 | compile time are almost always designed by humans, who frequently need/want | |
193 | a sophisticated state model in order to keep the complexity at acceptable | |
194 | levels. Dynamically configurable FSM frameworks are therefore often | |
195 | optimized for simple flat machines while incarnations of the static variant | |
196 | tend to offer more features for abstraction.</p> | |
197 | ||
198 | <p>However, fully-featured dynamic FSM libraries do exist. So, the question | |
199 | is:</p> | |
200 | ||
201 | <h3>Why not use a dynamically configurable FSM library for all state | |
202 | machines?</h3> | |
203 | ||
204 | <p>One might argue that a dynamically configurable FSM framework is all one | |
205 | ever needs because <b>any</b> state machine can be implemented with it. | |
206 | However, due to its nature such a framework has a number of disadvantages | |
207 | when used to implement static machines:</p> | |
208 | ||
209 | <ul> | |
210 | <li>No compile-time optimizations and validations can be made. For | |
211 | example, Boost.Statechart determines the <a href= | |
212 | "definitions.html#InnermostCommonContext">innermost common context</a> of | |
213 | the transition-source and destination state at compile time. Moreover, | |
214 | compile time checks ensure that the state machine is valid (e.g. that | |
215 | there are no transitions between orthogonal states).</li> | |
216 | ||
217 | <li>Double dispatch must inevitably be implemented with some kind of a | |
218 | table. As argued under <a href="performance.html#DoubleDispatch">Double | |
219 | dispatch</a>, this scales badly.</li> | |
220 | ||
221 | <li>To warrant fast table lookup, states and events must be represented | |
222 | with an integer. To keep the table as small as possible, the numbering | |
223 | should be continuous, e.g. if there are ten states, it's best to use the | |
224 | ids 0-9. To ensure continuity of ids, all states are best defined in the | |
225 | same header file. The same applies to events. Again, this does not | |
226 | scale.</li> | |
227 | ||
228 | <li>Because events carrying parameters are not represented by a type, | |
229 | some sort of a generic event with a property map must be used and | |
230 | type-safety is enforced at runtime rather than at compile time.</li> | |
231 | </ul> | |
232 | ||
233 | <p>It is for these reasons, that Boost.Statechart was built from ground up | |
234 | to <b>not</b> support dynamic configurability. However, this does not mean | |
235 | that it's impossible to dynamically shape a machine implemented with this | |
236 | library. For example, guards can be used to make different transitions | |
237 | depending on input only available at runtime. However, such layout changes | |
238 | will always be limited to what can be foreseen before compilation. A | |
239 | somewhat related library, the boost::spirit parser framework, allows for | |
240 | roughly the same runtime configurability.</p> | |
241 | ||
242 | <h2><a name="ErrorHandling" id="ErrorHandling">Error handling</a></h2> | |
243 | ||
244 | <p>There is not a single word about error handling in the UML state machine | |
245 | semantics specifications. Moreover, most existing FSM solutions also seem | |
246 | to ignore the issue. </p> | |
247 | ||
248 | <h3>Why an FSM library should support error handling</h3> | |
249 | ||
250 | <p>Consider the following state configuration:</p> | |
251 | ||
252 | <p><img alt="A" src="A.gif" border="0" width="230" height="170"></p> | |
253 | ||
254 | <p>Both states define entry actions (x() and y()). Whenever state A becomes | |
255 | active, a call to x() will immediately be followed by a call to y(). y() | |
256 | could depend on the side-effects of x(). Therefore, executing y() does not | |
257 | make sense if x() fails. This is not an esoteric corner case but happens in | |
258 | every-day state machines all the time. For example, x() could acquire | |
259 | memory the contents of which is later modified by y(). There is a different | |
260 | but in terms of error handling equally critical situation in the Tutorial | |
261 | under <a href= | |
262 | "tutorial.html#GettingStateInformationOutOfTheMachine">Getting state | |
263 | information out of the machine</a> when <code>Running::~Running()</code> | |
264 | accesses its outer state <code>Active</code>. Had the entry action of | |
265 | <code>Active</code> failed and had <code>Running</code> been entered anyway | |
266 | then <code>Running</code>'s exit action would have invoked undefined | |
267 | behavior. The error handling situation with outer and inner states | |
268 | resembles the one with base and derived classes: If a base class | |
269 | constructor fails (by throwing an exception) the construction is aborted, | |
270 | the derived class constructor is not called and the object never comes to | |
271 | life.<br> | |
272 | In most traditional FSM frameworks such an error situation is relatively | |
273 | easy to tackle <b>as long as the error can be propagated to the state | |
274 | machine client</b>. In this case a failed action simply propagates a C++ | |
275 | exception into the framework. The framework usually does not catch the | |
276 | exception so that the state machine client can handle it. Note that, after | |
277 | doing so, the client can no longer use the state machine object because it | |
278 | is either in an unknown state or the framework has already reset the state | |
279 | because of the exception (e.g. with a scope guard). That is, by their | |
280 | nature, state machines typically only offer basic exception safety.<br> | |
281 | However, error handling with traditional FSM frameworks becomes | |
282 | surprisingly cumbersome as soon as a lot of actions can fail and the state | |
283 | machine <b>itself</b> needs to gracefully handle these errors. Usually, a | |
284 | failing action (e.g. x()) then posts an appropriate error event and sets a | |
285 | global error variable to true. Every following action (e.g. y()) first has | |
286 | to check the error variable before doing anything. After all actions have | |
287 | completed (by doing nothing!), the previously posted error event has to be | |
288 | processed what leads to the execution of the remedy action. Please note | |
289 | that it is not sufficient to simply queue the error event as other events | |
290 | could still be pending. Instead, the error event has absolute priority and | |
291 | has to be dealt with immediately. There are slightly less cumbersome | |
292 | approaches to FSM error handling but these usually necessitate a change of | |
293 | the statechart layout and thus obscure the normal behavior. No matter what | |
294 | approach is used, programmers are normally forced to write a lot of code | |
295 | that deals with errors and most of that code is <b>not</b> devoted to error | |
296 | handling but to error propagation.</p> | |
297 | ||
298 | <h3>Error handling support in Boost.Statechart</h3> | |
299 | ||
300 | <p>C++ exceptions may be propagated from any action to signal a failure. | |
301 | Depending on how the state machine is configured, such an exception is | |
302 | either immediately propagated to the state machine client or caught and | |
303 | converted into a special event that is dispatched immediately. For more | |
304 | information see the <a href="tutorial.html#ExceptionHandling">Exception | |
305 | handling</a> chapter in the Tutorial.</p> | |
306 | ||
307 | <h3>Two stage exit</h3> | |
308 | ||
309 | <p>An exit action can be implemented by adding a destructor to a state. Due | |
310 | to the nature of destructors, there are two disadvantages to this | |
311 | approach:</p> | |
312 | ||
313 | <ul> | |
314 | <li>Since C++ destructors should virtually never throw, one cannot simply | |
315 | propagate an exception from an exit action as one does when any of the | |
316 | other actions fails</li> | |
317 | ||
318 | <li>When a <code>state_machine<></code> object is destructed then | |
319 | all currently active states are inevitably also destructed. That is, | |
320 | state machine termination is tied to the destruction of the state machine | |
321 | object</li> | |
322 | </ul> | |
323 | ||
324 | <p>In my experience, neither of the above points is usually problem in | |
325 | practice since ...</p> | |
326 | ||
327 | <ul> | |
328 | <li>exit actions cannot often fail. If they can, such a failure is | |
329 | usually either | |
330 | ||
331 | <ul> | |
332 | <li>not of interest to the outside world, i.e. the failure can simply | |
333 | be ignored</li> | |
334 | ||
335 | <li>so severe, that the application needs to be terminated anyway. In | |
336 | such a situation stack unwind is almost never desirable and the | |
337 | failure is better signaled through other mechanisms (e.g. | |
338 | abort())</li> | |
339 | </ul> | |
340 | </li> | |
341 | ||
342 | <li>to clean up properly, often exit actions <b>must</b> be executed when | |
343 | a state machine object is destructed, even if it is destructed as a | |
344 | result of a stack unwind</li> | |
345 | </ul> | |
346 | ||
347 | <p>However, several people have put forward theoretical arguments and | |
348 | real-world scenarios, which show that the exit action to destructor mapping | |
349 | <b>can</b> be a problem and that workarounds are overly cumbersome. That's | |
350 | why <a href="tutorial.html#TwoStageExit">two stage exit</a> is now | |
351 | supported.</p> | |
352 | ||
353 | <h2><a name="AsynchronousStateMachines" id= | |
354 | "AsynchronousStateMachines">Asynchronous state machines</a></h2> | |
355 | ||
356 | <h3>Requirements</h3> | |
357 | ||
358 | <p>For asynchronous state machines different applications have rather | |
359 | varied requirements:</p> | |
360 | ||
361 | <ol> | |
362 | <li>In some applications each state machine needs to run in its own | |
363 | thread, other applications are single-threaded and run all machines in | |
364 | the same thread</li> | |
365 | ||
366 | <li>For some applications a FIFO scheduler is perfect, others need | |
367 | priority- or EDF-schedulers</li> | |
368 | ||
369 | <li>For some applications the boost::thread library is just fine, others | |
370 | might want to use another threading library, yet other applications run | |
371 | on OS-less platforms where ISRs are the only mode of (apparently) | |
372 | concurrent execution</li> | |
373 | </ol> | |
374 | ||
375 | <h3>Out of the box behavior</h3> | |
376 | ||
377 | <p>By default, <code>asynchronous_state_machine<></code> subtype | |
378 | objects are serviced by a <code>fifo_scheduler<></code> object. | |
379 | <code>fifo_scheduler<></code> does not lock or wait in | |
380 | single-threaded applications and uses boost::thread primitives to do so in | |
381 | multi-threaded programs. Moreover, a <code>fifo_scheduler<></code> | |
382 | object can service an arbitrary number of | |
383 | <code>asynchronous_state_machine<></code> subtype objects. Under the | |
384 | hood, <code>fifo_scheduler<></code> is just a thin wrapper around an | |
385 | object of its <code>FifoWorker</code> template parameter (which manages the | |
386 | queue and ensures thread safety) and a | |
387 | <code>processor_container<></code> (which manages the lifetime of the | |
388 | state machines).</p> | |
389 | ||
390 | <p>The UML standard mandates that an event not triggering a reaction in a | |
391 | state machine should be silently discarded. Since a | |
392 | <code>fifo_scheduler<></code> object is itself also a state machine, | |
393 | events destined to no longer existing | |
394 | <code>asynchronous_state_machine<></code> subtype objects are also | |
395 | silently discarded. This is enabled by the fact that | |
396 | <code>asynchronous_state_machine<></code> subtype objects cannot be | |
397 | constructed or destructed directly. Instead, this must be done through | |
398 | <code>fifo_scheduler<>::create_processor<>()</code> and | |
399 | <code>fifo_scheduler<>::destroy_processor()</code> | |
400 | (<code>processor</code> refers to the fact that | |
401 | <code>fifo_scheduler<></code> can only host | |
402 | <code>event_processor<></code> subtype objects; | |
403 | <code>asynchronous_state_machine<></code> is just one way to | |
404 | implement such a processor). Moreover, | |
405 | <code>create_processor<>()</code> only returns a | |
406 | <code>processor_handle</code> object. This must henceforth be used to | |
407 | initiate, queue events for, terminate and destroy the state machine through | |
408 | the scheduler.</p> | |
409 | ||
410 | <h3>Customization</h3> | |
411 | ||
412 | <p>If a user needs to customize the scheduler behavior she can do so by | |
413 | instantiating <code>fifo_scheduler<></code> with her own class | |
414 | modeling the <code>FifoWorker</code> concept. I considered a much more | |
415 | generic design where locking and waiting is implemented in a policy but I | |
416 | have so far failed to come up with a clean and simple interface for it. | |
417 | Especially the waiting is a bit difficult to model as some platforms have | |
418 | condition variables, others have events and yet others don't have any | |
419 | notion of waiting whatsoever (they instead loop until a new event arrives, | |
420 | presumably via an ISR). Given the relatively few lines of code required to | |
421 | implement a custom <code>FifoWorker</code> type and the fact that almost | |
422 | all applications will implement at most one such class, it does not seem to | |
423 | be worthwhile anyway. Applications requiring a less or more sophisticated | |
424 | event processor lifetime management can customize the behavior at a more | |
425 | coarse level, by using a custom <code>Scheduler</code> type. This is | |
426 | currently also true for applications requiring non-FIFO queuing schemes. | |
427 | However, Boost.Statechart will probably provide a | |
428 | <code>priority_scheduler</code> in the future so that custom schedulers | |
429 | need to be implemented only in rare cases.</p> | |
430 | ||
431 | <h2><a name="MemberFunctionsVsFunctionObjects" id= | |
432 | "MemberFunctionsVsFunctionObjects">User actions: Member functions vs. | |
433 | function objects</a></h2> | |
434 | ||
435 | <p>All user-supplied functions (<code>react</code> member functions, | |
436 | entry-, exit- and transition-actions) must be class members. The reasons | |
437 | for this are as follows:</p> | |
438 | ||
439 | <ul> | |
440 | <li>The concept of state-local storage mandates that state-entry and | |
441 | state-exit actions are implemented as members</li> | |
442 | ||
443 | <li><code>react</code> member functions and transition actions often | |
444 | access state-local data. So, it is most natural to implement these | |
445 | functions as members of the class the data of which the functions will | |
446 | operate on anyway</li> | |
447 | </ul> | |
448 | ||
449 | <h2><a name="Limitations" id="Limitations">Limitations</a></h2> | |
450 | ||
451 | <h4>Junction points</h4> | |
452 | ||
453 | <p>UML junction points are not supported because arbitrarily complex guard | |
454 | expressions can easily be implemented with | |
455 | <code>custom_reaction<></code>s.</p> | |
456 | ||
457 | <h4>Dynamic choice points</h4> | |
458 | ||
459 | <p>Currently there is no direct support for this UML element because its | |
460 | behavior can often be implemented with | |
461 | <code>custom_reaction<></code>s. In rare cases this is not possible, | |
462 | namely when a choice point happens to be the initial state. Then, the | |
463 | behavior can easily be implemented as follows:</p> | |
464 | <pre> | |
465 | struct make_choice : sc::event< make_choice > {}; | |
466 | ||
467 | // universal choice point base class template | |
468 | template< class MostDerived, class Context > | |
469 | struct choice_point : sc::state< MostDerived, Context > | |
470 | { | |
471 | typedef sc::state< MostDerived, Context > base_type; | |
472 | typedef typename base_type::my_context my_context; | |
473 | typedef choice_point my_base; | |
474 | ||
475 | choice_point( my_context ctx ) : base_type( ctx ) | |
476 | { | |
477 | this->post_event( boost::intrusive_ptr< make_choice >( | |
478 | new make_choice() ) ); | |
479 | } | |
480 | }; | |
481 | ||
482 | // ... | |
483 | ||
484 | struct MyChoicePoint; | |
485 | struct Machine : sc::state_machine< Machine, MyChoicePoint > {}; | |
486 | ||
487 | struct Dest1 : sc::simple_state< Dest1, Machine > {}; | |
488 | struct Dest2 : sc::simple_state< Dest2, Machine > {}; | |
489 | struct Dest3 : sc::simple_state< Dest3, Machine > {}; | |
490 | ||
491 | struct MyChoicePoint : choice_point< MyChoicePoint, Machine > | |
492 | { | |
493 | MyChoicePoint( my_context ctx ) : my_base( ctx ) {} | |
494 | ||
495 | sc::result react( const make_choice & ) | |
496 | { | |
497 | if ( /* ... */ ) | |
498 | { | |
499 | return transit< Dest1 >(); | |
500 | } | |
501 | else if ( /* ... */ ) | |
502 | { | |
503 | return transit< Dest2 >(); | |
504 | } | |
505 | else | |
506 | { | |
507 | return transit< Dest3 >(); | |
508 | } | |
509 | } | |
510 | }; | |
511 | </pre> | |
512 | ||
513 | <p><code>choice_point<></code> is not currently part of | |
514 | Boost.Statechart, mainly because I fear that beginners could use it in | |
515 | places where they would be better off with | |
516 | <code>custom_reaction<></code>. If the demand is high enough I will | |
517 | add it to the library.</p> | |
518 | ||
519 | <h4>Deep history of orthogonal regions</h4> | |
520 | ||
521 | <p>Deep history of states with orthogonal regions is currently not | |
522 | supported:</p> | |
523 | ||
524 | <p><img alt="DeepHistoryLimitation1" src="DeepHistoryLimitation1.gif" | |
525 | border="0" width="331" height="346"></p> | |
526 | ||
527 | <p>Attempts to implement this statechart will lead to a compile-time error | |
528 | because B has orthogonal regions and its direct or indirect outer state | |
529 | contains a deep history pseudo state. In other words, a state containing a | |
530 | deep history pseudo state must not have any direct or indirect inner states | |
531 | which themselves have orthogonal regions. This limitation stems from the | |
532 | fact that full deep history support would be more complicated to implement | |
533 | and would consume more resources than the currently implemented limited | |
534 | deep history support. Moreover, full deep history behavior can easily be | |
535 | implemented with shallow history:</p> | |
536 | ||
537 | <p><img alt="DeepHistoryLimitation2" src="DeepHistoryLimitation2.gif" | |
538 | border="0" width="332" height="347"></p> | |
539 | ||
540 | <p>Of course, this only works if C, D, E or any of their direct or indirect | |
541 | inner states do not have orthogonal regions. If not so then this pattern | |
542 | has to be applied recursively.</p> | |
543 | ||
544 | <h4>Synchronization (join and fork) bars</h4> | |
545 | ||
546 | <p><img alt="JoinAndFork" src="JoinAndFork.gif" border="0" width="541" | |
547 | height="301"></p> | |
548 | ||
549 | <p>Synchronization bars are not supported, that is, a transition always | |
550 | originates at exactly one state and always ends at exactly one state. Join | |
551 | bars are sometimes useful but their behavior can easily be emulated with | |
552 | guards. The support of fork bars would make the implementation <b>much</b> | |
553 | more complex and they are only needed rarely.</p> | |
554 | ||
555 | <h4>Event dispatch to orthogonal regions</h4> | |
556 | ||
557 | <p>The Boost.Statechart event dispatch algorithm is different to the one | |
558 | specified in <a href= | |
559 | "http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf">David | |
560 | Harel's original paper</a> and in the <a href= | |
561 | "http://www.omg.org/cgi-bin/doc?formal/03-03-01">UML standard</a>. Both | |
562 | mandate that each event is dispatched to all orthogonal regions of a state | |
563 | machine. Example:</p> | |
564 | ||
565 | <p><img alt="EventDispatch" src="EventDispatch.gif" border="0" width="436" | |
566 | height="211"></p> | |
567 | ||
568 | <p>Here the Harel/UML dispatch algorithm specifies that the machine must | |
569 | transition from (B,D) to (C,E) when an EvX event is processed. Because of | |
570 | the subtleties that Harel describes in chapter 7 of <a href= | |
571 | "http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf">his | |
572 | paper</a>, an implementation of this algorithm is not only quite complex | |
573 | but also much slower than the simplified version employed by | |
574 | Boost.Statechart, which stops searching for <a href= | |
575 | "definitions.html#Reaction">reactions</a> as soon as it has found one | |
576 | suitable for the current event. That is, had the example been implemented | |
577 | with this library, the machine would have transitioned | |
578 | non-deterministically from (B,D) to either (C,D) or (B,E). This version was | |
579 | chosen because, in my experience, in real-world machines different | |
580 | orthogonal regions often do not specify transitions for the same events. | |
581 | For the rare cases when they do, the UML behavior can easily be emulated as | |
582 | follows:</p> | |
583 | ||
584 | <p><img alt="SimpleEventDispatch" src="SimpleEventDispatch.gif" border="0" | |
585 | width="466" height="226"></p> | |
586 | ||
587 | <h4>Transitions across orthogonal regions</h4> | |
588 | ||
589 | <p><img alt="TransAcrossOrthRegions" src="TransAcrossOrthRegions.gif" | |
590 | border="0" width="226" height="271"></p> | |
591 | ||
592 | <p>Transitions across orthogonal regions are currently flagged with an | |
593 | error at compile time (the UML specifications explicitly allow them while | |
594 | Harel does not mention them at all). I decided to not support them because | |
595 | I have erroneously tried to implement such a transition several times but | |
596 | have never come across a situation where it would make any sense. If you | |
597 | need to make such transitions, please do let me know!</p> | |
598 | <hr> | |
599 | ||
600 | <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= | |
601 | "../../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional" | |
602 | height="31" width="88"></a></p> | |
603 | ||
604 | <p>Revised | |
605 | <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->03 December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38512" --></p> | |
606 | ||
607 | <p><i>Copyright © 2003-<!--webbot bot="Timestamp" s-type="EDITED" s-format="%Y" startspan -->2006<!--webbot bot="Timestamp" endspan i-checksum="770" --> | |
608 | <a href="contact.html">Andreas Huber Dönni</a></i></p> | |
609 | ||
610 | <p><i>Distributed under the Boost Software License, Version 1.0. (See | |
611 | accompanying file <a href="../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or | |
612 | copy at <a href= | |
613 | "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> | |
614 | </body> | |
615 | </html> |