compiler/rustc_data_structures/src/intern.rs

   1 use std::cmp::Ordering;
   2 use std::hash::{Hash, Hasher};
   3 use std::ops::Deref;
   4 use std::ptr;
   5
   6 mod private {
   7     #[derive(Clone, Copy, Debug)]
   8     pub struct PrivateZst;
   9 }
  10
  11 /// A reference to a value that is interned, and is known to be unique.
  12 ///
  13 /// Note that it is possible to have a `T` and a `Interned<T>` that are (or
  14 /// refer to) equal but different values. But if you have two different
  15 /// `Interned<T>`s, they both refer to the same value, at a single location in
  16 /// memory. This means that equality and hashing can be done on the value's
  17 /// address rather than the value's contents, which can improve performance.
  18 ///
  19 /// The `PrivateZst` field means you can pattern match with `Interned(v, _)`
  20 /// but you can only construct a `Interned` with `new_unchecked`, and not
  21 /// directly.
  22 #[derive(Debug)]
  23 #[cfg_attr(not(bootstrap), rustc_pass_by_value)]
  24 pub struct Interned<'a, T>(pub &'a T, pub private::PrivateZst);
  25
  26 impl<'a, T> Interned<'a, T> {
  27     /// Create a new `Interned` value. The value referred to *must* be interned
  28     /// and thus be unique, and it *must* remain unique in the future. This
  29     /// function has `_unchecked` in the name but is not `unsafe`, because if
  30     /// the uniqueness condition is violated condition it will cause incorrect
  31     /// behaviour but will not affect memory safety.
  32     #[inline]
  33     pub const fn new_unchecked(t: &'a T) -> Self {
  34         Interned(t, private::PrivateZst)
  35     }
  36 }
  37
  38 impl<'a, T> Clone for Interned<'a, T> {
  39     fn clone(&self) -> Self {
  40         *self
  41     }
  42 }
  43
  44 impl<'a, T> Copy for Interned<'a, T> {}
  45
  46 impl<'a, T> Deref for Interned<'a, T> {
  47     type Target = T;
  48
  49     #[inline]
  50     fn deref(&self) -> &T {
  51         self.0
  52     }
  53 }
  54
  55 impl<'a, T> PartialEq for Interned<'a, T> {
  56     #[inline]
  57     fn eq(&self, other: &Self) -> bool {
  58         // Pointer equality implies equality, due to the uniqueness constraint.
  59         ptr::eq(self.0, other.0)
  60     }
  61 }
  62
  63 impl<'a, T> Eq for Interned<'a, T> {}
  64
  65 // In practice you can't intern any `T` that doesn't implement `Eq`, because
  66 // that's needed for hashing. Therefore, we won't be interning any `T` that
  67 // implements `PartialOrd` without also implementing `Ord`. So we can have the
  68 // bound `T: Ord` here and avoid duplication with the `Ord` impl below.
  69 impl<'a, T: Ord> PartialOrd for Interned<'a, T> {
  70     fn partial_cmp(&self, other: &Interned<'a, T>) -> Option<Ordering> {
  71         Some(self.cmp(other))
  72     }
  73 }
  74
  75 impl<'a, T: Ord> Ord for Interned<'a, T> {
  76     fn cmp(&self, other: &Interned<'a, T>) -> Ordering {
  77         // Pointer equality implies equality, due to the uniqueness constraint,
  78         // but the contents must be compared otherwise.
  79         if ptr::eq(self.0, other.0) {
  80             Ordering::Equal
  81         } else {
  82             let res = self.0.cmp(&other.0);
  83             debug_assert_ne!(res, Ordering::Equal);
  84             res
  85         }
  86     }
  87 }
  88
  89 impl<'a, T> Hash for Interned<'a, T> {
  90     #[inline]
  91     fn hash<H: Hasher>(&self, s: &mut H) {
  92         // Pointer hashing is sufficient, due to the uniqueness constraint.
  93         ptr::hash(self.0, s)
  94     }
  95 }
  96
  97 #[cfg(test)]
  98 mod tests;