Is it possible to make similar generic types different at compile-time?
I've recently started a personal project to create a Arena allocator using generational indicies to practice writing Rust. I was curious if it's possible to create index types which are linked to the arena at compile time, such that an index can only be used to index into the arena it came from. I figured out how to do this when the arena contains different types, however when the arenas contains the same type, the indexes are interchangeable (see example). I could "force" the user to make a unique empty type for each arena which has to be given as a generic parameter when creating the arena, but I would prefer to avoid this. Is there another way to accomplish this?
Here is my current code which works when the arenas contain different types, but not when they have the same type parameter (playground).
use std::marker::PhantomData;
use std::vec::Vec;
pub struct Arena<T> {
vec: Vec<Option<T>>,
}
impl<T> Arena<T> {
pub fn new() -> Self {
Arena { vec: Vec::new() }
}
pub fn insert(&mut self, v: T) -> Index<Self> {
let idx = self.vec.len();
self.vec.push(Some(v));
Index {
idx,
_storage: PhantomData,
}
}
pub fn get(&self, idx: Index<Self>) -> Option<&T> {
let Index { idx, .. } = idx;
self.vec.get(idx).and_then(|v| v.as_ref())
}
pub fn remove(&mut self, idx: Index<Self>) -> Option<T> {
let Index { idx, .. } = idx;
self.vec[idx].take()
}
}
pub struct Index<S> {
idx: usize,
_storage: PhantomData<S>,
}
impl<S> Copy for Index<S> {}
impl<S> Clone for Index<S> {
fn clone(&self) -> Self {
Self {
idx: self.idx,
_storage: PhantomData,
}
}
}
#[test]
fn ensure_indicies_to_different_arenas_are_distinct() {
let mut a: Arena<u32> = Arena::new();
let mut b: Arena<i32> = Arena::new();
let _idxa = a.insert(123);
let _ = b.insert(123);
// Uncommenting the following line causes a compilation error as expected.
// b.get(_idxa);
}
#[test]
fn ensure_indicies_to_similar_arenas_are_distinct() {
let mut a: Arena<u32> = Arena::new();
let mut b: Arena<u32> = Arena::new();
let idxa = a.insert(123);
let _ = b.insert(123);
b.get(idxa); // This should preferably be a compilation error.
}
EDIT: After getting a lot of good tips I decided to make an optional marker struct which will default to (). That way a consumer can, if it is wanted, mark an arena with a custom empty struct which will then be a part of all indicies made from the arena. It is probably unnessecary, but I do not see any great drawbacks besides that the generic might be confusing to new users of the API. E.g the signature is now pub struct Arena<T, U = ()> and pub struct Index<S, U = ()> (where S is the related arena), which might be a bit strange to look at. Thanks to everyone giving pointers and tips.
Posted May 29, 2019, 12:43 PM UTC · edited
Yes, but rust is not designed for it. The method is documented in this thesis (Chapter 6.3). I had a similar discussion about this topic earlier.
Rust's monomorphisation rules prevent you from creating this structure from real types, however, the
forkeyword in closure type signatures can be used to create a new lifetime on demand. Here's a summary of some of the key points.iddatatype is as follows:type Id<’id> = PhantomData<Cell<&’id u8>>;Putting your lifetime in aCellprevents the compiler from coercing one lifetime into another, keeping them unique.F: for<’id> FnOnce(SomeData<’a, ’id>)to create an existential type. This is essentially the same as Haskell'sSTmonad.In short: don't do it. It's verbose and you're more likely to create an error in the lifetime code than actually mis-indexing something.
If it were me, I would probably create a struct which owns the arena and anything that has an index to it. The public interface to this object should not return anything that could be potentially mis-indexed. That way, as long as the code inside the module is correct, and we only use the public interface outside of it, then we shouldn't be able to mis-index anything.
Alternatively, you could create a unique ID at runtime for each arena, and then check at runtime if the index and arena are the same.
Thank you very much for the detailed answer. After some experimenting I definitly agree with your sentiment that it's not worth the complexity. It's not a particular requirement neither so the only reason I asked the question was to explore the possibilities of the language.
The thesis you linked looks really interesting as it dives deeper into other parts of the language aswell.
This is what is used in
qcellfor theLCelltype. The fact that Rust can prove this to itself (although with a huge amount of help in the form of lifetime annotations) means that there might be some hope that one day some way to describe this might be formulated that Rust can prove without the annotations. For example something that says "Rust, dive down the callstack to prove that this is okay". So this produces a kind of viral requirement on callers that is not specified in the API. This isn't the "Rust way", I know, but it would solve the problem. Also whilst slower than the normal proof checks, it's not something unbounded -- it either passes or fails.