jcunit's blog

JCUnitの開発日誌（ログ）です。"その時点での"JCUnit作者の理解や考え、開発状況を日本語で書きます。

ConstraintManagerとIPO2TupleGenerator

開発日誌

IPOはテストケース(Tuple)内の因子(Factor)の水準(Level)を一個ずつ、すべての可能な組み合わせが網羅するように決めていくアルゴリズム。生成されるテストスイートは縦方向（テストケース数）と横方向（因子数）を必要に応じて交互に増加させながら成長していく。

大まかに言うと一番左のt個について可能な組み合わせをまず全部列挙する。この件数をHとしよう。
次にt+1個目をすでに決まったt個の右側にくっつける。このときその水準はできるだけt-wayカバレッジが上がるように選ぶ。もし、このときまでにすでにあるH個のテストケースだけでは可能なすべてのt-wayタプルを網羅できてなければ、網羅できていないt-wayタプルをもとにテストケースを増やしていく。
これを繰り返して全部の因子の処理が終わったらテストスイートの生成が完了するというわけだ。

タプル内のキーが全部出揃ってから制約検査を行うのは、生成されるテストスイートの品質や性能の観点で現実的ではない。
そこで、JCUnitでは中途半端な状態のタプルでもしようがないのでまずはConstraintManager#checkを使って検査を行うことにしている。

すると、ConstraintManager#checkが制約検査を行うにあたって必要な因子の水準が決まっていないということがありえる。
この場合、trueでもfalseでもないのでUndefinedSymbolを投げましょうというのがJCUnitの設計。
IPO2TupleGeneratorはUndefinedSymbolを検知した場合ひとまず別の因子の水準を決めて再びcheckメソッドにお伺いを立てることを繰り返す。

一応、そのへんのことをConstraintManager#checkメソッドのJavadocにも書いてあったのだが、わかりにくいところと間違い(例外クラス名)があったので、以下のように明確化する。

  /**
   * Returns {@code true} if the given tuple doesn't violate any known constraints.
   * In case tuple doesn't have sufficient attribute values to be evaluated,
   * a {@code UndefinedSymbol} will be thrown.
   * Otherwise, {@code false} should be returned.
   *
   * @param tuple A tuple to be evaluated.
   * @return {@code true} - The tuple doesn't violate any constraints managed by this object / {@code false} - The tuple DOES violate a constraint.
   * @throws com.github.dakusui.jcunit.exceptions.UndefinedSymbol Failed to evaluate the tuple for insufficient attribute(s).
   */
  boolean check(Tuple tuple) throws UndefinedSymbol;

この修正は次回のリリース(0.5.5)には含まれるようにする。なおこの部分に関する変更はドキュメントに対してだけのものであり、制約検査やテストケース生成の挙動に変化は生じない。

実を言えば制約が定義されたもとで効率的に t-wiseのテストスイート生成を行うアルゴリズムはホットな研究領域であり、制約検査とテストスイート生成を独立に行えることを前提としたこのインタフェース設計は野心的というか楽観的なものなのだ。

参考:
IWCT 2015 : Fourth International Workshop on Combinatorial Testing

IPOは非常に面白いアルゴリズムなのだが、制約をどのように取り扱うべきかということになると、こうやってややこしい問題が生じてくる。
そもそも、ある論理式を満たすタプルを見つけましょうってSAT問題そのものですよね。と。そこにさらにどういう順番で因子を処理するべきかとかそういう話が加わってくるわけだから非常に悩ましい。
t-wayでテストスイートを生成するアルゴリズムにはAETGというものもあり、一件のテストケースの全因子の水準をいっぺんに決めるやり方だ。この点ではおそらく制約処理機能を実装する上ではいくらかはやりやすいアルゴリズムと言える。

こんなチケットを先日作ったのは、そんな背景がある。

AETG algorithm support · Issue #17 · dakusui/jcunit · GitHub

JCUnit 0.5.4リリース。

TupleGeneratorを直接取り扱いたい人々が一定数いるように見受けられるので、そのためのクラスやメソッドを整理してみた。

        TupleGenerator tg = new TupleGenerator.Builder().setFactors(
            new Factors.Builder()
                .add("OS", "Windows", "Linux")
                .add("Browser", "Chrome", "Firefox")
                .add("Bits", "32", "64").build()
        ).build();
        for (Tuple each : tg) {
          ps.println(each);
        }

TupleGeneratorを明示的に指定するときはこう。

    TupleGenerator tg = new TupleGenerator.Builder(
        IPO2TupleGenerator.class, 
        ConstraintManager.DEFAULT_CONSTRAINT_MANAGER
    ).setFactors(new Factors.Builder()
        ...

その他の変更点は以下。

Enhancements

  1. Local constraints:
  2. Support overloading methods with the same number of arguments
  3. Multi-threading support

Fixed bugs

  1. Story objects are not refreshed before each test case is executed. Due to this issue, nested FSMs might not be tested when there is more than one test method in a test class.

JCUnit 0.5.1 リリース(更新)

（早速機能拡張をしてるので、10/5現在の最新版は0.5.4です。
JCUnit 0.5.4リリース。 - jcunit's blog
）

今回の目玉は何といってもFSM（有限状態機械）のサポートだ。github.com


ユーザがSUT(テスト対象ソフトウェア)を有限状態機械としてモデルすると、pairwiseを使って、カバレッジもよくて件数もそんなに多くないテストスイートを自動でつくってそのまま実行してくれるという（私にとって）夢のような機能だ。
まあ、ほんとにカバレッジが十分にいいかとかは、これからちゃんと評価するのだけれど。
実際にはテストケースの生成はpairwiseでなくても別によいので、JCUnitによるモデルベーステスティング(Model-based testing, MBT)のサポートと言ってもよい。

三月くらいにJCUnitによるFSMサポートを作っていたときはこんなもんちょっと頑張ればあっという間だろうと思っていたのだが、仕事が忙しくなったり、入れ子になった有限状態機械を取り扱う仕組みがなかなかよくならなかったりでずいぶんとてこずってしまった。

こつこつと作りつづけ、一応は形になったので、0.5.1としてリリースする。
てこずっただけあり、実用上（少なくとも自分に）必要な機能はこれで網羅できたと思う。ドキュメントも頑張って書いたので、以前に書いたブログのエントリよりもわかりやすいと思う。英語だけど。
mavenのcoordinateは以下。

    <dependency>
      <groupId>com.github.dakusui</groupId>
      <artifactId>jcunit</artifactId>
      <version>0.5.4</version>
    </dependency>

（この数日で早速バグフィックスや拡張を入れて0.5.4をリリースしているので、更新しました）

テストは整理して充実させる必要があるし、若干迷っている箇所もある。（といっても外部仕様に影響しそうなのは@ParametersSpecの仕様だけだが）
Future worksのセクションに書いた点のうちいくつかは0.5.xの間にサポートされるかもしれない。

なんにしても、0.5.xを使って実例を積み重ね、そののちに0.6.xをリリースすることにしたい。

思うにAnnotationは

雑感

MVCで言うならVのようなソフトウェアのプレゼンテーションとかUIとかを担う層とも言える。
モデルとビューを分離するのはビューへの変更は頻繁に起こることから来ていて、そしてそれはユーザの選好に大きく依存するからなわけだ。

するとアノテーションの体系はユーザの選好に基づいて組み立てられてしかるべき（と言えそう）なのだが、APIライブラリのインタフェースとしてアノテーションを使う以上、そんなことはできないよね。

アノテーションもクラスなので、モデルに現れるクラス名との衝突を回避するために自然な名前を使いにくいというのも困る。（無論パッケージが違うので全くできないということではないのだが、一つのファイル内でimport文によってFQCNを省略できる同名のクラスはひとつだけだ。）

世間の人々はどうして（どう考えて）いるのだろう。

再始動

前回のポストからずいぶん時間が経ってしまった。
FSMサポートについてのこれまでの設計を見直したいと思ったのと、他のことに興味を奪われていたためだ。

間は開いてしまったもののもうすぐ前回の続きを書けると思う。

JCUnitによる有限状態機械のテスト - 有限状態機械テストの方法(その3)

考えてみれば、ソフトウェアシステムというのは有限状態機械であり、ソフトウェアシステムの仕様を決めるとはその有限状態機械の仕様を決めることに他ならない。

と、いうことは有限状態機械の仕様からテストを自動的に生成して、それを自動的に実施できるなら、人間はソフトウェアシステム自体の設計と開発に集中してあとのことは計算機にやらせればよい、ということにならないだろうか？

なったらいいなあ。

今回のFSMサポートの目的はこの辺だ。
では、有限状態機械の仕様をどのようにJCUnitに伝えればよいだろうか？
ということでいよいよ、JCUnit上で如何にして有限状態機械を定義するかの解説に移る。

jcunit/FlyingSpaghettiMonsterTest.java at develop · dakusui/jcunit · GitHub

  public static enum Spec implements FSMSpec<FlyingSpaghettiMonster> {
    @StateSpec I {
      @Override public boolean check(FlyingSpaghettiMonster flyingSpaghettiMonster) {
        return flyingSpaghettiMonster.isReady();
      }

      @Override public Expectation<FlyingSpaghettiMonster> cook(FSM<FlyingSpaghettiMonster> fsm, String dish, String sauce) {
        return FSMUtils.valid(fsm, COOKED, CoreMatchers.startsWith("Cooking"));
      }
    },
    @StateSpec COOKED {
      @Override public boolean check(FlyingSpaghettiMonster flyingSpaghettiMonster) {
        return flyingSpaghettiMonster.isReady();
      }

      @Override public Expectation<FlyingSpaghettiMonster> eat(FSM<FlyingSpaghettiMonster> fsm) {
        return FSMUtils.valid(fsm, COOKED, CoreMatchers.containsString("yummy"));
      }

      @Override public Expectation<FlyingSpaghettiMonster> cook(FSM<FlyingSpaghettiMonster> fsm, String dish, String sauce) {
        return FSMUtils.valid(fsm, COOKED, CoreMatchers.startsWith("Cooking"));
      }
    },;


    @ActionSpec public Expectation<FlyingSpaghettiMonster> cook(FSM<FlyingSpaghettiMonster> fsm, String pasta, String sauce) {
      return FSMUtils.invalid();
    }

    @ParametersSpec public static final Object[][] cook = new Object[][] {
        { "spaghetti", "spaghettini" },
        { "peperoncino", "carbonara", "meat sauce" },
    };

    @ActionSpec public Expectation<FlyingSpaghettiMonster> eat(FSM<FlyingSpaghettiMonster> fsm) {
      return FSMUtils.invalid();
    }
  }

途中をすっとばすならば、上記の内部クラスSpecがJCUnitに渡す有限状態機械の仕様そのものだ。
JCUnitはこのSpecの定義内容を解析し、テストを生成し、実行する。

Specは別に内部クラスでなくてもよいし、enumでなくてもよいが以下の条件を満たす必要がある。

  1. SUTは任意のクラス。
  2. FSMSpecインタフェースを実装する必要がある。
  3. 状態を定義するには、フィールドを定義し、これにStateSpecアノテーションを付す。これらのフィールドは以下の条件を満たす必要がある。
    1. publicであること
    2. staticであること
    3. finalであること
    4. nullではないこと
    5. そのクラスのオブジェクトであること。(上述の例で言うとSpecクラスのオブジェクト。enumの場合には自動的にそうなる)
    6. checkメソッドは引数に与えられるSUTオブジェクトが、それが表す状態に適合しているか検査し、適合するならtrue、しないならfalseを返すこと
    7. "I"という名前のものがあること。初期状態として使われる。
  4. 状態遷移関数を定義するにはメソッドを定義し、これにActionSpecアノテーションを付す。これにより、SUTにある同名のメソッドが必要なタイミングで自動的に呼ばれるようになる。上掲の例で言うと、"cook"メソッドと"eat"メソッド。これらのメソッドは以下の条件を満たす必要がある。
    1. 第一引数はFSMクラスのオブジェクト
    2. 第二引数以降は、SUTの同名のメソッドに渡すべき引数。
    3. 名前が同じメソッドは一つしか使えない。（オーバーロードできない）
    4. 必ずExpectationオブジェクトを返すこと。このオブジェクトは、そのメソッドが実行された時に期待される戻り値や例外、実行後に遷移するべき状態が格納されたオブジェクトである。
  5. 上述の状態遷移関数に渡す引数がある時には、同名のフィールドを定義し、ParamsSpecアノテーションを付す。上掲の例で言うと、"cook"フィールド。このフィールドは以下の条件を満たす必要がある。
    1. publicであること
    2. staticであること
    3. finalであること
    4. nullではないこと
    5. Objectオブジェクトの値を持つこと。
    6. 配列の長さが、SUTの同名のメソッドの引数と同じであること。
    7. 配列の各要素は、nullではないこと。
    8. 配列の各要素は、それぞれSUTの同名のメソッドに与える引数の候補になっていること。この例で言うと、FlyingSpaghttiMonster#cookの第一引数にはspaghettiまたはspaghettini、第二引数にはcarbonara, peperoncino, またはmeat sauceが渡されるようにテストケースが生成される。

うーん。
頑張ってシンプルにしたんだけど、書き下してみると、けっこうややこしいなあ。
なんにしても、有限状態機械を定義するのには必要な情報だし、なれれば難しくはないと思う（多分）

。。続きます。