2026-10-19 — Valen 的借用檢查器改成從函式尾端往回掃

Valen 的借用檢查器改成從函式尾端往回掃

Verdagon（Evan Ovadia）部落格 · 2026-10-18

Rust 的借用檢查先解一輪區域（region）限制式，再由前往後掃描找衝突；Valen 把後半段整個倒過來，安全檢查從函式最後一行往第一行走。作者 Evan Ovadia 在這篇文章中說明，Valen 是實驗性語言，借用檢查器目前只有 3,600 行，尚未完成。

原本的問題

文章指出，Rust 的 NLL 與 Polonius 都是先做區域推導的限制式求解，再用一趟順向掃描偵測衝突。Valen 先前的檢查器也是順向：每遇到一次使用，就確認該參考的宣告時間比最近一次失效更晚。

迴圈是順向掃描的痛點。迴圈內的某次使用，可能因為迴圈尾端的 set 才合法，也可能因為上一輪迭代的修改而非法。作者列出三種補救：往前看、重複跑不動點（fixpoint）、延後檢查，但他認為這些都會增加複雜度，還要多一道去找「最後一次使用」的步驟。

核心改動：四個階段與倒著走的第四階段

Valen 對每個函式做四個階段：解析成 AST、靜態型別、靜態分組（記錄每個參考指向哪個變數或變數的哪一部分，並寫進參考的型別），最後才是安全檢查。只有第四階段是倒著走，用來抓 use-after-free。文章也提到另有一個未公開細節的「第五階段」，負責輸出 LLVM 屬性。

倒著走時維護一個 pending 集合，裡面是「後面還會用到、因此必須保持有效」的變數。三條事件規則如下：

USE：把變數加入 pending。
MUTATE：檢查這次修改有沒有讓 pending 裡的任何變數失效。
DECLARE：把變數從 pending 移除，因為再往前它還不存在。

因為是從尾端往回走，「之後有沒有人還要用」這個資訊在走到修改點時已經在手上，不必另外往前探查。

Before / after 對照

下面是文章給的 use-after-free 例子。buff 先指進 e.buffs[0]，再被 add_buff 讓底層陣列可能搬家，最後才使用。倒著走時，先遇到 USE buff（加入 pending），再遇到 MUTATE group g，此時 buff 的群組 g.buffs[] 在 pending 內，所以報錯。

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

把修改移到宣告之前，倒著走時先看到 DECLARE 把 buff 移出 pending，再遇到 MUTATE 就沒有衝突：

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

迴圈怎麼處理

迴圈靠兩個額外集合：MUTATE 時把修改記進所屬迴圈的 mutations_after_this；DECLARE 時若之後沒有修改使它失效，就加入 revived_after_this。走到 LOOP START 時，凡是 pending 中會被 mutations_after_this 弄失效的變數，也必須出現在 revived_after_this，否則報錯。

while ... {                    // LOOP START
  observe(e);                  // USE e (group arr[])
  add_element(&arr);           // MUTATE arr
  set e = &arr[0];             // DECLARE e (group arr[])
}

這段會被接受：e 在迴圈尾端被重新指派，所以下一輪開頭的 observe(e) 用到的是新值。順向掃描要靠額外機制才能得出同一結論。

影響範圍

目前只影響 Valen 本身。文章說 Valen 的 v0.1 目標在二月，並可在記憶體安全的前提下呼叫 Rust 函式，後端是 LLVM，檢查結果會轉成描述「哪些操作改動哪些群組」的屬性。Rust 使用者不需要改任何東西，但寫編譯器或做靜態分析的人可以拿這個倒向模型與 NLL 對照。

限制也相當明確。文章寫到尚未支援 break、continue 這類中斷控制流、關聯群組與閉包，計畫先把檢查器搬到控制流圖（CFG）上。第三階段目前只做單向推導；若將來換成像 rustc 那樣的完整求解器，第四階段的倒向掃描不必改。

複雜度尚未達 O(n)，因為 MUTATE 要檢查 pending 的每個項目。
每個節點在第三階段順向掃一次、第四階段倒向掃一次；作者表示沒有做過效能測試。
作者自己也說檢查器「遠未完成」，做法可能有缺陷而需要推翻重來。

原始來源：Verdagon 部落格原文、Valen 專案

End of article