C++ Boost

Boost Statechart 庫

Rationale 原理

Introduction 簡介
Why yet another state machine framework 為何還要另一個狀態機框架
State-local storage 狀態局部存儲
Dynamic configurability 動態配置能力
Error handling 錯誤處理
Asynchronous state machines 異步狀態機
User actions: Member functions vs. function objects 用戶的動作:成員函數 vs. 函數對像
Limitations 局限性

Introduction 簡介

Most of the design decisions made during the development of this library are the result of the following requirements.

Boost.Statechart should ...
Boost.Statechart 應該 ...

  1. be fully type-safe. Whenever possible, type mismatches should be flagged with an error at compile-time
    是完全類型安全的。只要有可能,類型的錯配就應當被標 識為編譯期錯誤
  2. not require the use of a code generator. A lot of the existing FSM solutions force the developer to design the state machine either graphically or in a specialized language. All or part of the code is then generated
    無需使用代碼生成 器。大量已有的FSM解決方案都強迫開發人員以圖形化的方式或特定語言的方式來設計狀態機。然後生成全部或部分代碼
  3. allow for easy transformation of a UML statechart (defined in http://www.omg.org/cgi-bin/doc?formal/03-03-01) into a working state machine. Vice versa, an existing C++ implementation of a state machine should be fairly trivial to transform into a UML statechart. Specifically, the following state machine features should be supported:
    可以很容易地從一個UML狀態圖(在 http://www.omg.org/cgi-bin/doc?formal/03-03-01 中定義)轉化為可工作的狀態機。反之亦然,一個已有狀態機的C++實現也可以相當簡單地轉化為一個UML狀態圖。特別是,可以支持以下狀態機特性:
  4. produce a customizable reaction when a C++ exception is propagated from user code
  5. support synchronous and asynchronous state machines and leave it to the user which thread an asynchronous state machine will run in. Users should also be able to use the threading library of their choice
  6. support the development of arbitrarily large and complex state machines. Multiple developers should be able to work on the same state machine simultaneously
  7. allow the user to customize all resource management so that the library could be used for applications with hard real-time requirements
  8. enforce as much as possible at compile time. Specifically, invalid state machines should not compile
  9. offer reasonable performance for a wide range of applications

Why yet another state machine framework? 為何還要另一個狀態機框架?

Before I started to develop this library I had a look at the following frameworks:

I believe Boost.Statechart satisfies all requirements.
我相信 Boost.Statechart 可以滿足以上所有要求。

State-local storage 狀態局部存儲

This not yet widely known state machine feature is enabled by the fact that every state is represented by a class. Upon state-entry, an object of the class is constructed and the object is later destructed when the state machine exits the state. Any data that is useful only as long as the machine resides in the state can (and should) thus be a member of the state. This feature paired with the ability to spread a state machine over several translation units makes possible virtually unlimited scalability. 
狀態機的一個尚未廣為人知的特性是,事實上每一個狀態可以用一個類來表示。在進入狀態時,該類的一個對像被構造,而在狀態機退出該狀態時,該對象就被析 構。任何僅在狀態機處於該狀態時才可用的數據可以(也應當)成為該狀態的數據成員。這一特性和可以將狀態機分散到多個編譯單元中的能力一起,使得無限擴展 成為可能。

In most existing FSM frameworks the whole state machine runs in one environment (context). That is, all resource handles and variables local to the state machine are stored in one place (normally as members of the class that also derives from some state machine base class). For large state machines this often leads to the class having a huge number of data members most of which are needed only briefly in a tiny part of the machine. The state machine class therefore often becomes a change hotspot what leads to frequent recompilations of the whole state machine.
在大多數已有的FSM框架中,整個狀態機運行在一個環境(上下文)中。即,所有在狀態機中的局部資源句柄和變量都保存在一個地方(通常被作為派生自狀態機 基類的某個子類的數據成員)。對於大的狀態機來說,這種方法常常會導致這個類具有大量的數據成員,而所需的只是其中一小部分。因此這個狀態機類常常會成為 修改熱點,從而導致整個狀態機的頻繁重編譯。

The FAQ item "What's so cool about state-local storage?" further explains this by comparing the tutorial StopWatch to a behaviorally equivalent version that does not use state-local storage.
在FAQ中的 "狀態局部存儲有什麼好處?" 一項中,通過將"指南"一文中的 StopWatch 例子和一個不使用狀態局部存儲的等效版本進行比較,進一步解釋了這個問題。

Dynamic configurability 動態配置能力

Two types of state machine frameworks 兩類狀態機框架

State machines that are built at runtime almost always get away with a simple state model (no hierarchical states, no orthogonal states, no entry and exit actions, no history) because the layout is very often computed by an algorithm. On the other hand, machine layouts that are fixed at compile time are almost always designed by humans, who frequently need/want a sophisticated state model in order to keep the complexity at acceptable levels. Dynamically configurable FSM frameworks are therefore often optimized for simple flat machines while incarnations of the static variant tend to offer more features for abstraction.
在運行期構建的狀態機幾乎總是使用簡單的狀態模型(沒有分層狀態,沒有正交狀態,沒有進入和退出動作,沒有歷史),因為它的佈局通常都是用一個算法來計算的。另一方面,在編譯期就固 定的狀態機佈局則幾乎總是由人來設計的,通常都需要/希望使用複雜的狀態模型以將複雜度保持在可接受的水平。因此可動態配置的FSM框架通常為簡單的平面 狀態機進行優化,而靜態的狀態機框架則關注於為抽像能力提供更多的特性。

However, fully-featured dynamic FSM libraries do exist. So, the question is:

Why not use a dynamically configurable FSM library for all state machines? 為何不對所有狀態機使用可動態配置的FSM庫?

One might argue that a dynamically configurable FSM framework is all one ever needs because any state machine can be implemented with it. However, due to its nature such a framework has a number of disadvantages when used to implement static machines:
有人可能會爭辨,可動態配置的FSM框架是所有人都需要的,因為任 意狀態機都可以用它來實現。但是,由於它的固有特點,這樣的框架被用於實現靜態狀態機時,具有多個缺點:

It is for these reasons, that Boost.Statechart was built from ground up to not support dynamic configurability. However, this does not mean that it's impossible to dynamically shape a machine implemented with this library. For example, guards can be used to make different transitions depending on input only available at runtime. However, such layout changes will always be limited to what can be foreseen before compilation. A somewhat related library, the boost::spirit parser framework, allows for roughly the same runtime configurability.
由於這些原因,Boost.Statechart 從開始構建起就支 持動態配置能力。不過,這並不意味著用本庫實現的狀態機不可能動態改變。例如,可以用警戒來根據僅在運行期有效的輸入來進行不同的轉換。但是,這種佈局的 變化總是被限制在編譯前就預見到的範圍之內。有一個稍微有點相關的庫,boost::spirit 分析器框架,同樣允許這種粗略的運行期配置能力。

Error handling 錯誤處理

There is not a single word about error handling in the UML state machine semantics specifications. Moreover, most existing FSM solutions also seem to ignore the issue. 

Why an FSM library should support error handling 為什麼一個FSM庫應該支持錯誤處理

Consider the following state configuration:


Both states define entry actions (x() and y()). Whenever state A becomes active, a call to x() will immediately be followed by a call to y(). y() could depend on the side-effects of x(). Therefore, executing y() does not make sense if x() fails. This is not an esoteric corner case but happens in every-day state machines all the time. For example, x() could acquire memory the contents of which is later modified by y(). There is a different but in terms of error handling equally critical situation in the Tutorial under Getting state information out of the machine when Running::~Running() accesses its outer state Active. Had the entry action of Active failed and had Running been entered anyway then Running's exit action would have invoked undefined behavior. The error handling situation with outer and inner states resembles the one with base and derived classes: If a base class constructor fails (by throwing an exception) the construction is aborted, the derived class constructor is not called and the object never comes to life.
以上兩個狀態均定義了進入動作(x() 和 y())。當狀態 A 成為活動時,將會調用 x() 並立即跟隨一個對 y() 的調用。y() 可能依賴於 x() 的副作用。因此,如果 x() 失敗則執行 y() 是沒有意義的。這並非一種隱秘或罕見的情形,而是在每天的狀態機中隨時都會發生的。例如,x() 可能要負責申請稍後由 y() 進行修改的數據內容的內存。這與"指南"文檔的 從 狀態機之外獲取狀態信息Running::~Running() 訪問其外層狀態 Active 的例子雖然不同,但在錯誤處理方面則是同樣危險的情形。如果 Active 的進入動作失敗了,而照樣進入 Running 的話,那麼 Running 的退出動作將引發未定義的行為。外層狀態與內層狀態的錯誤處理就像基類和派生類一樣:如果基類的構造函數失敗(拋出一個異常)而退出構造的話,派生類的構 造函數則不會被調用,對象也不會成為生存的。
In most traditional FSM frameworks such an error situation is relatively easy to tackle as long as the error can be propagated to the state machine client. In this case a failed action simply propagates a C++ exception into the framework. The framework usually does not catch the exception so that the state machine client can handle it. Note that, after doing so, the client can no longer use the state machine object because it is either in an unknown state or the framework has already reset the state because of the exception (e.g. with a scope guard). That is, by their nature, state machines typically only offer basic exception safety.
在許多傳統的FSM框架中,這種錯誤情況相對容易應付,只 要錯誤可以被傳播給狀態機的客戶。在這種情況下,失敗的動作只需傳遞一個異常給框架就可以了。框架通常不會捕獲該異常,這樣狀 態機的客戶就可以處理它了。注意,這樣做之後,客戶不可能再使用這個狀態機對象,因為它已經處於未知狀態,或者框架由於該異常而重置了狀態(如使用一個全 局的警戒)。即,由於這些固有的特性,狀態機通常只提供基本的異常保證。
However, error handling with traditional FSM frameworks becomes surprisingly cumbersome as soon as a lot of actions can fail and the state machine itself needs to gracefully handle these errors. Usually, a failing action (e.g. x()) then posts an appropriate error event and sets a global error variable to true. Every following action (e.g. y()) first has to check the error variable before doing anything. After all actions have completed (by doing nothing!), the previously posted error event has to be processed what leads to the execution of the remedy action. Please note that it is not sufficient to simply queue the error event as other events could still be pending. Instead, the error event has absolute priority and has to be dealt with immediately. There are slightly less cumbersome approaches to FSM error handling but these usually necessitate a change of the statechart layout and thus obscure the normal behavior. No matter what approach is used, programmers are normally forced to write a lot of code that deals with errors and most of that code is not devoted to error handling but to error propagation.
但是,一旦這些傳統FSM框架中有大量動作有可能失敗,且狀態機本 身需要適度地處理這些錯誤時,錯誤的處理將變得異常的笨重。通常 ,一個失敗的動作(如 x())會發出一個適當的錯誤事件並將一個全局的錯誤變量設置為真。接下來的每個動作(如 y())在做任何事情之前首先要檢查這個錯誤變量。在所有動作完成後(其實沒有做任何事!),先前被發出的錯誤事件必須進行處理,它引發補救動作的執行。 請注意,僅將錯誤事件和其它未決事件一樣進行排隊是不夠的。相反,錯誤事件應具有絕對的優先級且必須立即處理。有一些稍微沒那麼笨重的FSM錯誤處理方 法,但通常都需要對狀態圖佈局作一些修改,從而使得正常的行為變得模糊。無論使用哪一種方法,程序員通常都要寫大量的代碼來處理錯誤,而這些代碼中的大部 分不是專注於錯誤的處理而是 錯誤的傳播。

Error handling support in Boost.Statechart Boost.Statechart 中所支持的錯誤處理

C++ exceptions may be propagated from any action to signal a failure. Depending on how the state machine is configured, such an exception is either immediately propagated to the state machine client or caught and converted into a special event that is dispatched immediately. For more information see the Exception handling chapter in the Tutorial.
C++ 異常可以從任何動作中傳出,以表示某種失敗。取決於狀態機如何配置,這種異常要麼被立即傳遞給狀態機的客戶,要麼被捕獲並轉換為一種被立即分派的特殊事 件。更多的信息請見"指南"中的 錯 誤處理 一章。

Two stage exit 兩階段退出

An exit action can be implemented by adding a destructor to a state. Due to the nature of destructors, there are two disadvantages to this approach:

In my experience, neither of the above points is usually problem in practice since ...
以我的經驗,以上兩點通常實際上都不是問題,因為 ...

However, several people have put forward theoretical arguments and real-world scenarios, which show that the exit action to destructor mapping can be a problem and that workarounds are overly cumbersome. That's why two stage exit is now supported.
不過,有些人已經提出理論依據和實際情形,顯示將退出動作映射為析構函數存 在問題,而且解決的辦法相當麻煩。這就是為什麼現在已經支持 兩 階段退出 的原因。

Asynchronous state machines 異步狀態機

Requirements 要求

For asynchronous state machines different applications have rather varied requirements:

  1. In some applications each state machine needs to run in its own thread, other applications are single-threaded and run all machines in the same thread
  2. For some applications a FIFO scheduler is perfect, others need priority- or EDF-schedulers
  3. For some applications the boost::thread library is just fine, others might want to use another threading library, yet other applications run on OS-less platforms where ISRs are the only mode of (apparently) concurrent execution
    對於某些應用,boost::thread 庫就夠用了,而有些則希望使用其它線程庫,還有些應用則運行在沒有OS的平台上,ISR是其 唯一的並行執行模式(很顯然)

Out of the box behavior

By default, asynchronous_state_machine<> subtype objects are serviced by a fifo_scheduler<> object. fifo_scheduler<> does not lock or wait in single-threaded applications and uses boost::thread primitives to do so in multi-threaded programs. Moreover, a fifo_scheduler<> object can service an arbitrary number of asynchronous_state_machine<> subtype objects. Under the hood, fifo_scheduler<> is just a thin wrapper around an object of its FifoWorker template parameter (which manages the queue and ensures thread safety) and a processor_container<> (which manages the lifetime of the state machines).
缺省情況下,asynchronous_state_machine<> 子類的對象由一個 fifo_scheduler<> 對像服務。fifo_scheduler<> 在單線程應用中不會有鎖或等待,而在多線程程序中很使用 boost::thread 原語來實現。此外,一個 fifo_scheduler<> 對象可以服務任意數量的 asynchronous_state_machine<> 子類對象。在內部,fifo_scheduler<> 只是對其 FifoWorker 模板參數(負責管理隊列並確保線程安全)的一個對像和一個 processor_container<> (負責管理狀態機的生命週期)的簡單包裝。

The UML standard mandates that an event not triggering a reaction in a state machine should be silently discarded. Since a fifo_scheduler<> object is itself also a state machine, events destined to no longer existing asynchronous_state_machine<> subtype objects are also silently discarded. This is enabled by the fact that asynchronous_state_machine<> subtype objects cannot be constructed or destructed directly. Instead, this must be done through fifo_scheduler<>::create_processor<>() and fifo_scheduler<>::destroy_processor() (processor refers to the fact that fifo_scheduler<> can only host event_processor<> subtype objects; asynchronous_state_machine<> is just one way to implement such a processor). Moreover, create_processor<>() only returns a processor_handle object. This must henceforth be used to initiate, queue events for, terminate and destroy the state machine through the scheduler.
UML標準要求,在一個狀態機中,不觸發反應的事件應被丟棄。由於 fifo_scheduler<> 對像本身也是一個狀態機,所以發往不再存在的 asynchronous_state_machine<> 子類對象的事件也會被丟棄。這是通過不允許直接構造或析構 asynchronous_state_machine<> 子類對像來實現的。相反,必須通過 fifo_scheduler<>::create_processor<>()fifo_scheduler<>::destroy_processor() (processor 指出以下事實,fifo_scheduler<> 只能管理 event_processor<> 子類對像;asynchronous_state_machine<> 是實現這樣一個 processor 的唯一方法)來完成這一工作。此外,create_processor<>() 只返回一個 processor_handle 對象。其後它將被調度器用於初 始化、事件排隊、終止和銷毀狀態機。

Customization 定制

If a user needs to customize the scheduler behavior she can do so by instantiating fifo_scheduler<> with her own class modeling the FifoWorker concept. I considered a much more generic design where locking and waiting is implemented in a policy but I have so far failed to come up with a clean and simple interface for it. Especially the waiting is a bit difficult to model as some platforms have condition variables, others have events and yet others don't have any notion of waiting whatsoever (they instead loop until a new event arrives, presumably via an ISR). Given the relatively few lines of code required to implement a custom FifoWorker type and the fact that almost all applications will implement at most one such class, it does not seem to be worthwhile anyway. Applications requiring a less or more sophisticated event processor lifetime management can customize the behavior at a more coarse level, by using a custom Scheduler type. This is currently also true for applications requiring non-FIFO queuing schemes. However, Boost.Statechart will probably provide a priority_scheduler in the future so that custom schedulers need to be implemented only in rare cases.
如果用戶需要定制調度器的行為,他可通過以自己的符合 FifoWorker 概念的類型來實例化 fifo_scheduler<>,以實現定 制。我考慮過一個更為通用的設計,基於策略來實現鎖和等待,但是我到目前為止也無法拿出一個清晰而簡單的接口。特別是在等待方面,有的平台有條件變量,另 一些則有事件,還有一些什麼都沒有(它們只能循環直至事件到達,可能是通過ISR實現),難以建立統一的模型。以相對較少的代碼來實現一個定制的 FifoWorker 類型,並且事實上幾乎所有應用程序都只會實現最多一個這樣的類,看來這是不值得的。要求對事件處理器進行更少或更多的生存期管理的應用程序,可以在更為低 的級別來定制這些行為,通過使用一個定制的 Scheduler 類型。對於要求非FIFO隊列機制的應用程序,也可以如此。不過,Boost.Statechart 有可能在以後提供 priority_scheduler, 這樣就只在很罕見的情況下才需要實現定制的調度器了。

User actions: Member functions vs. function objects 用戶的動作:成員函數 vs. 函數對像

All user-supplied functions (react member functions, entry-, exit- and transition-actions) must be class members. The reasons for this are as follows:
所有用戶提供的函數(react 成員函數,進入、退出和轉換動作)都必須是類成員。原因如下:

Limitations 局限性

Junction points 匯合點

UML junction points are not supported because arbitrarily complex guard expressions can easily be implemented with custom_reaction<>s.
不支持 UML 的匯合點,因為可用多個 custom_reaction<> 很容易地實現任意複雜的警戒表達式。

Dynamic choice points 動態選擇點

Currently there is no direct support for this UML element because its behavior can often be implemented with custom_reaction<>s. In rare cases this is not possible, namely when a choice point happens to be the initial state. Then, the behavior can easily be implemented as follows:
當前沒有對這個 UML 元素的直接支持,因為它的行為通常可以用多個 custom_reaction<> 來實現。有極少見的情形下可能不行,即當選擇點恰好是初始狀態時。這時,可以像以下這樣來實現:

struct make_choice : sc::event< make_choice > {};

// universal choice point base class template
// 通用的選擇點基類模板
template< class MostDerived, class Context >
struct choice_point : sc::state< MostDerived, Context,
sc::custom_reaction< make_choice > >
typedef sc::state< MostDerived, Context,
sc::custom_reaction< make_choice > > base_type;
typedef typename base_type::my_context my_context;
typedef choice_point my_base;

choice_point( my_context ctx ) : base_type( ctx )
this->post_event( boost::intrusive_ptr< make_choice >(
new make_choice() ) );

// ...

struct MyChoicePoint;
struct Machine : sc::state_machine< Machine, MyChoicePoint > {};

struct Dest1 : sc::simple_state< Dest1, Machine > {};
struct Dest2 : sc::simple_state< Dest2, Machine > {};
struct Dest3 : sc::simple_state< Dest3, Machine > {};

struct MyChoicePoint : choice_point< MyChoicePoint, Machine >
MyChoicePoint( my_context ctx ) : my_base( ctx ) {}

sc::result react( const make_choice & )
if ( /* ... */ )
return transit< Dest1 >();
else if ( /* ... */ )
return transit< Dest2 >();
return transit< Dest3 >();

choice_point<> is not currently part of Boost.Statechart, mainly because I fear that beginners could use it in places where they would be better off with custom_reaction<>. If the demand is high enough I will add it to the library.
choice_point<> 現在還不是 Boost.Statechart 的組成部分,主要是因為我擔心初學者會將它用於本應使用 custom_reaction<> 的地方。如果有足夠多的需求,我會將它加入到本庫中。

Deep history of orthogonal regions 正交區域的深歷史

Deep history of states with orthogonal regions is currently not supported:


Attempts to implement this statechart will lead to a compile-time error because B has orthogonal regions and its direct or indirect outer state contains a deep history pseudo state. In other words, a state containing a deep history pseudo state must not have any direct or indirect inner states which themselves have orthogonal regions. This limitation stems from the fact that full deep history support would be more complicated to implement and would consume more resources than the currently implemented limited deep history support. Moreover, full deep history behavior can easily be implemented with shallow history:
試圖實現以上狀態圖會導致編譯期錯誤,因為 B 具有正交區域,且它的直接或間接外層狀態包含有深歷史偽狀態。換句話說,一個包含有深歷史偽狀態的狀態不能有任何直接或間接的內層狀態帶有正交區域。這一 限制是由以下事實引致的,完全深歷史的支持實現起來非常複雜,而且要比當前的實現消耗更多的資源。此外,完全深歷史的行為可以很容易地用淺歷史來實現:


Of course, this only works if C, D, E or any of their direct or indirect inner states do not have orthogonal regions. If not so then this pattern has to be applied recursively.
當然,這僅在 C, D, E 或其所有直接或間接內層狀態不帶正交區域時才可以。如果不是這樣的話,這一模式必須被重複遞歸應用。

Synchronization (join and fork) bars 同步(匯合與分叉)條


Synchronization bars are not supported, that is, a transition always originates at exactly one state and always ends at exactly one state. Join bars are sometimes useful but their behavior can easily be emulated with guards. The support of fork bars would make the implementation much more complex and they are only needed rarely.

Event dispatch to orthogonal regions 分派到多個正交區域的事件

The Boost.Statechart event dispatch algorithm is different to the one specified in David Harel's original paper and in the UML standard. Both mandate that each event is dispatched to all orthogonal regions of a state machine. Example:
Boost.Statechart 的事件分派算法與在 David Harel 的原創論文UML 標準 中所給出的算法不同。它們都要求每個事件要被分派到狀態機的所有正交區域。例如:


Here the Harel/UML dispatch algorithm specifies that the machine must transition from (B,D) to (C,E) when an EvX event is processed. Because of the subtleties that Harel describes in chapter 7 of his paper, an implementation of this algorithm is not only quite complex but also much slower than the simplified version employed by Boost.Statechart, which stops searching for reactions as soon as it has found one suitable for the current event. That is, had the example been implemented with this library, the machine would have transitioned non-deterministically from (B,D) to either (C,D) or (B,E). This version was chosen because, in my experience, in real-world machines different orthogonal regions often do not specify transitions for the same events. For the rare cases when they do, the UML behavior can easily be emulated as follows:
這裡,Harel/UML 的分派算法規定,狀態機在處理一個 EvX 事件時,必須從 (B,D) 轉換為 (C,E)。因為 Harel 在 他的論文 的第7章中所描述的這一點區別,這一算法的實現不僅非常複雜,而且比 Boost.Statechart 所採用的簡化版本要慢很多,簡化版本在查找到適用於當前事件的一個 反應 後,就會馬上停止搜索。即,這個例子如果用本庫來實現,狀態機會不確定地由 (B,D) 轉換到 (C,D) 或 (B,E)。選擇這一版本的原因是,以我的經驗,在真實世界中狀態機的不同正交區域通常不會同時為同一個事件指定轉換。對於確實這樣做的極少數情形, UML 的行為也可以很容易地模擬出來:


Transitions across orthogonal regions 跨正交區域的轉換


Transitions across orthogonal regions are currently flagged with an error at compile time (the UML specifications explicitly allow them while Harel does not mention them at all). I decided to not support them because I have erroneously tried to implement such a transition several times but have never come across a situation where it would make any sense. If you need to make such transitions, please do let me know!
跨正交區域的轉換當前會被標記為編譯期錯誤(UML 明確規定可以允許這樣而 Harel 則根本未提及)。我決定不支持這種轉換,因為我幾次嘗試實現這種轉換都不正確,而且從未碰到過一種值得去這樣做的情況。如果你需要這種轉換,請告訴我!

Valid HTML 4.01 Transitional

Revised 03 December, 2006

Copyright © 2003-2006 Andreas Huber Dönni

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)