Chapter 2: 借用チェッカーの内部動作
学習目標
- 借用チェッカーのアルゴリズムを理解する
- Non-Lexical Lifetimes (NLL) の仕組みを学ぶ
- MIR（Mid-level IR）での解析過程を理解する
- エラーメッセージの生成プロセスを学ぶ
- コンパイラがどのように所有権を検証するか深掘りする
---
2.1 借用チェッカーの役割
2.1.1 コンパイルパイプライン
ソースコード
│
▼ (Lexer/Parser)
AST（抽象構文木）
│
▼ (HIR Lowering)
HIR（High-level IR）
│
▼ (Type Checking)
THIR（Typed HIR）
│
▼ (MIR Building)
MIR（Mid-level IR） ← 借用チェッカーはここで動作
│
▼ (Borrow Checking)
検証済みMIR
│
▼ (LLVM IR Generation)
LLVM IR
│
▼ (LLVM)
機械語
2.1.2 MIR（Mid-level Intermediate Representation）
// ソースコード
fn example() {
let mut x = 0;
let y = &mut x;
*y += 1;
}
// MIR（簡略化）
fn example() -> () {
let mut _0: ();
let mut _1: i32;
let mut _2: &mut i32;
bb0: {
_1 = const 0_i32;
_2 = &mut _1;
*_2 = Add(move (*_2), const 1_i32);
return;
}
}
---
2.2 Non-Lexical Lifetimes (NLL)
2.2.1 Lexical Lifetimes（Rust 2015）
// Rust 2015: エラー
fn example() {
let mut s = String::from("hello");
let r = &s;
// rはここまで有効（スコープ全体）
s.push_str(" world"); // エラー！rが存在する
println!("{}", r);
}
問題点：
- スコープベース（レキシカル）
- 参照の実際の使用期間を考慮しない
- 不必要に制限的
2.2.2 Non-Lexical Lifetimes（Rust 2018+）
// Rust 2018: OK
fn example() {
let mut s = String::from("hello");
let r = &s;
println!("{}", r); // rの最後の使用
// rはここで終了
s.push_str(" world"); // OK！
}
改善点：
- データフロー解析ベース
- 参照の実際の使用期間を追跡
- より自然なコード
---
2.3 借用チェックのアルゴリズム
2.3.1 ローン（Loan）の概念
let mut x = 5;
let r = &x; // Loan開始: x から r へ
// x は "貸し出し中"
println!("{}", r); // Loan使用
// rの最後の使用 → Loan終了
ローンの種類：
Shared Loan（共有ローン）
- &T を作成
- 複数同時に存在可能
- 元の値への書き込みを禁止
Mutable Loan（可変ローン）
- &mut T を作成
- 排他的（1つのみ）
- 元の値へのアクセスを完全に禁止
2.3.2 制約生成
fn example<'a>(x: &'a i32) -> &'a i32 {
let y = x;
y
}
// コンパイラが生成する制約
// 'x: ライフタイムof x
// 'y: ライフタイムof y
//
// 制約:
// 'y ⊇ 'x （yはxと同じかそれ以上生きる）
// 戻り値のライフタイム = 'y
2.3.3 到達可能性解析
Control Flow Graph (CFG)：
fn example(condition: bool) {
let mut x = 5;
let r = &x; // Loan開始
if condition {
println!("{}", r); // 経路1: rを使用
} else {
// 経路2: rを使用しない
}
x = 10; // ここでxに書き込めるか？
}
// 解析:
// 経路1: r が使用される → Loan が到達
// 経路2: r が使用されない → Loan は到達しない
//
// 結論: 経路1でエラー
---
2.4 ポーリーアナ解析（Polonius）
2.4.1 旧来の借用チェッカーの問題
// Rust 2018 でもエラーになるケース
fn get_default<'m, K, V>(
map: &'m mut HashMap<K, V>,
key: K,
) -> &'m mut V
where
K: Clone + Eq + Hash,
V: Default,
{
match map.get_mut(&key) {
Some(value) => value,
None => {
map.insert(key.clone(), V::default());
map.get_mut(&key).unwrap()
}
}
}
// エラー！mapが借用中なのに再度借用している
2.4.2 Polonius の改善
ポイント：
- ローンではなく「起源（Origin）」を追跡
- より精密なデータフロー解析
- 将来のRustでデフォルトになる予定
旧来の借用チェッカー:
- ローンベース
- 保守的（安全側に倒す）
Polonius:
- 起源ベース
- より精密
- 上記のコードも受理
---
2.5 エラーメッセージの生成
2.5.1 エラー診断の仕組み
let s = String::from("hello");
let r = &s;
drop(s);
println!("{}", r);
エラーメッセージ：
error[E0505]: cannot move out of `s` because it is borrowed
--> src/main.rs:3:10
|
2 | let r = &s;
| -- borrow of `s` occurs here
3 | drop(s);
| ^ move out of `s` occurs here
4 | println!("{}", r);
| - borrow later used here
生成プロセス：
1. 制約違反を検出
2. 関連する位置を特定
- 借用の発生位置
- 移動の発生位置
- 借用の使用位置
3. ユーザーフレンドリーなメッセージを構築
4. 修正案を提示（可能な場合）
2.5.2 修正案の自動生成
let s = String::from("hello");
drop(s);
エラーメッセージ：
error[E0382]: borrow of moved value: `s`
--> src/main.rs:3:14
|
1 | let s = String::from("hello");
| - move occurs because `s` has type `String`,
| which does not implement the `Copy` trait
2 | drop(s);
| - value moved here
3 | let r = &s;
| ^^ value borrowed here after move
help: consider cloning the value if the performance cost is acceptable
|
2 | drop(s.clone());
| ++++++++
---
2.6 借用チェッカーの内部データ構造
2.6.1 ローンパス（Loan Paths）
struct Point {
x: i32,
y: i32,
}
let mut p = Point { x: 1, y: 2 };
let r1 = &p.x; // ローンパス: p.x
let r2 = &p.y; // ローンパス: p.y (独立)
// p.x と p.y は独立したパス → 両方借用OK
パスの階層：
p (全体)
├─ p.x (フィールド)
└─ p.y (フィールド)
ルール:
- 子パスのローンは親パスに影響
- 兄弟パス同士は独立
2.6.2 ライフタイム推論
fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
if x.len() > y.len() { x } else { y }
}
// コンパイラの推論:
// 'a = min(x のライフタイム, y のライフタイム)
推論アルゴリズム：
1. 全てのライフタイムに変数を割り当て
2. 制約を生成
3. 制約を解く（最小不動点アルゴリズム）
4. 矛盾があればエラー
---
2.7 高度な借用パターン
2.7.1 分割借用（Split Borrowing）
let mut arr = [1, 2, 3, 4, 5];
let (left, right) = arr.split_at_mut(2);
// left と right は独立した可変参照
内部実装：
pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
let len = self.len();
let ptr = self.as_mut_ptr();
unsafe {
(
slice::from_raw_parts_mut(ptr, mid),
slice::from_raw_parts_mut(ptr.add(mid), len - mid),
)
}
}
// unsafe を使ってメモリが重複しないことを保証
2.7.2 リバッファリング（Reborrowing）
fn foo(s: &mut String) {
bar(&mut *s); // リバッファ
// ^^
// 明示的なデリファレンス
// sはまだ使える
s.push_str("!");
}
fn bar(s: &mut String) {
s.push_str("bar");
}
---
2.8 まとめ
2.8.1 借用チェッカーの進化
Rust 1.0 (2015):
- Lexical Lifetimes
- 保守的だが単純
Rust 2018:
- Non-Lexical Lifetimes
- より賢いデータフロー解析
Future (Polonius):
- Origin-based analysis
- さらに精密
2.8.2 重要なポイント
---
練習問題
問題1
以下のコードがRust 2015ではエラーだがRust 2018ではOKな理由を説明しなさい。let mut s = String::from("hello");
let r = &s;
println!("{}", r);
s.push_str(" world");
問題2
分割借用が安全である理由を借用チェッカーの観点から説明しなさい。---