UMLの状態遷移図をC言語のStateパターンで実装&単体テストしてみる

UMLの状態遷移図(ステートマシン図/ステートチャート図)の実装

サンプルとして、こちらの図11を実装した。
http://labo.mamezou.com/special/sp_002/sp_002_003.html

最上位の状態は「停止中」と「運転中」の2つの状態。「運転中」はコンポジット状態(入れ子のある状態)であり、サブ状態として「冷房」「暖房」「除湿」の3つの状態を持つ。

最上位の初期状態は停止中で、サブ状態の初期状態は冷房。ただし、運転中から停止中に戻る時にサブ状態は記憶され、次回運転中状態になった時は前回のサブ状態になる。

イベントは「運転開始」「運転停止」「運転切替」の3つ。

状態遷移図を実装する方法で一番簡単なのは、状態変数をswitch文で分岐する方法だと思うけど、ここではGoFのデザインパターンのStateパターンを参考にして実装してみた。
ソースのリポジトリは以下。
https://bitbucket.org/katono/cstatepattern

FSM.h

#ifndef FSM_H_INCLUDED
#define FSM_H_INCLUDED

struct State;

/* 有限状態機械(FSM)クラス */
typedef struct FSM {
	const struct State *current_state;    /* 現在の状態 */
	const struct State *current_substate; /* 現在のサブ状態 */
	const struct State *last_substate;    /* サブ状態の前回の状態 */
} FSM;
void FSM_init(FSM *self);

void FSM_run(FSM *self);    /* 運転開始イベント */
void FSM_stop(FSM *self);   /* 運転停止イベント */
void FSM_switch(FSM *self); /* 運転切替イベント */

/* 状態遷移 */
void FSM_change_state(FSM *self, const struct State *new_state);
/* 状態遷移(サブ状態用) */
void FSM_change_substate(FSM *self, const struct State *new_state);

#endif /* FSM_H_INCLUDED */

有限状態機械(FSM)クラス定義。
FSMクラスはGoFのStateパターンでContextクラスに相当する。
3つのイベントはFSM_run(), FSM_stop(), FSM_switch()で処理される。

現在の状態を示す変数と状態遷移関数は、最上位の状態とサブ状態のそれぞれに必要となる。

C言語だからグローバルになってしまうけど、FSMのメンバ変数とFSM_change_state(), FSM_change_substate()はStateクラスのみに公開しているつもり。

State.h

#ifndef STATE_H_INCLUDED
#define STATE_H_INCLUDED

#include "FSM.h"

/* 状態クラス */
typedef struct State {
	void (*entry)(FSM *fsm);        /* 入状イベント */
	void (*exit)(FSM *fsm);         /* 出状イベント */
	void (*event_run)(FSM *fsm);    /* 運転開始イベント */
	void (*event_stop)(FSM *fsm);   /* 運転停止イベント */
	void (*event_switch)(FSM *fsm); /* 運転切替イベント */
} State;
void State_init(FSM *fsm);

#endif /* STATE_H_INCLUDED */

状態(State)クラス定義。
Stateクラスは各イベントの仮想関数(関数ポインタ)を持つだけ。状態に入ったときに実行されるentryイベントと状態から出たときに実行されるexitイベントにも対応できるようにしておく。

FSM.c

#include <stdio.h>
#include "FSM.h"
#include "State.h"

void FSM_init(FSM *self)
{
	State_init(self);
}

/* 運転開始イベント */
void FSM_run(FSM *self)
{
	if (self->current_state && self->current_state->event_run) {
		printf("Event: Run\n");
		self->current_state->event_run(self);
	}
}

/* 運転停止イベント */
void FSM_stop(FSM *self)
{
	if (self->current_state && self->current_state->event_stop) {
		printf("Event: Stop\n");
		self->current_state->event_stop(self);
	}
}

/* 運転切替イベント */
void FSM_switch(FSM *self)
{
	if (self->current_substate && self->current_substate->event_switch) {
		printf("Event: Switch\n");
		self->current_substate->event_switch(self);
	}
}

/* 状態遷移(共通) */
static void change_state_common(FSM *self, const State **current, const State *new_state)
{
	if (*current && (*current)->exit) {
		(*current)->exit(self);
	}
	*current = new_state;
	if (new_state && new_state->entry) {
		new_state->entry(self);
	}
}

/* 状態遷移 */
void FSM_change_state(FSM *self, const State *new_state)
{
	change_state_common(self, &self->current_state, new_state);
}

/* 状態遷移(サブ状態用) */
void FSM_change_substate(FSM *self, const State *new_state)
{
	change_state_common(self, &self->current_substate, new_state);
}

FSMクラスの実装。
各イベントの処理は、現在の状態の仮想関数を呼び出す。

状態遷移関数は現在の状態のexitを呼び出し、現在の状態を更新して、新しい状態のentryを呼び出す。FSM_change_state()とFSM_change_substate()は使用するcurrent_*stateが違うだけで同じ処理なので共通化している。

State.c

#include <stdio.h>
#include "State.h"

static void StateStopped_run(FSM *fsm);

static void StateRunning_entry(FSM *fsm);
static void StateRunning_exit(FSM *fsm);
static void StateRunning_stop(FSM *fsm);

/* 各Stateの唯一のオブジェクト */
static const State state_Stopped = { 0                  , 0                 , StateStopped_run , 0                 , 0 };
static const State state_Running = { StateRunning_entry , StateRunning_exit , 0                , StateRunning_stop , 0 };

/* 初期状態の設定 */
void State_init(FSM *fsm)
{
	void init_last_substate(FSM *fsm);
	fsm->current_state = &state_Stopped;
	fsm->current_substate = 0; /* NULLだと何のイベントも処理しない */
	init_last_substate(fsm);
}

/* 
 * 停止中状態
 */

/* 運転開始イベント */
static void StateStopped_run(FSM *fsm)
{
	printf("  State: Stopped -> Running\n");
	FSM_change_state(fsm, &state_Running);
}


/* 
 * 運転中状態(コンポジット状態)
 */

/* 入状イベント */
static void StateRunning_entry(FSM *fsm)
{
	/* サブ状態をNULLから前回の状態に遷移(サブ状態のentryがあれば呼ばれる) */
	FSM_change_substate(fsm, fsm->last_substate);
}

/* 出状イベント */
static void StateRunning_exit(FSM *fsm)
{
	/* 現在のサブ状態を保存 */
	fsm->last_substate = fsm->current_substate;
	/* 運転中状態以外の時にサブ状態へイベントが飛ばないようにするために、
	 * サブ状態をNULLにする(サブ状態のexitがあれば呼ばれる) */
	FSM_change_substate(fsm, 0);
}

/* 運転停止イベント */
static void StateRunning_stop(FSM *fsm)
{
	printf("  State: Running -> Stopped\n");
	FSM_change_state(fsm, &state_Stopped);
}

最上位の2つのStateクラスの実装。
Stateクラスはデータを持たないのでstatic constによるシングルトンでオブジェクトを定義する。ここで定義したオブジェクトがGoFのConcreteStateクラスのオブジェクトに相当する。Stateオブジェクトの定義で0が指定されたイベントは、そのイベントが発生しても何も処理をしない。シングルトンなのでもしデータの操作をする必要がある場合はStateには持たせずFSMのメンバに追加する。

イベントの関数の中ではアクションや状態遷移を実装する。

状態遷移はFSM_change_state()で行う。FSM_change_state()の後はもう状態遷移し終わっているので何もせずに関数から戻ること。

コンポジット状態のentryとexitでは、サブ状態の設定をすること。

SubState.c

#include <stdio.h>
#include "State.h"

static void SubStateCooling_switch(FSM *fsm);
static void SubStateWarming_switch(FSM *fsm);
static void SubStateDehumidifying_switch(FSM *fsm);

/* 各Stateの唯一のオブジェクト */
static const State substate_Cooling       = { 0, 0, 0, 0 ,SubStateCooling_switch };
static const State substate_Warming       = { 0, 0, 0, 0 ,SubStateWarming_switch };
static const State substate_Dehumidifying = { 0, 0, 0, 0 ,SubStateDehumidifying_switch };

/* サブ状態の初期状態の設定 */
void init_last_substate(FSM *fsm)
{
	fsm->last_substate = &substate_Cooling;
}

/* 
 * 冷房状態
 */

/* 運転切替イベント */
static void SubStateCooling_switch(FSM *fsm)
{
	printf("  SubState: Cooling -> Warming\n");
	FSM_change_substate(fsm, &substate_Warming);
}

/* 
 * 暖房状態
 */

/* 運転切替イベント */
static void SubStateWarming_switch(FSM *fsm)
{
	printf("  SubState: Warming -> Dehumidifying\n");
	FSM_change_substate(fsm, &substate_Dehumidifying);
}

/* 
 * 除湿状態
 */

/* 運転切替イベント */
static void SubStateDehumidifying_switch(FSM *fsm)
{
	printf("  SubState: Dehumidifying -> Cooling\n");
	FSM_change_substate(fsm, &substate_Cooling);
}

サブ状態の3つのStateクラスの実装。
サブ状態のオブジェクトにもStateを使う。
Stateオブジェクトやイベントの実装方法は最上位の場合と同じだが、サブ状態では状態遷移には専用のFSM_change_substate()を使う。

サブ状態の実装からは上位の状態について何も気にしなくていい。

main.c

#include <stdio.h>
#include "FSM.h"

int main(void)
{
	int c;
	FSM fsm;
	FSM_init(&fsm);

	while ((c = getchar()) != EOF) {
		switch (c) {
		case 'x':
			FSM_run(&fsm);
			break;
		case 'y':
			FSM_stop(&fsm);
			break;
		case 'z':
			FSM_switch(&fsm);
			break;
		default:
			break;
		}
	}
	return 0;
}

FSMクラスを使用したmain関数。標準入力からx, y, zの入力がそれぞれのイベントになる。
現在の状態を気にせずイベントを通知できる。

単体テスト

単体テストはPCUnitを使った。
どの状態の時にどのイベントが発生したらどの状態に遷移するか、のテストをする。
"単体"テストと言ってもFSM.c, State.c, SubState.cそれぞれのソースを別々にテストするわけじゃなく、これらをまとめて1つのFSMクラスをテストするという扱い。

TODO

テストしているのは状態遷移のテストだけで、アクションのテストと状態遷移時のentry, exitが正しく呼ばれているかのテストはできてない。この方法はそのうち考える。

FSMTest.c

#include "PCUnit/PCUnit.h"
#include "../FSM.h"
#include "../State.h"

/* static変数を使うためにソースをインクルードする */
#include "../State.c"
#include "../SubState.c"

static FSM fsm;

static int setup(void)
{
	FSM_init(&fsm);
	return 0;
}


static void test_init(void)
{
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);
}

static void test_run(void)
{
	/* 変化しない */
	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);

	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	/* 変化しない */
	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	/* 変化しない */
	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);
}

static void test_stop(void)
{
	/* 変化しない */
	FSM_stop(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);

	/* 変化しない */
	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);

	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	FSM_stop(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);
}

static void test_switch(void)
{
	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Warming, fsm.current_substate);

	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Dehumidifying, fsm.current_substate);

	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	FSM_stop(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);
}

static void test_history(void)
{
	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Warming, fsm.current_substate);

	FSM_stop(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);

	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Warming, fsm.current_substate);

	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Dehumidifying, fsm.current_substate);

	FSM_stop(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);

	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Dehumidifying, fsm.current_substate);

	FSM_switch(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

	FSM_stop(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Stopped, fsm.current_state);
	PCU_ASSERT_PTR_NULL(fsm.current_substate);

	FSM_run(&fsm);
	PCU_ASSERT_PTR_EQUAL(&state_Running, fsm.current_state);
	PCU_ASSERT_PTR_EQUAL(&substate_Cooling, fsm.current_substate);

}

PCU_Suite *FSMTest_suite(void)
{
	static PCU_Test tests[] = {
		PCU_TEST(test_init),
		PCU_TEST(test_run),
		PCU_TEST(test_stop),
		PCU_TEST(test_switch),
		PCU_TEST(test_history),
	};
	static PCU_Suite suite = {
		"FSMTest", tests, sizeof tests / sizeof tests[0], setup
	};
	return &suite;
}

状態遷移の単体テストは、FSMクラスに現在の状態を取得するAPIがないため、内部実装に依存したテストになってしまった。本来ユーザー側にはprivateにするべきFSMクラスのメンバ変数にアクセスしている。
また、シングルトンのStateオブジェクトはstatic変数なのでテストコードのファイルからアクセスできない。苦肉の策として、「ソースファイル(.c)をインクルードする」という手段を使った。この方法はstaticの変数や関数の名前が衝突する場合は使えない。
テストコードの保守性が悪い。もっといいやり方はあるだろうか？

その他の状態遷移の実装例

ガード条件による状態遷移の分岐

A状態の時にXイベントが発生したら、data >= 100ならB状態へ遷移し、50 <= data < 100ならC状態へ遷移し、そうでなければ遷移しない、という例。

static void StateA_eventX(FSM *fsm)
{
	/* アクション */
	...

	if (fsm->data >= 100) {
		FSM_change_state(fsm, &state_B);
		return;
	} else if (fsm->data >= 50) {
		FSM_change_state(fsm, &state_C);
		return;
	}
}

普通にif文で条件分岐すればいい。
returnを書いているのは、状態遷移後この関数内では何の処理も行わないようにするため。(マクロにして常にreturnするようにしてもいいかも。#define FSM_CHANGE_STATE(f, s) do { FSM_change_state(f, s); return; } while (0) みたいに)

自己遷移

A状態の時にXイベントが発生したら、いったんA状態から出て、またA状態へ遷移する、という例。

static void StateA_eventX(FSM *fsm)
{
	/* アクション */
	...

	FSM_change_state(fsm, &state_A);
}

普通の状態遷移のやり方と同じ。exitとentryも呼ばれる。

内部遷移

A状態の時にXイベントが発生したら、状態遷移はせずアクションのみ実行する、という例。

static void StateA_eventX(FSM *fsm)
{
	/* アクション */
	...

	/* FSM_change_state()を呼ばない */
}

イベントの関数の中でアクションを実行するのみ。FSM_change_state()を呼ばない。

自動遷移

ある状態からA状態に遷移したら何のイベントも待たずに自動的にB状態へ遷移する、という例。

static void StateA_entry(FSM *fsm)
{
	/* アクション */
	...

	FSM_change_state(fsm, &state_B);
}

entryの中でFSM_change_state()を呼び出せばOK。ガード条件との組み合わせも可。

スタックオーバーフローを引き起こすので以下のように自動遷移の無限ループに陥らないように注意。

/* 再帰的にA->B->A->B->A...と遷移してしまうのでNG */
static void StateA_entry(FSM *fsm)
{
	FSM_change_state(fsm, &state_B);
}
static void StateB_entry(FSM *fsm)
{
	FSM_change_state(fsm, &state_A);
}

引数のあるイベント

Xイベント発生時に何らかのデータを渡したい、という例。

void FSM_eventX(FSM *self, const unsigned char *data, size_t num);

typedef struct State {
	void (*eventX)(FSM *fsm, const unsigned char *data, size_t num);
} State;

イベント関数に任意の引数をつけるだけでOK。Stateクラスの仮想関数にも同じ引数を追加する。

サブ状態が最終状態へ遷移→コンポジット状態が完了遷移

サブ状態CがイベントXが発生して最終状態へ遷移すると、自動的にコンポジット状態Aが状態Bに遷移する(完了遷移という)例

/* サブ状態に最終状態を追加する。最終状態では何もできないのでメンバはすべて0 */
static const State substate_Final = {0};

/* サブ状態が最終状態かどうか判定する関数を追加 */
int SubState_is_final(FSM *fsm)
{
	return fsm->current_substate == &substate_Final;
}

/* 最終状態に遷移するイベント処理を追加 */
static void SubStateC_eventX(FSM *fsm)
{
	FSM_change_substate(fsm, &substate_Final);
}

typedef struct State {
	...
	void (*event_completion)(FSM *fsm); /* 完了遷移を発生させるための完了イベントを追加 */
} State;

static void StateA_event_complettion(FSM *fsm)
{
	/* 完了遷移 */
	FSM_change_state(fsm, &state_B);
}

void FSM_eventX(FSM *self)
{
	if (self->current_substate && self->current_substate->eventX) {
		self->current_substate->eventX(self);
		if (SubState_is_final(self) && self->current_state->event_completion) {
			/* サブ状態のXイベントを処理後、最終状態になっていたら完了イベントを発生させる */
			self->current_state->event_completion(self);
		}
	}
}