Rust从入门到精通

我这个人不喜欢废话，本文基本都是干货（其实一开始是写给自己看的Cheat Sheet性质的笔记没想到越写越长），没必要展开的地方就不展开讲了，读者可自行参考The Rust Book和Rust Reference。基本上Part I就是搬运的The Rust Book，补上了若干细节，Part II是一些相对更「高级」的特性，可对照Rust Reference食用，Part III是全文的精髓，里面对Rust核心的ownership、borrow和lifetime机制的讨论，目前中文资料里还没有如此深入的（好像英文也没有，大家都是复读机，只会复读最基本的知识）。

Part I. Common Rust

Basics

首先看一下基本语法，在传统的C-like基础上引入了大量ML-Style语法：

• 注释：// this is a line comment, /* this is a block comment */
  • /// inner line doc, /** inner block doc */: 这种注释用于为紧跟着的对象提供文档
  • //! outer line doc, /*! inner block doc */: 这种注释用于为父对象提供文档
  • 文档注释支持Markdown语法
• ML风格变量声明
  • let lhs = rhs;: Statement以分号结尾
  • let x: u32;: 默认使用类型推导
  • let mut y = 42;: 默认immutable，加mut表示mutable
  • let x = 3; let x = x * 2;: 支持Variable Shadowing
  • let声明不是Expression，不能作为RHS
• 单独的const声明，不允许声明为mutable
  • const MAX: u32 = 100;: 必须提供类型annotation
  • const允许在Global Scope声明，而let不允许
  • const只允许赋值Constant Expression，编译时无法确定的值不能赋值
• 基本类型
  • 整数类型：i8,u8,i16,u16,i32,u32,i64,u64,i128,u128，此外还有isize,usize根据平台位数决定其长度
    • 整数默认推导类型为i32
    • Debug模式下Integer Overflow会产生panic，但Release模式下不会
  • 浮点类型：f32,f64，默认推导类型为f64
  • 布尔类型：bool，取值为true,false
  • 字符类型：char，4字节宽，代表一个Unicode Scalar Value（即除用于UTF-16的Surrogate以外的所有Unicode Code Point）
  • Tuple类型：let tup: (A, B, C) = (a, b, c);，即典型的Product Type
    • 可以通过下标直接访问其成员：tup.0, tup.1, tup.2
    • 可以进行destructuring：let (x, y, _) = tup;
  • Array类型：let a: [i32; 5] = [1, 2, 3, 4, 5]
    • Array类型是定长的，其类型声明需指定长度
    • Array总是分配在栈上
    • let a = [3; 5]，相当于let a = [3, 3, 3, 3, 3]
    • Rust对数组越界有Runtime Check，一旦越界就会panic
  • type A = B提供了Type Aliasing功能
• 操作符
  • +,-,*,/,%,&,|,^,<<,>>: 二元算数操作符，可重载
  • =,+=,-=,*=,/=,%=,&=,|=,^=,<<=,>>=: 赋值操作符，可重载（除=本身外）
    • 赋值操作的返回值是()，即禁止类似x = y = 3;的写法
  • !expr, -expr: 一元逻辑操作符和一元算数操作符，可重载
  • &&, ||: 二元逻辑操作符，不可重载
  • ==,!=,<,<=,>,>=: 二元比较操作符，可重载
  • .., expr.., ..expr, expr..expr: 表示范围，不包括RHS
  • ..=expr, expr..=expr: 表示范围，包括RHS
  • []: 数组下标操作符，可重载
• 函数
  • fn func(x: i32, y: i32) -> i32 {}
  • 参数必须提供类型声明，返回值类型不写则表示()即Unit Type
  • 函数以Statement结尾则返回()，以Expression结尾则返回该expr的值，或者也可以用return expr;返回
  • 函数不允许重载，同名函数即使参数、返回值不同也会冲突
  • const fn func(): 通过const关键字可以指定const function，可以在编译时执行（当然同时也能在运行时被调用），类似于C++的constexpr
• 控制流
  • if expr {} else {}
    • 不像C/C++/Java/C#，expr不需要加括号
    • expr必须是bool类型，Rust不会进行隐式类型转换
    • if语句属于Expression而不是Statement，因此可以作为赋值的RHS
  • 循环语句
    • loop {}: 相当于传统的while (true) {}
    • while expr {}
    • for pattern in expr {}: 要求expr实现了std::iter::IntoInterator接口
    • 在循环语句前可以加Label，其格式为'label，然后可以通过break 'label;或continue 'label;跳出嵌套循环
    • 循环语句也都属于Expression
      • while, for返回一个()，故其类型为Unit Type
      • 仅在loop语句中，允许break expr;，此时其类型为expr的类型
      • loop语句中break;，则返回一个()
      • 不含break的loop语句类型为Never Type（!），即Bottom Type

Move Semantics and References

Rust Book第四章介绍了如下内容（补充了书中未提到的必要细节）。

首先是整体的语义：

• 存在且默认使用move语义
  • Assignment（=）、函数传参以及函数返回值，都采用move语义
  • 只有对实现了CopyTrait（类似于接口，下面会详细介绍）的类型，才会是copy语义
    • 此处的copy语义是指浅拷贝
    • 只有可以完全分配在栈上的类型才可以使用copy语义
  • 实现了CloneTrait（Copy的父Trait）的类型，可以通过.clone()方法进行深拷贝
• 一个value最多只有一个变量作为其owner，但一个变量不一定有value（可能被move走了，此时不能再使用该变量）
  • value可以是临时产生的，此时没有owner，否则应当有一个owner
• 存在RAII语义，变量离开作用域（Scope）时，被其own的value可能需要被销毁
  • 若存在，则Destructor即drop()方法会被调用
  • drop()属于Drop Trait，类型若实现了Drop则不允许实现Copy

然后是Reference的语义：

• &expr表示取引用，*expr表示解引用，&T表示引用类型
  • 取引用操作的正式名称为borrow，表示借走了expr的ownership
  • *操作符可重载
• 引用不是被引用的对象的owner，离开作用域时不会造成被引用者析构
• 引用默认是immutable的，&mut expr表示取mutable引用，&mut T表示mutable引用类型
  • 即&T相当于C的const T*，&mut T相当于C的T*
  • 不能对immutable变量取mutable引用
  • &操作符正式名称为shared borrow，&mut操作符正式名称为mutable borrow
• 对同一个value的immutable引用和mutable引用作用域不能重叠，mutable引用和mutable引用作用域也不能重叠
  • 即只允许immutable引用发生Aliasing

还有一种裸指针*const T, *mut T，裸指针只能在unsafe块中才能解引用，后面会专门讲解Rust的unsafe特性

最后是Slice的语义：

• 基本的Slice Type为[T]，它是一种Dynamically Sized Type，即只有在运行时才能知道其大小
• 通常我们使用的类型是&[T]或&mut[T]，通过&expr[expr..expr]或&mut expr[expr..expr]获得，访问时使用下标[expr]访问即可
  • Slice的引用实现为Fat Pointer，除包含一个指针外还包含一个size，并会在运行时进行边界检查
• 事实上，Slice只允许通过类似指针的类型访问，例如引用、裸指针（仅限unsafe块）和智能指针

最后补充一下str类型（也是基本类型）：

• 同Slice Type类似，也是Dynamically Sized Type，本质上可以视为一种特殊的String Slice，用法与Slice相同
• String Literal的类型为&str
• println!, eprintln!, format!: 用于输出到stdout、输出到stderr以及格式化字符串，采用"{}"python式的语法

Data Structures

首先来看struct，正如名字所暗示的，它不支持继承。Rust虽然支持Dynamic Dispatching，但故意没有实现继承，这是为了避免Fragile Base-Class Problem。

最典型的定义Struct的方式如下：

struct A {
    a: String,
    b: i32,
    c: u64,
}

• 结尾不需要分号
• 最后一项可以加逗号（可选）

创建Struct对象的方式如下：

A {
    a: str,
    b: x,
    c: y,
}

当变量与Field同名时，可简写如下：

A {
    a,
    b,
    c: y,
}

或者还可以基于一个Instance创建另一个Instance，称为struct update syntax：

let a_2 = A {
    a: str,
    ..a_1
}

• struct update syntax下，最后一项必须是..expr的格式，不能加逗号
• 否则可以加逗号（可选）

此外还有一种tuple struct，可定义如下：

struct Point(i32, i32, i32,);

• 结尾要加分号
• 最后一项可以加逗号（可选）
• 用法本质上和普通的Tuple一样，除了创建需要用Point(a, b, c)的形式进行
• 其主要用途是为Tuple标记上不同的Nominal Type，防止互相混用
  • 为单独一个Type创建一个tuple struct称为Newtype Pattern，意思是类似于Haskell的newtype操作

如果要定义的Struct没有任何成员，则称为unit-like struct，此时可以这样定义：

struct U; // now U is also a constant

• 等价于struct U {}
• 但会同时定义一个常量const U: U = U {};

在Struct上可以定义Method以及Function：

impl A {
    // A method, invoked by a.meth()
    fn meth(&self) -> bool {
        true
    }

    // A function, invoked by A::func()
    fn func() -> bool {
        false
    }
}

• 可以有多个impl Block
• 不加self参数则为Struct Function，也就是通常说的Static Method
• 加self参数则为Struct Method
  • &self相当于C++的void f() const成员函数
  • &mut self相当于各语言中普通的成员函数
  • 实际上可以使用self作为参数，这是其他语言没有的功能，一般用于调用method后不希望对象再被使用的情形
• impl Block内还可以定义Constant

---

再来看enum，这是一个Sum Type或者说Tagged Union：

enum Animal {
    Cat { name: String, weight: f64 },
    Dog(String, f64),
    Horse = 100,
    Sheep,
}

• 最后一项可以加逗号（可选）
• 每一项（称为Variant）的声明实际上和Struct声明格式相同（除了没有struct关键字）
• 使用时通过Animal::Cat { name: "Kitty", weight: 1.5 }的形式创建对象
  • 除了不支持struct update syntax，其余与Struct初始化语法相同
• 可以通过Variant = num的形式为Variant指定编号（称为Discrimination），此后的项的编号从该编号开始依序增加
  • 此处的编号即底层实现时用于区分Variant的Tag
  • 目前只有当所有Variant都是unit-like时（即退化为C/C++/Java/C#的enum时），才可以使用该特性
• 没有Variant的Enum（enum E {}）本质上是空集，不能实例化
• Enum同样可以通过impl块定义Method、Function、Constant和Type Alias

一个非常常用的Enum是Option：

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

Module System and Visibility

从项目的组织上来看，顶层是Package，一个Package由若干Crate构成：

• Package就是一个通过cargo new创建的包含Cargo.toml的项目
• 一个Package最多只能有一个Library Crate，但可以有任意多个Binary Crate
• cargo new会默认创建src/main.rs，这会被理解为一个与Package同名的Binary Crate的Crate Root
  • 进一步地，src/bin/目录下的每个文件都会被当做一个Binary Crate
• 若存在src/lib.rs，则会被理解为一个与Package同名的Library Crate的Crate Root

每个Crate就是一个完整的程序（Binary Crate）或库（Library Crate），它由一棵Module树构成，这棵树的根就位于Crate Root源文件，并且是隐式声明的，其名称为crate。

我们可以在Crate Root中嵌套地定义Module，注意Module和类型共享同一个namespace：

mod a {
    mod a1 {
        fn f1() {}
        fn f2() {}
    }

    mod a2 {
        fn g1() {}
        fn g2() {}
    }

    struct B;

    // Wrong! This wouldn't compile.
    mod B {
        fn h() {}
    }
}

我们可以通过Path访问Module及其中定义的Item（即函数、Struct、Enum、Trait、Constant等的定义），通过Path访问一个Item要求其Visibility是public的，关于Visibility的规则如下：

• Rust中所有Item默认都是private的
• 你可以通过pub将Item（Module也视为Item的一种）标记为public的，若你能访问其Parent Module，则你也能访问该Item
  • 但Struct的Field、Method等需要单独标记为pub，否则即使Struct本身标记为pub也无法被外界访问
  • Enum的所有Variant，只要Enum本身是pub，就自动成为public的
• 对于private的Item，只有它所在的Module，以及该Module的Descendant可以访问
  • 一个典型的例子是，一个Crate的顶层Module可以被该Crate中的所有代码使用，但它若是private的则不能被其他Crate使用
• 存在几个pub的变种：
  • pub(in path)，表示对path可见，path必须是当前Module或其祖先
  • pub(crate)，表示对整个Crate可见
  • pub(super)，表示对Parent Module可见
  • pub(self)，表示对当前Module可见

在pub(in path)中的path，以及use语句（详下）中使用的Path，只能是Simple Path，其格式如下：

• 形如a::a1::f1
• 以::开头表示Global Path，可以引用External Crate，例如::rand::Rng
• 以self开头表示从当前Module开始
• 以super开头表示从当前Module的Parent开始，super出现在中间表示取Parent Module
• 以crate开头表示从当前Crate开始，注意::crate是无效路径
• 默认表示从当前Local Context开始

Edition Difference: 在2018 Edition中，::路径下只有External Crate，而在2015 Edition中::路径下还包含当前Crate的顶层Item，以及std等默认引入的Item。

若声明Module时不指定定义，如mod a;，则会从同名文件a.rs查找该Module，源文件的路径和Module的Path吻合，例如crate::a::a1应当由src/a.rs中的mod a1;声明，其对应源文件位于src/a/a1.rs。这样，我们只需为编译器提供Crate Root源文件，编译器即可自动查找到项目的所有文件并编译出库或可执行文件。

Edition Difference: 2015 Edition使用src/a/mod.rs来对应于crate::a，而不是src/a.rs，目前仍支持这种用法但不鼓励，因为这样会在项目中产生很多mod.rs。

此外，我们可以通过path Attribute改变上述默认映射。对于顶层Module，若Attribute为#[path = "foo.rs"]，则Module对应的文件将是foo.rs，位于Module声明所在的源文件的同级目录下。对于Nested Module，则源文件要位于Parent对应的路径下。

我们可以通过use语句引入别名：

• use crate::a::a1;后，可以直接使用Module a1
• use crate::a::a1::f1后，可以直接使用函数f1
• use crate::a::a1::self也可以用于引入Module a1
• use crate::a::a1::{self, f2}支持用括号一次性引入多个Item，且可嵌套使用括号
• use crate::a::a1::*引入a1中的所有Item
• use crate::a::a1::{f1 as g1, f2 as g2}支持对引入的Item起别名（Alias)
• use crate::a::a1::f1 as _可以引入Item的定义，但不绑定到任何Name，这对于引入Trait有时是有用的
• pub use crate::a::a1::f1，use语句引入的Item默认是private的，通过添加pub可以让外部也能访问引入的Item
• use语句总是要以crate, self, super或::开头，除非是访问external crate

Edition Difference: 在2015 Edition中，必须手动通过extern crate xxx;才能引入External Crate。这个操作实际上是将External Crate加入了Crate Root，因此通过::ext_crate或crate::ext_crate都可以访问External Crate。进一步地，只有在Crate Root的Context下才能通过ext_crate::引用External Crate，在内部的Module中就无法直接通过ext_crate::访问External Crate。

在2018 Edition中，Cargo.toml引入的External Crate会被特殊处理，不需要手动extern crate（因此也就不会加入到Crate Root，通过crate::ext_crate无法访问它们），且无论在什么Context都可以通过ext_crate::访问它们，这样比2015 Edition清晰且方便。

Note: External crate的名称中可以出现hyphen-，但在Rust代码中使用时，必须把-替换成_。

Parametric Polymorphism

Rust中有Trait的概念，类似于其他语言的Interface：

trait Trait {
    fn f(&self) -> i32;
    fn g(x: i32) -> i32;
}

struct A { x: i32 }

impl Trait for A {
    fn f(&self) -> i32 {
        self.x
    }
}

• Trait可以定义一系列接口，可以用impl Trait for T来实现接口，Trait和T必须至少有一个定义在当前Crate
  • 可以为external crate的类型实现本地定义的Trait
  • 可以为本地定义的类型实现external crate的Trait
  • 但不能为external crate的类型实现external crate的Trait，这是为了防止使用上的混乱
• Trait可以提供Default Implementation
  • impl Trait for A {}将为A引入Default Implementation
  • Default Implementation可以引用同一个Trait中的抽象方法，在impl块中只需实现这些抽象方法即可
• 实际上，Trait中可以声明Method、Function、Constant和Type Alias，其中只有Type Alias不能提供Default Implementation
  • type T;（Type Alias Declaration）的作用是提供一个Placeholder，以便在Method中使用T。在具体的Trait Implementation中，可以为T提供Concrete Type

Edition Difference: 在2015 Edition中，允许Anonymous Parameter，例如在Trait中声明fn f(i32) -> i32，但在2018 Edition中取消了该功能，现在强制要求写出参数名

---

我们可以在不同的场合使用Type Parameter，Rust将其称为Generic：

• fn f<T>(a: &[T]) -> T {}: 函数可以是Generic的
  • Generic函数不允许Specialization
• struct Point<T> { x: T, y: T }: Struct可以是Generic的
• enum Option<T> { Some(T), None }: Enum可以是Generic的
• impl<T> Point<T> { fn x(&self) -> &T { &self.x } }: Method可以是Generic的
  • 若impl后面不加<T>，即impl Point<T> { fn x(&self) -> &T { &self.x } }，则我们是在进行Specialization，而不是定义Generic Method，此时T应是一个Concrete Type
• trait Trait<T> { fn f<U>(&self, u: U); }: Trait可以是Generic的
  • 同一个Generic Trait，可以实例化多次并实现在同一个类型上，例如impl Trait<T> for A {}, impl Trait<U> for A {}
• Rust的Generic和C++的Template一样，会进行Monomorphization
• Rust的Generic Method不是Duck Typing的，和C++的Template Function不同。必须通过Bounded Type Parameter指定Type Parameter实现了什么Trait，不属于Trait的Method不允许调用。

首先来看Type Parameter：

• <T, U = A>: 支持多个Type Parameter，并且可以为Type Parameter提供默认值
• Struct<T, _>: 可以用_作为占位符，让Rust进行类型推导
• <T: Trait>: 支持Bounded Type Parameter，T必须实现Trait
• <T: Trait + Display + >: 支持多个Type Bound，结尾可以加一个加号（可选）
• <T: Trait + ?Sized>: Type Parameter默认要求实现Sized，可以通过?Sized解除该限制，对其他Trait而言?Trait是Nop
• where T: Trait + Display: 也可以通过where子句来指定Type Bound
  • fn f<T>(x: T) where T: Debug {}: where子句跟在类型声明的末尾，比全都写在<>内更清晰
• 利用Bounded Type Parameter，我们可以为Struct/Enum进行Specialization
  • impl<T: Trait> Point<T> {}可以为Pointer<T: Trait>进行Specialization
  • 在Rust中，这称为Blanket Implementation

通过Simple Path不能确定目标时，就需要使用Type Parameter来进一步区分，若还不能区分则需要使用Fully Qualified Path：

• 首先，Path分为Path in Expression和Path in Type
  • Path in Expression必须使用A::<T>来确定A的Type Parameter
  • Path in Type可以使用A<T>或A::<T>
  • Path in Expression是指出现在表达式中的Path，为了防止和<号混淆必须使用::，例如Vec::<u8>::with_capacity(1024)
• 其次，在trait和impl中可以使用Self
  • 在trait中指实现了该Trait的类型
  • 在impl中指impl A, impl T for A的A
• 最后，可以通过<T as Trait>::指定Qualified Path
  • S::f()调用的是S上的函数
  • <S as T1>::f()调用的是Trait T1的函数
  • <S as T2>::f()调用的是Trait T2的函数

where子句的用途实际上比<>更广泛：

• where T::Item: Copy: 可以指定Type Parameter内部的类型的Type Bound
• trait Circle where Self : Shape {}: 要求实现Circle就必须实现Shape，此时Shape被称为Supertrait
  • 可以简写为trait Circle : Shape {}
• trait A where Self::B: Copy { type B; }: 可以对Trait中的Type Declaration限制Type Bound
  • 可以简写为trait A { type B : Copy; }

Dynamic Dispatching

Rust通过trait object进行Dynamic Dispatching：

• Trait (deprecated), dyn Trait: 表示trait object类型
• dyn Trait + Send + Sync: trait object可以有多个Type Bound，但是除了第一个Type Bound以外必须都是auto trait，并且不能有?Sized
  • auto trait包括Send, Sync, UnwindSafe、RefUnwandSafe和Unpin
  • 若Base Trait不同，即使Type Bounds相同，也视为不同的trait object类型，例如dyn Send + Sync和dyn Sync + Send不同
• trait object同Slice一样，都属于Dynamically Sized Type，必须通过引用、裸指针或智能指针访问，例如&dyn Trait
  • 这是因为trait object的大小无法在编译时获知，因此也就无法分配在栈上
  • trait object的引用实现为Fat Pointer，除包含一个指向trait object的指针外，还包含一个指向其vtable的指针
• 编译器会自动为trait object实现其Base Trait，因此总是有dyn T: T
• 你可以为dyn T提供impl dyn T {}，此时trait object表现得就好像普通的struct一样

在一定条件下，编译器会自动实现auto trait，这就是为什么它们被叫做auto trait：

• 若T实现了某auto trait，则&T, &mut T, *const T, *mut T, [T; n], [T]也会自动实现该auto trait
• 若所有field都实现了某auto trait，则struct、enum、union（详见unsafe一节）、tuple也会自动实现该auto trait
• 函数和函数指针类型会自动实现所有auto trait，Closure则会实现其所有capture共同实现了的auto trait
• 注意： 若已经提供了auto trait的Generic实现，则上述规则的优先级低于Generic实现，不满足Generic实现的Type Bound则不会自动实现auto trait

---

现在我们可以总结一下Dynamically Sized Type (DST)：

• slice和trait object都属于DST
• 将DST作为Struct的最后一个Field，则此Struct也将成为DST
• 除了DST，其余所有类型都由编译器实现了Sized Trait
  • Generic中类型参数默认是实现了Sized的，即T等价于T: Sized，要想消除该限制要写成T: ?Sized
• 可以为DST实现Trait，即Trait默认没有Self: Sized的限制
• 变量、常量、函数参数都必须是Sized的，即不能使用DST，这就限制了我们必须通过引用、裸指针或智能指针来使用DST

---

只有object safe的Trait才能作为trait object的Base Trait，object safe需要满足以下条件：

• 不能有Self: Sized的Type Bound
  • 若我们允许为trait T: Sized {}创建trait object，则由于dyn T是DST，没有实现Sized（即dyn T: ?Sized），故dyn T: T必不成立，这是自相矛盾的
• 所有的supertrait也都是object safe的
• Method可以标记为where Self: Sized，此时表示该Method对trait object不可用
• 否则，必须满足以下条件
  • 不能返回Self类型，也不能使用Self类型作为参数
    • 因为dyn T类型作为DST，不能作为函数参数，也不能作为返回值被赋值给其他变量
  • 不能是Generic Function
    • 若将Generic Function的实例化也加入vtable，则vtable的大小将迅速膨胀，大量不必要的函数Specialization将会被生成，支持Generic Function因此被认为是不切实际的
  • 不能是Static Method
    • 因为没有self指针，就没有vtable，仅凭<dyn T as T>::foo()并不能确定具体的foo实例
• 不能有Constant成员
  • 因为Fat Pointer只包含了vtable，不能容纳constant
• supertrait中不能出现Self作为Type Parameter
  • 考虑trait Super<A> {}; trait T: Super<Self> {};，若Super<A>有一个Method返回A，则T将继承一个函数返回Self，这是不可接受的

---

此外，我们还有impl Trait类型，当我们需要一个opaque的static type时可以使用impl Trait，它只能用在两个地方：

• 函数的参数的类型
  • 此时fn f(x: impl Trait)和fn f<T: Trait>(x: T)等价，对于不同类型的x，都会实例化为不同的Specialization
  • 但使用impl Trait时，所有的Specialization都共享函数名f，而使用Generic时每个Specialization都有自己的函数名f::<T>
• 函数的返回值的类型
  • 适用于返回Closure，因为Closure的类型无法显式指定
  • impl Trait只能对应于一个Concrete Type（即并不支持任何意义上的多态），它可以理解为一种Existential Type
    • 如果函数不是Generic的，且参数没有impl Trait，则返回的始终是同一个Concrete Type

Pattern Matching

我们可以使用match进行Pattern Matching：

match expr {
    pattern => expr,
    _ => (),
}

• 被Match的expr称为scrutinee
  • 若它是Value Expression（即rvalue），则会创建一个临时变量，Pattern中的变量都绑定到该临时变量
  • 若它是Place Expression（即lvalue），则Pattern中的变量都直接绑定到该lvalue
• 上述含有=>的每一项称为一个Arm
  • Arm返回一个Expression则要加逗号，返回一个Block则不需要加逗号
  • 最后一个Arm可以加逗号（可选）
• | pat1 | pat2 => {}: 可以由多个Pattern构成一个Arm，开头可以加一个|（可选）
  • 用于绑定的变量，必须出现在一个Arm的所有Pattern中，并且以同样方式绑定（例如都按值绑定）
• pattern if expr => expr: 可以添加一个if expr作为match guard
  • 对于一个Arm有多个Pattern的情况，match guard可以执行多次，每次失败后就尝试匹配下一个Pattern
• Pattern Matching是exhaustive的，必须列举所有可能性，因此通常使用_ => {}表示Default Arm

if let是match的语法糖，if let pattern1 | pattern2 = expr {} else {}等价于以下match语句：

match expr {
    pattern1 | pattern2 => {},
    _ => {}
}

while let是match的另一个语法糖，while let pattern1 | pattern2 = expr { body }等价于以下语句：

loop {
    match expr {
        pattern1 | pattern2 => { body },
        _ => break,
    }
}

Pattern还能用来进行destructuring：

• for pattern in expr: 例如for (index, value) in v.iter().enumerate()
• let pattern = expr: 例如let (x, y) = (3, 4)
• fn f(pattern: type): 函数以及Closure的参数也可以使用Pattern，例如&(x, y): &(i32, i32)
• Pattern分为refutable和irrefutable两种，在上述三种语法中Pattern必须是irrefutable即必然匹配成功的，而在match、if let、while let中则必须是refutable的

Pattern的语法如下：

• true,1,-1,"string": Literal Pattern，即直接指定一个值，类似传统的switch语句的用法
• A::B::x: Path Pattern，只允许引用Constant、unit-like Struct和unit-like Enum Variant
• 'a'..='z', 1...10: Range Pattern，只能用于整数类型和char类型，范围是[LHS, RHS]，..=和...含义相同（后者现已Deprecated）
• _: Wildcard Pattern，可以match一个任意值

---

• &pattern, &mut pattern: Reference Pattern，解引用被Match的对象（scrutinee），绑定到pattern
  • 若scrutinee的类型是immutable reference，则必须使用&pattern
  • 若scrutinee的类型是mutable reference，则必须使用&mut pattern
  • 即使是&mut x，也不会使x成为mutable变量，即使使用&mut mut x，修改x也不会改变scrutinee
• ref mut x @ pattern: Identifier Pattern，将会创造一个变量x绑定到被Match的Expression的一部分，ref、mut和@ pattern都是可选的
  • x默认由scrutinee的匹配部分move或copy得到，因此实际上是一个新的本地局部变量
  • mut x表示x是mutable的，但对x的修改不会影响原来的scrutinee
  • ref x表示x是一个引用，指向匹配的部分，因此通过x可以修改原来的scrutinee
    • 注意ref x和&x不同，例如let (ref x, y) = (3, 4)合法，而let (&x, y) = (3, 4)不合法
  • x @ pattern相当于先匹配了pattern，然后将其作为一个整体绑定到了x
• Binding Mode
  • 默认的Binding Mode是move或copy
  • 当scrutinee是Reference Type而Pattern不是Reference Type时，会将scrutinee解引用而Pattern不变，然后重复匹配过程，此后Binding Mode会改为ref或ref mut
    • 这意味着x默认会被理解为ref x或ref mut x，自动成为一个引用
    • 例如let t = (3, 4); let (x, y) = &t;中，x, y都将是&i32
    • 注意：Pattern是单独一个x时，只会直接move或copy
  • 若Binding Mode已经是ref，则即使解引用了mutable reference，也不会将Binding Mode改为ref mut

通过ref x以及Binding Mode为ref/ref mut的Pattern Matching，会产生对scrutinee的borrow。

---

• (pattern): Grouped Pattern，用于明确优先级，避免Ambiguity
• path {x: pat, y: pat, ..}: Struct Pattern，用于destructure一个Struct
  • path用于指定Struct的完整路径，如A::B::C
  • 对于tuple struct，应使用0: pat, 1: pat, ..
  • 末尾的, ..表示其余Fields，是可选的，不使用..则需要列出所有Field
  • {x, ref y, mut z}: 等价于{x: x, y: ref y, z: mut z}，相当于Struct初始化的反向操作
• path (pat, pat,): Tuple Struct Pattern，用于destructure一个tuple struct
  • path (pat, pat, ..), path (.., pat, pat), path (pat, .., pat)可以用于省略若干元素
• (pat, pat,): Tuple Pattern，用于destructure一个Tuple
  • (pat, pat, ..), (.., pat, pat), (pat, .., pat)可以用于省略若干元素
• [pat, pat,]: Slice Pattern，用于destructure一个Array或Slice
  • 目前在Slice Pattern中不支持..的使用

More on Move Semantics

首先，我们进一步明确move的语义：

• Expression分为Place Expression（即左值lvalue）和Value Expression（即右值rvalue）
• 又有Place Expression Context和Value Expression Context的区别，前者期望一个左值而后者期望一个右值
  • 例如Assignment操作，LHS为Place Expression Context，RHS为Value Expression Context
• 若一个Place Expression出现在Value Expression Context，则我们需要取出其值，这一步就会进行move或copy操作
  • 注意： 已经被borrow过的变量，不能被move（关于borrow下面会详细介绍）
  • 当然，其value已经被move走的变量，也不能被move

另一方面，若Value Expression出现在Place Expression Context，则会创建一个临时变量，以获得其地址，其lifetime为：

• 对于在if或while条件中创建的临时变量，在条件判断完毕后就会销毁
  • let x = if foo(&temp()) {bar()} else {baz()};: 临时变量会在bar, baz执行前销毁
  • while foo(&temp()) {bar();}: 临时变量会在bar执行前销毁
• 对于其他情况，lifetime为最内层的包含该Value Expression的语句（a.k.a innermost enclosing statement）
  • let x = foo(&temp());，临时变量会在赋值完成后销毁
• 对于let语句，若临时变量的引用/指针被赋值到LHS，则临时变量的lifetime会扩展为整个let语句所在的innermost enclosing statement
  • let x = &temp(), let x = S { foo: &temp() }, let x = [ &temp() ]: 临时变量会延续到整个block结束
  • let ref x = temp(): 通过ref x的pattern，实现的效果是相同的

现在来看各种类型的move语义：

• 基本类型都支持copy语义
• 对Array和Tuple，若所有成员都可以copy，则它可以copy
• 对immutable引用使用copy语义
  • let a = &x; let b = a;: a, b均为对x的immutable引用
• 对mutable引用使用move语义，这保证了mutable引用的唯一性（uniqueness）/排他性（exclusiveness）
  • let a = &mut x; let b = a;: 仅b为对x的有效mutable引用，a中存放的引用已经被move走
• 对Struct、Enum等用户自定义类型，默认没有实现Copy，采用move语义
  • 可以通过impl Copy for T {}让其支持copy语义，注意此处不需要填写实现，因为copy语义是由编译器自动实现的
  • 也可以在类型的定义前添加#[derive(Copy)]效果相同
  • 若其成员有不可copy的，或其实现了DropTrait，不允许实现Copy，此时上述做法无法通过编译

Functions and Closures

我们首先考察函数类型，有两种函数类型：

• function item type: 函数以及tuple-like struct和enum variant的constructor，其本质类型都是function item
  • 该类型的Size为0，并且Rust的Type Annotation语法无法表示这种类型
  • 每个函数的function item type都是不同的，即使两个函数signature相同仅名称不同，它们也是不同的类型
  • 编译器出错信息中function item type的格式为fn(i32) -> i32 {foo}，最后的{foo}就是表示函数名称，函数名不同则类型不同
• function pointer type: fn (i32) -> i32
  • 类型也可写作fn (_: i32) -> i32或fn (x: i32) -> i32，参数名会被编译器忽略
  • function item可以隐式转换（coercion）成function pointer，特别地，这可以在条件语句中发生
    • if expr { fn_item1 } else { fn_item2 }中，若fn_item1和fn_item2signature相同但不是同一个function item，整个表达式的返回值将是一个函数指针
  • non-capture的closure也可以隐式转换成function pointer
  • unsafe和extern的函数也可以转换为函数指针，特别地，来自C的函数（"C", "cdecl"）支持变长参数（variadic parameters）

再来看closure，创建closure的语法类似Ruby：

• |pat1, pat2| expr: 简单的closure不需要加花括号
• |pat1: T1, pat2: T2| -> Tr {}: 类型信息是可选的
• 可以使用irrefutable pattern来指定参数，例如|(x, y)| -> x + y

closure可以对外界变量进行capture：

• 有三种capture mode，分别是immutable borrow、mutable borrow和move，即通过immutable引用、mutable引用或值捕获
• 编译器会自动选择变量的capture mode，优先选择immutable borrow，其次mutable borrow，最后move，选择的依据是以能编译通过为准
• move |pat1, pat2| -> expr: 通过添加move关键字，可以强制所有变量按值捕获
• closure body中即使只引用了structure、tuple或enum的一部分，也会按整体进行捕获

---

现在来考察以上三种类型的move语义：

• function item和function pointer显然可以进行copy
• 本质上，closure可以理解为一个struct，里面包含了其捕获的变量
• 若所有的capture都可以copy，则整个closure可以copy，否则使用move语义
  • 若存在mutable borrow捕获，则不能copy
  • 若存在按值捕获，则捕获的变量必须支持copy语义，否则不能copy

同function item一样，每个closure的类型都不同，并且无法在Rust中表示。我们可以通过Trait来表示closure：

• 共有三种Trait，分别是FnOnce、FnMut和Fn
• 配合参数和返回值类型才构成完整的Trait，例如FnOnce(i32) -> i32
• FnOnce调用时，closure作为self按值传入
  • 若closure没有实现Copy，则FnOnce只能使用一次，这就是其名称的由来
  • 所有closure都会自动实现FnOnce
• FnMut调用时，closure作为&mut self按mutable引用传入
  • 若closure会将捕获到的值或引用返回（即move到closure外部），则它真的只能调用一次，不允许实现FnMut和Fn
• Fn调用时，closure作为&self按immutable引用传入
  • 若closure含有mutable borrow捕获，则不允许实现Fn
• Fn: FnMut, FnMut: FnOnce: 它们之间有supertrait的关系，从上面的描述不难看出这样设计的理由
• function item和function pointer都会自动实现FnOnce、FnMut和Fn，因为它们没有任何capture，这三者对它们没有区别
• 为了将closure作为值从函数返回，我们可以使用impl Fn(i32) -> i32作为函数的返回值类型，这样就不需要先将其包装到堆上再返回了

Smart Pointers

在Rust中仅仅使用reference是无法在堆上分配内存的，为了在堆上管理对象，我们需要使用智能指针。

首先来看std::boxed::Box<T>:

• 类似于C++的unique_ptr
• 可以使用Box::new(x)创建一个box，它将对x持有ownership
• 没有实现Copy，采用move语义
• 可以对box直接使用*解引用操作符
• box在离开作用域时会释放其申请的内存，因为Box<T>实现了Drop这个Trait

可以调用std::mem::drop(x)令x提前析构，但只对move语义的x有效，这也就包括了Box<T>

对于Box<T>可以使用解引用操作符，是因为其实现了Deref和DerefMut这两个Trait：

• 对于immutable的x，*x相当于*std::Deref::deref(&x)，其中deref返回&Self::Target
• 对于mutable的x，*x相当于*std::DerefMut::deref_mut(&mut x)，其中deref_mut返回&mut Self::Target
• 若T: Deref<Target=U>，则&T类型的变量会coercion（隐式类型转换）到&U类型
  • 例如&Box<T>会被coercion到&T，所以对于f: fn(&T)可以这样调用：f(&x), x: Box<T>
• 若T: DerefMut<Target=U>，则&mut T类型的变量会coercion到&mut U或&U类型

---

我们接下来考察interior mutability：

• 通常只有声明为mutable的变量以及mutable引用允许修改，这称为inherited mutability
• 但部分具有interior mutability的类型允许通过immutable reference对其内容进行修改
• 所有的interior mutability都是来自于std::cell::UnsafeCell<T>的
  • 例如所有原子变量和锁都具有interior mutability，它们内部都是用UnsafeCell<T>实现的

UnsafeCell<T>其实是一个简单的值类型容器：

pub struct UnsafeCell<T: ?Sized> {
    value: T,
}

• 通过UnsafeCell<T>::new(x)创建一个unsafe cell
• 通过UnsafeCell<T>::get(&self) -> *mut T可以从unsafe cell获得指向其内部的值的raw pointer
  • 所有的interior mutability实际上都是依据这个raw pointer实现的
  • memory safety要由raw pointer的使用者来保证，unsafe cell只是提供raw pointer而已，不提供任何safety保证。不管怎样，若要使用raw pointer，必须用到unsafe块，此时保证safety的责任就交给了调用者。

std::cell::Cell<T>提供了一个具有interior mutability的值类型，它实际上就是对UnsafeCell<T>的简单包装，内存布局仍等价于{T}：

• 它不是线程安全的，只能在单线程使用
• 通过Cell<T>::new(x)创建一个cell
• 若T: Copy，可以通过Cell::get(&self) -> T获得cell的当前值
• 通过Cell<T>::set(&self, T)可以为cell赋值
• 通过Cell<T>::replace(&self, T) -> T可以为cell写入新值，同时将旧值换出

有多个&Cell<T>时，各个引用都可以使用set进行赋值，从而体现了interior mutability

std::cell::RefCell<T>仍是值类型，即它直接含有T而不是通过引用或指针持有T：

• 它不是线程安全的，只能在单线程使用
• 通过RefCell<T>::new(x)创建一个ref cell
• 通过RefCell<T>::borrow(&self) -> Ref<T>获得一个模拟immutable reference的Ref<'b, T>对象
  • 若当前已经被mutably borrow过，则立即panic
  • 若不想panic，可以使用RefCell<T>::try_borrow(&self) -> Result<Ref<T>, BorrowError>
  • Ref<T>含有一个&T，Ref<T>实现了Deref因此可以像&T一样使用
• 通过RefCell<T>::borrow_mut(&self) -> RefMut<T>获得一个模拟mutable reference的RefMut<'b, T>对象
  • 若当前已经被borrow过，则立即panic
  • 若不想panic，可以使用RefCell<T>::try_borrow_mut(&self) -> Result<RefMut<T>, BorrowMutError>
  • RefMut<T>含有一个&mut T，RefMut<T>实现了Deref和DerefMut因此可以像&mut T一样使用
• 还可以通过RefCell<T>::replace(&self, T) -> T替换ref cell的值
  • 若当前已经被borrow过，则立即panic

有多个&RefCell<T>时，相当于它们共享对T的ownership，各个引用都可以获得&T或&mut T，但Rust的borrow规则仍会通过运行时检查得到保证

---

下面来看std::rc::Rc<T>，这是一个基于引用计数的智能指针：

• 类似于C++的shared_ptr，但不是线程安全的，只能在单线程使用
• 通过Rc<T>::new(x)创建一个Rc<T>，它将对x持有ownership
• Rc<T>实现了Deref，因此可以直接对其使用*解引用操作符，但未实现DerefMut，因此只能获得immutable reference，不能进行修改
  • 可以借助interior mutability实现共同引用T且能修改其值，只要使用Rc<RefCell<T>>即可
• 通过Rc<T>::clone(x)可以复制一份Rc<T>，并将引用计数+1
  • 这里的引用计数是指strong reference count

我们知道基于引用计数的智能指针面临引用成环的问题，需要引入弱引用，Rc<T>对应的弱引用就是std::rc::Weak<T>：

• Rc<T>::downgrade(this: &Rc<T>) -> Weak<T>: 产生一个弱引用，令weak reference count +1
  • 注意原本的强引用并未销毁，该函数执行后强引用数量不变，弱引用数+1
• Rc<T>::weak_count(this: &Rc<T>) -> usize, Rc<T>::strong_count(this: &Rc<T>) -> usize: 返回当前的弱引用、强引用计数
  • Rc<T>析构时，会令强引用计数-1，Weak<T>析构时，会令弱引用计数-1
  • 强引用计数到零时，即可调用T的析构函数drop
  • 弱引用计数到零时，才会真正释放内存
• Weak<T>没有实现Deref，必须调用Weak<T>::upgrade(&self) -> Option<Rc<T>>升级成Rc<T>后才能读取
  • 若强引用计数为零，则升级失败
• 通过Weak<T>::clone(x)可以复制一份Weak<T>，并将弱引用计数+1

若需要使用线程安全的智能指针，可以使用std::sync::Arc<T>和std::sync::Weak<T>，其引用计数使用原子操作维护（Arc意为Atomically Reference Counted）

Method的self参数可以显式指定类型，除了此前提到的Self、&Self和&mut Self外，还支持智能指针，包括：

• Box<Self>, Rc<Self>, Arc<Self>
• Pin<&Self>, Pin<&mut Self>, Pin<Box<Self>>, Pin<Rc<Self>>, Pin<Arc<Self>>（Pin<T>类型详下）

---

Rust提供了std::borrow::Borrow<T>和std::borrow::BorrowMut<T>，用于抽象borrow行为：

• Borrow<T>提供了borrow(&self) -> &T方法，代表能以&T被borrow的类型
  • 对于任意T总有T: Borrow<T>
  • Box<T>, Rc<T>, Arc<T>都实现了Borrow<T>
• BorrowMut<T>提供了borrow_mut(&mut self) -> &mut T方法，代表能以&mut T被borrow的类型
  • 对于任意T总有T: BorrowMut<T>
  • Box<T>实现了BorrowMut<T>
• 一个类型可以被borrow为几种类型，例如String: Borrow<String>且String: Borrow<str>

若T: Clone，则我们可以通过clone方法从一个borrowed的&T获得一个owned的T，std::borrow::ToOwned就是这一概念的泛化：

pub trait ToOwned {
    type Owned: Borrow<Self>;
    fn to_owned(&self) -> Self::Owned;
}

我们假设T: ToOwned，则我们可以通过to_owned方法从一个&T获得一个owned的Borrow<T>。

现在我们来看Rust中提供的CoW的智能指针std::borrow:Cow：

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

• 实现了Deref，可以直接使用*解引用操作符，deref返回的是&B
• 但没有实现DerefMut，而是要通过Cow<B>::to_mut(&mut self) -> &mut <B as ToOwned>::Owned获得对owned data的mutable reference
  • 若当前值还是Borrowed(p)，则会通过clone先将当前值变为Owned(v)，再返回&mut v，这就是Copy-on-Write
• Cow<B>::into_owned(self) -> <B as ToOwned>::Owned会直接将data移出，若尚处在Borrowed状态，则先进行clone

Error Handling

当遇到不可恢复的错误时，可以使用panic!("message")结束当前线程。panic!默认会进行Stack Unwinding，调用变量的destructor（即drop函数）进行一定程度的清理。若希望立即abort，结束整个进程，则可以在Cargo.toml中加入以下内容：

[profile.release]
panic = 'abort'

若在panic过程中再次panic，即所谓的double panic，则程序会直接abort。由于drop函数会在stack unwinding时被调用，在drop函数中调用panic!很可能导致double panic，建议不要在drop函数中panic。

通常，我们使用Error Code来表示一个可恢复的错误：

enum Result<T, E> {
    Ok(T),
    Err(E),
}

Result有很多方法方便其使用，避免错误处理代码充斥着match：

• result.unwrap(): 若为Ok(T)则获得T，否则panic
• result.expect(msg): 若为Ok(T)则获得T，否则panic，使用msg作为panic message
• result.unwrap_or_else(op): 若为Ok(T)则获得T，否则对E调用函数op（接受E返回T），并返回其返回值

如果不想在当前函数处理错误，而是希望将错误propagate到上层，我们可以使用?操作符：

• let r = result?;: 当result为Ok(T)时获得T并赋值给r，否则函数直接返回result
  • 若result的类型为Result<T,E>，函数的返回值为Result<T,E'>，则会自动将E转换到E'，并返回Err(E')
• ?操作符只能在返回值为Result的函数中使用，为了在main函数中使用?操作符，可以令main函数返回一个Result

在早期是使用try!宏来实现此处?操作符的功能，由于这个功能太常用所以专门发明了?操作符，现在try!已经deprecated，并且在Rust 2018 Edition中try已经被保留为keyword

Writing Tests

凡是标记有#[test]属性的函数，都会被视为测试函数，在测试时会创建一个线程专门运行该函数：

• 测试函数不能是Generic的，且不能有输入参数
• 测试函数只能返回()或Result<(), E: Error>
• 返回()的测试函数，若panic则视为测试失败，否则视为测试通过
• 返回Result<(), E: Error>的测试函数，若返回Ok(())则视为测试通过，否则视为测试失败

对于返回()的测试函数，还可以加上#[should_panic]属性：

• 此时若函数panic则视为测试通过，否则视为测试失败
• #[should_panic(expected = "...")]: panic信息中含有expected时，才视为测试通过，否则视为测试失败

测试函数中常用的宏如下：

• assert!(expr): 当expr为false时panic
• assert_eq!(expr, expr), assert_ne!(expr, expr): 当两个expr不等/相等时panic
• 以上宏可以提供额外的参数，以输出格式化字符串，如assert!(expr, "sth bad: {}", bad_stuff)

---

运行cargo test即可运行测试，实际上cargo test还会将doc comment中的样例代码也作为测试运行：

• cargo test -- --test-threads=1: 令测试按顺序执行，默认是多线程并发执行
• cargo test -- --nocapture: 实时打印测试函数的输出，默认是收集其输出，并在全部测试运行完毕后，只打印测试失败的函数的输出
• cargo test TESTNAME: 只有函数名包含TESTNAME的测试函数会被执行
• cargo test -- --ignored: 运行具有#[ignore]属性的测试函数，默认行为是忽略具有#[ignore]属性的测试函数

单元测试通常放在一个名为tests的module中，并和被测试的代码写在同一个rs源文件中：

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}

其中#[cfg(test)]表示条件编译，只有在运行cargo test时才会编译测试模块。

集成测试则是放在项目根目录下的tests/目录中，与src/目录平级：

• tests/目录下的每个文件都构成一个独立的crate，因此我们不需要#[cfg(test)]进行条件编译
• cargo test --test TESTNAME: 运行tests/TESTNAME.rs中的所有测试
• tests/subdir/mod.rs: 可以用来为测试文件提供modulesubdir，因为所有子目录下的文件都不会被编译为独立的crate
• 只有library crate可以有集成测试，binary crate不支持集成测试
  • 因此Rust项目通常将大部分逻辑实现在library crate中，然后提供一个binary crate作为thin wrapper

More on Cargo

Cargo有release profile的概念，默认有dev和release两个profile。我们可以通过[profile.dev], [profile.release]覆盖默认的参数：

[profile.release]
opt-level = 3

将crate上传至crates.io只需要两步：

• 用Github账号注册crates.io账号，获得API token，然后运行cargo login $TOKEN
• 运行cargo publish

欲成功上传，在[package]项目下要填写如下信息：

• name: 与*crates.io*上已有的项目不能冲突
• description: 用一两句话介绍该项目
• license: 必须选择一个License，可使用SPDX规定的缩写作为License名称
  • 可以用MIT OR Apache-2.0的形式指定Dual License
  • SPDX中没有的License，需要通过license-file直接指定License文件

一旦上传到*crates.io*，就不能再删除。若发布的某个版本存在严重问题，可以通过cargo yank --vers 1.2.3进行补救，执行后新项目将不能再下载并使用1.2.3版本，但已经生成了Cargo.lock文件的旧项目仍能使用1.2.3版本。

---

当项目的规模扩大到一定程度，可能希望分解成多个crate来实现，此时就需要*workspace*功能对多个package进行组织：

[workspace]

members = [
    "bin-crate",
    "lib-one",
    "lib-two",
]

• 一个workspace下的package共享一个Cargo.lock文件以及output目录
• package之间默认不会有依赖，需要手动指定：

[dependencies]

lib-one = { path = "../lib-one" }

• 每个package的外部依赖都要各自指定，不能在workspace的Cargo.toml中指定

Part II. Advanced Rust

Pinned Pointers

有时我们需要一个self-referential的struct，对于这种对象，其内存地址必须固定，也就是说其value不能被move。Rust提供了Pin<P>类型，来实现「pin」住内存的需求：

• Pin<P>是对指针P的包装，它要求P至少实现了Deref和DerefMut其中之一，Pin<P>的所有method都只为指针类型实现
  • 也就是说，Pin<i32>根本没有method，你甚至无法创建一个Pin<i32>
• Pin<P>提供的invariant是一个强约束，一旦为P的实例p创建对应的Pin<P>对象，就要求p指向的value永远不能被move或invalidate，直到该value析构（被drop）为止
  • 也就是说，即使Pin<P>本身已经析构，只要p指向的value还有效，Pin<P>提供的约束就必须仍保持有效。

**注意:** 使用std::mem::swap<T>(x: &mut T, y: &mut T)，可以在不改变x和y的地址的情况下，将x和y中的value交换位置，此时也发生了move。从中可以看出，对value的move不一定要持有其ownership，只要持有其mutable reference即可完成。

此外，还增加了一个Auto Trait Unpin，可以抵消pin的效果，即<P as Deref>::Target: Unpin时，就不需要维持Pin<P>的invariant，Pin<P>可以视同普通的P：

• 实际上大部分类型都是Unpin的，只有需要内存地址固定作为其invariant的类型T（例如自引用的类型），才需要显示声明为!Unpin
• 通过引入一个（大小为零的）std::marker::PhantomPinned类型的field，可以避免自动实现Unpin
• &T, &mut T, Box<T>, Rc<T>, Arc<T>等类型都是Unpin的，因为它们不要求内存地址固定即可工作，这里要分清指针指向的T是否为Unpin和指针本身是否为Unpin是两回事

Pin<P>实现pin功能实际上靠的就是encapsulation，其暴露的API不足以实现对其指针P指向的value进行move或invalidate，这样就阻止了对value进行move或invalidate。

我们来看对于P: Deref，Pin<P>提供了哪些接口：

• 实现了Deref，Deref::deref(&self)返回一个&<P as Deref>::Target，这样Pin<P>作为指针就和P用法相同
• 只提供了unsafe的Pin::new_unchecked(x)进行初始化
  • Pin<P>的invariant就是在此调用后，x指向的value就不能再被move或invalidate，直到该value析构为止
  • 由于我们无法保证此invariant，所以该函数是unsafe的，invariant要由调用者保证
• 提供了Pin<P>::as&lowbar;ref(&self) -> Pin<&<P as Deref>::Target>，可以将&Pin<Pointer<T>>变为Pin<&T>
  • 该函数是safe的，因为根据new_unchecked的约束条件，在从Pointer<T>获取&T的过程中不会发生move

再来看对于P: DerefMut，Pin<P>又提供了哪些接口：

• 没有实现DerefMut，因此无法获取被指向的类型T的mutable reference&mut T进行move
• 提供了Pin<P>::as&lowbar;mut(&mut self) -> Pin<&mut <P as Deref>::Target>，可以将&mut Pin<Pointer<T>>变为Pin<&mut T>
  • 若Pointer::deref_mut能保持invariant，不moveT的value，则Pin<Pointer<T>>的invariant能够保持，于是Pin<&mut T>的invariant也能保持
• 提供了Pin<P>::set(&mut self, <P as Deref>::Target)，可以替换被指向的类型T的value，由于替换前会执行drop函数，这并不违反invariant

对于P: DerefMut, <P as Deref>::Target: Unpin，Pin<P>额外实现了DerefMut，这样一来Pin<P>就和P全无差别。

---

应当注意到，调用new_unchecked(x)时建立的contract实际上包括两点：

• 在Pin<P>尚未析构前，通过Pin<P>调用P::deref、P::deref_mut以访问到目标T时，不会对T的value进行move，即要求指针P的实现不是malicious的
• 在Pin<P>析构后，即P析构后，P指向的value仍不会被move
  • 例如若P为&mut T，则P“析构”后，被其指向的v: T仍然可以存在，并且可以被move，那么调用者就必须保证v实际上不可能被move，否则就属于违反contract，是调用者的编程错误

关于第一点，由于Pin<P>将接口限制在以上范围，这就使得在Pin<P>析构前，完全不可能获取对P指向的T的ownership或mutable reference，因此唯一有机会对T的value进行move的就只有P::deref和P::deref_mut。只要保证这两个函数不是malicious的，就能保证第一条约束条件成立。

关于第二点，注意到Pin<P>在内存中的表示与P完全相同，这样当Pin<P>析构时，P也随之析构，且在Pin<P>析构前我们无法直接取出P，因为Pin<P>只提供了unsafe的Pin<P>::into&lowbar;inner&lowbar;unchecked(Pin<P>) -> P。为了满足第二条约束条件，我们通常要求P对T是own而不是borrow关系，即当P析构时T也一起析构，那么T就不可能还会被move。

对于Box<T>、Rc<T>、Arc<T>，显然满足上述两个条件，因此我们可以安全地将它们Pin住。实际上，我们可以safe地从T直接创建Pin<Pointer<T>>，并能保证T不被move：

• Box<T>::pin(T) -> Pin<Box<T>>
• Rc<T>::pin(T) -> Pin<Rc<T>>
• Arc<T>::pin(T) -> Pin<Arc<T>>

---

使用Pin<P>时，还有一些注意点。首先，drop函数接受的参数为&mut self，但若Self有被pin住的需求，则必须先将其&mut Self类型的参数转化为Pin<&mut Self>，再实现drop函数，以避免在drop的过程中违反了Pin<P>的invariant。

其次，有时可能希望操作被pin住的struct的其中一个field，或者被pin住的enum的一个variant，这就需要获取对其的引用。我们需要通过unsafe的helper method来获取这样的引用，一般称之为projection。

以获取mutable引用为例，此时有两种选择：

• structral projection，即获取一个Pin<&mut Field>
• non-structral projection，即获取一个&mut Field
• 但对同一个field，不能混用两者

对于non-structral projection，只要没有同时存在一个Pin<&mut Field>，我们就无需对&mut Field保证任何invariant，这样的用法自然是safe的。

对于structral projection，需要保证以下几点：

• 只有当所有采用structral projection的field都是Unpin时，整个struct才能是Unpin的
• 整个struct不能提供违反structral projection的invariant的method，包括其drop函数也如此
  • 即method不能移动structral field
  • 且drop函数要将&mut Self先转换为Pin<&mut Self>再行操作

Concurrency

要进行并发编程，首先就需要有多线程，在Rust中线程功能由std::thread提供：

• Rust的线程是1:1的，M:N的green thread/coroutine可以由额外的crate提供
• 通过thread::spawn(move || {...})创建一个线程
  • 它接受一个FnOnce() -> T参数
  • 返回一个thread::JoinHandle<T>
• 通过JoinHandle<T>::join(self) -> Result<T>可以join创建的线程，若不调用则当返回的JoinHandledrop时，就会和创建的线程detach
  • join的返回值为Result<T>，若线程发生panic而没有正常返回，则返回值为Err而不是Ok(T)
• 通过thread::LocalKey<T: &apos;static>表示thread local storage，tls变量的lifetime必须是'static
  • 通过std::thread_local! {...}宏创建tls变量，其中的static变量声明都会被处理为tls变量
  • 通过key.with(|t| {...})使用tls变量key，它接受一个FnOnce(&T) -> R，返回一个R
  • tls变量只能通过&T访问，因此若要修改tls变量必须用到Cell<T>或RefCell<T>

Rust中有两个特殊的TraitSend和Sync：

• Send表示该类型的ownership可以在thread之间转移
• Sync表示该类型可以被多个thread引用，更准确地定义是T: Sync当且仅当&T: Send
• 裸指针没有实现Send和Sync，其余基本类型（不包括引用）都实现了Send和Sync
• 数组、tuple、struct、enum等组合类型，其成员实现了Send或Sync，则该类型自动实现Send或Sync
• 引用不会默认实现Send或Sync，关于引用的规则如下：
  • 若T: Sync，则&T: Send + Sync且&mut T: Sync
  • 若T: Send，则&mut T: Send
• Cell<T>、RefCell<T>没有实现Sync，Rc<T>没有实现Sync和Send，通常都是这类具有*interior mutability*，但实现方式线程不安全的类型，会不实现Sync和Send

Shared Memory

在std::sync::atomic中提供了底层的同步原语，包括内存屏障（memory barrier）和原子操作：

• Ordering有以下几种：
  • Relaxed: 相当于C++11的memory_order_relaxed，没有任何Happen-Before约束
  • Release: 相当于C++11的memory_order_release
  • Acquire: 相当于C++11的memory_order_acquire
  • AcqRel: 相当于C++11的memory_order_acq_rel，其Acquire和Release操作之间不是SC的（允许Release->Acquire乱序成为Acquire->Release）
  • SeqCst: 相当于C++11的memory_order_seq_cst
• compiler_fence(order: Ordering)提供了编译器级别的内存屏障
  • 若order为Relaxed则panic
• fence(order: Ordering)提供了CPU指令级别的内存屏障
  • 若order为Relaxed则panic
• AtomicBool, AtomicI8/I16/I32/I64/Isize/U8/U16/U32/U64/Usize, AtomicPtr（包装了一个裸指针*mut T）
  • load(&self, Ordering) -> T: load的同时emit内存屏障
  • store(&self, T, Ordering): store的同时emit内存屏障
  • swap(&self, T, Ordering) -> T: 首先swap操作是原子的，其次至少具备Ordering指定的barrier语义
  • compare_and_swap(&self, current: T, new: T, order: Ordering) -> T: 首先CAS操作是原子的，其次至少具备Ordering指定的barrier语义
  • 此外还有compare_excahnge, fetch_add, fetch_sub等，详情可查阅文档

高级的同步原语自然是mutex和rwlock，分别是sync::Mutex<T>和sync::RwLock<T>。Rust中的锁和数据绑定，这是为了防止访问数据时忘记加锁。通常都是将锁放在智能指针里进行使用，如Arc<Mutex<T>>, Arc<RwLock<T>>。

先来看Mutex<T>，其中T作为值直接嵌入在Mutex<T>中，不涉及引用：

• 具有*interior mutability*，多个对其持有shared reference的线程可以各自进行加锁，从而修改其内嵌的T
• 通过Mutex::new(x)创建一个新的mutex
• 通过Mutex::lock(&self) -> LockResult<MutexGuard<T>>加锁
  • 首先，返回值是一个Result类型，若返回Err则表示该mutex处在poisoned状态，通常我们直接unwrap()即可
  • 所谓poisoned就是当thread在持有锁时发生panic，则该锁会进入poisoned状态，不允许其他线程加锁
  • MutexGuard<T>是一个RAII类型，在它析构（drop）时会将锁释放
  • MutexGuard<T>实现了Deref和DerefMut，因此可以直接进行*解引用操作

再来看RwLock<T>，其中T也是作为值直接嵌入在RwLock<T>中：

• 具有*interior mutability*，多个对其持有shared reference的线程可以各自获取写锁，从而修改其内嵌的T
• 通过RwLock::new(x)创建一个新的rwlock
• 通过RwLock::read(&self) -> LockResult<RwLockReadGuard<T>>获取读锁
  • 返回值是Result类型，Err表示poisoned，对于读写锁只有当thread在持有写锁时panic才会进入poisoned状态，在持有读锁时panic不会影响读写锁的状态
  • RwLockReadGuard<T>在析构时会将读锁释放，它实现了Deref因此可以进行读取
• 通过RwLock::write(&self) -> LockResult<RwLockWriteGuard<T>>获取写锁
  • RwLockWriteGuard<T>在析构时会将写锁释放，它实现了Deref和DerefMut因此可以读写

此外我们还有conditional variablesync::Condvar：

• 通过Condvar::new()创建一个新的conditional variable
• 通过Condvar::wait(&self, MutexGuard<&apos;a, T>) -> LockResult<MutexGuard<&apos;a, T>>进行等待
  • 在等待的同时会释放锁，当被唤醒时会自动重新获取锁，若获取失败则会返回Err
• 通过Condvar::notify_one(&self)唤醒一个等待的线程
• 通过Condvar::notify_all(&self)唤醒所有等待的线程

Message Passing

Rust中message passing功能由std::sync::mpsc提供，其中mpsc意为Multiple Producer Single Consumer：

• 通过mpsc::channel<T>() -> (Sender<T>, Receiver<T>)创建channel的两端
• 或通过mpsc::sync&lowbar;channel<T>(usize) -> (SyncSender<T>, Receiver<T>)创建channel的两端
• Sender<T>不是Sync的，必须通过clone来实现multiple producer
• 若T: Send则SyncSender<T>: Sync，因此只需通过shared reference即可实现multiple producer

Sender<T>是一个non-blocking的sender：

• send(&self, T) -> Result<(), SendError<T>>是non-blocking的发送操作
• 返回Ok不代表receiver能收到该消息，只是表示发送成功
• 返回Err表示receiver已经被销毁

SyncSender<T>有一个固定大小的buffer，其大小在调用sync_channel时指定：

• send(&self, T) -> Result<(), SendError<T>>
  • 若buffer size为0，则会block直到receiver收到消息
  • 否则，会block直到能将消息放入buffer，但不保证receiver收到消息
  • 返回Err表示receiver已经被销毁
• try&lowbar;send(&self, T) -> Result<(), TrySendError<T>>
  • 若不能立即发送，则返回Err
  • TrySendError<T>是一个enum，包含Full(T)和Disconnected(T)两种variant

Receiver<T>负责接收消息：

• recv(&self) -> Result<T, RecvError>: blocking操作，若channel上可能会来消息，则会一直保持等待
  • 返回Err表示所有的sender都已经被销毁
• try&lowbar;recv(&self) -> Result<T, TryRecvError>: non-blocking操作，TryRecvError是一个enum，包含Empty和Disconnected两种variant
• recv&lowbar;timeout(&self, Duration) -> Result<T, RecvTimeoutError>: 等待消息到来，直到超时为止
• for msg in rx {}: 从receiver可以获得iterator，因此我们可以直接对receiver使用for循环

Attributes

Attribute分为两种：

• #![attr]: inner attribute，作用于attribute所在的item
• #[attr]: outer attribute，作用于紧接着的item

#[attr]中的attr称为*meta item*，其格式如下：

• A::attr: 首先必须有一个*simple path*，后面的内容可选
• A::attr = "abc": 可以跟一个=加上literal（数字、字符串）
• A::attr($meta0, $meta1, ..., $metaN): 递归定义，每个$meta可以是一个literal或一个meta item

---

现在来看条件编译，一个条件编译的predicate形式如下：

• id, id= "str"
• all($pred0, $pred1, ..., $predN), any($pred0, $pred1, ..., $predN): 其中$pred为条件编译的predicate
• not($pred): 其中$pred为条件编译的predicate

我们可以用#[cfg($pred)]对紧接着的item进行条件编译，例如#[cfg(target_os = "macos")]。

我们可以使用#[cfg_attr($pred, $attr0, $attr1, ..., $attrN)]来条件启用attributes，例如#[cfg_attr(linux, path = "linux.rs")]。

在表达式中，可以使用cfg!($pred)宏，当predicate为真时，会展开为true，否则展开为false。

常用的predicate如下：

• target_arch = "x86"
• target_feature = "avx"
• target_os = "windows"
• target_family = "unix", target_family = "windows": 目前只有这两个family，分别可以简写为unix和windows
• target_env = "gnu"
• target_endian = "little", target_endian = "big"
• target_pointer_width = "32", target_pointer_width = "64"
• target_vendor = "unknown"
• test: 仅在rustc --test, cargo test时编译
• debug_assertions: 编译debug_assert!宏，默认仅在不开启优化时编译debug_assert!
• proc_macro: 表示当前crate以proc-macro类型编译，这种类型的crate只允许导出procedural macro

crate的编译类型包括：

• #[crate_type = "bin"]: 即binary crate
• #[crate_type = "lib"]: 即library crate，生成什么类型的library是compiler defined的
• #[crate_type = "dylib"]: 生成动态链接库（*.so, *.dll, *.dylib）
  • 包含metadata，只能被Rust程序链接
• #[crate_type = "staticlib"]: 生成静态链接库（*.a, *.lib）
  • 用途是提供给其他语言的程序使用
• #[crate_type = "cdylib"]: 生成动态链接库
  • 用途是提供给其他语言的程序链接
• #[crate_type = "rlib"]: 生成「Rust库」，只能被Rust编译器链接到Rust程序
• #[crate_type = "proc-macro"]: 只导出procedural macro

---

上文已经介绍过关于测试的attribute：

• #[test]: 将函数标记为测试函数
• #[ignore = "why ignored"]: 令测试函数默认被忽略
• #[should_panic(expected = "msg")]: 使测试函数panic时测试通过，否则测试失败

下面再介绍一些内置的attribute：

• #[derive(PartialEq, Clone)]: 可以自动实现Trait
• #[inline]: 提示编译器inline该函数
  • #[inline(always)], #[inline(never)]: 强制编译器inline/不要inline该函数
• #[cold]: 提示编译器该函数很少被调用
• #[path = "foo.rs"]: 指定module的源文件路径
• #[deprecated = "why deprecated"]: 表示deprecated API
  • #[deprecated(since = "5.2", note = "foo is bad, use bar instead")]: 用此形式可以说明自某版本起deprecated
• #[must_use = "why must use"]: 表示必须使用

Hygienic Macro

首先，我们定义token tree:

• token tree就是一棵由token构成的树，所有token都属于叶子节点
• (...), [...], {...}可以作为非叶子节点，将其下的子树group起来

宏在使用时，后面跟着一棵token tree。由于Rust的宏是卫生宏，宏展开的过程是一种AST变换，将token tree替换成新的AST：

• mac!(...), mac![...], mac! {...}

Macros by Example

用macro_rules!可以定义宏，我们称这种方式为macros by example:

macro_rules! $name {
    ($pattern) => {$expansion};
    $rule1;
    //...
    $ruleN
}

• macro_rules的body由若干条替换规则构成，规则的左边称为matcher，右边称为transcriber
• 实际上macro_rules! $name (...);, macro_rules! $name [...];的写法也是可以的，matcher和transcriber也可以使用三种括号中的任意一种
  • 但一般习惯上matcher用()，其余两个用{}
• matcher和transcriber可以视为token tree的扩充，你仍然可以在matcher和transcriber中使用普通的token tree，它们会被literally进行比较/替换
  • matcher的最外层括号不必匹配，但内层括号必须匹配，例如matcher为(())，则可以匹配macro!{()}，但不能匹配macro!{[]}
• macro展开时，即使某条规则匹配，也可能展开失败，例如由于展开后内部还含有宏要递归展开，但递归展开失败，此时不会再尝试下一条规则

---

在matcher中可以使用形如$id: fragspec的metavariable matcher，在transcriber中可以使用matcher中出现过的$id:

• $id: item: 可以capture一个item，例如function、struct、module等
• $id: block: 可以capture一个block
• $id: stmt: 可以capture一个statement（不包括结尾的;）
• $id: pat: 可以capture一个pattern
• $id: expr: 可以capture一个expression
• $id: ty: 可以capture一个type
• $id: ident: 可以capture一个identifier，注意这是一个TOKEN
• $id: path: 可以capture一个path，更准确地说是「TypePath」，即使用::A::B<T>而非::A::B::<T>形式来指定type parameter的path
• $id: tt: 可以capture一棵TOKEN tree
• $id: meta: 可以capture一个attribute的meta item
• $id: lifetime: 可以capture一个lifetime TOKEN
• $id: vis: 可以capture一个visibility qualifier（e.g. pub(super)），可以为空
• $id: literal: 可以capture一个literal（数字或字符串）
• 宏展开时，metavariable会被替换为opaque的AST节点，transcriber中嵌套的宏将无法观察到AST节点内部的结构

在matcher中我们还可以指定repetition：

• $(...)?: 表示match零次或一次
• $(...),*, $(...);+: 分别表示match任意次和match至少一次，括号后跟的,/;表示group以,/;分隔
  • 事实上seperator可以是任意token，不限于,和;，只要不是()[]{}或$即可
• 在transcriber中可以使用同样的语法，将matcher中捕获的repetition展开相应的次数
  • 此时会利用transcriber中用到的metavariable来确定使用的matcher中的repetition
  • 若有多个对应的repetition，则它们的重复次数必须相同，否则匹配失败
  • 例如( $( $i:ident ),* ; $( $j:ident ),* ) => ( $( ($i,$j) ),* )，输入(a, b, c; d, e)会匹配失败

---

*Macros by example*有两种scope，textual scope和path scope：

• 若通过macro引用，则首先在textual scope中查找，然后在path scope中查找
• 若通过A::B::macro引用，则直接在path scope中查找

textual scope的规则如下：

• macro在定义后，方可使用，和let声明类似
• macro定义允许shadowing，这也和let声明类似
• macro定义在item（例如module，甚至function）中时，只在item的scope中有效
• #[macro_use]可以令module中定义的macro，在离开module的scope后还继续保持有效

path scope的规则如下：

• #[macro_export]可以令macro具备path scope，也就是能够用path访问该macro，并且其他crate也能导入该macro
  • 此时不受textual scope的限制，可以在macro定义之前使用macro，就和函数定义类似

通过#[macro_export]导出的宏，除了通过import语句导入外，还可以通过#[macro_use]导入，但并不常用：

#[macro_use(macro0, macro1)] // or #[macro_use] to import all macros
extern crate has_macro;

---

Rust的macro是hygienic的，在transcriber中引入的identifier和来自invocation site的identifier不会冲突。例如，以下代码无法通过编译，因为transcriber中的a和$e展开得到的a不是同一个a：

macro_rules! using_a {
    ($e:expr) => {
        {
            let a = 42;
            $e
        }
    }
}

let four = using_a!(a / 10);

若在transcriber中未重新定义一个identifier，就直接使用，那么会默认该identifier来自invocation site：

• 使用$crate::A::B::id可以强制使用macro所在的crate中的identifier

Procedural Macros

Procedural macro是另一种macro，它定义了一个函数，在编译期会直接执行该函数进行宏展开。Procedural macro必须在proc-macro类型的crate中定义，在Cargo.toml中可以这样定义proc-macrocrate：

[lib]
proc-macro = true

Procedural macro不是hygienic的，它和C Macro更类似，但更灵活。目前共有三种procedure macro，分别是：

• Function-like macro: custom!()
• Derive macro: #[derive(CustomDerive)]
• Attribute macro: #[CustomAttribute]

先来看function-like macro，它通过一个#[proc_macro]属性的public函数定义：

• 函数的类型必须是fn (TokenStream) -> TokenStream，macro名为函数名
• TokenStream类型来自proc_macrocrate，表示一个token tree的stream
• 输入是custom!($args)中的$args，输出则会替换整个宏

再来看derive macro，它通过一个#[proc_macro_derive(CustomDerive)]属性的public函数定义：

• 函数的类型必须是fn (TokenStream) -> TokenStream，macro名来自属性，与函数名无关
• 输入是#[derive(CustomDerive)]后紧跟的item，输出必须是一系列的item，输出会被添加到原item所在的module或block，而原item不会被修改或删除
• #[proc_macro_derive(CustomDerive, attributes(helper0, helper1, ..., helperN))]
  • 定义derive macro时，可以额外指定若干helper attributes，它们本身并没有任何含义，也不会有任何效果
  • 这些attributes可以在输入的item中使用，然后可以被derive macro识别，从而被derive macro赋予含义
  • 事实上，它们也可以被任何其他macro识别，而赋予含义

最后来看attribute macro，它通过一个#[proc_macro_attribute]属性的public函数定义：

• 函数的类型必须是fn (TokenStream, TokenStream) -> TokenStream，macro名为函数名
• 第一个参数是attribute，若attribute后面没有跟参数则第一个参数为空
• 第二个参数是#[CustomAttribute]后紧跟的item
• 输出是任意数量的item，输出会替换原item

External Block & External Function

Rust中external block用于提供FFI（Foreign Function Interface），位于external block中的函数代表来自外部的Non-Rust代码，没有function body。这些函数的参数不能使用pattern，只能声明为x: T或_: T。

首先，声明external block时需要指定ABI，如extern "stdcall" {...}，若不指定则默认为C ABI即extern "C"。

有三个ABI是跨平台的：

• extern "Rust": 即Rust自身的ABI
• extern "C": 即系统的C编译器提供的ABI
• extern "system": 通常为C ABI，在Win32上为"stdcall"（即用于链接Win API的ABI）

此外还有以下platform-specific的ABI：

• extern "cdecl": x86-32的默认C ABI
• extern "stdcall": x86-32的Win32 ABI
• extern "win64": x86-64的Win ABI
• extern "sysv64": x86-64的Non-Win ABI
• extern "aapcs": ARM的默认ABI
• extern "fastcall": 对应于MSVC的__fastcall和GCC/Clang的__attribute__((fastcall))
• extern "vectorcall": 对应于MSVC的__vectorcall和GCC/Clang的__attribute__((vectorcall))

其次，external block中只能定义两种item，即static item和function item：

• static item代表来自外部的全局变量，没有initalizer
  • 无论有没有mut修饰符，访问external static item都是unsafe的
• function item代表来自外部的函数，没有body
  • 所有external function都默认被声明为unsafe的
  • external function支持variadic parameter，如extern { fn foo(x: i32, ...); }
    • 相应地，由external function经coercion得到的函数指针的类型可以是unsafe extern fn(i32, ...)
  • 但只有"C"或"cdecl"ABI支持variadic parameter

最后，我们可以通过attribute控制link行为：

• #[link_name = "actual_symbol_name"]: 可以给external函数加上该属性，这可以令Rust中的函数名可以和外部库中的函数名不同
• #[link(name = "CoreFoundation", kind = "framework")]: 可以给external block加上link属性，表示要链接到哪个库
  • kind可以取dylib, static或framework，其中framework是指macOS framework，仅限macOS平台
  • kind不填时默认为dylib

Nullable Pointer Optimization: 在Rust中有些类型是non-null的，例如&T, &mut T, Box<T>以及函数指针。若一个enum只有两个variant，其中一个是empty variant，另一个是上述non-null type，则Rust会进行所谓的「nullable pointer optimization」，使得enum不需要存储discriminant。这样的enum（例如Option<T>）可以用来包装从外部的C语言库中返回的nullable的值。

---

反之，如果在external block外定义的函数，声明为extern，则表示该函数是export给外部使用：

• 例如extern "stdcall" fn new_i32_stdcall() -> i32 { 0 }
• 由此经coercion得到的函数指针类型为extern "stdcall" fn() -> i32
• 使用#[no_mangle]属性让extern函数以其名称export，而不是以mangled name进行export

Exception Safety

Rust中的panic!实际上已经成了一种Exception机制：

• 首先，panic只会结束当前线程，而不是结束整个程序，因此在该线程invariants被破坏的数据会感染其他线程
• 其次，可以使用std::panic::catch_unwind(|| { panic!("oh panic!"); })来catch当前正在unwinding的panic
• 最后，可以用std::panic::resume_unwind(Box<dyn Any + Send>) -> !进行rethrow，重新引发panic

于是我们有必要引入Exception Safety的概念，但相比C++、Java、C#等严重依赖Exception的语言，程序员实际上不需要关心太多：

• Safe的代码最好能达到C++的strong exception safety级别，Rust称之为maximal exception safety
  • 即面对panic能保持数据结构的invariants不被破坏
  • 但达不到也行，因为safe代码面对exception至少能保证memory safety，也就是C++的basic exception safety
• Unsafe的代码（unsafe块和unsafe函数中的代码）必须达到basic exception safety级别，Rust称之为minimal exception safety
  • unsafe代码面对exception有违反memory safety的风险，而Rust的目标是保证memory safety，故要求unsafe的代码必须实现basic exception safety
  • 也就是说，对于一般程序员而言，只有写unsafe代码时需要注意exception safety，心智负担较低

Rust引入了两个Auto TraitRefUnwindSafe和UnwindSafe：

• T: RefUnwindSafe表示&T是unwind safe的
• T: UnwindSafe表示T是unwind safe的
  • 若T: RefUnwindSafe则&T: UnwindSafe
  • 但&mut T被显式声明为!UnwindSafe
• 实际上UnwindSafe在整个标准库中的使用只有一处，就是catch_unwind(f: F) -> Result<R>中要求闭包F: UnwindSafe
  • 也就是闭包捕获的变量，必须在panic后保证其invariant不被破坏
• 而RefUnwindSafe则是用来判断如Rc<T>等类型是否是UnwindSafe的
  • 当T: RefUnwindSafe时，Rc<T>、Arc<T>是UnwindSafe的
  • UnsafeCell<T>被显式声明为!RefUnwindSafe

这里的unwind safety并不是类型的本质性质，而是程序员提供给编译器的一个hint：

• 我们可以通过std::panic::AssertUnwindSafe<T>把不是UnwindSafe的T包裹起来，然后变成UnwindSafe的
  • 因此，程序员可以自由决定是否提供UnwindSafe这个hint
  • 它只是用来提示Rust，类型T在被catch_unwind的闭包捕获后，即使发生panic也仍能使用
• 默认情况下，标准库认为以下类型是UnwindSafe的
  • &T, *const T, *mut T, NonNull<T>, Rc<T>, Arc<T>, Mutex<T>, RwLock<T>，其中T: RefUnwindSafe
    • 因为T不含UnsafeCell，上述类型必然是只读的，一定不会破坏T的invariants
  • 所有基本类型，以及不含有指针或仅含有上述UnwindSafe的指针的聚合类型
    • 它们必然按照move或copy语义被捕获，又没有指向共享的内存，这样即使在catch_unwind的闭包内产生了broken invariants，也不会被catch_unwind外的代码观察到
• 对于在闭包中进行的修改，可能被catch_unwind外的代码观察的情形，就需要程序员在确保了exception safety的情况下，手动提供UnwindSafe，来告知编译器这样做是安全的
  • 若没有实现exception safety却将类型声明为了UnwindSafe，这就是一个逻辑上的bug，尽管我们不认为其违反了Rust的safety保证（即memory safety）

---

综上所述：

• 对于unsafe代码，需要仔细考虑exception safety的问题，以保证memory safety
  • unsafe关键字这里起了提示作用
• 使用catch_unwind进行catch时，若有可能破坏数据结构的invariants，即达不到strong exception safety，编译器会提示你的类型没有实现UnwindSafe
  • UnwindSafe这里起了提示作用
• 没有使用catch_unwind时，则不会有相应提示，从而代码有可能没有实现strong exception safety，导致panic时数据结构的invariants被破坏
  • 但若要观察到broken invariants，需从另一个线程访问该数据结构
  • 这就必须用到Mutex<T>或RwLock<T>，除非用户不使用标准库
  • Mutex和RwLock提供了poison语义，如果在critical section发生panic，会使Mutex/RwLock被poison
  • 这样在另一个线程试图访问T时，poison状态就提示该数据结构的invariants可能已经被破坏，若要仍要访问该数据结构，请程序员自己确保strong exception safety

对于每种情形，Rust都提供了一定的提示，帮助程序员更好地意识到exception safety问题，但总的来说对exception safety的支持仍旧是best-effort的。对于以下情形，Rust不能很好地起到提示程序员注意exception safety问题的作用：

• 在destructor（drop函数）中总是有可能观察到broken invariants，程序员需要根据实际情况确定这是否会引起问题，并实施相应的对策
  • 这里Rust不会提供任何提示，程序员必须认识到drop函数是特殊的，需要仔细审查其代码
• 在使用catch_unwind进行catch时，除了通过闭包的捕获变量，还可以通过TLS (Thread Local Storage)在catch_unwind内外共享数据
  • 由于TLS不像static变量一样要求实现Sync，故其可以存放RefCell<T>
  • 通过RefCell<T>修改T时若发生panic，则在catch_unwind外可能观察到invariants被破坏的T，从而违反strong exception safety
  • 这里Rust同样不会提供任何提示，程序员必须认识到使用TLS是危险的，需要仔细考虑exception safety问题

Type Layout

大部分类型的layout都是直观的：

• 对于bool、char、整数和浮点类型，其size是明确的，但alignment是platform-specific的
  • 其中usize、isize的size定义为足够容纳任何内存地址
• 对于引用和裸指针，指向非DST类型的，size和alignment与usize相同，指向DST类型的，size为usize的两倍，alignment大于等于usize
  • Rust仍保留改变指向DST类型的指针的size的可能性，即将来可能从fat pointer改为vtable的实现方式
• 对于array[T; n]、slice[T]（包括str，视为[u8]），其第i个元素的offset位于i * sizeof(T)，整体size为n * sizeof(T)，alignment与T相同
• 对于trait objectdyn Trait，layout与其underlying的类型T: Trait相同
• 对于tuple和closure，没有任何size和alignment的guarantee

对于struct、enum和union，则有representation的说法，representation不同则layout不同：

• Default representation: 不提供任何guarantee，也称为Rust representation
• C representation: 通过#[repr(C)]属性指定，用于与C交互，或需要手动控制layout的场合（例如网络包）
• Primitive representation: 包括#[repr(u8)], #[repr(u16)]等，所有整数类型都可以填入#[repr(..)]中
  • 只适用于enum类型，并且只适用于C-like enum（即所有variant都是empty variant的enum），否则其layout是unspecified的
  • 对于C-like enum，其size和alignment都和#[repr(..)]中填入的整数类型相同
• Trasparent representation: 通过#[repr(transparent)]属性指定
  • 只能用于仅含一个非零size的field和零到若干size为零的field的struct
  • 表示其layout与唯一的非零size field相同

现在来详细解释C representation：

• 对于struct，alignment取所有field中最大的alignment，field的offset以及总的size按如下算法确定
  1. 初始状态，current_offset = 0
  2. 每次按声明顺序取出下一个field，若current_offset不满足其alignment，则插入若干padding bytes
  3. 该field的offset就是current_offset + padding_size
  4. 在取出下一个field前，令current_offset += padding_size + field.size，然后回到第2步
  5. 上述循环结束后，若current_offset不满足struct整体的alignment，则再插入若干padding bytes，最后整个struct的size为current_offset + padding_size
• 对于enum，C representation只适用于C-like enum，否则其layout是unspecified的
  • 对于C-like enum，其size和alignment都和target platform上Cenum默认的size和alignment相同
  • 由于C中enum的representation是implementation defined的，Rust不保证#[repr(C)] enum一定与C兼容
• 对于union，size和alignment将和一个等价的Cunion相同
  • alignment取所有field中最大的alignment
  • size取所有field中最大的size，再向上round到整个union的alignment

此外，对于struct和union，还可以指定align(x)和packed(x)：

• 其中x必须取2的幂，packed相当于packed(1)
• 适用于default和C representation，如#[repr(packed)], #[repr(C, align(8))]
• align(x)用于提升alignment，而packed(x)用于降低alignment
  • align(x)中x若小于被修饰的类型的alignment，则会被忽略
  • packed(x)中x若大于被修饰的类型的alignment，则会被忽略
  • 两者不能修饰同一个类型
• packed类型不能含有被align修饰的field
• #[repr(packed)]与GCC的__attribute__ ((packed))不同
  • 前者只去除了struct/union末尾的padding，每个field的alignment还保持原样不变
  • 后者相当于递归地令所有field都具备了packed属性，消除了所有padding

实际上，还可以对enum指定align(x)，增加其alignment，但不能对其指定packed(x)。

Unsafe Rust

Definition of Unsafe

先来看涉及unsafe的两个特性：

• 裸指针: *const T表示只读指针，*mut T表示可读写的指针，裸指针都没有lifetime，从裸指针得到的引用都具备unbounded lifetime
  • 解引用裸指针是unsafe操作，必须在unsafe块中进行
  • 但对裸指针进行算数操作是safe的，因为裸指针到整数之间的coercion是safe的
  • 裸指针不受borrow checker的限制，不遵循borrow规则
  • 裸指针可以是null，也可以是dangling pointer
• Union: union Union {...}，union的声明方式和struct完全相同，除了struct关键字换成了union，union也可以是generic的
  • 读取union的field是unsafe操作，必须在unsafe块中进行
  • 但初始化union以及为union的field赋值是safe的
  • 一旦borrow了union的一个field，就视为borrow了其所有field

unsafe关键词有三种用途：

• unsafe {...}: unsafe block，在其中可以调用unsafe function，或进行unsafe操作
• unsafe fn: unsafe function，在其中可以调用unsafe function，或进行unsafe操作
• unsafe trait: unsafe trait，表示实现trait是unsafe的，对应的impl必须是unsafe impl，例如Sync和Send就是unsafe trait

所谓unsafe操作包括如下内容：

• 解引用裸指针
• 读取或写入mutable static变量或external static变量
• 读取union的field
• 调用unsafe function，包括unsafe external function
• 实现unsafe trait

Semantics of Unsafe

首先，我们要明确的是Rust发明unsafe特性的目的是什么：

• Rust作为一个system language，必须具备操作raw pointer的能力，一旦引入raw pointer就必然引入UB (Undefined Behavior)
• Rust又希望能够保证memory safety（包括data race free也算作memory safety）
• 因此通过unsafe将代码分为了Safe Rust和Unsafe Rust，在Unsafe Rust中允许使用raw pointer等功能，而在Safe Rust中则可以假定memory safety总是得到保证
  • Safe Rust依赖于Unsafe Rust提供的guarantee，即保证Safe Rust的memory safety
  • 一段Unsafe Rust代码如果不能保证memory safety，我们就说它是unsound的

总而言之，unsafe的含义是双重的：

• 第一重是在Rust语言中的定义，即在unsafe block和function中，可以使用4种unsafe操作，并且实现unsafe trait需要使用unsafe关键字
• 第二重则是对程序员的要求，即要求程序员保证使用了unsafe的代码的memory safety，确保程序是sound的
  • 而要实现memory safety，就不能发生UB，这样就排除了C/C++中臭名昭著的UB
  • 实际上Rust语言认为发生UB和程序执行出错是一回事，尽管程序不一定立即crash，但这应当认为是用户代码中的一个bug

---

需要注意的是，unsafe块的memory safety可能依赖于它外部的safe代码：

• 一个函数可能依赖于其参数满足某些invariants，才能确保其中的unsafe操作是memory safe的
  • 此时就需要将整个函数标记为unsafe函数，并在函数的文档中详细说明调用者应保证何种invariant
  • 而调用者也会被此unsafe感染，必须使用unsafe块才能调用该函数
• 一个generic函数可能依赖于其使用的trait满足某些invariants，才能确保其中的unsafe操作
  • 此时就需要将该trait标记为unsafe trait，并在trait的文档中详细说明实现时应保证何种invariant
  • Send和Sync就是unsafe trait，因为若不满足其性质却将其实现，可能会导致data race，破坏Safe Rust的memory safety保证

甚至没有直接使用unsafe代码的safe函数，也可能间接破坏memory safety。假设Vec的定义如下：

pub struct Vec<T> {
    ptr: *mut T,
    cap: usize,
    len: usize,
}

若我们为其增加一个函数evil，则调用evil会破坏memory safety，因为有可能访问到尚未初始化的内存，但evil中并不包含unsafe代码：

impl Vec<T> {
    pub fn evil(&mut self) {
        self.len += 2;
    }
}

从这个例子可以看出，凡是使用了unsafe代码的，为了保证memory safety，都必须维护一定的invariant：

• 若invariant可以local地保证，则unsafe感染的范围仅限于unsafe块内部
• 若invariant依赖于函数参数，则unsafe会感染函数的所有调用者
• 若invariant依赖于trait实现，则unsafe会感染trait的所有实现者
• 若invariant依赖于一些可变的状态（即上文的len、cap），则unsafe会感染这些状态的所有访问者
  • 前两种情形下，我们依赖于将函数或trait标记成unsafe，来感染所有调用者或实现者
  • 而这种情形下，我们无法将这些状态（可能是struct field或仅仅是一些变量）标记为unsafe
  • 这里的解决方案是限制这些状态的visible scope，例如len、cap是private field，因此unsafe至多只能感染当前module，只要当前module提供的safe API保证不会违反memory safety，unsafe的影响范围就不会超出当前module

Part III. The Essence of Rust

Reference is Borrow

在Rust中，取引用操作的正式名称为borrow，&操作符正式名称为shared borrow，而&mut操作符正式名称是mutable borrow。相应地，&T可以称为shared reference或shared borrow，而&mut T可以称为mutable reference或mutable borrow。

从本质上讲，borrow是对ownership机制的一种扩充：

• 原本一个value只能被一个变量持有（own）
  • let a = expr;, let mut a = expr;
• 现在可以通过borrow，使得reference暂时持有value的ownership
  • let r = &a;, let ref r = a;
  • let r = &mut a;, let ref mut r = a;

borrow的基本原则是明确的：

• reference不能比被引用者延续更久：这是为了解决Dangling Pointer问题，避免bug
• mutable reference不能有aliasing：这是为了解决Pointer Aliasing问题，方便编译器优化
  • 这还有一个好处，就是并发编程时不能使用普通的mutable reference，强迫用户使用标准库提供的同步原语，避免低级错误导致的Data Race

---

shared reference和mutable reference的区别，实际上是双重的。

第一重区别在于mutability，即是否允许修改被引用者：

• shared reference是immutable的，因此又可以称为immutable reference
• mutable reference是mutable的

第二重区别在于uniqueness（或者说exclusiveness）：

• shared reference是shared的，对同一个place允许存在多个shared reference
• mutable reference是unique的，对同一个place只允许存在一个mutable reference，因此又可以称为unique reference
  • 更准确地说，是对该place的引用被该mutable reference独占（exclusive borrow），mutable reference不能与shared reference共享对该place的引用
• 这里的place不仅可以是对象，也可以是对象的一部分，只要是一种左值即可，这样就允许我们对一个struct的不同field分别取mutable reference

shared reference实际上不一定总是immutable的，它有时可以具备interior mutability，因此shared reference和mutable reference的本质区别实际上是uniqueness。

实际上，在closure的capture中，还存在一种特殊的capture mode，称为unique immutable borrow，仅在closure中可用，它就是一种在mutability层面上是immutable的，而在unqieuness层面上是unique的引用。编译器会按照immutable borrow, unique immutable borrow, mutable borrow, move从高到低的优先级自动为capture选取适当的模式。

这样，我们可以将几种borrow总结如下：

	Immutable	Mutable
Shared	Shared Borrow	Interiorly Mutable Shared Borrow
Unique	Unique Immutable Borrow	Mutable Borrow

---

shared borrow和unique immutable borrow的区别在于：

• shared borrow的immutability具有传递性
• unique immutable borrow的immutability不具有传递性
• 所谓传递性，就是指被引用对象中的引用，是否都被视为immutable

例如let mut x = 42; let y = &mut x; let a = &y; **a = 10;是无法编译通过的，即使按通常的逻辑*a是mutable reference，因此应该可以修改**a，这体现了shared reference的传递性。

shared borrow的immutability还能感染其引用者，例如let mut x = 42; let y = &mut x; let z = &y; let a = &mut z; ***a = 10;是无法编译通过的，因为从a到***a即x的过程中，要经过shared borrowz。

反之，考察如下代码，closure会按照unique immutable borrow进行捕获：

let mut a = false;
let x = &mut a;
{
    let mut c = || { *x = true; };
    // let y = &x;  this line will not compile, borrow of x must be unique
    c();
}
let z = &x;

• 由于x是immutable的，不能对x按mutable引用捕获
• 若对x按immutable引用捕获，则无法执行*x = true（传递性）
• 但对x按unique immutable borrow进行捕获，就可以执行*x = true（非传递性）

实际上这体现了mutable reference不能有aliasing的规则：

• 若可以通过shared reference引用到mutable reference，然后间接地修改mutable reference引用的对象，则等同于shared reference成了mutable reference的alias
• 因此shared reference的immutability必须有传递性
• 而反之，unique immutable borrow以及immutable binding（let a = expr;）不具有传递性，因为它们是独占的，不会产生alias

注意上面代码中的let mut c = || { *x = true; };，含有unique immutable borrow的closure，相当于含有mutable borrow，在调用时必须使用&mut self。这是因为&self受immutable reference的传递性限制，无法通过unique immutable borrow进行修改。

---

为了方便使用，Rust在以下情形会自动进行borrow：

• Method调用: a.f()可以被自动处理为(&a).f()（若a: Self而f: fn (&Self) -> T）
• Closure调用: c()可以被自动处理为(&a)()（若c只按immutable引用捕获）
• 数组下标操作符[]: 可重载，LHS参数为引用，a[b]可以被自动处理为*::std::ops::Index::index(&a, b)
• 比较操作符==,!=,<,<=,>,>=: 可重载，参数为引用，a == b可以被自动处理为::std::cmp::PartialEq::eq(&a, &b)
• 赋值操作符+=,-=,*=,/=,%=,&=,|=,^=,<<=,>>=: 可重载，LHS参数为mutable引用，a += b可以被自动处理为::std::ops::AddAssign::add_assign(&a, b)
• 解引用操作符*: 可重载，参数为引用，*x可以被自动处理为*std::ops::Deref::deref(&x)

此外，Rust还会自动进行dereference，基本上所有场合发生Type不一致时，Rust都会尝试解引用以使Type匹配。

Reborrow and Borrow Stack

考虑函数调用f(x)，其中f: fn (&mut i32) -> i32, x: &mut i32，按照通常的逻辑，x将会被move到f的作用域中，最后在f返回时被丢弃，这样一来将无法第二次调用f(x)。然而实际上，可以无限次调用f(x)，而仍保持x有效。

这是由于编译器会自动将f(x)转变为f(&mut *x)，而&mut *x是所谓的reborrow操作，将会对mutable referencex再次borrow，获得一个新的mutable reference，而原本的x暂时被shadow，处于inactive状态，直到f返回时，新的mutable reference被销毁，x重新回到active状态。

对于generic函数，则不一定会进行reborrow操作，设v: &mut i32：

• fn f<T>(x: &mut T): f(v)会自动reborrow，变成f(&mut *v)
• fn f<T>(x: T): f(v)不会自动reborrow，v会被move到f中
• fn f<T>(x: T, y: T): 对于f(v1, v2)，只有v1会被move到f中，v2会被自动reborrow，即最后变成f(v1, &mut *v2)

所谓的reborrow实际上本质上仍是borrow，也就是说Rust并没有对&*x或&mut *x引入特殊的语义。试考虑&mut *x，它可以理解为先获得了lvalue*x，然后对这个lvalue进行了borrow。之所以称其为reborrow，是因为该lvalue所在的place实际上已经被xborrow过了，我们又「重新borrow」了一次，reborrow的特殊之处就在于Rust允许我们borrow一个已经被borrow过的lvalue。

更进一步，形如&(*ref).x的borrow也是允许的，也可以视为一种reborrow，即我们可以单独reborrow一个已经被borrow过的lvalue的一部分。

实际上reborrow的行为也是有其适用范围的：

• 被shared borrow的lvalue，不能被reborrow为mutable reference，只能被reborrow为shared reference
• 被unique immutable borrow的lvalue，不能被reborrow为mutable reference，但能被reborrow为shared reference
• 被mutable borrow的lvalue，可以被reborrow为shared reference或mutable reference

---

需要注意的是，当我们使用&mut *xreborrow了x后，我们就将无法使用x，直到该reborrow expire为止，例如下列代码就是错误的：

let a = &mut 3;
let b = &mut *a;    // `a` is reborrowed
*a = 4;             // `a` is shadowed, ERROR
*b = 5;             // reborrow expired

应该说，引入reborrow后，每个memory location都会有一个borrow stack。将borrow stack定义在memory location上而不是place上，是因为memory location没有进一步的结构，可以简化讨论，而place可以有子place，其不同的子place可以被分别reborrow，于是构不成一个stack。

borrow stack的规则很简单：

• 对最初的变量的borrow，位于栈底
• 此后的每次reborrow，都会将该reborrow放入栈顶
• reborrow得到的mutable reference，会将栈中更早的mutable reference屏蔽，使其不能被访问或reborrow
• reborrow得到的shared reference，会使栈中更早的mutable reference退化为shared reference，即只能被读取或被reborrow为shared reference
• 栈顶的reborrow一旦expire，其引起的屏蔽效果即会解除

这里忽略了具有interior mutability的shared reference以及raw pointer，真正用于定义Rust语义的borrow stack模型要复杂得多，因为需要考虑unsafe特性与mutable/shared reference的语义的交互。

注意有时实际上可能发生reborrow产生的新reference尚且存活，旧的reference却已经被销毁的情况：

• 例如let new; { let old = &mut x; new = &*old; }; use(new);，即新reference的作用域比旧reference更大
• 又如let mut parent = &mut p; let child = &parent.x; let parent = &mut q;，即旧reference被覆盖，从而不可达

此时我们并不会立即将旧的reference从borrow stack中移除，而是会等待栈顶的reborrow先expire，再将旧的borrow移除。

Lifetime Part I. What is Lifetime

上面已经介绍了Rust中关于borrow也就是reference的规则，Rust语言的最大特色就在于该规则不是在运行时enforce而是在编译时enforce，Rust编译器中负责检查borrow规则的部分称为borrow checker。显然，由于静态分析的固有缺陷（停机问题），borrow check必然是保守的，会拒绝一部分（根据borrow规则）正确的程序，事实上在1.31版本引入NLL (Non-Lexical Lifetime)之前一些显然正确的程序也会被编译器拒绝。

为了解决编译期borrow check的问题，Rust为其类型系统引入了lifetime的概念，引用类型&T、&mut T和trait object类型dyn Trait实际上都附带有lifetime。我们知道，type variable一般用大写字母表示，如T, U。在Rust代码中，我们用'加上小写字母表示lifetime variable，例如'a, 'foo，引用类型和trait object类型完整地写出应该是：

• 引用：&'a T, &'a mut T
• trait object： dyn Trait + 'a，这里的'a实际上也是用于表示trait object内部的引用的lifetime，根源上还是引用的lifetime
• 可以写'_表示lifetime留待编译器推导（如&'_ i32），就像_表示类型待编译器推导（如(_, i32)）

我们知道type variable的实例是i32、(bool, [u32; 4])等concrete type，那么lifetime variable的实例是什么呢。Rust引入lifetime的概念，是试图表达引用有效的时间范围，即类型为&'a T的引用，在'a这段时间内有效，也就是允许解引用（不是dangling pointer）。显然，这是一个运行时才有的概念，同一个程序运行多次，引用的lifetime会随着code path的不同而或长或短。为了静态地建模lifetime，Rust中lifetime的实例实际上是代码的范围，它应当包含引用当前可能有效的所有code point。

为了更好地理解这一点，我们来看一个例子：

let a = &mut 0i32;  // --+ lifetime of `a`
let b = &mut *a;    //   |
...                 //   |
last_use(a); // <--------+

这里a的lifetime从其初始化延续到最后一次使用，在整个过程中，访问a都应当是有效的。中间a可以被reborrow，此时仍将a视为是有效的，因为当reborrow expire后我们又可以继续使用a。

假设a和b的类型分别是&'a mut i32和&'b mut i32，即它们的lifetime分别是'a和'b。由于reborrowb先于被reborrow的aexpire，a的lifetime应该大于b，我们将这种关系称为'a outlive 'b，记作'a : 'b。

基于outlive关系，还可以得到一条subtyping rule：

• 若'a : 'b则&'a T <: &'b T、&'a mut T <: &'b mut T

这条规则可以这样理解，考虑x = y，若x的lifetime为'b，y的lifetime为'a，则应当有'a : 'b即y的有效期比x更长，否则若y已无效而从y派生的x仍有效，就会导致use-after-free的bug。由此可见，只有lifetime更长的引用可以赋值给lifetime更短的引用，反之则不行，这就说明了这条subtyping rule的合理性。

我们再来考察let b = &mut *a;这一行，RHS尽管是一个rvalue但它仍然应该有一个类型，实际上在Rust中任何表达式都应该被赋予一个类型。不妨将RHS的类型记作&'r mut i32，它需要满足'r : 'b（subtyping rule）以及'a : 'r（reborrow总是先expire）。在类型推导时，'r可以取任何满足'a : 'r : 'b的值，它不一定要和'a或'b相等，也就是说borrow操作会引入一个独立的lifetime'r。某种程度上，我们可以将&lvalue/&mut lvalue看作是&'r lvalue/&'r mut lvalue的缩写，在创建一个新的引用的同时，也就引入了一个新的lifetime，这个lifetime就表示该引用可以有效使用的范围。

---

下面再看这个例子：

let new;
{
    let old = &mut x;   // --+ lifetime of `old`
    new = &*old;        //   |
}                       //   |
use(new);               //   |
// <-------------------------+

尽管old在use(new);之前已经离开了作用域，可以认为被销毁了，但其lifetime实际上还是会延续到use(new);之后，以保证old的lifetime要大于new的lifetime，这是为了保证「borrow stack」的先进后出性质。

从这个例子我们可以看出，Rust类型系统中的「lifetime」只是一种近似。一个引用的「lifetime」必须包含一切该引用确实有效的code point，但也可以包含该引用实际上已经无效的code point。Rust编译器在进行borrow check时，只会根据引用类型中的lifetime信息来判断该引用是否有效，因此若lifetime比实际的要大，则编译器可能会拒绝一些按照borrow规则实际上正确的程序，但至少绝不会通过违反borrow规则的程序。

对于编译器拒绝实际上正确的程序，一个典型的例子如下，这个例子常被用于说明Rust 1.30版本及以前使用的Lexical Scope Lifetime的不足：

fn foo() {
    let mut data = vec![1, 2, 3];
    let slice = &mut data[..];  // <-+ lifetime of `slice`
    capitalize(slice);          //   |
    data.push('d'); // ERROR!   //   |
    data.push('e'); // ERROR!   //   |
    data.push('f'); // ERROR!   //   |
} // <-------------------------------+

在1.30版本及以前，Rust中的lifetime是基于lexical scope的，lifetime必须一直延续到scope的末尾，例如上述代码中的slice的lifetime一直延续到了函数的末尾。注意到data.push()调用时也自动取了data的mutable引用，这个引用的lifetime与slice的lifetime重叠，于是编译器认为可能违反mutable引用的uniqueness性质，拒绝通过编译。

实际上我们知道这个程序显然是正确的，只是由于lifetime取得太大导致编译器误以为程序会违反borrow规则。只需令slice的lifeitme在capitalize(slice);这一行结束，就能避免borrow checker错误地拒绝该程序。为了解决这类问题，从1.31版本起引入了Non-Lexical Lifetime (NLL)，支持非lexical scope的lifetime，使编译器可以接受更多正确的程序。当然，NLL也仍有缺陷，有时推导出的lifetime还是会太大，导致拒绝正确的程序，因此Rust团队还在不断改进lifetime和borrow check的机制。

---

值得指出的是，无论是NLL还是更进一步的改进，都仍局限于静态分析，这种编译期的分析必然会拒绝一些运行时不违反borrow规则的代码，例如以下代码：

fn f(condition: bool, outer: &i32) {
    let mut _a = 0i32;

    let parent = &mut _a;
    let y;
    {
        let x;
        if condition {
            x = &*parent;
            y = outer;
        } else {
            y = &*parent;           // `parent` is borrowed here
        }
    }
    if condition { *parent = 10 }   // ERROR! `parent` is already borrowed
    println!("{}", y);              // borrow used here
}

我们知道*parent = 10这一句若得到执行，则一定是取condition = true，那么此时parent的reborrowx已经expire，而y不是parent的reborrow，因此该赋值语句是合法的。但目前的NLL无法分析出函数中两个if语句的联系，它会认为parent已经在y = &*parent一句被reborrow（因为编译器认为&'y *parent的lifetime'y延续到了println!("{}", y)这一行），因此不能进行赋值。

这个例子是trival的，可以用一个简单的heuristic来处理，但一般来说这类问题是无法在编译期彻底解决的，例如我可以在一个循环中检查数学定理，并通过某种方式将其和lifetime联系起来，编译器不可能知道数学定理是必然正确的，它就不可能作出正确的判断。

Lifetime Part II. Lifetime Parameter

在Rust中，只有一种concrete lifetime可以通过代码指定，即'static，表示lifetime贯穿整个程序执行过程，即全局变量。实际上Rust中有全局变量的概念，称为static变量，它们都具有'staticlifetime：

• static x: T = expr;: 与constant声明类似，必须写明类型，所有对x的引用的lifetime都将是static的
  • static变量必须是Sync的，这样才能保证其能安全地被多个线程共享
• static mut x: T = expr;: static变量可以是mutable的
  • 对mutable static变量的访问必须在unsafe块中进行，因为有可能引入race condition
  • 即使是读取也必须在unsafe块中进行，以避免data race，因此mutable static变量不需要实现Sync

此外，string literal默认拥有'static lifetime，例如let a = "asdf";实际上相当于let a: &'static str = "asdf";。

---

对于type，我们可以有无数的concrete type，但对于lifetime，我们不能指定除'static外的concrete lifetime。因为这一重要区别，Rust专门提供了在generic中引入bounded lifetime variable的方法，即<'a, T>这样的写法，并将如此引入的lifetime variable称为lifetime parameter。

应当认识到lifetime本质上仅仅是type的组成部分，理论上不提供单独指定lifetime variable的方式也是可以的，即lifetime蕴含在type variable T中。通过提供lifetime parameter机制，实际上是将lifetime抬到了和type平起平坐的地位，可以视为两种kind了（即LT和*，例如Struct<'a>的kind为LT -> *）

当函数有引用或trait object作为参数或返回值时，需要提供lifetime parameter（除非lifetime显式指定为'static）：

• fn f<'a, 'b>(x: &'a i32, y: &'b i32): 可以引入任意多个lifetime parameter
• fn f<'a>(x: &'a i32, y: &'a i32) -> &'a i32: 两个引用使用同一个lifetime parameter，就构成了对类型推导的一种约束
  • 因为函数实际调用时我们通常无法指定'a，'a是由类型推导得来的
• 函数体中可以使用let r: &'a i32 = &0i32;这样的声明，因为'a已经作为bounded lifetime variable引入到了当前的context
  • lifetime parameter甚至可以不出现在参数和返回值中，而只是用来引入一个lifetime variable，如fn f<'a>()

在struct、enum的定义中出现引用或trait obejct时，也需要提供lifetime parameter（除非lifetime显式指定为'static），如：

• struct A<'a, 'b> { x: &'a i32, y: &'b i32 }
• 对应的impl也要有lifetime parameter：impl<'a, 'b> A<'a, 'b> {}，或写作impl A<'_, '_> {}，两者等价

在trait定义中可以使用lifetime parameter，例如trait Trait<'a>，对应的impl trait中也要有lifetime parameter如impl<'a> Trait<'a> for i32。另外，在impl trait中也可以这样的形式引入lifetime parameter：impl<'a> Trait for Struct<'a>。

带有lifetime parameter的trait看似没有用，实际上可以为其method引入early-bound lifetime parameter，下面这个来自Stackoverflow的例子能很好地说明这个问题。

假设我们有如下代码：

struct SimpleKeeper<'a> {
    val: &'a u8,
}

impl<'a> SimpleKeeper<'a> {
    fn save(&mut self, v: &'a u8) { self.val = v }
    fn restore(&self) -> &'a u8 { self.val }
}

利用带有lifetime parameter的trait，可以generalize如下：

trait Keeper<'a> {
    fn save(&mut self, v: &'a u8);
    fn restore(&self) -> &'a u8;
}

struct SimpleKeeper<'a> {
    val: &'a u8,
}

impl<'a> Keeper<'a> for SimpleKeeper<'a> {
    fn save(&mut self, v: &'a u8) { self.val = v }
    fn restore(&self) -> &'a u8 { self.val }
}

这样，假设后来又引入了ComplexKeeper<'a, 'b, T>，我们可以为其实现impl<'a, 'b, T> Keeper<'a> for ComplexKeeper<'a, 'b, T>，将ComplexKeeper<'a, 'b, T>和SimpleKeeper<'a>统一抽象为Keeper<'a>。

---

引入lifetime parameter后，type bound规则也要相应增加：

• 'a: 'b: 表示'a必须outlive'b，例如fn f<'a, 'b>(x: &'a i32, y: &'b i32) where 'a: 'b
• T: 'a: 表示T必须outlive'b，例如fn f<'a, T>(x: &'a i32, y: T) where T: 'a

其中T: 'a的具体含义是T中出现的所有lifetime variable都要outlive'a：

• 例如'r: 'a且U: 'a时，&'r U: 'a、S<'r>: 'a成立
• 若T不含lifetime variable，则T: 'a是vacuously true的，例如i32: 'a

这条规则最常见的用途就是用于指定&'a T中T: 'a，因为被引用者的lifetime必须要比引用长。事实上在struct中若不提供此type bound是无法通过编译的，例如：

struct Ref<'a, T: 'a> {
    r: &'a T
}

在1.30版本及以前，不写T: 'a是无法通过编译的，在1.31版本及以后，编译器添加了自动推导T: 'a类型约束的功能，我们便可以不需要每次都写上T: 'a了。

Lifetime Part III. Lifetime Polymorphic Types

现在我们考察关于lifetime polymorphic的函数的实际语义，考虑函数fn f<'a>(x: &'a T) -> &'a T，某个call site为f(v)，其中实参v: &'b T：

• 形参中的'a表示的是实参的lifetime至少为'a
  • 在传递参数时会对v进行复制，得到形参x，这一过程与x = v类似
  • 因此应遵循&'b T <: &'a T，于是'b : 'a，实参的lifetime大于等于形参的lifetime
• 返回值中的'a表示的是其lifetime至多为'a
  • 考虑返回值赋值给变量m或临时变量，根据同样道理，变量m或临时变量的lifetime小于等于返回值的lifetime
• 综上可知，fn f<'a>(x: &'a i32, y: &'a i32) -> &'a i32实际上可以理解为，返回值的lifetime与实参的lifetime的交（或者说最大公约数）相同

假设上述函数替换为fn f<'a>(x: &'a mut T) -> &'a mut T，则x = v仍应满足&'b mut T <: &'a mut T的subtyping规则，不因mutable reference的move语义而改变，因此上述结论仍将成立。

对于函数，若其返回值的lifetime不是从参数的lifetime获得，则其lifetime是unbounded lifetime，也就是凭空而来的（譬如是由unsafe代码产生的），例如fn f<'a>(x: *const T) -> &'a T。

凭空而来的unbounded lifetime是existential的，它产生时没有受到subtyping或reborrow赋予的outlive约束，因此可以是context要求的任意lifetime，这实际上比'staticlifetime还要强。例如&'static &'a T是无效类型，但&'unbounded &'a T会被视为&'a &'a T从而通过type check。一般而言，如非必要，应避免unbounded lifetime。

---

为了考察lifetime polymorphic的struct和enum的实际语义，我们需要回到lifetime的定义上来。事实上lifetime这个词可以指代两种概念：

• lifetime of reference，即引用有效的时间范围，也就是Rust类型系统中的lifetime概念
• lifetime of value，即值从创建到析构的时间范围

假若一个变量中存放的是引用，即v: &'a T，那么变量的lifetime和引用的lifetime有可能是相同的，但一般来说两者并不能等同。下面我们用斜体的「lifetime」表示value的lifetime，用不带斜体的「lifetime」表示reference的lifetime。

为了考察struct和enum，不失一般性，考虑structS<'a, 'b, ..., 'n, P1, P2, ..., Pn>，其实例为s，我们递归地检验其field的类型：

• 整数、浮点、bool、char：与lifetime无关
• for <'r1, 'r2, ..., 'rn> fn(T1, T2, ..., Tn) -> R
  • 即使T1, T2, ..., Tn或R中含有struct的lifetime parameter'a或type parameterPi，也与struct的lifetime无关
• *const T, *mut T
  • 即使T中含有struct的lifetime parameter'a或type parameterPi，也与struct的lifetime无关
• [T; n], (T1, T2, ..., Tn): 递归地检验T, T1, ..., Tn
• Struct<'a1, 'a2, ..., 'an, T1, T2, ..., Tn>, Enum<'a1, 'a2, ..., 'an, T1, T2, ..., Tn>
  • 其中T1, T2, ..., Tn可以具有进一步的结构，不一定只是type parameter
  • 将T1, T2, ..., Tn代入后，得到Struct<'a1, 'a2, ..., 'an, Pi1, Pi2, ..., Pik>/Enum<'a1, 'a2, ..., 'an, Pi1, Pi2, ..., Pik>
  • 递归地检验其field/varaint
• &'a T, &'a mut T
  • 它是struct的一个fragment（指field或field的一部分），例如s.f, s.f[idx]（Array Member）, s.f.idx（Tuple Member）, s.f1.f2（Field of Embedded Struct）
  • 类型推导时应有'a: lifetime(s)的约束
    • 首先，fragment的lifetime与struct的lifetime相同，而lifetime'a也应该和fragment的lifetime相等
    • 但实际上类型推导时'a也可以再放宽些，使得其大于fragment的lifetime，这可能是为了满足某处产生的一个subtyping约束
    • 故'a应该大于等于struct的lifetime
• 上述讨论的是由struct直接持有（own）的fragment，下面对于&'a T、&'a mut T类型的fragment中被间接引用的T作分类讨论：
  • 整数、浮点、bool、char、函数指针、*const U、*mut U、str：与lifetime无关
  • [U], [U; n], (U1, U2, ..., Un): 递归地检验被间接引用的U, U1, ..., Un
  • Struct<'a1, 'a2, ..., 'an, U1, U2, ..., Un>, Enum<'a1, 'a2, ..., 'an, U1, U2, ..., Un>: 将U1, U2, ..., Un代入，再递归地检验其被间接引用的field/variant即可
  • &'r U, &'r mut U
    • 间接引用可能有多层，即&'r U'被&'r1 U1引用，&'r1 U1又被&'r2 U2引用，最终&'rn Un被&'a T引用
    • lifetime的约束关系为'r: 'r1, 'r1: 'r2, ..., 'rn: 'a, 'a : lifetime(s)，即'r: lifetime(s)
  • dyn Trait + 'r: 同理应有'r: lifetime(s)

综上可知，struct的lifetime parameter'a的含义需要具体情况具体分析，它可能代表了struct的lifetime的一个上界，也可能与struct的lifetime毫无关系。又其type parameterP在实例化为concrete type时，也可能引入lifetime variable'p，'p是否为struct的lifetime的上界也需具体分析。

回顾一下，T: 'a的含义是T中的所有lifetime variable都要outlive'a，若T是一个struct：

• 可能lifetime variable'b与struct的lifetime毫无关系，却必须满足'b : 'a，这是保守的设计，会导致编译器拒绝一些正确的程序
• 也可能lifetime variable满足'b: lifetime(s)，但这并不意味着lifetime(s): 'a，完全有可能struct本身的lifetime没有'a长

下面这段代码就展示了一个T: 'a中structT的lifetime没有'a长的例子：

struct Struct<'a> {
    x: &'a str
}

struct Example<'a, T: 'a> {
    x: T,
    y: &'a i32
}

fn f<'a>(x: &'a i32) {
    println!("{}", x);
    {
        let s = Struct::<'a>{ x: "str" };
        let example = Example::<'a>{ x: s, y: &42 };
    }
    println!("{}", x);
}

再考虑下面这段代码，它是无法通过编译的，因为structs的lifetime比'a要短（Playground）：

struct Struct<'a> {
    x: &'a str
}

struct Fail<'a, T: 'a> {
    r: &'a T
}

fn f<'a>(x: &'a i32) {
    println!("{}", x);
    {
        let s = Struct::<'a>{ x: "str" };
        let fail = Fail::<'a>{ r: &s };
    }
    println!("{}", x);
}

可以看到s的类型是Struct<'a>，实际上是满足Struct<'a>: 'a的要求的，编译不通过的原因是&'a T本身就附带了一个implicit的约束，即T的lifetime要大于'a，需要注意这和T: 'a是不同的，因为即使T本身的lifetime要大于'a，其中的引用的lifetime不一定大于'a。

Lifetime Part IV. Advanced Features of Lifetime

对于struct和enum，存在一条额外的borrow check规则，称为sound generic drop，检查是否符合该规则的过程称为drop check（简称dropck），习惯上我们也把这条规则称为drop check (dropck)。

考虑一个struct，其中含有一个引用field，且其实现了Drop：

• 该引用field可能会引用struct的另一个field
• drop函数中，若被引用的field先析构，该引用field再进行解引用，就会造成use-after-free的bug

这说明对于实现了Drop的generic struct，其中的lifetime parameter'a必须严格大于struct的lifetime，只有这样drop函数才是sound的，这一原则就是sound generic drop的核心思想。

drop check的详细规则如下（参考RFC 1238）：

• 对于变量v，若它own某个类型D，而D又（直接或间接地）可达引用&'a T，且D实现了Drop，则D有可能适用于drop check
  • 所谓的own就是说v的某个fragment的类型为D，或者v本身的类型就是D
• 若D适用于drop check，则要求'a严格大于lifetime(v)
• 我们规定impl<...> Drop for D<...>中若是出现lifetime parameter'a，则D适用于drop check
  • 若'a是D的lifetime parameter，则Drop是为D<..., 'a, ...>实现的
  • 因为此时D的drop函数中可以直接访问&'a T，可能造成use-after-free，故D适用于drop check
• 我们规定impl<...> Drop for D<...>中若是出现type parameterU，则D适用于drop check
  • 若'a不是D的lifetime parameter，则它是通过D的type parameterU传入的
  • 由于Drop是不允许specialization的，故Drop只能是为Drop<..., U, ...>实现的
  • 因此，drop函数可能通过U访问到&'a T，造成use-after-free，故D适用于drop check

其实上述两条规则已经涵盖了所有可以含有&'a T的D，这意味着凡是含有引用且实现了Drop，就适用于drop check。RFC 1238采用这样繁复的语言来描述drop check，可能是为了向前兼容，也方便以后改进drop check规则。

Rust还提供了一个unstable的特性#![feature(dropck_eyepatch)]，允许在实现Drop时将lifetime parameter或type parameter标记为#[may_dangle]，表示其lifetime不必大于struct的lifetime：

• unsafe impl<#[may_dangle] 'a> Drop for Inspector<'a> {}
• unsafe impl<'a, #[may_dangle] 'b, #[may_dangle] T, U: Display> Drop for Inspector<'a, 'b, T, U>
• 一旦使用了#[may_dangle]，就必须标记为unsafe impl

---

Rust支持将polymorphic函数作为first-class value，也即通常所说的Higher-Rank Type，但仅限于只有lifetime parameter'a而没有type parameterT的情况，这个特性称为Higher-Rank Trait Bound (HRTB)。

首先，仅含有lifetime parameter的polymorphic函数会被视为Polytype (*)，而非Type Operator (LT -> *) ：

• for<'a> fn (&'a i32): 在函数指针的类型中可以出现for<'a, 'b, ..., 'n>前缀
  • for<'a>表示对于任意'a，显然∀'a. fn(&'a i32)就是generic函数fn f<'a>(&'a i32)的类型
• 函数可以接受这样的polymorphic函数作为参数，或者将其返回，通过嵌套使用for<...>可以构造任意rank的函数类型
• 但并不存在for<T> fn() -> T，因为Rust尚不支持含有真正type parameter的polymorphic type，会将其视为Type Operator

此外，仅含有lifetime parameter的trait object也会被视为Polytype（*），而非Type Operator（LT -> *）：

• for<'a> Trait<'a>, for<'a> Fn(&'a i32): 这个用法通常配合Fn、FnMut、FnOnce这三个trait使用，用于指定closure的类型
• 例如将closure放入box中，得到的类型即为Box<dyn for<'a> Fn(&'a i32)>

for<...>前缀还可以在where子句中使用，如where for<'a> F: Fn(&'a i32), G: FnMut(&'a u8)，相当于where子句中的每个type bound都加了for<...>前缀。

---

函数的lifetime parameter存在early-bound和late-bound的区别：

考虑structList<'a, T>，若不指定具体的T，则List会被视为type operator，因此我们称T是early-bound的type parameter。对于List<'a, T>中的'a而言，情况是相同的，List<T>会被视为type operator，必须指定具体的'a才能构成完整的Type，因此'a是early-bound的lifetime parameter。

由于有类型推导的存在，List<T>会被视为List<'_, T>并自动推导出'_的值，但编译器实际上仍认为List<'a, T>才是type，而List<T>只是接受一个lifetime parameter返回一个type的type operator。

对于函数，则for<'a> fn(&'a i32)是一个合法的type，考虑一个函数指针f: for<'a> fn(&'a i32)，对其的两次调用f(v1)和f(v2)中，'a可以实例化为不同的lifetime，也就是说'a是在调用时才进行绑定，因此称其为late-bound lifetime parameter。注意对于late-bound lifetime parameter，不能通过f::<'static>这样的形式显式地指定其值，也就是说必须等到调用时推导。

但是并不是所有函数中的lifetime parameter都是late-bound parameter：

• 若它出现在where子句中，则为early-bound parameter
  • 如fn f<'a, T: 'a>(x: T) {}，若要实例化f，必须提供T，而要提供T，就必须提供'a，因此'a是early-bound的
• 若它只出现在返回值的类型中，则为early-bound parameter
  • 如fn f<'a>() -> &'a i32中的'a是early-bound的
  • 但fn f<'a>()中的'a是late-bound的
  • 这个设计似乎仅仅是一个arbitrary decision，没有什么深层次的原因
• 它已经在trait或impl<...>中被绑定，那么自然是early-bound parameter，例如
  • trait Trait<'a> { fn(x: &'a i32); }
  • impl<'a> Struct<'a> { fn(x: &'a i32) {...} }
  • impl<'a> Trait<'a> for Struct { fn(x: &'a i32) {...} }

---

为了方便使用，Rust有所谓lifetime elision规则。首先看函数的lifetime elision：

• 在function item（即function定义）、function pointer类型、Fn, FnMut, FnOnceTrait中，可以省略lifetime
  • 建议对于引用直接省略lifetime，对于struct、enum等使用'_通配符，如fn new(buf: &mut [u8]) -> BufWriter<'_>
• 首先，函数参数中省略的每个lifetime，都会被推导为不同的lifetime parameter
• 若函数参数中仅有一个lifetime parameter，则函数返回值中所有省略的lifetime，都会被推导为该lifetime parameter
• 对于Method，若self参数为&Self或&mut Self类型，则函数返回值中所有省略的lifetime都会被推导为self参数的lifetime
• 若上述两条都不适用，则函数返回值中省略的lifetime无法推导，不能通过编译

对于trait object，有两套规则：

• 若通过dyn Foo + '_指定省略的lifetime，则遵循上述函数的lifetime elision规则
  • 例如fn f(x: Box<dyn Trait + '_>)等价于fn f<'a>(x: Box<dyn Trait + 'a>)
• 若只指定dyn Foo，则编译器会自动生成default trait object lifetime bound
  • 例如fn f(x: Box<dyn Trait>)等价于fn f(x: Box<dyn Trait + 'static>)

default trait object lifetime bound的规则如下：

• 若containing type对trait object有唯一的type bound，则就取其作为默认的lifetime bound
  • 例如std::cell::Ref<'a, dyn Foo>等价于std::cell::Ref<'a, dyn Foo + 'a>
• 若没有containing type或containing type对trait object没有type bound，则
  • 默认type bound为'static，例如Box<dyn Foo>等价于Box<dyn Foo + 'static>
  • 若出现在expression context中，则根据context推导lifetime
• 若containing type对trait object有多个type bound，则需要显式指定lifetime bound

对于static或constant声明，默认其lifetime parameter为'static，因为手动指定时也只能是'static：

• 例如const STRING: &str = "string"等价于const STRING: &'static str = "string"

Type Coercion and Type Cast

首先来看Rust的subtyping规则，实际上在Rust中subtyping只涉及lifetime，即将lifetime进行type erasure后将没有subtyping：

Type	Variance in 'a	Variance in T
&'a T	covariant	covariant
&'a mut T	covariant	invariant
*const T		covariant
*mut T		invariant
[T] and [T; n]		covariant
fn() -> T		covariant
fn(T) -> ()		contravariant
std::cell::UnsafeCell<T>		invariant
std::marker::PhantomData<T>		covariant
dyn Trait<T> + 'a	covariant	invariant

对于struct或enumF<T>，其关于T的variance由其含有T的field的variance决定，若所有含有T的variance一致，则就取该variance，若不一致则为invariant。

下面逐一考察以上规则：

• &'a T、&'a mut T和dyn Trait<T> + 'a对于'a是covariant的，这在前文介绍'a : 'b时已经解释过，是因为lifetime更长的可以赋值给lifetime更短的，反之则不行
• &'a T和*const T对于T是covariant的，因为其对T是只读的，只要S <: T，我们就可以将指向S的引用视为指向T的引用
• &'a mut T和*mut T对于T是invariant的，因为其是对T的可读写的引用，下面通过反证法进一步说明：
  • 若&'a mut T对于T是covariant的，则S <: T时，可以将x: &'a mut S赋值给y: &'a mut T，再执行*y = z，其中z: R、S <: R <: T
  • 假设y的当前值即x赋值给y的值来自于x = &mut u, u: U，则应有U <: S
  • 然而由于U <: S <: R，u的当前值z不一定是一个合法的U，这就说明covariant会导致unsound的结果，因此T必须是invariant的
• 函数fn(T) -> U关于Tcontravariant，关于Ucovaraint，这和一般的subtyping理论一致，不需要解释
• 数组[T]、[T; n]是covariant的，因为它们对于T是own而不是borrow的关系，故不会发生&'a mut T一样的unsound问题
• dyn Trait<T>是invariant的，因为其成员函数完全可以关于T是invariant的，此时我们只有作最坏推定令dyn Trait<T>总是invariant的
• std::cell::UnsafeCell<T>对于T是invariant的，一个简单推论是interior mutability会带来invariance
• PhantomData<T>可以提供covariant的T，PhantomData<fn(T)>可以用来提供contravariant的T，还可以有更多组合方式如PhantomData<&'a T>，因此标准库只需要提供一个PhantomData就足够了

PhantomData<T>的一个重要作用是为使用裸指针的类型提供lifetime限制，例如使用*const T的类型S<T>可以添加一个PhantomData<&'a T>类型的成员，此时整个类型变为S<'a, T: 'a>。

PhantomData<T>还会被编译器特殊对待，在drop check时PhantomData<T>会被视为T，即使T并不是PhantomData<T>的fragment的类型（PhantomData<T>甚至没有field）。例如Vec<T>内部也是使用裸指针存放数据，它需要一个PhantomData<T>类型的成员，以保证实现了Drop的T中的引用的lifetime严格大于Vec<T>实例的lifetime。

---

另外，由于引入了Higher-Rank Type，我们需要引入一条新的subtyping规则，可以称之为subsume或generic instance规则。简而言之，就是A如果比B更polymorphic，我们就说AsubsumesB或者A是B的generic instance，记作A <: B。

现在通过一个经典的例子来进一步解释：

• 考虑三个函数类型A = ∀a.a -> a, B = ∀b.[b] -> [b], C = [Int] -> [Int]
• A代表了一个更大的函数集合，B代表了一个更小的函数集合，C代表单独一个函数
• 所谓polymorphic的程度，就是其代表的集合的大小，我们有A ⊇ B ⊇ C，就对应于A <: B <: C

具体到Rust，就是：

• &(for<'a> fn(&'a i32) -> &'a i32) <: &(fn(&'static i32) -> &'static i32)，因为左边存在一个成员等于右边
• &(for<'a, 'b> fn(&'a i32, &'b i32)) <: &for<'c> fn(&'c i32, &'c i32)，因为左边存在一个子集等于右边

---

为了更好地理解上面的例子，我们需要进一步展开解释。

首先注意到Rust中允许省略type application（例如f::<T>可以略写为f），这属于type inference的一部分。

先不考虑Rust，回顾经典的Type Theory中对此的建模：

• 以System F为例，写作$(\Lambda X.\lambda x^X.x)\,[\mathrm{Bool}]\,a$的表达式，可以略作$(\Lambda X.\lambda x^X.x)\,a$
• 写作$(\Lambda X.\lambda x^X.x)\,a$只是影响type check，但对于计算结果没有影响，因为计算是在type erasure后进行的
  • 即$(\Lambda X.\lambda x^X.x)\,a$在计算时实际上是$(\lambda x.x)\,a = a$
  • 换句话说，从纯理论（类型系统）的角度看，所有函数本质上都是untyped的，类似动态语言中duck typing的函数
    • 我们可以将monomorphic函数针对不同类型，生成不同机器码/字节码的具体行为，视为语言实现时的一种优化
    • 同理，我们可以将Rust/C++针对polymorphic函数进行monomorphization的行为，视为语言实现时的一种优化，有些语言则没有实现这一优化或这一优化是可选的
• type check实际上是要求，存在一个type application，使得添加它之后的式子，在System F中能通过type check

我们在此模型下，考察B <: C的由来：

• 期望C类型的位置若替换成B类型的值，则存在type application b = Int，令其类型变为[Int] -> [Int] = C，因此允许替换，即B <: C
• 上述论述等价于将B视为一个集合，要求∃b. b ∈ B ∧ b = C，也就是C ∈ B或者说{C} ⊆ B

再考虑A <: B的由来：

• 期望B类型的位置若替换成A类型的值，假设原本B类型需要的type application为b = b0，则可令type application改为a = [b0]，得到的类型都是[b0] -> [b0]，因此允许替换，即A <: B
• 上述论述等价于将A、B视为集合，要求∀b ∈ B. ∃a ∈ A. a = b，也就是B ⊆ A

这样，我们就解释了为什么subtyping规则是更polymorphic的类型（更大的集合）是不够polymorphic的类型（更小的集合）的subtype。

回到Rust，在Rust中省略函数的type parameter会造成两种不同的语义：

• f::<'a, T>省略为f::<'a>，此时f::<'a>不能作为一个polymorphic type的值存在
  • 因为涉及T时会发生monomorphization，f::<'a>代表了无数个monomorphic type的值
  • 而许多函数式语言中，编译时polymorphic function会发生type erasure，最后落实到单独一个值，而不是无穷多个
• f::<'a, T>省略为f::<T>，此时f::<T>能作为一个polymorphic type的值存在
  • 因为lifetime'a会发生type erasure，故能够表现地像典型的函数式语言一样
• 只有后者遵循上面描述的模型，故只有它才支持Higher-Rank Type以及上述subtyping规则

---

下面介绍type coercion，也就是隐式类型转换。

coercion只能发生在以下场合，即coerce的目标类型已经确定的场合，称为coercion site：

• const、static语句，显式声明了类型的let语句，以及赋值语句
• 函数参数，实参被coerce到形参
• 函数返回值，return的值被coerce到返回值类型
• struct、enum的初始化
• 上述场景的expression中的sub-expression，以及sub-expression的sub-expression等等（可递归），包括：
  • array和tuple，如果整个expression有确定的coerce目标类型，则每个sub-expression也能确定coerce目标类型
  • block语句，若其有确定的coerce目标类型，则其中最后一个expression的coerce目标类型也就确定了

coercion包括以下隐式类型转换：

• 若T <: U，则T可以coerce到U
• 若T1可以coerce到T2，T2可以coerce到T3，则T1可以coerce到T3
• &mut T可以coerce到&T，*mut T可以coerce到*const T
• &T可以coerce到*const T，&mut T可以coerce到*mut T
• 若T: Deref<Target = U>，则&T和&mut T可以coerce到&U
• 若T: DerefMut<Target = U>，则&mut T可以coerce到&mut U
• 无捕获的closure类型可以coerce到函数指针类型
• Bottom Type!可以coerce到任意类型T
• 若T到U存在unsized coercion，则&T, &mut T, *const T, *mut T, Box<T>可以coerce到&U, &mut U, *const U, *mut U, Box<U>
  • 实际上凡是实现了std::ops::CoerceUnsized<Ptr<U>>的Ptr<T>，都能coerce到Ptr<U>，所有智能指针都通过这种方式实现了对unsized coercion的支持

所谓unsized coercion就是从sized type转换到unsized type，包括如下隐式类型转换：

• [T; n]可以转换为[T]
• 若T: Trait，则T可以转换为dyn Trait
• 若TraitT : TraitU，则dyn TraitT可以转换为dyn TraitU
• Foo<..., T, ...>可以转换为Foo<..., U, ...>，只要满足：
  • T到U存在unsized coercion
  • Foo是一个struct，且最后一个field的类型中含有T，而其他field中不含T
  • 若最后一个field类型中含有Bar<T>，则Bar<T>到Bar<U>必须也存在unsized coercion

注意coercion不一定总是no-op，从&[T; n]到&[T]、从&T到&dyn Trait都需要从thin pointer转换到fat pointer。

RustLang Reference Defect? 上述Foo<..., T, ...>到Foo<..., U, ...>的unsized coercion规则有些不严谨，若最后一个field含有的是函数指针fn(T) -> T，也适用于unsized coercion吗，似乎并不合适。反之，若非最后一个field含有&'a T，则实际上将T转换到U是合法的。

---

除此之外，Rust还提供了type cast即强制类型转换，其语法为expr as Type，例如i as f64。

首先，Rust提供了各种数值类型的type cast：

• Numeric Cast: 从integer/float到integer/float
  • u32 -> i32: size相同则仅改变类型
  • u32 -> u8: 从大到小会truncate
  • u8 -> u32: 从小到大会extend，unsigned整数进行zero-extend，signed整数进行sign-extend
  • f32 -> i32: 从float到integer会round to zero，若超出integer表示范围则是UB
  • i32 -> f32: 从integer到float会产生最接近的值
    • rounding mode取IEEE 754-2008的「ties to even」模式
    • 若发生overflow，则产生±Inf，符号与integer相同，当前只有u128 -> f32可能发生overflow
  • f32 -> f64: 从f32到f64是loseless的
  • f64 -> f32: 从f64到f32会产生最接近的值
    • rounding mode取IEEE 754-2008的「ties to even」模式
    • 若发生overflow，则产生±Inf，符号与f64相同
• Enum Cast: 从C-like enum（即field-less enum）到integer，取其discriminant即可，可能需再进行一次numeric cast
• Primitive to Integer Cast: 从bool或char到integer
  • bool -> u32: false变成0，true变成1
  • char -> u32: 取char的code point值即可，可能需再进行一次numeric cast
• u8 to char Cast: 得到相应code point的char

其次，提供了涉及指针的各类type cast，尽管看起来是unsafe的但实际上这些操作也是safe的，因为若要解引用指针则必须使用unsafe块，故type cast就无需额外标记为unsafe的了。Rust提供了以下type cast，其中*T代表*const T或*mut T，：

• Array to Pointer Cast: &[T; n] -> *const T
• Pointer to Pointer Cast: *T -> *U
  • 或者是T和U都是sized类型
  • 或者是T和U同属slice或同属dynamic trait，这样它们的fat pointer互相兼容
• Address Cast: Integer -> *U, *T -> Integer, fn -> Integer
  • 地址只能转换为*U, U: Sized，因为指向unsized type的指针是fat pointer
  • 反之，也只有*T, T: Sized才能转换为地址，因为fat pointer不能转换为地址
  • 此外，函数指针也能转换为地址
• Function Pointer to Pointer Cast: fn -> *U
  • 函数指针只能转换为*U, U: Sized，因为函数指针是thin pointer，而指向unsized type的指针是fat pointer
• Closure to Function Pointer Cast: Closure -> fn
  • 只有无capture的closure可以转换为function pointer，因为此时closure只是一个普通的匿名函数

最后，所有type coercion同时也可以显式地用作type cast。

---

Rust还提供了AsRef<T>和AsMut<T>这两个Trait来进行reference到reference的转换：

• AsRef<T>只有一个as_ref(&self) -> &T方法，用于将U: AsRef<T>转换为&T
• AsMut<T>只有一个as_mut(&mut self) -> &mut T方法，用于将U: AsMut<T>转换为&mut T
• 在generic函数中，可以使用T: AsRef<U>类型的参数，来接受一切可以转换成&U的变量，对于AsMut<T>也是同理

此外还有From<T>和Into<T>这两个Trait可以进行value到value的转换：

• From<T>只有一个from(T) -> Self的方法，用于将T转换为U: From<T>
• Into<T>只有一个into(self) -> T的方法，用于将U: Into<T>转换为T
• 对任意类型都有T: From<T>和T: Into<T>
• 应当优先实现From<T>，因为若U: From<T>则标准库会自动为我们实现Into<U> for T，反之则不行
• Into<T>适合作为generic函数中参数的类型
• 错误处理时，若函数返回值为Result<T, MyError>，则?操作符会自动调用Into<MyError>::into，将各种错误转换为MyError
  • 因此建议为自己自定义的错误类型实现From<E>

Reborrow Rules

自动reborrow不仅可以发生在函数参数传递时，还有多种方法触发自动reborrow，但Rust文档中并未提供详细的规则，下面谈谈我的理解。

首先，let语句和赋值语句可以引起reborrow，设u: &mut i32, v: &mut i32, w: &i32，则：

• let x: &i32 = u: u会被reborrow
  • 这里本质上是发生了&mut T到&T的coercion，而该coercion的实现方式就是reborrow
• let x = w; x = u;: u会被reborrow
  • 首先x的类型被推导为&i32，let语句进行copy操作
  • 然后x = u发生了&mut T到&T的coercion，于是发生了reborrow
• 类型推导决定了是否发生mutable reference到mutable reference的reborrow，参见这个issue
  • let x = u: u会被move
  • let x; x = u;: u仍会被move
  • let x: &mut i32 = u: u会被reborrow
    • 按照Rust维护者Nicholas D. Matsakis的说法，这里发生的reborrow本质上是&mut T到&mut T的coercion，其实现方式是进行reborrow
    • 尽管Rust文档中并未列出一条&mut T到&mut T的coercion
  • 若let语句未指定类型，需要类型推导，则不属于coercion site，因此不会发生reborrow，而是会进行move
  • 若let语句指定了类型，则属于coercion site，因此会发生reborrow
• let mut x = u; x = v;: u会被move，v会被reborrow
  • 初始化时不属于coercion site，故u会被move
  • 随后的每次赋值，都属于coercion site，故v会被reborrow
• x.0 = u, x.field_0 = u, x[0] = u: u均会被reborrow
  • 无论LHS是什么，我们总能确定LHS的类型，因此总会进行coercion，于是总是会进行reborrow

由上述论述可知，reborrow和coercion密切相关，凡属于coercion site的都会发生reborrow：

• struct、enum的初始化，若发生&mut T到&T或&mut T的coercion，则会发生reborrow
• 函数调用，若发生实参&mut T到形参&T或&mut T的coercion，则会发生reborrow
• 函数返回值，若发生返回值&mut T到&T的coercion，则会发生reborrow
  • 例如fn f(x: &mut i32) -> &i32 {x}
  • 这里&mut T到&mut T的coercion没有意义，因为返回总是需要经历「move out」的过程

这里generic的struct、enum和函数，也会遇到和let语句类似的情况：

• 考虑函数fn f<T, U>(x: T, y: U, z: T)，设x: &mut i32, y: &mut i32, z: &mut i32，则在调用f(x, y, z)中
  • x和y被move
    • 因为此时尚不知道T和U的类型，要先进行类型推导，这就相当于let t = x; let u = y;，不会发生coercion
  • z被reborrow
    • 此时已经确定了T的类型，相当于let a: &mut i32 = z;，因此会发生coercion
• 再考虑struct Struct<T>{ s: T, t: T }，设x: &mut i32, y: &mut i32，则
  • let a = Struct{ s: x, t: y }中x被move，而y被reborrow
  • let a = Struct{ t: y, s: x }中y被move，而x被reborrow
  • 这说明类型推导的顺序不是按照struct中声明的顺序，而是实际初始化时的使用顺序，最先用于推导的变量不会被reborrow

Lifetime Part V. Non-Lexical Lifetime

在1.30版本及以前，引用的lifetime必须从其borrow时延续到scope末尾，从1.31版本起引入了Non-Lexical Lifetime (NLL)，从而使得lifetime可以是Non-Lexical的。

实际上，NLL带来的更大的改变是将'a: 'b的outlive关系改为了location-aware的，我们来看一个例子：

let mut u = 0i32;
let mut v = 1i32;
let mut w = 2i32;

// lifetime of `a` = α ∪ β ∪ γ
let mut a = &mut u;     // --+ α. lifetime of `&mut u`  --+ lexical "lifetime" of `&mut u`,`&mut u`, `&mut w` and `a`
use(a);                 //   |                            |
*a = 3; // <-----------------+                            |
...                     //                                |
a = &mut v;             // --+ β. lifetime of `&mut v`    |
use(a);                 //   |                            |
*a = 4; // <-----------------+                            |
...                     //                                |
a = &mut w;             // --+ γ. lifetime of `&mut w`    |
use(a);                 //   |                            |
*a = 5; // <-----------------+ <--------------------------+

在传统的lexical lifetime模型中，&mut u、&mut v、&mut w以及a的lifetime都相同，从let mut a = &mut u;这一句一直延续到*a = 5;。但是在NLL中，&mut u的lifetime为α，&mut v的lifetime为β、&mut v的lifetime为γ，而a的lifetime为α ∪ β ∪ γ（不连续）。显然，NLL中的outlive关系不再是简单的集合包含关系，否则根据subtyping rule，&mut u、&mut v、&mut w的lifetime应该包含'a而不是反过来被包含于'a。

实际上NLL下的lifetime是更为合理的，因为本质上说，一个rvalue引用&'r lvalue的lifetime'r，和一个lvalue引用x.y.z的lifetime'a从概念上讲是不同的。假设x.y.z是mutable的，那么在x.y.z的整个生命周期中，它可能被赋值若干次，每次赋值的RHS都有一个lifetime'ri，总的来说其lifetime就应该是所有这些lifetime的并∪'ri。而对于作为rvalue的引用，其lifetime就应该单纯是该引用有效的范围。NLL对此能作出区分，而lexical lifetime则会将rvalue引用的lifetime扩大到与lvalue引用的lifetime相等。

在RFC 2094中详细介绍了NLL的机制，对lifetime的推导算法给出了详细描述，现介绍如下，了解NLL的细节有助于我们深入理解Rust中lifetime和borrow check的本质。

根据Nicholas D. Matsakis的这篇博客，由于性能上的考虑，NLL似乎并没有实现RFC 2094中的全部内容（对Named Lifetime的处理没有实现，因此我们也不介绍这一点）。目前Rust团队正在推进Polonius项目[1][2]，它将作为NLL 2.0，最终取代现在的NLL。Polonius将会解决RFC 2094试图解决的所有问题，并能解决更多borrow check问题。

Basic Algorithm

首先，在NLL中borrow check被推迟到了产生MIR (Mid-Level Intermediate Representation)后进行，而MIR在编译器中是以CFG而不是AST的形式表示的，我们所有的概念都可以定义到CFG上，这远远比基于AST的lexical lifetime灵活得多。MIR语句大致是Three Address Code的格式，每一句只对应于Rust源码中的一步操作，此外在MIR中还显式编码了Rust源码中隐式蕴含的语义：

• StorageDead(x)表示栈变量x已经离开其作用域，其占据的stack slot可以被回收利用
• drop(x)表示调用x的析构函数进行析构

我们首先引入point的概念，若将每一句MIR语句视为CFG中的一个节点，则每个节点的进入端称为point，表示该语句尚未执行而它之前的语句已经执行的时刻。

借此可以严格定义lifetime如下：

定义1： lifetime是CFG中的一系列point的集合。

• lifetime中的point不必是连续的
• 变量（包括临时变量）的类型中可以包含lifetime，此外每个borrow操作都会附带一个lifetime

Lifetime可能可以有多种合法的取值，Rust的lifetime inference算法会取其最小的合法值。

---

我们回顾一下编译器中的liveness analysis，它用于分析变量的liveness，当变量的值还会被再次用到时它是live的，否则它就是dead的。这里的重点在于，从变量的当前值最后一次被使用，到变量被再次赋值之间，变量处于dead状态，即使该变量之后还会被使用。

现在我们将liveness推广到lifetime上：

定义2： 我们说lifetimeL在pointP是live的，若：

• 存在某变量p在P是live的
• L出现在p的类型中

有了这个概念，我们就可以引入lifetime inference算法的第一条约束：

约束1： 若L在P是live的，则P ∈ L

这条规则使lifetime中间可以有空洞，不必连续，因此我们可以编写如下代码：

let mut x = 0;
let mut a = &x;
// `a` is dead
let u = &mut x;
// `a` is dead
let a = &1;
// `a` is live
use(a);

由于a在let u = &mut x;这一行已经处于dead状态，故a的lifetime不必包含该行，从而我们可以取x的mutable reference。

接下来，我们将outlive和subtype的关系推广为location-aware的：

定义3： (L1: L2) @ P表示L1必须包含L2的子集L2'，该子集由所有满足Q从P出发可达（这也包括了P本身），且路径上的所有point都属于L2的pointQ构成。

由location-aware的outlive关系经过subtyping rule推导得到的，自然就是location-aware的subtype关系了。当然，由于Higher-Rank Type的subtyping rule不涉及lifetime，这类subtype关系自然就应该在任意locationP都成立。

根据subtype关系，我们可以引入lifetime inference算法的第二条约束：

约束2： 根据MIR代码，我们可以推理出一系列的(T1 <: T2) @ P约束关系，其中每一条又可以推出零到若干个(L1: L2) @ P的约束关系

考虑下面这个例子，其中a: &'a T、b: T：

// P0
let a = &'b b;
// P1
...
// Pn
use(a);

从中可以得到的约束是(&'a T <: &'b T) @ P1，从而有('a : 'b) @ P1。也就是说，一条赋值语句蕴含的subtyping约束，应作用于该语句流出端的point，而不是进入端的point。我们也无需考虑整个函数的最后一条MIR语句的约束如何处理，因为最后一条语句一定是return;，不含任何约束。

下面我们处理reborrow，为此先定义一些前置概念：

定义4：

• 一个lvalue的prefix，是指我们从该lvalue舍去最后若干步dereference、field access后得到的前缀访问，如*a.b的prefix包括*a.b、a.b和a。
• 一个lvalue的supporting prefix，是指我们在舍去最后若干步时，遇到shared reference即停止不允许再舍弃而得到的prefix子集（对shared reference的dereference不应舍去）

现在可以引入lifetime inference算法的第三条约束：

约束3： 考虑一个reborrowr = &'b lv_b或r = &'b mut lv_b：

• 设lv_b的supporting prefix为集合B
• 对所有*lv ∈ B，若lv的类型是lifetime为'a的reference，则引入约束('a : 'b) @ P，其中P为该语句流出端的point

求解lifetime首先需要进行一轮liveness analysis，这是一种backward dataflow analysis，需要通过反复迭代求不动点的方式获取变量的liveness。然后，我们从所有lifetime为空集出发，反复迭代，利用约束条件扩大lifetime，直到达到不动点。整个过程需要求解两次不动点。

Reasoning

现在我们来解释为什么这个算法是正确的。首先，约束1是不言自明的，当一个变量有可能被用到时，其中含有的引用必须是有效的，因为它有可能还需要被解引用。

对于约束2，考虑一个lvalueΠ，他在pointP处被以lifetime'Lborrow为R，即R <- &'L Π @ P，然后在pointQ处被使用。在整个过程中，R最初被赋值给pathΠ1，而Π1可能被赋值给Π2，Π2又被赋值给Π3，如此辗转最后再Q处解引用Πn：

P: Π1 = &'L Π
...
   Π2 = Π1      // or Φ2 (containing Π2) = Φ1 (containing Π1)
...
Q: use(*Πn)

我们应当确保'L能从P一路延续到Q处以保证解引用操作确实有效，而约束2恰好就保证了这一点。根据约束2，我们知道Πn-1的lifetime从Πn = Πn-1至少延续到Q，而由此又可推理出Πn-2的lifetime从Πn-1 = Πn-2至少延续到Q，依此类推，'L从Π1 = &'L Π至少延续到Q。

并且，若Πn后续被重新赋值，约束2的location-aware的特点，使其不会让'L延续到Πn被重新赋值后：

Q: use(*Πn)     // last use of Πn
...             // Πn is dead, so 'L doesn't include this
Πn = &'a x      // Πn reactivated, not related to 'L

凭借这一点就能实现本节开头所示的例子中lifetime的推导。

---

最后考察约束3，首先考虑如下例子r = &'r **a.b.c，其中a.b.c和*a.b.c都是mutable reference，于是**a.b.c的supporting prefix为**a.b.c、*a.b.c和a.b.c，因此根据约束3有'b: 'r和'a: 'r：

 a.b.c
   ↓ &'a mut
*a.b.c
   ↓ &'b mut
**a.b.c   <-- &'r **a.b.c

首先，对于遇到的第一层解引用，&'r **a.b.c和*a.b.c是reborrow的关系，在borrow stack中&'r **a.b.c位于*a.b.c的上方，因此有'b : 'r，即后者的lifetime大于前者。这说明对于遇到的第一层mutable dereference，应当满足约束3。

需要指出的是，这里的'b : 'r实际上是保守的，因为它要求「borrow stack」确实是一个stack，即reborrow先出栈，被reborrow者后出栈，实际上即使这个约束不成立程序也可以是正确的。回顾此前用过的这个例子：

let new;
{
    let old = &mut x;   // --+ lifetime of `old`
    new = &*old;        //   |
}                       //   |
use(new);               //   |
// <-------------------------+

可以看到old的lifetime由于约束3被延长了，延伸至了old已经离开作用域的use(new)。我们为其增加一行read(x)：

let new;
{
    let old = &mut x;   // --+ lifetime of `old`
    new = &*old;        //   |
}                       //   |
read(x);                //   | ERROR!
use(new);               //   |
// <-------------------------+

显然，由于独占x的old已经离开了作用域，我们在read(x)中对x的读取和new这个对x的shared borrow并不冲突，但程序无法通过编译，因为old和&mut x的lifetime根据约束3已扩展得太大了。

---

对于第二层解引用，由于a.b.c引用了*a.b.c，应当有'b : 'a，但不一定有'a : 'r，完全可以a.b.c已经expire而r还保持有效。这说明约束3要求的'a : 'r实际上并不是由lifetime的定义自然导出的，而是人工构造（Artificial）的要求，后面我们将看到引入这一约束条件的目的是为了配合不够精确的borrow check算法。

'b : 'a实际上由约束1保证，不需要额外引入新的约束条件。事实上，考虑x: &'a &'b T，根据约束1，凡是使用x之处，都同时属于lifetime'a和'b，但对于location*x可能还有其他变量p可以访问，因此有'b : 'a。

下面来看一个例子，体现了为什么这一约束是不必要的：

let mut u = 0;
let mut c = 1;
let mut b = &mut c;
let d;
{
    let a = &mut b;     // --+ lifetime of `a` and `&mut b`
    d = &mut **a;       //   |
}                       //   |
b = &mut u;             //   | ERROR!
println!("{}", d);      //   |
// <-------------------------+

上述代码中，bmutably borrow了c，然后d对c进行了reborrow，最后b被赋值为了另一个mutable borrow，显然整个过程没有违反borrow规则。然而由于约束3的限制，a的lifetime会被延长至println!("{}", d)，从而导致borrow checker认为&mut b这个对b的borrow和b = &mut u冲突，程序无法通过编译。

---

再来考虑如下例子r = &'r **a.b.c，其中a.b.c和*a.b.c都是shared reference，于是**a.b.c的supporting prefix为**a.b.c，因此根据约束3有'b : 'r：

 a.b.c
   ↓ &'a
*a.b.c    <-- other shared references
   ↓ &'b
**a.b.c   <-- other shared references
   ↑ &'r
&'r **a.b.c

对于遇到的第一层解引用，&'r **a.b.c和*a.b.c是reborrow的关系，因此有'b : 'r，而对于遇到的第二层解引用，a.b.c的lifetime与&'r **a.b.c'的lifetime并没有什么必然的联系。在这里，约束3的导出是较为自然的，尽管'b : 'r仍然是为了满足「borrow stack」语义而凑出的约束条件。

下面这个例子说明了borrow stack语义实际上是保守的：

let mut x = (3, 4);
let new;
{
    let old = &x;       // --+ lifetime of `old`
    new = &(*old).0;    //   |
}                       //   |
x.1 = 0;                //   | ERROR!
println!("{}", new);    //   |
// <-------------------------+

由于约束3，old的lifetime被延伸至println!("{}", new)处，导致borrow checker认为&x这个对x的borrow和x.1 = 0冲突，程序无法通过编译。但此时只有x.0还被new所borrow，对x作为一个整体的borrow已经expire，程序实际上是正确的。

Avoiding Infinite Loops

无限循环会导致lifetime推导遇到问题，下面这个（unsafe的）scoped thread的例子可以说明这一点：

let scope = Scope::new();
let mut foo = 22;

unsafe {
    // dtor joins the thread
    let _guard = scope.spawn(&mut foo);
    loop {
        foo += 1;   // should be ERROR!
    }
    // drop of `_guard` joins the thread
}

我们希望_guard的lifetime从unsafe块的开头延续到结尾，但由于中间的无限循环，编译器会认为最后的drop(_guard)不可达，因此_guard的lifetime仅限于它所在中的这一行。这样一来，这段程序将能通过borrow check，但实际上我们希望foo += 1这一行是不合法的，因为此时spawn的thread可能正在运行并通过mutable reference访问foo。

Rust对此的解决方案是在每个无限循环中加入一条false “unwind” edge，让循环看似可以退出，但退出条件永远是false。我们称之为"unwind" edge，是因为形式上看它代表了panic时的stack unwinding这条隐藏的code path。这样一来，编译器就能够推导出正确的lifetime。

Drop Check

为了处理drop check，我们需要对lifetime的liveness定义作一修改。实际上，我们要定义两种liveness：

• 一种liveness表示变量在将来可能还会被use，这里use不包括drop
• 一种liveness表示变量在将来可能会被drop

lifetime的liveness要据此修改如下：

定义2’： 我们说lifetimeL在P是live的，若：

• 存在某变量p在P是use意义上live的，且L出现在p的类型中
• 或存在某变量p在P是drop意义上live的，L出现在p的类型中，且不是may dangle的
  • 若L不受drop check限制，例如p未实现Drop，则L是may dangle的
  • 若L被显式标记为#[may_dangle]以绕过drop check，则L也是may dangle的

也就是说，如果L是may dangle的话，其lifetime可以无需延伸至drop处，即L不一定要大于等于包含其的变量的lifetime。

Borrow Check Algorithm

Borrow checker分两个阶段运作，第一阶段的工作是为CFG中的每一个pointP计算其in-scope loan：

定义5： loan是一个('a, shared|uniq|mut, lvalue)三元组，表示一个rvalue的borrow&'a lvalue/&'a uniq lvalue/&'a mut lvalue，其中&uniq表示closure捕获时才会产生的unique immutable borrow，在Rust代码中无法显式使用。

我们在每个pointP按如下方法更新in-scope loan，通过forward dataflow analysis即可得出每个point的in-scope loan：

• 对于lifetime不包含P的loan，从in-scope loan中删除
• 若P处发生了borrow/reborrow，则产生对应的loan，加入in-scope loan
• 若P是一个assignmentlv = rvalue，则从in-scope loan中删除所有满足lv是其pathp的prefix的loan('a, _, p)

对于最后一条规则，我们看一个例子来帮助理解：

let r = &(*a.b).x.y;
// (*a.b).x = u;    // ERROR! &(*a.b).x.y is in-scope
a = new;
(*a.b).x = u;       // LEGAL! &(*a.b).x.y not in-scope
use(r);

在对a进行赋值前，&(*a.b).x.y是in-scope的，这意味着对(*a.b).x、(*a.b).x.y、(*a.b).x.y.z等不能进行写入。而对a进行赋值后，(*a.b).x、(*a.b).x.y、(*a.b).x.y.z都不再与r所指向的对象相关，可以任意访问，因此我们认为此时&(*a.b).x.y不再in-scope，即使其lifetime延续到a被赋值以后。

---

第二阶段，遍历CFG并找出不合法的操作，报告错误。对于每个对lvalue的访问，我们要在in-scope loan中找出对应的relevant loans，对于其中的每个loan：

• 若loan为shared或uniq，且访问是读取，则合法
• 否则不合法

当然，若没有relevant loan，就代表当前值没有被borrow，访问合法。

我们将对lvalue的access分为deep和shallow，deep表示lvalue下通过引用可达的数据都有可能被修改或invalidate，而shallow表示访问过程不会涉及解引用，不影响通过引用间接可达的数据。

以下操作属于shallow access：

• StorageDead(x)属于shallow write
• Lv = Rv属于对Lv的shallow write

对lvalue的shallow access的relevant loans('a, _, p)要满足如下要求之一：

• p为lvalue
  • 这表示a.b.c被borrow时，a.b.c就不能被写入或离开作用域
• p为lvalue的prefix
  • 这表示a或a.b被borrow时，a.b.c就不能被写入或离开作用域
• lvalue为p的shallow prefix，shallow prefix指取prefix时，遇到dereference即停止，比supporting prefix的范围还小
  • 这表示a.b.c被borrow时，a或a.b就不能被写入或离开作用域
  • 但*a被borrow时，a可以被写入或离开作用域

以下操作属于deep access：

• 在Lv = Rv的Rv中
  • 每个lvalue operand都是一个deep access，若其实现了Copy则是deep read，否则为deep write
    • 即copy为deep read，而move为deep write
  • shared borrow&lvalue算作deep read
  • mutable borrow&mut lvalue算作deep write
• drop(x)属于deep write

对lvalue的deep access的relevant loans('a, _, p)要满足如下要求之一：

• p为lvalue
  • 这表示a.b.c被mutably borrow时，a.b.c不能再被reborrow也不能被访问
• p为lvalue的prefix
  • 这表示a或a.b被mutably borrow时，a.b.c不能再被reborrow也不能被访问
• lvalue为p的supporting prefix
  • 这表示a.b.c被borrow时，a或a.b作为一个整体，不能被borrow或访问（但可以borrow或访问a.x.y）
  • 与shallow access相对，*a被mutably borrow时，a不能被borrow或访问

Borrow Check Reasoning

上述描述可能不够直观，我们来看一个典型的borrow check示例：

let r = &'r mut a.b;    // --+ lifetime `'r`
use(a);                 //   | ERROR! conflict with &'r mut a.b
use(a.b);               //   | ERROR! conflict with &'r mut a.b
use(a.b.c);             //   | ERROR! conflict with &'r mut a.b
use(r);                 //   |
// <-------------------------+

整个borrow check的过程有两个要点，第一是确定&'r mut a.b这个borrow的lifetime，第二是找到和该borrow冲突的访问，即对a、a.b、a.b.c的访问。由此可见borrow checker的算法是比较dumb的，它实际上无法追踪引用指向的locations，而只是对于所有的rvalue的引用&'r mut path，检查对于path或其prefix、field的访问。

由于borrow checker只关心path，因此引入in-scope loan的概念是必要的，若当前pointP还包含在loan&'r mut path的lifetime'r中，但path已经失效，不再指向borrow所引用的locations，则不必检查与path冲突的访问，此时我们就说loan&'r mut path不再in-scope了。

---

下面进一步考察borrow check的规则，不失一般性，考虑let r = &'r mut a.b：

• 首先，使用r本身与borrow check无关，因此我们可以对*r、**r等进行写入（除非path中有对shared reference的dereference）
• 其次，除了对a、a.b、a.b.c禁止访问，我们还对*a.b、**a.b等禁止访问，因为a.b是它们的prefix
  • 这说明borrow对被borrow对象的所有权是deep的（即transitive的），所有对能被间接引用的数据的访问，都被视为与borrow冲突

上面第二点实际上揭示了另一条隐藏的borrow规则，这在网上任何地方都没有介绍。概念上可以认为，对于b = &mut c; a = &b;，c的borrow stack由[c, b, a]构成，即a在这里起到的效果相当于一个对b的shared reborrow，它会导致我们无法通过b修改c的值，我们不妨将这种现象称为transborrow。

需要指出的是transborrow和普通的reborrow有所不同，考虑b = &c; a = &mut b;，此时c的borrow stack可以视为[c, b, a]，这说明我们可以用一个mutable borrow来transborrow一个shared borrow，但在[c, b, a]中a实际上从mutable borrow退化为了shared borrow。

---

现在考虑let r = &'r mut *a，其中a为mutable reference，不妨设a = &'a mut b：

我们知道，r实际上是对b的reborrow，因此对a的shallow access应该允许，例如令a指向另一个变量c（a = &mut c）。由于我们规定对于loan&'r path，只有对path的shallow prefixlvalue的访问才是冲突的shallow access，容易看出当前的borrow check算法满足这一点。

另一方面，注意到不仅通过*a = x或x = *a的形式可以访问b，表达式中只出现a而不出现*a也能间接访问到b，也就是所谓的deep access。这就是为什么对于loan&'r mut *a，我们认为对a的deep access与该loan是冲突的。

需要指出的是，deep access不一定是立即访问了b，而是说造成了一种将来间接访问b的可能性。考虑let x = &a，创建引用本身是合法的，因为r没有引用a，a还处于未被borrow的状态，但此后引用x可能被用于访问b，例如y = **x。由于borrow checker无法追踪引用指向的location，它无法检查出**x是对b的访问，因此为了保证borrow check算法的soundness，我们必须直接禁止引用x的创建。

之所以对a的copy被视为deep read，而move被视为deep write，是因为mutable reference都采用move语义。若a使用copy语义，则说明其中不直接含有mutable reference（可以间接含有，例如a: & &mut T），因此对于从acopy得到的任意x = a，我们至多只能通过x读取a所引用的数据。反之，若a采用move语义，则其可能含有mutable reference，因此可能产生对a引用的数据的写入。

若此处的a的类型是Ref<'a> { x: &'a mut T }，且Ref<'a>实现了Drop，则有可能drop(a)这个deep access会直接访问到*a.x。

borrow check算法中规定，若lvalue是对path的loan的supporting prefix，则对lvalue的deep access和该loan冲突，我们来考察这一规定的正确性：

• 首先，对于loan&'r mut path，path中的每个解引用都必须是对mutable reference的解引用，否则无法创建reborrow
  • 根据shared reference的immutability的传递性，path作为一个lvalue时是只读的，因此Rust规定不能对其创建mutable的reborrow
• 若loan为&'r mut path，则path的所有prefix都是supporting prefix，且通过所有这些prefix都可以对path进行访问，因此所有这些prefix都和该loan冲突
• 若loan为&'r path，不失一般性，考虑&'r ***a，其中a: &mut & &mut T，***a指向b
  • 实际上由于中间的shared reference，无论通过a、*a还是**a都只能对b进行读取而不能写入，故我们只需认为***a和&'r ***a冲突即可
    • 对于**a，无法通过x = **a将其move out然后再通过x写入b（被borrow者不能被move），也无法通过x = &mut **a建立引用再通过x写入b（由于shared reference的传递性）
    • 对于*a，由于*a是一个shared reference，通过x = *a不能写入b，通过x = &mut *a也无法写入b
    • 对于a，即使对a进行move或borrow，最后要访问到b总是会经过shared reference，因此无法写入b
  • supporting prefix为***a和**a，还额外包含了**a，因此显然是正确的。其实对于shared reference，只需检查shallow prefix即可。

---

我们上面只考虑了对于&'r *a需要检查对a的访问，实际上对于loan&'r path，除了path的prefix和field，也有可能通过其他变量访问path所在的locations，这就不是通过对该loan本身的borrow check能保证的了。

首先，对于形如&'r mut a.b.c的loan，容易看出在其lifetime内，只有其reborrow可以访问path所在的locations，因为若存在其他borrow能访问path所在的locations，则该loan的创建就会违反borrow check。同理，对于形如&'r a.b.c的loan，在其lifetime内除了path本身外没有任何引用可以写入path所在的locations。因此，我们只需要考虑path中含有dereference的loan即可。

先考虑path仅含一个dereference的情形，不失一般性，考虑path为*a的loan即可：

• 对于&'r *a，其中a = &'a lvalue，根据约束3有'a : 'r，因此根据针对&'a lvalue的borrow check，在lifetime'r内不允许通过lvalue写入*a
• 对于&'r *a或&'r mut *a，其中a = &'a mut lvalue，同理可知在lifetime'r内不允许通过lvalue访问*a
• 若a本身又是reborrow，即lvalue中含有dereference，则再次运用上述推理即可

由此可知borrow check算法在此种情形下的正确性。实际上lifetime推导算法中的约束3，正是为了保证borrow check算法的正确性而设置，我们看下面这个例子：

let new;
{
    let old = &mut x;   // --+ lifetime of `old`
    new = &*old;        //   |
}                       //   |
x = x0;                 //   | ERROR! conflict with `&mut x`
use(new);               //   |
// <-------------------------+

若没有约束3，&mut x的lifetime限制在old的作用域内，则borrow checker无法发现x = x0与new这个shared borrow冲突，因为字面上new引用的是*old而不是x。

---

下面我们考虑path含有多个dereference的情形，不失一般性，考虑path为**a的loan即可，这将说明约束3中的supporting prefix这个条件是怎么来的。

第一种情况，a = &'a mut b，b = &'b mut c：

 a
 ↓ &'a mut
*a
 ↓ &'b mut
**a     <-- &'r **a / &'r mut **a

首先，根据上一节的讨论我们需要'b : 'r，保证对c的访问不与loan&'r **a或&'r mut **a冲突。此外，我们还需要保证不能通过b产生对**a的与loan冲突的访问，这就要求'a : 'r，从而在loan的lifetime内我们无法访问b从而也就无法通过b访问**a。

实际上，假如约束3不引入'a : 'r这个约束条件，即'a可能小于'r，则我们可以通过*b = d修改**a的值，从而违反borrow规则。例如在下列代码中，因为borrow checker无从了解*b = 2与&mut **a冲突，必须引入约束3才能保证*b = 2被borrow checker拒绝。

let mut c = 1;
let mut b = &mut c;
let d;
{
    let a = &mut b;     // --+ lifetime of `a` and `&mut b`
    d = &mut **a;       //   |
}                       //   |
*b = 2;                 //   | ERROR! conflict with `&mut b`
println!("{}", d);      //   |
// <-------------------------+

第二种情况，a = &'a b，b = &'b mut c：

 a
 ↓ &'a
*a
 ↓ &'b mut
**a     <-- &'r **a

此时合法的loan只有&'r **a，若要求'a : 'r，则我们只能够通过b对**a进行读取，不会和loan冲突。若不要求'a : 'r，则有可能通过b对**a进行写入，这是违反borrow规则的。这说明约束3保证了这种情况下borrow check的正确性。

第三种情况，a = &'a b或a = &'a mut b，b = &'b c：

 a
 ↓ &'a / &'a mut
*a
 ↓ &'b
**a     <-- &'r **a

此时合法的loan只有&'r **a，而通过b只能读取**a，不会违反borrow规则，因此不需要要求'a : 'r，实际上约束3也没有要求'a : 'r。

综上所述，可以看出约束3中只考虑path的supporting prefix，对每个形如*p的supporting prefix要求p的lifetime大于'r，恰好可以保证borrow check算法在loan的path中含有dereference时的正确性，而又没有引入不必要的约束条件。至此，我们就完整地说明了borrow check算法的正确性，整个lifetime和borrow check系统的设计还是比较巧妙的，只看RFC 2094的文本很难完整地把握其中的细节。