Property Based Testing in Elixir

Posted on June 22, 2016
Tags: elixir, haskell, testing, quickcheck

Contents

TL;DR

Property based testing lets the developer describes properties about his or her code that should always hold true. QuickCheck style testing frameworks use random data, derived from user supplied generators, to repeatedly test these properties. In this way, a single property test can result in hundreds of test runs against a random sample of possible inputs. ExCheck is an Elixir library for property based testing.

Last edited: 2016-07-29

Introduction

Testing code is difficult. Writing effective tests requires thinking about how to actually break the tested code. It isn’t enough to write example tests that cover the best-case or most obvious scenarios. Instead, it is necessary to consider the entirety of the function’s domain and determine which arguments are the best for covering both the desired functionality and edge cases.

A good test suite is an experiment designed to find evidence to reject the hypothesis1 that the tested code is correct. As with any set of experiments, thousands of test cases can support the hypothesis, but the developer must try to find and test against the one case of unaccounted for or malformed input that will cause the system to crash.

That said, I find that for personal projects I often end up neglecting rigorous automated testing. Instead, I tend to exercise my modules and functions in a repl because there’s less up front cost to that than coming up with appropriate test cases that fully cover the functional domain2. Unlike traditional example based testing (writing one test run at a time: perform some set up, add a few carefully crafted examples, and check that the results equal some expected outcome), I believe that property based testing provides the right balance of power to time to make it worthwhile.

Property based testing was popularized by Haskell’s QuickCheck library. Since its debut in 1999, QuickCheck has been ported in some capacity to many languages. To write property based tests, the developer specifies properties or laws about his or her code that should always hold true. Each property is then tested against a large number of random inputs; in this way, a single property is tested with arguments randomly sampled from the function’s domain (e.g. very large numbers, very small numbers, empty lists, unicode characters, binary data, etc…) as is appropriate based on the function’s signature.

Anatomy of QuickCheck tests

QuickCheck tests require a few things3:

  • A boolean property written as a function
commutativeAdd x y = x + y == y + x
  • A way to generate sample data (in QuickCheck, this is the property’s type declaration)
commutativeAdd :: Int -> Int -> Bool
  • Optionally, a predicate or condition to filter out some subset of generated inputs
  • Optionally, a number of tests to run for a property; this is 100 by default

QuickCheck randomly generates inputs that fit the type declaration to test the property’s validity. If a test fails, QuickCheck shrinks the test input to find the smallest example of a failing value4. For functions that operate on more complex types, users can write generators that tell QuickCheck how to randomly create test data.

A suite of property tests for a list reversal function could look like the following5:

-- Reversing a list twice is the same as
--   the original list.
prop_doubleReverseList :: [Int] -> Bool          -- Type declaration/input generator
prop_doubleReverseList xs =
  xs == reverse(reverse xs)                      -- Property to test

-- A reversed list is the same length as 
--  the original list.
prop_reverseLength :: [Int] -> Bool
prop_reverseLength xs =
  length xs == length $ reverse xs

-- The first element of a list becomes the 
--   last element when reversed.
prop_reverseHeadToLast :: [Int] -> Property
prop_reverseHeadToLast xs =
  length xs > 0 ==>                             -- Predicate, so we don't test against empty lists 
  (head xs) == (last $ reverse xs)

Running these tests in ghci (the Haskell repl):

$ cabal repl
Preprocessing executable 'reverse_test' for quickcheck-demo-0.1.0.0...
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( reverse_test.hs, interpreted )
Ok, modules loaded: Main.
*Main> quickCheck prop_doubleReverseList        # Running the quickCheck function on a property 
+++ OK, passed 100 tests.
*Main> quickCheck prop_reverseLength 
+++ OK, passed 100 tests.
*Main> quickCheck prop_reverseHeadToLast 
+++ OK, passed 100 tests.

So, coming up with a few properties that a reverse function on a list should satisfy, allows us to run hundreds of tests with randomly generated data.

ExCheck

ExCheck is an Elixir property based testing library that is built on top of the Erlang QuickCheck port Triq. ExCheck allows developers to easily add property based tests to test suites with minimal friction.

To demonstrate its use, we’ll create a new Elixir project for an implementation of the quicksort algorithm and write some tests based on properties that a sorted list should satisfy.

Project setup6

We’ll start by creating a new project using mix new:

$ mix new quicksort
  * creating README.md
  * creating .gitignore
  * creating mix.exs
  * creating config
  * creating config/config.exs
  * creating lib
  * creating lib/quicksort.ex
  * creating test
  * creating test/test_helper.exs
  * creating test/quicksort_test.exs

Your Mix project was created successfully.
You can use "mix" to compile it, test it, and more:

    cd quicksort
    mix test

Run "mix help" for more commands.

# From here out it we'll work in the project directory.
# All paths will be relative to it.
$ cd quicksort

To add ExCheck to the project, modify the dependencies section7 of mix.exs to look like:

defp deps do
  [
    {:excheck, "~> 0.3", only: :test},
    {:triq, github: "krestenkrab/triq", only: :test},
  ]
end

To install these dependencies, run:

$ mix deps.get

Quicksort

This is the quicksort implementation that we’re going to test:

defmodule Quicksort do
  @moduledoc """
  Implementation of quicksort algorithm for sorting lists.

  ## Examples

    iex> Quicksort.sort([4,5,2,3,1])
    [1,2,3,4,5]

  """

  @spec sort([any]) :: [any]
  def sort([]), do: []
  def sort(array) do
    [head | tail] = array
    pivot = head
    smaller = tail |> Enum.filter(&(&1 <= pivot))
    greater = tail |> Enum.filter(&(&1 > pivot))
    [sort(smaller) | [pivot | sort(greater)]] |> List.flatten
  end
end

This should go in lib/quicksort.ex.

Building a test suite for Quicksort.sort

Properties

To make sure that the sorting function is doing what we expect, we can create a test suite of properties that should hold true for sorted lists. We’ll use the following properties (expressed in pseudocode) to test our quicksort:

  • Sorting an already sorted list is the same as the initial list8.
sort(sort(x)) == sort(x)
  • Sorting a list with a single item results in the single element list.
sort([1]) == [1]
  • The first element of a sorted list should be less than or equal to the last element of the list.
sorted = sort(aList)
head(aList) <= last(aList)
  • Sorting a list with our sorting function should give the same result as sorting with Elixir’s standard sorting function.
Quicksort.sort(x) == sort(x)

ExCheck specific usage

  1. Properties

    In ExCheck, we use the property macro to define our tests:

    property :property_name do
      ...
    end

    Inside of the block, we’ll include our generators, (optionally) predicates, and property equations.

  2. Generators

    The generator is the first thing we specify inside of the property macro. These follow the format:

    property :property_name do
      for_all :var in :generator do
        ...
      end
    end

    ExCheck provides generators for the following types9:

    • list/1, tuple/1, int/0, int/1, int/2, byte/0, real/0, sized/1, elements/1, any/0, atom/0, atom/1, choose/2, oneof/1, frequency/1, bool/0, char/0, return/1, vector/2, binary/1, binary/0, non_empty/1, resize/2, non_neg_integer/0, pos_integer/0,
    • unicode_char/0, unicode_string/0, unicode_string/1, unicode_binary/0, unicode_binary/1, unicode_binary/2, unicode_characters/0, unicode_characters/1,
    • bind/2, bindshrink/2, suchthat/2, pick/2, shrink/2, sample/1, sampleshrink/1, seal/1, open/1, peek/1, domain/3, shrink_without_duplicates/1
  3. Specifying predicates (implies, such_that)

    Optionally, we can use the implies macro to predicate the generated test data.

    property :property_name do
      for_all :var in :generator do
        implies {:predicate} do
          ...
        end
      end
    end

    The implies macro will be useful to write a test for the third property we came up with previously, the head of a sorted list should be less than or equal to the last element. Without constraining the test input here, an ArgumentError would be raised if we tried to call head on an empty list (hd([])).

    property :head_less_eql_to_tail do
      for_all x in list(int) do
        implies x != [] do                # Condition for test data
          sorted = Quicksort.sort(x)
          hd(sorted) <= List.last(sorted)
        end
      end
    end

    A potential drawback to using implies is that it generates the data up front and simply skips test runs on data that fail the predicate. Depending on the probability of generating data that satisy the condition, it’s possible that a lot of runs could be skipped. An alternative is to define a generator using the such_that macro.

    These take the form for_all :var in such_that(:var in :generator when :predicate) do. Using such_that, we could rewrite this test as:

    property :head_less_eql_to_tail_two do
      # x can be any list of integers as long as it isn't empty
      for_all x in such_that(x in list(int) when x != []) do
        sorted = Quicksort.sort(x)
        hd(sorted) <= List.last(sorted)
      end
    end

    Now, we’ve written the generator so that all the data generated for the test satisfy the predicate. The tradeoff is that, if the generator is particularly complex, it can take longer to generate the data.

Testing

So, we’ve got a quicksort implementation (in lib/quicksort.ex), we have some properties that we believe our quicksort should satisfy, and we’ve seen the form that ExCheck tests should take.

Let’s put it all together and write our tests for Quicksort.sort.

First, we need to update test/test_helper.exs so that we can use ExCheck.

ExUnit.start()         # This should be the only line in the file.
ExCheck.start()        # Add this line.

Then, we’ll replace test/quicksort_test.exs with the following (these are the properties we previously devised expressed as ExCheck tests):

defmodule QuicksortTest do
  use ExUnit.Case, async: true
  use ExCheck                           # Import ExCheck into the module.
  doctest Quicksort

  property :sort_is_idempotent do
    for_all x in list(int) do           # Generate lists of integers
      sorted = Quicksort.sort(x)
      Quicksort.sort(sorted) == sorted  # This is the property to test
    end
  end

  property :single_element_list_is_sorted do
    for_all x in int do                 # Generate single integers
      Quicksort.sort([x]) == [x]        # Property test
    end
  end

  property :head_less_eql_to_tail do
    for_all x in list(int) do           
      implies x != [] do                # Predicate indicating we want to skip tests on empty lists
        sorted = Quicksort.sort(x)
        hd(sorted) <= List.last(sorted)
      end
    end
  end

  property :head_less_eql_to_tail_two do
    for_all x in such_that(x in list(int) when x != []) do # Generate test data without any empty lists
      sorted = Quicksort.sort(x)
      hd(sorted) <= List.last(sorted)
    end
  end

  property :sorts_integers do
    for_all x in list(int) do
      Quicksort.sort(x) == Enum.sort(x)  # Test against Elixir's sort 
    end
  end

  property :sorts_real_numbers do
    for_all x in list(real) do          # Generate lists of real numbers
      Quicksort.sort(x) == Enum.sort(x)
    end
  end
end

We can now run our tests from the command line:

$ mix test --trace test/quicksort_test.exs

QuicksortTest
  * test sorts_real_numbers_property (23.1ms)..................................................
    .........................................
  * test head_less_eql_to_tail_property (14.6ms).x.............................................
    .................x..............x............
  * test single_element_list_is_sorted_property (1.0ms)........................................
    ....................................................
  * test sorts_integers_property (11.6ms)......................................................
    ....................................
  * test sort_is_idempotent_property (31.3ms)..................................................
    ..........................................
  * test head_less_eql_to_tail_two_property (10.4ms)...........................................
    ...............................................
  * test moduledoc at Quicksort (1) (0.02ms)


Finished in 0.1 seconds
606 tests, 0 failures

Randomized with seed 339750

The x’s in the output indicate tests that failed the implies predicate and were skipped.

In this case, all of our tests passed. One of the most useful things about ExCheck and other QuickCheck ports though is what happens when tests fail.

Failure

When tests fail, ExCheck attempts to shrink the generated input into a minimal example of failure.

To demonstrate, we can add a test that we expect to fail, e.g. with our Quicksort.sort function, a sorted list’s head should be greater than its last element:

property :head_greater_than_tail do
  for_all x in list(int) do
    implies x != [] do
      sorted = Quicksort.sort(x)
      hd(sorted) >= List.last(sorted)
    end
  end
end

Running this (other tests omitted for brevity) results in:

  * test head_greater_than_tail_property (5.3ms)
......................................................................
  1) test head_greater_than_tail_property (QuicksortTest)
     test/quicksort_test.exs:52
     Expected truthy, got false
     code: ExCheck.check(prop_head_fail(), context[:iterations])
     stacktrace:
       test/quicksort_test.exs:52: (test)

Failed!

Failed after 3 tests with false
Simplified:
        x = [0,-1]

ExCheck is telling us that our property doesn’t hold up and it gives us an example of input that results in failure. In our property, we expected the head of the list to be greater than or equal to the last element; 0 >= -1 in this case. Shrinking is extremely useful for checking assumptions you’ve made about your code, discovering edge cases you hadn’t considered, sanity checking the properties themselves, and debugging in general.

Conclusion

I find property based testing to be a valuable tool for thoroughly testing code and helping me to uncover edge cases that I hadn’t properly handled. Formalizing the properites that I want to test helps me to think about what it is I actually want my code to do.

ExCheck provides a nice QuickCheck implementation for Elixir by leveraging triq, an existing Erlang QuickCheck port. By using ExCheck’s properties, generators, and predicates, you can add this powerful testing methodology to your repertoire.

Further Reading

QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs
Claessen & Hughes, 1999. pdf
QuickCheck: An Automatic Testing Tool for Haskell
The QuickCheck user manual. http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html
Property-Based Testing Basics
http://ferd.ca/property-based-testing-basics.html
Hypothesis Quick Start Guide
Specifically for Python’s Hypothesis, but still useful. https://hypothesis.readthedocs.io/en/master/quickstart.html

Footnotes


  1. Perhaps not incidentally, Hypothesis is the name of the de-facto property based testing framework for Python.

  2. It is not lost on me that automating what often ends up being the same few commands run in the repl in a test-suite would ultimately end up saving me time.

  3. Examples in this section use Haskell syntax.

  4. More on this in the section about ExCheck.

  5. By convention, QuickCheck properties begin with prop_.

  6. You’ll need a working version of Elixir to follow along. Edit: 2016-06-23 If you’d rather download the project, it’s available at https://github.com/tpoulsen/quicksort.

  7. At the time of this writing, ExCheck 0.3.0 crashes at the end of test runs in the newly released released Elixir 1.3.0. I’ve submitted a patch, but until it’s fixed upstream you can use {:excheck, github: "tpoulsen/excheck", only: :test,} instead of v0.3.0 if you’re using elixir 1.3.0. Edit: 2016-07-29 As of v0.4.0, ExCheck works with Elixir v.1.3 and up.

  8. An example of idempotency, a useful property to test when possible. An idempotent function is one which produces the same result no matter how many times it is called; f(f(x)) == f(x)

  9. https://github.com/parroty/excheck#generators