generic_array/
lib.rs

1//! This crate implements a structure that can be used as a generic array type.
2//! Core Rust array types `[T; N]` can't be used generically with
3//! respect to `N`, so for example this:
4//!
5//! ```rust{compile_fail}
6//! struct Foo<T, N> {
7//!     data: [T; N]
8//! }
9//! ```
10//!
11//! won't work.
12//!
13//! **generic-array** exports a `GenericArray<T,N>` type, which lets
14//! the above be implemented as:
15//!
16//! ```rust
17//! use generic_array::{ArrayLength, GenericArray};
18//!
19//! struct Foo<T, N: ArrayLength<T>> {
20//!     data: GenericArray<T,N>
21//! }
22//! ```
23//!
24//! The `ArrayLength<T>` trait is implemented by default for
25//! [unsigned integer types](../typenum/uint/index.html) from
26//! [typenum](../typenum/index.html):
27//!
28//! ```rust
29//! # use generic_array::{ArrayLength, GenericArray};
30//! use generic_array::typenum::U5;
31//!
32//! struct Foo<N: ArrayLength<i32>> {
33//!     data: GenericArray<i32, N>
34//! }
35//!
36//! # fn main() {
37//! let foo = Foo::<U5>{data: GenericArray::default()};
38//! # }
39//! ```
40//!
41//! For example, `GenericArray<T, U5>` would work almost like `[T; 5]`:
42//!
43//! ```rust
44//! # use generic_array::{ArrayLength, GenericArray};
45//! use generic_array::typenum::U5;
46//!
47//! struct Foo<T, N: ArrayLength<T>> {
48//!     data: GenericArray<T, N>
49//! }
50//!
51//! # fn main() {
52//! let foo = Foo::<i32, U5>{data: GenericArray::default()};
53//! # }
54//! ```
55//!
56//! For ease of use, an `arr!` macro is provided - example below:
57//!
58//! ```
59//! # #[macro_use]
60//! # extern crate generic_array;
61//! # extern crate typenum;
62//! # fn main() {
63//! let array = arr![u32; 1, 2, 3];
64//! assert_eq!(array[2], 3);
65//! # }
66//! ```
67
68#![deny(missing_docs)]
69#![deny(meta_variable_misuse)]
70#![no_std]
71#![cfg_attr(docsrs, feature(doc_auto_cfg))]
72
73#[cfg(feature = "serde")]
74extern crate serde;
75
76#[cfg(feature = "zeroize")]
77extern crate zeroize;
78
79#[cfg(test)]
80extern crate bincode;
81
82pub extern crate typenum;
83
84mod hex;
85mod impls;
86
87#[cfg(feature = "serde")]
88mod impl_serde;
89
90#[cfg(feature = "zeroize")]
91mod impl_zeroize;
92
93use core::iter::FromIterator;
94use core::marker::PhantomData;
95use core::mem::{MaybeUninit, ManuallyDrop};
96use core::ops::{Deref, DerefMut};
97use core::{mem, ptr, slice};
98use typenum::bit::{B0, B1};
99use typenum::uint::{UInt, UTerm, Unsigned};
100
101#[cfg_attr(test, macro_use)]
102pub mod arr;
103pub mod functional;
104pub mod iter;
105pub mod sequence;
106
107use self::functional::*;
108pub use self::iter::GenericArrayIter;
109use self::sequence::*;
110
111/// Trait making `GenericArray` work, marking types to be used as length of an array
112pub unsafe trait ArrayLength<T>: Unsigned {
113    /// Associated type representing the array type for the number
114    type ArrayType;
115}
116
117unsafe impl<T> ArrayLength<T> for UTerm {
118    #[doc(hidden)]
119    type ArrayType = [T; 0];
120}
121
122/// Internal type used to generate a struct of appropriate size
123#[allow(dead_code)]
124#[repr(C)]
125#[doc(hidden)]
126pub struct GenericArrayImplEven<T, U> {
127    parent1: U,
128    parent2: U,
129    _marker: PhantomData<T>,
130}
131
132impl<T: Clone, U: Clone> Clone for GenericArrayImplEven<T, U> {
133    fn clone(&self) -> GenericArrayImplEven<T, U> {
134        GenericArrayImplEven {
135            parent1: self.parent1.clone(),
136            parent2: self.parent2.clone(),
137            _marker: PhantomData,
138        }
139    }
140}
141
142impl<T: Copy, U: Copy> Copy for GenericArrayImplEven<T, U> {}
143
144/// Internal type used to generate a struct of appropriate size
145#[allow(dead_code)]
146#[repr(C)]
147#[doc(hidden)]
148pub struct GenericArrayImplOdd<T, U> {
149    parent1: U,
150    parent2: U,
151    data: T,
152}
153
154impl<T: Clone, U: Clone> Clone for GenericArrayImplOdd<T, U> {
155    fn clone(&self) -> GenericArrayImplOdd<T, U> {
156        GenericArrayImplOdd {
157            parent1: self.parent1.clone(),
158            parent2: self.parent2.clone(),
159            data: self.data.clone(),
160        }
161    }
162}
163
164impl<T: Copy, U: Copy> Copy for GenericArrayImplOdd<T, U> {}
165
166unsafe impl<T, N: ArrayLength<T>> ArrayLength<T> for UInt<N, B0> {
167    #[doc(hidden)]
168    type ArrayType = GenericArrayImplEven<T, N::ArrayType>;
169}
170
171unsafe impl<T, N: ArrayLength<T>> ArrayLength<T> for UInt<N, B1> {
172    #[doc(hidden)]
173    type ArrayType = GenericArrayImplOdd<T, N::ArrayType>;
174}
175
176/// Struct representing a generic array - `GenericArray<T, N>` works like [T; N]
177#[allow(dead_code)]
178#[repr(transparent)]
179pub struct GenericArray<T, U: ArrayLength<T>> {
180    data: U::ArrayType,
181}
182
183unsafe impl<T: Send, N: ArrayLength<T>> Send for GenericArray<T, N> {}
184unsafe impl<T: Sync, N: ArrayLength<T>> Sync for GenericArray<T, N> {}
185
186impl<T, N> Deref for GenericArray<T, N>
187where
188    N: ArrayLength<T>,
189{
190    type Target = [T];
191
192    #[inline(always)]
193    fn deref(&self) -> &[T] {
194        unsafe { slice::from_raw_parts(self as *const Self as *const T, N::USIZE) }
195    }
196}
197
198impl<T, N> DerefMut for GenericArray<T, N>
199where
200    N: ArrayLength<T>,
201{
202    #[inline(always)]
203    fn deref_mut(&mut self) -> &mut [T] {
204        unsafe { slice::from_raw_parts_mut(self as *mut Self as *mut T, N::USIZE) }
205    }
206}
207
208/// Creates an array one element at a time using a mutable iterator
209/// you can write to with `ptr::write`.
210///
211/// Increment the position while iterating to mark off created elements,
212/// which will be dropped if `into_inner` is not called.
213#[doc(hidden)]
214pub struct ArrayBuilder<T, N: ArrayLength<T>> {
215    array: MaybeUninit<GenericArray<T, N>>,
216    position: usize,
217}
218
219impl<T, N: ArrayLength<T>> ArrayBuilder<T, N> {
220    #[doc(hidden)]
221    #[inline]
222    pub unsafe fn new() -> ArrayBuilder<T, N> {
223        ArrayBuilder {
224            array: MaybeUninit::uninit(),
225            position: 0,
226        }
227    }
228
229    /// Creates a mutable iterator for writing to the array using `ptr::write`.
230    ///
231    /// Increment the position value given as a mutable reference as you iterate
232    /// to mark how many elements have been created.
233    #[doc(hidden)]
234    #[inline]
235    pub unsafe fn iter_position(&mut self) -> (slice::IterMut<T>, &mut usize) {
236        ((&mut *self.array.as_mut_ptr()).iter_mut(), &mut self.position)
237    }
238
239    /// When done writing (assuming all elements have been written to),
240    /// get the inner array.
241    #[doc(hidden)]
242    #[inline]
243    pub unsafe fn into_inner(self) -> GenericArray<T, N> {
244        let array = ptr::read(&self.array);
245
246        mem::forget(self);
247
248        array.assume_init()
249    }
250}
251
252impl<T, N: ArrayLength<T>> Drop for ArrayBuilder<T, N> {
253    fn drop(&mut self) {
254        if mem::needs_drop::<T>() {
255            unsafe {
256                for value in &mut (&mut *self.array.as_mut_ptr())[..self.position] {
257                    ptr::drop_in_place(value);
258                }
259            }
260        }
261    }
262}
263
264/// Consumes an array.
265///
266/// Increment the position while iterating and any leftover elements
267/// will be dropped if position does not go to N
268#[doc(hidden)]
269pub struct ArrayConsumer<T, N: ArrayLength<T>> {
270    array: ManuallyDrop<GenericArray<T, N>>,
271    position: usize,
272}
273
274impl<T, N: ArrayLength<T>> ArrayConsumer<T, N> {
275    #[doc(hidden)]
276    #[inline]
277    pub unsafe fn new(array: GenericArray<T, N>) -> ArrayConsumer<T, N> {
278        ArrayConsumer {
279            array: ManuallyDrop::new(array),
280            position: 0,
281        }
282    }
283
284    /// Creates an iterator and mutable reference to the internal position
285    /// to keep track of consumed elements.
286    ///
287    /// Increment the position as you iterate to mark off consumed elements
288    #[doc(hidden)]
289    #[inline]
290    pub unsafe fn iter_position(&mut self) -> (slice::Iter<T>, &mut usize) {
291        (self.array.iter(), &mut self.position)
292    }
293}
294
295impl<T, N: ArrayLength<T>> Drop for ArrayConsumer<T, N> {
296    fn drop(&mut self) {
297        if mem::needs_drop::<T>() {
298            for value in &mut self.array[self.position..N::USIZE] {
299                unsafe {
300                    ptr::drop_in_place(value);
301                }
302            }
303        }
304    }
305}
306
307impl<'a, T: 'a, N> IntoIterator for &'a GenericArray<T, N>
308where
309    N: ArrayLength<T>,
310{
311    type IntoIter = slice::Iter<'a, T>;
312    type Item = &'a T;
313
314    fn into_iter(self: &'a GenericArray<T, N>) -> Self::IntoIter {
315        self.as_slice().iter()
316    }
317}
318
319impl<'a, T: 'a, N> IntoIterator for &'a mut GenericArray<T, N>
320where
321    N: ArrayLength<T>,
322{
323    type IntoIter = slice::IterMut<'a, T>;
324    type Item = &'a mut T;
325
326    fn into_iter(self: &'a mut GenericArray<T, N>) -> Self::IntoIter {
327        self.as_mut_slice().iter_mut()
328    }
329}
330
331impl<T, N> FromIterator<T> for GenericArray<T, N>
332where
333    N: ArrayLength<T>,
334{
335    fn from_iter<I>(iter: I) -> GenericArray<T, N>
336    where
337        I: IntoIterator<Item = T>,
338    {
339        unsafe {
340            let mut destination = ArrayBuilder::new();
341
342            {
343                let (destination_iter, position) = destination.iter_position();
344
345                iter.into_iter()
346                    .zip(destination_iter)
347                    .for_each(|(src, dst)| {
348                        ptr::write(dst, src);
349
350                        *position += 1;
351                    });
352            }
353
354            if destination.position < N::USIZE {
355                from_iter_length_fail(destination.position, N::USIZE);
356            }
357
358            destination.into_inner()
359        }
360    }
361}
362
363#[inline(never)]
364#[cold]
365fn from_iter_length_fail(length: usize, expected: usize) -> ! {
366    panic!(
367        "GenericArray::from_iter received {} elements but expected {}",
368        length, expected
369    );
370}
371
372unsafe impl<T, N> GenericSequence<T> for GenericArray<T, N>
373where
374    N: ArrayLength<T>,
375    Self: IntoIterator<Item = T>,
376{
377    type Length = N;
378    type Sequence = Self;
379
380    fn generate<F>(mut f: F) -> GenericArray<T, N>
381    where
382        F: FnMut(usize) -> T,
383    {
384        unsafe {
385            let mut destination = ArrayBuilder::new();
386
387            {
388                let (destination_iter, position) = destination.iter_position();
389
390                destination_iter.enumerate().for_each(|(i, dst)| {
391                    ptr::write(dst, f(i));
392
393                    *position += 1;
394                });
395            }
396
397            destination.into_inner()
398        }
399    }
400
401    #[doc(hidden)]
402    fn inverted_zip<B, U, F>(
403        self,
404        lhs: GenericArray<B, Self::Length>,
405        mut f: F,
406    ) -> MappedSequence<GenericArray<B, Self::Length>, B, U>
407    where
408        GenericArray<B, Self::Length>:
409            GenericSequence<B, Length = Self::Length> + MappedGenericSequence<B, U>,
410        Self: MappedGenericSequence<T, U>,
411        Self::Length: ArrayLength<B> + ArrayLength<U>,
412        F: FnMut(B, Self::Item) -> U,
413    {
414        unsafe {
415            let mut left = ArrayConsumer::new(lhs);
416            let mut right = ArrayConsumer::new(self);
417
418            let (left_array_iter, left_position) = left.iter_position();
419            let (right_array_iter, right_position) = right.iter_position();
420
421            FromIterator::from_iter(left_array_iter.zip(right_array_iter).map(|(l, r)| {
422                let left_value = ptr::read(l);
423                let right_value = ptr::read(r);
424
425                *left_position += 1;
426                *right_position += 1;
427
428                f(left_value, right_value)
429            }))
430        }
431    }
432
433    #[doc(hidden)]
434    fn inverted_zip2<B, Lhs, U, F>(self, lhs: Lhs, mut f: F) -> MappedSequence<Lhs, B, U>
435    where
436        Lhs: GenericSequence<B, Length = Self::Length> + MappedGenericSequence<B, U>,
437        Self: MappedGenericSequence<T, U>,
438        Self::Length: ArrayLength<B> + ArrayLength<U>,
439        F: FnMut(Lhs::Item, Self::Item) -> U,
440    {
441        unsafe {
442            let mut right = ArrayConsumer::new(self);
443
444            let (right_array_iter, right_position) = right.iter_position();
445
446            FromIterator::from_iter(
447                lhs.into_iter()
448                    .zip(right_array_iter)
449                    .map(|(left_value, r)| {
450                        let right_value = ptr::read(r);
451
452                        *right_position += 1;
453
454                        f(left_value, right_value)
455                    }),
456            )
457        }
458    }
459}
460
461unsafe impl<T, U, N> MappedGenericSequence<T, U> for GenericArray<T, N>
462where
463    N: ArrayLength<T> + ArrayLength<U>,
464    GenericArray<U, N>: GenericSequence<U, Length = N>,
465{
466    type Mapped = GenericArray<U, N>;
467}
468
469unsafe impl<T, N> FunctionalSequence<T> for GenericArray<T, N>
470where
471    N: ArrayLength<T>,
472    Self: GenericSequence<T, Item = T, Length = N>,
473{
474    fn map<U, F>(self, mut f: F) -> MappedSequence<Self, T, U>
475    where
476        Self::Length: ArrayLength<U>,
477        Self: MappedGenericSequence<T, U>,
478        F: FnMut(T) -> U,
479    {
480        unsafe {
481            let mut source = ArrayConsumer::new(self);
482
483            let (array_iter, position) = source.iter_position();
484
485            FromIterator::from_iter(array_iter.map(|src| {
486                let value = ptr::read(src);
487
488                *position += 1;
489
490                f(value)
491            }))
492        }
493    }
494
495    #[inline]
496    fn zip<B, Rhs, U, F>(self, rhs: Rhs, f: F) -> MappedSequence<Self, T, U>
497    where
498        Self: MappedGenericSequence<T, U>,
499        Rhs: MappedGenericSequence<B, U, Mapped = MappedSequence<Self, T, U>>,
500        Self::Length: ArrayLength<B> + ArrayLength<U>,
501        Rhs: GenericSequence<B, Length = Self::Length>,
502        F: FnMut(T, Rhs::Item) -> U,
503    {
504        rhs.inverted_zip(self, f)
505    }
506
507    fn fold<U, F>(self, init: U, mut f: F) -> U
508    where
509        F: FnMut(U, T) -> U,
510    {
511        unsafe {
512            let mut source = ArrayConsumer::new(self);
513
514            let (array_iter, position) = source.iter_position();
515
516            array_iter.fold(init, |acc, src| {
517                let value = ptr::read(src);
518
519                *position += 1;
520
521                f(acc, value)
522            })
523        }
524    }
525}
526
527impl<T, N> GenericArray<T, N>
528where
529    N: ArrayLength<T>,
530{
531    /// Extracts a slice containing the entire array.
532    #[inline]
533    pub fn as_slice(&self) -> &[T] {
534        self.deref()
535    }
536
537    /// Extracts a mutable slice containing the entire array.
538    #[inline]
539    pub fn as_mut_slice(&mut self) -> &mut [T] {
540        self.deref_mut()
541    }
542
543    /// Converts slice to a generic array reference with inferred length;
544    ///
545    /// # Panics
546    ///
547    /// Panics if the slice is not equal to the length of the array.
548    #[inline]
549    pub fn from_slice(slice: &[T]) -> &GenericArray<T, N> {
550        slice.into()
551    }
552
553    /// Converts mutable slice to a mutable generic array reference
554    ///
555    /// # Panics
556    ///
557    /// Panics if the slice is not equal to the length of the array.
558    #[inline]
559    pub fn from_mut_slice(slice: &mut [T]) -> &mut GenericArray<T, N> {
560        slice.into()
561    }
562}
563
564impl<'a, T, N: ArrayLength<T>> From<&'a [T]> for &'a GenericArray<T, N> {
565    /// Converts slice to a generic array reference with inferred length;
566    ///
567    /// # Panics
568    ///
569    /// Panics if the slice is not equal to the length of the array.
570    #[inline]
571    fn from(slice: &[T]) -> &GenericArray<T, N> {
572        assert_eq!(slice.len(), N::USIZE);
573
574        unsafe { &*(slice.as_ptr() as *const GenericArray<T, N>) }
575    }
576}
577
578impl<'a, T, N: ArrayLength<T>> From<&'a mut [T]> for &'a mut GenericArray<T, N> {
579    /// Converts mutable slice to a mutable generic array reference
580    ///
581    /// # Panics
582    ///
583    /// Panics if the slice is not equal to the length of the array.
584    #[inline]
585    fn from(slice: &mut [T]) -> &mut GenericArray<T, N> {
586        assert_eq!(slice.len(), N::USIZE);
587
588        unsafe { &mut *(slice.as_mut_ptr() as *mut GenericArray<T, N>) }
589    }
590}
591
592impl<T: Clone, N> GenericArray<T, N>
593where
594    N: ArrayLength<T>,
595{
596    /// Construct a `GenericArray` from a slice by cloning its content
597    ///
598    /// # Panics
599    ///
600    /// Panics if the slice is not equal to the length of the array.
601    #[inline]
602    pub fn clone_from_slice(list: &[T]) -> GenericArray<T, N> {
603        Self::from_exact_iter(list.iter().cloned())
604            .expect("Slice must be the same length as the array")
605    }
606}
607
608impl<T, N> GenericArray<T, N>
609where
610    N: ArrayLength<T>,
611{
612    /// Creates a new `GenericArray` instance from an iterator with a specific size.
613    ///
614    /// Returns `None` if the size is not equal to the number of elements in the `GenericArray`.
615    pub fn from_exact_iter<I>(iter: I) -> Option<Self>
616    where
617        I: IntoIterator<Item = T>,
618    {
619        let mut iter = iter.into_iter();
620
621        unsafe {
622            let mut destination = ArrayBuilder::new();
623
624            {
625                let (destination_iter, position) = destination.iter_position();
626
627                destination_iter.zip(&mut iter).for_each(|(dst, src)| {
628                    ptr::write(dst, src);
629
630                    *position += 1;
631                });
632
633                // The iterator produced fewer than `N` elements.
634                if *position != N::USIZE {
635                    return None;
636                }
637
638                // The iterator produced more than `N` elements.
639                if iter.next().is_some() {
640                    return None;
641                }
642            }
643
644            Some(destination.into_inner())
645        }
646    }
647}
648
649/// A reimplementation of the `transmute` function, avoiding problems
650/// when the compiler can't prove equal sizes.
651#[inline]
652#[doc(hidden)]
653pub unsafe fn transmute<A, B>(a: A) -> B {
654    let a = ManuallyDrop::new(a);
655    ::core::ptr::read(&*a as *const A as *const B)
656}
657
658#[cfg(test)]
659mod test {
660    // Compile with:
661    // cargo rustc --lib --profile test --release --
662    //      -C target-cpu=native -C opt-level=3 --emit asm
663    // and view the assembly to make sure test_assembly generates
664    // SIMD instructions instead of a naive loop.
665
666    #[inline(never)]
667    pub fn black_box<T>(val: T) -> T {
668        use core::{mem, ptr};
669
670        let ret = unsafe { ptr::read_volatile(&val) };
671        mem::forget(val);
672        ret
673    }
674
675    #[test]
676    fn test_assembly() {
677        use crate::functional::*;
678
679        let a = black_box(arr![i32; 1, 3, 5, 7]);
680        let b = black_box(arr![i32; 2, 4, 6, 8]);
681
682        let c = (&a).zip(b, |l, r| l + r);
683
684        let d = a.fold(0, |a, x| a + x);
685
686        assert_eq!(c, arr![i32; 3, 7, 11, 15]);
687
688        assert_eq!(d, 16);
689    }
690}