ArrayVec<A> is invariant in A

[mbrubeck]

struct ArrayVec<A> contains a field of type A::Index. This makes it invariant over A, for reasons described in rust-lang/rust#21726 (comment) and rustc_typeck::variance.

It would be nice for ArrayVec<A> to be covariant over A, so that for example an ArrayVec<[&'long T; N]> could be used where an ArrayVec<[&'short T; N]> is expected, if 'long: 'short. This would make it act more like [T] and Vec<T> and other standard library containers.

Fixing this might require getting rid of Array::Index as an associated type, and finding some other way to specify it.

[bluss]

arrayvec 2.0, which “will” be implemented with const generics, might have to use usize for the index? I don't know.

[bluss]

Too speculative and not actionable at this point. It's an interesting note, but it's not the main challenge we have in arrayvec (that's the “const generics” part).

[clarfonthey]

FWIW the problem of using usize alongside const generics could be solved by this incredibly hacky solution below:

struct Index<const N: usize> {
    inner: [u8; index_size!(N)],
}

// can't do `const fn` here because it's unstable
macro_rules! index_size {
    ($n: expr) => {
        match $n {
            0 => 0,
            1..=0xFF => 1,
            0x100..=0xFFFF => 2,
            #[cfg(not(target_pointer_width = "16"))]
            0x10000..=0xFFFFFFFF => 4,
            _ => size_of::<usize>(),
        }
    }
}

impl<const N: usize> From<Index<N>> {
    fn from(index: Index<N>) -> usize {
        match index_size!(N) {
            0 => 0,
            1 => transmute::<_, u8>(index.inner) as usize,
            2 => transmute::<_, u16>(index.inner) as usize,
            3 => transmute::<_, u32>(index.inner) as usize,
            _ => transmute::<_, usize>(index.inner),
    }
}

Note that this would get rid of a potential [T; 1]::Index = bool optimisation, but it's not a super big deal. The point is that it would be possible. I'm also assuming that match will be allowed in constants before const generics are implemented, which is a pretty reasonable assumption.

The only real issue is getting the alignment of Index<N> to work correctly, but I have a feeling this would be doable.