Debian Codegraph @

attribute/hash_test.go

raw
1 // Copyright The OpenTelemetry Authors
2 // SPDX-License-Identifier: Apache-2.0
3
4 package attribute // import "go.opentelemetry.io/otel/attribute"
5
6 import (
7 "cmp"
8 "fmt"
9 "math"
10 "reflect"
11 "slices"
12 "strings"
13 "testing"
14 )
15
16 // keyVals is all the KeyValue generators that are used for testing. This is
17 // not []KeyValue so different keys can be used with the test Values.
18 var keyVals = []func(string) KeyValue{
19 func(k string) KeyValue { return Bool(k, true) },
20 func(k string) KeyValue { return Bool(k, false) },
21 func(k string) KeyValue { return BoolSlice(k, []bool{false, true}) },
22 func(k string) KeyValue { return BoolSlice(k, []bool{true, true, false}) },
23 func(k string) KeyValue { return Int(k, -1278) },
24 func(k string) KeyValue { return Int(k, 0) }, // Should be different than false above.
25 func(k string) KeyValue { return IntSlice(k, []int{3, 23, 21, -8, 0}) },
26 func(k string) KeyValue { return IntSlice(k, []int{1}) },
27 func(k string) KeyValue { return Int64(k, 1) }, // Should be different from true and []int{1}.
28 func(k string) KeyValue { return Int64(k, 29369) },
29 func(k string) KeyValue { return Int64Slice(k, []int64{3826, -38, -29, -1}) },
30 func(k string) KeyValue { return Int64Slice(k, []int64{8, -328, 29, 0}) },
31 func(k string) KeyValue { return Float64(k, -0.3812381) },
32 func(k string) KeyValue { return Float64(k, 1e32) },
33 func(k string) KeyValue { return Float64Slice(k, []float64{0.1, -3.8, -29., 0.3321}) },
34 func(k string) KeyValue { return Float64Slice(k, []float64{-13e8, -32.8, 4., 1e28}) },
35 func(k string) KeyValue { return String(k, "foo") },
36 func(k string) KeyValue { return String(k, "bar") },
37 func(k string) KeyValue { return StringSlice(k, []string{"foo", "bar", "baz"}) },
38 func(k string) KeyValue { return StringSlice(k, []string{"[]i1"}) },
39 func(k string) KeyValue { return KeyValue{Key: Key(k)} }, // Empty value.
40 }
41
42 func TestHashKVsEquality(t *testing.T) {
43 type testcase struct {
44 hash uint64
45 kvs []KeyValue
46 }
47
48 keys := []string{"k0", "k1"}
49
50 // Test all combinations up to length 3.
51 n := len(keyVals)
52 result := make([]testcase, 0, 1+len(keys)*(n+(n*n)+(n*n*n)))
53
54 result = append(result, testcase{hashKVs(nil), nil})
55
56 for _, key := range keys {
57 for i := range keyVals {
58 kvs := []KeyValue{keyVals[i](key)}
59 hash := hashKVs(kvs)
60 result = append(result, testcase{hash, kvs})
61
62 for j := range keyVals {
63 kvs := []KeyValue{
64 keyVals[i](key),
65 keyVals[j](key),
66 }
67 hash := hashKVs(kvs)
68 result = append(result, testcase{hash, kvs})
69
70 for k := range keyVals {
71 kvs := []KeyValue{
72 keyVals[i](key),
73 keyVals[j](key),
74 keyVals[k](key),
75 }
76 hash := hashKVs(kvs)
77 result = append(result, testcase{hash, kvs})
78 }
79 }
80 }
81 }
82
83 for i := 0; i < len(result); i++ {
84 hI, kvI := result[i].hash, result[i].kvs
85 for j := 0; j < len(result); j++ {
86 hJ, kvJ := result[j].hash, result[j].kvs
87 m := msg{i: i, j: j, hI: hI, hJ: hJ, kvI: kvI, kvJ: kvJ}
88 if i == j {
89 m.cmp = "=="
90 if hI != hJ {
91 t.Errorf("hashes not equal: %s", m)
92 }
93 } else {
94 m.cmp = "!="
95 if hI == hJ {
96 // Do not use testify/assert here. It is slow.
97 t.Errorf("hashes equal: %s", m)
98 }
99 }
100 }
101 }
102 }
103
104 type msg struct {
105 cmp string
106 i, j int
107 hI, hJ uint64
108 kvI, kvJ []KeyValue
109 }
110
111 func (m msg) String() string {
112 return fmt.Sprintf(
113 "(%d: %d)%s %s (%d: %d)%s",
114 m.i, m.hI, slice(m.kvI), m.cmp, m.j, m.hJ, slice(m.kvJ),
115 )
116 }
117
118 func slice(kvs []KeyValue) string {
119 if len(kvs) == 0 {
120 return "[]"
121 }
122
123 var b strings.Builder
124 _, _ = b.WriteRune('[')
125 _, _ = b.WriteString(string(kvs[0].Key))
126 _, _ = b.WriteRune(':')
127 _, _ = b.WriteString(kvs[0].Value.Emit())
128 for _, kv := range kvs[1:] {
129 _, _ = b.WriteRune(',')
130 _, _ = b.WriteString(string(kv.Key))
131 _, _ = b.WriteRune(':')
132 _, _ = b.WriteString(kv.Value.Emit())
133 }
134 _, _ = b.WriteRune(']')
135 return b.String()
136 }
137
138 func BenchmarkHashKVs(b *testing.B) {
139 attrs := make([]KeyValue, len(keyVals))
140 for i := range keyVals {
141 attrs[i] = keyVals[i]("k")
142 }
143
144 b.ResetTimer()
145 b.ReportAllocs()
146 for b.Loop() {
147 hashKVs(attrs)
148 }
149 }
150
151 func FuzzHashKVs(f *testing.F) {
152 // Add seed inputs to ensure coverage of edge cases.
153 f.Add("", "", "", "", "", "", 0, int64(0), 0.0, false, uint8(0))
154 f.Add("key", "value", "🌍", "test", "bool", "float", -1, int64(-1), -1.0, true, uint8(1))
155 f.Add("duplicate", "duplicate", "duplicate", "duplicate", "duplicate", "NaN",
156 0, int64(0), math.Inf(1), false, uint8(2))
157
158 f.Fuzz(func(t *testing.T, k1, k2, k3, k4, k5, s string, i int, i64 int64, fVal float64, b bool, sliceType uint8) {
159 // Test variable number of attributes (0-11).
160 numAttrs := len(k1) % 12 // Use key length to determine number of attributes.
161 if numAttrs == 0 && k1 == "" {
162 // Test empty set.
163 h := hashKVs(nil)
164 if h == 0 {
165 t.Error("hash of empty slice should not be zero")
166 }
167 return
168 }
169
170 var kvs []KeyValue
171
172 // Add basic types.
173 if numAttrs > 0 {
174 kvs = append(kvs, String(k1, s))
175 }
176 if numAttrs > 1 {
177 kvs = append(kvs, Int(k2, i))
178 }
179 if numAttrs > 2 {
180 kvs = append(kvs, Int64(k3, i64))
181 }
182 if numAttrs > 3 {
183 kvs = append(kvs, Float64(k4, fVal))
184 }
185 if numAttrs > 4 {
186 kvs = append(kvs, Bool(k5, b))
187 }
188
189 // Add slice types based on sliceType parameter
190 if numAttrs > 5 {
191 switch sliceType % 4 {
192 case 0:
193 // Test BoolSlice with variable length.
194 bools := make([]bool, len(s)%5) // 0-4 elements
195 for i := range bools {
196 bools[i] = (i+len(k1))%2 == 0
197 }
198 kvs = append(kvs, BoolSlice("boolslice", bools))
199 case 1:
200 // Test IntSlice with variable length.
201 ints := make([]int, len(s)%6) // 0-5 elements
202 for i := range ints {
203 ints[i] = i + len(k2)
204 }
205 kvs = append(kvs, IntSlice("intslice", ints))
206 case 2:
207 // Test Int64Slice with variable length.
208 int64s := make([]int64, len(s)%4) // 0-3 elements
209 for i := range int64s {
210 int64s[i] = int64(i) + i64
211 }
212 kvs = append(kvs, Int64Slice("int64slice", int64s))
213 case 3:
214 // Test Float64Slice with variable length and special values.
215 float64s := make([]float64, len(s)%5) // 0-4 elements
216 for i := range float64s {
217 switch i % 4 {
218 case 0:
219 float64s[i] = fVal
220 case 1:
221 float64s[i] = math.Inf(1) // +Inf
222 case 2:
223 float64s[i] = math.Inf(-1) // -Inf
224 case 3:
225 float64s[i] = math.NaN() // NaN
226 }
227 }
228 kvs = append(kvs, Float64Slice("float64slice", float64s))
229 }
230 }
231
232 // Add StringSlice.
233 if numAttrs > 6 {
234 strings := make([]string, len(k1)%4) // 0-3 elements
235 for i := range strings {
236 strings[i] = fmt.Sprintf("%s_%d", s, i)
237 }
238 kvs = append(kvs, StringSlice("stringslice", strings))
239 }
240
241 // Test duplicate keys (should be handled by Set construction).
242 if numAttrs > 7 && k1 != "" {
243 kvs = append(kvs, String(k1, "duplicate_key_value"))
244 }
245
246 // Add more attributes with Unicode keys.
247 if numAttrs > 8 {
248 kvs = append(kvs, String("🔑", "unicode_key"))
249 }
250 if numAttrs > 9 {
251 kvs = append(kvs, String("empty", ""))
252 }
253
254 // Add empty value.
255 if numAttrs > 10 {
256 kvs = append(kvs, KeyValue{Key: Key("empty_value")})
257 }
258
259 // Sort to ensure consistent ordering (as Set would do).
260 slices.SortFunc(kvs, func(a, b KeyValue) int {
261 return cmp.Compare(string(a.Key), string(b.Key))
262 })
263
264 // Remove duplicates (as Set will do).
265 if len(kvs) > 1 {
266 j := 0
267 for i := 1; i < len(kvs); i++ {
268 if kvs[j].Key != kvs[i].Key {
269 j++
270 kvs[j] = kvs[i]
271 } else {
272 // Keep the later value for duplicate keys.
273 kvs[j] = kvs[i]
274 }
275 }
276 kvs = kvs[:j+1]
277 }
278
279 // Hash the key-value pairs.
280 h1 := hashKVs(kvs)
281 h2 := hashKVs(kvs) // Should be deterministic
282
283 if h1 != h2 {
284 t.Errorf("hash is not deterministic: %d != %d for kvs=%v", h1, h2, kvs)
285 }
286
287 if h1 == 0 && len(kvs) > 0 {
288 t.Errorf("hash should not be zero for non-empty input: kvs=%v", kvs)
289 }
290
291 // Test that different inputs produce different hashes (most of the time).
292 // This is a probabilistic test - collisions are possible but rare.
293 if len(kvs) > 0 {
294 // Modify one value slightly.
295 modifiedKvs := make([]KeyValue, len(kvs))
296 copy(modifiedKvs, kvs)
297 if len(modifiedKvs) > 0 {
298 switch modifiedKvs[0].Value.Type() {
299 case STRING:
300 modifiedKvs[0] = String(string(modifiedKvs[0].Key), modifiedKvs[0].Value.AsString()+"_modified")
301 case INT64:
302 modifiedKvs[0] = Int64(string(modifiedKvs[0].Key), modifiedKvs[0].Value.AsInt64()+1)
303 case BOOL:
304 modifiedKvs[0] = Bool(string(modifiedKvs[0].Key), !modifiedKvs[0].Value.AsBool())
305 case FLOAT64:
306 val := modifiedKvs[0].Value.AsFloat64()
307 if !math.IsNaN(val) && !math.IsInf(val, 0) {
308 modifiedKvs[0] = Float64(string(modifiedKvs[0].Key), val+1.0)
309 }
310 case EMPTY:
311 modifiedKvs[0] = String(string(modifiedKvs[0].Key), "not_empty")
312 }
313
314 h3 := hashKVs(modifiedKvs)
315 // Note: We don't assert h1 != h3 because hash collisions are theoretically possible
316 // but we can log suspicious cases for manual review.
317 if h1 == h3 && !reflect.DeepEqual(kvs, modifiedKvs) {
318 t.Logf("Potential hash collision detected: original=%v, modified=%v, hash=%d", kvs, modifiedKvs, h1)
319 }
320 }
321 }
322 })
323 }