metrics/
key.rs

1use crate::{atomics::AtomicU64, cow::Cow, IntoLabels, KeyHasher, Label, SharedString};
2use std::{
3    borrow::Borrow,
4    cmp, fmt,
5    hash::{Hash, Hasher},
6    slice::Iter,
7    sync::atomic::{AtomicBool, Ordering},
8};
9
10const NO_LABELS: [Label; 0] = [];
11
12/// Name component of a key.
13#[derive(Clone, Debug, Eq, Hash, PartialEq, PartialOrd, Ord)]
14pub struct KeyName(SharedString);
15
16impl KeyName {
17    /// Creates a `KeyName` from a static string.
18    pub const fn from_const_str(name: &'static str) -> Self {
19        KeyName(SharedString::const_str(name))
20    }
21
22    /// Gets a reference to the string used for this name.
23    pub fn as_str(&self) -> &str {
24        &self.0
25    }
26
27    /// Consumes this [`KeyName`], returning the inner [`SharedString`].
28    pub fn into_inner(self) -> SharedString {
29        self.0
30    }
31}
32
33impl<T> From<T> for KeyName
34where
35    T: Into<SharedString>,
36{
37    fn from(name: T) -> Self {
38        KeyName(name.into())
39    }
40}
41
42impl Borrow<str> for KeyName {
43    fn borrow(&self) -> &str {
44        self.0.borrow()
45    }
46}
47
48impl From<KeyName> for std::borrow::Cow<'static, str> {
49    fn from(name: KeyName) -> Self {
50        name.0.into()
51    }
52}
53
54/// A metric identifier.
55///
56/// A key represents both the name and labels of a metric.
57///
58/// # Safety
59/// Clippy will report any usage of `Key` as the key of a map/set as "mutable key type", meaning
60/// that it believes that there is interior mutability present which could lead to a key being
61/// hashed different over time.  That behavior could lead to unexpected behavior, as standard
62/// maps/sets depend on keys having stable hashes over time, related to times when they must be
63/// recomputed as the internal storage is resized and items are moved around.
64///
65/// In this case, the `Hash` implementation of `Key` does _not_ depend on the fields which Clippy
66/// considers mutable (the atomics) and so it is actually safe against differing hashes being
67/// generated.  We personally allow this Clippy lint in places where we store the key, such as
68/// helper types in the `metrics-util` crate, and you may need to do the same if you're using it in
69/// such a way as well.
70#[derive(Debug)]
71pub struct Key {
72    name: KeyName,
73    labels: Cow<'static, [Label]>,
74    hashed: AtomicBool,
75    hash: AtomicU64,
76}
77
78impl Key {
79    /// Creates a [`Key`] from a name.
80    pub fn from_name<N>(name: N) -> Self
81    where
82        N: Into<KeyName>,
83    {
84        let name = name.into();
85        let labels = Cow::from_owned(Vec::new());
86
87        Self::builder(name, labels)
88    }
89
90    /// Creates a [`Key`] from a name and set of labels.
91    pub fn from_parts<N, L>(name: N, labels: L) -> Self
92    where
93        N: Into<KeyName>,
94        L: IntoLabels,
95    {
96        let name = name.into();
97        let labels = Cow::from_owned(labels.into_labels());
98
99        Self::builder(name, labels)
100    }
101
102    /// Creates a [`Key`] from a non-static name and a static set of labels.
103    pub fn from_static_labels<N>(name: N, labels: &'static [Label]) -> Self
104    where
105        N: Into<KeyName>,
106    {
107        Self {
108            name: name.into(),
109            labels: Cow::const_slice(labels),
110            hashed: AtomicBool::new(false),
111            hash: AtomicU64::new(0),
112        }
113    }
114
115    /// Creates a [`Key`] from a static name.
116    ///
117    /// This function is `const`, so it can be used in a static context.
118    pub const fn from_static_name(name: &'static str) -> Self {
119        Self::from_static_parts(name, &NO_LABELS)
120    }
121
122    /// Creates a [`Key`] from a static name and static set of labels.
123    ///
124    /// This function is `const`, so it can be used in a static context.
125    pub const fn from_static_parts(name: &'static str, labels: &'static [Label]) -> Self {
126        Self {
127            name: KeyName::from_const_str(name),
128            labels: Cow::const_slice(labels),
129            hashed: AtomicBool::new(false),
130            hash: AtomicU64::new(0),
131        }
132    }
133
134    fn builder(name: KeyName, labels: Cow<'static, [Label]>) -> Self {
135        let hash = generate_key_hash(&name, &labels);
136
137        Self { name, labels, hashed: AtomicBool::new(true), hash: AtomicU64::new(hash) }
138    }
139
140    /// Name of this key.
141    pub fn name(&self) -> &str {
142        self.name.0.as_ref()
143    }
144
145    /// Name of this key as a [`KeyName`]
146    pub fn name_shared(&self) -> KeyName {
147        self.name.clone()
148    }
149
150    /// Labels of this key, if they exist.
151    pub fn labels(&self) -> Iter<'_, Label> {
152        self.labels.iter()
153    }
154
155    /// Consumes this [`Key`], returning the name parts and any labels.
156    pub fn into_parts(self) -> (KeyName, Vec<Label>) {
157        (self.name, self.labels.into_owned())
158    }
159
160    /// Clones this [`Key`], and expands the existing set of labels.
161    pub fn with_extra_labels(&self, extra_labels: Vec<Label>) -> Self {
162        if extra_labels.is_empty() {
163            return self.clone();
164        }
165
166        let name = self.name.clone();
167        let mut labels = self.labels.clone().into_owned();
168        labels.extend(extra_labels);
169
170        Self::builder(name, labels.into())
171    }
172
173    /// Gets the hash value for this key.
174    pub fn get_hash(&self) -> u64 {
175        if self.hashed.load(Ordering::Acquire) {
176            self.hash.load(Ordering::Acquire)
177        } else {
178            let hash = generate_key_hash(&self.name, &self.labels);
179            self.hash.store(hash, Ordering::Release);
180            self.hashed.store(true, Ordering::Release);
181            hash
182        }
183    }
184}
185
186fn generate_key_hash(name: &KeyName, labels: &Cow<'static, [Label]>) -> u64 {
187    let mut hasher = KeyHasher::default();
188    key_hasher_impl(&mut hasher, name, labels);
189    hasher.finish()
190}
191
192fn key_hasher_impl<H: Hasher>(state: &mut H, name: &KeyName, labels: &Cow<'static, [Label]>) {
193    name.0.hash(state);
194    labels.len().hash(state);
195    match labels.len() {
196        0 => {}
197        1 => labels[0].hash(state),
198        2 => {
199            if labels[0] < labels[1] {
200                labels[0].hash(state);
201                labels[1].hash(state);
202            } else {
203                labels[1].hash(state);
204                labels[0].hash(state);
205            }
206        }
207        n if n < 8 => {
208            let mut labels_sort_map: [u8; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
209            labels_sort_map[..n].sort_by_key(|i| labels[*i as usize].key());
210            for i in 0..n {
211                labels[labels_sort_map[i] as usize].hash(state)
212            }
213        }
214        n => {
215            let mut labels_sort_map: Vec<usize> = (0..n).collect();
216            labels_sort_map.sort_by_key(|i| labels[*i].key());
217            for i in 0..n {
218                labels[labels_sort_map[i]].hash(state)
219            }
220        }
221    }
222}
223
224impl Clone for Key {
225    fn clone(&self) -> Self {
226        Self {
227            name: self.name.clone(),
228            labels: self.labels.clone(),
229            hashed: AtomicBool::new(self.hashed.load(Ordering::Acquire)),
230            hash: AtomicU64::new(self.hash.load(Ordering::Acquire)),
231        }
232    }
233}
234
235impl PartialEq for Key {
236    fn eq(&self, other: &Self) -> bool {
237        if self.name != other.name {
238            return false;
239        }
240        if self.labels.len() != other.labels.len() {
241            return false;
242        }
243        match self.labels.len() {
244            0 => true,
245            1 => self.labels[0] == other.labels[0],
246            2 => {
247                if self.labels[0] == other.labels[0] {
248                    self.labels[1] == other.labels[1]
249                } else if self.labels[0] == other.labels[1] {
250                    self.labels[1] == other.labels[0]
251                } else {
252                    false
253                }
254            }
255            n if n < 8 => {
256                let mut labels_sort_map: [u8; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
257                labels_sort_map[..n].sort_by_key(|i| self.labels[*i as usize].key());
258                let mut his_labels_sort_map: [u8; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
259                his_labels_sort_map[..n].sort_by_key(|i| other.labels[*i as usize].key());
260                for i in 0..n {
261                    if self.labels[labels_sort_map[i] as usize]
262                        != other.labels[his_labels_sort_map[i] as usize]
263                    {
264                        return false;
265                    }
266                }
267                true
268            }
269            n => {
270                let mut labels_sort_map: Vec<usize> = (0..n).collect();
271                labels_sort_map.sort_by_key(|i| self.labels[*i].key());
272                let mut his_labels_sort_map: Vec<usize> = (0..n).collect();
273                his_labels_sort_map.sort_by_key(|i| other.labels[*i].key());
274                for i in 0..n {
275                    if self.labels[labels_sort_map[i]] != other.labels[his_labels_sort_map[i]] {
276                        return false;
277                    }
278                }
279                true
280            }
281        }
282    }
283}
284
285impl Eq for Key {}
286
287impl PartialOrd for Key {
288    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
289        Some(self.cmp(other))
290    }
291}
292
293impl Ord for Key {
294    fn cmp(&self, other: &Self) -> cmp::Ordering {
295        match (&self.name, self.labels.len()).cmp(&(&other.name, other.labels.len())) {
296            cmp::Ordering::Less => return cmp::Ordering::Less,
297            cmp::Ordering::Equal => {}
298            cmp::Ordering::Greater => return cmp::Ordering::Greater,
299        }
300        match self.labels.len() {
301            0 => cmp::Ordering::Equal,
302            1 => self.labels[0].cmp(&other.labels[0]),
303            n if n < 8 => {
304                let mut labels_sort_map: [u8; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
305                labels_sort_map[..n].sort_by_key(|i| self.labels[*i as usize].key());
306                let mut his_labels_sort_map: [u8; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
307                his_labels_sort_map[..n].sort_by_key(|i| other.labels[*i as usize].key());
308                for i in 0..n {
309                    match self.labels[labels_sort_map[i] as usize]
310                        .cmp(&other.labels[his_labels_sort_map[i] as usize])
311                    {
312                        cmp::Ordering::Less => return cmp::Ordering::Less,
313                        cmp::Ordering::Equal => {}
314                        cmp::Ordering::Greater => return cmp::Ordering::Greater,
315                    }
316                }
317                cmp::Ordering::Equal
318            }
319            n => {
320                let mut labels_sort_map: Vec<usize> = (0..n).collect();
321                labels_sort_map.sort_by_key(|i| self.labels[*i].key());
322                let mut his_labels_sort_map: Vec<usize> = (0..n).collect();
323                his_labels_sort_map.sort_by_key(|i| other.labels[*i].key());
324                for i in 0..n {
325                    match self.labels[labels_sort_map[i]].cmp(&other.labels[his_labels_sort_map[i]])
326                    {
327                        cmp::Ordering::Less => return cmp::Ordering::Less,
328                        cmp::Ordering::Equal => {}
329                        cmp::Ordering::Greater => return cmp::Ordering::Greater,
330                    }
331                }
332                cmp::Ordering::Equal
333            }
334        }
335    }
336}
337
338impl Hash for Key {
339    fn hash<H: Hasher>(&self, state: &mut H) {
340        key_hasher_impl(state, &self.name, &self.labels);
341    }
342}
343
344impl fmt::Display for Key {
345    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
346        if self.labels.is_empty() {
347            write!(f, "Key({})", self.name.as_str())
348        } else {
349            write!(f, "Key({}, [", self.name.as_str())?;
350            let mut first = true;
351            for label in self.labels.as_ref() {
352                if first {
353                    write!(f, "{} = {}", label.0, label.1)?;
354                    first = false;
355                } else {
356                    write!(f, ", {} = {}", label.0, label.1)?;
357                }
358            }
359            write!(f, "])")
360        }
361    }
362}
363
364impl<T> From<T> for Key
365where
366    T: Into<KeyName>,
367{
368    fn from(name: T) -> Self {
369        Self::from_name(name)
370    }
371}
372
373impl<N, L> From<(N, L)> for Key
374where
375    N: Into<KeyName>,
376    L: IntoLabels,
377{
378    fn from(parts: (N, L)) -> Self {
379        Self::from_parts(parts.0, parts.1)
380    }
381}
382
383#[cfg(test)]
384mod tests {
385    use super::Key;
386    use crate::{KeyName, Label};
387    use std::{cmp, collections::HashMap, ops::Deref, sync::Arc};
388
389    static BORROWED_NAME: &str = "name";
390    static FOOBAR_NAME: &str = "foobar";
391    static BORROWED_BASIC: Key = Key::from_static_name(BORROWED_NAME);
392    static LABELS: [Label; 1] = [Label::from_static_parts("key", "value")];
393    static BORROWED_LABELS: Key = Key::from_static_parts(BORROWED_NAME, &LABELS);
394
395    #[test]
396    fn test_key_ord_and_partialord() {
397        let keys_expected: Vec<Key> =
398            vec![Key::from_name("aaaa"), Key::from_name("bbbb"), Key::from_name("cccc")];
399
400        let keys_unsorted: Vec<Key> =
401            vec![Key::from_name("bbbb"), Key::from_name("cccc"), Key::from_name("aaaa")];
402
403        let keys = {
404            let mut keys = keys_unsorted.clone();
405            keys.sort();
406            keys
407        };
408        assert_eq!(keys, keys_expected);
409
410        let keys = {
411            let mut keys = keys_unsorted.clone();
412            keys.sort_by(|a, b| a.partial_cmp(b).unwrap());
413            keys
414        };
415        assert_eq!(keys, keys_expected);
416    }
417
418    #[test]
419    fn test_key_ord_total() {
420        let mut keys: Vec<_> = (1..16)
421            .flat_map(|i| {
422                let names: Vec<Label> =
423                    (0..i).map(|s| Label::new(format!("{}", s), format!("{}", s))).collect();
424                let key1 = Key::from_parts("key", names.clone());
425
426                // test that changing the order doesn't affect the value
427                let mut names_alt = names.clone();
428                names_alt.rotate_left(1);
429                let key2 = Key::from_parts("key", names_alt);
430                assert_eq!(key1, key2);
431
432                // check that the first element affects the order
433                names_alt = names.clone();
434                names_alt[0] = Label::new("x".to_string(), "0".to_string());
435                let key3 = Key::from_parts("key", names_alt);
436                assert_ne!(key1, key3);
437
438                // check that the last element affects the order
439                names_alt = names.clone();
440                names_alt[i - 1] = Label::new("x".to_string(), "0".to_string());
441                let key4 = Key::from_parts("key", names_alt);
442                assert_ne!(key1, key4);
443
444                [key1, key2, key3, key4]
445            })
446            .collect();
447        keys.push(Key::from_parts("key", vec![]));
448        keys.sort();
449        for i in 0..keys.len() {
450            for j in 0..keys.len() {
451                // check that the order is a total order
452                match (keys[i] == keys[j], keys[i].cmp(&keys[j])) {
453                    (true, cmp::Ordering::Equal) => {}
454                    (true, cmp::Ordering::Less) => panic!("at {} {} equal keys compared lt", i, j),
455                    (true, cmp::Ordering::Greater) => {
456                        panic!("at {} {} equal keys compared gt", i, j)
457                    }
458                    (false, cmp::Ordering::Equal) => {
459                        panic!("at {} {} unequal keys compared equal", i, j)
460                    }
461                    (false, cmp::Ordering::Less) => assert!(i < j),
462                    (false, cmp::Ordering::Greater) => assert!(i > j),
463                }
464            }
465        }
466    }
467
468    #[test]
469    fn test_key_eq_and_hash() {
470        let mut keys = HashMap::new();
471
472        let owned_basic: Key = Key::from_name("name");
473        assert_eq!(&owned_basic, &BORROWED_BASIC);
474
475        let previous = keys.insert(owned_basic, 42);
476        assert!(previous.is_none());
477
478        let previous = keys.get(&BORROWED_BASIC);
479        assert_eq!(previous, Some(&42));
480
481        let labels = LABELS.to_vec();
482        let owned_labels = Key::from_parts(BORROWED_NAME, labels);
483        assert_eq!(&owned_labels, &BORROWED_LABELS);
484
485        let previous = keys.insert(owned_labels, 43);
486        assert!(previous.is_none());
487
488        let previous = keys.get(&BORROWED_LABELS);
489        assert_eq!(previous, Some(&43));
490
491        let basic: Key = "constant_key".into();
492        let cloned_basic = basic.clone();
493        assert_eq!(basic, cloned_basic);
494
495        for i in 1..16 {
496            let names: Vec<Label> =
497                (0..i).map(|s| Label::new(format!("{}", s), format!("{}", s))).collect();
498            let key1 = Key::from_parts("key", names.clone());
499            let mut names_alt = names.clone();
500
501            // test that changing the order doesn't affect the hash
502            names_alt.rotate_left(1);
503            let key2 = Key::from_parts("key", names_alt);
504            assert_eq!(key1, key2);
505            assert_eq!(key1.get_hash(), key2.get_hash());
506
507            // check that the first element affects the hash
508            names_alt = names.clone();
509            names_alt[0] = Label::new("x".to_string(), "0".to_string());
510            let key2 = Key::from_parts("key", names_alt);
511            assert_ne!(key1, key2);
512            assert_ne!(key1.get_hash(), key2.get_hash());
513
514            // check that the last element affects the hash
515            names_alt = names.clone();
516            names_alt[i - 1] = Label::new("x".to_string(), "0".to_string());
517            let key2 = Key::from_parts("key", names_alt);
518            assert_ne!(key1, key2);
519            assert_ne!(key1.get_hash(), key2.get_hash());
520
521            // check that it differs from a key with no labels
522            let key2 = Key::from_parts("key", vec![]);
523            assert_ne!(key1, key2);
524            assert_ne!(key1.get_hash(), key2.get_hash());
525        }
526    }
527
528    #[test]
529    fn test_key_data_proper_display() {
530        let key1 = Key::from_name("foobar");
531        let result1 = key1.to_string();
532        assert_eq!(result1, "Key(foobar)");
533
534        let key2 = Key::from_parts(FOOBAR_NAME, vec![Label::new("system", "http")]);
535        let result2 = key2.to_string();
536        assert_eq!(result2, "Key(foobar, [system = http])");
537
538        let key3 = Key::from_parts(
539            FOOBAR_NAME,
540            vec![Label::new("system", "http"), Label::new("user", "joe")],
541        );
542        let result3 = key3.to_string();
543        assert_eq!(result3, "Key(foobar, [system = http, user = joe])");
544
545        let key4 = Key::from_parts(
546            FOOBAR_NAME,
547            vec![
548                Label::new("black", "black"),
549                Label::new("lives", "lives"),
550                Label::new("matter", "matter"),
551            ],
552        );
553        let result4 = key4.to_string();
554        assert_eq!(result4, "Key(foobar, [black = black, lives = lives, matter = matter])");
555    }
556
557    #[test]
558    fn test_key_name_equality() {
559        static KEY_NAME: &str = "key_name";
560
561        let borrowed_const = KeyName::from_const_str(KEY_NAME);
562        let borrowed_nonconst = KeyName::from(KEY_NAME);
563        let owned = KeyName::from(KEY_NAME.to_owned());
564
565        let shared_arc = Arc::from(KEY_NAME);
566        let shared = KeyName::from(Arc::clone(&shared_arc));
567
568        assert_eq!(borrowed_const, borrowed_nonconst);
569        assert_eq!(borrowed_const.as_str(), borrowed_nonconst.as_str());
570        assert_eq!(borrowed_const, owned);
571        assert_eq!(borrowed_const.as_str(), owned.as_str());
572        assert_eq!(borrowed_const, shared);
573        assert_eq!(borrowed_const.as_str(), shared.as_str());
574    }
575
576    #[test]
577    fn test_shared_key_name_drop_logic() {
578        let shared_arc = Arc::from("foo");
579        let shared = KeyName::from(Arc::clone(&shared_arc));
580
581        assert_eq!(shared_arc.deref(), shared.as_str());
582
583        assert_eq!(Arc::strong_count(&shared_arc), 2);
584        drop(shared);
585        assert_eq!(Arc::strong_count(&shared_arc), 1);
586
587        let shared_weak = Arc::downgrade(&shared_arc);
588        assert_eq!(Arc::strong_count(&shared_arc), 1);
589
590        let shared = KeyName::from(Arc::clone(&shared_arc));
591        assert_eq!(shared_arc.deref(), shared.as_str());
592        assert_eq!(Arc::strong_count(&shared_arc), 2);
593
594        drop(shared_arc);
595        assert_eq!(shared_weak.strong_count(), 1);
596
597        drop(shared);
598        assert_eq!(shared_weak.strong_count(), 0);
599    }
600}
metrics/key.rs

metrics/
key.rs
