与Rust编译器的斗争- 3

coding到灯火阑珊发表于 5天以前 | 总阅读数：56 次

让我们在Rust中使用RefCell结构实现一个简单的Tree数据结构。特别是，我们将编写traverse()方法来收集树中包含的所有项。

代码如下：

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
}

为了理解错误消息，记录一下与编译器错误相关的变量类型：

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 |         }
   |         -
   |         |
   |         `borrowed` dropped here while still borrowed
   |         borrow might be used here, when `borrowed` is dropped and runs the destructor for type `Ref<'_, TreeNode>`

了解了这些类型之后，让我们来检查一下错误消息。编译器抱怨借用的变量生命周期不够长，在第21行被drop了。根源在于node，注意，node变量的类型是&Rc<RefCell>，这是Rc<…>的借用。这种类型没有多大意义- Rc<…>是一个引用计数智能指针，其目的是允许多个指针/引用其内容。换句话说，我们通常希望Rc::clone()它而不是创建它的引用，因为它本身已经是引用了。这意味着我们实际上希望node变量的类型是Rc<RefCell>。

好，那我们怎么修改代码呢？查看我们的类型，我们观察到&Rc<…>类型源自队列变量，当前类型为VecDeque<Option<&Rc<RefCell>>>。我们需要修复它的类型为VecDeque<Option<Rc<RefCell>>>在Rc前面去掉&引用。要做到这一点，当我们将Option<&Rc<…>>压入队列时，可以调用map()函数并调用Rc::clone()转换为另一个指针实例。

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)));
        }
    }

    result
}

注意，为了克隆Rc，必须使用Rc::clone(Rc)而不是Rc .clone()来调用它。修复后，以下是变量的新类型：

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

编译器不再报错！

虽然我们修复了编译器错误，但这个修复似乎使我们的代码变得有点冗长。有更简单的方法吗？本质上，我们要做的是取&Option并返回Option，其中包含的值是克隆的，在我们的例子中T = Rc<…>。Option实现了Clone特性，因此提供了Clone()方法，因此，一个更简单的解决方案如下：

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)));
    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.as_ref().map(|rc| Rc::clone(rc)));
            // queue.push_back(borrowed.right.as_ref().map(|rc| Rc::clone(rc)));
            queue.push_back(borrowed.left.clone());
            queue.push_back(borrowed.right.clone());
        }
    }

    result
}