1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
//! Array-based data structures using densely numbered entity references as mapping keys.
//!
//! This crate defines a number of data structures based on arrays. The arrays are not indexed by
//! `usize` as usual, but by *entity references* which are integers wrapped in new-types. This has
//! a couple advantages:
//!
//! - Improved type safety. The various map and set types accept a specific key type, so there is
//!   no confusion about the meaning of an array index, as there is with plain arrays.
//! - Smaller indexes. The normal `usize` index is often 64 bits which is way too large for most
//!   purposes. The entity reference types can be smaller, allowing for more compact data
//!   structures.
//!
//! The `EntityRef` trait should be implemented by types to be used as indexed. The `entity_impl!`
//! macro provides convenient defaults for types wrapping `u32` which is common.
//!
//! - [`PrimaryMap`](struct.PrimaryMap.html) is used to keep track of a vector of entities,
//!   assigning a unique entity reference to each.
//! - [`SecondaryMap`](struct.SecondaryMap.html) is used to associate secondary information to an
//!   entity. The map is implemented as a simple vector, so it does not keep track of which
//!   entities have been inserted. Instead, any unknown entities map to the default value.
//! - [`SparseMap`](struct.SparseMap.html) is used to associate secondary information to a small
//!   number of entities. It tracks accurately which entities have been inserted. This is a
//!   specialized data structure which can use a lot of memory, so read the documentation before
//!   using it.
//! - [`EntitySet`](struct.EntitySet.html) is used to represent a secondary set of entities.
//!   The set is implemented as a simple vector, so it does not keep track of which entities have
//!   been inserted into the primary map. Instead, any unknown entities are not in the set.
//! - [`EntityList`](struct.EntityList.html) is a compact representation of lists of entity
//!   references allocated from an associated memory pool. It has a much smaller footprint than
//!   `Vec`.

#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
#![warn(unused_import_braces)]
#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
#![cfg_attr(
    feature = "cargo-clippy",
    warn(
        clippy::float_arithmetic,
        clippy::mut_mut,
        clippy::nonminimal_bool,
        clippy::map_unwrap_or,
        clippy::clippy::print_stdout,
        clippy::unicode_not_nfc,
        clippy::use_self
    )
)]
#![no_std]

extern crate alloc;

// Re-export core so that the macros works with both std and no_std crates
#[doc(hidden)]
pub extern crate core as __core;

/// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key
/// of an `SecondaryMap` or `SparseMap`.
pub trait EntityRef: Copy + Eq {
    /// Create a new entity reference from a small integer.
    /// This should crash if the requested index is not representable.
    fn new(_: usize) -> Self;

    /// Get the index that was used to create this entity reference.
    fn index(self) -> usize;
}

/// Macro which provides the common implementation of a 32-bit entity reference.
#[macro_export]
macro_rules! entity_impl {
    // Basic traits.
    ($entity:ident) => {
        impl $crate::EntityRef for $entity {
            #[inline]
            fn new(index: usize) -> Self {
                debug_assert!(index < ($crate::__core::u32::MAX as usize));
                $entity(index as u32)
            }

            #[inline]
            fn index(self) -> usize {
                self.0 as usize
            }
        }

        impl $crate::packed_option::ReservedValue for $entity {
            #[inline]
            fn reserved_value() -> $entity {
                $entity($crate::__core::u32::MAX)
            }

            #[inline]
            fn is_reserved_value(&self) -> bool {
                self.0 == $crate::__core::u32::MAX
            }
        }

        impl $entity {
            /// Create a new instance from a `u32`.
            #[allow(dead_code)]
            #[inline]
            pub fn from_u32(x: u32) -> Self {
                debug_assert!(x < $crate::__core::u32::MAX);
                $entity(x)
            }

            /// Return the underlying index value as a `u32`.
            #[allow(dead_code)]
            #[inline]
            pub fn as_u32(self) -> u32 {
                self.0
            }

            /// Return the raw bit encoding for this instance.
            #[allow(dead_code)]
            #[inline]
            pub fn as_bits(self) -> u32 {
                self.0
            }

            /// Create a new instance from the raw bit encoding.
            #[allow(dead_code)]
            #[inline]
            pub fn from_bits(x: u32) -> Self {
                $entity(x)
            }
        }
    };

    // Include basic `Display` impl using the given display prefix.
    // Display a `Block` reference as "block12".
    ($entity:ident, $display_prefix:expr) => {
        entity_impl!($entity);

        impl $crate::__core::fmt::Display for $entity {
            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
                write!(f, concat!($display_prefix, "{}"), self.0)
            }
        }

        impl $crate::__core::fmt::Debug for $entity {
            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
                (self as &dyn $crate::__core::fmt::Display).fmt(f)
            }
        }
    };

    // Alternate form for tuples we can't directly construct; providing "to" and "from" expressions
    // to turn an index *into* an entity, or get an index *from* an entity.
    ($entity:ident, $display_prefix:expr, $arg:ident, $to_expr:expr, $from_expr:expr) => {
        impl $crate::EntityRef for $entity {
            #[inline]
            fn new(index: usize) -> Self {
                debug_assert!(index < ($crate::__core::u32::MAX as usize));
                let $arg = index as u32;
                $to_expr
            }

            #[inline]
            fn index(self) -> usize {
                let $arg = self;
                $from_expr as usize
            }
        }

        impl $crate::packed_option::ReservedValue for $entity {
            #[inline]
            fn reserved_value() -> $entity {
                $entity::from_u32($crate::__core::u32::MAX)
            }

            #[inline]
            fn is_reserved_value(&self) -> bool {
                self.as_u32() == $crate::__core::u32::MAX
            }
        }

        impl $entity {
            /// Create a new instance from a `u32`.
            #[allow(dead_code)]
            #[inline]
            pub fn from_u32(x: u32) -> Self {
                debug_assert!(x < $crate::__core::u32::MAX);
                let $arg = x;
                $to_expr
            }

            /// Return the underlying index value as a `u32`.
            #[allow(dead_code)]
            #[inline]
            pub fn as_u32(self) -> u32 {
                let $arg = self;
                $from_expr
            }
        }

        impl $crate::__core::fmt::Display for $entity {
            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
                write!(f, concat!($display_prefix, "{}"), self.as_u32())
            }
        }

        impl $crate::__core::fmt::Debug for $entity {
            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
                (self as &dyn $crate::__core::fmt::Display).fmt(f)
            }
        }
    };
}

pub mod packed_option;

mod boxed_slice;
mod iter;
mod keys;
mod list;
mod map;
mod primary;
mod set;
mod sparse;

pub use self::boxed_slice::BoxedSlice;
pub use self::iter::{Iter, IterMut};
pub use self::keys::Keys;
pub use self::list::{EntityList, ListPool};
pub use self::map::SecondaryMap;
pub use self::primary::PrimaryMap;
pub use self::set::EntitySet;
pub use self::sparse::{SparseMap, SparseMapValue, SparseSet};

/// A collection of tests to ensure that use of the different `entity_impl!` forms will generate
/// `EntityRef` implementations that behave the same way.
#[cfg(test)]
mod tests {
    /// A macro used to emit some basic tests to show that entities behave as we expect.
    macro_rules! entity_test {
        ($entity:ident) => {
            #[test]
            fn from_usize_to_u32() {
                let e = $entity::new(42);
                assert_eq!(e.as_u32(), 42_u32);
            }

            #[test]
            fn from_u32_to_usize() {
                let e = $entity::from_u32(42);
                assert_eq!(e.index(), 42_usize);
            }

            #[test]
            fn comparisons_work() {
                let a = $entity::from_u32(42);
                let b = $entity::new(42);
                assert_eq!(a, b);
            }

            #[should_panic]
            #[cfg(debug_assertions)]
            #[test]
            fn cannot_construct_from_reserved_u32() {
                use crate::packed_option::ReservedValue;
                let reserved = $entity::reserved_value().as_u32();
                let _ = $entity::from_u32(reserved); // panic
            }

            #[should_panic]
            #[cfg(debug_assertions)]
            #[test]
            fn cannot_construct_from_reserved_usize() {
                use crate::packed_option::ReservedValue;
                let reserved = $entity::reserved_value().index();
                let _ = $entity::new(reserved); // panic
            }
        };
    }

    /// Test cases for a plain ol' `EntityRef` implementation.
    mod basic_entity {
        use crate::EntityRef;
        #[derive(Clone, Copy, Debug, PartialEq, Eq)]
        struct BasicEntity(u32);
        entity_impl!(BasicEntity);
        entity_test!(BasicEntity);
    }

    /// Test cases for an `EntityRef` implementation that includes a display prefix.
    mod prefix_entity {
        use crate::EntityRef;
        #[derive(Clone, Copy, PartialEq, Eq)]
        struct PrefixEntity(u32);
        entity_impl!(PrefixEntity, "prefix-");
        entity_test!(PrefixEntity);

        #[test]
        fn display_prefix_works() {
            let e = PrefixEntity::new(0);
            assert_eq!(alloc::format!("{}", e), "prefix-0");
        }
    }

    /// Test cases for an `EntityRef` implementation for a type we can only construct through
    /// other means, such as calls to `core::convert::From<u32>`.
    mod other_entity {
        mod inner {
            #[derive(Clone, Copy, PartialEq, Eq)]
            pub struct InnerEntity(u32);

            impl From<u32> for InnerEntity {
                fn from(x: u32) -> Self {
                    Self(x)
                }
            }

            impl From<InnerEntity> for u32 {
                fn from(x: InnerEntity) -> Self {
                    x.0
                }
            }
        }

        use {self::inner::InnerEntity, crate::EntityRef};
        entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i));
        entity_test!(InnerEntity);

        #[test]
        fn display_prefix_works() {
            let e = InnerEntity::new(0);
            assert_eq!(alloc::format!("{}", e), "inner-0");
        }
    }
}