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