search

servo / rust-smallvec

"Small vector" optimization for Rust: store up to a small number of items on the stack
Apache License 2.0
1.35k stars 145 forks source link

SmallVec<[T; N]> is invariant over T #146

Open zakarumych opened 5 years ago

zakarumych commented 5 years ago

SmallVec<[T; N]> is invariant over T. Although [T; N] is covariant over T as expected.

This is due to SmallVec<A> having field of type <A as Array>::Item in underlying union. I propose to change that field type to A and remove A: Array bound from type declaration.

mbrubeck commented 5 years ago

For reference, this is similar to bluss/arrayvec#96, and is caused by rust-lang/rust#21726.

Nadrieril commented 4 years ago

The following trick (can't remember where I found it):

enum SmallVec<A: Array<Item=Item>, Item=<A as Array>::Item> {
    Inline(MaybeUninit<A>),
    Heap((NonNull<Item>, usize)),
}

fixes the variance issue (playground link). Would that be possible to use or would it be a breaking change to the API ?

bkolobara commented 3 years ago

I just spent a few hours debugging a lifetime compilation error related to this after replacing Vec with SmallVec. It took me a long time to figure out that the error originated in SmallVec. This can be really a tricky issue.

mbrubeck commented 3 years ago

Fortunately, I expect this issue will be fixed in smallvec 2.0 when we replace the Array trait with const generics (#240).

That work depends on the min_const_generics feature, which the Rust team is planning to ship in early 2021: https://github.com/rust-lang/rust/pull/79135

tesujimath commented 11 months ago

Having stumbled upon a lifetime problem caused by this, I found the very new 2.0.0-alpha.1 version, tried it, and found it fixed my problem, so yay! And thanks!

Nadrieril commented 10 months ago

min_const_generics was stabilized 3 years ago: https://github.com/rust-lang/rust/pull/79135, are there any plans to provide a SmallVec<T, N> alternative that has the right variance?

Nadrieril commented 10 months ago

Oh wait, it looks like master has that already, I guess it's not finalized yet?