CODEWITHSUNDEEP
rustborrow-checker
wingerse
wingerse

Reputation: 3796

Compiler thinks a borrow is alive when it isn't

I've got this code of an arena where allocation gives you an index and you use the same index to get the object later.

struct Node<'a>(i32, Option<&'a Node<'a>>);

struct Arena<'a>(Vec<Node<'a>>);

impl<'a> Arena<'a> {
    fn alloc(&'a mut self, node: Node<'a>) -> usize {
        let index = self.0.len();
        self.0.push(node);
        index
    }
    fn get(&'a mut self, index: usize) -> &'a mut Node<'a> {
        &mut self.0[index]
    }
}

fn main() {
    let mut arena = Arena(vec![]);
    let x = arena.alloc(Node(1, None));
    println!("{}", arena.get(x).0)
}

self is using lifetime 'a because rust gives another error otherwise:

cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements

The return value of alloc is just a usize so the borrow of self should be temporary. However, for some reason, when I call arena.get in the println, rust thinks arena is still mutably borrowed and gives me this error:

error[E0499]: cannot borrow `arena` as mutable more than once at a time
  --> src/main.rs:19:20
   |
18 |     let x = arena.alloc(Node(1, None));
   |             ----- first mutable borrow occurs here
19 |     println!("{}", arena.get(x).0)
   |                    ^^^^^
   |                    |
   |                    second mutable borrow occurs here
   |                    first borrow later used here

So why is this happening?

Note: I know I can use indices in Option and forget about this issue, but I still want to know why rust think arena is mutably borrowed.

Upvotes: 0

Views: 108

Answers (1)

user2722968
user2722968

Reputation: 16475

Because that's what you are telling the compiler. Two steps:

In the line

fn alloc(&'a mut self, node: Node<'a>) -> usize

there is some lifetime 'a for Node; also, you are telling the compiler that the mutable reference &mut self will have the same lifetime 'a, via &'a mut self. That is, the &mut self reference will live for as long as the lifetime-parameter of Node.

Second, in the line arena.alloc(Node(1, None)), the literal instance of Node you are creating has no lifetime shorter than 'static, so it's a Node<'static>. This means arena is a Arena<'static>.

Where it all goes wrong is when these two combine: Since you declared &mut self to have the same lifetime as Node, the compiler has to deduce that the &mut self is a &'static mut self, because 'a is 'static. So, once the first borrow occurs in main, no further borrows are ever allowed and you are officially stuck.

AFAICS there is no need for those lifetime annotations anyway. If you change the signatures to simply

fn alloc(&mut self, node: Node<'a>) -> usize {
fn get(&mut self, index: usize) -> &mut Node<'a> {

you example compiles, as the compiler is free to assign lifetimes shorter than whatever Node carries to the borrow of Arena.

Upvotes: 3

Related Questions