A struct generic over the stack and the heap

I'm working on a data structure that has to be generic over how it stores its data. In this case I don't want to have slightly different structures with a lot of repeated methods, and I also don't want to use an enum and dynamic matching, instead I prefer to leverage the type system and its monomorphization.

I made a simplified example using an array, showing the only way I've found to do it. I want to make sure I'm not missing anything obvious. I also don't understand why do I need to use PhantomData in the example, since the generic trait already contains the generic type. Is that a temporary limitation of the type system?

What about the fact that the code doesn't actually enable you to call a method like read_first generically? MyStructureGeneric doesn't offer any advantage over simply using ArrayStack or ArrayHeap directly, since it always has to be parameterized with one or the other, if you want to call its useful methods. It is a concrete abstraction. In other words, you can't write a function like fn read_many<T, A>(s: MyStructureGeneric<T, A>) { /* using read_first */ }.

You "need" to use it because your Array trait is uselessly generic. That is, you have written an Array trait that can be implemented like so:

impl Array<String> for [String; 10] {...}
impl Array<i32> for [String; 10] {...}
impl Array<()> for [String; 10] {...}
/* etc. */

instead of implementing Array only once for each array type. Moreover, you have compounded this mistake by putting the A: Array bound on the MyStructureGeneric type, instead of only on the impls and fns where it is needed [1].

This is all rather academic since, as I mentioned before, there's no actually generic use of either type. Moreover, Rust has other features that allow you to generalize stack and heap storage, either by indirection (&) or by runtime state (enum and dyn) but you are not using those either.


  1. this wouldn't necessarily be a problem, except that combined with the needlessly generic Array, it leads you to introduce a spurious T generic ↩︎

2 Likes

Not sure how practical and/or nice this is or isn’t and I don’t plan on writing a lengthy response here right now, but since I’ve programmed it now, and it compiles and runs fine, feel free to take a look :wink::

Rust Playground

2 Likes

Thank you both! this is great information. I still find hard to grokk the traits and generics interactions...

One last thing, if I may. @steffahn I like your example a lot. I've simplified it to the essence to work with it, but I'm bumping my head to a wall trying to impl Clone & Copy on MyStructure when the T and the particular Storage implementation would in theory allow it (without them being associated type trait bounds in the trait). I'm not sure if that is even possible with GATs yet? If not, I'm gonna have to renounce to generics and do the separate types thing...

pub trait Storage {
    type Container<T>: From<T>;
}

pub struct Boxed;
impl Storage for Boxed {
    type Container<T> = Box<T>;
}

pub struct Direct;
impl Storage for Direct {
    type Container<T> = T;
}

pub struct MyStructure<T, S: Storage> {
    data: S::Container<[T; 10]>,
}

// FIXME
impl<T: Clone, S: Storage> Clone for MyStructure<T, S> where S::Container<T>: Clone {
    fn clone(&self) -> Self {
        Self { data: self.data.clone() }
    }
}

// FIXME
impl<T: Copy, S: Storage> Copy for MyStructure<T, S> where S::Container<T>: Copy {}

The fact that T is a type parameter of some trait doesn't imply anything about the qualities of T that influence qualities of the containing type: autotraits (e.g. is it Send or Sync), variance, etc.

Line up the types.

2 Likes

Ouch, I was blind. Thank you so much!

Copy is hard/impossible generically, without exposing the [T; 10]. E.g.

impl<T, S: Storage> Copy for MyStructure<T, S> where S::Container<[T; 10]>: Copy {}

would “expose” that type. For the case at hand, where only the two kinds of storage exist, one of which is never Copy, one could write a Copy impl for the concrete type

impl<T: Copy> Copy for MyStructure<T, Direct> {}

For Clone, you can write a trait bound for the S parameter, which is probably the nicest looking approach since no bounds on S::Container<[T; 10]> are involved then. I.e. some trait SupportsCloneStorage could allow

impl<T: Clone, S: SupportsCloneStorage> Clone for MyStructure<T, S> { … }

However, again assuming that we only want to have the Direct and Boxed storage anyways, both of which are clonable, we can make it part of Storage itself, so we have

impl<T: Clone, S: Storage> Clone for MyStructure<T, S> { … }

How to do this: Since it’s impossible/hard to write something like “this shall be Clone for all parameters T: Clone” on a GAT, the easiest approach is to introduce a helper method to Storage trait and just use that.

pub trait Storage {
    type Container<T>: From<T>;
    fn clone<T: Clone>(this: &Self::Container<T>) -> Self::Container<T>;
}

impl<T: Clone, S: Storage> Clone for MyStructure<T, S> {
    fn clone(&self) -> Self {
        Self {
            data: S::clone(&self.data),
        }
    }
}

Rust Playground

1 Like

I'm not exactly sure what you're trying to do, but from the description, you might be looking for a bound of Borrow in std::borrow - Rust on your data, which lets you directly implement your struct method without regards to how the data is stored.

1 Like