r/rust•
barskern

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

526
pilotInPyjamas•

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 for keyword in closure type signatures can be used to create a new lifetime on demand. Here's a summary of some of the key points.

  • The id datatype is as follows: type Id<’id> = PhantomData<Cell<&’id u8>>; Putting your lifetime in a Cell prevents the compiler from coercing one lifetime into another, keeping them unique.
  • Use the closure signature F: for<’id> FnOnce(SomeData<’a, ’id>) to create an existential type. This is essentially the same as Haskell's ST monad.
  • Even with all of this, you have to keep the indices and the parent in a closure. It requires an enormous amount of boilerplate, and when you get things wrong, the compiler gives nonsensical errors.

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.

8
barskernOP•

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.

3
jimuazu•

This is what is used in qcell for the LCell type. 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.

1
SethDusek5•

I think you could get something close to this with a PhantomData marker for your indexes? That way you can't use an index obtained from an Arena<u64> into an Arena<u8> but beyond that it won't work if both Arenas are of the same type. I've made a proof of concept demonstrating this however I don't think this matches exactly what you were looking for.

2
barskernOP•

Thank you for the quick response! This is pretty much what I'm already doing, but I rather use the whole arena as the type parameter to the index so that the error message is a bit more descriptive. I was wondering if it's possible to solve the case where the types are equal at compile time.

1
jimuazu•

See my qcell crate where I tried all the options I was aware of (after also asking here). If you come up with a new way, I'll try and incorporate it, but I think those are the choices: numeric ID, marker type or unique lifetime. Lifetime has good properties but means lifetime annotations everywhere.

2
barskernOP•

I will take a closer look at this. Thank you for the suggestion! Have you thought about using closures as shown in the article linked by u/shadow31?

1
jimuazu•

It is equivalent to using a marker type, because the same closure at the same point in the source code always has the same type. (Unfortunately!!!)

1

How about adding a unit struct representing each instance of the arena, and add it as a type parameter for both index and the arena?

Maybe with const generics you could have an instance ID which would be incremented every time you instantiated an arena.

1
barskernOP•

Yeah I was considering it, but then the consumer of the API would have to make a unit struct for each arena, which is not a big annoyance, but I was hoping there was a elegant way around it.

Using const generics would probably be my best bet, thanks for the tip!

1
shadow31•

Have you seen this? https://fullyfaithful.eu/bounds-check-elision-rust/

It sounds very similar to what you're trying to do.

1
barskernOP•

Thank you so much! I think that pointed me in the right direction, because closures always have unique types even though they are visually equal in the sourcecode. I will try to use that fact to make this work.

EDIT: I had not come to the errata yet when I posted this, so based on that using closures does not seem like a viable way to accommplish this. TLDR; closures are only uniq when they are created at different places in the code, hence creating a closure within a constructor does not create uniq closures. Perhaps doing it in a macro would work?

1
jimuazu•

The same closure in the same place in the source code always has the same type. See the errata. So the closure type trick is exactly the same as using a marker type (i.e. you might as well just put struct Marker; inside the function.

2
pilotInPyjamas•

Macros always expand to code and nothing else. If you can't do it with pure code, you can't do it with a macro.

1
barskernOP•

You can do it with pure code, it's just verbose and error prone. However using a macro is also error prone because it doesn't work in all contexts (playground).

1
pilotInPyjamas•

If you can't do it without errors, you can't do it.

Anywhere you call your constructor inside a loop or a reusable function, which is pretty much anywhere, you have broken your guarantees that each arena has a unique type. This is not going to be a rare occurrence, or an edge case. Anyone who puts arena! inside another function is going to be breaking guarantees. That's not a technique that "doesn't work in some contexts" that is a technique that "doesn't work in any context".

The number of unique closure types is the number of times you write it in your code after you expand macros. This is guaranteed by the monomorphisation process which makes all types concrete. If there are 5 instances of arena! in your code, and 10 arenas at runtime, then by the pigeonhole principle, you know that at least 5 of those arenas have indexes that can be used on another arena.

You need existential types: types that cannot be monomorphised.

2