关于 salsa

Salsa 是一个用于编写增量、按需程序的 Rust 框架。这类程序会随着输入变化而自适应，并持续产出最新结果。 Salsa 基于我们在 rustc 中实践过的增量重编译技术，它的很多使用者（但不是全部）都在构建编译器或类似工具。

如果你想进一步了解 Salsa，可以先看：

概述：快速了解核心概念。
教程：从头到尾走一个完整示例。
视频：也可以看一些讲解（内容略有过时）。

如果你希望交流或参与贡献，欢迎加入我们的 Zulip： salsa.zulipchat.com。

Salsa 概述

这一页会简要介绍一个 Salsa 程序由哪些部分组成。如果你想看更细致的讲解，可以继续阅读教程，它会从头到尾带你实现一个完整项目。

Salsa 的目标

Salsa 的目标是支持高效的增量重计算（incremental recomputation）。例如，rust-analyzer 就使用了 Salsa，帮助它在你输入代码时快速重新编译程序。

一个 Salsa 程序的基本形态大致如下：

#![allow(unused)]
fn main() {
let mut input = ...;
loop {
    let output = your_program(&input);
    modify(&mut input);
}
}

你先拥有一份输入值，调用程序得到结果。过一段时间后，输入发生变化，你再调用程序一次。 我们的目标，是通过复用第一次调用中的部分结果，让第二次调用更快。

当然，现实中的程序通常会有很多输入，而 your_program 也可能是定义在这些输入上的许多方法和函数的组合。不过这张图依然表达了几个关键点：

Salsa 把“增量计算”（也就是 your_program）与定义输入的外层循环分离开来。
Salsa 提供了定义 your_program 所需的工具。
Salsa 假设 your_program 是其输入的纯确定性函数，否则这一整套机制就没有意义。
输入的修改总是发生在 your_program 之外，也就是这个主循环的一部分。

数据库

每次运行程序时，Salsa 都会把每一步计算的值记录在数据库中。当输入发生变化时，它会查询这个数据库，看看哪些值可以复用。数据库还会用于实现 interning （也就是把某个值规范化为唯一副本，使其可以被廉价复制并快速比较相等）以及其他一些很方便的 Salsa 特性。

输入

每个 Salsa 程序都从输入（input）开始。输入是一些特殊结构体，用来定义程序的起点。程序中其余一切最终都必须是这些输入的某个确定性函数。

例如，在编译器中，可能会有一个输入表示磁盘上某个文件的内容：

#![allow(unused)]
fn main() {
#[salsa::input]
pub struct ProgramFile {
    pub path: PathBuf,
    pub contents: String,
}
}

你可以通过 new 方法来创建一个输入。由于输入字段的值会被存储进数据库，因此你还要把数据库的一个 & 引用传进去：

#![allow(unused)]
fn main() {
let file: ProgramFile = ProgramFile::new(
    &db,
    PathBuf::from("some_path.txt"),
    String::from("fn foo() { }"),
);
}

这里并不需要可变引用，因为创建一个新输入不会影响数据库中已有的 tracked 数据。

Salsa 结构体本质上只是整数

由 salsa::input 宏生成出来的 ProgramFile 结构体本身其实并不存数据。它只是一个 newtype 的整数 id：

#![allow(unused)]
fn main() {
// Generated by the `#[salsa::input]` macro:
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ProgramFile(salsa::Id);
}

这意味着一旦你拿到一个 ProgramFile，就可以很方便地复制、传递、随处存放。不过如果你想真正读取它的字段值，还是必须借助数据库和 getter 方法。

读取字段与 `returns(ref)`

你可以通过 getter 方法访问输入字段的值。由于这里只是读取字段，所以只需要数据库的 & 引用：

#![allow(unused)]
fn main() {
let contents: String = file.contents(&db);
}

调用这个访问器时，值会从数据库中被克隆出来。有时候这不是你想要的，于是你可以在字段上加 #[returns(ref)] 标注，告诉 Salsa 应当返回一个指向数据库内部的引用，而不是克隆值：

#![allow(unused)]
fn main() {
#[salsa::input]
pub struct ProgramFile {
    pub path: PathBuf,
    #[returns(ref)]
    pub contents: String,
}
}

现在 file.contents(&db) 返回的就是 &String。

你也可以通过 data 方法访问整个结构体：

#![allow(unused)]
fn main() {
file.data(&db)
}

写入输入字段

最后，你也可以通过 setter 方法修改输入字段的值。因为这会真正修改输入，并可能使依赖于它的派生数据失效，所以 setter 需要数据库的 &mut 引用：

#![allow(unused)]
fn main() {
file.set_contents(&mut db).to(String::from("fn foo() { /* add a comment */ }"));
}

注意，set_contents 返回的是一个 “builder”。这样你就可以进一步设置持久性等高级概念。

tracked 函数

定义好输入之后，下一步通常就是定义tracked 函数：

#![allow(unused)]
fn main() {
#[salsa::tracked]
fn parse_file(db: &dyn crate::Db, file: ProgramFile) -> Ast {
    let contents: &str = file.contents(db);
    ...
}
}

调用 tracked 函数时，Salsa 会跟踪它访问了哪些输入（在这个例子里，也就是 file.contents(db)）。它也会把返回值缓存下来（这里是 Ast）。如果你调用同一个 tracked 函数两次， Salsa 会检查它的输入是否发生变化；如果没有，就可以直接返回缓存值。 Salsa 用来判断 tracked 函数是否需要重新执行的算法，就叫作红绿算法，也正是 “Salsa” 这个名字的来源之一。

tracked 函数必须遵守一些结构约束：

第一个参数必须是数据库的 & 引用。
- 也正因为它只是 & 引用，所以在 tracked 函数内部不可能修改输入。
第二个参数必须是某种 “Salsa 结构体”。在这里它是一个 input struct，不过稍后我们还会看到别的类型。
可以有额外参数，但通常没有会更快，也更灵活。

tracked 函数可以返回任何可克隆的类型。因为当值被缓存后，结果需要从数据库里被克隆出来。如果你更希望返回指向数据库内部的引用，也可以给 tracked 函数加上 #[returns(ref)] 标注（例如，如果 parse_file 这样标注，那么调用者拿到的将是 &Ast）。

tracked 结构体

tracked 结构体是在计算过程中创建出来的中间结构体。和 input 一样，它们的字段也存储在数据库中，而结构体本身只是一个 id 的包装。不同之处在于：它们只能在 tracked 函数内部创建，而且一旦创建，它们的字段值就不能再变化（至少在当前修订里不会变）。 Salsa 只会为它们生成字段 getter，不会生成 setter。例如：

#![allow(unused)]
fn main() {
#[salsa::tracked]
struct Ast<'db> {
    #[returns(ref)]
    top_level_items: Vec<Item>,
}
}

和 input 一样，新值通过 Ast::new 创建。不过 tracked struct 的 new 只需要数据库的 & 引用：

#![allow(unused)]
fn main() {
#[salsa::tracked]
fn parse_file(db: &dyn crate::Db, file: ProgramFile) -> Ast {
    let contents: &str = file.contents(db);
    let parser = Parser::new(contents);
    let mut top_level_items = vec![];
    while let Some(item) = parser.parse_top_level_item() {
        top_level_items.push(item);
    }
    Ast::new(db, top_level_items) // <-- create an Ast!
}
}

`#[id]` 字段

当某个 tracked 函数因为输入变化而重新执行时，它在新执行过程中创建出的 tracked struct，会和旧执行中创建出的对应结构体进行匹配，并比较字段值。如果字段值没有变化，那么那些只读取这些字段的其他 tracked 函数就不需要重新执行。

默认情况下，tracked struct 是按创建顺序进行匹配的。例如，旧执行里 parse_file 创建的第一个 Ast，会与新执行里创建的第一个 Ast 进行匹配。在我们的例子中，parse_file 只会创建一个 Ast，所以这样完全没问题。但有时效果就没那么好。比如，假设我们还为文件中的条目定义了一个 tracked struct：

#![allow(unused)]
fn main() {
#[salsa::tracked]
struct Item {
    name: Word, // 稍后会定义 Word
    ...
}
}

假设解析器第一次先创建名为 foo 的 Item，接着又创建一个名为 bar 的 Item。后来用户修改输入，把两个函数的顺序调换了。尽管结构体数量没变，但现在它们的创建顺序正好反过来，于是朴素算法就会把旧的 foo 与新的 bar 匹配起来。对 Salsa 来说，这看起来就像 foo 被重命名成了 bar，而 bar 又被重命名成了 foo。结果当然仍然是正确的，但如果我们能理解它们只是“调换顺序”而不是“改名”，就可以少做很多不必要的重计算。

为了解决这个问题，你可以把某些字段标记为 #[id]。这些字段随后就会被用来在不同执行之间“匹配”结构体实例：

#![allow(unused)]
fn main() {
#[salsa::tracked]
struct Item {
    #[id]
    name: Word, // 稍后会定义 Word
    ...
}
}

为某些结构体专门指定 tracked 函数结果

有时你会希望定义一个 tracked 函数，但又想对某些特定结构体的结果进行特殊指定。例如，默认情况下你可能通过读取 AST 来计算某个函数的表示形式，但语言里又有一批内建函数，你想直接把它们的结果硬编码进去。

这也可以用来模拟一种场景： tracked struct 创建之后，再初始化其中某个字段。

为了支持这种用例，你可以使用 tracked 函数对应的 specify 方法。要启用它，需要在函数属性上加 specify 标志，提醒使用者：这个函数的值有时会由外部指定。

#![allow(unused)]
fn main() {
#[salsa::tracked(specify)] // <-- specify flag required
fn representation(db: &dyn crate::Db, item: Item) -> Representation {
    // 默认通过读取用户输入的 AST 来计算
    let ast = ast(db, item);
    // ...
}

fn create_builtin_item(db: &dyn crate::Db) -> Item {
    let i = Item::new(db, ...);
    let r = hardcoded_representation();
    representation::specify(db, i, r); // <-- use the method!
    i
}
}

只有那种除数据库参数外、只接收单个 tracked struct 作为参数的 tracked 函数，才支持 specify。

interned 结构体

最后一种 Salsa 结构体是 interned 结构体。它们非常适合做快速相等比较，常见用法是表示字符串或其他基础值。

例如，大多数编译器都会定义一种类型来表示用户标识符：

#![allow(unused)]
fn main() {
#[salsa::interned]
struct Word {
    #[returns(ref)]
    pub text: String,
}
}

和 input / tracked struct 一样， Word 本身只是一个 newtype 的整数，真正的数据仍然存放在数据库里。

你可以像创建 input 和 tracked struct 一样，通过 new 创建一个 interned 结构体：

#![allow(unused)]
fn main() {
let w1 = Word::new(db, "foo".to_string());
let w2 = Word::new(db, "bar".to_string());
let w3 = Word::new(db, "foo".to_string());
}

如果你用相同字段值创建两个 interned struct，那就一定会得到同一个整数 id。因此这里我们知道 assert_eq!(w1, w3) 为真，而 assert_ne!(w1, w2) 也同样成立。

你可以通过 getter 访问 interned struct 的字段，例如 word.text(db)。这些 getter 同样会遵守 #[returns(ref)] 的语义。和 tracked struct 一样，interned struct 的字段也是不可变的。

累加器

Salsa 最后一个值得介绍的概念是累加器（accumulator）。累加器是一种汇报错误，或其他“旁路信息”（side channel information）的方法，这类信息独立于函数的主返回值之外。

要创建一个累加器，你需要把某个类型声明成 accumulator：

#![allow(unused)]
fn main() {
#[salsa::accumulator]
pub struct Diagnostics(String);
}

它必须是某种值的 newtype，例如这里的 String。之后，在 tracked 函数执行期间，你就可以往里 push 这些值：

#![allow(unused)]
fn main() {
Diagnostics::push(db, "some_string".to_string())
}

稍后，在函数执行之外，你就可以查询某个特定 tracked 函数累积到的诊断集合。例如，假设我们有一个类型检查器，并且在类型检查期间它会汇报一些诊断信息：

#![allow(unused)]
fn main() {
#[salsa::tracked]
fn type_check(db: &dyn Db, item: Item) {
    // ...
    Diagnostics::push(db, "some error message".to_string())
    // ...
}
}

之后我们就可以调用关联的 accumulated 函数，把所有被 push 进去的 String 都取出来：

#![allow(unused)]
fn main() {
let v: Vec<String> = type_check::accumulated::<Diagnostics>(db);
}

教程：calc

本教程会通过一个端到端示例来介绍如何使用 Salsa。它不假设你事先了解 Salsa，不过先读一遍概述会更容易熟悉基本概念。

我们的目标是为一门名为 calc 的简单语言定义一个编译器/解释器。 calc 编译器接收如下程序，然后对其进行解析并执行：

fn area_rectangle(w, h) = w * h
fn area_circle(r) = 3.14 * r * r
print area_rectangle(3, 4)
print area_circle(1)
print 11 * 2

执行时，这个程序会输出 12、3.14 和 22。

如果程序里包含错误（例如引用了未定义的函数），它也会把这些错误打印出来。当然，它还是响应式的，所以对输入做小修改时，不需要重新编译（或者说，不一定需要重新执行）整个程序。

基本结构

在使用 Salsa 之前，让我们先来讨论一下 calc 编译器的基本结构。

Salsa 所设计的一部分内容是，你能够编写感觉“非常接近”正常 Rust 程序的程序。

示例程序

这是我们的示例 calc 程序：

x = 5
y = 10
z = x + y * 3
print z

解析器

calc 编译器接受由字符串表示的程序作为输入：

#![allow(unused)]
fn main() {
struct ProgramSource {
    text: String
}
}

它做的第一件事是将该字符串解析为一系列语句，这些语句看起来类似于下面的伪 Rust 代码¹：

#![allow(unused)]
fn main() {
enum Statement {
    /// Defines `fn <name>(<args>) = <body>`
    Function(Function),
    /// Defines `print <expr>`
    Print(Expression),
}

/// Defines `fn <name>(<args>) = <body>`
struct Function {
    name: FunctionId,
    args: Vec<VariableId>,
    body: Expression
}
}

其中，表达式类似于这样（伪 Rust 代码，因为 Expression 枚举是递归的）：

#![allow(unused)]
fn main() {
enum Expression {
    Op(Expression, Op, Expression),
    Number(f64),
    Variable(VariableId),
    Call(FunctionId, Vec<Expression>),
}

enum Op {
    Add,
    Subtract,
    Multiply,
    Divide,
}
}

最后，对于函数/变量名， FunctionId 和 VariableId 类型将是被驻留的 (interned) 字符串：

#![allow(unused)]
fn main() {
type FunctionId = /* interned string */;
type VariableId = /* interned string */;
}

因为 calc 非常简单，所以我们不必费心将词法分析器 (lexer) 和解析器 (parser) 分开。

检查器

“检查器” (checker) 的任务是确保用户只引用已定义的变量。

我们将以一种“无上下文”的风格编写检查器，这有点不直观，但允许更多的增量复用。

其思想是为给定的表达式计算它引用的变量。然后有一个函数 check，它确保这些变量是已经定义的变量的子集。

解释器

解释器 (interpreter) 将执行程序并打印结果。这里不需要太多的增量复用，尽管这当然是可能的。

定义数据库结构体

首先，我们需要创建数据库结构体。通常它只会被应用程序的“驱动代码”使用，也就是负责启动程序、提供输入并转发输出的那一部分。

在 calc 中，数据库结构体位于 db 模块里，形式如下：

#![allow(unused)]
fn main() {
#[salsa::db]
#[derive(Clone)]
#[cfg_attr(not(test), derive(Default))]
pub struct CalcDatabaseImpl {
    storage: salsa::Storage<Self>,

    // The logs are only used for testing and demonstrating reuse:
    #[cfg(test)]
    logs: Arc<Mutex<Option<Vec<String>>>>,
}

#[cfg(test)]
impl Default for CalcDatabaseImpl {
    fn default() -> Self {
        let logs = <Arc<Mutex<Option<Vec<String>>>>>::default();
        Self {
            storage: salsa::Storage::new(Some(Box::new({
                let logs = logs.clone();
                move |event| {
                    eprintln!("Event: {event:?}");
                    // Log interesting events, if logging is enabled
                    if let Some(logs) = &mut *logs.lock().unwrap() {
                        // only log interesting events
                        if let salsa::EventKind::WillExecute { .. } = event.kind {
                            logs.push(format!("Event: {event:?}"));
                        }
                    }
                }
            }))),
            logs,
        }
    }
}
}

#[salsa::db] 属性会把这个结构体标记为数据库。它必须包含一个名为 storage 的字段，其类型为 salsa::Storage<Self>，但你也可以根据需要添加其他字段。

实现 `salsa::Database` trait

除了结构体本身，我们还必须实现 salsa::Database：

#![allow(unused)]
fn main() {
#[salsa::db]
impl salsa::Database for CalcDatabaseImpl {}
}

定义 IR

在定义解析器之前，我们需要先定义 calc 程序要使用的中间表示（IR）。在基础结构一节中，我们已经写出过一些像 Statement、Expression 这样的“伪 Rust”结构；现在我们要把它们真正定义出来。

“Salsa 结构体”

除了普通 Rust 类型之外，我们还会使用各种 Salsa 结构体。所谓 Salsa 结构体，就是那些带有 Salsa 注解之一的结构体：

#[salsa::input]：表示计算的“基础输入”；
#[salsa::tracked]：表示计算过程中创建的中间值；
#[salsa::interned]：表示易于做相等比较的小值。

所有 Salsa 结构体的字段实际值都存放在 Salsa 数据库中。这使得我们能够追踪这些字段何时变化，从而判断哪些工作需要被重新执行。

当你给结构体加上这些 Salsa 属性之一时， Salsa 实际上会生成一大段代码，把这个结构体接入数据库。

输入结构体

我们首先要定义的是输入。每个 Salsa 程序都会有一些基础输入，它们驱动后续所有计算。程序剩余部分必须是这些基础输入的某个确定性函数，这样当输入变化时，我们才能尽可能高效地重新计算结果。

输入通过带 #[salsa::input] 注解的 Rust 结构体来定义：

#![allow(unused)]
fn main() {
#[salsa::input(debug)]
pub struct SourceProgram {
    #[returns(ref)]
    pub text: String,
}
}

在我们的编译器中，只有一个很简单的输入：SourceProgram，它包含一个 text 字段（字符串）。

数据存活在数据库里

虽然 Salsa 结构体的声明形式看起来和普通 Rust 结构体一样，但实现方式却完全不同。它们字段的值存放在 Salsa 数据库中，结构体本身只是对数据库中那份数据的一个引用式句柄。这意味着这些结构体实例都是可复制的，无论它们的字段里包含什么类型。创建结构体实例、读取字段、修改字段，都是通过 new、getter、setter 等方法完成的。

对 #[salsa::input] 来说，这个结构体内部持有的是一个 salsa::Id，也就是一个非零整数。因此，生成出来的 SourceProgram 大致长这样：

#![allow(unused)]
fn main() {
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SourceProgram(salsa::Id);
}

Salsa 还会生成一个 new 方法，让你能够在数据库中创建一个 SourceProgram。对 input 来说，需要传入数据库的 &db 引用以及每个字段的值：

#![allow(unused)]
fn main() {
let source = SourceProgram::new(&db, "print 11 + 11".to_string());
}

你可以用 source.text(&db) 读取字段值，也可以用 source.set_text(&mut db, "print 11 * 2".to_string()) 来修改它。

数据库修订

当一个函数接收数据库的 &mut 引用时，这意味着它只能从程序“增量化部分”的外部被调用，这一点在概述中已经解释过。每当你修改某个输入字段的值时，数据库中的 “revision counter” 就会递增，表示现在有一些输入与之前不同了。当我们说数据库的某个 “revision” 时，指的就是两次输入修改之间数据库所处的状态。

表示解析后的程序

接下来，我们要定义一个 tracked struct。 input 表示计算的起点，而 tracked struct 表示计算过程中产生的中间值。

在我们的例子里，解析器会接收前面提到的 SourceProgram，并返回一个 Program，表示已经完整解析后的程序：

#![allow(unused)]
fn main() {
#[salsa::tracked(debug)]
pub struct Program<'db> {
    #[tracked]
    #[returns(ref)]
    pub statements: Vec<Statement<'db>>,
}
}

和 input 一样，tracked struct 的字段也存储在数据库里。不同之处在于，这些字段是不可变的（不能再被 “set”），而且 Salsa 会在不同修订之间比较它们，判断何时发生了变化。例如，如果对输入的重新解析产生了与之前相同的 Program （比如用户只是加了点结尾空白），那么后续依赖它的计算就不需要重新执行。

除了字段不可变之外，使用 tracked struct 的 API 与 input 很相似：

你仍然通过 new 创建一个新值，例如 Program::new(&db, some_statements)；
你仍然通过 getter 读取字段值，例如 my_func.statements(db) 读取 statements 字段。
- 在这个例子里，字段带有 #[returns(ref)] 标注，所以 getter 返回的是 &Vec<Statement>，而不是克隆这个向量。

`'db` 生命周期

与 input 不同，tracked struct 会携带一个 'db 生命周期。这个生命周期与创建它时使用的 &db 绑定，并保证只要这个结构体还在被使用，数据库就保持不可变；换句话说，你不能在这期间去修改某个 salsa::Input 的值。

'db 生命周期还允许 tracked struct 在内部通过指针来实现（而不是像 salsa::input 结构体那样只保存数值 id）。对用户来说，这几乎是透明的；唯一能明显感觉到的好处，是 tracked struct 字段访问这种高频操作会被优化得更快。

表示函数

我们还会用一个 tracked struct 来表示每个函数。 Function 结构体会由解析器创建，对应用户定义出来的每个函数：

#![allow(unused)]
fn main() {
#[salsa::tracked(debug)]
pub struct Function<'db> {
    pub name: FunctionId<'db>,

    name_span: Span<'db>,

    #[tracked]
    #[returns(ref)]
    pub args: Vec<VariableId<'db>>,

    #[tracked]
    #[returns(ref)]
    pub body: Expression<'db>,
}
}

例如，如果我们创建了一个 Function 实例 f，后来发现 f.body 字段发生了变化，那就意味着用户修改了 f 的定义。于是我们只需要重新执行那些依赖 f.body 的代码，而不必重新执行依赖其他函数体的那部分逻辑。

除了字段不可变之外，使用 tracked struct 的方式依旧和 input 很像：

通过 new 创建新值，例如 Function::new(&db, some_name, some_args, some_body)；
通过 getter 读取字段值，例如 my_func.args(db) 读取 args 字段。

id 字段

为了在不同修订之间获得更好的复用，尤其是在实体顺序发生变化时，你可以把某些表示实体身份的字段标记为 #[id]。通常你会把它加在表示“名字”的字段上。这表示：如果在两个修订 R1 和 R2 中，创建出来的两个函数拥有相同的名字，那么它们就被视为同一个实体；于是我们可以比较它们其他字段的相等性，从而判断哪些内容需要重新执行。添加 #[id] 纯粹是一种优化，不会影响正确性。更多细节可以参考算法一页。

interned 结构体

最后一种 Salsa 结构体是 interned 结构体。和 input 以及 tracked struct 一样，它们的数据也保存在数据库中。但与前两者不同的是：如果你对同样的数据做两次 interning，你会拿到同一个整数。

interning 的经典用途，是表示函数名、变量名这类短字符串。如果一直传递需要 clone 的 String，既麻烦又低效；比较它们是否相等时还得做字符串比较，同样也不高效。因此，我们定义了两个 interned 结构体：FunctionId 和 VariableId，它们各自只有一个字段，用来存储字符串：

#![allow(unused)]
fn main() {
#[salsa::interned(debug)]
pub struct VariableId<'db> {
    #[returns(ref)]
    pub text: String,
}

#[salsa::interned(debug)]
pub struct FunctionId<'db> {
    #[returns(ref)]
    pub text: String,
}
}

例如，当你调用 FunctionId::new(&db, "my_string".to_string()) 时，你会得到一个 FunctionId，它本质上只是一个 newtype 的整数。但如果你再次用同样的参数调用 new，你拿到的会是同一个整数：

#![allow(unused)]
fn main() {
let f1 = FunctionId::new(&db, "my_string".to_string());
let f2 = FunctionId::new(&db, "my_string".to_string());
assert_eq!(f1, f2);
}

interned 值同样携带 `'db` 生命周期

像 tracked struct 一样，interned 值也会携带 'db 生命周期，这会阻止它们被跨修订使用。同时，它也允许这些值在底层通过指针来实现，从而让字段访问更高效。 interned 值在单个修订内部保证一致性。在不同修订之间，它们可能会被清空、重新分配甚至重新编号，但你通常观察不到这一点，因为 'db 生命周期保证了：只要某个 interned 值还在被活跃使用，你就不能去修改输入，也就不能触发新修订。

表达式与语句

对表达式和语句，我们不会使用任何特殊的 “Salsa 结构体”：

#![allow(unused)]
fn main() {
#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub struct Statement<'db> {
    pub span: Span<'db>,

    pub data: StatementData<'db>,
}

impl<'db> Statement<'db> {
    pub fn new(span: Span<'db>, data: StatementData<'db>) -> Self {
        Statement { span, data }
    }
}

#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub enum StatementData<'db> {
    /// Defines `fn <name>(<args>) = <body>`
    Function(Function<'db>),
    /// Defines `print <expr>`
    Print(Expression<'db>),
}

#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub struct Expression<'db> {
    pub span: Span<'db>,

    pub data: ExpressionData<'db>,
}

impl<'db> Expression<'db> {
    pub fn new(span: Span<'db>, data: ExpressionData<'db>) -> Self {
        Expression { span, data }
    }
}

#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub enum ExpressionData<'db> {
    Op(Box<Expression<'db>>, Op, Box<Expression<'db>>),
    Number(OrderedFloat<f64>),
    Variable(VariableId<'db>),
    Call(FunctionId<'db>, Vec<Expression<'db>>),
}

#[derive(Eq, PartialEq, Copy, Clone, Hash, Debug)]
pub enum Op {
    Add,
    Subtract,
    Multiply,
    Divide,
}
}

由于语句和表达式本身不被跟踪，这意味着我们的增量复用粒度只到函数级别：只要函数体里任意内容发生变化，我们就会认为整个函数体都脏了，并重新执行一切依赖它的内容。通常像这样画出一个“足够粗、但合理”的边界是有意义的。

不过这种设计也有一个缺点：我们把位置信息直接内联进了每个结构体中。

定义解析器：记忆化函数与输入

calc 编译器的下一步是定义解析器。解析器负责接收 ProgramSource 输入，读取 text 字段中的字符串，并创建在 ir 模块中定义好的 Statement、Function 和 Expression 结构。

为了尽量减少依赖，我们会编写一个递归下降解析器。另一种选择是使用某种 Rust 解析框架。本教程不会展开介绍解析算法本身，如果你感兴趣可以去读源码；这里我们只关注与 Salsa 有关的部分。

`parse_statements` 函数

解析器的入口是 parse_statements 函数：

#![allow(unused)]
fn main() {
#[salsa::tracked]
pub fn parse_statements(db: &dyn crate::Db, source: SourceProgram) -> Program<'_> {
    // Get the source text from the database
    let source_text = source.text(db);

    // Create the parser
    let mut parser = Parser {
        db,
        source_text,
        position: 0,
    };

    // Read in statements until we reach the end of the input
    let mut result = vec![];
    loop {
        // Skip over any whitespace
        parser.skip_whitespace();

        // If there are no more tokens, break
        if parser.peek().is_none() {
            break;
        }

        // Otherwise, there is more input, so parse a statement.
        if let Some(statement) = parser.parse_statement() {
            result.push(statement);
        } else {
            // If we failed, report an error at whatever position the parser
            // got stuck. We could recover here by skipping to the end of the line
            // or something like that. But we leave that as an exercise for the reader!
            parser.report_error();
            break;
        }
    }

    Program::new(db, result)
}
}

这个函数被标注为 #[salsa::tracked]。这意味着当它被调用时，Salsa 会跟踪它读取了哪些输入，以及它返回了什么值。返回值会被记忆化（memoized），所以如果之后再次调用这个函数且输入没有变化， Salsa 就会直接克隆结果，而不是重新执行函数体。

tracked 函数是复用的基本单位

tracked 函数是 Salsa 实现增量复用的核心。框架的目标是尽量避免重新执行 tracked 函数，而改为复用它们已经记忆化的结果。

Salsa 使用红绿算法来决定何时需要重新执行函数。简而言之，tracked 函数会在以下两种情况下被重新执行：

它直接读取了某个输入，而这个输入已经变化。
它直接调用了另一个 tracked 函数，而那个函数的返回值已经变化。

在 parse_statements 的例子里，它直接读取 ProgramSource::text，所以只要文本变化，解析器就会重新执行。

通过选择哪些函数要标记为 #[tracked]，你就能控制自己想获得多细粒度的复用。在这里，我们选择把最外层的解析函数标记为 tracked，而不是更内部的那些函数。这意味着输入变化时，我们总会重新解析整个输入，并重新创建得到的语句等结果。不过稍后我们会看到，这并不意味着类型检查器和编译器其他部分也总得重新跑一遍。

这是一个合理的取舍，因为：

解析本身非常便宜，额外引入更细粒度跟踪的开销通常不值得。
字符串本质上只是一个缺少结构的大字节块，很难精准判断 IR 的哪一部分需要重解析。

有些系统确实会做更细粒度的重解析，通常方式是先对字符串做一遍“预扫描”，给它一点结构信息，例如先识别函数边界，再把每个函数体的真正解析延后。在 Salsa 里实现这种方案也不难，而且会用到和后面避免重复执行类型检查器时相同的原理。

tracked 函数的参数

tracked 函数的第一个参数始终是数据库，也就是 db: &dyn crate::Db。

tracked 函数的第二个参数始终是某种 Salsa 结构体。

tracked 函数也可以接收额外参数，虽然这里的例子没有这样做。带额外参数的函数通常效率更低、灵活性也更差。如果可以，最好尽量把 tracked 函数组织成“单个 Salsa 结构体 -> 结果”的形式。

`returns(ref)` 注解

你可能已经注意到，parse_statements 被标注成了 #[salsa::tracked(returns(ref))]。通常情况下，调用 tracked 函数时，返回值会从数据库里克隆出来。 returns(ref) 表示改为返回一个指向数据库内部的引用。因此，调用 parse_statements 时，你拿到的是 &Vec<Statement>，而不是一个被克隆出来的 Vec。这是一种性能优化。（你可能还记得教程 ir 一节里提到过 returns(ref)，它放在结构体字段上时含义也基本相同。）

定义解析器：报告错误

解析器里最后一个有意思的问题，是如何处理解析错误。因为 Salsa 函数是会缓存的，而且可能根本不会执行，所以它们不应该产生副作用，因此我们不能直接调用 eprintln!。如果这么做，错误只会在函数第一次执行时被打印，而在后续直接返回缓存值的调用里就不会再出现。

Salsa 为此提供了一种机制，叫做累加器（accumulator）。在我们的例子里，我们在 ir 模块中定义了一个名为 Diagnostics 的累加器结构体：

#![allow(unused)]
fn main() {
#[salsa::accumulator]
#[derive(Debug)]
#[allow(dead_code)] // Debug impl uses them
pub struct Diagnostic {
    pub start: usize,
    pub end: usize,
    pub message: String,
}
}

累加器结构体总是一个只有单个字段的 newtype，这里字段类型是 Diagnostic。记忆化函数可以把 Diagnostic 值 push 到这个累加器里。之后，你可以通过一个方法找出这些记忆化函数及其调用的函数所 push 的所有值。例如，我们就可以拿到 parse_statements 产生的那组 Diagnostic 值。

Parser::report_error 方法里就有一个 push 诊断信息的例子：

#![allow(unused)]
fn main() {
    /// Report an error diagnostic at the current position.
    fn report_error(&self) {
        let next_position = match self.peek() {
            Some(ch) => self.position + ch.len_utf8(),
            None => self.position,
        };
        Diagnostic {
            start: self.position,
            end: next_position,
            message: "unexpected character".to_string(),
        }
        .accumulate(self.db);
    }
}

要获取 parse_statements 或其他记忆化函数产生的诊断集合，

#![allow(unused)]
fn main() {
let accumulated: Vec<Diagnostic> =
    parse_statements::accumulated::<Diagnostics>(db);
                      //            -----------
                      //     用 turbofish 指定
                      //     诊断类型。
}

accumulated 以数据库 db 为参数，并返回一个 Vec。

定义解析器：Debug 实现与测试

作为解析器部分的最后一步，我们需要编写一些测试。为此，我们会创建一个数据库，设置输入源文本，运行解析器并检查结果。不过在这之前，还有一个问题必须先解决：我们要如何查看像 Expression 这种 interned 类型所代表的值？

`DebugWithDb` trait

像 Expression 这种 interned 类型本质上只存了一个整数，所以传统的 Debug trait 并不怎么有用。要正确打印一个 Expression，你需要访问 Salsa 数据库，才能知道这个整数实际对应的值是什么。

为了解决这个问题，salsa 提供了 DebugWithDb trait。它的行为类似普通的 Debug，但额外接收一个数据库参数。对实现了这个 trait 的类型，你可以调用 debug 方法。它会返回一个临时值，这个临时值实现了普通的 Debug trait，于是你就可以写出下面这样的代码：

#![allow(unused)]
fn main() {
eprintln!("Expression = {:?}", expr.debug(db));
}

并得到你真正想看到的输出。

DebugWithDb 会自动为所有 #[input]、#[interned] 和 #[tracked] 结构体派生。

转发到普通 `Debug` trait

为了保持一致性，即使对于像 Op 这种普通枚举，有时也希望它实现 DebugWithDb。你可以像下面这样做：

#![allow(unused)]

fn main() {
}

编写单元测试

现在 DebugWithDb 的实现已经准备好了，我们就可以写一个简单的单元测试辅助函数。下面的 parse_string 会创建一个数据库、设置源文本，然后调用解析器：

#![allow(unused)]
fn main() {
/// Create a new database with the given source text and parse the result.
/// Returns the statements and the diagnostics generated.
#[cfg(test)]
fn parse_string(source_text: &str) -> String {
    use salsa::Database;

    use crate::db::CalcDatabaseImpl;

    CalcDatabaseImpl::default().attach(|db| {
        // Create the source program
        let source_program = SourceProgram::new(db, source_text.to_string());

        // Invoke the parser
        let statements = parse_statements(db, source_program);

        // Read out any diagnostics
        let accumulated = parse_statements::accumulated::<Diagnostic>(db, source_program);

        // Format the result as a string and return it
        format!("{:#?}", (statements, accumulated))
    })
}
}

再配合 expect-test crate，我们就能写出这样的单元测试：

#![allow(unused)]
fn main() {
#[test]
fn parse_print() {
    let actual = parse_string("print 1 + 2");
    let expected = expect_test::expect![[r#"
        (
            Program {
                [salsa id]: Id(800),
                statements: [
                    Statement {
                        span: Span {
                            [salsa id]: Id(404),
                            start: 0,
                            end: 11,
                        },
                        data: Print(
                            Expression {
                                span: Span {
                                    [salsa id]: Id(403),
                                    start: 6,
                                    end: 11,
                                },
                                data: Op(
                                    Expression {
                                        span: Span {
                                            [salsa id]: Id(400),
                                            start: 6,
                                            end: 7,
                                        },
                                        data: Number(
                                            1.0,
                                        ),
                                    },
                                    Add,
                                    Expression {
                                        span: Span {
                                            [salsa id]: Id(402),
                                            start: 10,
                                            end: 11,
                                        },
                                        data: Number(
                                            2.0,
                                        ),
                                    },
                                ),
                            },
                        ),
                    },
                ],
            },
            [],
        )"#]];
    expected.assert_eq(&actual);
}
}

定义 checker

定义 interpreter

参考

持久性（Durability）

“持久性”（durability）是一种可以显著提升 Salsa 程序性能的优化。它描述的是某个输入值发生变化的概率。

默认情况下，输入具有“低持久性”。但在设置输入值时，你也可以手动指定更高的持久性，通常是 Durability::HIGH。

Salsa 会跟踪那些只消费高持久性值的 tracked 函数。如果高持久性输入没有发生变化，它就可以跳过对这些函数依赖的遍历。

典型的“高持久性”值包括标准库中的数据，或者其他终端用户不会频繁编辑的输入。

“红-绿”算法

本页面介绍基本的 Salsa 增量算法。这种算法被称为“红-绿”算法，这是 Salsa 这个名字的由来¹。

译者注：墨西哥辣番茄酱 (salsa) 以鲜艳的红绿配色为特色。

数据库的修订版本

Salsa 数据库始终跟踪一个修订版本 (revision)。每次设置输入时，修订都是增量的。

所以 Salsa 从修订版本 R1 开始，但当调用 set 方法时，将变为 R2，然后是 R3，依此类推。对于每个输入，Salsa 还跟踪上次更改它的修订版本。

基本规则：输入发生变化时重新执行

当你调用跟踪函数时，除了存储已经被返回的值之外，Salsa 还跟踪它所依赖的其他跟踪函数，以及它们的值最后一次更改的修订版本。

当你再次调用该函数时，如果数据库处于新的修订版本中，Salsa 则检查该函数的任何输入是否在该新修订版本中发生了更改。

如果没有发生更改，Salsa 可以只返回其缓存的值。但如果输入已更改（或可能已更改），Salsa 将重新执行该函数以得到最新的结果。

下面是一个简单的例子，其中 parse_module 函数调用 module_text 函数：

#[salsa::tracked]
fn parse_module(db: &dyn Db, module: Module) -> Ast {
    let module_text: &String = module_text(db, module);
    Ast::parse_text(module_text)
}

#[salsa::tracked(returns(ref))]
fn module_text(db: &dyn Db, module: Module) -> String {
    panic!("text for module `{module:?}` not set")
}

如果调用了两次 parse_module，但是其间更改了模块的文本，那么 Salsa 将不得不重新执行 parse_module：

module_text::set(
    db,
    module,
    "fn foo() { }".to_string(),
);
parse_module(db, module); // executes

// ...some time later...

module_text::set(
    db,
    module,
    "fn foo() { /* add a comment */ }".to_string(),
);
parse_module(db, module); // executes again!

追溯：有时我们可以更聪明

不过，跟踪函数通常不直接依赖于输入。相反，它们将依赖于其他一些跟踪函数。例如，我们可能有一个读取 AST 的 type_check 函数：

#[salsa::tracked]
fn type_check(db: &dyn Db, module: Module) {
    let ast = parse_module(db, module);
    ...
}

如果模块中文本被更改，Salsa 必须重新执行 parse_module，但对源文本的许多更改仍然会生成相同的 AST。

例如，假设我们只添加了一条注释？在这种情况下，如果再次调用 type_check，我们将：

首先重新执行 parse_module，因为它的输入发生了变化。
然后比较得到的 AST：如果它与上次相同，我们可以追溯 (backdate) 结果；也就是说，即使输入改变了，输出也没有改变。

持久性：优化

作为一种优化，Salsa 包含了持久性 (durability) 的概念，这是指一些被跟踪的数据更改的频率。

例如，在编译 Rust 程序时，你可能会把来自 crates.io 的输入标记为高持久性输入，因为它们不太可能更改；把当前工作区可以标记为低持久性，因为对其的更改一直在发生。

当设置跟踪函数值时，你还可以给定持久性：

module_text::set_with_durability(
    db,
    module,
    "fn foo() { }".to_string(),
    salsa::Durability::HIGH
);

对于每个持久性，Salsa 跟踪与该持久性相关的某些输入所发生更改的修订。

如果一个跟踪函数只（传递地）依赖高持久性输入，而你更改了一个低持久性输入，那么 Salsa 可以非常容易地确定跟踪函数的结果仍然有效，从而避免了逐个遍历输入。

常见模式

这一节记录了使用 Salsa 的常见模式。

按需（惰性）输入

如果你可以很轻松地在一开始就提供全部输入，那么 Salsa 的 input 会用得最顺手。但有时候，输入集合并不是预先已知的。

一个典型例子就是从磁盘读取文件。你当然可以预先扫描某个目录，把整棵文件树作为 Salsa input struct 建出来；但更直接的做法通常是惰性地读取文件。也就是说，当某个查询第一次请求某个文件的文本时：

从磁盘读取文件并把它缓存起来。
为这个路径安装文件系统监听器。
当监听器收到文件变化通知时，更新缓存中的文件内容。

在 Salsa 里，这种方案是可行的：你可以把 input 缓存在数据库结构体中，再给数据库 trait 增加一个方法，从这个缓存里按需取出它们。

一个完整、可运行的文件监听示例可以在 lazy-input 示例中找到。

它的大致结构如下：

#[salsa::input]
struct File {
    path: PathBuf,
    #[returns(ref)]
    contents: String,
}

#[salsa::db]
trait Db: salsa::Database {
    fn input(&self, path: PathBuf) -> Result<File>;
}

#[salsa::db]
#[derive(Clone)]
struct LazyInputDatabase {
    storage: Storage<Self>,
    logs: Arc<Mutex<Vec<String>>>,
    files: DashMap<PathBuf, File>,
    file_watcher: Arc<Mutex<Debouncer<RecommendedWatcher>>>,
}

impl LazyInputDatabase {
    fn new(tx: Sender<DebounceEventResult>) -> Self {
        let logs: Arc<Mutex<Vec<String>>> = Default::default();
        Self {
            storage: Storage::new(Some(Box::new({
                let logs = logs.clone();
                move |event| {
                    // don't log boring events
                    if let salsa::EventKind::WillExecute { .. } = event.kind {
                        logs.lock().unwrap().push(format!("{event:?}"));
                    }
                }
            }))),
            logs,
            files: DashMap::new(),
            file_watcher: Arc::new(Mutex::new(
                new_debouncer(Duration::from_secs(1), tx).unwrap(),
            )),
        }
    }
}

#[salsa::db]
impl salsa::Database for LazyInputDatabase {}

#[salsa::db]
impl Db for LazyInputDatabase {
    fn input(&self, path: PathBuf) -> Result<File> {
        let path = path
            .canonicalize()
            .wrap_err_with(|| format!("Failed to read {}", path.display()))?;
        Ok(match self.files.entry(path.clone()) {
            // If the file already exists in our cache then just return it.
            Entry::Occupied(entry) => *entry.get(),
            // If we haven't read this file yet set up the watch, read the
            // contents, store it in the cache, and return it.
            Entry::Vacant(entry) => {
                // Set up the watch before reading the contents to try to avoid
                // race conditions.
                let watcher = &mut *self.file_watcher.lock().unwrap();
                watcher
                    .watcher()
                    .watch(&path, RecursiveMode::NonRecursive)
                    .unwrap();
                let contents = std::fs::read_to_string(&path)
                    .wrap_err_with(|| format!("Failed to read {}", path.display()))?;
                *entry.insert(File::new(self, path, contents))
            }
        })
    }
}

我们在 Db trait 上声明一个按需获取 File input 的方法（它只需要 &dyn Db，不需要 &mut dyn Db）。
每个文件应该只对应一个 input struct，所以我们会用一个缓存来实现这个方法（DashMap 可以理解为类似 RwLock<HashMap> 的结构）。

负责发起顶层查询的驱动代码，在收到文件变化通知时，就要负责更新文件内容。它更新 Salsa input 的方式，和更新其他 input 没有什么区别。

这里我们实现了一个简单的驱动循环：每当文件发生变化，就重新编译代码。你可以通过日志观察到，只有那些可能受到影响的查询才会被重新计算。

fn main() -> Result<()> {
    // Create the channel to receive file change events.
    let (tx, rx) = unbounded();
    let mut db = LazyInputDatabase::new(tx);

    let initial_file_path = std::env::args_os()
        .nth(1)
        .ok_or_else(|| eyre!("Usage: ./lazy-input <input-file>"))?;

    // Create the initial input using the input method so that changes to it
    // will be watched like the other files.
    let initial = db.input(initial_file_path.into())?;
    loop {
        // Compile the code starting at the provided input, this will read other
        // needed files using the on-demand mechanism.
        let sum = compile(&db, initial);
        let diagnostics = compile::accumulated::<Diagnostic>(&db, initial);
        if diagnostics.is_empty() {
            println!("Sum is: {sum}");
        } else {
            for diagnostic in diagnostics {
                println!("{}", diagnostic.0);
            }
        }

        for log in db.logs.lock().unwrap().drain(..) {
            eprintln!("{log}");
        }

        // Wait for file change events, the output can't change unless the
        // inputs change.
        for event in rx.recv()?.unwrap() {
            let path = event.path.canonicalize().wrap_err_with(|| {
                format!("Failed to canonicalize path {}", event.path.display())
            })?;
            let file = match db.files.get(&path) {
                Some(file) => *file,
                None => continue,
            };
            // `path` has changed, so read it and update the contents to match.
            // This creates a new revision and causes the incremental algorithm
            // to kick in, just like any other update to a salsa input.
            let contents = std::fs::read_to_string(path)
                .wrap_err_with(|| format!("Failed to read file {}", event.path.display()))?;
            file.set_contents(&mut db).to(contents);
        }
    }
}

调优 Salsa

缓存淘汰（LRU）

Salsa 支持为 tracked 函数启用 LRU（Least Recently Used，最近最少使用）缓存淘汰。默认情况下，memoized 值永远不会被淘汰，也就是无界缓存。你可以在编译期通过指定容量来启用 LRU：

#![allow(unused)]
fn main() {
#[salsa::tracked(lru = 128)]
fn parse(db: &dyn Db, input: SourceFile) -> Ast {
    // ...
}
}

当设置 lru = 128 时， Salsa 最多会为这个函数保留 128 个缓存结果。当缓存超过这个容量后，每次进入新修订时，就会把最久未使用的值淘汰掉。

关闭时零成本

如果没有指定 lru 容量（也就是默认情况）， Salsa 会使用一个空操作的淘汰策略，编译器会把它完全优化掉。这意味着那些不需要缓存淘汰的函数不会承担任何运行时开销。

运行时调整容量

对于启用了 LRU 的函数，你还可以在运行时调整容量：

#![allow(unused)]
fn main() {
#[salsa::tracked(lru = 128)]
fn my_query(db: &dyn Db, input: MyInput) -> Output {
    // ...
}

// 之后再调整容量：
my_query::set_lru_capacity(db, 256);
}

注意： set_lru_capacity 方法只会为带有 lru 属性的函数生成。没有启用 LRU 的函数并不会生成这个方法。

内存管理

旧查询的键和值目前都不会被垃圾回收，因此对于基于 Salsa 的长时间运行程序来说， LRU 缓存是目前避免内存无限增长的主要机制。

Intern 查询

Intern 查询可以让键查找更便宜、节省内存，并避免依赖 Arc。

对于那些涉及嵌套树状数据结构的查询， interning 尤其有帮助。

参见：

compiler 示例，其中就使用了 interning。

取消（Cancellation）

当并发写入发生，或者依赖关系变化导致某些查询结果已经不再需要时， Salsa 会取消这些查询。每一次访问中间查询，都是一个潜在的取消点。取消是通过 panic 实现的，而 Salsa 内部的设计目标之一就是保证 panic-safe。

如果你的某个查询里有一个很长的循环，并且这个循环期间没有执行任何中间查询，那么 Salsa 就无法自动取消它。这时你可能希望自行调用 db.unwind_if_cancelled() 来检查是否已被取消。

关于取消的更多细节，可以参考 Salsa 仓库里那些测试取消行为的测试用例。

处理循环

默认情况下，当 Salsa 在计算图中检测到循环时，Salsa 会 panic，并在消息中指出“循环头”（cycle head）；也就是那个在仍位于活动查询栈上时又被调用、从而形成循环的查询。

Salsa 也支持通过不动点迭代从查询循环中恢复，可以使用 cycle_fn 和 cycle_initial，或者通过 cycle_result 显式定义回退值。

不动点迭代

只有当可能参与循环的查询是单调的，并且作用于一个具有固定高度的偏序值域时，不动点迭代才可用。实际意思是：查询的输出必须总是“比输入更大”，同时还必须存在某种“最大值”或“顶值”。这样才能保证不动点迭代收敛到一个值。（一个典型例子是对类型进行操作的查询；类型可以形成一个带有“顶类型”的偏序。）

为了让某个查询支持不动点迭代，需要在 salsa::tracked 上提供 cycle_fn 和 cycle_initial 参数：

#![allow(unused)]
fn main() {
#[salsa::tracked(cycle_fn=cycle_fn, cycle_initial=cycle_initial)]
fn query(db: &dyn salsa::Database) -> u32 {
    // ...
}

fn cycle_fn(_db: &dyn KnobsDatabase, _id: salsa::Id, _last_provisional_value: &u32, value: u32, _count: u32) -> u32 {
    value
}

fn cycle_initial(_db: &dyn KnobsDatabase, _id: salsa::Id) -> u32 {
    0
}
}

cycle_fn 是可选的。默认实现总是返回计算得到的 value。

如果 query 成为了某个循环的循环头（也就是说，query 正在执行并且位于活动查询栈上，它调用了 query2，query2 又调用了 query3，而 query3 再次调用了 query；参与循环的查询数量可以更多），那么 cycle_initial 就会被调用，为固定点计算中的 query 生成一个“初始”值。（这个初始值通常应该是该偏序里的“底值”。）循环中的所有查询都会基于这个循环头的初始值计算一个暂定结果。也就是说，query3 会使用 query 的初始值计算一个暂定结果，query2 会使用 query3 的这个暂定结果继续计算。当 query2 把它的暂定结果返回给 query 时，query 会观察到自己收到了来自其所属循环的暂定结果，并调用 cycle_fn（参数包括上一次暂定值、新计算出的值，以及迄今为止发生的迭代次数）。cycle_fn 可以直接返回参数 value，表示继续用这个计算值迭代；也可以返回另一个值（一个回退值），改为用那个值继续迭代。

循环会一直迭代，直到收敛为止；也就是直到 cycle_fn 返回的值与前一次迭代的值相等。

如果某个循环迭代超过 200 次，Salsa 会 panic，而不是无限迭代下去。

所有可能成为循环头的查询都必须设置 `cycle_fn` 和 `cycle_initial`

考虑一个由两个查询构成的循环：query_a 调用 query_b，而 query_b 又调用 query_a。如果先调用 query_a，那么它会成为“循环头”；但如果先调用的是 query_b，那 query_b 就会成为循环头。要让一个循环使用不动点迭代而不是 panic，循环头必须设置 cycle_fn 和 cycle_initial。这意味着，为了在查询执行顺序变化时仍然可靠，query_a 和 query_b 都必须设置 cycle_fn 和 cycle_initial。

确保收敛

不动点迭代是一个很强大的工具，但也很容易被误用，从而导致无限迭代。为了避免这一点，请确保所有参与不动点迭代的查询都是确定性的并且满足单调性。

为了保证收敛，你可以利用 cycle_fn 收到的 last_provisional_value（第 3 个参数）。当 cycle_fn 收到一个新计算出来的值时，你可以实现一种策略，参考上一次暂定值来对结果做 “join” 或 “widen”，并返回一个回退值。这样可以保证计算的单调性，并抑制循环之间出现无限振荡。

此外，在不动点迭代中，如果能够识别某个值是由哪个循环头播种出来的，也会很有帮助。通过把一个 salsa::Id（第 2 个参数）嵌入初始值中，作为“循环标记”，恢复函数就能检测到源自自身的递归。

在 `cycle_fn` 或 `cycle_initial` 中调用 Salsa 查询

允许在 cycle_fn 和 cycle_initial 中调用其他 Salsa 查询。不过，如果这些函数重新进入了同一个循环，就可能导致不可预测的结果。因此，在循环恢复函数内部调用查询时要格外小心，并避免触发新的循环。

回退值

如果 Salsa 检测到循环，你可以使用 cycle_result 指定一个回退值。带有 cycle_result 的查询总会运行到结束，但如果遇到了循环，最终得到的值会被替换成这个回退值。

#![allow(unused)]
fn main() {
#[salsa::tracked(cycle_result=cycle_result)]
fn query(db: &dyn salsa::Database) -> u32 {
    // ...
}

fn cycle_result(_db: &dyn KnobsDatabase, _id: salsa::Id) -> u32 {
    42
}
}

与不动点迭代不同，带有 cycle_result 的查询在参与循环时也会使用它们的回退值。这是为了确保查询结果不依赖于查询的执行顺序（详情）。

Salsa 如何工作

视频介绍

关于 Salsa 工作原理的最完整介绍，请查看 youtube 上的 How Salsa Works 视频。

如果想更深入了解， Salsa In More Depth 深入了增量算法的细节。

如果你在中国，可以在 B 站上观看 "How Salsa Works" 和 "Salsa In More Depth"。

核心理念

Salsa 的关键思想是将你的程序定义为一组查询。每个查询都像函数 K -> V 一样使用，该函数从某个 K 类型的键映射到一个 V 类型的值。查询有两种基本类型：

输入：系统的基本输入。你可以随时更改它们。
函数：将你的输入转换为其他值的纯函数（没有副作用）。查询的结果被记录下来，以避免大量的重新计算。
当你对输入进行更改时，Salsa 将（相当智能地）计算出何时可以重新使用这些被记录的值，以及何时必须重新计算它们。

三步使用 Salsa

使用 Salsa 就像 1、2、3 一样简单：

定义一个或多个包含所需输入和查询的查询组 (query groups) 。从一个这样的组开始，但稍后你可以使用多个组将你的系统分解为组件（或将代码分散到多个 crates 中）。
在适当的地方定义查询函数 (query functions)。
定义数据库（database）结构体，它包含你将使用的所有输入/查询的存储，也可以包含代码需要的其他内容（例如配置数据）。

要查看这方面的实际示例，请查看 hello_world 示例，该示例有许多解释如何工作的注释。

深入管道

查看管道章节 (plumbing) ，了解对 Salsa 生成的代码以及它如何连接到 Salsa 库的更深入的解释。

视频

当前有一个关于 Salsa 最新版本的视频：

Salsa Architecture Walkthrough，它讲解了重新设计后的架构中的许多方面。

另外还有两个关于旧版 Salsa 的视频，但它们已经比较过时了：

How Salsa Works，它从高层介绍了其中涉及的关键概念，并展示了如何使用 Salsa；
Salsa In More Depth，它更深入地讲解了增量算法，并从高层解释了 Salsa 是如何实现的。

如果你在中国，可以在 B 站上观看 How Salsa Works、 Salsa In More Depth。

底层机制（Plumbing）

这一章介绍 Salsa 生成的代码及其“内部工作方式”。我们把这部分称为“底层机制”（plumbing）。

概览

管道部分分为以下章节：

数据库与运行时：介绍运行期使用的数据结构，包括如何协调 worker、触发取消、跟踪活跃函数及其累积依赖等。
查询操作：介绍函数配料上的主要操作。虽然这部分文字最初针对更早版本的 Salsa 编写，但核心逻辑相同。
- maybe changed after：判断某个 tracked 函数的 memoized 值是否已过期。
- fetch：计算最新值。
- 派生查询流程图：以流程图形式展示逻辑。
- 循环处理：说明出现循环时会发生什么。
术语：解释本章反复出现的术语。

数据库与运行时

Salsa 数据库结构体由用户通过 #[salsa::db] 属性来声明。它包含程序执行所需的全部数据：

#[salsa::db]
struct MyDatabase {
    storage: Storage<Self>,
    maybe_other_fields: u32,
}

这些数据分成两类：

由 Salsa 管理的存储，也就是 Storage<Self> 字段中的内容。这部分是必须存在的。
用户自己定义的其他字段（例如 maybe_other_fields）。它们可以是任意内容，用来让你的数据库接入某些特殊资源或其他上下文。

并行句柄

如果数据库会被多个并行线程共同使用，那么用户定义的数据库类型必须支持一种 “snapshot” 操作。这个 snapshot 应当创建出一个可供并行线程使用的数据库克隆。 Storage 本身就支持 snapshot。 snapshot 方法会返回 Snapshot<DB> 类型，从而阻止这些克隆通过 &mut 引用被访问。

`Storage` 结构体

Salsa 的 Storage 结构体包含了 Salsa 自己需要使用和维护的全部数据。其中有三个关键组成部分：

Shared 结构体，包含所有 snapshot 共享的数据，例如同步信息（如条件变量）。这部分数据会用于取消（cancellation）。
- 只有当其他线程处于活跃状态时，Shared 中的数据才会在线程间共享。某些操作，例如修改 input，需要拿到 Shared 的 &mut 句柄。这个句柄是通过 Arc::get_mut 获得的；显然，只有当所有 snapshot 和线程都已停止执行时这才可能发生，因为此时 Arc 必须只剩唯一一个句柄。
Routes 结构体，包含查找任意 ingredient 所需的信息。这部分数据同样在各个句柄之间共享。把它从 Shared 中拆出来，是因为它始终都是真正不可变的；我们希望在获取 Shared 的 &mut 访问权时，仍然能够同时持有 Routes 的句柄。
Runtime 结构体，它专属于某一个具体数据库实例。它保存单个活跃线程的数据，同时也持有一些指向共享数据的链接。

修订计数器的递增

Salsa 的整体模型是：数据库有一个唯一的“主”副本，以及零个或多个 snapshot。这些 snapshot 并不是直接被拥有的，而是被包在 Snapshot<DB> 类型中，这个类型只允许 & 解引用。因此，唯一能通过 &mut 引用访问的数据库，始终只有主数据库。不过每个 snapshot 都会在 Storage 持有 ingredient 的那个 Arc 上再多持有一个句柄。

每当用户尝试进行某个 &mut 操作，例如修改 input 字段时，首先就必须取消掉所有并行 snapshot，并等待那些线程结束。等它们结束之后，我们就可以通过 Arc::get_mut 拿到指向 ingredient 数据的 &mut 引用。这样一来，我们无需任何 unsafe 代码就能获得 &mut 访问，并且还能保证其他工作线程已经被成功取消（否则我们只会把自己送进死锁）。

这里最关键的一点是：在继续往下执行之前，它会先调用 cancel_other_workers：

#![allow(unused)]
fn main() {
    /// Sets cancellation flag and blocks until all other workers with access
    /// to this storage have completed.
    ///
    /// This could deadlock if there is a single worker with two handles to the
    /// same database!
    ///
    /// Needs to be paired with a call to `reset_cancellation_flag`.
    fn cancel_others(&mut self) -> &mut Zalsa {
        debug_assert!(
            self.zalsa_local
                .try_with_query_stack(|stack| stack.is_empty())
                == Some(true),
            "attempted to cancel within query computation, this is a deadlock"
        );
        self.handle.zalsa_impl.runtime().set_cancellation_flag();

        self.handle
            .zalsa_impl
            .event(&|| Event::new(EventKind::DidSetCancellationFlag));

        let mut clones = self.handle.coordinate.clones.lock();
        while *clones != 1 {
            clones = self.handle.coordinate.cvar.wait(clones);
        }
        // The ref count on the `Arc` should now be 1
        let zalsa = Arc::get_mut(&mut self.handle.zalsa_impl).unwrap();
        // cancellation is done, so reset the flag
        zalsa.runtime_mut().reset_cancellation_flag();
        zalsa
    }
}

Salsa 运行时

Salsa runtime 为各个 ingredient 提供辅助方法。例如，它会跟踪活跃查询栈，并提供在查询之间建立依赖的方法（如 report_tracked_read），以及解决循环的能力。它还会跟踪当前修订，以及关于“低持久性”和“高持久性”值上次何时发生变化的信息。

大体上说，ingredient 结构体负责存储那些“静止的数据” 例如缓存值，以及“每个 ingredient 自己持有”的内容。

而 runtime 负责存储那些“活跃的、进行中的数据”，例如当前有哪些查询在栈上，以及当前活跃查询访问了哪些依赖。

`'db` 生命周期

Tracked 结构体和 interned 结构体都会带一个 'db 生命周期。这个生命周期与创建它们时使用的 db: &DB 引用绑定在一起。 'db 生命周期带来了几个重要影响：

它保证了当某个 tracked / interned 结构体仍在被活跃使用时，用户不能开启一个新的 Salsa 修订。因为开启新修订需要修改 input，而这要求拿到 &mut DB，所以在 'db 生命周期期间这件事不可能发生。
- 而且该结构体在新修订中甚至可能根本不存在，所以允许继续访问它本身也会让语义变得混乱。
它也使得这些结构体可以用指针来实现，而不是 salsa::Id，从而让字段访问更高效（不再需要读锁）。

本节讨论的就是这种基于指针访问所用到的 unsafe 代码，以及背后的推理。为了更具体一些，我们主要聚焦 tracked struct，因为 interned struct 与它非常相似。

关于 UB 的说明

当本页说“用户不能做 X”时，我们的意思是：在不触发 Undefined Behavior 的前提下，用户不能做 X。例如通过随意 transmute 整数之类的方式并不在讨论范围内。

需要证明的义务

下面是一个 tracked struct 的典型生命周期，以及其中那些需要我们为 unsafe 假设给出证明的用户操作：

某个 tracked 函数 f 在修订 R0 中执行，第一次创建了一个 #[id] 字段为 K 的 tracked struct。
- K 会被存进 interning hashmap，并映射到一个全新的标识符 id。
- 标识符 id 会作为 StructMap 的键，指向一块新分配的内存 alloc : Alloc。
- 一个 ts: TS<'db> 会由这个原始指针 alloc 构造出来，并返回给用户。
用户通过 ts.field(db) 访问 ts 的字段 field。
- Unsafe： 这一步会访问指向 alloc 的原始指针。
开始一个新修订 R1。
tracked 函数 f 在 R1 中没有重新执行。
用户再次通过 ts.field(db) 访问字段 field。
- Unsafe： 仍然是在访问指向 alloc 的原始指针。
开始一个新修订 R2。
tracked 函数 f 在 R2 中重新执行，并再次以键 K 创建了一个 tracked struct，但字段值（某些）发生了变化。
- ts 的字段会被更新。
用户再次通过 ts.field(db) 访问字段 field。
- Unsafe： 这里仍然会访问指向 alloc 的原始指针。
开始一个新修订 R3。
当 f 这次执行时，它不会再创建一个键为 K 的 tracked struct。因此 tracked struct ts 会被放进“待删除”列表。
开始一个新修订 R4：
- 分配 alloc 被释放。

如上所示，用户能够触发的核心 “unsafe” 操作，就是访问 tracked struct 的字段。 tracked struct 内部保存的是一个指向 alloc 的原始指针，这块内存由 ingredient 持有，并包含字段数据。而访问字段时会返回一个指向 alloc 内字段的 & 引用，这意味着我们必须保证 Rust 的两个核心约束在这个引用的生命周期内始终成立：

alloc 这块分配不会被释放（也就是不会 drop）。
字段内容不会被修改。

而从上面的序列可以看出，我们需要在多种场景下证明这两件事：

新创建出来的 tracked struct。
在旧修订中创建、并在当前修订中被重新验证过的 tracked struct。
在当前修订中字段被更新过的 tracked struct。
在当前修订里并未被创建的 tracked struct。

定义

对于任意 tracked struct ts，我们称它有一个定义查询（defining query）f(..)。这指的是 tracked 函数 f 的某一次具体调用，其中参数集合 .. 也是特定的。在单个修订内，这个定义查询是唯一的，也就是说，对同一组参数，f 最多只会执行一次。

我们说一个查询在修订 R 中执行过，是指它的函数体在该修订里真的被执行了。一旦发生这种情况，该查询定义（创建）的所有 tracked struct，都会与这个查询结果一起被记录下来。

我们说一个查询在修订 R 中被验证过，是指 Salsa 系统判定它的输入没有变化，因此跳过了函数体执行。这同样会导致该查询定义的 tracked struct 被视为已验证（更具体地说，我们会在它们身上执行一个函数，更新一些内部字段，稍后会解释）。

当我们谈到 ts 时，我们指的是……

定理：在新修订开始时，所有对 `ts` 的引用都位于 Salsa 数据库内部

在 ts 被删除之后，仍然可能存在一些 memoized 值继续引用 ts，但它们必须有某个 red input query。

即使用户函数是非确定性的，这件事还成立吗？

直觉上的论证是：成立。因为基于“不可伪造性”，那些 memoized 值本身其实无法被用户拿到并继续访问。那么这些 memoized 值最初是如何得到 TS<'db> 的呢？它只能来自某个函数参数（XX：那 thread-local state 呢）。所以如果要再次访问这个值，用户必须重新提供那些函数参数。但这些参数本身又是怎么来的？

潜在漏洞包括：

某些 thread-local API 可以把 'db 值“隐式地”往下传，从而让你在返回值里带出它们，而它们并没有显式出现在参数里。例如一个 tracked 函数 () -> S<'db>，它实际上是从 thread-local state 里取到值的。
- 我们也许可以通过定义一组 trait，去静态检查返回值里的生命周期标记内容“理论上都可能来自某个参数”，但我并不觉得这能彻底证明一切。所以我们要么告诉用户“别这么做”，要么就需要某种动态检查机制，例如带版本号的指针。需要注意，这件事目前确实会涉及 unsafe，但更多是因为现有 API 的能力边界。
- 另一种思路是把删除对象的清理工作做得更彻底。这个方向是可行的。
还有那些很奇怪的 Eq 实现之类的问题呢？我们是不是也得把它们视作 unsafe？

定理：在修订 R 中访问 tracked struct `ts`，其定义查询 `f(..)` 必须已经在 R 中执行过或被验证过

这是后续大部分推理的核心。基本想法是：用户不能“伪造”一个 tracked struct 实例 ts。他们只能通过 Salsa 的内部机制拿到它。这点非常关键，因为 Salsa 会把指向字段内部的 & 引用交给用户，而这些引用在一个修订内必须保持有效。但在新修订开始时，Salsa 可能会修改这些字段，甚至释放对应分配。之所以这仍然安全，就是因为用户不可能在新修订开始时还持有对 ts 的可用引用。

引理

我们会沿着前面那条生命周期序列，按修订顺序推进证明（也可以把它看作一种归纳证明）。

在 R0 第一次创建 `ts` 之前

用户最初拿到 ts: TS<'db>，必然是通过调用 TS::new(&db, ...)。原因是，创建 TS 实例需要提供一个 NonNull<salsa::tracked_struct::ValueStruct> 指针，而这是某个 unsafe 函数的参数，其契约要求这个指针必须有效。

FIXME： 严格来说这句话现在还不完全正确。我觉得构造函数目前可能只是个私有 tuple ctor，我们应该把这点修正掉。

在 R0 期间

归纳情形：考虑某个修订 R

我们先展示一些不可能发生的情况：

访问一个从未被创建过的 tracked struct ts 的字段。
在 ts 已经被释放后继续访问它的字段。

引理（不可伪造）：用户无法伪造 tracked struct

第一个观察是：用户无法“伪造”一个 tracked struct ts 实例。他们必须拿到一个指向 Alloc 的指针。这意味着每个 tracked struct ts 的来源都只能是 ingredient。而像 input struct 就不是这样，因为 input struct 只是用整数 id 构造出来的，用户完全可以自己随便编一个。

引理（单修订内）：用户无法跨修订持有 tracked struct `ts`

tracked struct ts: TS<'db> 的生命周期 'db 是由一个 db: &'db dyn Db 句柄生成出来的。而开启一个新修订需要拿到 &mut 引用。因此，只要用户还在活跃地使用 ts，数据库就不可能开始新修订。

检查点： 如果用户手里有两个数据库并调用了一些内部方法，会不会绕过这个约束？也许会，我们可能需要再补一些断言。

定理：在修订 R0 中拿到 tracked struct `ts`，创建它的 tracked 函数 `f` 必须先执行过或被验证过

上面两个点结合起来，就能推出……

创建新值

每个新值都会通过 StructMap::insert 被存放进一个 salsa::alloc::Alloc 中。 Alloc 可以看作标准 Rust Box 的一种变体，但它不携带唯一性语义。这意味着每个 tracked struct 都有自己单独的一块分配。这块分配由 tracked struct ingredient 持有，因此只要 tracked struct ingredient 还活着，或者它尚未被移除，这块内存就会保持有效（至于移除时如何保证安全，稍后还会继续讨论）。

用户可见类型内部使用的是原始指针

#[salsa::tracked] 宏会生成一个暴露给用户的结构体，大致形如下：

#![allow(unused)]
fn main() {
// 这个结构体包装了实际字段，
// 额外附带一些修订元数据。
// 你可以把它理解为 tracked struct 字段的一层 newtype 包装。
use salsa::tracked_struct::ValueStruct;

struct MyTrackedStruct<'db> {
    value: *const ValueStruct<..>,
    phantom: PhantomData<&'db ValueStruct<...>>
}
}

这里有两个关键点：

运行时实际保存的并不是指向 ValueStruct 的 Rust 引用，而是原始指针。这是为了符合 stacked borrows 规则。
PhantomData 被用来维持 'db 生命周期信息。

我们之所以在结构体里存原始指针，是因为这个结构体实例本身会活得比某次具体的 'db 引用更久。看下面这个例子：

#![allow(unused)]
fn main() {
let mut db = MyDatabase::default();
let input = MyInput::new(&db, ...);

// Revision 1:
let result1 = tracked_fn(&db, input);

// Revision 2:
input.set_field(&mut db).to(...);
let result2 = tracked_fn(&db, input);
}

tracked_fn 在 Revision 1 创建的 tracked struct，可能会在 Revision 2 中被复用，但创建它们时使用的那个原始 &db 引用已经过期了。如果我们把它存成真正的 Rust 引用，那就会违反 stacked borrows 规则。

因此我们选择保存原始指针；当用户调用某个字段访问器时，我们再临时创建一个新的引用：

#![allow(unused)]
fn main() {
impl<'db> MyTrackedStruct<'db> {
    fn field(self, db: &'db dyn DB) -> &'db FieldType {
        ...
    }
}
}

这个引用与 db 绑定，并且只要……

“静止状态”下的 `'db` 生命周期

跨修订更新 tracked struct 字段

`XX`

安全性引理

这些引理用于支撑整个系统的安全性论证。

在某个修订 R 中使用 `MyTracked<'db>`，总是发生在一次 `MyTracked::new` 调用之后

当某个 tracked struct 实例 TS<'db> 第一次在修订 R1 中被创建时，其结果对应的是一块全新的分配，因此此前不可能已经存在它的别名。

此时 TS<'db> 也会被存入 Salsa 数据库。而在后续修订里，我们断言……

`&'db T` 引用永远不会被存进数据库

我们维护一个不变量：在后续任意修订 R2 中，……

然而在某个更晚的修订 R2 中，又是如何……

这套机制可能出错的方式，以及我们如何防止它们

把一个 `&'db T` 存进字段里

在 tracked struct 仍然活着时释放它的内存

tracked struct 的别名问题

跟踪结构体

Tracked struct 会用一种特殊方式存储，以降低它们的成本。

Tracked struct 通过 new 操作来创建。

tracked struct ingredient 与 tracked field ingredient

对于单个 tracked struct，我们会生成多个 ingredient。

首先创建的是 tracked struct ingredient。它负责提供创建结构体新实例的方法，因此也独占访问那些用来生成 struct id 的 interner 和 hashmap。它还会共享访问另一个 hashmap，这个 hashmap 存储的是包含字段数据的 ValueStruct。

而对于每个字段，我们都会创建一个 tracked field ingredient，它负责调节对某个具体字段的访问。这些 ingredient 全部共享访问同一个 hashmap，从而能通过某个 id 找到对应的 ValueStruct。 ValueStruct 中不仅保存字段值，也保存这些字段上一次发生变化时对应的修订版本。

每个 tracked struct 都有全局唯一的 id

首先会为这个 tracked struct 生成一个全局唯一的 32 位 id。它是通过 intern 以下信息的组合得到的：

当前正在执行的查询。
#[id] 字段的一个 u64 哈希值。
一个 disambiguator，用于保证这个哈希值在当前查询内部唯一。也就是说，当某个查询开始执行时，它会创建一个空 map；第一次创建某个给定哈希值的 tracked struct 时，它拿到的 disambiguator 是 0；下一次则会拿到 1，以此类推。

每个 tracked struct 都有一个 `ValueStruct` 来存储数据

struct ingredient 和 field ingredient 会共享访问一个 hashmap，它把每个 field id 映射到一个 value struct：

pub struct Value<C>
where
    C: Configuration,
{
    /// The revision when this tracked struct was last updated.
    /// This field also acts as a kind of "lock" over the `value` field. Once it is equal
    /// to `Some(current_revision)`, the fields are locked and
    /// cannot change further. This makes it safe to give out `&`-references
    /// so long as they do not live longer than the current revision
    /// (which is assured by tying their lifetime to the lifetime of an `&`-ref
    /// to the database).
    ///
    /// The struct is updated from an older revision `R0` to the current revision `R1`
    /// when the struct is first accessed in `R1`, whether that be because the original
    /// query re-created the struct (i.e., by user calling `Struct::new`) or because
    /// the struct was read from. (Structs may not be recreated in the new revision if
    /// the inputs to the query have not changed.)
    ///
    /// When re-creating the struct, the field is temporarily set to `None`.
    /// This is signal that there is an active `&mut` modifying the other fields:
    /// even reading from those fields in that situation would create UB.
    /// This `None` value should never be observable by users unless they have
    /// leaked a reference across threads somehow.
    updated_at: OptionalAtomicRevision,

    /// The durability minimum durability of all inputs consumed
    /// by the creator query prior to creating this tracked struct.
    /// If any of those inputs changes, then the creator query may
    /// create this struct with different values.
    durability: Durability,

    /// The revision information for each field: when did this field last change.
    /// When tracked structs are re-created, this revision may be updated to the
    /// current revision if the value is different.
    revisions: C::Revisions,

    /// Fields of this tracked struct. They can change across revisions,
    /// but they do not change within a particular revision.
    ///
    /// TODO: Consider whether we need a more explicit aliasing barrier or whether
    /// this should be restructured (e.g., with a nested struct for `fields` + `memos`)
    /// to make the aliasing guarantees more obvious. See PR #741 for prior discussion.
    fields: C::Fields<'static>,

    /// Memo table storing the results of query functions etc.
    /*unsafe */
    memos: MemoTable,
}

这个 value struct 既保存字段值，也保存字段上次发生变化的修订版本。每当这个结构体在新修订中被重新创建时，都会比较新旧字段值，并据此创建新的修订记录。

宏会生成 tracked struct 的 `Configuration`

tracked struct 的 “configuration” 不仅定义了字段类型，还定义了一些关键操作，例如如何提取可哈希的 id 字段，以及如何更新那些用来记录字段最后一次变化时间的 “revisions”：

/// Trait that defines the key properties of a tracked struct.
///
/// Implemented by the `#[salsa::tracked]` macro when applied
/// to a struct.
pub trait Configuration: Sized + 'static {
    const LOCATION: crate::ingredient::Location;

    /// The debug name of the tracked struct.
    const DEBUG_NAME: &'static str;

    /// The debug names of any tracked fields.
    const TRACKED_FIELD_NAMES: &'static [&'static str];

    /// The relative indices of any tracked fields.
    const TRACKED_FIELD_INDICES: &'static [usize];

    /// Whether this struct should be persisted with the database.
    const PERSIST: bool;

    /// A (possibly empty) tuple of the fields for this struct.
    type Fields<'db>: Send + Sync;

    /// A array of [`AtomicRevision`][] values, one per each of the tracked value fields.
    /// When a struct is re-recreated in a new revision, the corresponding
    /// entries for each field are updated to the new revision if their
    /// values have changed (or if the field is marked as `#[no_eq]`).
    #[cfg(feature = "persistence")]
    type Revisions: Send
        + Sync
        + Index<usize, Output = AtomicRevision>
        + plumbing::serde::Serialize
        + for<'de> plumbing::serde::Deserialize<'de>;

    #[cfg(not(feature = "persistence"))]
    type Revisions: Send + Sync + Index<usize, Output = AtomicRevision>;

    type Struct<'db>: Copy + FromId + AsId;

    fn untracked_fields(fields: &Self::Fields<'_>) -> impl Hash;

    /// Create a new value revision array where each element is set to `current_revision`.
    fn new_revisions(current_revision: Revision) -> Self::Revisions;

    /// Update the field data and, if the value has changed,
    /// the appropriate entry in the `revisions` array (tracked fields only).
    ///
    /// Returns `true` if any untracked field was updated and
    /// the struct should be considered re-created.
    ///
    /// # Safety
    ///
    /// Requires the same conditions as the `maybe_update`
    /// method on [the `Update` trait](`crate::update::Update`).
    ///
    /// In short, requires that `old_fields` be a pointer into
    /// storage from a previous revision.
    /// It must meet its validity invariant.
    /// Owned content must meet safety invariant.
    /// `*mut` here is not strictly needed;
    /// it is used to signal that the content
    /// is not guaranteed to recursively meet
    /// its safety invariant and
    /// hence this must be dereferenced with caution.
    ///
    /// Ensures that `old_fields` is fully updated and valid
    /// after it returns and that `revisions` has been updated
    /// for any field that changed.
    unsafe fn update_fields<'db>(
        current_revision: Revision,
        revisions: &Self::Revisions,
        old_fields: *mut Self::Fields<'db>,
        new_fields: Self::Fields<'db>,
    ) -> bool;

    /// Returns the size of any heap allocations in the output value, in bytes.
    fn heap_size(_value: &Self::Fields<'_>) -> Option<usize> {
        None
    }

    /// Serialize the fields using `serde`.
    ///
    /// Panics if the value is not persistable, i.e. `Configuration::PERSIST` is `false`.
    fn serialize<S>(value: &Self::Fields<'_>, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: plumbing::serde::Serializer;

    /// Deserialize the fields using `serde`.
    ///
    /// Panics if the value is not persistable, i.e. `Configuration::PERSIST` is `false`.
    fn deserialize<'de, D>(deserializer: D) -> Result<Self::Fields<'static>, D::Error>
    where
        D: plumbing::serde::Deserializer<'de>;
}

查询操作

所有查询都支持的、最重要的基础操作有两种：

maybe changed after：如果某个查询（针对给定 key）的值，自某个修订之后可能发生了变化，就返回 true。
Fetch：返回给定 K 的最新值（如果发生了未恢复的循环，则返回错误）。

在某个修订之后是否可能发生变化

maybe_changed_after 操作用来计算某个查询的值在给定修订之后是否可能发生过变化。换句话说，如果查询 Q 的值可能在 (R+1)..R_now 这些修订之间发生了变化，那么 Q.maybe_change_since(R) 就会返回 true，其中 R_now 是当前修订。注意，对 maybe_changed_after(R_now) 提问本身是没有意义的。

输入查询

输入查询由用户显式设置，因此 maybe_changed_after 只需要检查该值上一次被设置的时间并进行比较即可。

Interned 查询

派生查询

派生查询上的逻辑要复杂得多。这里只总结高层思路；如果你想继续深挖，流程图会很有帮助。术语一节也可能派上用场；在某些场合，我们会在某个术语第一次出现时直接链接过去。

如果找到了现有的 memo，那么先检查它是否已经在当前 revision 中被 verified。如果是，就可以比较它的 changed at 修订，并据此返回 true 或 false。
否则，我们就必须检查 dependencies 是否发生过变化：
- 设 R 为这个 memo 上一次被验证的修订；我们想知道自修订 R 以来，它的依赖里是否有任何一个发生了变化。
- 首先检查 durability。对每个 memo，我们都会记录其依赖中的最小 durability。如果某个 memo 的 durability 是 D，并且自上次验证以来，没有任何 durability 为 D 的输入发生变化，那么就无需再做额外工作，也可以把这个 memo 视为已验证。
- 如果 durability 检查还不够，那就必须逐个检查依赖。做法是遍历每个依赖 D，并调用 maybe changed after 来检查 D 自修订 R 之后是否发生了变化。
- 如果没有任何依赖发生变化：
  - 那么我们就可以把 memo 标记为已验证，并使用它的 changed at 修订来返回 true 或 false。
如果依赖确实发生了变化：
- 那么我们就执行用户的查询函数（与 fetch 操作中的逻辑相同），这个过程可能会对最终结果进行 backdate。
- 然后比较新结果 memo 的 changed at 修订，并据此返回 true 或 false。

Fetch

fetch 操作用来计算某个查询的值。只要可能，它就会优先复用已经缓存（memoized）的值。

输入查询

输入查询只需要直接从表中读取结果即可。

Interned 查询

Interned 查询会把输入映射到一个 hashmap 中，查找是否已经存在对应的整数 id。如果不存在，就创建一个新值。

派生查询

派生查询的逻辑要更复杂一些。这里先总结高层思路；如果想继续深入，流程图会很有帮助。术语一节也同样值得配合阅读；在某些地方，我们会在术语第一次出现时直接链接过去。

如果找到了现有的 memo，我们先检查它是否已经在当前 revision 中被 verified。如果是，就可以直接返回缓存值。
否则，如果这个 memo 里保存了缓存值，那么我们就必须检查 dependencies 是否发生了变化：
- 设 R 为这个 memo 上一次被验证的修订；我们想知道自修订 R 以来，依赖中是否有任何一个发生了变化。
- 首先检查 durability。对每个 memo，我们都会记录其依赖的最小 durability。如果某个 memo 的 durability 是 D，并且自上次验证以来，没有任何 durability 为 D 的输入发生过变化，那么无需额外工作，也可以把这个 memo 视为已验证。
- 如果 durability 检查还不够，那就必须逐个检查依赖。做法是遍历每个依赖 D，并调用 maybe changed after 来判断 D 自修订 R 之后是否已经变化。
- 如果没有任何依赖变化：
  - 那么就可以把这个 memo 标记为已验证，并直接返回它缓存的值。
如果依赖发生了变化，或者 memo 根本没有保存缓存值：
- 那么就执行用户的查询函数。
- 接下来，计算这个缓存值最后一次发生变化的修订：
  - Backdate： 如果之前存在旧的缓存值，并且新值与旧值相等，那么我们就可以对这个 memo 做 backdate，也就是沿用之前的 changed at 修订。
    - 借助 backdating，就有可能出现这样的情况：查询的某个依赖在修订 R1 中变化了，但查询本身的输出却是在某个更早的修订 R2 中最后一次变化的，其中 R2 < R1。
  - 否则，就使用当前修订。
- 然后为这个新值构造一个新的 memo 并返回。

派生查询流程图

派生查询是至今为止最复杂的概念。

此流程图记录了 maybe_changed_after 和 fetch 操作的流程。

此流程图可在 draw.io 上编辑。

Flowchart

循环

跨线程阻塞

当前，用于跨线程阻塞的接口按如下方式工作：

当线程 T1 想要阻塞等待另一个线程 T2 正在执行的查询 Q 时，它会调用 Runtime::try_block_on。这个调用会检查是否存在循环。假设没有检测到循环，它就会阻塞 T1，直到 T2 完成 Q。此时 T1 会被唤醒。不过，我们并不知道执行 Q 的结果，所以 T1 现在必须“重试”（retry）。通常这会成功读到缓存值。
当 T1 被阻塞时，运行时会把它的查询栈（一个 Vec）移动到共享依赖图数据结构中。当 T1 被唤醒时，它会在 try_block_on 返回前重新取回这份查询栈的所有权。

检测循环

当线程 T1 试图执行查询 Q 时，它会尝试从记忆化表中加载 Q 的值。如果发现一个 InProgress 标记，就表示 Q 当前正在计算中。这说明可能存在循环。接着 T1 会尝试阻塞等待查询 Q：

如果 Q 也是由 T1 在计算，那么就存在循环。
否则，如果 Q 是由另一个线程 T2 在计算，我们就必须检查 T2 是否（传递地）阻塞在 T1 上。如果是，就存在循环。

这两种情况都由 Runtime::try_block_on 在内部处理。检测线程内循环比较容易；为了检测跨线程循环，运行时维护了一张线程之间的依赖 DAG（线程以 RuntimeId 标识）。在把一条边 T1 -> T2（也就是 T1 阻塞等待 T2）加入 DAG 之前，它会先检查从 T2 到 T1 是否已经存在一条路径。如果存在，就说明形成了循环，这条边不能加入（否则 DAG 就不再是无环的）。

术语

Backdate

回溯：指将在版本 R 中计算的值标记为在某个较早的版本中最后一次更改。

这在有一个较旧的 memo M 时完成，并且我们可以比较这两个值来看到它，虽然对 M 的依赖项 (dependencies) 可能已经改变，但查询函数 (query function) 的结果没有改变。

Changed at

memo 的 changed_at 修订版本 (revision) 是指 memo 的值上次更改所在的修订版本。

通常，这与上次执行查询函数 (query function) 的版本相同，但如果 memo 是回溯的 (backdated)，则可能是较早的版本。

Dependency

查询 (query) Q 的 依赖项 (dependency)：指其他某个查询 Q1，该查询是作为与 Q 有关的调用中计算值的一部分（调用通常为 Q 的 query function）。

Derived query

派生查询 (derived query) ：指一种这样的查询 (query)，它的值由使用者所提供的 query function 的结果确定。

执行那种查询函数以获得查询结果。与输入查询 (input queries) 不同的是，每当需要的时候，只需重新执行函数，派生查询的结果就可以随时重新计算。

Durability

持久性 (durability)：指 Salsa 用来避免单独检查查询 (query) 的依赖项 (dependencies) 的一种优化。

Input query

输入查询 (input query) 是其值由用户显式设置的查询 (query)。当设置该值时，还可以提供持久性 (durability)。

Ingredient

配料（ingredient）指的是用于构成某个 Salsa 条目（Salsa item）的一块独立存储。

LRU

set_lru_capacity 方法可用于将查询的最大容量固定为特定数量的值。

如果在设置之后添加了更多的值，Salsa 则删除较旧的 memos 中的值以节省内存。

然而，Salsa 总是保留这些 memo 的依赖项 (dependency) 信息，以便仍然可以计算值是否已经改变，即使不知道该值是什么。

Memo

memo 存储有关上次执行某个查询 (query) Q 的 query function 的信息：

通常，它包含从该查询函数返回的值，因此不必再次执行这个查询函数。
- 然而，这并不总是正确的：一些查询不缓存其结果值，并且值也可能由于 LRU 集合而被删除。
- 此时，memo 仅存储依赖项 (dependency) 的信息，该信息对于确定将 Q 作为依赖项的其他查询是否已更改很有用。
memo 上次验证 (verified) 的修订版本 (revision)。
memo 的值上次更改的 (changed at) 修订版本。注意，它可能是回溯的 (backdated)。
memo 的依赖项 (dependencies) 的最小持久性 (durability) 。
（如果有的话）完整的依赖项的集合，或 memo 未跟踪的依赖项 (untracked dependency) 的标记。