エイリアスベースの借用チェッカーの定式化 (2018年)
An alias-based formulation of the borrow checker (2018) (smallcultfollowing.com)
要約
この記事は、Rustの借用チェッカーの新しい定式化について解説しています。このアプローチは、既存のNLL(Non-Lexical Lifetimes)分析の課題を克服し、計算速度の向上を目指しています。提案されている「エイリアスベース」の定式化では、ライフタイムを「ローン(借用)の集合」として捉え直し、Datalogを用いて分析を行います。この新しい考え方は、コンパイラがプログラムをどのように解釈するかという点で微妙な変化をもたらし、将来的な言語機能に影響を与える可能性があります。
全文翻訳
エイリアスベースの借用チェッカーの定式化
Rust All Hands以来、私はRustの借用チェッカーの代替定式化を試してきました。その目標は、現在の提案のいくつかの欠点を克服し、かつ計算速度も向上するような定式化を見つけることです。この分析のためのプロトタイプを実装しました。それは完全なNLLテストスイートをパスし、現在のNLL分析では対応できないいくつかのケース(例:#47680)も扱えます。しかし、パフォーマンスはまだ改善の余地があります(現在は既存の分析よりも遅いです)。とはいえ、まだ最適化に着手しておらず、明らかに改善できる非効率なことをいくつか行っていることはわかっているので、そこで大きな進歩を遂げられると楽観視しています。
また、昨日4月26日が借用チェッカーの6回目の「誕生日」であったことを指摘されました。当時の私のコミット(https://github.com/rust-lang/rust/commit/50a3dd40ae8ae6494e55d5cfc29eafdb4172af52)を見ると、当時のRustがどのようなものであったかがよくわかります。[1][2]
エンドユーザーは気にする必要はない
まず注意すべきは、この提案はRustのエンドユーザーの視点からは何の違いももたらさないということです。つまり、借用チェッカーはNLL提案の下で動作するのとほぼ同じように動作するはずです。
しかし、コンパイラがプログラムをどのように考えるかという点では、この提案にはいくつかの微妙な変化があり、将来の言語機能に影響を与える可能性があります。
最初の例
この分析はMIR(Mid-level Intermediate Representation)上で動作しますが、ここでは簡単なRustの例で説明します。最初の例を例Aと呼びます。ご覧の通り、この例はコンパイルされるべきではありません。
fn main() {
let mut x: i32 = 22;
let mut v: Vec<&i32> = vec![];
let r: &mut Vec<&i32> = &mut v;
let p: &i32 = &x; // 1. `x` はここで借用されて `p` が作成される
r.push(p); // 2. `p` は `r` を介して `v` に格納される
x += 1; // <-- エラー!借用中に `x` を変更できない
take(v); // 3. `x` への参照は後でここで使用される
}
fn take<T>(p: T) { .. }
リージョンはローンの集合
この新しいアプローチにおける最大のシフトは、&'a i32 のような型を持つ場合、'a の意味が変わることです。
- NLL RFCで説明されているシステムでは、
'a(ライフタイムと呼ばれる)は最終的にソースプログラムまたは制御フローグラフの一部に対応していました。 - この提案の下では、
'a(ここではリージョン[3]と呼びます)は、代わりにローンの集合に対応します。つまり、例Aの&xや&mut vのような借用式の集合です。アイデアは、参照rが&'a i32型を持つ場合、'aのローンの条件のいずれかが無効化されるとrも無効化されるということです。
ローンの条件を無効化するとは、ローンによって借用されたパスへの不正なアクセスを実行することです。例えば、r = &mut v のようなミュータブルなローンがある場合、値 v にアクセスできるのは参照 r を介してのみです。v への直接的なアクセス(読み取り、書き込み、移動)は、ローンを無効化します。共有ローン p = &x の場合、x(または p)を介した読み取りは許可されますが、x の書き込みやミューテーションはローンの条件を無効化します(p を介した書き込みも不可能です)。
参照のサブタイピング規則は、リージョンがプログラムポイントではなくローンの集合になったことで、少し異なります。ポイントの場合はライフタイムを短縮することで参照を近似できますが、ローンの集合の場合は集合を拡大することで近似できます。言い換えると:
'a ⊆ 'b
------------------
&'a u32 <: &'b u32
Rustの構文では、'a ⊆ 'b は 'a: 'b という表記に対応し、以降の投稿ではこれを使用します。従来、これを「アウトライブ関係」と呼んでいましたが、リージョンの新しい意味合いにふさわしく、「サブセット関係」と呼ぶことにします[4]。
リージョンをローンの集合という考え方でより直感的に理解するために、このプログラムを考えてみましょう。
let x = vec![1, 2];
let p: &'a i32 = if random() {
&x[0] // Loan L0
} else {
&x[1] // Loan L1
};
ここで、リージョン 'a は {L0, L1} という集合に対応します。なぜなら、ローンL0によって生成されたデータに参照できるかもしれませんが、ローンL1のデータに参照できる可能性もあるからです。
Datalog
この記事全体を通して、分析をDatalogのルールを使用して定義していきます。Datalogは、ある意味で、効率的な実行のために設計されたPrologの部分集合です。基本的に次のようなルールに対応します(Souffleプロジェクトの構文を使用)。
.decl cfg_edge(P:point, Q:point)
.input cfg_edge
.decl reachable(P:point, Q:point)
reachable(P, Q) :- cfg_edge(P, Q).
reachable(P, R) :- reachable(P, Q), cfg_edge(Q, R).
ここからわかるように、Datalogプログラムは事柄間の関係を定義します。ここでは、それらの関係は.declで宣言されています[5]。一部の関係は.inputで宣言された入力であり、その値はユーザーによって事前に与えられます(これらは事実とも呼ばれます)。このプログラムでは、それが cfg_edge です。reachable のような他の関係は、それらの事実から新しい事柄を合成するルールを介して定義されます。Prologと同様に、大文字の識別子は変数であり、変数が2回現れる場合は常に同じ値を持つ必要があります。
Datalogは、その部分集合であるため、Prologのより「プログラミング言語」的な特性の多くを回避します。例えば、Datalogプログラムは、有限の事実の集合に対して実行される場合(上記の例のように再帰する場合でも)、常に終了します。また、Datalogプログラムでは否定的な推論を使用しても問題ありません。なぜなら、否定的なサイクルを排除しているからです。「論理的な否定」と「失敗としての否定」の区別に関する微妙な懸念はありません[6]。
これらのルールを実装するために、私はFrank McSherryの素晴らしいdifferential-dataflowクレートを使用しています。これは非常に良い経験でした。慣れてしまえば、Datalogルールを非常に直接的な方法で変換できるため、新しい設計をわずか1〜2時間で迅速にプロトタイプ化できました。さらに、結果の実行はかなり高速です(最新の設計でパフォーマンスをあまり測定していませんが)。
リージョン変数
リージョンをローンの集合として説明しましたが、今はそれをすべて忘れてください。私が定義した分析は、少なくとも初期段階では、それらの集合を直接操作しません。代わりに、「リージョン変数」を使用してすべてのリージョンを表します。これらを '0、'1 などの「番号付き」リージョンとして示します。
プログラムをこれらの抽象リージョンを使用して書き直すと(基本的に、MIRがリージョンを持つあらゆる場所に番号付きリージョンを配置すると)、次のようになります。
fn main() {
let mut x: i32 = 22;
let mut v: Vec<&'0 i32> = vec![];
let r: &'1 mut Vec<&'2 i32> = &'3 mut v;
let p: &'5 i32 = &'4 x;
r.push(p);
x += 1;
take::<Vec<&'6 i32>>(v);
}
fn take<T>(p: T) { .. }
これらの抽象リージョンは、Datalogルール全体に現れます。ここでは「R」を「リージョン」として示します。
リージョン間の関係
先ほど見た抽象リージョンは、現時点では意味を持ちません。次に、型システムのルールを標準的な方法で適用します。これにより、前述の「サブセット」関係がリージョン間に生じます。例えば、例Aの次の行を考えてみましょう。
let p: &'5 i32 = &'4 x;
ここでは、式 &'4 x は &'4 i32 型の値を出力します。この型は p の型 &'5 i32 のサブタイプでなければならないため、次のようになります。
&'4 i32 <: &'5 i32
これは '4: '5 を必要とします。プログラムを見ると、多くのサブタイプ関係が生じていることがわかります。それぞれの関係を、結果のサブセット関係とともに書き出します。
fn main() {
let mut x: i32 = 22;
let mut v: Vec<&'0 i32> = vec![];
let r: &'1 mut Vec<&'2 i32> = &'3 mut v;
// 必要条件: &'3 mut Vec<&'0 i32> <: &'1 mut Vec<&'2 i32>
// => '3: '1, '0: '2, '2: '0
let p: &'5 i32 = &'4 x;
// 必要条件: &'4 i32 <: &'5 i32
// => '4: '5
r.push(p);
// 必要条件: &'5 i32 <: &'2 i32
// => '5: '2
x += 1;
take::<Vec<&'6 i32>>(v);
// 必要条件: Vec<&'0 i32> <: Vec<&'6 i32>
// => '0: '6
}
fn take<T>(p: T) { .. }
最終的に、これらのサブセット関係はシステムへの入力事実となります。後で明らかになる理由から、これらを「ベースサブセット」関係と呼びます。
.decl base_subset(R1:region, R2:region, P:point)
.input base_subset
言い換えると、base_subset(R1, R2, P) は P の時点で R1: R2 が真であることが要求されたことを意味します。
この base_subset 入力は出発点にすぎないことをすぐに確認します。これは最初に直接要求された関係を示しますが、任意の時点での関係の完全なセットを示すものではありません。なぜなら、サブセット関係は反復中に「蓄積」されるため、古い関係と新しい関係の両方を保証する必要があるからです。ここでは、両方を含む、より完全な subset 関係を定義しますが、それを行う前に、制御フローグラフを定義する方法を確認する必要があります。
制御フローグラフのポイント
この分析で使用される制御フローグラフは、MIRに基づいています。フローグラフのポイントを次のように定義します。
Point = Start(Statement) | Mid(Statement)
Statement = BBi '/' j
ここで、Statement は特定のステートメント(i番目の基本ブロックからのj番目のステートメント)を識別します。次に、ステートメントの開始ポイントと中間ポイントを区別します。開始ポイントは基本的に「何もしていない状態」であり、「中間ポイント」はステートメントが実行されている場所です。そのため、前のセクションのすべてのベースサブセット関係は、対応するステートメントの中間ポイントで定義されます。
フローをグラフ内で cfg_edge 入力を使用して定義します。
.decl cfg_edge(P:point, Q:point)
.input cfg_edge
当然、すべての開始ポイントには対応する中間ポイントへのエッジがあります。中間ポイントは、次のステートメントの開始ポイントへのエッジ、またはターミネーターの場合は、後続する基本ブロックの開始ポイントへのエッジを持ちます。
(ほとんどの場合、中間ポイントは現時点では無視できますが、後でライブネスの概念を統合する際に非常に重要になります。)
グラフを横断するサブセット関係の追跡
ここで、分析の最も興味深い部分、つまりサブセット関係の計算に進みます。直感を養うために、最終的な分析よりも単純な形式から提示し、その後、少し複雑にします。
ここでの鍵となる考え方は、分析が各リージョン変数の値を直接計算しないということです。代わりに、制御フローグラフの各ポイントで保持する必要があるサブセット関係を計算します。これらの関係は、「ベースサブセット」関係によって導入されますが、これは型チェックの結果です。その後、次のルールに従って制御フローエッジを横断して伝播されます。
- ベースサブセット関係が2つのリージョン
'a: 'bの間に導入されると、それは真でなければなりません。
これをDatalogで次のように定義できます。まず subset 関係から始めます。
.decl subset(R1:region, R2:region, P:point)
subset(R1, R2, P) が定義されている場合、P の時点で R1: R2 が真でなければならないということです。型チェッカーによって提供される「ベースサブセット」関係から始めることができます。
// Rule subset1
subset(R1, R2, P) :- base_subset(R1, R2, P).
サブセットは推移的なので、それも定義できます。
// Rule subset2
subset(R1, R3, P) :- subset(R1, R2, P), subset(R2, R3, P).
最後に、サブセット関係を制御フローグラフエッジを横断して伝播するルールを定義します。[7]
// Rule subset3 (version 1)
subset(R1, R2, Q) :- subset(R1, R2, P), cfg_edge(P, Q).
簡単です。娘が言うように、「イージーピー、レモン スクイーイー」。これらのルールを例Aに適用すると、各ステートメントの間に次のサブセット関係が得られます(ここでは各「開始」ポイントの関係のみを示し、完全な推移閉包は示していません)。それらは増え続けていることがわかります。
fn main() {
let mut x: i32 = 22;
// (なし)
let mut v: Vec<&'0 i32> = vec![];
// (なし)
let r: &'1 mut Vec<&'2 i32> = &'3 mut v;
// '3: '1, '0: '2, '2: '0
let p: &'5 i32 = &'4 x;
// '3: '1, '0: '2, '2: '0, '4: '5
r.push(p);
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2,
x += 1;
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2,
take::<Vec<&'6 i32>>(v);
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2, '0: '6
}
fn take<T>(p: T) { .. }
最終的な関係のセットを検討してください。これに基づいて、興味深いことがいくつか見えます。例えば、リージョン'4(つまり x の借用からのリージョン)とリージョン'0(つまりベクター v のデータからのリージョン)の間の関係を見ることができます。
'4: '5: '2: '0
これは基本的にプログラムのデータフローを反映しています。各リージョンを「ローンの集合」として考えると、これは'0(つまりベクター)が &x ステートメントから派生した参照を保持する可能性があることを示しています。これが次の分析部分につながります。
ボローリージョン
これまでのところ、リージョン変数間の関係を示すサブセット関係を導入し、それが制御フローグラフにどのように拡張されるかを示しました。今度は、どのリージョンがどのローンに依存しているかを追跡するために、これを行います。
まず、borrow_region という新しい入力を作成します。
.decl borrow_region(R:region, L:loan, P:point)
.input borrow_region
この入力は、プログラム内の各借用式(例:&x または &mut v)に対して定義されます。これは、借用からのリージョンと作成された抽象ローンを関連付けます。例Aを、各ポイントで作成されるボローリージョンを含めて注釈付けします。
fn main() {
let mut x: i32 = 22;
let mut v: Vec<&'0 i32> = vec![];
let r: &'1 mut Vec<&'2 i32> = &'3 mut v;
// borrow_region('3, L0)
let p: &'5 i32 = &'4 x;
// borrow_region('4, L1)
r.push(p);
x += 1;
take::<Vec<&'6 i32>>(v);
}
fn take<T>(p: T) { .. }
base_subset 関係と同様に、borrow_region は対応する借用ステートメントの中間ポイントで作成されます。
ライブリージョンとローン
通常のコンパイラ用語では、変数Xは制御フローグラフのポイントPでライブであるとは、その現在の値が後で使用される可能性があることを意味します(より正式には、PからQへのパスがあり、QがXを使用し、そのパスでXが代入されない場合)。
リージョンについても同様の定義ができます。リージョン'aは、ポイントPでライブであるとは、&'a i32 型の参照が後で逆参照される可能性があることを意味します。ほとんどの場合、これはライブ変数Xが存在し、'aがXの型に含まれていることを意味します。ただし、ドロップに関してはいくつかの微妙な点があります。デストラクタが使用するリージョンと使用しないリージョンを賢く理解しようとするためです(例:Vec<&'a u32> 型の値は、ドロップ時に'aにアクセスしないことがわかっています)。その仕組みの詳細はここでは説明しません。NLL RFCで定義されているものと同じですhttps://rust-lang.github.io/rfcs/2094-nll.html。
Datalogの観点から、region_live_at という入力を次のように定義できます。
.decl region_live_at(R:region, P:point)
.input region_live_at
ここでの初期値は、NLL RFCと同じように計算されます。
「要求する」関係
これで、制御フローグラフ全体にborrow_region関係を拡張できます。前と同様に、requires という新しい関係を作成します。
.decl requires(R:region, L:loan, P:point)
これは次のように読むことができます。
リージョンRは、ポイントPでローンLの条件を強制することを要求します。
または、別の言い方をすれば:
ローンLの条件がポイントPで違反された場合、リージョンRは無効化されます。
(「requires」という名前はあまり好きではありませんが、まだより良い名前を思いついていません。)
最初のルールは、借用のリージョンは常にそれに対応するローンに依存することを示しています。
// Rule requires1
requires(R, L, P) :- borrow_region(R, L, P).
次のルールは、R1: R2 の場合、R2 は R1 が依存するローンに依存することを示しています。
// Rule requires2
requires(R2, L, P) :- requires(R1, L, P), subset(R1, R2, P).
最後に、サブセットと同様に、これらの要求を制御フローエッジを横断して伝播できます。しかし、ここではひねりがあります。
// Rule requires3 (version 1)
requires(R, L, Q) :-
requires(R, L, P),
!killed(L, P),
cfg_edge(P, Q).
このルールは、リージョンRがポイントPでローンLを要求する場合、LがPで「キルされていない」限り、後続のQでもLを要求することを示しています。では、この!killed(L, P)ルールとは何でしょうか? killed 入力関係は次のように定義されます。
.decl killed(L:loan, P:point)
.input killed
killed(L, P) は、ポイントPがローンLで借用された参照の参照先を上書きする代入である場合に定義されます。次のようなものがあると想像してください。
let p = 22;
let q = 44;
let x: &mut i32 = &mut p; // `x` は `p` を指す
let y = &mut *x; // Loan L0, `y` も `p` を指す
// ...
x = &mut q; // `x` は `q` を指す; L0 をキルする
ここで、x は最初に p を参照し、それが y にコピーされます。この時点(...)で、*x へのアクセスは、y がそれを借用しているため、不正です。しかし、その後 x は q を指すように再代入されます。これにより、*x へのアクセスは *y とエイリアスしなくなります。これは、ローンL0をキルすることによって反映され、*x へのアクセスがもはや y を無効化しないことを示します。
これで、例Aを subset 関係と requires 関係の両方を含むように注釈付けできます。前と同様に、可能性のある完全な推移閉包は示さず、代わりに「ベースファクト」のみを示します。プログラムを進めるにつれて、それらが蓄積し続けていることがわかります。
fn main() {
let mut x: i32 = 22;
// (なし)
let mut v: Vec<&'0 i32> = vec![];
// (なし)
// Loan L0
let r: &'1 mut Vec<&'2 i32> = &'3 mut v;
// '3: '1, '0: '2, '2: '0
// requires('3, L0)
// Loan L1
let p: &'5 i32 = &'4 x;
// '3: '1, '0: '2, '2: '0, '4: '5
// requires('3, L0)
// requires('4, L1)
r.push(p);
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2,
// requires('3, L0)
// requires('4, L1)
x += 1;
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2,
// requires('3, L0)
// requires('4, L1)
take::<Vec<&'6 i32>>(v);
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2, '0: '6
// requires('3, L0)
// requires('4, L1)
}
fn take<T>(p: T) { .. }
特に、x += 1 ステートメントのエントリで保持されるファクトのセットを検討してください。
// '3: '1, '0: '2, '2: '0, '4: '5,
// '5: '2,
// requires('3, L0)
// requires('4, L1)
ローンL1はxの共有借用であり、'4はL1を要求することに注意してください。さらに、変数vは&'0 i32型の参照を保持しており、'4が'0のサブセットであることがわかります。
'4: '5: '2: '0
これは、ベクターv内の参照がxをミューテートすることによって無効化されることを意味します。なぜなら、それはL1の条件を無効化するからです。次の行でvが使用されることを考えると、それは問題です。そして、これはルール、エラーの定義の最後の部分につながります。
エラーの定義
そしてついに、借用チェックエラーとは何かを定義できます。invalidates(P, L) という入力を定義します。これは、ポイントPでのアクセスまたはアクションがローンLの条件を無効化することを示します。
.decl invalidates(P:point, L:loan)
.input invalidates
次に、ライブネスの概念をリージョンからローンに拡張します。ローンLは、ポイントPでライブであるとは、ライブなリージョンRがそれを要求することです。
.decl loan_live_at(R:region, P:point)
// Rule loan_live_at1
loan_live_at(L, P) :-
region_live_at(R, P),
requires(R, L, P).
最後に、ポイントPがローンLを無効化し、かつローンLがライブである場合にエラーとなります。
.decl error(P:point)
// Rule error1
error(P) :-
invalidates(P, L),
loan_live_at(L, P).
ライブネスによる制約伝播の洗練
これは、私が実装した分析のほぼすべてですが、1つの点を除きます。ライブネスを考慮に入れることで制約伝播をわずかに洗練でき、多くのプログラムを受け入れることができます。各ポイントで導入された主要なファクトを注釈付けしたこの例を考えてみましょう(これらのファクトは制御フローを通じて順方向に伝播することを忘れないでください)。
let x = 22;
let y = 44;
let mut p: &'0 i32 = &'1 x; // Loan L0
// '1: '0
// requires('1, L0)
p = &'3 y; // Loan L1
// '3: '0
// requires('3, L1)
x += 1;
// invalidates(L0)
print(*p);
このプログラムを受け入れることができれば良いでしょう。p は最初は x を参照しますが、後で y を参照するように再代入されるため、x += 1 を実行する時点ではローンは解放されている可能性があります。しかし、これまでのルールでは、情報を着実に蓄積しているため、これを拒否します。したがって、x += 1 を実行する時点では、requires('0, L0) が非常に簡単に導き出されます。
問題は、新しい変数を宣言するのではなく、既存の変数 p を再代入したことです。これにより、同じリージョン '0 が再利用されます。したがって、これを解決するには、プログラムを新しい変数を使用するように書き換えることができます。
let x = 22;
let y = 44;
let p: &'0 i32 = &'1 x;
let q: &'4 i32 = &'3 y;
x += 1;
print(*q);
しかし、それは満足のいく答えではありません。別の可能性は、SSA形式のようなもので書き直すことですが、それは基本的に上記の変換を自動化します。それは依然として選択肢ですが、私が選んだものではありません。とりわけ、MIRの変数は「プレース」であり、SSA形式を使用するとそれが少し複雑になります(つまり、変数は間接的に借用されたり代入されたりします)。
私が代わりにやったのは、ポイント間でサブセットおよび要求関係を伝播するルールを変更することでした。以前は、これらのルールは無差別に伝播するように定義されていました。今、後続のポイントでライブなリージョンの関係のみを伝播するように変更します。
// Rule subset3 (version 2)
subset(R1, R2, Q) :-
subset(R1, R2, P),
cfg_edge(P, Q),
region_live_at(R1, Q), // new
region_live_at(R2, Q). // new
// Rule requires3 (version 2)
requires(R, L, Q) :-
requires(R, L, P),
!killed(L, P),
cfg_edge(P, Q),
region_live_at(R, Q). // new
これらのルールを使用すると、元のプログラムは受け入れられます。重要な点は、p = &y の行に入るとき、変数 p は死んでいる(その値は上書きされようとしている)ため、そのリージョン '0 も死んでいることです。したがって、それに影響を与える requires(および subset)制約は順方向に伝播しません。
この改善は、現在のNLL分析では拒否される#47680の例を受け入れるためにも重要です。
struct Thing;
impl Thing {
fn maybe_next(&mut self) -> Option<&mut Self> {
..
}
}
fn main() {
let mut temp = &mut Thing;
loop {
match temp.maybe_next() {
Some(v) => { temp = v; }
None => { }
}
}
}
ここで問題は、temp.maybe_next() が *temp を借用することです。この借用は、時には v を介して返され、temp に(temp の値を置き換えて)格納されます。これは、トレースアウトすると、借用がループの周りでライブであることを意味します。再代入されたため「キル」されると考えるかもしれませんが、実際にはそうすべきですが、現在のルールでは、None が返されたときに temp が再代入されなかったため、そうではありませんでした。基本的に分析はループでつまずいていました。
新しいルールでは、Some パスに沿って、temp が再代入されるためローンがキルされることがわかります。一方、None パスに沿って、その時点では死んだリージョンにのみ関連付けられているため、requires 関係はドロップされます。したがって、プログラムは受け入れられます。
トップダウン対ボトムアップと因果計算
もちろん、実際のコンパイラでは、エラーがあるかどうかを知るだけでは不十分です。ユーザーにエラーをうまく報告できる必要もあります。NLL RFCでは、私が3点形式と呼んだエラー報告の手法を提案しました。
可能な限り、すべてのエラーを3つのポイントで説明しようとします。
- 借用が発生したポイント(B)。
- 結果の参照が使用されるポイント(U)。
- 参照を無効にした可能性のある介在ポイント(A)。
分析をDatalogルールのシリーズとしてフレーミングすることの興味深い副産物の1つは、各エラーを導き出した方法を見ることでこれらの3つのポイントを抽出できることです。つまり、例Aのエラー(不正な x += 1)を考えてみましょう。そのインクリメントがポイントPで発生した場合、error(P)をクエリすることでエラーを見つけられるかもしれません。Prologを使用している場合(「トップダウン」、つまり証明したい目標から開始して実行される)、次のような証明ツリーに遭遇する可能性があります。
error(P) :-
invalidates(P, L1), // input fact
loan_live_at(L1, P) :- // rule loan_live_at1
region_live_at('0, P), // input fact
requires('0, L1, P) :- // rule requires2
requires('4, L1, P) :- // rule requires3
...
subset('4, '0, P) :- // rule subset3
...
このツリーを見ると、知る必要があるすべてが含まれています。ポイントPにエラーがあるのは、(a)PがL1を無効にし、(b)L1がライブだからです。L1がライブなのは、'0がライブであり、'0がL1を要求するからです。'0がL1を要求するのは'4のため…といった具合です。抽出するものを決定するためのヒューリスティックを記述するだけです。
しかし、伝統的にDatalogはボトムアップで実行されます。つまり、すべてのベースファクトを計算し、次にそれらから導出されたファクトを計算します。これはより効率的ですが、それらのファクトがすべて最終的に必要ない場合は無駄になる可能性があります。トップダウンとボトムアップ伝播を組み合わせる技術(例:マジックセット)があります。また、Datalogから「説明」を取得する技術もあります。基本的に、特定のタプル(error(P)など)を導出するために必要な最小限のファクトのセットです。あるそのような技術は、differential-dataflowを使用して実装され、定義さえされています。これは素晴らしいことです。
私はまだこの方向ではあまり作業していませんが、この分析が望ましいものであることを確認しようとしています。しかし、この方向に行けば、良いエラー情報を引き出すことができることは明らかです。
質問は?
Rust internals boardのスレッドで議論のために開設しました。
感謝
このアイデアに影響を与えた数人の人々やプロジェクトに感謝の意を表したいと思います。まず、Frank McSherryの素晴らしいdifferential-dataflowクレートは、私がより速くイテレーションすることを可能にしました。非常に良いものです。
次に、コンパイラの型システムが従来のエイリアス分析とかなり異なるように動作する理由をしばらく考えていました。しばらく前に、Lionel Parreauxと、リージョンがプログラムパス上の正規表現であったRustの借用チェックの興味深い代替アプローチについて非常に興味深い会話をしました。その後、Rust All HandsでVytautas AstrauskasとFederico Poliと、RustをViper静的検証器と統合する彼らの取り組みについて話しました。これには、ここで説明されているサブセット関係と非常によく似たエイリアス関係を再設計する必要がありました。これらの取り組みを熟考し、最新のCプログラムでのエイリアス分析に関する多くの論文を再読しました。これは、多くの実験とイテレーションと組み合わさって、私をここに導きました。皆さん、ありがとう!
フットノート
- まだ
altとretキーワードを使用しており([https://github.com/rust-lang/rust/commit/50a3dd40ae8ae6494e55d5cfc29eafdb4172af52#diff-26be476d05bea7e3cd4e452d6104482dR1758](https://github.com/rust-lang/rust/commit/50a3dd40ae8ae6494e55d5cfc29eafdb4172af52#diff-26be476d05bea7e3cd4e452d6104482dR1758)、マッチアームに=>を使用していませんでした!面白い。そして、私にはまだ少し不可解です。↩︎ - そして、マクロは
foo!(..)ではなく#foo[..]のようでした([https://github.com/rust-lang/rust/commit/50a3dd40ae8ae6494e55d5cfc29eafdb4172af52#diff-20cc6d854aa3f056ddd3c36b7c257765R332](https://github.com/rust-lang/rust/commit/50a3dd40ae8ae6494e55d5cfc29eafdb4172af52#diff-20cc6d854aa3f056ddd3c36b7c257765R332)。pcwaltonがコード全体に「つぶれたクモ」が散らばっていると不平を言っていたのを覚えています。↩︎ - リージョンは学術界の標準用語なので、デフォルトで採用しますが、ここでは必ずしも適切な「直感」を伴わないかもしれません。より良い用語を探すべきかもしれません。↩︎
- 興味深いことに、これは
&'a u32型が'aに関して共変であることを意味しますが、以前は反変として最も自然に定義されていました。つまり、サブタイプはより小さい集合(ただしより大きいライフタイム)に対応します。これもRustユーザーにとって本当に重要なことではありませんが、型システムを深く掘り下げる人々にとっては良い特性です。↩︎ - これらの
.fooディレクティブは、私の知る限り、souffleに特有です。↩︎ - これらのルールでは否定を使用しますが、否定された入力という非常に単純な方法でのみ使用します。↩︎
- このサブセット伝播ルールは、後で改良するルールです。↩︎