ハクソク

世界を動かす技術を、日本語で。

木の借用

320日前原文(plf.inf.ethz.ch)

概要

Tree Borrows は、Rust言語の 所有権システム を活用した新しい状態機械モデル。 従来の Stacked Borrows よりも柔軟で、現実のunsafe Rustコードとの互換性向上。 30,000 の主要Rustクレートで54%多くのテストケースを許容。 PLDI'25 でDistinguished Paper Award受賞。 安全性と最適化の両立を目指す設計。

Tree Borrowsの状態機械とその特徴

  • Rustの 所有権型システム を基盤としたメモリ安全性保証
  • unsafeコード の利用により、型システムの保証が自動的に適用されない現状
  • 最適化のためには、 ポインタのエイリアス規則 の厳格な定義が必要
  • 既存のStacked Borrowsでは、現実のunsafe Rustコードでよく使われるパターンが拒否される問題
  • 新しい Tree Borrows モデルでは、スタック構造を ツリー構造 に置換
  • これにより、より多様なunsafeコードパターンへの対応が可能
  • Rust borrow checker の最新機能にも対応
  • 評価結果として、 Stacked Borrows よりも54%多くのテストケースを受け入れ
  • Rocq による証明で、Stacked Borrowsの最適化の多くを維持しつつ新たな最適化（例：read-read reorderings）が可能
  • 実装例や論文、ソースコードも公開

Tree Borrowsが解決する課題

  • unsafeコードによる 最適化の破壊 リスクの低減
  • 現実のRustコード でよく見られるunsafeパターンの許容
  • 最適化の正当性 を担保しつつ、開発者の利便性向上
  • Stacked Borrows の限界を克服する新しい理論的枠組み

Tree Borrowsの導入による効果

  • Rustコンパイラ による強力な最適化の実現
  • 安全性 と パフォーマンス の両立
  • Rustコミュニティ への貢献とエコシステムの発展
  • PLDI'25 での高評価（Distinguished Paper Award受賞）

参考資料・リソース

  • 論文（PDF）、Artifact、Source codeが 外部ページ で公開
  • 詳細な理論背景や実装例を確認可能

Hackerたちの意見

スタックド・ボロウズについては、2020年と2018年にスレッドがあったよ。 https://news.ycombinator.com/item?id=22281205 https://news.ycombinator.com/item?id=17715399

Ralf Jungの最近のブログ記事が、ちょっとした背景を提供してるよ。 https://www.ralfj.de/blog/2025/07/07/tree-borrows-paper.html ボーナス：Ralf JungがRustの操作的意味論を実行可能な形で正確に指定するためのグループの取り組みについての最近のトークもあるよ。 https://youtube.com/watch?v=yoeuW_dSe0o

論文からの引用: > Unsafeコードの問題は、こんなことができることだ: fn main() { let mut x = 42; let ptr = &mut x as *mut i32; let val = unsafe { write_both(&mut *ptr, &mut *ptr) }; println!("{val}"); } できないって？ 同じ変数に対して複数の可変参照を共存させるためにポインタを使うのは未定義動作だよ。もしかして、彼らが言おうとしているポイントを誤解してるのかな。

└

この場合の「can do things」は「やってもいい」という意味じゃないよ。「Unsafeコードは次のようなことを表現できるが、それはUBだ」ということ。

└

まさにその通りだと思う: 複数の可変参照を許さないという制約を破るのは簡単すぎる。Unsafeは、コードの有効性をRustのライフタイム分析で証明するのが難しい場合に使うためのもので、でもそれを悪用してもっと多くのことができちゃうんだ。

└

この研究の目的は、未定義動作の正確な境界を明確にすることだよ。確かに上のコードはRustコンパイラに受け入れられるけど、ルールを破ってるんだ。どのルール？ 本質的には、以下のことがわかってる: - ボロウチェッカーが受け入れるものは合法 - Unsafeは違法/未定義の動作を表現できる - ボロウチェッカーがチェックできる範囲よりも広い、合法/定義された動作のルールのセットがある この研究の目標は、そのルールのセットを正確に指定することなんだ。大まかなアウトラインは明確だけど（基本的に、書き込み可能なポインタがエイリアスしてはいけない）、詳細（内部ポインタ、イテレータの無効化、悪いポインタを作ることや使うことが悪いのか、など）は本当に難しい。前の論文、スタックド・ボロウズはシンプルだけど制約が厳しかったし、実際のunsafeコードはそのルールに違反することが多かった（見た目は正しいのに）。Tree Borrowsはより広範で、より多くのことを許容しつつ、証明可能に安全なんだ。

└

もうたくさんの返信が来てるし、これ以上増やしたくないけど、そこに意図があるのを一番わかりやすく見る方法は、次の段落の冒頭にあると思う: > Rustコンパイラの開発者が明らかにサポートしたいと思っているエイリアス最適化を考えると、上のような反例を考慮から「排除する」方法が必要だ。

└

同じ変数に対して複数の可変参照を共存させるためにポインタを使うのは未定義動作だ。そうだけど、どのルールを正確に破ってるの？ それがUBだと言う正確な定義は何？ Tree Borrowsはまさにその定義の提案なんだ。「コードはこんなことができる」というのは、「このコードを書いてコンパイルして実行すると何かが起こるけど、Tree Borrowsのようなものがなければ、このコードに何か問題がある理由はない」という意味だよ。君はすでにTree Borrowsのようなものが必要だと受け入れてるみたいだね（つまり、こんなコードはUBだと言うべきだ）。この論文のこの部分は、なぜTree Borrowsのようなものが必要なのかを主張してるんだ。 :)

└

彼らがここで言おうとしているポイントを誤解しているだけかもしれない。 「できる」という言葉を誤解してるよ。はい、unsafeコードではそれができる。で、はい、それは未定義の動作だよ ;)

著者の一人、ネヴン・ヴィラーニがセドリック・ヴィラーニ（フィールズ賞2010年）の息子だって気づいた。ほんと、親の背中を見て育つってやつだね。

└

ほんと、親の背中を見て育つってやつだね。 それに、彼らは木からいくつかの特性を借りているとも言えるね。ごめん、つい言いたくなっちゃった。

└

そういえば、昔、父親のオフィスの近くにいたことがあるよ :) でも、彼が政治に入る前の話ね。

Rustや将来のプログラミング言語が、異なる特徴（コンパイル速度、実行速度、アルゴリズムの柔軟性など）を持つ複数の借用チェッカー実装を許可するように進化するのかな。プロジェクトが選べるように。

└

それがどう機能するのか全く想像できない。異なる借用ルールが適用されることを期待するコードを組み合わせることはできないよ。実質的に、借用チェッカーの実装の数だけサブ方言を作ることになる。

└

現在のコンパイル速度や実行速度に何か問題があるの？

└

すでに、アフィン型（Rustが使ってるやつ）、線形型、効果、依存型、形式的証明を通じて複数のアプローチがあるからね。実装やパフォーマンス、開発者体験において、それぞれ異なるコストと能力がある。で、Rust以外の他の言語が実際に目指しているのは、自動リソース管理の生産性（方法は問わず）、それに上記の型システムの一つを組み合わせて、パフォーマンスが重要なコードパスだけに適用することだよ。

└

俺の理解では、借用チェッカーは偽陰性はあるけど、偽陽性はないってことで合ってる？ちょっとバカな質問かもしれないけど、複数の実装を並行スレッドで走らせて、最初にポジティブな結果が出たやつが勝ちってできないの？

└

それだとエコシステムが分裂しちゃうから、あんまり良くないよね。

すごい仕事だね。数年前にネヴンのウェブサイトでTree Borrowsの仕様を読んで、かなり印象的だったのを覚えてる。結構厄介な問題を優雅に解決してるんだよね。私の経験では、確かに[1][2] Stacked Borrowsでは違法な合理的なコードを許可している。

うーん、論文の例4で示されている以下のRustコードが拒否されるっていう主張を試してみたんだけど、安定版コンパイラではそうならないみたい？

fn write(x: &mut i32) {*x = 10}
fn main() {
    let x = &mut 0;
    let y = x as *mut i32;
    //write(x); // これが暗黙の二段階借用を使うはず
    *x = 10; // これはダメなはずで、コンパイラに拒否されるべき
    unsafe {*y = 15 };
}
└

スタックされた借用はMiriのランタイムモデルだよ。Miriで実行すると、*x = 10;のバージョンではエラーが報告されるけど、write(x);のバージョンでは報告されないのがわかるよ。「未定義の動作: [...]を使って書き込みアクセスを試みたが、この場所の借用スタックにはそのタグが存在しない」rustc自体はどちらのバージョンも拒否する理由がないんだ。なぜなら、yは*mutで、xの&mutとは借用やライフタイムの関係がないから、コンパイル時や型システムの観点から見るとね。