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

bevy_ecs/
intern.rs
