注意: 正確性は重視していない意訳なので、正確に知りたい人は原文を参照のこと
関連:
------
3-3-7. 制約を解決する
制約群が生成されたら、推論アルゴリズムがそれを解決する。
これは不動点反復によって実施される:
各ライフタイム変数の初期状態は空集合
各制約は繰り返し走査される:
全ての制約を満たすまでライフタイムが育ったら、そこで停止する
('a: 'b) @ Pのような制約は「ライフタイム'b内の、地点Pから到達可能な全ての点を、ライフタイム'aが含んでいる必要がある」ということを意味する。
ライフタイム'bが終了したら、探索を止める
それまでは、探索した各地点を'aに追加する
Example4での制約の完全な集合は以下の通り:
code:rust
('foo: 'p) @ A/1
('bar: 'p) @ B/3
('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
これを解決すると以下のライフタイムが得られる(期待した通りの結果):
code:rust
'p = {A/1, B/0, B/3, B/4, C/0}
'foo = {A/1, B/0, C/0}
'bar = {B/3, B/4, C/0}
3-3-8. なぜこのアルゴリズムは正しいのか、に関する直観
このアルゴリズムが正しくあるためには、維持しなければならない不変項が存在する。
以下のケースを考えてみる:
あるパスHが、参照Rを生成するために、地点PでライフタイムLで借用されている
この参照R(ないし、そのコピー先・移動先)は、後続の地点Qでderefされる
この参照が無効とならないことを保証しなければならない:
つまりQに到達する前に、借用されているメモリ領域が解放されてはならない
また、
もし参照Rが共有参照(&T)なら、書き込まれてもいけない
もし参照Rが破壊的な参照(&mut T)なら、R経由以外でのアクセスは完全に禁止される
これらの性質を保証するために、地点P(借用)から地点Q(使用)の間で、借用されたメモリに影響を与え得るアクションを禁止しなければならない
これはLが、最低でもPとQの間の全ての地点を含まなければならないことを意味する。
考えるべきケースが二つある。
一つ目は、地点Qでのアクセスが借用によって生成された参照R経由で行われた場合:
code:rust
R = &H; // point P
...
use(R); // point Q
この場合は、変数Rが、PとQの間の全ての地点で生きていることになるので、生存性ベースのルールで十分にカバーできる。
具体的には、Rの型にはライフタイムLが含まれるので、Rが生きているなら、LにはPとQの間の全ての地点が含まれなければならないことが分かる。
二つ目は、Rによって参照されるメモリが、エイリアス(や移動後の変数)経由でアクセスされる場合:
code:rust
R = &H; // point P
R2 = R; // last use of R, point A
...
use(R2); // point Q
この場合は生存性ルールだけでは不十分。
問題は、R2 = Rの代入の以降はRは使用されていないので、変数Rはこの地点で死んでしまう、ということ。
しかしR内の値は、まだ後でR2を通してderefされるので、ライフタイムLには、それらの地点も含まれていてほしい。
これを解決するのがサブタイピング制約:
R2の型はライフタイムL2を含み、代入R2 = Rによって、長生き制約(L: L2) @ Aを確立される
さらに変数R2は、代入地点から最後の使用地点(A...Q)まで生存している
=> これらの事実を合わせると、Lには、P...A (Rの生存性)とA...Q(R2の生存性によって伝搬されたサブタイピング要求)が含まれることになる
ライフタイムがギャップを持つことも可能。
これは同一の変数に対して、複数回の代入が行われた際に発生し得る:
code:rust
let R: &L i32;
let R2: &L2 i32;
R = &H1; // point P1
R2 = R; // point A1
use(R2); // point Q1
...
R2 = &H2; // point P2
use(R2); // point Q2
この例では、R2の生存性制約は、ライフタイムL2がQ1とQ2を含むことを保証する。
ただし...の箇所および地点P1とP2は含まれない。
ちなみに、A1でのサブタイピング関係(L: L2) @ A1は、LがQ1を含むことを要求するが、Q2はその対象とならない(L2とは異なり)。何故ならR2の値は、P2での再代入によって、別の値に更新されてしまっているので。
3-3-9. その他の例
いくつかの例を見ていく。
まずは、冒頭で取り上げた問題ケースの#1と#2から。
問題ケース#3は名前付きライフタイムを扱った後に改めて取り上げることとする。
問題ケース#1
再掲:
code:problem1.rs
fn bar() {
let slice = &mut data..; // <-+ 'lifetime capitalize(slice); // |
data.push('d'); // ERROR! // |
data.push('e'); // ERROR! // |
data.push('f'); // ERROR! // |
} // <------------------------------+
変換後の(大まかな)MIR:
code:rust
let mut data: Vec<i32>;
let slice: &'slice mut i32;
START {
data = ...;
slice = &'borrow mut data;
capitalize(slice);
data.push('d');
data.push('e');
data.push('f');
}
生成される制約:
code:rust
('slice: {START/2}) @ START/2
('borrow: 'slice) @ START/2
'sliceと'borrowの両方がSTART/2をライムタイムの値として推論する。そのためSTART/3以降でのdataに対する操作は許容される。
問題ケース#2
再掲:
code:problem2.rs
fn process_or_default() {
let mut map = ...;
let key = ...;
match map.get_mut(&key) { // -------------+ 'lifetime
Some(value) => process(value), // |
None => { // |
map.insert(key, V::default()); // |
// ^~~~~~ ERROR. // |
} // |
} // <------------------------------------+
}
変換後のMIR(注: 本質的ではない細部は省略されている)。
match文はSWITCHに変換されており、そこでは各節のテストと"ダウンキャスト"(Someの場合)が行われている。
code:rust
let map: HashMap<K,V>;
let key: K;
let tmp0: &'tmp0 mut HashMap<K,V>;
let tmp1: &K;
let tmp2: Option<&'tmp2 mut V>;
let value: &'value mut V;
START {
/*0*/ map = ...;
/*1*/ key = ...;
/*2*/ tmp0 = &'map mut map;
/*3*/ tmp1 = &key;
/*4*/ tmp2 = HashMap::get_mut(tmp0, tmp1);
/*5*/ SWITCH tmp2 { None => NONE, Some => SOME }
}
NONE {
/*0*/ ...
/*1*/ goto EXIT;
}
SOME {
/*0*/ value = tmp2.downcast<Some>.0;
/*1*/ process(value);
/*2*/ goto EXIT;
}
EXIT {
}
以下の生存性制約が生成される:
code:rust
('tmp0: {START/3}) @ START/3
('tmp0: {START/4}) @ START/4
('tmp2: {SOME/0}) @ SOME/0
('value: {SOME/1}) @ SOME/1
以下のサブタイピングベースの制約が生成される:
code:rust
('map: 'tmp0) @ START/3
('tmp0: 'tmp2) @ START/5
('tmp2: 'value) @ SOME/1
最も興味深いのはmapの借用期間を示すライフタイム'mapの値。
上の制約を解くと、以下が得られる:
code:rust
'map == {START/3, START/4, SOME/0, SOME/1}
'tmp0 == {START/3, START/4, SOME/0, SOME/1}
'tmp2 == {SOME/0, SOME/1}
'value == {SOME/1}
この結果はmapがNone節内では更新可能なことを示している。
またmapはSome節内でも、process()関数呼び出し後(i.e., SOME/2以降)であれば更新可能(期待する結果通り)。
Example4, 不変項
これまで使ってきたExample4の変種を見ることには価値がある。
&'a TがFoo<'a>に変わっていることだけが変更点。
これにより'aが不変項(invariant)となり、Foo<'a>内の'aの近似が不可能となる(i.e., 通常の参照とは異なり、必要に応じて'aのライフタイムを縮めることができなくなる)。
通常は、不偏性は可変性により生じる(e.g., Foo<'a>は内部にCell<&'a ()>というフィールドを含むかもしれない)。
重要な点は、位置ベースのサブタイピングにより、この不偏性は推論結果に対して、実質的には全く影響を与えないということである。
code:example4-invariant.rs
let mut foo: T = ...;
let mut bar: T = ...;
let p: Foo<'a>;
p = Foo::new(&foo);
if condition {
print(*p);
p = Foo::new(&bar);
}
print(*p);
基本的にはオリジナルのコードと同様の制約が得られる。
ただし、不偏性により'foo: 'pおよび'bar: 'pに加えて、'p: 'fooおよび'p: 'barが制約に追加される:
code:rust
('foo: 'p) @ A/1
('p: 'foo) @ A/1 // 追加
('bar: 'p) @ B/3
('p: 'bar) @ B/3 // 追加
('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
ただし、この新規制約は、最終的な結果には影響を与えない(以前の結果でも既に満たされているため)。
vec-push-ref
この提案の古い版では、位置ベースのサブタイピングルールの代わりに、SSAフォームの変換が使われていた。
vec-push-refの例を使って、位置ベースのサブタイピングが旧方式よりも優れていることを示す。
code:vec-push-ref.rs
let foo: i32;
let vec: Vec<&'vec i32>;
let p: &'p i32;
foo = ...;
vec = Vec::new();
p = &'foo foo;
if true {
vec.push(p);
} else {
// Key point: foo not borrowed here.
use(vec);
}
対応する制御フローグラフ:
code:rust
block START {
v = Vec::new();
p = &'foo foo;
goto B C;
}
block B {
vec.push(p);
goto EXIT;
}
block C {
// Key point: foo not borrowed here
use(vec);
goto EXIT;
}
block EXIT {
}
生存性制約:
code:rust
('vec: {START/1}) @ START/1
('vec: {START/2}) @ START/2
('vec: {B/0}) @ B/0
('vec: {C/0}) @ C/0
('p: {START/2}) @ START/2
('p: {B/0}) @ B/0
vec.push(c)の呼び出しは以下のサブタイピング制約を確立する:
code:rust
('p: 'vec) @ B/1
('foo: 'p) @ START/2
解法:
code:rust
'vec = {START/1, START/2, B/0, C/0}
'p = {START/2, B/0}
'foo = {START/2, B/0}
この例を興味深くするのはライフタイム'vecはif分岐の両方を含まなければならないということ:
'vec自体は両方の分岐先で使用されているため
ただし、'pとの関係が構築されるのは片方でのみ
位置ベースのサブタイピングのおかげで、'pは"else"節の中では、'vecよりも長生きする必要がなくなる
------