vendor/github.com/mitchellh/hashstructure/hashstructure.go

   1 package hashstructure
   2
   3 import (
   4         "encoding/binary"
   5         "fmt"
   6         "hash"
   7         "hash/fnv"
   8         "reflect"
   9 )
  10
  11 // ErrNotStringer is returned when there's an error with hash:"string"
  12 type ErrNotStringer struct {
  13         Field string
  14 }
  15
  16 // Error implements error for ErrNotStringer
  17 func (ens *ErrNotStringer) Error() string {
  18         return fmt.Sprintf("hashstructure: %s has hash:\"string\" set, but does not implement fmt.Stringer", ens.Field)
  19 }
  20
  21 // HashOptions are options that are available for hashing.
  22 type HashOptions struct {
  23         // Hasher is the hash function to use. If this isn't set, it will
  24         // default to FNV.
  25         Hasher hash.Hash64
  26
  27         // TagName is the struct tag to look at when hashing the structure.
  28         // By default this is "hash".
  29         TagName string
  30
  31         // ZeroNil is flag determining if nil pointer should be treated equal
  32         // to a zero value of pointed type. By default this is false.
  33         ZeroNil bool
  34 }
  35
  36 // Hash returns the hash value of an arbitrary value.
  37 //
  38 // If opts is nil, then default options will be used. See HashOptions
  39 // for the default values. The same *HashOptions value cannot be used
  40 // concurrently. None of the values within a *HashOptions struct are
  41 // safe to read/write while hashing is being done.
  42 //
  43 // Notes on the value:
  44 //
  45 //   * Unexported fields on structs are ignored and do not affect the
  46 //     hash value.
  47 //
  48 //   * Adding an exported field to a struct with the zero value will change
  49 //     the hash value.
  50 //
  51 // For structs, the hashing can be controlled using tags. For example:
  52 //
  53 //    struct {
  54 //        Name string
  55 //        UUID string `hash:"ignore"`
  56 //    }
  57 //
  58 // The available tag values are:
  59 //
  60 //   * "ignore" or "-" - The field will be ignored and not affect the hash code.
  61 //
  62 //   * "set" - The field will be treated as a set, where ordering doesn't
  63 //             affect the hash code. This only works for slices.
  64 //
  65 //   * "string" - The field will be hashed as a string, only works when the
  66 //                field implements fmt.Stringer
  67 //
  68 func Hash(v interface{}, opts *HashOptions) (uint64, error) {
  69         // Create default options
  70         if opts == nil {
  71                 opts = &HashOptions{}
  72         }
  73         if opts.Hasher == nil {
  74                 opts.Hasher = fnv.New64()
  75         }
  76         if opts.TagName == "" {
  77                 opts.TagName = "hash"
  78         }
  79
  80         // Reset the hash
  81         opts.Hasher.Reset()
  82
  83         // Create our walker and walk the structure
  84         w := &walker{
  85                 h:       opts.Hasher,
  86                 tag:     opts.TagName,
  87                 zeronil: opts.ZeroNil,
  88         }
  89         return w.visit(reflect.ValueOf(v), nil)
  90 }
  91
  92 type walker struct {
  93         h       hash.Hash64
  94         tag     string
  95         zeronil bool
  96 }
  97
  98 type visitOpts struct {
  99         // Flags are a bitmask of flags to affect behavior of this visit
 100         Flags visitFlag
 101
 102         // Information about the struct containing this field
 103         Struct      interface{}
 104         StructField string
 105 }
 106
 107 func (w *walker) visit(v reflect.Value, opts *visitOpts) (uint64, error) {
 108         t := reflect.TypeOf(0)
 109
 110         // Loop since these can be wrapped in multiple layers of pointers
 111         // and interfaces.
 112         for {
 113                 // If we have an interface, dereference it. We have to do this up
 114                 // here because it might be a nil in there and the check below must
 115                 // catch that.
 116                 if v.Kind() == reflect.Interface {
 117                         v = v.Elem()
 118                         continue
 119                 }
 120
 121                 if v.Kind() == reflect.Ptr {
 122                         if w.zeronil {
 123                                 t = v.Type().Elem()
 124                         }
 125                         v = reflect.Indirect(v)
 126                         continue
 127                 }
 128
 129                 break
 130         }
 131
 132         // If it is nil, treat it like a zero.
 133         if !v.IsValid() {
 134                 v = reflect.Zero(t)
 135         }
 136
 137         // Binary writing can use raw ints, we have to convert to
 138         // a sized-int, we'll choose the largest...
 139         switch v.Kind() {
 140         case reflect.Int:
 141                 v = reflect.ValueOf(int64(v.Int()))
 142         case reflect.Uint:
 143                 v = reflect.ValueOf(uint64(v.Uint()))
 144         case reflect.Bool:
 145                 var tmp int8
 146                 if v.Bool() {
 147                         tmp = 1
 148                 }
 149                 v = reflect.ValueOf(tmp)
 150         }
 151
 152         k := v.Kind()
 153
 154         // We can shortcut numeric values by directly binary writing them
 155         if k >= reflect.Int && k <= reflect.Complex64 {
 156                 // A direct hash calculation
 157                 w.h.Reset()
 158                 err := binary.Write(w.h, binary.LittleEndian, v.Interface())
 159                 return w.h.Sum64(), err
 160         }
 161
 162         switch k {
 163         case reflect.Array:
 164                 var h uint64
 165                 l := v.Len()
 166                 for i := 0; i < l; i++ {
 167                         current, err := w.visit(v.Index(i), nil)
 168                         if err != nil {
 169                                 return 0, err
 170                         }
 171
 172                         h = hashUpdateOrdered(w.h, h, current)
 173                 }
 174
 175                 return h, nil
 176
 177         case reflect.Map:
 178                 var includeMap IncludableMap
 179                 if opts != nil && opts.Struct != nil {
 180                         if v, ok := opts.Struct.(IncludableMap); ok {
 181                                 includeMap = v
 182                         }
 183                 }
 184
 185                 // Build the hash for the map. We do this by XOR-ing all the key
 186                 // and value hashes. This makes it deterministic despite ordering.
 187                 var h uint64
 188                 for _, k := range v.MapKeys() {
 189                         v := v.MapIndex(k)
 190                         if includeMap != nil {
 191                                 incl, err := includeMap.HashIncludeMap(
 192                                         opts.StructField, k.Interface(), v.Interface())
 193                                 if err != nil {
 194                                         return 0, err
 195                                 }
 196                                 if !incl {
 197                                         continue
 198                                 }
 199                         }
 200
 201                         kh, err := w.visit(k, nil)
 202                         if err != nil {
 203                                 return 0, err
 204                         }
 205                         vh, err := w.visit(v, nil)
 206                         if err != nil {
 207                                 return 0, err
 208                         }
 209
 210                         fieldHash := hashUpdateOrdered(w.h, kh, vh)
 211                         h = hashUpdateUnordered(h, fieldHash)
 212                 }
 213
 214                 return h, nil
 215
 216         case reflect.Struct:
 217                 parent := v.Interface()
 218                 var include Includable
 219                 if impl, ok := parent.(Includable); ok {
 220                         include = impl
 221                 }
 222
 223                 t := v.Type()
 224                 h, err := w.visit(reflect.ValueOf(t.Name()), nil)
 225                 if err != nil {
 226                         return 0, err
 227                 }
 228
 229                 l := v.NumField()
 230                 for i := 0; i < l; i++ {
 231                         if innerV := v.Field(i); v.CanSet() || t.Field(i).Name != "_" {
 232                                 var f visitFlag
 233                                 fieldType := t.Field(i)
 234                                 if fieldType.PkgPath != "" {
 235                                         // Unexported
 236                                         continue
 237                                 }
 238
 239                                 tag := fieldType.Tag.Get(w.tag)
 240                                 if tag == "ignore" || tag == "-" {
 241                                         // Ignore this field
 242                                         continue
 243                                 }
 244
 245                                 // if string is set, use the string value
 246                                 if tag == "string" {
 247                                         if impl, ok := innerV.Interface().(fmt.Stringer); ok {
 248                                                 innerV = reflect.ValueOf(impl.String())
 249                                         } else {
 250                                                 return 0, &ErrNotStringer{
 251                                                         Field: v.Type().Field(i).Name,
 252                                                 }
 253                                         }
 254                                 }
 255
 256                                 // Check if we implement includable and check it
 257                                 if include != nil {
 258                                         incl, err := include.HashInclude(fieldType.Name, innerV)
 259                                         if err != nil {
 260                                                 return 0, err
 261                                         }
 262                                         if !incl {
 263                                                 continue
 264                                         }
 265                                 }
 266
 267                                 switch tag {
 268                                 case "set":
 269                                         f |= visitFlagSet
 270                                 }
 271
 272                                 kh, err := w.visit(reflect.ValueOf(fieldType.Name), nil)
 273                                 if err != nil {
 274                                         return 0, err
 275                                 }
 276
 277                                 vh, err := w.visit(innerV, &visitOpts{
 278                                         Flags:       f,
 279                                         Struct:      parent,
 280                                         StructField: fieldType.Name,
 281                                 })
 282                                 if err != nil {
 283                                         return 0, err
 284                                 }
 285
 286                                 fieldHash := hashUpdateOrdered(w.h, kh, vh)
 287                                 h = hashUpdateUnordered(h, fieldHash)
 288                         }
 289                 }
 290
 291                 return h, nil
 292
 293         case reflect.Slice:
 294                 // We have two behaviors here. If it isn't a set, then we just
 295                 // visit all the elements. If it is a set, then we do a deterministic
 296                 // hash code.
 297                 var h uint64
 298                 var set bool
 299                 if opts != nil {
 300                         set = (opts.Flags & visitFlagSet) != 0
 301                 }
 302                 l := v.Len()
 303                 for i := 0; i < l; i++ {
 304                         current, err := w.visit(v.Index(i), nil)
 305                         if err != nil {
 306                                 return 0, err
 307                         }
 308
 309                         if set {
 310                                 h = hashUpdateUnordered(h, current)
 311                         } else {
 312                                 h = hashUpdateOrdered(w.h, h, current)
 313                         }
 314                 }
 315
 316                 return h, nil
 317
 318         case reflect.String:
 319                 // Directly hash
 320                 w.h.Reset()
 321                 _, err := w.h.Write([]byte(v.String()))
 322                 return w.h.Sum64(), err
 323
 324         default:
 325                 return 0, fmt.Errorf("unknown kind to hash: %s", k)
 326         }
 327
 328 }
 329
 330 func hashUpdateOrdered(h hash.Hash64, a, b uint64) uint64 {
 331         // For ordered updates, use a real hash function
 332         h.Reset()
 333
 334         // We just panic if the binary writes fail because we are writing
 335         // an int64 which should never be fail-able.
 336         e1 := binary.Write(h, binary.LittleEndian, a)
 337         e2 := binary.Write(h, binary.LittleEndian, b)
 338         if e1 != nil {
 339                 panic(e1)
 340         }
 341         if e2 != nil {
 342                 panic(e2)
 343         }
 344
 345         return h.Sum64()
 346 }
 347
 348 func hashUpdateUnordered(a, b uint64) uint64 {
 349         return a ^ b
 350 }
 351
 352 // visitFlag is used as a bitmask for affecting visit behavior
 353 type visitFlag uint
 354
 355 const (
 356         visitFlagInvalid visitFlag = iota
 357         visitFlagSet               = iota << 1
 358 )