注意: 正確性は重視していない意訳なので、正確に知りたい人は原文を参照のこと
関連:
------
3. 詳細なデザイン
3-1. デザインの階層
階層に分けて今回のデザインを説明していく:
(1) 最初に、一つの関数内の制御フローに焦点を当てて、基本的なデザインの説明を行う
(2) 次に、無限ループを上手く扱えるように、制御フローを拡張する (3) 次に、dropckとRFC 1327で導入された#[may_dangle]属性を扱えるようにデザインを拡張する (4) 次に、問題ケース3で出てきたような、名前付けされたライフタイムパラメータを考慮するようにデザインを拡張する
(5) 最後に、借用チェッカの簡単な説明を行う
3-2. 階層0: 定義
まずは用語定義から (このRFCではMIRの用語の簡略版を使用): 左辺値(lvalue):
MIRの"左辺値"とは、あるメモリ位置に繋がるパス、のこと このRFCで使用する定義は次の通り:
code:rust
LV = x // local variable
| LV.f // field access
| *LV // deref
*の優先順位は低い
*a.b.cは、(*a).b.c、と解釈される
接頭辞群:
"左辺値の接頭辞群"とは、左辺値からフィールドとderefを除いて得られる、全ての左辺値のことを指す
*a.bの接頭辞群は、*a.bとa.b、aとなる
制御フローグラフ(CFG):
これはコンパイラが"HIR"(high-level IR)を変換することで生成される
このRFCで関心のある文は、以下の三つのカテゴリに収まる:
x = yのような代入:
複合的な右辺値は存在せず、各文は即座に実行可能な別々のアクションとなる
例: Rustのa = b + c + dは、temp0 = b + c; a = temp0 + dといったような二つのMIR命令にコンパイルされる
drop(lvalue)による左辺値の解放:
「lvalueに値が入っているかどうか」のチェックが実行時に必要となる
"精巧なドロップ"と呼ばれるMIR内のパスが、この変換を実施する
StorageDead(x)によるxのためのスタックストレージの解放:
これはLLVMに、スタックに割り当てられる値群が、同じスタックスロットを使用することを許容する それらの生存期間に重複がないなら
3-3. 階層1: 関数内での制御フロー
3-3-1. 実行可能な例
実行可能な例(Example 4)を使ってデザインを説明する。その後、デザインを(前節で取り上げた)三つの問題およびその他の興味深い例に適用する。
code:rust:Example4
let mut foo: T = ...;
let mut bar: T = ...;
let p: &T;
p = &foo;
// (0)
if condition {
print(*p);
// (1)
p = &bar;
// (2)
}
// (3)
print(*p);
// (4)
重要な点:
fooは、地点0と3でのみ借用されていると見做されるべき
barは、地点2と3
どちらも地点1と4では借用されていない (pがもう使用されていないので)
この例は以下のような制御フローグラフに変換可能。
復習: MIR内の制御フローグラフは「個々の文のリストと末尾の終止符を含む基本ブロック群」から構成される code:rust
// let mut foo: i32;
// let mut bar: i32;
// let p: &i32;
A
| |
| B v
| |
+-------------/
|
C v
制御フローグラフ内の特定の文ないし終止符を参照するためにBlock/Indexといった記法を用いる:
A/0はp = &fooを指す
B/4はgoto C
3-3-2. ライフタイムとは何か、そしてそれは借用チェッカとどのように相互作用するのか
初めは、ライフタイム群を制御フローグラフ内の地点の集合と考えることにする:
ライフタイムが地点Pを含むなら、それはそのライフタイムに紐付く参照群がPで有効なことを意味する
RFCの後の方で、この集合のドメインがスコーレム化(skolemized)されたライフタイムを含むように拡張する これは関数内で宣言された名前付きライフタイムに対応する
ライフタイムはMIR表現内の様々な場所で現れている: 変数(および一時変数、etc)の型は、ライフタイムを含む可能性がある
全ての借用式は、専用のライフタイムを有する
ライフタイムの名前を明示するようにExample4を拡張することが可能。
この例には三つのライフタイムがあって、それぞれを'p、'foo、'barと呼称する:
code:rust
let mut foo: T = ...;
let mut bar: T = ...;
let p: &'p T;
// --
p = &'foo foo;
// ----
if condition {
print(*p);
p = &'bar bar;
// ----
}
print(*p);
ライフタイム'pは変数pの型の一部で、pが安全に参照外し可能な制御フローグラフ内の範囲を示している。
それとは異なり'fooと'barは、それぞれfooおよびbarの借用のライフタイムを指している。
'fooや'barのような借用式に付随するライフタイムは、借用チェッカにとって重要:
これらは、制御フローグラフ内で、借用チェッカが制限を行使する範囲に対応している
このケースでは、どちらも共有借用(&):
借用チェッカは'fooの範囲では、fooが修正されることを防止する
'barとbarに関しても同様
もしこれが破壊的な借用(&mut)だったら、借用チェッカは、ライムタイム期間中のfooおよびbarに対する全てのアクセスを禁止する
'fooや'barの範囲を決めるための妥当な選択肢はいろいろとあるけれど、このRFCでは各借用が機能する中で最小限のライフタイムを選択するための推論アルゴリズムを説明している(i.e., プログラマに課される制限も最も少なくなる)。
Example4に当てはめると:
'fooの集合{A/1, B/0, C/0}となる(べき)
{B/1, .., B/4}は対象外
'barなら{B/3, B/4, C/0}
'pは'fooと'barの和集合
3-3-3. ライフタイム推論制約
推論アルゴリズムは、MIRを分析し制約のシリーズを生成することで動作する。
制約は以下の文法に従う:
code:rust
// A constraint set C:
C = true
| C, (L1: L2) @ P // 地点Pで、ライフタイムL1はライフタイムL2よりも長生きする
// A lifetime L:
L = 'a
| {P}
終端Pは制御フローグラフ内でのある地点を表し、記法'aは名前付きのライフタイム推論変数(e.g., 'p、'foo、'bar)を指す。
制約群が生成されたなら、推論アルゴリズムがそれを解決する:
これは不動点反復(fixed-point iteration)を通して行われる:
各ライフタイム変数は、最初は空集合
各制約は繰り返し走査され、全ての制約が満たされるようになるまでライフタイムは育っていく
3-3-4. 生存性
NLLがどう動作するのかを理解するためのキー要因の一つは、生存性を理解すること。 "生存性(liveness)"という用語はコンパイラ解析から生まれたものだが、十分に直観的。
「ある変数は、それが現在保持する値が後で使われる可能性があるなら、生存している」といえる。
これはExample4でとても重要。
code:rust
let mut foo: T = ...;
let mut bar: T = ...;
let p: &'p T = &foo;
// pは生きている: 値は次の行で使われるかもしれない
if condition {
// pは生きている: 値は次の行で使われる
print(*p);
// pは死んでいる: 値はもう使われることはない
p = &bar;
// pは生きている: 値は後で使用される
}
// pは生きている: 値は次の行で使われるかもしれない
print(*p);
// pは死んでいる: 値はもう使われない
変数pは、
プログラムの先頭で値が代入され、ifブロックの中で再代入される可能性がある
再代入前の区間で死んだ状態になるのがキーポイント
pは再び使われるが、そこに保持されていた値はもう使われなくなるため
伝統的なコンパイラは変数に基づく生存性を計算するが、今回はライフタイムの生存性を計算したい。
変数ベースのライフタイム解析を、以下のようにライフタイム用に拡張可能:
次が成り立つなら、ライフタイムLは地点Pで生きている、と言える:
Pで生きている変数pがある
Lはpの型に含まれている
以降でdropckを扱う際には、ライフタイムの生存性に関してより選択的な概念を使用する
変数の型の中のあるライフタイムは生きているかもしれないし、他のものは死んでいるかもしれない
上の例で言えば、ライフタイム'pの生存期間は変数pのそれと完全に同一。
'fooと'barは何かの変数の型に出現することはないので、(直接的には)生きているといえる地点が存在しない。
ただし、それらのライフタイムを気にしなくて良い、という訳ではなく、後続の解析によって導入されるサブタイピング制約(後述)によって、最終的には'fooと'barが'pより長生きすることが要求される。
3-3-4-1. 生存性に基づくライフタイム制約
制約の集合は、最初は生存性から導出される。
特に、もしライフタイムLが地点Pで生きているなら、以下のような制約が導入される:
code:rust
(L: {P}) @ P
今回の例に当てはめると、以下のような生存性制約が導入されることになる:
code:rust
('p: {A/1}) @ A/1
('p: {B/0}) @ B/0
('p: {B/3}) @ B/3
('p: {B/4}) @ B/4
('p: {C/0}) @ C/0
3-3-5. サブタイピング
参照がある場所から別の場所にコピーされた時はいつでも、Rustのサブタイピングルールは、ソース参照のライフタイムがターゲットのライフタイムよりも長生きすることを要求する。
前述の通り、このRFCでは、サブタイピングの概念が位置を認識(location-aware)するように拡張する (i.e., どこで値がコピーされたのかが考慮される)。
Example4を例にあげると、
地点A/0はp = &'foo fooという借用式を含んでいる
この借用式は&'foo Tの型の参照を生成する(Tはfooの型を表す)
この値(参照)は、&'p Tという型を持つpに代入される
=> &'foo Tは、&'p Tのサブタイプとなる
note.icon "代入可能"であることは"サブタイプ"であることを意味する
この関係はA/1でも保持される必要がある
代入が発生した地点A/0の後続であり、そこで初めてpの新しい値が認識可能となる
上のサブタイピング制約は、次のように記述できる:
code:rust
(&'foo T <: &'p T) @ A/1
Rust標準のサブタイピングルール(二つの例が以下で示されている)は、推論に必要なライフタイム制約へと"分解"することが可能。
code:rust
(T_a <: T_b) @ P
('a: 'b) @ P // <-- 推論アルゴリズムのための制約
------------------------
(&'a T_a <: &'b T_b) @ P
(T_a <: T_b) @ P
(T_b <: T_a) @ P // (&mut T is invariant)
('a: 'b) @ P // <-- 別の制約
------------------------
(&'a mut T_a <: &'b mut T_b) @ P
Example4のケースでは、以下のサブタイピング制約が生成される:
code:rust
(&'foo T <: &'p T) @ A/1
(&'bar T <: &'p T) @ B/3
これらは次のライフタイム制約に変換可能:
code:rust
('foo: 'p) @ A/1
('bar: 'p) @ B/3
note.icon ライフタイム'pの生涯でみれば'fooや'barよりも長生きするけれど、特定の地点だけに限定するなら↑が成立する:
束縛中に&'foo Tが死んだら、pの値が無効になってしまうので「'fooは'pより長生きする」必要がある
逆にpが先に死んでも、単に&'foo Tが参照されなくなるだけなので問題ない
3-3-6. 再借用制約
"再借用"は制約の最後のソース。
再借用は、既存の参照の参照先に対して、借用式を適用した際に発生する:
code:rust
let x: &'x i32 = ...;
let y: &'y i32 = &*x;
この場合、借用のライフタイム'yとオリジナル参照のライフタイム'xの間には接続がある。特に、'xは'yより長生き('x: 'y)しなければならない。
このような簡単なケースでは、オリジナルの参照xが共有(&)でも破壊的(&mut)でも、関係は変わらない。しかし、複数の参照外しが関わるようなより複雑なケースでは、破壊的かどうかで扱いが変わってくる。
3-3-6-1. サポート接頭辞群 (Supporting prefixes)
再借用制約を定義するために、まずは「サポート接頭辞群」というアイディアを導入する:
左辺値のサポート接頭辞群は、フィールドと参照外しを取り除くことで形成される:
ただし共有参照の参照外しに到達した時点で、取り除くのを停止する
note.icon &と&mutの扱いの違いに関しては、後に出てくる例2と例3が分かりやすい
code:rust
let r: (&(i32, i64), (f32, f64));
// The path (*r.0).1 has type i64 and supporting prefixes:
// - (*r.0).1
// - *r.0
// The path r.1.0 has type f32 and supporting prefixes:
// - r.1.0
// - r.1
// - r
let m: (&mut (i32, i64), (f32, f64));
// The path (*m.0).1 has type i64 and supporting prefixes:
// - (*m.0).1
// - *m.0
// - m.0
// - m
3-3-6-2. 再借用制約
左辺値lv_bに対して、ライフタイム'bの(共有ないし破壊的な)借用が存在するケースを考えてみる:
code:rust
lv_l = &'b lv_b // or:
lv_l = &'b mut lv_b
この場合、lv_bのサポート接頭辞群が計算され、その集合内の全ての参照外し左辺値*lvが探索される(lvはライフタイム'aを持つ参照)。
次に、制約('a: 'b) @ Pが追加される (Pは借用の直後の地点)。
いくつかの例を取り上げてみていく(リンク先はプロトタイプ実装での対応するテストコード)。
例1. このルールがなぜ必要かを理解するために、最初は単一の参照のみが存在する簡単な例を取り上げる: code:rust
let mut foo: i32 = 22;
let r_a: &'a mut i32 = &'a mut foo;
let r_b: &'b mut i32 = &'b mut *r_a;
...
use(r_b);
*r_aのサポート接頭辞群は*r_aとr_a。その中の*r_aのみが参照外し左辺値であり、参照r_aのライフタイムは'a。
ここでは制約'a: 'bが追加され、r_bが使用中の間はfooが借用されているものと見做されることを保証する。この制約が無ければ、ライフタイム'aが二回目の借用の後に終了し、(*r_b経由でまだアクセスがあるのに)fooは借用されていないものと見做されてしまう可能性がある。
code:rust
let mut foo: i32 = 22;
let mut r_a: &'a i32 = &'a foo;
let r_b: &'b &'a i32 = &'b r_a;
let r_c: &'c i32 = &'c **r_b;
// What is considered borrowed here?
use(r_c);
前の例と同様に、r_cが使用されている間はfooは借用されていると見做される必要がある。
では変数r_aに関してはどうか:
(r_cの使用中は)借用されているものとして扱われるべきか?
=> NO
いちどr_cが初期化されたら、r_aの値はもう重要ではない
fooが借用中でも、r_aの値を上書きしてしまって大丈夫
この結果は、再借用ルールの副次的な効果:
**r_bのサポート接頭辞分群は**r_bのみ
**r_bは、*r_bの参照外しであり、その型は&'a i32
=> 'a: 'cという再借用制約のみが追加される
=> この制約はr_cの使用中はfooが借用されていることを保証するが、ライフタイムが'bのr_aは終了可能
例3. 前述の例(r_a)とは異なり、破壊的な参照(p)の終了は安全ではない: code:rust
let mut foo = Foo { ... };
let mut p: &'p mut Foo = &mut foo;
let q: &'q mut &'p mut Foo = &mut p;
let r: &'r mut Foo = &mut **q;
use(*p); // <-- This line should result in an ERROR
use(r);
キーポイント:
**qを再借用することで、参照rを生成している
その後、rはプログラムの最後の行で使用される
これにより(rの生成に関わった)pとqの両方のライフタイムを拡張しなければならなくなる:
さもなければ、同じメモリ領域が*rと*pの両方から更新可能になってしまう
破壊的な参照の参照外しは、サポート接頭辞群の列挙を中止しないので、**qのサポート接頭辞群は**q、*q、qとなる。したがって、'q: 'r および'p: 'rの二つの再借用制約が追加され、問題の個所ではどちらの借用もスコープ内と見做される。
この例を別の観点から見てみる:
破壊的な参照pを生成すると、fooに対する"ロック" (有効期間はpの使用期間と等しい)が取得される
またqを生成することで、破壊的な参照pに対するロックが取得される (有効期間はqの使用期間)
次に**qを借用することでrが生成される:
qが直接使用されるのはここが最後
qはもう(直接は)使用されないので、pに対するロックが解放可能だと思うかもしれない
ただしそれだと不健全
rと*pが同じメモリ領域を参照しているため
note.icon pに対するロックを解放してしまうと、pとrの両方がfooに対するロックを獲得している状態となってしまう
重要なのは「rがqの間接的な使用を表現している」ことを位階すること:
さらにqは、pの間接的な使用、となる
=> rが使用中なら、pとqも"使用中"と見做されなければならない (それらの"ロック"も有効)
------