Support generators that may fail to make a value

[sir4ur0n]

While migrating some tests from Crowbar to QCheck, I could not find a way to "behave" when failing to generate a value. As a minimal example, consider I have my business code:

type foo = private int

(** Smart constructor, ensures invariants *)
val make_foo : int -> (foo, string) result

Now I want to write a foo QCheck.arbitrary or foo QCheck.Gen.t, but I can't reproduce all the preconditions on the input int, so the technique often used is to use an arbitrary int, call the smart constructor, and if the result is failed (Error "Invalid input", None, etc.):

• either give up (similar to assume or assume_fail but in the arbitrary, not the test)
• or try again with a new random int

Give up

I could not find a way to give up during generation (in Crowbar this is bad_test ()), is there such a way?

Try again

I managed to make it work as such:

  (** Convert a generator of ['a option] into a generator of ['a] by generating values until one is not [None]. *)
  let rec gen_backtrack (gen : 'a option QCheck.Gen.t) : 'a QCheck.Gen.t =
   fun random ->
    match gen random with None -> gen_backtrack gen random | Some a -> a

  (** Convert an ['a option arbitrary] into a ['a arbitrary]. For generation, it calls the optional generator until a [Some] value is generated. For shrinking, it ignores [None] values. *)
  let arb_backtrack
      ({gen; print; small; shrink; collect; stats} :
        'a option QCheck.arbitrary) : 'a QCheck.arbitrary =
    let gen = gen_backtrack gen in
    let print = Option.map (fun print_opt a -> print_opt (Some a)) print in
    let small = Option.map (fun small_opt a -> small_opt (Some a)) small in
    (* Only shrink if the optional value is non-empty. *)
    let shrink =
      Option.map
        (fun shrink_opt a f -> shrink_opt (Some a) (Option.iter f))
        shrink
    in
    let collect =
      Option.map (fun collect_opt a -> collect_opt (Some a)) collect
    in
    let stats =
      List.map (fun (s, f_opt) -> (s, fun a -> f_opt (Some a))) stats
    in
    QCheck.make ?print ?small ?shrink ?collect ~stats gen

I propose both capabilities are added in QCheck, what do you think?

[c-cube]

I need to look more before truly replying, but take a look at https://github.com/gasche/random-generator/ in the meantime!

[sir4ur0n]

Yes sorry, I should have mentioned that: I already took a look (and I actually took inspiration from it, cf the name backtrack) :sweat_smile:

[sir4ur0n]

I should think twice before hitting "Comment" :bow:

To further explain: I implemented it because:

• The library random-generator is not on Opam
• There is no explanation as to how to use it with QCheck
• I did not see in random-generator how to transpose the concept of arbitrary which is bigger than Gen.t
• The author himself kindly encourages devs to steal his design/impl :grin:

I consider the value of this library to be in its interface, not necessarily its implementation. I think the current interface is solid (though it can still be improved) and encourage people writing random generators to steal and reuse it -- or at least feel inspired by it.

The benefit of embarking such features in QCheck is a simpler, faster dev UX

[c-cube]

There is no explanation as to how to use it with QCheck

I can at least mention that the 'a QCheck.Gen.t is compatible with the random-generator type (it's Random.State.t -> 'a basically).

[jmid]

I think it is a good idea to add a sub-module of backtracking (option-valued) generators similar to https://github.com/gasche/random-generator/. For both

• eff-tester https://github.com/jmid/efftester and
• wasm-prop-tester https://github.com/jmid/wasm-prop-tester we ended up writing "manual backtracking" generators. That option-dispatching logic could ideally be reused.

[ghilesZ]

About generators that may fail, I also already felt the need for such a feature and we talked briefly about that in #99 . I finally managed to bypass it in a hackish way, but i would like to see such generators in QCheck.

[sir4ur0n]

Small remark coming from a review on my current implementation: it would be great to add (optional) arguments to configure how to behave if the recursive calls fail too... E.g. arb_backtrack ~max_tries:10

Ideas:

• max number of tries
• try forever
• should it be linked to the warning/error if no values passed the assumptions?