Library
Module
Module type
Parameter
Class
Class type
Module defining what a random generator is.
This module is similar to the Random
module exposed by the standard library except it contains also a split
function. This function exists in the Random
module of the standard library since OCaml 5.0. We use this one for compatibility with previous OCaml versions.
Datatype for generators of type 'a
. A generator should be thought as a tree (or for some usage a sequence of tree (see sequence
). The root of the tree is the generated value. Children of the tree are "smaller" values that can be used during the shrinking.
While shrinking, it may be interesting to produce multiple values. This is why there is a sequence
function and this is why a generator is actually a sequence of trees. A typical use case is a shrinker for lists with the Skip
strategy. Skipping an element of the list during the shrinking process is the same as producing two trees: one with the element and one without.
However, when calling run
, the generator should always be a single tree (a sequence of length one). It is only during the shrinking that sequences of more trees may appear. This invariant is not guaranteed by the type system (see run
).
To understand how shrinking works, you should have a look at A primer on shrinking.
val make : 'a -> ('a -> 'a Stdlib.Seq.t) -> 'a t
make root make_children
builds a generator out of a root value root
and a function to make children from their father. This can build an infinite tree if the function f
never returns an empty sequence.
z_range ?root ?shrink min max
returns a generator producing a uniform value between min
(inclusive) and max
(exclusive). It shrinks towards the value origin
using a binary search (see Tree.binary_search
. By default origin
is 0
if 0
is in the interval min;max
. Otherwise origin
is set to min
.
If root
is specified, the value returned is root
with the same shrinking tree as if the random generator had produce this value.
val float_range :
?root:float ->
?exhaustive_search_digits:int ->
?precision_digits:int ->
?origin:float ->
min:float ->
max:float ->
unit ->
float t
float_range ?root ?shrink min max
returns a generator producing a value between min
(inclusive) and max
(exclusive). It shrinks towards the value min
using a binary search (see Tree.binary_search
. The generator is not uniform. In particular when the fractional part of min
and max
are getting closer to 0.5
, the generator may tend to create more values equal to min
or max
. If the fractional part is 0.
, it should be uniform.
If root
is specified, the value returned is root
with the same shrinking tree as if the random generator had produce this value.
run ?on_failure gen state
runs the generator gen
on the state
given in parameter. It is expected that the generator returns only a single tree. This is always true except if the generator used sequence
. See its documentation for more details.
val return : 'a -> 'a t
return v
returns a generator generating the value v
. There is no shrinking defined for this generator.
bind gen f
returns a new generator out of a generator and a function taking a value produce by this generator and return a new generator.
root gen f
is similar to bind, except that the value given to f
is always the root of gen
(if the sequence has more than one element, it is the root of the first tree which is taken).
As a result, this new generator forgets completely the other values of gen
. It acts as if it contains only the root.
val of_seq : 'a Stdlib.Seq.t -> 'a option t
of_seq seq
returns a generator that will produce successively the values of the sequence until the sequence is empty.
module Syntax : sig ... end
val shrink : ('a -> ('ok, 'err) Stdlib.Result.t) -> 'a Tree.t -> 'a
shrink tree f
returns a value a
that has the following specification assuming f
is deterministic and f tree.root
is Error _
:
f a = Error _
path(a,tree.root) = true
v \in path(a, tree.root)
then f v = Error _
v' = left(v)
and v \in path(a, tree.root)
then f v = Ok _
where:
path(a,b)
returns true
if there is a path in the tree from node a
to node b
.left a
is the node b
such that a
and b
have the same parent, and a
is the successor of b
when iterating children.crunch i gen
returns a generator with the same root but a more aggressive shrinking strategy. It crunchs the first i
levels of the tree into a single level. Hence, to be effective i
must be greater or equal to 2
since i=0
is the root and i=1
is the first row that can't be crunched.
module Merge : sig ... end
The bind function needs to be able to merge nodes between two trees. This library allows you to override the default behaviour be defining your own merge function. The function with_merge
aims to be used just before the next bind.
with_merge merge gen
sets a new merging strategy for the generator.
The function sequence
takes advantage of the fact that a generator can be actually a sequence of trees also known as "forest". bind
will always try to make a single tree out of two trees, however some shrinking strategies require to keep the two separetely. This is the case of the Skip
strategy for list
allowing to skip some elements of the list. While for the initial value, we expect a single tree, for example 1;3;5;7
, during the shrinking we may want to explore the tree associated to sublists such as 1;3
or 3;5
. This is cannot be achieved easily with bind
.
In that case, during the shrinking process, we need to generate multiple trees corresponding to different sublists. This is the purpose of the sequence
function.
sequence gen seq
returns a new generator out of a non-empty sequence of generators gen::seq
. This function aims to be used to define better shrinking strategies. This means that we should never have: bind gen (fun x -> ... (sequence gen seq))
such that seq
is not empty when x
is the originate value of the generator gen
. It should only happen when x
is a smaller value generated via the shrinking.