Borrowed value does not live long enough when creating reference to parent node

Viewed 72

I'm trying to learn Rust, and for that I decided to implement Depth First Search algorithm.

So far I have the following Node struct:

#[derive(Debug)]
pub struct Node<'a> {
    parent: Option<&'a Node<'a>>,
    position: crate::entities::Position,
}

As you can see every time I create a node there is a reference to its parent.

Now, I have the dfs algorithm:

pub fn dfs<'a>(maze: &crate::entities::Maze) -> Node<'static> {
    let mut traversed = Vec::new();
    let mut frontier = Vec::new();
    let mut seen: HashSet<crate::entities::Position> = HashSet::new();

    let parent = Node {
        parent: None,
        position: maze.start // position is just a holder for row and column
    };
    frontier.push(parent);

    loop {
        if frontier.is_empty() {
            panic!("No solution found!")
        }
        let current: Node<'static> = frontier.pop().expect("There must be a node here");
        let position = current.position;
        if current.position == maze.exit {
            break current;
        } else {
            if !seen.contains(&current.position) {
                let neighbours = maze.get_neighbours(current.position).iter().map(|pos| Node {
                    parent: Some(&current), // this line is not compiling
                    position: *pos
                }).collect::<Vec<Node>>();
                frontier.append(&mut neighbours); 
                traversed.push(current);
            }
        }
        seen.insert(position);
    }
}

But I am getting a compile error:

27 |                     parent: Some(&current),
   |                                   ^^^^^^^ borrowed value does not live long enough

How can I fix that?

1 Answers

Your basic problem is you management of the nodes. Notice that a node is first created by the matrix, then put into the frontier and lastly moved into traversed. This means that you cannot use references to your nodes, since they might move, invalidating the reference.

The solution is to have a central store of node, and then using indices when referring to them. This of course, doesn't play nice with you implementation of Node, but you could change that to use indices instead of references to parents.

Related