gnat 0.1.8

//! This crate provides type-level natural numbers, similar to [`typenum`](https://docs.rs/typenum/latest/typenum/).
//!
//! A type-level number is a type that represents a number. The [`Nat`] trait takes the role of the
//! "type-level number type", i.e. one accepts a type-level number using a generic parameter with
//! bound [`Nat`].
//!
//! The use cases are the same as those of generic consts.
//!
//! `gnat` differs from `typenum` in that its [`Nat`] trait is not a marker trait, but defines
//! enough (internal) structure to be able to define and use operations on it, generically.
//!
//! This crate is more expressive than `typenum` or `generic_const_exprs`.
//! For example, consider the case of concatenating arrays at compile time:
//! ```
#![cfg_attr(doctest, doc = "```\n```compile_fail")]
//! #![feature(generic_const_exprs)]
//! const fn concat_arrays_gcex<T, const M: usize, const N: usize>(
//!     a: [T; M],
//!     b: [T; N],
//! ) -> [T; M + N]
//! where
//!     [T; M + N]:, // well-formedness bound
//! {
//!     todo!()
//! }
//!
//! use generic_array::{GenericArray, ArrayLength};
//! const fn concat_arrays_tnum<T, M: ArrayLength, N: ArrayLength>(
//!     a: GenericArray<T, M>,
//!     b: GenericArray<T, N>,
//! ) -> GenericArray<T, typenum::op!(M + N)>
//! where // ArrayLength is not enough, we also need to add a bound for `+`
//!     M: std::ops::Add<N, Output: ArrayLength>,
//! {
//!     todo!()
//! }
//! ```
//! Using this crate:
//! ```
//! use gnat::{Nat, array::Arr};
//! const fn concat_arrays_gnat<T, M: Nat, N: Nat>(
//!     a: Arr<T, M>,
//!     b: Arr<T, N>,
//! ) -> Arr<T, gnat::eval!(M + N)> { // no extra bounds!
//!     a.concat_arr(b).retype()
//! }
//! ```
//!
//! Because we do not require any bounds at all for operations, this also means that we can write
//! recursive functions over [`Nat`] parameters, the equvialent of which is almost impossible in typenum
//! and `generic_const_exprs`, since it would require recursively specifying that the output of the
//! operation can be operated on again:
//! ```compile_fail
//! fn recursive_gcex<const N: usize>() -> u32
//! where
//!     [(); N / 2]:,
//!     [(); { N / 2 } / 2]:,
//!     // ... we would need infinitely many bounds, even though we always reach 0
//! {
//!     if N == 0 {
//!         0
//!     } else {
//!         recursive_gce::<{ N / 2 }>() + 1
//!     }
//! }
//!
//! use {std::ops::Div, typenum::P2};
//! fn recursive_tnum<N>() -> u32
//! where
//!     N: Div<P2, Output: Div<P2, Output: Div<P2>>> + typenum::Unsigned
//!     // Again, we would need infinitely many bounds
//! {
//!     if N::USIZE == 0 {
//!         0
//!     } else {
//!         recursive_gce::<typenum::op!(N / 2)>() + 1
//!     }
//! }
//! ```
//! ```
//! use gnat::Nat;
//! fn recursive_gnat<N: Nat>() -> u32 {
//!     if gnat::to_usize::<N>() == Some(0) {
//!         0
//!     } else {
//!         recursive_gnat::<gnat::eval!(N / 2)>() + 1
//!     }
//! }
//! assert_eq!(recursive_gnat::<gnat::lit!(10)>(), 4); // 10 5 2 1 0
//! ```
//!
//! It is also possible to implement custom operations without any extra bounds needed to use them.
//! See the [`mod@expr`] module.
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(not(any(test, doc, feature = "std")), no_std)]
#![cfg_attr(test, recursion_limit = "1024")]
#![warn(
    clippy::nursery,
    clippy::missing_panics_doc,
    clippy::missing_const_for_fn,
    clippy::missing_errors_doc,
    clippy::undocumented_unsafe_blocks,
    missing_docs
)]
#![allow(clippy::redundant_pub_crate, clippy::use_self)]

#[cfg(feature = "alloc")]
extern crate alloc;

// Nat Implementation internals
mod internals;
mod uimpl;

// Macro implementation details
#[doc(hidden)]
pub mod __mac;

// internal utils
mod const_fmt;
mod maxint;
mod num;
mod utils;

// Public API
pub mod array;
pub mod condty;
pub mod consts;
pub mod expr;

mod nat_api;
pub use nat_api::*;

/// Trait for type-level natural numbers.
///
/// See the [crate level documentation](crate).
///
/// It is guaranteed that there is a one-to-one correspondence between
/// the natural numbers including zero and the types that implement this trait.
#[diagnostic::on_unimplemented(
    message = "`{Self}` is not a `gnat::Nat`",
    label = "`{Self}` is expected to implement `gnat::Nat` directly",
    note = "Consider using `gnat::Eval<{Self}>` if `{Self}: gnat::NatExpr`"
)]
pub trait Nat: Sized + 'static + internals::NatSealed + NatExpr<Eval = Self> {}

/// Trait for deferred [`Nat`] expressions.
///
/// This is not only a conversion trait, but forms an important part in how most operations are
/// implemented. See the [`mod@expr`] module.
#[diagnostic::on_unimplemented(
    message = "Cannot convert `{Self}` to a `gnat::Nat`",
    label = "To be used like a `Nat`, `{Self}` must implement `gnat::NatExpr`"
)]
pub trait NatExpr {
    /// Evaluates to [`Nat`].
    type Eval: Nat;
}

/// Turns an integer literal into a [`Nat`].
///
/// If you have a small constant value that is not a literal, use [`consts::Usize`].
///
/// # Examples
/// ```
/// #![recursion_limit = "1024"] // `lit!` doesn't recurse, the type is just long
///
/// assert_eq!(gnat::to_u128::<gnat::lit!(1)>(), Some(1));
/// assert_eq!(
///     gnat::to_u128::<gnat::lit!(100000000000000000000000000000)>(),
///     Some(100000000000000000000000000000),
/// )
/// ```
#[macro_export]
macro_rules! lit {
    (0) => {
        $crate::__mac::lit::_0
    };
    (1) => {
        $crate::__mac::lit::_1
    };
    ($l:literal) => {
        $crate::__mac::proc::__lit! {
            ($l)
            ($crate::__mac::lit::_U)
            ($crate::__mac::lit::_0)
            ($crate::__mac::lit::_1)
        }
    };
}

/// Converts expression syntax into [`NatExpr`] type expressions.
///
/// # Examples
/// ```
/// # macro_rules! chk_same_type {
/// #     ($l:ty, $r:ty $(,)?) => { let _: $l = panic!() as $r; };
/// # }
/// fn with_exprs<A: gnat::NatExpr, B: gnat::NatExpr>() {
///     // Unsuffixed literals are translated to `Nat`s
///     chk_same_type!(
///         gnat::expr! { 2 },
///         gnat::lit!(2),
///     );
///     // Most operators map to their correspondingly named operation
///     chk_same_type!(
///         gnat::expr! { A + B },
///         gnat::expr::Add<A, B>,
///     );
///     chk_same_type!(
///         gnat::expr! { A == B },
///         gnat::expr::Eq<A, B>,
///     );
///     // Subtraction is saturating
///     chk_same_type!(
///         gnat::expr! { A - B },
///         gnat::expr::SatSub<A, B>,
///     );
///     // `!` uses logical negation
///     chk_same_type!(
///         gnat::expr! { !A },
///         gnat::expr::IsZero<A>,
///     );
///     // Function calls translate to type paths
///     chk_same_type!(
///         gnat::expr! { gnat::expr::AbsDiff(A, B) },
///         gnat::expr::AbsDiff<A, B>,
///     );
///     // Expression paths also translate to type paths
///     chk_same_type!(
///         gnat::expr! { gnat::expr::AbsDiff::<A, B> },
///         gnat::expr::AbsDiff<A, B>,
///     );
///     // Conditionals are also supported
///     chk_same_type!(
///         gnat::expr! { if A { B } else { 2 * B } },
///         gnat::expr::If<
///             A,
///             B,
///             gnat::expr::Mul<gnat::lit!(2), B>,
///         >,
///     );
/// }
/// ```
#[macro_export]
#[cfg(feature = "macros")]
macro_rules! expr {
    { $($t:tt)* } => { $crate::__mac::proc::expr!($($t)*) };
}

/// Same as [`expr!`] wrapped in [`Eval`]. Useful for use with [`mod@array`].
///
/// # Examples
/// The [`mod@array`] uses [`Nat`] instead of [`NatExpr`] (for better type inference), so
/// this is more convenient than [`expr!`]+[`Eval`]:
/// ```
/// use gnat::{Nat, array::*};
/// fn concat<T, M: Nat, N: Nat>(a: Arr<T, M>, b: Arr<T, N>) -> Arr<T, gnat::eval! { M + N }> {
///     a.concat_arr(b).retype()
/// }
/// ```
#[macro_export]
#[cfg(feature = "macros")]
macro_rules! eval {
    { $($t:tt)* } => { $crate::Eval<$crate::expr!($($t)*)> };
}

/// Converts type alias syntax into a [`NatExpr`] impl.
///
/// # Examples
/// ```
/// #[gnat::nat_expr]
/// type Factorial<N: gnat::NatExpr> = gnat::expr! {
///     if N {
///         Factorial(gnat::Eval(N - 1)) * N
///     } else {
///         1
///     }
/// };
/// assert_eq!(
///     gnat::to_u128::<Factorial<gnat::lit!(5)>>(),
///     Some(120),
/// );
/// ```
/// Equivalent code without this attribute:
/// ```
/// struct Factorial<N>(N);
/// impl<N: gnat::NatExpr> gnat::NatExpr for Factorial<N> {
///     type Eval = gnat::eval! {
///         if N {
///             Factorial(gnat::Eval(N - 1)) * N
///         } else {
///             1
///         }
///     };
/// }
/// ```
#[cfg(feature = "macros")]
pub use gnat_proc::nat_expr;