Is it possible to express Dynamic Vector?

With the currently stable Rust is it possible to construct a vector of items with statically unknown type of the Item?

Using trait objects we can coerce Box of object-safe type to be dynamically dispatched Box<dyn Any> object. Informally speaking I would like to construct something like "Vec<dyn Any>" where the container would represent a memory slice of uniform items, but the type of all items will be unknown at compile time.

I want to emphasize that Vec<Box<dyn Any> where each item resides in random memory and have individual type per Item is not my goal. The container should represent a slice of contiguous memory of items of uniform type.

The first thing that comes into my mind is to manually re-implement or partially utilize the existing Vec data structure enreaching it with underlying item type Layout.

The main issue arising with this solution is that in currently stable Std manual memory allocation and deallocation is not possible. Maybe there are some workarounds?

So, you have a statically known layout?

I have a crate list-any that seeks to provide this.

1 Like

Thank you so much, that's exactly what I was looking for.

Very interesting trick with specialized Vec drop function in Metadata for arbitrary type. So you don't need to deeply dig into Allocator stuff. This is amazing!

It is assumed that the target container would be created with concrete type. Similarly to Box<T> as Box<dyn Any>. So at the creation point whatever way we created the container we statically known the Item type, and it's Layout as well.

This is not true. What makes you think this is the case? There are several, lower-level and higher-level abstractions in std that you can use to manually manage memory. For example, there is alloc::System with a GlobalAlloc impl. Shouldn't that suffice for most needs?

Also, I believe you don't need any manual memory management for this anyway. Here's a possible implementation:

use core::any::Any;
use core::slice::SliceIndex;

trait DynVec: Any {
    fn get(&self, index: usize) -> Option<&dyn Any>;
    fn get_mut(&mut self, index: usize) -> Option<&mut dyn Any>;

    // downcasting helpers
    fn as_any(&self) -> &dyn Any;
    fn as_any_mut(&mut self) -> &mut dyn Any;
}

trait AnyVec<T>: DynVec {
    fn get<I>(&self, index: I) -> Option<&I::Output>
    where
        I: SliceIndex<[T]>;

    fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
    where
        I: SliceIndex<[T]>;

    fn push(&mut self, item: T) -> Result<&mut T, T>;
    fn pop(&mut self) -> Option<T>;
}

impl<T: Any> DynVec for Vec<T> {
    fn get(&self, index: usize) -> Option<&dyn Any> {
        self.as_slice().get(index).map(|item| item as &dyn Any)
    }

    fn get_mut(&mut self, index: usize) -> Option<&mut dyn Any> {
        self.as_mut_slice().get_mut(index).map(|item| item as &mut dyn Any)
    }

    fn as_any(&self) -> &dyn Any {
        self
    }

    fn as_any_mut(&mut self) -> &mut dyn Any {
        self
    }
}

impl<T: Any, U: Any> AnyVec<T> for Vec<U> {
    fn get<I>(&self, index: I) -> Option<&I::Output>
    where
        I: SliceIndex<[T]>
    {
        self.as_any().downcast_ref::<Vec<T>>().and_then(|this| this.as_slice().get(index))
    }

    fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
    where
        I: SliceIndex<[T]>
    {
        self.as_any_mut().downcast_mut::<Vec<T>>().and_then(|this| this.as_mut_slice().get_mut(index))
    }

    fn push(&mut self, item: T) -> Result<&mut T, T> {
        if let Some(this) = self.as_any_mut().downcast_mut::<Vec<T>>() {
            this.push(item);
            Ok(this.last_mut().unwrap())
        } else {
            Err(item)
        }
    }

    fn pop(&mut self) -> Option<T> {
        self.as_any_mut().downcast_mut::<Vec<T>>().and_then(Vec::pop)
    }
}

struct ErasedVec(Box<dyn DynVec>);

impl DynVec for ErasedVec {
    fn get(&self, index: usize) -> Option<&dyn Any> {
        self.0.get(index)
    }
    
    fn get_mut(&mut self, index: usize) -> Option<&mut dyn Any> {
        self.0.get_mut(index)
    }

    // downcasting helpers
    fn as_any(&self) -> &dyn Any {
        self.0.as_any()
    }

    fn as_any_mut(&mut self) -> &mut dyn Any {
        self.0.as_any_mut()
    }
}

impl<T: Any> AnyVec<T> for ErasedVec {
    fn get<I>(&self, index: I) -> Option<&I::Output>
    where
        I: SliceIndex<[T]>
    {
        AnyVec::<T>::get(self.as_any().downcast_ref::<Vec<T>>()?, index)
    }

    fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
    where
        I: SliceIndex<[T]>
    {
        AnyVec::<T>::get_mut(self.as_any_mut().downcast_mut::<Vec<T>>()?, index)
    }

    fn push(&mut self, item: T) -> Result<&mut T, T> {
        if let Some(this) = self.as_any_mut().downcast_mut::<Vec<T>>() {
            AnyVec::<T>::push(this, item)
        } else {
            Err(item)
        }
    }

    fn pop(&mut self) -> Option<T> {
        AnyVec::<T>::pop(self.as_any_mut().downcast_mut::<Vec<T>>()?)
    }
}

impl<T: Any> From<Vec<T>> for ErasedVec {
    fn from(vec: Vec<T>) -> Self {
        ErasedVec(Box::new(vec))
    }
}

fn main() {
    let ty_vec: Vec<u64> = vec![1, 2, 3];
    let mut er_vec = ErasedVec::from(ty_vec);

    dbg!(DynVec::get(&er_vec, 0));
    dbg!(DynVec::get_mut(&mut er_vec, 1));
    dbg!(DynVec::get_mut(&mut er_vec, 3));
    dbg!(AnyVec::<u64>::get_mut(&mut er_vec, 2));
    dbg!(AnyVec::<String>::get(&mut er_vec, 1));
    dbg!(AnyVec::<String>::pop(&mut er_vec));
    dbg!(AnyVec::<u64>::pop(&mut er_vec));
    dbg!(AnyVec::<u64>::push(&mut er_vec, 1337));
    dbg!(AnyVec::<String>::push(&mut er_vec, String::from("nope")));
}
2 Likes

I feel you have misunderstanding on what OP wants. OP wants something operates like Vec<Box<dyn Any>> but without the Box. OP want to support any_vec![1, 2, "abc", String::from("haha")]-like operation.

Thank you for your reply, and for the detailed example. After reading of your example and the list-any crate mentioned by Violet Leonard above, I realized that I underestimate the expressiveness of the Rust type system, and that my initial thoughts about low-level Vec re-implementation was in wrong direction anyway. What I wanted to achieve in the beginning could be expressed much easier in many ways.

As of alloc::System, as far as I understand all of it's allocation/deallocation functions are under the Allocator API nightly feature. That's why I considered it as unstable.

I like your solution too, it is based on completely safe Rust and very elegant, and basically achieve the desired goal in general. One issue I see here comparing to Violet Leonard's solution is that you create indirection by wrapping Vec<T> into Box. This is additional allocation (which is maybe will not always be a big issue in many cases), and because of this it also slightly harms memory locality too.

yes, to be clear you can make this very concisely with just Box<Vec<T>>, and upcast the it to Box<dyn Any> where the Vec itself is the trait object. The purpose of my crate was solely to remove that extra indirection.

1 Like

This is not the case; as I mentioned, impl GlobalAlloc for System is already stable today (they both have been, since 1.28). This compiles under the stable toolchain.

It's probably not a big deal. You will already have dynamic dispatch for every single call you make to the ErasedVec anyway. Traversing a single pointer is probably at most comparable to that.

Note though that the two traits, DynVec and AnyVec<T> are implemented for all Vec<U> concrete types directly. Therefore, if you are OK with having such a concrete type own the elements, and only drop down to &(mut) dyn DynVec or &(mut) dyn AnyVec<T> when you actually need to access the elements in some other methods, then you can just accept such borrowed trait objects in any function that needs them, and otherwise keep the concretely-typed Vec around. This avoids boxing the vector itself.

No, that's wrong. It's explicitly in the OP:

2 Likes

Oh yeah, that's totally my bad then.

oh, I didn't realize that the implement of unstable trait is stable itself. Thanks!

GlobalAlloc is not an unstable trait. It is 100% stable since 1.28. Not only the impl for System, but the trait itself as well.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.