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