Support for constant generics

[c410-f3r]

Constant generics is becoming more mature and soon will be in an usable state for complex projects.

[bluss]

Yes! Const generics is "on the roadmap" as the item for ArrayVec 2.0. See #48

[c410-f3r]

Hi @bluss Glad to know your presence.

I opened a PR that adds support for constant generics in rust-smallvec, can I do same with arrayvec? It is basically a macro controlled by a feature that generates the necessary stuff like in this file.

[bluss]

@c410-f3r Sure. Unfortunately I will probably not be able to look at it before September. Maybe it's best to at least allow the 0.5/master changes to rip out nodrop and go all in on MaybeUninit, land first, too.

[c410-f3r]

@bluss

The best approach I could think of, to avoid code duplication and keep compatibility with the legacy Array trait, was the use of a declarative macro to expand code according to a const-generics feature. E.g.:

#![cfg_attr(feature = "const-generics", feature(const_generics))]

use core::mem::MaybeUninit;

macro_rules! create_with_parts {
(
    <$($({$s_impl_ty_prefix:ident})? $s_impl_ty:ident$(: $s_impl_ty_bound:ident)?),*>,
    <$s_decl_ty:ident$(, {$s_decl_const_ty:ident})?>,
    $array:ty
) => {

pub struct ArrayVec<$($($s_impl_ty_prefix)? $s_impl_ty$(: $s_impl_ty_bound)?),*>
{
    xs: MaybeUninit<$array>,
    len: usize
}

impl<$($($s_impl_ty_prefix)? $s_impl_ty$(: $s_impl_ty_bound)?),*>
    ArrayVec<$s_decl_ty$(, {$s_decl_const_ty})?>
{
}

    }
}

#[cfg(feature = "const-generics")]
create_with_parts!(<T, {const} N: usize>, <T, {N}>, [T; N]);
#[cfg(not(feature = "const-generics"))]
create_with_parts!(<A: Array>, <A>, A);

Resolves into:

pub struct ArrayVec<A: Array>
{
    xs: MaybeUninit<A>,
    len: usize
}

impl<A: Array> ArrayVec<A> {}

or

pub struct ArrayVec<T, const N: usize>
{
    xs: MaybeUninit<[T; N]>,
    len: usize
}

impl<T, const N: usize> ArrayVec<T, {N}> {}

It is a bit verbose but it works. Could there be any other way?

However, as you may have noticed, arrayvec uses the Index trait to define the len type that is currently attached to the Array trait as an associated parameter and this architecture don't play well with the above declarative macro. To make everything work properly, the Index bound should be removed from Array to be incorporated directly into the ArrayVec struct. E.g.:

#![feature(const_generics)]

use core::mem::MaybeUninit;

macro_rules! create_with_parts {
(
    <$($({$s_impl_ty_prefix:ident})? $s_impl_ty:ident$(: $s_impl_ty_bound:ident)?),*>,
    <$s_decl_ty:ident$(, {$s_decl_const_ty:ident})?>,
    $array:ty
) => {

pub struct ArrayVec<I: Index, $($($s_impl_ty_prefix)? $s_impl_ty$(: $s_impl_ty_bound)?),*>
{
    xs: MaybeUninit<$array>,
    len: I
}

impl<I: Index, $($($s_impl_ty_prefix)? $s_impl_ty$(: $s_impl_ty_bound)?),*>
    ArrayVec<I, $s_decl_ty$(, {$s_decl_const_ty})?>
{
}

    }
}

#[cfg(feature = "const-generics")]
create_with_parts!(<T, {const} N: usize>, <T, {N}>, [T; N]);
#[cfg(not(feature = "const-generics"))]
create_with_parts!(<A: Array>, <A>, A);

Resolves into:

pub struct ArrayVec<I: Index, A: Array>
{
    xs: MaybeUninit<A>,
    len: I
}

impl<I: Index, A: Array> ArrayVec<I, A> {}

or

pub struct ArrayVec<I: Index, T, const N: usize>
{
    xs: MaybeUninit<[T; N]>,
    len: I
}

impl<I: Index, T, const N: usize> ArrayVec<I, T, {N}> {}

Please, let me know what you think about this whole process.

[bluss]

I don't have a plan for how to handle const generics before it's stable. Looks like you have a cool plan there, that could work, but it doesn't seem appropriate for a crate feature - the whole API changes when the feature is enabled. It looks more like it has to be a fork or a separate version.

On the topic of indices, that is an expected loss. I'd say we don't want an index parameter. Either the index type should depend on N (if possible), or it simply will have to be a "hardcoded" index type. (Maybe have several if we can type alias the Main variants?)

[c410-f3r]

I see. Stabilization of const_generics shouldn't take too long once lazy normalization lands

[bluss]

What I said of making the whole API change might be premature - there could be ways with type aliases and other ways to completely mask the const generics?

With that said, once we go all out on stable const generics, we don't need the old Array trait, of course, and we should remove it and forget it -- make the best API we can with const generics.

[c410-f3r]

Well, it is possible to implement Array for [T; N]. E.g.:

unsafe trait Array {
    type Item;
    type Index;
    const CAPACITY: usize;
    
    fn as_slice(&self) -> &[Self::Item];
    fn as_mut_slice(&mut self) -> &mut [Self::Item];
}


#[cfg(feature = "const-generics")]
unsafe impl<T, const N: usize> Array for [T; N] {
    const CAPACITY: usize = N;
    type Item = T;
    type Index = usize; // Hardcoded
    
    fn as_slice(&self) -> &[Self::Item] {
        self
    }
    
    fn as_mut_slice(&mut self) -> &mut [Self::Item] {
        self
    }
}

#[cfg(not(feature = "const-generics"))]
// Legacy implementation

The problem with this approach is that #96 will still remain (maybe remove Item from Array?) and it will not be possible to define a reasonable type Index for a given N (Index probably won't be relevant with constant generics).

[clarfonthey]

Potentially bad idea: why not make Index a [u8; M] where M is an appropriate number given the size and alignment of the rest of the array? Then, that number could be cast to the appropriate actual integer type using from_ne_bytes. Pretty much all of the maths require to make this work will be optimised out by the compiler and it'll be optimal for each usage.

[tbu-]

Sounds good, will work well on x86 at least I guess. For other platforms, there might be alignment issues, e.g. if you have a 256 byte array of bytes, it requires a 16 bit integer as index, but that will potentially not be aligned, leading to more expensive stores/loads.

[clarfonthey]

That's actually a good point; I wonder if there would be an easy way around that besides forcing alignment.

[bluss]

Just to say that it's possible to define a quick Array trait wrapper from outside the crate (using arrayvec from master).

Just in this code, I found ICEs in most of the things I wanted to do, so it doesn't seem to be exactly ready 🙂

#![feature(const_generics)]

use arrayvec::{Array, ArrayVec};

#[repr(transparent)]
struct Data<T, const N: usize>(pub [T; N]);

unsafe impl<T, const N: usize> Array for Data<T, {N}> {
    const CAPACITY: usize = N;
    type Index = usize;
    type Item = T;
    fn as_slice(&self) -> &[Self::Item] { &self.0 }
    fn as_mut_slice(&mut self) -> &mut [Self::Item] { &mut self.0 }
}

/* compiler error / ICE
struct BTreeNode<const B: usize> {
    keys: ArrayVec<Data<i32, {2 * B}>>,
    children: ArrayVec<Data<i32, {2 * B + 1}>>,
}
*/

// ICEs on use
//type CArrayVec<T, const N: usize> = ArrayVec<Data<T, {N}>>;

fn main() {
    //let mut v = CArrayVec::from(Data([0; 47]));

    let mut u = ArrayVec::from(Data([0; 47]));
    let mut i = 0;
    for elt in &mut u {
        *elt = i;
        i += 1;
    }
    println!("{:?}", u);
}

(using rustc 1.39.0-nightly (9b9d2aff8 2019-09-19) )

[Michael-F-Bryan]

I just did a write-up on implementing ArrayVec using const generics and found it can be implemented fairly easily by dropping the Array trait and using an array directly.

pub struct ArrayVec<T, const N: usize> {
    items: [MaybeUninit<T>; N],
    length: usize,
}

Throughout the entire process I didn't hit a single ICE, so maybe it's worth giving another shot?

[bluss]

@Michael-F-Bryan Yes, I think we should, if it makes sense. There might be other crates already filling this need?

[vadixidav]

@bluss I think a better intermediary solution could be to add a const-generics feature that optionally retrofits the existing Array trait to impl for all arrays. I am looking at using this in the hnsw crate right now (currently switching to const generics), but that is a blocker for me, so I am temporarily implementing it with regular arrays and some tricks.

[clarfonthey]

Perhaps the best approach would be to have an unstable 2.0 branch that could be used by folks who want const generics but is kept in an alpha state until those features are merged. A feature isn't the best as the API should change for const generics IMHO.