1#[cfg(feature = "read")]
2use alloc::boxed::Box;
3#[cfg(feature = "read")]
4use alloc::vec::Vec;
5use core::fmt;
6use core::mem::MaybeUninit;
7use core::ops;
8use core::ptr;
9use core::slice;
10
11mod sealed {
12 /// # Safety
13 /// Implementer must not modify the content in storage.
14 pub unsafe trait Sealed {
15 type Storage;
16
17 fn new_storage() -> Self::Storage;
18
19 fn grow(_storage: &mut Self::Storage, _additional: usize) -> Result<(), CapacityFull> {
20 Err(CapacityFull)
21 }
22 }
23
24 #[derive(Clone, Copy, Debug)]
25 pub struct CapacityFull;
26}
27
28use sealed::*;
29
30/// Marker trait for types that can be used as backing storage when a growable array type is needed.
31///
32/// This trait is sealed and cannot be implemented for types outside this crate.
33pub trait ArrayLike: Sealed {
34 /// Type of the elements being stored.
35 type Item;
36
37 #[doc(hidden)]
38 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<Self::Item>];
39
40 #[doc(hidden)]
41 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<Self::Item>];
42}
43
44// Use macro since const generics can't be used due to MSRV.
45macro_rules! impl_array {
46 () => {};
47 ($n:literal $($rest:tt)*) => {
48 // SAFETY: does not modify the content in storage.
49 unsafe impl<T> Sealed for [T; $n] {
50 type Storage = [MaybeUninit<T>; $n];
51
52 fn new_storage() -> Self::Storage {
53 // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid.
54 unsafe { MaybeUninit::uninit().assume_init() }
55 }
56 }
57
58 impl<T> ArrayLike for [T; $n] {
59 type Item = T;
60
61 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
62 storage
63 }
64
65 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
66 storage
67 }
68 }
69
70 impl_array!($($rest)*);
71 }
72}
73
74impl_array!(0 1 2 3 4 8 16 32 64 128 192);
75
76#[cfg(feature = "read")]
77unsafe impl<T> Sealed for Vec<T> {
78 type Storage = Box<[MaybeUninit<T>]>;
79
80 fn new_storage() -> Self::Storage {
81 Box::new([])
82 }
83
84 fn grow(storage: &mut Self::Storage, additional: usize) -> Result<(), CapacityFull> {
85 let mut vec: Vec<_> = core::mem::replace(storage, Box::new([])).into();
86 vec.reserve(additional);
87 // SAFETY: This is a `Vec` of `MaybeUninit`.
88 unsafe { vec.set_len(new_len:vec.capacity()) };
89 *storage = vec.into_boxed_slice();
90 Ok(())
91 }
92}
93
94#[cfg(feature = "read")]
95impl<T> ArrayLike for Vec<T> {
96 type Item = T;
97
98 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
99 storage
100 }
101
102 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
103 storage
104 }
105}
106
107pub(crate) struct ArrayVec<A: ArrayLike> {
108 storage: A::Storage,
109 len: usize,
110}
111
112impl<A: ArrayLike> ArrayVec<A> {
113 pub fn new() -> Self {
114 Self {
115 storage: A::new_storage(),
116 len: 0,
117 }
118 }
119
120 pub fn clear(&mut self) {
121 let ptr: *mut [A::Item] = &mut **self;
122 // Set length first so the type invariant is upheld even if `drop_in_place` panicks.
123 self.len = 0;
124 // SAFETY: `ptr` contains valid elements only and we "forget" them by setting the length.
125 unsafe { ptr::drop_in_place(ptr) };
126 }
127
128 pub fn try_push(&mut self, value: A::Item) -> Result<(), CapacityFull> {
129 let mut storage = A::as_mut_slice(&mut self.storage);
130 if self.len >= storage.len() {
131 A::grow(&mut self.storage, 1)?;
132 storage = A::as_mut_slice(&mut self.storage);
133 }
134
135 storage[self.len] = MaybeUninit::new(value);
136 self.len += 1;
137 Ok(())
138 }
139
140 pub fn try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityFull> {
141 assert!(index <= self.len);
142
143 let mut storage = A::as_mut_slice(&mut self.storage);
144 if self.len >= storage.len() {
145 A::grow(&mut self.storage, 1)?;
146 storage = A::as_mut_slice(&mut self.storage);
147 }
148
149 // SAFETY: storage[index] is filled later.
150 unsafe {
151 let p = storage.as_mut_ptr().add(index);
152 core::ptr::copy(p as *const _, p.add(1), self.len - index);
153 }
154 storage[index] = MaybeUninit::new(element);
155 self.len += 1;
156 Ok(())
157 }
158
159 pub fn pop(&mut self) -> Option<A::Item> {
160 if self.len == 0 {
161 None
162 } else {
163 self.len -= 1;
164 // SAFETY: this element is valid and we "forget" it by setting the length.
165 Some(unsafe { A::as_slice(&self.storage)[self.len].as_ptr().read() })
166 }
167 }
168
169 pub fn swap_remove(&mut self, index: usize) -> A::Item {
170 assert!(self.len > 0);
171 A::as_mut_slice(&mut self.storage).swap(index, self.len - 1);
172 self.pop().unwrap()
173 }
174}
175
176#[cfg(feature = "read")]
177impl<T> ArrayVec<Vec<T>> {
178 pub fn into_vec(mut self) -> Vec<T> {
179 let len: usize = core::mem::replace(&mut self.len, 0);
180 let storage = core::mem::replace(&mut self.storage, Box::new([]));
181 let slice = Box::leak(storage);
182 debug_assert!(len <= slice.len());
183 // SAFETY: valid elements.
184 unsafe { Vec::from_raw_parts(slice.as_mut_ptr() as *mut T, length:len, capacity:slice.len()) }
185 }
186}
187
188impl<A: ArrayLike> Drop for ArrayVec<A> {
189 fn drop(&mut self) {
190 self.clear();
191 }
192}
193
194impl<A: ArrayLike> Default for ArrayVec<A> {
195 fn default() -> Self {
196 Self::new()
197 }
198}
199
200impl<A: ArrayLike> ops::Deref for ArrayVec<A> {
201 type Target = [A::Item];
202
203 fn deref(&self) -> &[A::Item] {
204 let slice: &&[{unknown}] = &A::as_slice(&self.storage);
205 debug_assert!(self.len <= slice.len());
206 // SAFETY: valid elements.
207 unsafe { slice::from_raw_parts(slice.as_ptr() as _, self.len) }
208 }
209}
210
211impl<A: ArrayLike> ops::DerefMut for ArrayVec<A> {
212 fn deref_mut(&mut self) -> &mut [A::Item] {
213 let slice: &mut &mut [{unknown}] = &mut A::as_mut_slice(&mut self.storage);
214 debug_assert!(self.len <= slice.len());
215 // SAFETY: valid elements.
216 unsafe { slice::from_raw_parts_mut(slice.as_mut_ptr() as _, self.len) }
217 }
218}
219
220impl<A: ArrayLike> Clone for ArrayVec<A>
221where
222 A::Item: Clone,
223{
224 fn clone(&self) -> Self {
225 let mut new = Self::default();
226 for value in &**self {
227 new.try_push(value.clone()).unwrap();
228 }
229 new
230 }
231}
232
233impl<A: ArrayLike> PartialEq for ArrayVec<A>
234where
235 A::Item: PartialEq,
236{
237 fn eq(&self, other: &Self) -> bool {
238 **self == **other
239 }
240}
241
242impl<A: ArrayLike> Eq for ArrayVec<A> where A::Item: Eq {}
243
244impl<A: ArrayLike> fmt::Debug for ArrayVec<A>
245where
246 A::Item: fmt::Debug,
247{
248 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
249 fmt::Debug::fmt(&**self, f)
250 }
251}
252