Implement decorator pattern and lifetimes

[jorgecarleitao]

Hi,

I am trying to make the following code to compile, but I am struggling to achieve it. Sorry this was the smallest example I could come with. While the example is not very performant, the interesting bits here are:

1. we have structs that memcopies (i.e. deep copy) items (Builder::push)
2. we have a nested struct whose push wraps Builder::push (aka the decorator pattern) with some logic
3. the items in the push may be of variable size and thus require a reference
4. the nested struct must phantom the inner type's generic
5. this phantom will need to include lifetimes, even if the item is consumed on push

use std::collections::{HashMap};
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

pub trait DynVec {
    fn len(&self) -> usize;
}

pub struct StringVec {
    values: Vec<String>,
}

impl StringVec {
    pub fn new() -> Self {
        Self {
            values: vec![],
        }
    }
}

impl DynVec for StringVec {
    fn len(&self) -> usize {
        self.values.len()
    }
}

/// Trait for building trait objects of `DynVec`
pub trait Builder<T> {
    fn push(&mut self, item: T);

    fn into_box(self) -> Box<dyn DynVec>;
}

impl Builder<&str> for StringVec {
    // note how this 
    fn push(&mut self, item: &str) {
        self.values.push(item.to_string());  // copy the item, so the lifetime is not really used...
    }
    fn into_box(self) -> Box<dyn DynVec> {
        Box::new(self)
    }
}

pub struct HashVec {
    indices: Vec<usize>,
    values: Box<dyn DynVec>,
}

impl DynVec for HashVec {
    fn len(&self) -> usize {
        self.indices.len()
    }
}

/// Builder of HashVec
// T must be here due to <T> in Builder<T>
pub struct HashBuilder<B: Builder<T>, T> {
    map: HashMap<u64, usize>,
    indices: Vec<usize>,
    values: B,
    // answering the compiler: consider removing `T`, referring to it in a field, or using a marker such as `PhantomData`
    phantom: std::marker::PhantomData<T>,
}

impl<T: Hash, B: Builder<T>> HashBuilder<B, T> {
    pub fn new(values: B) -> Self {
        Self {
            indices: vec![],
            values,
            map: HashMap::new(),
            phantom: std::marker::PhantomData,
        }
    }
}

impl<T: Hash, B: Builder<T>> Builder<T> for HashBuilder<B, T> {
    fn push(&mut self, item: T) {
        let mut hasher = DefaultHasher::new();
        item.hash(&mut hasher);
        let hash = hasher.finish();
        match self.map.get(&hash) {
            Some(key) => self.indices.push(*key),
            None => {
                let key = self.map.len();
                self.values.push(item);
                self.map.insert(hash, key);
                self.indices.push(key);
            }
        }
    }
    fn into_box(self) -> Box<dyn DynVec> {
        Box::new(HashVec {
            indices: self.indices,
            values: self.values.into_box()
        })
    }
}

//////////// declarations finished
fn main() {
    // this works because T: &'static str
    let mut builder = HashBuilder::new(StringVec::new());
    builder.push("a");
    builder.push("b");
    builder.push("a");
    assert_eq!(builder.indices.len(), 3);
    assert_eq!(builder.values.len(), 2);
}

// this does not; even though it seems safe to me.
// note how `v` is anonymous here, even though we though HashBuilder will 
// copy `v`'s contents and `&'static str` is just used to make the compiler happy...
// in general I do not have information about `v`'s lifetime when `HashBuilder`
// is initialized ()
fn push_element_lifetimes(b: &mut HashBuilder<StringVec, &'static str>, v: &str) {
    b.push(v)
}

Is there a way to solve this? I.e. how to keep the lifetime of v anonymous and still compile?

playground

[quinedot]

Instead of implementing for &T and taking T as an argument, implement for T: ?Sized and take &T as an argument.

Here is a pretty much entirely mechanical adjustment to your playground, which (disclaimer) I haven't examined at all beyond doing the adjustment until it compiled.

@jorgecarleitao

this phantom will need to include lifetimes, even if the item is consumed on push

I'm also not sure what this is about, but didn't really preserve it, since T is now str.