[ANN] Bam - A property-based testing with internal shrinking

I am excited to introduce Bam, a robust and versatile property-based testing (PBT) library. Bam simplifies the process of testing properties across a wide range of randomly generated values, making it easier to identify and debug issues in your code.

Key Features

  • Monad-like Generators: Create new generators easily with a monad-like pattern that works seamlessly with shrinking mechanisms.
  • PPX Support: Automatically derive generators based on type descriptions. The customizable deriver ensures smooth integration into your codebase.
  • Tezt Integration: Integrates with the Tezt test framework, providing a user-friendly experience, especially notable in debugging scenarios.
  • Internal Shrinking: Various default shrinking strategies help efficiently pinpoint minimal counterexamples. Internal shrinking ensures that only ‘smaller’ values are used during the process, and this is done in a way that is compatible with the monad-like operators.
  • Custom Shrinking: Define custom shrinkers that work well with the existing shrinking strategies.

Installation

You can install Bam using opam:

opam install bam tezt-bam

Getting started

Here is an example to get you started:

open Tezt_bam

type t = Foo of {a: int; b: string} | Bar of int list [@@deriving gen]
(** The deriver creates a value [val gen : t Bam.Std.t]. *)

let register () =
  let property = function
    | Foo {a; b} ->
        if a > 1_000 && String.contains b 'z' then
          Error (`Fail "A counter-example was found")
        else Ok ()
    | Bar [1; 2; 3; 4] ->
        Error `Bad_value
    | Bar _ ->
        Ok ()
  in  
  Pbt.register ~__FILE__ ~title:"Simple example of bam" ~tags:["bam"; "simple"]
    ~gen ~property ()

let _ = 
    register ();
    Test.run ()

There are several more detailed examples in the repository to show you around the library.

Contributions

Contributions from the community are welcome! If you have ideas, bug reports, or improvements, feel free to share them!

6 Likes

Can it be compared to GitHub - c-cube/qcheck: QuickCheck inspired property-based testing for OCaml. ?

My work around Bam started after using “QCheck” and especially “QCheck2” quite a lot for the Tezos project.

With respect to QCheck, QCheck2 came with “integrated” shrinking allowing to derive automatically shrinkers for generators. This aim to simplify debugging when a counter-example is found, so that a smaller example is reported to the user.

However, this came with a cost:

  • Performance-wise, there was a regression from “QCheck”, especially the time taken to report a counter-example because the shrinking process was taking a lot of time
  • At some point, we even faced an issue were the shrinking process never ended. We started to implement an ad-hoc shrinker but it was not working either and we never really figured out. The solution was to deactivate shrinking
  • There are other UX considerations: debugging can be tedious (especially “hello” debugging)

So basically Bam started as an experiment to understand shrinking and come up with something easier to understand and compose better. This is why bam relies mainly on monadic operators.

This makes the writing of generators easier, the shrinking is internal ensuring the shrinking won’t new random values. If you use the mondic operator of QCheck2, last time I checked it was not the case. This is why to create a generator for a pair, it is recommended to use tup2 instead of monadic operators.

Bam library is rather small thanks to having monadic-operators.

I also developped the integration of bam with Tezt in a way to avoid currently pitfalls we had with QCheck2:

  • You can easily control the stopping condition of the test
  • The test can be easily run in parallel or in a loop mode to help you find a counter-example quicker
  • The runner can fail if not enough values were generated (likely due to a regression)
  • It captures the output, so that only the one for the counter-example reported to the user is shown. This is very handy during debugging. Otherwise, it is quite tedious to understand which line comes from which attempt made by the shrinker
  • It is easy to opt-out from shrinking if it takes too much time. Can be useful for a CI. Shrinking only needs to be executed locally (assuming the property is deterministic) with a given seed

I also had some fun trying to define shrinking strategies allowing you to skip elements in a list. This is very handy when your property is about running a scenario made of a list of actions (a use-case very close to the monolith library from François Pottier). In general the initial counter-example contains superfluous actions. Such a strategy allows you to remove them to ease the debugging.

I don’t have concrete data to compare Bam with QCheck2 at the moment. Let me know if you have ideas to make an objective comparison between those two libraries.

2 Likes

Thank you! I currently work on property-based testing research, so this looks really exciting!

I was wondering in your opinion, how Bam compares to Jane Street’s PBT libraries such as Base_quickcheck and Core.Quickcheck?

I am not familiar with their library. It seems we both use a splittable PRNG, I guess to make sure no new values are generated during shrinking. However, the approach for shrinking seems different but I could not make a concrete comparison for now.

Something I have tried to do in bam, is to make the default shrinking strategy as much as possible predictable and easily customizable.

To understand the default shrinking strategy, one must understand how the bind operator works. I have started a documentation there.

For example the list generator written this way:

let list : size:int Gen.t -> 'a Gen.t -> 'a list Gen.t =
   fun ~size gen ->
    let open Gen.Syntax in
    let* size = size in
    let rec loop n acc =
      if n = 0 then Gen.return (List.rev acc)
      else
        let* x = gen in
        loop (n - 1) (x :: acc)
    in
    loop size []

which is a very natural way to write a generator for lists, enables to derive automatically a shrinker that first reduces on the size of the list, and then reduces the values one by one starting from the first one.

The fact we can derive such a shrinker automatically without having to write anything makes me think Bam can be helpful to write better shrinkers/generators on more complex examples.

As mentioned above, the core of Bam allows you to extend this generator so that you can implement a shrinking strategy where at most n elements are skipped during the search. This is implemented in the standard library of Bam.

I would be curious to know more about Janestreet approach, or other PBTs and try to compare them. But I suspect it is non-negligible amount of time to spend on it.

1 Like

Regarding the comparison of property-based testing frameworks, this is a very nice comparison: GitHub - jmid/pbt-frameworks: An overview of property-based testing functionality

2 Likes

Thank you for the detailed reply! Will check out the documentation!