Fuzzers should exhaustively check all values of a type if possible/reasonable

[Janiczek]

We've been talking with @gampleman about this a few times, and I believe I have a rough plan of attack.

Expand the Fuzzer definition, add an exhaustive : Maybe (() -> List a) field inside or make a sum type:

type Fuzzer
  = Random (PRNG -> GenResult a)
  | Exhaustive (() -> List a)

For certain fuzzers (bool, unit, intRange in case the range is below some threshold, etc.) this would be populated with \() -> [False, True] etc. and would be used instead of randomly generating values.

For other fuzzers it would be disabled (float, int, string, list etc.).

Then there's a class of fuzzers which preserve the exhaustive mode if all their children are exhaustive: map, lazy, tuple, triple, oneOf, etc.

---

We would still honor the runs : Int config, but we'd warn if exhaustiveness was possible but above the threshold: something like

NOTE: Fuzzer for this test can be checked exhaustively (324 cases). To enable the exhaustive check increase your --runs configuration value.

[gampleman]

I think the cool and tricky thing to note is that if you have exhaustive fuzzers, then the random generation strategy can switch to sampling from that list. Ideally that would be something like possibleValues |> shuffle |> take runs, so that you are guaranteed to not repeat values.

I think from a performance perspective it would be somewhat challenging how to do this efficiently for large possibleValues, as you'd want that to be a lazy data structure which supports random access (and length) and composition (i.e. you can map2 over these datastructures and get a composite that has the same properties).

[miniBill]

For random access you could have the function be Exhaustive { count : Int, generate : Int -> a } (which also avoids the issue of possibly generating massive lists). Some examples:

bool =
    Exhaustive { count = 2, generate = \x -> modBy 2 x == 0 }

map f (Exhaustive e) =
    Exhaustive { count = e.count, generate = \x -> f (e.generate x) }

map2 f (Exhaustive l) (Exhaustive r) =
    Exhaustive { count = l.count * r.count = generate = \x -> f (l.generate (x // r.count)) (r.generate (x |> modBy r.count))

oneOf xs =
    Exhaustive { count = List.length xs, generate = \x -> List.Extra.getAt (modBy (List.length xs) x) xs}

It might also be useful to have an inverseGenerate : a -> Int, because then you can do things like fuzzing functions

[gampleman]

The other thing that should be said about this is that ideally we would want to support some sort of combination of strategies. A simple example is Result String Bool. We'd likely define it something like:

Fuzz.oneOf 
    [ Fuzz.map Err Fuzz.string
    , Fuzz.map Ok (Fuzz.oneOfValues [True, False])
    ]

The ideal behavior would be (with sufficiently high runs) to test Ok True, Ok False exhaustively and spend the rest of the runs testing the Err cases.

How to model that?

```elm type Fuzzer a = Random (PRNG -> GenResult a) | Exhaustive { count : Int, generate : Int -> a } -- lazy version | Choice (List (Fuzzer a)) -- Potentially defunctionalize others, like map2? numCases : Fuzzer a -> Int numCases fuzz = case fuzz of Random _ -> maxInt Exhaustive { count } -> count Choice options -> List.sum (List.map numCases options) isExhaustive : Int -> Fuzzer a -> Bool isExhaustive runs fuzz = numCases fuzz <= runs sample : Int -> Fuzzer a -> List a sample runs fuzz = case fuzz of Random rnd -> doWhateverWeCurrentlyDo runs rnd Exhaustive {count, generate} -> if count <= runs then List.range 0 count |> List.map generate else -- ugh, there's probably a more efficient algorithm for this List.range 0 count |> shuffle |> List.take runs |> List.map generate Choices options -> if isExhaustive runs fuzz then List.concatMap (sample runs) options else let fairShare = (runs // List.length options) (exhaustive, infinite) = List.parition (isExhaustive fairShare) exhaustiveNumCases = List.map numCases exhaustive |> List.sum infiniteN = (runs - exhaustiveNumCases) // List.length infinite in List.concatMap (sample fairShare) ++ List.concatMap (sample infiniteN) infinite ```

[miniBill]

Going to drop this here so I can write a more detailed list of ideas later: https://en.m.wikipedia.org/wiki/Lehmer_code

@gampleman I think your idea of "if runs is high enough, check all the exhaustive part" is really interesting, and probably not super hard to do.