リージョン推論 (NLL)

MIR ベースのリージョンチェックコードは、rustc_mir::borrow_check モジュールにあります。

MIR ベースのリージョン解析は、2 つの主要な関数で構成されています。

• 最初に呼び出される replace_regions_in_mir には、2 つの役割があります。
  • 1 つ目は、関数のシグネチャ内に現れるリージョンの集合を見つけることです （例: fn foo<'a>(&'a u32) { ... } における 'a）。これらは「ユニバーサル」または「自由」リージョンと呼ばれます。 特に、これらは関数本体において自由に現れるリージョンです。
  • 2 つ目は、関数本体内のすべてのリージョンを新しい推論変数に置き換えることです。 これは、（現時点では）それらのリージョンが字句的リージョン推論の結果であり、 したがってあまり関心の対象ではないためです。意図としては、最終的にはそれらを 「消去されたリージョン」（つまり、情報をまったく持たないもの）にすることです。 なぜなら、字句的リージョン推論はまったく行わなくなるためです。
• 2 番目に呼び出される compute_regions は、ムーブ解析の結果を引数として受け取ります。 この関数の役割は、replace_regions_in_mir が導入したすべての推論変数の値を計算することです。
  • そのために、まず [MIR 型チェッカー]を実行します。これは基本的には通常の型チェッカーですが、 MIR に特化したものであり、当然ながら完全な Rust よりもはるかに単純です。 ただし、MIR 型チェッカーを実行すると、リージョン変数間にさまざまな制約が作成され、 それらの潜在的な値や相互関係が示されます。
  • その後、RegionInferenceContext を作成し、その solve メソッドを呼び出すことで、制約伝播を実行します。
  • NLL RFC にも、かなり徹底した（そしてできれば読みやすい） 説明が含まれています。

ユニバーサルリージョン

UniversalRegions 型は、何らかの MIR DefId に対応する ユニバーサル リージョンの集合を表します。これは、 すべてのリージョンを新しい推論変数に置き換える際に replace_regions_in_mir で構築されます。UniversalRegions には、 与えられた MIR 内のすべての自由リージョンのインデックスと、 それらの間で成り立つことが 既知 である関係 （例: 暗黙の境界、where 句など）が含まれます。

たとえば、次の関数の MIR が与えられたとします。

#![allow(unused)]
fn main() {
fn foo<'a>(x: &'a u32) {
    // ...
}
}

この場合、'a に対するユニバーサルリージョンと、'static に対するユニバーサルリージョンを作成します。 クロージャの処理にはいくつか複雑な点がある可能性もありますが、ここではひとまず無視します。

TODO: これらのリージョンが どのように 計算されるかについて書く。

リージョン変数

リージョンの値は 集合 と考えることができます。この集合には、 そのリージョンが有効である MIR 内のすべての点と、 このリージョンによってアウトライブされる任意のリージョン （例: 'a: 'b の場合、end('b) は 'a の集合に含まれる）が含まれます。 この集合のドメインを RegionElement と呼びます。コード内では、 すべてのリージョンの値は the rustc_borrowck::region_infer module で管理されます。 各リージョンについて、その値に含まれる要素を格納する集合を保持します（これを効率的にするために、 各種類の要素にインデックスである RegionElementIndex を与え、 スパースビットセットを使用します）。

リージョン要素の種類は次のとおりです。

• MIR 制御フローグラフ内の各 location: location は、 基本ブロックとインデックスのペアにすぎません。これは、そのインデックスを持つ文 （または、インデックスが statements.len() と等しい場合は終端）の 入口 の点を識別します。
• 各ユニバーサルリージョン 'a には、end('a) という要素があります。 これは、呼び出し元（または呼び出し元の呼び出し元など）の制御フローグラフの ある部分に対応します。
• 同様に、この関数が戻った後のプログラム実行の残りに対応する、 end('static) と表記される要素があります。
• 各プレースホルダーリージョン !1 には、要素 !1 があります。 これは（直感的には）他の要素からなる未知の集合に対応します。 プレースホルダーの詳細については、プレースホルダーとユニバース のセクションを参照してください。

制約

リージョンの値を推論できるようになる前に、リージョンに関する制約を収集する必要があります。 制約の完全な集合については、制約伝播に関するセクションで説明されていますが、 最も一般的な 2 種類の制約は次のとおりです。

1. アウトライブ制約。これは、あるリージョンが別のリージョンをアウトライブするという制約です （例: 'a: 'b）。アウトライブ制約は、[MIR 型チェッカー]によって生成されます。
2. 生存性制約。各リージョンは、それが使用され得る点でライブである必要があります。

推論の概要

では、リージョンの内容はどのように計算するのでしょうか。このプロセスは リージョン推論 と呼ばれます。 大まかな考え方は非常に単純ですが、対処する必要のある細部がいくつかあります。

大まかな考え方は次のとおりです。まず、生存性制約からそのリージョンに含まれていなければならないと わかっている MIR location を、各リージョンの初期値とします。そこから、型チェッカーから計算された すべてのアウトライブ制約を使用して、制約を 伝播 します。各リージョン 'a について、 'a: 'b であれば、end('b) を含む 'b のすべての要素を 'a に追加します。 これはすべて propagate_constraints で行われます。

その後、エラーをチェックします。まず、check_type_tests を呼び出して、 型テストが満たされていることを確認します。これは T: 'a のような制約をチェックします。 次に、ユニバーサルリージョンが「大きすぎ」ないことを確認します。これは check_universal_regions を呼び出すことで行われます。これは、各リージョン 'a について、 'a が要素 end('b) を含む場合、'a: 'b が成り立つことを （例: where 句から）すでに知っていなければならない、ということをチェックします。 これをまだ知らない場合、それはエラーです……まあ、ほぼそうです。クロージャにはいくつか特別な処理があり、 これについては後で説明します。

例

次の例を考えてみましょう。

fn foo<'a, 'b>(x: &'a usize) -> &'b usize {
    x
}

明らかに、これはコンパイルされるべきではありません。なぜなら、'a が 'b をアウトライブするかどうかが わからないためです（そうでない場合、戻り値がダングリング参照になり得ます）。

少し戻りましょう。いくつかの自由推論変数を導入する必要があります （これは replace_regions_in_mir で行われます）。この例では実際に生成されるリージョンそのものは 使用していませんが、考え方を伝えるには（おそらく）十分です。

fn foo<'a, 'b>(x: &'a /* '#1 */ usize) -> &'b /* '#3 */ usize {
    x // '#2、位置 L1
}

表記について説明します。'#1、'#3、'#2 はそれぞれ、引数、戻り値、式 x のユニバーサルリージョンを表します。さらに、式 x の位置を L1 と呼ぶことにします。

これで、生存性制約を使用して次の開始点を得られます。

次に、outlives 制約を使用して各リージョンを拡張します。具体的には、'#2: '#3 であることが分かっています …

… そして '#1: '#2 なので …

次に、大きすぎるリージョンがなかったことを確認する必要があります（この場合、確認すべき型テストはありません）。'#1 が今や end('#3) を含んでいることに注意してください。しかし、'a: 'b であることを示す where 句や暗黙の境界はありません … これはエラーです！

詳細

RegionInferenceContext 型には、replace_regions_in_mir からのユニバーサルリージョンや、各リージョンについて計算された制約など、推論を行うために必要なすべての情報が含まれています。これは、生存性制約を計算した直後に構築されます。

この構造体のフィールドの一部を以下に示します。

• constraints: すべての outlives 制約を含みます。
• universal_regions: replace_regions_in_mir によって返される UniversalRegions を含みます。
• universal_region_relations: ユニバーサルリージョンについて真であることが分かっている関係を含みます。たとえば、'a: 'b という where 句がある場合、その関係は実装を借用チェックしている間は真であると仮定されます（呼び出し元でチェックされます）。したがって、universal_region_relations には 'a: 'b が含まれます。
• type_tests: 推論後にチェックしなければならない型に関するいくつかの制約（例: T: 'a）を含みます。

TODO: 他のフィールドについて議論すべきでしょうか？SCC についてはどうでしょうか？

さて、RegionInferenceContext を構築したので、推論を行うことができます。これは、コンテキスト上で solve メソッドを呼び出すことで行われます。ここで propagate_constraints を呼び出し、その後、上で説明したように、結果として得られた型テストとユニバーサルリージョンをチェックします。