リバース（逆方向）での借用チェックの新しい考え方

リバース（逆方向）で考える借用チェックの新しい方法

時間を逆行して、未来を知る

2026年10月18日 —

奇妙なアイデアを思いつき、それがうまくいったものの、なぜか信じられないような経験をしたことはありませんか？

それが、Valenの借用チェッカーについて今感じていることです。

なぜなら、それは時間を逆行するからです。

あるいは、ドラマチックに言わないとすれば、それは関数を逆方向に辿ることであり、それは依然として非常に奇妙です。

数年前、関数を逆方向にイテレートするのが良いと言われたら、私はあなたをクレイジーと呼んだでしょう。

実際、これにはいくつかの非常に良い理由があり、例えば最適化パスを行う際にはかなり一般的です0。しかし、メモリ安全性のチェックのためにこれを行った人はいないと思います。

借用チェックの世界を深く覗きたいなら、読み進めてください！

奇妙なことが起こるでしょう。1

これは借用チェックアルゴリズムのかなり深い内部構造の解説です。もしエピックでエンターテイニングなものを求めているなら、私の最近の記事「The Golden Spike, and Resurrecting the Vale(n) Programming Language」をご覧ください！

A New Way to Think About Borrow Checking (In Reverse)

• A weird kind of borrow checker

• ...and a weird, backwards implementation!

• Phase 2: Static Typing

• Phase 3: Static Grouping

• Phase 4: Safety Checking

• Another Example

• Why backwards?

• Reverse-Walking with Loops

• More towards Rust's borrow checker?

• That's all for now

0

あるいはデストラクタ挿入であり、そして今、メモリ安全性のチェックです！

1

この記事の0%はAIによって書かれました。詳細はこちら。

私のスタンス：誰かに何かを読む時間を使ってもらいたいなら、手書きで書く時間を使ってください。

読んでくれてありがとう=)

奇妙な借用チェッカー

これは通常の共有-XOR-ミュータブルな借用チェックではありません。

これはValenの借用チェッカーで、共有-XOR-ミュータブルをオプションにすることができ、Rust関数を呼び出すことができ、境界を越えてメモリ安全性を確保するものです。

Valenはまだ非常に実験的です。多くのものには穴や鋭いエッジがあり、v0.1が2月頃に来るまでそうである可能性が高いです。輝かしい数ヶ月にわたるリファクタリングのスプリーはすでに進行中です（だからこそこの新しい借用チェッカーなのです！）。Valenリポジトリを自由にチェックしてみてください、ただし注意してください、ここにはドラゴンがいます！2

Rustの借用チェッカーに似ていますが、メモリ安全なミュータブルエイリアシングも備えています。それについてもっと知りたい場合は、この記事をチェックしてください。ただし、この記事のほとんどではそれを理解する必要はありません。

2

具体的には緑のドラゴンです。

...そして奇妙な、逆方向の実装！

Valenは関数を4つのフェーズでコンパイルします3：

1. ソーステキストをASTに変換する、関数のパースを行います。
2. すべての変数、引数、式の型を決定する、静的型付けを行います。
3. 各参照がどの変数（またはどの変数のどの部分）を指しているかを知る、静的グルーピングを行います4。
4. 参照が無効化された後に使用されていないことを確認する、安全性チェックを行います。

以下でこれらすべてを説明します。

最も奇妙な部分は、#4が逆方向に実行されることです。 関数の最後のステートメントを見て、関数の先頭に達するまで逆方向に辿ります。

私の知る限り、これは安全性チェックを逆方向に行う唯一の借用チェッカーであるため、これは奇妙です5。

以下で、なぜ逆方向に行くのかを説明します（ヒント：利便性、ループ、速度）。

しかし、まずどのように機能するのか、そして逆方向に行くことが何を意味するのかを見てみましょう。

フェーズ1はスキップして、フェーズ2から始めます。

3

また、LLVMにどの操作がどのグループを変更する可能性があるかを記述するためにどの属性を送信するかを計算する秘密の5番目のフェーズもあります。しかし、それはこの記事の範囲外です。

4

また、任意のミュータブル効果によって無効化されるすべてのグループも特定します。

5

例えば：

• Rust（NLLと現在のPolonius）は、領域推論のために制約を解き、次に順方向のパスで競合をチェックします。（rustcは各変数がどこで使用されているかを特定するために逆方向のスキャンを行いますが、実際のメモリ安全性チェックは順方向のパスで行われます。）
• Valeの型付けパスは領域を決定し、その後、実行時の世代チェックを安全にスキップできる時期を決定する領域借用チェックを順方向のパスで行います。（Valeの領域借用チェッカーは、実際にはインストゥルメンター/モノモーフィザーと融合されていました。）
• Valenの以前の借用チェッカーもValeと同様でした。型付けパスはグループを決定し、その後、後続の順方向パスが、すべての使用箇所で、それが「無効化」されてからより最近に宣言されたかどうかをチェックしていました。
• 他の借用チェッカーもたくさんありますが、安全性チェックを逆方向に行っているという話は聞いたことがありません。もし知っている人がいたら教えてください！

フェーズ2：静的型付け

静的型付けパスは、一部の人には馴染みがあるでしょう。変数の型を割り当てます。

例えば、このプログラムを次のように変換します。

exported func main() {
  let fuel = 5;
  let force = fuel;
}

次のように変換します。

exported func main() {
  let fuel i64 = 5;
  let force i64 = fuel;
}

これはかなり標準的で、多くのコンパイラが行っています。

コンパイラは通常、これを順方向のパスとして、関数の先頭から末尾までを辿りながら型を決定します。

フェーズ3では、これと似ていますがより奇妙なことを行います。フェーズ3は静的グルーピングを行います。

フェーズ3：静的グルーピング6

これは別の順方向パスで、各参照がどこを指しているかを決定します。

例えば、このプログラムでは：

func print_first_fuel_cell(s &Ship) {
  let first_ref = &s.fuel_cells[0];
  print_int(first_ref);
}

静的グルーピングは、first_refがs.fuel_cells[]を指していることを決定します7：

func print_first_fuel_cell(s &Ship) {
  // 静的型付けは言う:   first_ref &int
  // 静的グルーピングは言う: first_ref &int in s.fuel_cells[]
  let first_ref = &s.fuel_cells[0];
  print_int(first_ref);
}

つまり、s.fuel_cells[]配列内のどこかのintを指しているということです。

この情報は、次のフェーズで使用されます。このフェーズが実際に使用後解放（use-after-free）をチェックします。

6

「グループ」という言葉は、おそらくすぐに使わなくなり、「パス」に切り替えるでしょう。意見を歓迎します！

7

V1の静的グルーピングフェーズでは、参照がいつ作成されたかも決定していました。例えば、s.fuel_cells[]の&intではなく、7.2行目のs.fuel_cells[]の&intであることがわかっていました。これは非常に素晴らしく、私たちは文字通り時間と空間の情報を変数の型に密輸していました。この新しいV2バージョンは、次のセクションでわかるように逆方向スキャンを行うため、これを行う必要はありません。

フェーズ4：安全性チェック

この記事は半分は楽しみのためですが、アルゴリズムへのフィードバックを求めるためでもあります。私は誰もこの方法でやったことがないと思うので、それには良い理由があるかもしれません。このアプローチに問題が見つかった場合は、コメントを残して、修正（または却下！）できるように協力してください8。

これでフェーズ3で計算されたすべてを使用できます！

これが使用後解放（use-after-free）をチェックするフェーズです。

これは逆方向のスキャンで行われます、予言された通り。

少し大きな例でそれがどのように行われるか見てみましょう。

struct Entity { hp int; buffs []int; }
func add_buff(self &Entity mut) { ... }

func foo(e &Entity mut) {
  let buff = &e.buffs[0];
  e.add_buff();
  print_int(buff);
}

このプログラムは使用後解放を行っており、コンパイラに警告してもらいたいのです。

まず、より明示的な構文にデシュガーします。

struct Entity { hp int; buffs []int; }
func add_buff<g'>(self &Entity in g) mut(g) { ... }

func foo<g'>(e &Entity in g) mut(g) {
  let buff = &e.buffs[0];
  e.add_buff();
  print_int(buff);
}

ここで、逆方向スキャンが実行されるにつれて決定されるコメントを追加します。

以下で、「DECLARE」、「USE」、「MUTATE」の意味を説明します。

struct Entity { hp int; buffs []int; }
func add_buff<g'>(self &Entity in g) mut(g) { ... }

func foo<g'>( 
  e &Entity in g          // DECLARE e (group g)
) mut(g) {
  let buff = &e.buffs[0]; // DECLARE buff (group g.buffs[])
  e.add_buff();           // USE e (group g)
                          // MUTATE group g
  print_int(buff);        // USE buff (group g.buffs[])
}

アルゴリズムは関数の末尾から先頭に向かって逆方向にスキャンします。

上にスキャンしながら、これらのイベントを探します。

• 変数をUSEしたとき、保留リストに追加します。
• 何かをMUTATEしたとき、保留中の変数が無効化されていないことを確認します。
• 変数をDECLAREしたとき、保留リストから削除します。

pendingには、後でUSEされることが期待されるすべての変数が含まれています。

MUTATEが保留中のものに影響しないことを願っています。

これは、pendingに「関数内の後で/下でいつか使用される」すべての変数が含まれており、それまで有効であるべきだと考えるのが最良の方法だと思います。

それを本当に理解するために、実際に動作する様子を見てみましょう。

まず、最後の行を見ます。

  print_int(buff);        // USE buff (group g.buffs[])

これはUSEなので、保留リストに追加します。pendingには次が含まれます。

• buff (group g.buffs[])

次に、逆方向に進み、その上の行に遭遇します。

  e.add_buff();           // USE e (group g)
                          // MUTATE group g

MUTATEが見つかったので、保留中の変数が無効化されていないことを確認します。

具体的には、pendingのいずれかがeの下にあるものを指していないことを確認します。

• buff (group g.buffs[]) ... これは一致します！コンパイルエラーを表示します。

ここで何が起こったのか：buffはg.buffs[]を指していましたが、これはadd_buffでミューテートされたgから始まります。これは、buffが使用される行よりも上で無効化されていることを意味し、これは使用後解放です。

したがって、コンパイラはここでエラーを表示します。やったー！

8

最初に壊した人に賞品をあげます！

別の例

正しいプログラムを見て、宣言に遭遇する逆方向ウォークを見てみましょう。

同じプログラムですが、e.add_buff();を関数の最初の行になるように上に移動させました。

struct Entity { hp int; buffs []int; }
func add_buff<g'>(self &Entity in g) mut(g) { ... }

func foo<g'>( 
  e &Entity in g          // DECLARE e (group g)
) mut(g) {
  e.add_buff();           // USE e (group g)
                          // MUTATE group g
  let buff = &e.buffs[0]; // DECLARE buff (group g.buffs[])
  print_int(buff);        // USE buff (group g.buffs[])
}

前と同様に、末尾から開始し、この行に到達します。

  print_int(buff);        // USE buff (group g.buffs[])

...そしてそれがUSEであることを見て、buffを保留リストに追加します。

• buff (group g.buffs[])

次に1行上に進み、この行を見ます。

  let buff = &e.buffs[0]; // DECLARE buff (group g.buffs[])

これはbuffをDECLAREするので、保留リストから削除します。

pendingは空になりました。

（これは、後で/下で関数で使用される変数が存在しないことを意味します。）

次に1行上に進み、この行を見ます。

  e.add_buff();           // USE e (group g)
                          // MUTATE group g

MUTATEが見つかったので、保留中の変数が無効化されていないことを確認します。

保留中の変数がないため、何も起こりません。

次にeをUSEするので、それを保留リストに追加します。

• e (group g)

そして関数の終わりです！

MUTATEが保留中の変数をミューテートするのを見ることなく最後まで到達したので、プログラムはメモリ安全です。

なぜ逆方向なのか？

3つの理由があります：利便性、ループ、速度。

一般的に、逆方向に行くことは、いつ物が最後に使用されたかを把握するのに便利です。

例えば、この関数を見てみましょう。

func attack(a &Entity in g, d &Entity in g) mut(g) {
  let a_power = a.calculate_attack_power();
  let a_energy_cost = a.calculate_attack_cost(d);
  let d_armor = d.calculate_defense();
  let d_energy_cost = d.calculate_defend_cost(a);
  a.use_energy(a_energy_cost);
  d.use_energy(d_energy_cost);
  d.damage(a_power - d_armor);
}

aが宣言されたときにブックキーピングXを行い、aが不要になったときにブックキーピングYを行いたい場合9、2つの選択肢があります。

• 順方向スキャンを実行します。aの宣言に遭遇し、Xを実行します。次に、aの使用を記録しながら続行します。関数の終わりに到達したら、最後に記録された場所にフェッチ/ナビゲートして、Yを実行します。
• 逆方向スキャンを実行します。aの最後の使用に遭遇し、Yを実行します。次に、aの宣言を探しながら続行します。見つけたら、Xを実行します。

順方向スキャンでは、最後の使用を認識できなかったため、追加のフェッチ/ナビゲートが必要だったことに注意してください。

逆方向スキャンはよりシンプルでした。

デストラクタ挿入で逆方向スキャンが役立つ別の例を見るには、私のLLVMトーク（2024年）をご覧ください！多くのコンパイラ開発者が言うように、逆方向にスキャンすることは多くのことに役立ちます。

逆方向に行くことは、ループにとっても優れています。

ループについて考えるために使用している例をいくつか示します10。

これは正しいプログラムですが、observe(e)が有効かどうかを知るのがいかに難しいかを示しています。

exported func main() {
  let arr = ArrayList<int>(3);
  let e = &arr[0];
  
  while ... {
    observe(e); // 有効な `e` の使用。
    add_element(&arr);
    set e = &arr[0];
  }
}

そのeは実際には2つの異なる場所から来る可能性があります。

• ループの前の e = &arr[0];
• ループの最後の set e = &arr[0];

ループのobserve(e)に遭遇する順方向スキャンは、それが有効であると結論付けるために、先読みしてset eを見る必要があります。

これは似たような例ですが、set eはありません。

exported func main() {
  let arr: ArrayList<int> = ...;
  let e = &arr[0];

  while ... {
    observe(e); // 無効な `e` の使用。
    add_element(&arr);

  }
}

set eがない場合、ループ内のeはループの前のイテレーションによって無効化されます。

順方向スキャンを行った場合、eを復活させるset eがないことを確認するために、先読みする必要があります。

これは難しい問題です。次のことができます。

• それらのsetを検索するために先読みする（その後、ジャンプバックする）。
• より多くの情報を得るまで、順方向パスを繰り返し実行する（「データフロー固定点」）。
• 順方向パスを実行して情報を収集し、後でチェックを延期する。

最後のものは魅力的でした。 alas、そのデータ構造は非常に複雑になり、上記のfunc attack例と同じ「フェッチ/ナビゲート」の問題がありました。

V2の逆方向ウォークアプローチに直接移行する方が簡単でした。

また、V2のアプローチの方が高速であると確信しています。なぜなら、フェーズ3の順方向パスで各ノードを1回、フェーズ4の逆方向パスで1回処理するだけで済むからです11。

まだベンチマークしていませんが、大きな塩で取ってください12。

しかしもちろん、逆方向ウォークアプローチはループを無料では提供しません。まだ調整が必要です。

9

このブックキーピングは、参照カウントをデクリメントしたり、デストラクタ呼び出しを追加したり、使用後解放をチェックしたりすることなどです。

10

これらの例ではArrayListという名前を使用していますが、実際のValenコンパイラでは、歴史的な理由からArrayと呼ばれています。それはすぐに変更されます。

11

このアルゴリズムがまだO(n)であることを意味するわけではありません。MUTATEはまだ保留リストのすべてをチェックする必要があります。しかし、そのチェックを大幅にスピードアップする方法があると思います。指をクロスさせてください！

12

V1には完全なループサポートがなかったため、ベンチマーク対象は実際にはありません。

ループでの逆方向ウォーク13

アルゴリズムはループを処理するために少し追加が必要です。

具体的には、MUTATEとDECLAREの処理方法を変え、LOOP STARTにも反応します。

逆方向にスキャンし、これらのイベントを探します。

• 変数をUSEしたとき、保留リストに追加します。

• 何かをMUTATEしたとき：

  • 保留中の変数が無効化されていないことを確認します。
  • ミューテーションを、それが含まれるループのmutations_after_thisリストに追加します。

• 変数をDECLAREしたとき：

  • 保留リストから削除します。
  • mutations_after_thisのいずれかによって無効化されていなかった場合、それをループのrevived_after_thisリストに追加します。

• LOOP STARTに到達したとき：

  • 保留リストの各項目について、ループのmutations_after_thisによって無効化されている場合、それがループのrevived_after_thisにも含まれていることを確認します14。

これがこの例に何をするか見てみましょう。これは正しいプログラムなので、コンパイルエラーは発生しないはずです。

exported func main() {
  let arr: ArrayList<int> = ...; // DECLARE arr (group arr)
  let e = &arr[0];               // DECLARE e (group arr[])
  
  while ... {                    // LOOP START
    observe(e);                  // USE e (group arr[])
    add_element(&arr);           // MUTATE arr (group arr)
    set e = &arr[0];             // DECLARE e (group arr[])
  }
}

逆方向にウォークしているので、最後の行から開始します。

    set e = &arr[0];             // DECLARE e (group arr[])

これはDECLARE15なので、2つのことを行います。

• 保留リストから削除します。リストに含まれていないので、何も起こりません。
• それが含まれるmutations_after_thisのいずれかによって無効化されていなかった場合（空なので無効化されていません）、revived_after_thisに追加します。

revived_after_thisには現在1つのエントリが含まれています：e。

次に1行上に進み、これを見ます。

    add_element(&arr);           // MUTATE arr (group arr)

これはMUTATEなので、2つのことを行います。

• 保留中の変数が無効化されていないことを確認します。pendingは空なので、何も起こりません。
• ミューテーションを、それが含まれるループのmutations_after_thisリストに追加します。

mutations_after_thisには現在1つのエントリが含まれています：arr。

次に1行上に進み、これを見ます。

    observe(e);                  // USE e (group arr[])

これはUSEなので、保留リストに追加します。

pendingには現在1つのエントリが含まれています：e (group arr[])。

次に1行上に進み、ループの開始を見ます。

  while ... {                    // LOOP START

そこでLOOP STARTチェックを行います：保留リストの各項目について、ループのmutations_after_thisによって無効化されている場合、ループのrevived_after_thisにも含まれていることを確認します。

この場合、pendingにはe (group arr[])が含まれています。eはmutations_after_thisのいずれかによって無効化されています。したがって、ループのrevived_after_thisに含まれているか（含まれています）を確認します。チェックはパスし、問題ありません。

上の2つのDECLAREの説明はスキップします。以前にカバーしたためです。

そして関数の先頭に到達します！エラーは発生しなかったので、借用チェッカーはこの関数はメモリ安全であると結論付けることができます。

これで、この新しい逆方向借用チェッカーでループを処理する方法は終わりです！

13

イースターエッグノート！

Sergeant Stubbyは第一次世界大戦中の第102歩兵連隊のマスコットであり、フランスに部隊と共に渡り、フランス人と共に戦いました。彼は18ヶ月間勤務し、西部戦線で17回の戦闘と4回の攻勢に参加しました。

彼は金メダル、負傷者用ストライプ、パープルハート2つを含む多くの賞を受賞しました。

Sergeant Stubbyは、大戦で最も勲章を受けた軍用犬であり、戦闘を通じて軍曹に推薦・昇進した唯一の犬と呼ばれています。

(出典：Wikipedia)

このノートを見たら、「gold」という単語をコメントに忍ばせてください！

（timpi4everとgavinmorrowが最初に見つけたことに祝意を表します！）

14

ここではpendingから何も削除しません。なぜなら、それらのpendingの使用は、ループより上のコードによって満たされる必要があるからです。

15

はい、DECLAREと呼んだことを後悔しています。実際には、これは既存の変数を再ポインタしているだけです。

Rustの借用チェッカーに近づく？

最終的に変更したいもう1つの大きなことがあります。

Rustには、参照のライフタイムを決定するために、関数のどこからでも事実を使用できる非常に便利な機能があります。

例えば、このRustプログラムは、後続のr = &b[0];を見て、rがaまたはbを指していることを決定します。

fn main() {
  let a = vec![1, 2, 3];
  let b = vec![4, 5, 6];

  let mut r = &a[0];
  if some_condition() {
    r = &b[0];
  }
  println!("{}", r);
}

Valenはまだこれをしていません。Valenのフェーズ3（静的グルーピング）は、まだ通常の一次元の推論を行っています。

しかし、フェーズ3をrustcが行うような完全なソルバーに変更すれば、同様のスーパーパワーを得ることができます。

クールな点：これはフェーズ4の逆方向パスを変更する必要はありません。最終的には、フェーズ3のためのソルバーと、フェーズ4のための逆方向パスを持つことになります。

それが私にとってどれほどクールかを説明するのは難しいです。このような瞬間があるからこそ、私はコンパイラオタクなのかもしれないと疑っています。やったー！

今はここまで

Valenの借用チェッカーはまだかなり若く、わずか3,600行です。

そして、まだ完成していません！制御フローの中断（break、continue）16、関連グループ、クロージャ17など、多くのことを追加する必要があります。すべて楽しいものです。

いつかそこに着くでしょう。その日は輝かしいものになるでしょう。

読んでくれてありがとう！

次のいくつかの記事では、参照カウントと世代参照をどのようにブレンドするかについてさらに説明する予定です。また、この種の新しいメモリ安全性アプローチを探求している他のすべての言語（Ante、Carbon、Zeta、Fang、exclusion typingなど！）についても書くつもりです。

これは氷山の一角に過ぎないので、RSSフィード、r/valenを購読するか、Valen Discordに参加して最新情報を入手してください。そして、BlueskyとMastodonで私をフォローしてください！

乾杯、

• Evan Ovadia

16

現在の計画は、まず借用チェッカーが型付きASTではなく制御フローグラフを参照するようにリファクタリングすることです。これにより、制御フローの中断がはるかに容易になるはずです。

17

クロージャについては非常に興奮しています。非常にエレガントな解決策を見つけたと思います。続報をお待ちください！