完全な仕様に基づいたテスト

以下の文章はこちらの記事を翻訳したものです。https://github.com/HypothesisWorks/hypothesis/blob/master/HypothesisWorks.github.io/_posts/2016-06-30-tests-as-complete-specifications.md

時折、結果がいくつかのシンプルな特性によって完全に定義される問題に出会うことがあります。

これが簡単だとは限りません。実のところ、多くのこのタイプの問題は非常に複雑な実装を必要とします。

しかし、これはテストが容易であることを意味します。どのように行うかを見てみましょう。

ここでは、バイナリサーチの問題について考えてみます。具体的には、左に寄せたバイナリサーチに焦点を当てます。つまり、ソートされたリストと特定の値が与えられたとき、その値を挿入してもリストがソートされた状態を維持する最小のインデックスを見つけたいというものです。

この問題には以下のような特性があります：

1. binary_searchは常に値を挿入するのに適切なインデックスを返す必要があります。
2. そのインデックスに値を挿入すると、リストはソートされた状態でなければなりません。
3. より小さいインデックスに値を挿入すると、リストはソートされていない状態になる必要があります。

Hypothesisを使って、これらの特性のテストを記述することができます。

以下にそのコード例を示します：

from hypothesis import given, strategies as st

@given(st.lists(st.integers()).map(sorted), st.integers())
def test_binary_search_gives_valid_index(ls, v):
    i = binary_search(ls, v)
    assert 0 <= i <= len(ls)

@given(st.lists(st.integers()).map(sorted), st.integers())
def test_inserting_at_binary_search_remains_sorted(ls, v):
    i = binary_search(ls, v)
    ls.insert(i, v)
    assert sorted(ls) == ls

@given(st.lists(st.integers()).map(sorted), st.integers())
def test_inserting_at_smaller_index_gives_unsorted(ls, v):
    for i in range(binary_search(ls, v)):
        ls2 = list(ls)
        ls2.insert(i, v)
        assert sorted(ls2) != ls2

これらのテストがパスする場合、実装は完全に正しいと言えます。これらはbinary_search関数の仕様を正確に捉えているため、十分なはずです。

しかし、大抵の場合これで十分ですが、プロパティベースドテストには時々問題が生じることがあります。それは、すべてのバグを十分に高い確率で検出しないことです。

これは、テストと数学的証明との違いです。証明はこれらの特性が常に成立することを保証しますが、テストはチェックした範囲でのみ成立することを保証します。Hypothesisを使用したテストは、手書きのテストよりもはるかに広範囲をチェックしますが、それでも有限の例のセットに限られます。

次に示すのは、バイナリサーチの実装例です：

def binary_search(list, value):
    if not list:
        return 0
    if value > list[-1]:
        return len(list)
    if value <= list[0]:
        return 0
    lo = 0
    hi = len(list) - 1
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        pivot = list[mid]
        if value < pivot:
            hi = mid
        elif value == pivot:
            return mid
        else:
            lo = mid
    return hi

このコードは、ピボットインデックスの値がちょうど求めている値と一致した場合、すぐにその値を返すという一般的な処理を行います。しかしこの場合、その処理は間違っています。なぜなら、常に最小の適切なインデックスを見つけるべきという性質に反するため、第三のテストが失敗するはずです。

実際に、テストを何度か実行すると最終的に失敗します：

Falsifying example: test_inserting_at_smaller_index_gives_unsorted(
    ls=[0, 1, 1, 1, 1], v=1
)

（または、ls=[-1, 0, 0, 0, 0], v=0 という結果が出ることもあります）

しかし、私がテストを実行すると、通常は最初の試行では失敗しません。失敗するまでに、2回から5回の試行が必要となります。この誤った動作が発生するためには、valueがリストlsに少なくとも2回現れ、そのうちの1つが最初のインデックスでない場合にプロセスの途中でmidとして選ばれるなど、特定の条件が必要です。Hypothesisはこれが起こる確率を高めるためにいくつかの工夫をしていますが、それでも完全ではありません。

もちろん、一度失敗が始まると、Hypothesisのテストデータベースが作動し、バグが修正されるまでテストは失敗し続けます。しかし、低確率の失敗は問題を引き起こす可能性があります。特にステートフルテストを使用している場合、検索スペースが非常に大きいため、多くの低確率のバグが存在する可能性があります。

幸いなことに、このケースではバグを発見する可能性が高い追加のテストを記述することができます。

次のテストを考えてみましょう：

@given(st.lists(st.integers()).map(sorted), st.integers())
def test_inserting_at_result_point_and_searching_again(ls, v):
    i = binary_search(ls, v)
    ls.insert(i, v)
    assert binary_search(ls, v) == i

ここでの考え方は、検索を行い、そのインデックスに値を挿入し、もう一度検索することで、挿入ポイントが移動していないことを確認することです。再びそこに挿入すると、リストは依然としてソートされた状態になり、より早い位置に挿入すると、依然としてソートされていないリストになるはずなので、これは依然として同じ挿入ポイントでなければなりません（これは、以前にオプティマイザーをテストするために使用したアプローチを少し思い出させるかもしれません）。このテストはかなり一貫して失敗します。なぜなら、それは特定の重複を見つけることに頼っていないからです。代わりに、意図的に問題が発生しそうな状況を作り出します。

したがって、結論として：

1. 問題が完全に定義されると、Hypothesisを使って自然なテストを容易に記述することができます。
2. しかし、これはテストの始まりであって終わりではありません。ソフトウェアをテストする他の興味深い方法についても模索する必要があるでしょう。