testing/quick: Go's little-known blackbox test harness

Go Meetup Zürich

14 October 2015

Matt T. Proud

Software Engineer, Google, Inc.

Genesis of Talk

This talk is a synthesis of an article I wrote earlier this year:

It also lives at the following location:

Dramatis Personae (1/2)

I assume you have some familiarity with testing in Go.

import "testing"

If not, you have some homework:

2.1. The Usual Suspects

Dramatis Personae (2/2)

This talk is about testing techniques you might not know about Go using only
the standard library.

import "testing/quick"

Namely the much unnoticed pkg/testing/quick.

Familiar friend if you're coming from the Haskell world: QuickCheck.

3.1. New Suspects

Pillar I: Value Generation (1/3)

Did you know that Go can generate arbitrary values?

// synthesis of src/builtin/builtin.go and src/reflect/type.go:
type (
    bool 
    int
    int8
    // …
    string
    struct
)

… of builtin types?

Pillar I: Value Generation (2/3)

… and …

package main

import (
    "fmt"
    "math/rand"
    "reflect"
    "testing/quick"
)

type Point struct{ X, Y int8 }

func main() {
    rnd := rand.New(rand.NewSource(42))
    t := reflect.TypeOf(Point{})
    v, _ := quick.Value(t, rnd)
    fmt.Println("Here's a point:", v)
}

… your own?

Pillar I: Value Generation (3/3)

The meat:

func Value(t reflect.Type, rand *rand.Rand) (value reflect.Value, ok bool)

Under-the-Hood (Bonnet)

White noise generation in the default case.

Custom strategy if your type fulfills quick.Generator:

package main

import (
	"fmt"
	"math/rand"
	"reflect"
	"testing/quick"
)

type Stooge int

const (
    Invalid Stooge = iota
    Moe
    Larry
    Shemp
    Curly
    Joe
    CurlyJoe

    nStooges = int(CurlyJoe) + 1
)

func (s Stooge) Generate(rand *rand.Rand, size int) reflect.Value {
    return reflect.ValueOf(Stooge(rand.Intn(nStooges)))
}

func (s Stooge) String() string {
	switch s {
	case Invalid:
		return "Invalid"
	case Moe:
		return "Moe"
	case Larry:
		return "Larry"
	case Shemp:
		return "Shemp"
	case Curly:
		return "Curly"
	case Joe:
		return "Joe"
	case CurlyJoe:
		return "Curly Joe"
	}
	panic("unreachable")
}

func main() {
	var (
		rnd = rand.New(rand.NewSource(42))
		t   = reflect.TypeOf(Stooge(0))
	)
	fmt.Println("Introducing the Stooges:")
	for i := 0; i < 3; i++ {
		v, _ := quick.Value(t, rnd)
		fmt.Println(v.Interface())
	}
}

Example TypeOf Literals

builtin: int

reflect.TypeOf(int(0))

builtin: *int

reflect.TypeOf((*int)(nil))

first-class type: http.Dir

reflect.TypeOf(http.Dir(""))

anonymous: struct { X, Y int }

reflect.TypeOf(struct{ X, Y int }{})

anonymous: *struct { X, Y int }

reflect.TypeOf((*struct{ X, Y int })(nil))

quick.Value Limitations

Legal

type point struct { X, Y int }

Illegal

type point struct { x, y int }

All fields (including children) must be exported identifiers.

Purely an implementation choice; nothing in the specification prohibits this.

9.1. Exported Fields

quick.Value Limitations

Appears to be artificial as opposed to substantive.

Reflection supports it: reflect.MakeChan.

10.1. Channels

quick.Value Limitations

quick.Value(reflect.TypeOf(struct{ R io.Reader }{}), rnd)

A legitimate limitation:

11.1. Interfaces

quick.Value Limitations

type Node struct {
    V int
    Next *Node
}

Probably won't fulfill your connectivity or structural requirements out of the box:

quick.Generator to the rescue!

12.1. Graph Type / Structural

quick.Value Limitations

Watch out with: unsafe.Pointer.

You have no idea what it points to, its type, whether legal, etc.

It is called "unsafe" for a reason.

13.1. Unsafe Pointers

quick.Value Limitations

All of the previous considerations apply.

Look up pbtest.SanitizeGenerated if using Protocol Buffers.

14.1. Foreign Code

Public API Design Considerations

Opt not to fulfill quick.Generator in your public types:

Moral of the story: be absolutely sure that everyone wants your implementation.

With unexported internals, go right ahead!

Pillar II: Fuzz Testing

Everything in Value Generation leads up to this.

The art of enforcing the invariant.

Defining an Invariant

"A condition that can be relied upon to be true during execution of a program or some portion of it." — Wikipedia

Take the commutative property of addition:

a + b == b + a

Could we test this in Go? Yes, with quick.CheckEqual!

package main

import (
	"fmt"
	"testing/quick"
)

func main() {
    f := func(a, b int) int { return a + b }
    g := func(a, b int) int { return b + a }
    fmt.Println("Counter examples against commutativity:", quick.CheckEqual(f, g, nil))
}

Counter Examples

Division is commutative—right?

a / b == b / a
package main

import (
	"fmt"
	"testing/quick"
)

func main() {
    f := func(a, b int) int { return a / b }
    g := func(a, b int) int { return b / a }
    fmt.Println("Counter examples against commutativity:", quick.CheckEqual(f, g, nil))
}

Equality Testing with quick.CheckEqual (1/4)

Let's dissect this:

func CheckEqual(f, g interface{}, config *Config) (err error)

Using reflection on f and g, we attempt to find a counter example against …

∀(x0, x1, … xn) f(x0, x1, … xn) == g(x0, x1, … xn)

Expects symmetry between f and g's signatures: arguments and return values.

Arguments must be generatable by quick.Value.

19.1. The Principles

Equality Testing with quick.CheckEqual (2/4)

package main

import (
	"fmt"
	"sort"
	"testing/quick"
)

func SliceCopy(data sort.IntSlice) sort.IntSlice {
	d := make(sort.IntSlice, len(data))
	copy(d, data)
	return d
}
func main() {
    BubbleSort := func(data sort.Interface) {
        for {
            var swapped bool
            for i := 1; i < data.Len(); i++ {
                if data.Less(i, i-1) {
                    data.Swap(i-1, i)
                    swapped = true
                }
            }
            if !swapped {
                break
            }
        }
    }
    f := func(data sort.IntSlice) sort.IntSlice { d := SliceCopy(data); sort.Sort(d); return d }
    g := func(data sort.IntSlice) sort.IntSlice { d := SliceCopy(data); BubbleSort(d); return d }
    fmt.Println("Counter examples against sort:", quick.CheckEqual(f, g, nil))
}

20.1. An Example: Whiz-Bang Sorting!

Equality Testing with quick.CheckEqual (3/4)

The simplest case of invariant testing.

Most useful when comparing a known-good reference implementation against a proposed experimental one.

21.1. Applicability

Equality Testing with quick.CheckEqual (4/4)

Powered by reflect.DeepEqual, which means …

[]T(nil) != []T{}

map[T]T(nil) != make(map[T]T)

… are tripping points.

Arguments to f and g are passed as the same value, so mutations in f or g to …

x0, x1, xn

… are propagated from one to the other.

22.1. Caveats

Invariant Testing with quick.Check (1/5)

Bring out the big guns with quick.Check:

func Check(f interface{}, config *Config) (err error)

Similar story to quick.CheckEqual, except that f must conform to this signature …

func f(x0, x1, … xn) (ok bool)

… where ok indicates whether the invariants were upheld.

Arguments are value generated just like before.

23.1. Swiss Army Knife of Fuzz Checkers

Invariant Testing with quick.Check (2/5)

func TestFoo(t *testing.T) {
    satisfies := func(/* arguments */) bool {
        // Setup Test Context
        // Exercise System under Test using Context and Arguments
        // Validate Invariants
        return invariantsSatisfied
    }
    if err := quick.Check(satisifies, nil); err != nil {
        t.Error(err)
    }
}

24.1. The Pattern

Invariant Testing with quick.Check (3/5)

25.1. Applicability

Invariant Testing with quick.Check (4/5)

Let's turn our attention to a non-deterministic system: a skip list.

package main

import (
	"fmt"
	"log"
	"sort"
	"testing/quick"

	"github.com/ryszard/goskiplist/skiplist"
)

func skipListTest(in []int) bool {
	// Arrange
	var (
		found     int
		no        = len(in)
		reference = make([]int, no)
		skiplist  = skiplist.NewIntSet()
	)
	copy(reference, in)
	sort.Ints(reference)

	// Act
	for _, v := range in {
		skiplist.Add(v)
	}

	// Assert
	for it := skiplist.Iterator(); it.Next(); {
		got := it.Key().(int)
		// first invariant
		if found > no {
			log.Print("skiplist contains more items than were given as input")
			return false
		}
		// second invariant
		if want := reference[found]; got != want {
			log.Printf("skiplist at %d got %d, want %d", found, got, want)
			return false
		}
		found++
	}
	// third invariant
	if found < no {
		log.Printf("skiplist had insufficient elements: got %d, want %d", found, no)
		return false
	}

	return true
}

func main() {
    err := quick.Check(skipListTest, nil /* configuration */)
    fmt.Printf("Skip list invariant counter examples: %v", err)
}

Explore this Example's Source

26.1. Example

Invariant Testing with quick.Check (5/5)

You will likely use this within the confines of …

func TestFoo(t *testing.T) {}

…, so include the *testing.T in the test's closure, so you can call …

t.Error(args ...interface{})
t.Errorf(format string, args ...interface{})

… to provide useful context about why the input was invalid and which invariant was broken.

27.1. Good Practices

Similar Efforts (1/2)

Dmitry Vyukov has authored the brilliant go-fuzz tool.

It is handy. Found many bugs in Go and external libraries.

pkg/testing/quick predates it and debuted in Go 1.0.

When to use which?

28.1. Focused Fuzzing

Similar Efforts (2/2)

Using quick.Check to drive monkey test of system under test' state transitions.

This is subject of an in-progress article that I hope to publish by EoY.

29.1. Stochastic Monkey Testing

Takeaways

Do not abuse and overuse pkg/testing/quick; it should augment pre-existing conventions:

It shines when invariants can be easily computed for combinatorily large inputs.

Further: I completely ignored the topic of configuration. Read up on this if you are going to use the package.

Future Opportunities for testing/quick

There is room for improvement:

Thank you

Matt T. Proud

Software Engineer, Google, Inc.

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)