proposal: add Shrinker interface to testing/quick

[spacejam]

The ability to simplify failing test cases that are automatically generated by testing/quick has the potential to enhance its usefulness. Often, automatically generated test cases take a long time to debug, as they may be quite complex.

Consider a slice of automatically generated events of length 50. There exists some subsequence that triggers a defect. Without reducing this slice to something more manageable, it may be cumbersome for the user of testing/quick to debug the issue.

My more lengthy comments describing the usefulness of this type of behavior: #9282 (comment)

It is common for quickcheck-style testing libraries to support "shrinking" where a failing testcase may be automatically simplified before being surfaced to the user. It is possible to support this with the addition of a simple interface:

// A Shrinker can produce simplified values of its own type.
type Shrinker interface {                                           
    // Shrink returns a slice of simplified instances of this value.
    Shrink() []reflect.Value
} 

When running Check and CheckEqual, when a failing input is discovered, the library may attempt to use the rest of our configured MaxCount cycles trying to Shrink the arguments, for each argument that implements the Shrinker interface. It is possible to mix Shrinker and non-Shrinker arguments, and the library should attempt to Shrink every argument that implements Shrinker, up until the configured MaxCount has been exhausted, even when different arguments require different numbers of iterations to reach a local minima.

The following property fails when any argument of type events contains 3.

type events []int

func doesntContain3(i1, i2, i3 events) bool {
	for _, input := range []events{i1, i2, i3} {
		for _, event := range input {
			if event == 3 {
				return false
			}
		}
	}
	return true
}

The shrinker, which could be made to work as a fallback "default" Shrinker for any slice argument, returns a slice of events with individual elements dropped out:

func (e events) Shrink() (ret []reflect.Value) {
	if len(e) < 2 {
		return
	}
	for i := range e {
		var evs events
		for j := range e {
			if i == j {
				// drop out individual elements
				continue
			}
			evs = append(evs, e[j])
		}
		ret = append(ret, reflect.ValueOf(evs))
	}
	return
}

Let's give it some inputs that we expect it to fail:

var nGenerated = 0
var genCases = []events{
	[]int{0, 0, 3},
	[]int{0, 3, 0},
	[]int{3, 0, 0},
}

func (e events) Generate(r *rand.Rand, _ int) reflect.Value {
	v := genCases[nGenerated%len(genCases)]
	nGenerated += 1
	return reflect.ValueOf(v)
}

When running with the Shrinker interface implemented for events, testing/quick will now simplify each argument passed in before presenting the failure to the user for debugging:

quick_test.go:375: #3: failed on input quick.events{3}, quick.events{0}, quick.events{0}

And when commenting out Shrinker, the pre-Shrinker behavior persists:

quick_test.go:377: #1: failed on input quick.events{0, 0, 3}, quick.events{0, 3, 0}, quick.events{3, 0, 0}

There are several different search strategies that may be employed. Because we have a finite number of iterations to work with, it may be a good idea to try shrinking several arguments simultaneously, and then then become more fine-grained after we overshoot our simplified target. This can be made to be fairly complex, which is at-odds with the current testing/quick implementation, so there is a trade-off to be made between code simplicity and search thoroughness.

Some quickcheck implementations allow the configuration of a second iteration budget to consume while searching for a simplified failing set of arguments, which allows users to generally have a shorter test latency when failures are not detected, but the library is able to spend a bit more time trying to simplify arguments when a failure is detected, to make debugging simpler. I am in favor of adding a field to Config in testing/quick for this purpose, perhaps called MaxShrinkCount, and when left unset simply consuming iterations from MaxCount.

If this new Shrinker interface is not desirable, I would argue that the above shrinking behavior would still be quite useful to apply to failing slice arguments by default for simplifying the information presented to the user, easing the debugging process.

[tj]

The testing/quick package is frozen and is not accepting new features.

I think that part is relevant :D (https://golang.org/pkg/testing/quick/). I didn't even know testing/quick existed. I love the assertion style personally but the name is a bit clunky anyway.

[spacejam]

You may not have heard about it because it's often considered incomplete by people familiar with property testing libraries. The current implementation is good at testing things like codecs, but it breaks down when testing things like user interfaces, distributed systems, services, or generally anything that is nice to test by generating a sequence of events/requests/interactions/partitions to find defects. Shrinking is the missing piece to get there.

P.S. @tj in the off-chance you're jumping in to throw sand on work that may benefit a particular competitor, I'm not currently engaged with them.

[tj]

I'm not sure what you mean by that. I just saw this proposal in my GH feed, checked out what "quick" was and saw that it's deprecated, just wanted to mention that.

[spacejam]

testing/quick was frozen to prevent test breakage, as I understand it. I believe the addition of this interface dramatically improves the viability of this library, without causing any breakage. When we can generate and shrink sequences of events/interactions/requests/partitions, it becomes far easier to test complex high-level interactions in systems that engineers are often unequipped to build in a low-defect manner. Given Go's usage for infrastructure and services, which engineers are generally unable to test thoroughly on their laptops, I believe this could be awesome for the ecosystem.

[dominikh]

testing/quick was frozen as part of #15557, with the intention of not developing it further. Quoting @bradfitz: "testing/quick can be forked and develop elsewhere on Github, perhaps with versioning."

These, and other, packages aren't frozen to prevent "test breakage", but because it has been decided that they shouldn't be developed further as part of the standard library.

In the case of testing/quick, several people have worked on far more powerful 3rd party solutions that are worth using.

[rsc]

I'd be happy to see this in third-party copies of testing/quick. If one takes off, we can look at adding it then.

[josharian]

fyi @arschles and @benbjohnson