查询式编译器与增量类型检查：Salsa 架构

1. 增量编译的两个层次

一句话总结： 查询式编译器把整个编译过程表示成一张「问题 → 答案」的查询图，用记忆化与修订号让每次编辑只重算真正受影响的节点。

「增量」有两种做法。粗粒度的是文件级缓存：把每个源文件的编译产物存起来，编辑一个文件就重编它并重新链接。这适用于批处理构建，但对 IDE 场景太慢——用户敲一个字符就要重编整个文件。

细粒度的是查询式（query-based）增量：把编译拆成成千上万个小问题，例如「Foo::bar 的类型是什么」「这个函数体里 x 是否在作用域内」「模块 m 的导出集合有哪些」，每个问题的答案被缓存，并记录它依赖了哪些别的答案。用户编辑时，只有依赖了被改动文本的那些问题需要重算。

批处理:  编辑 1 个字符 → 重编整个文件（秒级）
查询式:  编辑 1 个字符 → 重算 ~10 个查询（毫秒级）

这也是 rust-analyzer 能在用户每次击键后重新做类型检查、补全与跳转的底层原因。

四种增量粒度的对比，能看清查询式处在什么位置：

从文件级降到查询级，靠的不是更快的重编，而是不再重编不需要的东西。

2. 查询式编译：把编译过程建模成求值

查询式编译器的基本抽象是一个带记忆化的纯函数：

#[salsa::query_group]
trait Db {
    // 输入查询：由外部（编辑器）直接设置
    #[salsa::input]
    fn file_text(&self, file: FileId) -> Arc<str>;

    // 派生查询：从输入算出来，自动缓存
    fn parse(&self, file: FileId) -> Arc<ParseTree>;
    fn def_map(&self, crate_id: CrateId) -> Arc<DefMap>;
    fn infer(&self, def: DefId) -> Arc<InferenceResult>;
}

关键约束是纯函数性：同一个查询、同一份输入，必须得到同一个答案。这条约束是记忆化成立的前提，也决定了查询函数的签名不能依赖隐藏状态——所有输入必须显式声明为参数或其它查询。

调用关系构成一张查询图（query graph）：

file_text(f1) ──► parse(f1) ──► def_map(c1) ──► infer(main)
                                        ▲
file_text(f2) ──► parse(f2) ────────────┘

当一个输入变化，依赖它的查询全部失效（invalidated），但失效是惰性（lazy） 的：只有下一次有人真的来问答案时才重算。这避免了「改动一处导致全图重算」的连锁爆炸。

2.1 查询图与记忆化的关系

查询式编译器与「普通记忆化」的差别在于依赖的显式记录。朴素的记忆化只缓存 (函数, 参数) → 结果，一旦输入变化，整个缓存作废。查询式额外记录「这个结果是怎么算出来的、依赖了谁」，于是能精确失效。

朴素记忆化:
  cache[parse(f1)] = tree1        # f1 变了 → 只能整个清空
查询式:
  cache[parse(f1)] = tree1
  deps[parse(f1)] = { file_text(f1) }   # f1 变了 → 只清 parse(f1) 及其下游

这套机制也叫按需增量（demand-driven incrementality）：不预先算，只在被问到时才算，算完记住「我问过谁」。它天然适合 IDE——IDE 的访问模式本身就是「用户光标在哪，就问哪里」。

3. Salsa 的键值模型与依赖追踪

Salsa 是 Rust 生态里最成熟的查询式框架，也是 rust-analyzer 的核心引擎。它的模型可以概括为四张表：

核心机制是修订号与验证（validation）：

1. 每次输入改变，全局修订号 +1；
2. 某个查询被再次请求时，Salsa 检查它的验证状态：若在上次计算之后没有任何依赖发生实质变化，直接返回缓存值；
3. 否则重新执行查询函数，并在执行过程中重新记录依赖。

时间线:
  rev 1: 计算 infer(main)，记录依赖 { def_map(c1), type_of(Foo) }
  rev 2: 用户改了 f2  → def_map(c1) 失效
  rev 3: 有人问 infer(main) → 验证发现 def_map(c1) 已变 → 重算
  rev 4: 用户改了注释（parse 结果不变）→ parse(f2) 重算但值相同
         → def_map(c1) 验证时发现依赖值未变 → 不失效 → infer(main) 保留

第 4 步是**「值相同即不算变化」（early cutoff）** 的关键优化：即使 parse(f2) 被重算了，只要它返回的语法树与之前相等，下游就不必失效。这要求查询的返回值实现高效的相等比较（通常是 Arc + 结构相等，或直接比较哈希）。

// Salsa 早期版本里，返回 Arc<T> 时用 ptr_eq 做快速相等判断
#[salsa::query_group]
trait Db {
    #[salsa::invoke(parse_impl)]
    fn parse(&self, f: FileId) -> Arc<ParseTree>;   // 值相等 → 下游不失效
}

3.1 修订号与验证的具体算法

把验证过程展开，可以看清每次查询的成本：

def request(query, key):
    entry = cache.get((query, key))
    if entry is None:
        return compute_and_record(query, key)

    # 若在上次验证后没有任何依赖变化，直接命中
    if entry.verified_at == current_revision:
        return entry.value

    # 否则逐个检查依赖是否「实质变化」
    for dep in entry.dependencies:
        if request(dep.query, dep.key) != dep.recorded_value:
            return compute_and_record(query, key)   # 依赖变了，重算

    entry.verified_at = current_revision              # 依赖都没变，标记为已验证
    return entry.value

注意最后一步：验证通过后要把 verified_at 更新到当前修订号，这样同一修订号内再次请求能直接命中，避免重复验证。这个「每修订号最多验证一次」的优化，是查询图规模很大时仍能保持响应速度的关键。

3.2 输入查询与派生查询的边界

Salsa 严格区分两类查询：

• 输入查询（input query）：值由外部直接设置，例如 file_text。它没有依赖，是图的叶子；
• 派生查询（derived query）：值由函数计算，依赖其它查询。它是图的内部节点。

// 输入：编辑器改文件内容时调用
db.set_file_text(file, new_text);   // 修订号 +1

// 派生：任何地方都能调，自动缓存
let tree = db.parse(file);

边界不能混：若把一个本该是输入的查询写成派生（例如让它去读磁盘），Salsa 就无法在文件变化时失效它。这解释了一个常见设计——文件内容必须先经 vfs 变成 file_text 输入查询，而不是让 parse 直接读磁盘。

4. 增量类型检查的挑战

把增量做进类型检查器，比做进解析器难得多，原因有三。

4.1 查询粒度与依赖爆炸

粒度太粗（「检查整个 crate」）则增量无意义；粒度太细（「检查一个表达式」）则依赖边数量爆炸，单次验证的开销超过重算。rust-analyzer 的折中是函数级：infer(body) 以函数体为键，函数之间通过 type_of(def) 相互依赖。

infer(body_a) → type_of(foo) → infer(body_foo) → ...

函数级粒度意味着改一个函数体只重算该函数；但如果改的是函数签名，所有调用者的 infer 都要重算——这正是签名修改在 IDE 里明显变慢的原因。

4.2 循环依赖与不动点

类型推断天然有循环：a 的类型依赖 b，b 又依赖 a。查询图必须容忍环，或用不动点迭代（fixpoint iteration） 打破环。Salsa 的做法是：查询执行中若发现自己被再次请求（检测到环），返回一个「暂定值」并记录该查询需要重跑，循环结束后再迭代到收敛。

// 伪代码：处理循环的定值
fn infer_cycle(&self, body: BodyId) -> InferenceResult {
    // 第一次进入：返回占位结果，并注册为 "cycle participant"
    // 迭代直到所有参与者的结果稳定
    self.iterate_to_fixpoint(body)
}

一个具体例子：两个函数互相递归，且其中一个调用了另一个的泛型实例。

fn a<T>(x: T) -> T { b(x) }     // a 的类型依赖 b
fn b<T>(x: T) -> T { a(x) }     // b 的类型依赖 a

推断 a 时进入 b，推断 b 时又回到 a——查询图出现环。处理方式是把参与环的查询标记为「本轮暂定」，用占位类型（如 {unknown}）先算一遍，然后重新求值直到不再变化。若迭代超过上限（例如 100 轮）仍不收敛，就报「类型推断无法收敛」，而不是无限循环。

4.3 内存与缓存淘汰

IDE 会话可能持续数小时，缓存只增不减会耗尽内存。Salsa 与 rust-analyzer 用LRU 淘汰 + 按需重算：缓存值被逐出后，下次请求会重新执行查询——正确性不受影响，只是失去一次加速机会。

// 设置缓存容量上限
let db = RootDatabase::builder()
    .with_lru_capacity(1024)   // 每个查询保留最近 1024 个键
    .build();

4.4 查询式框架的横向对比

Salsa 不是唯一的查询式框架，但它的「修订号 + 惰性验证」模型影响了很多后来者：

共同点是「纯函数 + 显式依赖 + 惰性失效」三件套；差别在于对循环、并发与内存管理的处理策略。

5. 实战：rust-analyzer 的查询骨架

rust-analyzer 的 crates/hir-ty 与 crates/hir-def 就是一组 Salsa 查询。把它的分层看清，就理解了一个查询式编译器该长什么样：

vfs (文件系统抽象)
  └─ file_text(file)              ← 输入查询
      └─ parse(file)              ← 语法树
          └─ item_tree(file)      ← 模块内的条目
              └─ def_map(crate)   ← 全 crate 的名字解析
                  └─ type_of(def) ← 单个定义的类型
                      └─ infer(body) ← 函数体类型推断

每一层都只依赖下一层，形成无环（或可控有环） 的分层。跨层访问只能通过查询，不允许直接持有下层数据结构的可变引用——这条纪律保证了依赖追踪的完整性。

# 打开 rust-analyzer 的查询日志，观察增量行为
RA_LOG=hir_ty=info rust-analyzer analysis-stats .
# 观察每次编辑后重算了哪些查询
RA_LOG=salsa=info rust-analyzer

analysis-stats 会打印「本次分析执行了多少个查询、缓存命中率多少」，是验证增量效果的直接手段：

Database loaded: 1234 files, 5678 queries executed, 89% cache hit

5.1 与「批处理增量」的关系

查询式与批处理增量不是二选一。Cargo 的增量编译解决的是「上次构建到这次构建之间哪些 crate 需要重编」，Salsa 解决的是「一次分析内部哪些查询需要重算」。两者叠起来：外层按 crate 分块，内层按查询细化。

# Cargo 的 crate 级增量
CARGO_INCREMENTAL=1 cargo build
# 看哪些 crate 被重编
cargo build -v 2>&1 | grep Compiling

6. 工程实践与陷阱

• 纯函数纪律：查询函数里读全局变量、时间、随机数都会破坏记忆化的正确性。所有输入必须走参数或输入查询。
• 避免超大返回值：查询返回一个巨大的 Vec 会让相等比较与克隆变贵，尽量返回 Arc<T> 或分解成更小的查询。
• 依赖记录要完整：如果查询函数里偷偷访问了某个没被追踪的数据，Salsa 就不会在它变化时失效该查询，导致陈旧结果（stale result） ——这是最难查的一类 bug。
• 失效传播的代价：反向依赖表让「改一处、问多处」变快，但构建反向边本身有成本，超大依赖集会拖慢首次分析。
• 别过早优化：先把查询粒度做对、正确性做稳，再根据 analysis-stats 的命中率调粒度。

一句话：查询式编译器的本质是「用记忆化 + 依赖追踪换取细粒度增量」。它把编译器从「一次性批处理」改造成「可反复问问题、只算必要部分」的交互式服务，是语言服务器与 IDE 体验的技术底座。

延伸阅读

• 并行与增量编译
• 类型系统与类型推断
• 语言服务器与 IDE 工具链
• 编译器正确性与验证