Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

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.

`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.

`range ?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`

.

```
val float_range :
?exhaustive_search_digits:int ->
?precision_digits:int ->
?origin:float ->
min:float ->
max:float ->
unit ->
float t
```

`range ?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.

`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.

`module Syntax : sig ... end`

`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`

- forall v, if
`v \in path(a, tree.root)`

then`f v = Error _`

- if
`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.

On This Page