gen_map 0.3.0

use core::fmt::Debug;
use core::hash::Hash;
use core::num::NonZero;

// A `Slot` reads one of its union fields based on what `is_odd` says about its
// generation, so the crate's unsafe code relies on every method behaving
// exactly like it does for the standard unsigned integers. In particular,
// `into_non_zero` returns `Some` for every value except `ZERO`. `from_usize`,
// `into_usize` and `from_u128` return `None` for a value that does not fit in
// the target type, and converting a value to a type that can hold it and back
// gives the same value. The largest value is odd, which `Even::next` and
// `Split`'s `max_generation` rely on.

/// An unsigned integer that can be the index or the generation of a
/// [`Key`](crate::Key). It is implemented for `u8`, `u16`, `u32`, `u64`,
/// `u128` and `usize`.
///
/// It is sealed, so it cannot be implemented outside this crate.
pub trait KeyPiece:
    sealed::Sealed + Copy + Eq + Ord + Hash + Debug + Send + Sync + 'static
{
    /// The `NonZero` form of this integer. [`Odd`](crate::Odd) stores its
    /// number in this form, and [`Packed`](crate::Packed) stores its whole
    /// integer this way, which makes `Option<Key>` the same size as `Key`.
    type NonZero: Copy + Eq + Ord + Hash + Debug + Send + Sync + 'static;

    /// The value zero.
    const ZERO: Self;

    /// The value one.
    const ONE: Self;

    /// The largest value.
    const MAX: Self;

    /// The number of bits.
    const BITS: u32;

    /// Returns `self + rhs`, or `None` if the sum does not fit in this type.
    fn checked_add(self, rhs: Self) -> Option<Self>;

    /// Returns `self + rhs`, wrapping around at the largest value of this
    /// type.
    fn wrapping_add(self, rhs: Self) -> Self;

    /// Returns `self - rhs`, wrapping around below zero to the largest value
    /// of this type.
    fn wrapping_sub(self, rhs: Self) -> Self;

    /// Returns `true` if the lowest bit is set.
    fn is_odd(self) -> bool;

    /// Converts the value to a `usize`, or returns `None` if it does not fit.
    fn into_usize(self) -> Option<usize>;

    /// Converts the value to a `usize`, like [`into_usize`](Self::into_usize),
    /// but without checking that it fits.
    ///
    /// # Safety
    ///
    /// The value must fit in a `usize`, meaning
    /// [`into_usize`](Self::into_usize) returns `Some` for it.
    unsafe fn into_usize_unchecked(self) -> usize;

    /// Converts a `usize` to this type, or returns `None` if it does not fit.
    fn from_usize(v: usize) -> Option<Self>;

    /// Converts a `usize` to this type, like [`from_usize`](Self::from_usize),
    /// but without checking that it fits.
    ///
    /// # Safety
    ///
    /// `v` must fit in this type, meaning [`from_usize`](Self::from_usize)
    /// returns `Some` for it.
    unsafe fn from_usize_unchecked(v: usize) -> Self;

    /// Converts the value to its `NonZero` form, or returns `None` if it is
    /// zero.
    fn into_non_zero(self) -> Option<Self::NonZero>;

    /// Converts the value to its `NonZero` form, like
    /// [`into_non_zero`](Self::into_non_zero), but without checking that it is
    /// not zero.
    ///
    /// # Safety
    ///
    /// The value must not be [`ZERO`](Self::ZERO).
    unsafe fn into_non_zero_unchecked(self) -> Self::NonZero;

    /// Converts a `NonZero` value back to the plain integer.
    fn from_non_zero(v: Self::NonZero) -> Self;

    /// Converts the value to a `u128`, which every value fits in.
    fn into_u128(self) -> u128;

    /// Converts a `u128` to this type, or returns `None` if it does not fit.
    fn from_u128(v: u128) -> Option<Self>;

    /// Converts a `u128` to this type, like [`from_u128`](Self::from_u128), but
    /// without checking that it fits.
    ///
    /// # Safety
    ///
    /// `v` must fit in this type, meaning [`from_u128`](Self::from_u128)
    /// returns `Some` for it.
    unsafe fn from_u128_unchecked(v: u128) -> Self;
}

mod sealed {
    /// Keeps [`KeyPiece`](super::KeyPiece) from being implemented outside
    /// this crate.
    pub trait Sealed {}
}

macro_rules! impl_key_piece {
    ($($t:ty)*) => {
        $(
            impl sealed::Sealed for $t {}

            // This macro only implements the trait for the standard unsigned
            // integers, which the contract at the top of this file is written
            // for. Every method forwards to the integer's own operation or to
            // an exact cast, and the largest value of every unsigned integer is
            // odd.
            impl KeyPiece for $t {
                type NonZero = NonZero<$t>;

                const ZERO: Self = 0;
                const ONE: Self = 1;
                const MAX: Self = <$t>::MAX;
                const BITS: u32 = <$t>::BITS;

                #[inline]
                fn checked_add(self, rhs: Self) -> Option<Self> {
                    <$t>::checked_add(self, rhs)
                }

                #[inline]
                fn wrapping_add(self, rhs: Self) -> Self {
                    <$t>::wrapping_add(self, rhs)
                }

                #[inline]
                fn wrapping_sub(self, rhs: Self) -> Self {
                    <$t>::wrapping_sub(self, rhs)
                }

                #[inline]
                fn is_odd(self) -> bool {
                    self & 1 == 1
                }

                #[inline]
                fn into_usize(self) -> Option<usize> {
                    usize::try_from(self).ok()
                }

                // An `as` cast only truncates a value that does not fit,
                // and the caller promises the value fits, so the cast is
                // exact.
                #[inline]
                unsafe fn into_usize_unchecked(self) -> usize {
                    debug_assert!(usize::try_from(self).is_ok());
                    self as usize
                }

                #[inline]
                fn from_usize(v: usize) -> Option<Self> {
                    <$t>::try_from(v).ok()
                }

                // An `as` cast from a `usize` is exact here too, because the
                // caller promises that `v` fits in this type.
                #[inline]
                unsafe fn from_usize_unchecked(v: usize) -> Self {
                    debug_assert!(<$t>::try_from(v).is_ok());
                    v as $t
                }

                #[inline]
                fn into_non_zero(self) -> Option<Self::NonZero> {
                    NonZero::new(self)
                }

                #[inline]
                unsafe fn into_non_zero_unchecked(self) -> Self::NonZero {
                    debug_assert!(self != 0);
                    // SAFETY: the caller promises the value is not zero.
                    unsafe { NonZero::new_unchecked(self) }
                }

                #[inline]
                fn from_non_zero(v: Self::NonZero) -> Self {
                    v.get()
                }

                #[inline]
                fn into_u128(self) -> u128 {
                    self as u128
                }

                #[inline]
                fn from_u128(v: u128) -> Option<Self> {
                    <$t>::try_from(v).ok()
                }

                // An `as` cast from a `u128` is exact here too, because the
                // caller promises that `v` fits in this type.
                #[inline]
                unsafe fn from_u128_unchecked(v: u128) -> Self {
                    debug_assert!(<$t>::try_from(v).is_ok());
                    v as $t
                }
            }
        )*
    };
}

impl_key_piece!(u8 u16 u32 u64 u128 usize);