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