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:

	(ns bst-properties-based-testing.binary-search-tree-test
	(:use midje.sweet)
	(:require [bst-properties-based-testing.binary-search-tree :as binary-search-tree]))
	(facts
	"about binary search tree in-order traversal"
	(fact
	"sorts the elements of a tree without any sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [3])) => [3])
	(fact
	"sorts the elements of a tree with left and right sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [2 5 1])) => [1 2 5])
	(fact
	"sorts the elements of a complex tree created inserting values one by one"
	(let [tree (->> (binary-search-tree/singleton 4)
	(binary-search-tree/insert 6)
	(binary-search-tree/insert 5)
	(binary-search-tree/insert 8)
	(binary-search-tree/insert 2)
	(binary-search-tree/insert 3)
	(binary-search-tree/insert 1))]
	(binary-search-tree/in-order tree) => [1 2 3 4 5 6 8]))
	(fact
	"sorts the elements of a complex tree created from a list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [4 6 5 8 2 3 1])) => [1 2 3 4 5 6 8]))

view raw binary-search-tree-tests.clj hosted with ❤ by GitHub

And this was the binary search tree code:

	(ns bst-properties-based-testing.binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes :as nodes]]
	(reduce #(insert %2 %1) (singleton root) rest-nodes))
	(defn in-order [tree]
	(if tree
	(concat (in-order (left tree))
	[(value tree)]
	(in-order (right tree)))
	[]))

view raw binary-search-tree-initial.clj hosted with ❤ by GitHub

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:

	(defproject bst-properties-based-testing "0.0.1-SNAPSHOT"
	:description "Cool new project to do things and stuff"
	:dependencies [[org.clojure/clojure "1.6.0"]]
	:profiles {:dev {:dependencies [[midje "1.6.3"]
	[org.clojure/test.check "0.7.0"]]}})

view raw binary-searc-tre-project.clj hosted with ❤ by GitHub

and added a new spec to the tests:

	(ns bst-properties-based-testing.binary-search-tree-test
	(:use midje.sweet)
	(:require [bst-properties-based-testing.binary-search-tree :as binary-search-tree]
	[clojure.test.check.clojure-test :refer [defspec]]
	[clojure.test.check.generators :as gen]
	[clojure.test.check.properties :as prop]))
	(def in-order-traversal-of-bst-sorts-elements-property
	(prop/for-all [v (gen/vector gen/int)]
	(= (binary-search-tree/in-order
	(binary-search-tree/from-list v))
	(sort v))))
	(defspec in-order-traversal-of-bst-sorts-elements
	100
	in-order-traversal-of-bst-sorts-elements-property)
	(facts
	"about binary search tree"
	(fact
	"creates a tree without any sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [3])) => [3])
	(fact
	"creates a tree with left and right sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [2 5 1])) => [1 2 5])
	(fact
	"creates a complex tree inserting values one by one"
	(let [tree (->> (binary-search-tree/singleton 4)
	(binary-search-tree/insert 6)
	(binary-search-tree/insert 5)
	(binary-search-tree/insert 8)
	(binary-search-tree/insert 2)
	(binary-search-tree/insert 3)
	(binary-search-tree/insert 1))]
	(binary-search-tree/in-order tree) => [1 2 3 4 5 6 8]))
	(fact
	"creates a complex tree from a list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [4 6 5 8 2 3 1])) => [1 2 3 4 5 6 8]))

view raw binary-search-tree-tests-with-property-based-tests.clj hosted with ❤ by GitHub

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):

	======================================================================
	Loading (bst-properties-based-testing.binary-search-tree-test)
	{:test-var "in-order-traversal-of-bst-sorts-elements",
	:result false,
	:seed 1437929928970,
	:failing-size 0,
	:num-tests 1,
	:fail [[]],
	:shrunk {:total-nodes-visited 0,
	:depth 0,
	:result false,
	:smallest [[]]}}
	>>> Output from clojure.test tests:
	FAIL in (in-order-traversal-of-bst-sorts-elements) (clojure_test.clj:18)
	expected: result
	actual: false
	1 failures, 0 errors.
	>>> Midje summary:
	All checks (4) succeeded.

view raw binary_search_tree_tests_output.sh hosted with ❤ by GitHub

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:

	(ns bst-properties-based-testing.binary-search-tree-test
	(:use midje.sweet)
	(:require [bst-properties-based-testing.binary-search-tree :as binary-search-tree]
	[clojure.test.check.clojure-test :refer [defspec]]
	[clojure.test.check.generators :as gen]
	[clojure.test.check.properties :as prop]))
	(def in-order-traversal-of-bst-sorts-elements-property
	(prop/for-all [v (gen/vector gen/int)]
	(= (binary-search-tree/in-order
	(binary-search-tree/from-list v))
	(sort v))))
	(defspec in-order-traversal-of-bst-sorts-elements
	100
	in-order-traversal-of-bst-sorts-elements-property)
	(facts
	"about binary search tree in-order traversal"
	(fact
	"sorts the elements of a tree without any sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [3])) => [3])
	(fact
	"sorts the elements of a tree with left and right sons"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [2 5 1])) => [1 2 5])
	(fact
	"sorts the elements of a complex tree created inserting values one by one"
	(let [tree (->> (binary-search-tree/singleton 4)
	(binary-search-tree/insert 6)
	(binary-search-tree/insert 5)
	(binary-search-tree/insert 8)
	(binary-search-tree/insert 2)
	(binary-search-tree/insert 3)
	(binary-search-tree/insert 1))]
	(binary-search-tree/in-order tree) => [1 2 3 4 5 6 8]))
	(fact
	"sorts the elements of a complex tree created from a list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [4 6 5 8 2 3 1])) => [1 2 3 4 5 6 8])
	(fact
	"sorts the elements of an empty tree created from an empty list"
	(binary-search-tree/in-order
	(binary-search-tree/from-list [])) => []))

view raw binary-search-tree-tests-with-new-failing-test.clj hosted with ❤ by GitHub

and modified the code to make it pass:

	(ns bst-properties-based-testing.binary-search-tree)
	(defn singleton [val]
	{:value val})
	(def value :value)
	(def left :left)
	(def right :right)
	(defn insert [val tree]
	(let [add-node
	(fn [location node]
	(assoc tree location
	(if node (insert val node)
	(singleton val))))]
	(if (<= val (value tree))
	(add-node :left (left tree))
	(add-node :right (right tree)))))
	(defn from-list [[root & rest-nodes :as nodes]]
	(if (empty? nodes)
	nil
	(reduce #(insert %2 %1) (singleton root) rest-nodes)))
	(defn in-order [tree]
	(if tree
	(concat (in-order (left tree))
	[(value tree)]
	(in-order (right tree)))
	[]))

view raw binary-search-tree-corrected.clj hosted with ❤ by GitHub

Now the tests were all passing:

	Loading (bst-properties-based-testing.binary-search-tree-test)
	{:test-var "in-order-traversal-of-bst-sorts-elements", :result true, :num-tests 100, :seed 1437930264045}
	>>> Output from clojure.test tests:
	0 failures, 0 errors.
	>>> Midje summary:
	All checks (5) succeeded.

view raw binary_search_tree_tests_correct_output.sh hosted with ❤ by GitHub

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 :)