Borrowing on RefCell

Question

I'm just getting started with rust, and trying to implement some simple data structures. I am getting the following error on an iterator for a doubly linked list, and cannot understand why this is happening.

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

struct Node<T> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>,
    prev: Option<Rc<RefCell<Node<T>>>>,
}

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

pub struct DoublyLinkedList<T> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
    len: usize,
}

impl<T> DoublyLinkedList<T> {
    pub fn new() -> Self {
        DoublyLinkedList {
            head: None,
            tail: None,
            len: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn push_front(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_node.clone());
                new_node.borrow_mut().next = Some(old_head);
                self.head = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
        self.len += 1;
    }

    pub fn push_back(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
                new_node.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
        self.len += 1;
    }

    pub fn pop_front(&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 = None;
                    self.head = Some(new_head);
                }
                None => {
                    self.tail = None;
                }
            }
            self.len -= 1;
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().value
        })
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next = None;
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head = None;
                }
            }
            self.len -= 1;
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().value
        })
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            next: self.head.as_ref().map(|node| node.clone()),
        }
    }
}

pub struct Iter<T> {
    next: Option<Rc<RefCell<Node<T>>>>,
}

impl<T> Iterator for Iter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node
                .borrow()
                .next
                .as_ref()
                .map(|next_node| next_node.clone());
            node.borrow().value
            // Rc::try_unwrap(node).ok().unwrap().into_inner().value
        })
    }
}

I would have thought the borrow would be able to pull the internal value of the RefCell, but I'm getting the following error:

cannot move out of dereference of `Ref<'_, Node<T>>`

node.borrow().value
move occurs because value has type `T`, which does not implement the `Copy` trait

However, the commented out code below it works.

Answer 1

RefCell::borrow() returns a Ref<Node> which implements Deref<Target = Node>, which gives you an &Node reference, which lets you read from it but not mutate it or move it out.

The line node.borrow().value is attempting to move out the contents of the field value of the Node structure. You cannot do that given only the &Node access.

As a general principle in Rust:

• If you have &T you can read from the T. This is the situation you are in.
• If you have &mut T then you can read and also mutate the T; and you can move out the T but only if you swap in a replacement (with std::mem::swap or one of its relatives).
• If you have T then you can do everything that &mut T allows and also move out without replacing.

In order to move the value out of a RefCell, without a replacement, your

Rc::try_unwrap(node).ok().unwrap().into_inner().value

is the right way to go about it; deconstructing the wrappers until you have the value. Many Rust types will have methods in the style of into_inner(), precisely so that this sort of thing is possible.