この記事は Property-Based Testing Advent Calendar 2018 3日目の記事です。

==> Day2: Property-Based Testing とは

今日は、Property-Based Testing (PBT) において中心的な役割を果たす、Property, Generator, Shrinking の3つを説明します。

PBT では、フレームワークがテストケースを半自動的に生成します。一方テスト作成者は、テスト対象への入力と、テスト対象が満たすべき要件（関数の出力やシステムの状態など）を定義することになります。

PBT において、入力を生成する機能を Generator といいます。Generator は多様な入力をランダムに生成します。また、テスト対象が満たすべき性質を Property といいます。

PBT フレームワークには、Generator を構築し、Property を記述するための便利な DSL が含まれています（具体例は後半の記事で紹介します）。

PBT フレームワークは、ユーザが定義した Generator からテスト入力を生成し、それをシステムに流し込み、ユーザが定義した Property を検査します。 これを繰り返しながら、Property の検査が失敗したり、システムがクラッシュするテストケースを探索するのが、PBT におけるテスト実行の流れです。

失敗するテストケースが見つかると、PBT フレームワークはもう一つ仕事をしてくれます。 これは Shrinking と呼ばれる機能で、テストが失敗した入力を人間が理解しやすいよう簡略化してくれるものです。

今日の記事では、Generator, Property, Shrinking の例を挙げながら、実際どのように PBT でテストを記述するかを紹介します。

Generator

PBT フレームワークは Generator を構築するための DSL を持っています。Generator はシステムの入力として、どういう集合からどういう条件を満たす要素を選べばよいかを指定します。

PBT フレームワークは、Generator を使ってテストに使う入力を生成します。だんだんと複雑な入力を生成する機構や、なるべく多様な入力を生成する機構が入っているフレームワークもあります。

例えば、多くの PBT フレームワークには、型定義からその型の値をランダムに生成する Generator が含まれています。 それに加えて、入力をより細かく制御するために、生成した入力を条件で間引いたり、入力生成器を直接実装したりすることもあります。

-type number_list() :: list(number()).
-spec sort(number_list()) -> number_list().

number().

number_list() -> list(number()).

Generator を使ってテストケースを生成すると、人手でテストケースを書くのと比べて気軽に大量のテストケースを生成できます。 また、Generator は結構複雑な入力も生成し、システムをテストしてくれます。

% こういう入力を、100個でも100万個でも気軽に生成し、テストできる

[-5,-80,-3,-7,-4,-13,-7]
[3,5,-2,2,-19,-2,-16,2,3,-6]
[14,2,-4,1,8,6,7,-12,-12]
[]
[8,-5,8]
[5,-11,-8,2,4,22,12,-1,-2,7]
[17,-1,9,4]
[2,14,-12,-12,-6,6,3,8,5]
[-3]
[9,3,13,0,3,8,11]
[-4]
...

また、PBT では大量・多様なテストケースを自動生成して、網羅的にシステムの振る舞いをテストしようします。個例を書くテストでは、実装を踏まえてテストを書いていた箇所も、自動生成したテストでカバーしようとします。この結果、テストが実装に依存しにくくなり、実装を変えても、テストを書き換えなくてすむようになります。

PBT を使って機械的に生成したテストで、実際どの程度のバグが検出でき、どの程度カバレッジが達成できるのか、などは6日目以降に検証記事を書く予定です。

Property

Property は、テストしたいシステムの性質をプログラミング言語で表現したものです。具体的には、Generator が生成した入力をシステムが処理した結果、出力が満たすべき性質や、システムの状態が満たすべき条件を判定するプログラムを書きます。

これはふつうのユニットテストにおいて assert を書くようなものですが、PBT では少し抽象化した形式で Property を記述します。

Property 例えば以下のようになります。

% For all number_list L, sort(L) should be ordered and has the same elements as L.
?FORALL(number_list(), L,
        is_ordered(sort(L)) and has_same_elements(sort(L), L)).

このコードは、sort の出力が満たすべき性質（整列されており、入力と同じ要素からなる）を書いたものです。

コードの上にコメントとして書いた、「sort されるとはどういうことか」を自然言語で書いたステートメントと、テストコードとが似た見た目になっているところがポイントです

宣言的な言語と命令的な言語の対比を思い出すといいかもしれません。

例えば、SQL はデータベース問い合わせのための宣言的な言語です。SQL の売りは、自然言語に似た言語で問い合わせを書ける（ビジネスの人でもデータ解析ができる）ことです。このとき、データの物理的な配置や、結果の効率的な計算方法、並行性の制御といった詳細は、DBMS に委ねられます。

PBT では、テスト作成者はシステムの性質を、自然言語に近い記法で記述します。 これをテストするための具体的なテストケースは、PBT フレームワークが生成します。 これは、仕様を書くのに近い言語でテストを書けるということで、PBT が仕様からテストを自動生成するというのはこういう意味です。

Shrinking

PBT フレームワークは、Generator を使って繰り返し入力を生成し、Property を使ってシステムの正しさをテストします。PBT のユーザは、Generator と Property を設計します。

それに加えて、PBT フレームワークには、テストに失敗したケースを人に理解しやすいものに変形する Shrinking という機能があります。

Generator は単純な入力を生成することもあれば、複雑な入力を生成することもあります。 複雑な入力によりテストが失敗したとき、その入力のうちどの部分が本質的なのかを PBT フレームワークは自動的に発見しようと試みます。 具体的には、失敗したテストケースの一部を取り除きながら繰り返しテストを実行し、テストが失敗する極小の入力を見出します。

こうして、PBTフレームワークは単純なものから複雑なものまで多様なテストケースを自動生成しながらも、見つけたバグを理解しやすいよう要約して人間に提示してくれます。

これは人間がバグを見つけるときにもしていることです。 バグを見つけるために色々な入力を試してみて、バグが見つかったら試行錯誤しながらより単純なバグの再現条件を探します。 PBT では、これを機械的に行うことで、無数のテストケースを機械的に生成してより多くのバグを見つけだし、再現条件の絞り込みまで自動でやってくれます。

まとめ

Property-Based Testing とはシステムの仕様からテストケースを半自動生成するランダムテスト手法です。

PBT の主要な構成要素は次の3つです。

  • 入力を生成する Generator
  • テスト対象の満たすべき性質を述べた Property
  • テストに失敗したケースを人に理解しやすく変形する Shrinking

お話ばかり書いてきましたが、明日は PBT を使って実際にテストを動かしてみようと思います。

==> Day4: Property-Based Testing の Hello, world!

余談

Generator, Property, Shrinking の三つを PBT のキモとするのは必ずしも一般的な定義ではないかもしれません。

例えば、Golang の標準ライブラリにある PBT ライブラリには、Shrinking がないようです。 また、Haskell や Scala などの先進的な界隈では、実験的な機能を入れてみた PBT フレームワーク1が色々あるようです。

2000 年の論文 “QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs (Claessen, Koen, and John Hughes)”2 で Generator, Property, Shrinking を含む今の PBT フレームワークの原形が提示されました。

Web アプリケーションフレームワークやビジネスフレームワークと同様に、テストフレームワークもデザインの要素が強いものです。 QuickCheck が提示した設計が、どのように進展し、収束していくのか、消えていくのか、それとも最終的に今の形に戻ってくるのかはわかりません。 しかし直感的には、QuickCheck の提示した PBT の形は幾分アドホックに思え、まだ原石なのではないかと僕は思っています。

ただ、現時点の PBT フレームワークは基本的に Generator, Property, Shrinking を踏襲し続けており、それ以外の機能として決定的なものは加わっていないように思うため、この記事ではこれらを PBT の主要な構成要素として紹介しました。

  1. 私にはまだ網羅的に書ける見識はありませんが、例えば日本で一番 Property Based Testing に詳しい @xuwei_k さん3が公開しておられる Scala の PBT ライブラリの実装資料などは、日本語で読める貴重な情報源のうちの一つです ↩

  2. この論文の Appendix では QuickCheck の実装がたった1ページで書かれています。PBT フレームワーク、そんなに実装は大変じゃなさそうだなぁと思っていたけど、1ページでかけちゃうのは結構ビックリしました。書いてみようかな ↩

  3. @xuwei_k さんの書いた日本で一番 Property-Based Testing に詳しいアドベントカレンダーが読みたい人は、この Tweet をふぁぼってプレッシャーをかけましょう ↩