1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package quick implements utility functions to help with black box testing.
6//
7// The testing/quick package is frozen and is not accepting new features.
8package quick
9
10import (
11	"flag"
12	"fmt"
13	"math"
14	"math/rand"
15	"reflect"
16	"strings"
17	"time"
18)
19
20var defaultMaxCount *int = flag.Int("quickchecks", 100, "The default number of iterations for each check")
21
22// A Generator can generate random values of its own type.
23type Generator interface {
24	// Generate returns a random instance of the type on which it is a
25	// method using the size as a size hint.
26	Generate(rand *rand.Rand, size int) reflect.Value
27}
28
29// randFloat32 generates a random float taking the full range of a float32.
30func randFloat32(rand *rand.Rand) float32 {
31	f := rand.Float64() * math.MaxFloat32
32	if rand.Int()&1 == 1 {
33		f = -f
34	}
35	return float32(f)
36}
37
38// randFloat64 generates a random float taking the full range of a float64.
39func randFloat64(rand *rand.Rand) float64 {
40	f := rand.Float64() * math.MaxFloat64
41	if rand.Int()&1 == 1 {
42		f = -f
43	}
44	return f
45}
46
47// randInt64 returns a random int64.
48func randInt64(rand *rand.Rand) int64 {
49	return int64(rand.Uint64())
50}
51
52// complexSize is the maximum length of arbitrary values that contain other
53// values.
54const complexSize = 50
55
56// Value returns an arbitrary value of the given type.
57// If the type implements the Generator interface, that will be used.
58// Note: To create arbitrary values for structs, all the fields must be exported.
59func Value(t reflect.Type, rand *rand.Rand) (value reflect.Value, ok bool) {
60	return sizedValue(t, rand, complexSize)
61}
62
63// sizedValue returns an arbitrary value of the given type. The size
64// hint is used for shrinking as a function of indirection level so
65// that recursive data structures will terminate.
66func sizedValue(t reflect.Type, rand *rand.Rand, size int) (value reflect.Value, ok bool) {
67	if m, ok := reflect.Zero(t).Interface().(Generator); ok {
68		return m.Generate(rand, size), true
69	}
70
71	v := reflect.New(t).Elem()
72	switch concrete := t; concrete.Kind() {
73	case reflect.Bool:
74		v.SetBool(rand.Int()&1 == 0)
75	case reflect.Float32:
76		v.SetFloat(float64(randFloat32(rand)))
77	case reflect.Float64:
78		v.SetFloat(randFloat64(rand))
79	case reflect.Complex64:
80		v.SetComplex(complex(float64(randFloat32(rand)), float64(randFloat32(rand))))
81	case reflect.Complex128:
82		v.SetComplex(complex(randFloat64(rand), randFloat64(rand)))
83	case reflect.Int16:
84		v.SetInt(randInt64(rand))
85	case reflect.Int32:
86		v.SetInt(randInt64(rand))
87	case reflect.Int64:
88		v.SetInt(randInt64(rand))
89	case reflect.Int8:
90		v.SetInt(randInt64(rand))
91	case reflect.Int:
92		v.SetInt(randInt64(rand))
93	case reflect.Uint16:
94		v.SetUint(uint64(randInt64(rand)))
95	case reflect.Uint32:
96		v.SetUint(uint64(randInt64(rand)))
97	case reflect.Uint64:
98		v.SetUint(uint64(randInt64(rand)))
99	case reflect.Uint8:
100		v.SetUint(uint64(randInt64(rand)))
101	case reflect.Uint:
102		v.SetUint(uint64(randInt64(rand)))
103	case reflect.Uintptr:
104		v.SetUint(uint64(randInt64(rand)))
105	case reflect.Map:
106		numElems := rand.Intn(size)
107		v.Set(reflect.MakeMap(concrete))
108		for i := 0; i < numElems; i++ {
109			key, ok1 := sizedValue(concrete.Key(), rand, size)
110			value, ok2 := sizedValue(concrete.Elem(), rand, size)
111			if !ok1 || !ok2 {
112				return reflect.Value{}, false
113			}
114			v.SetMapIndex(key, value)
115		}
116	case reflect.Ptr:
117		if rand.Intn(size) == 0 {
118			v.Set(reflect.Zero(concrete)) // Generate nil pointer.
119		} else {
120			elem, ok := sizedValue(concrete.Elem(), rand, size)
121			if !ok {
122				return reflect.Value{}, false
123			}
124			v.Set(reflect.New(concrete.Elem()))
125			v.Elem().Set(elem)
126		}
127	case reflect.Slice:
128		numElems := rand.Intn(size)
129		sizeLeft := size - numElems
130		v.Set(reflect.MakeSlice(concrete, numElems, numElems))
131		for i := 0; i < numElems; i++ {
132			elem, ok := sizedValue(concrete.Elem(), rand, sizeLeft)
133			if !ok {
134				return reflect.Value{}, false
135			}
136			v.Index(i).Set(elem)
137		}
138	case reflect.Array:
139		for i := 0; i < v.Len(); i++ {
140			elem, ok := sizedValue(concrete.Elem(), rand, size)
141			if !ok {
142				return reflect.Value{}, false
143			}
144			v.Index(i).Set(elem)
145		}
146	case reflect.String:
147		numChars := rand.Intn(complexSize)
148		codePoints := make([]rune, numChars)
149		for i := 0; i < numChars; i++ {
150			codePoints[i] = rune(rand.Intn(0x10ffff))
151		}
152		v.SetString(string(codePoints))
153	case reflect.Struct:
154		n := v.NumField()
155		// Divide sizeLeft evenly among the struct fields.
156		sizeLeft := size
157		if n > sizeLeft {
158			sizeLeft = 1
159		} else if n > 0 {
160			sizeLeft /= n
161		}
162		for i := 0; i < n; i++ {
163			elem, ok := sizedValue(concrete.Field(i).Type, rand, sizeLeft)
164			if !ok {
165				return reflect.Value{}, false
166			}
167			v.Field(i).Set(elem)
168		}
169	default:
170		return reflect.Value{}, false
171	}
172
173	return v, true
174}
175
176// A Config structure contains options for running a test.
177type Config struct {
178	// MaxCount sets the maximum number of iterations.
179	// If zero, MaxCountScale is used.
180	MaxCount int
181	// MaxCountScale is a non-negative scale factor applied to the
182	// default maximum.
183	// A count of zero implies the default, which is usually 100
184	// but can be set by the -quickchecks flag.
185	MaxCountScale float64
186	// Rand specifies a source of random numbers.
187	// If nil, a default pseudo-random source will be used.
188	Rand *rand.Rand
189	// Values specifies a function to generate a slice of
190	// arbitrary reflect.Values that are congruent with the
191	// arguments to the function being tested.
192	// If nil, the top-level Value function is used to generate them.
193	Values func([]reflect.Value, *rand.Rand)
194}
195
196var defaultConfig Config
197
198// getRand returns the *rand.Rand to use for a given Config.
199func (c *Config) getRand() *rand.Rand {
200	if c.Rand == nil {
201		return rand.New(rand.NewSource(time.Now().UnixNano()))
202	}
203	return c.Rand
204}
205
206// getMaxCount returns the maximum number of iterations to run for a given
207// Config.
208func (c *Config) getMaxCount() (maxCount int) {
209	maxCount = c.MaxCount
210	if maxCount == 0 {
211		if c.MaxCountScale != 0 {
212			maxCount = int(c.MaxCountScale * float64(*defaultMaxCount))
213		} else {
214			maxCount = *defaultMaxCount
215		}
216	}
217
218	return
219}
220
221// A SetupError is the result of an error in the way that check is being
222// used, independent of the functions being tested.
223type SetupError string
224
225func (s SetupError) Error() string { return string(s) }
226
227// A CheckError is the result of Check finding an error.
228type CheckError struct {
229	Count int
230	In    []interface{}
231}
232
233func (s *CheckError) Error() string {
234	return fmt.Sprintf("#%d: failed on input %s", s.Count, toString(s.In))
235}
236
237// A CheckEqualError is the result CheckEqual finding an error.
238type CheckEqualError struct {
239	CheckError
240	Out1 []interface{}
241	Out2 []interface{}
242}
243
244func (s *CheckEqualError) Error() string {
245	return fmt.Sprintf("#%d: failed on input %s. Output 1: %s. Output 2: %s", s.Count, toString(s.In), toString(s.Out1), toString(s.Out2))
246}
247
248// Check looks for an input to f, any function that returns bool,
249// such that f returns false. It calls f repeatedly, with arbitrary
250// values for each argument. If f returns false on a given input,
251// Check returns that input as a *CheckError.
252// For example:
253//
254// 	func TestOddMultipleOfThree(t *testing.T) {
255// 		f := func(x int) bool {
256// 			y := OddMultipleOfThree(x)
257// 			return y%2 == 1 && y%3 == 0
258// 		}
259// 		if err := quick.Check(f, nil); err != nil {
260// 			t.Error(err)
261// 		}
262// 	}
263func Check(f interface{}, config *Config) error {
264	if config == nil {
265		config = &defaultConfig
266	}
267
268	fVal, fType, ok := functionAndType(f)
269	if !ok {
270		return SetupError("argument is not a function")
271	}
272
273	if fType.NumOut() != 1 {
274		return SetupError("function does not return one value")
275	}
276	if fType.Out(0).Kind() != reflect.Bool {
277		return SetupError("function does not return a bool")
278	}
279
280	arguments := make([]reflect.Value, fType.NumIn())
281	rand := config.getRand()
282	maxCount := config.getMaxCount()
283
284	for i := 0; i < maxCount; i++ {
285		err := arbitraryValues(arguments, fType, config, rand)
286		if err != nil {
287			return err
288		}
289
290		if !fVal.Call(arguments)[0].Bool() {
291			return &CheckError{i + 1, toInterfaces(arguments)}
292		}
293	}
294
295	return nil
296}
297
298// CheckEqual looks for an input on which f and g return different results.
299// It calls f and g repeatedly with arbitrary values for each argument.
300// If f and g return different answers, CheckEqual returns a *CheckEqualError
301// describing the input and the outputs.
302func CheckEqual(f, g interface{}, config *Config) error {
303	if config == nil {
304		config = &defaultConfig
305	}
306
307	x, xType, ok := functionAndType(f)
308	if !ok {
309		return SetupError("f is not a function")
310	}
311	y, yType, ok := functionAndType(g)
312	if !ok {
313		return SetupError("g is not a function")
314	}
315
316	if xType != yType {
317		return SetupError("functions have different types")
318	}
319
320	arguments := make([]reflect.Value, xType.NumIn())
321	rand := config.getRand()
322	maxCount := config.getMaxCount()
323
324	for i := 0; i < maxCount; i++ {
325		err := arbitraryValues(arguments, xType, config, rand)
326		if err != nil {
327			return err
328		}
329
330		xOut := toInterfaces(x.Call(arguments))
331		yOut := toInterfaces(y.Call(arguments))
332
333		if !reflect.DeepEqual(xOut, yOut) {
334			return &CheckEqualError{CheckError{i + 1, toInterfaces(arguments)}, xOut, yOut}
335		}
336	}
337
338	return nil
339}
340
341// arbitraryValues writes Values to args such that args contains Values
342// suitable for calling f.
343func arbitraryValues(args []reflect.Value, f reflect.Type, config *Config, rand *rand.Rand) (err error) {
344	if config.Values != nil {
345		config.Values(args, rand)
346		return
347	}
348
349	for j := 0; j < len(args); j++ {
350		var ok bool
351		args[j], ok = Value(f.In(j), rand)
352		if !ok {
353			err = SetupError(fmt.Sprintf("cannot create arbitrary value of type %s for argument %d", f.In(j), j))
354			return
355		}
356	}
357
358	return
359}
360
361func functionAndType(f interface{}) (v reflect.Value, t reflect.Type, ok bool) {
362	v = reflect.ValueOf(f)
363	ok = v.Kind() == reflect.Func
364	if !ok {
365		return
366	}
367	t = v.Type()
368	return
369}
370
371func toInterfaces(values []reflect.Value) []interface{} {
372	ret := make([]interface{}, len(values))
373	for i, v := range values {
374		ret[i] = v.Interface()
375	}
376	return ret
377}
378
379func toString(interfaces []interface{}) string {
380	s := make([]string, len(interfaces))
381	for i, v := range interfaces {
382		s[i] = fmt.Sprintf("%#v", v)
383	}
384	return strings.Join(s, ", ")
385}
386