Applying property-based testing on my binary search tree implementation

Some weeks ago I did the the Binary Search Tree problem from Exercism in Clojure.

I used TDD using some of the sample tests that Exercism provided and some other that I added.

These were the tests, after deleting some redundant ones:

And this was the binary search tree code:

I was just testing a few cases.

To gain confidence in my solution and play a bit more with the exercise, I decided to apply a bit of property-based testing on it.

So I added the clojure/test.check dependency to my project:

and added a new spec to the tests:

The in-order-traversal-of-bst-sorts-elements spec is checking the in-order-traversal-of-bst-sorts-elements-property 100 times.

For each check, the generator creates a random vector of integers and checks if the result of calling in-order on the binary search tree created from the vector is equal to the sorted vector.

The macro clojure.test.check.clojure-test/defspec allows to integrate clojure/test.check with clojure.test, so that properties can run under the clojure.test runner.

Midje, the test framework I'm using, can also detect and run clojure.test tests.

Ok, after running the tests, this is what I got (formatted so it fits without a lot of scrolling):

There was a case that was failing.

A really nice thing about clojure/test.check is that it tells you the smallest case that makes your code fail. See the value of the :smallest key inside the map associated to the :shrunk key of the map in the output.

I had forgotten to write a test for the empty vector!

So I added a new failing test for that case:

and modified the code to make it pass:

Now the tests were all passing:

At this moment, I could have deleted all the unit tests and kept only the property-based ones, because the former were now redundant.

I chose not to do it, because I really like the readability of midje's facts.

In this case, I've used property-based testing to thoroughly check my solution after I had finished doing TDD. I wasn't wearing the TDD hat when I used it, I was just doing testing.

I think property-based testing and TDD can complement each other very nicely.

Another way to combine property-based testing and TDD is using the capability of clojure/test.check of giving you the smallest case that fails to help you choose the next test to drive your code.

Jan Stępień talked about this in his talk in last EuroClojure conference:

• Generative Testing: Properties, State and Beyond.

Another thing to consider is that the smallest case that makes the code fail given by property-based testing may not always correspond to the test that allows the code to grow in a small and easy to implement step.

I think that chances are that many times it might be, though.

Another thing to explore :)