Chapter 4
Designing Properties
The previous chapters have given you a thorough introduction to ScalaCheck properties. You've seen how to write down properties and let ScalaCheck verify them. You have been given a theoretical overview of property-based testing and seen comparisons to traditional unit testing. However, we have not yet touched upon what might be the most tricky part of property-based testing: how should you come up with testable properties for your code?
The concept of a property is not hard to grasp; it's basically a boolean expression. The difficulty lies in transforming the ideas you have about your program's behavior into formal properties suitable for ScalaCheck's verification machinery. This chapter's sections each address a technique, strategy, or way of thinking around how to design and implement properties. The sections are not mutually exclusive, and they are not recipes on how to write property implementations. Rather, you should try to pick up ideas from all of the sections and use this as a toolbox when designing your own properties. Mix and match, and use whatever techniques that make the most sense for your particular situation.
4.1 Incomplete properties
This book's introductory chapters pushed for property-based testing as a way to achieve more complete specifications and better test coverage. It might therefore sound contradictory to recommend writing incomplete properties. However, it can be hard to immediately come up with a ScalaCheck property that completely describes all behavioral aspects that you want to specify. Therefore, it is often easier to write properties in an iterative fashion.
Start out with simple facts that you know always should hold true for your code. A starting question you can ask yourself is: What would be totally unacceptable? For example, the tested method should never return a negative integer. Or, the output list must always be shorter than the input list. These are simple sanity checks, not full specifications. Some concrete ScalaCheck examples:
property("no negative output") = forAll { (m: Int, n: Int) => val result: Int = myMagicMathOperation(m, n) result >= 0 }
property("actually compressed") = forAll { xs: List[String] => val result: List[String] = myCompressor(xs) result.length <= xs.length }
property("is monotonic") = forAll { (n1: Float, n2: Float) => val r1 = myMonotonicFunction(n1) val r2 = myMonotonicFunction(n2) if (n1 > n2) r1 >= r2 else r1 <= r2 }
The last property in the example above checks if myMonotonicFunction is monotonically increasing, which is the mathematical term for a function with a slope that never is negative.
Properties like the ones above can act as a great support when you're starting out development of a piece of code, or when refactoring existing code. They provide definite boundaries for your implementations. Later on you can extend your properties with more complete conditions or simply add more properties, to cover more aspects of the functionality. Don't be afraid of leaving a property incomplete if it starts to get too involved. If a property is equally complex as the code it is supposed to specify, and maybe also similar in its implementation, then there's a high risk of introducing bugs in both the property and the code. Strive to make your properties straightforward, and try to make them as different as possible from the tested code, even if it means you lose specification completeness. This also makes your properties more usable as a readable documentation of your programs.
Incomplete properties can even be more useful than complete properties. In certain cases, you can afford some slack in your implementation. For example, say you're building a web application and want to present a survey to your users, at random. You'll need a function that decides whether each user should be presented with a survey popup. There's no need to precisely specify that function. Instead, you can decide on some boundary conditions, such as: a single user session should never get more than one survey popup, and the likelihood for an individual user to get a popup should decrease with the number of open user sessions. This way, the specification is kept concise and understandable, while the implementation retains some freedom to solve the task in an efficient way.
4.2 Relation properties
A special form of incomplete properties are relation properties. Instead of specifying a unit of code against one input instance at a time, you can use two or more test cases in the same property and base your specification on the relation between the inputs.
For example, say you're implementing a function that should rank Twitter tweets by producing an integer score for each input tweet. A traditional property that verifies the output of the ranking function based only one input instance could look something like this:
import org.scalacheck.{Gen, Prop}
// A tweet generator val genTweet: Gen[String] = ...
// The function under test def rankTweet(tweet: String): Int = ...
val propRankTweet = Prop.forAll(genTweet) { tweet => val score = rankTweet(tweet) ... }
Above we assume we have a generator that is able to generate random tweets. Such a generator could be implemented by constructing random synthetic strings, or by compiling a large list of real tweets and let the generator pick tweets from the list at random.
The problem with this approach is that the propRankTweet property basically would have to duplicate the logic from the function under test, rankTweet, in order say something useful about the output.
However, if we instead let propRankTweet take two tweets as input, we can let the property state facts about the relation between two output instances. For example, if we would like our ranking function to always rank short tweets higher than longer tweets, we can specify that quite easily:
val propRankTweet = Prop.forAll(genTweet, genTweet) { (tweet1,tweet2) => val score1 = rankTweet(tweet1) val score2 = rankTweet(tweet2) if (tweet1.length <= tweet2.length) score1 >= score2 else score1 < score2 }
Now, the propRankTweet property doesn't care about the absolute score returned by rankTweet, it only cares about the relation between outputs given a pair of input values. This gives freedom to the implementation to return any score values as long as the important properties are fulfilled. It also makes the property clear and avoids duplicating the implementation logic.
4.3 Reference implementations
One technique for writing complex specifications is to use a reference implementation. Instead of writing down the direct conditions that should hold, you make an indirect specification by relating your implementation to a known working one. The reference implementation can either be a well-used and tested one from a standard library, or a simple proof-of-concept implementation that you've written from scratch without any considerations other than correctness. The trusted reference implementation can be used to test that another, perhaps performance-optimized, version behaves correctly.
Below, the class IntMap from the Scala library is tested against the standard Java HashMap implementation. IntMap is a specialized immutable map with integer-only keys, based on the concept of Fast Mergeable Integer Maps by Chris Okasaki and Andrew Gill. IntMap's high-performance implementation relies on the fact that keys are always integers. It makes sense to test such a specialized implementation against the tried-and-true Java HashMap implementation.
To be able to write properties for IntMap based on comparisons with HashMap we need a way to generate maps of both kinds, and a way to compare them with each other. We define helpers for this:
import java.util.HashMap import collection.JavaConversions._ import collection.immutable.IntMap
def equalMaps(hm: HashMap[Int,Any], im: IntMap[Any]) = { im.keys.forall(hm.containsKey) && hm.keySet.containsAll(im.keys) && im.keys.forall(k => im(k) == hm(k)) }
import org.scalacheck.Gen import org.scalacheck.Arbitrary.arbitrary
val genMaps: Gen[(HashMap[Int,Any],IntMap[Any])] = arbitrary[List[Int]] map { xs => val mappings = for(n <- xs) yield (n, new Object) val im = IntMap(mappings: _*) val hm = new HashMap[Int, Any] for((n,x) <- mappings) hm.put(n,x) (hm,im) }
genMaps takes advantage of ScalaCheck's ability to automatically generate lists. We let ScalaCheck come up with a random list, and then create IntMap and HashMap instances from that list.
We can now create a property for each method we want to test, using genMaps to get comparable instances of both IntMap and HashMap:
import org.scalacheck.Prop.{forAll, AnyOperators} import org.scalacheck.Properties
object IntMapSpec extends Properties("IntMap") { property("size") = forAll(genMaps) { case (hm, im) => im.size ?= hm.size } property("isEmpty") = forAll(genMaps) { case (hm,im) => im.isEmpty ?= hm.isEmpty } property("add") = forAll(genMaps) { case (hm,im) => forAll { (k: Int, v: String) => hm.put(k, v) equalMaps(hm, im + (k -> v)) } } }
As you can see in the IntMapSpec example, the IntMap methods aren't specified directly; instead the HashMap implementation is employed in each property to make sure the specialized integer map behaves exactly like the generic hash map from the Java standard library.
Of course, the specifications become less formal this way, since we put our trust in the arguably informal reference implementation. However, this is a technique that can be used successfully in cases where direct specifications are hard to define or when it is very simple to define a correct reference implementation that can be used to test a more complex one. You can also use this method in an iterative development process, testing new and improved implementations against old and stable ones. When the reference implementation is familiar one (like the HashMap case), the properties become a great documentation, since it is easy for the reader to understand how the implementation should behave.
4.4 Restricting test cases
A method can have preconditions, which are conditions that are expected to be fulfilled by the caller of the method. It might be restrictions on the input parameters: for example, maybe you are not allowed to send in null values, or negative integers. A method can also demand that the class instance is in a certain state—that certain methods have been invoked or certain fields set before the given method can run.
In logic, a precondition is an implication, which takes the form p =>
q. If p is false, then the whole statement becomes true, no matter what
q is. This is equivalent to saying that if the precondition is false, then
the method behaves correctly no matter what it does. If the caller does not
fulfill the preconditions, then it can't expect the method to fulfill any
conditions. On the other hand, if p is true, then q also must be true for
the whole statement to be satisfied. So, if the caller has fulfilled its
duties, then the method also must fulfill its duties.
Since ScalaCheck borrows much from logic when it comes to writing specifications, preconditions are specified as implications with the ==> operator. You must import Prop.BooleanOperators to make this operator available. This module contains implicit methods that extend boolean values with various property-related operators and methods.
Here is a simple example where a precondition is used in a property:
import org.scalacheck.Prop.{forAll, BooleanOperators}
val propSqrt = forAll { n: Int => (n >= 0) ==> { val m = math.sqrt(n) math.round(m*m) == n } }
This property specifies scala.math.sqrt, which is only defined for non-negative numbers. When ScalaCheck tests this property, it skips over the cases where the precondition is not fulfilled, and regards them as discarded. Discarded test cases are not included in the total sum of passed tests for a property, which means that if the precondition is hard to fulfill when generating random test data, ScalaCheck might not be able to verify the property at all. Consider the following property:
import org.scalacheck.Prop.{forAll, BooleanOperators}
val propSlice = forAll { (xs: List[Int], n: Int, m: Int) => (m >= n && xs.indices.contains(n) && xs.indices.contains(m) ) ==> { val s = xs.slice(n,m) s.length == (m-n) && xs.containsSlice(s) } }
The property propSlice verifies that methods List.containsSlice and List.slice work correctly in relation to each other. The precondition is quite involved in order to filter out any indices that are out of bounds. We now try checking the property:
scala> propSlice.check
! Gave up after only 2 passed tests. 99 tests were discarded.
As you can see, by randomly generating lists and integers ScalaCheck fails to come up with enough input sets that satisfy the precondition. In such cases, we need to help ScalaCheck a bit, and be more explicit about how the parameters should be generated. We can do this by nesting two calls to forAll, and use explicit generators to put boundaries on the generated integers:
import org.scalacheck.Prop.{forAll, BooleanOperators} import org.scalacheck.Gen.oneOf
val propSlice = forAll { xs: List[Int] => forAll(oneOf(xs.indices), oneOf(xs.indices)) { (m, n) => m >= n ==> { val s = xs.slice(n,m) s.length == (m-n) && xs.containsSlice(s) } } }
A console session shows that the property now passes nicely:
scala> propSlice.check
+ OK, passed 100 tests.
Note that, in some special cases ScalaCheck's test case simplification feature can cause troubles when methods with preconditions are tested. In such cases, you need to specify the complete precondition in your property even though you are using custom generators for the method input. An example of such a situation is shown in Chapter 6. Generally, it is never a bad idea to write out the preconditions in your properties, since it also works as documentation of the code under test.
4.5 Round-trip properties
A piece of code can have an inverse. A trivial example is the List.reverse method, which is an inverse of itself. That is, if you run reverse on a list and then run reverse on the resulting list, you end up with the list you started with. More formally, you say that the function g(x) is an inverse function of the function f(x) if the condition g(f(x)) = x holds for all values of x. This condition is really simple to specify in ScalaCheck, at least if you have a way to generate the values of x. For the List.reverse method, we can define the following property:
property("reverse inverse") = Prop.forAll { xs: List[Int] => xs.reverse.reverse == xs }
This property doesn't specify the reverse method completely; it actually says nothing about what the method actually should do. But it states an important fact about reverse, in a very simple way. These kind of properties can be called round-trip properties, and can be very useful when you're dealing with complex implementations and tricky corner cases. They can help catch regression errors and usually exercise lots of code paths in an implementation.
While the List.reverse method is a bit trivial, there is another class of methods that really gain from round-trip properties: decoders and encoders. A decoder (or a parser) can contain a lot of nitty-gritty details, and it is easy to unknowingly introduce errors when implementation changes are made. However, if you also have an encoder, chances are small that you introduce corresponding errors in that implementation at the same time. Therefore, a round-trip property can catch errors that could be hard to discover otherwise, since it often can be difficult to define a property that completely specifies a complex decoder or parser.
Below follows a simple implementation of an encoder and decoder that convert integer values to and from binary strings composed of the characters 1 and 0.
import org.scalacheck.Prop.forAll
def encodeBin(n: Int): String = n match { case 0 => "0" case 1 => "1" case n if n % 2 == 1 => encodeBin(n / 2) + "1" case n => encodeBin(n / 2) + "0" }
def decodeBin(s: String): Int = if (s.isEmpty) 0 else s.last match { case '0' => 2 * decodeBin(s.substring(0,s.length-1)) case '1' => 2 * decodeBin(s.substring(0,s.length-1)) + 1 }
val propDecodeEncode = forAll { n: Int => decodeBin(encodeBin(n)) == n }
We can test the pair of methods with the round-trip property:
scala> propDecodeEncode.check ! Falsified after 2 passed tests. > ARG_0: -1 > ARG_0_ORIGINAL: -927439645
We immediately discover that our implementation doesn't support negative integer values. In this case, we can simply add a precondition to our property to skip negative values:
import org.scalacheck.Prop.{forAll, BooleanOperators}
val propDecodeEncode = forAll { n: Int => n >= 0 ==> (decodeBin(encodeBin(n)) == n) }
For parsers, the idea is the same. Given a method that parses text into an abstract syntax tree type; a pretty-printer that converts these back into text; and a ScalaCheck generator that provides random instances of the abstract syntax tree, you can define a round-trip property. For example:
type AST = ...
def parse(s: String): AST = ...
def prettyPrint(ast: AST): String = ...
val astGenerator: Gen[AST] = ...
val prop = forAll(astGenerator) { ast => parse(prettyPrint(ast)) == ast }
Chapter 6 explains how to define custom generators like the previous astGenerator.
4.6 Constructing optimal output
A variation on the round-trip theme is a case when it is easy to synthesize an optimal output for the method you're testing, but not equally trivial to check whether a given output is optimal.
An example of this is a run-length encoder, which can be (naively) declared like this:
def runlengthEnc[A](xs: List[A]): List[(Int,A)] = ...
Run-length encoding is a simple compression algorithm that looks for sequences of identical items in a data stream. When it finds such sequences, it replaces them by just one item and a number that indicates how many times that item is repeated. An input of List('a','b','b','a') could produce the output List((1,'a'),(2,'b'),(1,'a')) for our runlengthEnc definition. An optimal implementation of runlengthEnc would produce a list where no runs of equal items remain. For instance, you would not want it to produce List((2,"a"),(3,"a")) since it could have been replaced with List((5,"a")). When implementing a property that checks for this, you can let your property check for runs in the output of runlengthEnc. In a way, your property will be a kind of very simple run-length encoder itself. In this specific case you could probably go for such a solution, since the property would be quite easy to implement. In general, though, you should avoid replicating the implementation of the code you're testing in the property that tests it, since you might introduce similar bugs in both implementations.
For the run-length encoder, there's another way to attack the problem. As stated before, the output from runlengthEnc should ideally never contain runs of identical items. An output list meeting this condition can be constructed using ScalaCheck's generators:
import org.scalacheck.Gen import Gen.{choose, alphaNumChar, sized}
val genOutput: Gen[List[(Int,Char)]] = {
def rleItem: Gen[(Int,Char)] = for { n <- choose(1,20) c <- alphaNumChar } yield (n,c)
def rleList(size: Int): Gen[List[(Int,Char)]] = { if (size <= 1) rleItem.map(List(_)) else for { tail@(_,c1)::_ <- rleList(size-1) head <- rleItem retryUntil (_._2 != c1) } yield head :: tail }
sized(rleList) }
The generator uses the Gen.retryUntil method, described in Chapter 6, to avoid too many discarded tests.
We also need a way to decompress a run-length encoded list. Thankfully, that is a one-liner:
def runlengthDec[A](r: List[(Int,A)]): List[A] = r flatMap { case (n,x) => List.fill(n)(x) }
Now we can write a property that tests runlengthEnc in a backward fashion. First, let ScalaCheck generate a sample output, then decode it with runlengthDec, and then make sure runlengthEnc encodes that result into the original list:
val p = Prop.forAll(genOutput) { r =>
runlengthEnc(runlengthDec(r)) == r
}
As you can see, this is a round-trip property like the ones in the previous section. However, since we can be reasonably sure that runlengthDec is correct, our property is a good specification of runlengthEnc. We can also feel confident that the generated expected outputs r cover most of the possible inputs to runlengthEnc. In the parser example from the previous section, that was not the case. Since we only tested the parser with inputs that were generated by the pretty-printer, we most definitely missed out on a large set of inputs that the parser also should be able to handle correctly.
4.7 Conclusion
This chapter has presented a number of techniques you can use when designing properties, but there are plenty of other ways to come up with properties. As property-based testing gains traction, it can be expected that more techniques of property design are discovered. For ScalaCheck users, the natural places to read up and share ideas on this topic are the ScalaCheck web site and mailing list.