Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

rust - Cyclic reference of RefCell borrows in traversal

I'm learning Rust and tried coding a doubly-linked list. However, I'm stuck already at a typical iterative traversal implementation. I'm getting the impression that the borrow checker / drop checker is too strict and cannot infer the correct lifetime for the borrow when it crosses the function boundary from RefCell. I need to repeatedly set a variable binding (curr in this case) to the borrow of its current contents:

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

pub struct LinkedList<T> {
    head: Option<Rc<RefCell<LinkedNode<T>>>>,
    // ...
}

struct LinkedNode<T> {
    value: T,
    next: Option<Rc<RefCell<LinkedNode<T>>>>,
    // ...
}

impl<T> LinkedList<T> {
    pub fn insert(&mut self, value: T, idx: usize) -> &mut LinkedList<T> {
        // ... some logic ...

        // This is the traversal that fails to compile.
        let mut curr = self.head.as_ref().unwrap();
        for _ in 1..idx {
            curr = curr.borrow().next.as_ref().unwrap()
        }

        // I want to use curr here.
        // ...
        unimplemented!()
    }
}

The compiler complains:

Without NLL

error[E0597]: borrowed value does not live long enough
  --> src/lib.rs:22:20
   |
22 |             curr = curr.borrow().next.as_ref().unwrap()
   |                    ^^^^^^^^^^^^^ temporary value does not live long enough
23 |         }
   |         - temporary value dropped here while still borrowed
...
28 |     }
   |     - temporary value needs to live until here
   |
   = note: consider using a `let` binding to increase its lifetime

With NLL

error[E0716]: temporary value dropped while borrowed
  --> src/lib.rs:22:20
   |
22 |             curr = curr.borrow().next.as_ref().unwrap()
   |                    ^^^^^^^^^^^^^
   |                    |
   |                    creates a temporary which is freed while still in use
   |                    a temporary with access to the borrow is created here ...
23 |         }
   |         -
   |         |
   |         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::Ref<'_, LinkedNode<T>>`
   |
   = note: consider using a `let` binding to create a longer lived value
   = note: The temporary is part of an expression at the end of a block. Consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped.

I would really appreciate a iterative solution (non-recursive) to this problem.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

You can clone Rc to avoid lifetime issues:

let mut curr = self.head.as_ref().unwrap().clone();
for _ in 1..idx {
    let t = curr.borrow().next.as_ref().unwrap().clone();
    curr = t;
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...