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