Chapter 6
Generators in Detail
You know how to design and write properties that check the code under test for all kinds of conditions, for each set of generated input. The last piece is controlling the generation of that input. From defining valid values to constructing your own custom types, you'll have control of your data sets through ScalaCheck generators.
This chapter consists of two parts. The first part presents ScalaCheck's various generator combinators in a systematic way, and the second part describes how you can implement your own shrinking algorithms that can be used by ScalaCheck to narrow down failed properties to the simplest failing test case.
6.1 Generator combinators
Chapter 3 described how you can use generator combinators to create custom generators, that produce specific values needed by your properties. The following example from that chapter demonstrates how a generator that produces pairs of integers can be defined:
import org.scalacheck.Gen.choose
val myGen = for { n <- choose(1, 50) m <- choose(n, 2*n) } yield (n, m)
Gen.choose is an example of a combinator that can be used as one piece of a complex generator. Scala's for-syntax makes it intuitive to combine the various generator pieces, which was also demonstrated in Chapter 3. This chapter presents most of the available generator combinators in ScalaCheck. The combinators are grouped into subsections to make it easier to navigate through the text, and small usage examples are given for most of the methods. For even more details on the generator API you should check ScalaCheck's online documentation.
Number generators
Gen.choose is one of the most fundamental generators in ScalaCheck, and the one on which many other generators are based. You use Gen.choose to create a generator that returns a random number in a specified inclusive interval. Its usage is simple:
import org.scalacheck.Gen.choose import org.scalacheck.Prop.forAll
val g = choose(-2, 5)
val h = choose(4.1, 4.2)
val p = forAll(h) { n => n >= 4.1 && n <= 4.2 }
scala> g.sample res0: Option[Int] = Some(5)
scala> h.sample res1: Option[Double] = Some(4.189116648661569)
scala> p.check + OK, passed 100 tests.
Gen.posNum and Gen.negNum are number generators that produce arbitrary positive or negative numbers:
import org.scalacheck.Gen.negNum import org.scalacheck.Prop.forAll
val propAbs = forAll(negNum[Int]) { n => math.abs(n) == -n }
Character generators
There are several different character generators in ScalaCheck. You can use these as building blocks for various string generators:
import org.scalacheck.Gen
val genString = for { c1 <- Gen.numChar c2 <- Gen.alphaUpperChar c3 <- Gen.alphaLowerChar c4 <- Gen.alphaChar c5 <- Gen.alphaNumChar } yield List(c1,c2,c3,c4,c5).mkString
scala> genString.sample res0: Option[java.lang.String] = Some(2MwMh)
scala> genString.sample res1: Option[java.lang.String] = Some(3Fik3)
String generators
You can generate commonly used strings easily in ScalaCheck. For example, Gen.alphaStr generates strings of only alpha characters; Gen.numStr produces numeric strings; and Gen.identifier gives you a non-empty string that always starts with a lowercase alpha character followed by alphanumeric characters:
import org.scalacheck.Gen
val stringsGen = for { alpha <- Gen.alphaStr num <- Gen.numStr id <- Gen.identifier } yield (alpha.take(4), num.take(4), id.take(4))
scala> println(stringsGen.sample)
Some((vHoc,1991,xM1j))
Constant generators
Gen.const takes any value and wraps it inside a generator. Anytime that generator is evaluated it returns this value. This can be useful when you need a generator instance but only want it to return a specific value. This method is implicit, so in most cases you don't need to use it explicitly. Instead, you can use an ordinary value in places where a generator is expected.
Gen.fail returns a generator that never returns a value when evaluated. Instead, it returns None. ScalaCheck uses this generator combinator in several places internally. You will probably not use it, but it can come in handy when implementing complex generators. It can for example act as a way to force ScalaCheck to rerun a generator if some condition is not fulfilled.
scala> org.scalacheck.Gen.fail.sample
res0: Option[Nothing] = None
Higher-order generators
Generator combinators that take one or more generators as arguments to produce a new generator might be called higher-order, which is analogous with higher-order functions (functions that take other functions as parameters). In ScalaCheck, there are several useful higher-order generator combinators.
Gen.sequence takes a list of generators and returns a generator that creates lists of values when evaluated. If any of the provided generators fail, the whole sequence generator will fail.
import org.scalacheck.Gen.{sequence, choose, const}
val numbers = sequence(List(choose(1,10), const(20), const(30)))
scala> numbers.sample res0: Option[java.util.ArrayList[Int]] = Some([9, 20, 30])
Gen.frequency takes a list of pairs of integers and generators. It then returns a new generator, which uses the provided generators to generate values with the integers as probability weights. For instance, we can get a weighted distribution of integers:
import org.scalacheck.Arbitrary.arbitrary import org.scalacheck.Gen.{choose, frequency}
val evenNumberGen = for { n <- choose(2,100000) } yield 2*n
val oddNumberGen = for { n <- choose(0,100000) } yield 2*n + 1
val numberGen = frequency( (1, oddNumberGen), (2, evenNumberGen), (4, 0) )
The definition of numberGen says that it should use oddNumberGen with weight 1, evenNumberGen with weight 2, and a constant generator that generates zeros with weight 4. Remember, since Gen.const is implicit, we can give the value 0 directly to the frequency method as above. Now, the numberGen generator should generate an even number twice as often as it generates an odd one, and in turn a zero twice as often as an even number. How can we verify it will do this? We can check it with a simple property using the Prop.collect method for collecting the data distribution:
import org.scalacheck.Prop.{forAll, collect}
val propNumberGen = forAll(numberGen) { n => val l = { if (n == 0) "zero" else if (n % 2 == 0) "even" else "odd" } collect(l)(true) }
scala> propNumberGen.check + OK, passed 100 tests. > Collected test data: 61% zero 26% even 13% odd
Since the data set is quite small, we can't expect the figures to be exact, but the above numbers seem to be acceptable. If we increase the number of tests we can see that the Gen.frequency combinator works exactly as expected:
scala> propNumberGen.check(10000) + OK, passed 10000 tests. > Collected test data: 57% zero 29% even 14% odd
scala> propNumberGen.check(100000) + OK, passed 100000 tests. > Collected test data: 57% zero 29% even 14% odd
Gen.oneOf takes two or more generators and returns a new generator that randomly picks one of the given generators to use when it is evaluated. You can also give Gen.oneOf plain values. Here are some examples:
import org.scalacheck.Gen.{oneOf, choose}
val genNotZero = oneOf(choose(-10,-1), choose(1,10))
val genVowel = oneOf('a', 'e', 'i', 'o', 'u', 'y')
You can supply the Gen.oneOf with a list of values, if you can't enumerate all values directly:
def genUser(db: DB): Gen[User] = { val users: List[User] = db.getUsers Gen.oneOf(users) }
List generators
Gen.listOf is a generator combinator that takes another generator as its parameter. When evaluated, listOf will generate lists of random lengths, using the given generator to produce the list elements. There are also two other variants of the listOf generator. listOfN takes both a generator and a positive integer as parameters and generates lists of the given length. nonEmptyListOf works like listOf, but will never generate empty lists.
Here are examples of how you can use the generators, as well as properties that specify their behavior:
import org.scalacheck.Gen.{ choose, listOf, nonEmptyListOf, listOfN, oneOf } import org.scalacheck.Arbitrary.arbitrary import org.scalacheck.Prop.forAll
val genIntList = listOf(choose(0,10))
val genNonEmptyList = nonEmptyListOf(oneOf("foo", "bar"))
val genEightBytes = listOfN(8, arbitrary[Byte])
val propIntsWithinBounds = forAll(genIntList) { xs => xs.forall { n:Int => n >= 0 && n <= 10 } }
val propCorrectStrings = forAll(genNonEmptyList) { xs => (xs.size > 0) && xs.forall { s:String => s == "foo" || s == "bar" } }
val propListLength = forAll(genEightBytes) { xs => xs.size == 8 }
Gen.containerOf is a general combinator that can produce instances of virtually any type of collection. listOf is really only a special case of containerOf. Therefore, you could have defined the three previous generators like this:
import org.scalacheck.Gen.{ choose, containerOf, nonEmptyContainerOf, containerOfN, oneOf } import org.scalacheck.Arbitrary.arbitrary import org.scalacheck.Prop.forAll
val genIntList = containerOf[List,Int](choose(0,10))
val genNonEmptyList = nonEmptyContainerOf[List,String](oneOf("foo", "bar"))
val genEightBytes = containerOfN[List,Byte](8, arbitrary[Byte])
As you can see, the containerOf generators are abstracted over a container type and an element type. ScalaCheck will figure out by itself how to build the desired collection instances. To be able to do this, an implicit instance of org.scalacheck.util.Buildable for the given collection type must exist. Such instances are defined in ScalaCheck for all the common collection types like lists, sets, and arrays. It is easy to implement it for your own custom collection types and in that way gain both the containerOf generators and also Arbitrary instances for free.
Generator filters
One way of creating a new generator is to attach a filter to an existing one, by using the Gen.suchThat method. The new generator will simply discard all values that don't pass the filter. Look at the following example:
import org.scalacheck.Arbitrary.arbitrary
val oddInt = arbitrary[Int] suchThat (_ % 2 != 0)
If we run this generator now, we can see that it sometimes return None:
scala> oddInt.sample res0: Option[Int] = Some(2068378103)
scala> oddInt.sample res1: Option[Int] = None
scala> oddInt.sample res2: Option[Int] = Some(-1)
In the second invocation of Gen.sample above, the Gen.choose combinator returned an even integer that was filtered out and replaced with None. If you use this generator in a property, each filtered generator value results in a discarded property evaluation. That is exactly the same situation you get when you have a property precondition that is not fulfilled. ScalaCheck treats generator filters and property preconditions in much the same way. That means you can run in to the same problems: if you add a filter that is too narrow, too many values will be discarded and ScalaCheck will give up on checking the property. This is demonstrated by the following two properties, which are equivalent from ScalaCheck's perspective:
import org.scalacheck.Prop.{forAll,BooleanOperators} import org.scalacheck.Gen.choose
def isPrime(n: Int): Boolean = n > 0 && (2 to n).forall(n % _ != 0)
val p1 = forAll(choose(1,100)) { n => isPrime(n) ==> !isPrime(2*n) }
val p2 = forAll(choose(1,100) suchThat isPrime) { n => !isPrime(2*n) }
If we try to check these properties, we end up with a lot of discarded tests since the probability of generating prime numbers at random is very low:
scala> p1.check ! Gave up after only 1 passed tests. 100 tests were discarded.
scala> p2.check ! Gave up after only 0 passed tests. 101 tests were discarded.
Chapter 4 discussed how you can get around situations like this. In this case you would have to design a generator that generates prime numbers in a more clever way than just filtering out non-primes. The simplest way would probably be to let your generator pre-calculate a sizeable number of primes, and then just use Gen.oneOf to select a prime from the list.
There are situations where a generator filter is perfectly acceptable. If you are confident the filter will not exlude too many cases, then use it. The oddInt generator showed earlier is usable since only half of the generated values will be filtered out:
scala> (forAll(oddInt)(_ % 2 != 0)).check + OK, passed 100 tests.
However, if you try to use the oddInt generator as part of another generator you might run into trouble. For example, try defining a generator that produces lists of odd integers:
import org.scalacheck.Gen.listOf
val listOfOddInt = listOf(oddInt)
val p = forAll(listOfOddInt)(_.forall(_ % 2 != 0))
scala> p.check ! Gave up after only 8 passed tests. 93 tests were discarded.
The problem is that the listOf generator fails if any item fails to be generated. It is very unlikely that no even number appears in a random sequence of integers, so listOfOddInt fails almost always, resulting in too many discarded tests. We can get around this by replacing Gen.suchThat with Gen.retryUntil. retryUntil takes a filtering function just as suchThat, but instead of failing the generation when the filter is false, it retries until the generated value passes the filter. This is a bit risky, since you might end up in an infinite loop if the filter is too narrow. However, in the case of oddInt we know that exactly half of the generated numbers will be filtered out, so we can safely use retryUntil instead of suchThat:
import org.scalacheck.Arbitrary.arbitrary import org.scalacheck.Gen.listOf import org.scalacheck.Prop.forAll
val oddInt = arbitrary[Int] retryUntil (_ % 2 != 0)
val listOfOddInt = listOf(oddInt)
val p = forAll(listOfOddInt)(_.forall(_ % 2 != 0))
scala> p.check
+ OK, passed 100 tests.
Generator filters and property preconditions
I discussed property preconditions in Chapter 4, and demonstrated how you could use custom generators to generate only inputs that fulfill a method's preconditions. Sometimes, however, ScalaCheck's simplification feature can interfere with that approach.
As soon as ScalaCheck finds a test case that makes a property false, it will take that test case and try to simplify, or shrink, it. If ScalaCheck can find a smaller value that still makes the property false, that value will be presented in the test report. When performing this simplification routine, ScalaCheck tries to be as clever as possible and not simplify values beyond what the generator originally was able to generate. For example, look at the two properties below:
import org.scalacheck.Gen.{choose, oneOf} import org.scalacheck.Prop.forAll
val p1 = forAll(choose(0,20)) { n => n > 10 }
val p2 = forAll(oneOf(8,9,10,11)) { n => n > 10 }
The properties are intentionally incorrect in order to trigger ScalaCheck's simplification mechanism:
scala> p1.check ! Falsified after 1 passed tests. > ARG_0: 0 > ARG_0_ORIGINAL: 8
scala> p2.check ! Falsified after 0 passed tests. > ARG_0: 8 > ARG_0_ORIGINAL: 9
As you can see, the test case in the first property has been simplified to 0 and in the second property to 8. This is because ScalaCheck keeps track of which generator produced the test case in the first place. And since oneOf(8,9,10,11) can never generate a number smaller than 8, the simplification stops there.
However, sometimes ScalaCheck can't know the boundaries of the generator. For example, if you map a generator with an arbitrary function, ScalaCheck will lose track:
import org.scalacheck.Gen.oneOf import org.scalacheck.Prop.forAll
val p3 = forAll(oneOf(8,9,10,11) map (_ - 1)) { n => n > 10 }
Now, the generated value is simplified to 0, even though the generator couldn't have produced that value initially:
scala> p3.check Falsified after 0 passed tests. > ARG_0: 0 > ARG_0_ORIGINAL: 9
This can cause trouble if you're testing a method with a precondition that doesn't allow the simplified value. The solution is to add the precondition to the property, which will cause the simplification algorithm to skip the invalid inputs. You can also achieve the same thing by adding the condition to the generator using the suchThat method.
Gen.someOf and Gen.pick
These generators produce lists of elements from a predefined set. Gen.pick is more generic than Gen.someOf as it allows you to specify how many elements the resulting list should contain. Otherwise, the two combinators work in the same way:
import org.scalacheck.Gen.{someOf, pick}
val numbers = someOf(List(1,2,3,4))
val twoStrings = pick(2, List("red", "blue", "green", "pink"))
val numberLists = someOf(numbers, numbers, numbers)
As you can see, you can provide the combinators with either a list of elements or with several generator instances. Try out the generators:
scala> numbers.sample res0: Option[Seq[Int]] = Some(ListBuffer(1, 2, 4))
scala> twoStrings.sample res1: Option[Seq[java.lang.String]] = Some(ListBuffer(red, pink))
scala> numberLists.sample res2: Option[Seq[Seq[Int]]] = Some(List( ListBuffer(1, 2, 3, 4), ListBuffer(1, 2, 3, 4), ListBuffer()))
Gen.sized and Gen.resize When ScalaCheck produces data with a generator, it tells the generator what data size it wants. This lets you test a property with increasingly larger data sets. A generator may interpret the data size parameter freely, or even ignore it if it doesn't make sense to use it. Most standard arbitrary generators implement the size parameter in a straightforward way. The list generators, for example, inspect the size parameter to decide how long the generated lists should be.
When you implement your own generator, you can use the size variable by utilizing the Gen.sized or Gen.resize methods. The Gen.size method takes an anonymous function as its only parameter, and this function in turn takes an integer value as its parameter. That integer parameter represents the size that ScalaCheck specifies when evaluating your generator. Here is an example implementation of a list generator, which resembles ScalaCheck's own list generator:
import org.scalacheck.Gen import org.scalacheck.Gen.{sized, listOfN}
def genList[T](genElem: Gen[T]): Gen[List[T]] = { sized { sz: Int => for { listSize <- Gen.choose(0, sz) list <- Gen.listOfN(listSize, genElem) } yield list } }
The Gen.resize method creates a resized version of an existing generator. This can be useful when you create new generators by composing existing ones and want to tweak the data size without re-implementing the underlying generators. The next section describes how recursive generators are implemented, and in such cases Gen.resize comes in very handy.
Recursive generators
When defining generators for non-trivial data structures, it is sometimes convenient or necessary to use recursion. A recursive generator is one that uses itself internally, either directly or indirectly by using another generator that depends on the first one. A tree generator is an example of a recursive generator. Below is a simple tree type defined:
trait Tree[T] { def size: Int }
case class Leaf[T]( item: T ) extends Tree[T] { def size = 1 }
case class Node[T] ( children: List[Tree[T]] ) extends Tree[T] { def size = children.map(_.size).sum }
Since trees are inherently recursive, we define a recursive generator that should produce tree instances if it is given a node generator:
import org.scalacheck.Gen import org.scalacheck.Gen.{oneOf, listOf}
def genTree[T](genT: Gen[T]): Gen[Tree[T]] = oneOf(genLeaf(genT), genNode(genT))
def genLeaf[T](genT: Gen[T]): Gen[Leaf[T]] = genT map (Leaf(_))
def genNode[T](genT: Gen[T]): Gen[Node[T]] = for { children <- listOf(genTree(genT)) } yield Node(children)
If you paste the above code into the Scala REPL, remember to use the :paste command so the interdependencies between the methods are handled correctly.
Let's try to create a tree generator by providing genTree with an arbitrary integer generator:
scala> import org.scalacheck.Arbitrary.arbitrary
scala> val genIntTree = genTree(arbitrary[Int]) java.lang.StackOverflowError at org.scalacheck.Gen$class.map(Gen.scala:41) at org.scalacheck.Gen$$anon$3.map(Gen.scala:51) at .genLeaf(<console>:23) at .genTree(<console>:19) at $anonfun$genNode$1.apply(<console>:28) at $anonfun$genNode$1.apply(<console>:28)
Ouch, we didn't expect that nasty stack overflow, did we? As you can see, we got an exception before we even tried to use the generator. The reason for this is the recursive definition of genTree. When Scala evaluates the oneOf method, it first evaluates both parameters, leading to an infinite recursion. This wouldn't be a problem if the oneOf method used call-by-name parameters instead of ordinary call-by-value ones. Instead of requiring every possible generator combinator to use call-by-name parameters, there's a handy method in org.scalacheck.Gen that you can use in these situations. The lzy method takes a generator as its only parameter and returns a new generator that wraps the original generator lazily by delaying its parameter evaluation until it's really needed. Let's change our implementation a bit, using the lzy method:
import org.scalacheck.Gen import org.scalacheck.Gen.{oneOf, listOf, lzy}
def genTree[T](genT: Gen[T]): Gen[Tree[T]] = lzy { oneOf(genLeaf(genT), genNode(genT)) }
def genLeaf[T](genT: Gen[T]): Gen[Leaf[T]] = genT.map(Leaf(_))
def genNode[T](genT: Gen[T]): Gen[Node[T]] = for { children <- listOf(genTree(genT)) } yield Node(children)
Now we can create a generator without running into any problems:
scala> import org.scalacheck.Arbitrary.arbitrary
scala> val genIntTree = genTree(arbitrary[Int]) genIntTree: org.scalacheck.Gen[Tree[Int]] = ...
However, if we try to sample the generator we run into a stack overflow again:
scala> genIntTree.sample res0: Option[Tree[Int]] = Some(Leaf(-2147483648))
scala> genIntTree.sample res1: Option[Tree[Int]] = Some(Leaf(0))
scala> genIntTree.sample java.lang.StackOverflowError at org.scalacheck.Gen$$anonfun$1$$anonfun$apply... at org.scalacheck.Gen$$anonfun$1$$anonfun$apply... at scala.collection.LinearSeqOptimized$class.fo... at scala.collection.immutable.List.foldLeft(Lis... at org.scalacheck.Gen$$anonfun$1.apply(Gen.scal... at org.scalacheck.Gen$$anonfun$1.apply(Gen.scal...
The problem is that the generator diverges, since each node can have an arbitrary number of child nodes. The size of the generated tree simply explodes and causes a stack overflow when Scala tries to create an infinite structure. To get around this, we need a way to generate trees that converge. We can achieve this by using the Gen.sized and Gen.resize combinators that were presented in the previous section.
import org.scalacheck.Gen import org.scalacheck.Gen.{sized, choose, resize, listOfN, oneOf, lzy}
def genTree[T](genT: Gen[T]): Gen[Tree[T]] = lzy { oneOf(genLeaf(genT), genNode(genT)) }
def genLeaf[T](genT: Gen[T]): Gen[Leaf[T]] = genT.map(Leaf(_))
def genNode[T](genT: Gen[T]): Gen[Node[T]] = sized { size => for { s <- choose(0, size) g = resize(size / (s+1), genTree(genT)) children <- listOfN(s, g) } yield Node(children) }
When creating the list of child nodes, the generator now takes into account the size parameter provided by ScalaCheck. In addition, Gen.resize is used when calling genTree to make the number of child nodes smaller on each level in the tree structure. This way, the tree size should converge and stack overflow is avoided. Note that we have to use both sized and resize, since the genTree generator can't know which level in the tree it is in. The only thing it can control is that next level will get a smaller size parameter, by using the Gen.resize combinator.
Let's try out the latest generator implementaion:
scala> import org.scalacheck.Arbitrary.arbitrary
scala> val genIntTree = genTree(arbitrary[Int])
scala> genIntTree.sample res0: Option[Tree[Int]] = Some(Node(List( Leaf(-567182617), Node(List(Leaf(0))), Leaf(2147483647), Leaf(953266546), Node( List(Node(List()))), Leaf(896351754), ...
Finally, the recursive genTree generator works as desired.
6.2 Custom test case simplification
Chapter 3 described how you can define generators for custom types that ScalaCheck does not directly support. You also saw how you can define implicits so that ScalaCheck understands which generator to use by looking at the type of the requested parameter in a forAll-property. This section will take the use of custom types in ScalaCheck one step further, showing how to implement support for the test case simplification feature (also introduced in Chapter 3).
To demonstrate, I will use a very simple type representing arithmetic expressions, shown below:
trait Expression { override def toString = show(this) }
case class Const(n: Int) extends Expression
case class Add( e1: Expression, e2: Expression ) extends Expression
case class Mul( e1: Expression, e2: Expression ) extends Expression
def eval(e: Expression): Int = e match { case Const(n) => n case Add(e1,e2) => eval(e1) + eval(e2) case Mul(e1,e2) => eval(e1) * eval(e2) }
def show(e: Expression): String = e match { case Const(n) => n.toString case Add(e1,e2) => "("+show(e1)+" + "+show(e2)+")" case Mul(e1,e2) => "("+show(e1)+" * "+show(e2)+")" }
Remember to use the :paste command if you paste this code directly into the Scala REPL console.
Next we'll define a generator, genExpr, that can generate instances of the Expression type. Since the generator is recursive, we use the tricks picked up from the previous section to avoid problems with too-large expressions:
import org.scalacheck.Gen
val genExpr: Gen[Expression] = Gen.sized { sz => Gen.frequency( (sz, genConst), (sz - math.sqrt(sz).toInt, Gen.resize(sz/2, genAdd)), (sz - math.sqrt(sz).toInt, Gen.resize(sz/2, genMul)) ) }
val genConst = Gen.choose(0, 10).map(Const(_))
val genAdd = for { e1 <- genExpr; e2 <- genExpr } yield Add(e1, e2)
val genMul = for { e1 <- genExpr; e2 <- genExpr } yield Mul(e1, e2)
We can try out the generator:
scala> genExpr.sample res0: Option[Expression] = Some((9 + (3 + ((0 * (3 + 1)) + 3))))
Now let's define something we can test. The method rewrite below is intended to optimize expressions by finding parts that can be rewritten in a simpler way. This particular implementation of rewrite is not that good, though. It even contains a bug, for demonstration purposes:
def rewrite(e: Expression): Expression = e match { case Add(e1, e2) if e1 == e2 => Mul(Const(2), e1) case Mul(Const(0), e) => Const(0) case Add(Const(1), e) => e case _ => e }
We can specify the behavior of rewrite by defining a simple property that states that a rewritten expression always should evaluate to the same value as the original expression:
import org.scalacheck.Prop.forAll
val propRewrite = forAll(genExpr) { expr => eval(rewrite(expr)) == eval(expr) }
Checking the property reveals that there is something wrong with the rewrite implementation:
scala> propRewrite.check ! Falsified after 40 passed tests. > ARG_0: (1 + (((1 + 10) + 10) * (2 + 0)))
scala> propRewrite.check + OK, passed 100 tests.
scala> propRewrite.check(1000) ! Falsified after 313 passed tests. > ARG_0: (1 + ((8 * ((1 + 0) * (10 * 7))) + (6 * 0)))
As you can see, the property doesn't fail every time. In such cases it can be worthwhile to increase the minSuccessfulTests parameters from the default value of 100 to something higher, as we did in the previous run. That way, you'll get more reliable failures.
In this situation, it would be nice if ScalaCheck could try to simplify the expressions that it finds, just like it does for the standard types. That would make the error much clearer, rather than trying to decipher the rather unwieldy expressions presented above.
To do that, we can define a org.scalacheck.Shrink instance for type Expression. The Shrink type is a class with only one method, named shrink:
trait Shrink[T] { def shrink(x: T): scala.collection.immutable.Stream[T] }
The shrink method takes a value and returns a stream of simpler variants of that value. We use the Stream type because it evaluates all elements lazily, which makes the process of simplifying test cases more performant.
There is no exact definition of what is a simpler variant of a value. You are free to implement the shrink method in a way that makes sense for your particular type. However, the shrink method must converge towards an empty stream. That is, if you run shrink on elements in its output, the original value is not allowed to re-appear. Otherwise, you end up with an infinite number of alternative values.
You can see how ScalaCheck simplifies values by running the shrink method of the module org.scalacheck.Shrink:
scala> org.scalacheck.Shrink.shrink(10) res0: Stream[Int] = Stream(0, ?)
scala> res0.print 0, 5, -5, 8, -8, 9, -9, empty
You create Shrink instances by providing the apply factory method of the Shrink module with the shrinking method for your type. You must make your instance implicit so that ScalaCheck can pick it up automatically during property evaluation. For the Expression type, we can use the following implementation:
import org.scalacheck.Shrink import org.scalacheck.Shrink.shrink import scala.collection.immutable.Stream
implicit val shrinkExpr: Shrink[Expression] = Shrink({ case Const(n) => shrink(n) map Const case Add(e1, e2) => Stream.concat( Stream(e1, e2), shrink(e1) map (Add(_, e2)), shrink(e2) map (Add(e1, _)) ) case Mul(e1, e2) => Stream.concat( Stream(e1, e2), shrink(e1) map (Mul(_, e2)), shrink(e2) map (Mul(e1, _)) ) })
For the Const case, we use ScalaCheck's own integer shrinker. It will provide us with a stream of Int values, and we wrap them in Const objects.
For the Add and Mul, we simplify the expression in three different ways. The first way removes the operator and keeps the left and right expressions. The two other methods keep the operator but simplify the left or right expression, respectively. All the various alternatives are returned in one Stream instance.
We can test that our simplification works as expected for the simple Const case:
scala> org.scalacheck.Shrink.shrink[Expression](Const(10)) res0: Stream[Expression] = Stream(0, ?)
scala> res0.print 0, 5, -5, 8, -8, 9, -9, empty
In the code above, it is important to specify the type variable used by shrink so Scala can pick the correct implicit method.
Before trying out propRewrite with our new simplification support, we'll improve the property by using the labeling techniques presented in Chapter 5. This will make it even easier to debug the rewrite method:
import org.scalacheck.Prop.{forAll, AnyOperators}
val propRewrite = forAll(genExpr) { expr => val rexpr = rewrite(expr) (eval(rexpr) ?= eval(expr)) :| "rewritten = "+rexpr }
If you run these examples in the Scala REPL, you must make sure to define (or redefine) propRewrite after you have defined the Shrink instance. This is because Scala decides on which implicit Shrink instance to use at the time the forAll method is called, not when the property is evaluated.
Check the property a couple of times:
scala> propRewrite.check(1000) ! Falsified after 43 passed tests. > Labels of failing property: Expected 1 but got 0 rewritten = 0 > ARG_0: (1 + 0) > ARG_0_ORIGINAL: (1 + (6 * (7 * ((4 + 0) * (9 + 1)))))
scala> propRewrite.check(1000) ! Falsified after 121 passed tests. > Labels of failing property: Expected 1 but got 0 rewritten = 0 > ARG_0: (1 + 0) > ARG_0_ORIGINAL: (1 + (6 * (7 * 0)))
Now we clearly can see that the rewrite method handles expressions of the form 1 + 0 incorrectly.
6.3 Conclusion
Generating random values is fundamental to property-based testing. Part of ScalaCheck's strength is its ability to come up with test cases without requiring any input from the user. All you need to do is provide forAll with a suitable property function, and ScalaCheck will handle input generation all by itself. However, another strength of ScalaCheck is the combinators and methods it puts at your disposal when implementing generators that can produce exactly the correct random input for your properties. This chapter has presented many of the various generator combinators that exist in ScalaCheck, together with plenty of usage examples. You can now take full advantage of property-based testing, and make sure that ScalaCheck can generate even very specific data structures in a random fashion.