set.go

Documentation: go.opentelemetry.io/otel/attribute

     1  // Copyright The OpenTelemetry Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package attribute // import "go.opentelemetry.io/otel/attribute"
    16  
    17  import (
    18  	"encoding/json"
    19  	"reflect"
    20  	"sort"
    21  	"sync"
    22  )
    23  
    24  type (
    25  	// Set is the representation for a distinct attribute set. It manages an
    26  	// immutable set of attributes, with an internal cache for storing
    27  	// attribute encodings.
    28  	//
    29  	// This type supports the Equivalent method of comparison using values of
    30  	// type Distinct.
    31  	Set struct {
    32  		equivalent Distinct
    33  	}
    34  
    35  	// Distinct wraps a variable-size array of KeyValue, constructed with keys
    36  	// in sorted order. This can be used as a map key or for equality checking
    37  	// between Sets.
    38  	Distinct struct {
    39  		iface interface{}
    40  	}
    41  
    42  	// Sortable implements sort.Interface, used for sorting KeyValue. This is
    43  	// an exported type to support a memory optimization. A pointer to one of
    44  	// these is needed for the call to sort.Stable(), which the caller may
    45  	// provide in order to avoid an allocation. See NewSetWithSortable().
    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  	// sortables is a pool of Sortables used to create Sets with a user does
    61  	// not provide one.
    62  	sortables = sync.Pool{
    63  		New: func() interface{} { return new(Sortable) },
    64  	}
    65  )
    66  
    67  // EmptySet returns a reference to a Set with no elements.
    68  //
    69  // This is a convenience provided for optimized calling utility.
    70  func EmptySet() *Set {
    71  	return emptySet
    72  }
    73  
    74  // reflectValue abbreviates reflect.ValueOf(d).
    75  func (d Distinct) reflectValue() reflect.Value {
    76  	return reflect.ValueOf(d.iface)
    77  }
    78  
    79  // Valid returns true if this value refers to a valid Set.
    80  func (d Distinct) Valid() bool {
    81  	return d.iface != nil
    82  }
    83  
    84  // Len returns the number of attributes in this set.
    85  func (l *Set) Len() int {
    86  	if l == nil || !l.equivalent.Valid() {
    87  		return 0
    88  	}
    89  	return l.equivalent.reflectValue().Len()
    90  }
    91  
    92  // Get returns the KeyValue at ordered position idx in this set.
    93  func (l *Set) Get(idx int) (KeyValue, bool) {
    94  	if l == nil || !l.equivalent.Valid() {
    95  		return KeyValue{}, false
    96  	}
    97  	value := l.equivalent.reflectValue()
    98  
    99  	if idx >= 0 && idx < value.Len() {
   100  		// Note: The Go compiler successfully avoids an allocation for
   101  		// the interface{} conversion here:
   102  		return value.Index(idx).Interface().(KeyValue), true
   103  	}
   104  
   105  	return KeyValue{}, false
   106  }
   107  
   108  // Value returns the value of a specified key in this set.
   109  func (l *Set) Value(k Key) (Value, bool) {
   110  	if l == nil || !l.equivalent.Valid() {
   111  		return Value{}, false
   112  	}
   113  	rValue := l.equivalent.reflectValue()
   114  	vlen := rValue.Len()
   115  
   116  	idx := sort.Search(vlen, func(idx int) bool {
   117  		return rValue.Index(idx).Interface().(KeyValue).Key >= k
   118  	})
   119  	if idx >= vlen {
   120  		return Value{}, false
   121  	}
   122  	keyValue := rValue.Index(idx).Interface().(KeyValue)
   123  	if k == keyValue.Key {
   124  		return keyValue.Value, true
   125  	}
   126  	return Value{}, false
   127  }
   128  
   129  // HasValue tests whether a key is defined in this set.
   130  func (l *Set) HasValue(k Key) bool {
   131  	if l == nil {
   132  		return false
   133  	}
   134  	_, ok := l.Value(k)
   135  	return ok
   136  }
   137  
   138  // Iter returns an iterator for visiting the attributes in this set.
   139  func (l *Set) Iter() Iterator {
   140  	return Iterator{
   141  		storage: l,
   142  		idx:     -1,
   143  	}
   144  }
   145  
   146  // ToSlice returns the set of attributes belonging to this set, sorted, where
   147  // keys appear no more than once.
   148  func (l *Set) ToSlice() []KeyValue {
   149  	iter := l.Iter()
   150  	return iter.ToSlice()
   151  }
   152  
   153  // Equivalent returns a value that may be used as a map key. The Distinct type
   154  // guarantees that the result will equal the equivalent. Distinct value of any
   155  // attribute set with the same elements as this, where sets are made unique by
   156  // choosing the last value in the input for any given key.
   157  func (l *Set) Equivalent() Distinct {
   158  	if l == nil || !l.equivalent.Valid() {
   159  		return emptySet.equivalent
   160  	}
   161  	return l.equivalent
   162  }
   163  
   164  // Equals returns true if the argument set is equivalent to this set.
   165  func (l *Set) Equals(o *Set) bool {
   166  	return l.Equivalent() == o.Equivalent()
   167  }
   168  
   169  // Encoded returns the encoded form of this set, according to encoder.
   170  func (l *Set) Encoded(encoder Encoder) string {
   171  	if l == nil || encoder == nil {
   172  		return ""
   173  	}
   174  
   175  	return encoder.Encode(l.Iter())
   176  }
   177  
   178  func empty() Set {
   179  	return Set{
   180  		equivalent: emptySet.equivalent,
   181  	}
   182  }
   183  
   184  // NewSet returns a new Set. See the documentation for
   185  // NewSetWithSortableFiltered for more details.
   186  //
   187  // Except for empty sets, this method adds an additional allocation compared
   188  // with calls that include a Sortable.
   189  func NewSet(kvs ...KeyValue) Set {
   190  	// Check for empty set.
   191  	if len(kvs) == 0 {
   192  		return empty()
   193  	}
   194  	srt := sortables.Get().(*Sortable)
   195  	s, _ := NewSetWithSortableFiltered(kvs, srt, nil)
   196  	sortables.Put(srt)
   197  	return s
   198  }
   199  
   200  // NewSetWithSortable returns a new Set. See the documentation for
   201  // NewSetWithSortableFiltered for more details.
   202  //
   203  // This call includes a Sortable option as a memory optimization.
   204  func NewSetWithSortable(kvs []KeyValue, tmp *Sortable) Set {
   205  	// Check for empty set.
   206  	if len(kvs) == 0 {
   207  		return empty()
   208  	}
   209  	s, _ := NewSetWithSortableFiltered(kvs, tmp, nil)
   210  	return s
   211  }
   212  
   213  // NewSetWithFiltered returns a new Set. See the documentation for
   214  // NewSetWithSortableFiltered for more details.
   215  //
   216  // This call includes a Filter to include/exclude attribute keys from the
   217  // return value. Excluded keys are returned as a slice of attribute values.
   218  func NewSetWithFiltered(kvs []KeyValue, filter Filter) (Set, []KeyValue) {
   219  	// Check for empty set.
   220  	if len(kvs) == 0 {
   221  		return empty(), nil
   222  	}
   223  	srt := sortables.Get().(*Sortable)
   224  	s, filtered := NewSetWithSortableFiltered(kvs, srt, filter)
   225  	sortables.Put(srt)
   226  	return s, filtered
   227  }
   228  
   229  // NewSetWithSortableFiltered returns a new Set.
   230  //
   231  // Duplicate keys are eliminated by taking the last value.  This
   232  // re-orders the input slice so that unique last-values are contiguous
   233  // at the end of the slice.
   234  //
   235  // This ensures the following:
   236  //
   237  // - Last-value-wins semantics
   238  // - Caller sees the reordering, but doesn't lose values
   239  // - Repeated call preserve last-value wins.
   240  //
   241  // Note that methods are defined on Set, although this returns Set. Callers
   242  // can avoid memory allocations by:
   243  //
   244  // - allocating a Sortable for use as a temporary in this method
   245  // - allocating a Set for storing the return value of this constructor.
   246  //
   247  // The result maintains a cache of encoded attributes, by attribute.EncoderID.
   248  // This value should not be copied after its first use.
   249  //
   250  // The second []KeyValue return value is a list of attributes that were
   251  // excluded by the Filter (if non-nil).
   252  func NewSetWithSortableFiltered(kvs []KeyValue, tmp *Sortable, filter Filter) (Set, []KeyValue) {
   253  	// Check for empty set.
   254  	if len(kvs) == 0 {
   255  		return empty(), nil
   256  	}
   257  
   258  	*tmp = kvs
   259  
   260  	// Stable sort so the following de-duplication can implement
   261  	// last-value-wins semantics.
   262  	sort.Stable(tmp)
   263  
   264  	*tmp = nil
   265  
   266  	position := len(kvs) - 1
   267  	offset := position - 1
   268  
   269  	// The requirements stated above require that the stable
   270  	// result be placed in the end of the input slice, while
   271  	// overwritten values are swapped to the beginning.
   272  	//
   273  	// De-duplicate with last-value-wins semantics.  Preserve
   274  	// duplicate values at the beginning of the input slice.
   275  	for ; offset >= 0; offset-- {
   276  		if kvs[offset].Key == kvs[position].Key {
   277  			continue
   278  		}
   279  		position--
   280  		kvs[offset], kvs[position] = kvs[position], kvs[offset]
   281  	}
   282  	if filter != nil {
   283  		return filterSet(kvs[position:], filter)
   284  	}
   285  	return Set{
   286  		equivalent: computeDistinct(kvs[position:]),
   287  	}, nil
   288  }
   289  
   290  // filterSet reorders kvs so that included keys are contiguous at the end of
   291  // the slice, while excluded keys precede the included keys.
   292  func filterSet(kvs []KeyValue, filter Filter) (Set, []KeyValue) {
   293  	var excluded []KeyValue
   294  
   295  	// Move attributes that do not match the filter so they're adjacent before
   296  	// calling computeDistinct().
   297  	distinctPosition := len(kvs)
   298  
   299  	// Swap indistinct keys forward and distinct keys toward the
   300  	// end of the slice.
   301  	offset := len(kvs) - 1
   302  	for ; offset >= 0; offset-- {
   303  		if filter(kvs[offset]) {
   304  			distinctPosition--
   305  			kvs[offset], kvs[distinctPosition] = kvs[distinctPosition], kvs[offset]
   306  			continue
   307  		}
   308  	}
   309  	excluded = kvs[:distinctPosition]
   310  
   311  	return Set{
   312  		equivalent: computeDistinct(kvs[distinctPosition:]),
   313  	}, excluded
   314  }
   315  
   316  // Filter returns a filtered copy of this Set. See the documentation for
   317  // NewSetWithSortableFiltered for more details.
   318  func (l *Set) Filter(re Filter) (Set, []KeyValue) {
   319  	if re == nil {
   320  		return Set{
   321  			equivalent: l.equivalent,
   322  		}, nil
   323  	}
   324  
   325  	// Note: This could be refactored to avoid the temporary slice
   326  	// allocation, if it proves to be expensive.
   327  	return filterSet(l.ToSlice(), re)
   328  }
   329  
   330  // computeDistinct returns a Distinct using either the fixed- or
   331  // reflect-oriented code path, depending on the size of the input. The input
   332  // slice is assumed to already be sorted and de-duplicated.
   333  func computeDistinct(kvs []KeyValue) Distinct {
   334  	iface := computeDistinctFixed(kvs)
   335  	if iface == nil {
   336  		iface = computeDistinctReflect(kvs)
   337  	}
   338  	return Distinct{
   339  		iface: iface,
   340  	}
   341  }
   342  
   343  // computeDistinctFixed computes a Distinct for small slices. It returns nil
   344  // if the input is too large for this code path.
   345  func computeDistinctFixed(kvs []KeyValue) interface{} {
   346  	switch len(kvs) {
   347  	case 1:
   348  		ptr := new([1]KeyValue)
   349  		copy((*ptr)[:], kvs)
   350  		return *ptr
   351  	case 2:
   352  		ptr := new([2]KeyValue)
   353  		copy((*ptr)[:], kvs)
   354  		return *ptr
   355  	case 3:
   356  		ptr := new([3]KeyValue)
   357  		copy((*ptr)[:], kvs)
   358  		return *ptr
   359  	case 4:
   360  		ptr := new([4]KeyValue)
   361  		copy((*ptr)[:], kvs)
   362  		return *ptr
   363  	case 5:
   364  		ptr := new([5]KeyValue)
   365  		copy((*ptr)[:], kvs)
   366  		return *ptr
   367  	case 6:
   368  		ptr := new([6]KeyValue)
   369  		copy((*ptr)[:], kvs)
   370  		return *ptr
   371  	case 7:
   372  		ptr := new([7]KeyValue)
   373  		copy((*ptr)[:], kvs)
   374  		return *ptr
   375  	case 8:
   376  		ptr := new([8]KeyValue)
   377  		copy((*ptr)[:], kvs)
   378  		return *ptr
   379  	case 9:
   380  		ptr := new([9]KeyValue)
   381  		copy((*ptr)[:], kvs)
   382  		return *ptr
   383  	case 10:
   384  		ptr := new([10]KeyValue)
   385  		copy((*ptr)[:], kvs)
   386  		return *ptr
   387  	default:
   388  		return nil
   389  	}
   390  }
   391  
   392  // computeDistinctReflect computes a Distinct using reflection, works for any
   393  // size input.
   394  func computeDistinctReflect(kvs []KeyValue) interface{} {
   395  	at := reflect.New(reflect.ArrayOf(len(kvs), keyValueType)).Elem()
   396  	for i, keyValue := range kvs {
   397  		*(at.Index(i).Addr().Interface().(*KeyValue)) = keyValue
   398  	}
   399  	return at.Interface()
   400  }
   401  
   402  // MarshalJSON returns the JSON encoding of the Set.
   403  func (l *Set) MarshalJSON() ([]byte, error) {
   404  	return json.Marshal(l.equivalent.iface)
   405  }
   406  
   407  // MarshalLog is the marshaling function used by the logging system to represent this exporter.
   408  func (l Set) MarshalLog() interface{} {
   409  	kvs := make(map[string]string)
   410  	for _, kv := range l.ToSlice() {
   411  		kvs[string(kv.Key)] = kv.Value.Emit()
   412  	}
   413  	return kvs
   414  }
   415  
   416  // Len implements sort.Interface.
   417  func (l *Sortable) Len() int {
   418  	return len(*l)
   419  }
   420  
   421  // Swap implements sort.Interface.
   422  func (l *Sortable) Swap(i, j int) {
   423  	(*l)[i], (*l)[j] = (*l)[j], (*l)[i]
   424  }
   425  
   426  // Less implements sort.Interface.
   427  func (l *Sortable) Less(i, j int) bool {
   428  	return (*l)[i].Key < (*l)[j].Key
   429  }
   430
View as plain text