倒着走的借用检查器：Valen 如何反向扫描函数
来源：verdagon.dev — 2026-10-18
📋 概述
Evan Ovadia 在给实验语言 Valen 重写借用检查器时，发现一个自己都觉得诡异却有效的做法：安全检查阶段从函数最后一行往回走。Valen 把函数分四阶段编译——解析成 AST、静态定型、静态分组（每个引用都记下自己指向哪个变量的哪一部分）、安全检查。前三阶段都是正序的，第四阶段倒序：从尾部扫到开头，遇到「使用」就把变量塞进 pending 列表，遇到「声明」就把它从 pending 移除，遇到「修改」就检查 pending 里有没有东西指被改动的区域，有就是 use-after-free。这套规则在循环上需要额外处理：修改要记进当前循环的 mutations_after_this，声明若未被这些修改作废就记进 revived_after_this，走到循环开头时再核对每个 pending 是否都有复活来源。作者给出三条倒序的理由：找「最后一次使用」更自然（正序得回填跳转）、循环里无需前瞻或反复迭代到不动点、每个节点正反各扫一遍就够。目前这套检查器只有 3600 行，break/continue、闭包、关联组都还没做。
🔑 核心要点
- Valen 的编译四阶段：解析、静态定型、静态分组、安全检查——只有第四阶段（安全）是倒着走的，作者称没听说有别的借用检查器这么做
- 倒序算法只有三条规则：USE 入 pending、DECLARE 出 pending、MUTATE 时若 pending 里有变量指向被改区域就报错
- pending 的语义很好记：装着「下面还会被用到、因此到那一刻必须仍然有效」的所有变量
- 循环靠两张表补丁：MUTATE 记入 mutations_after_this，未被作废的 DECLARE 记入 revived_after_this，走到循环开头时核对每个 pending 是否都有复活来源
- 倒序的三条理由：找最后一次使用无需回填跳转、循环不必前瞻或反复迭代到不动点、每节点正反各扫一次就够
- 还差的一块是对齐 Rust：若把第三阶段换成完整求解器，就能像 rustc 那样从函数任意位置的事实推断引用生命周期，而第四阶段的倒序扫描不用改
💡 金句
这相当于逆着时间旅行，于是你已经知道未来。
👍 0
👎 0
← 返回 Lobsters 首页