commonware_utils/

lib.rs

//! Leverage common functionality across multiple primitives.

#![doc(
    html_logo_url = "https://commonware.xyz/imgs/rustdoc_logo.svg",
    html_favicon_url = "https://commonware.xyz/favicon.ico"
)]
#![cfg_attr(not(any(feature = "std", test)), no_std)]

commonware_macros::stability_scope!(ALPHA, cfg(any(feature = "std", test)) {
    pub use rng::{Entropy, FuzzRng, ScriptedRng, TestRng, test_rng};
});
commonware_macros::stability_scope!(BETA {
    #[cfg(not(feature = "std"))]
    extern crate alloc;

    /// Lossless integer conversions that std provides no [From] impl for
    /// (for example `NonZeroU16` or `usize` into `u64`).
    pub trait Widen<T> {
        /// Convert without loss.
        fn widen(self) -> T;
    }

    macro_rules! impl_widen {
        ($($nz:ty => $($t:ty),+);+ $(;)?) => {$($(
            impl Widen<$t> for $nz {
                #[inline]
                fn widen(self) -> $t {
                    <$t>::from(self.get())
                }
            }
        )+)+};
    }
    impl_widen!(
        core::num::NonZeroU8 => u16, u32, u64, u128, usize;
        core::num::NonZeroU16 => u32, u64, u128, usize;
        core::num::NonZeroU32 => u64, u128;
        core::num::NonZeroU64 => u128;
    );

    impl Widen<usize> for u32 {
        #[inline]
        fn widen(self) -> usize {
            const { assert!(Self::BITS <= usize::BITS) };
            self as usize
        }
    }

    impl Widen<u64> for usize {
        #[inline]
        fn widen(self) -> u64 {
            const { assert!(Self::BITS <= u64::BITS) };
            self as u64
        }
    }

    #[cfg(not(feature = "std"))]
    use alloc::{boxed::Box, vec::Vec};
    use bytes::{BufMut, BytesMut};
    use core::time::Duration;
    pub mod faults;
    pub use faults::{Faults, N3f1, N5f1};

    pub mod sequence;
    pub use sequence::{Array, Span};

    pub mod hostname;
    pub use hostname::Hostname;

    pub mod bitmap;
    pub mod cache;
    pub mod handles;
    pub mod iter;
    pub mod ordered;
    pub mod prefetch;
    pub mod probability;
    pub use probability::Probability;
    pub mod range;
    pub mod sampling;

    use commonware_codec::{
        Buf, EncodeSize, Error as CodecError, MaxEncodeSize, Read, ReadExt, Write, varint::UInt,
    };

    /// Maximum byte size representable by an [allocation layout](core::alloc::Layout).
    ///
    /// A [`Vec`] whose element type `T` is not zero-sized holds at most
    /// `MAX_ALLOCATION_BYTES / size_of::<T>()` elements. A `Vec` of a zero-sized type never
    /// allocates.
    pub const MAX_ALLOCATION_BYTES: usize = isize::MAX as usize;

    /// 64-bit golden-ratio-derived odd mixing constant.
    ///
    /// Equal to `floor(2^64 / phi)`. Because it is odd, multiplication by it
    /// is a bijection modulo `2^64`.
    pub const GOLDEN_RATIO: u64 = 0x9e37_79b9_7f4a_7c15;

    /// Represents a participant/validator index within a consensus committee.
    ///
    /// Participant indices are used to identify validators in attestations,
    /// votes, and certificates. The index corresponds to the position of the
    /// validator's public key in the ordered participant set.
    #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
    #[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
    pub struct Participant(u32);

    impl Participant {
        /// Creates a new participant from a u32 index.
        pub const fn new(index: u32) -> Self {
            Self(index)
        }

        /// Creates a new participant from a usize index.
        ///
        /// # Panics
        ///
        /// Panics if `index` exceeds `u32::MAX`.
        pub fn from_usize(index: usize) -> Self {
            Self(u32::try_from(index).expect("participant index exceeds u32::MAX"))
        }

        /// Returns the underlying u32 index.
        pub const fn get(self) -> u32 {
            self.0
        }
    }

    impl From<Participant> for usize {
        fn from(p: Participant) -> Self {
            p.0 as Self
        }
    }

    impl core::fmt::Display for Participant {
        fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl Read for Participant {
        type Cfg = ();

        fn read_cfg(buf: &mut impl Buf, _cfg: &Self::Cfg) -> Result<Self, CodecError> {
            let value: u32 = UInt::read(buf)?.into();
            Ok(Self(value))
        }
    }

    impl Write for Participant {
        fn write(&self, buf: &mut impl bytes::BufMut) {
            UInt(self.0).write(buf);
        }
    }

    impl EncodeSize for Participant {
        fn encode_size(&self) -> usize {
            UInt(self.0).encode_size()
        }
    }

    impl MaxEncodeSize for Participant {
        const MAX_ENCODE_SIZE: usize = UInt::<u32>::MAX_ENCODE_SIZE;
    }

    /// A type that can be constructed from an iterator, possibly failing.
    pub trait TryFromIterator<T>: Sized {
        /// The error type returned when construction fails.
        type Error;

        /// Attempts to construct `Self` from an iterator.
        fn try_from_iter<I: IntoIterator<Item = T>>(iter: I) -> Result<Self, Self::Error>;
    }

    /// Extension trait for iterators that provides fallible collection.
    pub trait TryCollect: Iterator + Sized {
        /// Attempts to collect elements into a collection that may fail.
        fn try_collect<C: TryFromIterator<Self::Item>>(self) -> Result<C, C::Error> {
            C::try_from_iter(self)
        }
    }

    impl<I: Iterator> TryCollect for I {}

    /// Alias for boxed errors that are `Send` and `Sync`.
    pub type BoxedError = Box<dyn core::error::Error + Send + Sync>;

    /// Computes the union of two byte slices.
    pub fn union(a: &[u8], b: &[u8]) -> Vec<u8> {
        let mut union = Vec::with_capacity(a.len() + b.len());
        union.extend_from_slice(a);
        union.extend_from_slice(b);
        union
    }

    /// Concatenate a namespace and a message, prepended by a varint encoding of the namespace length.
    ///
    /// This produces a unique byte sequence (i.e. no collisions) for each `(namespace, msg)` pair.
    pub fn union_unique(namespace: &[u8], msg: &[u8]) -> Vec<u8> {
        use commonware_codec::EncodeSize;
        let len_prefix = namespace.len();
        let mut buf =
            BytesMut::with_capacity(len_prefix.encode_size() + namespace.len() + msg.len());
        len_prefix.write(&mut buf);
        BufMut::put_slice(&mut buf, namespace);
        BufMut::put_slice(&mut buf, msg);
        buf.into()
    }

    /// Compute the modulo of bytes interpreted as a big-endian integer.
    ///
    /// This function is used to select a random entry from an array when the bytes are a random seed.
    ///
    /// # Panics
    ///
    /// Panics if `n` is zero.
    pub fn modulo(bytes: &[u8], n: u64) -> u64 {
        assert_ne!(n, 0, "modulus must be non-zero");

        let n = n as u128;
        let mut result = 0u128;
        for &byte in bytes {
            result = (result << 8) | (byte as u128);
            result %= n;
        }

        // Result is either 0 or modulo `n`, so we can safely cast to u64
        result as u64
    }

    /// Returns the larger of two sizes. Unlike [`Ord::max`], it can be evaluated in constant
    /// expressions.
    pub const fn max(a: usize, b: usize) -> usize {
        if a > b { a } else { b }
    }

    /// A wrapper around `Duration` that guarantees the duration is non-zero.
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
    pub struct NonZeroDuration(Duration);

    impl NonZeroDuration {
        /// Creates a `NonZeroDuration` if the given duration is non-zero.
        pub fn new(duration: Duration) -> Option<Self> {
            if duration == Duration::ZERO {
                None
            } else {
                Some(Self(duration))
            }
        }

        /// Creates a `NonZeroDuration` from the given duration, panicking if it's zero.
        pub fn new_panic(duration: Duration) -> Self {
            Self::new(duration).expect("duration must be non-zero")
        }

        /// Returns the wrapped `Duration`.
        pub const fn get(self) -> Duration {
            self.0
        }
    }

    impl From<NonZeroDuration> for Duration {
        fn from(nz_duration: NonZeroDuration) -> Self {
            nz_duration.0
        }
    }
});
commonware_macros::stability_scope!(BETA, cfg(any(feature = "std", test)) {
    pub mod rng;
    pub use rng::sys_rng;
});
commonware_macros::stability_scope!(BETA, cfg(feature = "std") {
    pub mod acknowledgement;
    pub use acknowledgement::Acknowledgement;

    pub mod net;
    pub use net::IpAddrExt;

    pub mod time;
    pub use time::{DurationExt, SystemTimeExt};

    pub mod rational;
    pub use rational::BigRationalExt;

    mod priority_set;
    pub use priority_set::PrioritySet;

    pub mod channel;
    pub mod concurrency;
    pub mod futures;
    pub mod sync;

    pub mod thread_local;
    pub use thread_local::Cached;
});
#[cfg(not(any(
    commonware_stability_GAMMA,
    commonware_stability_DELTA,
    commonware_stability_EPSILON,
    commonware_stability_RESERVED
)))] // BETA
pub mod vec;

/// A macro to create a `NonZeroUsize` from a value, panicking if the value is zero.
/// For literal values, validation occurs at compile time. For expressions, validation
/// occurs at runtime.
#[macro_export]
macro_rules! NZUsize {
    ($val:literal) => {
        const { ::core::num::NonZeroUsize::new($val).expect("value must be non-zero") }
    };
    ($val:expr) => {
        // This will panic at runtime if $val is zero.
        ::core::num::NonZeroUsize::new($val).expect("value must be non-zero")
    };
}

/// A macro to create a `NonZeroU8` from a value, panicking if the value is zero.
/// For literal values, validation occurs at compile time. For expressions, validation
/// occurs at runtime.
#[macro_export]
macro_rules! NZU8 {
    ($val:literal) => {
        const { ::core::num::NonZeroU8::new($val).expect("value must be non-zero") }
    };
    ($val:expr) => {
        // This will panic at runtime if $val is zero.
        ::core::num::NonZeroU8::new($val).expect("value must be non-zero")
    };
}

/// A macro to create a `NonZeroU16` from a value, panicking if the value is zero.
/// For literal values, validation occurs at compile time. For expressions, validation
/// occurs at runtime.
#[macro_export]
macro_rules! NZU16 {
    ($val:literal) => {
        const { ::core::num::NonZeroU16::new($val).expect("value must be non-zero") }
    };
    ($val:expr) => {
        // This will panic at runtime if $val is zero.
        ::core::num::NonZeroU16::new($val).expect("value must be non-zero")
    };
}

/// A macro to create a `NonZeroU32` from a value, panicking if the value is zero.
/// For literal values, validation occurs at compile time. For expressions, validation
/// occurs at runtime.
#[macro_export]
macro_rules! NZU32 {
    ($val:literal) => {
        const { ::core::num::NonZeroU32::new($val).expect("value must be non-zero") }
    };
    ($val:expr) => {
        // This will panic at runtime if $val is zero.
        ::core::num::NonZeroU32::new($val).expect("value must be non-zero")
    };
}

/// A macro to create a `NonZeroU64` from a value, panicking if the value is zero.
/// For literal values, validation occurs at compile time. For expressions, validation
/// occurs at runtime.
#[macro_export]
macro_rules! NZU64 {
    ($val:literal) => {
        const { ::core::num::NonZeroU64::new($val).expect("value must be non-zero") }
    };
    ($val:expr) => {
        // This will panic at runtime if $val is zero.
        ::core::num::NonZeroU64::new($val).expect("value must be non-zero")
    };
}

/// Re-export of `commonware_formatting` so that the `fixed_bytes!` macro's
/// expansion can resolve `hex!` in any caller's namespace.
#[doc(hidden)]
pub use ::commonware_formatting as __formatting;

/// Macro for converting sequence of string literals containing hex-encoded data
/// into a [`crate::sequence::FixedBytes`] type.
#[cfg(not(any(
    commonware_stability_GAMMA,
    commonware_stability_DELTA,
    commonware_stability_EPSILON,
    commonware_stability_RESERVED
)))] // BETA
#[macro_export]
macro_rules! fixed_bytes {
    ($s:tt) => {
        const { $crate::sequence::FixedBytes::new($crate::__formatting::hex!($s)) }
    };
}

/// A macro to create a `NonZeroDuration` from a duration, panicking if the duration is zero.
#[macro_export]
macro_rules! NZDuration {
    ($val:expr) => {
        // This will panic at runtime if $val is zero.
        $crate::NonZeroDuration::new_panic($val)
    };
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::TestRng;
    use commonware_formatting::hex;
    use num_bigint::BigUint;
    use rand::RngExt as _;

    #[test]
    fn test_union() {
        // Test case 0: empty slices
        assert_eq!(union(&[], &[]), Vec::<u8>::new());

        // Test case 1: empty and non-empty slices
        assert_eq!(union(&[], &hex!("0x010203")), hex!("0x010203"));

        // Test case 2: non-empty and non-empty slices
        assert_eq!(
            union(&hex!("0x010203"), &hex!("0x040506")),
            hex!("0x010203040506")
        );
    }

    #[test]
    fn test_max() {
        const UNEQUAL: usize = max(3, 7);
        const REVERSED: usize = max(7, 3);
        const EQUAL: usize = max(5, 5);
        const ZERO: usize = max(0, 0);
        const LARGEST: usize = max(usize::MAX, 0);
        assert_eq!(UNEQUAL, 7);
        assert_eq!(REVERSED, 7);
        assert_eq!(EQUAL, 5);
        assert_eq!(ZERO, 0);
        assert_eq!(LARGEST, usize::MAX);
        assert_eq!(max(0, usize::MAX), usize::MAX);
    }

    #[test]
    fn test_union_unique() {
        let namespace = b"namespace";
        let msg = b"message";

        let length_encoding = vec![0b0000_1001];
        let mut expected = Vec::with_capacity(length_encoding.len() + namespace.len() + msg.len());
        expected.extend_from_slice(&length_encoding);
        expected.extend_from_slice(namespace);
        expected.extend_from_slice(msg);

        let result = union_unique(namespace, msg);
        assert_eq!(result, expected);
        assert_eq!(result.len(), result.capacity());
    }

    #[test]
    fn test_union_unique_zero_length() {
        let namespace = b"";
        let msg = b"message";

        let length_encoding = vec![0];
        let mut expected = Vec::with_capacity(length_encoding.len() + namespace.len() + msg.len());
        expected.extend_from_slice(&length_encoding);
        expected.extend_from_slice(msg);

        let result = union_unique(namespace, msg);
        assert_eq!(result, expected);
        assert_eq!(result.len(), result.capacity());
    }

    #[test]
    fn test_union_unique_long_length() {
        // Use a namespace of over length 127.
        let namespace = &b"n".repeat(256);
        let msg = b"message";

        let length_encoding = vec![0b1000_0000, 0b0000_0010];
        let mut expected = Vec::with_capacity(length_encoding.len() + namespace.len() + msg.len());
        expected.extend_from_slice(&length_encoding);
        expected.extend_from_slice(namespace);
        expected.extend_from_slice(msg);

        let result = union_unique(namespace, msg);
        assert_eq!(result, expected);
        assert_eq!(result.len(), result.capacity());
    }

    #[test]
    fn test_modulo() {
        // Test case 0: empty bytes
        assert_eq!(modulo(&[], 1), 0);

        // Test case 1: single byte
        assert_eq!(modulo(&hex!("0x01"), 1), 0);

        // Test case 2: multiple bytes
        assert_eq!(modulo(&hex!("0x010203"), 10), 1);

        // Test case 3: check equivalence with BigUint
        for i in 0..100 {
            let mut rng = TestRng::new(i);
            let bytes: [u8; 32] = rng.random();

            // 1-byte modulus
            let n = 11u64;
            let big_modulo = BigUint::from_bytes_be(&bytes) % n;
            let utils_modulo = modulo(&bytes, n);
            assert_eq!(big_modulo, BigUint::from(utils_modulo));

            // 2-byte modulus
            let n = 11_111u64;
            let big_modulo = BigUint::from_bytes_be(&bytes) % n;
            let utils_modulo = modulo(&bytes, n);
            assert_eq!(big_modulo, BigUint::from(utils_modulo));

            // 8-byte modulus
            let n = 0xDFFFFFFFFFFFFFFD;
            let big_modulo = BigUint::from_bytes_be(&bytes) % n;
            let utils_modulo = modulo(&bytes, n);
            assert_eq!(big_modulo, BigUint::from(utils_modulo));
        }
    }

    #[test]
    #[should_panic]
    fn test_modulo_zero_panics() {
        modulo(&hex!("0x010203"), 0);
    }

    #[test]
    fn test_non_zero_macros_compile_time() {
        // Literal values are validated at compile time.
        // NZU32!(0) would be a compile error.
        assert_eq!(NZUsize!(1).get(), 1);
        assert_eq!(NZU8!(2).get(), 2);
        assert_eq!(NZU16!(3).get(), 3);
        assert_eq!(NZU32!(4).get(), 4);
        assert_eq!(NZU64!(5).get(), 5);

        // Literals can be used in const contexts
        const _: core::num::NonZeroUsize = NZUsize!(1);
        const _: core::num::NonZeroU8 = NZU8!(2);
        const _: core::num::NonZeroU16 = NZU16!(3);
        const _: core::num::NonZeroU32 = NZU32!(4);
        const _: core::num::NonZeroU64 = NZU64!(5);
    }

    #[test]
    fn test_non_zero_macros_runtime() {
        // Runtime variables are validated at runtime
        let one_usize: usize = 1;
        let two_u8: u8 = 2;
        let three_u16: u16 = 3;
        let four_u32: u32 = 4;
        let five_u64: u64 = 5;

        assert_eq!(NZUsize!(one_usize).get(), 1);
        assert_eq!(NZU8!(two_u8).get(), 2);
        assert_eq!(NZU16!(three_u16).get(), 3);
        assert_eq!(NZU32!(four_u32).get(), 4);
        assert_eq!(NZU64!(five_u64).get(), 5);

        // Zero runtime values panic
        let zero_usize: usize = 0;
        let zero_u8: u8 = 0;
        let zero_u16: u16 = 0;
        let zero_u32: u32 = 0;
        let zero_u64: u64 = 0;

        assert!(std::panic::catch_unwind(|| NZUsize!(zero_usize)).is_err());
        assert!(std::panic::catch_unwind(|| NZU8!(zero_u8)).is_err());
        assert!(std::panic::catch_unwind(|| NZU16!(zero_u16)).is_err());
        assert!(std::panic::catch_unwind(|| NZU32!(zero_u32)).is_err());
        assert!(std::panic::catch_unwind(|| NZU64!(zero_u64)).is_err());

        // NZDuration is runtime-only since Duration has no literal syntax
        assert!(std::panic::catch_unwind(|| NZDuration!(Duration::ZERO)).is_err());
        assert_eq!(
            NZDuration!(Duration::from_secs(1)).get(),
            Duration::from_secs(1)
        );
    }

    #[test]
    fn test_non_zero_duration() {
        // Test case 0: zero duration
        assert!(NonZeroDuration::new(Duration::ZERO).is_none());

        // Test case 1: non-zero duration
        let duration = Duration::from_millis(100);
        let nz_duration = NonZeroDuration::new(duration).unwrap();
        assert_eq!(nz_duration.get(), duration);
        assert_eq!(Duration::from(nz_duration), duration);

        // Test case 2: panic on zero
        assert!(std::panic::catch_unwind(|| NonZeroDuration::new_panic(Duration::ZERO)).is_err());

        // Test case 3: ordering
        let d1 = NonZeroDuration::new(Duration::from_millis(100)).unwrap();
        let d2 = NonZeroDuration::new(Duration::from_millis(200)).unwrap();
        assert!(d1 < d2);
    }

    #[test]
    fn test_participant_constructors() {
        assert_eq!(Participant::new(0).get(), 0);
        assert_eq!(Participant::new(42).get(), 42);
        assert_eq!(Participant::from_usize(0).get(), 0);
        assert_eq!(Participant::from_usize(42).get(), 42);
        assert_eq!(Participant::from_usize(u32::MAX as usize).get(), u32::MAX);
    }

    #[test]
    #[should_panic(expected = "participant index exceeds u32::MAX")]
    fn test_participant_from_usize_overflow() {
        Participant::from_usize((u32::MAX as usize) + 1);
    }

    #[test]
    fn test_participant_display() {
        assert_eq!(format!("{}", Participant::new(0)), "0");
        assert_eq!(format!("{}", Participant::new(42)), "42");
        assert_eq!(format!("{}", Participant::new(1000)), "1000");
    }

    #[test]
    fn test_participant_ordering() {
        assert!(Participant::new(0) < Participant::new(1));
        assert!(Participant::new(5) < Participant::new(10));
        assert!(Participant::new(10) > Participant::new(5));
        assert_eq!(Participant::new(42), Participant::new(42));
    }

    #[test]
    fn test_participant_encode_decode() {
        use commonware_codec::{DecodeExt, Encode};

        let cases = vec![0u32, 1, 127, 128, 255, 256, u32::MAX];
        for value in cases {
            let participant = Participant::new(value);
            let encoded = participant.encode();
            assert_eq!(encoded.len(), participant.encode_size());
            let decoded = Participant::decode(encoded).unwrap();
            assert_eq!(participant, decoded);
        }
    }

    #[cfg(feature = "arbitrary")]
    mod conformance {
        use super::*;
        use commonware_codec::conformance::CodecConformance;

        commonware_conformance::conformance_tests! {
            CodecConformance<Participant>,
        }
    }
}