cranelift_entity/
lib.rs

1//! Array-based data structures using densely numbered entity references as mapping keys.
2//!
3//! This crate defines a number of data structures based on arrays. The arrays are not indexed by
4//! `usize` as usual, but by *entity references* which are integers wrapped in new-types. This has
5//! a couple advantages:
6//!
7//! - Improved type safety. The various map and set types accept a specific key type, so there is
8//!   no confusion about the meaning of an array index, as there is with plain arrays.
9//! - Smaller indexes. The normal `usize` index is often 64 bits which is way too large for most
10//!   purposes. The entity reference types can be smaller, allowing for more compact data
11//!   structures.
12//!
13//! The `EntityRef` trait should be implemented by types to be used as indexed. The `entity_impl!`
14//! macro provides convenient defaults for types wrapping `u32` which is common.
15//!
16//! - [`PrimaryMap`](struct.PrimaryMap.html) is used to keep track of a vector of entities,
17//!   assigning a unique entity reference to each.
18//! - [`SecondaryMap`](struct.SecondaryMap.html) is used to associate secondary information to an
19//!   entity. The map is implemented as a simple vector, so it does not keep track of which
20//!   entities have been inserted. Instead, any unknown entities map to the default value.
21//! - [`SparseMap`](struct.SparseMap.html) is used to associate secondary information to a small
22//!   number of entities. It tracks accurately which entities have been inserted. This is a
23//!   specialized data structure which can use a lot of memory, so read the documentation before
24//!   using it.
25//! - [`EntitySet`](struct.EntitySet.html) is used to represent a secondary set of entities.
26//!   The set is implemented as a simple vector, so it does not keep track of which entities have
27//!   been inserted into the primary map. Instead, any unknown entities are not in the set.
28//! - [`EntityList`](struct.EntityList.html) is a compact representation of lists of entity
29//!   references allocated from an associated memory pool. It has a much smaller footprint than
30//!   `Vec`.
31
32#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
33#![warn(unused_import_braces)]
34#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
35#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
36#![cfg_attr(
37    feature = "cargo-clippy",
38    warn(
39        clippy::float_arithmetic,
40        clippy::mut_mut,
41        clippy::nonminimal_bool,
42        clippy::map_unwrap_or,
43        clippy::clippy::print_stdout,
44        clippy::unicode_not_nfc,
45        clippy::use_self
46    )
47)]
48#![no_std]
49
50extern crate alloc;
51
52// Re-export core so that the macros works with both std and no_std crates
53#[doc(hidden)]
54pub extern crate core as __core;
55
56/// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key
57/// of an `SecondaryMap` or `SparseMap`.
58pub trait EntityRef: Copy + Eq {
59    /// Create a new entity reference from a small integer.
60    /// This should crash if the requested index is not representable.
61    fn new(_: usize) -> Self;
62
63    /// Get the index that was used to create this entity reference.
64    fn index(self) -> usize;
65}
66
67/// Macro which provides the common implementation of a 32-bit entity reference.
68#[macro_export]
69macro_rules! entity_impl {
70    // Basic traits.
71    ($entity:ident) => {
72        impl $crate::EntityRef for $entity {
73            #[inline]
74            fn new(index: usize) -> Self {
75                debug_assert!(index < ($crate::__core::u32::MAX as usize));
76                $entity(index as u32)
77            }
78
79            #[inline]
80            fn index(self) -> usize {
81                self.0 as usize
82            }
83        }
84
85        impl $crate::packed_option::ReservedValue for $entity {
86            #[inline]
87            fn reserved_value() -> $entity {
88                $entity($crate::__core::u32::MAX)
89            }
90
91            #[inline]
92            fn is_reserved_value(&self) -> bool {
93                self.0 == $crate::__core::u32::MAX
94            }
95        }
96
97        impl $entity {
98            /// Create a new instance from a `u32`.
99            #[allow(dead_code)]
100            #[inline]
101            pub fn from_u32(x: u32) -> Self {
102                debug_assert!(x < $crate::__core::u32::MAX);
103                $entity(x)
104            }
105
106            /// Return the underlying index value as a `u32`.
107            #[allow(dead_code)]
108            #[inline]
109            pub fn as_u32(self) -> u32 {
110                self.0
111            }
112
113            /// Return the raw bit encoding for this instance.
114            #[allow(dead_code)]
115            #[inline]
116            pub fn as_bits(self) -> u32 {
117                self.0
118            }
119
120            /// Create a new instance from the raw bit encoding.
121            #[allow(dead_code)]
122            #[inline]
123            pub fn from_bits(x: u32) -> Self {
124                $entity(x)
125            }
126        }
127    };
128
129    // Include basic `Display` impl using the given display prefix.
130    // Display a `Block` reference as "block12".
131    ($entity:ident, $display_prefix:expr) => {
132        entity_impl!($entity);
133
134        impl $crate::__core::fmt::Display for $entity {
135            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
136                write!(f, concat!($display_prefix, "{}"), self.0)
137            }
138        }
139
140        impl $crate::__core::fmt::Debug for $entity {
141            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
142                (self as &dyn $crate::__core::fmt::Display).fmt(f)
143            }
144        }
145    };
146
147    // Alternate form for tuples we can't directly construct; providing "to" and "from" expressions
148    // to turn an index *into* an entity, or get an index *from* an entity.
149    ($entity:ident, $display_prefix:expr, $arg:ident, $to_expr:expr, $from_expr:expr) => {
150        impl $crate::EntityRef for $entity {
151            #[inline]
152            fn new(index: usize) -> Self {
153                debug_assert!(index < ($crate::__core::u32::MAX as usize));
154                let $arg = index as u32;
155                $to_expr
156            }
157
158            #[inline]
159            fn index(self) -> usize {
160                let $arg = self;
161                $from_expr as usize
162            }
163        }
164
165        impl $crate::packed_option::ReservedValue for $entity {
166            #[inline]
167            fn reserved_value() -> $entity {
168                $entity::from_u32($crate::__core::u32::MAX)
169            }
170
171            #[inline]
172            fn is_reserved_value(&self) -> bool {
173                self.as_u32() == $crate::__core::u32::MAX
174            }
175        }
176
177        impl $entity {
178            /// Create a new instance from a `u32`.
179            #[allow(dead_code)]
180            #[inline]
181            pub fn from_u32(x: u32) -> Self {
182                debug_assert!(x < $crate::__core::u32::MAX);
183                let $arg = x;
184                $to_expr
185            }
186
187            /// Return the underlying index value as a `u32`.
188            #[allow(dead_code)]
189            #[inline]
190            pub fn as_u32(self) -> u32 {
191                let $arg = self;
192                $from_expr
193            }
194        }
195
196        impl $crate::__core::fmt::Display for $entity {
197            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
198                write!(f, concat!($display_prefix, "{}"), self.as_u32())
199            }
200        }
201
202        impl $crate::__core::fmt::Debug for $entity {
203            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
204                (self as &dyn $crate::__core::fmt::Display).fmt(f)
205            }
206        }
207    };
208}
209
210pub mod packed_option;
211
212mod boxed_slice;
213mod iter;
214mod keys;
215mod list;
216mod map;
217mod primary;
218mod set;
219mod sparse;
220
221pub use self::boxed_slice::BoxedSlice;
222pub use self::iter::{Iter, IterMut};
223pub use self::keys::Keys;
224pub use self::list::{EntityList, ListPool};
225pub use self::map::SecondaryMap;
226pub use self::primary::PrimaryMap;
227pub use self::set::EntitySet;
228pub use self::sparse::{SparseMap, SparseMapValue, SparseSet};
229
230/// A collection of tests to ensure that use of the different `entity_impl!` forms will generate
231/// `EntityRef` implementations that behave the same way.
232#[cfg(test)]
233mod tests {
234    /// A macro used to emit some basic tests to show that entities behave as we expect.
235    macro_rules! entity_test {
236        ($entity:ident) => {
237            #[test]
238            fn from_usize_to_u32() {
239                let e = $entity::new(42);
240                assert_eq!(e.as_u32(), 42_u32);
241            }
242
243            #[test]
244            fn from_u32_to_usize() {
245                let e = $entity::from_u32(42);
246                assert_eq!(e.index(), 42_usize);
247            }
248
249            #[test]
250            fn comparisons_work() {
251                let a = $entity::from_u32(42);
252                let b = $entity::new(42);
253                assert_eq!(a, b);
254            }
255
256            #[should_panic]
257            #[test]
258            fn cannot_construct_from_reserved_u32() {
259                use crate::packed_option::ReservedValue;
260                let reserved = $entity::reserved_value().as_u32();
261                let _ = $entity::from_u32(reserved); // panic
262            }
263
264            #[should_panic]
265            #[test]
266            fn cannot_construct_from_reserved_usize() {
267                use crate::packed_option::ReservedValue;
268                let reserved = $entity::reserved_value().index();
269                let _ = $entity::new(reserved); // panic
270            }
271        };
272    }
273
274    /// Test cases for a plain ol' `EntityRef` implementation.
275    mod basic_entity {
276        use crate::EntityRef;
277        #[derive(Clone, Copy, Debug, PartialEq, Eq)]
278        struct BasicEntity(u32);
279        entity_impl!(BasicEntity);
280        entity_test!(BasicEntity);
281    }
282
283    /// Test cases for an `EntityRef` implementation that includes a display prefix.
284    mod prefix_entity {
285        use crate::EntityRef;
286        #[derive(Clone, Copy, PartialEq, Eq)]
287        struct PrefixEntity(u32);
288        entity_impl!(PrefixEntity, "prefix-");
289        entity_test!(PrefixEntity);
290
291        #[test]
292        fn display_prefix_works() {
293            let e = PrefixEntity::new(0);
294            assert_eq!(alloc::format!("{}", e), "prefix-0");
295        }
296    }
297
298    /// Test cases for an `EntityRef` implementation for a type we can only construct through
299    /// other means, such as calls to `core::convert::From<u32>`.
300    mod other_entity {
301        mod inner {
302            #[derive(Clone, Copy, PartialEq, Eq)]
303            pub struct InnerEntity(u32);
304
305            impl From<u32> for InnerEntity {
306                fn from(x: u32) -> Self {
307                    Self(x)
308                }
309            }
310
311            impl From<InnerEntity> for u32 {
312                fn from(x: InnerEntity) -> Self {
313                    x.0
314                }
315            }
316        }
317
318        use {self::inner::InnerEntity, crate::EntityRef};
319        entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i));
320        entity_test!(InnerEntity);
321
322        #[test]
323        fn display_prefix_works() {
324            let e = InnerEntity::new(0);
325            assert_eq!(alloc::format!("{}", e), "inner-0");
326        }
327    }
328}
cranelift_entity/lib.rs

cranelift_entity/
lib.rs
