Fuzzers should exhaustively check all values of a type if possible/reasonable
Opened this issue · 4 comments
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.
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).
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
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?
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
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.