Soundness of Heterogeneous collection of types

code review
1

Hi there,

I am currently working on a type to store a heterogeneous collection of types where every type is uniquely stored inside a set / map (as I've already talked about here). Assuming UniqueTypeId is truly unique across all types, is the following idea sound? I don't see any obvious issues but as it's my first time working with unsafe i would love to have a second pair of eyes look over my code (and as stated in linked post I sadly can't use std::any::Any for it)

pub trait UniqueTypeId {
    fn id() -> &'static str
    where
        Self: Sized;
}

struct HeterogeneousSet<'a> {
    backend: HashMap<&'a str, Box<dyn UniqueTypeId + 'a>>,
}

impl<'a> HeterogeneousSet<'a> {
    #[must_use]
    fn get_or_insert_with<'b, T: 'a>(&'b mut self, f: impl FnOnce() -> T) -> &'b mut T
    where
        T: UniqueTypeId,
    {
        let r#ref = self
            .backend
            .entry(T::id())
            .or_insert_with(|| Box::new(f()))
            .as_mut();

        unsafe { &mut *(r#ref as *mut dyn UniqueTypeId as *mut T) }
    }

    #[must_use]
    fn get_or_insert_default<'b, T: 'a>(&'b mut self) -> &'b mut T
    where
        T: UniqueTypeId + Default,
    {
        self.get_or_insert_with(T::default)
    }

    #[must_use]
    fn get<'b, T>(&'b self) -> Option<&'b T>
    where
        T: UniqueTypeId,
    {
        let r#ref = self.backend.get(T::id()).map(AsRef::as_ref);

        r#ref.map(|x| unsafe { &*(x as *const dyn UniqueTypeId as *const T) })
    }
}

Thank you for your time taken to review this :slight_smile:

Justus Flügel

2

The problem is that you can't directly assign a unique type id across all non-'static types. If the assumption can't be met, the answer is moot.

Read the conversation here and also this comment and the immediate followup. And also the last comment/link in that issue.

4 Likes
3

Just like you described in post you linked, downcast need both the equivalent of dyn Any and the T to be 'static in order to be sound. All three of your methods can potentially downcast a dyn UniqueTypeid + 'a to a T, so you need to require 'a = 'static and T: 'static in order to be sound, but at that point this is no different than Any.

To show how this can be abused, you just need to insert some value with lifetime 'a, and then get it with a longer lifetime (potentially 'static, so requiring T: 'static when downcasting is not enough, you also need HeterogeneousSet<'static>): Rust Playground

2 Likes
4

If you restrict it to types covariant in a single lifetime parameter, I think that something like this should be possible by using the type id of T<'static> to represent all of its supertypes. Here's my quick-and-dirty POC:

struct TypeSet<'a> {
    map: HashMap<TypeId, Box<dyn Opaque + 'a>>,
    lt: std::marker::PhantomData<fn(&'a ())->&'a ()>
}

impl<'a> TypeSet<'a> {
    pub fn new()->Self {
        TypeSet {
            map: HashMap::new(),
            lt: std::marker::PhantomData
        }
    }
    
    pub fn get_or_insert_with<'b, T: 'a + Covariant<'a>>(&'b mut self, f: impl FnOnce() -> T) -> &'b mut T {
        let item: &mut Box<dyn Opaque + 'a> = self.map
            .entry(TypeId::of::<T::Template>())
            .or_insert_with(|| Box::new(f()));
        
        let ptr = (&mut **item) as *mut dyn Opaque;
        unsafe { &mut *(ptr as *mut T) }
    }

    pub fn get_or_insert_default<'b, T: Default + 'a + Covariant<'a>>(&'b mut self) -> &'b mut T {
        self.get_or_insert_with(T::default)
    }

    pub fn get<'b, T: 'b + Covariant<'b>>(&'b self)->Option<&'b T> where 'a:'b {
        let item:&Box<dyn Opaque> = self.map.get(&TypeId::of::<T::Template>())?;
        let ptr = (&**item) as *const dyn Opaque;
        Some(unsafe { &* (ptr as *const T)}) 
    }

    pub fn take<T:'a + Covariant<'a>>(&mut self)->Option<T> {
        let item = self.map.remove(&TypeId::of::<T::Template>())?;
        Some(unsafe { *Box::from_raw(Box::into_raw(item) as *mut T)})
    }
}

trait Opaque {}
impl<T> Opaque for T {}

// ---------------

unsafe trait CovariantTemplate: 'static {
    /// Safety requirements:  For all lifetimes `'a` and `'b`,
    ///  * Short<'a> must be a supertype of Self
    ///  * If 'b is a supertype of 'a, Short<'b> must be a supertype of Short<'a>
    type Short<'a>: 'a + ?Sized;
}

trait Covariant<'a> {
    type Template: CovariantTemplate<Short<'a> = Self> + ?Sized;
}

// See playground for impls...
1 Like
5

It still looks unsound to me, but I think it might work if instead of returning (references to) T you return (references to) T::Template::Short<'a>.

Edit: I misinterpreted the meaning of Covariant<'a>, I see now why it should work. You're essentially re-implementing better-any

2 Likes
6

My naming here could certainly be better. Thanks for letting me know about better-any; I got the idea from an IRLO post a while back, but I didn't realize that someone had written a crate for it.

1 Like
7

Thanks for help.

I think I am gonna go and modify my / your code to use better-any instead and only rely on safe code on my side for now (where possible). I think I understand why my code was not sound in the first place, T: 'a only meant T has to be able to live for at least 'a, but not exactly 'a. Your code then constrains it to 'a and Covariant<'a> which I guess should mean that T must be Covariant over 'a and as such can only be held safely for 'a as T has to be a subtype of 'a. Then T must be able to be held safely for min 'a and max 'a and as such there is no way to create references with a longer lifetime than my Set. Thanks.

I am gonna go and help some others in this forum where I can to repay the favor :slight_smile: