Property Based Testing in Scala

Problem Overview

Earlier this year was the qualification round for Google Hashcode 2017 .

In order to prepare a bit, I started working on the practice problem : Slice the Pizza .

It involves slicing a pizza in slices small enough, with enough Tomato and Mushrooms in each slice, and getting as much of the pizza in the slices.

Once I have selected some slices, I need to check if other possible slices intersect with the selected ones. So I had a code similar to this one, which checks if there is a common cell:

case class Slice(row1: Int, row2: Int, col1: Int, col2: Int) {
  lazy val cells = (for {
    r <- row1 until row2
    c <- col1 until col2
  } yield Point(r, c)).toSet

  def intersects(that: Slice) = cells.exists(that.cells.contains)
}

I was concerned about the performance of this code and I wanted to rewrite it using only the col and row indices.

Property Based Testing

Short intro to PBT

Test Driven Development leads to better production code, but it has its limitations. We can only write so many tests, and the more tests we maintain, the more tests we might change with new requirements. Can we do better?

Property-based testing is a technique out of functional programming that works in any language. Property-based tests make statements about the output of your code based on the input, and these statements are verified for many different possible inputs. A property-based testing framework runs the same test over and over with generated input.

This contrasts with example-based testing, which is most of the tests we write these days.

Testing that the new implementation behaves the same way

I wanted to be sure to avoid regressions and that the new implementation of intersects returns the same result as the old one in all cases.

This can be achieved easily with ScalaCheck framework (integrated with ScalaTest ).

Here is the basic test I wanted to write:

"2 Slices" should "intersect properly" in {
  forAll { (slice1: Slice, slice2: Slice) =>
    slice1.intersects(slice2) shouldBe slice1.cells.exists(slice2.cells.contains)
  }
}

Generating test instances of Slice

By adding scalacheck-shapeless as described in this sample project , we can have ScalaCheck generate automatically instances of case classes.

<dependency>
  <groupId>com.github.alexarchambault</groupId>
  <artifactId>scalacheck-shapeless_1.13_2.11</artifactId>
  <version>1.1.1</version>
  <scope>test</scope>
</dependency>

But this is not very usefull here since a Slice only makes sense for specific rows and cols.

So it’s better to control the generation of our own Slices, with rows and cols between 1 and 200, and be sure that row2 > row1.

implicit val arbitrarySlice = Arbitrary {
  for {
    row1 <- Gen.chooseNum(1, 200)
    row2 <- Gen.chooseNum(row1 + 1, 200)
    col1 <- Gen.chooseNum(1, 200)
    col2 <- Gen.chooseNum(col1 + 1, 200)
  } yield Slice(row1, row2, col1, col2)
}

New implementation of intersects

With this in place, I can change the implementation of intersects. I made several tries before arriving to this one, hence the utility of my test!

 def intersects(that: Slice) = {
    @inline def between(a: Int, b: Int, x: Int) = x >= a && x <= b
    @inline def intersects1d(x1: Int, x2: Int, a1: Int, a2: Int) =
      between(x1, x2, a1) || between(x1, x2, a2) ||
        between(a1, a2, x1) || between(a1, a2, x2)

    intersects1d(col1, col2 - 1, that.col1, that.col2 - 1) && intersects1d(row1, row2 - 1, that.row1, that.row2 - 1)
  }

I could have checked that the new implementation is really faster with a ScalaMeter microbenchmark but this is another story.

Shrinking

ScalaCheck can perform “shrinking” on the instances generated which fail your test. This gives you better error messages with simpler instances.

It does it automatically for basic types (Lists, Int …) but you need to provide a Shrinker for your own classes. It’s rather simple when you reuse the existing shrink method which takes a Tuple.

implicit val shrinkSlice: Shrink[Slice] = Shrink {
  case Slice(a, b, c, d) => for {
    (a1, b1, c1, d1) <- shrink((a, b, c, d))
  } yield Slice(a1, b1, c1, d1)
}

You can find the full test file on my Github project .