一种把借用检查倒过来做的新思路

逆着时间旅行，于是你已预知未来

你有没有过这样的经历，冒出一个古怪的念头，然后它居然成了，可你自己都不太敢相信？

我现在对 Valen 的借用检查器就是这种感觉。

因为它会逆着时间走。

或者说得没那么夸张一点，它倒着遍历函数，这依然_非常_古怪。

几年前，你要是告诉我「把一个函数反过来迭代是件好事」，我会觉得你疯了。

结果发现，这么做其实有相当充分的理由，而且在做优化 pass 之类的场景里相当常见。¹ 但我不认为有谁把这一招用在内存安全检查上。

如果你想深入看看借用检查的世界，那就往下读吧！

我们即将见到一些古怪的东西。²

这是一篇相当深入底层的借用检查算法剖析。如果你想要的是史诗感和娱乐性，去看看我最近那篇 The Golden Spike, and Resurrecting the Vale(n) Programming Language 吧！

一种古怪的借用检查器

这可不是你熟悉的那种 shared-xor-mutable 借用检查。

这是 Valen 的借用检查器，它让 shared-xor-mutable 变成可选项，还能调用 Rust 函数，并在边界两侧保持内存安全。

Valen 仍处于高度实验阶段。很多东西还有漏洞和锋利的边角，而且在 v0.1 于二月某个时候发布之前，大概都会如此。那场声势浩大的、持续数月的重构已经开始了（这个新的借用检查器就是它的产物！）。欢迎去看看 Valen 仓库，当心，此处有龙！³

它有点像 Rust 的借用检查器，但它同时支持内存安全的可变别名。想了解更多的话，可以看这篇文章，不过本文的大部分内容并不需要你理解那一点。

……以及一个古怪的、倒着来的实现！

Valen 分四个阶段编译一个函数：⁴

1. 解析函数，把源文本变成 AST。
2. 做静态类型检查，确定每个变量、参数和表达式的类型。
3. 做静态分组，让每个引用都知道自己指向哪个变量（或者某个变量的哪_一部分_）。⁵
4. 对函数做安全检查，确保引用在失效之后没有被使用。

下面我会详细解释这些内容。

最奇怪的一点是，第 4 步是反着走的。 它先看函数里的最后一条语句，然后一路往回走，直到函数开头。

说它奇怪，是因为据我所知，它是唯一一个安全检查方向朝后的借用检查器。⁶

后面我会解释为什么要反着走（提示：为了方便、为了循环、也为了速度）。

不过先来看看它是怎么工作的，以及“反着走”到底意味着什么。

先跳过第 1 阶段，从第 2 阶段讲起。

第 2 阶段：静态类型标注

静态类型标注这一遍，有些人应该不陌生，它给变量赋予类型。

比如，它把下面这个程序：

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

变成：

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

这很常规，很多编译器都会这么做。

编译器通常把它做成一次正向遍历，从函数顶部走到函数底部，边走边推断类型。

第 3 阶段要做的事类似，但更奇怪；第 3 阶段做的是静态分组。

第 3 阶段：静态分组

这也是一次正向遍历，负责确定每个引用指向哪里。⁷

比如，在下面这个程序里：

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

静态分组会推断出 first_ref 指向 s.fuel_cells[] 中的某个位置：⁸

func print_first_fuel_cell(s &Ship) {
  // Static typing says:   first_ref &int
  // Static grouping says: 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。

第 4 阶段：安全检查

这篇文章一半是写着玩，另一半是想征求对这个算法的反馈。 我不认为之前有人这么做过，而且这背后可能确实有原因。如果你发现这个做法有什么问题，请在评论区留言帮我一把，这样我就能修正（或者干脆废弃！）这个方案。⁹

现在可以用上第 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);
}

这个程序犯了 use after free，我们希望编译器报错。

先把它脱糖成更显式的语法：

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 一个变量时，把它加入 pending 列表。
• 当我们 MUTATE 任何东西时，确保 pending 中没有变量被失效。
• 当我们 DECLARE 一个变量时，把它从 pending 列表中移除。

pending 里装的是所有在下方被 USE、而我们希望在上方看到 DECLARE 的东西。

我们希望永远不会看到对 pending 中任何东西的 MUTATE。

理解这件事最好的方式，大概是 pending 包含所有将会被使用的变量，在函数中更靠下的位置、更晚的时候，因此它们在那之前必须保持有效。

要真正理解它，还是看它跑一遍。

首先，我们看最后一行：

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

这是一次 USE，所以把它加入 pending。现在 pending 里有：

• buff（group g.buffs[]）

继续往回走，遇到它上面那一行：

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

我们看到 MUTATE，于是确保 pending 中没有变量被失效。

具体来说，我们要确保 pending 里没有任何东西指向 e 之下的任何内容。

• buff（group g.buffs[]）……匹配上了！ 报编译错误。

刚才发生的是，buff 指向 g.buffs[]，而 g.buffs[] 以我们刚用 add_buff 修改过的那个 g 开头。也就是说，buff 在它被使用的那一行之上就已经失效了，这就是 use-after-free。

于是编译器在这里报错。好耶！

另一个例子

来看一个正确的程序，看看反向遍历遇到声明时会发生什么。

还是同一个程序，只是把 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（组 g.buffs[]）

接着往上走一行，到这一行：

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

这里 DECLARE 了 buff，于是把它从待处理列表中移除。

现在待处理列表空了。

（这意味着函数中下方/之后没有任何变量被使用。）

再往上走一行，到这一行：

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

我们看到 MUTATE，于是确保待处理列表中没有变量被失效。

待处理列表里没有变量，所以什么也没发生。

然后我们看到它 USE 了 e，于是把它加入待处理列表：

• e（组 g）

函数到此结束！

我们一路走到末尾，没有看到任何 MUTATE 作用于待处理变量，这意味着这个程序是内存安全的。

为什么要反向

原因有三条，方便、循环，以及速度。

一般来说，反向遍历便于判断某个东西最后一次被使用是在什么时候。

看这个函数：

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，¹⁰ 我们有两种选择：

• 做一次正向扫描。遇到 a 的声明，做 X。然后继续往下走，边走边记录 a 的使用。走到函数末尾时，再跳回最后记录的位置，做 Y。
• 做一次反向扫描。先遇到 a 的最后一次使用，做 Y。然后继续往前找 a 的声明，找到时做 X。

注意正向扫描多出了那一步跳转，因为遇到最后一次使用时我们当场认不出来。

反向扫描更简单。

想看反向扫描在析构函数插入上的另一个例子，可以看我 2024 年的 LLVM 演讲。很多编译器开发者都会告诉你，反向扫描在很多场景下都很好用。

反向遍历对循环也更友好。

下面是我思考循环时常用的两个例子：¹¹

这个程序是正确的，但它说明了判断 observe(e) 是否有效有多棘手。

exported func main() {
  let arr = ArrayList<int>(3);
  let e = &arr[0];
  
  while ... {
    observe(e); // Valid `e` use.
    add_element(&arr);
    set e = &arr[0];
  }
}

那个 e 实际上可能来自两个地方：

• 循环之前的 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); // Invalid `e` use.
    add_element(&arr);

  }
}

没有 set e 时，循环里的 e 是被循环的_上一轮迭代_失效的。

如果做正向扫描，就得向后看，确认没有 set e 让 e 重新生效。

这个问题很棘手。可以：

• 向后扫描寻找那些 set（然后再跳回来）。
• 反复做正向遍历，每轮获得更多信息，直到结果稳定（即“数据流不动点”）。
• 先做一次正向遍历收集信息，把检查推迟到之后再做。

上一个方案确实诱人。可惜它的数据结构最终变得非常复杂，而且还存在我们在上面 func 攻击示例里看到的同一个“fetch/navigate”问题。

直接采用 V2 的反向遍历方案更简单。

我也相当确定 V2 的方案更快，因为每个节点只需在阶段 3 的前向遍历中处理一次，在阶段 4 的后向遍历中再处理一次。¹²

我没有做过基准测试，所以这话别太当真。¹³

不过，反向遍历方案当然不能白得循环处理能力。我们还需要做一些调整。

带循环的反向遍历

算法还需要再补充一点东西才能处理循环。¹⁴

具体来说，我们会用不同的方式处理 MUTATE 和 DECLARE，同时还会对 LOOP START 做出反应。

我们向上扫描，寻找这些事件：

• 当我们 USE 一个变量时，把它加入待处理列表。
• 当我们 MUTATE 任何东西时：
  • 确保待处理列表中没有变量被作废。
  • 把这次修改加入所属循环的 mutations_after_this 列表。
• 当我们 DECLARE 一个变量时：
  • 把它从待处理列表中移除。
  • 如果它没有被 mutations_after_this 中的任何内容作废，就把它加入所属循环的 revived_after_this 列表。
• 当我们遇到 LOOP START 时：
  • 对于待处理列表中的每一项，如果它被该循环 mutations_after_this 中的某个内容作废，就确保它同时也在该循环的 revived_after_this 中。¹⁵

看看这在这个例子上会怎样。这是一个正确的程序，所以不应该出现编译错误。

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[])

这是一条 DECLARE ¹⁶，所以我们做两件事：

• 把它从待处理列表中移除。它不在列表里，所以什么也不会发生。
• 如果它没有被所属 mutations_after_this 中的任何内容作废（确实没有，因为该列表是空的），就把它加入 revived_after_this。

revived_after_this 现在包含一个条目 e。

现在我们向上走一行，看到：

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

这是一条 MUTATE，所以我们做两件事：

• 确保待处理列表中没有变量被作废。待处理列表是空的，所以什么也不会发生。
• 把这次修改加入所属循环的 mutations_after_this 列表。

mutations_after_this 现在有一条记录 arr。

向上走一行，看到：

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

这是一次 USE，所以把它加入 pending 列表。

pending 现在有一条记录 e（组 arr[]）。

再向上走一行，看到循环开头：

  while ... {                    // LOOP START

于是做 LOOP START 检查，对 pending 中的每一项，如果它被循环的 mutations_after_this 中的某个东西失效，就确认它出现在循环的 revived_after_this 中。

这里 pending 中有 e（组 arr[]）。e 确实 被 mutations_after_this 中的某个东西失效了。所以检查它是否在循环的 revived_after_this 中（在）。检查通过，没问题。

最上面两个 DECLARE 的解释就跳过了，前面已经讲过。

然后我们走到了函数的开头！全程没有遇到错误，所以借用检查器可以得出结论，这个函数是内存安全的。

就是这样！这就是我们用这个新的反向借用检查器处理循环的方式。

更接近 Rust 的借用检查器？

还有一件大事，我最终想改。

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）、¹⁷ 关联组、闭包，¹⁸ 各种好玩的东西。

总有一天我们会做到的。那一天会很辉煌。

感谢阅读！

在接下来的几篇文章里，我希望能多讲讲我们将如何融入引用计数和分代引用。我还会写写其他探索这类新内存安全方法的语言（Ante、Carbon、Zeta、Fang、排除类型等等！）。

这还只是冰山一角，想跟进的话可以订阅我的 RSS feed、r/valen，或者加入 Valen discord。也欢迎在 Bluesky 和 Mastodon 上关注我！

Cheers，

• Evan Ovadia

Footnotes

1. 或者说是析构函数插入，以及现在，检查内存安全！ ↩

2. 这篇文章 0% 由 AI 撰写。更多想法在这里。我的立场是，如果你希望别人花时间读点什么，那就花时间亲手写出来。感谢阅读 =) ↩

3. 具体来说是绿龙。 ↩

4. 还有隐藏的第五个阶段，计算要向 LLVM 发送哪些属性，用来描述哪些操作可能改动哪些 group。这超出了本文范围。 ↩

5. 它还会找出被任何指令的 mut 效果所波及、因而失效的所有 group。 ↩

6. 例如：

   • Rust（NLL 和当前的 Polonius）先对 region 推断做约束求解，再用一个前向遍历检查冲突。（注意 rustc 确实会反向扫描以确定每个变量在何处被使用，但真正的内存安全检查发生在前向遍历中。）
   • Vale 的类型检查阶段确定 region，之后一个前向遍历做 region borrow checking，判断何时可以安全跳过运行时的 generation checks。（Vale 的 region borrow checker 实际上与它的 instantiator/monomorphizer 合并在一起。）
   • Valen 之前的 borrow checker 做法与 Vale 相同，类型检查阶段确定 group，之后一个前向遍历在每次使用时检查该引用是否比它被“置为失效”的时刻声明得更晚。
   • 市面上还有很多别的 borrow checker，但我没听说有谁把安全检查放在反向遍历里做。如果有人知道，请告诉我！
   ↩

7. 我大概很快就会弃用“group”这个说法，改用“path”。欢迎提意见！ ↩

8. 在 V1 的静态分组阶段，它还会确定引用是在何时创建的。比如它不会只知道 s.fuel_cells[] 里有个 &int，而是知道那是第 7.2 行时 s.fuel_cells[] 里的 &int。这相当厉害，我们等于把时间和空间信息偷渡进了变量的类型里。新的 V2 不需要这么做，因为它做的是反向扫描，下面就会看到。 ↩

9. 第一个把它弄坏的人有奖！ ↩

10. 这份记账可能是递减引用计数，也可能是插入一次析构函数调用，或者检查 use-after-free，等等。 ↩

11. 注意，这些例子里我用的是 ArrayList 这个名字，但在真正的 Valen 编译器里它们叫 Array，原因说来话长。这很快会改。 ↩

12. 注意，这并不意味着算法已经是 O(n) 了。MUTATE 仍然需要检查 pending 列表里的所有内容。不过我觉得有办法大幅加快这项检查。但愿如此！ ↩

13. V1 从来没有完整的循环支持，所以实在没什么可做基准对比的。 ↩

14. 彩蛋提示！Sergeant Stubby 是第一次世界大战中第 102 步兵团的名角，随所在师远赴法国，与法军并肩作战。他服役 18 个月，在西线参加了 17 场战斗和四次攻势。他获得过许多嘉奖，包括一枚金质奖章、一道负伤条纹和两枚紫心勋章。Sergeant Stubby 被称为一战中受勋最多的战犬，也是唯一一只因战功被提名并晋升为军士的狗。（来源：Wikipedia）如果你看到了这条注释，请在评论里悄悄带上“gold”这个词！（恭喜 timpi4ever 和 gavinmorrow 最先发现了它！） ↩

15. 这里不从 pending 中移除任何东西，因为这些 pending 用法仍然需要由循环上方的代码来满足。 ↩

16. 是的，我现在后悔把它叫作 DECLARE 了，因为实际上这只是重新指向一个已有的变量。 ↩

17. 目前的计划是先做重构，让借用检查器面对的是控制流图而不是带类型的 AST。这样应该能让中断控制流容易得多。 ↩

18. 我对闭包挺期待的。我觉得自己找到了一种_非常_优雅的实现方式。敬请期待！ ↩