Hypothesisの仕組み
0
以下の文章はこちらの記事を翻訳したものです。https://github.com/HypothesisWorks/hypothesis/blob/master/HypothesisWorks.github.io/_posts/2016-12-10-how-hypothesis-works.md
Hypothesisは、従来のプロパティベースドテストシステムとは一線を画す、全く新しい設計に基づいて開発されました。この設計の核心は、Hypothesisのストラテジーが自動的に対応する以下の特性群です。
- 生成された全ての例が安全に変更可能
- 生成された全ての例をディスクに保存でき、Hypothesisは過去の失敗を記録して再現することができるため、これは重要
- 生成された全ての例が縮小可能
- 生成時に成立している全ての不変条件が、縮小時にも保持される。（ただし、確率分布が変わる可能性があるため、高確率でのみサポートされる条件は、縮小時にはサポートされないこともあり得ます。）
他のプロパティベースドシステムでは、これらの特性のうちの一つを管理することさえ難しいです。
これらを支えるための最初のメカニズムはかなり複雑でしたが、数回の改良を経て、これらの特性を全て統合する強力な基本設計に辿り着きました。
Hypothesisの実装はまだ複雑ですが、その大部分は最適化や基本コンセプトを機能させるために必要なものです。もっと重要なのは、この複雑さが大きく限定されているという点です。比較的小さい核心部が全ての複雑な処理を担い、新しいストラテジーを定義する際には、通常のケースと比較してそれほど複雑さを増すことはありません（少なくとも外見上は）。
この記事では、Hypothesisのモデル全体とその動作原理を高いレベルで解説します。
Hypothesisは基本的に以下の3つの主要部分から成り立っており、それぞれが先行する部分を基盤として構築されています。
- Conjectureと呼ばれる低レベルのインタラクティブなバイトストリームファジャー。
- Conjectureのバイトストリームを高レベルの構造化データに変換するストラテジーライブラリ。
- Hypothesisのストラテジーライブラリからのデータを利用してテストを実行するテストインターフェース。
ここでは、主に最初の2つに焦点を当てます。後者は複雑ですが、主に内部の連結に関する問題です。
Conjectureによって提供される基本的なオブジェクトは、TestDataというクラスです。このクラスは基本的に、バイトを読み取ることが可能な開いたファイルハンドルのようなものです：
class TestData:
def draw_bytes(self, n):
...
（注：この記事に記載されているPythonコードは、Hypothesisに実際に存在するコードの正確なコピーではなく、教育的な目的で簡略化されています。）
さらに、ストラテジーは、SearchStrategyクラスからの単一の抽象メソッドを実装するオブジェクトに過ぎません：
class SearchStrategy:
def do_draw(self, data):
raise NotImplementedError()
テストインターフェースは、テスト関数とそれに必要なストラテジーを変換します。この変換により、TestDataオブジェクトを受け取り、テストが失敗した場合はTrueを、成功した場合はFalseを返す形式になります。
符号なし64ビット整数のためのストラテジーを実装する簡単な例を以下に示します。
class Int64Strategy:
def do_draw(self, data):
return int.from_bytes(data.draw_bytes(8), byteorder="big", signed=False)
この例で、draw_bytesメソッドはバイトを返すだけでなく、テストを停止させる例外を発生させることもできます。これは、例が大きすぎるのを防ぐための有効な方法です（後ほど示しますが、縮小のプロセスにも重要です）。
これを見ると、私たちがどのようにして、例を保存し、変更することを可能としているかが明確になるかと思います。すべての例を保存することが可能なのは、生成したバイトをディスクに書き込むだけでよいからです。また、変更も可能なのは、ストラテジーは、私たちがどのように保持しているかに関係なく値を返すからです。
では、縮小はどのように機能するのでしょうか？
縮小の重要な考え方は、以前の記事で述べた通り、入力を縮小することで出力を縮小できるということです。この場合、入力はバイトストリームです。
Hypothesisが失敗を見つけた後、ShrinkingTestDataオブジェクトを使ってバイトストリームの縮小を開始します：
class ShrinkingTestData:
def __init__(self, data):
self.data = data
self.index = 0
def draw_bytes(self, n):
if self.index + n > len(self.data):
raise StopTest()
result = self.data[self.index : self.index + n]
self.index += n
return result
縮小は、渡されたバイト配列のデータを縮小するプロセスですが、変換されたテスト関数が依然としてTrueを返す条件のもとで行われます。
バイト配列の縮小は、以下のルールに基づいて最小化されます：
- 常に短い方がシンプル
- 同じ長さの2つのバイト配列の場合、辞書順で早い方（バイトを符号なし8ビット整数として考えた場合）がシンプル
デルタデバッギングのバリエーションを使ってバイト配列を縮小することが想像できるかと思います。このプロセスでは、データを削除したりバイトを減らしたりしながら、これ以上の削減が不可能になるまで繰り返します。実際にはもっと複雑ですが、詳細は省略します。
ストラテジーが適切に書かれていれば、バイト配列の縮小は生成されたデータの良好な縮小につながります。たとえば、ビッグエンディアンで選ばれた64ビット符号なし整数の場合、バイトデータを辞書順に縮小すると、整数はゼロに向かって縮小します。
良好な削除動作を得るためには、生成されたデータでの削除に対応するように、基盤となるバイトストリームの並びを注意深く扱う必要があります。
たとえば、次のようにリスト用のストラテジーを設計すると、問題が生じる可能性があります：
class ListStrategy(SearchStrategy):
def __init__(self, elements):
self.elements = elements
def do_draw(self, data):
n_elements = integers(0, 10).do_draw(data)
return [self.elements.do_draw(data) for _ in range(n_elements)]
この方法の課題は、データを削除しても実際にリストの要素が減らないことです。起こり得るのは、描画処理がバッファの端を超えてしまうことです。n_elementsの数を減らすことは可能ですが、これではリストの終わりから要素を取り除くことしかできません。そうすると、最終的に不要なデータが残ってしまう可能性があります。これが最後に描画されるデータなら問題は少ないですが、次のストラテジーに進む際には不確かな挙動となり得ます。
実際には、このようなストラテジーでの縮小処理を改善するための取り組みを進めています。このタイプのストラテジーはユーザーによって頻繁に使用されるため、改善することには大きな価値があります。しかし、理想的には、リストからの要素の削除が基本的なバイトストリームのデータ削除に対応するべきです。次のような方法でこれを実現することができます：
class ListStrategy(SearchStrategy):
def __init__(self, elements):
self.elements = elements
def do_draw(self, data):
result = []
while booleans().do_draw(data):
result.append(self.elements.do_draw(data))
return result
このアプローチでは、リストが「True, 要素, True, 要素, ..., False」という形で描画されます。そうすると、バイトストリーム内でTrueから始まり要素の終わりで終わる区間を削除することにより、その要素がリストから削除され、残りの要素が一つずつ左にシフトされます。
注意深くストラテジーを設計することで、このアプローチはかなりうまく機能します。しかし、2つの小さな問題が発生することがあります：
- あまり良いデータが生成されない。
- 縮小がうまく行われない。
幸いなことに、これらの問題は解決可能です。
良いデータが不足する主な理由は、Conjectureが特定のストラテジーに対して適切なバイト分布を生成するための十分な情報を持っていないことにあります。例えば、先に挙げた符号なし64ビット整数の例では、0が特別な値であることは想定できるかもしれませんが、小さい値に焦点を当てることの重要性が必ずしも明確でない場合があります。
この問題は、整数のようなシンプルなケースから離れるとさらに悪化します。例えば、バイトを浮動小数点数に変換する場合、Conjectureが無限大などの興味深い値をどのようにして識別すべきかが問題となります。
この問題に対する簡単な解決策として、ユーザーが分布のヒントを提供できるようにする、という方法があります。
class TestData:
def draw_bytes(self, n, distribution=None):
...
ここで、分布関数はランダムオブジェクトとバイト数を取り、ユーザーによって指定されます。
これにより、ユーザーはバイトの分布を指定することができ、特別な値などを強調するための良い出発点が提供されます。この分布は必ずしも厳密に尊重されるわけではありません。例えば、縮小時には必ずしもその通りにはならず、ファジャーも生成中に値を変化させることができますが、それでも有用です。
例として、私たちの64ビット整数用のストラテジーを以下のように再定義することができます。
class Int64Strategy:
def do_draw(self, data):
def biased_distribution(random, n):
if random.randint(0, 1):
return random.randint(0, 100).to_bytes(n, byteorder="big", signed=False)
else:
return uniform(random, n)
return int.from_bytes(
data.draw_bytes(8, biased_distribution), byteorder="big", signed=False
)
この変更により、0から100の間の整数が半分の確率で生成される偏った分布を持つ整数が得られます。
初期バッファの生成には、これらのストラテジーを使います。例えば、GeneratingTestDataという実装をTestDataに渡すことができます。
class GeneratingTestData(TestData):
def __init__(self, random, max_bytes):
self.max_bytes = max_bytes
self.random = random
self.record = bytearray()
def draw_bytes(self, n, distribution):
if n + len(self.record) > self.max_bytes:
raise StopTest()
result = distribution(self.random, n)
self.record.extend(result)
return result
これにより、提供された分布からデータを引き出して記録します。この結果、テストを再生するために使用されたすべてのバイトが最終的に記録されます。
これがほとんどのケースにおいて十分であることがわかりました。私はこのAPIをより構造化された形に置き換えるための研究を進めています（理想的には、不透明な分布オブジェクトの代わりに明示的な文法の組み合わせからデータを引き出すことです）。しかし、現在Hypothesis開発に資金がないため、このような大規模な変更に関する研究は一時的に棚上げされ、あまり進展していません。
初期のデザインでは、バイトストリームからのデータを使用して分布を定義することでこのアプローチを避けようとしましたが、これはバイトストリーム内でかなり不透明な構造を生み出し、縮小がうまく行かなかったため、現在のよりシンプルな方法が優れていることがわかりました。
縮小がうまくいかないという第二の問題は比較的簡単に解決できます。問題は、縮小自体がうまくいかないことではなく、何をすべきかを判断するのが遅いために縮小が遅くなることです。前述したリストの例では、現在要素を削除する唯一の方法は、対応する間隔を削除することであり、適切な間隔を見つける唯一の方法は、すべてを試すことです。これにはO(n^2)の削除が必要になることがあります。
解決策としては、データを生成する際にもう少し詳細な記録を残し、有用な間隔をマークすることです。TestDataは以下のように変更されます：
class TestData:
def start_interval(self):
...
def stop_interval(self):
...
def draw_bytes(self, n):
...
def draw(self, strategy):
self.start_interval()
result = strategy.do_draw(self)
self.stop_interval()
return result
これにより、すべてをstrategy.do_drawの代わりにdata.drawを通して処理することで、この記録を維持します。
これらの間隔はバイトストリーム内で重要な境界を示しており、最適な箇所を削除するのに役立ちます。特に、値の境界を越えていない区間は、削除に際して特に有効であることが多いです。
ただし、Hypothesisの完全な機能を実現するためには、さらに多くの細部に注意を払う必要があります。縮小機構とストラテジーライブラリは連携して機能するよう細かく設計されており、スムーズに運用するためには多数のヒューリスティックや特殊なケースが必要です。また、ここでは触れていないが、多くの詳細な記録が間隔を超えて存在します。
Hypothesisは完璧なシステムではないものの、効果的に機能しています。これは2016年初めのバージョン3.0リリース以来、Hypothesisの基本的な実装であり、エンドユーザーにとってはほぼ無感覚な切り替えが行われました。以前の実装はクラシックなQuickCheckモデルに近いもので、完全なHypothesis機能セットをサポートするために多くの追加複雑さを含んでいました。
多くの場合、特別にカスタマイズされた解決策よりも優れた結果をもたらします。たとえば、バイトベースのアプローチの利点は、データの各部分が完全に理解可能であることです。より構造化された縮小手法はしばしば局所的な最小値に陥りやすいですが、Hypothesisはデータ内のパターンを見つけて、それらを推測的に縮小し、その効果をテストすることができます。
データ生成を連鎖させるサポートも、Hypothesisの利点の一つです。Hypothesisでは、次のようにストラテジーを連鎖させることができます。
class SearchStrategy:
def do_draw(self, data):
raise NotImplementedError()
def flatmap(self, bind):
return FlatmappedStrategy(self, bind)
class FlatmappedStrategy(SearchStrategy):
def __init__(self, base, bind):
self.base = base
self.bind = bind
def do_draw(self, data):
value = data.draw(self.base)
return data.draw(self.bind(value))
このアイデアは、flatmapメソッドを使用して、他のストラテジーからの値に依存するデータを描画することにより、ストラテジーの定義を連鎖させることが可能になります。
これは現代のHypothesisで非常にうまく機能していますが、歴史的には（たとえばtest.checkやHypothesisのバージョン3.0以前など）統合テストと生成に問題を引き起こしていました。
通常、これが問題になるのは、最初に描画された値を縮小すると、bind(value)から描画された値が基本的に無効になるためです。これは、それが完全に異なるジェネレータから来たものであるため、実際には保持する方法がありません。これにより、初期値を縮小するために他の場所での縮小が突然成功した場合、多くの以前の作業が無駄になる可能性があります。
Hypothesisのバイトストリーム方式は、このような問題に対してほとんど影響を受けません。新しいストラテジーが以前のストラテジーと似た構造を持っている限り、同じ基本バイトストリーム上で操作が行われるので、一度の縮小が終わった後もスムーズに引き続き処理を進めることができます。
このタイプの構造では、最初に描画された値を縮小すると、それに続くバインドされたストラテジーが大きく変化することがあるかもしれません。しかし、縮小のプロセスには柔軟性があり、通常はこのような変更も乗り越えることができます。
このモデルは現在の形でも十分強力で、さらなる拡張の可能性もありますが、無理に拡張する必要はありません。現在のモデルの魅力は、そのシンプルさにあります。Hypothesis for Javaのプロトタイプはわずか数時間で書かれたもので、非常に効果的です。PythonのConjecture実装はわずか千行未満で、高い移植性を備えています。ストラテジーライブラリやテストインターフェースにはまだ改善の余地がありますが、Hypothesis/Conjecture方式は、これまでの縮小機能を持たないプロパティベースドテストライブラリの限界を克服するための有望な手法です。
関連記事
関連記事
