The deduped versions of the `*View` types break variance:

[sosthene-nitrokey]

The following compiles with v0.8.0 and https://github.com/rust-embedded/heapless/pull/425, but not with latest main:

fn test_variance<'a: 'b, 'b>(x: Vec<&'a (), 42>) -> Vec<&'b (), 42> {
    x
}

@Dirbaio

I think this is caused the intermediary Generic Associated Type, but I could not find where this is documented.

[sosthene-nitrokey]

I just tested, it's not related to GAT, even with a modified Storage trait to not use GAT, it does not compile:

pub(crate) trait SealedStorage<T> {
    type Buffer: ?Sized + Borrow<[T]> + BorrowMut<[T]>;
}

[Dirbaio]

:scream:

[Dirbaio]

see discussion in https://rust-lang.zulipchat.com/#narrow/stream/144729-t-types/topic/variance.20of.20GATs.20when.20the.20type.20is.20known

I think this is fundamentally unfixable :sob:

[sosthene-nitrokey]

What do you think about this approach:

mod storage {
    use std::mem::MaybeUninit;

    pub trait VecStorage<T>: VecSealedStorage<T> {}

    pub trait VecSealedStorage<T> {
        // part of the sealed trait so that no trait is publicly implemented by `OwnedVecStorage` besides `Storage`
        fn borrow(&self) -> &[MaybeUninit<T>];
        fn borrow_mut(&mut self) -> &mut [MaybeUninit<T>];
    }

    // One sealed layer of indirection to hide the internal details (The MaybeUninit).
    pub struct VecStorageInner<T: ?Sized> {
        buffer: T,
    }

    // These are the public types
    pub type OwnedVecStorage<T, const N: usize> = VecStorageInner<[MaybeUninit<T>; N]>;
    pub type ViewVecStorage<T> = VecStorageInner<[MaybeUninit<T>]>;

    impl<T, const N: usize> VecSealedStorage<T> for OwnedVecStorage<T, N> {
        fn borrow(&self) -> &[MaybeUninit<T>] {
            &self.buffer
        }
        fn borrow_mut(&mut self) -> &mut [MaybeUninit<T>] {
            &mut self.buffer
        }
    }
    impl<T, const N: usize> VecStorage<T> for OwnedVecStorage<T, N> {}

    impl<T> VecSealedStorage<T> for ViewVecStorage<T> {
        fn borrow(&self) -> &[MaybeUninit<T>] {
            &self.buffer
        }
        fn borrow_mut(&mut self) -> &mut [MaybeUninit<T>] {
            &mut self.buffer
        }
    }
    impl<T> VecStorage<T> for ViewVecStorage<T> {}
}

use std::marker::PhantomData;

pub use storage::{OwnedVecStorage, VecStorage, ViewVecStorage};

pub struct VecInner<T, S: VecStorage<T> + ?Sized> {
    // This phantomdata is required because otherwise rustc thinks that `T` is not used
    phantom: PhantomData<T>,
    len: usize,
    buffer: S,
}

pub type Vec<T, const N: usize> = VecInner<T, OwnedVecStorage<T, N>>;
pub type VecView<T> = VecInner<T, ViewVecStorage<T>>;

fn test_variance<'a: 'b, 'b>(x: Vec<&'a (), 42>) -> Vec<&'b (), 42> {
    x
}

fn test_variance_view<'a: 'b, 'b, 'c>(x: &'c VecView<&'a ()>) -> &'c VecView<&'b ()> {
    x
}

It keeps the variance, and it allows us to keep the internal details of Vec private, while still allowing downstreams to use the generic VecInner (which I found to be really useful to wrap Vec in heapless-bytes), so even though I didn't see it a useful feature initially, it turns out to be worth keeping.

The only downside over the current approach is that we need a separate mechanism for each container. I don't think that can be worked around.

[sosthene-nitrokey]

Overall I also want to say I don't think the View types are worth breaking Covariance even with a major semver bump. Variance issues are so hard to wrap your head around and can be pretty hard to understand/work around.

Honestly here I don't really understand why the variance is broken when using the current approach, even after reading the zulip thread.

[Dirbaio]

What do you think about this approach:

oh yes! that could work. It's unfortunate that it requires duplicating the Storage structs/traits for each container. Perhaps with a macro to generate them it wouldn't be that bad?

An alternative would be pub struct VecInner<T, S: Storage<MaybeUninit<T>> + ?Sized> but then we're leaking in the public API the fact that we're using a MaybeUninit or a Cell or whatever. Not worth it.

use the generic VecInner (which I found to be really useful to wrap Vec in heapless-bytes), so even though I didn't see it a useful feature initially, it turns out to be worth keeping.

that's awesome to hear :star_struck:

Overall I also want to say I don't think the View types are worth breaking Covariance even with a major semver bump. Variance issues are so hard to wrap your head around and can be pretty hard to understand/work around.

Yes, I agree, unfortunately :smiling_face_with_tear:

Honestly here I don't really understand why the variance is broken when using the current approach, even after reading the zulip thread.

rustc calculates variance for the struct "eagerly", by looking just at the raw struct definition, before substituting any generic params. It takes just

pub struct VecInner<T, S: Storage> {
    len: usize,
    buffer: S::Buffer<MaybeUninit<T>>,
}

then it deduces that

• VecInner<T, S> is invariant wrt S, because changing S can change the type of the buffer field in arbitrary ways.
• VecInner<T, S> is invariant wrt T, because S::Buffer could be anything. One trait impl could have type Buffer<T> = fn() -> T (covariant), another could have type Buffer<T> = fn(T) -> () (contravariant), so it's forced to assume it's invariant, which is the most conservative option.

then it just uses these deductions everywhere. It doesn't take into account substitutions.

[sosthene-nitrokey]

Yes, I understand why VecInner<T, S> is not covariant in T. But I thought the type alias would be strictly equivalent to the struct it resolves to, but it appears it's not the case.

This is the kind of thing that feels like an arbitrary limitation of the compiler rather than something that makes sense in the language itself. Though I understand I wouldn't want to be the one having to implement this in the compiler or even review a PR that does it...

[Dirbaio]

the compiler does treat Vec<T, N> and VecInner<T, OwnedStorage<N>> the same, they're both invariant on T. The limitation is it won't apply substitutions before computing variance, independently of whether you use a typealias or not.

[sosthene-nitrokey]

I meant treating the type alias Vec the same as the v0.8 version of Vec, because it contains the same fields.