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!" }