Generative Testing with test.check

Generative testing, also called Property Based testing, is a powerful technique able to expose some of the most obscure bugs. You’ll learn how to create and compose generators, and how to define properties that together can verify many aspects of your code.

Transcript

clojure.test.check is a library for testing your code with lots of random data. You first specify certain properties of your program, and test.check will generate data and verify that the properties hold. Let’s see how that looks in practice.

First take a regular unit test. This one tests the normalize function from lambdaisland.uri by feeding it a string, and checking the result.

(ns lambdaisland.uri.normalize-test
  (:require [lambdaisland.uri :as uri]
            [lambdaisland.uri.normalize :as n]
            [clojure.test :refer [deftest testing is are]]))

(deftest normalize-test
  (is (= (str (n/normalize (uri/uri "http://foo.bar?q=💃")))
         "http://foo.bar?q=%F0%9F%92%83")))

That’s a useful test, but that test alone isn’t enough to inspire confidence, so you go on and add more and more of these test cases, each time coming up with some data that tests a specific aspect of the implementation. This works alright, but coming up with good test cases is limited by your patience and imagination.

It’s not just that you won’t come up with enough test cases, it’s also that you will tend to test “reasonable” data, missing many edge cases.

(deftest normalize-test
  (are [in out] (= (str (n/normalize (uri/uri in))) out)
    "http://foo.bar?q=💃" "http://foo.bar?q=%F0%9F%92%83"
    "http://foo.bar/./foo/../bar/baz" "http://foo.bar/bar/baz"
    "HTTP://foo.bar" "http://foo.bar"
    "http://foo.BAR" "http://foo.bar"
    "" ""
    "#" "#"
    ":::Av?%f" ":::Av?%25f"))

Wouldn’t it be great if you could generate test cases on the fly, testing them by the hundreds or thousands?

It’s a nice thought, but how would it work? Generating inputs is easy enough, but you can’t so easily generate the output to test again.

You can rephrase the problem though by looking for invariants, also called properties. These are things that must be true for any input.

Say you are writing a sort algorithm. In a sorted list, the first element can not be bigger than the last element, no matter which list you try this with.

(let [list [-1 -8 -5 5 9 0 4]
      sorted (sort list)]
  (<= (first sorted) (last sorted)))
;;=> true

You can check this property for a very large number of random lists by using generators. Using test.check always starts with setting up some generators. These live in the clojure.test.check.generators namespace, which is usually aliased to gen.

(require '[clojure.test.check.generators :as gen])

The gen/int generator generates numbers. You can try it out with gen/generate, or generate a bunch of them with gen/sample.

You don’t usually use generate or sample a lot in your code, but they’re great for testing out generators from the REPL, so keep them handy. There’s also sample-seq, which returns a lazy, infinite sequence.

(gen/generate gen/int)
;;=> -12

(gen/sample gen/int)
;;=> (0 1 0 0 -3 -2 5 1 -2 -5)

(take 10 (gen/sample-seq gen/int))
;;=> (0 0 -2 -3 0 -1 4 -3 -5 -7)

Some generators combine with others to form more complex generators. The vector generator is a good example. This is how you generate a vector of integers.

(gen/sample (gen/vector gen/int))
;;=> ([] [] [2] [3 3 0] [-1 -3 -4 -3] [1 2 4 -4 2] [4] [5 7] [-5] [])

Let’s assign that generator to a var so you can use it to define a property.

(require '[clojure.test.check.generators :as gen])

(def vector-of-int (gen/vector gen/int))

Properties are defined using the for-all macro from the clojure.test.check.properties namespace.

You first pass it a binding form, a vector which declares which variables need to be assigned, and how values should be generated. In this case the list variable will receive values coming from the vector-of-int generator.

Then you use that list variable to write the actual property, which should evaluate to truthy.

Finally assign it to a var, we’ll test this property next.

(require '[clojure.test.check.properties :as prop])

(def first-cant-be-more-than-last
  (prop/for-all [list vector-of-int]
    (let [sorted (sort list)]
      (<= (first sorted) (last sorted)))))

Finally you’re ready to test wether this property holds, using quick-check from the top level clojure.test.check namespace. Let’s try a hundred different inputs, and see if the property holds.

Owww… that failed straight away. The result of quick-check is a map, and when it fails like this then the :fail key contains the input values that caused trouble.

(require '[clojure.test.check :as tc])

(tc/quick-check 100 first-cant-be-more-than-last)
;;=>
{:seed 1504183219109,
 :failing-size 0,
 :num-tests 1,
 :fail [[]]
 :result #error {:cause nil
                 :via [{:type java.lang.NullPointerException}]
                 :trace
                 [[clojure.lang.Numbers ops "Numbers.java" 1013]
                  [clojure.lang.Numbers lte "Numbers.java" 225]
                  ,,,]}}

Apparently the empty vector causes this property to throw an exception.

(let [sorted []]
  (<= (first sorted) (last sorted)))
;; => Unhandled java.lang.NullPointerException

Let’s fix that for now by just adding an empty? check.

(def first-cant-be-more-than-last
  (prop/for-all [list vector-of-int]
    (let [sorted (sort list)]
      (or (empty? list) (<= (first sorted) (last sorted))))))

And now it works, quick-check generated a hundred lists, and verified that for each of them, after sorting, the first element is no greater than the last.

You can check a few more if you have the time, but this already starts to give you some confidence that sort at least partially does its job.

(tc/quick-check 100 first-cant-be-more-than-last)
;;=> {:result true, :num-tests 100, :seed 1504183661234}

(tc/quick-check 1000 first-cant-be-more-than-last)
;;=> {:result true, :num-tests 1000, :seed 1504183709306}

(tc/quick-check 10000 first-cant-be-more-than-last)
;;=> {:result true, :num-tests 10000, :seed 1504183711023}

Learning to use test.check effectively means learning how to create generators that fit your data, and how to come up with good properties to test. Let’s quickly recap the API, because it’s scattered a bit across namespaces.

The top-level clojure.test.check only defines a single public function, quick-check. The function is called quick-check because that’s the name of the Haskell library that test.check is inspired by.

(require '[clojure.test.check :refer [quick-check]])

(quick-check <num-tests> <property> <kw-args>)

Alternatively you can also check your properties with defspec defined in clojure.test.check.clojure-test. This macro defines a test which verifies the property, and is compatible with the built-in clojure.test testing library.

(require '[clojure.test.check.clojure-test :refer [defspec]])

(defspec first-cant-be-more-than-last-test
  (prop/for-all [list vector-of-int]
    (let [sorted (sort list)]
      (or (empty? list) (<= (first sorted) (last sorted))))))

(clojure.test/run-tests)
;;=> {:test 1, :pass 1, :fail 0, :error 0, :type :summary}

The properties themselves are defined with for-all in the clojure.test.check.properties namespace, which takes a binding form, and then a body expression.

for-all is a macro. There’s also a plain function version, for-all*, which is useful if you want to simply wrap a pre-existing predicate.

(require '[clojure.test.check              :refer [quick-check]]
         '[clojure.test.check.clojure-test :refer [defspec]]
         '[clojure.test.check.properties   :refer [for-all  ;; macro
                                                   for-all* ;; function
                                                   ]])

test.check works both on Clojure and on ClojureScript, but since defspec and for-all are macros, you need to use :refer-macros when using them from ClojureScript.

(require '[clojure.test.check :refer [quick-check]]
         '[clojure.test.check.clojure-test :refer-macros [defspec]]
         '[clojure.test.check.properties :refer-macros [for-all]])

Everything else, some 70-odd generators and related functions, are all cramped together in clojure.test.check.generators.

Functions in that namespace roughly fall into five categories: scalar generators, collection generators, generator combinators, generator modifiers, and functions that consume generators.

(require '[clojure.test.check              :refer [quick-check]]
         '[clojure.test.check.clojure-test :refer [defspec]]
         '[clojure.test.check.properties   :refer [for-all for-all*]]

         ;; ~70 generators and generator combinators
         '[clojure.test.check.generators :as gen])

The most basic generators generate just a single value, I call these scalar generators. All of Java’s number types, as well as Clojure’s ratio all have corresponding generators.

(gen/generate gen/byte)              ;;=> -30
(gen/generate gen/char)              ;;=> \h
(gen/generate gen/int)               ;;=> 16
(gen/generate gen/double)            ;;=> 0.038860321044921875
(gen/generate gen/ratio)             ;;=> -7/16

There are also specialized number generators for positive and negative integers, which both have a strict version which doesn’t return 0.

Finally there’s choose, you give it a lower and an upper bound, and it picks an integer within the given range.

(gen/generate gen/pos-int)                     ;;=> 11
(gen/generate gen/neg-int)                     ;;=> -26
(gen/generate gen/s-pos-int)                   ;;=> 11
(gen/generate gen/s-neg-int)                   ;;=> -21
(gen/generate (gen/choose 50 500))             ;;=> 116

Strings, keywords, and symbols also have their own generators, with variants for namespaces keywords and symbols. Notice that these last two have a slash in them.

(gen/generate gen/string)                      ;;=> "\b¬Ð¦"
(gen/generate gen/keyword)                     ;;=> :On*+Jg7dfxz-PRY!g?3fUD:A
(gen/generate gen/symbol)                      ;;=> O837r!Z_hgG!
(gen/generate gen/keyword-ns)                  ;;=> :O7ThR-g++*D5--70J912_*1y/r9-7qec
(gen/generate gen/symbol-ns)                   ;;=> b1_?Gj81yfuA*c9F-b-*9/?Z0??-?*e6XEg!eT?._W!d

To generate collections like vectors or maps you use collection generators, passing in other generators to handle the elements inside the collection.

(gen/sample (gen/vector gen/boolean))          ;;=> ([] [false] [false true] [true])
(gen/sample (gen/map gen/keyword gen/pos-int)) ;;=> ({} {} {:T9:lXZ:2++ 2} {:!v 2, :m 2, :-UW:*E1!:3*l 0})
(gen/sample (gen/hash-map :name gen/string
                          :age gen/int))       ;;=> ({:name "", :age 0} {:name "", :age 0} {:name "y", :age 2})

These are again just generators, so you combine them however which way you choose. A vector of maps with vectors as values? Not a problem.

(gen/generate
 (gen/vector
  (gen/map gen/pos-int
           (gen/vector gen/pos-int))))
;;=> [{} {1 [3 17 17 20 24 0], 0 [22 17 4]} {22 [15], 2 [21 20 30 19 8 27 12 20 23 12 20 6 19 0 13 13 7 15], 6 [14 25 16 4 18 26 13 9 6 30 26 30 16 20 27 11 12 2 8 13 28 29 15 9]}]

Generator combinators and generator modifiers let you build new generators based on existing ones. For instance, fmap and such-that are similar to map and filter. fmap lets you apply a regular function over the results of a generator, and such-that lets you reject certain generated values.

So this first example will generate only cubic numbers, and the second one generates strings that don’t contain the letter “a”.

;; generate cubic numbers
(gen/sample (gen/fmap #(* % % %) gen/pos-int))                   ;;=> (0 1 8 1 1 64 0 216 64 512)

;; generate strings that don't contain the letter "a"
(gen/sample (gen/such-that #(not (re-find #"a" %)) gen/string))  ;;=> ("" "" "" "î�" "«n9”" "{" "±ËÇ\t" "" "hp'" "^")

If you look at the docs for generate you’ll notice there’s an optional size parameter, which defaults to 30. What this does depends on the specific generator, for instance, number generators may use this as a maximum size for the generated number, or a vector generator could use this as an upper bound for the size of the vector.

When generating data for tests, test.check will start with a small size parameter, and gradually increase it, testing with larger and larger values. Most of the time you don’t have to worry about the size, but it’s good to know why it’s there.

clojure.test.check.generators/generate
 [generator]
 [generator size]
  Returns a single sample value from the generator, using a default
  size of 30.

There’s also a resize modifier, for giving generators a specific fixed size.

(gen/sample
 (gen/fmap #(* % % %) (gen/resize 1000 gen/pos-int)))
;;=> (12812904 37595375 86938307 401947272 2000376 1030301 1259712 656234909 862801408 1225043)

When running quick-check it will try progressively larger generated values, until it finds a value for which the property does not hold. This value may be huge though, a string with thousands of characters, or a vector nested hundreds of levels deep, which isn’t very helpful for pinpointing the problem.

Therefore quick-check tries to progressively “shrink” the value again, until it’s found a minimal case that violates the property. What shrinking means is generator-dependent. It could for instance mean removing characters from a string, or elements from a vector.

In the quick-check output you find the value that originally caused the property to fail under the :fail key. The :shrunk key contains the result after shrinking, with some indicators of how many steps it took to find a value that could no longer be made any smaller.

This shrinking is really what makes test.check awesome.

(tc/quick-check 10000
                (prop/for-all [s gen/string]
                  (= s (str (uri s)))))
;;=>
{:result false,
 :seed 1505742494487,
 :failing-size 54,
 :num-tests 55,
 :fail ["²Ôpòü³Áá)ØÑH¸Á«q�\"R´»#†5OÂR\f™ë—Žúø\nL"],
 :shrunk {:total-nodes-visited 65, :depth 39, :result false, :smallest ["#\n"]}}

If you look again at the map that quick-check outputs, there’s something else there as well, a number called :seed. It’s a random number that determines which exact values are generated. You can pass this :seed value back to quick-check as a keyword argument, and it will re-check the property using the exact same values as before.

So suppose quick-check finds an obscure bug, you fix it, and then you run quick-check again and it passes. Did it pass because the bug is fixed, or because it happened to pick values that didn’t trigger the bug? By using the :seed value that initially triggered the bug, you can make sure you actually fixed it.

This is especially helpful if your implementation turns out to have multiple bugs. Each run of quick-check may trigger a different bug. By using :seed you can focus on one bug at the time.

Another use case is reproducing failures that happened on the build server. Just copy the seed from the build output and take it from there.

(tc/quick-check 100 first-cant-be-more-than-last)
;;=>
{:seed 1504183219109,
 :failing-size 0,
 :num-tests 1,
 :fail [[]]
 :result #error {:cause nil
                 :via [{:type java.lang.NullPointerException}]
                 :trace
                 [[clojure.lang.Numbers ops "Numbers.java" 1013]
                  [clojure.lang.Numbers lte "Numbers.java" 225]
                  ,,,]}}

;; fix the bug, then re-run the exact same tests
(tc/quick-check 10000 first-cant-be-more-than-last :seed 1504183219109)
;;=> {:result true, :num-tests 100, :seed 1504183219109}

Writing generative tests takes some getting used to. With practice you’ll learn to write generators that fit your domain, but it can still be a challenge to come up with properties to test.

You’ll find that most properties fit one of six categories, so if you need some inspiration you can mentally go over this list, and see if any of these categories apply to the code you’re writing.

The first category is round tripping. This applies to operations that are each other’s opposite, like encode/decode, or parse/unparse. For example, lambdaisland.uri contains functions that perform percent encoding and decoding of URI segments. This test assures that after encoding and then decoding a string the result is unchanged.

(defspec percent-encode-round-trip-test
  (for-all [s gen/string]
    (= s
       (-> s
           n/percent-encode
           n/percent-decode))))

Another category of property based tests are tests that check an implementation against a reference implementation. This may not sound too useful at first, why would you implement something if another implementation is already available? And yet this is more common than you might think, especially for low level algorithms.

The simplest example is checking an optimized implementation against a naive, brute force version. The latter will be too slow for production use, but it’s easy to write, and less likely to contain bugs.

Also don’t forget other JVM languages. When writing the normalize function in lambdaisland.uri I used JRuby to compare it to the normalize functionality from Ruby’s Addressable::URI library. You could do the same thing to compare algorithms across Java, Scala, Groovy, or any other JVM language. This will often find bugs in both implementations, or gray areas where they “agree to disagree”, and which are worth documenting.

Here you also see an example of how to build up a string from a custom set of characters. I first create a generator that generates individual characters, then generate sequences of characters with gen/vector, and turn them into strings with fmap and clojure.string/join.

(def char-valid-uri (gen/one-of [gen/char-alphanumeric
                                 (gen/elements [\- \. \_ \~
                                                \: \/ \? \# \[ \] \@
                                                \! \$ \& \' \( \) \* \+ \, \; \=])]))

(def string-valid-uri (gen/fmap clojure.string/join
                                (gen/vector char-valid-uri)))

(tc/quick-check 1000
                (prop/for-all [s string-valid-uri]
                  (= (ruby.addressable/normalize s) (into {} (normalize (uri s))))))

The third category is called “Same Destination, Different Route”. A naive example of this is making a string uppercase, and then reversing it. Wether you reverse it first and then turn it uppercase or the other way around, the result should be the same.

(defspec reverse-uppercase-test
  (for-all [s gen/string]
    (= (-> s
           clojure.string/upper-case
           clojure.string/reverse)
       (-> s
           clojure.string/reverse
           clojure.string/upper-case))))

If you have functions that are idempotent, meaning you can apply them multiple times without changing the result, then this is also a great thing to test for.

Normalizing an already normalized URI should not change it. You can call normalize on it as many times as you like, the result should stay the same.

Also noticed that this is a cross-plaform Clojure/ClojureScript test. It uses some reader conditionals to select the right syntax for the current platform.

(defspec normalize-idempotence-test
  (for-all [s gen/string]
    (= (-> s
           uri/parse
           n/normalize)
       (-> s
           uri/parse
           n/normalize
           n/normalize))))

The fifth category are invariants. These are probably the first thing you think of when talking about “properties”.

This can mean checking a result for internal consistency. A percent encoded string should only contain the percent character and hexadecimals. It can also mean verifying some relationship between the input and output. For instance, a sorted collection should have the same size as its unsorted counterpart.

(defspec percent-encode-consistency-test
  (for-all [s gen/string]
    (re-find #"^(%[0-9A-F]{2})*$" (n/percent-encode s))))

The final category are things that are hard to do, but easy to verify. Take a sudoku solver. Implementing it is hard, but verifying that the final result is correct is trivial.

Show Notes

Broad overview of the API

(require '[clojure.test.check              :refer [quick-check]]
         '[clojure.test.check.clojure-test :refer [defspec]]
         '[clojure.test.check.properties   :refer [for-all for-all*]]

         ;; ~70 generators and generator combinators
         '[clojure.test.check.generators :as gen])

Example property-based test

(ns lambdaisland.sorted-test
  (:require [clojure.test.check.generators :as gen]
            [clojure.test.check.properties :as prop]
            [clojure.test.check.clojure-test :refer [defspec]]))

(def vector-of-int (gen/vector gen/int))

(defspec first-cant-be-more-than-last-test
  (prop/for-all [list vector-of-int]
    (let [sorted (sort list)]
      (or (empty? list) (<= (first sorted) (last sorted))))))

Generators

There really is a lot cramped together in the generators namespace, which makes the API docs a bit difficult to navigate. To get a better sense of what’s there I’ve categorized the various functions. If you’re ready to dig deeper I encourage you to read up on the functions under “Combinators” and “Modifiers”.

Types of properties

Most properties fall in these categories. When looking to test a function, go over this list to get ideas for properties to check.

Round Trip

Do an operation and its inverse.

Alternative Implementation

Verify against a reference implementation.

Same Destination, Different Route

Re-order operations without changing the result.

Idempotence

When doing something twice is the same as doing it once.

Invariants (size, contents, consistency)

Some things are always true. Some things never change.

“Hard to do, easy to verify”

I don’t know what you did there, but I can see that it’s right.