Generic array types in Rust

Related tags

Data structures rust
Overview

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
  • Small fixes and improvements before next release

    Small fixes and improvements before next release

    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.

    opened by novacrazy 15
  • Functional system redesign

    Functional system redesign

    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.

    opened by novacrazy 12
  • mem::uninitialized is nearly always UB, switch to MaybeUninitialized or something else

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

    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.)

    opened by programmerjake 9
  • Default doesn't work

    Default doesn't work

    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
    
    opened by WaDelma 9
  • Implement Into trait

    Implement Into trait

    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.

    opened by newpavlov 8
  • Fix unsoundness in `from_exact_iter`

    Fix unsoundness in `from_exact_iter`

    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.

    opened by oli-cosmian 6
  • `arr!` unsoundness

    `arr!` unsoundness

    The arr! macro silently and unsoundly extends arbitrary lifetimes to 'static (playground):

    fn unsound_lifetime_extension<'a, A>(a: &'a A) -> &'static A {
      arr![&A; a][0]
    }
    
    opened by jswrenn 6
  • UB in Default impl of GenericArray

    UB in Default impl of GenericArray

    Today I was running cargo miri test on one of my projects that is using the generic-array crate internally. The cargo miri test runs tests of the project using the Rust MIR interpreter miri. Due to execution the tool is sometimes able to detect undefined behaviour in Rust code upon execution - however, there might be false positives.

    The output of miri's execution:

    error: Undefined Behavior: type validation failed: encountered uninitialized bytes at .value.data.parent1.parent1.data, but expected a valid enum discriminant
       --> /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/maybe_uninit.rs:502:34
        |
    502 |         ManuallyDrop::into_inner(self.value)
        |                                  ^^^^^^^^^^ type validation failed: encountered uninitialized bytes at .value.data.parent1.parent1.data, but expected a valid enum discriminant
        |
        = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
        = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
        = note: inside `std::mem::MaybeUninit::<generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>>::assume_init` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/maybe_uninit.rs:502:34
        = note: inside `std::mem::uninitialized::<generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/mod.rs:664:5
        = note: inside `generic_array::ArrayBuilder::<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at /home/.cargo/registry/src/github.com-1ecc6299db9ec823/generic-array-0.13.2/src/lib.rs:187:38
        = note: inside `<generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>> as generic_array::sequence::GenericSequence<std::option::Option<storage2::lazy::entry::Entry<u8>>>>::generate::<[closure@DefId(32:51 ~ generic_array[53b7]::impls[0]::{{impl}}[0]::default[0]::{{closure}}[0])]>` at /home/.cargo/registry/src/github.com-1ecc6299db9ec823/generic-array-0.13.2/src/lib.rs:344:35
        = note: inside `generic_array::impls::<impl std::default::Default for generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>>::default` at /home/.cargo/registry/src/github.com-1ecc6299db9ec823/generic-array-0.13.2/src/impls.rs:17:9
    note: inside `storage2::lazy::lazy_array::EntryArray::<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at core/src/storage2/lazy/lazy_array.rs:109:22
       --> core/src/storage2/lazy/lazy_array.rs:109:22
        |
    109 |             entries: Default::default(),
        |                      ^^^^^^^^^^^^^^^^^^
    note: inside `<storage2::lazy::lazy_array::EntryArray<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>> as std::default::Default>::default` at core/src/storage2/lazy/lazy_array.rs:119:9
       --> core/src/storage2/lazy/lazy_array.rs:119:9
        |
    119 |         Self::new()
        |         ^^^^^^^^^^^
    note: inside `storage2::lazy::lazy_array::LazyArray::<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at core/src/storage2/lazy/lazy_array.rs:182:45
       --> core/src/storage2/lazy/lazy_array.rs:182:45
        |
    182 |             cached_entries: UnsafeCell::new(Default::default()),
        |                                             ^^^^^^^^^^^^^^^^^^
    note: inside `<storage2::lazy::lazy_array::LazyArray<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>> as std::default::Default>::default` at core/src/storage2/lazy/lazy_array.rs:165:9
       --> core/src/storage2/lazy/lazy_array.rs:165:9
        |
    165 |         Self::new()
        |         ^^^^^^^^^^^
    note: inside `storage2::collections::smallvec::SmallVec::<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at core/src/storage2/collections/smallvec/mod.rs:79:20
       --> core/src/storage2/collections/smallvec/mod.rs:79:20
        |
    79  |             elems: Default::default(),
        |                    ^^^^^^^^^^^^^^^^^^
    note: inside `storage2::collections::smallvec::tests::first_last_of_empty` at core/src/storage2/collections/smallvec/tests.rs:61:19
       --> core/src/storage2/collections/smallvec/tests.rs:61:19
        |
    61  |     let mut vec = <SmallVec<u8, U4>>::new();
        |                   ^^^^^^^^^^^^^^^^^^^^^^^^^
    note: inside closure at core/src/storage2/collections/smallvec/tests.rs:60:1
       --> core/src/storage2/collections/smallvec/tests.rs:60:1
        |
    60  | / fn first_last_of_empty() {
    61  | |     let mut vec = <SmallVec<u8, U4>>::new();
    62  | |     assert_eq!(vec.first(), None);
    63  | |     assert_eq!(vec.first_mut(), None);
    64  | |     assert_eq!(vec.last(), None);
    65  | |     assert_eq!(vec.last_mut(), None);
    66  | | }
        | |_^
        = note: inside `<[closure@core/src/storage2/collections/smallvec/tests.rs:60:1: 66:2] as std::ops::FnOnce<()>>::call_once - shim` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ops/function.rs:232:5
        = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ops/function.rs:232:5
        = note: inside `test::__rust_begin_short_backtrace::<fn()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:517:5
        = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:508:30
        = note: inside `<[closure@DefId(38:631 ~ test[140d]::run_test[0]::{{closure}}[2]) 0:fn()] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ops/function.rs:232:5
        = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/boxed.rs:1008:9
        = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:318:9
        = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:331:40
        = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:274:15
        = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:14
        = note: inside `test::run_test_in_process` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:541:18
        = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:450:39
        = note: inside `test::run_test::run_test_inner` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:475:13
        = note: inside `test::run_test` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:505:28
        = note: inside `test::run_tests::<[closure@DefId(38:230 ~ test[140d]::console[0]::run_tests_console[0]::{{closure}}[2]) 0:&mut test::console::ConsoleTestState, 1:&mut std::boxed::Box<dyn test::formatters::OutputFormatter>]>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:284:13
        = note: inside `test::run_tests_console` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/console.rs:280:5
        = note: inside `test::test_main` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:120:15
        = note: inside `test::test_main_static` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:139:5
        = note: inside `main`
        = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:34
        = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:73
        = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<[closure@DefId(1:6025 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/sys_common/backtrace.rs:130:5
        = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:13
        = note: inside `std::panicking::r#try::do_call::<[closure@DefId(1:6024 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:331:40
        = note: inside `std::panicking::r#try::<i32, [closure@DefId(1:6024 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:274:15
        = note: inside `std::panic::catch_unwind::<[closure@DefId(1:6024 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:14
        = note: inside `std::rt::lang_start_internal` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:51:25
        = note: inside `std::rt::lang_start::<()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:5
        = note: this error originates in an attribute macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error: aborting due to previous error
    

    So it seems to be a problem with uninitialized data in the Default implementation of GenericArray where it is using a ManuallyDrop with uninitialized data.

    This is the test code that triggered the UB of my crate that is using generic-array: https://github.com/paritytech/ink/blob/redo-init-and-flush/core/src/storage2/collections/smallvec/tests.rs#L60

    I belive the problem is somewhere in this method: https://github.com/fizyk20/generic-array/blob/master/src/lib.rs#L207 The array field is of type MaybeUninit and during the loop in fn generate (same file) the underlying array is initialized. However, in the linked method no call to assume_init is made and instead a core::mem::ptr::read is performed on the potentially uninitialized array contents. This doesn't necessarily need to be wrong, however, it could be that it confuses miri.

    opened by Robbepop 6
  • Add `GenericSequence`, `Lengthen`, `Shorten`, `Split` and `Concat` traits.

    Add `GenericSequence`, `Lengthen`, `Shorten`, `Split` and `Concat` traits.

    Here are some more useful features that allow for easier passing of GenericArray via generics, as well as some simple resize methods implemented as inverse traits. I've had to use these a few times already.

    These really should have been in that last pull request, but I wasn't far enough along in a dependent project to really test it.

    opened by novacrazy 6
  • Make Array Consumer/Builder structures public, but hidden, for use in other crates

    Make Array Consumer/Builder structures public, but hidden, for use in other crates

    I thought it was silly that I had to re-implement ArrayBuilder and ArrayConsumer for numeric-array, so I think we should just expose those quietly.

    I went ahead and implemented a simple "API" for the private stuff and added some doc comments for anyone that wants to snoop around the source code to use them. I also converted our existing code to use the API, because why not.

    This isn't a breaking change, though, so a quick minor revision is good enough. Everything still works the exact same and should produce nearly identical machine code.

    opened by novacrazy 5
  • Obtaining &[T; N] for GenericArray<T, N>

    Obtaining &[T; N] for GenericArray

    Apologies if there's already a way to do this, but I can't figure it out.

    I'd like to pass a generic array as a sized array reference. I'm able to do this using e.g. the arrayref crate but I'd like to avoid that if possible (among other things by virtue of using a macro that expands to unsafe code I'm unable to deny(unsafe_code).

    opened by tarcieri 5
  • support try_form?

    support try_form?

    GenericArray::from_slice(&[u8) will panic if slice length is not match. It would be great to provide a Result version, e.g. (GenericArray::try_from_slice(&[u8) -> Result<Self, LengthNotMatch>)

    opened by bigdogs 3
  • Add try_from_slice() and try_from_mut_slice()

    Add try_from_slice() and try_from_mut_slice()

    Add two new methods for creating a GenericArray reference from a slice in situations where the caller doesn't know the length of the incoming slice. In such a situation, these methods are safer than from_slice() and from_mut_slice() because they don't panic.

    opened by peterkelly 0
  • Project future post-1.51.0 and min_const_generics, possible deprecation?

    Project future post-1.51.0 and min_const_generics, possible deprecation?

    Now that min_const_generics has been stabilized in Rust 1.51.0, should we begin deprecating this crate? We can use the existing build.rs script to check the version number and only generate the deprecation on post-1.51.0 versions.

    However, an alternative would be to port much of this crate's functionality to a new (simpler) array wrapper type that fully utilizes const generics, to work alongside and ease replacement of existing code.

    Please feel free to submit your thoughts on the matter.

    opened by novacrazy 3
  • Broken links in doc.rs documentation

    Broken links in doc.rs documentation

    There are a few broken links in the documentation located at https://docs.rs/generic-array/0.14.4/generic_array/index.html. Namely, both unsigned integer types and typenum links are dead. The version build directly from the GitHub repo (located at https://fizyk20.github.io/generic-array/generic_array/) works though.

    opened by louib 0
  • Instantiating the array via default seems to have a very large stack footprint

    Instantiating the array via default seems to have a very large stack footprint

    May be misunderstanding something here, but it looks like the instantiation process has an unnecessarily heavy stack footprint. I expect to have a few MB of stack space available, but can't instantiate an array of size larger than ~200kB.

    #[cfg(test)]
    mod test {
        #[test]
        fn it_defaults() {
            // 208896
            dbg!(std::mem::size_of::<GenericArray<[u64; 32], U816>>());
            // 209152
            dbg!(std::mem::size_of::<GenericArray<[u64; 32], U817>>());
            
            // Works
            GenericArray::<[u64; 32], U816>::default();
            
            // Stack Overflow
            GenericArray::<[u64; 32], U817>::default();
        }
    }
    
    opened by prestwich 5
Releases(0.12.0)
Owner
Bartłomiej Kamiński
Physics graduate, programming at work and as a hobby
Bartłomiej Kamiński
Serialize/DeSerialize for Rust built-in types and user defined types (complex struct types)

Serialize/DeSerialize for Rust built-in types and user defined types (complex struct types)

null 2 May 3, 2022
Array helpers for Rust's Vector and String types

array_tool Array helpers for Rust. Some of the most common methods you would use on Arrays made available on Vectors. Polymorphic implementations for

Daniel P. Clark 69 Dec 9, 2022
enum-map enum-map xfix/enum-map [enum-map] — An optimized map implementation for enums using an array to store values.

enum-map A library providing enum map providing type safe enum array. It is implemented using regular Rust arrays, so using them is as fast as using r

Konrad Borowski 57 Dec 19, 2022
A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings

RadixTrie A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings. It is a root tree, each edge

null 2 Jan 28, 2022
Parameterized routing for generic resources in Rust

Usher Usher provides an easy way to construct parameterized routing trees in Rust. The nodes of these trees is naturally generic, allowing Usher to le

Isaac Whitfield 34 Oct 22, 2022
Rust crate to extend io::Read & io::Write types with progress callbacks

progress-streams Rust crate to provide progress callbacks for types which implement io::Read or io::Write. Examples Reader extern crate progress_strea

Pop!_OS 19 Dec 3, 2022
Rust-algorithm-club - Learn algorithms and data structures with Rust

Rust Algorithm Club ?? ?? This repo is under construction. Most materials are written in Chinese. Check it out here if you are able to read Chinese. W

Weihang Lo 360 Dec 28, 2022
Ternary search tree collection in rust

tst Ternary search tree collection in rust with similar API to std::collections as it possible. Ternary search tree is a type of trie (sometimes calle

Alexey Pervushin 20 Dec 7, 2022
A priority queue for Rust with efficient change function.

PriorityQueue This crate implements a Priority Queue with a function to change the priority of an object. Priority and items are stored in an IndexMap

null 139 Dec 30, 2022
K-dimensional tree in Rust for fast geospatial indexing and lookup

kdtree K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup Crate Documentation Usage Benchmark License Usage Add kdtr

Rui Hu 152 Jan 2, 2023
Roaring bitmap implementation for Rust

RoaringBitmap This is not yet production ready. The API should be mostly complete now. This is a Rust port of the Roaring bitmap data structure, initi

Roaring bitmaps: A better compressed bitset 552 Jan 1, 2023
Rust Persistent Data Structures

Rust Persistent Data Structures Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Setup To use rpds a

Diogo Sousa 883 Dec 31, 2022
RiteLinked - LinkedHashMap & LinkedHashSet in Rust

RiteLinked -- HashMap-like containers that hold their key-value pairs in a user controllable order RiteLinked provides more up to date versions of Lin

Rite Database 52 Aug 19, 2022
A proof of concept implementation of cyclic data structures in stable, safe, Rust.

A proof of concept implementation of cyclic data structures in stable, safe, Rust. This demonstrates the combined power of the static-rc crate and the

null 157 Dec 28, 2022
Doubly-Linked List Implementation in Rust

Doubly-Linked List Implementation in Rust Purely for educational and recreational purposes. For real world production please use std::collections::Lin

Tsoding 9 Jul 28, 2022
Rust library for string parsing of basic data structures.

afmt Simple rust library for parsing basic data structures from strings. Usage You can specify string formats to any strucute, via the use of the fmt

Eduard 4 May 8, 2021
Hash Table Implementation in Rust

Hash Table Implementation in Rust Purely for educational and recreational purposes. For real world production please use std::collections::HashMap. Fo

Tsoding 11 Sep 6, 2022
SegVec data structure for rust. Similar to Vec, but allocates memory in chunks of increasing size.

segvec This crate provides the SegVec data structure. It is similar to Vec, but allocates memory in chunks of increasing size, referred to as "segment

Jacob Ryan McCollum 30 Dec 16, 2022
Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

null 6.5k Dec 31, 2022