Struggle with Rust compiler — 3 Link to heading

Let’s implement a simple Tree data structure in Rust using RefCell struct. In particular, we will write traverse() method that collects all the items contained in the tree.

Struggle with Rust compiler — clone Option Link to heading

Let’s implement a simple Tree data structure in Rust using RefCell struct. In particular, we will write traverse() method that collects all the items contained in the tree. Here is link on Rust Playground:

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

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut queue = VecDeque::new();
    queue.push_back(root.as_ref());
    while let Some(opt) = queue.pop_front() {
        if let Some(node) = opt {
            let borrowed = node.borrow();
            result.push(borrowed.val);
            queue.push_back(borrowed.left.as_ref());
            queue.push_back(borrowed.right.as_ref());
        }
    }

    result
}

Here is what the compiler is complaining:

error[E0597]: `borrowed` does not live long enough
  --> src/lib.rs:19:29
   |
17 |             let borrowed = node.borrow();
   |                 -------- binding `borrowed` declared here
18 |             result.push(borrowed.val);
19 |             queue.push_back(borrowed.left.as_ref());
   |                             ^^^^^^^^ borrowed value does not live long enough
20 |             queue.push_back(borrowed.right.as_ref());
21 |         }
   |         -<br>        |
   |         |<br>        |<br>        `borrowed` dropped here while still borrowed
   |         borrow might be used here, when `borrowed` is dropped and runs the destructor for type `Ref<'_, TreeNode>`

To understand the error message, it is always helpful to make a note of variable types that are related to the compiler error.

queue: VecDeque<Option<&Rc<RefCell<TreeNode>>>><br>opt: Option<&Rc<RefCell<TreeNode>>><br>node: &Rc<RefCell<TreeNode>><br>borrowed: Ref<TreeNode>

With the types in mind, let’s examine the error messages. The compiler complains that borrowed variable does not live long enough and is dropped in line 21. The root cause stems from node. Note that node variable is of type &Rc<RefCell<TreeNode>>, which is a borrow of Rc<…>. This type does not make much sense — Rc<...> is a reference counting smart pointer and serves the purpose of allowing multiple pointers/references to its content. In other words, we typically want to Rc::clone() it rather than creating a reference of it, which is already reference by itself. This means we actually want the node variable to be of type Rc<RefCell<TreeNode>>.

OK, how do we then fix the code? Looking at our types, we observe that &Rc<...> type originates from queue variable, which is currently of type VecDeque<Option<&Rc<RefCell<TreeNode>>>>. We need to fix it to be of type VecDeque<Option<Rc<RefCell<TreeNode>>>> without the & reference in front of Rc. To do that, we can call map() function and call Rc::clone() to convert to another instance of pointer when we are pushing Option<&Rc<…>> onto the queue.

--- before
+++ after
@@ -11,13 +11,13 @@
 pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
     let mut result = Vec::new();
     let mut queue = VecDeque::new();
-    queue.push_back(root.as_ref());
+    queue.push_back(root.as_ref().map(|rc| Rc::clone(rc)));
     while let Some(opt) = queue.pop_front() {
         if let Some(node) = opt {
             let borrowed = node.borrow();
             result.push(borrowed.val);
-            queue.push_back(borrowed.left.as_ref());
-            queue.push_back(borrowed.right.as_ref());
+            queue.push_back(borrowed.left.as_ref().map(|rc| Rc::clone(rc)));
+            queue.push_back(borrowed.right.as_ref().map(|rc| Rc::clone(rc)));
         }
     }

Note that in order to clone Rc, it is recommended that we invoke it with Rc::clone(rc) rather than rc.clone(). See this doc for more details. With the fix, the following are new types of the variables:

queue: VecDeque<Option<Rc<RefCell<TreeNode>>>><br>opt: Option<Rc<RefCell<TreeNode>>>><br>node: Rc<RefCell<TreeNode>><br>borrowed: Ref<TreeNode>

and the compiler no longer complains!

Though we fixed the compiler error, the fix seems to make our code a bit verbose. Could there be an easier way to do it? Essentially, what we want to do is to take &Option<T> and return Option<T> where the contained value is cloned, where in our case T = Rc<…>. Option implements Clone trait and hence provides clone() method, which does exactly that! Hence, a bit simpler solution is as follows

--- before
+++ after
@@ -11,13 +11,13 @@
 pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
     let mut result = Vec::new();
     let mut queue = VecDeque::new();
-    queue.push_back(root.as_ref());
+    queue.push_back(root.clone());
     while let Some(opt) = queue.pop_front() {
         if let Some(node) = opt {
             let borrowed = node.borrow();
             result.push(borrowed.val);
-            queue.push_back(borrowed.left.as_ref());
-            queue.push_back(borrowed.right.as_ref());
+            queue.push_back(borrowed.left.clone());
+            queue.push_back(borrowed.right.clone());
         }
     }