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

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

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

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

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

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

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

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

こんな解決法はいかがでしょう。

  • ‘Locked’状態で
    • ‘Coin’イベントが発生したら’判定(Check)’アクションののち’確認(Confirm)’状態に遷移する。
  • ‘確認(Confirm)’状態で
    • ‘本物(realCoin)’イベントが発生したら’ゲートを開ける’アクションののち’Unlocked’状態に遷移する。
    • ‘偽物(fakeCoin)’イベントが発生したら(アクション無しで)’Locked’状態に遷移する。

上記の各状態遷移は、現FSMの文法で記述できます。

Gate.xml

<FSM name="Gate" initial="Locked" error="error">

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

  <State name="Confirm">
    <Event name="realCoin" action="Unlock" transition="Unlocked" />
    <Event name="fakeCoin" action="Lock"   transition="Locked"/>
  </State>

  <State name="Unlocked" enter="EnterUnlocked" exit="ExitUnlocked">
    <Event name="Coin" action="ThankYou" />
    <Event name="Pass" action="Lock" transition="Locked" />
  </State>

</FSM>

アクションの中からイベントを発行し、そのイベントが次の状態に遷移した途端に受理されるなら、’判定(Check)’アクションで偽コインか否かを判定し、その結果に従って’本物(realCoin)’あるいは’偽物(fakeCoin)’イベントを発行すればいいことになります。

このように、

  • アクションからイベントを発行できること
  • ある状態に遷移した瞬間、直前のアクションでイベントが発行されていたらそれを受理すること

を盛り込めばいいわけです。

新しいsmcはC++コードを吐きます(Javaコードは…ごめん)。

たとえば smc gate.xml すると、

  • Gate_state.h : enum Gate::state;
  • Gate_event.h : enum Gate::event;
  • Gate_context.h : class Gate::Context;
  • Gate_fsm.h : class Gate::FSM;
  • Gate_impl.cpp : Gate::Context / Gate::FSM の実装

が生成されます。コンテキストをGate::Contextから導出し、仮想関数を再定義して、FSMにsetContextします。

Gate.xml

<?xml-stylesheet type="text/xsl" href="fsm.xsl" media="msie 5.0" ?>

<!DOCTYPE FSM SYSTEM "fsm.dtd">

<FSM name="Gate" initial="Locked" error="error">
  <Note>門番のいるゲート</Note>
  <State name="Locked" enter="EnterLocked" exit="ExitLocked">
    <Note>ゲートが閉じている</Note>
    <Event name="Coin" action="Check" transition="Confirm">
      <Note>不正なコインでないことを確認する</Note>
    </Event>
    <Event name="Pass" action="Alarm">
      <Note>不法侵入</Note>
    </Event>
  </State>

  <State name="Confirm">
    <Event name="realCoin" action="Unlock" transition="Unlocked">
      <Note>ゲートを開ける</Note>
    </Event>
    <Event name="fakeCoin" action="Lock"   transition="Locked"/>
  </State>

  <State name="Unlocked" enter="EnterUnlocked" exit="ExitUnlocked">
    <Note>ゲートが開いている</Note>
    <Event name="Coin" action="ThankYou">
      <Note>チップとして受け取る</Note>
    </Event>
    <Event name="Pass" action="Lock" transition="Locked">
      <Note>ゲートを閉じる</Note>
    </Event>
  </State>

</FSM>

Gate.html (Gate.xml を fsm.xsl で変換したもの)

Gate の状態遷移

門番のいるゲート

初期状態 Locked
異常時のアクション error
  1. 状態 : Locked

    ゲートが閉じている

    • 入場動作 : EnterLocked
    • 退場動作 : ExitLocked
    イベント アクション 遷移先 説明
    Coin Check Confirm 不正なコインでないことを確認する
    Pass Alarm 不法侵入
  2. 状態 : Confirm
    • 入場動作 :
    • 退場動作 :
    イベント アクション 遷移先 説明
    realCoin Unlock Unlocked ゲートを開ける
    fakeCoin Lock Locked
  3. 状態 : Unlocked

    ゲートが開いている

    • 入場動作 : EnterUnlocked
    • 退場動作 : ExitUnlocked
    イベント アクション 遷移先 説明
    Coin ThankYou チップとして受け取る
    Pass Lock Locked ゲートを閉じる

※ 遷移先が空欄である場合、状態の変化がなく、入場/退場動作も行わないことを意味します

コンテキスト

class GateContext : public Gate::Context {
public:
  virtual void error();
  virtual void Alarm();
  virtual void EnterLocked();
  virtual void EnterUnlocked();
  virtual void ExitLocked();
  virtual void ExitUnlocked();
  virtual void Lock();
  virtual void ThankYou();
  virtual void Unlock();
  virtual void Check();
};

// 本物/偽物を判定する
void GateContext::Check() {
  string prompt;
  cout << "コインは本物? [y/n] ";
  cin >> prompt;
  if ( prompt[0] == 'y' ) {
    realCoin(); // '本物'イベント発行
  } else {
    fakeCoin(); // '偽物'イベント発行
  }
}

...

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

実行結果

Locked
  enter an event(coin/pass or exit) [c/p/e]:c
Check: state=Locked event=Coin
コインは本物? [y/n] y
ExitLocked: state=Locked event=(none)
閉じた状態を終わります
Unlock: state=Confirm event=realCoin
ゲートを開けます
EnterUnlocked: state=Unlocked event=(none)
ゲートが開きました
Unlocked
  enter an event(coin/pass or exit) [c/p/e]:p
Lock: state=Unlocked event=Pass
ゲートを閉めます
ExitUnlocked: state=Unlocked event=(none)
開いた状態を終わります
EnterLocked: state=Locked event=(none)
ゲートが閉まりました
Locked
  enter an event(coin/pass or exit) [c/p/e]:c
Check: state=Locked event=Coin
コインは本物? [y/n] n
ExitLocked: state=Locked event=(none)
閉じた状態を終わります
Lock: state=Confirm event=fakeCoin
ゲートを閉めます
EnterLocked: state=Locked event=(none)
ゲートが閉まりました
Locked
  enter an event(coin/pass or exit) [c/p/e]:e

上記戦略を盛り込んだのが以下のコードです。コンテキスト内部からイベントを発行することができ、次の状態に遷移したら直ちにイベントを受理します。

smc.cpp

/*
 * Finite State Machine code generator
 *  using IBM alphaWorks XML4C
 */

#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <string>
#include <algorithm>

#include <util/PlatformUtils.hpp>    // PlatformUtils
#include <parsers/SAXParser.hpp>     // SAXParser
#include <sax/HandlerBase.hpp>       // HandlerBase
#include <sax/SaxParseException.hpp> // SaxParseException

#define LN "¥n"

using namespace std;

/*
 * UNICODEからstringへの変換
 */
inline string transcode(const XMLCh* xmlch) {
  string result;
  if ( xmlch ) {
    char* p = XMLString::transcode(xmlch);
    result = p;
    delete[] p;
  }
  return result;
}

typedef set<string> strings;

void insert_strings(strings& ss, const string& s) {
  istringstream strm(s);
  string token;
  while ( strm >> token ) {
    ss.insert(token);
  }
}

/*
 * Event
 */
struct Event {
  std::string name;        // 名前
  strings     actions;     // アクション
  std::string transition;  // 次の状態
};

inline bool operator<(const Event& x, const Event& y) {
  return x.name < y.name;
}

typedef std::set<Event> Events;

/*
 * State
 */
struct State {
  std::string name;   // 名前
  strings     enter;  // 入場動作
  strings     exit;   // 退場動作
  Events      events; // Eventの集合
  State() {}
};

inline bool operator<(const State& x, const State& y) {
  return x.name < y.name;
}

typedef std::set<State> States;

/*
 * FSM
 */
struct FSM {
  std::string name;     // 名前
  std::string initial;  // 初期状態
  strings     error;    // エラーアクション
  States      states;   // Stateの集合
  strings     state_names;
  strings     event_names;
  strings     action_names;
  strings     transition_names;
};

/*
 * エラーメッセージの出力
 */
ostream& operator<<(ostream& stream, const SAXParseException& exception) {
  return stream << "public-id=" << transcode(exception.getPublicId())
                << " system-id=" << transcode(exception.getSystemId())
                << " line=" << exception.getLineNumber()
                << " column=" << exception.getColumnNumber()
                << " : " << transcode(exception.getMessage());
}

/*
 * XMLからFSMを構築するためのハンドラ
 */
class Handler : public HandlerBase {
  State current_state;
  FSM&  fsm;
public:

  Handler(FSM& f) : fsm(f) {}

  // DocumentHandler

  // エレメント(タグ)の開始
  virtual void startElement(const XMLCh* const tag_name, AttributeList& attrs) {
    std::string tag = transcode(tag_name);
    std::string tmp;
    // <FSM ...>
    if ( tag == "FSM" ) {
      fsm.name     = transcode(attrs.getValue(L"name"));
      fsm.initial  = transcode(attrs.getValue(L"initial"));
      tmp = transcode(attrs.getValue(L"error"));
      insert_strings(fsm.error, tmp);
      insert_strings(fsm.action_names, tmp);
    } else
    // <State ...>
    if ( tag == "State" ) {
      current_state.events.clear();
      current_state.enter.clear();
      current_state.exit.clear();
      current_state.name  = tmp = transcode(attrs.getValue(L"name"));
      if ( !tmp.empty() ) fsm.state_names.insert(tmp);
      tmp = transcode(attrs.getValue(L"enter"));
      if ( !tmp.empty() ) {
        insert_strings(fsm.action_names, tmp);
        insert_strings(current_state.enter, tmp);
      }
      tmp = transcode(attrs.getValue(L"exit"));
      if ( !tmp.empty() ) {
        insert_strings(fsm.action_names, tmp);
        insert_strings(current_state.exit, tmp);
      }
    } else
    // <Event ...>
    if ( tag == "Event" ) {
      Event event;
      event.name = tmp = transcode(attrs.getValue(L"name"));
      if ( !tmp.empty() ) fsm.event_names.insert(tmp);
      tmp = transcode(attrs.getValue(L"action"));
      if ( !tmp.empty() ) {
        insert_strings(event.actions, tmp);
        insert_strings(fsm.action_names, tmp);
      }
      event.transition = tmp = transcode(attrs.getValue(L"transition"));
      if ( !tmp.empty() ) fsm.transition_names.insert(tmp);
      current_state.events.insert(event);
    }
  }

  // エレメント(タグ)の終了
  virtual void endElement(const XMLCh* const tag_name) {
    std::string tag = transcode(tag_name);
    // </State>
    if ( tag == "State" ) {
      fsm.states.insert(current_state);
    }
  }

  // ErrorHandler

  virtual void warning(const SAXParseException& exception)
    { cout << "warning: " << exception << endl; }

  virtual void error(const SAXParseException& exception)
    { cout << "error:   " << exception << endl; }

  virtual void fatalError(const SAXParseException& exception)
    { cout << "fatal:   " << exception << endl; }

};

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

  cerr << "smc - State Map Compiler for C++ " __DATE__ << endl
       << "      using IBM alphaWorks XML Parser for C++ (XML4C)¥n" << endl;
  if ( argc != 2 ) {
    cerr << "usage: smc <xml-script>" << endl;
    return 0;
  }

  FSM fsm;
  Events::const_iterator  eit;
  States::const_iterator  sit;
  strings::const_iterator nit;

  /*
   * 初期化とFSMの構築
   */
  try {
    XMLPlatformUtils::Initialize();
    SAXParser parser;
    Handler   handler(fsm);

    parser.setDoValidation(true);        // DTDによる検証を行う
    parser.setDocumentHandler(&handler); // ハンドラ設定
    parser.setErrorHandler(&handler);    // 同上(エラー用)

    parser.parse(argv[1]);

  } catch ( const XMLException& er ) {
    cout << er.getMessage() << endl;
  }

  /*
   * 初期状態は定義されているか?
   */
  if ( fsm.state_names.find(fsm.initial) == fsm.state_names.end() ) {
    cerr << "invalid initial : " << fsm.initial << endl;
    return 1;
  }

  /*
   * 遷移先は定義されているか?
   */
  for ( nit = fsm.transition_names.begin(); nit != fsm.transition_names.end(); ++nit ) {
    if ( fsm.state_names.find(*nit) == fsm.state_names.end() ) {
      cerr << "invalid transition : " << *nit << endl;
      return 1;
    }
  }

  ofstream fout;
  string   fname;
  /*
   * C++ コードの生成
   */

  ///// STATE

  fname = fsm.name + "_state.h";
  fout.open(fname.c_str());
  cout << fname << endl;

  fout << "#ifndef __" << fsm.name << "_state_h__" LN
       << "#define __" << fsm.name << "_state_h__" LN LN;

  fout << "namespace " << fsm.name << " {" LN LN;

  fout << "enum state { ";
  for ( nit = fsm.state_names.begin(); nit != fsm.state_names.end(); ++nit ) {
    fout << *nit << ", ";
  }
  fout << "};" LN LN
          "}" LN
          "#endif" LN;
  fout.close();

  ///// EVENT

  fname = fsm.name + "_event.h";
  fout.open(fname.c_str());
  cout << fname << endl;

  fout << "#ifndef __" << fsm.name << "_event_h__" LN
       << "#define __" << fsm.name << "_event_h__" LN LN;

  fout << "namespace " << fsm.name << " {" LN LN;

  fout << "enum event { ";
  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << *nit << ", ";
  }
  fout << "none };" LN LN
          "}" LN
          "#endif" LN;
  fout.close();

  ///// CONTEXT

  fname = fsm.name + "_context.h";
  fout.open(fname.c_str());
  cout << fname << endl;

  /*
   * 宣言部 (ヘッダ)
   */
  fout << "#ifndef __" << fsm.name << "_context_h__" LN
          "#define __" << fsm.name << "_context_h__" LN LN
          "#include ¥"" << fsm.name << "_state.h¥"" LN
          "#include ¥"" << fsm.name << "_event.h¥"" LN LN
          "namespace " << fsm.name << " {" LN LN;

  /*
   * Context 宣言
   */
  fout << "class FSM;" LN LN
          "class Context {" LN "public:" LN;
  for ( nit = fsm.action_names.begin(); nit != fsm.action_names.end(); ++nit ) {
    fout << "  virtual void " << *nit << "() =0;" LN;
  }
  fout << LN "private:" LN "  FSM* fsm_;" LN "  friend class FSM;" LN;
  fout << LN "protected:" LN
          "  state getState() const;" LN
          "  event getEvent() const;" LN
          "  const char* getStateName() const;" LN
          "  const char* getEventName() const;" LN;
  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "  void " << *nit << "();" LN;
  }
  fout << "};" LN LN
          "}" LN
          "#endif" LN LN;

  fout << "/* prototype of Context's derivative */" LN
          "/*" LN LN
          "#include ¥"context.h¥"" LN LN
          "class ContextDerivative : public " << fsm.name << "::Context {" LN
          "public:" LN;
  for ( nit = fsm.action_names.begin(); nit != fsm.action_names.end(); ++nit ) {
    fout << "  virtual void " << *nit << "();" LN;
  }
  fout << "};" LN LN
          "*/" LN;

  fout.close();

  ///// FSM

  fname = fsm.name + "_fsm.h";
  fout.open(fname.c_str());
  cout << fname << endl;

  fout << "#ifndef __" << fsm.name << "_fsm_h__" LN
          "#define __" << fsm.name << "_fsm_h__" LN LN
          "#include ¥"" << fsm.name << "_state.h¥"" LN
          "#include ¥"" << fsm.name << "_event.h¥"" LN LN
          "namespace " << fsm.name << " {" LN LN
          "class Context;" LN
          "class State;" LN LN;

  /*
   * FSM 宣言
   */
  fout << "class FSM  {" LN
          "  Context* context_;" LN
          "  State*   state_;" LN
          "  event    post_event_;" LN
          "  event    event_;" LN
          "  void     prologue();" LN
          "  static State* state_v[];" LN
          "  static const char* event_v[];" LN LN
          "  friend class Context;" LN;
  for ( nit = fsm.state_names.begin(); nit != fsm.state_names.end(); ++nit ) {
    fout << "  friend class " << *nit << "State;" LN;
  }
  fout << "public:" LN
          "  FSM() : state_(state_v[" << fsm.initial << "]), context_(0), post_event_(none), event_(none) {}" LN;
  fout << "  void        setContext(Context* context);" LN
          "  Context*    getContext() const { return context_; }" LN
          "  state       getState() const;" LN
          "  const char* getStateName() const;" LN
          "  event       getEvent() const;" LN
          "  const char* getEventName() const;" LN LN;
  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "  void " << *nit << "();" LN;
  }
  fout << "};" LN LN
          "}" LN LN
          "#endif" LN;
  fout.close();

  ///// IMPLEMENTATION

  fname = fsm.name + "_impl.cpp";
  fout.open(fname.c_str());
  cout << fname << endl;

  fout << "#include ¥"" << fsm.name << "_context.h¥"" LN
          "#include ¥"" << fsm.name << "_fsm.h¥"" LN LN;

  fout << "namespace " << fsm.name << " {" LN LN;

  // Context

  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "void Context::" << *nit << "() { fsm_->post_event_ = " << fsm.name << "::" << *nit << "; }" LN;
  }
  fout << "state Context::getState() const { return fsm_->getState(); }" LN
          "const char* Context::getStateName() const { return fsm_->getStateName(); }" LN
          "event Context::getEvent() const { return fsm_->getEvent(); }" LN
          "const char* Context::getEventName() const { return fsm_->getEventName(); }" LN LN;

  // State

  fout << "class State {" LN "public:" LN
          "  virtual const char* name() const =0;" LN
          "  virtual state id() const =0;" LN
          "  virtual void enter(FSM* fsm) {}" LN
          "  virtual void exit(FSM* fsm) {}" LN
          "  void error(FSM* fsm);" LN;
  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "  virtual void " << *nit << "(FSM* fsm) { error(fsm); }" LN;
  }
  fout << "};" LN LN;

  fout << "void State::error(FSM* fsm) {" LN;
  if ( !fsm.error.empty() ) {
    fout << "  Context* context = fsm->getContext();" LN;
    for ( nit = fsm.error.begin(); nit != fsm.error.end(); ++nit ) {
      fout << "  context->" << *nit << "();" LN;
    }
  }
  fout << "}" LN LN;

  // State's derivatives

  for ( sit = fsm.states.begin(); sit != fsm.states.end(); ++sit) {
    fout << "class " << sit->name << "State : public State {" LN "public:" LN
            "  virtual const char* name() const { return ¥"" << sit->name << "¥"; }" LN
            "  virtual state id() const { return " << sit->name << "; }" LN;
    if ( !sit->enter.empty() ) {
      fout << "  virtual void enter(FSM* fsm);" LN;
    }
    if ( !sit->exit.empty() ) {
      fout << "  virtual void exit(FSM* fsm);" LN;
    }
    for ( eit = sit->events.begin(); eit != sit->events.end(); ++eit ) {
      fout << "  virtual void " << eit->name << "(FSM* fsm);" LN;
    }
    fout << "};" LN LN;

    // State (impl)

    if ( !sit->enter.empty() ) {
      fout << "void " << sit->name << "State::enter(FSM* fsm) {" LN
              "  Context* context = fsm->getContext();" LN;
      for ( nit = sit->enter.begin(); nit != sit->enter.end(); ++nit ) {
        fout << "  context->"  << *nit << "();" LN;
      }
      fout << "}" LN LN;
    }
    if ( !sit->exit.empty() ) {
      fout << "void " << sit->name << "State::exit(FSM* fsm) {" LN
              "  Context* context = fsm->getContext();" LN;
      for ( nit = sit->exit.begin(); nit != sit->exit.end(); ++nit ) {
        fout << "  context->"  << *nit << "();" LN;
      }
      fout << "}" LN LN;
    }
    fout << LN;

  // State's derivatives (impl.)

    for ( eit = sit->events.begin(); eit != sit->events.end(); ++eit ) {
      fout << "void " << sit->name << "State::" << eit->name << "(FSM* fsm) {" LN;
      if ( !eit->actions.empty() ) {
        fout << "  Context* context = fsm->getContext();" LN;
        for ( nit = eit->actions.begin(); nit != eit->actions.end(); ++nit ) {
          fout << "  context->"  << *nit << "();" LN;
        }
      }
      fout << "  fsm->event_ = " << fsm.name << "::none;" LN;
      if ( !eit->transition.empty() ) {
        if ( !sit->exit.empty() ) {
          fout << "  exit(fsm);" LN;
        }
        fout << "  fsm->state_ = FSM::state_v[" << eit->transition << "];" LN
                "  fsm->state_->enter(fsm);" LN;
      }
      fout << "}" LN LN;
    }
    fout <<"static " << sit->name << "State " << sit->name << "_;" LN LN;
  }

  // FSM (impl.)

  fout << "State* FSM::state_v[] = { ";
  for ( nit = fsm.state_names.begin(); nit != fsm.state_names.end(); ++nit ) {
    fout << "&" << *nit << "_, ";
  }
  fout << "0 };" LN;

  fout << "const char* FSM::event_v[] = { ";
  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "¥"" << *nit << "¥", ";
  }
  fout << "¥"(none)¥" };" LN;

  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "void FSM::" << *nit << "() { event_ = " << fsm.name << "::"
         << *nit << "; state_->" << *nit << "(this); prologue(); }" LN;
  }

  fout << "void FSM::setContext(Context* context) { context_ = context; context_->fsm_ = this; }" LN
          "state FSM::getState() const { return state_->id(); }" LN
          "const char* FSM::getStateName() const { return state_->name(); }" LN
          "event FSM::getEvent() const { return event_; }" LN
          "const char* FSM::getEventName() const { return event_v[event_]; }" LN LN;

  fout << "void FSM::prologue() {" LN
          "  event_ = post_event_;" LN
          "  post_event_ = none;" LN
          "  switch ( event_ ) {" LN;
  for ( nit = fsm.event_names.begin(); nit != fsm.event_names.end(); ++nit ) {
    fout << "  case " << fsm.name << "::" << *nit  << " : " << *nit << "(); break;" LN;
  }
  fout << "  }" LN
          "}" LN LN;

  fout << "}" LN;
  fout.close();

  return 0;
}