Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
894 lines (777 sloc) 22.7 KB
/**
* Copyright (c) Facebook, Inc. and its affiliates.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*/
module QuickCheck;
/**
* Property testing library borrowing ideas from Haskell's
* [QuickCheck](http://hackage.haskell.org/package/QuickCheck).
*
* QuickCheck allows defining "properties" - conditions that should hold
* for arbitrary values of some type(s) - and verifying that the property
* does in fact hold given pseudo-randomly generated values of that type
* Examples of such properties are "Int addition is commutative" or
* "Vector::sort returns inputs in sorted order".
*
* When a property does not hold, QuickCheck attempts to find a minimal
* failure case (where "minimal" is defined by the type of the input). This
* can help to hone in on the nature of a bug by finding the exact value
* that triggers edge-case behavior.
*
* ## Example Usage:
*
* ```
* // The general form is to combine check() and forAll():
* QuickCheck.check(Foo::generator(), foo ~> {
* isValid(foo) // => Bool
* })
*
* // Test that converting an Int to/from a String equals the original Int:
* QuickCheck.check(Int::generator(), x ~> {
* x.toString().toInt() == x
* })
*
* // Test that Vector sorts ints:
* QuickCheck.check(Vector::generator(Int::generator()), vec ~> {
* sorted = vec.sorted();
* prev = Int::min;
* for (x in sorted) {
* if (x < prev) { break false }
* !prev = x;
* } else true
* })
* ```
*
* ## Built-In Generators
*
* QuickCheck.sk supports generating values of the following types by default:
* - `Bool::generator()`
* - `Char::generator()`
* - `Float::generator()`
* - `Int::generator()`
* - `String::generator()`
* - `Order::generator()`
* - `Vector::generator(<value-generator>)`, ie `Vector::generator(Int::generator())`
* - `Map::generator(<key-generator>, <value-generator>)`
* - `Set::generator(<value-generator>)`
* - `Option::generator(<value-generator>)`
* - Functions of arity 1 (`A ~> B`) with `QuickCheck.Fun1::generator<A, B>(B::generator())`
* Note the two type parameters for the input/output type of the generated function
* and that the generator must produce the output type (B, B::generator).
*
* ## Custom Generators
*
* To create a generator for a custom type, extend `QuickCheck.Generator`:
*
* ```
* // Generator of `Foo`s
* class FooGenerator extends QuickCheck.Generator<Foo> {
* fun generate(rng: mutable Random, sizeBound: Int): Foo {
* // create values from rng. for continuous values like Int/Float,
* // scale them to within [0, sizeBound)
* Foo(...)
* }
* }
* ```
*
* To make your type support shrinking (finding a minimal failure case),
* extend `QuickCheck.Shrinkable`:
*
* ```
* class Foo uses QuickCheck.Shrinkable {
* fun shrink(): mutable Iterator<Foo> {
* yield Foo(...)
* yield ...
* }
* }
* ```
*/
// ----------- PUBLIC API -----------
const defaultSeed: Int = 2;
const defaultAttempts: Int = 100;
const defaultMaxSize: Int = 30;
class Config{
seed: Int = defaultSeed,
attempts: Int = defaultAttempts,
maxSize: Int = defaultMaxSize,
}
// Check that a test property holds. The test function should return true
// if the property holds for a given input, false otherwise.
fun check<A: Shrinkable & Show, T: Testable>(
gen: Generator<A>,
f: A ~> T,
config: Config = Config{},
): TestResult {
run(ForAllProperty(gen, f), config)
}
// Similar to check(), but designed for use in assertion tests where
// exceptions are used to indicate failure. The test function should
// throw if the test property does not hold for a given input. Assert()
// throws an AssertionFailure if the property fails for any input.
fun assert<A: Shrinkable & Show>(
gen: Generator<A>,
f: A ~> void,
config: Config = Config{},
): void {
test = a ~> {
try {
_ = f(a);
Success(void)
} catch {
| exn -> Failure(exn.getMessage())
}
};
assertEqual(run(ForAllProperty(gen, test), config), TestSuccess())
}
// Samples a generator - use this to see what values it will produce
// for a given Config.
fun sample<A>(gen: Generator<A>, config: Config = Config{}): Vector<A> {
rng = Random::mcreate(config.seed);
Vector::fillBy(config.attempts, index -> {
size = index % config.maxSize;
gen.generate(rng, size)
})
}
// Returns an iterator that can be used to sample how a value will shrink.
// Shrinking a value is not guaranteed to terminate so the resulting iterator
// should be limited via take() or similar.
fun sampleShrink<A: Shrinkable & Show>(a: A): mutable Iterator<A> {
buildShrinkTree(a).iterator();
}
// ----------- TRAITS/INTERFACES -----------
// A class that can generate values of type T from a pseudo-random source,
// optionally constraining the value based on a size.
mutable base class Generator<+T> {
fun generate(rng: mutable Random, size: Int): T;
static fun create(f: (mutable Random, Int) ~> T): Generator<T> {
CreateComposedGenerator(f)
}
fun map<T2>(f: T ~> T2): Generator<T2> {
MapComposedGenerator(this, f)
}
}
// A type that has a default generator. There can be multiple generators for
// any given type, for example it may be useful to have a Generator of Ints
// that only yields positive values.
trait Generatable {
static fun generator(): Generator<inst>;
}
// A type that supports shrinking to smaller values
trait Shrinkable {
// `firstShrink` may be set to false when shrinking an already
// shrunk value: the implementation should avoid including values
// that are guaranteed to have been produced in an earlier shrink.
// Examples:
// - Non-zero Ints will always include 0 when firstShrink is true,
// and exclude it thereafter.
// - Non-empty collections will include the empty collection
// when firstShrink is true, and exclude it thereafter.
fun shrink(firstShrink: Bool = true): mutable Iterator<inst>;
}
// A type that can perturb a random value based on its value
trait Perturb {
fun perturb(rng: mutable Random): void;
}
// A property that can be evaluated against random inputs
base class Property uses Testable {
fun generator(): Generator<Tree<TestResult>>;
fun property(): Property {
this
}
}
// A type that supports conversion to a Property
trait Testable {
fun property(): Property;
}
// ----------- INTERNALS -----------
private class ForAllProperty<A: Shrinkable & Show, T: Testable>(
gen: Generator<A>,
f: A ~> T,
) extends Property {
fun generator(): Generator<Tree<TestResult>> {
ForAllGenerator(this.gen, this.f)
}
}
private class ForAllGenerator<A: Shrinkable & Show, T: Testable>(
gen: Generator<A>,
f: A ~> T,
) extends Generator<Tree<TestResult>> {
fun generate(rng: mutable Random, size: Int): Tree<TestResult> {
seed1 = rng.next();
seed2 = rng.next();
arg = this.gen.generate(Random::mcreate(seed1), size);
shrinkTree = buildShrinkTree(arg);
f = this.f;
resultTree = shrinkTree.map(x ~> {
tree = f(x).property().generator().generate(Random::mcreate(seed2), size);
tree.map(result ~> {
result.flatMapFailure(failure ~> {
failure with {
counterExample => Vector[x.toString()].concat(
failure.counterExample,
),
}
})
})
});
resultTree.join()
}
}
// Check that a test property holds.
private fun run<T: Testable>(test: T, config: Config): TestResult {
rng = Random::mcreate(config.seed);
property = test.property();
generator = property.generator();
size = -1;
for (_ in Range(0, config.attempts)) {
!size = (size + 1) % config.maxSize;
tree = generator.generate(rng, size);
visit(tree) match {
| TestSuccess() -> void
| failure @ TestFailure _ -> break failure with {seed => config.seed}
}
} else {
TestSuccess()
}
}
private fun buildShrinkTree<A: Shrinkable & Show>(
a: A,
firstShrink: Bool = true,
): Tree<A> {
Tree(
a,
LazySource(() ~> a.shrink(firstShrink)).map(x ~> buildShrinkTree(x, false)),
)
}
private fun visit(tree: Tree<TestResult>): TestResult {
tree match {
| Tree(success @ TestSuccess _, _) -> success
| Tree(failure @ TestFailure _, descendants) ->
descendants.find(t ~> t.root.isFailure()).map(visit).default(failure)
}
}
// ----------- RESULT -----------
base class TestResult uses Testable, Show, Equality {
children =
| TestSuccess()
| TestFailure(seed: Int, counterExample: Vector<String>)
fun flatMapFailure(f: TestFailure -> TestResult): TestResult
| TestSuccess() -> TestSuccess()
| failure @ TestFailure _ -> f(failure)
fun isFailure(): Bool
| TestSuccess() -> false
| TestFailure _ -> true
fun isSuccess(): Bool
| TestSuccess() -> true
| TestFailure _ -> false
fun fromFailure(): TestFailure
| TestSuccess _ -> invariant_violation("fromFailure() called on TestSuccess")
| failure @ TestFailure _ -> failure
fun property(): Property {
TestResultProperty(this)
}
fun ==(other: TestResult): Bool {
(this, other) match {
| (TestSuccess _, TestSuccess _) -> true
| (
TestFailure(seed1, counterExample1),
TestFailure(seed2, counterExample2),
) ->
seed1 == seed2 && counterExample1 == counterExample2
| _ -> false
}
}
fun toString(): String
| TestSuccess() -> "TestSuccess"
| TestFailure(seed, counterExample) ->
`TestFailure: seed=${seed} counterExample=[${counterExample.join(", ")}]`
}
private class TestResultProperty(result: TestResult) extends Property {
fun generator(): Generator<Tree<TestResult>> {
TestResultGenerator(this.result)
}
}
private class TestResultGenerator(
result: TestResult,
) extends Generator<Tree<TestResult>> {
fun generate(_rng: mutable Random, _size: Int): Tree<TestResult> {
Tree(this.result, Lazy::empty())
}
}
// ----------- TREE -----------
private class Tree<T>(root: T, descendants: Lazy<Tree<T>>) {
fun join<T2>[T: Tree<T2>](): Tree<T2> {
outer = this.descendants;
root = this.root.root;
inner = this.root.descendants;
Tree(root, outer.map(n ~> n.join()).concat(inner))
}
fun map<T2>(f: T ~> T2): Tree<T2> {
Tree(f(this.root), this.descendants.map(node ~> node.map(f)))
}
fun iterator(): mutable Iterator<T> {
yield this.root;
for (descendant in this.descendants.iterator()) {
for (x in descendant.iterator()) {
yield x
}
}
}
}
private base class Lazy<+T>() {
static fun empty(): Lazy<T> {
EmptyLazy()
}
fun iterator(): mutable Iterator<T>;
fun map<T2>(f: T ~> T2): Lazy<T2> {
MapLazy(this, f)
}
fun concat<T2>[T: T2](second: Lazy<T2>): Lazy<T2> {
ConcatLazy(this, second)
}
fun find(p: T ~> Bool): ?T {
this.iterator().find(p)
}
fun each(f: T -> void): void {
this.iterator().each(f)
}
}
private class LazySource<+T>(
source: () ~> mutable Iterator<T>,
) extends Lazy<T> {
fun iterator(): mutable Iterator<T> {
this.source()
}
}
private class EmptyLazy<+T>() extends Lazy<T> {
fun iterator(): mutable Iterator<T> {
yield break;
}
}
private class MapLazy<T, T2>(source: Lazy<T>, f: T ~> T2) extends Lazy<T2> {
fun iterator(): mutable Iterator<T2> {
this.source.iterator().map(this.f)
}
}
private class ConcatLazy<T>(source: Lazy<T>, second: Lazy<T>) extends Lazy<T> {
fun iterator(): mutable Iterator<T> {
this.source.iterator().concat(this.second.iterator())
}
}
// ----------- INT -----------
extension class .Int uses Generatable, Perturb, Shrinkable {
static fun generator(): Generator<Int> {
IntGenerator()
}
fun perturb(rng: mutable Random): void {
rng.perturb(this)
}
fun shrink(firstShrink: Bool = true): mutable Iterator<Int> {
if (this != 0) {
absThis = Math.abs(this);
if (this < 0) {
yield absThis;
};
if (firstShrink) {
yield 0;
};
i = this / 2;
m = this - i;
while (Math.abs(m) < absThis) {
yield m;
!i = i / 2;
!m = this - i;
};
}
}
}
class IntGenerator() extends Generator<Int> {
fun generate(rng: mutable Random, size: Int): Int {
rng.random(-size, size + 1)
}
}
// ----------- BOOL -----------
extension class .Bool uses Generatable, Perturb, Shrinkable, Testable {
static fun generator(): Generator<Bool> {
BoolGenerator()
}
fun perturb(rng: mutable Random): void {
rng.perturb(if (this) 1 else 0)
}
fun shrink(_firstShrink: Bool = true): mutable Iterator<Bool> {
if (this) {
yield false;
}
}
fun property(): Property {
if (this) {
TestResultProperty(TestSuccess())
} else {
TestResultProperty(TestFailure(0, Vector[]))
}
}
}
class BoolGenerator() extends Generator<Bool> {
fun generate(rng: mutable Random, _size: Int): Bool {
rng.randomBool()
}
}
// ----------- Char -----------
extension class .Char uses Generatable, Shrinkable {
static fun generator(): Generator<Char> {
CharGenerator()
}
fun shrink(firstShrink: Bool = true): mutable Iterator<Char> {
// TODO: Better char shrinking
this.code().shrink(firstShrink).filter(Char::isValidCharCodePoint).map(x ~>
x.chr()
)
}
}
class CharGenerator() extends Generator<Char> {
fun generate(rng: mutable Random, size: Int): Char {
// TODO: Generate a wider range of Chars
loop {
code = rng.random(0, size + 1);
if (Char::isValidCharCodePoint(code)) {
return code.chr()
}
}
}
}
// ----------- Float -----------
extension class .Float uses Generatable, Shrinkable {
static fun generator(): Generator<Float> {
FloatGenerator()
}
fun shrink(firstShrink: Bool = true): mutable Iterator<Float> {
if (this < 0.0) {
yield -this
};
truncated = if (this > 0.0) {
this.toInt()
} else {
this.negate().toInt().negate()
};
for (x in truncated.shrink(firstShrink)) {
yield x.toFloat()
}
}
}
class FloatGenerator() extends Generator<Float> {
fun generate(rng: mutable Random, size: Int): Float {
rng.randomFloat() * (size * 2).toFloat() - size.toFloat()
}
}
// ----------- String -----------
extension class .String uses Generatable, Shrinkable {
static fun generator(): Generator<String> {
StringGenerator()
}
fun shrink(firstShrink: Bool = true): mutable Iterator<String> {
// TODO: better String shrinking
chars = this.getIter().collect(Vector);
chars.shrink(firstShrink).map(x ~> String::fromChars(x.toArray()))
}
}
class StringGenerator() extends Generator<String> {
fun generate(rng: mutable Random, sizeBound: Int): String {
// TODO: better String generation
size = rng.random(0, sizeBound + 1);
chars = CharGenerator();
String::fromChars(Array::fillBy(size, _ -> chars.generate(rng, sizeBound)))
}
}
// ----------- Order -----------
extension base class .Order uses Perturb, Generatable, Shrinkable {
static fun generator(): Generator<Order> {
OrderGenerator()
}
fun perturb(rng: mutable Random): void {
rng.perturb(
this match {
| LT() -> 0
| EQ() -> 1
| GT() -> 2
},
)
}
fun shrink(_firstShrink: Bool = true): mutable Iterator<Order>
| LT() -> yield break
| EQ() -> yield LT()
| GT() ->
yield EQ();
yield LT()
}
class OrderGenerator() extends Generator<Order> {
fun generate(rng: mutable Random, _size: Int): Order {
Array[LT(), EQ(), GT()][rng.random(0, 3)]
}
}
// ----------- Option -----------
extension base class .Option uses
Perturb[T: Perturb],
Shrinkable[T: Shrinkable],
{
static fun generator<T2>(generator: Generator<T2>): Generator<?T2> {
OptionGenerator(generator)
}
fun perturb[T: Perturb](rng: mutable Random): void
| None() -> rng.perturb(0)
| Some(x) ->
rng.perturb(1);
x.perturb(rng)
fun shrink[T: Shrinkable](firstShrink: Bool = true): mutable Iterator<?T>
| None() -> yield break
| Some(x) ->
yield None();
for (s in x.shrink(firstShrink)) {
yield Some(s)
}
}
class OptionGenerator<T>(generator: Generator<T>) extends Generator<?T> {
fun generate(rng: mutable Random, size: Int): ?T {
freq = rng.random(0, 4); // weighted random value biasing towards Some
if (freq == 0) {
None()
} else {
Some(this.generator.generate(rng, size))
}
}
}
// ----------- TestResult -----------
extension base class .Result uses
Testable[E: readonly Show],
Perturb[T: Perturb, E: Perturb],
Shrinkable[T: Shrinkable, E: Shrinkable],
{
static fun generator<T2, E2>(
successGenerator: Generator<T2>,
failureGenerator: Generator<E2>,
): Generator<Result<T2, E2>> {
ResultGenerator(successGenerator, failureGenerator)
}
fun perturb[T: Perturb, E: Perturb](rng: mutable Random): void
| .Success(s) ->
rng.perturb(0);
s.perturb(rng)
| .Failure(f) ->
rng.perturb(1);
f.perturb(rng)
fun shrink[T: Shrinkable, E: Shrinkable](
firstShrink: Bool = true,
): mutable Iterator<Result<T, E>>
| .Success(s) ->
s.shrink(firstShrink).map(s2 ~> (.Success(s2) : Result<T, E>))
| .Failure(f) ->
f.shrink(firstShrink).map(f2 ~> (.Failure(f2) : Result<T, E>))
fun property[E: readonly Show](): Property
| .Success _ -> TestResultProperty(TestSuccess())
| .Failure(f) -> TestResultProperty(TestFailure(0, Vector[f.toString()]))
}
class ResultGenerator<T, E>(
successGenerator: Generator<T>,
failureGenerator: Generator<E>,
) extends Generator<Result<T, E>> {
fun generate(rng: mutable Random, size: Int): Result<T, E> {
freq = rng.random(0, 3); // weighted random value biasing towards Success
if (freq == 0) {
.Failure(this.failureGenerator.generate(rng, size))
} else {
.Success(this.successGenerator.generate(rng, size))
}
}
}
// ----------- Vector -----------
extension class .Vector uses Perturb[T: Perturb], Shrinkable[T: Shrinkable] {
static fun generator<U>(generator: Generator<U>): Generator<Vector<U>> {
VectorGenerator(generator)
}
fun perturb[T: Perturb](rng: mutable Random): void {
for (x in this) {
x.perturb(rng)
}
}
fun shrink[T: Shrinkable](
firstShrink: Bool = true,
): mutable Iterator<Vector<T>> {
// TODO: better Vector shrinking
if (!this.isEmpty()) {
for (last in this.last().shrink(firstShrink)) {
yield Vector[last]
};
for (size in this.size().shrink(firstShrink)) {
yield this.slice(0, size);
};
};
}
}
class VectorGenerator<T>(generator: Generator<T>) extends Generator<Vector<T>> {
fun generate(rng: mutable Random, sizeBound: Int): Vector<T> {
size = rng.random(0, sizeBound + 1);
Vector::fillBy(size, _ -> this.generator.generate(rng, sizeBound))
}
}
// ----------- Map -----------
extension class .Map uses
Perturb[K: Perturb, V: Perturb],
Shrinkable[K: Shrinkable, V: Shrinkable],
{
static fun generator<K2: Hashable & Equality, V2>(
keyGenerator: Generator<K2>,
valueGenerator: Generator<V2>,
): Generator<Map<K2, V2>> {
MapGenerator(keyGenerator, valueGenerator)
}
fun perturb[K: Perturb, V: Perturb](rng: mutable Random): void {
for (k => v in this) {
k.perturb(rng);
v.perturb(rng)
}
}
fun shrink[K: Shrinkable, V: Shrinkable](
_firstShrink: Bool = true,
): mutable Iterator<Map<K, V>> {
// TODO: Map shrinking
if (!this.isEmpty()) {
yield Map[]
};
}
}
class MapGenerator<K: Hashable & Equality, V>(
keyGenerator: Generator<K>,
valueGenerator: Generator<V>,
) extends Generator<Map<K, V>> {
fun generate(rng: mutable Random, sizeBound: Int): Map<K, V> {
size = rng.random(0, sizeBound + 1);
map = Map::mcreate(size);
for (_ in Range(0, size)) {
map.set(
this.keyGenerator.generate(rng, sizeBound),
this.valueGenerator.generate(rng, sizeBound),
);
};
map.chill()
}
}
// ----------- Set -----------
extension class .Set uses Perturb[T: Perturb], Shrinkable[T: Shrinkable] {
static fun generator<T2: Hashable & Equality>(
generator: Generator<T2>,
): Generator<Set<T2>> {
SetGenerator(generator)
}
fun perturb[T: Perturb](rng: mutable Random): void {
for (x in this) {
x.perturb(rng);
}
}
fun shrink[T: Shrinkable](
_firstShrink: Bool = true,
): mutable Iterator<Set<T>> {
// TODO: Set shrinking
if (!this.isEmpty()) {
yield Set[]
};
}
}
class SetGenerator<T: Hashable & Equality>(
generator: Generator<T>,
) extends Generator<Set<T>> {
fun generate(rng: mutable Random, sizeBound: Int): Set<T> {
size = rng.random(0, sizeBound + 1);
set = Set::mcreate(size);
for (_ in Range(0, size)) {
set.insert(this.generator.generate(rng, sizeBound));
};
set.chill()
}
}
// ----------- Tuple2 -----------
extension class .Tuple2 uses
Perturb[T0: Perturb, T1: Perturb],
Shrinkable[T0: Shrinkable, T1: Shrinkable],
{
static fun generator(
g0: Generator<T0>,
g1: Generator<T1>,
): Generator<Tuple2<T0, T1>> {
Tuple2Generator(g0, g1)
}
fun perturb[T0: Perturb, T1: Perturb](rng: mutable Random): void {
this.i0.perturb(rng);
this.i1.perturb(rng);
}
fun shrink[T0: Shrinkable, T1: Shrinkable](
firstShrink: Bool = true,
): mutable Iterator<Tuple2<T0, T1>> {
for (i0 in this.i0.shrink(firstShrink)) {
yield (i0, this.i1);
};
for (i1 in this.i1.shrink(firstShrink)) {
yield (this.i0, i1)
}
}
}
class Tuple2Generator<T0, T1>(
g0: Generator<T0>,
g1: Generator<T1>,
) extends Generator<Tuple2<T0, T1>> {
fun generate(rng: mutable Random, sizeBound: Int): Tuple2<T0, T1> {
i0 = this.g0.generate(rng, sizeBound);
i1 = this.g1.generate(rng, sizeBound);
(i0, i1)
}
}
// ----------- Function (arity 1) -----------
class Fun1<I1, O: frozen>(f: I1 ~> O) uses Show, Shrinkable[O: Shrinkable] {
static fun generator<I1: Perturb, O: frozen>(
generator: Generator<O>,
): Generator<Fun1<I1, O>> {
Fun1Generator<I1, O>(generator)
}
fun toString(): String {
"<<function>>"
}
fun shrink[O: Shrinkable](_firstShrink: Bool = true): mutable Iterator<this> {
yield break;
}
}
private class Fun1Generator<I1: Perturb, O: frozen>(
generator: Generator<O>,
) extends Generator<Fun1<I1, O>> {
fun generate(rng: mutable Random, size: Int): Fun1<I1, O> {
seed = {
seed = rng.next();
while (seed == 0) {
!seed = rng.next()
};
seed
};
generator = this.generator;
Fun1(i1 ~> {
rng1 = Random::mcreate(seed);
i1.perturb(rng1);
generator.generate(rng1, size);
})
}
}
// ----------- Generator Composition -----------
class CreateComposedGenerator<T>(
f: (mutable Random, Int) ~> T,
) extends Generator<T> {
fun generate(rng: mutable Random, sizeBound: Int): T {
this.f(rng, sizeBound)
}
}
class MapComposedGenerator<T, T2>(
generator: Generator<T>,
f: T ~> T2,
) extends Generator<T2> {
fun generate(rng: mutable Random, sizeBound: Int): T2 {
this.f(this.generator.generate(rng, sizeBound))
}
}
module end;