How do I move an Arena without invalidating its references?

help
1

I'm trying to implement A* for a game. To do so, I'm creating an AStar struct. The struct retains ownership of every node it discovers and manages all the data structures A* needs to work. I need to hold onto every node I find until the algorithm terminates (and nodes are expensive to copy in the real code), so I'm storing nodes in a TypedArena and using the references in the A* data structures.

Complete example follows:

// main.rs
extern crate typed_arena;

use std::collections::{BinaryHeap};
use typed_arena::Arena;

#[derive(Ord, Eq, PartialEq, PartialOrd)]
struct Node {}

struct AStar<'a> {
    arena: Arena<Node>,
    f_score: BinaryHeap<(i8, &'a Node)>,
}

impl<'a> AStar<'a> {
    pub fn new(start: Node) -> Self {
        let arena = Arena::new();
        let owned_start_ref: &Node = arena.alloc(start);
        let mut f_score = BinaryHeap::new();
        f_score.push((0, owned_start_ref));

        AStar {
            arena: arena,
            f_score: f_score,
        }
    }
}

fn main() {
    let solver = AStar::new(Node{});
}

When I try to compile with rustc 1.16, I get this error:

error: `arena` does not live long enough
  --> src/main.rs:17:38
   |
17 |         let owned_start_ref: &Node = arena.alloc(start);
   |                                      ^^^^^ does not live long enough
...
25 |     }
   |     - borrowed value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the body at 15:36...
  --> src/main.rs:15:37
   |
15 |     pub fn new(start: Node) -> Self {
   |

Why does moving my TypedArena seem to invalidate references that it previously returned? What's the correct way to implement this struct? Is there something wrong in the way I'm modeling my data?

2

After following this example, I was able to get my example to work. The most important change is that the Arena is passed to AStar's constructor, and AStar merely holds a reference to it:

struct AStar<'a> {
    arena: &'a Arena<Node>,
    f_score: BinaryHeap<(i8, &'a Node)>,
}

Now it's easy for me to write that the lifetime of the arena matches up with the lifetimes of the other data structures.

2 Likes