Почему SmallVec ведет себя по-разному при хранении типов с временем жизни по сравнению с Vec? - PullRequest
Новая
       20

Почему SmallVec ведет себя по-разному при хранении типов с временем жизни по сравнению с Vec?

4 голосов
/ 21 мая 2019

У меня есть три примера, один с использованием Vec, другой с использованием SmallVec, а другой с моей собственной реализацией SmallVec. Те, которые используют Vec и мой SmallVec, компилируются, а те, которые используют реальный SmallVec, не компилируются.

Рабочий пример с использованием 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<'_>`
    }
}

Неудачный пример с SmallVec

Использует SmallVec вместо Vec без других изменений. 

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

Рабочий пример с моим собственным SmallVec

Когда я реализую свой собственный (очень наивный) SmallVec<[T; 2]> (называемый NaiveSmallVec2<T>), код также компилируется ... Очень странно! 

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
    }
}

Я ожидаю, что версия SmallVec будет компилироваться так же, как и версия Vec. Я не понимаю, почему в некоторых случаях (в случае Vec) &ItemTraitReturns<'static> можно преобразовать в &ItemTraitReturns<'_>, а в некоторых случаях (SmallVec) это невозможно (я не вижу влияния Vec / SmallVec).

Я не хочу менять время жизни этой черты: 

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

... так как при использовании этой черты мне не важно время жизни (это должно быть деталью реализации) ... но все же хотелось бы использовать SmallVec.

1 Ответ

4 голосов
/ 21 мая 2019

Эта разница, по-видимому, вызвана разницей в дисперсии между Vec и SmallVec. В то время как Vec<T> является ковариантным в T, SmallVec представляется инвариантным . В результате, SmallVec<[&'a T; 1]> не может быть преобразован в SmallVec<[&'b T; 1]>, даже если время жизни 'a переживает 'b, и преобразование должно быть безопасным. Вот минимальный пример, вызывающий ошибку компилятора: 

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
}

Это, похоже, недостаток SmallVec. Дисперсия автоматически определяет дисперсию, и иногда бывает сложно убедить компилятор в том, что можно с уверенностью предположить, что тип является ковариантным.

Для этой проблемы существует открытая проблема Github .

К сожалению, я не знаю способа выяснить дисперсию типа на основе его открытого интерфейса. Дисперсия не включена в документацию и зависит от частных деталей реализации типа. Вы можете прочитать больше о дисперсии в справочнике по языку или в Nomicon .

...