Variable in loop does not live long enough

Question

I've been playing with Rust for the past few days, and I'm still struggling with the memory management (figures).

I wrote a simple project that creates a hierarchy of structs ("keywords") from lexing/parsing a text file.

A keyword is defined like this:

pub struct Keyword<'a> {
    name: String,
    code: u32,
    parent: Option<&'a Keyword<'a>>,
}

which is my equivalent for this C struct:

typedef struct Keyword Keyword;

struct Keyword {
    char* name;
    unsigned int code;
    Keyword* parent;
};

A hierarchy is just a container for keywords, defined like this:

pub struct KeywordHierarchy<'a> {
    keywords: Vec<Box<Keyword<'a>>>,
}

impl<'a> KeywordHierarchy<'a> {
    fn add_keyword(&mut self, keyword: Box<Keyword<'a>>) {
        self.keywords.push(keyword);
    }
}

In the parse function (which is a stub of the complete parser), I recreated the condition that spawns the lifetime error in my code.

fn parse<'a>() -> Result<KeywordHierarchy<'a>, String> {

    let mut hierarchy = KeywordHierarchy { keywords: Vec::new() };

    let mut first_if = true;
    let mut second_if = false;

    while true {

        if first_if {

            // All good here.

            let root_keyword = Keyword {
                name: String::from("ROOT"),
                code: 0,
                parent: None,
            };
            hierarchy.add_keyword(Box::new(root_keyword));

            first_if = false;
            second_if = true;
        }

        if second_if {

            // Hierarchy might have expired here?

            // Find parent
            match hierarchy.keywords.iter().find(|p| p.code == 0) {
                None => return Err(String::from("No such parent")),
                Some(parent) => {

                    // If parent is found, create a child
                    let child = Keyword {
                        name: String::from("CHILD"),
                        code: 1,
                        parent: Some(&parent),
                    };
                    hierarchy.add_keyword(Box::new(child));
                }
            }

            second_if = false;
        }

        if !first_if && !second_if {
            break;
        }
    }

    Ok(hierarchy)

}

There's a while loop that goes through the lexer tokens.

In the first if, I add the ROOT keyword to the hierarchy, which is the only one that doesn't have a parent, and everything goes smoothly as expected.

In the second if, I parse the children keywords and I get a lifetime error when invoking KeywordHierarchy.add_keyword().

hierarchy.keywords` does not live long enough

Could you guys recommend an idiomatic way to fix this?

Cheers.

P.S. Click here for the playground

Answer 1

The immediate problem I can see with your design is that your loop is going to modify the hierarchy.keywords vector (in the first_if block), but it also borrows elements from the hierarchy.keywords vector (in the second_if block).

This is problematic, because modifying a vector may cause its backing buffer to be reallocated, which, if it were allowed, would invalidate all existing borrows to the vector. (And thus it is not allowed.)

Have you considered using an arena to hold your keywords instead of a Vec? Arenas are designed so that you can allocate new things within them while still having outstanding borrows to elements previously allocated within the arena.

---

Update: Here is a revised version of your code that illustrates using an arena (in this case a rustc_arena::TypedArena, but that's just so I can get this running on the play.rust-lang.org service) alongside a Vec<&Keyword> to handle the lookups.

https://play.rust-lang.org/?gist=fc6d81cb7efa7e4f32c481ab6482e587&version=nightly&backtrace=0

The crucial bits of code are this:

First: the KeywordHierarchy now holds a arena alongside a vec:

pub struct KeywordHierarchy<'a> {
    keywords: Vec<&'a Keyword<'a>>,
    kw_arena: &'a TypedArena<Keyword<'a>>,
}

Second: Adding a keyword now allocates the spot in the arena, and stashes a reference to that spot in the vec:

fn add_keyword(&mut self, keyword: Keyword<'a>) {
    let kw = self.kw_arena.alloc(keyword);
    self.keywords.push(kw);
}

Third: the fn parse function now takes an arena (reference) as input, because we need the arena to outlive the stack frame of fn parse:

fn parse<'a>(arena: &'a TypedArena<Keyword<'a>>) -> Result<KeywordHierarchy<'a>, String> {
    ...

Fourth: To avoid borrow-checker issues with borrowing hierarchy as mutable while also iterating over it, I moved the hierarchy modification outside of your Find parent match:

        // Find parent
        let parent = match hierarchy.keywords.iter().find(|p| p.code == 0) {
            None => return Err(String::from("No such parent")),
            Some(parent) => *parent, // (this deref is important)
        };
        // If parent is found, create a child
        let child = Keyword {
            name: String::from("CHILD"),
            code: 1,
            parent: Some(parent),
        };
        hierarchy.add_keyword(child);
        second_if = false;