Rust-Generic array: generic-array – a hack to allow for arrays sized by typenums

Crates.io Build Status

generic-array

This crate implements generic array types for Rust.

Requires minumum Rust version of 1.36.0, or 1.41.0 for From<[T; N]> implementations

Documentation

Usage

The Rust arrays [T; N] are problematic in that they can't be used generically with respect to N, so for example this won't work:

struct Foo<N> {
	data: [i32; N]
}

generic-array defines a new trait ArrayLength<T> and a struct GenericArray<T, N: ArrayLength<T>>, which let the above be implemented as:

struct Foo<N: ArrayLength<i32>> {
	data: GenericArray<i32, N>
}

The ArrayLength<T> trait is implemented by default for unsigned integer types from typenum crate:

use generic_array::typenum::U5;

struct Foo<N: ArrayLength<i32>> {
    data: GenericArray<i32, N>
}

fn main() {
    let foo = Foo::<U5>{data: GenericArray::default()};
}

For example, GenericArray<T, U5> would work almost like [T; 5]:

use generic_array::typenum::U5;

struct Foo<T, N: ArrayLength<T>> {
    data: GenericArray<T, N>
}

fn main() {
    let foo = Foo::<i32, U5>{data: GenericArray::default()};
}

In version 0.1.1 an arr! macro was introduced, allowing for creation of arrays as shown below:

let array = arr![u32; 1, 2, 3];
assert_eq!(array[2], 3);

Comments

  • Please push the git tags corresponding to releases.
    Please push the git tags corresponding to releases.

    Dec 17, 2019

    The newest tag is 0.12.0, but 0.13.2 is the current released version.

    Reply
  • Placement new
    Placement new

    Jan 5, 2020

    Not sure how messy this would turn out, but has anybody experimented with a "GenericArray with borrowed data", where the constructor would inject a pre-allocated &mut [T; N::to_usize()]? Or in other words, exposing the applicable GenericArray methods to "views" of array slices.

    Reply
  • Generic primitive type parameter with std::marker::Sized bound
    Generic primitive type parameter with std::marker::Sized bound

    May 9, 2020

    Hi, I am trying to implement something that looks like this for some tuple struct Array :

    impl<T: std::marker::Sized> Array<T, U3> {
        pub fn new(x: T, y: T, z: T) -> Array<T, U3> {
            let data: GenericArray<T, U3> = arr![T; x, y, z];
            Array { data }
        }
    }
    

    Unfortunately this seems to be impossible for now and the compilers complains that arr![T; x, y, z] has no fixed size at compile-time. It even points me to the impl<T: std::marker::Sized> telling me the parameter nneds to be std::marker::Sized even if it is already bounded. I suppose there must be a way in the macro to add this condition on T without loss of generality but I'm not familiar with procedural macros myself. Any tip here?

    Cheers, Philippe

    Reply
  • Release 1.0?
    Release 1.0?

    Jun 3, 2020

    This crate has become a pretty foundational part of a few Rust ecosystems:

    • Embedded (via heapless and other fixed-sized containers)
    • RustCrypto (where we just completed a generic-array v0.14 upgrade)

    Unfortunately, if you now use both heapless and RustCrypto in conjunction (via RustCrypto's aead::heapless for example) it pulls in generic-array v0.12, v0.13, and v0.14! (this is due to the as-slice crate, which pulls in both v0.12 and v0.13 for whatever reason)

    In addition to eliminating confusion around coordinating generic-array upgrades, a 1.0 release of generic-array is one of the main blockers for a 1.0 release of many of the RustCrypto crates, so it'd be fantastic if that were to happen.

    Any thoughts on a 1.0 release?

    Reply
  • Add From<&[T;N]> and From<&mut [T; N]> impls for &[mut] GenericArray
    Add From<&[T;N]> and From<&mut [T; N]> impls for &[mut] GenericArray

    Jun 11, 2020

    Adds the following impls to GenericArray:

    • impl From<&'a [T; N]> for &'a GenericArray<T, N>
    • impl From<&'a mut [T; N]> for &'a mut GenericArray<T, N>

    So far users had to convert their &'a [mut] [T; N] array references into slices to perform the conversion into the GenericArray reference. This also resulted into an additional unnecessary assertion since the length are known anyways.

    This PR adds the missing From implementations to drop the unnecessary assertion in those cases and to allow direct conversions between array references and generic array references.

    Reply
  • Fix unsoundness in `from_exact_iter`
    Fix unsoundness in `from_exact_iter`

    Jun 16, 2020

    While trying to figure out how to remove the Default bound from the Deserialize impl I found some unsoundness in from_exact_iter. Unfortunately ExactSizeIterator is not an unsafe trait, so you can't rely on it returning correct results for soundness.

    Alternatively, what do you think about removing the ExactSizeIterator bound and just returning None when either of these assertions would trigger? That is not a breaking change and would allow various other use cases like creating GenericArrays from std::iter::from_fn iterators combined with take and similar.

    Reply
  • Implement Into trait
    Implement Into trait

    Jun 24, 2019

    It would be nice to have the following traits:

    impl<T> Into<[T; 1]> for GenericArray<T, U1> { .. }
    impl<T> Into<[T; 2]> for GenericArray<T, U2> { .. }
    // up to 32, for 48 and 64
    

    One use-case is to easily convert hashes in RustCrypto crates from GenericArray to arrays. And it would be great if you'll publish a backport for v0.12, which is currently used by RustCrypto crates.

    Reply
  • mem::uninitialized is nearly always UB, switch to MaybeUninitialized or something else
    mem::uninitialized is nearly always UB, switch to MaybeUninitialized or something else

    Jan 23, 2020

    mem::uninitialized is deprecated because it's basically impossible to use correctly:

    From mem::uninitialized's docs:

    The reason for deprecation is that the function basically cannot be used correctly: the Rust compiler assumes that values are properly initialized. As a consequence, calling e.g. mem::uninitialized::<bool>() causes immediate undefined behavior for returning a bool that is not definitely either true or false. Worse, truly uninitialized memory like what gets returned here is special in that the compiler knows that it does not have a fixed value. This makes it undefined behavior to have uninitialized data in a variable even if that variable has an integer type. (Notice that the rules around uninitialized integers are not finalized yet, but until they are, it is advisable to avoid them.)

    Reply
  • Default doesn't work
    Default doesn't work

    Mar 30, 2017

    If I try to build:

    GenericArray::<u8, U1>::default();
    

    with rustc 1.17.0-nightly (3da40237e 2017-03-24) I get error:

    error: no associated item named `default` found for type `generic_array::GenericArray<u8, typenum::UInt<typenum::UTerm, typenum::B1>>` in the current scope
    
    Reply
  • Functional system redesign
    Functional system redesign

    Mar 5, 2018

    This explanation is going to be a bit wild.

    Basically, my entire motivation for this and the previous work with zip, map and so forth was to organize safe operations in a way conducive to compiler optimizations, specifically auto-vectorization.

    Unfortunately, this only seems to work on slices with a known size at compile-time. I guess because they are an intrinsic type. Any and all attempts to get a custom iterator to optimize like that has failed, even with unstable features.

    Even though they technically worked, I wasn't happy with how the previous work did functional operations, with map/map_ref and zip/zip_ref. It felt a bit unintuitive. They were also strictly attached to the GenericArray type, so they were useless with GenericSequence by itself, like with generics.

    So, I've redefined GenericSequence like this:

    pub unsafe trait GenericSequence<T>: Sized + IntoIterator {
        type Length: ArrayLength<T>;
        type Sequence: GenericSequence<T, Length=Self::Length> + FromIterator<T>;
    
        fn generate<F>(f: F) -> Self::Sequence
            where F: Fn(usize) -> T;
    }
    

    where Sequence is defined as Self for the GenericArray implementation.

    That may seem redundant, but now GenericSequence is broadly implemented for &'a S and &'a mut S, and carries over the same Sequence.

    So:

    <&'a S as GenericSequence<T>>::Sequence == <S as GenericSequence<T>>::Sequence
    

    Furthermore, IntoIterator is now implemented for &'a GenericArray<T, N> and &'a mut GenericArray<T, N>, where both of those implementations use slice iterators, and each reference type automatically implements GenericSequence<T>

    Next, I've added a new trait called MappedGenericSequence, which looks like:

    pub unsafe trait MappedGenericSequence<T, U>: GenericSequence<T>
    where
        Self::Length: ArrayLength<U>,
    {
        type Mapped: GenericSequence<U, Length=Self::Length>;
    }
    

    and the implementation of that for GenericArray is just:

    unsafe impl<T, U, N> MappedGenericSequence<T, U> for GenericArray<T, N>
    where
        N: ArrayLength<T> + ArrayLength<U>,
        GenericArray<U, N>: GenericSequence<U, Length=N>,
    {
        type Mapped = GenericArray<U, N>;
    }
    

    As you can see, it just defines another arbitrary GenericArray with the same length. The transformation allows for proving one GenericArray can be created from another, which leads into the FunctionalSequence trait.

    You can see the default implementation for it in src/functional.rs, which uses the fact that any GenericSequence is IntoIterator and the associated Sequence is FromIterator to map/zip sequences using only simple iterators.

    FunctionalSequence is also automatically implemented for &'a S and &'a mut S where S: GenericSequence<T>, so they automatically work with &GenericArray as well.

    Furthermore, it's implemented directly on GenericArray as well, which uses the ArrayConsumer system to provide a lightweight and optimizable implementation, rather than relying on GenericArrayIter, which cannot be optimized.

    As a result, code like in the assembly test:

    let a = black_box(arr![i32; 1, 3, 5, 7]);
    let b = black_box(arr![i32; 2, 4, 6, 8]);
    
    let c = a.zip(&b, |l: i32, r: &i32| l + r);
    
    assert_eq!(c, arr![i32; 3, 7, 11, 15]);
    

    will correctly be optimized into a single VPADDD instruction, just as desired.

    ~~The downside of this is that non-reference RHS arguments will kill this optimization, because it will use .into_iter() and GenericArrayIter. There really isn't a good way around this currently.~~ I found a good way around this currently.

    The upside of all of this is that pass any random GenericSequence without knowing the length is finally feasible, as shown in tests/std.rs, and here:

    pub fn test_generic<S>(s: S)
        where
            S: FunctionalSequence<i32>,            // `.map`
            SequenceItem<S>: Add<i32, Output=i32>, // `+`
            S: MappedGenericSequence<i32, i32>,    // `i32` -> `i32`
            MappedSequence<S, i32, i32>: Debug     // println!
    {
        let a = s.map(|x| x + 1);
    
        println!("{:?}", a);
    }
    

    Which still has zero runtime length checking, but we've avoided having to know the length of the sequence. Furthermore, now test_generic can work for GenericArray, &GenericArray and &mut GenericArray with no problems.

    BREAKING CHANGES:

    • The implementation of FromIterator for GenericArray now panics when the given iterator doesn't produce enough elements, wherein before it padded it with defaults.
    • map_ref and zip_ref are gone, replaced with the new functional system.
    • ~~map/zip can fail to optimize unless used with references.~~ Fixed
      • I should note that auto-vectorization only works on numbers anyway, so it's no worse than vec::IntoIter in the worst case.
    • ~~~GenericArray and GenericArrayIter now implement Send/Sync when possible.~~ This was a mistake, fixed in #61

    What do you think? Perhaps I should write up some examples for the docs, too?

    If I failed to explain anything, made a mistake or could improve on anything, please let me know. I just want to make the best things I can.

    Reply
  • new map method
    new map method

    Apr 25, 2016

    This adds mapping functions over GenericArrays Also improves some nits in the doc comments And ensures panic safety of all operations

    Reply
  • Small fixes and improvements before next release
    Small fixes and improvements before next release

    Mar 14, 2018

    I removed Send/Sync implementations on GenericArrayIter, because it was a mistake to add them. Rust will automatically implement Send where possible, and GenericArrayIter shouldn't be Sync because the indices are not atomic variables.

    I've improved the generics tests to include most of the common use scenarios, and noted in functional.rs that tests/generics.rs has those as examples.

    Finally, while writing the previous tests/examples, I noticed I did actually find the SequenceItem accessor alias type useful in keeping the generic conditions cleaner, so I added that back in.

    Reply