//! A vector type that guarantees at least one element. use crate::TryFromIterator; #[cfg(not(feature = "std"))] use alloc::{vec, vec::Vec}; use bytes::{Buf, BufMut}; use commonware_codec::{EncodeSize, RangeCfg, Read, Write}; use core::{ num::NonZeroUsize, ops::{Deref, DerefMut}, }; use thiserror::Error; /// Errors that can occur when creating a [`NonEmptyVec`]. #[derive(Error, Debug, PartialEq, Eq)] pub enum Error { /// The collection was empty. #[error("cannot create NonEmptyVec from empty collection")] Empty, } /// A vector that is guaranteed to contain at least one element. #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct NonEmptyVec(Vec); impl NonEmptyVec { /// Creates a new [`NonEmptyVec`] with a single element. pub fn new(first: T) -> Self { Self(vec![first]) } /// Creates a [`NonEmptyVec`] from a [`Vec`] without returning a `Result`. /// /// # Panics /// /// Panics if the vector is empty. pub fn from_unchecked(vec: Vec) -> Self { assert!( !vec.is_empty(), "NonEmptyVec::from_unchecked: vector is empty" ); Self(vec) } /// Returns the number of elements in the vector. /// /// This is guaranteed to be at least 1. pub const fn len(&self) -> NonZeroUsize { NonZeroUsize::new(self.0.len()).unwrap() } /// Returns `true` if the vector contains exactly one element. pub const fn is_singleton(&self) -> bool { self.0.len() == 1 } /// Returns a reference to the first element. /// /// Unlike [`slice::first`], this doesn't return an `Option`. pub fn first(&self) -> &T { self.0.first().unwrap() } /// Returns a mutable reference to the first element. /// /// Unlike [`slice::first_mut`], this doesn't return an `Option`. pub fn first_mut(&mut self) -> &mut T { self.0.first_mut().unwrap() } /// Returns a reference to the last element. /// /// Unlike [`slice::last`], this doesn't return an `Option`. pub fn last(&self) -> &T { self.0.last().unwrap() } /// Returns a mutable reference to the last element. /// /// Unlike [`slice::last_mut`], this doesn't return an `Option`. pub fn last_mut(&mut self) -> &mut T { self.0.last_mut().unwrap() } /// Maps each element to a new value, preserving the non-empty guarantee. pub fn map U>(&self, f: F) -> NonEmptyVec { NonEmptyVec(self.0.iter().map(f).collect()) } /// Consumes the vector and maps each element to a new value. pub fn map_into U>(self, f: F) -> NonEmptyVec { NonEmptyVec(self.0.into_iter().map(f).collect()) } /// Appends an element to the back of the vector. pub fn push(&mut self, value: T) { self.0.push(value); } /// Inserts an element at position `index`. /// /// # Panics /// /// Panics if `index > len`. pub fn insert(&mut self, index: usize, element: T) { self.0.insert(index, element); } /// Extends the vector with the contents of an iterator. pub fn extend>(&mut self, iter: I) { self.0.extend(iter); } /// Resizes the vector to the specified length. /// /// If `new_len` is greater than `len()`, the vector is extended with clones /// of `value`. If `new_len` is less than `len()`, the vector is truncated. /// /// Unlike [`Vec::resize`], this takes [`NonZeroUsize`] to maintain the /// non-empty guarantee. pub fn resize(&mut self, new_len: NonZeroUsize, value: T) where T: Clone, { self.0.resize(new_len.get(), value); } /// Resizes the vector to the specified length using a closure. /// /// If `new_len` is greater than `len()`, the vector is extended with values /// generated by calling `f` repeatedly. If `new_len` is less than `len()`, /// the vector is truncated. /// /// Unlike [`Vec::resize_with`], this takes [`NonZeroUsize`] to maintain the /// non-empty guarantee. pub fn resize_with(&mut self, new_len: NonZeroUsize, f: F) where F: FnMut() -> T, { self.0.resize_with(new_len.get(), f); } /// Removes the last element and returns it, or `None` if there is only one /// element. /// /// This ensures the vector always has at least one element. pub fn pop(&mut self) -> Option { if self.0.len() > 1 { self.0.pop() } else { None } } /// Removes and returns the element at position `index`, or `None` if /// removing would leave the vector empty. /// /// This ensures the vector always has at least one element. /// /// # Panics /// /// Panics if `index >= len`. pub fn remove(&mut self, index: usize) -> Option { assert!(index < self.0.len(), "index out of bounds"); if self.0.len() > 1 { Some(self.0.remove(index)) } else { None } } /// Provides mutable access to the underlying vector via a closure. /// /// This is an escape hatch for operations not directly exposed by `NonEmptyVec`. /// /// # Panics /// /// Panics if the closure leaves the vector empty. /// /// # Examples /// /// ``` /// use commonware_utils::non_empty_vec; /// /// let mut v = non_empty_vec![3, 1, 2]; /// v.mutate(|vec| vec.sort()); /// assert_eq!(v.first(), &1); /// ``` pub fn mutate(&mut self, f: F) -> R where F: FnOnce(&mut Vec) -> R, { let result = f(&mut self.0); assert!( !self.0.is_empty(), "NonEmptyVec::mutate: closure left vector empty" ); result } /// Consumes the [`NonEmptyVec`] and returns the underlying [`Vec`]. pub fn into_vec(self) -> Vec { self.0 } } impl Deref for NonEmptyVec { type Target = [T]; fn deref(&self) -> &Self::Target { &self.0 } } impl DerefMut for NonEmptyVec { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 } } impl AsRef<[T]> for NonEmptyVec { fn as_ref(&self) -> &[T] { &self.0 } } impl AsRef> for NonEmptyVec { fn as_ref(&self) -> &Vec { &self.0 } } impl From> for Vec { fn from(vec: NonEmptyVec) -> Self { vec.0 } } impl TryFrom> for NonEmptyVec { type Error = Error; fn try_from(vec: Vec) -> Result { if vec.is_empty() { Err(Error::Empty) } else { Ok(Self(vec)) } } } impl TryFrom<&[T]> for NonEmptyVec { type Error = Error; fn try_from(slice: &[T]) -> Result { if slice.is_empty() { Err(Error::Empty) } else { Ok(Self(slice.to_vec())) } } } impl TryFrom<[T; N]> for NonEmptyVec { type Error = Error; fn try_from(arr: [T; N]) -> Result { if N == 0 { Err(Error::Empty) } else { Ok(Self(arr.into())) } } } impl TryFrom<&[T; N]> for NonEmptyVec { type Error = Error; fn try_from(arr: &[T; N]) -> Result { Self::try_from(arr.as_slice()) } } impl TryFromIterator for NonEmptyVec { type Error = Error; fn try_from_iter>(iter: I) -> Result { let vec: Vec = iter.into_iter().collect(); Self::try_from(vec) } } impl IntoIterator for NonEmptyVec { type Item = T; type IntoIter = as IntoIterator>::IntoIter; fn into_iter(self) -> Self::IntoIter { self.0.into_iter() } } impl<'a, T> IntoIterator for &'a NonEmptyVec { type Item = &'a T; type IntoIter = core::slice::Iter<'a, T>; fn into_iter(self) -> Self::IntoIter { self.0.iter() } } impl<'a, T> IntoIterator for &'a mut NonEmptyVec { type Item = &'a mut T; type IntoIter = core::slice::IterMut<'a, T>; fn into_iter(self) -> Self::IntoIter { self.0.iter_mut() } } impl Write for NonEmptyVec { fn write(&self, buf: &mut impl BufMut) { self.0.write(buf); } } impl EncodeSize for NonEmptyVec { fn encode_size(&self) -> usize { self.0.encode_size() } } impl Read for NonEmptyVec { type Cfg = (RangeCfg, T::Cfg); fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result { let items = Vec::read_cfg(buf, &(cfg.0.into(), cfg.1.clone()))?; if items.is_empty() { return Err(commonware_codec::Error::Invalid( "NonEmptyVec", "cannot decode empty vector", )); } Ok(Self(items)) } } #[cfg(feature = "arbitrary")] impl<'a, T: arbitrary::Arbitrary<'a>> arbitrary::Arbitrary<'a> for NonEmptyVec { fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result { let first: T = u.arbitrary()?; let rest: Vec = u.arbitrary()?; let mut vec = Vec::with_capacity(1 + rest.len()); vec.push(first); vec.extend(rest); Ok(Self(vec)) } } /// Creates a [`NonEmptyVec`] containing the given elements. /// /// # Forms /// /// | Syntax | Count type | Guarantee | /// |--------|------------|-----------| /// | `non_empty_vec![a, b, c]` | - | Compile-time (at least one element required) | /// | `non_empty_vec![elem; N]` | const `usize` | Compile-time (N must be const and > 0) | /// | `non_empty_vec![elem; NZUsize!(N)]` | [`NZUsize!`] | Runtime (panics if N == 0) | /// | `non_empty_vec![elem; @n]` | [`NonZeroUsize`] | Type-safe (n is already non-zero) | /// | `non_empty_vec![@v]` | - | Runtime (panics if v is empty) | /// /// The `@` marker is required for runtime [`NonZeroUsize`] values to distinguish /// them from const `usize` values, since declarative macros cannot inspect types. /// /// [`NZUsize!`]: crate::NZUsize /// /// # Examples /// /// ``` /// use commonware_utils::{non_empty_vec, NZUsize}; /// /// // List form /// let v = non_empty_vec![1, 2, 3]; /// assert_eq!(v.len().get(), 3); /// /// // Const repeat: N must be a const expression > 0 /// let v = non_empty_vec![42; 5]; /// assert_eq!(v.len().get(), 5); /// /// // NZUsize! form: convenient for inline literals /// let v = non_empty_vec![42; NZUsize!(3)]; /// assert_eq!(v.len().get(), 3); /// /// // Runtime form: use @ with any NonZeroUsize expression /// let n = NZUsize!(2); /// let v = non_empty_vec![42; @n]; /// assert_eq!(v.len().get(), 2); /// /// // Vec form: wrap an existing Vec (panics if empty) /// let vec = vec![1, 2, 3]; /// let v = non_empty_vec![@vec]; /// assert_eq!(v.len().get(), 3); /// ``` /// /// # Compile Errors /// /// ```compile_fail /// use commonware_utils::non_empty_vec; /// let empty = non_empty_vec![]; // error: no elements /// ``` /// /// ```compile_fail /// use commonware_utils::non_empty_vec; /// let zero = non_empty_vec![42; 0]; // error: count is 0 /// ``` /// /// ```compile_fail /// use commonware_utils::non_empty_vec; /// let n: usize = 5; /// let v = non_empty_vec![42; n]; // error: n is not const (use @n with NonZeroUsize) /// ``` #[macro_export] macro_rules! non_empty_vec { (@$vec:expr) => {{ $crate::vec::NonEmptyVec::from_unchecked($vec) }}; ($elem:expr; NZUsize!($n:expr)) => {{ $crate::vec::NonEmptyVec::from_unchecked(vec![$elem; $crate::NZUsize!($n).get()]) }}; ($elem:expr; @$n:expr) => {{ let n: core::num::NonZeroUsize = $n; $crate::vec::NonEmptyVec::from_unchecked(vec![$elem; n.get()]) }}; ($elem:expr; $n:expr) => {{ const N: usize = $n; const _: () = assert!(N > 0, "count must be greater than 0"); $crate::vec::NonEmptyVec::from_unchecked(vec![$elem; N]) }}; ($first:expr $(, $rest:expr)* $(,)?) => { $crate::vec::NonEmptyVec::from_unchecked(vec![$first $(, $rest)*]) }; } #[cfg(test)] mod tests { use super::*; use crate::{NZUsize, TryCollect}; use commonware_codec::Error as CodecError; use std::num::NonZeroUsize; #[test] fn test_new() { let v = NonEmptyVec::new(42); assert_eq!(v.len().get(), 1); assert_eq!(v.first(), &42); assert_eq!(v.last(), &42); } #[test] #[should_panic(expected = "vector is empty")] fn test_from_unchecked_panics_on_empty() { let _: NonEmptyVec = NonEmptyVec::from_unchecked(vec![]); } #[test] fn test_is_singleton() { let v = non_empty_vec![42]; assert!(v.is_singleton()); let v = non_empty_vec![1, 2]; assert!(!v.is_singleton()); let v = non_empty_vec![1, 2, 3]; assert!(!v.is_singleton()); } #[test] fn test_macro() { let v = non_empty_vec![1, 2, 3]; assert_eq!(v.len().get(), 3); assert_eq!(v.first(), &1); assert_eq!(v.last(), &3); let v = non_empty_vec![42]; assert_eq!(v.len().get(), 1); assert_eq!(v.first(), &42); // Trailing comma support let v = non_empty_vec![1, 2, 3,]; assert_eq!(v.len().get(), 3); // Const repeat syntax let v = non_empty_vec![42; 5]; assert_eq!(v.len().get(), 5); assert!(v.iter().all(|&x| x == 42)); let v = non_empty_vec![0; 1]; assert_eq!(v.len().get(), 1); assert_eq!(v.first(), &0); // NZUsize! macro form let v = non_empty_vec![99; NZUsize!(3)]; assert_eq!(v.len().get(), 3); assert!(v.iter().all(|&x| x == 99)); // Runtime repeat syntax with NonZeroUsize variable let n = NonZeroUsize::new(4).unwrap(); let v = non_empty_vec![7; @n]; assert_eq!(v.len().get(), 4); assert!(v.iter().all(|&x| x == 7)); // Vec wrap syntax let vec = vec![1, 2, 3]; let v = non_empty_vec![@vec]; assert_eq!(v.len().get(), 3); assert_eq!(&*v, &[1, 2, 3]); } #[test] fn test_try_from_vec() { let v: NonEmptyVec = vec![1, 2, 3].try_into().unwrap(); assert_eq!(v.len().get(), 3); let result: Result, _> = Vec::new().try_into(); assert_eq!(result, Err(Error::Empty)); } #[test] fn test_try_from_slice() { let v: NonEmptyVec = [1, 2, 3].as_slice().try_into().unwrap(); assert_eq!(v.len().get(), 3); let empty: &[i32] = &[]; let result: Result, _> = empty.try_into(); assert_eq!(result, Err(Error::Empty)); } #[test] fn test_try_from_array() { let v: NonEmptyVec = [1, 2, 3].try_into().unwrap(); assert_eq!(v.len().get(), 3); let result: Result, _> = [0i32; 0].try_into(); assert_eq!(result, Err(Error::Empty)); } #[test] fn test_try_from_iterator() { let v: NonEmptyVec = (1..=3).try_collect().unwrap(); assert_eq!(v.len().get(), 3); let result: Result, _> = core::iter::empty().try_collect(); assert_eq!(result, Err(Error::Empty)); } #[test] fn test_first_last() { let mut v = non_empty_vec![1, 2, 3]; assert_eq!(v.first(), &1); assert_eq!(v.last(), &3); *v.first_mut() = 10; *v.last_mut() = 30; assert_eq!(v.first(), &10); assert_eq!(v.last(), &30); } #[test] fn test_push() { let mut v = non_empty_vec![1]; v.push(2); v.push(3); assert_eq!(v.len().get(), 3); assert_eq!(v.last(), &3); } #[test] fn test_insert() { let mut v = non_empty_vec![1, 3]; v.insert(1, 2); assert_eq!(&*v, &[1, 2, 3]); } #[test] fn test_extend() { let mut v = non_empty_vec![1]; v.extend([2, 3, 4]); assert_eq!(v.len().get(), 4); assert_eq!(&*v, &[1, 2, 3, 4]); } #[test] fn test_resize() { // Grow let mut v = non_empty_vec![1, 2]; v.resize(NonZeroUsize::new(5).unwrap(), 0); assert_eq!(&*v, &[1, 2, 0, 0, 0]); // Shrink v.resize(NonZeroUsize::new(2).unwrap(), 0); assert_eq!(&*v, &[1, 2]); // Shrink to 1 (minimum) v.resize(NonZeroUsize::new(1).unwrap(), 0); assert_eq!(&*v, &[1]); } #[test] fn test_resize_with() { let mut counter = 0; let mut v = non_empty_vec![1]; v.resize_with(NonZeroUsize::new(4).unwrap(), || { counter += 1; counter * 10 }); assert_eq!(&*v, &[1, 10, 20, 30]); // Shrink (closure not called) v.resize_with(NonZeroUsize::new(2).unwrap(), || { panic!("should not be called") }); assert_eq!(&*v, &[1, 10]); } #[test] fn test_pop() { let mut v = non_empty_vec![1, 2, 3]; assert_eq!(v.pop(), Some(3)); assert_eq!(v.len().get(), 2); assert_eq!(v.pop(), Some(2)); assert_eq!(v.len().get(), 1); // Cannot pop the last element assert_eq!(v.pop(), None); assert_eq!(v.len().get(), 1); assert_eq!(v.first(), &1); } #[test] fn test_remove() { let mut v = non_empty_vec![1, 2, 3]; assert_eq!(v.remove(1), Some(2)); assert_eq!(&*v, &[1, 3]); assert_eq!(v.remove(0), Some(1)); assert_eq!(&*v, &[3]); // Cannot remove the last element assert_eq!(v.remove(0), None); assert_eq!(&*v, &[3]); } #[test] fn test_mutate() { let mut v = non_empty_vec![3, 1, 2, 1]; v.mutate(|vec| { vec.sort(); vec.dedup(); }); assert_eq!(&*v, &[1, 2, 3]); // Test that return value is propagated let mut v = non_empty_vec![1, 2, 3]; let sum: i32 = v.mutate(|vec| vec.iter().sum()); assert_eq!(sum, 6); } #[test] #[should_panic(expected = "closure left vector empty")] fn test_mutate_panics_on_empty() { let mut v = non_empty_vec![1]; v.mutate(|vec| vec.clear()); } #[test] fn test_deref() { let v = non_empty_vec![3, 1, 2]; // slice methods via Deref assert_eq!(v.len().get(), 3); assert!(v.contains(&2)); assert_eq!(v.get(1), Some(&1)); } #[test] fn test_deref_mut() { let mut v = non_empty_vec![3, 1, 2]; // Mutable slice methods via DerefMut v.sort(); assert_eq!(&*v, &[1, 2, 3]); v.reverse(); assert_eq!(&*v, &[3, 2, 1]); v.swap(0, 2); assert_eq!(&*v, &[1, 2, 3]); } #[test] fn test_into_vec() { let v = non_empty_vec![1, 2, 3]; let vec: Vec = v.into_vec(); assert_eq!(vec, vec![1, 2, 3]); } #[test] fn test_map() { let v = non_empty_vec![1, 2, 3]; let doubled = v.map(|x| x * 2); assert_eq!(&*doubled, &[2, 4, 6]); // Original unchanged assert_eq!(&*v, &[1, 2, 3]); } #[test] fn test_map_into() { let v = non_empty_vec![1, 2, 3]; let doubled = v.map_into(|x| x * 2); assert_eq!(&*doubled, &[2, 4, 6]); } #[test] fn test_from_non_empty_vec() { let v = non_empty_vec![1, 2, 3]; let vec: Vec = v.into(); assert_eq!(vec, vec![1, 2, 3]); } #[test] fn test_index() { let v = non_empty_vec![1, 2, 3]; assert_eq!(v[0], 1); assert_eq!(v[1], 2); assert_eq!(v[2], 3); assert_eq!(&v[0..2], &[1, 2]); // IndexMut let mut v = non_empty_vec![1, 2, 3]; v[0] = 10; v[1..3].copy_from_slice(&[20, 30]); assert_eq!(&*v, &[10, 20, 30]); } #[test] fn test_iterators() { let v = non_empty_vec![1, 2, 3]; // iter() let sum: i32 = v.iter().sum(); assert_eq!(sum, 6); // iter_mut() let mut v = non_empty_vec![1, 2, 3]; for x in v.iter_mut() { *x *= 2; } assert_eq!(&*v, &[2, 4, 6]); // IntoIterator (owned) let v = non_empty_vec![1, 2, 3]; let collected: Vec<_> = v.into_iter().collect(); assert_eq!(collected, vec![1, 2, 3]); // IntoIterator (borrowed) let v = non_empty_vec![1, 2, 3]; let collected: Vec<_> = (&v).into_iter().copied().collect(); assert_eq!(collected, vec![1, 2, 3]); // IntoIterator (borrowed mut) let mut v = non_empty_vec![1, 2, 3]; for x in &mut v { *x += 10; } assert_eq!(&*v, &[11, 12, 13]); } #[test] fn test_codec_roundtrip() { let v = non_empty_vec![1u8, 2, 3]; let mut buf = Vec::with_capacity(v.encode_size()); v.write(&mut buf); let decoded = NonEmptyVec::::read_cfg( &mut buf.as_slice(), &(RangeCfg::from(NZUsize!(1)..=NZUsize!(10)), ()), ) .unwrap(); assert_eq!(v, decoded); } #[test] fn test_codec_rejects_empty() { let empty: Vec = vec![]; let mut buf = Vec::new(); empty.write(&mut buf); let result = NonEmptyVec::::read_cfg(&mut buf.as_slice(), &(RangeCfg::from(..), ())); assert!(matches!( result, Err(CodecError::Invalid( "NonEmptyVec", "cannot decode empty vector" )) )); let result = NonEmptyVec::::read_cfg(&mut buf.as_slice(), &(RangeCfg::from(..NZUsize!(10)), ())); assert!(matches!( result, Err(CodecError::Invalid( "NonEmptyVec", "cannot decode empty vector" )) )); let result = NonEmptyVec::::read_cfg( &mut buf.as_slice(), &(RangeCfg::from(NZUsize!(1)..NZUsize!(10)), ()), ); assert!(matches!(result, Err(CodecError::InvalidLength(0)))); } #[test] fn test_as_ref() { let v = non_empty_vec![1, 2, 3]; let slice: &[i32] = v.as_ref(); assert_eq!(slice, &[1, 2, 3]); let vec_ref: &Vec = v.as_ref(); assert_eq!(vec_ref, &vec![1, 2, 3]); } }