特集記事

状態遷移図／表、すなわち設計をコードでテストする

状態遷移のモデル検証

2015/01/14 14:00

ポスト

　状態遷移表を駆動するのが状態機械:statemachine、こいつに状態遷移表を与え、statemachine_drive()にイベントを投げ込むと、statemachine内部に保持された現状態と与えられたイベントの組に一致するレコードを見つけてアクションを実行し、新たな状態に遷移します。

list04　statemachine_defs.h

#ifndef STATEMACHINE_DEFS_H_
#define STATEMACHINE_DEFS_H_

typedef int  state_code;
typedef int  event_code;
typedef void event;
typedef void context;

typedef int        (*action)(const event* ev, context* ctx);
typedef event_code (*get_event_code)(const event* ev);
typedef void       (*dump)(state_code stc, event_code evc, unsigned pass, void* arg);
typedef void       (*audit)(state_code curr, event_code evc, state_code next, void* arg);

#ifndef STATEMACHINE_TRANSITION_BRANCH
#define STATEMACHINE_TRANSITION_BRANCH 4
#endif

// #define STATEMACHINE_TEST
 
struct transition_t {
  state_code state_code_;
  event_code event_code_;
  action     action_;
  state_code next_state_code_[STATEMACHINE_TRANSITION_BRANCH];
};
typedef struct transition_t transition;

#endif

list05　statemachine.h

#ifndef STATEMACHINE_H_
#define STATEMACHINE_H_

/* -----------------------------------------------------
 * 状態機械:
 * このファイルを修正する必要はない。
 * -----------------------------------------------------
 */
#include <stdbool.h> /* from C99 : defines bool, true, false */

#include "statemachine_defs.h"

struct statemachine_t {
  state_code     state_code_;
  get_event_code get_event_code_;
  context*       context_;
  transition*    transition_;
  unsigned       transition_size_;
  action         bad_action_;
  audit          audit_;
  void*          arg_;
};
typedef struct statemachine_t statemachine; 

#ifdef __cplusplus
extern "C" {
#endif

/* statemachineの初期化。
 * あらゆるstatemachine_xxx関数に先立って呼び出さねばならない。
*/
bool       statemachine_setup(statemachine* sm, transition* tr, get_event_code gec);

/* statemachineの使用を終えるとき、必ず呼び出さねばならない。
 *
 */
void       statemachine_teardown(statemachine* sm);

/* statemachineの現在のstate_codeを返す。
 */
state_code statemachine_get_state_code(const statemachine* sm);

/* statemachineにstate_codeを設定する。
 * 最初のstatemachine_driveに先立って少なくとも一度は呼び出さねばならない。
 */
void       statemachine_set_state_code(statemachine* sm, state_code st);

/* statemachineに設定されたcontextを返す。
 */
context*   statemachine_get_context(statemachine* sm);

/* statemachineにcontextを設定する。
 */
void       statemachine_set_context(statemachine* sm, context* ctx);

/* 状態遷移表に現れない状態とイベントの組を受理したとき呼び出されるアクションを設定する。
 */
void       statemachine_set_bad_transition_handler(statemachine* sm, action bad);

/* 状態遷移表に基づいて現状態と与えたイベントの組に応じたアクションを呼び出し、
 * 新たな状態に遷移する。
 */
state_code statemachine_drive(statemachine* sm, const event* ev);

/* 状態の遷移のたびに呼び出す関数を設定する
 */
void statemachine_set_transition_audit(statemachine* sm, audit au, void* arg);

#ifdef __cplusplus
}
#endif

#endif

list06　statemachine.c（抜粋）

/* -----------------------------------------------------
 * 状態機械:
 * このファイルを修正する必要はない。
 * -----------------------------------------------------
 */

#include <stdlib.h>
#include <assert.h>
#include "statemachine.h"

/* STATEMACHINE_QUICK_TRANSITION を #define すると、
 * statemachine_drive() 内での状態/イベントの検索が
 * 線形検索（linear-search）から二分検索（binary-search）となり、
 * 検索に要する時間計算量が O(N) から O(logN) となるため、
 * 特に大きな状態遷移表を与えた時のパフォーマンスを向上させる。
 *
 * ※ ただし、標準関数 qsortおよびbsearch を呼び出し、
 * statemachine_setup()に与えた状態遷移表（transaction*）の
 * 内容が変更（昇順にソート）される。
 */

#define STATEMACHINE_QUICK_TRANSITION

static int transition_compare(const void* v0, const void* v1) {
  const transition* t0 = (const transition*)v0;
  const transition* t1 = (const transition*)v1;
  if ( t0->state_code_ < t1->state_code_ ) {
    return -1;
  } else  
  if ( t0->state_code_ > t1->state_code_ ) {
    return 1;
  } else  
  if ( t0->event_code_ < t1->event_code_ ) {
    return -1;
  } else
  if ( t0->event_code_ > t1->event_code_ ) {
    return 1;
  }
  return 0;
}

//#define STATEMACHINE_QUICK_TRANSITION

static transition* transition_find(transition* tr, unsigned trsize, state_code stc, event_code evc) {
  transition key;
  key.state_code_ = stc;
  key.event_code_ = evc;
#ifndef STATEMACHINE_QUICK_TRANSITION
  // lenear-search
  for ( unsigned i = 0; i < trsize; ++i ) {
    if (  transition_compare(&key, &tr[i]) == 0 ) {
      return &tr[i];
    }
  }
  return NULL;
#else
  // binary-search
  return (transition*)bsearch(&key, tr, trsize, sizeof(transition), &transition_compare);
#endif
}

bool       statemachine_setup(statemachine* sm, transition* tr, get_event_code gec) {
  sm->context_        = NULL;
  sm->transition_     = tr;
  sm->get_event_code_ = gec;
  sm->bad_action_     = &default_bad_transition_action;
  sm->audit_          = &default_audit;
  sm->arg_            = NULL;
  statemachine_set_state_code(sm, -1);

  unsigned num = 0U;
  for ( const transition* p = tr; p->state_code_ >= 0 && p->event_code_ >= 0; ++p ) {
    ++num;
  }
  sm->transition_size_ = num;
#ifdef STATEMACHINE_QUICK_TRANSITION
  qsort(tr, num, sizeof(transition), &transition_compare);
#endif
  return true;
}

...中略...

state_code statemachine_drive(statemachine* sm, const event* ev) {
  const state_code stc = statemachine_get_state_code(sm); 
  const event_code evc = (*sm->get_event_code_)(ev);

  // 状態遷移表から、state,eventの一致する行を見つけ、
  // 　アクションおよび遷移先を手に入れる
  transition* trans = transition_find(sm->transition_, sm->transition_size_, stc, evc);
  int result;
  // アクションを実行する
  if ( trans == NULL ) {
    (*sm->bad_action_)(ev, sm->context_);
    statemachine_set_state_code(sm, -1);
    return -1;
  } else {
    result = (*trans->action_)(ev, sm->context_);
    state_code newstate = ( result < 0 || result >= STATEMACHINE_TRANSITION_BRANCH ) ? -1 : trans->next_state_code_[result];
    (*sm->audit_)(stc, evc, newstate, sm->arg_);
    statemachine_set_state_code(sm, newstate);
    return newstate;
  }
  // 新たな状態に遷移する
}

設計をコードでテストする

　ここからが新たな試み。生成されたひな型のアクション部分は当然ながらカラッポなので、main()を用意して動かしたところで何の結果も得られません。だけど状態遷移そのものはテンプレートに書いた状態遷移表のとおりに行われます。これを利用して状態遷移表が正しいか、言い換えれば「この状態遷移設計は与えられた要求（/*～*/ と //～改行を抽出する）を満足するか」をテスト／検証できるはず。設計をコードでテストしてみましょう。

　状態遷移設計が正しければ、

"abc"を与えたとき、状態は"コメントの外"
"/" を与えたとき、状態は"/の直後"
"/*" を与えたとき、状態は"ブロックコメントの中"
"//" を与えたとき、状態は"ラインコメントの中"

……といったテストケースが列挙できます。google testでテストを書きました。

list07　ec_gtest.cpp（抜粋）

#include <cstdio>
#include <gtest/gtest.h>

#include "statemachine.h"
#include "transition_log.h"
#include "ec_state_transition.h"

statemachine sm;
ec_context   ctx;
ec_event     ev;

state_code run_sequence(const std::string& input) {
  statemachine_set_state_code(&sm, EC_S_OUT_COMMENT);
  for ( char ch : input ) {
    ec_event_code evc;
    switch ( ch ) {
    case '*'  : evc = EC_E_STAR;  break;
    case '/'  : evc = EC_E_SLASH; break;
    case '\n' : evc = EC_E_LF;    break;
    default:    evc = EC_E_OTHER; break;
    }
    ec_event_set_event_code(&ev, evc);
    statemachine_drive(&sm, &ev);
  }
  return statemachine_get_state_code(&sm);
}

int main(int argc, char**argv) {
    
    ::testing::InitGoogleTest(&argc, argv);

    transition_log log;
    transition_log_setup(&log);

    ec_context_setup(&ctx, stdout);
    statemachine_setup(&sm, ec_state_transition_table(), &ec_event_get_event_code);
    statemachine_set_context(&sm, &ctx);
    statemachine_set_transition_audit(&sm, &transition_log_audit, &log);

    int result = RUN_ALL_TESTS();

    ...中略...

    transition_log_teardown(&log);
    statemachine_teardown(&sm);
    ec_context_teardown(&ctx);

    return result;
}

/* ----- tests from here... ----- */

TEST(ec,test0) {
  state_code st = run_sequence("abc");
  ASSERT_EQ(EC_S_OUT_COMMENT, st);
}

TEST(ec,test1) {
  state_code st = run_sequence("/");
  ASSERT_EQ(EC_S_SECOND_LEAD, st);
}

TEST(ec,test2) {
  state_code st = run_sequence("/*");
  ASSERT_EQ(EC_S_IN_BLOCKCOMMENT, st);
}

TEST(ec,test3) {
  state_code st = run_sequence("//");
  ASSERT_EQ(EC_S_IN_LINECOMMENT, st);
}

/* ----- ...to here ----- */

　コンパイル／実行すると...

　あれま、失敗してます。入力"//"に対し"ブロックコメント内"に遷移してますね。状態遷移（つまり設計そのもの）、もしくはテンプレート上の状態遷移表に間違いがあるのでしょう。state_transition.ttを修正し、再度ひな型を生成して再テスト。

　期待通りに動いてくれました...だけどこれではまだダメ、テスト・ケースがこれで十分なわけがない。

　statemachine_drive()には現状態／イベント／遷移先をモニタする仕組みを埋め込んでおきました。これを使うと状態遷移表の各マスのうち、一度でも通過したものをレポートでき、テストで通っていないマスを知ることができます。ついでにgraphvizを使って"テスト結果に基づいた状態遷移図"を描いてみました。

　graphvizの描いてくれた図は明快ですね、ブロックコメント／ラインコメントから外に出る矢印がないことからコメント終端に絡むテストケースが足りてないことが明らかです。正しく動くか、そしてテストケースが十分かを確認することで、状態遷移設計が要求を満たすことをテスト／検証できます。

　このテストをパスすれば、残るはからっぽのアクションを埋め、各アクションがちゃんと動くかテストします。状態遷移が正しいことは検証済みなので、実装段階ではアクションのふるまいに注力できますね。

この記事は参考になりましたか？

印刷用を表示

ポスト

特集記事連載記事一覧: 開発者のための「WWDC 2024」関連発表まとめ

LeSSやSAFeなど、大規模アジャイルにおけるソフトウェア品質の課題とは？

【オンライン技術書読書会のはじめかた】完璧じゃなくていい、雑談の延長線で開催してみませんか...

もっと読む

この記事の著者: επιστημη（エピステーメー）

C++に首まで浸かったプログラマ。Microsoft MVP, Visual C++ (2004.01～2018.06) "だった"りわんくま同盟でたまにセッションスピーカやったり中国茶淹れてにわか茶...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この著者の最近の執筆記事