Why does SmallVec have different behaviour when storing types with lifetimes compared to Vec?

Question

I've got three examples, one using Vec one using SmallVec, and one with my own implementation of SmallVec. The ones using Vec and my own SmallVec compile but the one using the real SmallVec does not.

Working example using Vec

use std::borrow::Cow;
use std::collections::HashMap;

pub trait MyTrait {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns;
}

/// IMPORTANT PART IS HERE: `Vec<Cow<'a, str>>`
pub struct ItemTraitReturns<'a>(Vec<Cow<'a, str>>);

/// this implementation only takes items with static lifetime (but other implementations also might have different lifetimes)
pub struct MyTraitStruct {
    map: HashMap<usize, ItemTraitReturns<'static>>,
}

impl MyTrait for MyTraitStruct {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns {
        let temp: &ItemTraitReturns<'static> = self.map.get(&id).unwrap();
        // Works as expected: I expect that I can return `&ItemTraitReturns<'_>`
        // when I have `&ItemTraitReturns<'static>` (since 'static outlives everything).
        temp
        // Will return `&ItemTraitReturns<'_>`
    }
}

Failing example with SmallVec

Uses SmallVec instead of Vec with no other changes.

use smallvec::SmallVec;
use std::borrow::Cow;
use std::collections::HashMap;

pub trait MyTrait {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns;
}

/// IMPORTANT PART IS HERE: Uses SmallVec instead of Vec
pub struct ItemTraitReturns<'a>(SmallVec<[Cow<'a, str>; 2]>);

/// this implementation only takes items with static lifetime (but other implementations also might have different lifetimes)
pub struct MyTraitStruct {
    map: HashMap<usize, ItemTraitReturns<'static>>,
}

impl MyTrait for MyTraitStruct {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns {
        let temp: &ItemTraitReturns<'static> = self.map.get(&id).unwrap();
        temp
    }
}

error[E0308]: mismatched types
  --> src/lib.rs:23:9
   |
23 |         temp
   |         ^^^^ lifetime mismatch
   |
   = note: expected type `&ItemTraitReturns<'_>`
              found type `&ItemTraitReturns<'static>`
note: the anonymous lifetime #1 defined on the method body at 18:5...
  --> src/lib.rs:18:5
   |
18 | /     fn get_by_id(&self, id: usize) -> &ItemTraitReturns {
19 | |         let temp: &ItemTraitReturns<'static> = self.map.get(&id).unwrap();
20 | |         // Error:
21 | |         //    = note: expected type `&demo2::ItemTraitReturns<'_>`
22 | |         //              found type `&demo2::ItemTraitReturns<'static>`
23 | |         temp
24 | |     }
   | |_____^
   = note: ...does not necessarily outlive the static lifetime

Working example with my own SmallVec

When I implement my own (very naive) SmallVec<[T; 2]> (called NaiveSmallVec2<T>) the code also compiles... Very strange!

use std::borrow::Cow;
use std::collections::HashMap;

/// This is a very naive implementation of a SmallVec<[T; 2]>
pub struct NaiveSmallVec2<T> {
    item1: Option<T>,
    item2: Option<T>,
    more: Vec<T>,
}

impl<T> NaiveSmallVec2<T> {
    pub fn push(&mut self, item: T) {
        if self.item1.is_none() {
            self.item1 = Some(item);
        } else if self.item2.is_none() {
            self.item2 = Some(item);
        } else {
            self.more.push(item);
        }
    }

    pub fn element_by_index(&self, index: usize) -> Option<&T> {
        match index {
            0 => self.item1.as_ref(),
            1 => self.item2.as_ref(),
            _ => self.more.get(index - 2),
        }
    }
}

pub trait MyTrait {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns;
}

/// IMPORTANT PART IS HERE: Uses NaiveSmallVec2
pub struct ItemTraitReturns<'a>(NaiveSmallVec2<Cow<'a, str>>);

/// only takes items with static lifetime
pub struct MyTraitStruct {
    map: HashMap<usize, ItemTraitReturns<'static>>,
}

impl MyTrait for MyTraitStruct {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns {
        let temp: &ItemTraitReturns<'static> = self.map.get(&id).unwrap();
        // astonishingly this works!
        temp
    }
}

---

I expect the SmallVec version to compile like the Vec version does. I don't understand why in some cases (in the case of Vec) &ItemTraitReturns<'static> can be converted to &ItemTraitReturns<'_> and in some cases (SmallVec) it's not possible (I don't see the influence of Vec / SmallVec).

I don't want to change lifetimes of this trait:

pub trait MyTrait {
    fn get_by_id(&self, id: usize) -> &ItemTraitReturns;
}

... since when using the trait I don't care about lifetimes (this should be an implementation detail) ... but still would like to use SmallVec.

Answer 1

This difference appears to be caused by a difference in variance between Vec and SmallVec. While Vec<T> is covariant in T, SmallVec appears to be invariant. As a result, SmallVec<[&'a T; 1]> can't be converted to SmallVec<[&'b T; 1]> even when lifetime 'a outlives 'b and the conversion should be safe. Here is a minimal example triggering the compiler error:

fn foo<'a, T>(x: SmallVec<[&'static T; 1]>) -> SmallVec<[&'a T; 1]> {
    x  // Compiler error here: lifetime mismatch
}

fn bar<'a, T>(x: Vec<&'static T>) -> Vec<&'a T> {
    x  // Compiles fine
}

This appears to be a shortcoming of SmallVec. Variance is automatically determined by the compiler, and it is sometimes cumbersome to convince the compiler that it is safe to assume that a type is covariant.

There is an open Github issue for this problem.

Unfortunately, I don't know a way of figuring out the variance of a type based on its public interface. Variance is not included in the documentation, and depends on the private implementation details of a type. You can read more on variance in the language reference or in the Nomicon.