123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667(** Quickcheck is a library that uses predicate-based tests and pseudo-random inputs to
automate testing.
For examples see {e lib/base_quickcheck/examples}.
*)open!ImportopenBase_quickcheckmoduletypeGenerator=sig(** An ['a t] a generates values of type ['a] with a specific probability distribution.
Generators are constructed as functions that produce a value from a splittable
pseudorandom number generator (see [Splittable_random]), with a [~size] argument
threaded through to bound the size of the result value and the depth of recursion.
There is no prescribed semantics for [size] other than that it must be non-negative.
Non-recursive generators are free to ignore it, and recursive generators need only
make sure it decreases in recursive calls and that recursion bottoms out at 0. *)type+'at='aGenerator.tvalcreate:(size:int->random:Splittable_random.t->'a)->'atvalgenerate:'at->size:int->random:Splittable_random.t->'a(** Generators form a monad. [t1 >>= fun x -> t2] replaces each value [x] in [t1] with
the values in [t2]; each value's probability is the product of its probability in
[t1] and [t2].
This can be used to form distributions of related values. For instance, the
following expression creates a distribution of pairs [x,y] where [x <= y]:
{[
Int.gen
>>= fun x ->
Int.gen_incl x Int.max_value
>>| fun y ->
x, y
]}
*)includeMonad.Swithtype'at:='atincludeApplicative.Swithtype'at:='at(** [size = create (fun ~size _ -> size)] *)valsize:intt(** [with_size t ~size = create (fun ~size:_ random -> generate t ~size random)] *)valwith_size:'at->size:int->'atvalbool:booltvalchar:chartvalchar_digit:chartvalchar_lowercase:chartvalchar_uppercase:chartvalchar_alpha:chartvalchar_alphanum:chartvalchar_print:chartvalchar_whitespace:chartvalsingleton:'a->'atvaldoubleton:'a->'a->'at(** Produce any of the given values, weighted equally.
[of_list [ v1 ; ... ; vN ] = union [ singleton v1 ; ... ; singleton vN ]] *)valof_list:'alist->'at(** Combine arbitrary generators, weighted equally.
[ union [ g1 ; ... ; gN ] = weighted_union [ (1.0, g1) ; ... ; (1.0, gN) ] ] *)valunion:'atlist->'at(** Generator for the values from a potentially infinite sequence. Chooses each value
with probability [p], or continues with probability [1-p]. Must satisfy [0. < p &&
p <= 1.]. *)valof_sequence:p:float->'aSequence.t->'atvaltuple2:'at->'bt->('a*'b)tvaltuple3:'at->'bt->'ct->('a*'b*'c)tvaltuple4:'at->'bt->'ct->'dt->('a*'b*'c*'d)tvaltuple5:'at->'bt->'ct->'dt->'et->('a*'b*'c*'d*'e)tvaltuple6:'at->'bt->'ct->'dt->'et->'ft->('a*'b*'c*'d*'e*'f)tvalvariant2:'at->'bt->[`Aof'a|`Bof'b]tvalvariant3:'at->'bt->'ct->[`Aof'a|`Bof'b|`Cof'c]tvalvariant4:'at->'bt->'ct->'dt->[`Aof'a|`Bof'b|`Cof'c|`Dof'd]tvalvariant5:'at->'bt->'ct->'dt->'et->[`Aof'a|`Bof'b|`Cof'c|`Dof'd|`Eof'e]tvalvariant6:'at->'bt->'ct->'dt->'et->'ft->[`Aof'a|`Bof'b|`Cof'c|`Dof'd|`Eof'e|`Fof'f]t(** [geometric init ~p] produces a geometric distribution (think "radioactive decay")
that produces [init] with probability [p], and otherwise effectively recursively
chooses from [geometric (init+1) ~p]. The implementation can be more efficient than
actual recursion. Must satisfy [0. <= p && p <= 1.]. *)valgeometric:int->p:float->intt(** [small_non_negative_int] produces a non-negative int of a tractable size, e.g.
allocating a value of this size should not run out of memory. *)valsmall_non_negative_int:intt(** [small_positive_int] produces a positive int of a tractable size, e.g. allocating a
value of this size should not run out of memory. *)valsmall_positive_int:intt(** Generators for functions; take observers for inputs and a generator for outputs. *)valfn:'aObserver.t->'bt->('a->'b)tvalfn2:'aObserver.t->'bObserver.t->'ct->('a->'b->'c)tvalfn3:'aObserver.t->'bObserver.t->'cObserver.t->'dt->('a->'b->'c->'d)tvalfn4:'aObserver.t->'bObserver.t->'cObserver.t->'dObserver.t->'et->('a->'b->'c->'d->'e)tvalfn5:'aObserver.t->'bObserver.t->'cObserver.t->'dObserver.t->'eObserver.t->'ft->('a->'b->'c->'d->'e->'f)tvalfn6:'aObserver.t->'bObserver.t->'cObserver.t->'dObserver.t->'eObserver.t->'fObserver.t->'gt->('a->'b->'c->'d->'e->'f->'g)t(** Generator for comparison functions; result is guaranteed to be a partial order. *)valcompare_fn:'aObserver.t->('a->'a->int)t(** Generator for equality functions; result is guaranteed to be an equivalence
relation. *)valequal_fn:'aObserver.t->('a->'a->bool)t(** [filter_map t ~f] produces [y] for every [x] in [t] such that [f x = Some y]. *)valfilter_map:'at->f:('a->'boption)->'bt(** [filter t ~f] produces every [x] in [t] such that [f x = true]. *)valfilter:'at->f:('a->bool)->'at(** Generator for recursive data type with multiple clauses. At size 0, chooses only
among the non-recursive cases; at sizes greater than 0, chooses among non-recursive
and recursive cases, calling the recursive cases with decremented size.
{[
type tree = Leaf | Node of tree * int * tree;;
recursive_union [return Leaf] ~f:(fun self ->
[let%map left = self
and int = Int.gen
and right = self
in Node (left, int, right)])
]} *)valrecursive_union:'atlist->f:('at->'atlist)->'at(** Like [recursive_union], with the addition of non-uniform weights for each clause. *)valweighted_recursive_union:(float*'at)list->f:('at->(float*'at)list)->'at(** Fixed-point generator. Use [size] to bound the size of the value and the depth of
the recursion. There is no prescribed semantics for [size] except that it must be
non-negative. For example, the following produces a naive generator for natural
numbers:
{[
fixed_point (fun self ->
match%bind size with
| 0 -> singleton 0
| n -> with_size self ~size:(n-1) >>| Int.succ)
]}
*)valfixed_point:('at->'at)->'at(** [weighted_union alist] produces a generator that combines the distributions of each
[t] in [alist] with the associated weights, which must be finite positive floating
point values. *)valweighted_union:(float*'at)list->'at(** [of_fun f] produces a generator that lazily applies [f].
It is recommended that [f] not be memoized. Instead, spread out the work of
generating a whole distribution over many [of_fun] calls combined with
[weighted_union]. This allows lazily generated generators to be garbage collected
after each test and the relevant portions cheaply recomputed in subsequent tests,
rather than accumulating without bound over time. *)valof_fun:(unit->'at)->'at(** Generators for lists, choosing each element independently from the given element
generator. [list] and [list_non_empty] distribute [size] among the list length and
the sizes of each element. [list_non_empty] never generates the empty list.
[list_with_length] generates lists of the given length, and distributes [size] among
the sizes of the elements. *)vallist:'at->'alisttvallist_non_empty:'at->'alisttvallist_with_length:int->'at->'alisttendmoduletypeDeriving_hash=sigtypet[@@derivinghash]endmoduletypeObserver=sig(** An ['a Quickcheck.Observer.t] represents a hash function on ['a]. Observers are
used to construct distributions of random functions; see [Quickcheck.Generator.fn].
Like generators, observers have a [~size] argument that is threaded through to bound
the depth of recursion in potentially infinite cases. For finite values, [size] can
be ignored.
For hashable types, one can construct an observer using [of_hash]. For other types,
use the built-in observers and observer combinators below, or use [create] directly.
*)type-'at='aObserver.tvalcreate:('a->size:int->hash:Hash.state->Hash.state)->'atvalobserve:'at->'a->size:int->hash:Hash.state->Hash.state(** [of_hash] creates an observer for any hashable type. *)valof_hash:(moduleDeriving_hashwithtypet='a)->'atvalbool:booltvalchar:chart(** [doubleton f] maps values to two "buckets" (as described in [t] above),
depending on whether they satisfy [f]. *)valdoubleton:('a->bool)->'at(** [enum n ~f] maps values to [n] buckets, where [f] produces the index for a bucket
from [0] to [n-1] for each value. *)valenum:int->f:('a->int)->'at(** [of_list list ~equal] maps values in [list] to separate buckets, and compares
observed values to the elements of [list] using [equal]. *)valof_list:'alist->equal:('a->'a->bool)->'at(** Fixed point observer for recursive types. For example:
{[
let sexp_obs =
fixed_point (fun sexp_t ->
unmap (variant2 string (list sexp_t))
~f:(function
| Sexp.Atom atom -> `A atom
| Sexp.List list -> `B list))
]}
*)valfixed_point:('at->'at)->'atvalvariant2:'at->'bt->[`Aof'a|`Bof'b]tvalvariant3:'at->'bt->'ct->[`Aof'a|`Bof'b|`Cof'c]tvalvariant4:'at->'bt->'ct->'dt->[`Aof'a|`Bof'b|`Cof'c|`Dof'd]tvalvariant5:'at->'bt->'ct->'dt->'et->[`Aof'a|`Bof'b|`Cof'c|`Dof'd|`Eof'e]tvalvariant6:'at->'bt->'ct->'dt->'et->'ft->[`Aof'a|`Bof'b|`Cof'c|`Dof'd|`Eof'e|`Fof'f]t(** [of_predicate t1 t2 ~f] combines [t1] and [t2], where [t1] observes values that
satisfy [f] and [t2] observes values that do not satisfy [f]. *)valof_predicate:'at->'at->f:('a->bool)->'at(** [comparison ~compare ~eq ~lt ~gt] combines observers [lt] and [gt], where [lt]
observes values less than [eq] according to [compare], and [gt] observes values
greater than [eq] according to [compare]. *)valcomparison:compare:('a->'a->int)->eq:'a->lt:'at->gt:'at->'at(** maps all values to a single bucket. *)valsingleton:unit->_t(** [unmap t ~f] applies [f] to values before observing them using [t]. *)valunmap:'at->f:('b->'a)->'btvaltuple2:'at->'bt->('a*'b)tvaltuple3:'at->'bt->'ct->('a*'b*'c)tvaltuple4:'at->'bt->'ct->'dt->('a*'b*'c*'d)tvaltuple5:'at->'bt->'ct->'dt->'et->('a*'b*'c*'d*'e)tvaltuple6:'at->'bt->'ct->'dt->'et->'ft->('a*'b*'c*'d*'e*'f)t(** Observer for function type. [fn gen t] observes a function by generating random
inputs from [gen], applying the function, and observing the output using [t]. *)valfn:'aGenerator.t->'bt->('a->'b)t(** [of_fun f] produces an observer that lazily applies [f].
It is recommended that [f] should not do a lot of expensive work and should not be
memoized. Instead, spread out the work of generating an observer over many [of_fun]
calls combined with, e.g., [variant] or [tuple]. This allows lazily generated
observers to be garbage collected after each test and the relevant portions cheaply
recomputed in subsequent tests, rather than accumulating without bound over time. *)valof_fun:(unit->'at)->'atendmoduletypeShrinker=sig(** A ['a Quickcheck.Shrinker.t] takes a value of type ['a] and produces similar values
that are smaller by some metric.
The defined shrinkers generally try to make a single change for each value based on
the assumption that the first resulting value that preserves the desired property
will be used to create another sequence of shrunk values.
Within [Quickcheck.test] the shrinker is used as described above.
Shrinkers aim to aid understanding of what's causing an error by reducing the input
down to just the elements making it fail. The default shrinkers remove elements of
compound structures, but leave atomic values alone. For example, the default list
shrinker tries removing elements from the list, but the default int shrinker does
nothing. This default strikes a balance between performance and precision.
Individual tests can use different shrinking behavior as necessary.
See lib/base_quickcheck/examples/shrinker_example.ml for some example shrinkers.
*)type'at='aShrinker.tvalshrink:'at->'a->'aSequence.tvalcreate:('a->'aSequence.t)->'atvalempty:unit->'atvalbool:booltvalchar:chartvalmap:'at->f:('a->'b)->f_inverse:('b->'a)->'btvalfilter:'at->f:('a->bool)->'at(** Filters and maps according to [f], and provides input to [t] via [f_inverse]. Only
the [f] direction produces options, intentionally. *)valfilter_map:'at->f:('a->'boption)->f_inverse:('b->'a)->'btvaltuple2:'at->'bt->('a*'b)tvaltuple3:'at->'bt->'ct->('a*'b*'c)tvaltuple4:'at->'bt->'ct->'dt->('a*'b*'c*'d)tvaltuple5:'at->'bt->'ct->'dt->'et->('a*'b*'c*'d*'e)tvaltuple6:'at->'bt->'ct->'dt->'et->'ft->('a*'b*'c*'d*'e*'f)tvalvariant2:'at->'bt->[`Aof'a|`Bof'b]tvalvariant3:'at->'bt->'ct->[`Aof'a|`Bof'b|`Cof'c]tvalvariant4:'at->'bt->'ct->'dt->[`Aof'a|`Bof'b|`Cof'c|`Dof'd]tvalvariant5:'at->'bt->'ct->'dt->'et->[`Aof'a|`Bof'b|`Cof'c|`Dof'd|`Eof'e]tvalvariant6:'at->'bt->'ct->'dt->'et->'ft->[`Aof'a|`Bof'b|`Cof'c|`Dof'd|`Eof'e|`Fof'f]t(** [fixed_point] assists with shrinking structures recursively. Its advantage over
directly using [rec] in the definition of the shrinker is that it causes lazy
evaluation where possible. *)valfixed_point:('at->'at)->'atendmoduletypeS=sigtypetvalquickcheck_generator:tGenerator.tvalquickcheck_observer:tObserver.tvalquickcheck_shrinker:tShrinker.tendmoduletypeS1=sigtype'atvalquickcheck_generator:'aGenerator.t->'atGenerator.tvalquickcheck_observer:'aObserver.t->'atObserver.tvalquickcheck_shrinker:'aShrinker.t->'atShrinker.tendmoduletypeS2=sigtype('a,'b)tvalquickcheck_generator:'aGenerator.t->'bGenerator.t->('a,'b)tGenerator.tvalquickcheck_observer:'aObserver.t->'bObserver.t->('a,'b)tObserver.tvalquickcheck_shrinker:'aShrinker.t->'bShrinker.t->('a,'b)tShrinker.tendmoduletypeS_range=sigincludeS(** [gen_incl lower_bound upper_bound] produces values between [lower_bound] and
[upper_bound], inclusive. It uses an ad hoc distribution that stresses boundary
conditions more often than a uniform distribution, while still able to produce any
value in the range. Raises if [lower_bound > upper_bound]. *)valgen_incl:t->t->tGenerator.t(** [gen_uniform_incl lower_bound upper_bound] produces a generator for values uniformly
distributed between [lower_bound] and [upper_bound], inclusive. Raises if
[lower_bound > upper_bound]. *)valgen_uniform_incl:t->t->tGenerator.tendmoduletypeS_int=sigincludeS_range(** [gen_log_uniform_incl lower_bound upper_bound] produces a generator for values
between [lower_bound] and [upper_bound], inclusive, where the number of bits used to
represent the value is uniformly distributed. Raises if [(lower_bound < 0) ||
(lower_bound > upper_bound)]. *)valgen_log_uniform_incl:t->t->tGenerator.t(** [gen_log_incl lower_bound upper_bound] is like [gen_log_uniform_incl], but weighted
slightly more in favor of generating [lower_bound] and [upper_bound]
specifically. *)valgen_log_incl:t->t->tGenerator.tend(** [seed] specifies how to initialize a pseudo-random number generator. When multiple
tests share a deterministic seed, they each get a separate copy of the random
generator's state; random choices in one test do not affect those in another. The
nondeterministic seed causes a fresh random state to be generated nondeterministically
for each test. *)typeseed=[`Deterministicofstring|`Nondeterministic]typeshrink_attempts=[`Exhaustive|`Limitofint]moduletypeQuickcheck_config=sig(** [default_seed] is used initialize the pseudo-random generator that chooses random
values from generators, in each test that is not provided its own seed. *)valdefault_seed:seed(** [default_sizes] determines the default sequence of sizes used in generating
values. *)valdefault_sizes:intSequence.t(** [default_trial_count] determines the number of trials per test, except in tests
that explicitly override it. *)valdefault_trial_count:int(** [default_can_generate_trial_count] determines the number of trials used in attempts
to generate satisfying values, except in tests that explicitly override it. *)valdefault_can_generate_trial_count:int(** [default_shrink_attempts] determines the number of attempts at shrinking
when running [test] or [iter] with [~shrinker] and without
[~shrink_attempts] *)valdefault_shrink_attempts:shrink_attemptsendmoduletypeQuickcheck_configured=sigincludeQuickcheck_config(** [random_value gen] produces a single value chosen from [gen] using [seed]. *)valrandom_value:?seed:seed->?size:int->'aGenerator.t->'a(** [iter gen ~f] runs [f] on up to [trials] different values generated by [gen]. It
stops successfully after [trials] successful trials or if [gen] runs out of values.
It raises an exception if [f] raises an exception. *)valiter:?seed:seed->?sizes:intSequence.t->?trials:int->'aGenerator.t->f:('a->unit)->unit(** [test gen ~f] is like [iter], with optional concrete [examples] that are tested
before values from [gen], and additional information provided on failure. If [f]
raises an exception and [sexp_of] is provided, the exception is re-raised with a
description of the random input that triggered the failure. If [f] raises an
exception and [shrinker] is provided, it will be used to attempt to shrink the value
that caused the exception with re-raising behaving the same as for unshrunk inputs.
*)valtest:?seed:seed->?sizes:intSequence.t->?trials:int->?shrinker:'aShrinker.t->?shrink_attempts:shrink_attempts->?sexp_of:('a->Base.Sexp.t)->?examples:'alist->'aGenerator.t->f:('a->unit)->unit(** [test_or_error] is like [test], except failure is determined using [Or_error.t]. Any
exceptions raised by [f] are also treated as failures. *)valtest_or_error:?seed:seed->?sizes:intSequence.t->?trials:int->?shrinker:'aShrinker.t->?shrink_attempts:shrink_attempts->?sexp_of:('a->Base.Sexp.t)->?examples:'alist->'aGenerator.t->f:('a->unitOr_error.t)->unitOr_error.t(** [test_can_generate gen ~f] is useful for testing [gen] values, to make sure they can
generate useful examples. It tests [gen] by generating up to [trials] values and
passing them to [f]. Once a value satisfies [f], the iteration stops. If no values
satisfy [f], [test_can_generate] raises an exception. If [sexp_of] is provided, the
exception includes all of the generated values. *)valtest_can_generate:?seed:seed->?sizes:intSequence.t->?trials:int->?sexp_of:('a->Base.Sexp.t)->'aGenerator.t->f:('a->bool)->unit(** [test_distinct_values gen] is useful for testing [gen] values, to make sure they
create sufficient distinct values. It tests [gen] by generating up to [trials]
values and making sure at least [distinct_values] of the resulting values are unique
with respect to [compare]. If too few distinct values are generated,
[test_distinct_values] raises an exception. If [sexp_of] is provided, the exception
includes the values generated. *)valtest_distinct_values:?seed:seed->?sizes:intSequence.t->?sexp_of:('a->Base.Sexp.t)->'aGenerator.t->trials:int->distinct_values:int->compare:('a->'a->int)->unit(** [random_sequence ~seed gen] produces a sequence of values chosen from [gen]. *)valrandom_sequence:?seed:seed->?sizes:intSequence.t->'aGenerator.t->'aSequence.tend(** Includes [Let_syntax] from [Monad.Syntax]. Sets [Open_on_rhs] to be all of
[Generator], except that it does not shadow [Let_syntax] itself. Both [Generator] and
[Open_on_rhs] are meant to be destructively assigned. *)moduletypeSyntax=sigmoduleGenerator:GeneratormoduleOpen_on_rhs:Generatorwithtype'at:='aGenerator.tandmoduleLet_syntax:=Generator.Let_syntaxincludeMonad.Syntaxwithtype'at:='aGenerator.tandmoduleLet_syntax.Let_syntax.Open_on_rhs=Open_on_rhsendmoduletypeQuickcheck=sigtypenonrecseed=seedtypenonrecshrink_attempts=shrink_attemptsmoduleGenerator:GeneratormoduleObserver:ObservermoduleShrinker:ShrinkermoduletypeS=SmoduletypeS1=S1moduletypeS2=S2moduletypeS_int=S_intmoduletypeS_range=S_rangeincludeSyntaxwithmoduleGenerator:=GeneratorandmoduleOpen_on_rhs:=GeneratormoduletypeQuickcheck_config=Quickcheck_configmoduletypeQuickcheck_configured=Quickcheck_configured(** with a default config *)includeQuickcheck_configuredmoduleConfigure(Config:Quickcheck_config):Quickcheck_configuredend