bevy_utils/
lib.rs

1#![cfg_attr(docsrs, feature(doc_auto_cfg))]
2#![allow(unsafe_code)]
3#![doc(
4    html_logo_url = "https://bevyengine.org/assets/icon.png",
5    html_favicon_url = "https://bevyengine.org/assets/icon.png"
6)]
7
8//! General utilities for first-party [Bevy] engine crates.
9//!
10//! [Bevy]: https://bevyengine.org/
11//!
12
13#[allow(missing_docs)]
14pub mod prelude {
15    pub use crate::default;
16}
17
18pub mod futures;
19mod short_names;
20pub use short_names::get_short_name;
21pub mod synccell;
22pub mod syncunsafecell;
23
24mod cow_arc;
25mod default;
26mod once;
27mod parallel_queue;
28
29pub use ahash::{AHasher, RandomState};
30pub use bevy_utils_proc_macros::*;
31pub use cow_arc::*;
32pub use default::default;
33pub use hashbrown;
34pub use parallel_queue::*;
35pub use tracing;
36pub use web_time::{Duration, Instant, SystemTime, SystemTimeError, TryFromFloatSecsError};
37
38use hashbrown::hash_map::RawEntryMut;
39use std::{
40    any::TypeId,
41    fmt::Debug,
42    hash::{BuildHasher, BuildHasherDefault, Hash, Hasher},
43    marker::PhantomData,
44    mem::ManuallyDrop,
45    ops::Deref,
46};
47
48#[cfg(not(target_arch = "wasm32"))]
49mod conditional_send {
50    /// Use [`ConditionalSend`] to mark an optional Send trait bound. Useful as on certain platforms (eg. WASM),
51    /// futures aren't Send.
52    pub trait ConditionalSend: Send {}
53    impl<T: Send> ConditionalSend for T {}
54}
55
56#[cfg(target_arch = "wasm32")]
57#[allow(missing_docs)]
58mod conditional_send {
59    pub trait ConditionalSend {}
60    impl<T> ConditionalSend for T {}
61}
62
63pub use conditional_send::*;
64
65/// Use [`ConditionalSendFuture`] for a future with an optional Send trait bound, as on certain platforms (eg. WASM),
66/// futures aren't Send.
67pub trait ConditionalSendFuture: std::future::Future + ConditionalSend {}
68impl<T: std::future::Future + ConditionalSend> ConditionalSendFuture for T {}
69
70/// An owned and dynamically typed Future used when you can't statically type your result or need to add some indirection.
71pub type BoxedFuture<'a, T> = std::pin::Pin<Box<dyn ConditionalSendFuture<Output = T> + 'a>>;
72
73/// A shortcut alias for [`hashbrown::hash_map::Entry`].
74pub type Entry<'a, K, V, S = BuildHasherDefault<AHasher>> = hashbrown::hash_map::Entry<'a, K, V, S>;
75
76/// A hasher builder that will create a fixed hasher.
77#[derive(Debug, Clone, Default)]
78pub struct FixedState;
79
80impl BuildHasher for FixedState {
81    type Hasher = AHasher;
82
83    #[inline]
84    fn build_hasher(&self) -> AHasher {
85        RandomState::with_seeds(
86            0b10010101111011100000010011000100,
87            0b00000011001001101011001001111000,
88            0b11001111011010110111100010110101,
89            0b00000100001111100011010011010101,
90        )
91        .build_hasher()
92    }
93}
94
95/// A [`HashMap`][hashbrown::HashMap] implementing aHash, a high
96/// speed keyed hashing algorithm intended for use in in-memory hashmaps.
97///
98/// aHash is designed for performance and is NOT cryptographically secure.
99///
100/// Within the same execution of the program iteration order of different
101/// `HashMap`s only depends on the order of insertions and deletions,
102/// but it will not be stable between multiple executions of the program.
103pub type HashMap<K, V> = hashbrown::HashMap<K, V, BuildHasherDefault<AHasher>>;
104
105/// A stable hash map implementing aHash, a high speed keyed hashing algorithm
106/// intended for use in in-memory hashmaps.
107///
108/// Unlike [`HashMap`] the iteration order stability extends between executions
109/// using the same Bevy version on the same device.
110///
111/// aHash is designed for performance and is NOT cryptographically secure.
112#[deprecated(
113    note = "Will be required to use the hash library of your choice. Alias for: hashbrown::HashMap<K, V, FixedState>"
114)]
115pub type StableHashMap<K, V> = hashbrown::HashMap<K, V, FixedState>;
116
117/// A [`HashSet`][hashbrown::HashSet] implementing aHash, a high
118/// speed keyed hashing algorithm intended for use in in-memory hashmaps.
119///
120/// aHash is designed for performance and is NOT cryptographically secure.
121///
122/// Within the same execution of the program iteration order of different
123/// `HashSet`s only depends on the order of insertions and deletions,
124/// but it will not be stable between multiple executions of the program.
125pub type HashSet<K> = hashbrown::HashSet<K, BuildHasherDefault<AHasher>>;
126
127/// A stable hash set implementing aHash, a high speed keyed hashing algorithm
128/// intended for use in in-memory hashmaps.
129///
130/// Unlike [`HashMap`] the iteration order stability extends between executions
131/// using the same Bevy version on the same device.
132///
133/// aHash is designed for performance and is NOT cryptographically secure.
134#[deprecated(
135    note = "Will be required to use the hash library of your choice. Alias for: hashbrown::HashSet<K, FixedState>"
136)]
137pub type StableHashSet<K> = hashbrown::HashSet<K, FixedState>;
138
139/// A pre-hashed value of a specific type. Pre-hashing enables memoization of hashes that are expensive to compute.
140/// It also enables faster [`PartialEq`] comparisons by short circuiting on hash equality.
141/// See [`PassHash`] and [`PassHasher`] for a "pass through" [`BuildHasher`] and [`Hasher`] implementation
142/// designed to work with [`Hashed`]
143/// See [`PreHashMap`] for a hashmap pre-configured to use [`Hashed`] keys.
144pub struct Hashed<V, H = FixedState> {
145    hash: u64,
146    value: V,
147    marker: PhantomData<H>,
148}
149
150impl<V: Hash, H: BuildHasher + Default> Hashed<V, H> {
151    /// Pre-hashes the given value using the [`BuildHasher`] configured in the [`Hashed`] type.
152    pub fn new(value: V) -> Self {
153        Self {
154            hash: H::default().hash_one(&value),
155            value,
156            marker: PhantomData,
157        }
158    }
159
160    /// The pre-computed hash.
161    #[inline]
162    pub fn hash(&self) -> u64 {
163        self.hash
164    }
165}
166
167impl<V, H> Hash for Hashed<V, H> {
168    #[inline]
169    fn hash<R: Hasher>(&self, state: &mut R) {
170        state.write_u64(self.hash);
171    }
172}
173
174impl<V, H> Deref for Hashed<V, H> {
175    type Target = V;
176
177    #[inline]
178    fn deref(&self) -> &Self::Target {
179        &self.value
180    }
181}
182
183impl<V: PartialEq, H> PartialEq for Hashed<V, H> {
184    /// A fast impl of [`PartialEq`] that first checks that `other`'s pre-computed hash
185    /// matches this value's pre-computed hash.
186    #[inline]
187    fn eq(&self, other: &Self) -> bool {
188        self.hash == other.hash && self.value.eq(&other.value)
189    }
190}
191
192impl<V: Debug, H> Debug for Hashed<V, H> {
193    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
194        f.debug_struct("Hashed")
195            .field("hash", &self.hash)
196            .field("value", &self.value)
197            .finish()
198    }
199}
200
201impl<V: Clone, H> Clone for Hashed<V, H> {
202    #[inline]
203    fn clone(&self) -> Self {
204        Self {
205            hash: self.hash,
206            value: self.value.clone(),
207            marker: PhantomData,
208        }
209    }
210}
211
212impl<V: Eq, H> Eq for Hashed<V, H> {}
213
214/// A [`BuildHasher`] that results in a [`PassHasher`].
215#[derive(Default, Clone)]
216pub struct PassHash;
217
218impl BuildHasher for PassHash {
219    type Hasher = PassHasher;
220
221    fn build_hasher(&self) -> Self::Hasher {
222        PassHasher::default()
223    }
224}
225
226/// A no-op hash that only works on `u64`s. Will panic if attempting to
227/// hash a type containing non-u64 fields.
228#[derive(Debug, Default)]
229pub struct PassHasher {
230    hash: u64,
231}
232
233impl Hasher for PassHasher {
234    #[inline]
235    fn finish(&self) -> u64 {
236        self.hash
237    }
238
239    fn write(&mut self, _bytes: &[u8]) {
240        panic!("can only hash u64 using PassHasher");
241    }
242
243    #[inline]
244    fn write_u64(&mut self, i: u64) {
245        self.hash = i;
246    }
247}
248
249/// A [`HashMap`] pre-configured to use [`Hashed`] keys and [`PassHash`] passthrough hashing.
250/// Iteration order only depends on the order of insertions and deletions.
251pub type PreHashMap<K, V> = hashbrown::HashMap<Hashed<K>, V, PassHash>;
252
253/// Extension methods intended to add functionality to [`PreHashMap`].
254pub trait PreHashMapExt<K, V> {
255    /// Tries to get or insert the value for the given `key` using the pre-computed hash first.
256    /// If the [`PreHashMap`] does not already contain the `key`, it will clone it and insert
257    /// the value returned by `func`.
258    fn get_or_insert_with<F: FnOnce() -> V>(&mut self, key: &Hashed<K>, func: F) -> &mut V;
259}
260
261impl<K: Hash + Eq + PartialEq + Clone, V> PreHashMapExt<K, V> for PreHashMap<K, V> {
262    #[inline]
263    fn get_or_insert_with<F: FnOnce() -> V>(&mut self, key: &Hashed<K>, func: F) -> &mut V {
264        let entry = self
265            .raw_entry_mut()
266            .from_key_hashed_nocheck(key.hash(), key);
267        match entry {
268            RawEntryMut::Occupied(entry) => entry.into_mut(),
269            RawEntryMut::Vacant(entry) => {
270                let (_, value) = entry.insert_hashed_nocheck(key.hash(), key.clone(), func());
271                value
272            }
273        }
274    }
275}
276
277/// A [`BuildHasher`] that results in a [`EntityHasher`].
278#[derive(Default, Clone)]
279pub struct EntityHash;
280
281impl BuildHasher for EntityHash {
282    type Hasher = EntityHasher;
283
284    fn build_hasher(&self) -> Self::Hasher {
285        EntityHasher::default()
286    }
287}
288
289/// A very fast hash that is only designed to work on generational indices
290/// like `Entity`. It will panic if attempting to hash a type containing
291/// non-u64 fields.
292///
293/// This is heavily optimized for typical cases, where you have mostly live
294/// entities, and works particularly well for contiguous indices.
295///
296/// If you have an unusual case -- say all your indices are multiples of 256
297/// or most of the entities are dead generations -- then you might want also to
298/// try [`AHasher`] for a slower hash computation but fewer lookup conflicts.
299#[derive(Debug, Default)]
300pub struct EntityHasher {
301    hash: u64,
302}
303
304impl Hasher for EntityHasher {
305    #[inline]
306    fn finish(&self) -> u64 {
307        self.hash
308    }
309
310    fn write(&mut self, _bytes: &[u8]) {
311        panic!("can only hash u64 using EntityHasher");
312    }
313
314    #[inline]
315    fn write_u64(&mut self, bits: u64) {
316        // SwissTable (and thus `hashbrown`) cares about two things from the hash:
317        // - H1: low bits (masked by `2ⁿ-1`) to pick the slot in which to store the item
318        // - H2: high 7 bits are used to SIMD optimize hash collision probing
319        // For more see <https://abseil.io/about/design/swisstables#metadata-layout>
320
321        // This hash function assumes that the entity ids are still well-distributed,
322        // so for H1 leaves the entity id alone in the low bits so that id locality
323        // will also give memory locality for things spawned together.
324        // For H2, take advantage of the fact that while multiplication doesn't
325        // spread entropy to the low bits, it's incredibly good at spreading it
326        // upward, which is exactly where we need it the most.
327
328        // While this does include the generation in the output, it doesn't do so
329        // *usefully*.  H1 won't care until you have over 3 billion entities in
330        // the table, and H2 won't care until something hits generation 33 million.
331        // Thus the comment suggesting that this is best for live entities,
332        // where there won't be generation conflicts where it would matter.
333
334        // The high 32 bits of this are ⅟φ for Fibonacci hashing.  That works
335        // particularly well for hashing for the same reason as described in
336        // <https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/>
337        // It loses no information because it has a modular inverse.
338        // (Specifically, `0x144c_bc89_u32 * 0x9e37_79b9_u32 == 1`.)
339        //
340        // The low 32 bits make that part of the just product a pass-through.
341        const UPPER_PHI: u64 = 0x9e37_79b9_0000_0001;
342
343        // This is `(MAGIC * index + generation) << 32 + index`, in a single instruction.
344        self.hash = bits.wrapping_mul(UPPER_PHI);
345    }
346}
347
348/// A [`HashMap`] pre-configured to use [`EntityHash`] hashing.
349/// Iteration order only depends on the order of insertions and deletions.
350pub type EntityHashMap<K, V> = hashbrown::HashMap<K, V, EntityHash>;
351
352/// A [`HashSet`] pre-configured to use [`EntityHash`] hashing.
353/// Iteration order only depends on the order of insertions and deletions.
354pub type EntityHashSet<T> = hashbrown::HashSet<T, EntityHash>;
355
356/// A specialized hashmap type with Key of [`TypeId`]
357/// Iteration order only depends on the order of insertions and deletions.
358pub type TypeIdMap<V> = hashbrown::HashMap<TypeId, V, NoOpHash>;
359
360/// [`BuildHasher`] for types that already contain a high-quality hash.
361#[derive(Clone, Default)]
362pub struct NoOpHash;
363
364impl BuildHasher for NoOpHash {
365    type Hasher = NoOpHasher;
366
367    fn build_hasher(&self) -> Self::Hasher {
368        NoOpHasher(0)
369    }
370}
371
372#[doc(hidden)]
373pub struct NoOpHasher(u64);
374
375// This is for types that already contain a high-quality hash and want to skip
376// re-hashing that hash.
377impl std::hash::Hasher for NoOpHasher {
378    fn finish(&self) -> u64 {
379        self.0
380    }
381
382    fn write(&mut self, bytes: &[u8]) {
383        // This should never be called by consumers. Prefer to call `write_u64` instead.
384        // Don't break applications (slower fallback, just check in test):
385        self.0 = bytes.iter().fold(self.0, |hash, b| {
386            hash.rotate_left(8).wrapping_add(*b as u64)
387        });
388    }
389
390    #[inline]
391    fn write_u64(&mut self, i: u64) {
392        self.0 = i;
393    }
394}
395
396/// A type which calls a function when dropped.
397/// This can be used to ensure that cleanup code is run even in case of a panic.
398///
399/// Note that this only works for panics that [unwind](https://doc.rust-lang.org/nomicon/unwinding.html)
400/// -- any code within `OnDrop` will be skipped if a panic does not unwind.
401/// In most cases, this will just work.
402///
403/// # Examples
404///
405/// ```
406/// # use bevy_utils::OnDrop;
407/// # fn test_panic(do_panic: bool, log: impl FnOnce(&str)) {
408/// // This will print a message when the variable `_catch` gets dropped,
409/// // even if a panic occurs before we reach the end of this scope.
410/// // This is similar to a `try ... catch` block in languages such as C++.
411/// let _catch = OnDrop::new(|| log("Oops, a panic occurred and this function didn't complete!"));
412///
413/// // Some code that may panic...
414/// // ...
415/// # if do_panic { panic!() }
416///
417/// // Make sure the message only gets printed if a panic occurs.
418/// // If we remove this line, then the message will be printed regardless of whether a panic occurs
419/// // -- similar to a `try ... finally` block.
420/// std::mem::forget(_catch);
421/// # }
422/// #
423/// # test_panic(false, |_| unreachable!());
424/// # let mut did_log = false;
425/// # std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
426/// #   test_panic(true, |_| did_log = true);
427/// # }));
428/// # assert!(did_log);
429/// ```
430pub struct OnDrop<F: FnOnce()> {
431    callback: ManuallyDrop<F>,
432}
433
434impl<F: FnOnce()> OnDrop<F> {
435    /// Returns an object that will invoke the specified callback when dropped.
436    pub fn new(callback: F) -> Self {
437        Self {
438            callback: ManuallyDrop::new(callback),
439        }
440    }
441}
442
443impl<F: FnOnce()> Drop for OnDrop<F> {
444    fn drop(&mut self) {
445        // SAFETY: We may move out of `self`, since this instance can never be observed after it's dropped.
446        let callback = unsafe { ManuallyDrop::take(&mut self.callback) };
447        callback();
448    }
449}
450
451/// Calls the [`tracing::info!`] macro on a value.
452pub fn info<T: Debug>(data: T) {
453    tracing::info!("{:?}", data);
454}
455
456/// Calls the [`tracing::debug!`] macro on a value.
457pub fn dbg<T: Debug>(data: T) {
458    tracing::debug!("{:?}", data);
459}
460
461/// Processes a [`Result`] by calling the [`tracing::warn!`] macro in case of an [`Err`] value.
462pub fn warn<E: Debug>(result: Result<(), E>) {
463    if let Err(warn) = result {
464        tracing::warn!("{:?}", warn);
465    }
466}
467
468/// Processes a [`Result`] by calling the [`tracing::error!`] macro in case of an [`Err`] value.
469pub fn error<E: Debug>(result: Result<(), E>) {
470    if let Err(error) = result {
471        tracing::error!("{:?}", error);
472    }
473}
474
475/// Like [`tracing::trace`], but conditional on cargo feature `detailed_trace`.
476#[macro_export]
477macro_rules! detailed_trace {
478    ($($tts:tt)*) => {
479        if cfg!(detailed_trace) {
480            bevy_utils::tracing::trace!($($tts)*);
481        }
482    }
483}
484
485#[cfg(test)]
486mod tests {
487    use super::*;
488    use static_assertions::assert_impl_all;
489
490    // Check that the HashMaps are Clone if the key/values are Clone
491    assert_impl_all!(PreHashMap::<u64, usize>: Clone);
492
493    #[test]
494    fn fast_typeid_hash() {
495        struct Hasher;
496
497        impl std::hash::Hasher for Hasher {
498            fn finish(&self) -> u64 {
499                0
500            }
501            fn write(&mut self, _: &[u8]) {
502                panic!("Hashing of std::any::TypeId changed");
503            }
504            fn write_u64(&mut self, _: u64) {}
505        }
506
507        std::hash::Hash::hash(&TypeId::of::<()>(), &mut Hasher);
508    }
509
510    #[test]
511    fn stable_hash_within_same_program_execution() {
512        let mut map_1 = HashMap::new();
513        let mut map_2 = HashMap::new();
514        for i in 1..10 {
515            map_1.insert(i, i);
516            map_2.insert(i, i);
517        }
518        assert_eq!(
519            map_1.iter().collect::<Vec<_>>(),
520            map_2.iter().collect::<Vec<_>>()
521        );
522    }
523}