hash_arr_map 0.4.0

use alloc::{
    borrow::{Borrow, Cow, ToOwned},
    boxed::Box,
    string::{String, ToString},
};
use core::{
    convert::{TryFrom, TryInto},
    fmt,
    marker::PhantomData,
    num::{
        NonZeroI128,
        NonZeroI16,
        NonZeroI32,
        NonZeroI64,
        NonZeroI8,
        NonZeroIsize,
        NonZeroU128,
        NonZeroU16,
        NonZeroU32,
        NonZeroU64,
        NonZeroU8,
        NonZeroUsize,
    },
};

/// A value represented as an index.
///
/// # Valid indices
///
/// Valid indices are defined by the type `T` and its borrowed forms.
/// In order for an index to be valid, it must be allowed to be passed
/// into [`FromIndex::from_index`] without causing UB.
///
/// Created by either [`IntoIndex::into_index`] or [`Idx::try_new`].
#[derive(Eq, PartialEq, Debug)]
pub struct Idx<T: ?Sized> {
    v: NonZeroUsize,
    _phantom: PhantomData<T>,
}

impl<T: ?Sized> Clone for Idx<T> {
    fn clone(&self) -> Self {
        Self {
            v: self.v,
            _phantom: PhantomData,
        }
    }
}

impl<T: ?Sized> fmt::Display for Idx<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Display::fmt(&self.v, f)
    }
}

impl<T: ?Sized + NewIndex> Idx<T> {
    /// Create a new index with the specified value if the type allows
    /// it.
    #[must_use]
    pub fn try_new(v: NonZeroUsize) -> Option<Self> {
        if <T as NewIndex>::new_index_allowed(v) {
            // SAFETY: New indices with that value are allowed.
            Some(unsafe { Self::new(v) })
        } else {
            None
        }
    }

    /// Create a new index with the specified value if the type allows
    /// it.
    #[must_use]
    crate fn try_new_usize(v: usize) -> Option<Self> {
        NonZeroUsize::new(v).and_then(Self::try_new)
    }
}

impl<T: ?Sized> Idx<T> {
    /// Create a new index with the specific value.
    ///
    /// # Safety
    ///
    /// The value must be a [valid index][idx].
    ///
    /// [idx]: #valid-indices
    #[must_use]
    pub const unsafe fn new(v: NonZeroUsize) -> Self {
        Self {
            v,
            _phantom: PhantomData,
        }
    }

    /// Same as [`Self::new`], except that `v` can be zero, and
    /// `None` will be returned.
    ///
    /// # Safety
    ///
    /// The value must either be a [valid index][idx] or zero.
    ///
    /// [idx]: #valid-indices
    #[must_use]
    pub const unsafe fn from_usize(v: usize) -> Option<Self> {
        if let Some(v) = NonZeroUsize::new(v) {
            Some(unsafe { Self::new(v) })
        } else {
            None
        }
    }

    #[must_use]
    pub const fn get(&self) -> NonZeroUsize {
        self.v
    }

    /// This reinterprets the index as a different type of index;
    /// essentially `Idx::<U>::new(self.get())`.
    ///
    /// # Safety
    ///
    /// The index must be a [valid index][idx] for type `U`.
    ///
    /// [idx]: #valid-indices
    #[must_use]
    pub const unsafe fn cast<U: ?Sized>(self) -> Idx<U> {
        unsafe { Idx::new(self.v) }
    }

    #[must_use]
    crate const unsafe fn new_unchecked(v: usize) -> Self {
        unsafe { Self::new(NonZeroUsize::new_unchecked(v)) }
    }
}

impl<T: ?Sized> Idx<T> {
    /// This reinterprets the index as a different type of index;
    /// essentially `Idx::<U>::new(self.get())`.
    ///
    /// This is restricted by [`Borrow`], meaning that it is type-safe.
    #[must_use]
    pub fn cast_safe<U: Borrow<T>>(self) -> Idx<U> {
        unsafe { Idx::new(self.v) }
    }
}

impl<T: ?Sized + FromIndex> Idx<T> {
    /// Convert this index into a value.
    ///
    /// A shorthand for [`<T as FromIndex>::from_index(self)`][fi].
    ///
    /// [fi]: FromIndex::from_index
    #[must_use]
    pub fn into_value(self) -> T {
        <T as FromIndex>::from_index(self)
    }
}

/// Whether a new index can be created out of thin air for the value.
pub unsafe trait NewIndex: FromIndex + IntoIndex {
    /// Whether the specified value is allowed to be used to make an
    /// index out of thin air.
    #[must_use]
    fn new_index_allowed(v: NonZeroUsize) -> bool;
}

/// An attempted conversion into an [`Idx`].
///
/// This is used when converting a value into an appropriate index. Therefore,
/// only types that are integer-like should return `Some` here.
///
/// Example:
///
/// ```rust
/// # use core::convert::{TryFrom, TryInto}; // If not edition-2021
/// use core::num::NonZeroUsize;
///
/// use hash_arr_map::{FromIndex, Idx, IntoIndex, NewIndex};
///
/// struct CouldBeAnIdx(i32);
///
/// impl IntoIndex for CouldBeAnIdx {
///     fn into_index(&self) -> Option<Idx<Self>> {
///         let nzu: NonZeroUsize = usize::try_from(self.0).ok()?.try_into().ok()?;
///         Some(unsafe { Idx::new(nzu) })
///     }
/// }
///
/// impl FromIndex for CouldBeAnIdx {
///     fn from_index(idx: Idx<Self>) -> Self {
///         Self(idx.get().get() as i32)
///     }
/// }
///
/// // Allow creating new indices out of thin air.
/// // To let `Ham::get_n` work.
/// unsafe impl NewIndex for CouldBeAnIdx {
///     fn new_index_allowed(idx: NonZeroUsize) -> bool {
///         i32::try_from(idx.get()).is_ok()
///     }
/// }
/// ```
pub trait IntoIndex {
    /// Try to convert `self` into an [`Idx`].
    ///
    /// ```rust
    /// use core::num::NonZeroUsize;
    ///
    /// use hash_arr_map::{Idx, IntoIndex};
    ///
    /// let a: i32 = 5;
    ///
    /// assert_eq!(
    ///     a.into_index(),
    ///     Some(unsafe { Idx::new(NonZeroUsize::new(5).unwrap()) })
    /// );
    /// ```
    #[allow(clippy::wrong_self_convention)]
    #[must_use]
    fn into_index(&self) -> Option<Idx<Self>>;
}

/// Conversion from an [`Idx`].
///
/// This trait implements conversion from an `Idx` into `Self`.
pub trait FromIndex: Sized + IntoIndex {
    /// Convert it.
    ///
    /// # Implementors
    ///
    /// The only guarantees about the index value is that it has either
    /// come from [`IntoIndex::into_index`], [`Idx::try_new`] or that it
    /// has come from a borrowed form of `Self`.
    ///
    /// By implementing `Borrow<T>` for your type, this loosens the
    /// guarantees given here, since this index could also come from `T`.
    #[must_use]
    fn from_index(idx: Idx<Self>) -> Self;
}

macro_rules! impl_test_index {
    ($($t:ty,)+) => {
        $(
            impl IntoIndex for $t {
                fn into_index(&self) -> Option<Idx<Self>> {
                    unsafe { Idx::from_usize(usize::try_from(*self).ok()?) }
                }
            }

            impl FromIndex for $t {
                fn from_index(idx: Idx<Self>) -> Self {
                    idx.get().get() as $t
                }
            }

            unsafe impl NewIndex for $t {
                fn new_index_allowed(idx: NonZeroUsize) -> bool {
                    <$t>::try_from(idx.get()).is_ok()
                }
            }
        )+
    }
}

impl_test_index! {
    i8,    u8,
    i16,   u16,
    i32,   u32,
    i64,   u64,
    i128,  u128,
    isize, usize,
}

macro_rules! impl_test_index_nonzero {
    ($($t:ty, $b:ty,)+) => {
        $(
            impl IntoIndex for $t {
                fn into_index(&self) -> Option<Idx<Self>> {
                    Some(unsafe { Idx::new((*self).try_into().ok()?) })
                }
            }

            impl FromIndex for $t {
                fn from_index(idx: Idx<Self>) -> Self {
                    unsafe { Self::new_unchecked(idx.get().get() as _) }
                }
            }

            unsafe impl NewIndex for $t {
                fn new_index_allowed(idx: NonZeroUsize) -> bool {
                    <$b>::try_from(idx.get()).is_ok()
                }
            }
        )+
    }
}

impl_test_index_nonzero! {
    NonZeroI8,    i8,    NonZeroU8,   u8,
    NonZeroI16,   i16,   NonZeroU16,  u16,
    NonZeroI32,   i32,   NonZeroU32,  u32,
    NonZeroI64,   i64,   NonZeroU64,  u64,
    NonZeroI128,  i128,  NonZeroU128, u128,
    NonZeroIsize, isize,
}

impl IntoIndex for NonZeroUsize {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(unsafe { Idx::new(*self) })
    }
}

impl FromIndex for NonZeroUsize {
    fn from_index(idx: Idx<Self>) -> Self {
        idx.get()
    }
}

unsafe impl NewIndex for NonZeroUsize {
    fn new_index_allowed(_: NonZeroUsize) -> bool {
        true
    }
}

impl IntoIndex for char {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(unsafe { u32::from(*self).into_index()?.cast() })
    }
}

impl FromIndex for char {
    fn from_index(idx: Idx<Self>) -> Self {
        unsafe { Self::from_u32_unchecked(idx.get().get() as u32) }
    }
}

unsafe impl NewIndex for char {
    fn new_index_allowed(idx: NonZeroUsize) -> bool {
        u32::try_from(idx.get())
            .ok()
            .and_then(Self::from_u32)
            .is_some()
    }
}

// Note: There is no matching FromIndex.
impl<T: IntoIndex> IntoIndex for &T {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(T::into_index(self)?.cast_safe())
    }
}

impl<T: IntoIndex> IntoIndex for Box<T> {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(T::into_index(self)?.cast_safe())
    }
}

impl<T: FromIndex> FromIndex for Box<T> {
    fn from_index(idx: Idx<Self>) -> Self {
        Self::new(T::from_index(unsafe { idx.cast() }))
    }
}

unsafe impl<T: NewIndex> NewIndex for Box<T> {
    fn new_index_allowed(idx: NonZeroUsize) -> bool {
        T::new_index_allowed(idx)
    }
}

impl<T: IntoIndex> IntoIndex for Option<T> {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(unsafe { self.as_ref().and_then(T::into_index)?.cast() })
    }
}

impl<T: FromIndex> FromIndex for Option<T> {
    fn from_index(idx: Idx<Self>) -> Self {
        Some(T::from_index(unsafe { idx.cast() }))
    }
}

unsafe impl<T: NewIndex> NewIndex for Option<T> {
    fn new_index_allowed(idx: NonZeroUsize) -> bool {
        T::new_index_allowed(idx)
    }
}

impl<T: IntoIndex, E> IntoIndex for Result<T, E> {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(unsafe { self.as_ref().ok()?.into_index()?.cast() })
    }
}

impl<T: FromIndex, E> FromIndex for Result<T, E> {
    fn from_index(idx: Idx<Self>) -> Self {
        Ok(T::from_index(unsafe { idx.cast() }))
    }
}

unsafe impl<T: NewIndex, E> NewIndex for Result<T, E> {
    fn new_index_allowed(idx: NonZeroUsize) -> bool {
        T::new_index_allowed(idx)
    }
}

impl<T: ?Sized + IntoIndex + ToOwned> IntoIndex for Cow<'_, T> {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some(T::into_index(self)?.cast_safe())
    }
}

impl<T: ?Sized + IntoIndex + ToOwned> FromIndex for Cow<'static, T>
where
    <T as ToOwned>::Owned: FromIndex,
{
    fn from_index(idx: Idx<Self>) -> Self {
        Self::Owned(FromIndex::from_index(unsafe { idx.cast() }))
    }
}

unsafe impl<T: ?Sized + IntoIndex + ToOwned> NewIndex for Cow<'static, T>
where
    <T as ToOwned>::Owned: NewIndex,
{
    fn new_index_allowed(idx: NonZeroUsize) -> bool {
        <T as ToOwned>::Owned::new_index_allowed(idx)
    }
}

impl IntoIndex for str {
    fn into_index(&self) -> Option<Idx<Self>> {
        if self.starts_with('0') {
            None
        } else {
            let u = self.bytes().try_fold(0, |acc, c| -> Option<usize> {
                acc.checked_mul(10)?
                    .checked_add(matches!(c, b'0'..=b'9').then(|| c - b'0')? as usize)
            })?;
            unsafe { Idx::from_usize(u) }
        }
    }
}

impl IntoIndex for String {
    fn into_index(&self) -> Option<Idx<Self>> {
        Some((**self).into_index()?.cast_safe())
    }
}

impl FromIndex for String {
    fn from_index(idx: Idx<Self>) -> Self {
        idx.to_string()
    }
}

unsafe impl NewIndex for String {
    fn new_index_allowed(_: NonZeroUsize) -> bool {
        true
    }
}