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?

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.

[miniBill]

What should happen when count gets bigger than - say 2^50? It's still a safe int, but you can't really do 2^50 tests, so at that point it doesn't make sense to talk about exhaustive.

On the other hand it count is something like 1000 then we can definitely do an exhaustive test.

So, this implies that we always want to keep the prng generation around, even for exhaustive ones, because we may need it.

Where do we want to set the line? It should be... somewhere between 100 and 2^53 😅

[miniBill]

I have (a fragment of) the idea in https://github.com/miniBill/elm-explorations-test/tree/exhaustive-test
This is just adding the data required for exhaustive checking, not using it yet.
The issue is that it runs out of memory when calling listOfLengthBetween, because of how it's generating it 🤔

The issue is implementing andThen, without it everything works fine.

[miniBill]

Ok, I think I've fixed list generation such that it doesn't explode, but I think andThen is still problematic and prone to making tests take incredibly long

In particular the test script goes from 5ish seconds to 3 minutes