cmd/bpa-operator/vendor/github.com/google/gofuzz/fuzz.go

   1 /*
   2 Copyright 2014 Google Inc. All rights reserved.
   3
   4 Licensed under the Apache License, Version 2.0 (the "License");
   5 you may not use this file except in compliance with the License.
   6 You may obtain a copy of the License at
   7
   8     http://www.apache.org/licenses/LICENSE-2.0
   9
  10 Unless required by applicable law or agreed to in writing, software
  11 distributed under the License is distributed on an "AS IS" BASIS,
  12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 See the License for the specific language governing permissions and
  14 limitations under the License.
  15 */
  16
  17 package fuzz
  18
  19 import (
  20         "fmt"
  21         "math/rand"
  22         "reflect"
  23         "time"
  24 )
  25
  26 // fuzzFuncMap is a map from a type to a fuzzFunc that handles that type.
  27 type fuzzFuncMap map[reflect.Type]reflect.Value
  28
  29 // Fuzzer knows how to fill any object with random fields.
  30 type Fuzzer struct {
  31         fuzzFuncs        fuzzFuncMap
  32         defaultFuzzFuncs fuzzFuncMap
  33         r                *rand.Rand
  34         nilChance        float64
  35         minElements      int
  36         maxElements      int
  37         maxDepth         int
  38 }
  39
  40 // New returns a new Fuzzer. Customize your Fuzzer further by calling Funcs,
  41 // RandSource, NilChance, or NumElements in any order.
  42 func New() *Fuzzer {
  43         return NewWithSeed(time.Now().UnixNano())
  44 }
  45
  46 func NewWithSeed(seed int64) *Fuzzer {
  47         f := &Fuzzer{
  48                 defaultFuzzFuncs: fuzzFuncMap{
  49                         reflect.TypeOf(&time.Time{}): reflect.ValueOf(fuzzTime),
  50                 },
  51
  52                 fuzzFuncs:   fuzzFuncMap{},
  53                 r:           rand.New(rand.NewSource(seed)),
  54                 nilChance:   .2,
  55                 minElements: 1,
  56                 maxElements: 10,
  57                 maxDepth:    100,
  58         }
  59         return f
  60 }
  61
  62 // Funcs adds each entry in fuzzFuncs as a custom fuzzing function.
  63 //
  64 // Each entry in fuzzFuncs must be a function taking two parameters.
  65 // The first parameter must be a pointer or map. It is the variable that
  66 // function will fill with random data. The second parameter must be a
  67 // fuzz.Continue, which will provide a source of randomness and a way
  68 // to automatically continue fuzzing smaller pieces of the first parameter.
  69 //
  70 // These functions are called sensibly, e.g., if you wanted custom string
  71 // fuzzing, the function `func(s *string, c fuzz.Continue)` would get
  72 // called and passed the address of strings. Maps and pointers will always
  73 // be made/new'd for you, ignoring the NilChange option. For slices, it
  74 // doesn't make much sense to  pre-create them--Fuzzer doesn't know how
  75 // long you want your slice--so take a pointer to a slice, and make it
  76 // yourself. (If you don't want your map/pointer type pre-made, take a
  77 // pointer to it, and make it yourself.) See the examples for a range of
  78 // custom functions.
  79 func (f *Fuzzer) Funcs(fuzzFuncs ...interface{}) *Fuzzer {
  80         for i := range fuzzFuncs {
  81                 v := reflect.ValueOf(fuzzFuncs[i])
  82                 if v.Kind() != reflect.Func {
  83                         panic("Need only funcs!")
  84                 }
  85                 t := v.Type()
  86                 if t.NumIn() != 2 || t.NumOut() != 0 {
  87                         panic("Need 2 in and 0 out params!")
  88                 }
  89                 argT := t.In(0)
  90                 switch argT.Kind() {
  91                 case reflect.Ptr, reflect.Map:
  92                 default:
  93                         panic("fuzzFunc must take pointer or map type")
  94                 }
  95                 if t.In(1) != reflect.TypeOf(Continue{}) {
  96                         panic("fuzzFunc's second parameter must be type fuzz.Continue")
  97                 }
  98                 f.fuzzFuncs[argT] = v
  99         }
 100         return f
 101 }
 102
 103 // RandSource causes f to get values from the given source of randomness.
 104 // Use if you want deterministic fuzzing.
 105 func (f *Fuzzer) RandSource(s rand.Source) *Fuzzer {
 106         f.r = rand.New(s)
 107         return f
 108 }
 109
 110 // NilChance sets the probability of creating a nil pointer, map, or slice to
 111 // 'p'. 'p' should be between 0 (no nils) and 1 (all nils), inclusive.
 112 func (f *Fuzzer) NilChance(p float64) *Fuzzer {
 113         if p < 0 || p > 1 {
 114                 panic("p should be between 0 and 1, inclusive.")
 115         }
 116         f.nilChance = p
 117         return f
 118 }
 119
 120 // NumElements sets the minimum and maximum number of elements that will be
 121 // added to a non-nil map or slice.
 122 func (f *Fuzzer) NumElements(atLeast, atMost int) *Fuzzer {
 123         if atLeast > atMost {
 124                 panic("atLeast must be <= atMost")
 125         }
 126         if atLeast < 0 {
 127                 panic("atLeast must be >= 0")
 128         }
 129         f.minElements = atLeast
 130         f.maxElements = atMost
 131         return f
 132 }
 133
 134 func (f *Fuzzer) genElementCount() int {
 135         if f.minElements == f.maxElements {
 136                 return f.minElements
 137         }
 138         return f.minElements + f.r.Intn(f.maxElements-f.minElements+1)
 139 }
 140
 141 func (f *Fuzzer) genShouldFill() bool {
 142         return f.r.Float64() > f.nilChance
 143 }
 144
 145 // MaxDepth sets the maximum number of recursive fuzz calls that will be made
 146 // before stopping.  This includes struct members, pointers, and map and slice
 147 // elements.
 148 func (f *Fuzzer) MaxDepth(d int) *Fuzzer {
 149         f.maxDepth = d
 150         return f
 151 }
 152
 153 // Fuzz recursively fills all of obj's fields with something random.  First
 154 // this tries to find a custom fuzz function (see Funcs).  If there is no
 155 // custom function this tests whether the object implements fuzz.Interface and,
 156 // if so, calls Fuzz on it to fuzz itself.  If that fails, this will see if
 157 // there is a default fuzz function provided by this package.  If all of that
 158 // fails, this will generate random values for all primitive fields and then
 159 // recurse for all non-primitives.
 160 //
 161 // This is safe for cyclic or tree-like structs, up to a limit.  Use the
 162 // MaxDepth method to adjust how deep you need it to recurse.
 163 //
 164 // obj must be a pointer. Only exported (public) fields can be set (thanks,
 165 // golang :/ ) Intended for tests, so will panic on bad input or unimplemented
 166 // fields.
 167 func (f *Fuzzer) Fuzz(obj interface{}) {
 168         v := reflect.ValueOf(obj)
 169         if v.Kind() != reflect.Ptr {
 170                 panic("needed ptr!")
 171         }
 172         v = v.Elem()
 173         f.fuzzWithContext(v, 0)
 174 }
 175
 176 // FuzzNoCustom is just like Fuzz, except that any custom fuzz function for
 177 // obj's type will not be called and obj will not be tested for fuzz.Interface
 178 // conformance.  This applies only to obj and not other instances of obj's
 179 // type.
 180 // Not safe for cyclic or tree-like structs!
 181 // obj must be a pointer. Only exported (public) fields can be set (thanks, golang :/ )
 182 // Intended for tests, so will panic on bad input or unimplemented fields.
 183 func (f *Fuzzer) FuzzNoCustom(obj interface{}) {
 184         v := reflect.ValueOf(obj)
 185         if v.Kind() != reflect.Ptr {
 186                 panic("needed ptr!")
 187         }
 188         v = v.Elem()
 189         f.fuzzWithContext(v, flagNoCustomFuzz)
 190 }
 191
 192 const (
 193         // Do not try to find a custom fuzz function.  Does not apply recursively.
 194         flagNoCustomFuzz uint64 = 1 << iota
 195 )
 196
 197 func (f *Fuzzer) fuzzWithContext(v reflect.Value, flags uint64) {
 198         fc := &fuzzerContext{fuzzer: f}
 199         fc.doFuzz(v, flags)
 200 }
 201
 202 // fuzzerContext carries context about a single fuzzing run, which lets Fuzzer
 203 // be thread-safe.
 204 type fuzzerContext struct {
 205         fuzzer   *Fuzzer
 206         curDepth int
 207 }
 208
 209 func (fc *fuzzerContext) doFuzz(v reflect.Value, flags uint64) {
 210         if fc.curDepth >= fc.fuzzer.maxDepth {
 211                 return
 212         }
 213         fc.curDepth++
 214         defer func() { fc.curDepth-- }()
 215
 216         if !v.CanSet() {
 217                 return
 218         }
 219
 220         if flags&flagNoCustomFuzz == 0 {
 221                 // Check for both pointer and non-pointer custom functions.
 222                 if v.CanAddr() && fc.tryCustom(v.Addr()) {
 223                         return
 224                 }
 225                 if fc.tryCustom(v) {
 226                         return
 227                 }
 228         }
 229
 230         if fn, ok := fillFuncMap[v.Kind()]; ok {
 231                 fn(v, fc.fuzzer.r)
 232                 return
 233         }
 234         switch v.Kind() {
 235         case reflect.Map:
 236                 if fc.fuzzer.genShouldFill() {
 237                         v.Set(reflect.MakeMap(v.Type()))
 238                         n := fc.fuzzer.genElementCount()
 239                         for i := 0; i < n; i++ {
 240                                 key := reflect.New(v.Type().Key()).Elem()
 241                                 fc.doFuzz(key, 0)
 242                                 val := reflect.New(v.Type().Elem()).Elem()
 243                                 fc.doFuzz(val, 0)
 244                                 v.SetMapIndex(key, val)
 245                         }
 246                         return
 247                 }
 248                 v.Set(reflect.Zero(v.Type()))
 249         case reflect.Ptr:
 250                 if fc.fuzzer.genShouldFill() {
 251                         v.Set(reflect.New(v.Type().Elem()))
 252                         fc.doFuzz(v.Elem(), 0)
 253                         return
 254                 }
 255                 v.Set(reflect.Zero(v.Type()))
 256         case reflect.Slice:
 257                 if fc.fuzzer.genShouldFill() {
 258                         n := fc.fuzzer.genElementCount()
 259                         v.Set(reflect.MakeSlice(v.Type(), n, n))
 260                         for i := 0; i < n; i++ {
 261                                 fc.doFuzz(v.Index(i), 0)
 262                         }
 263                         return
 264                 }
 265                 v.Set(reflect.Zero(v.Type()))
 266         case reflect.Array:
 267                 if fc.fuzzer.genShouldFill() {
 268                         n := v.Len()
 269                         for i := 0; i < n; i++ {
 270                                 fc.doFuzz(v.Index(i), 0)
 271                         }
 272                         return
 273                 }
 274                 v.Set(reflect.Zero(v.Type()))
 275         case reflect.Struct:
 276                 for i := 0; i < v.NumField(); i++ {
 277                         fc.doFuzz(v.Field(i), 0)
 278                 }
 279         case reflect.Chan:
 280                 fallthrough
 281         case reflect.Func:
 282                 fallthrough
 283         case reflect.Interface:
 284                 fallthrough
 285         default:
 286                 panic(fmt.Sprintf("Can't handle %#v", v.Interface()))
 287         }
 288 }
 289
 290 // tryCustom searches for custom handlers, and returns true iff it finds a match
 291 // and successfully randomizes v.
 292 func (fc *fuzzerContext) tryCustom(v reflect.Value) bool {
 293         // First: see if we have a fuzz function for it.
 294         doCustom, ok := fc.fuzzer.fuzzFuncs[v.Type()]
 295         if !ok {
 296                 // Second: see if it can fuzz itself.
 297                 if v.CanInterface() {
 298                         intf := v.Interface()
 299                         if fuzzable, ok := intf.(Interface); ok {
 300                                 fuzzable.Fuzz(Continue{fc: fc, Rand: fc.fuzzer.r})
 301                                 return true
 302                         }
 303                 }
 304                 // Finally: see if there is a default fuzz function.
 305                 doCustom, ok = fc.fuzzer.defaultFuzzFuncs[v.Type()]
 306                 if !ok {
 307                         return false
 308                 }
 309         }
 310
 311         switch v.Kind() {
 312         case reflect.Ptr:
 313                 if v.IsNil() {
 314                         if !v.CanSet() {
 315                                 return false
 316                         }
 317                         v.Set(reflect.New(v.Type().Elem()))
 318                 }
 319         case reflect.Map:
 320                 if v.IsNil() {
 321                         if !v.CanSet() {
 322                                 return false
 323                         }
 324                         v.Set(reflect.MakeMap(v.Type()))
 325                 }
 326         default:
 327                 return false
 328         }
 329
 330         doCustom.Call([]reflect.Value{v, reflect.ValueOf(Continue{
 331                 fc:   fc,
 332                 Rand: fc.fuzzer.r,
 333         })})
 334         return true
 335 }
 336
 337 // Interface represents an object that knows how to fuzz itself.  Any time we
 338 // find a type that implements this interface we will delegate the act of
 339 // fuzzing itself.
 340 type Interface interface {
 341         Fuzz(c Continue)
 342 }
 343
 344 // Continue can be passed to custom fuzzing functions to allow them to use
 345 // the correct source of randomness and to continue fuzzing their members.
 346 type Continue struct {
 347         fc *fuzzerContext
 348
 349         // For convenience, Continue implements rand.Rand via embedding.
 350         // Use this for generating any randomness if you want your fuzzing
 351         // to be repeatable for a given seed.
 352         *rand.Rand
 353 }
 354
 355 // Fuzz continues fuzzing obj. obj must be a pointer.
 356 func (c Continue) Fuzz(obj interface{}) {
 357         v := reflect.ValueOf(obj)
 358         if v.Kind() != reflect.Ptr {
 359                 panic("needed ptr!")
 360         }
 361         v = v.Elem()
 362         c.fc.doFuzz(v, 0)
 363 }
 364
 365 // FuzzNoCustom continues fuzzing obj, except that any custom fuzz function for
 366 // obj's type will not be called and obj will not be tested for fuzz.Interface
 367 // conformance.  This applies only to obj and not other instances of obj's
 368 // type.
 369 func (c Continue) FuzzNoCustom(obj interface{}) {
 370         v := reflect.ValueOf(obj)
 371         if v.Kind() != reflect.Ptr {
 372                 panic("needed ptr!")
 373         }
 374         v = v.Elem()
 375         c.fc.doFuzz(v, flagNoCustomFuzz)
 376 }
 377
 378 // RandString makes a random string up to 20 characters long. The returned string
 379 // may include a variety of (valid) UTF-8 encodings.
 380 func (c Continue) RandString() string {
 381         return randString(c.Rand)
 382 }
 383
 384 // RandUint64 makes random 64 bit numbers.
 385 // Weirdly, rand doesn't have a function that gives you 64 random bits.
 386 func (c Continue) RandUint64() uint64 {
 387         return randUint64(c.Rand)
 388 }
 389
 390 // RandBool returns true or false randomly.
 391 func (c Continue) RandBool() bool {
 392         return randBool(c.Rand)
 393 }
 394
 395 func fuzzInt(v reflect.Value, r *rand.Rand) {
 396         v.SetInt(int64(randUint64(r)))
 397 }
 398
 399 func fuzzUint(v reflect.Value, r *rand.Rand) {
 400         v.SetUint(randUint64(r))
 401 }
 402
 403 func fuzzTime(t *time.Time, c Continue) {
 404         var sec, nsec int64
 405         // Allow for about 1000 years of random time values, which keeps things
 406         // like JSON parsing reasonably happy.
 407         sec = c.Rand.Int63n(1000 * 365 * 24 * 60 * 60)
 408         c.Fuzz(&nsec)
 409         *t = time.Unix(sec, nsec)
 410 }
 411
 412 var fillFuncMap = map[reflect.Kind]func(reflect.Value, *rand.Rand){
 413         reflect.Bool: func(v reflect.Value, r *rand.Rand) {
 414                 v.SetBool(randBool(r))
 415         },
 416         reflect.Int:     fuzzInt,
 417         reflect.Int8:    fuzzInt,
 418         reflect.Int16:   fuzzInt,
 419         reflect.Int32:   fuzzInt,
 420         reflect.Int64:   fuzzInt,
 421         reflect.Uint:    fuzzUint,
 422         reflect.Uint8:   fuzzUint,
 423         reflect.Uint16:  fuzzUint,
 424         reflect.Uint32:  fuzzUint,
 425         reflect.Uint64:  fuzzUint,
 426         reflect.Uintptr: fuzzUint,
 427         reflect.Float32: func(v reflect.Value, r *rand.Rand) {
 428                 v.SetFloat(float64(r.Float32()))
 429         },
 430         reflect.Float64: func(v reflect.Value, r *rand.Rand) {
 431                 v.SetFloat(r.Float64())
 432         },
 433         reflect.Complex64: func(v reflect.Value, r *rand.Rand) {
 434                 panic("unimplemented")
 435         },
 436         reflect.Complex128: func(v reflect.Value, r *rand.Rand) {
 437                 panic("unimplemented")
 438         },
 439         reflect.String: func(v reflect.Value, r *rand.Rand) {
 440                 v.SetString(randString(r))
 441         },
 442         reflect.UnsafePointer: func(v reflect.Value, r *rand.Rand) {
 443                 panic("unimplemented")
 444         },
 445 }
 446
 447 // randBool returns true or false randomly.
 448 func randBool(r *rand.Rand) bool {
 449         if r.Int()&1 == 1 {
 450                 return true
 451         }
 452         return false
 453 }
 454
 455 type charRange struct {
 456         first, last rune
 457 }
 458
 459 // choose returns a random unicode character from the given range, using the
 460 // given randomness source.
 461 func (r *charRange) choose(rand *rand.Rand) rune {
 462         count := int64(r.last - r.first)
 463         return r.first + rune(rand.Int63n(count))
 464 }
 465
 466 var unicodeRanges = []charRange{
 467         {' ', '~'},           // ASCII characters
 468         {'\u00a0', '\u02af'}, // Multi-byte encoded characters
 469         {'\u4e00', '\u9fff'}, // Common CJK (even longer encodings)
 470 }
 471
 472 // randString makes a random string up to 20 characters long. The returned string
 473 // may include a variety of (valid) UTF-8 encodings.
 474 func randString(r *rand.Rand) string {
 475         n := r.Intn(20)
 476         runes := make([]rune, n)
 477         for i := range runes {
 478                 runes[i] = unicodeRanges[r.Intn(len(unicodeRanges))].choose(r)
 479         }
 480         return string(runes)
 481 }
 482
 483 // randUint64 makes random 64 bit numbers.
 484 // Weirdly, rand doesn't have a function that gives you 64 random bits.
 485 func randUint64(r *rand.Rand) uint64 {
 486         return uint64(r.Uint32())<<32 | uint64(r.Uint32())
 487 }