fixed_capacity_vec/

lib.rs

#![doc=include_str!("../README.md")]

use alloc::handle_alloc_error;
use core::fmt::{self, Debug, Display};
use core::hash::Hash;
use core::ops::{Deref, DerefMut};
use std::alloc::{self, Layout};
use std::convert::TryFrom;
use std::ptr::NonNull;
use std::{mem, ptr};

/// Like `Vec` with a capacity fixed at compile time
///
/// When full, can be converted without copying into `Box<[T; N]>`, using `TryFrom`.
///
/// See the [crate-level docs](crate) for an introduction,
/// and comparison to other data types.
//
// TODO we should impl Serialize, ...
pub struct FixedCapacityVec<T, const N: usize> {
    /// Data
    ///
    /// ### SAFETY
    ///
    /// Every element of data in 0..len must always be initialised.
    ///
    /// Always a valid, properly aligned, heap pointer to a `[T; N]`.
    ///
    /// Exception: if `[T; N]` is a ZST, i.e. `LAYOUT.size()` is zero,
    /// a dangling nonnull pointer is used instead.
    /// See [`std::boxed` on Memory layout](std::boxed#memory-layout).
    ///
    /// The constant [`Self::NZST`] can be used to test whether there's an allocation.
    ///
    /// ### Variance
    ///
    /// We want covariance: `FixedCapacityVec<T>` needs to be covariant in `T`,
    /// like `Vec` is.
    ///
    /// See the Rustonomicon section on
    /// [Variance](https://doc.rust-lang.org/nomicon/subtyping.html#variance),
    /// including in particular the table of example types and their variances.
    data: NonNull<T>,

    /// Initialised portion
    ///
    /// **SAFETY**: See `data`
    len: usize,
}

/// Implement `$trait` if `T: $trait`
macro_rules! impl_traits_if_T { { $( $trait:path $(, $unsafe:tt )?; )* } => { $(
    $( $unsafe )? impl<T: $trait, const N: usize> $trait for FixedCapacityVec<T, N> {}
)* } }

// (Vec implements all of these with the same bounds as we do)
impl_traits_if_T! {
    Send, unsafe;
    Sync, unsafe;
    std::panic::UnwindSafe;
    std::panic::RefUnwindSafe;
}

impl<T, const N: usize> FixedCapacityVec<T, N> {
    /// Create a new empty `FixedCapacityVec`, capable of holding up to `N` values of type `T`
    #[inline]
    pub fn new() -> Self {
        let data = if Self::NZST {
            unsafe {
                // SAFETY: the Layout is good since we got it from Layout::new
                let data: *mut u8 = alloc::alloc(Self::LAYOUT);
                let data: *mut T = data as _;
                let data: NonNull<T> =
                    NonNull::new(data).unwrap_or_else(|| handle_alloc_error(Self::LAYOUT));
                data
            }
        } else {
            NonNull::dangling()
        };

        FixedCapacityVec { data, len: 0 }
    }

    /// Return the `Layout` for our `data` pointer allocation
    const LAYOUT: Layout = { Layout::new::<[T; N]>() };

    /// True iff `[T; N]` is not a ZST: ie, if we **do** actually have an allocation.
    const NZST: bool = { Self::LAYOUT.size() != 0 };

    /// Return the number of values stored so far
    //
    // Not in safe.rs to get right method ordering in the docs
    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` iff the `FixedCapacityVec` is empty
    //
    // Not in safe.rs to get right method ordering in the docs
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns `true` iff the `FixedCapacityVec` is full - ie, it has `N` elements
    //
    // Not in safe.rs because unsafe code relies on it, and
    // to get right method ordering in the docs.
    #[inline]
    pub fn is_full(&self) -> bool {
        self.len == N
    }

    /// Append an element
    ///
    /// # Panics
    ///
    /// Panics if the `FixedCapacityVec` is full, ie if it already contains `N` elements
    #[inline]
    pub fn push(&mut self, item: T) {
        self.try_push_or_discard(item).unwrap();
    }

    /// Remove an element from the end
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.len = self.len.checked_sub(1)?;
        let item = unsafe {
            // item was initialised, since it was within the (old) length
            // we have marked it uninit in the array, so we can take it here
            self.data.as_ptr().add(self.len).read()
        };
        Some(item)
    }

    /// Return a slice pointer to the filled data
    ///
    /// ### SAFETY
    ///
    /// This method is, itself, safe.
    /// But even better, the returned slice can be safely turned into a reference,
    /// assuming the mutability and lifetime is right.
    #[inline]
    fn slice(&self) -> NonNull<[T]> {
        // Would like NonNull::slice_from_raw_parts but its MSRV is 1.70.0
        let p = self.data.as_ptr(); // turns NonNull into T pointer
        let p = ptr::slice_from_raw_parts(p, self.len); // turns T pointer into slice pointer
        unsafe { NonNull::new(p as _).unwrap_unchecked() } // pointer back to NonNull
    }

    /// Construct a `FixedCapacityVec` out of an allocation pointer and length
    ///
    /// ### SAFETY
    ///
    ///  * `data` must be from an allocation with layout `[T; N]`,
    ///    or, iff `[T; N]` is a ZST, a valid dangling non-null pointer.
    ///    (These are the same rules as for `Vec` and `Box`.)
    ///
    ///  * The elements `0..length` must be initialised.
    ///
    ///  * Obviously `length` must be `<= N`.
    #[inline]
    unsafe fn from_raw_parts(data: NonNull<T>, length: usize) -> Self {
        Self { data, len: length }
    }

    /// Deconstruct a `FixedCapacityVec` into an allocation pointer and length
    ///
    /// The returned pieces are as for the inputs to
    /// [`from_raw_parts`](Self::from_raw_parts).
    #[inline]
    fn into_raw_parts(self) -> (NonNull<T>, usize) {
        let data = self.data;
        let len = self.len;
        mem::forget(self);
        (data, len)
    }
}

/// Defines a "try_push" function, with visibility `$vis` and name `$fn`
///
/// The generated function will behave as follows:
///
/// If there is space, will push `$item` and return `Ok(())`.
///
/// Otherwise, it will return `Err($err)`.  `$err` should be of type `Error`.
macro_rules! define_try_push { {
    $( # $attr:tt )*
    $vis:vis fn $fn:ident($item:ident) -> Result<, $Error:ty> { or Err($err:expr) }
} => {
    impl<T, const N: usize> FixedCapacityVec<T, N> {
        $( # $attr )*
        $vis fn $fn(&mut self, $item: T) -> Result<(), $Error> {
            if self.len >= N {
                return Err($err);
            }
            unsafe {
                // SAFETY now len is within bounds and the pointer is aligned
                if Self::NZST {
                    self.data.as_ptr().add(self.len).write($item);
                }
                // SAFETY now that the value is written, we can say it's there
                self.len += 1;
            }
            Ok(())
        }
    }
} }

define_try_push! {
    /// Try to append an element
    ///
    /// If the `FixedCapacityVec` is full, i.e. if it already contains `N` elements,
    /// discards the element and returns `Err`.
    //
    // clippy wanted the custom FullError type, rather than simply ().
    // I think I agree that's better; it makes `.unwrap()` work right,
    // in our impl of push(), for example.
    #[inline]
    pub fn try_push_or_discard(item) -> Result<, FullError> { or Err(FullError) }
}

define_try_push! {
    /// Try to append an element
    ///
    /// If the `FixedCapacityVec` is full, i.e. if it already contains `N` elements,
    /// return the putative new item in `Err`.
    ///
    /// If you don't need the item back, in the `Err` case,
    /// consider `try_push_or_discard`, which can be marginally faster,
    /// as its return type doesn't need to maybe include a `T`.
    #[inline]
    pub fn try_push(item) -> Result<, T> { or Err(item) }
}

impl<T, const N: usize> Drop for FixedCapacityVec<T, N> {
    #[inline]
    fn drop(&mut self) {
        unsafe {
            // SAFETY
            //
            // We are about to break the invariants!  This is OK, because it cannot
            // be observed by anyone: we have &mut Self, so no-one else can see it,
            // and even if a panic unwinds from here, `self` will no longer be considered
            // valid by the language.
            if mem::needs_drop::<T>() {
                let data: NonNull<[T]> = self.slice();
                // This causes the supposedly-valid portion of data to become totally
                // invalid, breaking the invariants.  See above.
                ptr::drop_in_place(data.as_ptr());
            }
            // SAFETY: this causes self.data to become totally invalid, breaking
            // the invariants.  That's OK; see above.
            if Self::NZST {
                alloc::dealloc(self.data.as_ptr() as _, Self::LAYOUT);
            }
        }
    }
}

impl<T, const N: usize> Deref for FixedCapacityVec<T, N> {
    type Target = [T];

    #[inline]
    fn deref(&self) -> &[T] {
        unsafe {
            // SAFETY
            // See slice().  The lifetime and mutability are enforced by the Deref trait
            self.slice().as_ref()
        }
    }
}

impl<T, const N: usize> DerefMut for FixedCapacityVec<T, N> {
    #[inline]
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe {
            // SAFETY
            // See slice().  The lifetime and mutability are enforced by the Deref trait
            self.slice().as_mut()
        }
    }
}

/// Convert a full `FixedCapacityVec` into a boxed array.
///
/// If the `FixedCapacityVec` isn't full, it is returned as the `Err`
impl<T, const N: usize> TryFrom<FixedCapacityVec<T, N>> for Box<[T; N]> {
    type Error = FixedCapacityVec<T, N>;

    #[inline]
    fn try_from(v: FixedCapacityVec<T, N>) -> Result<Box<[T; N]>, FixedCapacityVec<T, N>> {
        if v.len == N {
            Ok(unsafe {
                let data: *mut [T; N] = v.data.as_ptr() as _;
                // stop drop from running
                mem::forget(v);
                // SAFETY
                // We have checked that every element is initialised
                // The pointer is valid according to the rules for Box, even for a ZST.
                // We pass ownership to the Box; that's OK, because we've called forget.
                let data: Box<[T; N]> = Box::from_raw(data);
                data
            })
        } else {
            Err(v)
        }
    }
}

/// Convert a boxed array into a full `FixedCapacityVec`
impl<T, const N: usize> From<Box<[T; N]>> for FixedCapacityVec<T, N> {
    #[inline]
    fn from(b: Box<[T; N]>) -> FixedCapacityVec<T, N> {
        let b: *mut [T; N] = Box::into_raw(b);
        let b: *mut T = b as _;
        // Docs for Box say this is non-null
        let b: NonNull<T> = unsafe { NonNull::new(b).unwrap_unchecked() };
        unsafe { FixedCapacityVec::from_raw_parts(b, N) }
    }
}

/// Convert a `FixedCapacityVec` into a `Vec`
impl<T, const N: usize> From<FixedCapacityVec<T, N>> for Vec<T> {
    #[inline]
    fn from(v: FixedCapacityVec<T, N>) -> Vec<T> {
        unsafe {
            let (data, len) = v.into_raw_parts();
            let data: *mut T = data.as_ptr();
            // SAFETY
            // Elements up to len are initialised
            // The pointer is valid according to the rules for Vec, even for a ZST.
            // We pass ownership to the Vec.
            let vec: Vec<T> = Vec::from_raw_parts(data, len, N);
            vec
        }
    }
}

/// Convert a `Vec` with the right capacity into a `FixedCapacityVec`
impl<T, const N: usize> TryFrom<Vec<T>> for FixedCapacityVec<T, N> {
    type Error = Vec<T>;

    #[inline]
    fn try_from(mut vec: Vec<T>) -> Result<FixedCapacityVec<T, N>, Vec<T>> {
        // If `T` is zero-sized then the Vec won't have allocated (says the manual).
        // In that case our allocation is a ZST too, and we can indeed take the Vec's pointer
        if vec.capacity() == N || Layout::new::<T>().size() == 0 {
            Ok(unsafe {
                let data: *mut T = vec.as_mut_ptr();
                // Vec guarantees a non-null pointer
                let data: NonNull<T> = NonNull::new(data).unwrap_unchecked();
                let len = vec.len();
                // Take ownership and stop Vec's destructor running
                mem::forget(vec);
                Self::from_raw_parts(data, len)
            })
        } else {
            Err(vec)
        }
    }
}

mod safe;
pub use safe::*;

#[cfg(test)]
mod test;

#[cfg(not(feature = "minimal-1"))]
compile_error! { "You must enable at least one fixed-capacity-vec crate feature!" }