implyとequivalent及びBranch coverageとDecision coverage

Twitterで話していたがまとめて話さないと伝わらないので、まとめてみる

ここに、Branch/Decision Testingという記事があって、冒頭に

For components with one entry point 100% Branch Coverage is equivalent to 100% Decision Coverage (入り口が一つのコンポーネントに対しては100%BCは100%DCと等しい)

と書いてある。

equivalentとは?
等しいのだからBDが100%ならDCも100%になりその逆も成立する。等価性には対称律が成立する。

入り口が複数あるとは?
構造化プログラム言語を使っていると関数の入り口は一つに決まっているが、昔のFortranのentry文を使うとサブルーチンの入り口を複数作ることができる。今でもOSのディスパッチャ等はマルチエントリの関数として実装されている。

この様な、プログラムでは100% Branch Coverage is equivalent to 100% Decision Coverageでは無くなる。

これとは別に


「デシジョンカバレッジとブランチカバレッジはお互いに、"A implies B"と定義されています。なので"A=B"となりますが、・・・」

と言うつぶやきがあり、これは違うでしょうと言ったのだけれど上の話と混ざってしまって140字では伝わらない。



implyとは?
implyとequivalentは違う。implyは片方向で、equivalentは両方向である。A implies B and B implies Aの時にequivalentと言って良い。これが対称律だ。

つまり

100%DC = 100%BC
DC⇒BC

は成立するが、

DC=BC

は成立しない。ここでBCと表しているのは、Branch/Decision Testingという記事で言えば

BC = {
B1 -> B2
B2 -> B3
B2 -> B9
B3 -> B4
B3 -> B5
B4 -> B8
B5 -> B6
B5 -> B7
B6 -> B8
B8 -> B2
}


と言う制御ブロック間の実行順序対の集合である。これは、元のプログラムのフローグラフの辺の集合として得ることができる。

一方、DCの方はプログラム内の論理判断の結果なので

DC = {

B2 -> B3

B2 -> B9

B3 -> B4

B3 -> B5

B5 -> B6

B5 -> B7

}

となる。従って

DC⇒BC

が成立していることが分かる。これは、DCの任意の要素を持ってくるとそれはBCの要素にもなっていると言う意味である。DCの要素ならばBCの要素でもある。これを省略して「DCならばBCである」と言うこともある。また

BC⇒DC

が成立していないことも分かる。これで、話は終わりかも知れないが、それなら100%DCだけど100%BCにならない例を見せてみろと尤もな突っ込みがあった。これは既に、シングルエントリの場合には、反例はないと言っているので、マルチエントリの場合を考えれば良いので、先のフローグラフの途中から実行を開始するようなパスを追加すれば良い。

だいたい
implyを暗黙に・・・等という訳の分からない日本語にするのが良くない。ことばを置き換えただけで分かったつもりになってしまう。

「ならば」と等価の区別はきっちり付けないといけない。アリバイがないから犯人にされてしまう世の中にはなって欲しくない。

カバレッジは幾つもあるが、そのカバレッジが定義する全体集合を実際に手で作って見れば色々なものが見えてくる。面倒くさいが実際に集合を作ってみて包含関係を見れば一目瞭然である。