Valen 的借用檢查換了新思路

Verdagon 這篇文章談的是 Valen 的借用檢查器。作者一開頭就把它放進更大的問題：他說自己「long suspected」，要找到他口中的 holy grail，得先解開三個記憶體安全的挑戰。第一個是做出更寬鬆的借用檢查器，第二個是讓借用檢查器讀得懂更複雜的資料，第三個是讓這兩套系統同時運作。文章明說主要處理第一個，所以下面談的大致都屬於「更寬鬆」這一塊，參照計數與世代參照要等後續幾篇。

點操作按鈕，看哪些參照失效 · 3 個操作 × 4 個參照

world.entities.push(…) step(world, entity) 改動整個 world 重來

尚未執行任何操作，四個參照都可用。表格每一列是單獨執行該操作的結果，按鈕則會累積。

上面這張圖是整套規則的縮影。左邊是 World 結構底下的四條路徑，每條路徑各有一個參照指著它；右邊的表是單獨執行某個操作時，四個參照各自的下場。你可以連續按幾個操作，看失效怎麼累積：失效的永遠是被動到的路徑「裡面」的參照，指著該路徑本身的那個照常可用。這個方向的區別是全文最需要先記住的一件事，後面每個例子都在重複它。

路徑：單一所有權之下，每個物件只有一條

Valen 的借用檢查建立在單一所有權上，作者的原話是「Valen's borrow checker is based on single ownership, like C++ and Rust.」每個值都歸一個擁有者，可能是外層物件、陣列、堆疊框或全域變數。擁有者只有一個，路徑也就只有一條。作者寫的是「Every piece of data has only one owner (because single ownership), so every object has one path.」這是我的推論，文章沒有這樣寫：檢查器大概不需要去追「這個物件還有誰在持有」，因為答案只有一個。不過作者自己在腳註提醒，這並非絕對，下文會再提到。

作者用一條階梯說明單一所有權是許多語言共同的地基：加上不受限制的指標與參照，得到 C++；加上世代參照與 region borrowing，得到 Vale；加上檢查排他性的參照，得到 Rust；加上 group borrowing 與其他幾個機制，就是 Valen。在這個架構裡，差別大致在於單一所有權之上疊的是哪一層參照規則。

路徑從哪裡開始，文章列了三種起點：區域變數（例如範例裡的 world）、函式參數，以及函式的「group parameter」，後者作者說稍後才會談到。起點後面可以接的延伸，文章列了像是這幾種：.diameter 這類成員名稱、[] 代表集合的元素、.SomeType 代表 union 的某個變體，作者說另外還有幾種選項，稍後才會談。文中的例子是 world.entities[]，作者把它讀成「world's entities's elements」。上面的圖用的就是這套寫法：world.entities[].hp 讀作「world 的 entities 的元素的 hp」。

文章沒有替「group」下一個正式定義，只用例子帶過：entity in world.entities[] 指向的是「somewhere in the group」，也就是活在 entities 陣列裡的那批物件之中的某一個。換成圖上的語言，我的推論是，一個 group 大致就是一條帶 [] 的路徑所涵蓋的一整批物件；這是我自己的讀法，文章另外還提到 group parameter、multi-typed group 與 associated group，這個說法未必涵蓋它們。作者也提醒，這個「一個物件一條路徑」並非絕對：透過 associated group 之類的機制，物件其實可以從多條路徑到達，他說那是另一個話題，改天再談。路徑的包含關係因此很關鍵：world.entities[] 落在 world.entities 之內。我的猜測是，這件事光看路徑的字面結構就能判斷，檢查器不必去追指標；文章把檢查器的實作留到後續文章，這裡沒有說明。

參照記住路徑，修改讓裡面的參照失效

作者把整套機制壓成五件事。先是兩件記帳：每個物件由單一所有權決定一條路徑，每個參照記住它所指物件的路徑。接著是兩條失效規則，物件被銷毀時，原文是「When we destroy an object, everything pointing at its path is no longer usable.」呼叫函式時，原文是「When we call a function, everything pointing inside its modified paths are no longer usable.」夾在中間的是函式簽名，它描述函式會修改的路徑，讓呼叫端知道該對哪些路徑套用後一條規則。真正擋下程式的，是這幾件合起來的作用。

兩條失效規則的措辭不一樣，這個差別值得停下來看。銷毀講的是「pointing at」，修改講的是「pointing inside」。作者在修改的情況下特別強調：「We don't invalidate references pointing to an object. We invalidate references pointing inside the object.」他舉的例子是 Vec：先拿一個指向整個 vec 的參照 vec_ref，再拿一個指向第 0 個元素的 elem_ref，然後對 vec 呼叫 push。文章說 push 會修改 vec，而這會讓「all references pointing inside vec」失效。結果是 vec_ref 還能繼續 push，elem_ref 一用就是編譯錯誤，訊息是「Used a borrow after invalidated」。

文章在這一段沒有展開為什麼線要劃在這裡。我的猜測是，這跟容器改動時元素的處境有關：Vec 增加元素時，裡面的元素可能被搬動，指向元素的參照因此不可信；Vec 這個物件本身還在原位，指著它的參照沒有理由作廢。作者在引用的段落裡沒有這樣寫。但它能解釋圖上為什麼 R1 在 push 之後仍然可用而 R2 不行。

下面是文章第一個用來示範失效的程式。它先在 world 裡放進一個 Entity，拿到指向第 0 個元素的 first_ref，接著把整個 world.entities 換成新的空 Vec，最後才讀 first_ref.hp。

struct Entity {
  hp int;
}
struct World {
  entities Vec<Entity>;
}
func main() int {
  let world = World(Vec<Entity>.new());

  world.entities.push(Entity(42));
  let first_ref = &world.entities[0];

  world.entities = Vec<Entity>.new();

  // 編譯錯誤，使用了已失效的借用
  return first_ref.hp;
}

這五行的時間順序，用下面的捲軸逐步走一遍最清楚。把圓點拖到第四步，看 first_ref 的狀態在哪一刻改變，又在哪一刻才被編譯器指出來。

拖曳圓點，逐行執行 main · 5 行 6 個狀態

1. let world = World(Vec<Entity>.new());
2. world.entities.push(Entity(42));
3. let first_ref = &world.entities[0];
4. world.entities = Vec<Entity>.new();
5. return first_ref.hp;

first_ref 尚不存在

還沒執行任何一行，world 與 first_ref 都還不存在。

失效發生在第四行，報錯卻在第五行。文章的說法是，編譯器看到 first_ref 被使用，所以顯示錯誤。照這個說法推論，一個已經失效的參照只要之後沒有人再用它，就不構成錯誤。這是我從作者敘述順序讀出來的結論，文章在這個例子旁沒有另外強調。它對寫程式的人有實際差別：違規的判準是「使用失效的參照」，而不是「讓參照失效」。

函式簽名：in 與 mut 各管一半

Valen 在參照的種類上刻意收斂。作者說「Valen, however, has only one kind of borrow reference.」可變或不可變，不寫在參照的型別上，原文是「In Valen, the mutability of something isn't part of its type, the surrounding function determines it.」換句話說，同一個參照在某個函式裡能不能寫，要看那個函式的簽名替它開了什麼權限。這跟習慣把 & 與 &mut 當成兩種型別的讀者直覺不同，也是接下來幾個例子能成立的前提。

權限怎麼寫在簽名上，文中的範例是 func step(world &World, entity in world.entities[] mut)。作者逐個詞拆解：in 的意思是「a reference to one of」，mut 在這裡的意思是「we can modify it」，合起來是「entity is a reference to one of world's entities's elements, and we can modify it.」所以這個簽名同時說了兩件事：entity 不是憑空來的參照，它指向 world.entities 的某個元素；而 step 被允許改它。

檢查器怎麼知道一次呼叫動了哪些路徑，文章的答案是簽名。以 push 為例，作者寫道 push 必須在簽名裡用 mut 關鍵字說明自己會修改，編譯器看到 mut(self)、知道 self 其實就是 vec，便知道 vec 被修改了。就我讀到的範圍，文章沒有提到檢查器要讀函式本體才能判斷；簽名是依據。呼叫端因此只需要簽名，這是我的推論；獨立編譯之類的好處，文章在這一段沒有明講。

回到圖上的 step 那一列。step 只改一個 entity 的內容，所以它動到的是 world.entities[] 這條路徑。另一個範例 step_and_read 先呼叫 step，再繼續讀 entity，旁邊的註解寫著「Only modifies an entity's contents」，文字說明則是 step 並未讓 entity 失效（原文是「doesn't invalidate the entity」）。在圖上的模型裡，這對應 R2 照常可用，只有裡面的 R3 失效。

放寬之後能過關的寫法，作者列了五種。多個區域變數指向同一物件，並且透過任何一個去寫。一個參數指向某個物件，另一個參數指向該物件裡面的某處，只透過後者去寫。多個函式參數指向同一物件，同樣能透過任何一個去寫。做一個「rollback」結構，在離開作用域時改動某個物件。以及多個結構都持有對同一個子系統的可變參照。作者說這些都是借用檢查器通常覺得棘手的寫法，在這裡只要不產生 use-after-free 就放行。作者還補了一句保留：這些好處帶著零執行期成本的主張，而他自己承認「Though it's debatable if any language can get memory safety with zero run-time cost.」

和 Rust 的差別：放寬的是哪一條規則

文章把整個提案的重點放在一個替換上：作者說 group borrowing 把 shared-xor-mutable 放寬成 no use-after-free。前者是「同一時間要嘛多個唯讀、要嘛一個可寫」，後者只問「你用的這個參照，指的東西還在不在」。前面這幾種寫法之所以能過，就是因為它們違反前者，卻沒有違反後者。文章同時指出，這種做法在編譯期抓 use-after-free，而且限制比先前的做法少，原文是「it does it in a way that has less restrictions than previous approaches」。

作者用同一個 step 例子做了橫向比較，對象是 C++、一般 Rust、加了 GhostCell 的 Rust 和 Valen。他的結論都是定性的，沒有給任何 benchmark 數字，下表把他的說法照原樣整理。C++ 那版他自己註明要靠寫的人小心維持記憶體安全，因為 C++ 不在編譯期檢查。Rust 版慢一點的原因，他在註腳裡說得具體：entity_mut.advance() 需要一個 &mut Entity，接著得把它丟掉，才能拿回外層的 &World 交給 get_collision_for_entity，之後 resolve 又要重新取一次 &mut Entity。範例程式碼裡的註解則標出每次取用都有 bounds check，可能 panic。他也提到另一條路，把程式重構得更「扁平」，但那有自己的取捨：樹狀結構攤平成多個陣列之後，節點不會隨父節點自動刪除，拆得太細還可能撞上「ID chasing」的 cache miss。一般 Rust 是「memory-safe, but a little slower, and a little more complex」。加上 GhostCell 之後「the same speed as C++, but it's still a bit complex」。Valen 則是「fast, safe, and simple」。

同一個 step 範例，作者對四種寫法的描述。這是他的定性說法，文章沒有附 benchmark。

寫法	記憶體安全	速度	複雜度
C++	編譯期不檢查，要靠寫的人維持	比 Rust 版快（作者拿它當對照）	比 Rust 版簡單（作者拿它當對照）
Rust	memory-safe	a little slower	a little more complex
Rust + GhostCell	文中未另述	same speed as C++	still a bit complex
Valen	safe	fast	simple

讀這張表要留意作者在註腳 29 自己加的保留：「There's some nuance here. You can generally rearrange your Rust code to match group borrowing's speed」，也就是一般 Rust 通常也能靠重排程式碼追上 group borrowing 的速度，GhostCell 並非必要。所以這張表比較的是「同一個例子，寫起來要付多少工」，沒有比較誰的最佳寫法更快。Valen 那一列的「simple」指的是這個例子裡程式碼比 Rust 版單純，不是整個語言比較簡單。

提案的來歷文章也交代了。作者說 Valen 的做法建立在他朋友 Nick Smith 設計的 Group Borrowing 提案之上，這個提案「originally designed with Mojo in mind」，但作者盡了力還是沒能說服 higher-ups 採用，他寫的是「Group borrowing was dead before it had the chance to succeed.」之後的發展，作者列了幾條線：Google 的 Carbon 語言「pivoted completely to group borrowing」，Plecra 的 exclusion typing 則是「redesigning the Rust borrow checker with concepts from group borrowing and GhostCell」。這些是作者的轉述，我沒有逐一查證其他專案的說法。

三個延伸：局部可變、暫時唯一、萬用後代路徑

先看 mutable-in-immutable。回頭看 step 的簽名：world 是一般的參照，只有 entity 帶著 mut。作者說加這個功能的目的，是「so that we don't have to do the classic borrow-checking pattern of taking in the entire world mutably」。圖上最後一列就是那個傳統做法的結果：整個 world 被視為被修改，R1、R2、R3 全部失效。局部的 mut 讓 step 只動到 world.entities[] 這條路徑；作者說這樣的好處是「this won't invalidate callers' references to entities」，也就是呼叫端指向那些 entity 的參照不會失效。這一段的規則套用是我在圖上做的推演，文章給的是目的和 step 的範例。

作者順帶提到，這種更細的資訊可能對最佳化器有用，但說法很保守。他寫「I suspect this feature could make Valen code optimize better.」接著補上但書：要做到這一點可能需要修補 LLVM，原因是 LLVM 想事情的方式是 noalias，而不是「read-only」（原文：「This might require patches to LLVM to make it better able to harness the information.」）。他在註腳另外寫道，這未必表示 Valen 會比 C++、Rust 等更快，他認為那些語言靠額外重構或 unsafe 也能得到同等的加速。這一整段是推測，沒有任何實測，使用時別把它讀成 Valen 保證更快。

temporary uniqueness 跟 Rust 互通有關。Valen 只有一種參照，Rust 卻分 & 與 &mut，所以呼叫 Rust 時要決定交出哪一種。作者的規則是：「We can hand a Valen reference into a Rust &mut if it's the only reference that can reach that data during that call.」反過來，若有多個 Valen 參照可能指向同一個物件，就「they can only be handed into Rust & references」。下面用兩個分頁並排這兩種情況。

切換兩種情況，看 Valen 參照能交給 Rust 的哪一種 · 2 個分頁

只有一個參照能到達 多個參照指向同一物件

作者接著推測還能往前走一步，他寫的是「I suspect」Valen 可以有類似「unique group」的東西，讓程式碼明講某個群組在呼叫期間是唯一的。這在文中是構想，沒有說已經做了。文章也沒有直接描述現況下，檢查器是怎麼判斷「能到達該資料的參照只有一個」的。

萬用後代路徑同樣是為 Rust 互通而加，處理的是 Rust 函式回傳參照的情況。作者說 Valen 想知道每一個參照的路徑，但 Rust 的 pub fn gem(&self) -> &Gem 沒有寫出來。他照實寫了難處：「But alas! Valen can't infer the in self.gem from the Rust code.」他的解法是讓 Valen 把這個 Rust 函式讀成 func gem(self &Chest) -> &Gem in self.gem... { &self.gem }，其中 in self.gem... 的意思，作者說是「points somewhere inside self.gem」。作者對「wildcard descendant path」這個名稱的評價是「it definitely needs a better name」。他還猜這個符號的用處不只 Rust 互通，但也提醒「we should be careful here too, because that same purpose can be served by other features in theory」。

還沒定案的部分

文章的附錄談 type-stability exception，而且一開頭就註明「This part isn't implemented in Valen yet. Stay tuned!」想法是：「group borrowing will never invalidate any type-stable data」，它只讓指在型別不穩定內容裡面的指標失效，作者舉的是 enum 的內容和指標的 pointee。範例裡的 Level 有 terrain 和兩個 HashMap，先拿一個指向 level.terrain 的參照，再呼叫 add_entity 往 HashMap 裡塞東西，程式碼旁的註解寫著「Doesn't invalidate terrain_ref!」。依前面的規則，add_entity 動到的是 level，裡面的參照理應全部失效；附錄的例外針對的看來就是這種過度保守。

其餘在文章裡有保留語氣的地方，我另外整理成下面的清單。它不是文章的目錄，而是把作者自己標示為「還沒做」「只是懷疑」「可能需要」「還待命名」「預告後續」「有爭議」的句子攤開，每一條都附上他的原話，方便你決定哪些可以先當成已確立的設計，哪些要等後續文章。

作者自己標明還沒定案的六件事，附他的用詞

• 類型穩定例外not implemented

  This part isn't implemented in Valen yet. Stay tuned!

• 對最佳化器的好處suspect

  I suspect this feature could make Valen code optimize better. / This won't necessarily mean Valen will be faster than C++, Rust, etc.

• unique group 標註suspect

  I suspect Valen can have something like a unique group（原文把 unique group 放在引號內）

• 萬用後代路徑的名稱needs a better name

  This is called a wildcard descendant path, and it definitely needs a better name.

• 以陣列描述參照計數物件next posts

  In the next few articles, I'll explain more about how we'll blend in reference counting and generational references, and how Valen's group borrow checker is implemented.

• 「零執行期成本」的說法debatable

  Though it's debatable if any language can get memory safety with zero run-time cost.

參照計數那一條連結到文章最後的伏筆。作者的靈感來自一個觀察，他寫的是「group borrowing understands arrays」。他的設想是，如果把參照計數的物件對借用檢查器描述成一堆陣列，也許就能在記憶體安全的前提下借用進去。要做到這件事，他說需要兩個新概念：一個是「multi-typed group」，跟 Vale 的 region 類似，不同於原本每個 group 都要有型別的 group borrowing；另一個是「run-time」group，指向它的參照不會失效。這兩個概念文章都只給了一句描述，沒有規則、沒有範例，所以現在能做的只有記下它們存在。

三個挑戰裡，這篇主要交代第一個的骨架，作者自己也說「This is just the tip of the iceberg」；後續幾篇要談參照計數與世代參照怎麼混進來，以及 Valen 的 group 借用檢查器怎麼實作。眼下能帶走的是一種讀法，這是我的推論，不是作者的主張：把借用規則當成路徑失效規則來讀。讀任何一條規則，都問同一組問題：這次操作動到哪條路徑，哪些參照記著的路徑在它裡面，失效之後有沒有人去用。圖上那張表就是這樣算出來的，你可以拿來檢查自己熟悉的借用規則放寬了多少。

要把它當成可採用的設計，還缺三樣東西，文章都沒有給。一是實作那一篇：簽名如何驅動失效標記，最後有沒有跑過編譯器。二是任何 benchmark：「零執行期成本」作者自己說有爭議，最佳化器的好處他只說「suspect」，可能要修補 LLVM。三是日常寫起來的手感：文章開頭說，auto-deref、直接對 struct 取索引與從 group 推導型別，作者預告會在 11 月推出（這是他的預告，可能變動），而目前的編譯器得手動 dereference，並且替每個參數寫上型別。在這之前，這套設計的安全性與效能都停在作者的描述。

What this enables：在作者的規則下，多個可寫的參照可以指向同一個物件，函式也能只拿到集合裡某一個元素的可變權限，編譯器靠路徑與簽名擋下的只剩 use-after-free。