Towards QA I: Property Based Testing

Overview

This is the first part of a series of posts where we discuss different approaches in the QA process. Each will cover an aspect of the problem; this may be unit testing, regression testing, systems testing, optimisation and so on so fourth. This post will focus on the world of Property Based Testing (PBT).

PBT is a form of unit testing which is focused on defining conditions and behaviours we expect our functions and types to obey. Traditional unit tests may construct a set of inputs and assert results on the output. In contrast, a PBT may construct a myriad of inputs via generators and assert high level properties that should hold for all cases.

For example, a set of traditional unit tests might take a number of lists as input and assert a set of results on the outputs. The key here is that we, as developers, define the input list and output assertions for a specific set of inputs. We must therefore be careful to ensure we don't miss any critical cases for lists (be it empty lists, singleton lists, or lists of length n). In PBT, we specify generators for random sets of input types (in this case Lists), and post-conditions that all these lists must satisfy. Provided the input set size is randomised effectively and uses a large enough sample size, we alleviate ourselves from the burden of missing input cases and can focus on the the properties that are under scrutiny.

In this post we will cover ScalaCheck, which is a Scala library inspired by Haskell's QuickCheck library, which enables PBT.

First steps...

To get started download the appropriate version of the ScalaCheck jar and launch the Scala Interpreter:

scala -cp scalacheck.jar

Now we can get started with a basic example of properties. Suppose we want to verify the following property of Lists:

head ( x::ls ) == x

We could verify this is the case using the forAll (universal quantifier) property as shown below:

import org.scalacheck.Prop.forAll

val propConsList = forAll { (ls: List[Int], x: Int) => 
(x::ls).head == x }

propConsList.check

Two interesting things are happening here. The first is that ScalaCheck is asserting our property holds over a number of arbitrary lists of Int and arbitrary Ints. Behind the scenes, there exist implicit definitions which define Arbitrary instances tasked with forming the input to our property - one for Lists[Int] and one for the set of Integers. You can of course define your own Arbitrary instances or even specific Generators if you are so inclined.

The result should be something like:

propConsList.check
+ OK, passed 100 tests.

It's worth trying to implement some other basic properties on Lists before moving on:

Lists:
1. ls.reverse.reverse == ls
2. (ls1 ::: ls2).size == ls1.size + ls2.size

Strings:
3. (s1 + s2).endsWith(s2)

From the ScalaCheck examples, we see that you can also represent implication:

import org.scalacheck.Prop.{forAll, BooleanOperators}

val propMakeList = forAll { n: Int =>
  (n >= 0 && n < 10000) ==> (List.fill(n)("").length == n)
}

Finally, you can group together logically similar properties using the Properties trait. An example from the ScalaCheck user guide demonstrates this nicely for properties of the String type:

import org.scalacheck._

object StringSpecification extends Properties("String") {
  import Prop.forAll

  property("startsWith") = forAll { (a: String, b: String) =>
    (a+b).startsWith(a)
  }

  property("endsWith") = forAll { (a: String, b: String) =>
    (a+b).endsWith(b)
  }

  property("substring") = forAll { (a: String, b: String) =>
    (a+b).substring(a.length) == b
  }

  property("substring") = forAll { (a: String, b: String, c: String) =>
    (a+b+c).substring(a.length, a.length+b.length) == b
  }
}

Each of these grouped properties can be composed into a single set using the include method:

object MyAppSpecification extends Properties("MyApp") {
  include(StringSpecification)
  include(...)
  include(...)
}

Custom Generators

So far we've seen how to verify universal quantifiers for properties over standard types (Int, String, List[Int] and so on so fourth). Now we will see how to implement our own generators (in the form of the Arbitrary type) so we can use them in our property tests.

Suppose you have a trait such as:

trait myType {

  type T

  type E

  def ord: Ordering[E]



  def empty: T

  def isEmpty(t: T): Boolean

  def insert(x: E, t: T): T

}

We can define a generator for arbitrary instance of myType using for comprehensions, arbitrary primitives (such as on Int) and simple generators such as OneOf and const:

lazy val genMyType: Gen[T] = for {
    v <- arbitrary[Int]
    m <- oneOf(const(empty), genMyType)
  } yield insert(v, m)
implicit lazy val arbMyType: Arbitrary[T] = Arbitrary(genMyType)

Execution Semantics

When the check method is executed, ScalaCheck will run the property tests with a set parameter size for each of the generators and incrementally increase this attribute up to a given limit on each execution. Execution is performed concurrently on a configurable number of workers.

One final point worth noting is how to minimise the number of test cases needed to prove/disprove a property. The ScalaCheck documentation uses the following example to demonstrate the various semantics of the default shrink methods:

import org.scalacheck.Arbitrary.arbitrary
import org.scalacheck.Prop.{forAll, forAllNoShrink}

val p1 = forAllNoShrink(arbitrary[List[Int]])(l => l == l.distinct)

val p2 = forAll(arbitrary[List[Int]])(l => l == l.distinct)

val p3 = forAll( (l: List[Int]) => l == l.distinct )

These all correctly falsify the property as one would expect - but the number of tests required to do so varies greatly. This is because p2 & p3 are able to shrink the lists under test down to a minimal failing test to disprove this property, whereas p1 generates larger lists and thus requires more checks to complete. The snippet below, which is taken from the ScalaCheck documentation, demonstrates this. You can see that p2 and p3 reduce the list to just two duplicate elements as this is the minimum list size required to disprove this property:

scala> p1.check
! Falsified after 11 passed tests:
> ARG_0 = "List(8, 0, -1, -3, -8, 8, 2, -10, 9, 1, -8)"

scala> p2.check
! Falsified after 4 passed tests:
> ARG_0 = "List(-1, -1)" (2 shrinks)

scala> p3.check
! Falsified after 7 passed tests:
> ARG_0 = "List(-5, -5)" (3 shrinks)

It's worth mentioning that you can also define your own shrinking methods. Simply define an implicit method that returns Shrink[T] instances. A final example of this is given in the ScalaCheck documentation for 2-tuples:

/** Shrink instance of 2-tuple */
implicit def shrinkTuple2[T1,T2](implicit s1: Shrink[T1], s2: Shrink[T2]
): Shrink[(T1,T2)] = Shrink { case (t1,t2) =>
  (for(x1 <- shrink(t1)) yield (x1, t2)) append
  (for(x2 <- shrink(t2)) yield (t1, x2))
}

Conclusion

To recap, we have touched on PBT and how it relates to traditional unit testing techniques, how to write basic properties over types, how to group/compose properties, implementing custom Arbitrary instances, and the execution semantics which govern ScalaCheck's property based testing system.

I hope you found this post to be informative... If you'd like to hear more on data analytics and programming please stay tuned.