Rust从入门到精通

五月 14, 2024 [Rust] #Rust #obsidian

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语法：

Move Semantics and References

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

首先是整体的语义：

然后是Reference的语义：

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

最后是Slice的语义：

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

Data Structures

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

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

1
2
3
4
5
struct A {
a: String,
b: i32,
c: u64,
}

创建Struct对象的方式如下：

1
2
3
4
5
A {
a: str,
b: x,
c: y,
}

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

1
2
3
4
5
A {
a,
b,
c: y,
}

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

1
2
3
4
let a_2 = A {
a: str,
..a_1
}

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

1
struct Point(i32, i32, i32,);

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

1
struct U; // now U is also a constant

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

1
2
3
4
5
6
7
8
9
10
11
impl A {
// A method, invoked by a.meth()
fn meth(&self) -> bool {
true
}
// A function, invoked by A::func()
fn func() -> bool {
false
}
}

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

1
2
3
4
5
6
enum Animal {
Cat { name: String, weight: f64 },
Dog(String, f64),
Horse = 100,
Sheep,
}

一个非常常用的Enum是Option<T>：

1
2
3
4
enum Option<T> {
Some(T),
None
}

Module System and Visibility

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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的规则如下：

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

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

若声明Module时不指定定义，如mod a;，则会从同名文件a.rs查找该Module，源文件的路径和Module的Path吻合，例如crate::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。

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

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

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：

1
2
3
4
5
6
7
8
9
10
11
12
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
}
}

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

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

首先来看Type Parameter：

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

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

Dynamic Dispatching

Rust通过trait object进行Dynamic Dispatching：

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

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

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

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

Pattern Matching

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

1
2
3
4
match expr {
pattern => expr,
_ => (),
}

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

1
2
3
4
match expr {
pattern1 | pattern2 => {},
_ => {}
}

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

1
2
3
4
5
6
loop {
match expr {
pattern1 | pattern2 => { body },
_ => break,
}
}

Pattern还能用来进行destructuring：

Pattern的语法如下：

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

More on Move Semantics

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

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

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

Functions and Closures

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

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

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

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

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

Smart Pointers

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

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

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

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

我们接下来考察interior mutability：

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

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
pub trait ToOwned {
type Owned: Borrow;
fn to_owned(&self) -> Self::Owned;
}

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

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

1
2
3
4
5
6
7
pub enum Cow<'a, B>
where
B: 'a + ToOwned + ?Sized,
{
Borrowed(&'a B),
Owned(::Owned),
}

Error Handling

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

1
2
[profile.release]
panic = 'abort'

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

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

1
2
3
4
enum Result<T, E> {
Ok(T),
Err(E),
}

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

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

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

Writing Tests

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

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

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

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

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

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

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

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

More on Cargo

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

1
2
[profile.release]
opt-level = 3

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

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

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

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

1
2
3
4
5
6
7
[workspace]
members = [
"bin-crate",
"lib-one",
"lib-two",
]
1
2
3
[dependencies]
lib-one = { path = "../lib-one" }

Part II. Advanced Rust

Pinned Pointers

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

注意: 使用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<i32>的invariant，Pin<i32>可以视同普通的P：

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

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

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

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

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

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

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

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

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

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

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

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

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

Concurrency

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

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

Shared Memory

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

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

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

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

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

Message Passing

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

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

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

Receiver<T>负责接收消息：

Attributes

Attribute分为两种：

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

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

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

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

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

常用的predicate如下：

crate的编译类型包括：

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

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

Hygienic Macro

首先，我们定义token tree:

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

Macros by Example

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

1
2
3
4
5
6
macro_rules! $name {
(expansion};
$rule1;
//...
$ruleN
}

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

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

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

textual scope的规则如下：

path scope的规则如下：

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

1
2
#[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：

1
2
3
4
5
6
7
8
9
10
macro_rules! using_a {
($e:expr) => {
{
let a = 42;
$e
}
}
}
let four = using_a!(a / 10);

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

Procedural Macros

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

1
2
[lib]
proc-macro = true

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

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

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

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

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是跨平台的：

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

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

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

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给外部使用：

Exception Safety

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

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

Rust引入了两个Auto TraitRefUnwindSafe和UnwindSafe：

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

综上所述：

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

Type Layout

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

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

现在来详细解释C representation：

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

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

Unsafe Rust

Definition of Unsafe

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

unsafe关键词有三种用途：

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

Semantics of Unsafe

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

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

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

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

1
2
3
4
5
pub struct Vec<T> {
ptr: *mut T,
cap: usize,
len: usize,
}

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

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

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

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机制的一种扩充：

borrow的基本原则是明确的：

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

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

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

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总结如下：

ImmutableMutable
SharedShared BorrowInteriorly Mutable Shared Borrow
UniqueUnique Immutable BorrowMutable Borrow

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

例如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进行捕获：

1
2
3
4
5
6
7
8
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;

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

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

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

此外，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：

所谓的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的行为也是有其适用范围的：

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

1
2
3
4
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的规则很简单：

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

注意有时实际上可能发生reborrow产生的新reference尚且存活，旧的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<T>实际上都附带有lifetime。我们知道，type variable一般用大写字母表示，如T, U。在Rust代码中，我们用'加上小写字母表示lifetime variable，例如'a, 'foo，引用类型和trait object类型完整地写出应该是：

我们知道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。

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

1
2
3
4
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，我们将这种关系称为'aoutlive'b，记作'a : 'b。

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

这条规则可以这样理解，考虑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就表示该引用可以有效使用的范围。

下面再看这个例子：

1
2
3
4
5
6
7
let new;
{
let old = &mut x; // --+ lifetime ofold``
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的不足：

1
2
3
4
5
6
7
8
fn foo() {
let mut data = vec![1, 2, 3];
let slice = &mut data[..]; // <-+ lifetime ofslice``
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规则的代码，例如以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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：

此外，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）：

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

在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的例子能很好地说明这个问题。

假设我们有如下代码：

1
2
3
4
5
6
7
8
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如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
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规则也要相应增加：

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

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

1
2
3
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：

假设上述函数替换为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这个词可以指代两种概念：

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

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

综上可知，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：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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：

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

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

其实上述两条规则已经涵盖了所有可以含有&'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：

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 -> *) ：

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

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<T>会被视为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：

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

对于trait object，有两套规则：

default trait object lifetime bound的规则如下：

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

Type Coercion and Type Cast

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

TypeVariance in'aVariance inT
&'a Tcovariantcovariant
&'a mut Tcovariantinvariant
*const Tcovariant
*mut Tinvariant
[T]and[T; n]covariant
fn() -> Tcovariant
fn(T) -> ()contravariant
std::cell::UnsafeCell<T>invariant
std::marker::PhantomData<T>covariant
dyn Trait<T> + 'acovariantinvariant

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

下面逐一考察以上规则：

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

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

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

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

具体到Rust，就是：

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

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

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

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

再考虑A <: B的由来：

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

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

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

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

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

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

注意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：

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

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

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

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

Reborrow Rules

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

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

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

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

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的，我们来看一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 wanda``
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源码中隐式蕴含的语义：

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
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：

1
2
3
4
5
6
// P0
let a = &'b b;
// P1
...
// Pn
use(a);

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

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

定义4：

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

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

求解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：

1
2
3
4
5
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被重新赋值后：

1
2
3
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：

1
2
3
4
5
 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者后出栈，实际上即使这个约束不成立程序也可以是正确的。回顾此前用过的这个例子：

1
2
3
4
5
6
7
let new;
{
let old = &mut x; // --+ lifetime ofold``
new = &*old; // |
} // |
use(new); // |
// <-------------------------+

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

1
2
3
4
5
6
7
8
let new;
{
let old = &mut x; // --+ lifetime ofold``
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。

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

1
2
3
4
5
6
7
8
9
10
11
let mut u = 0;
let mut c = 1;
let mut b = &mut c;
let d;
{
let a = &mut b; // --+ lifetime ofaand&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：

1
2
3
4
5
6
7
 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语义实际上是保守的：

1
2
3
4
5
6
7
8
9
let mut x = (3, 4);
let new;
{
let old = &x; // --+ lifetime ofold``
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的例子可以说明这一点：

1
2
3
4
5
6
7
8
9
10
11
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：

lifetime的liveness要据此修改如下：

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

也就是说，如果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：

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

1
2
3
4
5
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：

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

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

以下操作属于shallow access：

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

以下操作属于deep access：

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

Borrow Check Reasoning

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

1
2
3
4
5
6
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：

上面第二点实际上揭示了另一条隐藏的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冲突，我们来考察这一规定的正确性：

我们上面只考虑了对于&'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即可：

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

1
2
3
4
5
6
7
8
let new;
{
let old = &mut x; // --+ lifetime ofold``` 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：

1
2
3
4
5
 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拒绝。

1
2
3
4
5
6
7
8
9
10
let mut c = 1;
let mut b = &mut c;
let d;
{
let a = &mut b; // --+ lifetime ofaand&mut b``` d = &mut **a; // |} // |*b = 2; // | ERROR! conflict with &mut b``println!("{}", d); // |// <-------------------------+`

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

1
2
3
4
5
 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：

1
2
3
4
5
 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的文本很难完整地把握其中的细节。

索引
Rust从入门到精通
Part I. Common Rust
- Basics
- Move Semantics and References
- Data Structures
- Module System and Visibility
- Parametric Polymorphism
- Dynamic Dispatching
- Pattern Matching
- More on Move Semantics
- Functions and Closures
- Smart Pointers
- Error Handling
- Writing Tests
- More on Cargo
Part II. Advanced Rust
- Pinned Pointers
- Concurrency
· Shared Memory
· Message Passing
- Attributes
- Hygienic Macro
· Macros by Example
· Procedural Macros
- External Block & External Function
- Exception Safety
- Type Layout
- Unsafe Rust
· Definition of Unsafe
· Semantics of Unsafe
Part III. The Essence of Rust
- Reference is Borrow
- Reborrow and Borrow Stack
- Lifetime Part I. What is Lifetime
- Lifetime Part II. Lifetime Parameter
- Lifetime Part III. Lifetime Polymorphic Types
- Lifetime Part IV. Advanced Features of Lifetime
- Type Coercion and Type Cast
- Reborrow Rules
- Lifetime Part V. Non-Lexical Lifetime
· Basic Algorithm
· Reasoning
· Avoiding Infinite Loops
· Drop Check
· Borrow Check Algorithm
· Borrow Check Reasoning