Testing Go with QuickCheck

I wrote a post a couple of months ago about implementing tries in Go. It was one of the first Go projects I worked on so one thing I struggled with was the best way to test my code. A simplified version of the tests I wrote were along the lines of:

func TestAddKeys(t *testing.T) {
  trie := NewTrie()
  keys := []string{"Hello", "World", "Help", "Hell"}

  for _, key := range keys {  
    trie.Add(key) 
  }
  
  for _, key := range keys {
    _, ok := trie.Get(key)
    if !ok {
      t.Error("Missing key:", key)
    }
  }
}

This test is really simple, but all of the real tests follow the same basic pattern: define some things to add to the trie and then check they exist.

This works fine, but it would be great if the author of the code wasn’t also responsible for defining the test cases. QuickCheck is a library written in Haskell (and ported to many more languages) that allows you to do exactly this by attempting to falsify properties you define about a function using randomly generated input values.

Go provides QuickCheck like functionality in its testing/quick package, which has two functions for validating the inputs: Check and CheckEqual.

Check takes a function, optionally a quick.Config struct, and returns an error. The function should define the types it needs to run the test as arguments and return a bool indicating the whether the test passed or failed. If any of the function calls fail Check returns an error, which can be handled in the standard way.

For example, we can rewrite the above test as follows using testing/quick:

func TestAddingKeys(t *testing.T) {
  trie := NewTrie()
  add := func(key string) (ok bool) {
    trie.Add(key)
    _, ok = trie.Get(key)
    return
  }
  
  if err := quick.Check(add, nil); err != nil {
    t.Error(err)
  }
}

The add function takes a string, which quick.Check uses to generate random test cases that fulfil that type. We then use those random strings to add keys to our trie and test that they were successfully added.

CheckEqual works in a very similar way to Check, but takes two functions. These functions should return some value and if they are not equal CheckEqual returns an error. We can use this to test adding keys with associated values to our trie:

func TestAddingValues(t *testing.T) {
  trie := NewTrie()
  set := func(key string, value string) interface{} {
    c := trie.Add(key)
    c.Value = value
    return c.Value
  }
  get := func(key string, value string) interface{} {
    c, _ := trie.Get(key)
    return c.Value
  }
  if err := quick.CheckEqual(set, get, nil); err != nil {
    t.Error(err)
  }
}

The set and get functions add and retrieve values from the trie respectively. If they return different values at any point CheckEqual will return an error and the test will fail.

The tests that I’ve described are pretty basic and it might not seem worthwhile using this approach over manually defining the test cases. However, even in this simple example the randomly generated data exposed an issue I hadn’t properly handled — setting a key using an empty string.

It’s also worth noting that this approach doesn’t help with all scenarios. One of the tests I wrote for tries was verifying a given prefix has the expected child keys — e.g. “foo” should have “food” and “foodstuff” as children. There might be a way to generate the correct data for this type of test, but in those cases I found it easier to stick to manual tests.