vendor/cranelift-entity-0.111.0/src/lib.rs - toolchain/rustc - Git at Google

 //! 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)]
 #![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;

 use core::iter::FusedIterator;
 use core::ops::Range;

 /// 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;
 }

 /// Iterate over a `Range<E: EntityRef>`, yielding a sequence of `E` items.
 #[inline]
 pub fn iter_entity_range<E>(range: Range<E>) -> IterEntityRange<E>
 where
     E: EntityRef,
 {
     IterEntityRange {
         range: range.start.index()..range.end.index(),
         _phantom: core::marker::PhantomData,
     }
 }

 /// Iterator type returned by `iter_entity_range`.
 pub struct IterEntityRange<E> {
     range: Range<usize>,
     _phantom: core::marker::PhantomData<E>,
 }

 impl<E> Iterator for IterEntityRange<E>
 where
     E: EntityRef,
 {
     type Item = E;

     #[inline]
     fn next(&mut self) -> Option<Self::Item> {
         let i = self.range.next()?;
         Some(E::new(i))
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.range.size_hint()
     }
 }

 impl<E> DoubleEndedIterator for IterEntityRange<E>
 where
     E: EntityRef,
 {
     #[inline]
     fn next_back(&mut self) -> Option<Self::Item> {
         let i = self.range.next_back()?;
         Some(E::new(i))
     }
 }

 impl<E> FusedIterator for IterEntityRange<E>
 where
     E: EntityRef,
     Range<usize>: FusedIterator,
 {
 }

 impl<E> ExactSizeIterator for IterEntityRange<E>
 where
     E: EntityRef,
     Range<usize>: ExactSizeIterator,
 {
 }

 /// 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;
 mod unsigned;

 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};
 pub use self::unsigned::Unsigned;

 /// 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");
         }
     }
 }
	//! 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)]
	#![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;

	use core::iter::FusedIterator;
	use core::ops::Range;

	/// 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;
	}

	/// Iterate over a `Range<E: EntityRef>`, yielding a sequence of `E` items.
	#[inline]
	pub fn iter_entity_range<E>(range: Range<E>) -> IterEntityRange<E>
	where
	E: EntityRef,
	{
	IterEntityRange {
	range: range.start.index()..range.end.index(),
	_phantom: core::marker::PhantomData,
	}
	}

	/// Iterator type returned by `iter_entity_range`.
	pub struct IterEntityRange<E> {
	range: Range<usize>,
	_phantom: core::marker::PhantomData<E>,
	}

	impl<E> Iterator for IterEntityRange<E>
	where
	E: EntityRef,
	{
	type Item = E;

	#[inline]
	fn next(&mut self) -> Option<Self::Item> {
	let i = self.range.next()?;
	Some(E::new(i))
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	self.range.size_hint()
	}
	}

	impl<E> DoubleEndedIterator for IterEntityRange<E>
	where
	E: EntityRef,
	{
	#[inline]
	fn next_back(&mut self) -> Option<Self::Item> {
	let i = self.range.next_back()?;
	Some(E::new(i))
	}
	}

	impl<E> FusedIterator for IterEntityRange<E>
	where
	E: EntityRef,
	Range<usize>: FusedIterator,
	{
	}

	impl<E> ExactSizeIterator for IterEntityRange<E>
	where
	E: EntityRef,
	Range<usize>: ExactSizeIterator,
	{
	}

	/// 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;
	mod unsigned;

	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};
	pub use self::unsigned::Unsigned;

	/// 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");
	}
	}
	}