-
Notifications
You must be signed in to change notification settings - Fork 40
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Fuzzers should exhaustively check all values of a type if possible/reasonable #188
Comments
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 I think from a performance perspective it would be somewhat challenging how to do this efficiently for large |
For random access you could have the function be 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 |
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 Fuzz.oneOf
[ Fuzz.map Err Fuzz.string
, Fuzz.map Ok (Fuzz.oneOfValues [True, False])
] The ideal behavior would be (with sufficiently high 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 |
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: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 likeThe text was updated successfully, but these errors were encountered: