Source file src/pkg/testing/quick/quick.go

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