Trounble with lifetimes


#1

Hi all,

I’m running into trouble with lifetimes, and am having difficulty finding any documentation regarding lifetime constraints. The code in question is the following:

which features a single line that when uncommented causes me to get the dreaded “does not live long enough” error. I am using arena allocation, and I do not see any quantity that should not outlive the life of the Build::new function. I expect that I am not using the <'b: 'a> syntax properly? Or perhaps there is something confusing going on with the iterator?

I am at a loss even as to how to search for help. :frowning: I have yet to locate the documentation for the <'b: 'a> syntax, which isn’t mentioned in the section of the rust book on lifetimes.


#2

You should remove the 'b:'a constraint, I don’t think it makes sense there (it says 'b is at least as long as 'a, which then means the borrow of &self is longer than 'a, but Builder itself cannot outlive 'a). Something else may complain after that (I only had a cursory look), but let’s tackle that later :slight_smile:


#3

Okay, when I remove that constraint, I need to change the new_file_private method to take a &'a self (this is what I had before trying to debug this problem), and I still have the same error in my Build::new(). :frowning2:

impl<'a> Build<'a> {
    /// Construct a new `Build`.
    pub fn new() -> Build<'a> {
        let b: Build<'a> = Build {
            alloc_files: typed_arena::Arena::new(),
            alloc_rules: typed_arena::Arena::new(),
            files: RefCell::new(std::collections::HashMap::new()),
            rules: RefCell::new(RefSet::new()),
            statuses: StatusMap::new(|| RefCell::new(RefSet::new())),
        };
        for ref f in git::ls_files() {
            // b.new_file_private(f, true); // fixme: causes trouble, "does not live long enough".
            println!("i see {:?}", f);
        }
        b
    }

    fn new_file_private<P: AsRef<std::path::Path>>(&'a self, path: P,
                                                   is_in_git: bool)
                                                   -> &'a File<'a> {
        // If this file is already in our database, use the version
        // that we have.  It is an important invariant that we can
        // only have one file with a given path in the database.
        match self.files.borrow().get(path.as_ref()) {
            Some(f) => return f,
            None => ()
        }
        let f = self.alloc_files.alloc(File {
            // build: self,
            rule: RefCell::new(None),
            path: std::path::PathBuf::from(path.as_ref()),
            children: RefCell::new(RefSet::new()),
            kind: Cell::new(None),
            is_in_git: is_in_git,
        });
        self.files.borrow_mut().insert(& f.path, f);
        f
    }

#4

Remove 'a from &'a self in the new_file_private fn - it’s asking for an impossible borrow scope. What happens if you do that?


#5

If I remove the 'a from the self in new_file_private, I get an error because that function uses the arena allocator, and the lifetime of results from the arena allocator are tied to the lifetime of the reference to the allocator itself, which needs to be 'a.

Perhaps the answer here is that arena allocators don’t work well, or can’t be encapsulated in a struct as I am wanting to do? The struct in question is:

pub struct Build<'a> {
    alloc_files: typed_arena::Arena<File<'a>>,
    alloc_rules: typed_arena::Arena<Rule<'a>>,
    files: RefCell<std::collections::HashMap<&'a Path, &'a File<'a>>>,
    rules: RefCell<RefSet<'a, Rule<'a>>>,

    statuses: StatusMap<RefCell<RefSet<'a, Rule<'a>>>>,
}

where typed_areana is the typed-arena crate, RefSet is my HashSet of references that are wrapped in structs to hash by address. Everything here should have the same lifetime, and I expect the trouble is that typed_arena, requires that its reference have the same lifetime as the things it allocates (which only sort of makes sense), which requires me to have &'a self.

Perhaps I should give up on the idea of “zero cost abstraction” and just store a couple of Vecs and then use indices into those Vecs rather than references. (Which would eliminate the cost of the refcells in the process… but add a bounds check to every “dereference”.)

I’ve fixed my current lifetime errors by simply making the new function not perform any modifications, and moving that into another method with &'a self. But whether this will work when I go ahead and start using this data type is an entirely different question.


#6

The core issue here is that typed_arena::Arena::alloc is declared as fn alloc(&self, value: T) -> &mut T — in other words, the returned reference has the same lifetime as the reference to the Arena itself (i.e. it’s equivalent to fn alloc<'a>(&'a self, value: T) -> &'a mut T).

With no declared lifetime at all, &self has an anonymous lifetime equivalent to the length of the function, which isn’t as long as 'a. Declaring 'b: 'a for self is a good move, but then we get in trouble if we include a call to it in the same new function because 'b (the reference to the newly created Build) isn’t as long as 'a'b ends at the end of new. (My analysis here may be slightly off — please correct if so.)

Try this: make the return type of new_file_private like so: &File<'a>. Let the reference be bound by the lifetime of the reference to the Build itself. You should find this works.

EDIT: I’m wrong; my reduced test case didn’t include the HashMap. The insert inside new_file_private fails because we don’t have the right lifetime on the reference to insert.


#7

I’ve come to the conclusion that using references with arena allocation is a minefield that I just don’t want to step into, being relatively new to rust. I still haven’t found any documentation that would help with any of this, and trial and error (even with helpful advice from here) just isn’t working very well. I’m not quite sure what you’re suggesting, but a few attempts don’t seem to help. It looks like the lifetime language isn’t really sufficient for declaring a set of related data objects that all have a single lifetime, which was what I was hoping to use.

I’m just going to switch over to using plain old data, indexes to an array. It’s annoying having the extra overhead, but I suppose I could use unsafe code to remove that overhead later if I need to.


#8

For what it’s worth, when I’ve hit this in the past, I’ve just allocated the arenas outside the main object (Build in this case), then passed them into a new and held onto a &'a reference.


#9

And does the pain then decrease? My feeling at this point is that I’m writing code I can’t debug, and that doesn’t sound like a great plan. I’m concerned that I’m going to continue having weird lifetime issues if I continue with the arena allocation plan.


#10

Thankfully, yes — the user of the Build object needs to hold onto the actual Arenas itself (since Build only has references), but everything else from then on works perfectly. I did hit a few edge cases when writing functions on the main objects themselves where I started having lifetime “fun”, but it was just simple mislabelling of lifetimes on those functions, not fundamental issues.


#11

It makes sense for returned values to be tied to the arena, and therefore to your struct encapsulating it (the allocator). Your 'a is really putting a lifetime on the File itself not outliving 'a - you should be able to allocate File values holding 'a references where 'a outlives the allocator itself. But as @kivikakk mentioned, the insert into HashMap blocks that from working. Does reversing the lifetime constraints, 'a:'b where 'b is the self borrow, work?


#12

That attempts to declare a new lifetime, 'a, and so fails.


#13

@droundy So I don’t exactly think this is a good idea, but with a macro you can make this a little bit less painful:

macro_rules! with_arena {
    ($name:ident, $p:path) => {
        let a = Arena::new();
        let $name = ($p)(&a);
    };
    ($name:ident, $p:path, $($a:expr),*) => {
        let a = Arena::new();
        let $name = ($p)(&a, $($a),*);
    };
}

fn main() {
    with_arena!(b, Build::new);
    // `b` is now a Build local with an attached Arena.
}

This assumes Build::new takes a single &'a Arena<_> as its argument. You may want to modify it to create two Arenas in the macro; in essence all this does is hide away creating the Arena in the method body, but that is kind of nice. The type is inferred by the compiler as usual. The name a won’t conflict due to the hygienic macro system.


#14

@kivikakk I agree: probably not a good idea! :slight_smile: I’ve just created a function that returns an appropriate tuple of arenas, so it’s an easy extra line of code to create them first before calling Build::new(&arenas).


#15

Actually, it’s already implied that 'a outlives any self borrow. Ok, will try to play with this later when I’m at a computer.


#16

Ok, thinking a bit more about this, this is basically trying to store a self-reference (File owned by self, and &File being stored in self), which doesn’t work. But moving the arenas outside breaks this relationship, and makes it work.


#17

For those who are curious, here is a link to the documentation of what I’ve worked out so far, mostly based on the advise of @kivikakk

http://facio.gitlab.io/fac/doc/fac/build/struct.Build.html