Zenn
🎴

プロパティベーステストライブラリを作ってみた

2024/05/08に公開
Test
Dart
#
pbt
#
プロパティベーステスト
tech

Dart向けのプロパティベーステストライブラリ kiri-checkを作りました。DartにはGladosというライブラリがあり、しばらく試していたのですが、少し機能が物足りないのとあまりメンテナンスに熱心でなさそうで、学習を兼ねて自分でも作ってみることにしました。

本記事ではライブラリの簡単な使い方と、実装を通じて得られた知見を書きたいと思います。プロパティベーステストについては特に説明しませんので、 実践プロパティベーステスト などを参考にしてください。

ちなみに、 kiri-check の kiri は「きりがない」の「きり」です。

kiri-check の特徴

できるだけ独自の使い勝手を作らないようにしています。kiri-checkだけの独自機能！はありません。

  • test パッケージ を利用しており、普段のテストと同じ感覚で使えます。また、既存のテストコードを変更せずにプロパティベーステストを追加できます。
  • メジャーなプロパティベーステストライブラリに近いシンプルなAPIです。主に QuickCheck, PropEr, Hypothesis, jqwik を参考にしました。
  • 探索方法のカスタマイズが簡単です。データの範囲の指定、試行回数の増減、エッジケースの優先などができます。
  • Unicode文字列の生成をサポートしています。Unicodeカテゴリもサポートしており、文字種や特定のコードポイントで構成される文字列を生成できます。
  • タイムゾーンと架空の日付をサポートしています。架空の日付とは、うるう年でない2月29日や、4月31日といった存在しない日付です。

他にも次の機能の実装を予定しています。自分が欲しいので早めに実装したいと思います。

  • ステートフルテスト
  • 標的型プロパティ

インストール

pub.dev経由でインストールできます。以下のコマンドを実行するか、pubspec.yamlに手動で記述してください。

dart pub add kiri_check

クイックスタート

簡単な例として、FizzBuzzのテストを実装します。もちろんFizzBuzzの実装も用意していますが、よかったら自前で実装してテストしてみてください。

まず、新しいDartプロジェクトを用意し、kiri-checkをインストールしてください。次に、testディレクトリ以下にFizzBuzzテストのファイルを作成します。テストコードは以下の通りです。

test/fizzbuzz_test.dart:

Object fizzbuzzGood(int n) {
  if (n % 3 == 0 && n % 5 == 0) {
    return 'FizzBuzz';
  } else if (n % 3 == 0) {
    return 'Fizz';
  } else if (n % 5 == 0) {
    return 'Buzz';
  } else {
    return n;
  }
}

この関数のテストは次のように実装できます。

void main() {
  property('FizzBuzz (good)', () {
    forAll(
      integer(min: 0, max: 100),
      (n) {
        final result = fizzbuzzGood(n);
        if (n % 15 == 0) {
          expect(result, 'FizzBuzz');
        } else if (n % 3 == 0) {
          expect(result, 'Fizz');
        } else if (n % 5 == 0) {
          expect(result, 'Buzz');
        } else {
          expect(result, n);
        }
      },
    );
  });
}

propertyに与えるブロックがテスト内容です。propertyはtestのラッパーであり、testと同じ引数を受け取ります。forAllを除けばtestと同じ使い方で問題ありません。値のチェックもtestと同じexpectなどのメソッドを使えます。

forAllに与えるブロックで具体的なテストを実装します。forAllは引数にジェネレーター（※アービトラリー）を受け取り、ジェネレーターが（ほぼ）ランダムに生成した値をブロックに渡して実行します。

integerは整数を生成するジェネレーターを生成する関数です。minとmaxの引数で最小値と最大値を指定します。テストを実行すると、integerによって整数が生成され、その数の分だけブロックが繰り返し実行されます。デフォルトの生成回数は100回です。

FizzBuzzは単純な仕様なので、テストの内容もほとんど同じ実装になります。ただし、FizzBuzzの実装とテストコードで3と5の倍数の条件式を少しだけ変えています。FizzBuzzの実装では3と5の2つの除算を組み合わせていますが、テストコードでは少しでもミスを減らす目的で念のため定数にしています。単純だからと言ってまったく同じコードを使うと、バグがあってもテストをパスするので気付かない可能性があります。プロパティテストの意味がなくなってしまうので気をつけましょう。

テストを実行する

testと同じ方法で実行できます。dart testサブコマンドもしくはIDEで実行してください。

dart test fizzbuzz_test.dart

出力:

00:00 +1: All tests passed!

すべてのテストを無事パスしました。ただ、これだけだと本当にテストの意味があったのかわからないので、生成された値を表示してみましょう。生成された値を含むテストの詳細を表示するには、KiriCheck.verbosityにVerbosity.verboseを指定します。

void main() {
  KiriCheck.verbosity = Verbosity.verbose;
  ...

実行結果:

00:00 +0: FizzBuzz (good)                                                                                          
Max tries: 100
Max examples: 100
Random seed: null
Generation policy: GenerationPolicy.auto
Edge case policy: EdgeCasePolicy.mixin
Shrinking policy: null
Trying example: 0
Trying example: 5
Trying example: 73
Trying example: 33
Trying example: 4
（省略）
Trying example: 72
Trying example: 7
Trying example: 35
Trying example: 31
Trying example: 1
No falsifying examples found (100 tests passed)

00:00 +1: All tests passed!
完全な出力
00:00 +0: FizzBuzz (good)                                                                                          
Max tries: 100
Max examples: 100
Random seed: null
Generation policy: GenerationPolicy.auto
Edge case policy: EdgeCasePolicy.mixin
Shrinking policy: null
Trying example: 0
Trying example: 5
Trying example: 73
Trying example: 33
Trying example: 4
Trying example: 0
Trying example: 62
Trying example: 100
Trying example: 85
Trying example: 19
Trying example: 5
Trying example: 3
Trying example: 0
Trying example: 32
Trying example: 2
Trying example: 8
Trying example: 38
Trying example: 71
Trying example: 71
Trying example: 30
Trying example: 25
Trying example: 9
Trying example: 2
Trying example: 62
Trying example: 32
Trying example: 99
Trying example: 36
Trying example: 4
Trying example: 21
Trying example: 54
Trying example: 27
Trying example: 36
Trying example: 97
Trying example: 22
Trying example: 8
Trying example: 78
Trying example: 4
Trying example: 83
Trying example: 100
Trying example: 96
Trying example: 5
Trying example: 0
Trying example: 1
Trying example: 9
Trying example: 89
Trying example: 96
Trying example: 45
Trying example: 67
Trying example: 29
Trying example: 85
Trying example: 55
Trying example: 72
Trying example: 1
Trying example: 65
Trying example: 23
Trying example: 0
Trying example: 76
Trying example: 18
Trying example: 30
Trying example: 34
Trying example: 4
Trying example: 0
Trying example: 24
Trying example: 29
Trying example: 13
Trying example: 83
Trying example: 65
Trying example: 6
Trying example: 52
Trying example: 18
Trying example: 99
Trying example: 79
Trying example: 36
Trying example: 2
Trying example: 92
Trying example: 76
Trying example: 9
Trying example: 56
Trying example: 5
Trying example: 95
Trying example: 5
Trying example: 29
Trying example: 87
Trying example: 55
Trying example: 6
Trying example: 0
Trying example: 81
Trying example: 52
Trying example: 75
Trying example: 100
Trying example: 100
Trying example: 1
Trying example: 14
Trying example: 77
Trying example: 0
Trying example: 72
Trying example: 7
Trying example: 35
Trying example: 31
Trying example: 1
No falsifying examples found (100 tests passed)

00:00 +1: All tests passed!

Trying example: ... が実際にテストに使われた値を示します。No falsifying examples found はすべての値でエラーが発生しなかったことを示します。いくつかの値が重複していますが、これは仕様なので問題ありません。同じ値でテストしても1回目と2回目以降で成否の結果が異なる場合もあるので、意図的に重複を許容しています。

テストを失敗させてみる

今度は、わざと実装を間違えてテストを失敗させてみます。条件分岐を少しいじった新しい関数を定義してみましょう。

Object fizzbuzzBad(int n) {
  if (n % 3 == 0) {
    return 'Fizz';
  } else if (n % 5 == 0) {
    return 'Buzz';
  } else if (n % 3 == 0 && n % 5 == 0) {
    return 'FizzBuzz';
  } else {
    return n;
  }
}

このコードでは、0を含む15の倍数のときに "FizzBuzz" が出力されません。説明の都合で0を除きたいので、生成する最小値を1にして以下のテストを追加してください。

property('bad', () {
  forAll(
    integer(min: 1, max: 100),
    (n) {
      final result = fizzbuzzBad(n);
      if (n % 15 == 0) {
        expect(result, 'FizzBuzz');
      } else if (n % 3 == 0) {
        expect(result, 'Fizz');
      } else if (n % 5 == 0) {
        expect(result, 'Buzz');
      } else {
        expect(result, n);
      }
    },
    verbose: true,
  );
});

実行結果:

00:00 +1: FizzBuzz (bad)                                                                                           
（省略）
Trying example: 95
Falsifying example: 45
Shrinking step 1
Shrunk example to: 41
Shrunk example to: 37
Shrunk example to: 33
（省略）
Shrunk example to: 3
Shrunk example to: 2
Shrunk example to: 1
Shrinking step 4
Minimal failing example: 15
00:00 +1 -1: FizzBuzz (bad) [E]

  Falsifying example: 15
完全な出力
00:00 +1: FizzBuzz (bad)                                                                                           
Max tries: 100
Max examples: 100
Random seed: null
Generation policy: GenerationPolicy.auto
Edge case policy: EdgeCasePolicy.mixin
Shrinking policy: null
Trying example: 1
Trying example: 100
Trying example: 71
Trying example: 10
Trying example: 72
Trying example: 81
Trying example: 46
Trying example: 68
Trying example: 2
Trying example: 74
Trying example: 95
Falsifying example: 45
Shrinking step 1
Shrunk example to: 41
Shrunk example to: 37
Shrunk example to: 33
Shrunk example to: 29
Shrunk example to: 25
Shrunk example to: 21
Shrunk example to: 17
Shrunk example to: 13
Shrunk example to: 9
Shrunk example to: 1
Shrinking step 2
Shrunk example to: 43
Shrunk example to: 41
Shrunk example to: 39
Shrunk example to: 37
Shrunk example to: 35
Shrunk example to: 33
Shrunk example to: 31
Shrunk example to: 29
Shrunk example to: 27
Shrunk example to: 25
Shrunk example to: 23
Shrunk example to: 21
Shrunk example to: 19
Shrunk example to: 17
Shrunk example to: 15
Shrunk example to: 13
Shrunk example to: 11
Shrunk example to: 9
Shrunk example to: 7
Shrunk example to: 1
Shrinking step 3
Shrunk example to: 14
Shrunk example to: 13
Shrunk example to: 12
Shrunk example to: 11
Shrunk example to: 10
Shrunk example to: 9
Shrunk example to: 8
Shrunk example to: 7
Shrunk example to: 6
Shrunk example to: 5
Shrunk example to: 4
Shrunk example to: 3
Shrunk example to: 2
Shrunk example to: 1
Shrinking step 4
Minimal failing example: 15
00:00 +1 -1: FizzBuzz (bad) [E]
  Falsifying example: 15
  package:kiri_check/src/property.dart 103:7   Property.check
  package:kiri_check/src/property.dart 398:16  PropertyTestRunner.run
  package:kiri_check/src/property.dart 376:25  PropertyTestManager.runTest
  package:kiri_check/src/property.dart 337:27  PropertyTest.register.body

Falsifying example: 45 は、値が 45 のときにエラーが発生したことを示します。プロパティベーステストでは、エラーが見つかると基準値（integer()では0）に向けて値を減らしながらテストの実行を繰り返し、エラーが発生する最小値（最も基準値に近い値）を探します。この工程をシュリンク（収縮）と呼びます。

Shrunk example to: ...はシュリンク工程でテストされた値を示します。シュリンク値はランダムではなく、できるだけ再現可能な方法で生成されます。シュリンク値でエラーが発生したら、その値を元に再びシュリンク値を生成してテストします。基本的に、シュリンク値を再生成するたびに値の間隔を狭めていきます。

最後のMinimal failing example: 15 は、シュリンクで見つけたエラーの最小値です。45で最初のエラーが発生しましたが、シュリンクにより15でエラーが発生することがわかりました。30の差だけデバッグの手間が省けました。

今回は想定通りの最小値が見つかりましたが、必ずしも真の最小値が見つかるとは限りません。効率的にエラーの最小値を見つけるには、生成するデータの範囲を指定するなどの工夫が必要になります。

完全なコード

Object fizzbuzzGood(int n) {
  if (n % 3 == 0 && n % 5 == 0) {
    return 'FizzBuzz';
  } else if (n % 3 == 0) {
    return 'Fizz';
  } else if (n % 5 == 0) {
    return 'Buzz';
  } else {
    return n;
  }
}

Object fizzbuzzBad(int n) {
  if (n % 3 == 0) {
    return 'Fizz';
  } else if (n % 5 == 0) {
    return 'Buzz';
  } else if (n % 3 == 0 && n % 5 == 0) {
    return 'FizzBuzz';
  } else {
    return n;
  }
}

property('good', () {
  forAll(
    integer(),
    (n) {
      final result = fizzbuzzGood(n);
      if (n % 15 == 0) {
        expect(result, 'FizzBuzz');
      } else if (n % 3 == 0) {
        expect(result, 'Fizz');
      } else if (n % 5 == 0) {
        expect(result, 'Buzz');
      } else {
        expect(result, n);
      }
    },
  );
});

property('bad', () {
  forAll(
    integer(max: 10000),
    (n) {
      final result = fizzbuzzBad(n);
      if (n % 15 == 0) {
        expect(result, 'FizzBuzz');
      } else if (n % 3 == 0) {
        expect(result, 'Fizz');
      } else if (n % 5 == 0) {
        expect(result, 'Buzz');
      } else {
        expect(result, n);
      }
    },
  );
});

property('bad with range greater than 0', () {
  forAll(
    integer(min: 100),
    (n) {
      final result = fizzbuzzBad(n);
      if (n % 15 == 0) {
        expect(result, 'FizzBuzz');
      } else if (n % 3 == 0) {
        expect(result, 'Fizz');
      } else if (n % 5 == 0) {
        expect(result, 'Buzz');
      } else {
        expect(result, n);
      }
    },
    ignoreFalsify: true,
    onFalsify: (example) {
      expect(example, 105);
    },
    verbose: true,
  );
});

その他のジェネレーター

kiri-checkでは以下のジェネレーターを用意しています。

基本的なデータ型

  • boolean: trueまたはfalseを生成する
  • null_: nullのみ生成する
  • integer: intを生成する
  • string: 文字列を生成する。文字コード（ASCII, UTF-8, UTF-16）を指定可能
  • runes: Runesを生成する。内容はstringと同じ
  • datetime: DateTime（日付と時刻）を生成する。タイムゾーンを指定可能
  • date: DateTimeを生成する（日付のみ）。タイムゾーンを指定可能
  • time: DateTimeを生成する（時刻のみ）
  • constant: 指定した値のみを生成する
  • constantFrom: 指定したリストからいずれかの値を生成する
  • list: 指定したジェネレーターで生成した値のリストを生成する
  • map: キーと値のジェネレーターでマップを生成する
  • set: 指定したジェネレーターで生成した値のセットを生成する

組み合わせ

  • oneOf: 複数のジェネレーターのうち、いずれかのジェネレーターで値を生成する
  • frequency: 複数のジェネレーターの使用頻度を指定して値を生成する
  • combine: 複数のすべてのジェネレーターで生成した値の組み合わせを用意する。最大8つまでのジェネレーターを指定できる
  • recursive: 再帰的な構造の値（木構造など）を生成する
  • deck: テストブロック内で任意のジェネレーターを使用する

値の変形

ジェネレーターに対して以下のメソッドを使うと、生成された値を変形できます。変形後の値でエラーが発生すると、変形前の値でシュリンクが行われます。

  • map: 生成された値を別の値に変換する
  • flatMap: 生成された値を使用して新しいジェネレーターを生成する
  • filter: 生成された値のうち、指定した条件を満たす値のみテストを実行する

任意のジェネレーターを動的に選択する

使用するジェネレーターを、実行中の状態に応じて選択したい場合があります。任意のジェネレーターを動的に選択するには、特殊なジェネレーターdeckを使います。

例として、ランダムな整数を生成し、その値が偶数なら浮動小数点数、奇数なら文字列を生成するテストなら次のように実装できます。

property('deck example', () {
  forAll(deck(),
    (d) {
      // 整数ジェネレーターで値を生成する
      final i = d.draw(integer());
      // 使用するジェネレーターを動的に選択する
      final value = i.isEven() ? d.draw(float()) : d.draw(string());
      ...
    },
  );

deckジェネレーターは、任意のジェネレーターを実行するdrawメソッドを持つオブジェクトを生成します。drawの引数にジェネレーターを指定すると、そのジェネレーターを使ってランダムな値を生成します。mapメソッドやcombineジェネレーターよりも柔軟なテストを実装できます。

「ランダム」を疑う

「プロパティベーステストでは、ジェネレーターが ランダム に生成する入力値で機能テストができる」。私も最近プロパティベーステストに取り組み始めたばかりですが、本を読んだりライブラリを使ってみてもだいたいこのくらいの理解度でした。

実際に生成されるデータを、Pythonのプロパティベーステストライブラリ Hypothesis で確認してみましょう。 Hypothesis をインストールし、以下のコードを実行してください:

from hypothesis import given
from hypothesis import strategies as st

@given(st.integers())
def print_int(x):
    print(x)

print_int()

Hypothesis では、「ストラテジー strategy 」がジェネレーターに相当するコンポーネントです。 @given アノテーションでストラテジーを指定すると、生成された値が関数に渡されます。

このコードを実行すると、 100 個の整数が表示されます (途中を省略):

0
-2088329321
-107
...
19138
-16932
0
...
22587735
-4
-4
...
15820023
-17039
1132181008727235737
完全な出力
0
-2088329321
-107
30540
31590
-126646556799261029466118727496400491262
-59
120
-18364
-2553
12947
-395375784
-395375784
-1698126065338195494
-9933044
-8427408
-21
22245
-86
19138
-16932
0
-88
22587735
-4
-4
10257
17
0
43
-26883
105
24727
20421
-79
26738
-1752309874
1750826043390091266
-407645954
7
1890
7
16779
-7834
-7834
-30
0
-66
-5196
30743
120
-3513428102538797467
-818033726
1110720208
25215540
4751
-90
-90
3
-816
3
85
21876
85
-14
-14
-118952745846941223428316047197423712450
217
25941
21866
21866
21866
27207
18201
25
16532
1453724087561439426
338471515
-1453724089254237319
9710762
-22494
-87
38
6872
-26
0
-100
-25839
-100
20672
0
1
-77
1
1
-292
-1902442358
15820023
-17039
1132181008727235737

何度か実行して、生成された値を確認してみてください。

2回目:

0
1758
-29693
12000
5445
...

3回目:

0
1440722228
83
29461
-11

ざっと眺めてみると、次のことがわかります。

  • 最初の値は 0
  • 同じ値が重複する (それも頻繁に)
  • 2桁以下の値が多く、次に2万前後の値が多い
  • (おそらく) 64ビット以下
    • Pythonのint型の長さに制限はないので、最大値はマシンに依存します (詳細は sys.int_info で取得できます)
  • (おそらく) 最小値と最大値は含まれていない

特に最初の2つ、「最初の値は 0 」と「同じ値が重複する」は意外だったのではないでしょうか？また、最小値と最大値に制限があり (デフォルトの挙動。指定可能) 、64ビットであれば最小値と最大値である -9223372036854775808 と 9223372036854775807 は含まれていません。

偏りの少ないランダムなデータ

標準の乱数APIで生成した値と比較してみましょう。64ビットで10個の値を生成してみます。

>>> for i in range(0, 10): print(random.randint(-(1<<63), 1<<63))
... 
8310784346635777773
-3973264716979059331
-7043924164725946517
-4502560362736688420
1723727242751946619
-7512053481029123229
4262257813441119981
2084711476245707027
3170151199645919677
-9087175782144334735

Hypothesisが生成する値と似ても似つかない値が生成されてしまいました。それもそのはずで、64ビットの範囲は膨大だからです。2桁以下の正負の値が生成される確率は「18,446,744,073,709,551,616分の198」です。たかだか100回の生成で2桁以下の値が生成される可能性は、年末ジャンボ宝くじ1等の当選確率（20,000,000分の1）よりはるかに低くなります。つまり、Hypothesisが生成する値は単純なランダムではないということになります。

生成する値はランダムであるべき？

実は、ランダム性についてHypothesisのドキュメントで触れられています。

引用:

One of the things that is often concerning for people using randomized testing is the question of how to reproduce failing test cases.

It is better to think about the data Hypothesis generates as being arbitrary, rather than random. We deliberately generate any valid data that seems likely to cause errors, so you shouldn’t rely on any expected distribution of or relationships between generated data. You can read about “swarm testing” and “coverage guided fuzzing” if you’re interested, because you don’t need to know for Hypothesis!

訳:

ランダム化テストを使用する際に人々がよく懸念することの一つは、失敗したテストケースをどのように再現するかという問題です。

Hypothesisが生成するデータをランダムではなく、任意のものと考える方が良いでしょう。我々は意図的にエラーを引き起こしそうな有効なデータを生成するため、生成されたデータの予想される分布や関係性に依存すべきではありません。興味があれば、「スワームテスティング」や「カバレッジガイド付きファジング」について読んでみてください。Hypothesisに関しては知る必要はありません！

というわけで、Hypothesisが生成する値は完全なランダムではありません。多様なデータをテストする上で重要なのは、バグの検出とテストの再現性です。64ビット整数のデータが完全なランダムだったら、たかだか100個の値では確実にエラーが発生するとは限りません。運よく見つかったとしても、次の実行では見つからないかもしれません。値が大きいとシュリンクしても最小値が見つからない可能性もあります。

データの重複についても同様です。同じデータを使っているのに成否が異なるケースもあります。そのようなバグが隠れているとき、安易に重複するデータを除いてしまうと、データの範囲を広げても発見できない可能性があります。

テストすべきデータを十分に考え、データ内容をカスタマイズしなければ効果的なテストになりません。データの範囲を絞ってもあまりに広いようであれば、エラー発見時の乱数のシード値を保存するなどして再現性を確保する必要もあるでしょう。

乱数の精度

乱数の精度については、「高いに越したことはないが、多少低くてもクリティカルな要素にはならない」というのがライブラリを作ってみての感想です。精度が低いと重複が増えますが、データの範囲を絞った上で生成回数を増やせばカバーできます。

いまどきの言語は標準ライブラリでメルセンヌツイスターを採用していることが多いので、それを使っておけば問題ありません。

データ生成のアルゴリズム

ジェネレーターやシュリンクのデータ生成アルゴリズムは、特に決まったものはなさそうです。他のライブラリのドキュメントを見ても、生成方法について詳細なアルゴリズムが書かれたものは見かけませんでした。 PropEr の標的型プロパティでの焼きなまし法など、探索アルゴリズムが採用されるケースもありますが、特別な方法はあまり必要なさそうでした。基本的にはデフォルトの生成方法に頼り過ぎず、テストすべきデータをよく考えて明示的に指定するべきかと思われます。

シュリンク

基本的な流れ

シュリンク（収縮）はエラーの最小値を見つけるプロセスです。テスト中にエラーが発生するとシュリンクが始まり、エラーになった値を元にした新しい値を生成してテストを継続します。エラーが発生しなくなったら、最後にエラーが発生した値を最小値とし、テストを終了します。

たとえば、整数ジェネレーターで10がエラーになった場合、次は9以下の値を繰り返し試行し、エラーが出なくなったら最後にエラーが出た値を最小値とします。

ユーザーは最小値を参考にしてデバッグを行えばいいわけです。最小値が小さいほどエラーの原因を特定しやすくなります。最小値が10だった場合と10,000,000だった場合とでは、おそらく10のほうがデバッグしやすいでしょう。10,000,000-10=9,999,990の範囲を調べるコストが浮くからです。（もちろん、他のエラー原因がこの範囲に隠れている可能性もあります。シュリンクはデバッグの目安です）

シュリンクは現実的なコストを考慮しなければなりません。10程度なら1ずつ下げればよさそうに見えますが、エラーの最小値が64ビット符号付き整数の最小値 -9,223,372,036,854,775,808 だった場合、1ずつ下げる方法では1日かかっても終わらないかもしれません。そのため、現実的な時間でテストを終了させるにはシュリンク方法に制限を設ける必要があります。次の制限が一般的です。

  • 基準値を用意する
  • シュリンク回数を制限する

基準値とは、最小値が見つからなかった場合にシュリンクを終了する値です。基準値に近づける形で値の生成と試行を繰り返します。基準値はジェネレーターによって異なりますが、一般的には0や空が使われます。数値なら0に向けて値を下げていき、文字列やコレクションなら長さを空に向けて要素を減らします。0や空でもエラーが発生しなければ、最後にエラーが発生した値が最小値になります。

シュリンク回数はライブラリによって異なります。実行速度が速い言語なら多めに設定しても問題ないでしょう。だいたい50回から100回もあれば十分な精度が得られると思います。トライ＆エラーの回数が増えれば増えるほど詳細な特定ができますが、負荷も大きくなるのでトレードオフです。

シュリンクの回数

シュリンク回数は多ければ良いというわけではありません。シュリンク値の生成とテストの実行には時間がかかります。無制限にシュリンクを行えれば限りなく最小に近い近似値を発見できる可能性が高まりますが、無制限に時間がかかります。そのため、どのライブラリでもシュリンク回数に制限を設けています（jqwikやkiri-checkは基準値に達するまで無制限にシュリンク可能です）。

最小値を効率的に見つけるには、シュリンク回数に期待するよりもデータの範囲を指定すべきです。たとえば、先程のFizzBuzzのコードでは、最も0に近いエラー値は15です。integer()が生成する最大値は9,223,372,036,854,775,807ですが、実際にはFizzBuzzに64ビットの試験は必要ありません。FizzBuzzの用途から考えると、ここまで大きな値を試す必要はありません。せいぜい100あれば十分です。

アルゴリズム

基準値に向かって値を生成するにあたり、最も単純なアルゴリズムは二分法です。エラーが発生した値を出発点とし、値や長さを繰り返し半分に分割します。「256, 128, 64, 32, 16, 8, 4, 2, 1, 0」といった感じです。二分法のメリットは、実装が簡単なことと、少ない試行回数で基準値までたどり着けることです。

ただし、FizzBuzzの例（15の倍数）のようにエラーが飛び飛びになると、二分法ではすべてすり抜けてしまって最小値を見つけにくいケースも出てきます。たとえば105からシュリンクすると、試行する値は52, 26, 13, 6, 3, 1, 0となります。エラーの最小値は15ですが、単純な二分法では105が最小値になります。精度を上げるには分割数を増やすなどの工夫が必要になりますが、現実的にはそこそこの精度でも大きな問題はなさそうです。他のライブラリの実装を覗いてみると意外とシンプルだったりします。

ランダムな値は効果的？

単純な二分法ですり抜ける可能性があるなら、ランダムな要素を追加したらどうかと考えるかもしれません。たとえば、二分法で求めた値にランダムな値を追加するとか、ランダムな数で分割するなどです。ランダムなら、二分法で見つけにくい最小値が見つかる可能性が高いかもしれません。

しかし、シュリンクで生成するデータは一定のルールに従って生成するのが望ましいようです。ジェネレーターの目的がエラーの発見に対してシュリンクの目的はエラーの特定であり、バグ修正で人が介入するターンになるため再現性が重要です。シードを固定すれば同じデータを生成できるとしても、人を混乱させる要因になってしまうかもしれません。

値の変形時のシュリンク

だいたいのライブラリでは、生成された値をmapなどのメソッドで変形（加工）できます。変形後の値でエラーが発生した場合、シュリンクは変形前と変形後のどちらの値が対象になるのでしょうか？

この選択はライブラリによって異なります。変形後の値が対象になる場合、その値の型と結びつけられたジェネレーターが使われることが多いです。ただし、どちらの値がエラー原因とより深い関連があるかどうかは、ライブラリ側では判断できません。

文字コードと日付とタイムゾーン

Unicode

Unicodeのサポートはライブラリによって様々です。Unicodeのコードポイントの範囲は0-10FFFFであり、111万以上の文字を表現できます。現在割り当てられている文字数は11万あります。11万はあまりに範囲が広いので、単純なランダム生成だと期待される文字が生成される確率は限りなく低いでしょう。それでは不便なので、英数字などの特定の文字群を生成するジェネレーターが用意されているライブラリが多いです。ただし、UnicodeカテゴリをサポートしたメジャーなライブラリはHypothesisくらいのようです（kiri-checkも対応しています）。

もしライブラリを実装するなら、 Unicode Character Database で配布されているUnicodeData.txtを解析して、カテゴリごとのすべてのコードポイントを抽出するといいでしょう。AIを利用すれば解析コードを瞬時に生成してくれます。言語によってはUnicodeDataを操作するライブラリが存在しますが、カテゴリごとのコードポイントを取得できるものはたぶん少ないと思います（普通そんな機能は使わない）。

カテゴリは細分化されており、アルファベットだけでもいくつもカテゴリが存在します。改行など、特定のコードポイントの組み合わせが必要な場合もあります。基本的な文字セットを用意するなら、 Swift の CharacterSet などの既存のライブラリを真似すると楽です。

日付とタイムゾーン

日付とタイムゾーンの扱いはライブラリによってまちまちです。実在の日付、ローカル時刻、UTCのみに対応しているライブラリが多いようです。日付（＋時刻）とタイムゾーンの仕様は非常に複雑なので、ライブラリが頑張るよりも、それぞれのユーザーが需要に合わせて実装したほうがいいかもしれません。Hypothesisはタイムゾーンに対応しており、最も日付に強いライブラリと思われます。kiri-checkもHypothesisに倣って一応タイムゾーンに対応しています。

シュリンクの基準値は、Hypothesisでは2000年1月1日としています。開発するシステムの要件定義によって適切な基準値は異なると思いますが、無難な値ではないでしょうか。

架空の日付

架空の日付とは、実在しない日付のことです。うるう年でない年の2月29日や、30日までの月の31日、それからサマータイム開始・終了時に発生する存在しない時刻があります。

たとえば、アメリカのサマータイムの期間は毎年3月の第2日曜日から11月の第1日曜日までで、開始・終了時刻は午前2時です。開始日の午前2時になったら時刻を1時間早めて午前3時とし、終了日の午前2時は逆に1時間戻して午前1時にします。これらの1時間分が存在しない時間になります。開始日なら午前2時から3時までの1時間、終了日なら午前1時から2時までの1時間が存在しません。しかもサマータイムは国や地域によって有無も実施期間も異なります。

架空の日付をサポートしている主要なライブラリは、Hypothesisとfast-checkくらいのようです。kiri-checkもサポートしていますが、サマータイムに関する架空の日付は（大変そうなので）サポートしていません。

まとめ

実際にライブラリを作ってみると、生成されるデータの質が意外と心許ないことがわかります。それもそのはずで、膨大な組み合わせの中からせいぜい数百のデータを選ぶに過ぎないのです。すべてのテストに成功したとしても、もしかしたら成功しやすいデータが偶然選ばれているだけで、致命的なバグが見過ごされているかもしれません。また、テスト対象と同じロジックを実装するため、テスト対象とテストの両方に同じバグを抱えてしまう可能性もあります。その場合もテストに成功してしまえばバグが見過ごされやすくなります。どうですか？不安になってきませんか？

プロパティベーステストの本を読み込むのもいいですが、ライブラリを自作してみるのも理解を深めるいい方法だと思います。幸い、特別な知識は必要ありません。おそらく最初に動いたときは、まったく役に立ちそうにないデータを見て驚くでしょう。どうすれば役に立つデータを生成できるか、そもそも役に立つデータとは何か、テストに関する諸々を考えるいい機会にもなります。直接的な価値を生む類いのプロダクトではないのでコスパはよくないかもしれませんが…

よかったらバッジをいただけると嬉しいです。 kiri-check を使ってみて意見をいただけるのも嬉しいです。コーヒー代とモチベの足しにします。

Discussion