ルールベースドステートフルテスティング
0
以下の文章はこちらの記事を翻訳したものです: https://github.com/HypothesisWorks/hypothesis/blob/master/HypothesisWorks.github.io/_posts/2016-04-19-rule-based-stateful-testing.md
Hypothesisの標準的なテストメカニズムは、データを直接的に扱う際に非常に有効です。しかし、もし私たちが複雑なステートフルなシステムやオブジェクトのテストを行いたい場合はどうすれば良いでしょうか？
この記事では、Hypothesisのルールベースドステートマシンを用いて、単なるデータではなくステートフルなオブジェクトを使用した包括的なプログラムのテスト方法を探ります。これにより、オブジェクトが受け取るデータのテストで得られる利点を、オブジェクトの振る舞いをテストする際にも享受できます。
ここで使用するステートフルなシステムのモデルは、バイナリヒープで実装された優先度付きキューです。
以下の関数を使用して、ヒープ操作を行います：
newheap()- 新しい空のヒープを生成します。heappush(heap, value)- 指定された値をヒープに追加します。heappop(heap)- ヒープから現在の最小値を取り出し、それを返します。ヒープが空の場合はエラーが発生します。heapempty(heap)- ヒープが空の場合はTrueを、そうでない場合はFalseを返します。
これらの操作に対するPythonでの実装は以下の通りです：
def heapnew():
return []
def heapempty(heap):
return not heap
def heappush(heap, value):
heap.append(value)
index = len(heap) - 1
while index > 0:
parent = (index - 1) // 2
if heap[parent] > heap[index]:
heap[parent], heap[index] = heap[index], heap[parent]
index = parent
else:
break
def heappop(heap):
return heap.pop(0)
注意：この実装には問題があります。heappop関数は、ヒープから最小要素を取り出しますが、その後ヒープの再バランスを行わず、ヒープが不正な状態になる可能性があります。」
以下のようなテストを@givenデコレータを使って簡単に行うことができます：
from hypothesis import given
from hypothesis.strategies import integers, lists
@given(lists(integers()))
def test_pop_in_sorted_order(ls):
h = heapnew()
for l in ls:
heappush(h, l)
r = []
while not heapempty(h):
r.append(heappop(h))
assert r == sorted(ls)
このテストは実際にバグを検出します：
> assert r == sorted(ls)
E assert [0, 1, 0] == [0, 0, 1]
E At index 1 diff: 1 != 0
E Use -v to get the full diff
binheap.py:74: AssertionError
----- Hypothesis -----
Falsifying example: test_pop_in_sorted_order(ls=[0, 1, 0])
この問題を解決するために、ヒープを適切に再バランスするheappop関数の正しい実装に置き換えます：
def heappop(heap):
if len(heap) == 0:
raise ValueError("Empty heap")
if len(heap) == 1:
return heap.pop()
result = heap[0]
heap[0] = heap.pop()
index = 0
while index * 2 + 1 < len(heap):
children = [index * 2 + 1, index * 2 + 2]
children = [i for i in children if i < len(heap)]
assert children
children.sort(key=lambda x: heap[x])
for c in children:
if heap[index] > heap[c]:
heap[index], heap[c] = heap[c], heap[index]
index = c
break
else:
break
return result
しかし、どうやってこの実装が十分かどうかを確認できるでしょうか？プッシュとポップの操作を組み合わせた場合、ヒープの基本的な不変条件を破るような状況が発生しないという保証はあるのでしょうか？
この疑問に答えるために、ルールベースドステートマシンの概念を利用します。Hypothesisを用いて、データ構造に対する操作をランダムに選択させ、固定されたテスト構造に組み込むのではなく、より柔軟なアプローチを取ります：
from hypothesis.stateful import RuleBasedStateMachine, precondition, rule
class HeapMachine(RuleBasedStateMachine):
def __init__(self):
super().__init__()
self.heap = []
@rule(value=integers())
def push(self, value):
heappush(self.heap, value)
@rule()
@precondition(lambda self: self.heap)
def pop(self):
correct = min(self.heap)
result = heappop(self.heap)
assert correct == result
@ruleは@givenのような機能ですが、RuleBasedStateMachineのメソッドにのみ適用され、より制約があります。」
しかし、@givenとの間には1つの大きな違いがあります。それは、複数のルールを連続して適用することができる点です。このステートマシンを使ったテストでは、各ルールを個別に実行するのではなく、ステートマシンのインスタンスを作成し、それに対して複数のルールを順番に適用します。
@preconditionデコレータは、ルールが適用される条件を制限します。例えば、空のヒープからのポップは許されていないため、ポップルールはヒープにデータが存在する場合にのみ適用されるようになります。
このテストは、unittestやpy.testなどの標準的なユニットテストフレームワークを使って実行できます。これは、以下のようにTestCaseオブジェクトを使って行います：
TestHeaps = HeapMachine.TestCase
元の不完全なheappop関数を使用した場合、以前と同じようなバグを検出することができました：
E AssertionError: assert 0 == 1
binheap.py:90: AssertionError
----- Captured stdout call -----
Step #1: push(value=1)
Step #2: push(value=0)
Step #3: push(value=0)
Step #4: pop()
Step #5: pop()
しかし、修正された実装ではテストが正常に通過します。
この状態で、このテスト方法は既に非常に有用です。特に、単一のオブジェクトやストレージシステムのようなサービスをテストする際に優れた効果を発揮します。
ただし、現在の実装には1つの制限があります。それは、単一のヒープに対する操作にのみ焦点を当てている点です。では、2つのヒープを組み合わせたい場合はどうでしょうか？たとえば、2つのヒープを合わせて、それらのいずれかに含まれる値を持つ新しいヒープを作るようなヒープマージ操作を実行したいと考えるかもしれません。
まずは、不完全な実装からスタートします：
def heapmerge(x, y):
x, y = sorted((x, y))
return x + y
ヒープに対して単純な戦略を書くことはできません。それは、各ヒープが独立したオブジェクトであり、ステートフルな性質を持つためです。
そこで、Hypothesisのルールベースのステートマシンの別の重要な機能である「バンドル（Bundles）」を利用します。バンドルを使用すると、ルールが値を受け取るだけでなく、値を返すことも可能になります。実際には、バンドルはルールが以前にそれに提供した値を生成するための戦略となります。これらのバンドルは以下のようにして使用されます：
class HeapMachine(RuleBasedStateMachine):
Heaps = Bundle("heaps")
@rule(target=Heaps)
def newheap(self):
return []
@rule(heap=Heaps, value=integers())
def push(self, heap, value):
heappush(heap, value)
@rule(heap=Heaps.filter(bool))
def pop(self, heap):
correct = min(heap)
result = heappop(heap)
assert correct == result
@rule(target=Heaps, heap1=Heaps, heap2=Heaps)
def merge(self, heap1, heap2):
return heapmerge(heap1, heap2)
これにより、単一のヒープではなく、ヒープのコレクションを管理することが可能になります。以前の操作はすべて、特定のヒープのインスタンスに対して行われます。
フィルターの使用に注目してください。バンドルは、他の任意の戦略のように利用できます。ここでは、フィルターを使って特定の前提条件を実装しています。つまり、私たちはこの特定のヒープが空であるかどうかのみに注目しているのです。
この方法を使うと、実装が間違っていることが明らかになります：
@rule(heap=Heaps.filter(bool))
def pop(self, heap):
correct = min(heap)
result = heappop(heap)
> assert correct == result
E AssertionError: assert 0 == 1
binheap.py:105: AssertionError
----- Captured stdout call -----
Step #1: v1 = newheap()
Step #2: push(heap=v1, value=0)
Step #3: push(heap=v1, value=1)
Step #4: push(heap=v1, value=1)
Step #5: v2 = merge(heap2=v1, heap1=v1)
Step #6: pop(heap=v2)
Step #7: pop(heap=v2)
このテストは、小さなヒープを作成し、それを自身とマージするとすぐにバランスが崩れることを示しています。
以下のようにheapmerge関数を修正して正しい実装にすることで、この問題を解決できます：
def heapmerge(x, y):
result = list(x)
for v in y:
heappush(result, v)
return result
ただし、単純な修正はやや退屈です。そこで、もっと面白い不完全な実装を導入してみましょう：
def heapmerge(x, y):
result = []
i = 0
j = 0
while i < len(x) and j < len(y):
if x[i] <= y[j]:
result.append(x[i])
i += 1
else:
result.append(y[j])
j += 1
result.extend(x[i:])
result.extend(y[j:])
return result
このマージ操作は、2つのソートされたリストをマージするような方法で2つのヒープを結合します。ただし、ヒープは実際にはソートされていないため、このコードはあまり意味のある結果をもたらしません。
この実装は間違っていますが、小さなヒープでの動作は意外と良く、それが間違っていることを示す例を見つけるのは直感的ではありません。
Hypothesisが見つけたものは次の通りです：
Step #1: v1 = newheap()
Step #2: push(heap=v1, value=0)
Step #3: v2 = merge(heap1=v1, heap2=v1)
Step #4: v3 = merge(heap1=v2, heap2=v2)
Step #5: push(heap=v3, value=-1)
Step #6: v4 = merge(heap1=v1, heap2=v2)
Step #7: pop(heap=v4)
Step #8: push(heap=v3, value=-1)
Step #9: v5 = merge(heap1=v1, heap2=v2)
Step #10: v6 = merge(heap1=v5, heap2=v4)
Step #11: v7 = merge(heap1=v6, heap2=v3)
Step #12: pop(heap=v7)
Step #13: pop(heap=v7)
Hypothesisは、慎重にヒープを作成してマージすることにより、バランスが取れていないヒープの連続するマージを生成しました。v7に至るまでの各ヒープはバランスが取れていましたが、v7は以下のような状態になります：
>>> v7
[-1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0]
この状態では、リストの遠い位置にある-1のために、ヒープがヒープ特性を満たしていないことがわかります。
私自身、このような例を自分で思いつくことはおそらくなかったでしょう。異なる操作セットを適用すれば、もっと単純な例が存在するかもしれません。例えば、Hypothesisに要素のリストを持つ新しいヒープを生成させ、その後でポップ操作を行わせるようにすると、テストの品質が向上する可能性があります。
しかし、ルールベースドステートフルテスティングの真の強みは、そのような例を自分で考え出す必要がないことにあります。代わりに、Hypothesisはオブジェクトに対するさまざまな操作の組み合わせが機能することを保証し、その過程でかなり巧妙なバグを発見することができます。
最終的には、完全に間違った実装が間違っていることを示すためにこれほど複雑な例が必要である場合、より微妙なバグを発見するのがいかに困難かを考えると驚くべきことです。
実際の使用例
この機能はまだ広く文書化されていないため、一般的にはあまり使用されていません。しかし、少なくとも2つの面白い実例があります：
- Hypothesisは、自身のテストにこの機能を使用しています。Hypothesisには、上述した機能を用いたデータベーステストの例があり、ランダムな戦略を生成してテストを行うテストAPIの小さなモデルが含まれています。
- Mercurialのテストで使用されています。これにより、バグ5112とバグ5113が発見されました。Mercurialでの使用例では、ステートフルテスティングがさらに多くのバグを見つける前に、より多くのリソース、ルール、そして展開に関する作業が必要です。
関連記事
関連記事
