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