# Don't fear the shrinking - François Thiré - Software Engineer at Nomadic Labs (working for the Tezos blockchain) --- # Context - Writing **Property-Based Tests** allows to gain more confidence than unit tests - This was applied **successfully** on many components of the Tezos blockchain and allowed to detect many bugs (poke Julien Debon & Clément Hurlin) - We are using [QCheck2](https://opam.ocaml.org/packages/qcheck/) (thanks Julien :pray:) and [Tezt](https://opam.ocaml.org/packages/tezt/) --- # How this journey started - Gossipsub: A P2P protocol (state machine) - We encountered two kind of issues: - A test could <span style="color:red">hang for a while</span> - We tried to modify the **shrinking** <span style="color:red">strategy without success</span> :arrow_right: I reimplemented a PBT framework! --- # Property-Based Testing ```ocaml (* Provided by the framework *) type 'a property = 'a -> bool type 'a gen val run : 'a property -> 'a gen -> bool (* Provided by the developer. *) type t let property : t -> bool = ... let gen : t Gen.t = ... ``` --- # Example ```ocaml type t = int list let property l = l |> List.sort_uniq compare |> List.length < 3 let gen = PBT.Gen.list ~size:10 int_gen let () = PBT.run property gen ``` --- # Result ```bash= > Counter-example found: [234567;1230;3341;5098723123;23459087;1231094111] ``` --- # Let's see the shrink --- :::info **shrinking** uses a heuristic to find a "smaller" counter-example ::: ```bash= > Counter-example found: [0;1;2;3] ``` --- # Question How to implement a <span style="color:#4169e1">good</span> shrinking heuristic? --- # State of the art - *External shrinking*: The user *explains* to the framework how to shrink - *Integrated shrinking*: The framework can derive a shrinker for generated values automatically - *Internal shrinking*: The framework can derive *good* shrinkers for generated values automatically --- What is a generator? ```ocaml type 'a gen = unit -> 'a let int_gen : int gen = fun () -> Random.int () ``` --- - How can we **shrink** the initial value? - Two solutions: - Shrinking is indepenedent of the generator :question: - Shrinking is contained within the generator :heavy_check_mark: --- ```ocaml module Tree : sig type 'a t = { root : 'a; children : 'a t Seq.t } val singleton : 'a -> 'a t val make : 'a -> ('a -> 'a Seq.t) -> 'a t end type 'a gen = unit -> 'a Tree.t let int_gen : int gen = fun () -> let x = Random.int () in let children = fun x -> Seq.ints x |> Seq.map singleton in Tree.make x children ``` --- ### Linear search ```mermaid graph TB A((10000))-->B((0)) A-->C((1)) A-->D((2)) A-->E((3)) A-->F((4)) A-->G((5)) A-->H((6)) A-->I((...)) A-->J((9999)) ``` --- ### Binary search ```mermaid graph TB A((15))-->B((0)) A-->C((1)) A-->D((2)) A-->E((4)) E-->F((3)) A-->G((8)) A-->H((14)) G-->I((5)) G-->J((6)) G-->K((7)) H-->L((9)) H-->M((10)) H-->N((11)) H-->O((13)) O-->P((12)) ``` --- ### Shrinking ```mermaid graph TB A((15))-->B((0)) A-->C((1)) A-->D((2)) A-->E((4)) E-->F((3)) A-->G((8)) A-->H((14)) G-->I((5)) G-->J((6)) G-->K((7)) H-->L((9)) H-->M((10)) H-->N((11)) H-->O((13)) O-->P((12)) style A fill:#DF2E38 style B fill:#5D9C59 style C fill:#5D9C59 style D fill:#5D9C59 style E fill:#5D9C59 style G fill:#5D9C59 style H fill:#DF2E38 style I fill:#5D9C59 style K fill:#5D9C59 style M fill:#5D9C59 style N fill:#5D9C59 style F fill:#DF2E38 style J fill:#DF2E38 style L fill:#DF2E38 style O fill:#DF2E38 style P fill:#DF2E38 ``` - What is the output of the shrinking algorithm? --- Any questions? --- ### Is the gen datatype a monad? (1/2) ```ocaml type 'a gen = unit -> 'a let return x = fun () -> x let bind x f = fun () -> let v = x () in f v () ``` So far, so good :innocent: --- ### Is the gen datatype a monad? (2/2) ```ocaml type 'a gen = unit -> 'a Tree.t let return x = fun () -> {root = x; children = Seq.empty} let bind x f = fun () -> let tree = x () in f (Tree.root tree) () (* <-- wrong *) ``` --- ### A monadic tree ```ocaml module Tree = struct type 'a t = { root : 'a; children : 'a Seq.t } let return x = fun () -> {root = x; children = Seq.empty} let bind x f = fun a f -> let seq_left = Seq.map (fun tree -> bind tree f) a.children in let b = f a.root in let seq_right = b.children in {root = b.root; children = Seq.append seq_left seq_right} ``` --- ### Example  --- ### Example  --- ### Example  --- ### Example  --- ### A monadic generator ```ocaml ```ocaml type 'a gen = unit -> 'a Tree.t let return x = fun () -> Tree.return x let bind x f = fun () -> let tree = x () in Tree.bind tree f ``` --- ### Example ```ocaml let pair : (int * int) gen = fun () -> let* x = int_gen in let* y = int_gen in return (x,y) ``` What should be the expected shrinking tree when the initial value is `(3,3)`? --- ## Expected result ```mermaid graph TB A((3,3))-->B((0,3)) A-->C((1,3)) A-->D((2,3)) A-->E((3,0)) A-->F((3,1)) A-->G((3,2)) B-->H((0,1)) B-->I((0,2)) B-->J((0,3)) C-->K((1,1)) C-->L((1,2)) C-->M((1,3)) D-->N((...)) E-->O((...)) F-->P((...)) G-->Q((...)) ``` --- ### In practice... ```mermaid graph TB A((3,3))-->B((0,1605943)) A-->C((1,23424)) A-->D((2,23326)) A-->H((3,12323)) B-->E((...)) D-->F((...)) C-->G((...)) ``` The value generated for the second component depends on the first value! --- ### Fixed example ```ocaml type 'a gen = Random.state -> 'a Tree.t let return v _rs = Tree.return v let bind gen f = fun rs -> (* Random.split does the magic! *) let (rs_left,rs_right) = Random.split rs in let tree = gen rs_left in Tree.bind tree (fun v -> f v rs_right) ``` It is possible to provide a monadic structure for `'a gen`! --- ### Example with the list generator ```ocaml let list : int gen -> 'a gen -> 'a list gen = fun size_gen gen -> let* size = size_gen in let rec loop n = if n = 0 then return [] else let* v = gen in let* l = loop (n-1) in return (v::l) ``` - On example `[0;1;2;3;4]`, what the tree is supposed to look like? --- ```mermaid graph TB A("[0;1;2;3;4]")-->B("[]") A-->C("[0]") A-->D("[0;1]") A-->E("[0;1;2;3]") D-->F("[0;0]") E-->G("[0;0;2;3]") E-->H("[0;1;0;3]") E-->I("...") G-->J("...") H-->K("...") A-->L("[0;0;2;3;4]") A-->M("...") ``` --- # Question ```ocaml let list : int gen -> 'a gen -> 'a list gen = fun size_gen gen -> let* size = size_gen in let rec loop n = if n = 0 then return [] else let* v = gen in (* 1 *) let* l = loop (n-1) in (* 2 *) return (v::l) ``` What would happen if we switch lines `1` and `2`? --- # Internal shrinking for free - Easy to **write generators** - **Small kernel** (200 lines of code) - **prediction** of shrinking is easier: you only need to know how *bind* works - **Monads** are cool because you get composition for free! --- # Towards a PBT library Some discussions related to the design of the library being implemented --- # How to use the library - Library could be used inside a test framework (oUnit, Tezt, alcotest, ...). - There will be first a Unix runner (a JS-compatible runner should be easy to implement) --- ### Logging - The Unix runner allows to capture stdout/stderr so that only the run with the smallest counter-example are run --- # Multiple shrinkers > One ring to rule them all, one ring to find them, One ring to bring them all, and in the darkness bind them :thinking_face: Why not providing multiple shrinkers? --- ### Multiple shrinkers - The CI does not need to shrink values - Shrinking can be done in parallel - Shrinking should be fast by default --- ### Multiple shrinkers - Shrinking strategies can be implemented as a *tree monad transformer* instantiated by the `'a gen` monad - Enable parallel search *and* debug logging --- ### Extending the generator monad ```ocaml type 'a gen = Random.state -> 'a Tree Seq.t ``` This enables to implement more complex shrinking strategies. For example, a strategy that allows to skip `n` elements. --- ### Standard library - The standard library should contain: - Default generators - Default shrinkers --- ### Open questions Can we implement the monad `'a tree Seq.t` by reusing the monad `'a tree`? Apparently not :thinking_face: ```ocaml let tree_bind : 'a tree -> ('a -> 'a tree) -> 'a tree = ... let bind : 'a tree Seq.t -> ('a -> 'a tree Seq.t) -> 'a tree Seq.t = (* Can we reuse tree bind here? Apparently not. *) ``` --- # Source code of the library :point_right: [WIP version of the library](https://gitlab.com/nomadic-labs/tezt/-/merge_requests/31/diffs#3fbeb7df3a69231b33838fb7c15df7e6d0043c08)