Rust Lifetime for parameter explicit but not found in iter()

Question

I'm trying to write a tree in rust, here is the Node:

#[derive(Debug)]
struct Node<'a> {
    player_id: i8,
    visits : i32,
    score : i32,
    children : Vec<Node<'a>>,
    parent: Option<&'a mut Node<'a>>,
    action: usize,
}

impl Node<'_> {
    pub fn is_leaf(&self) -> bool {
        return self.children.is_empty()
    }
}

I am trying to add children for every move possible in game:

fn expand_children <'a>(node: & 'a mut Node<'a>, game : &GameState) {
    game.legal_moves().iter().for_each(
        |action|
        node.children.push(
            Node::<'a> {
                parent: Some(node),
                action : *action,
                player_id: game.curr_player(),
                visits: 0,
                score: 0,
                children: vec![]
            }
        )
    )
}

This is the error I get:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src/MCTS.rs:59:25
   |
59 |                 parent: Some(node),
   |                         ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'_` as defined here...
  --> src/MCTS.rs:56:9
   |
56 | /         |action|
57 | |         node.children.push(
58 | |             Node::<'a> {
59 | |                 parent: Some(node),
...  |
65 | |             }
66 | |         )
   | |_________^
note: ...so that closure can access `node`
  --> src/MCTS.rs:59:30
   |
59 |                 parent: Some(node),
   |                              ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined here...
  --> src/MCTS.rs:54:21
   |
54 | fn expand_children <'a>(node: & 'a mut Node<'a>, game : &GameState) {
   |                     ^^
note: ...so that the expression is assignable
  --> src/MCTS.rs:59:25
   |
59 |                 parent: Some(node),
   |                         ^^^^^^^^^^
   = note: expected `Option<&'a mut Node<'a>>`
              found `Option<&mut Node<'a>>`

I thought I did set the lifetime of node as 'a in the function parameters as its &'a mut Node<'a>. How is it possible that the compiler does not find it on compiletime? Or am I missing something.. I know that the error message should tell me whats wrong but I dont think I understand it very well..

Answer 1

How is it possible that the compiler does not find it on compiletime?

The compiler did find it, and it found it unsatisfactory. And the compiler is right ;)

To understand the deeper background, I strongly advice reading:

• https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
• Why can't I store a value and a reference to that value in the same struct?
• https://rust-unofficial.github.io/too-many-lists/

I will briefly try to explain the problem. If you don't understand parts of what I say, please read at least the chapter in the Rust book, it really does explain a lot about how references work.

The main problem is you cannot set the lifetime of an object via lifetime annotation. You can only describe how long it lives, but you cannot change it. An item lives until it doesn't. A reference does not keep an object alive, the lifetime annotation on it only specifies how long an object stored in it must be alive so it can be stored in it in the first place.

Further, only one mutable reference to an object may exist at any time.

With that knowledge you can probably already kind of see why parent: Option<&'a mut Node<'a>> is a problem. First, assuming you have more than one child, there are already multiple mutable references to the parent node, which can't be.

Second, the fact that the parent stores the children, and the children contain a reference to the parent forms a circular reference. Circular references are almost impossible in safe Rust. To know more about why, read the second and the third link.

So first off: don't use references in this case. Go one level higher and use smart pointers / refcounters. Maybe use Rc/Arc combined with Weak in the reverse direction (to avoid circular references; although if possible just avoid the reverse direction entirely). Further, you will need RefCell/Mutex for interiour mutability, as both Rc/Arc only expose immutable objects.

But again, look at the too-many-lists link, those problems are described there in great detail.