Debian Codegraph @

attribute/set.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 "encoding/json"
9 "reflect"
10 "slices"
11 "sort"
12
13 "go.opentelemetry.io/otel/attribute/internal/xxhash"
14 )
15
16 type (
17 // Set is the representation for a distinct attribute set. It manages an
18 // immutable set of attributes, with an internal cache for storing
19 // attribute encodings.
20 //
21 // This type will remain comparable for backwards compatibility. The
22 // equivalence of Sets across versions is not guaranteed to be stable.
23 // Prior versions may find two Sets to be equal or not when compared
24 // directly (i.e. ==), but subsequent versions may not. Users should use
25 // the Equals method to ensure stable equivalence checking.
26 //
27 // Users should also use the Distinct returned from Equivalent as a map key
28 // instead of a Set directly. Set has relatively poor performance when used
29 // as a map key compared to Distinct.
30 Set struct {
31 hash uint64
32 data any
33 }
34
35 // Distinct is an identifier of a Set which is very likely to be unique.
36 //
37 // Distinct should be used as a map key instead of a Set for to provide better
38 // performance for map operations.
39 Distinct struct {
40 hash uint64
41 }
42
43 // Sortable implements sort.Interface, used for sorting KeyValue.
44 //
45 // Deprecated: This type is no longer used. It was added as a performance
46 // optimization for Go < 1.21 that is no longer needed (Go < 1.21 is no
47 // longer supported by the module).
48 Sortable []KeyValue
49 )
50
51 // Compile time check these types remain comparable.
52 var (
53 _ = isComparable(Set{})
54 _ = isComparable(Distinct{})
55 )
56
57 func isComparable[T comparable](t T) T { return t }
58
59 var (
60 // keyValueType is used in computeDistinctReflect.
61 keyValueType = reflect.TypeFor[KeyValue]()
62
63 // emptyHash is the hash of an empty set.
64 emptyHash = xxhash.New().Sum64()
65
66 // userDefinedEmptySet is an empty set. It was mistakenly exposed to users
67 // as something they can assign to, so it must remain addressable and
68 // mutable.
69 //
70 // This is kept for backwards compatibility, but should not be used in new code.
71 userDefinedEmptySet = &Set{
72 hash: emptyHash,
73 data: [0]KeyValue{},
74 }
75
76 emptySet = Set{
77 hash: emptyHash,
78 data: [0]KeyValue{},
79 }
80 )
81
82 // EmptySet returns a reference to a Set with no elements.
83 //
84 // This is a convenience provided for optimized calling utility.
85 func EmptySet() *Set {
86 // Continue to return the pointer to the user-defined empty set for
87 // backwards-compatibility.
88 //
89 // New code should not use this, instead use emptySet.
90 return userDefinedEmptySet
91 }
92
93 // Valid reports whether this value refers to a valid Set.
94 func (d Distinct) Valid() bool { return d.hash != 0 }
95
96 // reflectValue abbreviates reflect.ValueOf(d).
97 func (l Set) reflectValue() reflect.Value {
98 return reflect.ValueOf(l.data)
99 }
100
101 // Len returns the number of attributes in this set.
102 func (l *Set) Len() int {
103 if l == nil || l.hash == 0 {
104 return 0
105 }
106 return l.reflectValue().Len()
107 }
108
109 // Get returns the KeyValue at ordered position idx in this set.
110 func (l *Set) Get(idx int) (KeyValue, bool) {
111 if l == nil || l.hash == 0 {
112 return KeyValue{}, false
113 }
114 value := l.reflectValue()
115
116 if idx >= 0 && idx < value.Len() {
117 // Note: The Go compiler successfully avoids an allocation for
118 // the interface{} conversion here:
119 return value.Index(idx).Interface().(KeyValue), true
120 }
121
122 return KeyValue{}, false
123 }
124
125 // Value returns the value of a specified key in this set.
126 func (l *Set) Value(k Key) (Value, bool) {
127 if l == nil || l.hash == 0 {
128 return Value{}, false
129 }
130 rValue := l.reflectValue()
131 vlen := rValue.Len()
132
133 idx := sort.Search(vlen, func(idx int) bool {
134 return rValue.Index(idx).Interface().(KeyValue).Key >= k
135 })
136 if idx >= vlen {
137 return Value{}, false
138 }
139 keyValue := rValue.Index(idx).Interface().(KeyValue)
140 if k == keyValue.Key {
141 return keyValue.Value, true
142 }
143 return Value{}, false
144 }
145
146 // HasValue reports whether a key is defined in this set.
147 func (l *Set) HasValue(k Key) bool {
148 if l == nil {
149 return false
150 }
151 _, ok := l.Value(k)
152 return ok
153 }
154
155 // Iter returns an iterator for visiting the attributes in this set.
156 func (l *Set) Iter() Iterator {
157 return Iterator{
158 storage: l,
159 idx: -1,
160 }
161 }
162
163 // ToSlice returns the set of attributes belonging to this set, sorted, where
164 // keys appear no more than once.
165 func (l *Set) ToSlice() []KeyValue {
166 iter := l.Iter()
167 return iter.ToSlice()
168 }
169
170 // Equivalent returns a value that may be used as a map key. Equal Distinct
171 // values are very likely to be equivalent attribute Sets. Distinct value of any
172 // attribute set with the same elements as this, where sets are made unique by
173 // choosing the last value in the input for any given key.
174 func (l *Set) Equivalent() Distinct {
175 if l == nil || l.hash == 0 {
176 return Distinct{hash: emptySet.hash}
177 }
178 return Distinct{hash: l.hash}
179 }
180
181 // Equals reports whether the argument set is equivalent to this set.
182 func (l *Set) Equals(o *Set) bool {
183 if l.Equivalent() != o.Equivalent() {
184 return false
185 }
186 if l == nil || l.hash == 0 {
187 l = &emptySet
188 }
189 if o == nil || o.hash == 0 {
190 o = &emptySet
191 }
192 return l.data == o.data
193 }
194
195 // Encoded returns the encoded form of this set, according to encoder.
196 func (l *Set) Encoded(encoder Encoder) string {
197 if l == nil || encoder == nil {
198 return ""
199 }
200
201 return encoder.Encode(l.Iter())
202 }
203
204 // NewSet returns a new Set. See the documentation for
205 // NewSetWithSortableFiltered for more details.
206 //
207 // Except for empty sets, this method adds an additional allocation compared
208 // with calls that include a Sortable.
209 func NewSet(kvs ...KeyValue) Set {
210 s, _ := NewSetWithFiltered(kvs, nil)
211 return s
212 }
213
214 // NewSetWithSortable returns a new Set. See the documentation for
215 // NewSetWithSortableFiltered for more details.
216 //
217 // This call includes a Sortable option as a memory optimization.
218 //
219 // Deprecated: Use [NewSet] instead.
220 func NewSetWithSortable(kvs []KeyValue, _ *Sortable) Set {
221 s, _ := NewSetWithFiltered(kvs, nil)
222 return s
223 }
224
225 // NewSetWithFiltered returns a new Set. See the documentation for
226 // NewSetWithSortableFiltered for more details.
227 //
228 // This call includes a Filter to include/exclude attribute keys from the
229 // return value. Excluded keys are returned as a slice of attribute values.
230 func NewSetWithFiltered(kvs []KeyValue, filter Filter) (Set, []KeyValue) {
231 // Check for empty set.
232 if len(kvs) == 0 {
233 return emptySet, nil
234 }
235
236 // Stable sort so the following de-duplication can implement
237 // last-value-wins semantics.
238 slices.SortStableFunc(kvs, func(a, b KeyValue) int {
239 return cmp.Compare(a.Key, b.Key)
240 })
241
242 position := len(kvs) - 1
243 offset := position - 1
244
245 // The requirements stated above require that the stable
246 // result be placed in the end of the input slice, while
247 // overwritten values are swapped to the beginning.
248 //
249 // De-duplicate with last-value-wins semantics. Preserve
250 // duplicate values at the beginning of the input slice.
251 for ; offset >= 0; offset-- {
252 if kvs[offset].Key == kvs[position].Key {
253 continue
254 }
255 position--
256 kvs[offset], kvs[position] = kvs[position], kvs[offset]
257 }
258 kvs = kvs[position:]
259
260 if filter != nil {
261 if div := filteredToFront(kvs, filter); div != 0 {
262 return newSet(kvs[div:]), kvs[:div]
263 }
264 }
265 return newSet(kvs), nil
266 }
267
268 // NewSetWithSortableFiltered returns a new Set.
269 //
270 // Duplicate keys are eliminated by taking the last value. This
271 // re-orders the input slice so that unique last-values are contiguous
272 // at the end of the slice.
273 //
274 // This ensures the following:
275 //
276 // - Last-value-wins semantics
277 // - Caller sees the reordering, but doesn't lose values
278 // - Repeated call preserve last-value wins.
279 //
280 // Note that methods are defined on Set, although this returns Set. Callers
281 // can avoid memory allocations by:
282 //
283 // - allocating a Sortable for use as a temporary in this method
284 // - allocating a Set for storing the return value of this constructor.
285 //
286 // The result maintains a cache of encoded attributes, by attribute.EncoderID.
287 // This value should not be copied after its first use.
288 //
289 // The second []KeyValue return value is a list of attributes that were
290 // excluded by the Filter (if non-nil).
291 //
292 // Deprecated: Use [NewSetWithFiltered] instead.
293 func NewSetWithSortableFiltered(kvs []KeyValue, _ *Sortable, filter Filter) (Set, []KeyValue) {
294 return NewSetWithFiltered(kvs, filter)
295 }
296
297 // filteredToFront filters slice in-place using keep function. All KeyValues that need to
298 // be removed are moved to the front. All KeyValues that need to be kept are
299 // moved (in-order) to the back. The index for the first KeyValue to be kept is
300 // returned.
301 func filteredToFront(slice []KeyValue, keep Filter) int {
302 n := len(slice)
303 j := n
304 for i := n - 1; i >= 0; i-- {
305 if keep(slice[i]) {
306 j--
307 slice[i], slice[j] = slice[j], slice[i]
308 }
309 }
310 return j
311 }
312
313 // Filter returns a filtered copy of this Set. See the documentation for
314 // NewSetWithSortableFiltered for more details.
315 func (l *Set) Filter(re Filter) (Set, []KeyValue) {
316 if re == nil {
317 return *l, nil
318 }
319
320 // Iterate in reverse to the first attribute that will be filtered out.
321 n := l.Len()
322 first := n - 1
323 for ; first >= 0; first-- {
324 kv, _ := l.Get(first)
325 if !re(kv) {
326 break
327 }
328 }
329
330 // No attributes will be dropped, return the immutable Set l and nil.
331 if first < 0 {
332 return *l, nil
333 }
334
335 // Copy now that we know we need to return a modified set.
336 //
337 // Do not do this in-place on the underlying storage of *Set l. Sets are
338 // immutable and filtering should not change this.
339 slice := l.ToSlice()
340
341 // Don't re-iterate the slice if only slice[0] is filtered.
342 if first == 0 {
343 // It is safe to assume len(slice) >= 1 given we found at least one
344 // attribute above that needs to be filtered out.
345 return newSet(slice[1:]), slice[:1]
346 }
347
348 // Move the filtered slice[first] to the front (preserving order).
349 kv := slice[first]
350 copy(slice[1:first+1], slice[:first])
351 slice[0] = kv
352
353 // Do not re-evaluate re(slice[first+1:]).
354 div := filteredToFront(slice[1:first+1], re) + 1
355 return newSet(slice[div:]), slice[:div]
356 }
357
358 // newSet returns a new set based on the sorted and uniqued kvs.
359 func newSet(kvs []KeyValue) Set {
360 s := Set{
361 hash: hashKVs(kvs),
362 data: computeDataFixed(kvs),
363 }
364 if s.data == nil {
365 s.data = computeDataReflect(kvs)
366 }
367 return s
368 }
369
370 // computeDataFixed computes a Set data for small slices. It returns nil if the
371 // input is too large for this code path.
372 func computeDataFixed(kvs []KeyValue) any {
373 switch len(kvs) {
374 case 1:
375 return [1]KeyValue(kvs)
376 case 2:
377 return [2]KeyValue(kvs)
378 case 3:
379 return [3]KeyValue(kvs)
380 case 4:
381 return [4]KeyValue(kvs)
382 case 5:
383 return [5]KeyValue(kvs)
384 case 6:
385 return [6]KeyValue(kvs)
386 case 7:
387 return [7]KeyValue(kvs)
388 case 8:
389 return [8]KeyValue(kvs)
390 case 9:
391 return [9]KeyValue(kvs)
392 case 10:
393 return [10]KeyValue(kvs)
394 default:
395 return nil
396 }
397 }
398
399 // computeDataReflect computes a Set data using reflection, works for any size
400 // input.
401 func computeDataReflect(kvs []KeyValue) any {
402 at := reflect.New(reflect.ArrayOf(len(kvs), keyValueType)).Elem()
403 for i, keyValue := range kvs {
404 *(at.Index(i).Addr().Interface().(*KeyValue)) = keyValue
405 }
406 return at.Interface()
407 }
408
409 // MarshalJSON returns the JSON encoding of the Set.
410 func (l *Set) MarshalJSON() ([]byte, error) {
411 return json.Marshal(l.data)
412 }
413
414 // MarshalLog is the marshaling function used by the logging system to represent this Set.
415 func (l Set) MarshalLog() any {
416 kvs := make(map[string]string)
417 for _, kv := range l.ToSlice() {
418 kvs[string(kv.Key)] = kv.Value.Emit()
419 }
420 return kvs
421 }
422
423 // Len implements sort.Interface.
424 func (l *Sortable) Len() int {
425 return len(*l)
426 }
427
428 // Swap implements sort.Interface.
429 func (l *Sortable) Swap(i, j int) {
430 (*l)[i], (*l)[j] = (*l)[j], (*l)[i]
431 }
432
433 // Less implements sort.Interface.
434 func (l *Sortable) Less(i, j int) bool {
435 return (*l)[i].Key < (*l)[j].Key
436 }