fixed_capacity_vec/
lib.rs

1#![doc=include_str!("../README.md")]
2
3use alloc::handle_alloc_error;
4use core::fmt::{self, Debug, Display};
5use core::hash::Hash;
6use core::ops::{Deref, DerefMut};
7use std::alloc::{self, Layout};
8use std::convert::TryFrom;
9use std::ptr::NonNull;
10use std::{mem, ptr};
11
12/// Like `Vec` with a capacity fixed at compile time
13///
14/// When full, can be converted without copying into `Box<[T; N]>`, using `TryFrom`.
15///
16/// See the [crate-level docs](crate) for an introduction,
17/// and comparison to other data types.
18//
19// TODO we should impl Serialize, ...
20pub struct FixedCapacityVec<T, const N: usize> {
21    /// Data
22    ///
23    /// ### SAFETY
24    ///
25    /// Every element of data in 0..len must always be initialised.
26    ///
27    /// Always a valid, properly aligned, heap pointer to a `[T; N]`.
28    ///
29    /// Exception: if `[T; N]` is a ZST, i.e. `LAYOUT.size()` is zero,
30    /// a dangling nonnull pointer is used instead.
31    /// See [`std::boxed` on Memory layout](std::boxed#memory-layout).
32    ///
33    /// The constant [`Self::NZST`] can be used to test whether there's an allocation.
34    ///
35    /// ### Variance
36    ///
37    /// We want covariance: `FixedCapacityVec<T>` needs to be covariant in `T`,
38    /// like `Vec` is.
39    ///
40    /// See the Rustonomicon section on
41    /// [Variance](https://doc.rust-lang.org/nomicon/subtyping.html#variance),
42    /// including in particular the table of example types and their variances.
43    data: NonNull<T>,
44
45    /// Initialised portion
46    ///
47    /// **SAFETY**: See `data`
48    len: usize,
49}
50
51/// Implement `$trait` if `T: $trait`
52macro_rules! impl_traits_if_T { { $( $trait:path $(, $unsafe:tt )?; )* } => { $(
53    $( $unsafe )? impl<T: $trait, const N: usize> $trait for FixedCapacityVec<T, N> {}
54)* } }
55
56// (Vec implements all of these with the same bounds as we do)
57impl_traits_if_T! {
58    Send, unsafe;
59    Sync, unsafe;
60    std::panic::UnwindSafe;
61    std::panic::RefUnwindSafe;
62}
63
64impl<T, const N: usize> FixedCapacityVec<T, N> {
65    /// Create a new empty `FixedCapacityVec`, capable of holding up to `N` values of type `T`
66    #[inline]
67    pub fn new() -> Self {
68        let data = if Self::NZST {
69            unsafe {
70                // SAFETY: the Layout is good since we got it from Layout::new
71                let data: *mut u8 = alloc::alloc(Self::LAYOUT);
72                let data: *mut T = data as _;
73                let data: NonNull<T> =
74                    NonNull::new(data).unwrap_or_else(|| handle_alloc_error(Self::LAYOUT));
75                data
76            }
77        } else {
78            NonNull::dangling()
79        };
80
81        FixedCapacityVec { data, len: 0 }
82    }
83
84    /// Return the `Layout` for our `data` pointer allocation
85    const LAYOUT: Layout = { Layout::new::<[T; N]>() };
86
87    /// True iff `[T; N]` is not a ZST: ie, if we **do** actually have an allocation.
88    const NZST: bool = { Self::LAYOUT.size() != 0 };
89
90    /// Return the number of values stored so far
91    //
92    // Not in safe.rs to get right method ordering in the docs
93    #[inline]
94    pub fn len(&self) -> usize {
95        self.len
96    }
97
98    /// Returns `true` iff the `FixedCapacityVec` is empty
99    //
100    // Not in safe.rs to get right method ordering in the docs
101    #[inline]
102    pub fn is_empty(&self) -> bool {
103        self.len == 0
104    }
105
106    /// Returns `true` iff the `FixedCapacityVec` is full - ie, it has `N` elements
107    //
108    // Not in safe.rs because unsafe code relies on it, and
109    // to get right method ordering in the docs.
110    #[inline]
111    pub fn is_full(&self) -> bool {
112        self.len == N
113    }
114
115    /// Append an element
116    ///
117    /// # Panics
118    ///
119    /// Panics if the `FixedCapacityVec` is full, ie if it already contains `N` elements
120    #[inline]
121    pub fn push(&mut self, item: T) {
122        self.try_push_or_discard(item).unwrap();
123    }
124
125    /// Remove an element from the end
126    #[inline]
127    pub fn pop(&mut self) -> Option<T> {
128        self.len = self.len.checked_sub(1)?;
129        let item = unsafe {
130            // item was initialised, since it was within the (old) length
131            // we have marked it uninit in the array, so we can take it here
132            self.data.as_ptr().add(self.len).read()
133        };
134        Some(item)
135    }
136
137    /// Return a slice pointer to the filled data
138    ///
139    /// ### SAFETY
140    ///
141    /// This method is, itself, safe.
142    /// But even better, the returned slice can be safely turned into a reference,
143    /// assuming the mutability and lifetime is right.
144    #[inline]
145    fn slice(&self) -> NonNull<[T]> {
146        // Would like NonNull::slice_from_raw_parts but its MSRV is 1.70.0
147        let p = self.data.as_ptr(); // turns NonNull into T pointer
148        let p = ptr::slice_from_raw_parts(p, self.len); // turns T pointer into slice pointer
149        unsafe { NonNull::new(p as _).unwrap_unchecked() } // pointer back to NonNull
150    }
151
152    /// Construct a `FixedCapacityVec` out of an allocation pointer and length
153    ///
154    /// ### SAFETY
155    ///
156    ///  * `data` must be from an allocation with layout `[T; N]`,
157    ///    or, iff `[T; N]` is a ZST, a valid dangling non-null pointer.
158    ///    (These are the same rules as for `Vec` and `Box`.)
159    ///
160    ///  * The elements `0..length` must be initialised.
161    ///
162    ///  * Obviously `length` must be `<= N`.
163    #[inline]
164    unsafe fn from_raw_parts(data: NonNull<T>, length: usize) -> Self {
165        Self { data, len: length }
166    }
167
168    /// Deconstruct a `FixedCapacityVec` into an allocation pointer and length
169    ///
170    /// The returned pieces are as for the inputs to
171    /// [`from_raw_parts`](Self::from_raw_parts).
172    #[inline]
173    fn into_raw_parts(self) -> (NonNull<T>, usize) {
174        let data = self.data;
175        let len = self.len;
176        mem::forget(self);
177        (data, len)
178    }
179}
180
181/// Defines a "try_push" function, with visibility `$vis` and name `$fn`
182///
183/// The generated function will behave as follows:
184///
185/// If there is space, will push `$item` and return `Ok(())`.
186///
187/// Otherwise, it will return `Err($err)`.  `$err` should be of type `Error`.
188macro_rules! define_try_push { {
189    $( # $attr:tt )*
190    $vis:vis fn $fn:ident($item:ident) -> Result<, $Error:ty> { or Err($err:expr) }
191} => {
192    impl<T, const N: usize> FixedCapacityVec<T, N> {
193        $( # $attr )*
194        $vis fn $fn(&mut self, $item: T) -> Result<(), $Error> {
195            if self.len >= N {
196                return Err($err);
197            }
198            unsafe {
199                // SAFETY now len is within bounds and the pointer is aligned
200                if Self::NZST {
201                    self.data.as_ptr().add(self.len).write($item);
202                }
203                // SAFETY now that the value is written, we can say it's there
204                self.len += 1;
205            }
206            Ok(())
207        }
208    }
209} }
210
211define_try_push! {
212    /// Try to append an element
213    ///
214    /// If the `FixedCapacityVec` is full, i.e. if it already contains `N` elements,
215    /// discards the element and returns `Err`.
216    //
217    // clippy wanted the custom FullError type, rather than simply ().
218    // I think I agree that's better; it makes `.unwrap()` work right,
219    // in our impl of push(), for example.
220    #[inline]
221    pub fn try_push_or_discard(item) -> Result<, FullError> { or Err(FullError) }
222}
223
224define_try_push! {
225    /// Try to append an element
226    ///
227    /// If the `FixedCapacityVec` is full, i.e. if it already contains `N` elements,
228    /// return the putative new item in `Err`.
229    ///
230    /// If you don't need the item back, in the `Err` case,
231    /// consider `try_push_or_discard`, which can be marginally faster,
232    /// as its return type doesn't need to maybe include a `T`.
233    #[inline]
234    pub fn try_push(item) -> Result<, T> { or Err(item) }
235}
236
237impl<T, const N: usize> Drop for FixedCapacityVec<T, N> {
238    #[inline]
239    fn drop(&mut self) {
240        unsafe {
241            // SAFETY
242            //
243            // We are about to break the invariants!  This is OK, because it cannot
244            // be observed by anyone: we have &mut Self, so no-one else can see it,
245            // and even if a panic unwinds from here, `self` will no longer be considered
246            // valid by the language.
247            if mem::needs_drop::<T>() {
248                let data: NonNull<[T]> = self.slice();
249                // This causes the supposedly-valid portion of data to become totally
250                // invalid, breaking the invariants.  See above.
251                ptr::drop_in_place(data.as_ptr());
252            }
253            // SAFETY: this causes self.data to become totally invalid, breaking
254            // the invariants.  That's OK; see above.
255            if Self::NZST {
256                alloc::dealloc(self.data.as_ptr() as _, Self::LAYOUT);
257            }
258        }
259    }
260}
261
262impl<T, const N: usize> Deref for FixedCapacityVec<T, N> {
263    type Target = [T];
264
265    #[inline]
266    fn deref(&self) -> &[T] {
267        unsafe {
268            // SAFETY
269            // See slice().  The lifetime and mutability are enforced by the Deref trait
270            self.slice().as_ref()
271        }
272    }
273}
274
275impl<T, const N: usize> DerefMut for FixedCapacityVec<T, N> {
276    #[inline]
277    fn deref_mut(&mut self) -> &mut [T] {
278        unsafe {
279            // SAFETY
280            // See slice().  The lifetime and mutability are enforced by the Deref trait
281            self.slice().as_mut()
282        }
283    }
284}
285
286/// Convert a full `FixedCapacityVec` into a boxed array.
287///
288/// If the `FixedCapacityVec` isn't full, it is returned as the `Err`
289impl<T, const N: usize> TryFrom<FixedCapacityVec<T, N>> for Box<[T; N]> {
290    type Error = FixedCapacityVec<T, N>;
291
292    #[inline]
293    fn try_from(v: FixedCapacityVec<T, N>) -> Result<Box<[T; N]>, FixedCapacityVec<T, N>> {
294        if v.len == N {
295            Ok(unsafe {
296                let data: *mut [T; N] = v.data.as_ptr() as _;
297                // stop drop from running
298                mem::forget(v);
299                // SAFETY
300                // We have checked that every element is initialised
301                // The pointer is valid according to the rules for Box, even for a ZST.
302                // We pass ownership to the Box; that's OK, because we've called forget.
303                let data: Box<[T; N]> = Box::from_raw(data);
304                data
305            })
306        } else {
307            Err(v)
308        }
309    }
310}
311
312/// Convert a boxed array into a full `FixedCapacityVec`
313impl<T, const N: usize> From<Box<[T; N]>> for FixedCapacityVec<T, N> {
314    #[inline]
315    fn from(b: Box<[T; N]>) -> FixedCapacityVec<T, N> {
316        let b: *mut [T; N] = Box::into_raw(b);
317        let b: *mut T = b as _;
318        // Docs for Box say this is non-null
319        let b: NonNull<T> = unsafe { NonNull::new(b).unwrap_unchecked() };
320        unsafe { FixedCapacityVec::from_raw_parts(b, N) }
321    }
322}
323
324/// Convert a `FixedCapacityVec` into a `Vec`
325impl<T, const N: usize> From<FixedCapacityVec<T, N>> for Vec<T> {
326    #[inline]
327    fn from(v: FixedCapacityVec<T, N>) -> Vec<T> {
328        unsafe {
329            let (data, len) = v.into_raw_parts();
330            let data: *mut T = data.as_ptr();
331            // SAFETY
332            // Elements up to len are initialised
333            // The pointer is valid according to the rules for Vec, even for a ZST.
334            // We pass ownership to the Vec.
335            let vec: Vec<T> = Vec::from_raw_parts(data, len, N);
336            vec
337        }
338    }
339}
340
341/// Convert a `Vec` with the right capacity into a `FixedCapacityVec`
342impl<T, const N: usize> TryFrom<Vec<T>> for FixedCapacityVec<T, N> {
343    type Error = Vec<T>;
344
345    #[inline]
346    fn try_from(mut vec: Vec<T>) -> Result<FixedCapacityVec<T, N>, Vec<T>> {
347        // If `T` is zero-sized then the Vec won't have allocated (says the manual).
348        // In that case our allocation is a ZST too, and we can indeed take the Vec's pointer
349        if vec.capacity() == N || Layout::new::<T>().size() == 0 {
350            Ok(unsafe {
351                let data: *mut T = vec.as_mut_ptr();
352                // Vec guarantees a non-null pointer
353                let data: NonNull<T> = NonNull::new(data).unwrap_unchecked();
354                let len = vec.len();
355                // Take ownership and stop Vec's destructor running
356                mem::forget(vec);
357                Self::from_raw_parts(data, len)
358            })
359        } else {
360            Err(vec)
361        }
362    }
363}
364
365mod safe;
366pub use safe::*;
367
368#[cfg(test)]
369mod test;
370
371#[cfg(not(feature = "minimal-1"))]
372compile_error! { "You must enable at least one fixed-capacity-vec crate feature!" }