Introduction to Property-based Testing using ScalaCheck

Tired of writing hundreds of unit tests manually? Write properties and let the test cases be generated automatically! We introduce the ScalaCheck library and demonstrate the benefits of property-based testing, an approach that is very different from the traditional unit testing, because we focus on writing general properties instead of specific test cases.

If you want to look at the full code for the post while reading, you can find it at github.

Writing good tests is an important building block for high software quality. On the developer side however, it is also well-known that writing good tests is extremely hard. As an example, even a basic unit test has to consider the intended use, possible edge cases of the test input, as well as the expected behavior if something goes wrong. This in turn leads to a huge number of individual tests, which make it hard to identify the original property.

Wouldn’t it be nice to have test cases automatically generated and the results checked if they match the specification? ScalaCheck does exactly this, given a property describing the expected behavior, it will generate random input data, covering many edge cases, and check the result. This form of testing is called property-based testing, originally invented in Haskell in the form of the QuickCheck library, which was later ported to Scala and many other languages.

In this post, we provide an introduction to ScalaCheck and use it to write and test a simple program that checks whether a given input is a palindrome. The purpose of this post is to get a quick overview of the how and why of ScalaCheck, not (yet) a complete overview of available features.

Before we can use ScalaCheck to test our implementation, we obviously first need an implementation. As our toy example, we use a simple problem: checking whether a string is a palindrome.

For simplicity, we consider only single words (instead of whole sentences or other units) and define a palindrome as:

A given word is a palindrome, iff it reads the same forwards and backwards.

Given this definition, we can translate it into Scala code easily:

def checkReverse(s: String): Boolean = s == s.reverse

This naive implementation is not the most efficient, but it has the advantage of obvious correctness by simplicity. This is a common situation: we have a very simple and naive solution, but we might want to replace it with a better implementation later on, using less memory and/or a faster algorithm. Before we start to develop alternative implementations to check palindromes, let’s have a first look at ScalaCheck.

Testing with ScalaCheck and using property-based testing in general, consists of two important activities:

1. formulating properties that hold for our implementation
2. writing generators, creating random test data for which the property has to hold

ScalaCheck then generates a (configurable) number of test input sets and checks, whether the property holds for all of them. Finding good properties is the point where developer creativity plays a big role, as thinking of tests in form of properties is different from the unit testing mindset. However, in this post we focus on a special case where ScalaCheck can be used without requiring us to find a good set of properties for our implementation: replacing algorithms with alternatives that are better (with regard to an aspect like memory allocation, runtime, etc.).

Writing a generator for your data is made easy, because ScalaCheck ships with a large number of predefined generators for a lot of standard types, as well as a rich library of combinators. Generators are represented as Gen[+T] which is a generator for values of type T. In order to test our implementation of checkReverse we need to generate palindromes, so let’s start with that.

val palindromeGen: Gen[String] = for {
  base <- arbitrary[String]
  middle <- Gen.option(arbitrary[Char])
} yield base + middle.getOrElse("") + base.reverse

We have a palindrome generator, where palindromes are normal Strings . Gen implements map, flatMap and friends, which allows us to use Scala’s for comprehensions as syntactic sugar. A palindrome is built from two other generators: base which is the part that is repeated in reversed form at the end (the very definition of a palindrome) and an optional middle of type Char to allow palindromes with an odd number of characters:

Gen.option takes as an argument a generator and returns another generator that may or may not generate a value. In order to provide default generators for types, ScalaCheck uses the Arbitrary type class, which defines the arbitrary method. Using arbitrary, we can make use of an implicitly defined generator for the given type. If we want to have this for our own types, we can do this by writing instances of the Arbitrary class.

To get an idea of the palindromes generated, we can sample our palindromeGen like this:

scala> palindromeGen.sample
res1: Option[String] = Some(㳺ᢨȕ❓❓ȕᢨ㳺)
scala> palindromeGen.sample
res2: Option[String] =
  Some(⻧᲎ჹ쩄颧㱵댤扛峌甔ᩡ잉ᇐ醢徉⧭༐跍멅跍༐⧭徉醢ᇐ잉ᩡ甔峌扛댤㱵颧쩄ჹ᲎⻧)

Not the palindromes you would have come up with in unit tests, right? This is where property-based testing really shines, because when writing unit tests, we have to make dedicated effort in order to come up with test cases that exercise corner cases and abnormal behavior, while here we can lean back and let ScalaCheck come up with them instead. Of course, we could have written our palindrome generator palindromeGen in a way, such that it does not use unicode chars, for example by using Gen.alphaStr or other predefined generators in the companion object for Gen.

As a first test, let’s check that our naive palindrome checker from above coincides with our palindrome generator. We do this by writing our very first property:

property("checkReverse coincides with generator") =
  forAll(palindromeGen) { palindrome =>
    checkReverse(palindrome)
  }

Our new property takes as an argument a description and consists of a check that forAll palindromes generated from our palindrome generator palindromeGen, checkReverse returns true. If we run the tests in sbt, we get:

> test
[info] + Palindrome.checkReverse: OK, passed 100 tests.

This means that our property held for all of the randomly generated test inputs. Not unexpected, but good to know in any case.

Our checkReverse method does the job and the nice thing is that the implementation is very simple. As hinted earlier, at some point, though, we might want to exchange the implementation for a better version. One problem of the naive reverse approach is that for every string we check, we need twice the memory to perform the actual equality check. With growing adoption of our palindrome-checking-service however, users want to have larger and larger strings checked for palindromicity, reaching millions of chars in length! When we want to check such a large string, it is unthinkable to just allocate twice the memory, certainly we can do better than that!

After a quick round on the white board, we come up with an alternative way to check for palindromicity: we keep track of two indices, starting from the very left and the very right of the palindrome. The idea is to then work our way towards the middle, comparing the characters as we go:

We start with an implementation and on the first try, we come up with this:

def checkIndices(s: String): Boolean = {
  @tailrec
  def loop(i: Int, j: Int): Boolean = (i,j) match {
    case (i,j) if i == j => true
    case (i,j) if s(i) != s(j) => false
    case (i,j) if s(i) == s(j) => loop(i+1,j-1)
  }

  loop(0,s.length-1)
}

To test this, we need a property. As we are pretty sure that checkReverse is a correct implementation, why not use that as reference:

property("checkIndices") = forAll(maybePalindrome) { s =>
  checkReverse(s) == checkIndices(s)
}

We say that for all strings generated by maybePalindrome, our checkIndices method should return the same result as checkReverse. We define maybePalindrome as:

val maybePalindrome: Gen[String] = Gen.oneOf(palindromeGen,arbitrary[String])

Note the use the oneOf method from Gen to create a generator that will sometimes produce palindromes and sometimes arbitrary strings. Now let’s test our new palindrome checker:

> test
[info] ! Palindrome.checkIndices: Exception raised on property evaluation.
[info] > ARG_0: ""
[info] > Exception: java.lang.StringIndexOutOfBoundsException:
  String index out of range: 0

We forgot about the empty string! Okay that’s easy, let’s fix that and just run the tests again:

> test
[info] ! Palindrome.checkIndices2: Exception raised on property evaluation.
[info] > ARG_0: "꫖꫖"
[info] > Exception: java.lang.StringIndexOutOfBoundsException:
  String index out of range: 2

Another error, this time when handling palindromes with an even number of chars. Investigating this, we come to the conclusion, that we forgot to consider what happens when the two indices never meet because they pass each other, due to an even number of chars:

Here in the next step, our current algorithm would continue with i and j in swapped position and then continue both indexes until we run out of chars, leading to the StringIndexOutOfBoundsException from above. To fix this, we add another case to our implementation:

def checkIndices(s: String): Boolean = {
  @tailrec
  def loop(i: Int, j: Int): Boolean = (i,j) match {

    // additional case: check for adjacent indices
    case (i,j) if i+1 == j => s(i) == s(j)

    case (i,j) if i == j => true
    case (i,j) if s(i) != s(j) => false
    case (i,j) if s(i) == s(j) => loop(i+1,j-1)
  }

  // additional check: "" is a palindrome
  s.isEmpty || loop(0,s.length-1)
}

Feeling lucky, we run our tests again:

> test
[info] + Palindrome.checkReverse: OK, passed 100 tests.
[info] + Palindrome.checkIndices: OK, passed 100 tests.
[info] Passed: Total 2, Failed 0, Errors 0, Passed 2

Success! For 100 randomly generated strings, our implementation of checkIndices returned the same result as our reference implementation checkReverse.

Properties do not have to be used exclusively, instead they can be combined with regular unit tests. Sometimes explicit examples in the form of unit tests are still desirable, for documentation purposes. In Scala, most testing frameworks have support for ScalaCheck properties, e.g. ScalaTest and specs2, making it easy to combine unit tests and properties.

This little demo of ScalaCheck only scratches the surface, but gives a brief glimpse of the strength of property-based testing. We wrote only one single property, to check a more complex implementation against a reference. By randomly generating test input we are able to cover a wide range of corner cases, which are easy to miss or cumbersome to enumerate with unit tests. The pattern of using a simple but slow implementation as reference for a better version is only one powerful scenario where property-based testing makes your life as a developer easier.

Exercise for interested readers: Download the code from github. Write another version that checks whether a given string is a palindrome. You can use any algorithm you want, alternatively, try to write a recursive version that proceeds by dropping chars from both ends until the check is done. Write a property that compares your implementation with our reference implementation checkReverse and see if you got it right by running the tests.

You can find more about ScalaCheck on the official website, including a user guide and the API documentation.

The code in this post (github) was tested with Scala 2.11.7 and ScalaCheck 1.12.5.