When reading
Learning Rust With Entirely Too Many Linked Lists > A Bad Safe Deque > Iteration Chapter, I'm confused.
For singly linked list,
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| { // &'a Node<T>
self.next = node.next.as_deref();
&node.elem
})
}
}
it's natural for me to understand self.next = node.next.as_deref();
works: the lifetime of reference doesn't change when passing. i.e.
node: &'a Node<T>
&node.next: &'a Link<T>
node.next.as_deref(): Option<&'a Node<T>>
But for double linked list,
pub struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
elem: T,
next: Link<T>,
prev: Link<T>,
}
pub struct Iter<'a, T>(Option<Ref<'a, Node<T>>>);
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter(self.head.as_ref().map(|head| head.borrow()))
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = Ref<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref| { // Ref<'a, Node<T>>
self.0 = node_ref.next.as_ref().map(|head| head.borrow());
Ref::map(node_ref, |node| &node.elem)
})
}
}
the error is:
error[E0521]: borrowed data escapes outside of closure
--> src/lib.rs:59:17
|
57 | fn next(&mut self) -> Option<Self::Item> {
| --------- `self` declared here, outside of the closure body
58 | self.0.take().map(|node_ref| {
59 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ^^^^^^ -------- borrow is only valid in the closure body
| |
| reference to `node_ref` escapes the closure body here
error[E0505]: cannot move out of `node_ref` because it is borrowed
--> src/lib.rs:60:26
|
57 | fn next(&mut self) -> Option<Self::Item> {
| --------- lifetime `'1` appears in the type of `self`
58 | self.0.take().map(|node_ref| {
59 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ------ -------- borrow of `node_ref` occurs here
| |
| assignment requires that `node_ref` is borrowed for `'1`
60 | Ref::map(node_ref, |node| &node.elem)
| ^^^^^^^^ move out of `node_ref` occurs here
Rust failed to understand the reference-passing relation
node_ref: Ref<'a, Node<T>>
&node_ref.next: &'a Link<T>
node_ref.next.as_ref(): Option<&'a Rc<RefCell<Node<T>>>>
node_ref.next.as_ref().map(|head| head.borrow()): Option<Ref<'a, Node<T>>>
I've searched around, and only to conclude that Rust seems to reborrow[1] in &node_ref.next: &'b Link<T>
(where 'a: 'b
).
I tried narrowing it with a function:
fn f<'a, T>(opt: &mut Option<Ref<'a, Node<T>>>, node_ref: Ref<'a, Node<T>>) {
*opt = node_ref.next.as_ref().map(|head| head.borrow());
}
error[E0597]: `node_ref` does not live long enough
--> src/lib.rs:66:16
|
65 | fn f<'a, T>(opt: &mut Option<Ref<'a, Node<T>>>, node_ref: Ref<'a, Node<T>>) {
| -- lifetime `'a` defined here
66 | *opt = node_ref.next.as_ref().map(|head| head.borrow());
| ^^^^^^^^ ------------- returning this value requires that `node_ref` is borrowed for `'a`
| |
| borrowed value does not live long enough
67 | }
| - `node_ref` dropped here while still borrowed
Well, hard to understand again...
The code of interest is on playground.
-
if this is the case, I suspect the code regarding singly linked list should fail too. âŠī¸