Brief: I'm new to Rust so I decided to practice by implementing a double linked list. For debugging purpose, I implemented the get() method, but I failed to copy the value out from a Rc<RefCell<_>>. (Sorry for asking dumb question)
Problem: I'm trying to return a Result<T, &'static str> in .get() where the T is the type of the data stored in node and &str is the error message string. The borrow checker tells me that I cannot return a reference to an in-method variable, so I tried to copy the inner value out and return it, but failed to do so.
Source code:
use std::{rc::Rc, cell::RefCell};
struct Node<T> {
data: Option<T>,
prev: Option<Rc<RefCell<Node<T>>>>,
next: Option<Rc<RefCell<Node<T>>>>,
}
impl<T> Node<T> {
/// Instantiate a new dummy node.
/// This node is used to mark the start and end of the list.
/// It is not counted in the size of the list.
fn new() -> Self {
Node {
data: None,
prev: None,
next: None,
}
}
/// Instantiate a new content node.
/// This node is used to store data.
/// It is counted in the size of the list.
fn from(data: T) -> Self {
Node {
data: Some(data),
prev: None,
next: None,
}
}
}
struct List<T> {
head: Rc<RefCell<Node<T>>>,
tail: Rc<RefCell<Node<T>>>,
size: usize,
}
impl<T> List<T> {
pub fn new() -> Self {
let head = Rc::new(RefCell::new(Node::new()));
let tail = Rc::new(RefCell::new(Node::new()));
head.borrow_mut().next = Some(Rc::clone(&tail));
tail.borrow_mut().prev = Some(Rc::clone(&head));
List { head, tail, size: 0 }
}
pub fn prepend(&self, data: T) {
let node = Rc::new(RefCell::new(Node::from(data)));
let mut head = self.head.borrow_mut();
node.borrow_mut().next = Some(head.next.take().unwrap());
node.borrow_mut().prev = Some(Rc::clone(&self.head));
head.next = Some(Rc::clone(&node));
if let Some(next) = node.borrow().next.as_ref() {
next.borrow_mut().prev = Some(Rc::clone(&node));
};
}
pub fn append(&self, data: T) {
let node = Rc::new(RefCell::new(Node::from(data)));
let mut tail = self.tail.borrow_mut();
node.borrow_mut().prev = Some(Rc::clone(&tail.prev.take().unwrap()));
node.borrow_mut().next = Some(Rc::clone(&self.tail));
tail.prev = Some(Rc::clone(&node));
if let Some(prev) = node.borrow().prev.as_ref() {
prev.borrow_mut().next = Some(Rc::clone(&node));
};
}
pub fn get(&self, index: isize) -> Result<T, &'static str> {
let mut current: Rc<RefCell<Node<T>>> = Rc::clone(self.head.borrow().next.as_ref().unwrap());
for _ in 0..index {
let tmp = Rc::clone(current.borrow().next.as_ref().ok_or("Index out of range")?);
current = tmp;
}
let result = current.borrow().data.as_ref().ok_or("Index out of range")?; // error[E0716]
Ok(*result) // error[E0507]
}
}
/*
error[E0716]: temporary value dropped while borrowed
--> src\linked.rs:74:22
|
74 | let result = current.borrow().data.as_ref().ok_or("Index out of range")?;
| ^^^^^^^^^^^^^^^^ - temporary value is freed at the end of this statement
| |
| creates a temporary value which is freed while still in use
75 | Ok(*result)
| ------- borrow later used here
|
help: consider using a `let` binding to create a longer lived value
|
74 ~ let binding = current.borrow();
75 ~ let result = binding.data.as_ref().ok_or("Index out of range")?;
|
error[E0507]: cannot move out of `*result` which is behind a shared reference
--> src\linked.rs:75:12
|
75 | Ok(*result)
| ^^^^^^^ move occurs because `*result` has type `T`, which does not implement the `Copy` trait
*/
I've Tried:
RefCell, but this did not help. I was trying to return it, not mutate it.RefCell, but I can't return the borrowed value because the borrowed Rc is short lived (but the inner value is not).RefCell and this post about how to return it with .map(), but I the compiler says "trait bound not satisfied" when I tried to use .into() and borrow checker complains "cannot move out" if I remove the .into().Rc::try_unwarp(), but it won't work since the inner data has more than one owner.Also: I may did these wrong, please forgive me if one of the posts solved my problem but I did not implement it in the right way, and please teach me how to do it properly. Many thanks.
This worked for me:
pub fn get(&self, index: isize) -> Result<T, &'static str>
where T: Clone
{
let mut current: Rc<RefCell<Node<T>>> = Rc::clone(self.head.borrow().next.as_ref().unwrap());
for _ in 0..index {
let tmp = Rc::clone(current.borrow().next.as_ref().ok_or("Index out of range")?);
current = tmp;
}
let guard = current.borrow();
guard.data.clone().ok_or("Index out of range")
}
You need the line where T: Clone to enable the .clone() method.
Some say it's a mistake to implement a doubly-linked list in order to learn Rust... I'm sorry to report that they are right. I did the exact same thing when I started. The other thing I tried was writing a ray-tracer; that went a lot better.
Core data structures are implemented using raw pointers. That means writing unsafe code and putting a safe API around it: an advanced Rust skill.