先日行われた We Are JavaScripters! @23rd で、Elm のテストフレームワーク elm-test に搭載されている Fuzzing 機能について発表してきました。
Fuzzing を利用するとテストデータを自動で生成することができるため、例えば「encode と decode を行うと元に戻る」といった、入力に依存しない 関数の性質に関するテスト をより簡単かつ効率的に実装することができます。
さらに、後で詳しく解説する通り、elm-test の Fuzzer にはバグが起こりやすいエッジケースを集中的に生成してくれるというメリットもあります。
elm-test の使い方は、すでに偉大なる先達によって大部分が解説済みです。普通にテストする上では、これらの内容を押さえておけば困ることはないでしょう。
- [Elm] Fuzzer でテストデータを量産しよう (by jinjor さん)
- [Elm]キミだけのッ最強Fuzzerを手に入れろ！ (by arowM さん)
そこでこの記事では、もう少し内部の実装にも踏み込んで説明します。なお、ソースコードを載せる際には執筆時点の master ブランチ (19f0bb3) を参照しています。
Fuzzer コンビネータの一覧
elm-test では、Fuzzing 関連の機能は Fuzz モジュールで定義されています。このモジュールが expose しているすべての関数を以下にリストアップしました。
便宜上「コンビネータ」と呼んではいますが種類さほど多くなく、Persec のような色々入ったライブラリを想像するとちょっと肩透かしかもしれません。特定の条件に従うような値を生成したい場合は、自分で Fuzzer を定義する必要があります。
組み込み型に対応するタイプ
基本パーツとなる Fuzzer です。読んで字のごとく、生成する値の型名に対応した Fuzzer が用意されています。
bool : Fuzzer Bool int : Fuzzer Int float : Fuzzer Float char : Fuzzer Char string : Fuzzer String order : Fuzzer Order unit : Fuzzer ()
最後の unit は常にユニット値 () のみを生成する Fuzzer です。テストに直接関係しない引数をプレースホルダーとして埋めるために用意されていて、例えば elm-test の内部では Result 型のエラー側に unit が使用されています。
パラメータが付いたタイプ
Int および Float 用には、範囲を指定するとその間の値を生成する Fuzzer が用意されています。
intRange : Int -> Int -> Fuzzer Int floatRange : Float -> Float -> Fuzzer Float percentage : Fuzzer Float
percentage は 0 から 1 の値を生成するための Fuzzer です。パーセンテージなら 0 から 100 であるべき気がしますがどうしてこうなった。
用途によっては最小値（もしくは最大値）のみ指定したいこともあるでしょう。その場合は intRange 0 Random.intMax のようにすれば表現することができます。
候補から選択するタイプ
あらかじめいくつかの Fuzzer を与えると、その中から乱択するタイプです。
constant : a -> Fuzzer a oneOf : List (Fuzzer a) - Fuzzer a frequency : List ( Float, Fuzzer a ) -> Fuzzer a
constant x は常に同じ値 x を返す Fuzzer です。これと oneOf を組み合わせると、与えられた選択肢からランダムにどれかを選ぶ Fuzzer になります。
logLevel = Fuzzer String logLevel = Fuzz.oneOf [ Fuzz.constant "ERROR" , Fuzz.constant "WARN" , Fuzz.constant "INFO" ]
また oneOf の代わりに frequency を使用すると、選択される割合に重みを掛けることができます。例えば次のように書けば、"ERROR" を 10%、"WARN" を 30%。"INFO" を 60% の内訳で生成する Fuzzer が得られます。
logLevel = Fuzzer String logLevel = Fuzz.frequency [ (1, Fuzz.constant "ERROR") , (3, Fuzz.constant "WARN") , (6, Fuzz.constant "INFO") ]
コンテナタイプ
中身の型に対する Fuzzer が与えられているとき、外側のコンテナ部分を含めた値を生成させるために使用します。
maybe : Fuzzer a -> Fuzzer (Maybe a) result : Fuzzer error -> Fuzzer value -> Fuzzer (Result error value) list : Fuzzer a -> Fuzzer (List a) array : Fuzzer a -> Fuzzer (Array a) tuple : (Fuzzer a, Fuzzer b) -> Fuzzer (a, b) tuple3 : (Fuzzer a, Fuzzer b, Fuzzer c) -> Fuzzer (a, b. d) tuple4 : (Fuzzer a, Fuzzer b, Fuzzer c, Fuzzer d) -> Fuzzer (a, b. c. d) tuple5 : (Fuzzer a, Fuzzer b, Fuzzer c, Fuzzer d, Fuzzer e) -> Fuzzer (a, b, c, d, e)
合成を定義するタイプ
必要な Fuzzer が以上の関数の組み合わせで表現できない場合は、Fuzzer どうしの合成を自分で定義しましょう。
Fuzz.map
map : (a -> b) -> Fuzzer a -> Fuzzer b map2 : (a -> b -> c) -> Fuzzer a -> Fuzzer b ->Fuzzer c map3 : (a -> b -> c -> d) -> Fuzzer a -> Fuzzer b ->Fuzzer c -> Fuzzer d map4 : (a -> b -> c -> d -> e) -> Fuzzer a -> Fuzzer b -> Fuzzer c -> Fuzzer d -> Fuzzer e map5 : (a -> b -> c -> d -> e -> f) -> Fuzzer a -> Fuzzer b -> Fuzzer c -> Fuzzer d -> Fuzzer e -> Fuzzer f
典型的な用途として、自作のデータ型に対して、各フィールド用の Fuzzer にコンストラクタを map すればそのデータ型用の Fuzzer を定義することができます。例えば以下は、String、Int、Bool をそれぞれ生成する Fuzzer を組み立てて User 型の Fuzzer を得る例です。
type alias User = { name : String , age : Int , active : Bool } user : Fuzzer User user = Fuzz.map3 User Fuzz.string (Fuzz.intRange 20 60) Fuzz.bool
map は 5 引数までしか用意されていません。6 個以上のフィールドを持つようなレコードに対して Fuzzer を定義したい場合には、次の andMap を使用しましょう。
Fuzz.andMap
andMap : Fuzzer a -> Fuzzer (a -> b) -> Fuzzer b
Haskell でいうところの Applicative 型クラスの <*> に相当します。部分適用を繰り返すことで、任意個の引数を持つ関数を Fuzzer に持ち上げることができます。
上で map3 を用いて定義した User の例は、次のように書き換えることが可能です。
user : Fuzzer User user = Fuzz.map User Fuzz.string |> Fuzz.andMap (Fuzz.intRange 20 60) |> Fuzz.andMap Fuzz.bool
Fuzz.andThen
andThen : (a -> Fuzzer b) -> Fuzzer a -> Fuzzer b
Haskell でいうところの Monad 型クラスの =<< に相当します。複数の Fuzzer に対して依存関係にある値を生成させることができます。
あまり効果的な用途が思いつかなかったのですが、例えば以下の Fuzzer は一度生成した文字列を逆順にしてくっつけることで、偶数文字からなる回文をランダムに生成します。
mkPalindrome : String -> Fuzzer String mkPalindrome x = Fuzz.constant <| x ++ String.reverse x palindrome : Fuzzer String palindrome = Fuzz.string |> Fuzz.andThen mkPalindrome
その他
それ以外にも、特殊な用途を持つ Fuzzer がいくつか定義されています。
Fuzz.invalid
invalid :: String -> Fuzzer a
常に失敗する Fuzzer で、第一引数はエラーメッセージを表します。
他の Fuzzer コンビネータに対して無効値が与えられたときに使用します。例として、elm-test 内では oneOf に空リストが与えられた場合の値として使用されています。
Fuzz.conditional
conditional : { retries : Int, fallback : a -> a, condition : a -> Bool } -> Fuzzer a -> Fuzzer a
いったん値を生成した後、それが条件 condition に合わないときに生成し直します。retries は再生成の最大回数で、それでも条件に合う値が得られなかった場合は fallback から得られる値を（condition は無視して）使用します。
ちなみに ドキュメント によれば retries の推奨値は 10 です。
custom
custom : Generator a -> Shrinker a -> Fuzzer a
ここまでに挙げたすべての Fuzzer の大元になっている最も抽象的な定義です。
定義を見ると、a 型に対する Fuzzer を定義するためには、a 型に対する Generator と Shrinker を与えればよいことが分かります。次節でそれぞれの役割を確認しましょう。
Fuzzer の構成要素と役割
Generator と Shrinker について説明する前に、Fuzz モジュール冒頭の ドキュメンテーションコメント を少し眺めてみましょう。
A `Fuzzer a` knows how to create values of type `a` in two different ways. It
can create them randomly, so that your test's expectations are run against many
values. Fuzzers will often generate edge cases likely to find bugs. If the
fuzzer can make your test fail, it also knows how to "shrink" that failing input
into more minimal examples, some of which might also cause the tests to fail. In
this way, fuzzers can usually find the smallest or simplest input that
reproduces a bug.
ここでは Fuzzing に関する重要なふたつの性質が述べられています。
- エッジケース（コーナーケース）をより頻繁に生成する
- テストに失敗した場合、入力を「縮小する」ことで失敗を再現する最小例を求める
前者の戦略を定義するのが Generator、後者の戦略を定義するのが Shrinker です。
Generator
エッジケースの判定
まずドキュメント通り、本当にエッジケースが多めに選ばれていることを確認するために、-4 以上 5 以下の整数を生成させてみましょう。intRange -4 5 により 10,000 ケース生成したところ、内訳は次のようになりました。
| value | count |
|---|---|
| -4 | 1833 |
| -3 | 745 |
| -2 | 823 |
| -1 | 802 |
| 0 | 825 |
| 1 | 825 |
| 2 | 787 |
| 3 | 758 |
| 4 | 788 |
| 5 | 1814 |
一見して、-4 と 5 が他の数値より特異的に多く生成されていることがわかります。区間の両端の値ですね。確かにバグの原因になる可能性は高そうです。
では、範囲を指定しない int ではどうでしょう？ 同じく 10,000 ケース生成して 0 の個数を数えてみると、10,000 個中 424 個が 0 でした。int は Int 値全体を生成する可能性があるため、424/10000 というのは特異的に多く 0 が生成されていることを予想させます。
もし仮に、intRange が単純に int により整数を生成してから -5 以下と 6 以上の数を捨てているとしたら、intRange の場合でも 0 にピークがあるはずです。このことから、生成される値の「エッジケースらしさ」は Fuzzer によって異なるロジックで判定されていることがわかります。
Generator の実装
この「エッジケースらしさ」を Fuzzer ごとに定義しているのが Generator です。
intRange の定義を見てみましょう。hi < lo の部分はエラー処理ですが本筋に関係ないので省略してあります。
intRange : Int -> Int -> Fuzzer Int intRange lo hi = if hi < lo then ... else custom (Random.frequency [ ( 8, Random.int lo hi ) , ( 1, Random.constant lo ) , ( 1, Random.constant hi ) ] ) (Shrink.keepIf (\i -> i >= lo && i <= hi) Shrink.int)
custom の第一引数に注目してください。Fuzzer 一覧の中に登場した Fuzz.frequency と紛らわしいですが、ここでは Random.frequency によって Generator が定義されていることがわかります。
区間の下端 lo と上端 hi の間の整数に対して 80%、さらに上下端の値については固定値に 10% の重みが掛けられています。これが、先ほど intRange -4 5 で -4 と 5 が多めになっていた原因です。
同様に int の実装を確認すると次のようになっています。
int : Fuzzer Int int = let generator = Random.frequency [ ( 3, Random.int -50 50 ) , ( 0.2, Random.constant 0 ) , ( 1, Random.int 0 (Random.maxInt - Random.minInt) ) , ( 1, Random.int (Random.minInt - Random.maxInt) 0 ) ] in custom generator Shrink.int
こちらも同じく、ケースごとの生起確率が定義されています。int の場合は区間ごとに確率が変えられていて、特に注意すべきケースは 0、また極端な値よりも -50 から 50 までの範囲を重視する、という定義になっています。
Shrinker
反例の発見
それでは二点目の論点に移りましょう。Shrinker について説明するために、まずわざと失敗するテストを書いてみます。
suite : Test suite = describe "String.reverse" [ fuzz Fuzz.string "is identity" <| \randomString -> randomString |> String.reverse |> Expect.equal randomString ]
このテストが判定しているのは「任意の文字列は、反転すると元の文字列に等しい」ですね。当然、回文でない文字列に対してこのテストは失敗します。
elm-test 0.18.12
----------------
Running 1 test. To reproduce these results, run: elm-test --fuzz 100 --seed 1428851996
↓ Example
↓ String.reverse
✗ is identity
Given "\t\n"
"\n\t"
╷
│ Expect.equal
╵
"\t\n"
...
テストの反例として "\t\n" が見つかりました。これ以外に複数挙げられる反例も 2 文字になっているはずです。
しかし、Generator がランダムに生成した値に対して単純に条件を判定しているとするとこれはやや奇妙です。当然もっと長い（回文でない）文字列も検出されてしかるべきに思えます。
逆に言えば、ドキュメントにうたわれている通り、Fuzzer は何らかの戦略によってテストを失敗させる「最小の例」を見つけていることになります。この戦略を定義しているのが Shrinker です。
Shrinker の役割
Shrinker は別パッケージ eeue56/elm-shrink で定義されています。
type alias Shrinker a = a -> LazyList a
標語的に述べるならば、入力された値を何らかの意味で「縮小」する関数が Shrinker です。複数の縮小結果を候補として考えるため、戻り値は（遅延）リストになっています。
Fuzzer は、次のような考え方で Shrinker 利用してテストが失敗する最小の入力を探します。
- テストが失敗した入力に対して、Shrinker で一段階「縮小」した値の候補の一覧を得る
- 「縮小」した値を新しい入力とし、テストが失敗する限り同じ手順を繰り返す
- 失敗しなくなったひとつ手前の入力が最小の反例
つまり先ほどの回文の例で言えば、最初に生成した（ほぼ確実にテストが失敗する）例から始めて文字列を「縮小」していくと、1 文字まで縮小された時点でテストが成功するようになります。結果として 2 文字の例が「最小の反例」として出力されるわけです。
Shrinker の実装
上では「文字列を縮小する」と簡単に書きましたが、実際の Shrinker は単に文字列の長さを縮めているだけではありません。実際にどのような実装になっているかも確認しておきましょう。以下に挙げたのが Shrink.string の実装です。
string : Shrinker String string = convert String.fromList String.toList (list character)
convert は文字列と文字のリストを相互変換するために使用されますが、「縮小」の動作にとって本質的ではありません。構成要素である Shrink.character と Shrink.list についてそれぞれ追いかけます。
Shrink.character
まず Char 型に対して定義された Shrinker です。
character : Shrinker Char character = atLeastChar (Char.fromCode 32) atLeastChar : Char -> Shrinker Char atLeastChar char = convert Char.fromCode Char.toCode (atLeastInt (Char.toCode char)) atLeastInt : Int -> Shrinker Int atLeastInt min n = if n < 0 && n >= min then -n ::: Lazy.List.map ((*) -1) (seriesInt 0 -n) else seriesInt (max 0 min) n
定義を追いかけていくと、文字コード n を持つ文字の「縮小」は、最終的に Int 区間の「縮小」である seriesInt 32 n に帰着されています。seriesInt の実装は以下です。
seriesInt : Int -> Int -> LazyList Int seriesInt low high = if low >= high then empty else if low == high - 1 then low ::: empty else let low_ = low + ((high - low) // 2) in low ::: seriesInt low_ high
このロジックに従うと、例えば文字コード 42 の '*' を「縮小」すると得られる候補は以下のリストであることがわかります。
Char.fromCode 32 ::: Char.fromCode 37 ::: Char.fromCode 39 ::: Char.fromCode 40 ::: Char.fromCode 41 ::: empty
すなわち、テストを失敗させる Char 型の値が発見された場合 Fuzzer は、元の値より文字コードが小さい側の印字可能文字を（元の値に近いほど密に）いくつかピックアップし、それでもテストが失敗するかどうか試す、ということになります。
Shrink.list
次に List a 型に対する Shrinker の実装です。
実際には遅延リストである Lazy.List a 型を経由して定義されていますが、ここではアルゴリズムに対する分かりやすさを優先して通常の List a で書き直してあります。擬似コードみたいなものだと思ってください。
list : Shrinker a -> Shrinker (List a) list shrink l = let n : Int n = List.length l in List.Extra.andThen (\k -> removes k n l) (List.Extra.takeWhile (\x -> x > 0) (List.Extra.iterate (\n -> n // 2) n)) +++ shrinkOne l shrinkOne : Shrinker a -> List a -> List (List a) shrinkOne shrink l = case l of [] -> [] x :: xs -> List.map (flip (::) xs) (shrink x) ++ List.map ((::) x) (shrinkOne xs) removes : Int -> Int -> Shrinker (List a) removes k n l = if k > n then [] else if List.isEmpty l then [ [] ] else let first = List.take k l rest = List.drop k l in rest :: List.map ((++) first) (removes k (n - k) rest)
ロジックを追っていくと、リストを「縮小」した結果は
shrinkOneによって得られる、リストの各要素に Shrinker を適用したものremovesによって得られる、元のリストから一部の要素を除外したもの
のいずれかに由来することがわかります。
具体例で考えましょう。a 型の値 x、y、z があって、あらかじめ与えられた shrink : Shrinker a によってそれぞれ
shrink x == x1 ::: x2 ::: empty shrink y == y1 ::: y2 ::: y3 empty shrink z == z1 ::: empty
のように「縮小」されるとします。このとき、List a 型の値 [x, y, z] は新しく組み立てられた list shrinker : Shrinker (List a) によって
list shrinker [x, y, z] == [] ::: [y, z] ::: [x, z] ::: [x, y] ::: [x1, y, z] ::: [x2, y, z] ::: [x, y1, z] ::: [x, y2, z] ::: [x, y3, z] ::: [x, y, z1] ::: empty
と「縮小」されます。リストの長さもしくは各構成要素のいずれかの意味で、元の値 [x, y, z] より小さくなっていることがわかります。
まとめ
今回の記事では、elm-test の Fuzz モジュールの実装について簡単にソースコードを挙げながら解説しました。特に
- 小さく単純な Fuzzer を組み立てることでより大きなデータ型や複雑な条件を表現する Fuzzer を構築できる
- Fuzzer は Generator と Shrinker によって構成される
という二点がポイントです。
ところで、つい先日 Elm の v0.19 がリリース されましたね。かなりいろいろな変更が入ったらしく、現在の elm-test はコンパイルできなくなる気がしますが、それはまた別の話。
