1// Copyright The OpenTelemetry Authors
  2// SPDX-License-Identifier: Apache-2.0
  3
  4package attribute // import "go.opentelemetry.io/otel/attribute"
  5
  6import (
  7	"cmp"
  8	"encoding/json"
  9	"reflect"
 10	"slices"
 11	"sort"
 12)
 13
 14type (
 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 be ensures equivalence stability: comparisons
 35	// will return the save value across versions. For this reason, Distinct
 36	// should always be used as a map key instead of a Set.
 37	Distinct struct {
 38		iface interface{}
 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
 49var (
 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.
 64func EmptySet() *Set {
 65	return emptySet
 66}
 67
 68// reflectValue abbreviates reflect.ValueOf(d).
 69func (d Distinct) reflectValue() reflect.Value {
 70	return reflect.ValueOf(d.iface)
 71}
 72
 73// Valid returns true if this value refers to a valid Set.
 74func (d Distinct) Valid() bool {
 75	return d.iface != nil
 76}
 77
 78// Len returns the number of attributes in this set.
 79func (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.
 87func (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.
103func (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 tests whether a key is defined in this set.
124func (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.
133func (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.
142func (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.
151func (l *Set) Equivalent() Distinct {
152	if l == nil || !l.equivalent.Valid() {
153		return emptySet.equivalent
154	}
155	return l.equivalent
156}
157
158// Equals returns true if the argument set is equivalent to this set.
159func (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.
164func (l *Set) Encoded(encoder Encoder) string {
165	if l == nil || encoder == nil {
166		return ""
167	}
168
169	return encoder.Encode(l.Iter())
170}
171
172func 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.
183func 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.
194func 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.
204func 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.
267func 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.
275func 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.
289func (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.
335func 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.
347func computeDistinctFixed(kvs []KeyValue) interface{} {
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.
376func computeDistinctReflect(kvs []KeyValue) interface{} {
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.
385func (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.
390func (l Set) MarshalLog() interface{} {
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.
399func (l *Sortable) Len() int {
400	return len(*l)
401}
402
403// Swap implements sort.Interface.
404func (l *Sortable) Swap(i, j int) {
405	(*l)[i], (*l)[j] = (*l)[j], (*l)[i]
406}
407
408// Less implements sort.Interface.
409func (l *Sortable) Less(i, j int) bool {
410	return (*l)[i].Key < (*l)[j].Key
411}