non_empty_vec/
lib.rs

1//! Non-empty vector, with non-emptiness ensured by construction.
2
3#![cfg_attr(not(any(feature = "std", doc, test)), no_std)]
4
5extern crate alloc;
6
7use alloc::boxed::Box;
8use alloc::collections::TryReserveError;
9use alloc::vec;
10use alloc::vec::{Drain, IntoIter, Vec};
11use core::borrow::{Borrow, BorrowMut};
12use core::convert::TryFrom;
13use core::fmt::{Debug, Display, Formatter};
14use core::iter::{Extend, FusedIterator};
15use core::num::NonZeroUsize;
16use core::ops::{Bound, Deref, DerefMut, Index, IndexMut, RangeBounds};
17use core::slice::{Iter, IterMut, SliceIndex};
18
19#[cfg(feature = "std")]
20use std::io::{IoSlice, Write};
21
22#[cfg(feature = "serde")]
23use serde::{de::Error, Deserialize, Deserializer, Serialize, Serializer};
24
25/// Calls [`std::hint::unreachable_unchecked`] in release mode, and panics in debug mode.
26macro_rules! unreachable_unchecked {
27    () => {{
28        #[cfg(debug_assertions)]
29        ::core::unreachable!();
30        #[allow(unreachable_code)]
31        ::core::hint::unreachable_unchecked()
32    }};
33}
34
35/// Error from trying to convert from an empty [`Vec`].
36#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Hash)]
37pub struct EmptyError;
38
39impl Display for EmptyError {
40    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
41        write!(f, "vector must be non-empty")
42    }
43}
44
45#[cfg(feature = "std")]
46impl std::error::Error for EmptyError {}
47
48/// Non-empty vector, with non-emptiness ensured by construction.
49///
50/// Inherits slices' methods through the [`Deref`] and [`DerefMut`] traits.
51///
52/// [`Vec`]'s methods are manually overriden. Some important differences:
53/// * [`len`](Self::len) returns [`NonZeroUsize`] and [`is_empty`](Self::is_empty) always returns `false`.
54/// * [`first(_mut)`](Self::first), [`last(_mut)`](Self::last), [`split_first(_mut)`](Self::split_first), [`split_last(_mut)`](Self::split_last) don't return [`Option`].
55/// * [`pop`](Self::pop) and [`remove`](Self::remove) return `None` if there is only one element.
56#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
57pub struct NonEmpty<T>(Vec<T>);
58
59impl<T> NonEmpty<T> {
60    /// Constructs a non-empty vector with a single element.
61    #[inline]
62    pub fn new(v: T) -> Self {
63        Self(vec![v])
64    }
65
66    /// Constructs a non-empty vector with a single element and a specific capacity.
67    #[inline]
68    pub fn with_capacity(v: T, capacity: usize) -> Self {
69        let mut vec = Vec::with_capacity(capacity);
70        vec.push(v);
71        Self(vec)
72    }
73
74    /// Constructs a non-empty vector without checking its size.
75    ///
76    /// # Safety
77    ///
78    /// The vector should not be empty.
79    #[inline]
80    pub const unsafe fn new_unchecked(vec: Vec<T>) -> Self {
81        Self(vec)
82    }
83
84    #[inline]
85    pub fn as_slice(&self) -> &[T] {
86        &self.0
87    }
88
89    #[inline]
90    pub fn as_mut_slice(&mut self) -> &mut [T] {
91        &mut self.0
92    }
93
94    #[inline]
95    pub fn as_ptr(&self) -> *const T {
96        self.0.as_ptr()
97    }
98
99    #[inline]
100    pub fn as_mut_ptr(&mut self) -> *mut T {
101        self.0.as_mut_ptr()
102    }
103
104    #[inline]
105    pub fn leak<'a>(self) -> &'a mut [T] {
106        self.0.leak()
107    }
108
109    #[inline]
110    pub fn into_boxed_slice(self) -> Box<[T]> {
111        self.0.into_boxed_slice()
112    }
113
114    #[inline]
115    pub fn len(&self) -> NonZeroUsize {
116        unsafe { NonZeroUsize::new_unchecked(self.0.len()) }
117    }
118
119    #[inline]
120    pub const fn is_empty(&self) -> bool {
121        false
122    }
123
124    #[inline]
125    pub fn capacity(&self) -> usize {
126        self.0.capacity()
127    }
128
129    #[inline]
130    pub fn reserve(&mut self, additional: usize) {
131        self.0.reserve(additional)
132    }
133
134    #[inline]
135    pub fn reserve_exact(&mut self, additional: usize) {
136        self.0.reserve_exact(additional)
137    }
138
139    #[inline]
140    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
141        self.0.try_reserve(additional)
142    }
143
144    #[inline]
145    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
146        self.0.try_reserve_exact(additional)
147    }
148
149    #[inline]
150    pub fn shrink_to_fit(&mut self) {
151        self.0.shrink_to_fit()
152    }
153
154    #[inline]
155    pub fn shrink_to(&mut self, min_capacity: usize) {
156        self.0.shrink_to(min_capacity)
157    }
158
159    #[inline]
160    pub fn first(&self) -> &T {
161        unsafe { self.0.get_unchecked(0) }
162    }
163
164    #[inline]
165    pub fn first_mut(&mut self) -> &mut T {
166        unsafe { self.0.get_unchecked_mut(0) }
167    }
168
169    #[inline]
170    pub fn last(&self) -> &T {
171        let i = self.len().get() - 1;
172        unsafe { self.0.get_unchecked(i) }
173    }
174
175    #[inline]
176    pub fn last_mut(&mut self) -> &mut T {
177        let i = self.len().get() - 1;
178        unsafe { self.0.get_unchecked_mut(i) }
179    }
180
181    #[inline]
182    pub fn split_first(&self) -> (&T, &[T]) {
183        (&self[0], &self[1..])
184    }
185
186    #[inline]
187    pub fn split_first_mut(&mut self) -> (&mut T, &mut [T]) {
188        let split = self.0.split_at_mut(1);
189        (&mut split.0[0], split.1)
190    }
191
192    #[inline]
193    pub fn split_last(&self) -> (&T, &[T]) {
194        let len = self.len().get();
195        (&self[len - 1], &self[..(len - 1)])
196    }
197
198    #[inline]
199    pub fn split_last_mut(&mut self) -> (&mut T, &mut [T]) {
200        let i = self.len().get() - 1;
201        let split = self.0.split_at_mut(i);
202        (&mut split.1[0], split.0)
203    }
204
205    #[inline]
206    pub fn truncate(&mut self, len: NonZeroUsize) {
207        self.0.truncate(len.get())
208    }
209
210    #[inline]
211    pub fn resize(&mut self, new_len: NonZeroUsize, value: T)
212    where
213        T: Clone,
214    {
215        self.0.resize(new_len.get(), value)
216    }
217
218    #[inline]
219    pub fn resize_with<F>(&mut self, new_len: NonZeroUsize, f: F)
220    where
221        F: FnMut() -> T,
222    {
223        self.0.resize_with(new_len.get(), f)
224    }
225
226    #[inline]
227    pub fn pop(&mut self) -> Option<T> {
228        if self.0.len() <= 1 {
229            None
230        } else {
231            self.0.pop()
232        }
233    }
234
235    #[inline]
236    pub fn push(&mut self, v: T) {
237        self.0.push(v)
238    }
239
240    #[inline]
241    pub fn insert(&mut self, index: usize, element: T) {
242        self.0.insert(index, element)
243    }
244
245    #[inline]
246    pub fn remove(&mut self, index: usize) -> Option<T> {
247        if index == 0 && self.0.len() == 1 {
248            None
249        } else {
250            Some(self.0.remove(index))
251        }
252    }
253
254    #[inline]
255    pub fn swap_remove(&mut self, index: usize) -> Option<T> {
256        if index == 0 && self.0.len() == 1 {
257            None
258        } else {
259            Some(self.0.swap_remove(index))
260        }
261    }
262
263    #[inline]
264    pub fn append(&mut self, other: &mut Vec<T>) {
265        self.0.append(other)
266    }
267
268    #[inline]
269    pub fn extend_from_slice(&mut self, other: &[T])
270    where
271        T: Clone,
272    {
273        self.0.extend_from_slice(other)
274    }
275
276    #[inline]
277    pub fn extend_from_within<R>(&mut self, src: R)
278    where
279        T: Clone,
280        R: RangeBounds<usize>,
281    {
282        self.0.extend_from_within(src)
283    }
284
285    #[inline]
286    pub fn dedup(&mut self)
287    where
288        T: PartialEq,
289    {
290        self.0.dedup()
291    }
292
293    #[inline]
294    pub fn dedup_by<F>(&mut self, same_bucket: F)
295    where
296        F: FnMut(&mut T, &mut T) -> bool,
297    {
298        self.0.dedup_by(same_bucket)
299    }
300
301    #[inline]
302    pub fn dedup_by_key<F, K>(&mut self, key: F)
303    where
304        F: FnMut(&mut T) -> K,
305        K: PartialEq,
306    {
307        self.0.dedup_by_key(key)
308    }
309}
310
311impl<T: Debug> Debug for NonEmpty<T> {
312    #[inline]
313    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
314        self.0.fmt(f)
315    }
316}
317
318impl<T> From<(Vec<T>, T)> for NonEmpty<T> {
319    fn from((mut xs, x): (Vec<T>, T)) -> NonEmpty<T> {
320        xs.push(x);
321        NonEmpty(xs)
322    }
323}
324
325impl<T> From<(T, Vec<T>)> for NonEmpty<T> {
326    fn from((x, mut xs): (T, Vec<T>)) -> NonEmpty<T> {
327        xs.insert(0, x);
328        NonEmpty(xs)
329    }
330}
331
332impl<T> From<NonEmpty<T>> for Vec<T> {
333    fn from(v: NonEmpty<T>) -> Self {
334        v.0
335    }
336}
337
338/// Returns a unit-length vector containing the default element value.
339impl<T: Default> Default for NonEmpty<T> {
340    fn default() -> Self {
341        ne_vec![T::default()]
342    }
343}
344
345impl<T> TryFrom<Vec<T>> for NonEmpty<T> {
346    type Error = EmptyError;
347
348    fn try_from(xs: Vec<T>) -> Result<Self, Self::Error> {
349        if xs.is_empty() {
350            Err(EmptyError)
351        } else {
352            Ok(NonEmpty(xs))
353        }
354    }
355}
356
357impl<T> From<Box<NonEmptySlice<T>>> for NonEmpty<T> {
358    #[inline]
359    fn from(slice: Box<NonEmptySlice<T>>) -> Self {
360        let v = Vec::from(slice.into_boxed_slice());
361        // SAFETY: We constructed this vector from a `NonEmptySlice`,
362        // so it's guaranteed to be non-empty.
363        unsafe { Self::new_unchecked(v) }
364    }
365}
366
367impl<T> TryFrom<Box<[T]>> for NonEmpty<T> {
368    type Error = EmptyError;
369
370    #[inline]
371    fn try_from(value: Box<[T]>) -> Result<Self, Self::Error> {
372        let v = Vec::from(value);
373        Self::try_from(v)
374    }
375}
376
377impl<T> Deref for NonEmpty<T> {
378    type Target = NonEmptySlice<T>;
379
380    fn deref(&self) -> &Self::Target {
381        unsafe {
382            // SAFETY: This type is guaranteed to be non-empty, so we don't
383            // need to check the length when wrapping into a `NonEmptySlice`.
384            NonEmptySlice::unchecked(&self.0)
385        }
386    }
387}
388
389impl<T> DerefMut for NonEmpty<T> {
390    fn deref_mut(&mut self) -> &mut Self::Target {
391        unsafe {
392            // SAFETY: This type is guaranteed to be non-empty, so we don't
393            // need to check the length when wrapping into a `NonEmptySlice`.
394            NonEmptySlice::unchecked_mut(&mut self.0)
395        }
396    }
397}
398
399impl<T> AsRef<[T]> for NonEmpty<T> {
400    #[inline]
401    fn as_ref(&self) -> &[T] {
402        self
403    }
404}
405
406impl<T> AsMut<[T]> for NonEmpty<T> {
407    #[inline]
408    fn as_mut(&mut self) -> &mut [T] {
409        self.0.as_mut()
410    }
411}
412
413impl<T> AsRef<Vec<T>> for NonEmpty<T> {
414    #[inline]
415    fn as_ref(&self) -> &Vec<T> {
416        &self.0
417    }
418}
419
420impl<T> Borrow<[T]> for NonEmpty<T> {
421    #[inline]
422    fn borrow(&self) -> &[T] {
423        self.0.borrow()
424    }
425}
426
427impl<T> Borrow<Vec<T>> for NonEmpty<T> {
428    #[inline]
429    fn borrow(&self) -> &Vec<T> {
430        &self.0
431    }
432}
433
434impl<T> BorrowMut<[T]> for NonEmpty<T> {
435    #[inline]
436    fn borrow_mut(&mut self) -> &mut [T] {
437        self.0.borrow_mut()
438    }
439}
440
441impl<T, I: SliceIndex<[T]>> Index<I> for NonEmpty<T> {
442    type Output = I::Output;
443
444    #[inline]
445    fn index(&self, index: I) -> &Self::Output {
446        self.0.index(index)
447    }
448}
449
450impl<T, I: SliceIndex<[T]>> IndexMut<I> for NonEmpty<T> {
451    #[inline]
452    fn index_mut(&mut self, index: I) -> &mut Self::Output {
453        self.0.index_mut(index)
454    }
455}
456
457impl<T> IntoIterator for NonEmpty<T> {
458    type Item = T;
459    type IntoIter = IntoIter<T>;
460
461    #[inline]
462    fn into_iter(self) -> Self::IntoIter {
463        self.0.into_iter()
464    }
465}
466
467impl<'a, T> IntoIterator for &'a NonEmpty<T> {
468    type Item = &'a T;
469    type IntoIter = Iter<'a, T>;
470
471    #[inline]
472    fn into_iter(self) -> Self::IntoIter {
473        self.iter()
474    }
475}
476
477impl<'a, T> IntoIterator for &'a mut NonEmpty<T> {
478    type Item = &'a mut T;
479    type IntoIter = IterMut<'a, T>;
480
481    #[inline]
482    fn into_iter(self) -> Self::IntoIter {
483        self.iter_mut()
484    }
485}
486
487impl<T> Extend<T> for NonEmpty<T> {
488    #[inline]
489    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
490        self.0.extend(iter)
491    }
492}
493
494impl<'a, T: Copy + 'a> Extend<&'a T> for NonEmpty<T> {
495    #[inline]
496    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
497        self.0.extend(iter)
498    }
499}
500
501#[cfg(feature = "std")]
502impl Write for NonEmpty<u8> {
503    #[inline]
504    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
505        self.0.write(buf)
506    }
507
508    #[inline]
509    fn write_vectored(&mut self, bufs: &[IoSlice<'_>]) -> std::io::Result<usize> {
510        self.0.write_vectored(bufs)
511    }
512
513    #[inline]
514    fn write_all(&mut self, buf: &[u8]) -> std::io::Result<()> {
515        self.0.write_all(buf)
516    }
517
518    #[inline]
519    fn flush(&mut self) -> std::io::Result<()> {
520        self.0.flush()
521    }
522}
523
524#[cfg(feature = "serde")]
525impl<T: Serialize> Serialize for NonEmpty<T> {
526    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
527        self.as_slice().serialize(serializer)
528    }
529}
530
531#[cfg(feature = "serde")]
532impl<'de, T: Deserialize<'de>> Deserialize<'de> for NonEmpty<T> {
533    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
534        Self::try_from(<Vec<T>>::deserialize(deserializer)?)
535            .map_err(|_| D::Error::custom("vector must be non-empty"))
536    }
537}
538
539impl<T> NonEmpty<T> {
540    /// Removes the specified range from the vector in bulk, returning the removed items as an iterator.
541    /// # Panics
542    /// If the range specified would remove all elements from the vector. There must be at least 1 element left over.
543    /// # Examples
544    /// Removing all but the first element.
545    /// ```
546    /// # use non_empty_vec::{NonEmpty, ne_vec};
547    /// let mut v = ne_vec!(0, 1, 2, 3, 4, 5);
548    /// let removed: Vec<_> = v.drain(1..).collect();
549    /// assert_eq!(removed, vec![1, 2, 3, 4, 5]);
550    /// assert_eq!(v, ne_vec![0]);
551    /// ```
552    ///
553    /// Removing all but the last element.
554    /// ```
555    /// # use non_empty_vec::{NonEmpty, ne_vec};
556    /// let mut v = ne_vec!(0, 1, 2, 3, 4, 5);
557    /// let removed: Vec<_> = v.drain(..v.len().get()-1).collect();
558    /// assert_eq!(removed, vec![0, 1, 2, 3, 4]);
559    /// assert_eq!(v, ne_vec![5]);
560    /// ```
561    /// Removing all elements (these panic).
562    /// ```should_panic
563    /// # use non_empty_vec::ne_vec;
564    /// # let mut v = ne_vec!(0, 1, 2, 3, 4, 5);
565    /// v.drain(..);
566    /// ```
567    /// ```should_panic
568    /// # use non_empty_vec::ne_vec;
569    /// # let mut v = ne_vec!(0, 1, 2, 3, 4, 5);
570    /// v.drain(0..v.len().get());
571    /// ```
572    #[track_caller]
573    pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<T> {
574        // whether or not there is space leftover in the start of the vector.
575        let leftover_start = match range.start_bound() {
576            Bound::Included(&start) => start > 0,
577            Bound::Excluded(_) => true,
578            Bound::Unbounded => false,
579        };
580        if !leftover_start {
581            // whether or not there is space leftover in the end of the vector.
582            let leftover_end = match range.end_bound() {
583                Bound::Excluded(&end) => end < self.len().get(),
584                Bound::Included(&end) => end < self.len().get() - 1,
585                Bound::Unbounded => false,
586            };
587            if !leftover_end {
588                panic!(
589                    "range specified for `NonEmpty::drain` must leave at least one element left"
590                );
591            }
592        }
593        self.0.drain(range)
594    }
595
596    /// Calls a predicate with every element of this vector, removing each element for which the predicate returns `true`.
597    /// All removed elements are yielded from the returned iterator.
598    /// # Examples
599    /// Normal use.
600    /// ```
601    /// // Filter out odd entries
602    /// # use non_empty_vec::ne_vec;
603    /// let mut v = ne_vec![1,2,3,4,5,6];
604    /// assert!(v.drain_filter(|i| *i % 2 == 1).eq([1, 3, 5]));
605    /// assert_eq!(v, ne_vec![2, 4, 6]);
606    /// ```
607    /// At least one element is always left behind.
608    /// ```
609    /// // When there's only one element left, the predicate never even gets called on it.
610    /// # use non_empty_vec::ne_vec;
611    /// let mut v = ne_vec![1];
612    /// v.drain_filter(|_| unreachable!());
613    /// assert_eq!(v, ne_vec![1]);
614    ///
615    /// // This also applies if all elements before the final get removed.
616    /// let mut v = ne_vec![1, 2, 3, 4, 5];
617    /// let removed = v.drain_filter(|&mut i| if i < 5 {
618    ///     true
619    /// } else {
620    ///     unreachable!()
621    /// });
622    /// assert!(removed.eq(1..=4));
623    /// assert_eq!(v, ne_vec![5]);
624    /// ```
625    /// Lazy execution.
626    /// ```
627    /// // Nothing gets removed until the iterator is consumed
628    /// # use non_empty_vec::ne_vec;
629    /// let mut v = ne_vec![1,2,3,4];
630    /// v.drain_filter(|_| true);
631    /// assert_eq!(v, ne_vec![1,2,3,4]);
632    /// ```
633    #[inline]
634    pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<T, F>
635    where
636        F: FnMut(&mut T) -> bool,
637    {
638        DrainFilter::new(self, f)
639    }
640}
641
642#[must_use = "iterators are lazy and do nothing unless consumed"]
643pub struct DrainFilter<'a, T, F>
644where
645    F: FnMut(&mut T) -> bool,
646{
647    vec: &'a mut NonEmpty<T>,
648    f: F,
649
650    // Always `0 <= left <= right <= vec.len()`, usually `left < right`.
651    // When `left == right`, the iterator is complete.
652    left: usize,
653    right: usize,
654}
655
656impl<'a, T, F> DrainFilter<'a, T, F>
657where
658    F: FnMut(&mut T) -> bool,
659{
660    #[inline]
661    pub fn new(vec: &'a mut NonEmpty<T>, f: F) -> Self {
662        let left = 0;
663        let right = vec.len().get();
664        Self {
665            vec,
666            f,
667            left,
668            right,
669        }
670    }
671}
672
673impl<'a, T, F> Iterator for DrainFilter<'a, T, F>
674where
675    F: FnMut(&mut T) -> bool,
676{
677    type Item = T;
678
679    fn next(&mut self) -> Option<Self::Item> {
680        // Loop until either we find an element or the list is depleted.
681        loop {
682            // Only try draining this element if there would be more elements leftover.
683            let any_yielded = self.left > 0 || self.right < self.vec.0.len();
684            if (any_yielded || self.right - self.left > 1) && self.left < self.right {
685                // If the elment passes the predicate, remove it and yield it.
686                if (self.f)(&mut self.vec[self.left]) {
687                    let item = self.vec.0.remove(self.left);
688                    self.right -= 1;
689                    break Some(item);
690                }
691                // If it doesn't pass, leave the element and repeat the loop.
692                else {
693                    self.left += 1;
694                }
695            }
696            // We've reached the point where we only have one element left, so leave it.
697            else {
698                break None;
699            }
700        }
701    }
702
703    fn size_hint(&self) -> (usize, Option<usize>) {
704        let max = self.right - self.left;
705        (0, Some(max))
706    }
707}
708
709impl<'a, T, F> DoubleEndedIterator for DrainFilter<'a, T, F>
710where
711    F: FnMut(&mut T) -> bool,
712{
713    fn next_back(&mut self) -> Option<Self::Item> {
714        // Loop until either we find an element or the list is depleted.
715        loop {
716            // Only try draining this element if there would be more elements leftover.
717            let any_yielded = self.right < self.vec.0.len() || self.left > 0;
718            if (any_yielded || self.right - self.left > 1) && self.right > self.left {
719                // If the elment passes the predicate, remove it and yield it.
720                if (self.f)(&mut self.vec[self.right - 1]) {
721                    let item = self.vec.0.remove(self.right - 1);
722                    self.right -= 1;
723                    break Some(item);
724                }
725                // If it doesn't pass, leave the element and repeat the loop.
726                else {
727                    self.right -= 1;
728                }
729            }
730            // We've reached the point where we only have one element left, so leave it.
731            else {
732                break None;
733            }
734        }
735    }
736}
737
738impl<'a, T, F> FusedIterator for DrainFilter<'a, T, F> where F: FnMut(&mut T) -> bool {}
739
740/// Wrapper for a slice that is guaranteed to have `len > 0`. This allows
741/// many operations to be infallible, such as [`first`](#method.first)
742/// or [`split_last_mut`](#method.split_last_mut).
743///
744/// This invariant may be relied upon in unsafe code.
745///
746/// `NonEmptySlice` dereferences to an `std` slice, so all of the familiar methods are still available.
747#[derive(Eq, Ord, Hash)]
748#[repr(transparent)]
749pub struct NonEmptySlice<T>([T]);
750
751impl<T> NonEmptySlice<T> {
752    /// Creates a new `NonEmptySlice` without checking the length.
753    /// # Safety
754    /// Ensure that the input slice is not empty.
755    /// # Examples
756    /// For a slice that is known not to be empty.
757    /// ```
758    /// # use non_empty_vec::NonEmptySlice;
759    /// let s = unsafe {
760    ///     // SAFETY: The passed slice is non-empty.
761    ///     NonEmptySlice::unchecked(&[1])
762    /// };
763    /// assert_eq!(s, &[1]);
764    /// ```
765    /// Improper use (instant undefined behavior).
766    /// ```ignore
767    /// # use non_empty_vec::NonEmptySlice;
768    /// let s: &NonEmptySlice<String> = unsafe { NonEmptySlice::unchecked(&[]) };
769    /// // Please don't try this.
770    /// println!("{}", s.first().as_str());
771    /// ```
772    #[inline]
773    pub const unsafe fn unchecked(slice: &[T]) -> &Self {
774        debug_assert!(!slice.is_empty());
775        // SAFETY: This type is `repr(transparent)`, so we can safely
776        // cast the references like this.
777        &*(slice as *const _ as *const Self)
778    }
779
780    /// Creates a new `NonEmptySlice` without checking the length.
781    /// # Safety
782    /// Ensure that the input slice is not empty.
783    #[inline]
784    pub unsafe fn unchecked_mut(slice: &mut [T]) -> &mut Self {
785        debug_assert!(!slice.is_empty());
786        // SAFETY: This type is `repr(transparent)`, so we can safely
787        // cast the references like this.
788        &mut *(slice as *mut _ as *mut Self)
789    }
790
791    /// Creates a boxed `NonEmptySlice` without checking the length.
792    /// # Safety
793    /// Ensure that the input slice is not empty.
794    #[inline]
795    pub unsafe fn unchecked_boxed(slice: Box<[T]>) -> Box<Self> {
796        debug_assert!(!slice.is_empty());
797        // SAFETY: This type is `repr(transparent)`, so we can safely
798        // cast the pointers like this.
799        // `Box` does not necessarily have a guaranteed type layout
800        // so it's safer to use methods to convert to/from raw pointers.
801        let ptr = Box::into_raw(slice) as *mut Self;
802        Box::from_raw(ptr)
803    }
804
805    /// Converts a reference into a [non-empty slice](NonEmptySlice) of length `1`.
806    /// # Example
807    /// ```
808    /// # use non_empty_vec::NonEmptySlice;
809    /// let slice = NonEmptySlice::from_ref(&5);
810    /// assert_eq!(slice, &[5]);
811    /// ```
812    #[inline]
813    pub fn from_ref(val: &T) -> &Self {
814        let slice = core::slice::from_ref(val);
815        // SAFETY: `slice::from_ref` returns a slice of length 1, so it's non-empty.
816        unsafe { Self::unchecked(slice) }
817    }
818
819    /// Converts a mutable reference into a [non-empty slice](NonEmptySlice) of length `1`.
820    #[inline]
821    pub fn from_mut(val: &mut T) -> &mut Self {
822        let slice = core::slice::from_mut(val);
823        unsafe { Self::unchecked_mut(slice) }
824    }
825
826    /// Creates a new `NonEmptySlice` from a primitive slice. Returns [`None`] if the slice is empty.
827    /// # Examples
828    /// ```
829    /// # use non_empty_vec::NonEmptySlice;
830    /// // Non-empty input
831    /// assert!(NonEmptySlice::from_slice(&[1]).is_some());
832    /// // Empty input
833    /// assert!(NonEmptySlice::<()>::from_slice(&[]).is_none());
834    /// ```
835    #[inline]
836    pub const fn from_slice(slice: &[T]) -> Option<&Self> {
837        if !slice.is_empty() {
838            // SAFETY: We just checked that it's not empty,
839            // so we can safely create a `NonEmptySlice`.
840            unsafe { Some(Self::unchecked(slice)) }
841        } else {
842            None
843        }
844    }
845
846    /// Creates a new `NonEmptySlice` from a primitive slice. Returns [`None`] if the slice is empty.
847    #[inline]
848    pub fn from_mut_slice(slice: &mut [T]) -> Option<&mut Self> {
849        if !slice.is_empty() {
850            // SAFETY: We just checked that it's not empty,
851            // so we can safely create a `NonEmptySlice`.
852            unsafe { Some(Self::unchecked_mut(slice)) }
853        } else {
854            None
855        }
856    }
857
858    /// Creates a new `NonEmptySlice` from a primitive slice. Returns [`None`] if the slice is empty.
859    #[inline]
860    pub fn from_boxed_slice(slice: Box<[T]>) -> Option<Box<Self>> {
861        if !slice.is_empty() {
862            // SAFETY: We just checked that it's not empty,
863            // so we can safely create a `NonEmptySlice`.
864            unsafe { Some(Self::unchecked_boxed(slice)) }
865        } else {
866            None
867        }
868    }
869
870    /// Converts this `NonEmptySlice` into a primitive slice.
871    #[inline]
872    pub const fn as_slice(&self) -> &[T] {
873        &self.0
874    }
875
876    /// Converts this `NonEmptySlice` into a primitive slice.
877    #[inline]
878    pub fn as_mut_slice(&mut self) -> &mut [T] {
879        &mut self.0
880    }
881
882    /// Converts this `NonEmptySlice` into a primitive boxed slice.
883    #[inline]
884    pub fn into_boxed_slice(self: Box<Self>) -> Box<[T]> {
885        // SAFETY: This type is `repr(transparent)`, so we can
886        // safely cast the pointer like this.
887        let ptr = Box::into_raw(self) as *mut [T];
888        unsafe { Box::from_raw(ptr) }
889    }
890
891    /// Returns the length of this slice.
892    #[inline]
893    pub const fn len(&self) -> NonZeroUsize {
894        unsafe { NonZeroUsize::new_unchecked(self.0.len()) }
895    }
896
897    /// Returns `false`.
898    #[inline]
899    pub const fn is_empty(&self) -> bool {
900        false
901    }
902
903    /// Returns a raw pointer to this slice's buffer. See [`slice::as_ptr`] for more info.
904    #[inline]
905    pub const fn as_ptr(&self) -> *const T {
906        self.0.as_ptr()
907    }
908
909    /// Returns a raw pointer to this slice's buffer. See [`slice::as_ptr`] for more info.
910    #[inline]
911    pub fn as_mut_ptr(&mut self) -> *mut T {
912        self.0.as_mut_ptr()
913    }
914
915    /// Returns a reference to the first element of this slice.
916    /// # Example
917    /// ```
918    /// # use non_empty_vec::ne_vec;
919    /// let v = ne_vec![1, 2, 3];
920    /// assert_eq!(v.first(), &1);
921    /// ```
922    #[inline]
923    pub const fn first(&self) -> &T {
924        if let [first, ..] = self.as_slice() {
925            first
926        } else {
927            // SAFETY: This instance is non-empty, so the above pattern will always match.
928            unsafe { unreachable_unchecked!() }
929        }
930    }
931
932    /// Returns a mutable reference to the first element of this slice.
933    /// # Example
934    /// ```
935    /// # use non_empty_vec::ne_vec;
936    /// let mut v = ne_vec![1, 2, 3];
937    /// *v.first_mut() = 10;
938    /// assert_eq!(v, ne_vec![10, 2, 3]);
939    /// ```
940    #[inline]
941    pub fn first_mut(&mut self) -> &mut T {
942        if let [first, ..] = self.as_mut_slice() {
943            first
944        } else {
945            // SAFETY: This instance is non-empty, so the above pattern will always match.
946            unsafe { unreachable_unchecked!() }
947        }
948    }
949
950    /// Returns a reference to the last element of this slice.
951    /// # Example
952    /// ```
953    /// # use non_empty_vec::ne_vec;
954    /// let mut v = ne_vec![1, 2, 3];
955    /// assert_eq!(v.last(), &3);
956    /// ```
957    #[inline]
958    pub const fn last(&self) -> &T {
959        if let [.., last] = self.as_slice() {
960            last
961        } else {
962            // SAFETY: This instance is non-empty, so the above pattern will always match.
963            unsafe { unreachable_unchecked!() }
964        }
965    }
966
967    /// Returns a mutable reference to the last element of this slice.
968    /// # Example
969    /// ```
970    /// # use non_empty_vec::ne_vec;
971    /// let mut v = ne_vec![1, 2, 3];
972    /// *v.last_mut() = 10;
973    /// assert_eq!(v, ne_vec![1, 2, 10]);
974    /// ```
975    #[inline]
976    pub fn last_mut(&mut self) -> &mut T {
977        if let [.., last] = self.as_mut_slice() {
978            last
979        } else {
980            // SAFETY: This instance is non-empty, so the above pattern will always match.
981            unsafe { unreachable_unchecked!() }
982        }
983    }
984
985    /// Splits this slice into
986    /// * A reference to the first element.
987    /// * A slice to the rest of the elements.
988    ///
989    /// This method is not usually very helpful, but it may shorten some expressions.
990    /// It is mainly included for the sake of parity with [`split_first_mut`](#method.split_first_mut).
991    #[inline]
992    pub const fn split_first(&self) -> (&T, &[T]) {
993        if let [first, rest @ ..] = self.as_slice() {
994            (first, rest)
995        } else {
996            // SAFETY: This instance is non-empty, so the above pattern will always match.
997            unsafe { unreachable_unchecked!() }
998        }
999    }
1000
1001    /// Splits this slice into
1002    /// * A mutable reference to the first element.
1003    /// * A mutable slice to the rest of the elements.
1004    ///
1005    /// This method is useful for breaking up a contiguous slice into multiple
1006    /// smaller references, which can each be mutated independently without
1007    /// tripping off the borrow checker.
1008    ///
1009    /// # Examples
1010    /// ```
1011    /// # use non_empty_vec::ne_vec;
1012    /// let mut v = ne_vec![1, 2, 3, 4];
1013    /// let (first, rest) = v.split_first_mut();
1014    /// *first *= 2;
1015    /// rest[1] += 2;
1016    /// assert_eq!(v, ne_vec![2, 2, 5, 4]);
1017    /// ```
1018    ///
1019    /// Only one element.
1020    /// ```
1021    /// # use non_empty_vec::ne_vec;
1022    /// let mut v = ne_vec![4];
1023    /// let (first, rest) = v.split_first_mut();
1024    /// assert_eq!(*first, 4);
1025    /// assert_eq!(rest, &[]);
1026    /// ```
1027    #[inline]
1028    pub fn split_first_mut(&mut self) -> (&mut T, &mut [T]) {
1029        if let [first, rest @ ..] = self.as_mut_slice() {
1030            (first, rest)
1031        } else {
1032            // SAFETY: This instance is non-empty, so the above pattern will always match.
1033            unsafe { unreachable_unchecked!() }
1034        }
1035    }
1036
1037    /// Splits this slice into
1038    /// * A reference to the last element.
1039    /// * A slice to the rest of the elements.
1040    ///
1041    /// This method is not usually very helpful, but it may shorten some expressions.
1042    /// It is mainly included for the sake of parity with [`split_last_mut`](#method.split_last_mut).
1043    #[inline]
1044    pub fn split_last(&self) -> (&T, &[T]) {
1045        if let [rest @ .., last] = self.as_slice() {
1046            (last, rest)
1047        } else {
1048            // SAFETY: This instance is non-empty, so the above pattern will always match.
1049            unsafe { unreachable_unchecked!() }
1050        }
1051    }
1052
1053    /// Splits this slice into
1054    /// * A mutable reference to the last element.
1055    /// * A mutable slice to the rest of the elements.
1056    ///
1057    /// This method is useful for breaking up a contiguous slice into multiple
1058    /// smaller references, which can each be mutated independently without
1059    /// tripping off the borrow checker.
1060    #[inline]
1061    pub fn split_last_mut(&mut self) -> (&mut T, &mut [T]) {
1062        if let [rest @ .., last] = self.as_mut_slice() {
1063            (last, rest)
1064        } else {
1065            // SAFETY: This instance is non-empty, so the above pattern will always match.
1066            unsafe { unreachable_unchecked!() }
1067        }
1068    }
1069}
1070
1071impl<'a, T> TryFrom<&'a [T]> for &'a NonEmptySlice<T> {
1072    type Error = EmptyError;
1073
1074    fn try_from(value: &'a [T]) -> Result<Self, Self::Error> {
1075        NonEmptySlice::from_slice(value).ok_or(EmptyError)
1076    }
1077}
1078
1079impl<'a, T> TryFrom<&'a mut [T]> for &'a mut NonEmptySlice<T> {
1080    type Error = EmptyError;
1081
1082    fn try_from(value: &'a mut [T]) -> Result<Self, Self::Error> {
1083        NonEmptySlice::from_mut_slice(value).ok_or(EmptyError)
1084    }
1085}
1086
1087impl<T> TryFrom<Box<[T]>> for Box<NonEmptySlice<T>> {
1088    type Error = EmptyError;
1089
1090    fn try_from(value: Box<[T]>) -> Result<Self, Self::Error> {
1091        NonEmptySlice::from_boxed_slice(value).ok_or(EmptyError)
1092    }
1093}
1094
1095impl<T> Deref for NonEmptySlice<T> {
1096    type Target = [T];
1097    #[inline]
1098    fn deref(&self) -> &Self::Target {
1099        self.as_slice()
1100    }
1101}
1102
1103impl<T> DerefMut for NonEmptySlice<T> {
1104    #[inline]
1105    fn deref_mut(&mut self) -> &mut Self::Target {
1106        self.as_mut_slice()
1107    }
1108}
1109
1110impl<T> AsRef<[T]> for NonEmptySlice<T> {
1111    #[inline]
1112    fn as_ref(&self) -> &[T] {
1113        self
1114    }
1115}
1116
1117impl<T> AsMut<[T]> for NonEmptySlice<T> {
1118    #[inline]
1119    fn as_mut(&mut self) -> &mut [T] {
1120        self
1121    }
1122}
1123
1124impl<T: Debug> Debug for NonEmptySlice<T> {
1125    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1126        write!(f, "{:?}", &self.0)
1127    }
1128}
1129
1130impl<T: PartialEq, U: ?Sized + AsRef<[T]>> PartialEq<U> for NonEmptySlice<T> {
1131    #[inline]
1132    fn eq(&self, other: &U) -> bool {
1133        &self.0 == other.as_ref()
1134    }
1135}
1136
1137impl<T: PartialEq> PartialEq<NonEmptySlice<T>> for [T] {
1138    #[inline]
1139    fn eq(&self, other: &NonEmptySlice<T>) -> bool {
1140        *self == other.0
1141    }
1142}
1143
1144impl<T: PartialOrd, U: ?Sized + AsRef<[T]>> PartialOrd<U> for NonEmptySlice<T> {
1145    #[inline]
1146    fn partial_cmp(&self, other: &U) -> Option<core::cmp::Ordering> {
1147        self.0.partial_cmp(other.as_ref())
1148    }
1149}
1150
1151impl<T: PartialOrd> PartialOrd<NonEmptySlice<T>> for [T] {
1152    #[inline]
1153    fn partial_cmp(&self, other: &NonEmptySlice<T>) -> Option<core::cmp::Ordering> {
1154        self.partial_cmp(&other.0)
1155    }
1156}
1157
1158impl<'a, T> IntoIterator for &'a NonEmptySlice<T> {
1159    type Item = &'a T;
1160    type IntoIter = Iter<'a, T>;
1161
1162    #[inline]
1163    fn into_iter(self) -> Self::IntoIter {
1164        self.iter()
1165    }
1166}
1167
1168impl<'a, T> IntoIterator for &'a mut NonEmptySlice<T> {
1169    type Item = &'a mut T;
1170    type IntoIter = IterMut<'a, T>;
1171
1172    #[inline]
1173    fn into_iter(self) -> Self::IntoIter {
1174        self.iter_mut()
1175    }
1176}
1177
1178/// Required to be used in the [`ne_vec`] macro.
1179#[doc(hidden)]
1180pub use alloc::vec as __vec;
1181
1182/// Constructs a [`NonEmpty`] vector, similar to `std`'s [`vec`](std::vec!) macro.
1183///
1184/// This macro will generally try to check the validity of the length at compile time if it can.
1185///
1186/// If the length is an expression (e.g. `ne_vec![(); { 0 }]`), the check is performed at runtime
1187/// to allow the length to be dynamic.
1188///
1189/// # Examples
1190///
1191/// Proper use.
1192///
1193/// ```
1194/// # use non_empty_vec::*;
1195/// # use std::convert::TryFrom;
1196/// assert_eq!(
1197///     ne_vec![1, 2, 3],
1198///     NonEmpty::try_from(vec![1, 2, 3_i32]).unwrap(),
1199/// );
1200///
1201/// assert_eq!(
1202///     ne_vec![1; 3],
1203///     NonEmpty::try_from(vec![1, 1, 1]).unwrap(),
1204/// );
1205/// ```
1206///
1207/// Improper use.
1208///
1209/// ```compile_fail
1210/// # use non_empty_vec::*;
1211/// let _ = ne_vec![];
1212/// ```
1213///
1214/// ```compile_fail
1215/// # use non_empty_vec::*;
1216/// let _ = ne_vec![1; 0];
1217/// ```
1218///
1219/// ```compile_fail
1220/// # use non_empty_vec::*;
1221/// let _ = ne_vec![1; 0usize];
1222/// ```
1223///
1224/// ```should_panic
1225/// # use non_empty_vec::*;
1226/// let n = 0;
1227/// let _ = ne_vec![1; n];
1228/// ```
1229#[macro_export]
1230macro_rules! ne_vec {
1231    () => {
1232        ::core::compile_error!("`NonEmpty` vector must be non-empty")
1233    };
1234    ($($x:expr),+ $(,)?) => {{
1235        let vec = $crate::__vec![$($x),+];
1236        unsafe { $crate::NonEmpty::new_unchecked(vec) }
1237    }};
1238    ($elem:expr; 0) => {
1239        // if 0 is passed to the macro we can generate a good compile error
1240        $crate::ne_vec![]
1241    };
1242    ($elem:expr; $n:literal) => {{
1243        // extra guard to reject compilation if $n ends up being 0 in some other way (e.g. ne_vec![1; 0usize])
1244        const _ASSERT_NON_ZERO: [(); $n - 1] = [(); $n - 1];
1245        let vec = $crate::__vec![$elem; $n];
1246        unsafe { $crate::NonEmpty::new_unchecked(vec) }
1247    }};
1248    ($elem:expr; $n:expr) => {{
1249        // if $n is an expression, we cannot check the length at compile time and do it at runtime
1250        let len = $n;
1251        if len == 0 {
1252            ::core::panic!("`NonEmpty` vector must be non-empty");
1253        }
1254        let vec = $crate::__vec![$elem; len];
1255        unsafe { $crate::NonEmpty::new_unchecked(vec) }
1256    }};
1257}
1258
1259#[cfg(test)]
1260mod tests {
1261    use super::*;
1262
1263    #[test]
1264    fn it_works() {
1265        // From
1266        let mut list: NonEmpty<i32> = (vec![1, 2], 3).into();
1267        assert_eq!(list, (1, vec![2, 3]).into());
1268        assert_eq!(&*list, &[1, 2, 3]);
1269
1270        // Index
1271        list[0] = 2;
1272        assert_eq!(list[0], 2);
1273        list[0] = 1;
1274        assert_eq!(list[0], 1);
1275
1276        // slice methods
1277        assert_eq!(list.len().get(), 3);
1278        assert_eq!(list.as_slice(), &[1, 2, 3]);
1279
1280        // TryFrom
1281        assert_eq!(<NonEmpty<i32>>::try_from(vec![]).ok(), None);
1282        assert_eq!(
1283            &*<NonEmpty<i32>>::try_from(vec![1, 2, 3]).unwrap(),
1284            &[1, 2, 3]
1285        );
1286
1287        // Iterator
1288        assert_eq!(
1289            list.iter().map(|n| n * 2).collect::<Vec<_>>(),
1290            vec![2, 4, 6]
1291        );
1292
1293        // Single
1294        let single = NonEmpty::new(15_i32);
1295        assert_eq!(single.len().get(), 1);
1296        assert_eq!(single[0], 15);
1297    }
1298
1299    #[test]
1300    fn default() {
1301        assert_eq!(NonEmpty::<i32>::default(), ne_vec![0]);
1302        assert_eq!(NonEmpty::<&str>::default(), ne_vec![""]);
1303    }
1304
1305    #[test]
1306    fn into_iter() {
1307        let mut list = ne_vec![1, 2, 3];
1308
1309        for (a, b) in [1, 2, 3].iter().zip(&list) {
1310            assert_eq!(a, b);
1311        }
1312
1313        for a in &mut list {
1314            *a += 1;
1315        }
1316        assert_eq!(list.as_slice(), &[2, 3, 4]);
1317
1318        for (a, b) in vec![2, 3, 4].into_iter().zip(list) {
1319            assert_eq!(a, b);
1320        }
1321    }
1322
1323    #[test]
1324    fn drain_filter() {
1325        // Filter out odd numbers.
1326        let mut v = ne_vec![1, 2, 3, 4, 5, 6];
1327        assert!(v.drain_filter(|val| *val % 2 == 1).eq([1, 3, 5]));
1328        assert_eq!(v, ne_vec![2, 4, 6]);
1329
1330        // singleton
1331        let mut v = ne_vec![1];
1332        for _ in v.drain_filter(|_| unreachable!()) {}
1333        assert_eq!(v, ne_vec![1]);
1334
1335        // leftover
1336        let mut v = ne_vec![1, 2, 3];
1337        let removed = v.drain_filter(|&mut val| if val < 3 { true } else { unreachable!() });
1338        assert!(removed.eq([1, 2]));
1339        assert_eq!(v, ne_vec![3]);
1340
1341        // double-ended, meet in middle
1342        let mut v = ne_vec![1, 2, 3, 4, 5, 6];
1343        let mut rem = v.drain_filter(|val| *val % 2 == 1);
1344        assert_eq!(rem.next(), Some(1));
1345        assert_eq!(rem.next_back(), Some(5));
1346        assert_eq!(rem.next_back(), Some(3));
1347        assert_eq!(rem.next(), None);
1348        assert_eq!(rem.next_back(), None);
1349
1350        // rev
1351        let mut v = ne_vec![1, 2, 3, 4, 5, 6];
1352        let rem = v.drain_filter(|val| *val % 2 == 0).rev();
1353        assert!(rem.eq([6, 4, 2]));
1354        assert_eq!(v, ne_vec![1, 3, 5]);
1355
1356        // singleton-back
1357        let mut v = ne_vec![1];
1358        for _ in v.drain_filter(|_| unreachable!()) {}
1359        assert_eq!(v, ne_vec![1]);
1360
1361        // leftover-back
1362        let mut v = ne_vec![1, 2, 3];
1363        let removed = v
1364            .drain_filter(|&mut val| if val > 1 { true } else { unreachable!() })
1365            .rev();
1366        assert!(removed.eq([3, 2]));
1367        assert_eq!(v, ne_vec![1]);
1368
1369        // meet in middle, unreachable
1370        let mut v = ne_vec![1, 2, 3];
1371        let mut rem = v.drain_filter(|&mut val| if val == 2 { unreachable!() } else { true });
1372        assert_eq!(rem.next_back(), Some(3));
1373        assert_eq!(rem.next(), Some(1));
1374        assert_eq!(rem.next_back(), None);
1375        assert_eq!(rem.next(), None);
1376        assert_eq!(v, ne_vec![2]);
1377    }
1378
1379    #[test]
1380    fn initialize_macro() {
1381        assert_eq!(ne_vec![1; 3].as_slice(), &[1, 1, 1]);
1382        assert_eq!(ne_vec!["string"; 5].as_slice(), &["string"; 5]);
1383    }
1384
1385    #[test]
1386    #[should_panic]
1387    fn initialize_macro_zero_size() {
1388        // ne_vec![1; 0] results in a compile error
1389        let n = 0;
1390        let _ = ne_vec![1; n];
1391    }
1392
1393    #[test]
1394    fn initialize_macro_fake_vec() {
1395        #[allow(unused_macros)]
1396        macro_rules! vec {
1397            ($($x:tt)*) => {
1398                Vec::new()
1399            };
1400        }
1401
1402        // ne_vec! should not be affected by a fake vec! macro being in scope.
1403        let list: NonEmpty<u32> = ne_vec![1, 2, 3];
1404        assert_eq!(list.len().get(), 3);
1405    }
1406
1407    #[cfg(feature = "serde")]
1408    #[test]
1409    fn serialize() {
1410        let vec: NonEmpty<u32> = (1, vec![]).into();
1411        assert_eq!(
1412            serde_json::from_str::<NonEmpty<u32>>(&serde_json::to_string(&vec).unwrap()).unwrap(),
1413            vec
1414        );
1415    }
1416}
non_empty_vec/lib.rs

non_empty_vec/
lib.rs
