詳解！ Elm における Fuzzing

先日行われた 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 はコンパイルできなくなる気がしますが、それはまた別の話。