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  //
     7  // The testing/quick package is frozen and is not accepting new features.
     8  package quick
     9  
    10  import (
    11  	"flag"
    12  	"fmt"
    13  	"math"
    14  	"math/rand"
    15  	"reflect"
    16  	"strings"
    17  	"time"
    18  )
    19  
    20  var 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.
    23  type 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.
    30  func 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.
    39  func 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.
    48  func 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.
    54  const 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.
    59  func 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.
    66  func 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.Pointer:
   117  		if rand.Intn(size) == 0 {
   118  			v.SetZero() // 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.
   177  type 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  
   196  var defaultConfig Config
   197  
   198  // getRand returns the *rand.Rand to use for a given Config.
   199  func (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.
   208  func (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.
   223  type SetupError string
   224  
   225  func (s SetupError) Error() string { return string(s) }
   226  
   227  // A CheckError is the result of Check finding an error.
   228  type CheckError struct {
   229  	Count int
   230  	In    []any
   231  }
   232  
   233  func (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.
   238  type CheckEqualError struct {
   239  	CheckError
   240  	Out1 []any
   241  	Out2 []any
   242  }
   243  
   244  func (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  //	}
   263  func Check(f any, 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.
   302  func CheckEqual(f, g any, 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.
   343  func 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  
   361  func functionAndType(f any) (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  
   371  func toInterfaces(values []reflect.Value) []any {
   372  	ret := make([]any, len(values))
   373  	for i, v := range values {
   374  		ret[i] = v.Interface()
   375  	}
   376  	return ret
   377  }
   378  
   379  func toString(interfaces []any) 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
View as plain text