recursive_array/
lib.rs

1#![no_std]
2
3use core::marker::PhantomData;
4
5/// a trait which when implemented by some type states that the type's memory representation can be treated directly as a slice of
6/// type `T`, with a length that is according to the `LENGTH` constant.
7pub unsafe trait RecursiveArray<T>: Sized + AsRef<[T]> + AsMut<[T]> {
8    /// the length of this array
9    const LENGTH: usize;
10
11    /// an empty recursive array.
12    const EMPTY: EmptyRecursiveArray = EmptyRecursiveArray;
13
14    /// returns an empty recursive array.
15    fn empty() -> EmptyRecursiveArray {
16        EmptyRecursiveArray
17    }
18
19    /// returns the length of this recursive array.
20    fn len(&self) -> usize {
21        Self::LENGTH
22    }
23
24    /// converts the given array to a recursive array.
25    ///
26    /// # Panics
27    ///
28    /// this function panics if the length of the array (`N`) is not equal to `Self::LENGTH`.
29    /// this condition currently can't be checked at compile time due to the limitation of const generics.
30    fn from_array<const N: usize>(array: [T; N]) -> Self {
31        if N != Self::LENGTH {
32            panic!(
33                "tried to convert an array of length {} to a recursive array of length {}",
34                N,
35                Self::LENGTH,
36            );
37        }
38        unsafe { runtime_checked_transmute(array) }
39    }
40
41    /// converts this recrusive array to a regular array (`[T; N]`).
42    ///
43    /// # Panics
44    ///
45    /// this function panics if the length of the array (`N`) is not equal to `Self::LENGTH`.
46    /// this condition currently can't be checked at compile time due to the limitation of const generics.
47    fn to_array<const N: usize>(self) -> [T; N] {
48        if N != Self::LENGTH {
49            panic!(
50                "tried to convert a recursive array of length {} to an array of length {}",
51                Self::LENGTH,
52                N,
53            );
54        }
55        unsafe { runtime_checked_transmute(self) }
56    }
57
58    /// converts the given slice to a recursive array reference. this is a zero cost operation, which just casts the slice.
59    ///
60    /// # Panics
61    ///
62    /// this function panics if the length of the slice is not equal to `Self::LENGTH`.
63    fn from_slice(slice: &[T]) -> &Self {
64        if slice.len() != Self::LENGTH {
65            panic!(
66                "tried to convert a slice of length {} to a recursive array of length {}",
67                slice.len(),
68                Self::LENGTH,
69            );
70        }
71        unsafe { &*slice.as_ptr().cast() }
72    }
73
74    /// converts the given mutable slice to a recursive array mutable reference. this is a zero cost operation, which just casts the slice.
75    ///
76    /// # Panics
77    ///
78    /// this function panics if the length of the slice is not equal to `Self::LENGTH`.
79    fn from_mut_slice(slice: &mut [T]) -> &mut Self {
80        if slice.len() != Self::LENGTH {
81            panic!(
82                "tried to convert a slice of length {} to a recursive array of length {}",
83                slice.len(),
84                Self::LENGTH,
85            );
86        }
87        unsafe { &mut *slice.as_mut_ptr().cast() }
88    }
89
90    /// returns the elements of this array as a slice.
91    fn as_slice(&self) -> &[T] {
92        unsafe { core::slice::from_raw_parts(self as *const Self as *const T, Self::LENGTH) }
93    }
94
95    /// returns the elements of this array as a mutable slice.
96    fn as_mut_slice(&mut self) -> &mut [T] {
97        unsafe { core::slice::from_raw_parts_mut(self as *mut Self as *mut T, Self::LENGTH) }
98    }
99
100    /// appends an element to the back of this array.
101    fn push_back(
102        self,
103        item: T,
104    ) -> RecursiveArrayConcatenation<T, Self, RecursiveArraySingleItem<T>> {
105        RecursiveArrayConcatenation::new(self, RecursiveArraySingleItem::new(item))
106    }
107
108    /// appends a recrusive array to the back of this array.
109    fn append_back<R: RecursiveArray<T>>(
110        self,
111        array: R,
112    ) -> RecursiveArrayConcatenation<T, Self, R> {
113        RecursiveArrayConcatenation::new(self, array)
114    }
115
116    /// appends an element to the fron of this array.
117    fn push_front(
118        self,
119        item: T,
120    ) -> RecursiveArrayConcatenation<T, RecursiveArraySingleItem<T>, Self> {
121        RecursiveArrayConcatenation::new(RecursiveArraySingleItem::new(item), self)
122    }
123
124    /// appends a recrusive array to the front of this array.
125    fn append_front<R: RecursiveArray<T>>(
126        self,
127        array: R,
128    ) -> RecursiveArrayConcatenation<T, R, Self> {
129        RecursiveArrayConcatenation::new(array, self)
130    }
131}
132
133/// an empty recrusive array.
134#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Default)]
135pub struct EmptyRecursiveArray;
136impl<T> AsRef<[T]> for EmptyRecursiveArray {
137    fn as_ref(&self) -> &[T] {
138        &[]
139    }
140}
141impl<T> AsMut<[T]> for EmptyRecursiveArray {
142    fn as_mut(&mut self) -> &mut [T] {
143        &mut []
144    }
145}
146unsafe impl<T> RecursiveArray<T> for EmptyRecursiveArray {
147    const LENGTH: usize = 0;
148}
149
150/// a recursive array with a single item.
151#[derive(Debug, Clone, Hash, PartialEq, Eq, Default)]
152#[repr(transparent)]
153pub struct RecursiveArraySingleItem<T> {
154    item: T,
155}
156impl<T> AsRef<[T]> for RecursiveArraySingleItem<T> {
157    fn as_ref(&self) -> &[T] {
158        self.as_slice()
159    }
160}
161impl<T> AsMut<[T]> for RecursiveArraySingleItem<T> {
162    fn as_mut(&mut self) -> &mut [T] {
163        self.as_mut_slice()
164    }
165}
166unsafe impl<T> RecursiveArray<T> for RecursiveArraySingleItem<T> {
167    const LENGTH: usize = 1;
168}
169impl<T> RecursiveArraySingleItem<T> {
170    /// creates a new recrusive array with a single item.
171    pub fn new(item: T) -> Self {
172        Self { item }
173    }
174}
175
176/// a recursive array which concatenates 2 recursive arrays.
177#[derive(Debug, Clone, Hash, PartialEq, Eq, Default)]
178#[repr(C)]
179pub struct RecursiveArrayConcatenation<T, A: RecursiveArray<T>, B: RecursiveArray<T>> {
180    a: A,
181    b: B,
182    phantom: PhantomData<T>,
183}
184impl<T, A: RecursiveArray<T>, B: RecursiveArray<T>> AsRef<[T]>
185    for RecursiveArrayConcatenation<T, A, B>
186{
187    fn as_ref(&self) -> &[T] {
188        self.as_slice()
189    }
190}
191impl<T, A: RecursiveArray<T>, B: RecursiveArray<T>> AsMut<[T]>
192    for RecursiveArrayConcatenation<T, A, B>
193{
194    fn as_mut(&mut self) -> &mut [T] {
195        self.as_mut_slice()
196    }
197}
198unsafe impl<T, A: RecursiveArray<T>, B: RecursiveArray<T>> RecursiveArray<T>
199    for RecursiveArrayConcatenation<T, A, B>
200{
201    const LENGTH: usize = A::LENGTH + B::LENGTH;
202}
203impl<T, A: RecursiveArray<T>, B: RecursiveArray<T>> RecursiveArrayConcatenation<T, A, B> {
204    /// creates a new recrusive array which concatenates the 2 given recursive arrays.
205    pub fn new(a: A, b: B) -> Self {
206        Self {
207            a,
208            b,
209            phantom: PhantomData,
210        }
211    }
212}
213impl<T, A: RecursiveArray<T>> RecursiveArrayConcatenation<T, A, RecursiveArraySingleItem<T>> {
214    /// pops an element from the back of this array.
215    /// returns a tuple whose first element is the popped item and its second element is the rest of the array.
216    pub fn pop_back(self) -> (T, A) {
217        (self.b.item, self.a)
218    }
219}
220
221impl<T, B: RecursiveArray<T>> RecursiveArrayConcatenation<T, RecursiveArraySingleItem<T>, B> {
222    /// pops an element from the front of this array.
223    /// returns a tuple whose first element is the popped item and its second element is the rest of the array.
224    pub fn pop_front(self) -> (T, B) {
225        (self.a.item, self.b)
226    }
227}
228
229/// a recursive array wrapper which wraps a regular rust array (`[T; N]`) and allows it to be treated as a recursive array.
230#[derive(Debug, Clone, Hash, PartialEq, Eq)]
231#[repr(transparent)]
232pub struct RecursiveArrayArrayWrapper<const N: usize, T> {
233    array: [T; N],
234}
235impl<const N: usize, T> RecursiveArrayArrayWrapper<N, T> {
236    /// creates a new recursive array wrapper which wraps the given array.
237    pub fn new(array: [T; N]) -> Self {
238        Self { array }
239    }
240}
241impl<const N: usize, T> AsRef<[T]> for RecursiveArrayArrayWrapper<N, T> {
242    fn as_ref(&self) -> &[T] {
243        self.as_slice()
244    }
245}
246impl<const N: usize, T> AsMut<[T]> for RecursiveArrayArrayWrapper<N, T> {
247    fn as_mut(&mut self) -> &mut [T] {
248        self.as_mut_slice()
249    }
250}
251unsafe impl<const N: usize, T> RecursiveArray<T> for RecursiveArrayArrayWrapper<N, T> {
252    const LENGTH: usize = N;
253}
254
255/// a recursive array which multiplies the given inner recursive array type `N` times.
256#[derive(Debug, Clone, Hash, PartialEq, Eq)]
257#[repr(transparent)]
258pub struct RecursiveArrayMultiplier<const N: usize, T, A: RecursiveArray<T>> {
259    multiplied: [A; N],
260    phantom: PhantomData<T>,
261}
262impl<const N: usize, T, A: RecursiveArray<T>> RecursiveArrayMultiplier<N, T, A> {
263    /// creates a new recursive array multiplier with the given values.
264    pub fn new(values: [A; N]) -> Self {
265        Self {
266            multiplied: values,
267            phantom: PhantomData,
268        }
269    }
270}
271impl<const N: usize, T, A: RecursiveArray<T>> AsRef<[T]> for RecursiveArrayMultiplier<N, T, A> {
272    fn as_ref(&self) -> &[T] {
273        self.as_slice()
274    }
275}
276impl<const N: usize, T, A: RecursiveArray<T>> AsMut<[T]> for RecursiveArrayMultiplier<N, T, A> {
277    fn as_mut(&mut self) -> &mut [T] {
278        self.as_mut_slice()
279    }
280}
281unsafe impl<const N: usize, T, A: RecursiveArray<T>> RecursiveArray<T>
282    for RecursiveArrayMultiplier<N, T, A>
283{
284    const LENGTH: usize = A::LENGTH * N;
285}
286
287/// a macro for instantiating a recursive array with the given elements.
288#[macro_export]
289macro_rules! recursive_array {
290    [] => {
291        ::recursive_array::EmptyRecursiveArray
292    };
293    [$item: expr $(,)?] => {
294        ::recursive_array::RecursiveArraySingleItem::new($item)
295    };
296    [$first_item: expr, $($item: expr),+] => {
297        ::recursive_array::RecursiveArrayConcatenation::new(
298            ::recursive_array::RecursiveArraySingleItem::new($first_item),
299            ::recursive_array::recursive_array![$($item),+],
300        )
301    };
302}
303
304/// a macro for getting the type of a generic array with the given item type and size.
305#[macro_export]
306macro_rules! recursive_array_type_of_size {
307    ($item_type: ty, $size: expr) => {
308        ::recursive_array::RecursiveArrayArrayWrapper<{$size}, $item_type>
309    };
310}
311
312/// A const reimplementation of the [`transmute`](core::mem::transmute) function,
313/// avoiding problems when the compiler can't prove equal sizes.
314///
315/// # Safety
316/// Treat this the same as [`transmute`](core::mem::transmute), or (preferably) don't use it at all.
317unsafe fn runtime_checked_transmute<A, B>(a: A) -> B {
318    if core::mem::size_of::<A>() != core::mem::size_of::<B>() {
319        panic!(
320            "tried to transmute a type of size {} to a type of size {}",
321            core::mem::size_of::<A>(),
322            core::mem::size_of::<B>()
323        );
324    }
325
326    #[repr(C)]
327    union Union<A, B> {
328        a: core::mem::ManuallyDrop<A>,
329        b: core::mem::ManuallyDrop<B>,
330    }
331
332    let a = core::mem::ManuallyDrop::new(a);
333    core::mem::ManuallyDrop::into_inner(Union { a }.b)
334}
recursive_array/lib.rs

recursive_array/
lib.rs
