一、所有权

所有权和生命周期是Rust和其它编程语言的主要区别，也是Rust其它知识点的基础。

1.1、变量在函数调用时发生了什么

fn main() {
    // vec 动态数组因为大小在编译期无法确定，所以放在堆上，
    // 并且在栈上有一个包含了长度和容量的胖指针指向堆上的内存。
    let data = vec![10, 42, 9, 8];
    let v = 42;
    if let Some(pos) = find_pos(data, v) {
        println!("Found {} at {}", v, pos);
    }
}

fn find_pos(data: Vec<u32>, v: u32) -> Option<usize> {
    for (pos, item) in data.iter().enumerate() {
        if *item == v {
            return Some(pos);
        }
    }
    
    None
}

按照大多数编程语言的做法，我们每把data作为参数传递一次，堆上的内存就会多一次引用。

堆内存多次被引用的问题：

这些引用究竟会做什么操作，我们不得而知，也无从限制；
而且堆上的内存究竟什么时候能释放，尤其在多个调用栈引用时，很难厘清，取决于最后一个引用什么时候结束

我们先来看大多数语言的方案：

C/C++要求开发者手工处理，非常不便。这需要我们在写代码时高度自律，按照前人总结的最佳实践来操作。但人必然会犯错，一个不慎就会导致内存安全问题，要么内存泄露，要么使用已释放内存，导致程序崩溃。
Java等语言使用追踪式GC，通过定期扫描堆上数据还有没有人引用，来替开发者管理堆内存，不失为一种解决之道，但 GC 带来的 STW 问题让语言的使用场景受限，性能损耗也不小。
ObjC/Swift 使用自动引用计数（ARC），在编译时自动添加维护引用计数的代码，减轻开发者维护堆内存的负担。但同样地，它也会有不小的运行时性能损耗。

Rust 的解决思路

在Rust以前，引用是一种随意的、可以隐式产生的、对权限没有界定的行为，比如C里到处乱飞的指针、Java中随处可见的按引用传参，它们可读可写，权限极大。而 Rust 决定限制开发者随意引用的行为。

1.2、所有权和 Move 语义

Rust给出了如下规则：

一个值只能被一个变量所拥有，这个变量被称为所有者（Each value in Rust has a variable that’s called its owner）。
一个值同一时刻只能有一个所有者（There can only be one owner at a time），也就是说不能有两个变量拥有相同的值。所以对应刚才说的变量赋值、参数传递、函数返回等行为，旧的所有者会把值的所有权转移给新的所有者，以便保证单一所有者的约束。
当所有者离开作用域，其拥有的值被丢弃（When the owner goes out of scope, the value will be dropped），内存得到释放。

上面代码在Rust会变成下图这样：

所有权规则，解决了谁真正拥有数据的生杀大权问题，让堆上数据的多重引用不复存在，这是它最大的优势。

fn main() {
    let data = vec![1, 2, 3, 4];
    let data1 = data;
    println!("sum of data1: {}", sum(data1));
    println!("data1: {:?}", data1); // error1  data1 所有权已经转移到 sum 中去了，不能在用了。
    println!("sum of data: {}", sum(data)); // error2  data 转移给 data1。
}

fn sum(data: Vec<u32>) -> u32 {
    data.iter().fold(0, |acc, x| acc + x)
}

像上面代码这种情况，如何要避免所有权转移之后不能访问的情况？

Copy，如果你不希望值的所有权被转移，在Move语义外，Rust提供了Copy语义。如果一个数据结构实现了 Copy trait，那么它就会使用Copy语义。这样，在你赋值或者传参时，值会自动按位拷贝（浅拷贝）
```
 let a = 100;
 let b = a; // copy
 println!("a = {}, b = {} ",a,b) // a = 100, b = 100 
```
Borrow，如果你不希望值的所有权被转移，又无法使用 Copy 语义，那你可以“借用”数据，我们下一讲会详细讨论“借用”。

1.3、Copy 语义

Copy总结：

原生类型，包括函数、不可变引用和裸指针实现了Copy；
数组和元组，如果其内部的数据结构实现了Copy，那么它们也实现了Copy；
可变引用没有实现Copy；
非固定大小的数据结构，没有实现Copy。比如Vec

Trait std::marker::Copy

有些类型在Rust中没有实现Copy trait。这些类型在赋值时涉及资源管理、堆内存分配或可变借用等问题。以下是一些没有实现Copy trait的类型：

String：String类型分配堆内存以存储字符串数据，所以它不实现Copy trait。当从一个String变量赋值给另一个变量时，会发生所有权的转移（称为move）。
Vec：Vec (向量) 类型分配堆内存以存储一个元素的动态列表。类似于String，Vec类型也不实现Copy trait，因为它涉及内存管理。将一个Vec变量赋给另一个时，同样会发生所有权转移。
Box：Box是一个智能指针，它在堆上分配内存并保存一个值。Box类型没有Copy trait，因为它在堆上拥有内存。将Box变量赋给另一个时，进行所有权转移。
HashMap和HashSet：这些集合类型在堆上分配内存以存储元素。它们管理资源并涉及内存分配，所以没有实现Copy trait。
Rc和Arc：Rc（引用计数智能指针）和Arc（跨线程原子引用计数智能指针）都实现了共享所有权的概念。由于资源共享和引用计数，它们不实现Copy trait。
自定义类型：对于用户定义的结构体和枚举类型，如果其成员中至少有一个类型没有实现Copy trait，那么这个自定义类型也不会自动实现Copy trait。你可以通过明确地要求实现Copy和Clone trait来实现。

在 Rust 下，分配在堆上的数据结构可以引用栈上的数据么？为什么？

可以，只要栈上的数据生命周期大于堆上数据的生命周期就可以，简单来说就是在堆上数据被回收之前栈上的数据一定会存在的情况下，是可以的。

let x = 1;
let y = 2;
let v = vec![&x, &y];
println!("{:?}", v);

1.4、Borrow 语义

Borrow语义允许一个值的所有权，在不发生转移的情况下，被其它上下文使用。

其实，在 Rust 中，借用和引用是一个概念，只不过在其他语言中引用的意义和Rust不同，所以Rust提出了新概念借用，便于区分。

在其他语言中，引用是一种别名，你可以简单理解成鲁迅之于周树人，多个引用拥有对值的无差别的访问权限，本质上是共享了所有权；而在Rust下，所有的引用都只是借用了“临时使用权”，它并不破坏值的单一所有权约束。

1.4.1、只读借用/引用

以Java为例，给函数传一个整数，这是传值，和Rust里的Copy语义一致；而给函数传一个对象，或者任何堆上的数据结构，Java都会自动隐式地传引用。刚才说过，Java的引用是对象的别名，这也导致随着程序的执行，同一块内存的引用到处都是，不得不依赖GC进行内存回收。

但Rust没有传引用的概念，Rust 所有的参数传递都是传值，不管是Copy还是Move（类似Go）。所以在Rust中，你必须显式地把某个数据的引用，传给另一个函数。

Rust 的引用实现了 Copy trait，所以按照 Copy 语义，这个引用会被复制一份交给要调用的函数。对这个函数来说，它并不拥有数据本身，数据只是临时借给它使用，所有权还在原来的拥有者那里。

fn main() {
    let data = vec![1, 2, 3, 4];
    let data1 = &data;

    println!("data = {:?}",data); // data = [1, 2, 3, 4]
    // 值的地址是什么？引用的地址又是什么？
    println!(
        "addr of value: {:p}({:p}), addr of data {:p}, data1: {:p}",
        &data, data1, &&data, &data1
    ); // addr of value: 0x16f3a25f8(0x16f3a25f8), addr of data 0x16f3a26d8, data1: 0x16f3a2610

     // 只读引用实现了 Copy trait，也就意味着引用的赋值、传参都会产生新的浅拷贝。
    println!("sum of data1: {}", sum(data1)); 
    // addr of value: 0x16f3a25f8, addr of ref: 0x16f3a24b0

    // 堆上数据的地址是什么？
    println!(
        "addr of items: [{:p}, {:p}, {:p}, {:p}]",
        &data[0], &data[1], &data[2], &data[3]
    ); // addr of items: [0x600000608050, 0x600000608054, 0x600000608058, 0x60000060805c]
}


fn sum(data: &Vec<u32>) -> u32 {
    // 值的地址会改变么？引用的地址会改变么？
    println!("addr of value: {:p}, addr of ref: {:p}", data, &data);
    data.iter().fold(0, |acc, x| acc + x)
}

只读引用实现了 Copy trait，也就意味着引用的赋值、传参都会产生新的浅拷贝。

1.4.2、借用的生命周期及其约束

代码一：

// 这段代码会报错了，因为 a 的生命周期 小于 r ，所以不能把 a 的引用给 r
fn main() {
    let r = local_ref();
    println!("r: {:p}", r);
}

fn local_ref<'a>() -> &'a i32 {
    let a = 42;
    &a
}

代码二：

// 这段代码正常，因为 42 虽然在栈上，data在堆上。但是42 和 data的生命周期是一样的，所以可以引用
fn main() {
    let mut data: Vec<&u32> = Vec::new();
    let v = 42;
    data.push(&v);
    println!("data: {:?}", data);
}

代码三：

// push_local_ref 中 42的生命周期小于 data 生命周期，所以代码报错。
fn main() {
    let mut data: Vec<&u32> = Vec::new();
    push_local_ref(&mut data);
    println!("data: {:?}", data);
}

fn push_local_ref(data: &mut Vec<&u32>) {
    let v = 42;
    data.push(&v);
}

抓住了一个核心要素“在一个作用域下，同一时刻，一个值只能有一个所有者”。

堆变量的生命周期不具备任意长短的灵活性，因为堆上内存的生死存亡，跟栈上的所有者牢牢绑定。而栈上内存的生命周期，又跟栈的生命周期相关，所以我们核心只需要关心调用栈的生命周期。

1.4.3、可变借用/引用

多个可变引用共存报错的例子：

fn main() {
    let mut data = vec![1, 2, 3];

    for item in data.iter_mut() {
        data.push(*item + 1); // 报错 cannot borrow `data` as mutable more than 
         // once at a time [E0499] second mutable borrow occurs here
    }
}

那如果同时有一个可变引用和若干个只读引用

fn main() {
    let mut data = vec![1, 2, 3];
    let data1 = vec![&data[0]];
    println!("data[0]: {:p}", &data[0]);

    for i in 0..100 {
        data.push(i); // cannot borrow `data` as mutable because it is 
        //also borrowed as immutable [E0502] mutable borrow occurs here
    }

    println!("data[0]: {:p}", &data[0]);
    println!("boxed: {:p}", &data1);

    // 如果你仔细推敲，就会发现这里有内存不安全的潜在操作：如果继续添加元素，
    // 堆上的数据预留的空间不够了，就会重新分配一片足够大的内存，把之前的值拷过来，
    // 然后释放旧的内存。这样就会让 data1 中保存的 &data[0] 引用失效，导致内存安全问题。
}

Rust 引用的限制，所以为了保证内存安全，Rust对可变引用的使用也做了严格的约束：

在一个作用域内，仅允许一个活跃的可变引用。所谓活跃，就是真正被使用来修改数据的可变引用，如果只是定义了，却没有使用或者当作只读引用使用，不算活跃。
在一个作用域内，活跃的可变引用（写）和只读引用（读）是互斥的，不能同时存在。

从可变引用的约束我们也可以看到，Rust 不光解决了 GC 可以解决的内存安全问题，还解决了GC无法解决的问题。

1.4.4、小结

一个值在同一时刻只有一个所有者。当所有者离开作用域，其拥有的值会被丢弃。赋值或者传参会导致值 Move，所有权被转移，一旦所有权转移，之前的变量就不能访问。
如果值实现了 Copy trait，那么赋值或传参会使用 Copy 语义，相应的值会被按位拷贝，产生新的值。
一个值可以有多个只读引用。
一个值可以有唯一一个活跃的可变引用。可变引用（写）和只读引用（读）是互斥的关系，就像并发下数据的读写互斥那样。
引用的生命周期不能超出值的生命周期。

1.4.5、可变引用是如何导致堆内存重新分配的

use std::mem;

fn main() {
    // capacity 是 1, len 是 0
    let mut v = vec![1];
    // capacity 是 8, len 是 0
    let v1: Vec<i32> = Vec::with_capacity(8);

    print_vec("v1", v1);

    // 我们先打印 heap 地址，然后看看添加内容是否会导致堆重分配
    println!("heap start: {:p}", &v[0] as *const i32);

    extend_vec(&mut v);

    // heap 地址改变了！这就是为什么可变引用和不可变引用不能共存的原因
    println!("new heap start: {:p}", &v[0] as *const i32);

    print_vec("v", v);
}

fn extend_vec(v: &mut Vec<i32>) {
    // Vec<T> 堆内存里 T 的个数是指数增长的，我们让它恰好 push 33 个元素
    // capacity 会变成 64
    (2..34).into_iter().for_each(|i| v.push(i));
}

fn print_vec<T>(name: &str, data: Vec<T>) {
    let p: [usize; 3] = unsafe { mem::transmute(data) };
    // 打印 Vec<T> 的堆地址，capacity，len
    // 注意这个不同系统/CPU 内存的排序不一样。
    println!("{}: cap = {}, data = 0x{:x}, len = {}", name, p[0], p[1], p[2]);
}

1.5、Rc

抛出问题：

一个有向无环图（DAG）中，某个节点可能有两个以上的节点指向它，这个按照所有权模型怎么表述？比如双向链表节点。
多个线程要访问同一块共享内存，怎么办？

我们知道，这些问题在程序运行过程中才会遇到，在编译期，所有权的静态检查无法处理它们，所以为了更好的灵活性，Rust提供了运行时的动态检查，来满足特殊场景下的需求。

那具体如何在运行时做动态检查呢？运行时的动态检查又如何与编译时的静态检查自洽呢？

Rust的答案是使用引用计数的智能指针：Rc（Reference counter） 和 Arc（Atomic reference counter）。这里要特别说明一下，Arc 和 ObjC/Swift 里的 ARC（Automatic Reference Counting）不是一个意思，不过它们解决问题的手段类似，都是通过引用计数完成的。

1.5.1、Rc

我们先看Rc。对某个数据结构T，我们可以创建引用计数Rc，使其有多个所有者。Rc会把对应的数据结构创建在堆上，堆是唯一可以让动态创建的数据被到处使用的内存。

use std::rc::Rc;
fn main() {    
  let a = Rc::new(1);
}

对一个 Rc 结构进行 clone()，不会将其内部的数据复制，只会增加引用计数。而当一个Rc结构离开作用域被 drop()时，也只会减少其引用计数，直到引用计数为零，才会真正清除对应的内存。

use std::rc::Rc;
fn main() {
    let a = Rc::new(1);
    let b = a.clone();
    let c = a.clone();
}

fn clone(&self) -> Rc<T> {
    // 增加引用计数
    self.inner().inc_strong();
    // 通过 self.ptr 生成一个新的 Rc 结构
    Self::from_inner(self.ptr)
}

1.5.2、Box::leak() 机制

Rust必须提供一种机制，让代码可以像C/C++那样，创建不受栈内存控制的堆内存，从而绕过编译时的所有权规则。Rust提供的方式是Box::leak()。

Box是Rust下的智能指针，它可以强制把任何数据结构创建在堆上，然后在栈上放一个指针指向这个数据结构，但此时堆内存的生命周期仍然是受控的，跟栈上的指针一致。

Box::leak()，顾名思义，它创建的对象，从堆内存上泄漏出去，不受栈内存控制，是一个自由的、生命周期可以大到和整个进程的生命周期一致的对象。

有了 Box::leak()，我们就可以跳出Rust编译器的静态检查，保证 Rc 指向的堆内存，有最大的生命周期，然后我们再通过引用计数，在合适的时机，结束这段内存的生命周期。如果你对此感兴趣，可以看 Rc::new() 的源码。

搞明白了Rc，我们就进一步理解 Rust是如何进行所有权的静态检查和动态检查了：

静态检查，靠编译器保证代码符合所有权规则；
动态检查，通过Box::leak让堆内存拥有不受限的生命周期，然后在运行过程中，通过对引用计数的检查，保证这样的堆内存最终会得到释放。

1.5.3、实现 DAG

use std::rc::Rc;

#[derive(Debug)]
struct Node {
    id: usize,
    downstream: Option<Rc<Node>>,
}

impl Node {
    pub fn new(id: usize) -> Self {
        Self {
            id,
            downstream: None,
        }
    }

    pub fn update_downstream(&mut self, downstream: Rc<Node>) {
        self.downstream = Some(downstream);
    }

    pub fn get_downstream(&self) -> Option<Rc<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(node4));

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

1.6、RefCell 和内部可变性

在运行上述代码时，细心的你也许会疑惑：整个DAG在创建完成后还能修改么？

let node5 = Node::new(5);
let node3 = node1.get_downstream().unwrap();
node3.update_downstream(Rc::new(node5)); // cannot borrow data in an `Rc` as mutable

println!("node1: {:?}, node2: {:?}", node1, node2);

这是因为 Rc 是一个只读的引用计数器，你无法拿到Rc结构内部数据的可变引用，来修改这个数据。这可怎么办？

这个就引出了内部可变性和外部可变性的概念：

外部可变性（exterior mutability），用let mut显式地声明一个可变的值，或者用&mut声明一个可变引用时，编译器可以在编译时进行严格地检查，保证只有可变的值或者可变的引用，才能修改值内部的数据，这被称作外部可变。
内部可变性（internal mutability），有时候我们希望能够绕开这个编译时的检查，对并未声明成mut的值或者引用，也想进行修改。在编译器的眼里，值是只读的，但是在运行时，这个值可以得到可变借用，从而修改内部的数据

我们可以用内部可变性RefCell，解决上面的问题：

use std::cell::RefCell;

fn main() {
    let data = RefCell::new(1); // let 申明是不可变变量
    {
        // 获得 RefCell 内部数据的可变借用
        let mut v = data.borrow_mut();
        *v += 1;
    }
    println!("data: {:?}", data.borrow());
}

因为根据所有权规则，在同一个作用域下，我们不能同时有活跃的可变借用和不可变借用。通过这对花括号，我们明确地缩小了可变借用的生命周期，不至于和后续的不可变借用冲突。

1.6.1、实现可修改 DAG

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

#[derive(Debug)]
struct Node {
    id: usize,
    // 使用 Rc<RefCell<T>> 让节点可以被修改
    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);
}

1.7、Arc 和 Mutex/RwLock

Arc内部的引用计数使用了Atomic Usize ，而非普通的usize。从名称上也可以感觉出来，Atomic Usize是 usize的原子类型，它使用了CPU的特殊指令，来保证多线程下的安全。如果你对原子类型感兴趣，可以看 std::sync::atomic的文档。

Rust实现两套不同的引用计数数据结构，完全是为了性能考虑，从这里我们也可以感受到Rust对性能的极致渴求。如果不用跨线程访问，可以用效率非常高的 Rc；如果要跨线程访问，那么必须用 Arc。

同样的，RefCell也不是线程安全的，如果我们要在多线程中，使用内部可变性，Rust提供了Mutex和RwLock。

use std::sync::{Arc, Mutex};
use std::thread;

const NUM_THREADS: usize = 5;

fn main() {
    // 创建一个原子引用计数（Arc）的互斥量（Mutex），用来共享计数器数据
    let counter = Arc::new(Mutex::new(0));

    // 生成线程句柄集合
    let mut handles = vec![];

    for _ in 0..NUM_THREADS {
        // 克隆 Arc，使其可以在多个线程之间共享
        let counter = Arc::clone(&counter);

        // 创建线程并更新计数器
        let handle = thread::spawn(move || {
            let mut num = counter.lock().unwrap();
            *num += 1;
        });

        // 将线程句柄添加到集合内
        handles.push(handle);
    }

    // 等待所有线程结束
    for handle in handles {
        handle.join().unwrap();
    }

    println!("Counter: {}", *counter.lock().unwrap());
}

二、生命周期

脑图链接

而在 Rust 中，除非显式地做Box::leak()/Box::into_raw()/ManualDrop等动作，一般来说，堆内存的生命周期，会默认和其栈内存的生命周期绑定在一起。

2.1、值的生命周期

如果一个值的生命周期贯穿整个进程的生命周期，那么我们就称这种生命周期为静态生命周期。

当值拥有静态生命周期，其引用也具有静态生命周期。我们在表述这种引用的时候，可以用'static来表示。比如： &'static str代表这是一个具有静态生命周期的字符串引用。

一般来说，全局变量、静态变量、字符串字面量（string literal）等，都拥有静态生命周期。我们上文中提到的堆内存，如果使用了Box::leak后，也具有静态生命周期。

如果一个值是在某个作用域中定义的，也就是说它被创建在栈上或者堆上，那么其生命周期是动态的。

2.2、生命周期标注

fn main() {
    let s1 = String::from("Lindsey");
    let s2 = String::from("Rosie");

    let result = max(&s1, &s2);

    println!("bigger one: {}", result);
}

// 这段代码是无法编译通过的，它会报错 “missing lifetime specifier” 
// 也就是说，编译器在编译 max() 函数时，无法判断 s1、s2 和返回值的生命周期。
fn max(s1: &str, s2: &str) -> &str {
    if s1 > s2 {
        s1
    } else {
        s2
    }
}

此时，就需要我们在函数签名中提供生命周期的信息，也就是生命周期标注（lifetime specifier）。在生命周期标注时，使用的参数叫生命周期参数（lifetime parameter）。通过生命周期标注，我们告诉编译器这些引用间生命周期的约束。

fn max<'a>(s1: &'a str, s2: &'a str) -> &'a str {
    if s1 > s2 {
        s1
    } else {
        s2
    }
}

fn main() {
    let string1 = String::from("xyz1");
    let result;
    {
        let string2 = String::from("xyz");
        result = max(&string1, &string2);
        println!("{}", result);
    }
}

2.2.1、编译器声明周期标注规则

虽然我们没有做任何生命周期的标注，但编译器会通过一些简单的规则为函数自动添加标注：

所有引用类型的参数都有独立的生命周期 'a 、'b 等。
如果只有一个引用型输入，它的生命周期会赋给所有输出。
如果有多个引用类型的参数，其中一个是self，那么它的生命周期会赋给所有输出。

Demo :

//pub fn strtok<'b, 'a>(s: &'b mut &'a str, delimiter: char) -> &'a str 与下面等价
pub fn strtok<'a>(s: &mut &'a str, delimiter: char) -> &'a str {
    if let Some(i) = s.find(delimiter) {
        let prefix = &s[..i];
        // 由于 delimiter 可以是 utf8，所以我们需要获得其 utf8 长度，
        // 直接使用 len 返回的是字节长度，会有问题
        let suffix = &s[(i + delimiter.len_utf8())..];
        *s = suffix;
        prefix
    } else { // 如果没找到，返回整个字符串，把原字符串指针 s 指向空串
        let prefix = *s;
        *s = "";
        prefix
    }
}

fn main() {
    let s = "hello world".to_owned();
    let mut s1 = s.as_str();
    let hello = strtok(&mut s1, ' ');
    println!("hello is: {}, s1: {}, s: {}", hello, s1, s);
}

如果我们把 strtok() 函数的签名写成这样，会发生什么问题？为什么它会发生这个问题？你可以试着编译一下看看。

pub fn strtok<'a>(s: &'a mut &str, delimiter: char) -> &'a str {...}

再运行,就会提示s1,同时存在可变和不可变引用。原来是s1的可变引用的周期和返回值绑定了.在hello使用结束前,编译器认为s1的可变引用一直存在.

error[E0502]: cannot borrow `s1` as immutable because it is also borrowed as mutable
   --> src/main.rs:384:52
    |
382 |     let hello = strtok(&mut s1, ' ');
    |                        ------- mutable borrow occurs here
383 |     // hello is: hello, s1: world, s: hello world
384 |     println!("hello is: {}, s1: {}, s: {}", hello, s1, s);
    |     -----------------------------------------------^^----
    |     |                                              |
    |     |                                              immutable borrow occurs here
    |     mutable borrow later used here
    |
    = note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)

Rust的借用规则要求在同一时间内，不能有一个变量的可变和不可变引用同时存在。在这个代码中，strtok函数创建了一个s1的可变引用，并返回了一个这个可变引用生命周期的不可变引用hello。而在println!宏里，尝试同时使用这两个引用：hello（不可变引用）和s1的可变引用。

那么根据这个理解,其实这样标注也可以.只要把打印拆开就行了.

pub fn strtok<'a>(s: &'a mut &str, delimiter: char) -> &'a str {
    if let Some(i) = s.find(delimiter) {
        let prefix = &s[..i];
        // 由于 delimiter 可以是 utf8，所以我们需要获得其 utf8 长度，
        // 直接使用 len 返回的是字节长度，会有问题
        let suffix = &s[(i + delimiter.len_utf8())..];
        *s = suffix;
        prefix
    } else { // 如果没找到，返回整个字符串，把原字符串指针 s 指向空串
        let prefix = *s;
        *s = "";
        prefix
    }
}

fn demo17() {
    let s = "hello world".to_owned();
    let mut s1 = s.as_str();
    let hello = strtok(&mut s1, ' ');
    // hello is: hello, s1: world, s: hello world
    // println!("hello is: {}, s1: {}, s: {}", hello, s1, s);
    println!("hello is: {}, s: {}", hello, s);
    println!("s1: {}", s1);
}

生命周期标注的目的是，在参数和返回值之间建立联系或者约束。调用函数时，传入的参数的生命周期需要大于等于（outlive）标注的生命周期。

2.2.2、Struct的生命周期

struct Employee<'a, 'b> {
  name: &'a str,
  title: &'b str,
  age: u8,
}

使用数据结构时，数据结构自身的生命周期，需要小于等于其内部字段的所有引用的生命周期。

三、内存管理

脑图链接

内存管理是任何编程语言的核心

整个堆内存生命周期管理的发展史如下图所示：

而Rust的创造者们，重新审视了堆内存的生命周期，发现大部分堆内存的需求在于动态大小，小部分需求是更长的生命周期。所以它默认将堆内存的生命周期和使用它的栈内存的生命周期绑在一起，并留了个小口子leaked机制，让堆内存在需要的时候，可以有超出帧存活期的生命周期。

3.1、值的创建

当我们为数据结构创建一个值，并将其赋给一个变量时，根据值的性质，它有可能被创建在栈上，也有可能被创建在堆上。

如果数据结构的大小无法确定，或者它的大小确定但是在使用时需要更长的生命周期，就最好放在堆上。

3.1.1 Struct 内存布局

内存对齐规则：

首先确定每个域的长度和对齐长度，原始类型的对齐长度和类型的长度一致。
每个域的起始位置要和其对齐长度对齐，如果无法对齐，则添加padding直至对齐。
结构体的对齐大小和其最大域的对齐大小相同，而结构体的长度则四舍五入到其对齐的倍数。

而Rust编译器替我们自动完成了这个优化，这就是为什么Rust会自动重排你定义的结构体，来达到最高效率。我们看同样的代码，在Rust下，S1和S2大小都是4

use std::mem::{align_of, size_of};

struct S1 {
    a: u8,
    b: u16,
    c: u8,
}

struct S2 {
    a: u8,
    c: u8,
    b: u16,
}

fn main() {
    println!("sizeof S1: {}, S2: {}", size_of::<S1>(), size_of::<S2>());
    println!("alignof S1: {}, S2: {}", align_of::<S1>(), align_of::<S2>());
}

Rust 编译器默认为开发者优化结构体的排列，但你也可以使用#[repr]宏，强制让Rust编译器不做优化，和C的行为一致，这样，Rust代码可以方便地和C代码无缝交互。

3.1.2 enum 内存布局

enum是一个标签联合体（tagged union），它的大小是标签的大小，加上最大类型的长度。

use std::collections::HashMap;
use std::mem::size_of;

enum E {
    A(f64),
    B(HashMap<String, String>),
    C(Result<Vec<u8>, String>),
}

// 这是一个声明宏，它会打印各种数据结构本身的大小，在 Option 中的大小，以及在 Result 中的大小
// 对于 Option 结构而言，它的 tag 只有两种情况：0 或 1，
//  tag 为 0 时，表示 None，tag 为 1 时，表示 Some。
macro_rules! show_size {
    (header) => {
        println!(
            "{:<24} {:>4}    {}    {}",
            "Type", "T", "Option<T>", "Result<T, io::Error>"
        );
        println!("{}", "-".repeat(64));
    };
    ($t:ty) => {
        println!(
            "{:<24} {:4} {:8} {:12}",
            stringify!($t),
            size_of::<$t>(),
            size_of::<Option<$t>>(),
            size_of::<Result<$t, std::io::Error>>(),
        )
    };
}

fn main() {
    show_size!(header);
    show_size!(u8);
    show_size!(f64);
    show_size!(&u8);
    show_size!(Box<u8>);
    show_size!(&[u8]);

    show_size!(String);
    show_size!(Vec<u8>);
    show_size!(HashMap<String, String>);
    show_size!(E);
}

3.1.3 vec 和 String

很多动态大小的数据结构，在创建时都有类似的内存布局：栈内存放的胖指针，指向堆内存分配出来的数据，我们之前介绍的Rc也是如此。

3.2、值的使用

其实Copy和Move在内部实现上，都是浅层的按位做内存复制，只不过Copy允许你访问之前的变量，而Move不允许。所以 Move = Copy + Delete （在栈上）

但是，如果你要复制的只是原生类型（Copy）或者栈上的胖指针（Move），不涉及堆内存的复制也就是深拷贝（deep copy），那这个效率是非常高的，我们不必担心每次赋值或者每次传参带来的性能损失。

不过也有一个例外，要说明：对栈上的大数组传参，由于需要复制整个数组，会影响效率。所以，一般我们建议在栈上不要放大数组，如果实在需要，那么传递这个数组时，最好用传引用而不是传值。

以一个 Vec<T> 为例，当你使用完堆内存目前的容量后，还继续添加新的内容，就会触发堆内存的自动增长。有时候，集合类型里的数据不断进进出出，导致集合一直增长，但只使用了很小部分的容量，内存的使用效率很低，所以你要考虑使用，比如shrink_to_fit方法，来节约对内存的使用。

3.3、值的销毁

这里用到了 Drop trait。Drop trait类似面向对象编程中的析构函数，当一个值要被释放，它的Drop trait会被调用。比如下面的代码，变量greeting是一个字符串，在退出作用域时，其drop()函数被自动调用，释放堆上包含 hello world的内存，然后再释放栈上的内存：

3.3.1 堆内存释放

所有权机制规定了，一个值只能有一个所有者，所以在释放堆内存的时候，整个过程简单清晰，就是单纯调用Drop trait，不需要有其他顾虑。这种对值安全，也没有额外负担的释放能力，是 Rust 独有的。

我觉得Rust在内存管理方面的设计特别像蚁群。在蚁群中，每个个体的行为都遵循着非常简单死板的规范，最终大量简单的个体能构造出一个高效且不出错的系统。

反观其它语言，每个个体或者说值，都非常灵活，引用传来传去，最终却构造出来一个很难分析的复杂系统。单靠编译器无法决定，每个值在各个作用域中究竟能不能安全地释放，导致系统，要么像C/C++一样将这个重担部分或者全部地交给开发者，要么像Java那样构建另一个系统来专门应对内存安全释放的问题。

3.3.2 释放其他资源

Rust的Drop trait主要是为了应对堆内存释放的问题，其实它还可以释放任何资源，比如 socket、文件、锁等等。Rust对所有的资源都有很好的 RAII 支持。

比如我们创建一个文件file，往里面写入 hello world，当file离开作用域时，不但它的内存会被释放，它占用的资源、操作系统打开的文件描述符，也会被释放，也就是文件会自动被关闭。（代码）

use std::fs::File;
use std::io::prelude::*;
fn main() -> std::io::Result<()> {
    let mut file = File::create("foo.txt")?;
    file.write_all(b"hello world")?;
    Ok(())
}

在其他语言中，无论 Java、Python 还是Golang，你都需要显式地关闭文件，避免资源的泄露。这是因为，即便 GC能够帮助开发者最终释放不再引用的内存，它并不能释放除内存外的其它资源。

四、类型系统

脑图链接

4.1、类型系统基本概念与分类

类型系统完全是一种工具，编译器在编译时对数据做静态检查，或者语言在运行时对数据做动态检查的时候，来保证某个操作处理的数据是开发者期望的数据类型。

类型系统其实就是，对类型进行定义、检查和处理的系统。所以，按对类型的操作阶段不同，就有了不同的划分标准，也对应有不同分类。

按定义后类型是否可以隐式转换，可以分为强类型和弱类型。Rust不同类型间不能自动转换，所以是强类型语言，而 C/C++/JavaScript会自动转换，是弱类型语言。

按类型检查的时机，在编译时检查还是运行时检查，可以分为静态类型系统和动态类型系统。对于静态类型系统，还可以进一步分为显式静态和隐式静态，Rust/Java/Swift 等语言都是显式静态语言，而Haskell是隐式静态语言。

在类型系统中，多态是一个非常重要的思想，它是指在使用相同的接口时，不同类型的对象，会采用不同的实现。

对于动态类型系统，多态通过鸭子类型（duck typing）实现；而对于静态类型系统，多态可以通过参数多态（parametric polymorphism）、特设多态（adhoc polymorphism）和子类型多态（subtype polymorphism）实现。

参数多态是指，代码操作的类型是一个满足某些约束的参数，而非具体的类型。
特设多态是指同一种行为有多个不同实现的多态。比如加法，可以1+1，也可以是 abc+cde、matrix1+matrix2、甚至matrix1 + vector1。在面向对象编程语言中，特设多态一般指函数的重载。
子类型多态是指，在运行时，子类型可以被当成父类型使用。

在Rust中，参数多态通过泛型来支持、特设多态通过trait来支持、子类型多态可以用trait object来支持。

4.2、Rust 类型系统

按刚才不同阶段的分类，在定义时， Rust不允许类型的隐式转换，也就是说，Rust是强类型语言；同时在检查时，Rust使用了静态类型系统，在编译期保证类型的正确。强类型加静态类型，使得Rust是一门类型安全的语言。

从内存的角度看，类型安全是指代码，只能按照被允许的方法，访问它被授权访问的内存。

到这里简单总结一下，我们了解到Rust是强类型、静态类型语言，并且在代码中，类型无处不在。

4.2.1 数据类型

Rust的原生类型包括字符、整数、浮点数、布尔值、数组（array）、元组（tuple）、切片（slice）、指针、引用、函数等，见下表：

在原生类型的基础上，Rust标准库还支持非常丰富的组合类型，看看已经遇到的：

4.2.2 类型推导

Rust编译器需要足够的上下文来进行类型推导，所以有些情况下，编译器无法推导出合适的类型，比如下面的代码尝试把一个列表中的偶数过滤出来，生成一个新的列表：

fn main() {
    let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    let even_numbers = numbers // let even_numbers: Vec<_> = numbers
        .into_iter()
        .filter(|n| n % 2 == 0)
        .collect(); // .collect::<Vec<_>>();

    println!("{:?}", even_numbers);
}

collect是Iterator trait的方法，它把一个iterator转换成一个集合。因为很多集合类型，如 Vec<T>、HashMap<K, V>等都实现了Iterator，所以这里的collect究竟要返回什么类型，编译器是无法从上下文中推断的。

在泛型函数后使用 :: 来强制使用类型 T，这种写法被称为 turbofish。我们再看一个对 IP 地址和端口转换的例子：

use std::net::SocketAddr;

fn main() {
    let addr = "127.0.0.1:8080".parse::<SocketAddr>().unwrap();
    println!("addr: {:?}, port: {:?}", addr.ip(), addr.port());
}

有些情况下，即使上下文中含有类型的信息，也需要开发者为变量提供类型，比如常量和静态变量的定义。看一个例子（代码）：

const PI: f64 = 3.1415926;
static E: f32 = 2.71828;

fn main() {
    const V: u32 = 10;
    static V1: &str = "hello";
    println!("PI: {}, E: {}, V {}, V1: {}", PI, E, V, V1);
}

4.3、泛型

4.3.1 泛型数据结构

我们从一个最简单的泛型例子 Option 开始回顾：

enum Option<T> {
  Some(T),
  None,
}

函数和泛型：

函数，是把重复代码中的参数抽取出来，使其更加通用，调用函数的时候，根据参数的不同，我们得到不同的结果；
而泛型，是把重复数据结构中的参数抽取出来，在使用泛型类型时，根据不同的参数，我们会得到不同的具体类型。

再来看一个复杂一点的泛型结构 Vec 的例子，验证一下这个想法：

pub struct Vec<T, A: Allocator = Global> {
    buf: RawVec<T, A>,
    len: usize,
}

pub struct RawVec<T, A: Allocator = Global> {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

Vec有两个参数，一个是 T，是列表里的每个数据的类型，另一个是 A，它有进一步的限制 A: Allocator ，也就是说A需要满足 Allocator trait。

A这个参数有默认值 Global，它是 Rust 默认的全局分配器 - jemallocator，这也是为什么Vec<T>虽然有两个参数，使用时都只需要用 T。

在讲生命周期标注的时候，我们讲过，数据类型内部如果有借用的数据，需要显式地标注生命周期。其实在 Rust 里，生命周期标注也是泛型的一部分，一个生命周期'a代表任意的生命周期，和T代表任意类型是一样的。

来看一个枚举类型Cow的例子：

pub enum Cow<'a, B: ?Sized + 'a> where B: ToOwned,
{
    // 借用的数据
    Borrowed(&'a B),
    // 拥有的数据
    Owned(<B as ToOwned>::Owned),
}

Cow（Clone-on-Write）是Rust中一个很有意思且很重要的数据结构。它就像Option一样，在返回数据的时候，提供了一种可能：要么返回一个借用的数据（只读），要么返回一个拥有所有权的数据（可写）。

对于拥有所有权的数据B ，第一个是生命周期约束。这里B的生命周期是'a，所以B需要满足'a，这里和泛型约束一样，也是用 B: 'a来表示。当Cow内部的类型B生命周期为'a 时，Cow自己的生命周期也是'a。

B还有两个约束：?Sized 和 where B: ToOwned。

?Sized是一种特殊的约束写法，?代表可以放松问号之后的约束。由于Rust默认的泛型参数都需要是Sized，也就是固定大小的类型，所以这里?Sized代表用可变大小的类型。

ToOwned是一个trait，它可以把借用的数据克隆出一个拥有所有权的数据。

所以这里对B的三个约束分别是：

生命周期'a
长度可变?Sized
符合ToOwned trait

最后我解释一下Cow这个enum里 <B as ToOwned>::Owned 的含义：它对B做了一个强制类型转换，转成 ToOwned trait，然后访问 ToOwned trait 内部的 Owned 类型。

因为在Rust里，子类型可以强制转换成父类型，B可以用ToOwned约束，所以它是ToOwned trait的子类型，因而B可以安全地强制转换成ToOwned。这里B as ToOwned是成立的。

Demo：

use std::borrow::Cow;

use url::Url;
fn main() {
    let url = Url::parse("https://tyr.com/rust?page=1024&sort=desc&extra=hello%20world").unwrap();
    let mut pairs = url.query_pairs();

    assert_eq!(pairs.count(), 3);

    let (mut k, v) = pairs.next().unwrap();
    // 因为 k, v 都是 Cow<str> 他们用起来感觉和 &str 或者 String 一样
    // 此刻，他们都是 Borrowed
    println!("key: {}, v: {}", k, v);
    // 当修改发生时，k 变成 Owned
    k.to_mut().push_str("_lala");

    print_pairs((k, v));

    print_pairs(pairs.next().unwrap());
    // 在处理 extra=hello%20world 时，value 被处理成 "hello world"
    // 所以这里 value 是 Owned
    print_pairs(pairs.next().unwrap());
}

fn print_pairs(pair: (Cow<str>, Cow<str>)) {
    println!("key: {}, value: {}", show_cow(pair.0), show_cow(pair.1));
}

fn show_cow(cow: Cow<str>) -> String {
    match cow {
        Cow::Borrowed(v) => format!("Borrowed {}", v),
        Cow::Owned(v) => format!("Owned {}", v),
    }
}

按类型定义、检查以及检查时能否被推导出来，Rust 是强类型 + 静态类型 + 显式类型。

五、trait

脑图链接

5.1、什么是trait

trait是Rust中的接口，它定义了类型使用这个接口的行为。你可以类比到自己熟悉的语言中理解，trait对于 Rust而言，相当于interface之于Java、protocol之于Swift、type class之于Haskell。

在开发复杂系统的时候，我们常常会强调接口和实现要分离。因为这是一种良好的设计习惯，它把调用者和实现者隔离开，双方只要按照接口开发，彼此就可以不受对方内部改动的影响。

5.1.1 基本 trait

以标准库中 std::io::Write 为例

pub trait Write {
    fn write(&mut self, buf: &[u8]) -> Result<usize>;
    fn flush(&mut self) -> Result<()>;
    fn write_vectored(&mut self, bufs: &[IoSlice<'_>]) -> Result<usize> { ... }
    fn is_write_vectored(&self) -> bool { ... }
    fn write_all(&mut self, buf: &[u8]) -> Result<()> { ... }
    fn write_all_vectored(&mut self, bufs: &mut [IoSlice<'_>]) -> Result<()> { ... }
    fn write_fmt(&mut self, fmt: Arguments<'_>) -> Result<()> { ... }
    fn by_ref(&mut self) -> &mut Self where Self: Sized { ... }
}

这些方法也被称作关联函数（associate function）。在trait中，方法可以有缺省的实现，对于这个Write trait，你只需要实现write和flush两个方法，其他都有缺省实现。

在刚才定义方法的时候，我们频繁看到两个特殊的关键字：Self和self。

Self代表当前的类型，比如File类型实现了Write，那么实现过程中使用到的Self就指代File。
self在用作方法的第一个参数时，实际上是self:Self的简写，所以&self是self:&Self, 而&mut self 是self: &mut Self。

5.1.2 基本 trait 练习

use std::str::FromStr;

use regex::Regex;
pub trait Parse {
    fn parse(s: &str) -> Self;
}

// 我们约束 T 必须同时实现了 FromStr 和 Default
// 这样在使用的时候我们就可以用这两个 trait 的方法了
impl<T> Parse for T
where
    T: FromStr + Default,
{
    fn parse(s: &str) -> Self {
        let re: Regex = Regex::new(r"^[0-9]+(\.[0-9]+)?").unwrap();
        // 生成一个创建缺省值的闭包，这里主要是为了简化后续代码
        // Default::default() 返回的类型根据上下文能推导出来，是 Self
        // 而我们约定了 Self，也就是 T 需要实现 Default trait
        let d = || Default::default();
        if let Some(captures) = re.captures(s) {
            captures
                .get(0)
                .map_or(d(), |s| s.as_str().parse().unwrap_or(d()))
        } else {
            d()
        }
    }
}

#[test]
fn parse_should_work() {
    assert_eq!(u32::parse("123abcd"), 123);
    assert_eq!(u32::parse("123.45abcd"), 0);
    assert_eq!(f64::parse("123.45abcd"), 123.45);
    assert_eq!(f64::parse("abcd"), 0f64);
}

fn main() {
    println!("result: {}", u8::parse("255 hello world"));
}

通过对带有约束的泛型参数实现 trait，一份代码就实现了u32 / f64等类型的Parse trait，非常精简。不过，看这段代码你有没有感觉还是有些问题？当无法正确解析字符串时，我们返回了缺省值，难道不是应该返回一个错误么？

是的。这里返回缺省值的话，会跟解析0abcd这样的情况混淆，不知道解析出的0，究竟是出错了，还是本该解析出0。

5.2、带关联类型的 trait

Rust允许 trait内部包含关联类型，实现时跟关联函数一样，它也需要实现关联类型。我们看怎么为Parse trait 添加关联类型：

pub trait Parse {
    type Error;
    fn parse(s: &str) -> Result<Self, Self::Error>;
}

有了关联类型Error，Parse trait 就可以在出错时返回合理的错误了，看修改后的代码：

use std::str::FromStr;

use regex::Regex;
pub trait Parse {
    type Error;
    fn parse(s: &str) -> Result<Self, Self::Error>
    where
        Self: Sized;
}

impl<T> Parse for T
where
    T: FromStr + Default,
{
    // 定义关联类型 Error 为 String
    type Error = String;
    fn parse(s: &str) -> Result<Self, Self::Error> {
        let re: Regex = Regex::new(r"^[0-9]+(\.[0-9]+)?").unwrap();
        if let Some(captures) = re.captures(s) {
            // 当出错时我们返回 Err(String)
            captures
                .get(0)
                .map_or(Err("failed to capture".to_string()), |s| {
                    s.as_str()
                        .parse()
                        .map_err(|_err| "failed to parse captured string".to_string())
                })
        } else {
            Err("failed to parse string".to_string())
        }
    }
}

#[test]
fn parse_should_work() {
    assert_eq!(u32::parse("123abcd"), Ok(123));
    assert_eq!(
        u32::parse("123.45abcd"),
        Err("failed to parse captured string".into())
    );
    assert_eq!(f64::parse("123.45abcd"), Ok(123.45));
    assert!(f64::parse("abcd").is_err());
}

fn main() {
    println!("result: {:?}", u8::parse("255 hello world"));
}

上面的代码中，我们允许用户把错误类型延迟到trait实现时才决定，这种带有关联类型的trait比普通trait，更加灵活，抽象度更高。

5.3、支持泛型的 trait

来看看标准库里的操作符是如何重载的，以std::ops::Add这个用于提供加法运算的trait为例：

pub trait Add<Rhs = Self> {
    type Output;
    #[must_use]
    fn add(self, rhs: Rhs) -> Self::Output;
}

这个trait有一个泛型参数Rhs，代表加号右边的值，它被用在add方法的第二个参数位。这里Rhs默认是 Self，也就是说你用Add trait，如果不提供泛型参数，那么加号右值和左值都要是相同的类型。

我们来定义一个复数类型，尝试使用下这个trait：

use std::ops::Add;

#[derive(Debug)]
struct Complex {
    real: f64,
    imagine: f64,
}

impl Complex {
    pub fn new(real: f64, imagine: f64) -> Self {
        Self { real, imagine }
    }
}

// 对 Complex 类型的实现
impl Add for Complex {
    type Output = Self;

    // 注意 add 第一个参数是 self，会移动所有权
    fn add(self, rhs: Self) -> Self::Output {
        let real = self.real + rhs.real;
        let imagine = self.imagine + rhs.imagine;
        Self::new(real, imagine)
    }
}

// 如果不想移动所有权，可以为 &Complex 实现 add，这样可以做 &c1 + &c2
impl Add for &Complex {
    // 注意返回值不应该是 Self 了，因为此时 Self 是 &Complex
    type Output = Complex;

    fn add(self, rhs: Self) -> Self::Output {
        let real = self.real + rhs.real;
        let imagine = self.imagine + rhs.imagine;
        Complex::new(real, imagine)
    }
}

// 因为 Add<Rhs = Self> 是个泛型 trait，我们可以为 Complex 实现 Add<f64>
impl Add<f64> for &Complex {
    type Output = Complex;

    // rhs 现在是 f64 了
    fn add(self, rhs: f64) -> Self::Output {
        let real = self.real + rhs;
        Complex::new(real, self.imagine)
    }
}

fn main() {
    let c1 = Complex::new(1.0, 1f64);
    let c2 = Complex::new(2 as f64, 3.0);
    println!("{:?}", &c1 + &c2);
    println!("{:?}", &c1 + 5.0);
    println!("{:?}", c1 + c2);
}

通过使用Add，为Complex实现了和f64相加的方法。所以泛型trait可以让我们在需要的时候，对同一种类型的同一个trait，有多个实现。

5.4、trait 的“继承”

在Rust中，一个trait可以继承另一个trait的关联类型和关联函数。比如 trait B: A ，是说任何类型 T，如果实现了trait B，它也必须实现trait A，换句话说，trait B 在定义时可以使用 trait A 中的关联类型和方法。

以StreamExt为例，由于StreamExt中的方法都有缺省的实现，且所有实现了Stream trait的类型都实现了 StreamExt：

impl<T: ?Sized> StreamExt for T where T: Stream {}

所以如果你实现了Stream trait，就可以直接使用StreamExt里的方法了，非常方便。

好，到这里trait就基本讲完了，简单总结一下，trait作为对不同数据结构中相同行为的一种抽象。除了基本trait 之外，

当行为和具体的数据关联时，比如字符串解析时定义的Parse trait，我们引入了带有关联类型的trait，把和行为有关的数据类型的定义，进一步延迟到trait实现的时候。
对于同一个类型的同一个trait行为，可以有不同的实现，比如我们之前大量使用的From，此时可以用泛型trait。

5.5、子类型多态

从严格意义上说，子类型多态是面向对象语言的专利。如果一个对象 A 是对象 B 的子类，那么 A 的实例可以出现在任何期望 B 的实例的上下文中，比如猫和狗都是动物，如果一个函数的接口要求传入一个动物，那么传入猫和狗都是允许的。

pub trait Formatter {
    fn format(&self, input: &mut String) -> bool;
}



struct MarkdownFormatter;
impl Formatter for MarkdownFormatter {
    fn format(&self, input: &mut String) -> bool {
        input.push_str("\nformatted with Markdown formatter");
        true
    }
}

struct RustFormatter;
impl Formatter for RustFormatter {
    fn format(&self, input: &mut String) -> bool {
        input.push_str("\nformatted with Rust formatter");
        true
    }
}

struct HtmlFormatter;
impl Formatter for HtmlFormatter {
    fn format(&self, input: &mut String) -> bool {
        input.push_str("\nformatted with HTML formatter");
        true
    }
}

pub fn format(input: &mut String, formatters: Vec<&dyn Formatter>) {
    for formatter in formatters {
        formatter.format(input);
    }
}


fn main() {
    let mut text = "Hello world!".to_string();
    let html: &dyn Formatter = &HtmlFormatter;
    let rust: &dyn Formatter = &RustFormatter;
    let formatters = vec![html, rust];
    format(&mut text, formatters);

    println!("text: {}", text);
}

所以我们要有一种手段，告诉编译器，此处需要并且仅需要任何实现了Formatter接口的数据类型。在Rust里，这种类型叫 Trait Object，表现为&dyn Trait或者Box<dyn Trait>。

这样可以在运行时，构造一个 Formatter 的列表，传递给 format 函数进行文件的格式化，这就是动态分派（dynamic dispatching）。

5.6、Trait Object 的实现机理

当需要使用Formatter trait做动态分派时，可以像如下例子一样，将一个具体类型的引用，赋给 &Formatter ：

HtmlFormatter的引用赋值给Formatter后，会生成一个Trait Object，在上图中可以看到，Trait Object 的底层逻辑就是胖指针。其中，一个指针指向数据本身，另一个则指向虚函数表（vtable）。

vtable是一张静态的表，Rust在编译时会为使用了trait object的类型的trait实现生成一张表，放在可执行文件中（一般在TEXT或RODATA段）。看下图，可以帮助你理解：

在这张表里，包含具体类型的一些信息，如size、aligment以及一系列函数指针：

这个接口支持的所有的方法，比如 format()；
具体类型的drop trait，当Trait object被释放，它用来释放其使用的所有资源。

这样，当在运行时执行 formatter.format()时，formatter就可以从vtable里找到对应的函数指针，执行具体的操作。

所以，Rust里的Trait Object没什么神秘的，它不过是我们熟知的C++/Java中vtable的一个变体而已。

这里说句题外话，C++/Java指向vtable的指针，在编译时放在类结构里，而Rust放在Trait object中。这也是为什么Rust很容易对原生类型做动态分派，而C++/Java不行。

事实上，Rust也并不区分原生类型和组合类型，对Rust来说，所有类型的地位都是一致的。

5.6.1 trait object safety

你使用trait object的时候，要注意对象安全（object safety）。只有满足对象安全的trait才能使用 trait object，在官方文档中有详细讨论。

那什么样的trait不是对象安全的呢？

如果 trait 所有的方法，返回值是 Self 或者携带泛型参数，那么这个 trait 就不能产生 trait object。

不允许返回Self，是因为trait object在产生时，原来的类型会被抹去，所以 Self 究竟是谁不知道。比如 Clone trait只有一个方法clone()，返回Self，所以它就不能产生 trait object。

不允许携带泛型参数，是因为 Rust 里带泛型的类型在编译时会做单态化，而 trait object 是运行时的产物，两者不能兼容。

比如 From trait，因为整个trait带了泛型，每个方法也自然包含泛型，就不能产生trait object。如果一个 trait只有部分方法返回Self或者使用了泛型参数，那么这部分方法在trait object中不能调用。

//如果 trait 所有的方法，返回值是 Self 或者携带泛型参数，那么这个 trait 就不能产生 trait object。
pub trait UnSafeTrait {
    fn format(&self, input: &mut String) -> Self;
}

struct MarkdownFormatter2;
impl UnSafeTrait for MarkdownFormatter2 {
    fn format(&self, input: &mut String) -> Self {
        input.push_str("\nformatted with Markdown formatter");
        MarkdownFormatter2
    }
}

fn main() {
    let md2: &dyn UnSafeTrait = &MarkdownFormatter2; // 报错 the trait `UnSafeTrait` cannot be made into an object

}

5.6.2 使用 trait 有两个注意事项：

第一，在定义和使用 trait 时，我们需要遵循孤儿规则（Orphan Rule）。
- trait 和实现 trait 的数据类型，至少有一个是在当前 crate 中定义的，也就是说，你不能为第三方的类型实现第三方的 trait，当你尝试这么做时，Rust 编译器会报错。
第二，Rust对含有async fn的trait，还没有一个很好的被标准库接受的实现。async-fn-in-traits-are-hard
- #[async_trait]。这是目前最推荐的无缝使用async trait的方法。未来async trait如果有了标准实现，我们不需要对现有代码做任何改动。

5.6.3 vtable 会为每个类型的每个 trait 实现生成一张表

use std::fmt::{Debug, Display};
use std::mem::transmute;

fn main() {
    let s1 = String::from("hello world!");
    let s2 = String::from("goodbye world!");
    // Display / Debug trait object for s
    let w1: &dyn Display = &s1;
    let w2: &dyn Debug = &s1;

    // Display / Debug trait object for s1
    let w3: &dyn Display = &s2;
    let w4: &dyn Debug = &s2;

    // 强行把 triat object 转换成两个地址 (usize, usize)
    // 这是不安全的，所以是 unsafe
    let (addr1, vtable1): (usize, usize) = unsafe { transmute(w1) };
    let (addr2, vtable2): (usize, usize) = unsafe { transmute(w2) };
    let (addr3, vtable3): (usize, usize) = unsafe { transmute(w3) };
    let (addr4, vtable4): (usize, usize) = unsafe { transmute(w4) };

    // s 和 s1 在栈上的地址，以及 main 在 TEXT 段的地址
    println!(
        "s1: {:p}, s2: {:p}, main(): {:p}",
        &s1, &s2, main as *const ()
    );
    // trait object(s / Display) 的 ptr 地址和 vtable 地址
    println!("addr1: 0x{:x}, vtable1: 0x{:x}", addr1, vtable1);
    // trait object(s / Debug) 的 ptr 地址和 vtable 地址
    println!("addr2: 0x{:x}, vtable2: 0x{:x}", addr2, vtable2);

    // trait object(s1 / Display) 的 ptr 地址和 vtable 地址
    println!("addr3: 0x{:x}, vtable3: 0x{:x}", addr3, vtable3);

    // trait object(s1 / Display) 的 ptr 地址和 vtable 地址
    println!("addr4: 0x{:x}, vtable4: 0x{:x}", addr4, vtable4);

    // 指向同一个数据的 trait object 其 ptr 地址相同
    assert_eq!(addr1, addr2);
    assert_eq!(addr3, addr4);

    // 指向同一种类型的同一个 trait 的 vtable 地址相同
    // 这里都是 String + Display
    assert_eq!(vtable1, vtable3);
    // 这里都是 String + Debug
    assert_eq!(vtable2, vtable4);
}

六、常见的trait

脑图链接

Clone/Copy trait，约定了数据被深拷贝和浅拷贝的行为；
Read/Write trait，约定了对I/O读写的行为；Iterator，约定了迭代器的行为；
Debug，约定了数据如何被以debug的方式显示出来的行为；
Default，约定数据类型的缺省值如何产生的行为；
From<T>/TryFrom<T>，约定了数据间如何转换的行为。

6.1、Clone/Copy/Drop

6.1.1 Clone trait

pub trait Clone {
  fn clone(&self) -> Self;

  fn clone_from(&mut self, source: &Self) {
    *self = source.clone()
  }
}

Clone trait有两个方法， clone()和clone_from()，后者有缺省实现，所以平时我们只需要实现clone()方法即可。如果a已经存在，用 a.clone_from(&b) 可以避免内存分配，提高效率。

Clone trait可以通过派生宏直接实现，这样能简化不少代码。如果在你的数据结构里，每一个字段都已经实现了 Clone trait，你可以用 #[derive(Clone)] ，看下面的代码：

#[derive(Clone, Debug)]
struct Developer {
  name: String,
  age: u8,
  lang: Language
}

#[allow(dead_code)]
#[derive(Clone, Debug)]
enum Language {
  Rust,
  TypeScript,
  Elixir,
  Haskell
}

fn main() {
    let dev = Developer {
        name: "Tyr".to_string(),
        age: 18,
        lang: Language::Rust
    };
    let dev1 = dev.clone();
    println!("dev: {:?}, addr of dev name: {:p}", dev, dev.name.as_str());
    println!("dev1: {:?}, addr of dev1 name: {:p}", dev1, dev1.name.as_str())
}

如果没有为Language实现Clone的话，Developer的派生宏Clone将会编译出错。运行这段代码可以看到，对于 name，也就是String类型的Clone，其堆上的内存也被Clone了一份，所以 Clone 是深度拷贝，栈内存和堆内存一起拷贝。

6.1.2 Copy trait

和Clone trait不同的是，Copy trait没有任何额外的方法，它只是一个标记trait（marker trait）。它的 trait定义：

pub trait Copy: Clone {}

这样的trait虽然没有任何行为，但它可以用作trait bound来进行类型安全检查，所以我们管它叫标记 trait。

和Clone一样，如果数据结构的所有字段都实现了Copy，也可以用 #[derive(Copy)]宏来为数据结构实现Copy。

Q: 不可变引用实现了Copy，而可变引用&mut T没有实现Copy。为什么是这样？

因为如果可变引用实现了 Copy trait，那么生成一个可变引用然后把它赋值给另一个变量时，就会违背所有权规则：同一个作用域下只能有一个可变引用。可见，Rust 标准库在哪些结构可以 Copy、哪些不可以 Copy 上，有着仔细的考量。

6.1.3 Drop trait

pub trait Drop {
    fn drop(&mut self);
}

大部分场景无需为数据结构提供Drop trait，系统默认会依次对数据结构的每个域做drop。但有两种情况你可能需要手工实现Drop。

第一种是希望在数据结束生命周期的时候做一些事情，比如记日志。
第二种是需要对资源回收的场景。编译器并不知道你额外使用了哪些资源，也就无法帮助你drop它们。比如说锁资源的释放，在MutexGuard中实现了Drop来释放锁资源：

比如：

impl<T: ?Sized> Drop for MutexGuard<'_, T> {
    #[inline]
    fn drop(&mut self) {
        unsafe {
            self.lock.poison.done(&self.poison);
            self.lock.inner.raw_unlock();
        }
    }
}

需要注意的是，Copy trait 和 Drop trait 是互斥的，两者不能共存，当你尝试为同一种数据类型实现Copy 时，也实现Drop，编译器就会报错。这其实很好理解：Copy是按位做浅拷贝，那么它会默认拷贝的数据没有需要释放的资源；而Drop恰恰是为了释放额外的资源而生的。

我们还是写一段代码来辅助理解，在代码中，强行用Box::into_raw获得堆内存的指针，放入RawBuffer结构中，这样就接管了这块堆内存的释放。

但是这个操作不会破坏Rust的正确性保证：即便你Copy了N份RawBuffer，由于无法实现Drop trait，RawBuffer指向的那同一块堆内存不会释放，所以不会出现use after free的内存安全问题。

use std::{fmt, slice};

// 注意这里，我们实现了 Copy，这是因为 *mut u8/usize 都支持 Copy
#[derive(Clone, Copy)]
struct RawBuffer {
    // 裸指针用 *const / *mut 来表述，这和引用的 & 不同
    ptr: *mut u8,
    len: usize,
}

impl From<Vec<u8>> for RawBuffer {
    fn from(vec: Vec<u8>) -> Self {
        let slice = vec.into_boxed_slice();
        Self {
            len: slice.len(),
            // into_raw 之后，Box 就不管这块内存的释放了，RawBuffer 需要处理释放
            ptr: Box::into_raw(slice) as *mut u8,
        }
    }
}

// 如果 RawBuffer 实现了 Drop trait，就可以在所有者退出时释放堆内存
// 然后，Drop trait 会跟 Copy trait 冲突，要么不实现 Copy，要么不实现 Drop
// 如果不实现 Drop，那么就会导致内存泄漏，但它不会对正确性有任何破坏
// 比如不会出现 use after free 这样的问题。
// 你可以试着把下面注释去掉，看看会出什么问题
// impl Drop for RawBuffer {
//     #[inline]
//     fn drop(&mut self) {
//         let data = unsafe { Box::from_raw(slice::from_raw_parts_mut(self.ptr, self.len)) };
//         drop(data)
//     }
// }

impl fmt::Debug for RawBuffer {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let data = self.as_ref();
        write!(f, "{:p}: {:?}", self.ptr, data)
    }
}

impl AsRef<[u8]> for RawBuffer {
    fn as_ref(&self) -> &[u8] {
        unsafe { slice::from_raw_parts(self.ptr, self.len) }
    }
}

fn main() {
    let data = vec![1, 2, 3, 4];

    let buf: RawBuffer = data.into();

    // 因为 buf 允许 Copy，所以这里 Copy 了一份
    use_buffer(buf);

    // buf 还能用
    println!("buf: {:?}", buf);
}

fn use_buffer(buf: RawBuffer) {
    println!("buf to die: {:?}", buf);

    // 这里不用特意 drop，写出来只是为了说明 Copy 出来的 buf 被 Drop 了
    drop(buf)
}

对于代码安全来说，内存泄漏危害大？还是 use after free 危害大呢？肯定是后者。Rust的底线是内存安全，所以两害相权取其轻。

6.2、Sized/Send/Sync/Unpin

6.2.1 Sized

Sized trait用于标记有具体大小的类型。在使用泛型参数时，Rust编译器会自动为泛型参数加上Sized约束，比如下面的Data和处理Data的函数process_data：

struct Data<T> {
    inner: T,
}

fn process_data<T>(data: Data<T>) {
    todo!();
}

它等价于：

struct Data<T: Sized> {
    inner: T,
}

fn process_data<T: Sized>(data: Data<T>) {
    todo!();
}

但是这个自动添加的约束有时候不太适用，在少数情况下，需要T是可变类型的，怎么办？Rust 提供了?Sized来摆脱这个约束。

trait MyDisplay {
    fn display(&self);
}

// 实现 MyDisplay trait 为具有 ?Sized 范围的泛型类型
impl<T: ?Sized> MyDisplay for T
    where
        T: std::fmt::Debug
{
    fn display(&self) {
        println!("{:?}", self);
    }
}

fn main() {
    let text: &str = "Hello, world!";
    let slice = &[1, 2, 3, 4, 5];

    (*text).display(); // 调用处理 ?Sized 的 MyDisplay trait 实现
    (*slice).display(); // 调用处理 ?Sized 的 MyDisplay trait 实现
}

这样[T]或者str类型也可以使用display方法。

6.2.2 Send/Sync

pub unsafe auto trait Send {}
pub unsafe auto trait Sync {}

这两个trait都是unsafe auto trait，auto意味着编译器会在合适的场合，自动为数据结构添加它们的实现，而 unsafe代表实现的这个trait可能会违背Rust的内存安全准则，如果开发者手工实现这两个trait ，要自己为它们的安全性负责。

Send/Sync是Rust并发安全的基础：

如果一个类型T实现了Send trait，意味着T可以安全地从一个线程移动到另一个线程，也就是说所有权可以在线程间移动。
如果一个类型T实现了Sync trait，则意味着&T可以安全地在多个线程中共享。一个类型T满足Sync trait，当且仅当&T满足Send trait。

对于Send/Sync在线程安全中的作用，可以这么看，如果一个类型 T:Send，那么T在某个线程中的独占访问是线程安全的；如果一个类型T:Sync，那么T在线程间的只读共享是安全的。

对于我们自己定义的数据结构，如果其内部的所有域都实现了Send/Sync，那么这个数据结构会被自动添加Send/Sync 。基本上原生数据结构都支持Send/Sync，也就是说，绝大多数自定义的数据结构都是满足Send/Sync的。标准库中，不支持Send/Sync的数据结构主要有：

裸指针*const T/*mut T。它们是不安全的，所以既不是Send也不是Sync。
UnsafeCell<T>不支持Sync。也就是说，任何使用了Cell或者RefCell的数据结构不支持Sync。
引用计数Rc不支持Send也不支持Sync。所以Rc无法跨线程。

如果尝试跨线程使用Rc/RefCell，会发生什么。在Rust下，如果想创建一个新的线程，需要使用 std::thread::spawn：

pub fn spawn<F, T>(f: F) -> JoinHandle<T> 
where
    F: FnOnce() -> T,
    F: Send + 'static,
    T: Send + 'static,

它的参数是一个闭包，这个闭包需要Send + 'static：

'static意思是闭包捕获的自由变量必须是一个拥有所有权的类型，或者是一个拥有静态生命周期的引用；
Send意思是，这些被捕获自由变量的所有权可以从一个线程移动到另一个线程。

从这个接口上，可以得出结论：如果在线程间传递Rc，是无法编译通过的，因为Rc的实现不支持Send和Sync。写段代码验证一下：

// Rc 既不是 Send，也不是 Sync
fn rc_is_not_send_and_sync() {
    let a = Rc::new(1);
    let b = a.clone();
    let c = a.clone();
    thread::spawn(move || {
        println!("c= {:?}", c);
    });
}

那么，RefCell可以在线程间转移所有权么？RefCell实现了Send，但没有实现Sync，所以，看起来是可以工作的：

既然Rc不能Send，我们无法跨线程使用Rc这样的数据，那么使用支持Send/Sync的Arc呢，使用Arc来获得，一个可以在多线程间共享，且可以修改的类型，可以？

// RefCell 现在有多个 Arc 持有它，虽然 Arc 是 Send/Sync，但 RefCell 不是 Sync
fn refcell_is_not_sync() {
    let a = Arc::new(RefCell::new(1));
    let b = a.clone();
    let c = a.clone();
    thread::spawn(move || {
        println!("c= {:?}", c);
    });
}

因为 Arc内部的数据是共享的，需要支持Sync的数据结构，但是RefCell不是Sync，编译失败。所以在多线程情况下，我们只能使用支持Send/Sync的Arc ，和Mutex一起，构造一个可以在多线程间共享且可以修改的类型（代码）：

use std::{
    sync::{Arc, Mutex},
    thread,
};

// Arc<Mutex<T>> 可以多线程共享且修改数据
fn arc_mutext_is_send_sync() {
    let a = Arc::new(Mutex::new(1));
    let b = a.clone();
    let c = a.clone();
    let handle = thread::spawn(move || {
        let mut g = c.lock().unwrap();
        *g += 1;
    });

    {
        let mut g = b.lock().unwrap();
        *g += 1;
    }

    handle.join().unwrap();
    println!("a= {:?}", a);
}

fn main() {
    arc_mutext_is_send_sync();
}

6.3、From/Into/AsRef/AsMut

// 第一种方法，为每一种转换提供一个方法
// 把字符串 s 转换成 Path
let v = s.to_path();
// 把字符串 s 转换成 u64
let v = s.to_u64();

// 第二种方法，为 s 和要转换的类型之间实现一个 Into<T> trait
// v 的类型根据上下文得出
let v = s.into();
// 或者也可以显式地标注 v 的类型
let v: u64 = s.into();

第一种方式，在类型T的实现里，要为每一种可能的转换提供一个方法；第二种，我们为类型T和类型U之间的转换实现一个数据转换trait，这样可以用同一个方法来实现不同的转换。

显然，第二种方法要更好，因为它符合软件开发的开闭原则（Open-Close Principle），“软件中的对象（类、模块、函数等等）对扩展是开放的，但是对修改是封闭的”。

在第一种方式下，未来每次要添加对新类型的转换，都要重新修改类型T的实现，而第二种方式，我们只需要添加一个对于数据转换trait的新实现即可。

基于这个思路，对值类型的转换和对引用类型的转换，Rust提供了两套不同的trait：

值类型到值类型的转换：From<T>/Into<T>/TryFrom<T>/TryInto<T>
引用类型到引用类型的转换：AsRef<T>/AsMut<T>

6.3.1 From/Into

pub trait From<T> {
    fn from(T) -> Self;
}

pub trait Into<T> {
    fn into(self) -> T;
}

在实现From的时候会自动实现Into。这是因为：

// 实现 From 会自动实现 Into
impl<T, U> Into<U> for T where U: From<T> {
    fn into(self) -> U {
        U::from(self)
    }
}

所以大部分情况下，只用实现From，然后这两种方式都能做数据转换，比如：

impl From<[u8; 4]> for Ipv4Addr {
    fn from(octets: [u8; 4]) -> Ipv4Addr {
        Ipv4Addr { octets }
    }
}

let s = String::from("Hello world!");
let s: String = "Hello world!".into();
let addr = Ipv4Addr::from([127u8, 0u8, 0u8, 0u8]);
let addr :IpAddr = [127u8, 0u8, 0u8, 0u8].into();

From<T> 可以根据上下文做类型推导，使用场景更多；而且因为实现了 From<T> 会自动实现Into<T>，反之不会。所以需要的时候，不要去实现 Into，只要实现 From 就好了。

此外，From和Into 还是自反的：把类型T的值转换成类型T，会直接返回。这是因为标准库有如下的实现：

// From（以及 Into）是自反的
impl<T> From<T> for T {
    fn from(t: T) -> T {
        t
    }
}

let result: i32 = i32::from(12);

注意，如果你的数据类型在转换过程中有可能出现错误，可以使用 TryFrom<T> 和 TryInto<T>，它们的用法和 From<T>/Into<T>一样，只是trait内多了一个关联类型Error，且返回的结果是Result<T, Self::Error>。

6.3.2 AsRef/AsMut

AsRef<T>/AsMut<T>用于从引用到引用的转换。还是先看它们的定义：

pub trait AsRef<T> where T: ?Sized {
    fn as_ref(&self) -> &T;
}

pub trait AsMut<T> where T: ?Sized {
    fn as_mut(&mut self) -> &mut T;
}

在trait的定义上，都允许T使用大小可变的类型，如str、[u8]等。AsMut<T>除了使用可变引用生成可变引用外，其它都和AsRef<T>一样。

来写一段代码体验一下AsRef的使用和实现：

#[allow(dead_code)]
enum Language {
    Rust,
    TypeScript,
    Elixir,
    Haskell,
}

impl AsRef<str> for Language {
    fn as_ref(&self) -> &str {
        match self {
            Language::Rust => "Rust",
            Language::TypeScript => "TypeScript",
            Language::Elixir => "Elixir",
            Language::Haskell => "Haskell",
        }
    }
}

fn print_ref(v: impl AsRef<str>) {
    println!("{}", v.as_ref());
}

fn main() {
    let lang = Language::Rust;
    // &str 实现了 AsRef<str>
    print_ref("Hello world!");
    // String 实现了 AsRef<str>
    print_ref("Hello world!".to_string());
    // 我们自己定义的 enum 也实现了 AsRef<str>
    print_ref(lang);
}

6.4、Deref/DerefMut

操作符相关的 trait ，上一讲我们已经看到了 Add<Rhs> trait，它允许你重载加法运算符。Rust为所有的运算符都提供了trait，你可以为自己的类型重载某些操作符。

今天重点要介绍的操作符是Deref和DerefMut。来看它们的定义：

pub trait Deref {
    // 解引用出来的结果类型
    type Target: ?Sized;
    fn deref(&self) -> &Self::Target;
}

pub trait DerefMut: Deref {
    fn deref_mut(&mut self) -> &mut Self::Target;
}

可以看到，DerefMut“继承”了Deref，只是它额外提供了一个deref_mut方法，用来获取可变的解引用。所以这里重点学习Deref。

let mut x = 42;
let y = &mut x;
// 解引用，内部调用 DerefMut（其实现就是 *self）
*y += 1;

可以看到，它最终指向了堆上的RcBox内部的value的地址，然后如果对其解引用的话，得到了value对应的值。以下图为例，最终打印出 v = 1。

从图中还可以看到，Deref和DerefMut是自动调用的，*b 会被展开为 *(b.deref())。

在Rust里，绝大多数智能指针都实现了Deref，我们也可以为自己的数据结构实现Deref。看一个例子（代码）：

use std::ops::{Deref, DerefMut};

#[derive(Debug)]
struct Buffer<T>(Vec<T>);

impl<T> Buffer<T> {
    pub fn new(v: impl Into<Vec<T>>) -> Self {
        Self(v.into())
    }
}

impl<T> Deref for Buffer<T> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<T> DerefMut for Buffer<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

fn main() {
    let mut buf = Buffer::new([1, 3, 2, 4]);
    // 因为实现了 Deref 和 DerefMut，这里 buf 可以直接访问 Vec<T> 的方法
    // 下面这句相当于：(&mut buf).deref_mut().sort()，也就是 (&mut buf.0).sort()
    buf.sort();
    println!("buf: {:?}", buf);
}

但是在这个例子里，数据结构Buffer<T>包裹住了Vec<T>，但这样一来，原本Vec<T>实现了的很多方法，现在使用起来就很不方便，需要用buf.0来访问。怎么办？

可以实现 Deref 和 DerefMut，这样在解引用的时候，直接访问到 buf.0，省去了代码的啰嗦和数据结构内部字段的隐藏。

在这段代码里，还有一个值得注意的地方：写buf.sort()的时候，并没有做解引用的操作，为什么会相当于访问了 buf.0.sort()呢？这是因为sort()方法第一个参数是&mut self，此时Rust编译器会强制做Deref/DerefMut 的解引用，所以这相当于 (*(&mut buf)).sort()。

6.5、Debug/Display/Default

可以看到，Debug 和 Display 两个 trait 的签名一样，都接受一个 &self 和一个&mut Formatter。那为什么要有两个一样的trait呢？

pub trait Debug {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>;
}

pub trait Display {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>;
}

这是因为Debug是为开发者调试打印数据结构所设计的，而Display是给用户显示数据结构所设计的。这也是为什么 Debug trait的实现可以通过派生宏直接生成，而Display必须手工实现。在使用的时候，Debug用{:?}来打印，Display用{}打印。

最后看Default trait。它的定义如下：

pub trait Default {
    fn default() -> Self;
}

Default trait用于为类型提供缺省值。它也可以通过derive宏 #[derive(Default)] 来生成实现，前提是类型中的每个字段都实现了jiDefault trait。在初始化一个数据结构时，我们可以部分初始化，然后剩余的部分使用 Default::default()。

Debug/Display/Default 如何使用，统一看个例子（代码）：

use std::fmt;
// struct 可以 derive Default，但我们需要所有字段都实现了 Default
#[derive(Clone, Debug, Default)]
struct Developer {
    name: String,
    age: u8,
    lang: Language,
}

// enum 不能 derive Default
#[allow(dead_code)]
#[derive(Clone, Debug)]
enum Language {
    Rust,
    TypeScript,
    Elixir,
    Haskell,
}

// 手工实现 Default
impl Default for Language {
    fn default() -> Self {
        Language::Rust
    }
}

impl Developer {
    pub fn new(name: &str) -> Self {
        // 用 ..Default::default() 为剩余字段使用缺省值
        Self {
            name: name.to_owned(),
            ..Default::default()
        }
    }
}

impl fmt::Display for Developer {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}({} years old): {:?} developer",
            self.name, self.age, self.lang
        )
    }
}

fn main() {
    // 使用 T::default()
    let dev1 = Developer::default();
    // 使用 Default::default()，但此时类型无法通过上下文推断，需要提供类型
    let dev2: Developer = Default::default();
    // 使用 T::new
    let dev3 = Developer::new("Tyr");
    println!("dev1: {}\\ndev2: {}\\ndev3: {:?}", dev1, dev2, dev3);
    // dev1: (0 years old): Rust developer
    // dev2: (0 years old): Rust developer
    // dev3: Developer { name: "Tyr", age: 0, lang: Rust }
}

在我们使用Rust开发时，trait占据了非常核心的地位。一个设计良好的trait可以大大提升整个系统的可用性和扩展性。

trait是行为的延迟绑定。我们可以在不知道具体要处理什么数据结构的前提下，先通过trait把系统的很多行为约定好。

七、智能指针

脑图链接

7.1、String

智能指针一定是一个胖指针，但胖指针不一定是一个智能指针。比如&str就只是一个胖指针，它有指向堆内存字符串的指针，同时还有关于字符串长度的元数据。

那么又有一个问题了，智能指针和结构体有什么区别呢？因为我们知道，String是用结构体定义的：

pub struct String {
    vec: Vec<u8>,
}

和普通的结构体不同的是，String实现了Deref和DerefMut，这使得它在解引用的时候，会得到&str，看下面的标准库的实现：

impl ops::Deref for String {
    type Target = str;

    fn deref(&self) -> &str {
        unsafe { str::from_utf8_unchecked(&self.vec) }
    }
}

impl ops::DerefMut for String {
    fn deref_mut(&mut self) -> &mut str {
        unsafe { str::from_utf8_unchecked_mut(&mut *self.vec) }
    }
}

另外，由于在堆上分配了数据，String还需要为其分配的资源做相应的回收。而String内部使用了Vec，所以它可以依赖Vec的能力来释放堆内存。下面是标准库中Vec的Drop trait的实现：

unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> {
    fn drop(&mut self) {
        unsafe {
            // use drop for [T]
            // use a raw slice to refer to the elements of the vector as weakest necessary type;
            // could avoid questions of validity in certain cases
            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
        }
        // RawVec handles deallocation
    }
}

所以再清晰一下定义，在Rust中，凡是需要做资源回收的数据结构，且实现了 Deref/DerefMut/Drop，都是智能指针。

7.2、`Box<T>`

我们先看Box<T>，它是Rust中最基本的在堆上分配内存的方式，绝大多数其它包含堆内存分配的数据类型，内部都是通过Box<T>完成的，比如Vec<T>。

C需要使用malloc/calloc/realloc/free来处理内存的分配，很多时候，被分配出来的内存在函数调用中来来回回使用，导致谁应该负责释放这件事情很难确定，给开发者造成了极大的心智负担。

C++在此基础上改进了一下，提供了一个智能指针unique_ptr，可以在指针退出作用域的时候释放堆内存，这样保证了堆内存的单一所有权。这个unique_ptr就是Rust的Box<T>的前身。

你看Box的定义里，内部就是一个Unique用于致敬C++，Unique是一个私有的数据结构，我们不能直接使用，它包裹了一个*const T指针，并唯一拥有这个指针。

pub struct Unique<T: ?Sized> {
    pointer: *const T,
    // NOTE: this marker has no consequences for variance, but is necessary
    // for dropck to understand that we logically own a `T`.
    //
    // For details, see:
    _marker: PhantomData<T>,
}

phantom-data

堆上分配内存的Box其实有一个缺省的泛型参数A，就需要满足Allocator trait，并且默认是 Global：

pub struct Box<T: ?Sized,A: Allocator = Global>(Unique<T>, A)

Allocator trait提供很多方法：

allocate是主要方法，用于分配内存，对应C的malloc/calloc；
deallocate，用于释放内存，对应C的free；
还有grow/shrink，用来扩大或缩小堆上已分配的内存，对应C的realloc。

可以使用 #[global_allocator] 标记宏，定义你自己的全局分配器

use jemallocator::Jemalloc;

#[global_allocator]
static GLOBAL: Jemalloc = Jemalloc;

fn main() {}

实现一个自己的内存分配Demo：

use std::alloc::{GlobalAlloc, Layout, System};

struct MyAllocator;

unsafe impl GlobalAlloc for MyAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        let data = System.alloc(layout);
        eprintln!("ALLOC: {:p}, size {}", data, layout.size());
        data
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        System.dealloc(ptr, layout);
        eprintln!("FREE: {:p}, size {}", ptr, layout.size());
    }
}

#[global_allocator]
static GLOBAL: MyAllocator = MyAllocator;

#[allow(dead_code)]
struct Matrix {
    // 使用不规则的数字如 505 可以让 dbg! 的打印很容易分辨出来
    data: [u8; 505],
}

impl Default for Matrix {
    fn default() -> Self {
        Self { data: [0; 505] }
    }
}

fn main() {
    // 在这句执行之前已经有好多内存分配
    let data = Box::new(Matrix::default());

    // 输出中有一个 1024 大小的内存分配，是 println! 导致的
    println!(
        "!!! allocated memory: {:p}, len: {}",
        &*data,
        std::mem::size_of::<Matrix>()
    );

    // data 在这里 drop，可以在打印中看到 FREE
    // 之后还有很多其它内存被释放
}

搞明白Box的内存分配，我们还很关心内存是如何释放的，来看它实现的Drop trait：

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<#[may_dangle] T: ?Sized, A: Allocator> Drop for Box<T, A> {
    fn drop(&mut self) {
        // FIXME: Do nothing, drop is currently performed by compiler.
    }
}

目前drop trait什么都没有做，编译器会自动插入deallocate的代码。这是Rust语言的一种策略：在具体实现还没有稳定下来之前，我先把接口稳定，实现随着之后的迭代慢慢稳定。

7.3、PhantomData

现在要设计一个User和Product数据结构，它们都有一个u64类型的id。然而我希望每个数据结构的id只能和同种类型的id比较，也就是说如果user.id和product.id比较，编译器就能直接报错，拒绝这种行为。该怎么做呢？

如果你使用过任何其他支持泛型的语言，无论是 Java、Swift还是TypeScript，可能都接触过Phantom Type（幽灵类型）的概念。像刚才的写法，Swift/TypeScript会让其通过，因为它们的编译器会自动把多余的泛型参数当成 Phantom type来用,比如下面TypeScript的例子，可以编译：

// NotUsed is allowed
class MyNumber<T, NotUsed> {
    inner: T;
    add: (x: T, y: T) => T;
}

但Rust对此有洁癖。Rust并不希望在定义类型时，出现目前还没使用，但未来会被使用的泛型参数，所以Rust编译器对此无情拒绝，把门关得严严实实。

不过Rust知道Phantom Type的必要性，所以开了一扇叫PhantomData的窗户：让我们可以用PhantomData来持有Phantom Type。但它被广泛用在处理，数据结构定义过程中不需要，但是在实现过程中需要的泛型参数。

实现user.id, product.id 不能比较的Demo：

use std::marker::PhantomData;

#[derive(Debug, Default, PartialEq, Eq)]
pub struct Identifier<T> {
    inner: u64,
    _tag: PhantomData<T>,
}

#[derive(Debug, Default, PartialEq, Eq)]
pub struct User {
    id: Identifier<Self>,
}

#[derive(Debug, Default, PartialEq, Eq)]
pub struct Product {
    id: Identifier<Self>,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn id_should_not_be_the_same() {
        let user = User::default();
        let product = Product::default();

        // 两个 id 不能比较，因为他们属于不同的类型
        // assert_ne!(user.id, product.id);

        assert_eq!(user.id.inner, product.id.inner);
    }
}

在定义数据结构时，对于额外的、暂时不需要的泛型参数，用PhantomData来“拥有”它们，这样可以规避编译器的报错。PhantomData正如其名，它实际上长度为零，是个ZST（Zero-Sized Type），就像不存在一样，唯一作用就是类型的标记。

7.4、Cow<’a, B>

它是一个 enum，可以包含一个对类型B的只读引用，或者包含对类型B的拥有所有权的数据。定义：

pub enum Cow<'a, B> where B: 'a + ToOwned + ?Sized {
  Borrowed(&'a B),
  Owned(<B as ToOwned>::Owned),
}


impl ToOwned for str {
    type Owned = String; // Borrowed<str>
    #[inline]
    fn to_owned(&self) -> String {
        unsafe { String::from_utf8_unchecked(self.as_bytes().to_owned()) }
    }

    fn clone_into(&self, target: &mut String) {
        let mut b = mem::take(target).into_bytes();
        self.as_bytes().clone_into(&mut b);
        *target = unsafe { String::from_utf8_unchecked(b) }
    }
}

    
impl Borrow<str> for String {
    #[inline]
    fn borrow(&self) -> &str {
        &self[..]
    }
}

Cow是智能指针，那它自然需要实现 Deref trait：

impl<B: ?Sized + ToOwned> Deref for Cow<'_, B> {
    type Target = B;

    fn deref(&self) -> &B {
        match *self {
            Borrowed(borrowed) => borrowed,
            Owned(ref owned) => owned.borrow(),
        }
    }
}

实现的原理很简单，根据self是Borrowed还是Owned，我们分别取其内容，生成引用：

对于Borrowed，直接就是引用；
对于Owned，调用其borrow()方法，获得引用。

使用Demo：

use std::borrow::Cow;

use url::Url;
fn main() {
    let url = Url::parse("https://tyr.com/rust?page=1024&sort=desc&extra=hello%20world").unwrap();
    let mut pairs = url.query_pairs();

    assert_eq!(pairs.count(), 3);

    let (mut k, v) = pairs.next().unwrap();
    // 因为 k, v 都是 Cow<str> 他们用起来感觉和 &str 或者 String 一样
    // 此刻，他们都是 Borrowed
    println!("key: {}, v: {}", k, v);
    // 当修改发生时，k 变成 Owned
    k.to_mut().push_str("_lala");

    print_pairs((k, v));

    print_pairs(pairs.next().unwrap());
    // 在处理 extra=hello%20world 时，value 被处理成 "hello world"
    // 所以这里 value 是 Owned
    print_pairs(pairs.next().unwrap());
}

fn print_pairs(pair: (Cow<str>, Cow<str>)) {
    println!("key: {}, value: {}", show_cow(pair.0), show_cow(pair.1));
}

fn show_cow(cow: Cow<str>) -> String {
    match cow {
        Cow::Borrowed(v) => format!("Borrowed {}", v),
        Cow::Owned(v) => format!("Owned {}", v),
    }
}

7.5、MutexGuard

MutexGuard<T>是另外一类很有意思的智能指针：它不但通过Deref提供良好的用户体验，还通过 Drop trait 来确保，使用到的内存以外的资源在退出时进行释放。

MutexGuard这个结构是在调用Mutex::lock时生成的：

pub fn lock(&self) -> LockResult<MutexGuard<'_, T>> {
    unsafe {
        self.inner.raw_lock();
        MutexGuard::new(self)
    }
}

首先，它会取得锁资源，如果拿不到，会在这里等待；如果拿到了，会把Mutex结构的引用传递给MutexGuard。

我们看MutexGuard的定义以及它的Deref和Drop的实现，很简单：

// 这里用 must_use，当你得到了却不使用 MutexGuard 时会报警
#[must_use = "if unused the Mutex will immediately unlock"]
pub struct MutexGuard<'a, T: ?Sized + 'a> {
    lock: &'a Mutex<T>,
    poison: poison::Guard,
}

impl<T: ?Sized> Deref for MutexGuard<'_, T> {
    type Target = T;

    fn deref(&self) -> &T {
        unsafe { &*self.lock.data.get() }
    }
}

impl<T: ?Sized> DerefMut for MutexGuard<'_, T> {
    fn deref_mut(&mut self) -> &mut T {
        unsafe { &mut *self.lock.data.get() }
    }
}

impl<T: ?Sized> Drop for MutexGuard<'_, T> {
    #[inline]
    fn drop(&mut self) {
        unsafe {
            self.lock.poison.done(&self.poison);
            self.lock.inner.raw_unlock();
        }
    }
}

从代码中可以看到，当MutexGuard结束时，Mutex会做unlock，这样用户在使用Mutex时，可以不必关心何时释放这个互斥锁。因为无论你在调用栈上怎样传递MutexGuard ，哪怕在错误处理流程上提前退出，Rust有所有权机制，可以确保只要MutexGuard离开作用域，锁就会被释放。

使用Demo：

use lazy_static::lazy_static;
use std::borrow::Cow;
use std::collections::HashMap;
use std::sync::{Arc, Mutex};
use std::thread;
use std::time::Duration;

// lazy_static 宏可以生成复杂的 static 对象
lazy_static! {
    // 一般情况下 Mutex 和 Arc 一起在多线程环境下提供对共享内存的使用
    // 如果你把 Mutex 声明成 static，其生命周期是静态的，不需要 Arc
    static ref METRICS: Mutex<HashMap<Cow<'static, str>, usize>> =
        Mutex::new(HashMap::new());
}

fn main() {
    // 用 Arc 来提供并发环境下的共享所有权（使用引用计数）
    let metrics: Arc<Mutex<HashMap<Cow<'static, str>, usize>>> =
        Arc::new(Mutex::new(HashMap::new()));
    for _ in 0..32 {
        let m = metrics.clone();
        thread::spawn(move || {
            let mut g = m.lock().unwrap();
            // 此时只有拿到 MutexGuard 的线程可以访问 HashMap
            let data = &mut *g;
            // Cow 实现了很多数据结构的 From trait，
            // 所以我们可以用 "hello".into() 生成 Cow
            let entry = data.entry("hello".into()).or_insert(0);
            *entry += 1;
            // MutexGuard 被 Drop，锁被释放
        });
    }

    thread::sleep(Duration::from_millis(100));

    println!("metrics: {:?}", metrics.lock().unwrap());
}

7.6、实现自己的智能指针

内部用一个字节表示字符串的长度，用30个字节表示字符串内容，再加上1个字节的tag，正好也是32字节，可以和 String放在一个enum里使用。

示例代码：

use std::{fmt, ops::Deref, str};

const MINI_STRING_MAX_LEN: usize = 30;

// MyString 里，String 有 3 个 word，供 24 字节，所以它以 8 字节对齐
// 所以 enum 的 tag + padding 最少 8 字节，整个结构占 32 字节。
// MiniString 可以最多有 30 字节（再加上 1 字节长度和 1字节 tag），就是 32 字节.
struct MiniString {
    len: u8,
    data: [u8; MINI_STRING_MAX_LEN],
}

impl MiniString {
    // 这里 new 接口不暴露出去，保证传入的 v 的字节长度小于等于 30
    fn new(v: impl AsRef<str>) -> Self {
        let bytes = v.as_ref().as_bytes();
        // 我们在拷贝内容时一定要使用字符串的字节长度
        let len = bytes.len();
        let mut data = [0u8; MINI_STRING_MAX_LEN];
        data[..len].copy_from_slice(bytes);
        Self {
            len: len as u8,
            data,
        }
    }
}

impl Deref for MiniString {
    type Target = str;

    fn deref(&self) -> &Self::Target {
        // 由于生成 MiniString 的接口是隐藏的，它只能来自字符串，所以下面这行是安全的
        str::from_utf8(&self.data[..self.len as usize]).unwrap()
        // 也可以直接用 unsafe 版本
        // unsafe { str::from_utf8_unchecked(&self.data[..self.len as usize]) }
    }
}

impl fmt::Debug for MiniString {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // 这里由于实现了 Deref trait，可以直接得到一个 &str 输出
        write!(f, "{}", self.deref())
    }
}

#[derive(Debug)]
enum MyString {
    Inline(MiniString),
    Standard(String),
}

// 实现 Deref 接口对两种不同的场景统一得到 &str
impl Deref for MyString {
    type Target = str;

    fn deref(&self) -> &Self::Target {
        match *self {
            MyString::Inline(ref v) => v.deref(),
            MyString::Standard(ref v) => v.deref(),
        }
    }
}

impl From<&str> for MyString {
    fn from(s: &str) -> Self {
        match s.len() > MINI_STRING_MAX_LEN {
            true => Self::Standard(s.to_owned()),
            _ => Self::Inline(MiniString::new(s)),
        }
    }
}

impl fmt::Display for MyString {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.deref())
    }
}

fn main() {
    let len1 = std::mem::size_of::<MyString>();
    let len2 = std::mem::size_of::<MiniString>();
    println!("Len: MyString {}, MiniString {}", len1, len2);

    let s1: MyString = "hello world".into();
    let s2: MyString = "这是一个超过了三十个字节的很长很长的字符串".into();

    // debug 输出
    println!("s1: {:?}, s2: {:?}", s1, s2);
    // display 输出
    println!(
        "s1: {}({} bytes, {} chars), s2: {}({} bytes, {} chars)",
        s1,
        s1.len(),
        s1.chars().count(),
        s2,
        s2.len(),
        s2.chars().count()
    );

    // MyString 可以使用一切 &str 接口，感谢 Rust 的自动 Deref
    assert!(s1.ends_with("world"));
    assert!(s2.starts_with("这"));
}

八、集合容器

集合容器，顾名思义，就是把一系列拥有相同类型的数据放在一起，统一处理，比如：

我们熟悉的字符串String、数组[T; n]、列表Vec和哈希表HashMap等；
虽然到处在使用，但还并不熟悉的切片slice；
在其他语言中使用过，但在Rust中还没有用过的循环缓冲区VecDeque、双向列表LinkedList等。

8.1、切片

在Rust里，切片是描述一组属于同一类型、长度不确定的、在内存中连续存放的数据结构，用[T]来表述。因为长度不确定，所以切片是个 DST（Dynamically Sized Type）。

切片一般只出现在数据结构的定义中，不能直接访问，在使用中主要用以下形式：

&[T]：表示一个只读的切片引用。
&mut [T]：表示一个可写的切片引用。
Box<[T]>：一个在堆上分配的切片。

怎么理解切片呢？我打个比方，切片之于具体的数据结构，就像数据库中的视图之于表。你可以把它看成一种工具，让我们可以统一访问行为相同、结构类似但有些许差异的类型。

来看下面的代码，辅助理解：

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let vec = vec![1, 2, 3, 4, 5];
    let s1 = &arr[..2];
    let s2 = &vec[..2];
    println!("s1: {:?}, s2: {:?}", s1, s2);

    // &[T] 和 &[T] 是否相等取决于长度和内容是否相等
    assert_eq!(s1, s2);
    // &[T] 可以和 Vec<T>/[T;n] 比较，也会看长度和内容
    assert_eq!(&arr[..], vec);
    assert_eq!(&vec[..], arr);
}

对于array和vector，虽然是不同的数据结构，一个放在栈上，一个放在堆上，但它们的切片是类似的；而且对于相同内容数据的相同切片，比如 &arr[1…3] 和 &vec[1…3]，这两者是等价的。除此之外，切片和对应的数据结构也可以直接比较，这是因为它们之间实现了 PartialEq trait。

Vec<T>、&[T]和&Vec<T>关系：

在使用的时候，支持切片的具体数据类型，你可以根据需要，解引用转换成切片类型。比如Vec和[T; n]会转化成为 &[T]，这是因为Vec实现了Deref trait，而array内建了到&[T]的解引用。

8.2、迭代器 Iterator

迭代器可以说是切片的孪生兄弟。切片是集合数据的视图，而迭代器定义了对集合数据的各种各样的访问操作。

通过切片的iter()方法，我们可以生成一个迭代器，对切片进行迭代。

iterator trait有大量的方法，但绝大多数情况下，我们只需要定义它的关联类型Item和next()方法。

Item定义了每次我们从迭代器中取出的数据类型；

next()是从迭代器里取下一个值的方法。当一个迭代器的next()方法返回None时，表明迭代器中没有数据了。

  #[must_use = "iterators are lazy and do nothing unless consumed"]
  pub trait Iterator {
      type Item;
      fn next(&mut self) -> Option<Self::Item>;
      // 大量缺省的方法，包括 size_hint, count, chain, zip, map, 
      // filter, for_each, skip, take_while, flat_map, flatten
      // collect, partition 等
      ... 
  }

看一个例子，对Vec使用iter()方法，并进行各种 map/filter/take 操作。在函数式编程语言中，这样的写法很常见，代码的可读性很强。Rust也支持这种写法：

fn main() {
    // 这里 Vec<T> 在调用 iter() 时被解引用成 &[T]，所以可以访问 iter()
    let result = vec![1, 2, 3, 4]
        .iter()
        .map(|v| v * v)
        .filter(|v| *v < 16)
        .take(1)
        .collect::<Vec<_>>();

    println!("{:?}", result);
}

整个过程是这样的：

在collect()执行的时候，它实际试图使用FromIterator从迭代器中构建一个集合类型，这会不断调用next()获取下一个数据；
此时的Iterator是Take，Take调自己的next()，也就是它会调用Filter的next()；
Filter的next()实际上调用自己内部的iter的find()，此时内部的iter是Map，find()会使用 try_fold()，它会继续调用next()，也就是Map的next()；
Map的next()会调用其内部的iter取next()然后执行map函数。而此时内部的iter来自Vec<i32>。

所以，只有在collect()时，才触发代码一层层调用下去，并且调用会根据需要随时结束。这段代码中我们使用了 take(1)，整个调用链循环一次，就能满足take(1)以及所有中间过程的要求，所以它只会循环一次。

8.3、&str、String、&String

8.4、`Vet<T>`、`Box<[T]>`、&T、&mut T

Box<[T]>是一个比较有意思的存在，它和Vec<T>有一点点差别：Vec<T> 有额外的capacity，可以增长；而 Box<[T]>一旦生成就固定下来，没有capacity，也无法增长。

那么如何产生 Box<[T]> 呢？目前可用的接口就只有一个：从已有的Vec中转换。我们看代码：

use std::ops::Deref;

fn main() {
    let mut v1 = vec![1, 2, 3, 4];
    v1.push(5);
    println!("cap should be 8: {}", v1.capacity());

    // 从 Vec<T> 转换成 Box<[T]>，此时会丢弃多余的 capacity
    let b1 = v1.into_boxed_slice();
    let mut b2 = b1.clone();

    let v2 = b1.into_vec();
    println!("cap should be exactly 5: {}", v2.capacity());

    assert!(b2.deref() == v2);

    // Box<[T]> 可以更改其内部数据，但无法 push
    b2[0] = 2;
    // b2.push(6);
    println!("b2: {:?}", b2);

    // 注意 Box<[T]> 和 Box<[T; n]> 并不相同
    let b3 = Box::new([2, 2, 3, 4, 5]);
    println!("b3: {:?}", b3);

    // b2 和 b3 相等，但 b3.deref() 和 v2 无法比较
    assert!(b2 == b3);
    // assert!(b3.deref() == v2);
}

运行代码可以看到，Vec<T>可以通过into_boxed_slice()转换成Box<[T]>，Box<[T]>也可以通过into_vec()转换回Vec<T>。

这两个转换都是很轻量的转换，只是变换一下结构，不涉及数据的拷贝。区别是，当Vec<T>转换成Box<[T]>时，没有使用到的容量就会被丢弃，所以整体占用的内存可能会降低。而且Box<[T]>有一个很好的特性是，不像Box<[T;n]>那样在编译时就要确定大小，它可以在运行期生成，以后大小不会再改变。

所以，**当我们需要在堆上创建固定大小的集合数据，且不希望自动增长，那么，可以先创建 Vec，再转换成 Box<[T]>**。tokio在提供broadcast channel时，就使用了Box<[T]> 这个特性，你感兴趣的话，可以自己看看源码。

fn main() {
    let vec = vec![1, 2, 3];

    let result = vec_to_array(vec);

    match result {
        Some(arr) => println!("Array: {:?}", arr),
        None => println!("Conversion failed"),
    }
}

// 将 Vec<i32> 转换为 [i32; 3] 数组
fn vec_to_array(vec: Vec<i32>) -> Option<[i32; 3]> {
    if vec.len() == 3 {
        let mut array = [0; 3];  // 创建一个固定大小的新数组

        // 转换 Vec<i32> 为 slice，尝试将其转换为 [i32; 3] 数组引用
        let slice = vec.as_slice().try_into().unwrap();

        // 使用 clone_from_slice 将数组引用的内容复制到新数组中
        array.clone_from_slice(slice);

        Some(array)
    } else {
        None
    }
}

九、哈希表

Google的工程师Matt Kulukundis在cppCon 2017 做的一个演讲，说：全世界Google的服务器上1%的CPU时间用来做哈希表的计算，超过4%的内存用来存储哈希表。足以证明哈希表的重要性。

A hash map implemented with quadratic probing and SIMD lookup.

二次探查（quadratic probing）和SIMD查表（SIMD lookup）它们是Rust哈希表算法的设计核心。

如何解决哈希冲突？

理论上，主要的冲突解决机制有链地址法（chaining）和开放寻址法（open addressing）。

开放寻址法把整个哈希表看做一个大数组，不引入额外的内存，当冲突产生时，按照一定的规则把数据插入到其它空闲的位置。比如线性探寻（linear probing）在出现哈希冲突时，不断往后探寻，直到找到空闲的位置插入。

而二次探查，理论上是在冲突发生时，不断探寻哈希位置加减n的二次方，找到空闲的位置插入，我们看图，更容易理解：

9.1、HashMap 的数据结构

use hashbrown::hash_map as base;

#[derive(Clone)]
pub struct RandomState {
    k0: u64,
    k1: u64,
}

pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}

可以看到，HashMap有三个泛型参数，K和V代表key/value 的类型，S是哈希算法的状态，它默认是 RandomState，占两个u64。RandomState使用SipHash作为缺省的哈希算法，它是一个加密安全的哈希函数（cryptographically secure hashing）。

从定义中还能看到，Rust的HashMap复用了hashbrown的HashMap。hashbrown是Rust下对 Google Swiss Table 的一个改进版实现，我们打开hashbrown 的代码，看它的结构：

pub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
    pub(crate) hash_builder: S,
    pub(crate) table: RawTable<(K, V), A>,
}

可以看到，HashMap里有两个域，一个是hash_builder，类型是刚才我们提到的标准库使用的RandomState，还有一个是具体的RawTable：

pub struct RawTable<T, A: Allocator + Clone = Global> {
    table: RawTableInner<A>,
    // Tell dropck that we own instances of T.
    marker: PhantomData<T>,
}

struct RawTableInner<A> {
    // Mask to get an index from a hash value. The value is one less than the
    // number of buckets in the table.
    bucket_mask: usize,

    // [Padding], T1, T2, ..., Tlast, C1, C2, ...
    //                                ^ points here
    ctrl: NonNull<u8>,

    // Number of elements that can be inserted before we need to grow the table
    growth_left: usize,

    // Number of elements in the table, only really used by len()
    items: usize,

    alloc: A,
}

RawTable中，实际上有意义的数据结构是RawTableInner，前四个字段很重要：

usize的bucket_mask，是哈希表中哈希桶的数量减一；
名字叫ctrl的指针，它指向哈希表堆内存末端的ctrl区；
usize的字段growth_left，指哈希表在下次自动增长前还能存储多少数据；
usize的items，表明哈希表现在有多少数据。

这里最后的alloc字段，和RawTable的marker一样，只是一个用来占位的类型，我们现在只需知道，它用来分配在堆上的内存。

9.1.1 HashMap 的基本使用方法

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    explain("empty", &map);

    map.insert('a', 1);
    explain("added 1", &map);

    map.insert('b', 2);
    map.insert('c', 3);
    explain("added 3", &map);

    map.insert('d', 4);
    explain("added 4", &map);

    // get 时需要使用引用，并且也返回引用
    assert_eq!(map.get(&'a'), Some(&1));
    assert_eq!(map.get_key_value(&'b'), Some((&'b', &2)));

    map.remove(&'a');
    // 删除后就找不到了
    assert_eq!(map.contains_key(&'a'), false);
    assert_eq!(map.get(&'a'), None);
    explain("removed", &map);
    // shrink 后哈希表变小
    map.shrink_to_fit();
    explain("shrinked", &map);
}

fn explain<K, V>(name: &str, map: &HashMap<K, V>) {
    println!("{}: len: {}, cap: {}", name, map.len(), map.capacity());
}

9.2、HashMap 的内存布局

但是通过HashMap的公开接口，我们无法看到HashMap在内存中是如何布局的，还是需要借助之前使用过的 std::mem::transmute方法，来把数据结构打出来：

use std::collections::HashMap;

fn main() {
    let map = HashMap::new();
    let mut map = explain("empty", map);

    map.insert('a', 1);
    let mut map = explain("added 1", map);
    map.insert('b', 2);
    map.insert('c', 3);

    let mut map = explain("added 3", map);

    map.insert('d', 4);

    let mut map = explain("added 4", map);

    map.remove(&'a');

    explain("final", map);
}

// HashMap 结构有两个 u64 的 RandomState，然后是四个 usize，
// 分别是 bucket_mask, ctrl, growth_left 和 items
// 我们 transmute 打印之后，再 transmute 回去
fn explain<K, V>(name: &str, map: HashMap<K, V>) -> HashMap<K, V> {
    let arr: [usize; 6] = unsafe { std::mem::transmute(map) };
    println!(
        "{}: bucket_mask 0x{:x}, ctrl 0x{:x}, growth_left: {}, items: {}",
        name, arr[2], arr[3], arr[4], arr[5]
    );
    unsafe { std::mem::transmute(arr) }
}

可以看到

empty: bucket_mask 0x0, ctrl 0x1056df820, growth_left: 0, items: 0
added 1: bucket_mask 0x3, ctrl 0x7fa0d1405e30, growth_left: 2, items: 1
added 3: bucket_mask 0x3, ctrl 0x7fa0d1405e30, growth_left: 0, items: 3
added 4: bucket_mask 0x7, ctrl 0x7fa0d1405e90, growth_left: 3, items: 4
final: bucket_mask 0x7, ctrl 0x7fa0d1405e90, growth_left: 4, items: 3

在OS X下，一开始哈希表为空，ctrl地址看上去是一个TEXT/RODATA段的地址，应该是指向了一个默认的空表地址；插入第一个数据后，哈希表分配了4个bucket，ctrl地址发生改变；在插入三个数据后，growth_left为零，再插入时，哈希表重新分配，ctrl地址继续改变。

因为哈希表有8个bucket（0x7 + 1），每个bucket大小是key（char+value（i32）的大小，也就是8个字节，所以一共是64个字节。对于这个例子，通过ctrl地址减去64，就可以得到哈希表的堆内存起始地址。然后，我们可以用rust-gdb/rust-lldb来打印这个内存。

9.2.1 Ctrl表

一张ctrl表里，有若干个128bit或者说16个字节的分组（group），group里的每个字节叫ctrl byte，对应一个bucket，那么一个group对应16个bucket。如果一个bucket对应的ctrl byte首位不为1，就表示这个ctrl byte被使用；如果所有位都是1，或者说这个字节是 0xff，那么它是空闲的。

一组control byte的整个128 bit 的数据，可以通过一条指令被加载进来，然后和某个值进行mask，找到它所在的位置。这就是一开始提到的SIMD查表。

具体怎么操作，我们来看HashMap是如何通过ctrl表来进行数据查询的。假设这张表里已经添加了一些数据，我们现在要查找key为c的数据：

首先对c做哈希，得到一个哈希值h；
把h跟bucket_mask做与，得到一个值，图中是139；
拿着这个139，找到对应的ctrl group的起始位置，因为ctrl group以16为一组，所以这里找到128；
用SIMD指令加载从128对应地址开始的16个字节；
对hash取头7个bit，然后和刚刚取出的16个字节一起做与，找到对应的匹配，如果找到了，它（们）很大概率是要找的值；
如果不是，那么以二次探查（以16的倍数不断累积）的方式往后查找，直到找到为止。

所以，当HashMap插入和删除数据，以及因此导致重新分配的时候，主要工作就是在维护这张ctrl表和数据的对应。

因为ctrl表是所有操作最先触及的内存，所以在 HashMap 的结构中，堆内存的指针直接指向ctrl表，而不是指向堆内存的起始位置，这样可以减少一次内存的访问。

9.2.2 哈希表重新分配与增长

首先，哈希表会按幂扩容，从4个bucket扩展到8个bucket。

这会导致分配新的堆内存，然后原来的ctrl table和对应的kv数据会被移动到新的内存中。这个例子里因为char和 i32实现了Copy trait，所以是拷贝；如果key的类型是String，那么只有String的24个字节 (ptr|cap|len) 的结构被移动，String的实际内存不需要变动。

9.3、删除一个值

当要在哈希表中删除一个值时，整个过程和查找类似，先要找到要被删除的key所在的位置。在找到具体位置后，并不需要实际清除内存，只需要将它的ctrl byte设回 0xff（或者标记成删除状态）。这样，这个bucket就可以被再次使用了：

这里有一个问题，当key/value有额外的内存时，比如String，它的内存不会立即回收，只有在下一次对应的bucket 被使用时，让HashMap不再拥有这个String的所有权之后，这个String的内存才被回收。我们看下面的示意图：

一般来说，这并不会带来什么问题，顶多是内存占用率稍高一些。但某些极端情况下，比如在哈希表中添加大量内容，又删除大量内容后运行，这时你可以通过shrink_to_fit/shrink_to 释放掉不需要的内存。

9.4、自定义 Hash key

有时候，我们需要让自定义的数据结构成为HashMap的key。此时，要使用到三个 trait：Hash、PartialEq、Eq，不过这三个trait都可以通过派生宏自动生成。其中：

实现了Hash，可以让数据结构计算哈希；
实现了PartialEq/Eq，可以让数据结构进行相等和不相等的比较。Eq实现了比较的自反性（a == a）、对称性（a == b则b == a）以及传递性（a == b，b == c，则a == c），PartialEq没有实现自反性。

Demo：

use std::{
    collections::{hash_map::DefaultHasher, HashMap},
    hash::{Hash, Hasher},
};

// 如果要支持 Hash，可以用 #[derive(Hash)]，前提是每个字段都实现了 Hash
// 如果要能作为 HashMap 的 key，还需要 PartialEq 和 Eq
#[derive(Debug, Hash, PartialEq, Eq)]
struct Student<'a> {
    name: &'a str,
    age: u8,
}

impl<'a> Student<'a> {
    pub fn new(name: &'a str, age: u8) -> Self {
        Self { name, age }
    }
}
fn main() {
    let mut hasher = DefaultHasher::new();
    let student = Student::new("Tyr", 18);
    // 实现了 Hash 的数据结构可以直接调用 hash 方法
    student.hash(&mut hasher);
    let mut map = HashMap::new();
    // 实现了 Hash / PartialEq / Eq 的数据结构可以作为 HashMap 的 key
    map.insert(student, vec!["Math", "Writing"]);
    println!("hash: 0x{:x}, map: {:?}", hasher.finish(), map);
}

9.5、HashSet/BTreeMap/BTreeSet

有时我们只需要简单确认元素是否在集合中，如果用HashMap就有些浪费空间了。这时可以用HashSet，它就是简化的 HashMap，可以用来存放无序的集合，定义直接是HashMap：

use hashbrown::hash_set as base;

pub struct HashSet<T, S = RandomState> {
    base: base::HashSet<T, S>,
}

pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
    pub(crate) map: HashMap<T, (), S, A>,
}

另一个和HashMap一样常用的数据结构就是BTreeMap 了。BTreeMap是内部使用B-tree来组织哈希表的数据结构。另外BTreeSet和HashSet类似，是BTreeMap的简化版，可以用来存放有序集合。

pub struct BTreeMap<K, V> {
    root: Option<Root<K, V>>,
    length: usize,
}

pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;

pub struct NodeRef<BorrowType, K, V, Type> {
    height: usize,
    node: NonNull<LeafNode<K, V>>,
    _marker: PhantomData<(BorrowType, Type)>,
}

struct LeafNode<K, V> {
    parent: Option<NonNull<InternalNode<K, V>>>,
    parent_idx: MaybeUninit<u16>,
    len: u16,
    keys: [MaybeUninit<K>; CAPACITY],
    vals: [MaybeUninit<V>; CAPACITY],
}

struct InternalNode<K, V> {
    data: LeafNode<K, V>,
    edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B],
}

有序Demo：

use std::collections::BTreeMap;

fn main() {
    let map = BTreeMap::new();
    let mut map = explain("empty", map);

    for i in 0..16usize {
        map.insert(format!("Tyr {}", i), i);
    }

    let mut map = explain("added", map);

    map.remove("Tyr 1");

    let map = explain("remove 1", map);

    for item in map.iter() {
        println!("{:?}", item);
    }
}

// BTreeMap 结构有 height，node 和 length
// 我们 transmute 打印之后，再 transmute 回去
fn explain<K, V>(name: &str, map: BTreeMap<K, V>) -> BTreeMap<K, V> {
    let arr: [usize; 3] = unsafe { std::mem::transmute(map) };
    println!(
        "{}: height: {}, root node: 0x{:x}, len: 0x{:x}",
        name, arr[0], arr[1], arr[2]
    );
    unsafe { std::mem::transmute(arr) }
}

// 输出
("Tyr 0", 0)
("Tyr 10", 10)
("Tyr 11", 11)
("Tyr 12", 12)
("Tyr 13", 13)
("Tyr 14", 14)
("Tyr 15", 15)
("Tyr 2", 2)
("Tyr 3", 3)
("Tyr 4", 4)
("Tyr 5", 5)
("Tyr 6", 6)
("Tyr 7", 7)
("Tyr 8", 8)
("Tyr 9", 9)

可以看到，在遍历时，BTreeMap会按照key的顺序把值打印出来。如果你想让自定义的数据结构可以作为BTreeMap的key，那么需要实现PartialOrd和Ord，这两者的关系和PartialEq/Eq类似，PartialOrd也没有实现自反性。同样的，PartialOrd和Ord也可以通过派生宏来实现。

9.5.1 为什么 Rust 的 HashMap 要缺省采用加密安全的哈希算法？

我们知道哈希表在软件系统中的重要地位，但哈希表在最坏情况下，如果绝大多数key的hash都碰撞在一起，性能会到 O(n)，这会极大拖累系统的效率。

比如1M大小的session表，正常情况下查表速度是O(1)，但极端情况下，需要比较1M个数据后才能找到，这样的系统就容易被DoS攻击。所以如果不是加密安全的哈希函数，只要黑客知道哈希算法，就可以构造出大量的key产生足够多的哈希碰撞，造成目标系统DoS。

SipHash 就是为了回应DoS攻击而创建的哈希算法，虽然和sha2这样的加密哈希不同（不要将SipHash用于加密！），但它可以提供类似等级的安全性。把SipHash作为 HashMap的缺省的哈希算法，Rust可以避免开发者在不知情的情况下被DoS，就像曾经在Web世界发生的那样。

当然，这一切的代价是性能损耗，虽然SipHash非常快，但它比hashbrown缺省使用的Ahash慢了不少。如果你确定使用的HashMap不需要DoS防护（比如一个完全内部使用的HashMap），那么可以用 Ahash 来替换。你只需要使用Ahash提供的RandomState即可：

十、错误处理

错误处理的主流方法.png

脑图链接

十一、闭包：FnOnce、FnMut、Fn

闭包是将函数，或者说代码和其环境一起存储的一种数据结构。闭包引用的上下文中的自由变量，会被捕获到闭包的结构中，成为闭包类型的一部分（第二讲）。

之前的课程中，多次见到了创建新线程的 thread::spawn，它的参数就是一个闭包：

pub fn spawn<F, T>(f: F) -> JoinHandle<T> 
where
    F: FnOnce() -> T,
    F: Send + 'static,
    T: Send + 'static,

仔细看这个接口：

F: FnOnce() → T，表明F是一个接受0个参数、返回T的闭包。
F: Send + 'static，说明闭包F这个数据结构，需要静态生命周期或者拥有所有权，并且它还能被发送给另一个线程。
T: Send + 'static，说明闭包F返回的数据结构T，需要静态生命周期或者拥有所有权，并且它还能被发送给另一个线程。

11.1、闭包本质上是什么？

闭包是一种匿名类型，一旦声明，就会产生一个新的类型，但这个类型无法被其它地方使用。这个类型就像一个结构体，会包含所有捕获的变量。

use std::{collections::HashMap, mem::size_of_val};
fn main() {
    // 长度为 0
    let c1 = || println!("hello world!");
    // 和参数无关，长度也为 0
    let c2 = |i: i32| println!("hello: {}", i);
    let name = String::from("tyr");
    let name1 = name.clone();
    let mut table = HashMap::new();
    table.insert("hello", "world");
    // 如果捕获一个引用，长度为 8
    let c3 = || println!("hello: {}", name);
    // 捕获移动的数据 name1(长度 24) + table(长度 48)，closure 长度 72
    let c4 = move || println!("hello: {}, {:?}", name1, table);
    let name2 = name.clone();
    // 和局部变量无关，捕获了一个 String name2，closure 长度 24
    let c5 = move || {
        let x = 1;
        let name3 = String::from("lindsey");
        println!("hello: {}, {:?}, {:?}", x, name2, name3);
    };

    println!(
        "c1: {}, c2: {}, c3: {}, c4: {}, c5: {}, main: {}",
        size_of_val(&c1),
        size_of_val(&c2),
        size_of_val(&c3),
        size_of_val(&c4),
        size_of_val(&c5),
        size_of_val(&main),
    )
}

c1没有参数，也没捕获任何变量，从代码输出可以看到，c1长度为0；
c2有一个i32作为参数，没有捕获任何变量，长度也为0，可以看出参数跟闭包的大小无关；
c3捕获了一个对变量name的引用，这个引用是&String，长度为8。而c3的长度也是8；
c4捕获了变量name1和table，由于用了move，它们的所有权移动到了c4中。c4长度是72，恰好等于 String的24字节，加上HashMap的48字节。
c5捕获了name2，name2的所有权移动到了c5，虽然c5有局部变量，但它的大小和局部变量也无关，c5的大小等于String的24字节。

加 move 和不加 move，这两种闭包有什么本质上的不同？

可以看到，不带move时，闭包捕获的是对应自由变量的引用；
带move时，对应自由变量的所有权会被移动到闭包结构中。

还知道了，闭包的大小跟参数、局部变量都无关，只跟捕获的变量有关。

而c4捕获的name和table，内存结构和下面的结构体一模一样：

struct Closure4 {
    name: String,  // (ptr|cap|len)=24字节
    table: HashMap<&str, &str> // (RandomState(16)|mask|ctrl|left|len)=48字节
}

不过，对于closure类型来说，编译器知道像函数一样调用闭包c4()是合法的，并且知道执行c4()时，代码应该跳转到什么地址来执行。在执行过程中，如果遇到name、table，可以从自己的数据结构中获取。

那么多想一步，闭包捕获变量的顺序，和其内存结构的顺序是一致的么？的确如此，如果我们调整闭包里使用name1和table的顺序：

let c4 = move || println!("hello: {:?}, {}", table, name1);

其数据的位置是相反的，类似于：

struct Closure4 {
    table: HashMap<&str, &str> // (RandomState(16)|mask|ctrl|left|len)=48字节
    name: String,  // (ptr|cap|len)=24字节
}

不过这只是逻辑上的位置，struct在内存的排布，Rust 编译器会重排内存，让数据能够以最小的代价对齐，所以有些情况下，内存中数据的顺序可能和struct定义不一致。

所以回到刚才闭包和结构体的比较。在Rust里，闭包产生的匿名数据类型，格式和struct是一样的。看图中gdb的输出，闭包是存储在栈上，并且除了捕获的数据外，闭包本身不包含任何额外函数指针指向闭包的代码。如果理解了c3/c4 这两个闭包，c5是如何构造的就很好理解了。

现在，你是不是可以回答为什么thread::spawn对传入的闭包约束是Send + 'static了？究竟什么样的闭包满足它呢？很明显，使用了move且move到闭包内的数据结构满足Send，因为此时，闭包的数据结构拥有所有数据的所有权，它的生命周期是'static。

11.1.1 不同语言的闭包设计

闭包最大的问题是变量的多重引用导致生命周期不明确，所以你先想，其它支持闭包的语言（lambda 也是闭包），它们的闭包会放在哪里？

因为闭包这玩意，从当前上下文中捕获了些变量，变得有点不伦不类，不像函数那样清楚，尤其是这些被捕获的变量，它们的归属和生命周期处理起来很麻烦。所以，大部分编程语言的闭包很多时候无法放在栈上，需要额外的堆分配。你可以看这个 Golang 的例子。

不光Golang，Java/Swift/Python/JavaScript 等语言都是如此，这也是为什么大多数编程语言闭包的性能要远低于函数调用。因为使用闭包就意味着：额外的堆内存分配、潜在的动态分派（很多语言会把闭包处理成函数指针）、额外的内存回收。

在其他语言中，闭包变量因为多重引用导致生命周期不明确，但Rust从一开始就消灭了这个问题：

如果不使用move转移所有权，闭包会引用上下文中的变量，这个引用受借用规则的约束，所以只要编译通过，那么闭包对变量的引用就不会超过变量的生命周期，没有内存安全问题。
如果使用move转移所有权，上下文中的变量在转移后就无法访问，闭包完全接管这些变量，它们的生命周期和闭包一致，所以也不会有内存安全问题。

而Rust为每个闭包生成一个新的类型，又使得调用闭包时可以直接和代码对应，省去了使用函数指针再转一道手的额外消耗。

11.2、FnOnce

定义：

pub trait FnOnce<Args> {
    type Output;
    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

FnOnce有一个关联类型Output，显然，它是闭包返回值的类型；还有一个方法call_once，要注意的是 call_once第一个参数是self，它会转移self的所有权到call_once函数中。

这也是为什么FnOnce被称作Once ：它只能被调用一次。再次调用，编译器就会报变量已经被move这样的常见所有权错误了。

fn main() {
    let name = String::from("Tyr");
    // 这个闭包啥也不干，只是把捕获的参数返回去
    let c = move |greeting: String| (greeting, name);

    let result = c("hello".to_string());

    println!("result: {:?}", result);

    // 无法再次调用
    let result = c("hi".to_string());
}

这个闭包c，啥也没做，只是把捕获的参数返回。就像一个结构体里，某个字段被转移走之后，就不能再访问一样，闭包内部的数据一旦被转移，这个闭包就不完整了，也就无法再次使用，所以它是一个FnOnce的闭包。

如果一个闭包并不转移自己的内部数据，那么它就不是FnOnce，然而，一旦它被当做FnOnce调用，自己会被转移到call_once函数的作用域中，之后就无法再次调用了，我们看个例子（代码）：

fn main() {
    let name = String::from("Tyr");

    // 这个闭包会 clone 内部的数据返回，所以它不是 FnOnce
    let c = move |greeting: String| (greeting, name.clone());

    // 所以 c1 可以被调用多次

    println!("c1 call once: {:?}", c("qiao".into()));
    println!("c1 call twice: {:?}", c("bonjour".into()));

    // 然而一旦它被当成 FnOnce 被调用，就无法被再次调用
    println!("result: {:?}", call_once("hi".into(), c));

    // 无法再次调用
    // let result = c("hi".to_string());

    // Fn 也可以被当成 FnOnce 调用，只要接口一致就可以
    println!("result: {:?}", call_once("hola".into(), not_closure));
}

fn call_once(arg: String, c: impl FnOnce(String) -> (String, String)) -> (String, String) {
    c(arg)
}

fn not_closure(arg: String) -> (String, String) {
    (arg, "Rosie".into())
}

11.3、FnMut

理解了FnOnce，我们再来看FnMut，它的定义如下：

pub trait FnMut<Args>: FnOnce<Args> {
    extern "rust-call" fn call_mut(
        &mut self, 
        args: Args
    ) -> Self::Output;
}

首先，FnMut“继承”了FnOnce，或者说FnOnce是FnMut的super trait。所以FnMut也拥有Output这个关联类型和call_once这个方法。此外，它还有一个call_mut()方法。注意call_mut()传入&mut self，它不移动self，所以FnMut可以被多次调用。

因为FnOnce是FnMut的super trait，所以，一个FnMut闭包，可以被传给一个需要FnOnce的上下文，此时调用闭包相当于调用了call_once()。

如果你理解了前面讲的闭包的内存组织结构，那么FnMut就不难理解，就像结构体如果想改变数据需要用let mut声明一样，如果你想改变闭包捕获的数据结构，那么就需要FnMut。我们看个例子（代码）：

fn main() {
    let mut name = String::from("hello");
    let mut name1 = String::from("hola");

    // 捕获 &mut name
    let mut c = || {
        name.push_str(" Tyr");
        println!("c: {}", name);
    };

    // 捕获 mut name1，注意 name1 需要声明成 mut
    let mut c1 = move || {
        name1.push_str("!");
        println!("c1: {}", name1);
    };

    c();
    c1();

    call_mut(&mut c);
    call_mut(&mut c1);

    call_once(c);
    call_once(c1);
}

// 在作为参数时，FnMut 也要显式地使用 mut，或者 &mut
fn call_mut(c: &mut impl FnMut()) {
    c();
}

// 想想看，为啥 call_once 不需要 mut？
fn call_once(c: impl FnOnce()) {
    c();
}

在声明的闭包c和c1里，我们修改了捕获的name和name1。不同的是name使用了引用，而name1移动了所有权，这两种情况和其它代码一样，也需要遵循所有权和借用有关的规则。所以，如果在闭包c里借用了name，你就不能把name移动给另一个闭包c1。

这里也展示了，c和c1这两个符合FnMut的闭包，能作为FnOnce来调用。我们在代码中也确认了，FnMut可以被多次调用，这是因为call_mut()使用的是&mut self，不移动所有权。

11.4、Fn

pub trait Fn<Args>: FnMut<Args> {
    extern "rust-call" fn call(&self, args: Args) -> Self::Output;
}

可以看到，它“继承”了FnMut，或者说FnMut是Fn的super trait。这也就意味着任何需要FnOnce或者FnMut的场合，都可以传入满足Fn的闭包。我们继续看例子（代码）：

fn main() {
    let v = vec![0u8; 1024];
    let v1 = vec![0u8; 1023];

    // Fn，不移动所有权
    let mut c = |x: u64| v.len() as u64 * x;
    // Fn，移动所有权
    let mut c1 = move |x: u64| v1.len() as u64 * x;

    println!("direct call: {}", c(2));
    println!("direct call: {}", c1(2));

    println!("call: {}", call(3, &c));
    println!("call: {}", call(3, &c1));

    println!("call_mut: {}", call_mut(4, &mut c));
    println!("call_mut: {}", call_mut(4, &mut c1));

    println!("call_once: {}", call_once(5, c));
    println!("call_once: {}", call_once(5, c1));
}

fn call(arg: u64, c: &impl Fn(u64) -> u64) -> u64 {
    c(arg)
}

fn call_mut(arg: u64, c: &mut impl FnMut(u64) -> u64) -> u64 {
    c(arg)
}

fn call_once(arg: u64, c: impl FnOnce(u64) -> u64) -> u64 {
    c(arg)
}

11.5、闭包的使用场景

fn map<B, F>(self, f: F) -> Map<Self, F>
where
    Self: Sized,
    F: FnMut(Self::Item) -> B,
{
    Map::new(self, f)
}

可以看到，Iterator的map()方法接受一个FnMut，它的参数是Self::Item，返回值是没有约束的泛型参数 B。Self::Item是Iterator::next()方法吐出来的数据，被map之后，可以得到另一个结果。

use std::ops::Mul;

fn main() {
    let c1 = curry(5);
    println!("5 multiply 2 is: {}", c1(2));

    let adder2 = curry(3.14);
    println!("pi multiply 4^2 is: {}", adder2(4. * 4.));
}

fn curry<T>(x: T) -> impl Fn(T) -> T
where
    T: Mul<Output = T> + Copy,
{
    move |y| x * y
}

最后，闭包还有一种并不少见，但可能不太容易理解的用法：为它实现某个trait，使其也能表现出其他行为，而不仅仅是作为函数被调用。比如说有些接口既可以传入一个结构体，又可以传入一个函数或者闭包。

我们看一个tonic（Rust下的gRPC库）的例子：

pub trait Interceptor {
    /// Intercept a request before it is sent, optionally cancelling it.
    fn call(&mut self, request: crate::Request<()>) -> Result<crate::Request<()>, Status>;
}

impl<F> Interceptor for F
where
    F: FnMut(crate::Request<()>) -> Result<crate::Request<()>, Status>,
{
    fn call(&mut self, request: crate::Request<()>) -> Result<crate::Request<()>, Status> {
        self(request)
    }
}

self是谁？ self指代的是F。F是闭包，本质上是特殊的结构体。他有自己的域，一个是从外面捕获的变量作为域一个是自己的局部变量作为域将request传递进去，也就是从外部捕捉的变量作为域。通过闭包本身的关联函数，将这些域的值给计算返回一个Result结果那么看上去就是位闭包实现一个trait 这样trait本身的行为就可以通过闭包来调用他自己的方法，将本身的行为也就是方法给改写成另外一种了。也就是做和说的表现出其他行为。这个其他行为就是通过闭包调用他本身的函数而改写后的行为。

在这个例子里，Interceptor有一个call方法，它可以让gRPC Request被发送出去之前被修改，一般是添加各种头，比如Authorization头。

11.5.1 小结

Rust闭包的效率非常高。首先闭包捕获的变量，都储存在栈上，没有堆内存分配。其次因为闭包在创建时会隐式地创建自己的类型，每个闭包都是一个新的类型。通过闭包自己唯一的类型，Rust 不需要额外的函数指针来运行闭包，所以闭包的调用效率和函数调用几乎一致。

Rust支持三种不同的闭包trait：FnOnce、FnMut和Fn。FnOnce是FnMut的super trait，而FnMut又是Fn的super trait。从这些trait的接口可以看出，

FnOnce只能调用一次；
FnMut允许在执行时修改闭包的内部数据，可以执行多次；
Fn不允许修改闭包的内部数据，也可以执行多次。

总结一下三种闭包使用的情况以及它们之间的关系：

十二、unsafe

12.1 unsafe trait

Rust里，名气最大的unsafe代码应该就是Send/Sync这两个trait了：

pub unsafe auto trait Send {}
pub unsafe auto trait Sync {}

因为Send/Sync是auto trait，所以大部分情况下，你自己的数据结构不需要实现Send/Sync，然而，当你在数据结构里使用裸指针时，因为裸指针是没有实现 Send/Sync 的，连带着你的数据结构也就没有实现 Send/Sync。但很可能你的结构是线程安全的，你也需要它线程安全。

此时，如果你可以保证它能在线程中安全地移动，那可以实现Send；如果可以保证它能在线程中安全地共享，也可以去实现Sync。之前我们讨论过的Bytes就在使用裸指针的情况下实现了Send/Sync：

pub struct Bytes {
    ptr: *const u8,
    len: usize,
    // inlined "trait object"
    data: AtomicPtr<()>,
    vtable: &'static Vtable,
}

// Vtable must enforce this behavior
unsafe impl Send for Bytes {}
unsafe impl Sync for Bytes {}

但是，在实现 Send/Sync 的时候要特别小心，如果你无法保证数据结构的线程安全，错误实现 Send/Sync 之后，会导致程序出现莫名其妙的还不太容易复现的崩溃。

比如下面的代码，强行为Evil实现了Send，而Evil内部携带的Rc是不允许实现Send的。这段代码通过实现Send而规避了Rust的并发安全检查，使其可以编译通过（代码）：

use std::{cell::RefCell, rc::Rc, thread};

#[derive(Debug, Default, Clone)]
struct Evil {
    data: Rc<RefCell<usize>>,
}

// 为 Evil 强行实现 Send，这会让 Rc 整个紊乱
unsafe impl Send for Evil {}

fn main() {
    let v = Evil::default();
    let v1 = v.clone();
    let v2 = v.clone();

    let t1 = thread::spawn(move || {
        let v3 = v.clone();
        let mut data = v3.data.borrow_mut();
        *data += 1;
        println!("v3: {:?}", data);
    });

    let t2 = thread::spawn(move || {
        let v4 = v1.clone();
        let mut data = v4.data.borrow_mut();
        *data += 1;
        println!("v4: {:?}", data);
    });

    t2.join().unwrap();
    t1.join().unwrap();

    let mut data = v2.data.borrow_mut();
    *data += 1;

    println!("v2: {:?}", data);
}

任何trait，只要声明成unsafe，它就是一个unsafe trait。而一个正常的trait里也可以包含unsafe函数，我们看下面的示例（代码）：

// 实现这个 trait 的开发者要保证实现是内存安全的
unsafe trait Foo {
    fn foo(&self);
}

trait Bar {
    // 调用这个函数的人要保证调用是安全的
    unsafe fn bar(&self);
}

struct Nonsense;

unsafe impl Foo for Nonsense {
    fn foo(&self) {
        println!("foo!");
    }
}

impl Bar for Nonsense {
    unsafe fn bar(&self) {
        println!("bar!");
        }
    }
    
    fn main() {
        let nonsense = Nonsense;
        // 调用者无需关心 safety
        nonsense.foo();
    
        // 调用者需要为 safety 负责
        unsafe { nonsense.bar() };
    }

unsafe trait是对trait的实现者的约束，它告诉trait的实现者：实现我的时候要小心，要保证内存安全，所以实现的时候需要加unsafe关键字。

但unsafe trait对于调用者来说，可以正常调用，不需要任何unsafe block，因为这里的safety已经被实现者保证了，毕竟如果实现者没保证，调用者也做不了什么来保证safety，就像我们使用Send/Sync一样。

而unsafe fn是函数对调用者的约束，它告诉函数的调用者：如果你胡乱使用我，会带来内存安全方面的问题，请妥善使用，所以调用unsafe fn时，需要加unsafe block提醒别人注意。

再来看一个实现和调用都是unsafe的trait：GlobalAlloc。

use std::alloc::{GlobalAlloc, Layout, System};

struct MyAllocator;

unsafe impl GlobalAlloc for MyAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        let data = System.alloc(layout);
        eprintln!("ALLOC: {:p}, size {}", data, layout.size());
        data
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        System.dealloc(ptr, layout);
        eprintln!("FREE: {:p}, size {}", ptr, layout.size());
    }
}

#[global_allocator]
static GLOBAL: MyAllocator = MyAllocator;

12.2、unsafe 函数

use std::collections::HashMap;

fn main() {
    let map = HashMap::new();
    let mut map = explain("empty", map);

    map.insert(String::from("a"), 1);
    explain("added 1", map);
}

// HashMap 结构有两个 u64 的 RandomState，然后是四个 usize，
// 分别是 bucket_mask, ctrl, growth_left 和 items
// 我们 transmute 打印之后，再 transmute 回去
fn explain<K, V>(name: &str, map: HashMap<K, V>) -> HashMap<K, V> {
    let arr: [usize; 6] = unsafe { std::mem::transmute(map) };
    println!(
        "{}: bucket_mask 0x{:x}, ctrl 0x{:x}, growth_left: {}, items: {}",
        name, arr[2], arr[3], arr[4], arr[5]
    );

    // 因为 std:mem::transmute 是一个 unsafe 函数，所以我们需要 unsafe
    unsafe { std::mem::transmute(arr) }
}

要调用一个unsafe函数，你需要使用unsafe block把它包裹起来。这相当于在提醒大家，注意啊，这里有unsafe 代码！

另一种调用unsafe函数的方法是定义unsafe fn，然后在这个unsafe fn里调用其它unsafe fn。

// safe 版本，验证合法性，如果不合法返回错误
pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
    run_utf8_validation(v)?;
    // SAFETY: Just ran validation.
    Ok(unsafe { from_utf8_unchecked(v) })
}

// 不验证合法性，调用者需要确保 &[u8] 里都是合法的字符
pub const unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
    // SAFETY: the caller must guarantee that the bytes `v` are valid UTF-8.
    // Also relies on `&str` and `&[u8]` having the same layout.
    unsafe { mem::transmute(v) }
}

12.3 对裸指针解引用

裸指针在生成的时候无需unsafe，因为它并没有内存不安全的操作，但裸指针的解引用操作是不安全的，潜在有风险，它也需要使用unsafe来明确告诉编译器，以及代码的阅读者，也就是说要使用unsafe block包裹起来。

fn main() {
    // let r1 = 0x123 as *mut u32;
    // unsafe { *r1 += 1; } // panic
    
    let mut age = 18;
    // 不可变指针
    let r1 = &age as *const i32;
    // 可变指针
    let r2 = &mut age as *mut i32;
    // 使用裸指针，可以绕过 immutable / mutable borrow rule
    // 然而，对指针解引用需要使用 unsafe
    unsafe {
        println!("r1: {}, r2: {}", *r1, *r2);
        *r2 = 10;
    }
    println!("{}", age); // 10
}

我们可以看到，使用裸指针，可变指针和不可变指针可以共存，不像可变引用和不可变引用无法共存。这是因为裸指针的任何对内存的操作，无论是ptr::read/ptr::write，还是解引用，都是unsafe的操作，所以只要读写内存，裸指针的使用者就需要对内存安全负责。

12.4 FFI

FFI ：Foreign Function Interface/语言交互接口。

当Rust要使用其它语言的能力时，Rust编译器并不能保证那些语言具备内存安全，所以和第三方语言交互的接口，一律要使用unsafe，比如，我们调用libc来进行C语言开发者熟知的malloc/free（代码）：

use std::mem::transmute;

fn main() {
    let data = unsafe {
        let p = libc::malloc(8);
        let arr: &mut [u8; 8] = transmute(p);
        arr
    };

    data.copy_from_slice(&[1, 2, 3, 4, 5, 6, 7, 8]);

    println!("data: {:?}", data);

    unsafe { libc::free(transmute(data)) };
}

12.4.1 FFI Demo

[dependencies]
anyhow = "1"

[build-dependencies]
bindgen = "0.59"

其中bindgen需要在编译期使用，所以我们在根目录下创建一个build.rs使其在编译期运行：

fn main() {
    // 告诉 rustc 需要 link bzip2
    println!("cargo:rustc-link-lib=bz2");

    // 告诉 cargo 当 wrapper.h 变化时重新运行
    println!("cargo:rerun-if-changed=wrapper.h");

    // 配置 bindgen，并生成 Bindings 结构
    let bindings = bindgen::Builder::default()
        .header("wrapper.h")
        .parse_callbacks(Box::new(bindgen::CargoCallbacks))
        .generate()
        .expect("Unable to generate bindings");

    // 生成 Rust 代码
    bindings
        .write_to_file("src/bindings.rs")
        .expect("Failed to write bindings");
}

12.5 不推荐 unsafe 的场景

12.5.1 访问或者修改可变静态变量

use std::thread;

static mut COUNTER: usize = 1;

fn main() {
    let t1 = thread::spawn(move || {
        unsafe { COUNTER += 10 };
    });

    let t2 = thread::spawn(move || {
        unsafe { COUNTER *= 10 };
    });

    t2.join().unwrap();
    t1.join().unwrap();

    unsafe { println!("COUNTER: {}", COUNTER) };
}

可以用Atomic来替代

use std::{
    sync::atomic::{AtomicUsize, Ordering},
    thread,
};

static COUNTER: AtomicUsize = AtomicUsize::new(1);

fn main() {
    let t1 = thread::spawn(move || {
        COUNTER.fetch_add(10, Ordering::SeqCst);
    });

    let t2 = thread::spawn(move || {
        COUNTER
            .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |v| Some(v * 10))
            .unwrap();
    });

    t2.join().unwrap();
    t1.join().unwrap();

    println!("COUNTER: {}", COUNTER.load(Ordering::Relaxed));
}

12.5.2 在宏里使用 unsafe

首先使用你的宏的开发者，可能压根不知道unsafe代码的存在；其次，含有unsafe代码的宏在被使用到的时候，相当于把unsafe代码注入到当前上下文中。在不知情的情况下，开发者到处调用这样的宏，会导致unsafe代码充斥在系统的各个角落，不好处理；最后，一旦unsafe代码出现问题，你可能都很难找到问题的根本原因。

// Generate implementation for dyn $name
macro_rules! downcast_dyn {
    ($name:ident) => {
        /// A struct with a private constructor, for use with
        /// `__private_get_type_id__`. Its single field is private,
        /// ensuring that it can only be constructed from this module
        #[doc(hidden)]
        #[allow(dead_code)]
        pub struct PrivateHelper(());

        impl dyn $name + 'static {
            /// Downcasts generic body to a specific type.
            #[allow(dead_code)]
            pub fn downcast_ref<T: $name + 'static>(&self) -> Option<&T> {
                if self.__private_get_type_id__(PrivateHelper(())).0
                    == std::any::TypeId::of::<T>()
                {
                    // SAFETY: external crates cannot override the default
                    // implementation of `__private_get_type_id__`, since
                    // it requires returning a private type. We can therefore
                    // rely on the returned `TypeId`, which ensures that this
                    // case is correct.
                    unsafe { Some(&*(self as *const dyn $name as *const T)) }
                } else {
                    None
                }
            }

            /// Downcasts a generic body to a mutable specific type.
            #[allow(dead_code)]
            pub fn downcast_mut<T: $name + 'static>(&mut self) -> Option<&mut T> {
                if self.__private_get_type_id__(PrivateHelper(())).0
                    == std::any::TypeId::of::<T>()
                {
                    // SAFETY: external crates cannot override the default
                    // implementation of `__private_get_type_id__`, since
                    // it requires returning a private type. We can therefore
                    // rely on the returned `TypeId`, which ensures that this
                    // case is correct.
                    unsafe { Some(&mut *(self as *const dyn $name as *const T as *mut T)) }
                } else {
                    None
                }
            }
        }
    };
}

其他

1、Rust 特点

Rust的变量默认是不可变的，如果要修改变量的值，需要显式地使用mut关键字。
除了let/static/const/fn等少数语句外，Rust绝大多数代码都是表达式（expression）。所以 if/while/for/loop都会返回一个值，函数最后一个表达式就是函数的返回值，这和函数式编程语言一致。
Rust支持面向接口编程和泛型编程。
Rust有非常丰富的数据类型和强大的标准库。
Rust有非常丰富的控制流程，包括模式匹配（pattern match）。

2、基本语法和基础数据类型

变量和函数

前面说到，Rust支持类型推导，在编译器能够推导类型的情况下，变量类型一般可以省略，但常量（const）和静态变量（static）必须声明类型。

定义变量的时候，根据需要，你可以添加mut关键字让变量具备可变性。默认变量不可变是一个很重要的特性，它符合最小权限原则（Principle of Least Privilege），有助于我们写出健壮且正确的代码。当你使用mut却没有修改变量，Rust 编译期会友好地报警，提示你移除不必要的 mut。

函数是一等公民，可以作为参数或者返回值。

fn apply(value: i32, f: fn(i32) -> i32) -> i32 {
    f(value)
}

fn square(value: i32) -> i32 {
    value * value
}

fn cube(value: i32) -> i32 {
    value * value * value
}

fn main() {
    println!("apply square: {}", apply(2, square));
    println!("apply cube: {}", apply(2, cube));
}

数据结构

数据结构是程序的核心组成部分，在对复杂的问题进行建模时，我们就要自定义数据结构。Rust非常强大，可以用 struct定义结构体，用enum定义标签联合体（tagged union），还可以像Python一样随手定义元组（tuple）类型。

#[derive(Debug)]
enum Gender {
  Unspecified = 0,
  Female = 1,
  Male = 2,
}

// UserId/TopicId ：struct 的特殊形式，称为元组结构体。它的域都是匿名的，可以用索引访问，适用于简单的结构体。
#[derive(Debug, Copy, Clone)]
struct UserId(u64);

#[derive(Debug, Copy, Clone)]
struct TopicId(u64);


// User/Topic：标准的结构体，可以把任何类型组合在结构体里使用。
#[derive(Debug)]
struct User {
  id: UserId,
  name: String,
  gender: Gender,
}

#[derive(Debug)]
struct Topic {
  id: TopicId,
  name: String,
  owner: UserId,
}

// Event：标准的标签联合体，它定义了三种事件：Join、Leave、Message。每种事件都有自己的数据结构。
// 定义聊天室中可能发生的事件
#[derive(Debug)]
enum Event {
  Join((UserId, TopicId)),
  Leave((UserId, TopicId)),
  Message((UserId, TopicId, String)),
}

fn main() {
    let alice = User { id: UserId(1), name: "Alice".into(), gender: Gender::Female };
    let bob = User { id: UserId(2), name: "Bob".into(), gender: Gender::Male };
    
    let topic = Topic { id: TopicId(1), name: "rust".into(), owner: UserId(1) };
    let event1 = Event::Join((alice.id, topic.id));
    let event2 = Event::Join((bob.id, topic.id));
    let event3 = Event::Message((alice.id, topic.id, "Hello world!".into()));
    
    println!("event1: {:?}, event2: {:?}, event3: {:?}", event1, event2, event3);
}

3、控制流程

4、模式匹配

fn process_event(event: &Event) {
    match event {
        Event::Join((uid, _tid)) => println!("user {:?} joined", uid),
        Event::Leave((uid, tid)) => println!("user {:?} left {:?}", uid, tid),
        Event::Message((_, _, msg)) => println!("broadcast: {}", msg),
    }
}


fn process_message(event: &Event) {
    if let Event::Message((_, _, msg)) = event {
        println!("broadcast: {}", msg);   
    }
}

5、Rust 项目的组织

当Rust代码规模越来越大时，我们就无法用单一文件承载代码了，需要多个文件甚至多个目录协同工作，这时我们可以用 mod来组织代码。

具体做法是：在项目的入口文件lib.rs/main.rs 里，用mod来声明要加载的其它代码文件。如果模块内容比较多，可以放在一个目录下，在该目录下放一个mod.rs引入该模块的其它文件。这个文件，和Python的__init__.py有异曲同工之妙。这样处理之后，就可以用mod+目录名引入这个模块了，如下图所示：

在Rust里，一个项目也被称为一个crate。crate可以是可执行项目，也可以是一个库，我们可以用cargo new <name> --lib来创建一个库。当crate里的代码改变时，这个crate需要被重新编译。

当代码规模继续增长，把所有代码放在一个crate里就不是一个好主意了，因为任何代码的修改都会导致这个crate重新编译，这样效率不高。我们可以使用workspace。

一个workspace可以包含一到多个crates，当代码发生改变时，只有涉及的crates才需要重新编译。当我们要构建一个workspace时，需要先在某个目录下生成一个如图所示的Cargo.toml，包含workspace里所有的crates，然后可以cargo new生成对应的crates：

6、常见问题

Q：如果我想创建双向链表，该怎么处理？

Rust标准库有 LinkedList，它是一个双向链表的实现。但是当你需要使用链表的时候，可以先考虑一下，同样的需求是否可以用列表Vec<T>、循环缓冲区VecDeque<T>来实现。因为，链表对缓存非常不友好，性能会差很多。

你也许好奇为什么Rust标准库的LinkedList不用Rc/Weak，那是因为标准库直接用NonNull指针和unsafe。

Q：为什么我的函数返回一个引用的时候，编译器总是跟我过不去？

函数返回引用时，除非是静态引用，那么这个引用一定和带有引用的某个输入参数有关。输入参数可能是&self、&mut self或者&T/&mut T。我们要建立正确的输入和返回值之间的关系，这个关系和函数内部的实现无关，只和函数的签名有关。

pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq

我们并不用实现它或者知道它如何实现，就可以确定返回值Option<&V>到底跟谁有关系。因为这里只有两个选择：&self或者k: &Q。显然是&self，因为HashMap持有数据，而k只是用来在HashMap里查询的key。

当你要返回在函数执行过程中，创建的或者得到的数据，和参数无关，那么无论它是一个有所有权的数据，还是一个引用，你只能返回带所有权的数据。对于引用，这就意味着调用clone()或者to_owned()来，从引用中得到所有权。

Q：为什么标准库的数据结构比如 Rc / Vec 用那么多 unsafe，但别人总是告诉我，unsafe 不好？

标准库的责任是，在保证安全的情况下，即使牺牲一定的可读性，也要用最高效的手段来实现要实现的功能；同时，为标准库的用户提供一个优雅、高级的抽象，让他们可以在绝大多数场合下写出漂亮的代码，无需和丑陋打交道。

Rust中，unsafe代码把程序的正确性和安全性交给了开发者来保证，而标准库的开发者花了大量的精力和测试来保证这种正确性和安全性。而我们自己撰写unsafe代码时，除非有经验丰富的开发者review 代码，否则，有可能疏于对并发情况的考虑，写出了有问题的代码。

所以只要不是必须，建议不要写unsafe代码。毕竟大部分我们要处理的问题，都可以通过良好的设计、合适的数据结构和算法来实现。

Q: 下面代码为什么会报错

use std::str::Chars;

// 错误，为什么？
fn lifetime1() -> &str {
    let name = "Tyr".to_string();
    &name[1..]
}

// 错误，为什么？
fn lifetime2(name: String) -> &str {
    &name[1..]
}

// 正确，为什么？
fn lifetime3(name: &str) -> Chars {
    name.chars()
}

第一个，没有标注生命周期，但即使标注也不对，因为返回值引用了本地已经drop的String，会造成悬垂指针问题；

第二个，和第一个类似，因为参数是具有所有权的String，该String会在函数执行完后被drop，返回值不能引用该 String；

第三个，因为Chars的完整定义是Chars<'a>，根据生命周期标注规则，Chars内部的引用的生命周期和参数name 一致，所以不会产生问题。

《Rust 编程第一课》

一、所有权

1.1、变量在函数调用时发生了什么

1.2、所有权和 Move 语义

1.3、Copy 语义

1.4、Borrow 语义

1.5、Rc

1.6、RefCell 和内部可变性

1.7、Arc 和 Mutex/RwLock

二、生命周期

2.1、值的生命周期

2.2、生命周期标注

三、内存管理

3.1、值的创建

3.2、值的使用

3.3、值的销毁

四、类型系统

4.1、类型系统基本概念与分类

4.2、Rust 类型系统

4.3、泛型

五、trait

5.1、什么是trait

5.2、带关联类型的 trait

5.3、支持泛型的 trait

5.4、trait 的“继承”

5.5、子类型多态

5.6、Trait Object 的实现机理

六、常见的trait

6.1、Clone/Copy/Drop

6.2、Sized/Send/Sync/Unpin

6.3、From/Into/AsRef/AsMut

6.4、Deref/DerefMut

6.5、Debug/Display/Default

七、智能指针

7.1、String

7.2、Box<T>

7.3、PhantomData

7.4、Cow<’a, B>

7.5、MutexGuard

7.6、实现自己的智能指针

八、集合容器

8.1、切片

8.2、迭代器 Iterator

8.3、&str、String、&String

8.4、Vet<T>、Box<[T]>、&T、&mut T

九、哈希表

9.1、HashMap 的数据结构

9.2、HashMap 的内存布局

9.3、删除一个值

9.4、自定义 Hash key

9.5、HashSet/BTreeMap/BTreeSet

十、错误处理

十一、闭包：FnOnce、FnMut、Fn

11.1、闭包本质上是什么？

11.2、FnOnce

11.3、FnMut

11.4、Fn

11.5、闭包的使用场景

十二、unsafe

12.1 unsafe trait

12.2、unsafe 函数

12.3 对裸指针解引用

12.4 FFI

12.5 不推荐 unsafe 的场景

其他

1、Rust 特点

2、基本语法和基础数据类型

3、控制流程

4、模式匹配

5、Rust 项目的组织

6、常见问题

7.2、`Box<T>`

8.4、`Vet<T>`、`Box<[T]>`、&T、&mut T