Can Rust lifetimes be used to enforce this API rule?


#1

Can lifetimes be used to enforce a rule like “both arguments to this function belong to the same parent object”?

I have this API:

pub struct Graph<'a> { ... }
pub struct VertexRef<'a> { ... }

impl<'a> Graph<'a> {
    pub fn new() -> Graph<'a> { ... }
    pub fn new_vertex(&mut self) -> VertexRef<'a> { ... }
    pub fn add_edge(&mut self, u: VertexRef<'a>, v: VertexRef<'a>) { ... }
}

I would like for this to be an error:

let mut g1 = Graph::new();
let mut g2 = Graph::new();
let v1 = g1.new_vertex();
let v2 = g2.new_vertex();
g1.add_edge(v1, v2);  // BAD - edges should not cross graphs

I could just add some assertions in Graph::add_edge. But I’m hoping rustc will enforce the rule for me statically, if only I can get the API design just right.

Can it be done?


#2

I just realized: the only problem is Graph::new().

Rust is inferring the same lifetime-parameter for g1 and g2, thus giving them the exactly same type. And if two objects have exactly the same type, the type system can hardly be expected to keep them separate.

But I don’t see how to prevent that. It would have to involve changing the type of Graph::new() somehow.


#3

Lifetimes won’t help you here. The 'a on Graph and VertexRef only requires that the latter lives at least as long as the former.

This is something that has to be checked dynamically. Have .add_edge() return Result<(), (VertexRef, VertexRef)> and return the two vertices in Err if either one is not in the graph.


#4

Yes, you can enforce that, but it’s only usable inside a restricted scope (a closure), see for example my experiment https://github.com/bluss/indexing which is quite developed and dedicated to to trusted indices. In my case, it uses an “anonymous” lifetime to brand indexes to be trusted (so that they don’t need bounds checking when used).


#5

It works! Here’s what it looks like to apply @bluss’s technique to my Graph example: https://gist.github.com/jorendorff/45116c5aa132d5fe58e9

As I suspected, Graph::new had to go. In its place there’s a new with_graph function which you can use with a closure. It’s only slightly weird. :slight_smile:


#6

I wonder if a similar design can be achieved with the help of OIBIT. If, for example, Graph and VertexRef are !Sync and !Send, the following is almost what we want here:

std::thread::spawn(|| {
    let mut g1 = Graph::new();
    std::thread::spawn(|| {
        let mut g2 = Graph::new();
    })
})


#7

I don’t know if this helps in any way, but here is another trick that I found pretty interesting in enforcing some rules by using the type system: http://os.phil-opp.com/modifying-page-tables.html#some-clever-solution


#8

Doesn’t that mean that every graph’s lifetime is tied to a function call? So two graphs’ lifetimes can never partially overlap, as they would in code like this using your original API:

let mut g1 = Some(Graph::new());
let g2 = Graph::new();
g1 = None; // g1's graph is freed at this point, but g2 lives on

#9

From Gankro’s gist, this seems to be the heart of the technique:

    // Cell<T> is invariant in T; so Cell<&'id _> makes `id` invariant.
    // This means that the inference engine is not allowed to shrink or
    // grow 'id to solve the borrow system. 

Without this, the borrow checker would just choose the larger scope. Do I have that right?


#10

I found a way to break that rule:

    with_graph("g1", |g1| {
        let mut opt = Some(g1);
        with_graph("g2", |mut g2| {
            opt = None;
            // g1 is gone, g2 is still alive
        });
    });

#11

Well, of course… I guess I didn’t manage to say what I was thinking.

It’s not possible to create a graph that can live beyond its call to with_graph; and this restriction stems not from anything about the data structure itself, but solely from the way we’re attaching incompatible lifetimes to each instance.

Does that work better?