]>
Commit | Line | Data |
---|---|---|
bae9f6d2 JC |
1 | package hashstructure |
2 | ||
3 | import ( | |
4 | "encoding/binary" | |
5 | "fmt" | |
6 | "hash" | |
7 | "hash/fnv" | |
8 | "reflect" | |
9 | ) | |
10 | ||
107c1cdb ND |
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 | ||
bae9f6d2 JC |
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 | |
107c1cdb ND |
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 | |
bae9f6d2 JC |
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 | |
107c1cdb ND |
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. | |
bae9f6d2 JC |
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 | // | |
107c1cdb | 60 | // * "ignore" or "-" - The field will be ignored and not affect the hash code. |
bae9f6d2 JC |
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 | // | |
107c1cdb ND |
65 | // * "string" - The field will be hashed as a string, only works when the |
66 | // field implements fmt.Stringer | |
67 | // | |
bae9f6d2 JC |
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{ | |
107c1cdb ND |
85 | h: opts.Hasher, |
86 | tag: opts.TagName, | |
87 | zeronil: opts.ZeroNil, | |
bae9f6d2 JC |
88 | } |
89 | return w.visit(reflect.ValueOf(v), nil) | |
90 | } | |
91 | ||
92 | type walker struct { | |
107c1cdb ND |
93 | h hash.Hash64 |
94 | tag string | |
95 | zeronil bool | |
bae9f6d2 JC |
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) { | |
107c1cdb ND |
108 | t := reflect.TypeOf(0) |
109 | ||
bae9f6d2 JC |
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 { | |
107c1cdb ND |
122 | if w.zeronil { |
123 | t = v.Type().Elem() | |
124 | } | |
bae9f6d2 JC |
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() { | |
107c1cdb | 134 | v = reflect.Zero(t) |
bae9f6d2 JC |
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: | |
bae9f6d2 | 217 | parent := v.Interface() |
107c1cdb | 218 | var include Includable |
bae9f6d2 JC |
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++ { | |
107c1cdb | 231 | if innerV := v.Field(i); v.CanSet() || t.Field(i).Name != "_" { |
bae9f6d2 JC |
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) | |
107c1cdb | 240 | if tag == "ignore" || tag == "-" { |
bae9f6d2 JC |
241 | // Ignore this field |
242 | continue | |
243 | } | |
244 | ||
107c1cdb ND |
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 | ||
bae9f6d2 JC |
256 | // Check if we implement includable and check it |
257 | if include != nil { | |
107c1cdb | 258 | incl, err := include.HashInclude(fieldType.Name, innerV) |
bae9f6d2 JC |
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 | ||
107c1cdb | 277 | vh, err := w.visit(innerV, &visitOpts{ |
bae9f6d2 JC |
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 | ||
bae9f6d2 JC |
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 | ) |