2015-10-26

0.5.5リリース

JUnit 開発日誌

なんとかかんとか、0.5.5をリリースした。発端は

uehaj.hatenablog.com

JCUnitが持っているプリミティブ用のデフォルト値を外部から取りやすいようにするというだけのことだったのだが、プラグインのインタフェースがあんまりよろしくないから変えないと、とか、この際だからRunnerもユーザが使えるようにするか、とかなってずいぶん手間取ってしまった。

MavenのCoordinateは以下のとおり。

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

リリースノートにも書いたが、@FactorFieldの静的インナークラスDefaultLevelsにintLevels、doubleLevels等のメソッドを作ったのでそこからJCUnitのビルトインされたデフォルト値がとれる。

ということで、フィードバックをお待ちしております。>uehajさん。

その他の変更は以下の通り。詳しくはリリースノートを見てほしい。

Issue-#21: Organize documentation
Issue-#22: Expose default values of @FactorField
Issue-#23: Separate annotation system from the other parts of JCUnit

2015-10-25

JCUnitを支える技術、あるいは再帰もループも用いない順列・組み合わせ列挙のアルゴリズム

開発日誌

今回の話はレポートで組み合わせとか順列の列挙をするプログラムを作る課題をやってる学生さんには面白い話かもしれない。

JCUnitは内部的にcombinatoradix(旧称enumerator)と呼ばれる私が作ったライブラリを使っている。

github.com

JCUnitは性質上、かなりヘビーに組み合わせや順列や直積の列挙を行う。そこで、専用の組み合わせ列挙の仕組みを持っている。もちろん、誰かが作ったライブラリを利用してもいいのだがそうしなかった理由は２つある。

そもそも外部への依存関係は最小にする必要がある。外部ライブラリを利用すると、そのライブラリ自体のテストにJCUnitが使えなくなるのはもとより、そのライブラリを使用した製品のテストの際にライブラリバージョンによる挙動の違いにより、テスト結果が変化する虞がある。
組み合わせを列挙してくれるライブラリは多くあるが、その際に「どのような順番で列挙するか」が明確なものは見つけられなかった。あるかもしれないが、列挙される要素の集合にa.equals(b)になるような組があった場合の挙動がどうなるか？など不安が多い。

JCUnitの場合、どんな順番で列挙がされるかは非常に重要で、これがないとテストの再現性が損なわれる。

combinatoradixは、「階乗進数」という特殊な記数法を使って、順列の列挙を行う。[1] 5個の要素から3個を選んで並べるとき、そのやり方は5P3=60通りだ。この時、下からひと桁目は0-4（5進数）、二桁目は0-3(4進数)、三桁目は0-2(3進数)にすると0-234までで60通りの数を表現できる。

2nd	1st	0th
0	0	0
1	1	1
2	2	2
(n/a)	3	3
(n/a)	(n/a)	4

         0   1   2   3    4
        10  11  12  13   14
        20  21  22  23   24
        30  31  32  33   34
       100 101 102 103  104
       110 111 112 113  114
       120 121 122 123  124
       130 131 132 133  134
       200 201 202 203  204
       210 211 212 213  214
       220 221 222 223  224
       230 231 232 233  234

記号[A,B,C,D,E]から3個を取る順列をこの60個の数字に割り当てる。割り当て方だが、下から順に、その桁の数字に対応する要素を取りさってゆけば良い。例えば。211なら

    0th = 1:   [A,B,C,D,E] -> "B" (残り:[A,C,D,E])

    1st = 1:   [A,C,D,E] -> "C" (残り:[A,D,E])

    2nd = 2:   [A,D,E] -> "E" (残り:[A,D])

つまり[B,C,E]が対応する値となる。

似た様な（しかしもう少し複雑な）記数法を考えると、組み合わせや重複を許す組み合わせについて同じことができる。

この方法は数の計算と要素の対応付けを行うので、可能な組み合わせをすべて列挙するだけなら、再起やループを使ったほうがずっと早いはずだ。しかし、際立った特徴がある。

例えば「AからZの文字のうち異なる10文字からなる単語を作り、それらを辞書順にならべたときに30億22番目にある単語はなにか？」という問に答えるのは1マイクロ秒くらいでできる。最初からじゅんじゅんにたどっていく必要がないので。この性質は大量の組み合わせを分散処理や並列処理で高速化して処理したい場合に有効なはずだ。つまり10億通りの組み合わせがあることがわかっていて（100P3とか1000C4とか簡単に公式で求まる）それぞれについて何らかの処理を行いたいのなら、各ノードはその組み合わせの総数（100P3とか1000C4とか）までの数のうち、ノード数で割った余りが自分のノード番号に等しいものだけを処理すればよいのだ。

[1] 偉そうに書いてしまったが、この方法を考えついたあとに誰かがすでにやってそうなもんだと思い調べてみてこういう名前が付いているの知った。不勉強を恥じる次第

2015-10-21

Pluginインタフェースの整理

開発日誌

こちらのエントリでご紹介いただいたときに「デフォルトで設定されている各型ごとの水準一覧を取る手段がない」という指摘も頂いた。

uehaj.hatenablog.com

それ自体は、なんとかなりそうで、難しいものでもないのでこんなチケットを作った。

github.com

で、こんなふうに

  class DefaultValues {
    public static final DefaultValues INSTANCE = new DefaultValues();

    @FactorField
    public final Object defaultValues = null;

    private DefaultValues() {
    }

    public boolean[] booleanLevels() {
      return get().booleanLevels();
    }

    public byte[] byteLevels() {
      return get().byteLevels();
    }

    public char[] charLevels() {
      return get().charLevels();
    }
    // 大体こんな雰囲気になるとは思うが、最終的には変更になりそうなので、注意。
  }

jcunit/FactorField.java at 0.5.x-develop · dakusui/jcunit · GitHub

すればよかろうと思う。が、LevelsProviderプラグインのインタフェースもついでに見直そうと思うとこれがはまるはまる。しかし、0.6.0は安定版にしたいので、今、綺麗にするしかない。

0.5.5のRelease contentsはこのIssue-#22、各プラグインインタフェースの整理、あとはドキュメントの整理ってあたりになるかなあ。今週末に出したいところだ。

2015-10-21

DefaultLevelsProvider

開発日誌

ダメだコイツ。解体しないと。つうかLevelsProviderのインタフェース自体を見直さないと。

2015-10-17

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

2015-10-05

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

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

Fixed bugs

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.

2015-09-28

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をリリースすることにしたい。