株式会社エス・スリー・フォー

アクションの結果に応じて遷移先を変えたいのです (改訂版)

たとえば”ファイルを開く”イベントが起こったらそのアクションとして’fopen()する’んだけど、ファイルのオープンに成功したら’読み込み中’、失敗したら’初期状態’に遷移したい、なんてやつです。ありますよねぇ、そんなこと。

‘門番のいるゲート’の例では’Locked’状態で’Coin’イベントが発生したとき、投入されたコインが偽コインだったらゲートを開けずに’Locked’状態に戻りたい、という場合です。

残念ながら現FSMで記述できる状態遷移は、ある状態下において:

  • 受理しうるイベント
  • その時のアクション
  • 新たな状態(遷移先)

を指定できますが、アクションを実行してみないことには遷移先を決定できない場合の記述ができません。

現FSMの文法を大幅に変更することなく”アクションが遷移先を決定する”ことができないか、検討しました。

…アクションによる遷移先の変更に関する解決法ですが、実装してはみたもののどうにも釈然としないものを感じていました。

FSMの文法を変更せずに解決するため、ありもしない仮想的な状態を定義し、さらにコンテキストが仮想的なイベントを発行しなければならないからです。もっと’素直’な解決法はなかろうかとしばし考えました。

さんざん考えた挙句、

FSM文法に手を加えない限り、素直な表現は無理だろう…

という結論に至りました。

ある状態/イベントの組に対するアクションと遷移先を:

  <State name="Locked" enter="EnterLocked" exit="ExitLocked">
    <Event name="Coin" action="Check" transition="Confirm" />
    <Event name="Pass" action="Alarm" />
  </State>

のようにEvent要素のaction, transition 属性で指定しているのが現在のFSM文法です。

以下のように記述できたら’アクションによる遷移先の変更’が実現できますよね:

  <State name="Locked" enter="EnterLocked" exit="ExitLocked">
    <Event name="Coin">
      <!-- Check の結果が true ならば Unlocked に遷移する -->
      <transit state="Unlocked" if="Check"/>
    </Event>
    <Event name="Pass">
      <!-- Alarm アクションを行う -->
      <execute action="Alarm"/>
    </Event>
  </State>

すなわち、Event の子要素として executetransit を並べることができるようにしようというわけです。

早速この戦術にしたがってFSM文法に変更を加えました。

変更を加えたFSM文法 ‘smc.dtd’

<!-- DTD for 'smc' -->

<!ELEMENT fsm (state)* >
<!ATTLIST fsm name    NMTOKEN #REQUIRED>
<!ATTLIST fsm initial NMTOKEN #REQUIRED>

<!ELEMENT state (event)*>
<!ATTLIST state name  NMTOKEN #REQUIRED>
<!ATTLIST state enter NMTOKEN #IMPLIED>
<!ATTLIST state exit  NMTOKEN #IMPLIED>

<!ELEMENT event (execute | transit)* >
<!ATTLIST event name NMTOKEN #REQUIRED>

<!ELEMENT execute EMPTY>
<!ATTLIST execute action NMTOKEN #REQUIRED>

<!ELEMENT transit EMPTY>
<!ATTLIST transit state NMTOKEN #REQUIRED>
<!ATTLIST transit if    NMTOKEN #IMPLIED>

この文法にしたがって’偽コイン検出版ゲート’を記述すると:

新たな文法に基づく ‘gate.xml’

<!DOCTYPE fsm SYSTEM 'smc.dtd'>

<fsm name='Gate' initial='Locked'>

  <state name='Locked' enter='Lock'>
    <event name='Coin'>
      <transit state='Unlocked' if='Confirm'/>
    </event>
    <event name='Pass'>
      <execute action='Alarm'/>
    </event>
  </state>

  <state name='Unlocked' enter='Unlock'>
    <event name='Coin'>
      <execute action='ThankYou'/>
    </event>
    <event name='Pass'>
      <transit state='Locked'/>
    </event>
  </state>

</fsm>

この文法を解釈する’新smc’に’gate.xml’を食わせると、以下のようなヘッダ’gate.h’を吐きます:

生成されたヘッダ ‘gate.h’

#ifndef Gate_fsm_h
#define Gate_fsm_h

namespace Gate {

enum StateCode {
  Locked_state = 1,
  Unlocked_state = 2,
};

enum EventCode {
  Coin_event = 1,
  Pass_event = 2,
};

class Context {
public:
  virtual ‾Context() {}
  virtual void error(StateCode,EventCode) =0;
  virtual bool Confirm() = 0;
  virtual void Alarm() = 0;
  virtual void Lock() = 0;
  virtual void ThankYou() = 0;
  virtual void Unlock() = 0;
};
  ... 省略 ...
}

#endif

transit要素のif属性に指定したConfirmアクションの戻り値がboolになっています。

Contextの導出クラスでtrueあるいはfalseを返してください。

お試しに書いたユーザコードを示します:

お試しコード ‘gate.cpp’

#include <iostream>
#include <string>
#include "gate.h"

using namespace std;

class GateContext : public Gate::Context {
public:
  virtual void error(Gate::StateCode, Gate::EventCode) {}
  virtual bool Confirm();
  virtual void Alarm()         { cout << "金払え!!" << endl; }
  virtual void ThankYou()      { cout << "ありがとうございます" << endl; }
  virtual void Lock()          { cout << "ゲートを閉めます" << endl; }
  virtual void Unlock()        { cout << "ゲートを開けます" << endl; }
};

bool GateContext::Confirm() {
  cout << "コインは本物? [y/n] " << flush;
  string answer;
  cin >> answer;
  return answer[0] == 'y';
}

int main() {

  GateContext context;
  Gate::FiniteStateMachine fsm;
  fsm.setContext(&context);

  while ( true ) {
    cout << "  enter an event Coin / Pass / exit :" << flush;
    string event_name;
    cin >> event_name;
    if ( event_name == "exit" ) break;
    else
    if ( event_name == "Coin" ) fsm.Coin();
    else
    if ( event_name == "Pass" ) fsm.Pass();
    else continue;
  }
  return 0;
}

いかがでしょう、これでずいぶんとスッキリしました。

新版 ‘smc.cpp’

/*
 * smc : State Map Compiler
 */

#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <string>

#include <util/PlatformUtils.hpp>
#include <sax/ErrorHandler.hpp>
#include <sax/SAXParseException.hpp>

#include <dom/DOM.hpp>
#include <parsers/DOMParser.hpp>

/* for ( ... ) 内で宣言した変数を閉じ込めるマクロ */
#define for if ( false ) ; else for

using namespace std;

inline string transcode(const DOMString& domstr) {
  char* cstr = domstr.transcode();
  string result = cstr;
  delete[] cstr;
  return result;
}

/*
 * elementからattribute_nameなるアトリビュート値を取り出す
 */
inline string attr(DOM_Element element, const char* attribute_name) {
  return transcode(element.getAttribute(attribute_name));
}

void generate(ostream& stream, DOM_Document document) {

  set<string>::iterator iter;
  set<string> state_names;
  set<string> event_names;
  set<string> action_names;
  set<string> pred_names;

  DOM_NodeList nodes;
  DOM_Element  element;
  string       value;

  /*
   * ルートエレメント(fsm)を取得する
   */
  DOM_Element fsm = document.getDocumentElement();

  /*
   * 全stateを取り出す
   */
  nodes = fsm.getElementsByTagName("state");
  for ( int i = 0; i < nodes.getLength(); ++i ) {
    element = static_cast<DOM_Element&>(nodes.item(i));
    state_names.insert(attr(element,"name"));
  }

  /*
   * 全eventを取り出す
   */
  nodes = fsm.getElementsByTagName("event");
  for ( int i = 0; i < nodes.getLength(); ++i ) {
    element = static_cast<DOM_Element&>(nodes.item(i));
    event_names.insert(attr(element,"name"));
  }

  /*
   * 全predicateを取り出す
   */
  nodes = fsm.getElementsByTagName("transit");
  for ( int i = 0; i < nodes.getLength(); ++i ) {
    element = static_cast<DOM_Element&>(nodes.item(i));
    value = attr(element,"if");
    if ( !value.empty() ) {
      pred_names.insert(value);
    }
  }

  /*
   * 全actionを取り出す
   */
  nodes = fsm.getElementsByTagName("state");
  for ( int i = 0; i < nodes.getLength(); ++i ) {
    element = static_cast<DOM_Element&>(nodes.item(i));
    value = attr(element,"enter");
    if ( !value.empty() && pred_names.find(value) == pred_names.end() ) {
      action_names.insert(value);
    }
    value = attr(element,"exit");
    if ( !value.empty() && pred_names.find(value) == pred_names.end() ) {
      action_names.insert(value);
    }
  }
  nodes = fsm.getElementsByTagName("execute");
  for ( int i = 0; i < nodes.getLength(); ++i ) {
    element = static_cast<DOM_Element&>(nodes.item(i));
    value = attr(element,"action");
    if ( !value.empty() && pred_names.find(value) == pred_names.end() ) {
      action_names.insert(value);
    }
  }

  /*
   * 生成!!!
   */
  stream << "#ifndef " << attr(fsm,"name") << "_fsm_h¥n"
            "#define " << attr(fsm,"name") << "_fsm_h¥n¥n"
            "namespace " << attr(fsm,"name") << " {¥n" << endl;

  stream << "enum StateCode {¥n";
  int count = 0;
  for ( iter = state_names.begin(); iter != state_names.end(); ++iter ) {
    stream << "  " << *iter << "_state = " << ++count << ",¥n";
  }
  stream << "};¥n" << endl;

  stream << "enum EventCode {¥n";
  count = 0;
  for ( iter = event_names.begin(); iter != event_names.end(); ++iter ) {
    stream << "  " << *iter << "_event = " << ++count << ",¥n";
  }
  stream << "};¥n" << endl;

  stream << "class Context {¥n"
            "public:¥n"
            "  virtual ‾Context() {}¥n"
            "  virtual void error(StateCode,EventCode) =0;¥n";
  for ( iter = pred_names.begin(); iter != pred_names.end(); ++iter ) {
    stream << "  virtual bool " << *iter << "() = 0;¥n";
  }
  for ( iter = action_names.begin(); iter != action_names.end(); ++iter ) {
    stream << "  virtual void " << *iter << "() = 0;¥n";
  }
  stream << "};¥n¥n";

  stream << "class State {¥n"
            "  friend class FiniteStateMachine;¥n"
            "protected:¥n";
  for ( iter = state_names.begin(); iter != state_names.end(); ++iter ) {
    stream << "  static State* " << *iter << "_();¥n";
  }
  stream << "public:¥n"
            "  virtual void _enter_(Context*) {}¥n"
            "  virtual void _exit_(Context*) {}¥n"
            "  virtual StateCode _code_() =0;¥n";
  for ( iter = event_names.begin(); iter != event_names.end(); ++iter ) {
    stream << "  virtual State* " << *iter << "(Context* ctx) "
              "{ ctx->error(_code_()," << *iter << "_event); return this; }¥n";
  }
  stream << "};¥n¥n";

  nodes = fsm.getElementsByTagName("state");
  for ( int i = 0; i < nodes.getLength(); ++i ) {
    DOM_Element state = static_cast<DOM_Element&>(nodes.item(i));
    stream << "class " << attr(state,"name") << " : public State {¥n"
              "public:¥n";
    value = attr(state,"enter");
    if ( !value.empty() ) {
      stream << "  virtual void _enter_(Context* ctx) { ctx->" << value << "(); }¥n";
    }
    value = attr(state,"exit");
    if ( !value.empty() ) {
      stream << "  virtual void _exit_(Context* ctx) { ctx->" << value << "(); }¥n";
    }
    stream << "  virtual StateCode _code_() { return " << attr(state,"name") << "_state; }¥n"; 
    for ( DOM_Node node = state.getFirstChild(); node != 0; node = node.getNextSibling() ) {
      DOM_Element event = static_cast<DOM_Element&>(node);
      stream << "  virtual State* " << attr(event,"name") << "(Context* context) {¥n";
      for ( DOM_Node subnode = event.getFirstChild(); subnode != 0; subnode = subnode.getNextSibling() ) {
        DOM_Element action = static_cast<DOM_Element&>(subnode);
        string tag_name = transcode(action.getTagName());
        string condition = attr(action,"if");
        if ( tag_name == "execute" ) {
          stream <<   "    context->" << attr(action,"action") << "();¥n";
        } else
        if ( tag_name == "transit" ) {
          if ( !condition.empty() ) {
            stream << "    if ( context->" << condition << "() ) {¥n";
          } else {
            stream << "    {¥n";
          }
          stream << "      _exit_(context);¥n"
                    "      " << attr(action,"state") << "_()->_enter_(context);¥n"
                    "      return " << attr(action,"state") << "_();¥n"
                    "    }¥n";          
        }
      }
      stream << "    return this;¥n"
                "  }¥n";
          }
    stream <<  "};¥n¥n";

    stream << "State* State::" << attr(state,"name") << "_() {¥n"
              "  static " << attr(state,"name") << " state;¥n"
              "  return &state;¥n"
              "}¥n¥n";
  }

  stream << "class FiniteStateMachine {¥n"
            "  Context* context_;¥n"
            "  State*   state_;¥n"
            "public:¥n"
            "  FiniteStateMachine() : context_(0) "
            "{ state_ = State::" << attr(fsm,"initial") << "_(); }¥n"
            "  void setContext(Context* ctx) { context_ = ctx; }¥n"
            "  Context* context() { return context_; }¥n"
            "  StateCode state() { return state_->_code_(); }¥n";
  for ( iter = event_names.begin(); iter != event_names.end(); ++iter ) {
    stream << "  void " << *iter << "() { state_ = state_->" << *iter << "(context()); }¥n";
  }
  stream << "};¥n¥n";

  stream << "}¥n¥n"
            "#endif" << endl;
}

/*
 * Parse中に発生したエラーを出力する
 */
class ErrorReporter : public ErrorHandler {
  bool ok_;
public:
  ErrorReporter() : ok_(true) {}
  ‾ErrorReporter() {}

  void warning(const SAXParseException& toCatch) {}
  void error(const SAXParseException& toCatch) {
    ok_ = false;
    std::cerr << "Error at file ¥"" << transcode(toCatch.getSystemId())
              << "¥", line " << toCatch.getLineNumber()
              << ", column " << toCatch.getColumnNumber()
              << "¥n   Message: " << transcode(toCatch.getMessage())
              << "¥n¥n";
  }

  void fatalError(const SAXParseException& toCatch) {
    ok_ = false;
    std::cerr << "Fatal Error at file ¥"" << transcode(toCatch.getSystemId())
              << "¥", line " << toCatch.getLineNumber()
              << ", column " << toCatch.getColumnNumber()
              << "¥n   Message: " << transcode(toCatch.getMessage())
              << "¥n¥n";
  }

  void resetErrors() {}

  bool ok() const { return ok_; }
};

/*
 * ----- main -----
 */
int main(int argc, char* argv[]) {

  if ( argc != 2 ) {
    cerr << "smc <URL for FSM>" << endl;
    return 1;
  }

  /*
   * XML Parser の生成と初期化
   */
  try {
    XMLPlatformUtils::Initialize();
  } catch ( XMLException& ex ) {
    cerr << transcode(ex.getMessage()) << endl;
    return 1;
  }
  DOMParser parser;
  ErrorReporter error;
  parser.setDoValidation(true);  // 検証を行う
  parser.setErrorHandler(&error); // エラーハンドラを設定
  parser.setIncludeIgnorableWhitespace(false);

  /*
   * 引数に与えられたURLで示されたXMLをロードする
   */
  try {
    parser.parse(argv[1]);
    if ( !error.ok() ) {
      return 1;
    }
  } catch ( XMLException& ex ) {
    cerr << transcode(ex.getMessage()) << endl;
    return 1;
  }

  /*
   * ドキュメントを取得する
   */
  DOM_Document document = parser.getDocument();

  generate(cout, document);

  XMLPlatformUtils::Terminate();

  return 0;
}