02-所有权系统的计算机科学基础

所有权系统的计算机科学基础

前置问题

1. 如果 C 语言的 free() 是手动调用，Java 的释放由 GC 自动执行，那么 Rust 的释放是如何做到既不需要手动调用、又不需要 GC 的？编译器做了什么？
2. 当你写 let b = a; 之后不能再使用 a，编译器追踪这个”不可用”状态的底层机制是什么？类似什么样的数学形式系统？
3. 一个值的”生命周期”究竟是如何在编译时计算的？编译器用什么数据结构来表示”变量 x 在程序的每一行是否存活”？

---

1. 从类型论到所有权

1.1 Affine 类型理论与线性逻辑

Rust 的所有权系统根植于数理逻辑中的 线性逻辑（Linear Logic）。Jean-Yves Girard 在 1987 年提出的线性逻辑中，命题被视为”资源”而非永恒的真理——每个命题恰好被使用一次。

在线性逻辑中：

A ⊸ B   — 线性蕴涵：消耗 A 这个资源来产生 B
!A      — 指数模态：A 可以被重复使用任意次（类传统逻辑）

Rust 的类型系统与之对应：

线性逻辑概念	Rust 中的对应
线性变量（用一次）	所有权类型 T（默认）
指数模态（用多次）	Copy trait — 可”复制”而非移动
线性蕴涵 A ⊸ B	函数 fn f(x: T) -> U 消耗输入
没有回收的线性和	Drop 销毁

这就是为什么 Rust 被称为 affine 类型系统（affine = 线性逻辑的”至少一次”约束放宽为”最多一次”）。

1.2 所有权在类型论中的形式化

用形式化符号表示所有权规则：

$\Gamma ,x:T⊢x:T\text{(变量使用，前提是 x 在上下文 }\Gamma \text{ 中且未被消耗)}$

$\frac{\Gamma ⊢e_1:T\Gamma ,x:T⊢e_2:U}{\Gamma ⊢\text{let }x=e_1;e_2:U\text{(x 转移所有权到延续)}}$

$\frac{\Gamma ,x:T⊢e:U\text{且 }e\text{ 没有使用 }x}{\Gamma ⊢\text{ 在 let 之后 x 不再存活}}$

这些规则不是随意制定的 — 它们保证了 $\text{引用计数}=1$（在编译时可证明），从而允许编译时确定释放点。

---

2. 栈帧：所有权在硬件层面的体现

2.1 函数调用的机器码实现

fn main() {
    let s = String::from("hello");  // s 获得 hello 的所有权
    takes_ownership(s);             // s 移动到函数中
    // println!("{}", s);           // 编译错误：s 已被移动
}
 
fn takes_ownership(s: String) {
    println!("{}", s);
    // s 在这里离开作用域，被 drop
}

编译器生成的等价逻辑（概念代码，非实际汇编）：

; main:
    sub  rsp, 40            ; 分配 main 的栈帧
    ; String 内部: { ptr: *mut u8, len: usize, cap: usize } = 24 bytes
    ; ... 调用 String::from，将返回值放在 [rsp+8] 到 [rsp+28] ...
    mov  rdi, rsp+8         ; 将 String 的栈上内容作为参数传递
    call takes_ownership
    ; 从这里开始，栈上那些字节已经"不属于" main 了
    add  rsp, 40
    ret
 
; takes_ownership:
    push rbp
    mov  rbp, rsp
    sub  rsp, 32
    ; rdi 指向调用者的栈空间，其中是 String 的数据
    ; ... 使用 s ...
    ; 离开作用域前，调用 String 的 drop
    mov  rdi, [rbp+16]      ; 获取堆指针
    call __rust_dealloc     ; 释放堆内存
    mov  rsp, rbp
    pop  rbp
    ret

关键观察：所有权的”移动（move）“在硬件层面只是复制了栈上的 24 个字节（ptr + len + cap），原位置的数据变成”逻辑上未定义”。编译器通过静态分析保证不会再次读取这些字节。

2.2 移动 vs 复制：memcpy 的分界线

let a = [1u8; 1000];
let b = a;  // Copy: 编译器生成对全部 1000 字节的 memcpy
// a 仍然可用，因为 [u8; 1000] 实现了 Copy
let c = b;  // 再次 memcpy

let a = String::from("hello");
let b = a;  // Move: 仅 memcpy 栈上的 24 字节（ptr+len+cap）
// a 不可用，因为 String 没有实现 Copy，它管理了堆资源

; 对于 Copy 类型的小型类型（如 i32），编译器优化为寄存器操作
; let b = a; 其中 a 和 b 都是 i32
mov eax, [rsp+4]   ; 读取 a 的值到寄存器
mov [rsp+8], eax   ; 写入 b 的位置
; 两个位置都有效（Copy trait 保证）
 
; 对于 Move（String），同样的 memcpy 但编译器"遗忘"了源位置
movdqu xmm0, [rsp+8]    ; 16 bytes: ptr + partial len
movdqu [rsp+32], xmm0
mov  rax, [rsp+24]       ; last 8 bytes: rest of cap
mov  [rsp+48], rax
; 共 24 bytes 复制，之后源位置 rsp+8 被编译器视为无效

---

3. Drop 与确定性销毁

3.1 C++ RAII vs Rust Drop

C++ 的 RAII 和 Rust 的 Drop 都是”确定性析构”——对象在离开作用域时自动调用析构函数。但有关键区别：

C++ RAII 的缺陷：

// C++: 移动后原对象仍然有效但处于"空"状态
std::string a = "hello";
std::string b = std::move(a);
// a 现在是"有效但未指定"状态 → 仍然可以调用 a.size()（返回 0）
// 这意味着 C++ 的析构函数仍然会被调用，必须处理"被移动过"的状态
std::cout << a.size();  // 合法，但结果不确定

Rust 的改进：

let a = String::from("hello");
let b = a;
// a 不再有效，编译器禁止任何对 a 的使用
// a 的 Drop 不会被调用（只有 b 的 Drop 会执行）
// println!("{}", a.len());  // 编译错误！

3.2 Drop 的调用时机

fn example() {
    let a = Foo(1);  // a 的作用域从这里开始
    let b = Foo(2);  // b 的作用域从这里开始
    {
        let c = Foo(3);  // c 的作用域从这里开始
    }  // c 在这里 drop（作用域结束）
    let d = Foo(4);  // d 的作用域从这里开始
}  // drop 顺序：d → b → a（后进先出，栈语义）

在汇编层面，编译器在每个作用域出口处插入对 drop 的调用：

; 伪汇编：fn example() 的作用域出口处理
    ; ... body ...
    ; d 的 drop:
    lea  rdi, [rsp+16]   ; d 的地址
    call <Foo as Drop>::drop
    ; b 的 drop:
    lea  rdi, [rsp+8]    ; b 的地址
    call <Foo as Drop>::drop
    ; a 的 drop:
    lea  rdi, [rsp]      ; a 的地址
    call <Foo as Drop>::drop

---

4. GC 暂停与所有权：两种内存管理哲学

4.1 追踪式 GC 的工作原理

标记-清除算法：
1. [STOP THE WORLD] 暂停所有线程
2. 从根集（栈、寄存器、全局变量）开始追踪所有可达对象
3. 标记所有可达对象
4. 清除所有未标记对象（回收内存）
5. [RESUME] 恢复所有线程

GC 暂停时间取决于：

• 存活对象的数量（标记阶段）—— O(live)
• 堆的大小（清除阶段）—— O(heap_size)，但通过分代优化
• 碎片化程度（压缩阶段）

4.2 所有权如何避免 GC

Rust 的所有权系统在编译时静态证明：

1. 每个堆对象恰好有一个所有者（或通过 Rc/Arc 精确计数）
2. 所有者离开作用域时，堆对象唯一可达的路径消失 → 必须释放
3. 无循环引用时，不需要 GC（参考计数 = 0 立即释放）

以 C 代码对比：

// C: 手动分配和释放
char *buf = malloc(1024);
// ... 使用 ...
free(buf);  // 忘记调用 → 内存泄漏
            // 提前调用 → use-after-free
            // 重复调用 → double-free

Rust 编译器确保精确的一次释放：

// Rust: 编译器自动插入释放代码
let buf = Box::new([0u8; 1024]);
// ... 使用 ...
// 编译器在此自动插入 Box::free 调用

---

5. 借用检查器作为定理证明器

5.1 借用规则的数学描述

借用检查器本质上是一个轻量级定理证明器，它验证程序的资源使用满足 affine 类型规则。

形式化描述（简化版）：

设 $\text{liveness}(v)$ 为变量 $v$ 在程序点存活的时间区间集合。
设 $\text{borrow}(r)$ 为引用 $r$ 的生命周期。

核心不变量：

$\forall \text{ 可变借用 }r:|\{r^{\prime }\mid \text{borrow}(r^{\prime })\text{ overlaps with }\text{borrow}(r)\}|=1$

即可变借用期间，没有其他借用（可变或不可变）与之重叠。

$\forall x:|\{r\mid r\text{ is a mutable borrow of }x\text{ and }r\text{ is live}\}|\le 1$

这是经典的”读者-写者锁”在编译时而非运行时的表达。

5.2 借用检查实现：位向量抽象

编译器使用基于位向量的数据流分析来追踪每个变量的借用状态：

每个变量在每个程序点有一个状态:
  - NotBorrowed    (00)
  - SharedBorrwed  (01)  可以被多个 & 借用
  - MutBorrowed    (10)  被一个 &mut 独占

借用检查器遍历 MIR（Mid-level Intermediate Representation）的控制流图，传播这些状态并检查冲突。

5.3 借用检查器不能证明的属性

借用检查器是保守的（sound but not complete）：

• 如果它说”安全” → 确实安全
• 如果它说”不安全” → 可能安全也可能不安全（拒绝了一些合法程序）

这就是 unsafe 存在的根本原因：程序员可以用 unsafe 证明借用检查器无法自动证明的属性。

---

6. ASM 深度分析：移动、复制、克隆

6.1 Move 的汇编（小类型）

let x: i32 = 42;
let y = x;  // Move (Copy trait): i32 实现了 Copy

; 两者完全相同，编译后不可区分
mov dword ptr [rsp+4], 42   ; x = 42
mov eax, dword ptr [rsp+4]  ; y = x (x 依然有效，因为 i32: Copy)
mov dword ptr [rsp+8], eax

6.2 Move 的汇编（非 Copy 类型）

let s1 = String::from("hello");
let s2 = s1;  // Move: String 不是 Copy

; String 的栈上部分：{ ptr(8), len(8), cap(8) }
; alloc::string::String::from 调用后，返回值在 rax, rdx, rcx
; 假设返回约定：rax=ptr, rdx=cap, rcx=len
mov [rsp+8],  rax    ; s1.ptr
mov [rsp+16], rcx    ; s1.len
mov [rsp+24], rdx    ; s1.cap
; s1 的值现在在栈上
 
; let s2 = s1; — 这仅仅是一个 24 字节的 memcpy
mov rax, [rsp+8]
mov [rsp+32], rax
mov rax, [rsp+16]
mov [rsp+40], rax
mov rax, [rsp+24]
mov [rsp+48], rax
; 编译器此后将 [rsp+8..rsp+28] 视为未初始化/无效
; 只有 s2 的 drop 会在作用域出口处被调用

6.3 Clone 的汇编

let s1 = String::from("hello");
let s2 = s1.clone();  // Clone: 显式复制所有数据（包括堆数据）

; Clone 需要：
; 1. 分配新的堆空间：call __rust_alloc
; 2. 复制堆数据：memcpy
; 3. 更新 s2 的 ptr/len/cap
; 这是一个昂贵的操作，尤其是对于大型数据
 
; s2 = s1.clone() 的简化汇编：
mov  rdi, [rsp+16]     ; s1.len = 要分配的大小
call __rust_alloc      ; 分配堆内存，返回指针在 rax
mov  [rsp+40], rax     ; s2.ptr = 新分配的堆指针
mov  rdx, [rsp+8]      ; s1.ptr（旧堆指针）
mov  rcx, [rsp+16]     ; s1.len
mov  rdi, rax          ; 目标 = s2.ptr
mov  rsi, rdx          ; 源 = s1.ptr
rep  movsb             ; memcpy(s2.ptr, s1.ptr, s1.len)
mov  rax, [rsp+16]
mov  [rsp+48], rax     ; s2.len = s1.len
mov  rax, [rsp+24]
mov  [rsp+56], rax     ; s2.cap = s1.cap

---

7. 所有权与并发安全

7.1 类型驱动的线程安全

Send:  所有权可以在线程间安全转移
Sync:   引用可以在线程间安全共享

(T: Send)  ⇔  (将 T 交给另一个线程不会造成数据竞争)
(T: Sync)  ⇔  (&T 可以同时存在于多个线程)

这是 Rust 将并发安全性静态化的关键机制。编译器在编译时检查这些 trait，不需要运行时检测。

7.2 所有权隔离的实际效果

use std::thread;
 
let data = vec![1, 2, 3];
thread::spawn(move || {
    // data 的所有权移动到了新线程
    println!("{:?}", data);
});
// 此处不能再访问 data — 编译时保证

这保证了如果 data 不是 Sync 的（Vec<i32> 不是），主线程和新线程永远不会同时访问它。

---

8. 内存安全性证明的框架

8.1 RustBelt 项目（形式化验证）

RustBelt 使用分离逻辑（Separation Logic）交互式证明工具 Coq 对 Rust 类型系统进行了形式化证明。其核心结论是：

如果程序不使用 unsafe 关键词，则不会发生内存不安全。

8.2 关键不变量的直观解释

$\text{safe Rust}=\text{所有内存访问满足:}$

1. 无悬挂引用: $\forall$ 指针解引用 $\ast p$, $p$ 指向的内存仍在存活期
2. 无多次释放: 每个堆分配恰有一个所有者
3. 无数据竞争: 两个线程不会同时（一个写、一个）访问同一内存
4. 无无效解引用: $p$ 不为 null 且对齐正确

---

本章考查

概念考查（每题2分，共20分）

1. Rust 的所有权系统基于哪种类型理论？

   • A) 多态λ演算（System F）
   • B) Affine类型理论（线性逻辑的变体）
   • C) 依值类型理论
   • D) 会话类型理论

2. 在汇编层面，Rust 的”移动（move）“本质上是什么操作？

   • A) 改变虚拟内存映射
   • B) 调用 memmove 系统调用
   • C) 栈上数据的 memcpy，编译器标记源位置为无效
   • D) 修改页表项

3. Drop 在离开作用域时的调用顺序是什么？

   • A) 按变量声明的顺序（先声明先 drop）
   • B) 按变量声明的逆序（后声明先 drop，LIFO）
   • C) 随机顺序
   • D) 按变量大小排序

4. C++ 的 std::move 和 Rust 的 move 的区别是：

   • A) 完全一样
   • B) C++ 移动后原对象仍然可访问（处于”有效但未指定”状态），Rust 移动后原变量编译时不可访问
   • C) Rust 移动涉及引用计数
   • D) C++ 移动更快

5. 为什么 GC 会有”暂停”（stop-the-world）？

   • A) GC 需要停止所有线程以遍历对象图，防止在标记过程中对象图被修改
   • B) GC 需要重新启动操作系统
   • C) GC 需要等待磁盘 I/O 完成
   • D) GC 需要将内存内容写入磁盘

6. 借用检查器本质上是：

   • A) 运行时检查器，在每个访问前验证
   • B) 编译时的轻量级定理证明器，验证资源使用满足 affine 类型规则
   • C) 一个单独的系统守护进程
   • D) 一个 CPU 硬件特性

7. Copy trait 在汇编层面的语义是：

   • A) 共享堆内存，使用引用计数
   • B) 允许在 memcpy 后源变量仍然有效
   • C) 阻止任何复制操作
   • D) 将数据从栈移动到堆

8. 以下哪个不变量是 Rust 安全子集保证的？

   • A) 程序不会死锁
   • B) 程序时间复杂度为 O(n)
   • C) 不存在 use-after-free 和 double-free
   • D) 程序不会 panic

9. String 在栈上的大小是：

   • A) 取决于字符串长度
   • B) 24 字节（在 64 位系统上：ptr + len + cap）
   • C) 8 字节（仅一个指针）
   • D) 不确定

10. 当 let b = a; 中 a 是 String 时，a 的 Drop::drop 是否会被调用？

    • A) 会，先 drop a，再 drop b
    • B) 会，在 b 被 drop 之后
    • C) 不会，编译器将 a 视为逻辑上”已移动”，只有 b 的 drop 会被调用
    • D) 取决于运行时条件

点击查看答案

1. B — Rust 的所有权系统源自 affine 类型理论，是线性逻辑的”最多一次使用”变体。
2. C — 移动在汇编层面就是 memcpy 栈上数据 + 编译器标记源位置无效。堆上的数据不移动。
3. B — Drop 遵循栈语义（LIFO）：后声明的变量先销毁（后进先出）。
4. B — C++ 移动后原对象仍在作用域且可访问，Rust 移动后原变量在编译时即不可访问。
5. A — GC 必须确保在标记对象图时，对象引用不被并发修改，因此需要暂停线程。
6. B — 借用检查器在编译时作为静态分析运行，验证资源使用约束。
7. B — Copy 类型在 memcpy 后源数据仍然有效，因为不涉及资源管理（无 Drop）。
8. C — 安全的 Rust 保证无内存安全错误（无悬挂引用、无多次释放、无数据竞争）。
9. B — String 包含指向堆数据的指针、长度、容量，在 64 位系统共 24 字节。
10. C — 编译器确保只有移动目标（b）被 drop，源变量（a）的 drop 不会被调用。

判断正误（每题2分，共20分）

1. Rust 的 move 操作在 CPU 层面是一个昂贵的系统操作，比 C++ 的 std::move 慢很多。
2. 所有权的核心思想是每个值在内存中的存在在编译时被精确追踪，一个值一旦被”移动”，旧的位置在编译时即不可访问。
3. GC（垃圾回收）和所有权系统都是内存管理的策略，两者可以在同一语言中共存。
4. String 实现了 Copy trait。
5. 由于栈向低地址增长，函数参数在栈上的地址比局部变量更低。
6. 借用检查器的分析是流敏感的（flow-sensitive），它知道在程序的不同位置变量的状态不同。
7. Drop 调用顺序与构造顺序相同。
8. 所有权系统消除了所有类型的内存错误，包括 panic 和逻辑错误。
9. let y = x.clone() 在汇编层面涉及堆内存分配和 memcpy，而 let y = x（move）只涉及栈上数据的 memcpy。
10. Rust 中 Copy 类型的赋值后，源变量在编译器视角仍然存在且有效。

点击查看答案

1. 错误 — Rust move 只是栈上 memcpy + 编译器标记，零运行时开销；C++ move 可能触发复杂的移动构造函数。
2. 正确 — 编译器通过所有权分析精确追踪值的”活跃”状态。
3. 正确 — 可以使用 Rc（引用计数，类似轻量级 GC）+ 所有权系统共存。
4. 错误 — String 管理堆资源，不能 Copy（否则出现双重释放），只实现了 Clone。
5. 错误 — 栈向低地址增长，函数参数在调用者的栈帧中（更高的地址，先压栈）。
6. 正确 — 借用检查器在程序的不同 CFG 点跟踪不同的借用状态。
7. 错误 — Drop 顺序是声明的逆序（LIFO）：后声明先销毁。
8. 错误 — 所有权系统防止内存安全错误，但不防止逻辑错误或 panic。
9. 正确 — clone 分配新堆内存并复制内容，move 仅复制栈上元数据。
10. 正确 — Copy 类型的值在 memcpy 后原位置仍然有效。

代码分析（每题3分，共15分）

1. 以下代码的编译结果是什么？

let s1 = String::from("hello");
let s2 = s1;
println!("{}", s1);

A) 正常输出 “hello”
B) 运行时报错
C) 编译错误：s1 已被移动
D) 输出 “hello” 但 s1 变成空字符串

点击查看答案

**C** — `String` 不是 `Copy`，`let s2 = s1` 将所有权从 s1 移动到 s2，编译器禁止后续使用 s1。

2. 以下代码中，drop 的顺序是什么？

fn main() {
    let a = D("A");
    let b = D("B");
    {
        let c = D("C");
    }
    let d = D("D");
}
// D 是一个在 drop 时打印自身名称的类型

A) A, B, C, D
B) C, D, B, A
C) D, B, C, A
D) C, B, A, D

点击查看答案

**B** — c 在内部大括号结束时 drop（最先）；然后 D, B, A 按逆声明顺序（LIFO）drop。

3. 这段代码为什么能编译通过？

let x = 42;
let y = x;
println!("{} {}", x, y);

A) 因为 i32 实现了 Copy trait，赋值后 x 仍然有效
B) 因为 Rust 自动克隆了 x
C) 因为 println! 宏有特殊处理
D) 因为编译器优化掉了移动

点击查看答案

**A** — `i32` 实现 `Copy` trait，memcpy 后源值仍有效，不涉及所有权转移。

4. 以下函数的汇编中，传递给 callee 的参数是如何放置的？

fn callee(data: [u8; 256]) {
    println!("{}", data.len());
}
fn caller() {
    let buf = [0u8; 256];
    callee(buf);
}

A) 传指针（8 字节）到 rdi
B) 将 256 字节复制到栈上（调用者的栈空间），传指针
C) 将 256 字节复制到 callee 的栈空间
D) 直接通过共享内存访问，无复制

点击查看答案

**B** — 大结构在 x86_64 System V ABI 中通过栈传递。调用者在自己的栈上分配空间，复制数据，传给 callee 一个指向该空间的指针。

5. 下列代码中 v 离开作用域时会发生什么？

fn main() {
    let v = vec![1, 2, 3, 4, 5];
}  // <-- 这里

A) 什么也不发生，栈帧被回收即可
B) 先调用 Vec 的 drop（释放堆上的数组内存），然后回收栈帧
C) 调用 GC 清理
D) 堆内存泄漏（因为没有显式 free）

点击查看答案

**B** — 编译器在作用域出口插入 `Vec::drop` 调用，释放堆内存，之后栈指针恢复。

编程大题（15分）

题目: 实现一个简单的 Arena（区域分配器），它持有所有分配的值的所有权，并在 Arena 被销毁时统一释放。这种模式展示了所有权的”严格树状结构”——父节点拥有子节点。

// 要求：
// 1. Arena::new() 创建一个新的 Arena
// 2. Arena::alloc(value: T) -> &mut T 在 Arena 内部存储 T 并返回可变引用
// 3. Arena 实现 Drop，在销毁时释放所有内部分配的值
// 4. 确保被分配的值的生命周期绑定到 Arena 上
// 5. 编写示例使用代码
 
use std::cell::RefCell;
 
struct Arena {
    // 提示：使用 RefCell<Vec<Box<dyn Any>>> 或 Vec<Box<dyn DropTrait>>
    // 或用 unsafe 手动管理原始内存块
    chunks: RefCell<Vec<Box<dyn std::any::Any>>>,
}
 
impl Arena {
    pub fn new() -> Self {
        // TODO
    }
 
    pub fn alloc<T: 'static>(&self, value: T) -> &mut T {
        // TODO: 将 value 装箱并存储，返回可变引用
        // 注意：生命周期绑定需要 unsafe 或巧妙设计
    }
}
 
impl Drop for Arena {
    fn drop(&mut self) {
        // TODO: 反转 chunks 保证正确的 drop 顺序
    }
}

点击查看答案

use std::cell::RefCell;
use std::any::Any;
 
struct Arena {
    chunks: RefCell<Vec<Box<dyn Any>>>,
}
 
impl Arena {
    pub fn new() -> Self {
        Arena {
            chunks: RefCell::new(Vec::new()),
        }
    }
 
    pub fn alloc<T: 'static>(&self, value: T) -> &mut T {
        let mut boxed = Box::new(value);
        let ptr: *mut T = &mut *boxed;
        // 将 Box 擦除类型后存储
        self.chunks.borrow_mut().push(boxed);
        // 安全：我们存储了 Box 的所有权，引用的生命周期与 Arena 绑定
        unsafe { &mut *ptr }
    }
}
 
impl Drop for Arena {
    fn drop(&mut self) {
        // 必须反向销毁以满足依赖关系
        let mut chunks = self.chunks.borrow_mut();
        chunks.reverse();  // 后分配的先释放
        // Box<dyn Any> 的 drop 会自动释放内部的 T
        // 不需要手动操作，Vec 的 drop 会处理
    }
}
 
// 使用示例
fn main() {
    let arena = Arena::new();
    let x = arena.alloc(42i32);
    let y = arena.alloc(String::from("hello"));
    *x = 100;
    println!("x={}, y={}", x, y);
    // arena 离开作用域时自动释放所有分配
}

设计要点：

1. RefCell 允许多次 alloc（获取 &mut T），但 Arena 自身是 &self（共享引用）
2. 生命周期 &mut T 实际上与 Arena 的借用关联，Rust 会防止 use-after-free
3. 反向 drop 确保依赖顺序（但在这里简单类型无关紧要）
4. 这是一个简化的实现；生产级 Arena 通常使用原始内存块 + UnsafeCell

填空题（每题1分，共5分）

1. Rust 的所有权系统基于 ____ 类型理论，该理论要求每个资源最多被使用 ____ 次。
2. 在硬件层面，栈的分配通过修改 ____ 寄存器实现，开销为 ____ 个 CPU 周期。
3. 当函数调用发生时，返回值通常通过 ____ 寄存器传递（在 x86_64 System V ABI 中）。
4. Copy trait 表示在 memcpy 后，源位置的数据仍然是 ____ 的。
5. 当值离开作用域时，编译器插入对 ____ trait 的 drop 方法调用。

点击查看答案

1. affine，一
2. rsp（栈指针），1
3. rax
4. 有效（valid）
5. Drop

代码补全（共5分）

1. 实现 Drop trait 打印销毁信息（2分）：

struct Resource {
    id: u32,
}
 
impl ____ for Resource {
    fn ____(&mut self) {
        println!("Resource {} dropped", self.id);
    }
}
 
fn main() {
    let _r = Resource { id: 1 };
    // 此处 _r 离开作用域，自动调用 drop
}

点击查看答案

impl Drop for Resource {
    fn drop(&mut self) {
        println!("Resource {} dropped", self.id);
    }
}

2. 使用 std::mem::drop 提前释放值（1分）：

let s = String::from("hello");
____;  // 提前释放 s
// println!("{}", s);  // 编译错误：s 已被移动

点击查看答案

drop(s);

3. 在 MIR 层面，借用检查器追踪变量的”存活”状态。补全以下描述（2分）：

// 借用检查器在编译器内部的 ____ 阶段运行
// 它遍历 ____ 图来追踪每个变量的借用状态
// 当发现冲突时，生成 ____ 错误（而非运行时 panic）

点击查看答案

// 借用检查器在编译器内部的 MIR 阶段运行
// 它遍历 控制流（CFG / Control Flow Graph） 图来追踪每个变量的借用状态
// 当发现冲突时，生成 编译（compile-time） 错误（而非运行时 panic）

---

本章小结

所有权的本质不是语法糖，而是一种基于 affine 类型论的编译时资源追踪系统。理解其原理需要打通三个层次：

• 数学层：线性逻辑和 affine 类型保证了”最多一次使用”
• 编译器层：借用检查器是流敏感的控制流分析，在 MIR 上逐点追踪每个变量的存货和借用状态
• 硬件层：move = 栈上 memcpy + 编译器标记；drop = 编译器自动插入的释放调用；没有运行时开销

这解释了为什么 Rust 能在没有 GC 的情况下实现内存安全：编译器在程序运行前就证明了资源使用是良基的（well-founded）。

下一章：03-引用与生命周期的底层实现 — 生命周期作为程序点的集合，以及借用检查器如何证明它们之间的关系。

---

深度阅读：Ralf Jung et al., “RustBelt: Securing the Foundations of the Rust Programming Language” (POPL 2018); Niko Matsakis, “Non-Lexical Lifetimes” (RFC 2094)

---

练习

练习

题号	题目	链接	知识点
146	LRU 缓存	https://leetcode.cn/problems/lru-cache/	双向链表 + 哈希表
23	合并 K 个升序链表	https://leetcode.cn/problems/merge-k-sorted-lists/	链表、分治
21	合并两个有序链表	https://leetcode.cn/problems/merge-two-sorted-lists/	链表、递归
102	二叉树的层序遍历	https://leetcode.cn/problems/binary-tree-level-order-traversal/	BFS、队列
236	二叉树的最近公共祖先	https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/	递归、树