Suggestions for fixing this lifetime error?


#1

I’ve written a type for caching/interning data. It’s used like this:

impl<T: Hash> Interner<T> {
    fn new() -> Interner<T>;
    fn intern<'i>(&'i self, data: T) -> Interned<'i, T>;
}

impl<'i, T: 'i> Deref for Interned<'i, T> {
    type Target = T;
}

The idea is, Interned<'i, T> is a lot like Rc<T>. The difference is that you create an Interned<'i, T> using an Interner and the Interner maintains a hash map of data that already exists. If you’re trying to intern something that already exists in the Interner then the Interner gives you a reference to it and increments the data’s reference count.

The full code is here: https://github.com/canndrew/interner/blob/master/src/lib.rs

This works for interning stuff like Strings But if I try to intern something that contains Interned<'i, T>s recursively then the lifetime checker gets upset.

For example this code:

extern crate interner;

#[derive(Hash)]
enum Foo<'i> {
    Bar,
    Baz(interner::Interned<'i, Foo<'i>>),
}

fn main() {
    let interner = interner::Interner::new();
    let interned = interner.intern(Foo::Bar);
    let _ = interner.intern(Foo::Baz(interned));
}

Fails to build with the following error

src/main.rs:11:20: 11:28 error: `interner` does not live long enough
src/main.rs:11     let interned = interner.intern(Foo::Bar);
                                  ^~~~~~~~
src/main.rs:9:11: 13:2 note: reference must be valid for the block at 9:10...
src/main.rs: 9 fn main() {
src/main.rs:10     let interner = interner::Interner::new();
src/main.rs:11     let interned = interner.intern(Foo::Bar);
src/main.rs:12     let _ = interner.intern(Foo::Baz(interned));
src/main.rs:13 }
src/main.rs:10:46: 13:2 note: ...but borrowed value is only valid for the block suffix following statement 0 at 10:45
src/main.rs:10     let interner = interner::Interner::new();
src/main.rs:11     let interned = interner.intern(Foo::Bar);
src/main.rs:12     let _ = interner.intern(Foo::Baz(interned));
src/main.rs:13 }

As far as I can tell, the lifetimes here should be sound. I just want to find a way to convince the compiler that they are. I don’t mind having to lie to the compiler if that’s what it takes (I already had to do that to implement what I’ve got).

Can anyone see a way to fix this?


#2

Have you tried something like this?

enum Foo<'i, 'j> {
    Bar,
    Baz(interner::Interned<'i, Foo<'j>>),
}

#3

I tried various different ways of stacking multiple lifetime variables just hoping something would work. But nothing did.I don’t understand what’s causing this error. The error message says “reference must be valid for this block … but borrowed value is only valid for that block” but afaict this and that are the same.


#4

They aren’t quite. I could make the “block suffix” explicit, like so:

fn main() {
    let interner = interner::Interner::new(); { // <-- here
    let interned = interner.intern(Foo::Bar);
    let _ = interner.intern(Foo::Baz(interned));
}}

The block suffix loosely correlates to the inner block indicated. What’s happening is that you have a borrow of the interner escaping into itself. The borrow is only valid for the block suffix where interner is in scope. However, it has to strictly outlive interner because it has to be valid when interner is being dropped. These are conflicting requirements.

A solution would be to use a higher order function to control the lifetimes. Basically, only give people access to an Interner you own by passing a borrow of it into a function the caller passes in. That way, you can use a different lifetime for the Interner than you use for the Interned returned from it. You just have to ensure that you don’t actually access any of the borrows of the Interner that it contains while it’s getting dropped. I haven’t worked out the details of doing this, though.