RC与 有向无环图（DAG）

1. RC: 一个值可以拥有多个所有者

a. 对一个 Rc 结构进行 clone()，不会将其内部的数据复制，只会增加引用计数。而当一个 Rc 结构离开作用域被 drop() 时，也只会减少其引用计数，直到引用计数为零，才会真正清除对应的内存。
b. 搞明白了 Rc，我们就进一步理解 Rust 是如何进行所有权的静态检查和动态检查了：
静态检查: 靠编译器保证代码符合所有权规则；
动态检查: 通过 Box::leak 让堆内存拥有不受限的生命周期，然后在运行过程中，通过对引用计数的检查，保证这样的堆内存最终会得到释放。

//1、内部可变性：允许在使用不可变引用时改变数据。
//
//2、通过RefCell<T>在运行时检查借用规则（通常情况下，是在编译时检查借用规则），RefCell<T>代表其数据的单一所有权。
//类似于Rc<T>，RefCell<T>只能用于单线程场景。
//
//3、选择Box<T>、Rc<T>或RefCell<T>的理由：
//Rc<T> 允许相同数据有多个所有者；Box<T> 和 RefCell<T> 有单一所有者。
//Box<T> 允许在编译时执行不可变或可变借用检查；Rc<T>仅允许在编译时执行不可变借用检查；RefCell<T> 允许在运行时执行不可变或可变借用检查。
//因为 RefCell<T> 允许在运行时执行可变借用检查，所以我们可以在即便 RefCell<T> 自身是不可变的情况下修改其内部的值。

2. RefCell 内部可变性

use std::cell::RefCell;
fn main() {
    // 内部可变性
    let data = RefCell::new(1);
    {
        // 获得 RefCell 内部数据的可变借用
        let mut v = data.borrow_mut();
        *v += 1;
    }
    // 获取 ReCell内部的不可变借用
    println!("data {}", data.borrow());
}
//你也许奇怪，
//这里为什么要把获取和操作可变借用的两句代码，用花括号分装到一个作用域下？
//因为根据所有权规则，在同一个作用域下，我们不能同时有活跃的可变借用和不可变借用。
//通过这对花括号，我们明确地缩小了可变借用的生命周期，不至于和后续的不可变借用冲突。

2. 实现一个有向无环图

image.png

假设 Node 就只包含 id 和指向下游（downstream）的指针，因为 DAG 中的一个节点可能被多个其它节点指向，所以我们使用 Rc 来表述它；一个节点可能没有下游节点，所以我们用 Option> 来表述它。

要建立这样一个 DAG，我们需要为 Node 提供以下方法：

1. new()：建立一个新的 Node。
2. update_downstream()：设置 Node 的 downstream。
3. get_downstream()：clone 一份 Node 里的 downstream。有了这些方法，我们就可以创建出拥有上图关系的 DAG 了

// 备注: Rc 是一个只读的引用计数器，你无法拿到 Rc 结构内部数据的可变引用
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Node {
    id: usize,
    // 使用 Rc> 让节点可以被修改
    downstream: Option<Rc<RefCell<Node>>>,
}
impl Node {
    pub fn new(id: usize) -> Self {
        Self {
            id,
            downstream: None,
        }
    }
    pub fn update_downstream(&mut self, downstream: Rc<RefCell<Node>>) {
        self.downstream = Some(downstream);
    }
    pub fn get_downstream(&self) -> Option<Rc<RefCell<Node>>> {
        self.downstream.as_ref().map(|v| v.clone())
    }
}

fn main() {
    let mut node1 = Node::new(1);
    let mut node2 = Node::new(2);
    let mut node3 = Node::new(3);
    let node4 = Node::new(4);

    node3.update_downstream(Rc::new(RefCell::new(node4)));

    node1.update_downstream(Rc::new(RefCell::new(node3)));
    node2.update_downstream(node1.get_downstream().unwrap());
    println!("node1: {:?}, node2: {:?}", node1, node2);

    let node5 = Node::new(5);
    let node3 = node1.get_downstream().unwrap();
    //获得可变引用, 来修改downstream
    node3.borrow_mut().downstream = Some(Rc::new(RefCell::new(node5)));

    println!("node1: {:?}, node2: {:?}", node1, node2);
}
//首先数据结构的 downstream 需要 Rc 内部嵌套一个 RefCell，
//这样，就可以利用 RefCell 的内部可变性，
//来获得数据的可变借用了，同时 Rc 还允许值有多个所有者

// Rc 为了性能，使用的不是线程安全的引用计数
// 我们需要另一个引用计数的智能指针：Arc，它实现了线程安全的引用计数器。