Confused by `temporary value dropped while borrowed`

Hello, I have a noob question about the following codes.
With these type definitions:

use std::rc::Rc;
use std::cell::RefCell;

type RcNode = Option<Rc<RefCell<TreeNode>>>;
fn new(i: i32) -> RcNode { Some(Rc::new(RefCell::new( TreeNode::new(i) ))) }

struct TreeNode {
    val: i32,
    left: RcNode,
    right: RcNode,
}
impl TreeNode { fn new(i: i32) -> Self { TreeNode{val: i, left: None, right: None} } }

Why does this compiles:

fn f() -> RcNode {
    let mut tree = None;
    {
        let mut buf = Vec::new();
    
        let r = &mut tree;
        *r = new(1);
        buf.push(&*r);
        
        let r = &mut (r.as_ref().unwrap().borrow_mut().left);
        *r = new(2);
        buf.push(&*r);
    }
    tree
}

but not this:

fn f() -> RcNode {
    let mut tree = None;
    {
        let mut buf = Vec::new();
    
        let mut r = &mut tree;
        *r = new(1);
        buf.push(&*r);
        
        r = &mut (r.as_ref().unwrap().borrow_mut().left);      <---change here
        *r = new(2);
        buf.push(&*r);
    }
    tree
}

error[E0716]: temporary value dropped while borrowed
  --> src/lib.rs:23:19
   |
23 |         r = &mut (r.as_ref().unwrap().borrow_mut().left);
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^      -
   |                   |                                     |
   |                   |                                     temporary value is freed at the end of this statement
   |                   |                                     ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `std::cell::RefMut<'_, TreeNode>`
   |                   creates a temporary which is freed while still in use
   |                   a temporary with access to the borrow is created here ...
   |
   = note: consider using a `let` binding to create a longer lived value

This also fails:

fn f() -> RcNode {
    let mut tree = None;
    {
        let mut buf = Vec::new();
    
        let r = &mut tree;
        *r = new(1);
        buf.push(&*r);
        
        let r = &mut (buf[0].as_ref().unwrap().borrow_mut().left);      <---change here
        *r = new(2);
        buf.push(&*r);
    }
    tree
}

error[E0716]: temporary value dropped while borrowed
  --> src/lib.rs:23:19
   |
23 |     let r = &mut (buf[0].as_ref().unwrap().borrow_mut().left);
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                   |
   |                   creates a temporary which is freed while still in use
   |                   a temporary with access to the borrow is created here ...
...
26 |     }
   |     -
   |     |
   |     temporary value is freed at the end of this statement
   |     ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `std::cell::RefMut<'_, TreeNode>`
   |
   = note: consider using a `let` binding to create a longer lived value

So I modifies accordingly:

fn f() -> RcNode {
    let mut tree = None;
    {
        let mut buf = Vec::new();
    
        let mut r = &mut tree;
        *r = new(1);
        buf.push(&*r);
        
        let mut temp = buf[0].as_ref().unwrap().borrow_mut();      <---change here
        r = &mut (temp.left);
        *r = new(2);
        buf.push(&*r);

        drop(buf);      <---change here
    }
    tree
}

error[E0597]: `temp` does not live long enough
  --> src/lib.rs:25:23
   |
25 |         r = &mut (temp.left);
   |                       ^^ borrowed value does not live long enough
...
29 |     }
   |     -
   |     |
   |     `temp` dropped here while still borrowed
   |     borrow might be used here, when `temp` is dropped and runs the destructor for type `std::cell::RefMut<'_, TreeNode>`

I don't understand the error, as the only place that can use the borrow of temp is buf.drop(), which has been dropped before temp is dropped. Reference can't call destructor so it is impossible for r to use temp.

How should I correct the code? Thanks!

Others will have to comment on your specific code. Which is complicated enough to give me headache.

But common advice to those trying to build trees, linked lists etc is to read this:
https://rust-unofficial.github.io/too-many-lists/

Thanks!

I'll explain my code's intention. The idea is to build a tree from root to leaves in preorder fashion. I use a buffer to record already created nodes so that I can insert into the right subtrees in the future.
For example to create tree

   /   2
1
   \   3

My code will do so:

  /        /   2        /   2
1    -> 1          -> 1
  \        \            \   3   

so

let r = &mut tree;
*r = new(1);
buf.push(&*r);

constructs and remembers the root node.

and this

let r = &mut (r.as_ref().unwrap().borrow_mut().left);
*r = new(2);
buf.push(&*r);

constructs and remembers the left node.
Because r always refers to the current inserted node, the only way to insert to the right tree is use the previously saved root node.

My whole program trys to programmatically construct the tree from input node data:

for (value, depth) in node_data_iter {
    if depth == current_depth + 1 {
        *r = new(value);
         buf.push(&*r);
         r = &mut (r.as_ref().unwrap().borrow_mut().left);
    }
    // ... traceback the tree using the saved reference in `buf` so I can insert to those empty right subtrees
}

Anyway, I will try reading the article. Thanks for your help!

If this is a tree, are you sure you need Rc<RefCell> and dynamic borrowing? Wouldn't you be able to just use Box? (Here's an earlier answer of mine to a different question where OP also needed to build a tree level by level, you can check how I solved that.)

This is a good question, and the answer is that let bindings are special. Consider this snippet from the rust reference:

let x = &temp() . Here, the same temporary is being assigned into x , rather than being passed as a parameter, and hence the temporary's lifetime is considered to be the enclosing block.
link

This means that your first example is equivalent to this:

    let temp = r.as_ref().unwrap().borrow_mut();
    let r = &mut temp.left;
    ...
} // temp is dropped here

But your second example does not use a let binding, so the temporary is dropped at the end of the expression, so it is equivalent to this:

    {
        let temp = r.as_ref().unwrap().borrow_mut();
        r = &mut temp.left;
    } // temp is dropped here
    ... // use of r happens here
}
3 Likes

Thanks! So I understand the let binding extends the lifetime of a temporary value behind a reference to the enclosing scope, but I wonder why the third example doesn't work.

        let mut buf = Vec::new();
    
        let mut r = &mut tree;
        *r = new(1);
        buf.push(&*r);
        
        let mut temp = buf[0].as_ref().unwrap().borrow_mut();   // explictly extends the lifetime to the whole scope
        r = &mut (temp.left);
        ...
        
        //  explicitly specify drop order
        drop(buf);
        drop(r);
        drop(temp);
    } 

even if I write out the drop order, borrow checker still complains temp does not live long enough.

Statically specifying drop order also fails:

    {
        let (mut temp, mut r, mut buf);
        buf = Vec::new();
    
        r = &mut tree;
        *r = new(1);
        buf.push(&*r);
        
        temp = buf[0].as_ref().unwrap().borrow_mut();
        r = &mut (temp.left);
        *r = new(2);
        buf.push(&*r);

        // implicit drop order
        // drop(buf);
        // drop(r);
        // drop(temp);
    }


I'm trying to use Rust to solve problems on Leetcode, and some problems about tree and graph seems to only permit using Rc. I'll take a look. Thanks anyway!

Serendipitously, I just read about how LeetCode handles their Rust exercises: https://github.com/pretzelhammer/rust-blog/blob/master/posts/learning-rust-in-2020.md#leetcode

Sure, it will still separate the temporary like this:

    ...
    let mut temp = buf[0].as_ref().unwrap().borrow_mut();
    let r = &mut temp.left;
    *r = new(2);
    buf.push(&*r);
}

The thing that happens here is that if a variable foo contains a borrow of bar, then foo must be dropped before bar. So:

  1. Since r is a reference into temp, the buf.push(&*r) call makes buf contain a reference into temp, so buf must be dropped before temp.
  2. But since temp is a borrow of buf, you must drop temp before buf.

These requirements together means that it wont compile regardless of the order they are dropped in.

2 Likes

Sorry for the late reply!
So my code actually introduces some cyclic lifetime dependency where

        buf.push(&*r);    // buf <= r
        
        temp = buf[0].as_ref().unwrap().borrow_mut();    // temp <= buf
        r = &mut (temp.left);    // r <= temp

makes buf's lifetime derive from r and r's derive from temp and finally temp from buf.

But I'm still confused why the compiler can't resolve those lifetimes to be equal. As I know, Rust's current lifetime dependency is not strict, which means the above inequalities have an equal solution. I've also read nomicon's drop check article which says "For a generic type to soundly implement drop, its generics arguments must strictly outlive it." So at first I thought it's Vec's drop implementation that causes the problem with the equal lifetimes. I try to replace the Vec with only ref:

        let mut single_ref;

        ...        

        single_ref = &*r;    // single_ref <= r
        
        let mut temp = single_ref.as_ref().unwrap().borrow_mut();    // temp <= single_ref
        r = &mut (temp.left);    // r <= temp

But it still fails.

Also, the original "let binding" version:

        buf.push(&*r);
        
        let r = &mut (r.as_ref().unwrap().borrow_mut().left);

as said above, is equivalent to

        buf.push(&*r);    // buf <= r

        let temp = r.as_ref().unwrap().borrow_mut();    // temp <= r
        let r = &mut temp.left;    // r <= temp
        ...
    } // temp is dropped here

seems like the compiler knows r and temp are created together and therefore have equal lifetimes.

After some experiments, I think I understand the problem. The complier rejects my code just because of drop check.

Following code compile:

struct S;
impl S {
    fn id(&self) -> &S { self }
    fn rf(&self) -> Ref { Ref(self) }
}
struct Ref<'a>(&'a S);
impl<'a> Ref<'a> {
    fn get(&self) -> &S { self.0 }
}
// impl<'a> Drop for Ref<'a> {
//     fn drop(&mut self) {}
// }
fn f() {
    let base = S; 
    let mut a = &base;
    let b = a.id();    // b borrowing a
    let c = b.rf();    // c borrowing b
    a = c.get();       // a borrowing c
}

until I uncomment the Drop impl:

error[E0597]: `c` does not live long enough
  --> src/lib.rs:66:9
   |
66 |     a = c.get();       // a borrowing c
   |         ^ borrowed value does not live long enough
67 | }
   | -
   | |
   | `c` dropped here while still borrowed
   | borrow might be used here, when `c` is dropped and runs the `Drop` code for type `Ref`

That's the same reason why my code doesn't pass:

fn f() -> RcNode {
    let mut tree = None;
    {
        let mut single_ref;
    
        let mut r = &mut tree;
        let mut temp;
        *r = new(1);
        single_ref = &*r;    // single_ref <= r
        
        temp = single_ref.as_ref().unwrap().borrow_mut();    // temp <= single_ref
        r = &mut (temp.left);    // r <= temp
        *r = new(2);
         
        // drop(temp);      // temp: RefMut drops here, it seems the borrow checker doesnt trust it!
        // drop(r);
        // drop(single_ref);
    }
    tree
}

I guess the ergonomics around the drop check could be further improved. Anyway, Thanks everyone for helping me out on this one!

I feel your frustration!

It does seem like two or more objects borrowing each other should just be able to exist happily within the same lifetime and all be able to be deallocated together at the same instant. Alas, it doesn't work that way.

Under the hood, there are very good reasons for the way it does work. Custom Drop trait implementations being one of the reasons.

I just went through a lot of quite a bit of tribulation trying to build an object that could be self-referential. With the help of many wonderful people on this message board, I think a safe implementation emerged, and I plan to publish it as a crate when I can spare a half-day soon. The odyssey is here: TrashPool to retain temporaries past the end of a scope

Another idea for self-referential objects (or sets of multiple objects) is the approach taken by the rental crate: https://docs.rs/rental/0.5.4/rental/ It can smooth over some of the rough edges using macros.

That's an interesting solution. I will take a closer look. Thanks!
But for this moment as I'm just writing those one-time codes on Leetcode, I'll take the simple but dangerous route : unsafe.

fn f() -> RcNode {
    let mut tree = None;
    {
        let (mut r, mut buf);
        buf = Vec::new();
    
        r = &mut tree as *mut RcNode;    // raw pointer have no lifetime, and is therefore not a borrow
        unsafe{ 
            *r = new(1); 
            buf.push((&*r).as_ref().unwrap().borrow_mut());    // dereferencing raw pointer produces unbounded lifetime!
            // buf no longer borrow r, no more cyclic borrow
        }
        
        r = &mut (buf[0].left) as *mut RcNode;
        unsafe{
            *r = new(2);
            buf.push((&*r).as_ref().unwrap().borrow_mut());
        }
        // SAFETY: buf.drop() will not touch the stored reference, no use after deallocate
    }
    tree
}

Still, I'd like to have a more precise builtin borrow checker, the current compiler error is really confusing without reading the nomicon. The good news is that "Future versions of the language may make the analysis more precise, to reduce the number of cases where sound code is rejected as unsafe."

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.