How would I create a handle manager in Rust?

Question

pub struct Storage<T>{
    vec: Vec<T>
}
impl<T: Clone> Storage<T>{
    pub fn new() -> Storage<T>{
        Storage{vec: Vec::new()}
    }
    pub fn get<'r>(&'r self, h: &Handle<T>)-> &'r T{
        let index = h.id;
        &self.vec[index]
    }
    pub fn set(&mut self, h: &Handle<T>, t: T){
        let index = h.id;
        self.vec[index] = t;
    }
    pub fn create(&mut self, t: T) -> Handle<T>{
        self.vec.push(t);
        Handle{id: self.vec.len()-1}
    }
}
struct Handle<T>{
    id: uint
}

I am currently trying to create a handle system in Rust and I have some problems. The code above is a simple example of what I want to achieve.

The code works but has one weakness.

let mut s1 = Storage<uint>::new();
let mut s2 = Storage<uint>::new();
let handle1 = s1.create(5);
s1.get(handle1); // works
s2.get(handle1); // unsafe

I would like to associate a handle with a specific storage like this

//Pseudo code
struct Handle<T>{
    id: uint,
    storage: &Storage<T>
}
impl<T> Handle<T>{
   pub fn get(&self) -> &T;
}

The problem is that Rust doesn't allow this. If I would do that and create a handle with the reference of a Storage I wouldn't be allowed to mutate the Storage anymore.

I could implement something similar with a channel but then I would have to clone T every time.

How would I express this in Rust?

Answer 1

The simplest way to model this is to use a phantom type parameter on Storage which acts as a unique ID, like so:

use std::kinds::marker;

pub struct Storage<Id, T> {
    marker: marker::InvariantType<Id>,
    vec: Vec<T>
}

impl<Id, T> Storage<Id, T> {
    pub fn new() -> Storage<Id, T>{
        Storage {
            marker: marker::InvariantType,
            vec: Vec::new()
        }
    }

    pub fn get<'r>(&'r self, h: &Handle<Id, T>) -> &'r T {
        let index = h.id;
        &self.vec[index]
    }

    pub fn set(&mut self, h: &Handle<Id, T>, t: T) {
        let index = h.id;
        self.vec[index] = t;
    }

    pub fn create(&mut self, t: T) -> Handle<Id, T> {
        self.vec.push(t);
        Handle {
            marker: marker::InvariantLifetime,
            id: self.vec.len() - 1
        }
    }
}

pub struct Handle<Id, T> {
    id: uint,
    marker: marker::InvariantType<Id>
}

fn main() {
    struct A; struct B;
    let mut s1 = Storage::<A, uint>::new();
    let s2 = Storage::<B, uint>::new();

    let handle1 = s1.create(5);
    s1.get(&handle1);

    s2.get(&handle1); // won't compile, since A != B
}

This solves your problem in the simplest case, but has some downsides. Mainly, it depends on the use to define and use all of these different phantom types and to prove that they are unique. It doesn't prevent bad behavior on the user's part where they can use the same phantom type for multiple Storage instances. In today's Rust, however, this is the best we can do.

An alternative solution that doesn't work today for reasons I'll get in to later, but might work later, uses lifetimes as anonymous id types. This code uses the InvariantLifetime marker, which removes all sub typing relationships with other lifetimes for the lifetime it uses.

Here is the same system, rewritten to use InvariantLifetime instead of InvariantType:

use std::kinds::marker;

pub struct Storage<'id, T> {
    marker: marker::InvariantLifetime<'id>,
    vec: Vec<T>
}

impl<'id, T> Storage<'id, T> {
    pub fn new() -> Storage<'id, T>{
        Storage {
            marker: marker::InvariantLifetime,
            vec: Vec::new()
        }
    }

    pub fn get<'r>(&'r self, h: &Handle<'id, T>) -> &'r T {
        let index = h.id;
        &self.vec[index]
    }

    pub fn set(&mut self, h: &Handle<'id, T>, t: T) {
        let index = h.id;
        self.vec[index] = t;
    }

    pub fn create(&mut self, t: T) -> Handle<'id, T> {
        self.vec.push(t);
        Handle {
            marker: marker::InvariantLifetime,
            id: self.vec.len() - 1
        }
    }
}

pub struct Handle<'id, T> {
    id: uint,
    marker: marker::InvariantLifetime<'id>
}

fn main() {
    let mut s1 = Storage::<uint>::new();
    let s2 = Storage::<uint>::new();

    let handle1 = s1.create(5);
    s1.get(&handle1);

    // In theory this won't compile, since the lifetime of s2 
    // is *slightly* shorter than the lifetime of s1.
    //
    // However, this is not how the compiler works, and as of today
    // s2 gets the same lifetime as s1 (since they can be borrowed for the same period)
    // and this (unfortunately) compiles without error.
    s2.get(&handle1);
}

In a hypothetical future, the assignment of lifetimes may change and we may grow a better mechanism for this sort of tagging. However, for now, the best way to accomplish this is with phantom types.