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

bevy_ecs/
intern.rs
