注意: 正確性は重視していない意訳なので、正確に知りたい人は原文を参照のこと
関連:
------
3-4. 階層2: 無限ループを避ける
しかし、無限ループが絡んだ場合、生のグラフはいくつかの望ましくない性質を持っている。
無限ループの場合は、グラフは出口(exit)を持たないので、生存性のような逆解析の伝統的な定義を覆してしまう。
これに対処するために、関数向けに制御フローグラフを構築する際には、それを追加のエッジで拡張する。特に、全ての無限ループ(loop { })に対して、偽の"unwind"エッジを追加する。
これにより制御フローグラフが、最終的な出口ノードを確実に含むようになる。この出口ノードは、グラフ内の他の全てのノードの後続に位置する(postdominate)。
もしこういったエッジが無い場合には、たくさんの驚くべきプログラムの存在を許すことになる。
例えば、関数が決してreturnしないなら、ローカル変数を'staticライフタイムで借用することが可能となる:
code:rust
fn main() {
let x: usize;
let y: &'static x = &x; // 驚くべき点: スタック変数の参照が'staticに出来てしまう
loop { }
}
このコードでは(借用チェックの節で出てくる)StorageDead(x)命令に決して到達しないために、借用に対して任意のライフタイムが許容可能となってしまっている。
note.icon 確かに(?)「無限ループ」して、かつ「例外が発生する可能性がない(i.e., unwindしない)」なら、事実上「xの生存期間はプログラムのそれと等しい」ことになるので'staticでも問題ないのかもしれない(?)。
次の例のように、スレッドの生成用の(正しくないが、unsafeと宣言された)APIを使用した、別のさらに驚くべきプログラムも存在する:
code:rust
let scope = Scope::new();
let mut foo = 22;
unsafe {
// デストラクタが、スレッドの終了を待機する
let _guard = scope.spawn(&mut foo);
loop {
foo += 1; // 驚くべき点: 上で破壊的な参照を渡したはずの変数が更新できてしまう
}
// _guard変数のドロップによって、スレッドの終了が待機される
}
note.icon ここで使用しているScopeの出自がいまいち不明 (spawnに整数の参照を渡しているのも謎)
unwindエッジなしでは、このコードは借用チェックを通ってしまう:
_guard (および StorageDead命令)のドロップには決して到達しない (無限ループがあるので)
そのため_guardは生存していると見做されない:
デストラクタは決して呼ばれることがない => 変数の使用箇所が一切ない => 死んでいる
note.icon その結果、借用された&mut fooのライフタイムの値も空集合となる
これによってfoo変数が、無限スープ内とscope.spawn()によって起動されたスレッド内の両方で更新されることが許可されてしまう
偽のunwindエッジがあれば、全てのスコープが理論上は実行され得るので、コンパイラは常にデストラクタが実行される可能性があるということを仮定できるようになる。
これによってscope.spawn()に与えれた&mut fooの借用は、(_guardを経由して)ループの本体をカバーするようになり、借用チェッカがエラーを出すようになる。
MIRは変数を"ドロップする"ことに関連したアクションを含んでいる:
code:rust
DROP(variable)
MIRは任意の左辺値のドロップをサポートしているが、ここで取り上げる解析内では、常に変数全体が一度にドロップされるものとする(note.icon let _ = foo.bar; let _ = foo; 的な記述が出来ず、最初の文でfoo全体がドロップされてしまう、ということだと思われる)。
この操作はvariableのデストラクタを実行する(もし変数が既にドロップ済みならDROPは何の効果も持たない; ただしこの挙動は今回の解析とは無関係)。
興味深いことに、多くのケースでは、値をドロップする際に、その中のライフタイムが有効であることは要求されない。
結局のところ、&'a Tや&'a mut Tといった型の参照をドロップすることはno-opとして定義されており、その参照先が妥当なメモリ領域かどうかは問題とならない。このような場合、ライフタイム'aはdangleする可能性があると呼ぶことにする(無効なメモリ領域を指すポインタを意味するC言語の"ダングリングポインタ"に由来)。 しかしながら、もし同じ参照が構造体のフィールドに格納され、かつその構造体がDropトレイトを実装した上で、デストラクタ内で参照先の値にアクセスするなら、「参照が有効であること」はとても重要となる。 別の言い方をすれば、もしDropを実装するFoo<'a>型の値vがあるなら、典型的には'aはvがドロップされる時にdangleであることは許容されない。
より一般的には、RFC 1327で「型の中のどのライフタイムがドロップ中にdangleになる可能性があるのか」に関するルールが定義されている。 ここでは以下のようにして、それらのルールを、本RFCの生存性解析に統合する:
生存性に関係する際には、MIRのDROP(variable)命令は、他のMIR命令のようには扱われない
ある意味で、概念的には二つの異なる生存性解析が実行されることになる(実際、プロトタイプ実装では各変数に付き二ビットを使用していた):
【1. これまで通りの方式】
変数に格納されている現在の値が将来に使用される可能性があるかどうかに基づく解析
これはMIR内での変数の"no-drop"な使用方法に対応する
この定義によって、変数が生きていると見做される時にはいつでも、その型に含まれる全てのライフタイムも生きていることになる
【2. 追加される方式】
変数に格納されている現在の値が将来にドロップされる可能性があるかどうかに基づく解析
これはMIR内での変数の"drop"な使用方法に対応する
この意味で、変数が生きていると見做される時にはいつでも、その型内のdangleする可能性があるとマークされたものを除いて全てのライフタイムも生きていることになる
ドロップ中にライフタイムがdangleすることを許可するのはとても重要!
結局のところ、問題ケース#1をMIRに変換したら、参照sliceはブロックの最後でドロップされることになる:
code:rust
let mut data: Vec<i32>;
let slice: &'slice mut i32;
START {
...
slice = &'borrow mut data;
capitalize(slice);
data.push('d');
data.push('e');
data.push('f');
DROP(slice); // ここで「sliceが使用中」とは見做されてほしくない(借用したライフタイムが延長されてしまうので)
DROP(data);
}
'sliceはドロップ中に"dangleする可能性"があり、生きているとは見做されないので、ライフタイムの解析で問題は発生しない。
3-6. 階層4: 名前付きライフタイム
ここまでは関数内のライフタイムについてだけ考慮してきた。
しばしば、現在の関数が終わった後に、開始ないし終了されるライムタイムについて推論したくなる。さらに微妙なことに、時々、「現在の関数内で開始および終了する」が、かつ、呼び出し元にも拡張される可能性があるような、ライフタイムを扱いたくなる時がある。
問題ケース#3を再び考えてみる:
code:problem3.rs
fn get_default<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
key: K)
-> &'r mut V {
match map.get_mut(&key) { // -------------+ 'r
Some(value) => value, // |
None => { // |
map.insert(key, V::default()); // |
// ^~~~~~ ERROR // |
map.get_mut(&key).unwrap() // |
} // |
} // |
} // v
これをMIRに変換すると(大まかには)以下のようになる:
code:rust
block START {
m1 = &'m1 mut *map; // temporary created for map.get_mut() call
v = Map::get_mut(m1, &key);
switch v { SOME NONE };
}
block SOME {
return = v.as<Some>.0; // assign to return value slot
goto END;
}
block NONE {
Map::insert(&*map, key, ...);
m2 = &'m2 mut *map; // temporary created for map.get_mut() call
v = Map::get_mut(m2, &key);
return = ... // "unwrap" of v
goto END;
}
block END {
return;
}
この例の重要な点は「mapの最初の借用で得られるライフタイム'm1は、'rの最後まで拡張される必要がある」が「それはSOMEブランチの場合のみ」であるということ。NONEブロックに入った場合には、即座に'm1のライフタイムは終了する。
このようなケースに適合するために、多様な名前付きライフタイム向けに領域(region)の概念を拡張し、それが制御フローグラフの地点群だけでなく、"終端領域"の集合(空の可能性もある)を含むようにする。
名前付き領域'rに対応する終端領域の集合をend('r)と表記する。
領域end('r)は、意味的には、呼び出し元の制御フローグラフのある部分範囲を参照するものとして理解することも可能(実際には、それらは"呼び出し元の呼び出し元の..."といった用に再帰的に拡張可能だが、今回の議論には関係ない)。
新しい領域は、以下のように表記可能(疑似コード形式):
code:rust
struct Region {
points: Set<Point>, // 以前の定義
end_regions: Set<NamedLifetime>, // 追加分
}
このケースでは、ある型が'rのような名前付きライフタイムに言及する場合、それは以下を含む領域として表現可能:
CFG全体 (note.icon 名前付きライフタイムは関数全体に適用されるものだから?)
名前付きライフタイムのための終端領域 (end('r))
note.icon 名前付きライフタイムの領域は「関数内の全て」および「関数外での使用箇所」ということ
加えて、'r: 'xとなるような全ての名前付きライフタイム'xに対して、'rの領域がend('x)を含むようにすることができる。何故なら、もし'r: 'xなら、'xが終了するまで'rも終了できないことになるからである。
最後に、改正された領域の定義に合わせて、サブタイピングの定義を修正する必要がある。
以下のような、ある長生き関係があるとして、
code:rust
'b: 'a @ P
CFGの終端地点が'aを残したままPから到達可能な場合、既存の推論アルゴリズムでは、単にその終端地点を'bに追加し、停止することになる。
新しいアルゴリズムでは、'aに含まれている全ての終端領域群も'bに追加されるようになる。
CFGの終端地点が到達可能であることを要求する理由は、さもなければそのデータは決して現在の関数を抜けず、end('r)は到達可能ではないからである(end('r)は呼び出し元の、return後に実行されるコード、のみをカバーするため)。
NB: この節の内容はプロトタイプでは部分的に実装されている。Issue#12が現在のステータスと関連PRへのリンクを含んでいる。 3-7. 階層5: 借用チェックがどのように動作するか
このRFCの大部分はライフタイムの構造に焦点を当てているが、ノンレキシカルなライフタイムを借用チェッカにどのように統合するかについて話すことにも価値はある。
特に、その一環として、このRFCでは現在の借用チェッカが抱える二つの欠点を修正したいと考えている:
一点目: vec.push(vec.len()) のようなネストしたメソッド呼び出しのサポートする
本RFCでは、RFC-2025で説明されている型ベースの解法は(まだ)提案しない e.g., "未来のための借用"やRef2
なぜこれらを扱わないかは、代替案の節で議論されている
効果としては、借用の開始が遅らせられることになる
二点目: ある破壊的参照の参照先が借用されている場合でも、それを保持する変数が更新されることは許容する
問題ケース#4で取り上げられたようなケースが許容されるようにしたい
code:problem4.rs
// 再掲: リンクリストを、破壊的な参照を要素とする配列に変換する例
struct List<T> {
value: T,
next: Option<Box<List<T>>>,
}
fn to_refs<T>(mut list: &mut List<T>) -> Vec<&mut T> {
let mut result = vec![];
loop {
result.push(&mut list.value);
if let Some(n) = list.next.as_mut() {
list = n; // 上の二行によって、ここがエラーとなる
} else {
return result;
}
}
}
3-5-1. 借用チェッカフェーズ1: スコープ内のローンを計算する
借用チェッカの最初のフェーズでは、CFG内の各地点に対して、スコープ内のローンの集合が計算される。
一つの"ローン"は('a, shared|uniq|mut, lvalue)のタプルで表現され、以下を示している:
(1) 借用のライフタイム'a
(2) このローンが、共有、ユニーク、可変、のどれか:
"ユニーク"ローンは、その参照先の変更を許可しない点を除けば、可変なローンと全く同一
これはクロージャの脱糖でのみ使用され、Rustの表面上の文法には含まれない
(3) 借用された左辺値 (e.g., x or (*x).foo)
各地点での、スロープ内のローンの集合は、不動点(fixed-point)データフロー計算を使って見つけることができる。
まず、MIR内の各右辺値(つまりtmp = &'a b.c.dのような代入文)の借用から、一つのローンタプルを生成し、それらにユニークなインデックスiを与える。次に、特定地点のスコープ内のローン集合をビット集合を使って表現した上で、標準的な前方データフロー伝搬を実施する。
グラフ内の地点Pの文に対して、"転送関数"(これがスコープに出入りするローンを決定する)を以下の様に定義する:
Pを領域に含まないローンは殺される
これが借用文なら、対応するローンが生成される
これがlv = <rvalue>といった代入なら、lvを接頭辞とするパスPに対応するローンは殺される
note.icon 紛らわしいけれど、ここでの"P"は地点の話ではなく、左辺値の接頭辞の話(おそらく)
最後の点はいくらか手が凝っている。
このルールによって、問題ケース#4のようなケースがサポート可能となる:
code:rust
let list: &mut List<T> = ...;
let v = &mut (*list).value;
list = ...; // <-- assignment
"assignment"とマークされている地点で、(*list).valueのローンはスコープ内ではあるが、その後はスコープ内として扱われる必要はない。
何故なら、変数listは今は新鮮な値を保持しており、かつ、その新しい値はまだ借用されていないからである。特に、MIRでlv = <rvalue>代入を見た時はいつでも、借用パスlv_loanがlvを接頭辞として持つ全てのローンをクリアすることが可能となる。(上の例のlistへの代入では、ローンパス(*list).value)がlistを接頭辞に含んでいる。)
NB. このフェーズでは、ある代入がある時には、上書きされたパスに適用された全てのローンを常にクリアする; しかしながら、いくつかのケースでは、代入自体がそれらのローンによって非合法となる可能性がある。上の例で、もしlistの型が&mut List<T> ではなくList<T>だった場合には、これが当てはまる。このようなケースは、次の節で説明される、借用チェックの次の部分で、エラーとして報告される。
3-5-2. 借用チェッカフェーズ2: エラーを報告する
ここまでで、各地点でのスコープ内のローン集合が計算できた。次は、MIRを横断して、スコープ内のローンに対して非合法なアクションの特定を行う。
以降では、全ての種類のMIR文を個別に扱うのではなく、以下の二種類のアクションに大別することにする:
左辺値へのアクセス:
さらに「shallow vs deep」および「read vs write」という二軸にカテゴライズする
左辺値のドロップ
上記のアクションそれぞれについて、アクションの開始地点でのスコープ内のローン集合Lが合法であるかどうかを決定するルールを、以降で導入する。
従って、借用チェックのフェーズ2は、MIR内の各文を走査しつつ、与えられたスコープ内のローン集合をもとに、その文が実行するアクションが合法かどうかを確認する、といった処理で構成されることになる。
MIR文のアクションへの変換は、大体の場合には直接的に実行可能:
StorageDead文は、shallow writeとして扱う
LV = RVという代入文は、LVへのshallow writeとなる
かつ、上記右辺値RVに関して:
各左辺値オペランドはdeep readないしdeep writeのどちらかのアクションとなる:
左辺値がCopyを実装しているかどうかに依存 (note.icon 実装しているならdeep read?)
捕捉: 移動はdeep writeとして扱われる
共有借用&LVはdeep read扱い
可変借用&mut LVはdeep write扱い
念頭に置いておきたい、いくつかの興味深いケースがある:
MIRは判別式(discriminants)をより正確にモデル化する:
借用時には、それらは個別のフィールドとして扱われるべき
note.icon enumの話?
現時点でのコンパイラでは、BoxはまだMIRに"組み込み"となっている:
本RFCでは、Boxが存在する可能性を無視し、借用された参照(&と&mut)および生ポインタ(*constと*mut)のみがポインタの種類として存在するものとして扱っている
これをBoxもカバーするように拡張するのは簡単であるはずだが、ドロップの扱い周りでいくつか疑問がある(詳細はドロップの節を参照)
3-5-2-1. 左辺値LVにアクセスする
左辺値LVにアクセスする際には、考慮すべき軸が二つある:
アクセスがSHALLOWとDEEPのどちらになりえるか:
shallow:
LVで到達した直接のフィールド、に対するアクセスを意味する
フィールドが参照やポインタの場合でも、derefされない
現時点では、shallowなアクセスはx = ...といった代入分のみである
これはxに対するshallow writeとなる
deep:
与えられた左辺値経由で到達可能な全てのデータが、このアクションによって、無効化ないしアクセスされる可能性があることを意味する
アクセスがREADとWRITEのどちらになりえるか:
read: 既存のデータは読み込まれるかもしれないが、変更はされない
write: データは新しい値に更新されるか、無効化される可能性がある
例えば、移動操作の中でde-initializedされるかもしれない
あるアクセスが合法かどうかを決定するための疑似コードは以下のようになる:
code:rust
fn access_legal(lvalue, is_shallow, is_read) {
let relevant_borrows = select_relevant_borrows(lvalue, is_shallow);
for borrow in relevant_borrows {
// &xの共有借用は、xからの読み込みは許容する (ただし書き込みは禁止)
if is_read && borrow.is_read { continue; }
// さもなければ、ここでエラーが報告される。
// 何故なら、スコープ内の借用と衝突するエラーが検出されたため。
report_error();
}
}
見ての通り、これは二つのステップで動作する:
最初に、lvalueに関連するスコープ内の借用の集合を列挙する
この集合の値は、対象が"shallow"と"deep"のどちらのアクションかによって変わってくる(後で軽く触れる)
次に、得られた各借用に対して、対象のアクションと衝突しないかをチェックする
i.e., そのいずれかが書き込むを行う可能性がないかどうか
もし衝突するならエラーを報告
パスlvalueに対するshallowアクセスの場合、以下の条件を満たした借用を関連するものとして見做す:
パスlvalueに対するローンが存在する:
従って: もしa.b.cが借用されているなら、パスa.b.cに書き込むことは非合法
パスlvalueのある接頭辞に対するローンが存在する:
従って もしaないしa.bが借用されているなら、パスa.b.cに書き込むことは非合法
lvalueはローンパスのshallow接頭辞:
shallow接頭辞群は、derefに到達するまで、フィールドを削っていくことで得られる
従って: a.bが借用されているなら、パスaに書き込むことは非合法
ただし: *aが借用されている時に、aに書き込むのは合法
aが共有参照か可変参照かは無関係
パスlvalueに対するdeepアクセスの場合、以下の条件を満たした借用を関連するものとして見做す:
パスlvalueに対するローンが存在する:
従って: a.b.cが破壊的に借用されているなら、パスa.b.cから読み込むことは非合法
パスlvalueのある接頭辞に対するローンが存在する:
従って: もしaないしa.bが破壊的に借用されているなら、パスa.b.cから読み込むことは非合法
lvalueはローンパスのサポート接頭辞:
サポート接頭辞群の定義は既出 (note.icon shallow接頭辞群と似ているが、停止するderefは共有の場合のみ)
従って: a.bが破壊的に借用されているなら、パスaから読み込むのは非合法
ただし、shallowアクセスとは対照的に、*aが破壊的に借用されている場合にaを読み込むことも非合法となる
3-5-2-2. 左辺値LVをドロップする
左辺値のドロップは、移動の場合と同様にDEEP WRITEとして扱われるが、これは過度に保守的ではある。
ここで説明されたルール群は、活発に開発中。詳細は#40を参照。 ------