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 }