How to get a rc::Ref<T> reference to a node pointed by a rc::Weak<RefCell<T>>?

Viewed 239

I'm writing a linked list where there are weak references linking the previous node.

use std::cell::{Ref, RefCell, RefMut};
use std::rc::{Rc, Weak};

pub struct List<T> {
    head: NextLink<T>,
    tail: PrevLink<T>,
}

type NextLink<T> = Option<Rc<RefCell<Node<T>>>>;
type PrevLink<T> = Weak<RefCell<Node<T>>>;

struct Node<T> {
    elem: T,
    prev: PrevLink<T>,
    next: NextLink<T>,
}

impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            elem,
            prev: Weak::new(),
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        Self {
            head: None,
            tail: Weak::new(),
        }
    }

    // add to tail
    pub fn push(&mut self, elem: T) {
        let new_node = Node::new(elem);
        match self.tail.upgrade().take() {
            Some(old_tail) => {
                new_node.borrow_mut().prev = Rc::downgrade(&old_tail);
                old_tail.borrow_mut().next = Some(new_node);
            }
            None => {
                self.tail = Rc::downgrade(&new_node);
                self.head = Some(new_node);
            }
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        self.tail.upgrade().map(|old_tail| {
            match old_tail.borrow_mut().prev.upgrade() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next = None;
                    self.tail = Rc::downgrade(&new_tail);
                }
                None => {
                    self.head.take();
                    self.tail = Weak::new();
                }
            };
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
        })
    }

    // add to head
    pub fn unshift(&mut self, elem: T) {
        let new_node = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Rc::downgrade(&new_node);
                new_node.borrow_mut().next = Some(old_head);
            }
            None => {
                self.tail = Rc::downgrade(&new_node);
                self.head = Some(new_node);
            }
        }
    }

    pub fn shift(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev = Weak::new();
                    self.head = Some(new_head);
                }
                None => {
                    self.tail = Weak::new();
                }
            };
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
        })
    }

    pub fn peek_head(&self) -> Option<Ref<T>> {
        self.head
            .as_ref()
            .map(|node| Ref::map(node.borrow(), |node| &node.elem))
    }

    pub fn peek_tail(&self) -> Option<Ref<T>> {
        self.tail
            .upgrade()
            .map(|node| Ref::map(node.borrow(), |node| &node.elem))
    }

    pub fn peek_head_mut(&mut self) -> Option<RefMut<T>> {
        self.head
            .as_ref()
            .map(|node| RefMut::map(node.borrow_mut(), |node| &mut node.elem))
    }

    pub fn peek_tail_mut(&mut self) -> Option<RefMut<T>> {
        unimplemented!()
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while let Some(old_head) = self.head.take() {
            self.head = old_head.borrow_mut().next.take();
        }
    }
}

There is a compilation error:

error[E0515]: cannot return value referencing function parameter `node`
   --> src/lib.rs:106:25
    |
106 |             .map(|node| Ref::map(node.borrow(), |node| &node.elem))
    |                         ^^^^^^^^^----^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                         |        |
    |                         |        `node` is borrowed here
    |                         returns a value referencing data owned by the current function

It seems that when the weak reference of the tail node upgrades to Rc, this Rc is owned by this function, and will be consumed in the end.

How can I fix that?

1 Answers

Your question

Use Weak::upgrade and RefCell::borrow:

fn example<T>(foo: Weak<RefCell<T>>) {
    let strong: Rc<RefCell<T>> = foo.upgrade().unwrap();
    let the_ref: Ref<T> = strong.borrow();
}

Your problem

self.head.as_ref() returns an Option<&Rc<_>>. self.tail.upgrade() returns an Option<Rc<_>>. When you call Option::map, ownership of the inner value is transferred to the closure, and you get the error you posted. You could call Option::as_ref, but the Option is owned by the function, so you are not allowed to return a reference because it wouldn't be valid once the Rc is destroyed.

The only thing you can do is to return the Rc from the function.

See also:

Related