Error when trying to borrow an element of a vector

[benlellouch]

I am trying to create a simple breadth-first search where the Blockworld struct represents a state of the problem (player position and block positions). Each blockworld object stores a reference of its parent node to create a tree of states.

pub struct Blockworld<'a> {
    pub root: bool,
    pub parent: Option<&'a Blockworld<'a>>,
    player: Pos,
    pub blocks: [Block; 3],
    depth: i32,
    pub move_taken: Option<Direction>,
    pub possible_moves: Vec<Direction>,
    manhattan_distance: i32,
}

bfs.rs

extern crate queues;

use crate::block_world::*;
use crate::search;
use queues::*;

pub struct BFS<'a> {
    fringe: Queue<Blockworld<'a>>,
    expanded: Vec<Blockworld<'a>>,
    expanded_nodes: i32,
    root_node: Blockworld<'a>,
}

impl<'a> BFS<'a> {
    pub fn new(node: Blockworld<'a>) -> Self {
        BFS {
            fringe: queue![],
            expanded: Vec::new(),
            expanded_nodes: 0,
            root_node: node,
        }
    }

    pub fn run(&mut self) {
        self.fringe.add(self.root_node.clone());
        while self.fringe.size() > 0 {
            let current = self.fringe.remove().unwrap();
            if search::check_for_solution(&current) {
                let mut stack = Vec::new();
                search::print_solution(&current, &mut stack);
                return;
            }

            self.expanded.push(current);

            self.expand(&self.expanded[self.expanded.len() - 1]); //error
        }
    }

    fn expand(&mut self, node: &'a Blockworld) {
        for direction in &node.possible_moves {
            self.fringe.add(Blockworld::new(node, direction.clone()));
        }
    }
}

Gives me this error when I try to compile:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/bfs.rs:43:26
   |
43 |             self.expand(&self.expanded[self.expanded.len()-1]);
   |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 28:5...
  --> src/bfs.rs:28:5
   |
28 | /     pub fn run(&mut self)
29 | |     {
30 | |         self.fringe.add(self.root_node.clone());
31 | |         while self.fringe.size() > 0
...  |
46 | |         }
47 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/bfs.rs:43:26
   |
43 |             self.expand(&self.expanded[self.expanded.len()-1]);
   |                          ^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 14:6...
  --> src/bfs.rs:14:6
   |
14 | impl<'a> BFS<'a>
   |      ^^
note: ...so that the types are compatible
  --> src/bfs.rs:43:18
   |
43 |             self.expand(&self.expanded[self.expanded.len()-1]);
   |                  ^^^^^^
   = note: expected `&mut bfs::BFS<'_>`
              found `&mut bfs::BFS<'a>`

I use expanded: Vec<Blockworld<'a>> to store current so that that node lives long enough so that its children nodes can access it through the reference they store in parent (This is used so that when a solution to the BFS is found, I can easily traverse up the tree and print the solution). If there is a more elegant way of storing those blockworld objects (there probably is) I would also be happy to hear it.

Here's the MRE i've created to reproduce the bug:

struct Node<'a>
{
    parent_node: Option<&'a Node<'a>>
}

impl<'a> Node<'a>
{
    fn new_root() -> Self
    {
        Node
        {
            parent_node: None
        }
    }

    fn new (parent: &'a Node) -> Self
    {
        Node
        {
            parent_node: Some(parent)
        }
    }
}

struct Search<'a>
{
    fringe: Vec<Node<'a>>,
    expanded_nodes: Vec<Node<'a>>
}

impl<'a> Search<'a>
{
    fn new() -> Self
    {
        Search
        {
            fringe: Vec::new(),
            expanded_nodes: Vec::new()
        }
    }
    
    fn run(&mut self, root: Node<'a>)
    {
        self.fringe.push(root);
        
        while self.fringe.len() > 0
        {
            let current = self.fringe.pop().unwrap();
            
            // do stuff with current such checking for solution etc ...
            
            self.expanded_nodes.push(current);
            
            self.expand_node(&self.expanded_nodes[self.expanded_nodes.len()-1]);
        }
    }
    
    fn expand_node (&mut self, parent_node: &'a Node)
    {
        self.fringe.push(Node::new(parent_node));
    }
}

fn main() {
    let initial_node = Node::new_root();
    let search = Search::new();
    search.run(initial_node);
}

with it's associated error message

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/lib.rs:54:31
   |
54 |             self.expand_node(&self.expanded_nodes[self.expanded_nodes.len()-1]);
   |                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 42:5...
  --> src/lib.rs:42:5
   |
42 | /     fn run(&mut self, root: Node<'a>)
43 | |     {
44 | |         self.fringe.push(root);
45 | |         
...  |
55 | |         }
56 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:54:31
   |
54 |             self.expand_node(&self.expanded_nodes[self.expanded_nodes.len()-1]);
   |                               ^^^^^^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 31:6...
  --> src/lib.rs:31:6
   |
31 | impl<'a> Search<'a>
   |      ^^
note: ...so that the types are compatible
  --> src/lib.rs:54:18
   |
54 |             self.expand_node(&self.expanded_nodes[self.expanded_nodes.len()-1]);
   |                  ^^^^^^^^^^^
   = note: expected  `&mut Search<'_>`
              found  `&mut Search<'a>`

I hope this helps!