solar_data_structures/
interned.rs

1// Modified from [`rustc_data_structures`](https://github.com/rust-lang/rust/blob/f82eb4d0a01e2dc782e582f7081439e172b858f9/compiler/rustc_data_structures/src/intern.rs).
2
3use std::{
4    cmp::Ordering,
5    fmt::{self, Debug},
6    hash::{Hash, Hasher},
7    ops::Deref,
8    ptr,
9};
10
11#[allow(unnameable_types)]
12mod private {
13    #[derive(Clone, Copy, Debug)]
14    pub struct PrivateZst;
15}
16
17/// A reference to a value that is interned, and is known to be unique.
18///
19/// Note that it is possible to have a `T` and a `Interned<T>` that are (or
20/// refer to) equal but different values. But if you have two different
21/// `Interned<T>`s, they both refer to the same value, at a single location in
22/// memory. This means that equality and hashing can be done on the value's
23/// address rather than the value's contents, which can improve performance.
24///
25/// The `PrivateZst` field means you can pattern match with `Interned(v, _)`
26/// but you can only construct a `Interned` with `new_unchecked`, and not
27/// directly.
28#[cfg_attr(feature = "nightly", rustc_pass_by_value)]
29pub struct Interned<'a, T>(pub &'a T, pub private::PrivateZst);
30
31impl<'a, T> Interned<'a, T> {
32    /// Create a new `Interned` value. The value referred to *must* be interned
33    /// and thus be unique, and it *must* remain unique in the future. This
34    /// function has `_unchecked` in the name but is not `unsafe`, because if
35    /// the uniqueness condition is violated condition it will cause incorrect
36    /// behaviour but will not affect memory safety.
37    #[inline]
38    pub const fn new_unchecked(t: &'a T) -> Self {
39        Interned(t, private::PrivateZst)
40    }
41}
42
43impl<T> Clone for Interned<'_, T> {
44    fn clone(&self) -> Self {
45        *self
46    }
47}
48
49impl<T> Copy for Interned<'_, T> {}
50
51impl<T> Deref for Interned<'_, T> {
52    type Target = T;
53
54    #[inline]
55    fn deref(&self) -> &T {
56        self.0
57    }
58}
59
60impl<T> PartialEq for Interned<'_, T> {
61    #[inline]
62    fn eq(&self, other: &Self) -> bool {
63        // Pointer equality implies equality, due to the uniqueness constraint.
64        ptr::eq(self.0, other.0)
65    }
66}
67
68impl<T> Eq for Interned<'_, T> {}
69
70impl<T: PartialOrd> PartialOrd for Interned<'_, T> {
71    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
72        // Pointer equality implies equality, due to the uniqueness constraint,
73        // but the contents must be compared otherwise.
74        if ptr::eq(self.0, other.0) {
75            Some(Ordering::Equal)
76        } else {
77            let res = self.0.partial_cmp(other.0);
78            debug_assert_ne!(res, Some(Ordering::Equal));
79            res
80        }
81    }
82}
83
84impl<T: Ord> Ord for Interned<'_, T> {
85    fn cmp(&self, other: &Self) -> Ordering {
86        // Pointer equality implies equality, due to the uniqueness constraint,
87        // but the contents must be compared otherwise.
88        if ptr::eq(self.0, other.0) {
89            Ordering::Equal
90        } else {
91            let res = self.0.cmp(other.0);
92            debug_assert_ne!(res, Ordering::Equal);
93            res
94        }
95    }
96}
97
98impl<T> Hash for Interned<'_, T> {
99    #[inline]
100    fn hash<H: Hasher>(&self, s: &mut H) {
101        // Pointer hashing is sufficient, due to the uniqueness constraint.
102        ptr::hash(self.0, s)
103    }
104}
105
106impl<T: Debug> Debug for Interned<'_, T> {
107    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108        self.0.fmt(f)
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115
116    #[derive(Debug)]
117    struct S(u32);
118
119    impl PartialEq for S {
120        fn eq(&self, _other: &Self) -> bool {
121            panic!("shouldn't be called");
122        }
123    }
124
125    impl Eq for S {}
126
127    #[allow(clippy::non_canonical_partial_ord_impl)]
128    impl PartialOrd for S {
129        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
130            // The `==` case should be handled by `Interned`.
131            assert_ne!(self.0, other.0);
132            self.0.partial_cmp(&other.0)
133        }
134    }
135
136    impl Ord for S {
137        fn cmp(&self, other: &Self) -> Ordering {
138            // The `==` case should be handled by `Interned`.
139            assert_ne!(self.0, other.0);
140            self.0.cmp(&other.0)
141        }
142    }
143
144    #[test]
145    fn test_uniq() {
146        let s1 = S(1);
147        let s2 = S(2);
148        let s3 = S(3);
149        let s4 = S(1); // violates uniqueness
150
151        let v1 = Interned::new_unchecked(&s1);
152        let v2 = Interned::new_unchecked(&s2);
153        let v3a = Interned::new_unchecked(&s3);
154        let v3b = Interned::new_unchecked(&s3);
155        let v4 = Interned::new_unchecked(&s4); // violates uniqueness
156
157        assert_ne!(v1, v2);
158        assert_ne!(v2, v3a);
159        assert_eq!(v1, v1);
160        assert_eq!(v3a, v3b);
161        assert_ne!(v1, v4); // same content but different addresses: not equal
162
163        assert_eq!(v1.cmp(&v2), Ordering::Less);
164        assert_eq!(v3a.cmp(&v2), Ordering::Greater);
165        assert_eq!(v1.cmp(&v1), Ordering::Equal); // only uses Interned::eq, not S::cmp
166        assert_eq!(v3a.cmp(&v3b), Ordering::Equal); // only uses Interned::eq, not S::cmp
167
168        assert_eq!(v1.partial_cmp(&v2), Some(Ordering::Less));
169        assert_eq!(v3a.partial_cmp(&v2), Some(Ordering::Greater));
170        assert_eq!(v1.partial_cmp(&v1), Some(Ordering::Equal)); // only uses Interned::eq, not S::cmp
171        assert_eq!(v3a.partial_cmp(&v3b), Some(Ordering::Equal)); // only uses Interned::eq, not S::cmp
172    }
173}
solar_data_structures/interned.rs

solar_data_structures/
interned.rs
