libgo/go/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 //
   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.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.
 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         // If zero, the default is unchanged.
 184         MaxCountScale float64
 185         // Rand specifies a source of random numbers.
 186         // If nil, a default pseudo-random source will be used.
 187         Rand *rand.Rand
 188         // Values specifies a function to generate a slice of
 189         // arbitrary reflect.Values that are congruent with the
 190         // arguments to the function being tested.
 191         // If nil, the top-level Value function is used to generate them.
 192         Values func([]reflect.Value, *rand.Rand)
 193 }
 194
 195 var defaultConfig Config
 196
 197 // getRand returns the *rand.Rand to use for a given Config.
 198 func (c *Config) getRand() *rand.Rand {
 199         if c.Rand == nil {
 200                 return rand.New(rand.NewSource(time.Now().UnixNano()))
 201         }
 202         return c.Rand
 203 }
 204
 205 // getMaxCount returns the maximum number of iterations to run for a given
 206 // Config.
 207 func (c *Config) getMaxCount() (maxCount int) {
 208         maxCount = c.MaxCount
 209         if maxCount == 0 {
 210                 if c.MaxCountScale != 0 {
 211                         maxCount = int(c.MaxCountScale * float64(*defaultMaxCount))
 212                 } else {
 213                         maxCount = *defaultMaxCount
 214                 }
 215         }
 216
 217         return
 218 }
 219
 220 // A SetupError is the result of an error in the way that check is being
 221 // used, independent of the functions being tested.
 222 type SetupError string
 223
 224 func (s SetupError) Error() string { return string(s) }
 225
 226 // A CheckError is the result of Check finding an error.
 227 type CheckError struct {
 228         Count int
 229         In    []interface{}
 230 }
 231
 232 func (s *CheckError) Error() string {
 233         return fmt.Sprintf("#%d: failed on input %s", s.Count, toString(s.In))
 234 }
 235
 236 // A CheckEqualError is the result CheckEqual finding an error.
 237 type CheckEqualError struct {
 238         CheckError
 239         Out1 []interface{}
 240         Out2 []interface{}
 241 }
 242
 243 func (s *CheckEqualError) Error() string {
 244         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))
 245 }
 246
 247 // Check looks for an input to f, any function that returns bool,
 248 // such that f returns false. It calls f repeatedly, with arbitrary
 249 // values for each argument. If f returns false on a given input,
 250 // Check returns that input as a *CheckError.
 251 // For example:
 252 //
 253 //      func TestOddMultipleOfThree(t *testing.T) {
 254 //              f := func(x int) bool {
 255 //                      y := OddMultipleOfThree(x)
 256 //                      return y%2 == 1 && y%3 == 0
 257 //              }
 258 //              if err := quick.Check(f, nil); err != nil {
 259 //                      t.Error(err)
 260 //              }
 261 //      }
 262 func Check(f interface{}, config *Config) error {
 263         if config == nil {
 264                 config = &defaultConfig
 265         }
 266
 267         fVal, fType, ok := functionAndType(f)
 268         if !ok {
 269                 return SetupError("argument is not a function")
 270         }
 271
 272         if fType.NumOut() != 1 {
 273                 return SetupError("function does not return one value")
 274         }
 275         if fType.Out(0).Kind() != reflect.Bool {
 276                 return SetupError("function does not return a bool")
 277         }
 278
 279         arguments := make([]reflect.Value, fType.NumIn())
 280         rand := config.getRand()
 281         maxCount := config.getMaxCount()
 282
 283         for i := 0; i < maxCount; i++ {
 284                 err := arbitraryValues(arguments, fType, config, rand)
 285                 if err != nil {
 286                         return err
 287                 }
 288
 289                 if !fVal.Call(arguments)[0].Bool() {
 290                         return &CheckError{i + 1, toInterfaces(arguments)}
 291                 }
 292         }
 293
 294         return nil
 295 }
 296
 297 // CheckEqual looks for an input on which f and g return different results.
 298 // It calls f and g repeatedly with arbitrary values for each argument.
 299 // If f and g return different answers, CheckEqual returns a *CheckEqualError
 300 // describing the input and the outputs.
 301 func CheckEqual(f, g interface{}, config *Config) error {
 302         if config == nil {
 303                 config = &defaultConfig
 304         }
 305
 306         x, xType, ok := functionAndType(f)
 307         if !ok {
 308                 return SetupError("f is not a function")
 309         }
 310         y, yType, ok := functionAndType(g)
 311         if !ok {
 312                 return SetupError("g is not a function")
 313         }
 314
 315         if xType != yType {
 316                 return SetupError("functions have different types")
 317         }
 318
 319         arguments := make([]reflect.Value, xType.NumIn())
 320         rand := config.getRand()
 321         maxCount := config.getMaxCount()
 322
 323         for i := 0; i < maxCount; i++ {
 324                 err := arbitraryValues(arguments, xType, config, rand)
 325                 if err != nil {
 326                         return err
 327                 }
 328
 329                 xOut := toInterfaces(x.Call(arguments))
 330                 yOut := toInterfaces(y.Call(arguments))
 331
 332                 if !reflect.DeepEqual(xOut, yOut) {
 333                         return &CheckEqualError{CheckError{i + 1, toInterfaces(arguments)}, xOut, yOut}
 334                 }
 335         }
 336
 337         return nil
 338 }
 339
 340 // arbitraryValues writes Values to args such that args contains Values
 341 // suitable for calling f.
 342 func arbitraryValues(args []reflect.Value, f reflect.Type, config *Config, rand *rand.Rand) (err error) {
 343         if config.Values != nil {
 344                 config.Values(args, rand)
 345                 return
 346         }
 347
 348         for j := 0; j < len(args); j++ {
 349                 var ok bool
 350                 args[j], ok = Value(f.In(j), rand)
 351                 if !ok {
 352                         err = SetupError(fmt.Sprintf("cannot create arbitrary value of type %s for argument %d", f.In(j), j))
 353                         return
 354                 }
 355         }
 356
 357         return
 358 }
 359
 360 func functionAndType(f interface{}) (v reflect.Value, t reflect.Type, ok bool) {
 361         v = reflect.ValueOf(f)
 362         ok = v.Kind() == reflect.Func
 363         if !ok {
 364                 return
 365         }
 366         t = v.Type()
 367         return
 368 }
 369
 370 func toInterfaces(values []reflect.Value) []interface{} {
 371         ret := make([]interface{}, len(values))
 372         for i, v := range values {
 373                 ret[i] = v.Interface()
 374         }
 375         return ret
 376 }
 377
 378 func toString(interfaces []interface{}) string {
 379         s := make([]string, len(interfaces))
 380         for i, v := range interfaces {
 381                 s[i] = fmt.Sprintf("%#v", v)
 382         }
 383         return strings.Join(s, ", ")
 384 }