bevy_ecs/
intern.rs

1//! Provides types used to statically intern immutable values.
2//!
3//! Interning is a pattern used to save memory by deduplicating identical values,
4//! speed up code by shrinking the stack size of large types,
5//! and make comparisons for any type as fast as integers.
6
7use std::{
8    fmt::Debug,
9    hash::Hash,
10    ops::Deref,
11    sync::{OnceLock, PoisonError, RwLock},
12};
13
14use bevy_utils::HashSet;
15
16/// An interned value. Will stay valid until the end of the program and will not drop.
17///
18/// For details on interning, see [the module level docs](self).
19///
20/// # Comparisons
21///
22/// Interned values use reference equality, meaning they implement [`Eq`]
23/// and [`Hash`] regardless of whether `T` implements these traits.
24/// Two interned values are only guaranteed to compare equal if they were interned using
25/// the same [`Interner`] instance.
26// NOTE: This type must NEVER implement Borrow since it does not obey that trait's invariants.
27///
28/// ```
29/// # use bevy_ecs::intern::*;
30/// #[derive(PartialEq, Eq, Hash, Debug)]
31/// struct Value(i32);
32/// impl Internable for Value {
33///     // ...
34/// # fn leak(&self) -> &'static Self { Box::leak(Box::new(Value(self.0))) }
35/// # fn ref_eq(&self, other: &Self) -> bool { std::ptr::eq(self, other ) }
36/// # fn ref_hash<H: std::hash::Hasher>(&self, state: &mut H) { std::ptr::hash(self, state); }
37/// }
38/// let interner_1 = Interner::new();
39/// let interner_2 = Interner::new();
40/// // Even though both values are identical, their interned forms do not
41/// // compare equal as they use different interner instances.
42/// assert_ne!(interner_1.intern(&Value(42)), interner_2.intern(&Value(42)));
43/// ```
44pub struct Interned<T: ?Sized + 'static>(pub &'static T);
45
46impl<T: ?Sized> Deref for Interned<T> {
47    type Target = T;
48
49    fn deref(&self) -> &Self::Target {
50        self.0
51    }
52}
53
54impl<T: ?Sized> Clone for Interned<T> {
55    fn clone(&self) -> Self {
56        *self
57    }
58}
59
60impl<T: ?Sized> Copy for Interned<T> {}
61
62// Two Interned<T> should only be equal if they are clones from the same instance.
63// Therefore, we only use the pointer to determine equality.
64impl<T: ?Sized + Internable> PartialEq for Interned<T> {
65    fn eq(&self, other: &Self) -> bool {
66        self.0.ref_eq(other.0)
67    }
68}
69
70impl<T: ?Sized + Internable> Eq for Interned<T> {}
71
72// Important: This must be kept in sync with the PartialEq/Eq implementation
73impl<T: ?Sized + Internable> Hash for Interned<T> {
74    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
75        self.0.ref_hash(state);
76    }
77}
78
79impl<T: ?Sized + Debug> Debug for Interned<T> {
80    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
81        self.0.fmt(f)
82    }
83}
84
85impl<T> From<&Interned<T>> for Interned<T> {
86    fn from(value: &Interned<T>) -> Self {
87        *value
88    }
89}
90
91/// A trait for internable values.
92///
93/// This is used by [`Interner<T>`] to create static references for values that are interned.
94pub trait Internable: Hash + Eq {
95    /// Creates a static reference to `self`, possibly leaking memory.
96    fn leak(&self) -> &'static Self;
97
98    /// Returns `true` if the two references point to the same value.
99    fn ref_eq(&self, other: &Self) -> bool;
100
101    /// Feeds the reference to the hasher.
102    fn ref_hash<H: std::hash::Hasher>(&self, state: &mut H);
103}
104
105impl Internable for str {
106    fn leak(&self) -> &'static Self {
107        let str = self.to_owned().into_boxed_str();
108        Box::leak(str)
109    }
110
111    fn ref_eq(&self, other: &Self) -> bool {
112        self.as_ptr() == other.as_ptr() && self.len() == other.len()
113    }
114
115    fn ref_hash<H: std::hash::Hasher>(&self, state: &mut H) {
116        self.len().hash(state);
117        self.as_ptr().hash(state);
118    }
119}
120
121/// A thread-safe interner which can be used to create [`Interned<T>`] from `&T`
122///
123/// For details on interning, see [the module level docs](self).
124///
125/// The implementation ensures that two equal values return two equal [`Interned<T>`] values.
126///
127/// To use an [`Interner<T>`], `T` must implement [`Internable`].
128pub struct Interner<T: ?Sized + 'static>(OnceLock<RwLock<HashSet<&'static T>>>);
129
130impl<T: ?Sized> Interner<T> {
131    /// Creates a new empty interner
132    pub const fn new() -> Self {
133        Self(OnceLock::new())
134    }
135}
136
137impl<T: Internable + ?Sized> Interner<T> {
138    /// Return the [`Interned<T>`] corresponding to `value`.
139    ///
140    /// If it is called the first time for `value`, it will possibly leak the value and return an
141    /// [`Interned<T>`] using the obtained static reference. Subsequent calls for the same `value`
142    /// will return [`Interned<T>`] using the same static reference.
143    pub fn intern(&self, value: &T) -> Interned<T> {
144        let lock = self.0.get_or_init(Default::default);
145        {
146            let set = lock.read().unwrap_or_else(PoisonError::into_inner);
147            if let Some(value) = set.get(value) {
148                return Interned(*value);
149            }
150        }
151        {
152            let mut set = lock.write().unwrap_or_else(PoisonError::into_inner);
153            if let Some(value) = set.get(value) {
154                Interned(*value)
155            } else {
156                let leaked = value.leak();
157                set.insert(leaked);
158                Interned(leaked)
159            }
160        }
161    }
162}
163
164impl<T: ?Sized> Default for Interner<T> {
165    fn default() -> Self {
166        Self::new()
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use std::{
173        collections::hash_map::DefaultHasher,
174        hash::{Hash, Hasher},
175    };
176
177    use crate::intern::{Internable, Interned, Interner};
178
179    #[test]
180    fn zero_sized_type() {
181        #[derive(PartialEq, Eq, Hash, Debug)]
182        pub struct A;
183
184        impl Internable for A {
185            fn leak(&self) -> &'static Self {
186                &A
187            }
188
189            fn ref_eq(&self, other: &Self) -> bool {
190                std::ptr::eq(self, other)
191            }
192
193            fn ref_hash<H: Hasher>(&self, state: &mut H) {
194                std::ptr::hash(self, state);
195            }
196        }
197
198        let interner = Interner::default();
199        let x = interner.intern(&A);
200        let y = interner.intern(&A);
201        assert_eq!(x, y);
202    }
203
204    #[test]
205    fn fieldless_enum() {
206        #[derive(PartialEq, Eq, Hash, Debug, Clone)]
207        pub enum A {
208            X,
209            Y,
210        }
211
212        impl Internable for A {
213            fn leak(&self) -> &'static Self {
214                match self {
215                    A::X => &A::X,
216                    A::Y => &A::Y,
217                }
218            }
219
220            fn ref_eq(&self, other: &Self) -> bool {
221                std::ptr::eq(self, other)
222            }
223
224            fn ref_hash<H: Hasher>(&self, state: &mut H) {
225                std::ptr::hash(self, state);
226            }
227        }
228
229        let interner = Interner::default();
230        let x = interner.intern(&A::X);
231        let y = interner.intern(&A::Y);
232        assert_ne!(x, y);
233    }
234
235    #[test]
236    fn static_sub_strings() {
237        let str = "ABC ABC";
238        let a = &str[0..3];
239        let b = &str[4..7];
240        // Same contents
241        assert_eq!(a, b);
242        let x = Interned(a);
243        let y = Interned(b);
244        // Different pointers
245        assert_ne!(x, y);
246        let interner = Interner::default();
247        let x = interner.intern(a);
248        let y = interner.intern(b);
249        // Same pointers returned by interner
250        assert_eq!(x, y);
251    }
252
253    #[test]
254    fn same_interned_instance() {
255        let a = Interned("A");
256        let b = a;
257
258        assert_eq!(a, b);
259
260        let mut hasher = DefaultHasher::default();
261        a.hash(&mut hasher);
262        let hash_a = hasher.finish();
263
264        let mut hasher = DefaultHasher::default();
265        b.hash(&mut hasher);
266        let hash_b = hasher.finish();
267
268        assert_eq!(hash_a, hash_b);
269    }
270
271    #[test]
272    fn same_interned_content() {
273        let a = Interned::<str>(Box::leak(Box::new("A".to_string())));
274        let b = Interned::<str>(Box::leak(Box::new("A".to_string())));
275
276        assert_ne!(a, b);
277    }
278
279    #[test]
280    fn different_interned_content() {
281        let a = Interned::<str>("A");
282        let b = Interned::<str>("B");
283
284        assert_ne!(a, b);
285    }
286}
bevy_ecs/intern.rs

bevy_ecs/
intern.rs
