In the last article we learned how to generate objects with Java 8 in a functional way and implemented a small API based around the Gen monad. Although already powerful one its own, generators really shine when using them in combination with property-based testing. This article builds upon the implementation of Gen and discusses a simple API that enables us to write property-based tests.
A property-based test verifies a statement about the output of your code based on some given input. The same statement - or property - is verified for many different possible inputs in order to find an input that falsifies that property. Thus, such tests rely heavily upon generators to randomly construct instances from a given domain. If the property cannot be falsified, the test passes. In fact, if the generator is total with regard to the instances it generates, we actually have a proof that the property holds under the given circumstances.
Drafting the API
As already hinted, a property closes over a given Gen<T> and a given Predicate<T>. We can express this with the following signature of a type constructor for instances of Property<T>.
public static <T> Property<T> forAll(final Gen<T> gen, final Predicate<T> predicate) {
...
}
While the Gen<T> knows how to generate instances of type T, the Predicate<T> encodes the actual logic on which instances of type T are tested against. We can use both types like this:
return listOfN(gen, n)
.sample()
.stream()
.allMatch(predicate::test);
This code uses the listOfN generator which uses the passed generator to create a list consisting of n instances of type T. These instances are then fed into the given predicate. Using the allMatch method on the stream we are able to enforce that all generated instances must satisfy the predicate.
However, simply returning a boolean value is not enough information in case the test fails on one of the generated instances. We need to capture those instances that falsify the property to be able to properly address the issues within our code. The underneath listing shows class Result<T> which collects information about the test execution.
public class Result<T> {
private final int numberOfPassedTests;
private final boolean passed;
private final T failedOn;
private Result(final int numberOfPassedTests, final boolean passed, final T failedOn) {
this.numberOfPassedTests = numberOfPassedTests;
this.failedOn = failedOn;
this.passed = passed;
}
public void assertPassed() {
if (!this.passed) {
throw new AssertionError("! Falsified after " + this.numberOfPassedTests + " tests on sample " + failedOn);
}
}
public int numberOfPassedTests() {
return this.numberOfPassedTests;
}
public boolean passed() {
return this.passed;
}
public Optional<T> failedOn() {
return Optional.ofNullable(this.failedOn);
}
public static <T> Result<T> passed(final int numbersOfPassedTests, final T failedOn) {
return new Result<>(numbersOfPassedTests, true, null);
}
public static <T> Result<T> falsified(final int numberOfPassedTests, final T failedOn) {
return new Result<>(numberOfPassedTests, false, failedOn);
}
}
Using Result<T>, we can rewrite the test execution:
final Deque<T> probedSamples = new LinkedList<>();
final boolean successful = listOfN(gen, n)
.sample()
.stream()
.peek(sample -> probedSamples.addLast(sample))
.allMatch(predicate::test);
if (successful) {
return passed(probedSamples.size(), null);
} else {
return falsified(probedSamples.size()-1, probedSamples.getLast());
}
There is still one problem, though. So far, it is unclear where the number of generated instances n comes from. Parameterizing the test execution with a proper value for n should be done when actually executing the check. To achieve this, we wrap the test logic using a Function<Integer, Result<T>>, which is passed to the constructor of Property<T>. The final code for the forAll looks like this:
public static <T> Property<T> forAll(final Gen<T> gen, final Predicate<T> predicate) {
final Function<Integer, Result<T>> f = n -> {
final Deque<T> probedSamples = new LinkedList<>();
final boolean successful = listOfN(gen, n)
.sample()
.stream()
.peek(sample -> probedSamples.addLast(sample))
.allMatch(predicate::test);
if (successful) {
return passed(probedSamples.size(), null);
} else {
return falsified(probedSamples.size()-1, probedSamples.getLast());
}
};
return new Property<>(f);
}
The implementation of Property<T> is straightforward, as it only provides check methods that execute the test and relay its result to the caller.
public class Property<T> {
private static final int DEFAULT_NUMBER_OF_INSTANCES = 100;
private final Function<Integer, Result<T>> runner;
private Property(Function<Integer, Result<T>> runner) {
this.runner = runner;
}
public Result<T> check() {
return check(DEFAULT_NUMBER_OF_INSTANCES);
}
public Result<T> check(final int numberOfInstances) {
final Result<T> result = runner.apply(numberOfInstances);
if (result.passed()) {
System.out.println("+ OK, passed " + numberOfInstances + " tests.");
} else {
System.out.println("! Falsified after " + result.numberOfPassedTests() + " tests on sample " + result.failedOn().get()); // safe get
}
return result;
}
}
Example: Verifying Fizzbuzz using Property-Based Tests
Fizzbuzz is still a popular problem given to candidates on a job interview. It is also a good showcase, since it falls into the category of problems that are best verified using property-based tests instead of instance-driven unit tests.
The specification of Fizzbuzz goes like this:
- All multiples of three that are not multiples of five must be mapped to Fizz.
- All multiples of five that are not multiples of three must be mapped to Buzz.
- All multiples of fifteen must be mapped to FizzBuzz.
- All numbers that are neither multiples of three nor multiples of five must be mapped to their identity.
An implementation of this specification might look like this:
public class Fizzbuzz {
public String fizzbuzz(int upToInclusive) {
return IntStream
.range(0, upToInclusive+1)
.boxed()
.map(n -> map(n))
.reduce("", (a, b) -> a + " " + b);
}
public String map(int n) {
if (n % 15 == 0) {
return "FizzBuzz";
} else if (n % 3 == 0) {
return "Fizz";
} else if (n % 5 == 0) {
return "Buzz";
} else {
return String.valueOf(n);
}
}
}
Please note that the interesting thing is not the fizzbuzz method, but map, since it implements the logic that must satisfy the specification. Thus, our tests will focus on testing map, not on fizzbuzz.
Expressing the first property as a JUnit test is simple:
@Test
public void mapShouldYieldFizzForMultiplesOfThreeButNotMultiplesOfFive() {
Gen<Integer> whollyDivisibleByThreeGen = choose(start, end)
.map(n -> 3 * n)
.suchThat(n -> n % 5 != 0);
forAll(whollyDivisibleByThreeGen, n -> fizzbuzz.map(n).equals("Fizz")).check().assertPassed();
}
assertPassed will raise an AssertionError if the property has been falsified, and thus fail the unit test. The console output for this test is either + OK, passed 100 tests. in the success case or ! Falsified after <number> tests on sample <object>. in case the property has been falsified.
Example: Verifying Monoid Laws using Property-Based Tests
A monoid is 3-tuple of the form (A, op, zero), where A denotes the type it operates on, op denotes a combinator operation for two instances of A and zero is the neutral element.
For a given monoid, the following properties must hold:
opis associative. Given a, b, and c,op(a, op(b, c)) = op(op(a, b), c)must hold.zerois the neutral element. Given a,op(a, zero) = amust hold.
The structure of the monoid can be easily expressed using a Java interface:
public interface Monoid<A> {
A op(A a1, A a2);
A zero();
}
A possible implementation of Monoid<A> might be a monoid that adds integers:
public class IntAdditionMonoid implements Monoid<Integer> {
@Override
public Integer op(final Integer a1, final Integer a2) {
return a1 + a2;
}
@Override
public Integer zero() {
return 0;
}
}
Testing this monoid implementation - and in fact all, all possible monoid implementations - can be achieved by expressing the aforementioned properties as part of a unit test. Have a look at this test class.
public class MonoidTest {
@Test
public void intAdditionMonoidRespectsMonoidLaws() {
forAll(choose(-127, 127), monoidRespectsLeftIdentity(new IntAdditionMonoid()))
.check()
.assertPassed();
forAll(choose(-127, 127), monoidRespectsRightIdentity(new IntAdditionMonoid()))
.check()
.assertPassed();
forAll(choose(-127, 127), choose(-127, 127), choose(-127, 127), monoidIsAssociative(new IntAdditionMonoid()))
.check()
.assertPassed();
}
private <T> Predicate<T> monoidRespectsLeftIdentity(final Monoid<T> monoid) {
return t -> monoid.op(monoid.zero(), t).equals(t);
}
private <T> Predicate<T> monoidRespectsRightIdentity(final Monoid<T> monoid) {
return t -> monoid.op(t, monoid.zero()).equals(t);
}
private <T> Predicate3<T, T, T> monoidIsAssociative(final Monoid<T> monoid) {
return (a, b, c) -> {
T sampleLeft = monoid.op(monoid.op(a, b), c);
T sampleRight = monoid.op(a, monoid.op(b, c));
return sampleLeft.equals(sampleRight);
};
}
}
Conclusion
Building up on the functional generators presented in the last article we came up with an easy-to-understand design for a powerful testing strategy called property-based testing. However, the Property<T> abstraction presented here is rather simple, as it does not leverage advanced techniques like shrinking. The shrinking technique tries to narrow down the problem space on instances that falsify the property, which is especially handy if the domain of generated values is large.
If you are interested in learning more on property-based testing (and I encourage you to do so) then you should check out either ScalaCheck for Scala or junit-quickcheck for Java.
The code presented in this article is available on GitHub. It includes an extended version of the design presented in this article as well as a set of generators that can be used to build up your own property-based tests.
