RUST Part1

RUST 概览

Rust 变量和函数

• const , static 变量需要声明类型。const 是右值，保存在可执行文件的数据段。static 可以声明为可变，lazy_static 结合使用。
• 默认变量不可变
• 函数可以作为参数或者返回值。函数没返回值时，默认返回 unit ()。

Rust 数据结构

• struct 定义结构体，struct () 元组结构体，有匿名域。空结构体不占任何空间。
• enum 定义 tagged union
• tuple ()
• 数据行为通过 trait 定义
• 派生宏支持，#[derive(Debug)] ，支持 {:?} 进行打印
• Copy 参数传递时，按字节拷贝
• Clone 支持结构复制

Rust 控制流程

• 顺序执行，函数跳转上下文执行
• 循环执行，loop 死循环，while 条件循环，迭代循环 for。for 循环可用于任何实现了 IntoIterator trait 的数据结构，实际上是 loop 访问迭代器，直到返回 None
• 分支执行，if/else
• 模式匹配分支执行。match expr {} ，if let pat = expr {} 只关心某一种匹配情况
• 错误跳转，终止当前函数执行，向上一层返回错误
• 异步跳转，async 函数执行 await ，程序可能阻塞当前上下文，跳转到另一个异步任务，直到 await 不再阻塞（poll()）

Rust 错误处理

• 借鉴 Haskell 的错误处理，错误封装在 Result<T, E> 类型中。? 用于传播错误。

Rust 项目组织

• mod 组织。在 lib.rs 或者 main.rs 中，用 mod 来声明要加载的模块。子文件下下，新建 mod.rs 类似 python 中的 __init__.py ，写入目录下的子模块文件名称 xx.rs
• 一个项目也被称为 crate，也可以是一个库。
• 单元测试一般放在被测试代码相同的文件中，使用条件编译 #[cfg(test)] 来确保测试代码旨在测试环境中编译。
• 集成测试一般放在 tests 目录下，集成测试只测试公开接口，编译时编译成单独的可执行文件。
• cargo test 运行测试用例
• 所有代码放在一个 crate 中，会导致修改后，频繁编译整个 crate。workspace 是管理多个 crate 的工具。修改只影响所在的 crate。

Rust 可以用过程宏、trait、泛型函数、trait object 等组织代码。

Rust 服务器参考：actix-web 、rocket 、warp、 axum

所有权和生命周期

• 一个值同一时刻只有一个所有者，作用域外释放资源

• 赋值或者传参 Move 语义转移所有权

• Copy trait 保留原所有权，按位拷贝数据，浅拷贝。可变引用、动态大小数据结构、包含动态大小成员的结构没有默认实现 Copy trait

• Borrow 默认是只读的，不影响所有权

• Rust 传参都是传值

• 一个值可以有多个只读引用，但是，只读引用不可以和可变引用共存，动态内存再分配导致地址失效的问题

• 一个值只能有一个可变引用

• 在所有权模型下，堆内存的生命周期，和创建它的栈内存的生命周期保持一致

• 引用的生命周期不能超过值的生命周期

• 运行时动态检查，提供所有权的灵活控制

• Rc 和 Arc ，创建多个所有者的数据结构，clone() 不会复制内存中数据，只会增加引用计数，Rc 和 Arc 是可变的，需要结合 RefCell 和 Mutex 实现数据的可变修改

• Weak 是 Rc 的弱引用版本

• RefCell 绕过 Rust 编译器静态检查，允许在运行时对只读数据进行可变借用。Rc 本身是一个只读的引用计数器

• Arc 跨线程访问，原子引用计数，RefCell 变为 Mutex(v.lock()) 或者 RwLock (v.read()/v.write())

• Box::leak() 创建了不受栈内存控制的堆内存，从而绕过了编译时所有权规则检查

• 外部可变性，let mut , let &mut，编译时检查

• 运行时，修改内部数据，RefCell borrow_mut()，出错会引发 panic

生命周期

• 除了显示地做 Box::leak() / Box::into_raw() / ManualDrop ，一般情况下，堆内存的生命周期会和其栈内存的生命周期绑定在一起

• 静态生命周期的值，其引用也有静态生命周期

• 全局变量，静态变量，字符串字面量等，都有静态生命周期，Box::leak 后也具有静态生命周期，函数指针变量也是静态生命周期（因为它在 text 段）

• 某个作用域中，创建在堆和栈上的值，其生命周期是动态的

• 动态生命周期的表达，约定使用 'a 'b 这样表述

• 生命周期描述的是参数与参数之间，参数与返回值之间的关系，并不改变原有的生命周期

• 所有引用类型的参数都需要生命周期标注

• 编译器可以依照一些准则，自动添加标注：

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

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

内存管理

• struct 在栈空间中，rust 会自动重排结构体
• enum 按照最大类型长度对齐，长度乘以成员数量
• Option 会被有值和无值分别占用两块内存位置
• Result<T, E> 会占用两块位置 T 和 E
• rust 会对 Option 这种引用类型数据进行优化，只占用一块空间，因为 ptr 引用为 0 是不可能的（一定错误的），那么就将 0 表示 None
• String 内部是 Vec，Vec 是 3 个 word 大小的胖指针：pointer，capacity，length

Ref : Rust Language Cheat Sheet

• Copy Move 都只是浅层的按位内存复制，只要不涉及栈上的大数组拷贝或者堆内存的深拷贝，效率还是很高的
• 动态数据结构，需要注意频繁的动态扩容缩容，导致的数据拷贝，造成的效率下降。同时考虑使用 shrink_to_fit 节省内存使用
• Drop trait ，相当于析构函数，递归调用成员的 drop()
• rust 会自动对 socket，file，lock 进行关闭，这是其他语言中很罕见的

多个变量和多种异常或者错误叠加，忘记释放资源的风险敞口会成倍增加，导致死锁或者资源泄露。

类型系统

对类型进行定义，检查，处理的系统。

• 按照定义后，类型是否可以隐式转化，分为强类型和弱类型
• 按照类型检查的时机是编译时检查还是运行时检查，分为静态类型系统和动态类型系统

Rust 是强类型加静态类型系统。只能按照被允许的方法，访问它被授权访问的内存。

Rust 中除了 let / fn / static / const 这些定义性语句外，都是表达式，而一切表达式都有类型，所以可以说在 Rust 中，类型无处不在。

多态的实现：

• 动态类型系统，通过鸭子类型实现
• 静态类型系统，通过参数多态，特设多态，子类型多态实现
  • 参数多态：代码操作的类型是，一个满足一些约束条件的参数，而非具体的类型
  • 特设多态：一种行为可以有多个不同实现的多态，比如函数重载
  • 子类型多态：在运行时，子类型可以被当成父类型使用

Rust 支持：

• 参数多态 -- 通过泛型实现
• 特设多态 -- 通过 trait 来支持
• 子类型多态 -- 通过 trait object 来支持

Rust 支持一个作用域内的局部类型推导。但是，在不能推断出类型的上下文中，需要手动指明类型。比如，全局变量 const / static。

Models of Generics and Metaprogramming: Go, Rust, Swift, D and More - Tristan Hume (thume.ca)

Trait

Rust 中的接口，定义了某个类型使用这个接口的行为。将数据结构的行为单独抽取出来，可以在多个类型中共享，或者作为参数约束，在泛型编程中使用。

带约束的 Trait

use std::str::FromStr;
use regex::Regex;

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

// 约束 T 必须同时实现了 FromStr 和 Default
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() 返回的类型根据上下文能推导出来
        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()
        }
    }
}

带关联类型的 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) {
            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())
        }
    }
}

trait 方法里的参数或者返回值，都可以用关联类型来表述，而在实现有关联类型的 trait 时，只需要额外提供关联类型的具体类型即可。

支持泛型的 Trait

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

// 对 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
impl Add for &Complex {
    // 返回 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);
}

泛型 trait 可以在需要的时候，对同一种类型的同一个 trait，有多个实现。

Trait 的继承

trait B: A，表示 trait B 在定义时可以使用 trait A 中的关联类型和方法。

很多常见的 trait 都会使用 trait 继承来提供更多的能力，比如 tokio 库中的 AsyncWriteExt、futures 库中的 StreamExt。

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

基于子类型多态

Rust 虽然没有父类和子类，但 trait 和实现 trait 的类型之间也是类似的关系。

struct Cat;
struct Dog;

trait Animal {
    fn name(&self) -> &'static str;
}

impl Animal for Cat {
    fn name(&self) -> &'static str {
        "Cat"
    }
}

impl Animal for Dog {
    fn name(&self) -> &'static str {
        "Dog"
    }
}

// 等价于 fn name<T: Animal>(animal: T) -> &'static str;
fn name(animal: impl Animal) -> &'static str {
    animal.name()
}

fn main() {
    let cat = Cat;
    println!("cat: {}", name(cat));
}

这种泛型函数会根据具体使用的类型被单态化，编译成多个实例，是静态分派。

但是有的时候，类型可能很难在编译时决定。使用 Trait Object 可以应对这种情况。

// Vec<> 容器里的类型需要是一致的，但此处无法给定一个一致的类型。
pub fn format(input: &mut String, formatters: Vec<???>) {
    for formatter in formatters {
        formatter.format(input);
    }
}

// 动态分派（dynamic dispatching）
pub fn format(input: &mut String, formatters: Vec<&dyn Formatter>) {
    for formatter in formatters {
        formatter.format(input);
    }
}

fn main() {
    let html: &dyn Formatter = &HtmlFormatter;
    let rust: &dyn Formatter = &RustFormatter;
    let formatters = vec![html, rust];
	...
}

HtmlFormatter 的引用赋值给 Formatter 后，会生成一个 Trait Object。

Trait Object 的底层逻辑就是胖指针。其中，一个指针指向数据本身，另一个则指向虚函数表（vtable）。

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

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

使用 trait object 的时候，要注意对象安全（object safety）。只有满足对象安全的 trait 才能使用 trait object。如果 trait 所有的方法，返回值是 Self 或者携带泛型参数，那么这个 trait 就不能产生 trait object。如果一个 trait 只有部分方法返回 Self 或者使用了泛型参数，那么这部分方法在 trait object 中不能调用。

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

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

vtable 测试

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 注意事项

1. 在定义和使用 trait 时，需要遵循孤儿规则（Orphan Rule）。trait 和实现 trait 的数据类型，至少有一个是在当前 crate 中定义的，也就是说，你不能为第三方的类型实现第三方的 trait。
2. Rust 对含有 async fn 的 trait ，还没有一个很好的被标准库接受的实现(2019)

常见 Trait

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

内存相关：Clone

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

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

在 clone 过程中会分配内存，那么用 a.clone_from(&b) 可以避免内存分配，提高效率。

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

Clone 是深度拷贝，栈内存和堆内存一起拷贝。

clone 方法的接口是 &self，这在绝大多数场合下都是适用的。在 clone 一个数据时只需要有已有数据的只读引用。但对 Rc 这样在 clone() 时维护引用计数的数据结构，clone() 过程中会改变自己，所以要用 Cell 这样提供内部可变性的结构来进行改变。

内存相关：Copy

Copy trait 没有任何额外的方法，它只是一个标记 trait（marker trait）.

pub trait Copy: Clone {}

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

如果类型实现了 Copy，那么在赋值、函数调用的时候，值会被拷贝，否则所有权会被移动 Move。

可变引用 &mut T 没有实现 Copy。因为，不符合同一个作用域下只能有一个可变引用 的所有权规则。

内存相关：Drop

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

大部分场景无需为数据结构提供 Drop trait，系统默认会依次对数据结构的每个域做 drop。

除了以下两种情况：

1. 希望在数据结束生命周期的时候做一些事情，比如记日志。
2. 需要对资源回收的场景。比如说锁资源的释放，在 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恰恰是为了释放额外的资源而生的。

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 的底线是内存安全，所以两害相权取其轻。

无法保证不发生人为的内存泄漏，比如程序在运行时，对哈希表只添加不删除，就会造成内存泄漏。

标记相关：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 来摆脱这个约束。

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

这样 B 就可以是 [T] 或者 str 类型，大小都是不固定的。要注意 Borrowed(&'a B) 大小是固定的，因为它内部是对 B 的一个引用，而引用的大小是固定的。

标记相关：Send/Sync

说完了 Sized，再来看 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。

如果一个类型T: Send，那么 T 在某个线程中的独占访问是线程安全的；如果一个类型 T: Sync，那么 T 在线程间的只读共享是安全的。

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

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

如果尝试跨线程使用 Rc / RefCell，会发生什么？

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

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

如果在线程间传递 Rc，是无法编译通过的，因为 Rc 的实现不支持 Send 和 Sync。

Arc 内部的数据是共享的，需要支持 Sync 的数据结构，但是RefCell 不是 Sync。

标记相关：Unpin

类型转换：From

// 第一种方法，为每一种转换提供一个方法
// 把字符串 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），“软件中的对象（类、模块、函数等等）对扩展是开放的，但是对修改是封闭的”。

Rust 提供了两套不同的 trait：

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

先看 From 和 Into。这两个 trait 的定义如下：

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，然后这两种方式都能做数据转换，比如：

let s = String::from("Hello world!");
let s: String = "Hello world!".into();

这两种方式是等价的，怎么选呢？From 可以根据上下文做类型推导，使用场景更多；而且因为实现了 From 会自动实现 Into，反之不会。所以需要的时候，不要去实现 Into，只要实现 From 就好了。

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

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

有了 From 和 Into，很多函数的接口就可以变得灵活，比如函数如果接受一个 IpAddr 为参数，可以使用 Into 让更多的类型可以被这个函数使用，看下面的代码：

use std::net::{IpAddr, Ipv4Addr, Ipv6Addr};

fn print(v: impl Into<IpAddr>) {
    println!("{:?}", v.into());
}

fn main() {
    let v4: Ipv4Addr = "2.2.2.2".parse().unwrap();
    let v6: Ipv6Addr = "::1".parse().unwrap();
    
    // IPAddr 实现了 From<[u8; 4]，转换 IPv4 地址
    print([1, 1, 1, 1]);
    // IPAddr 实现了 From<[u16; 8]，转换 IPv6 地址
    print([0xfe80, 0, 0, 0, 0xaede, 0x48ff, 0xfe00, 0x1122]);
    // IPAddr 实现了 From<Ipv4Addr>
    print(v4);
    // IPAddr 实现了 From<Ipv6Addr>
    print(v6);
}

所以，合理地使用 From / Into，可以让代码变得简洁，符合 Rust 可读性强的风格，更符合开闭原则。

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

类型转换：AsRef / AsMut

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 除了使用可变引用生成可变引用外，其它都和 AsRef 一样。

看标准库中打开文件的接口 std::fs::File::open：

pub fn open<P: AsRef<Path>>(path: P) -> Result<File>

它的参数 path 是符合 AsRef 的类型，所以，你可以为这个参数传入 String、&str、PathBuf、Path 等类型。而且，当你使用 path.as_ref() 时，会得到一个 &Path。

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

如果你的代码出现 v.as_ref().clone() 这样的语句，也就是说你要对 v 进行引用转换，然后又得到了拥有所有权的值，那么你应该实现 From，然后做 v.into()。

操作符相关：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 和 DerefMut 是自动调用的，b 会被展开为 (b.deref())

在 Rust 里，绝大多数智能指针都实现了 Deref，也可以为自己的数据结构实现 Deref。

对于普通的引用，解引用很直观，因为它只有一个指向值的地址，从这个地址可以获取到所需要的值，比如下面的例子：

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

但对智能指针来说，拿什么域来解引用就不那么直观了，来看之前学过的 Rc 是怎么实现 Deref 的：

impl<T: ?Sized> Deref for Rc<T> {
    type Target = T;

    fn deref(&self) -> &T {
        &self.inner().value
    }
}

可以看到，它最终指向了堆上的 RcBox 内部的 value 的地址，然后如果对其解引用的话，得到了 value 对应的值。

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

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

其它: Debug

先看 Debug / Display，它们的定义如下：

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

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

可以看到，Debug 和 Display 两个 trait 的签名一样，都接受一个 &self 和一个 &mut Formatter。

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

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

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

Default trait 用于为类型提供缺省值。它也可以通过 derive 宏 #[derive(Default)] 来生成实现，前提是类型中的每个字段都实现了 Default 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);
}

在软件开发中，延迟绑定会带来极大的灵活性。

从数据的角度看，数据结构是具体数据的延迟绑定，泛型结构是具体数据结构的延迟绑定；从代码的角度看，函数是一组实现某个功能的表达式的延迟绑定，泛型函数是函数的延迟绑定。那么 trait 是什么的延迟绑定呢？

trait 是行为的延迟绑定。可以在不知道具体要处理什么数据结构的前提下，先通过 trait 把系统的很多行为约定好。这也是为什么开头解释标准trait时，频繁用到了“约定……行为”。

智能指针

指针是一个持有内存地址的值，可以通过解引用来访问它指向的内存地址，理论上可以解引用到任意数据类型；引用是一个特殊的指针，它的解引用访问是受限的，只能解引用到它引用数据的类型。

智能指针是一个表现行为很像指针的数据结构，但除了指向数据的指针外，它还有元数据以提供额外的处理能力。

在 Rust 中，凡是需要做资源回收的数据结构，且实现了 Deref/DerefMut/Drop，都是智能指针。

用于在堆上分配内存的 Box 和 Vec、用于引用计数的 Rc 和 Arc 。很多其他数据结构，如 PathBuf、Cow<'a, B>、MutexGuard、RwLockReadGuard 和 RwLockWriteGuard 等也是智能指针。

String 是用结构体定义的：

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

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

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

Box

Rust 中最基本的在堆上分配内存的方式。

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:
    // https://github.com/rust-lang/rfcs/blob/master/text/0769-sound-generic-drop.md#phantom-data
    _marker: PhantomData<T>,
}

在堆上分配内存，需要使用内存分配器（Allocator）。设计内存分配器的目的除了保证正确性之外，就是为了有效地利用剩余内存，并控制内存在分配和释放过程中产生的碎片的数量。

堆上分配内存的 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] 标记宏，定义你自己的全局分配器。下面的代码展示了如何在 Rust 下使用 jemalloc：

use jemallocator::Jemalloc;

#[global_allocator]
static GLOBAL: Jemalloc = Jemalloc;

fn main() {}

这样设置之后，使用 Box::new() 分配的内存就是 jemalloc 分配出来的了。另外，撰写自己的全局分配器，可以实现 GlobalAlloc trait，它和 Allocator trait 的区别，主要在于是否允许分配长度为零的内存。

常见的通用内存分配器有 glibc 的 pthread malloc、Google 开发的 tcmalloc、FreeBSD 上默认使用的 jemalloc 等。除了通用内存分配器，对于特定类型内存的分配，还可以用 slab，slab 相当于一个预分配好的对象池，可以扩展和收缩。

示例

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
    // 之后还有很多其它内存被释放
}

注意这里不能使用 println!() 。因为 stdout 会打印到一个由 Mutex 互斥锁保护的共享全局 buffer 中，这个过程中会涉及内存的分配，再运行 println!()，最终造成程序崩溃。而 eprintln! 直接打印到 stderr，不会 buffer。

Box::new() 是一个函数，所以传入它的数据会出现在栈上，再移动到堆上。所以，如果的 Matrix 结构不是 505 个字节，是一个非常大的结构，就有可能出现 stack overflow 问题。

如果是 debug build，它不会做任何 inline 的优化，而 Box::new() 注明了要 inline，在 release 模式下，这个函数调用会被优化掉：

#[cfg(not(no_global_oom_handling))]
#[inline(always)]
#[doc(alias = "alloc")]
#[doc(alias = "malloc")]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn new(x: T) -> Self {
    box x
}

如果不 inline，整个 16M 的大数组会通过栈内存传递给 Box::new，导致栈溢出。

Box 的内存释放实现：

#[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 语言的一种策略：在具体实现还没有稳定下来之前，先把接口稳定，实现随着之后的迭代慢慢稳定。

Cow<'a, B>

Cow 是 Rust 下用于提供写时克隆（Clone-on-Write）的一个智能指针，有一个只读借用，但如果调用者需要所有权或者需要修改内容，那么它会 clone 借用的数据。

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

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

这里又引入了两个 trait，首先是 ToOwned，在 ToOwned trait 定义的时候，又引入了 Borrow trait，它们都是 std::borrow 下的 trait：

pub trait ToOwned {
    type Owned: Borrow<Self>;
    #[must_use = "cloning is often expensive and is not expected to have side effects"]
    fn to_owned(&self) -> Self::Owned;

    fn clone_into(&self, target: &mut Self::Owned) { ... }
}

pub trait Borrow<Borrowed> where Borrowed: ?Sized {
    fn borrow(&self) -> &Borrowed;
}

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() 方法，获得引用。

根据 enum 的不同状态来进行统一分发的方法是第三种分发手段，对应的有使用泛型参数做静态分发和使用 trait object 做动态分发。

相对于栈内存的分配释放来说，堆内存的分配和释放效率要低很多，其内部还涉及系统调用和锁，减少不必要的堆内存分配是提升系统效率的关键手段。而 Rust 的 Cow<'a, B>，在帮助你达成这个效果的同时，使用体验还非常简单舒服。

使用示例

在解析 URL 的时候，需要将 querystring 中的参数，提取成 KV pair 来进一步使用。绝大多数语言中，提取出来的 KV 都是新的字符串，在每秒钟处理几十 k 甚至上百 k 请求的系统中，堆内存的分配会很频繁。

但在 Rust 中，可以用 Cow 类型轻松高效处理它，在读取 URL 的过程中：

• 每解析出一个 key 或者 value，可以用一个 &str 指向 URL 中相应的位置，然后用 Cow 封装它；
• 而当解析出来的内容不能直接使用，需要 decode 时，比如 “hello%20world”，可以生成一个解析后的 String，同样用 Cow 封装它。

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 标准库和第三方库中非常常见。比如 Rust 下著名的 serde 库，可以非常高效地对 Rust 数据结构，进行序列化/反序列化操作，它对 Cow 就有很好的支持。

我们可以通过如下代码将一个 JSON 数据反序列化成 User 类型，同时让 User 中的 name 使用 Cow 来引用 JSON 文本中的内容：

use std::borrow::Cow;
use serde::Deserialize;

#[derive(Debug, Deserialize)]
struct User<'input> {
    #[serde(borrow)]
    name: Cow<'input, str>,
    age: u8,
}

fn main() {
    let input = r#"{ "name": "Tyr", "age": 18 }"#;
    let user: User = serde_json::from_str(input).unwrap();

    match user.name {
        Cow::Borrowed(x) => println!("borrowed {}", x),
        Cow::Owned(x) => println!("owned {}", x),
    }
}

MutexGuard

MutexGuard 不但通过 Deref 提供良好的用户体验，还通过 Drop trait 来确保，使用到的内存以外的资源在退出时进行释放。

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

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

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

// 这里用 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();
        }
    }
}

使用示例

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

MutexGuard 不允许 Send，只允许 Sync，也就是说，你可以把 MutexGuard 的引用传给另一个线程使用，但你无法把 MutexGuard 整个移动到另一个线程：

impl<T: ?Sized> !Send for MutexGuard<'_, T> {}
unsafe impl<T: ?Sized + Sync> Sync for MutexGuard<'_, T> {}

类似 MutexGuard 的智能指针有很多用途。比如要创建一个连接池，可以在 Drop trait 中，回收 checkout 出来的连接，将其再放回连接池。

数据库连接池实现：r2d2

优化 String

Rust 下 String 在栈上占了 24 个字节，然后在堆上存放字符串实际的内容，对于一些比较短的字符串，这很浪费内存。

用一个 enum 来处理：当字符串小于 N 字节时，我们直接用栈上的数组，否则，使用 String。但是这个 N 不宜太大，否则当使用 String 时，会比目前的版本浪费内存。

当使用 enum 时，额外的 tag + 为了对齐而使用的 padding 会占用一些内存。因为 String 结构是 8 字节对齐的，我们的 enum 最小 8 + 24 = 32 个字节。

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

通过实现 Deref trait 让 MyString 可以被解引用成 &str。除此之外，还可以实现 Debug/Display 和 From trait，让 MyString 使用起来更方便。

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("这"));
}

这个简单实现的 MyString，不管它内部的数据是纯栈上的 MiniString 版本，还是包含堆上内存的 String 版本，使用的体验和 &str 都一致，仅仅牺牲了一点点效率和内存，就可以让小容量的字符串，可以高效地存储在栈上并且自如地使用。

Rust 有个叫 smartstring 的第三方库就实现并优化了这个功能。

集合容器

切片

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

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

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

通过解引用，数据结构可以获得切片的所有能力，包括：binary_search、chunks、concat、contains、start_with、end_with、group_by、iter、join、sort、split、swap 等。

当构建自己的数据结构时，如果它内部也有连续排列的等长的数据结构，可以考虑 AsRef 或者 Deref 到切片。

切片的对象可以在堆上，也可以在栈上，并且其内容可以相互比较。

切片是集合数据的视图，而迭代器定义了对集合数据的各种各样的访问操作。

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

• Item 定义了每次我们从迭代器中取出的数据类型；
• next() 是从迭代器里取下一个值的方法。

#[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 操作。

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

需要注意的是 Rust 下的迭代器是个懒接口（lazy interface），也就是说这段代码直到运行到 collect 时才真正开始执行，之前的部分不过是在不断地生成新的结构，来累积处理逻辑而已。

Rust 大量使用了 inline 等优化技巧，函数式编程优化后，性能和 C 语言的 for 循环差别不大。

itertools，是和 Python 下 itertools 同名且功能类似的工具，提供了大量额外的 adapter。

use itertools::Itertools;

fn main() {
    let err_str = "bad happened";
    let input = vec![Ok(21), Err(err_str), Ok(7)];
    let it = input
        .into_iter()
        .filter_map_ok(|i| if i > 10 { Some(i * 2) } else { None });
    // 结果应该是：vec![Ok(42), Err(err_str)]
    println!("{:?}", it.collect::<Vec<_>>());
}

在实际开发中，我们可能从一组 Future 中汇聚出一组结果，里面有成功执行的结果，也有失败的错误信息。用 itertools 里的 filter_map_ok()，进一步做 filter/map。

String 是一个特殊的 Vec，所以在 String 上做切片，也是一个特殊的结构 &str。String 在解引用时，会转换成 &str。

Box<[T]>

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

Box<[T]>和切片的引用&[T] 也很类似：它们都是在栈上有一个包含长度的胖指针，指向存储数据的内存位置。区别是：Box<[T]> 只会指向堆，&[T] 指向的位置可以是栈也可以是堆；此外，Box<[T]> 对数据具有所有权，而 &[T] 只是一个借用。

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

// 从 Vec<T> 转换成 Box<[T]>，此时会丢弃多余的 capacity
let b1 = v1.into_boxed_slice();
// Box<[T]> 也可以通过 into_vec() 转换回 Vec<T>

// Box<[T]> 可以更改其内部数据，但无法 push
b2[0] = 2;
// b2.push(6);

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

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

into_boxed_slice 和 into_vec 两个转换都是很轻量的转换，只是变换一下结构，不涉及数据的拷贝。区别是，当 Vec 转换成 Box<[T]> 时，没有使用到的容量就会被丢弃，所以整体占用的内存可能会降低。

Box<[T]> 有一个很好的特性是，不像 Box<[T;n]> 那样在编译时就要确定大小，它可以在运行期生成，以后大小不会再改变。

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

哈希表

哈希冲突解决：链地址法（chaining）和开放寻址法（open addressing）。Rust 使用 开放寻址法 + 二次探查（开放寻址法把整个哈希表看做一个大数组，不引入额外的内存，在冲突发生时，不断探寻哈希位置加减 n 的二次方，找到空闲的位置插入）。

链地址法缺点是哈希表和冲突链使用了不同的内存，对缓存不友好。

标准库的 源代码：

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 的一个改进版实现：

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 区
    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,
	
    // 和 RawTable 的 marker 一样，只是一个用来占位的类型
    alloc: A,
}

HashMap 内存布局

ctrl 是一个指向哈希表堆地址末端 ctrl 区的地址。每个 bucket 大小是 key（char） + value（i32） 的大小，也就是 8 个字节。以此可以计算出哈希表的起始地址。

可用的调试工具：rust-gdb，rust-lldb

内存布局分为栈和堆两部分：

栈：RandomState(2*u64) | mask | ctrl ptr | growth_left | items

堆：(ctrl ptr) 指向 ctrl 表 | (key, value) | (key, value)

ctrl 表用于快速查找，由 16 字节大小的 control byte 组成，每个 byte 对应一个 bucket，每个 bucket 对应一个 (key, value) 对。

16 字节大小的 control byte 可以用 SIMD 指令快速读取到缓存中。

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

当要在哈希表中删除一个值时，先要找到要被删除的 key 所在的位置。在找到具体位置后，并不需要实际清除内存，只需要将它的 ctrl byte 设回 0xff。

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

所以，如果在 HashMap 中，添加大量内容，又删除大量内容，这时，最好使用 shrink_to_fit / shrink_to 释放不需要的内存占用。

如果需要自定义 Hash Key，只需要定义三个 Trait：Hash、PartialEq、Eq。

HashSet / BTreeMap / BTreeSet

HashSet 用于简单确认元素是否在集合中。

BTreeMap 和 BTreeSet 是内部使用 B-tree 来组织哈希表的数据结构，用来存放有序集合。 BTreeMap 的 key，需要实现 PartialOrd 和 Ord Trait。

SipHash

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

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

use ahash::{AHasher, RandomState};
use std::collections::HashMap;

let mut map: HashMap<char, i32, RandomState> = HashMap::default();
map.insert('a', 1);