一个增量计算框架如何设计与实现——以 Salsa 为例

在富文本文档里输入一个字，变化首先落在某个文本节点上，后续工作却可能越过这个节点：分段、换行、段落布局、分页，以及保存时的格式转换，都需要确认已有结果还能不能继续使用。协同编辑让更新来源更多，本地输入与远端操作都会改变文档，而每次更新的范围通常只占整篇文档的一小部分。

修改一个段落，其他段落的换行结果可能仍然有效；但这个段落高度变化，又可能影响后续分页。增量计算要在这些计算之间找到边界：哪些输入被读取过，哪些结果需要重算，新结果改变后又会影响谁。仅仅保存上次的返回值，还不足以回答这些问题。

Salsa 将计算组织成查询，用函数表达计算逻辑，由运行时维护依赖与缓存。下面从文档更新中的复用问题出发，再沿 Salsa 的 calc 示例走读查询、字段与运行时的实现，观察这种设计怎样确认复用依据、更新派生数据和截断变化传播。

一、背景

1. 增量计算框架要解决什么问题

假设段落 A 已经完成换行，段落 B 又收到一次远端编辑。A 的文本、字体和可用宽度都没有变化，就有机会继续使用原来的换行结果。若变化发生在 A 自己的文本中，旧结果则需要重新确认。我们希望每次更新只触发必要的计算，同时保证展示的结果来自当前文档状态。

一种直接办法是把计算写成 line_break(text, font, width)，保存这组参数对应的结果。再次遇到完全相同的参数，就可以取得缓存。这就是 Memoization：用完整输入定位已经完成的计算。

文档系统中的接口往往只接收段落 ID，再从模型中读取文本、样式和宽度。同一个段落 ID 可以对应不同内容，ID 相同并不足以说明缓存有效。若把整篇文档的修订也放入缓存 key，B 的一次编辑又会让 A 使用新的 key，失去区分相关与无关修改的机会。

增量计算框架需要把“定位计算”和“验证输入”分别处理。段落 ID 用于找到旧计算；计算过程中实际读取的文本、样式和宽度，才是判断它还能否使用的依据。Salsa 把具有缓存和依赖跟踪能力的函数称为查询，一个查询实例由查询种类和参数共同确定，例如 line_break(paragraph_a) 与 line_break(paragraph_b) 分别保存结果，同一个段落的换行与布局也属于不同查询。

如果将文档的派生计算组织成查询，可以得到下面这样的读取关系。这里用它说明计算边界；后面的源码示例采用 calc 中的解析与检查查询。箭头表示右侧计算读取左侧结果：

flowchart LR
    T["段落文本"] --> L["换行结果"]
    S["字符样式"] --> L
    W["可用宽度"] --> L
    L --> P["段落布局"]
    P --> G["页面布局"]

每个查询保存自己的直接依赖。页面布局读取段落布局，段落布局再读取换行结果；页面布局不必复制换行时读取的全部文本和样式依赖，验证时可以沿这些关系继续检查。多个消费者也可以共用同一个子查询的结果。

依赖图在执行中逐步建立。布局可能根据段落类型选择不同计算，名称查找可能根据表达式读取不同对象；运行时只有在读取发生后，才能记录对应关系。查询重新执行时，需要收集本轮实际使用的输入。

输入变化与结果变化也要分别处理。例如，若页面布局只消费段落的几何信息，一次颜色修改没有改变段落尺寸，分页就可能继续使用旧结果；需要绘制颜色的消费者仍然必须更新。能否停止传播，取决于消费者实际读取什么，以及查询返回值是否完整表达了这些信息。

协同编辑中的本地操作与远端操作都先更新文档模型，再触发派生计算。增量框架负责判断这些计算的复用，不负责决定协同操作如何合并。它的两个基本要求是：确认产生结果时使用了哪些输入，判断新旧结果是否等价。纯函数、函数组合和值相等，为理解这两个要求提供了基础。

2. 函数式计算模型

2.1 纯函数与引用透明性

纯函数的返回值由输入决定，执行过程不产生外部可观察的副作用。例如：

fn is_even(number: i64) -> bool {
    number % 2 == 0
}

对这个函数输入 11，结果是 false；再次输入 11，仍然得到 false。因此，在使用返回值的表达式中，可以用 false 替换 is_even(11)，不会改变表达式的含义。这种性质称为引用透明性。

缓存正是利用了这一性质：已经得到结果后，后续调用可以使用保存的值。如果函数还读取当前时间，相同参数就可能产生不同结果；如果调用负责发送消息，复用返回值则会跳过发送操作。这些额外行为需要单独管理，不能只根据参数复用结果。

纯函数可以使用局部可变变量。解析器在函数内部推进游标、向 Vec 添加节点，只要这些状态由输入初始化，不影响外部状态，仍然可以让完整输入决定完整输出。局部可变实现并不会自动破坏引用透明性。

Salsa 的查询参数可能只是数据对象标识，因此还要把受跟踪的数据库读取计入输入。文件 ID 决定读取哪个文件，文本字段决定解析什么内容。查询应当根据参数与这些读取计算结果；读取未受跟踪的外部状态，则会使缓存缺少验证依据。

2.2 函数值、高阶函数与闭包

函数可以作为值保存、传递，也可以成为另一个函数的返回值。接收函数或返回函数的函数，称为高阶函数。

Rust 的迭代器提供了常见例子：

fn is_even(number: i64) -> bool {
    number % 2 == 0
}

fn main() {
    let numbers = [11_i64, 13, 14];
    let parity: Vec<bool> = numbers.into_iter().map(is_even).collect();
    assert_eq!(parity, [false, false, true]);
}

这里传入 map 的 is_even 是函数值，map 则是高阶操作。map 实现逐项转换的过程，参数决定如何转换。这种分工允许同一段遍历逻辑处理不同计算。

闭包是能够捕获环境的函数值。例如，在比较之前固定一个阈值：

fn main() {
    let threshold = 10;
    let above_threshold = move |number: i64| number > threshold;
    assert!(above_threshold(11));
    assert!(!above_threshold(10));
}

above_threshold 保存了 threshold，调用时只需提供 number。本例捕获一个固定值，相同输入可以得到相同结果；若闭包访问共享可变状态，就需要进一步考虑该状态的变化。

闭包捕获环境时，可以借用变量，也可以通过 move 接管它们。具体的调用约束取决于函数体怎样使用这些值：只读取捕获值时，可以通过共享借用重复调用；需要修改捕获值时，调用要求可变借用；把捕获值移交出去时，闭包可能只能调用一次。Rust 用 Fn、FnMut、FnOnce 表达这些能力，调用方据此声明它需要哪一种函数。

move 决定捕获值怎样进入闭包，Fn 系列 trait 描述闭包怎样被调用，两者不能混为一谈。它们也不检查纯度：实现 Fn 的闭包仍可能通过内部可变性修改外部状态。进一步阅读：Rust 的闭包与捕获规则。

高阶函数使计算过程与具体规则可以分别定义。后面的 Salsa 源码也有类似分工：通用运行时处理缓存和验证，查询配置提供具体执行与结果比较规则，不过实现采用的是 trait 和关联类型。

2.3 柯里化与部分应用

一个接收两个参数的乘法函数，可以表示为：

multiply : (Factor, Number) → Number

柯里化将它转换为一系列单参数函数。先提供 Factor，取得一个接收 Number 的函数，再由后者计算结果：

curried_multiply : Factor → (Number → Number)

在 Rust 中，可以用返回闭包的闭包表达这个过程：

fn main() {
    let curried_multiply = |factor: i64| move |number: i64| factor * number;
    let triple = curried_multiply(3);
    assert_eq!(triple(7), 21);
}

curried_multiply(3) 尚未执行乘法，它返回了一个保存倍率 3 的闭包。调用 triple(7) 时，两个参数才都具备。

部分应用指的是固定一部分参数，得到仍需其他参数的计算。上例中取得 triple 就是一次部分应用。它也可以用于普通双参数函数：写成 |number| multiply(3, number)，同样得到固定倍率的函数。

柯里化改变的是函数的结构：接收两个参数的函数，被表示成先返回一个函数、再接收第二个参数的形式。部分应用是固定参数的操作：给乘法提供 3，就得到一个只需要另一个数字的“乘以 3”函数。前面的 triple 可以由柯里化函数产生，也可以由普通双参数函数外包一层闭包产生。

Haskell 中的 add x y 按 (add x) y 调用，因此 add 1 自然得到“加一”函数。Rust 的普通多参数函数不会自动采用这种形式，需要显式返回闭包。这里的关键是区分“函数如何组织参数”和“本次已经提供了哪些参数”。进一步阅读：Haskell 的柯里化与部分应用。

部分应用适合先配置规则、再处理输入的场景，例如先固定倍率，再对多个数字执行同一种转换。它与缓存是不同机制：取得 triple 并没有保存任何数字的计算结果。

将 db 固定到闭包中，可以得到只接收业务参数的函数，这属于部分应用。Salsa 的查询入口则接收 db 和查询参数，由缓存与依赖规则决定是否执行函数体。

2.4 函数组合

函数组合将前一个函数的返回值作为后一个函数的输入。若 f: A → B，g: B → C，组合后的类型就是 A → C。

下面的 compose 保留了这组类型关系：

fn compose<A, B, C>(
    first: impl Fn(A) -> B,
    second: impl Fn(B) -> C,
) -> impl Fn(A) -> C {
    move |input| second(first(input))
}

fn main() {
    let is_even = |number: i64| number % 2 == 0;
    let describe = compose(is_even, |even| if even { "even" } else { "odd" });
    assert_eq!(describe(13), "odd");
}

first 接收 A 并产生 B，second 接收这个 B 并产生 C。compose 不需要知道具体业务，只要求 first 返回的 B 能作为 second 的输入。

对于文本处理，可以分别定义文本解析、奇偶判断与展示函数，形成“文本 → 整数 → 布尔值 → 展示文本”的计算。中间值让每一步的职责清楚，也为增量计算提供了可独立比较的结果。

普通函数组合只负责传递值。Salsa 在查询之间保存返回值与依赖，某个中间结果不变时，依赖它的查询就有机会复用。例如，不同整数得到相同奇偶性，展示查询无需知道整数之间的差异。

函数拆分也有成本。为很小的操作单独建立查询，可能增加缓存定位、依赖记录和比较的开销。因此，普通辅助函数与 tracked 查询需要按计算职责和复用价值选择。

改变倍率和数字，对照普通调用、柯里化、部分应用与函数组合中的值如何传递：

2.5 不可变数据与副作用

缓存保存的结果需要具有稳定含义。如果返回一个可被外部随意修改的共享对象，对象标识虽然没变，内部内容却可能变化，运行时就不能仅凭对象标识相等确认结果有效。

不可变数据避免了这类隐式更新。变化通过构造新值表达，消费者读取既有值时不会受到后续修改影响；借用和共享可以减少复制，结果比较则用于判断新值是否与旧值等价。底层实现仍然可以使用可变哈希表、锁和原地更新，只要这些操作由运行时管理。

错误也可以作为返回值的一部分。例如，Result<i64, ParseIntError> 表示解析成功或失败，让后续代码按结果处理，避免把错误隐藏在其他状态中。完整的返回值使计算关系更容易理解，但是否可复用仍然取决于依赖与比较规则。

在 Salsa 应用中，输入更新、查询计算与外部操作有不同位置。应用先读取文件并更新数据库，查询根据数据库状态计算，应用再取得结果并显示。查询执行期间记录依赖、构造派生实体或累积诊断，由 Salsa 运行时管理；需要每次发生的外部 I/O 则应留在应用边界。

在这样的计算模型中，应用表达输入与结果之间的关系，运行时管理实际执行。接入增量框架后，这个分工还要落实为具体的数据结构：怎样定位一次查询，怎样保存它的读取，以及怎样验证旧计算。

二、Salsa 的增量计算实现

1. 用户函数怎样接入运行时

官方 calc 示例实现了一个小型语言分析器。下面这段程序包含两个函数，double 的函数体误用了未声明的变量 b：

fn double(a) = a * b
fn quadruple(a) = double(double(a))
print quadruple(2)

把 b 改成 2，错误就可以消除。输入文本需要重新解析，但 quadruple 的声明和表达式并没有修改。框架能否保留其他检查结果，取决于解析产物如何表示、检查过程读取了什么，以及这些读取在修改后是否仍然有效。

calc 把解析与检查组合在 compile 查询中：

#[salsa::tracked(returns(copy))]
pub fn compile(db: &dyn crate::Db, source_program: SourceProgram) {
    let program = parse_statements(db, source_program);
    type_check_program(db, program);
}

compile 先取得解析结果，再将它交给程序检查。解析入口读取输入文本，循环构造语句，最后创建保存语句列表的 Program 数据对象：

#[salsa::tracked(returns(copy))]
pub fn parse_statements(db: &dyn crate::Db, source: SourceProgram) -> Program<'_> {
    let source_text = source.text(db);

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

    let mut result = vec![];
    loop {
        parser.skip_whitespace();

        if parser.peek().is_none() {
            break;
        }

        if let Some(statement) = parser.parse_statement() {
            result.push(statement);
        } else {
            parser.report_error();
            break;
        }
    }

    Program::new(db, result)
}

程序检查沿语句列表处理函数声明和打印表达式：

#[salsa::tracked(returns(copy))]
pub fn type_check_program<'db>(db: &'db dyn crate::Db, program: Program<'db>) {
    for statement in program.statements(db) {
        match &statement.data {
            StatementData::Function(f) => type_check_function(db, *f, program),
            StatementData::Print(e) => CheckExpression::new(db, program, &[]).check(e),
        }
    }
}

SourceProgram 保存源文本，Program 保存解析产物。函数声明交给独立的 type_check_function 查询；表达式中的函数调用则通过 find_function 查询查找声明。这些边界将完整分析分成几项可以分别保存和验证的计算。

这些函数表达分析器的计算规则。Salsa 接管调用以后，需要先判断已有结果能否复用，再决定是否进入函数体。这个接管点由 #[salsa::tracked] 生成：宏保留原函数体，并生成一个具有相同调用方式的查询入口。

setup_tracked_fn! 中的入口模板将参数交给运行时：

#[allow(clippy::needless_lifetimes)]
$(#[$attr])*
$vis fn $fn_name<$db_lt>(
    $db: &$db_lt dyn $Db,
    $($input_id: $input_ty,)*
) -> ::salsa::plumbing::return_mode_ty!(
    ($return_mode, __), $db_lt, $output_ty
) {
    use ::salsa::plumbing as $zalsa;

    $zalsa::attach($db, || {
        let (zalsa, zalsa_local) = $db.zalsas();
        let result = $zalsa::macro_if! {
            if $needs_interner {
                {
                    let key = $fn_name::intern_ingredient_(zalsa)
                        .intern_id(zalsa, zalsa_local, ($($input_id),*));
                    $fn_name::fn_ingredient_($db, zalsa).fetch(
                        $db, zalsa, zalsa_local, key,
                    )
                }
            } else {
                {
                    $fn_name::fn_ingredient_($db, zalsa).fetch(
                        $db,
                        zalsa,
                        zalsa_local,
                        $zalsa::AsId::as_id(&($($input_id),*)),
                    )
                }
            }
        };

        $zalsa::return_mode_expression!(($return_mode, __), $output_ty, result,)
    })
}

这是 setup_tracked_fn! 生成查询函数的模板，$... 是宏展开时填入的函数名、类型与参数。attach 在数据库上下文中运行入口，两个分支最终都调用函数 ingredient 的 fetch；区别在于怎样把用户参数转换成 ID。compile(source)、parse_statements(source) 只有一个 Salsa 数据对象参数，可以直接使用对象 ID。type_check_function(function, program) 有两个参数，先将参数组合 intern，再用所得 ID 定位这组参数对应的查询。db 提供存储和运行状态，本身不进入这组业务参数。

Ingredient 是负责某类增量数据的管理器。函数 ingredient 的 IngredientImpl<C> 实现缓存、验证与执行，类型参数 C 则提供这项查询的具体规则：

Input 和 Output 是关联类型，让运行时取得这项查询对应的输入输出类型；'db 表达参数或结果对数据库的借用。需要重新计算时，execute_query 先将旧对象身份记录带入活动帧，再从 ID 恢复参数并调用用户计算：

fn execute_query<'db>(
    db: &'db C::DbView,
    zalsa: &'db Zalsa,
    active_query: ActiveQueryGuard<'db>,
    opt_old_header: Option<&MemoHeader>,
) -> (C::Output<'db>, ActiveQueryGuard<'db>) {
    if let Some(old_header) = opt_old_header {
        old_header.seed_active_query(zalsa, &active_query);
    }

    let new_value = C::execute(
        db,
        C::id_to_input(zalsa, active_query.database_key_index.key_index()),
    );

    (new_value, active_query)
}

运行时先恢复参数，再调用用户计算。不同查询的业务逻辑和返回类型由配置提供，缓存算法可以共用。这也使前面讨论的计算逻辑与执行管理有了具体实现：解析器决定如何解析，运行时决定这次是否需要解析。

入口最后按返回模式交出结果。内部 fetch 取得 memo 中结果的引用，ref 返回该借用，copy 复制值，clone 克隆值，deref 借用其目标类型。calc 的解析查询使用 copy，复制的是携带对象 ID 与生命周期标记的 Program 值；字段 getter 才从数据库中取得语句数据的借用。compile 和类型检查查询的普通返回值都是 ()，诊断另由 accumulator 管理。

现在可以区分两件事：参数决定寻找哪一项查询，fetch 决定如何取得它的结果。要理解后一个判断，先需要知道查询结果和被查询的数据分别保存在哪里。

2. 查询、字段与 memo 实际存在哪里

首次调用 compile 时，解析器通过 source.text(db) 借用文本，在局部 Parser 中构造语句列表，再用 Program::new(db, result) 将派生数据交给数据库。函数声明也在这个过程中被构造成 Function 对象。解析查询返回携带对象 ID 的 Program 值，检查查询使用它读取语句和函数字段。

先只看执行过程：compile 等待解析返回 Program P1，再把它交给程序检查；程序检查遍历语句，发起各函数的检查。下面的实线表示调用或读取，虚线表示解析结果返回。逐步推进，可以看到当前调用使用了什么数据：

解析完成后，需要分别保存查询的返回值和对象的内容。解析 memo 在 S1 的查询槽位中保存 Program P1；P1.statements 保存语句，其中的函数声明引用 Function F1；F1 自己保存 body 等字段。多参数的函数检查使用驻留后的参数组合 K1 保存 memo。

下面单独看存储布局：外框表示包含关系，引用按钮指向已经显示的目标对象。点击 P1、F1 或参数引用，会就地突出目标。对象的排列不表示调用先后或物理地址：

Program 值相等，只说明对象 ID 相同。语句列表仍可能改变；同一个 Function 的 body 也可能更新。如果运行时只比较对象 ID 而不跟踪字段，函数体变化就可能被遗漏。查询身份用来找到旧计算，字段依赖用来判断旧计算还能否使用，两者需要分别表示。

源码用 Id 定位对象，用 IngredientIndex 定位管理某类数据的 ingredient。DatabaseKeyIndex 将二者组合起来，表示一项具体的增量数据。下面沿这次调用中的四个定位动作展开：找到解析 memo、读取文本、找到函数检查 memo、读取函数体。每一步都将当前操作、key 的两部分和实际目标放在一起；推进时整条对应关系一起突出：

解析查询与文本字段即使使用同一个对象 ID，也因 ingredient 不同而指向不同数据。多个参数的查询先将组合驻留为一个数据对象，再使用该对象的 ID；不同的函数与程序组合因而可以分别保存结果。

字段 ingredient 保存读取和变化检查规则，函数 ingredient 则定位对应对象的 memo table，从这个函数的槽位中取得 Memo<C>：

#[repr(C)]
#[derive(Debug)]
pub struct Memo<C: Configuration> {
    /// Configuration-independent state used to validate and manage this memo.
    ///
    /// Must be at offset zero for [`ErasedMemo::header`].
    pub(super) header: MemoHeader,

    /// The result of the query, if we decide to memoize it.
    pub(super) value: Option<C::Output<'static>>,
}

value 是用户函数的返回值，header 是运行时判断这个值是否有效所需的记录。解析 memo 的 value 是 Program 值，并不包含一份独立的语句列表；语句列表仍在 Program 的对象字段中。

普通查询的验证记录主要包括：

查询返回值与验证记录分别保存在 value、header 中。代码通过 origin() 取得依赖来源；普通受跟踪查询对应 Derived(edges)，其中保存执行时记录的输入边和输出边。输入边记录本查询读取过的数据；普通输出边记录本查询通过 specify 为其他查询单元指定结果的关系，不表示当前 memo 的 value。Tracked 对象身份和 accumulator 诊断分别由对应的身份记录与累积记录管理，也不能与主返回值混为一体。后续验证会取出这些边，通过每条边的 DatabaseKeyIndex 找到对应的数据管理器，询问它是否发生变化。

返回值与验证记录分开保存，还有一个用途：运行时可以回收较大的返回值，保留其依赖和变化信息。Option 允许出现这种只有 header 的 memo。第三部分第 2 节再讨论回收；正常 fetch 要交出用户结果时，仍然需要一个有值的 memo。

内部的 Output<'static> 使用了生命周期擦除，取值时会恢复到 memo 的借用范围；公开返回的引用仍受数据库借用约束。替换 memo 后，运行时暂存仍可能被借用的旧记录，到下一次 revision 开始后再释放。

安装新记录时，参数 ID 选择数据对象，memo_ingredient_index 选择该对象内的查询槽位。新 memo 交给数据表；被替换的旧记录暂存到 deleted_entries，下一次修订开始、旧借用结束后才能释放：

fn insert_memo<'db>(
    &'db self,
    zalsa: &'db Zalsa,
    id: Id,
    mut memo: memo::Memo<C>,
    memo_ingredient_index: MemoIngredientIndex,
) -> &'db memo::Memo<C> {
    if let Some(tracked_struct_ids) = memo.header.revisions.tracked_struct_ids_mut() {
        tracked_struct_ids.shrink_to_fit();
    }

    // We convert to a `NonNull` here as soon as possible because we are going to alias
    // into the `Box`, which is a `noalias` type.
    // FIXME: Use `Box::into_non_null` once stable
    let memo = NonNull::from(Box::leak(Box::new(memo)));

    if let Some(old_value) =
        self.insert_memo_into_table_for(zalsa, id, memo, memo_ingredient_index)
    {
        // In case there is a reference to the old memo out there, we have to store it
        // in the deleted entries. This will get cleared when a new revision starts.
        //
        // SAFETY: Once the revision starts, there will be no outstanding borrows to the
        // memo contents, and so it will be safe to free.
        unsafe { self.deleted_entries.push(old_value) };
    }
    // SAFETY: memo has been inserted into the table
    unsafe { self.extend_memo_lifetime(memo.as_ref()) }
}

读取记录沿相反的路径，先定位对象的 memo table，再取出查询槽位。这里取得记录还不等于确认有效，fetch 仍要检查修订和结果值：

pub(super) fn get_memo_from_table_for<'db>(
    &self,
    zalsa: &'db Zalsa,
    id: Id,
    memo_ingredient_index: MemoIngredientIndex,
) -> Option<&'db Memo<C>> {
    let memo = zalsa
        .memo_table_for::<C::SalsaStruct<'_>>(id)
        .get(memo_ingredient_index)?;
    // SAFETY: The memo table owns this allocation for at least `'db`.
    Some(unsafe { memo.as_ref() })
}

验证通过后，运行时从记录取得主值的借用：

pub(super) fn value(&self) -> Option<&C::Output<'_>> {
    self.value.as_ref().map(|value| {
        // SAFETY: Guaranteed by `Configuration`; the restored lifetime is
        // bounded by the borrow of this memo.
        unsafe { std::mem::transmute::<&C::Output<'static>, &C::Output<'_>>(value) }
    })
}

这次生命周期恢复依赖 Configuration 与数据库的保存、回收协议；借用范围受当前 memo 的借用约束，不能把 transmute 单独理解成可以任意延长引用。

替换槽位中的指针，不代表可以立即释放旧 memo。下面的三个状态分别显示槽位所指向的记录和已有借用；最后一步要求旧借用结束，并取得新修订所需的独占访问：

flowchart TD
    A["替换前<br/>槽位 → 旧 memo<br/>已有借用 → 旧 memo"]
    A -->|安装新记录| B["替换后<br/>槽位 → 新 memo<br/>旧 memo 进入 deleted_entries<br/>已有借用仍 → 旧 memo"]
    B -->|旧借用结束 · 新修订独占边界| C["清理 deleted_entries<br/>释放旧 memo"]

中间状态允许读者继续使用已取得的旧记录；后续请求则从槽位读取新记录。第三部分会解释，多线程情况下输入写入怎样建立这个独占边界。

这些结构可以保存一次计算，却还没有说明 edges 从哪里来。首次执行时，运行时需要把解析和检查的实际读取，填入各自的查询记录。

3. 首次执行如何建立依赖

第一次请求 compile(source)，对应的 memo 尚不存在，运行时进入函数体。compile 请求 parse_statements(source)，解析查询又读取 source.text(db)。这次字段读取应该记录在解析查询名下：解析直接依赖文本，外层编译查询直接依赖解析结果。

Salsa 用活动查询栈区分当前执行的计算。执行路径在调用 C::execute 前压入 ActiveQuery，结束时取出完成记录。source.text(db) 的生成 getter 进入输入 ingredient 的 field：取得输入对象的字段值、对应字段的 durability 与 revision，再以文本字段的 ingredient 和 source ID 构造 key，调用 report_tracked_read_simple。

这项报告到达栈顶活动记录，最终进入 add_read_simple。嵌套调用中的读取因而归属当前最内层的查询：

ActiveQuery.input_outputs 是 FxIndexSet<QueryEdge>，同时收集输入与输出，去掉重复边并保留首次出现的顺序。字段读取还报告 durability 和最近写入的 revision，这些元数据与依赖边一起进入活动记录：

pub(super) fn add_read_simple(
    &mut self,
    input: DatabaseKeyIndex,
    durability: Durability,
    revision: Revision,
) {
    self.durability = self.durability.min(durability);
    self.add_changed_at(revision);

    if cfg!(feature = "persistence") || durability != Durability::NEVER_CHANGE {
        self.input_outputs.insert(QueryEdge::input(input));
    }
}

input 是刚才读到的字段 key。方法将 durability 取低值，用 add_changed_at 汇总读取中的最大变化标记，再加入输入边。本例的输入采用通常的 LOW 等级，会保存依赖边；NEVER_CHANGE 数据在部分配置下可以省略这条边。

解析器随后构造 Program、Function 等对象，返回 Program 值。执行收尾时，QueryCompletion::finish 保持边的原有顺序，依据是否发生未跟踪读取构造依赖来源，再把它与其他修订信息组成 CompletedQuery：

pub(crate) fn finish(
    self,
    input_outputs: &mut FxIndexSet<QueryEdge>,
) -> CompletedQuery {
    let edges = input_outputs.iter().copied();
    let origin_and_extra = if self.untracked_read {
        OriginAndExtra::derived_untracked(edges, self.extra)
    } else {
        OriginAndExtra::derived(edges, self.extra)
    };
    input_outputs.clear();
    CompletedQuery {
        revisions: QueryRevisions {
            changed_at: self.changed_at,
            durability: self.durability,
            origin_and_extra,
            #[cfg(feature = "accumulator")]
            accumulated_inputs: self.accumulated_inputs,
            verified_final: AtomicBool::new(self.verified_final),
        },
        stale_tracked_structs: self.stale_tracked_structs,
    }
}

finish 把边的来源写入 origin_and_extra，把 durability 与变化标记一同保存为 QueryRevisions；执行收尾再将返回值和这份记录安装为 memo。当前 revision 成为 verified_at：运行时已经在这一修订下取得了有效结果。派生对象的身份记录也随创建查询保存，重新解析时会用到它；第二部分第 7 节再看其匹配规则。

解析完成后，fetch 在将值交给 compile 之前调用 report_tracked_read。此时解析帧已经弹出，栈顶恢复为 compile，所以编译查询记录的是解析查询的 key、durability 和 changed_at，不复制解析的全部内部读取。

compile 接着调用 type_check_program。这个查询读取 program.statements(db)，并对函数声明发起独立的检查：

#[salsa::tracked(returns(copy))]
pub fn type_check_function<'db>(
    db: &'db dyn crate::Db,
    function: Function<'db>,
    program: Program<'db>,
) {
    CheckExpression::new(db, program, function.args(db)).check(function.body(db))
}

参数 function 只说明检查哪个对象；实际调用 args(db)、body(db) 才形成字段依赖。CheckExpression::check 是普通递归辅助方法，它继续读取受跟踪数据时，读取仍然属于当前的 type_check_function。不需要把每一步表达式遍历都变成查询。

在 quadruple 中，两次 double(...) 都通过 find_function(program, name) 查找同一个名称。第二次可以命中已有查询缓存，但 fetch 仍然报告读取，让函数检查保留对这个查找结果的依赖。集合会将重复 key 合为一条边；缓存命中可以省略子函数执行，不能省略父查询的依赖记录。

名称查找也是单独的查询，完整实现如下：

#[salsa::tracked(returns(copy))]
pub fn find_function<'db>(
    db: &'db dyn crate::Db,
    program: Program<'db>,
    name: FunctionId<'db>,
) -> Option<Function<'db>> {
    program
        .statements(db)
        .iter()
        .flat_map(|s| match &s.data {
            StatementData::Function(f) if f.name(db) == name => Some(*f),
            _ => None,
        })
        .next()
}

find_function 自己读取 Program.statements，再读取候选函数的 name，返回匹配的 Function 值。它没有读取 double.body。因此，quadruple 检查对名称查找的依赖，并不会自动变成对被调用函数体的依赖；修改后怎样验证这条关系，要继续看这些实际读取是否变化。

首次分析完成后，记录之间的关系如下。表中只列出与后续修改有关的主线输入，省略名称驻留等附加依赖和输出记录：

double 的检查发现 b 未声明，读取相关 Span.start、Span.end 生成错误位置，再将诊断累积到该查询的受管理输出中。位置读取也进入依赖记录。主值仍然是 ()，所以后续比较这个值，并不能判断诊断有没有变化。应用通过 accumulator 接口收集诊断时，使用的是查询保存的这类辅助输出。

这样，一次完整分析保存的不只是一组返回值。每份 memo 还说明了返回值依赖什么；创建查询保存派生对象身份，产生诊断的查询保存诊断。输入改动之后，这些记录各自参与验证和更新。

依赖也不是固定的。查询重新执行时会重新收集本轮输入；如果条件改变后读取了另一分支，新 memo 应当记录新分支。读取顺序同样有用途：旧条件已经失效时，验证不必继续检查后来读取的旧分支。接下来把 double 的函数体改为 a * 2，观察输入写入怎样触发对这些记录的检查。

逐步执行这段程序，观察读取进入哪个活动查询，以及子查询返回后留下哪些直接依赖：

4. 输入修改如何进入增量计算

首次请求完成后，数据库中已经有解析查询的 memo、解析产生的对象，以及类型检查查询的依赖记录。现在修复 double 中没有声明的变量，将函数体从 a * b 改成 a * 2，quadruple 的声明和表达式保持原样。

这次修改涉及的完整输入如下。double 原来使用了未声明的变量 b，检查得到一条诊断；将它改成数字 2 后，这条诊断消失。quadruple 的两次函数调用和最后的打印语句都没有改变。

fn double(a) = a * b
fn quadruple(a) = double(double(a))
print quadruple(2)

fn double(a) = a * 2
fn quadruple(a) = double(double(a))
print quadruple(2)

需要解释的是：解析必须重新执行，为什么 quadruple 的检查还能复用；double 的检查已经执行，为什么外层主值仍可能被判定为没有变化。下面沿写入、验证和重新执行逐步回答。

应用通过同一个输入对象的 setter 写入修改后的完整文本：

source_program
    .set_text(&mut db)
    .to(new_source_text.to_string());

SourceProgram 的身份没有因这次 setter 调用而改变，但它的文本值改变了。旧解析 memo 仍然能由同一个查询 key 找到；是否能够继续使用，则取决于文本的变化记录。

4.1 写入边界与 revision

Setter 要求 &mut Db。这使输入更新发生在查询计算之外；底层取得共享存储的独占访问后，才能修改字段。多个数据库实例如何结束旧计算并交出存储，在第三部分第 1 节继续解释。

生成的 setter 通过 Configuration::ingredient_mut 取得输入 ingredient 和 Runtime。这个适配器先调用 new_revision：

pub fn ingredient_mut(
    zalsa_mut: &mut $zalsa::Zalsa,
) -> (
    &mut $zalsa_struct::IngredientImpl<Self>,
    &mut $zalsa::Runtime,
) {
    zalsa_mut.new_revision();
    let index = zalsa_mut
        .lookup_jar_by_type::<$zalsa_struct::JarImpl<$Configuration>>();
    let (ingredient, runtime) = zalsa_mut.lookup_ingredient_mut(index);
    let ingredient = ingredient
        .assert_type_mut::<$zalsa_struct::IngredientImpl<Self>>();
    (ingredient, runtime)
}

ingredient_mut 将更新入口与修订推进放在一起。new_revision 将 Runtime 的当前修订推进到下一个序号，并执行需要在新修订开始时进行的维护。Revision 表示更新顺序，供后续比较一次变化发生在验证之前还是之后。

之后，input::set_field 更新文本字段的写入标记，处理 durability，再修改字段值：

pub fn set_field<R>(
    &mut self,
    runtime: &mut Runtime,
    id: C::Struct,
    field_index: usize,
    durability: Option<Durability>,
    setter: impl FnOnce(&mut C::Fields) -> R,
) -> R {
    let id: Id = id.as_id();

    let data_raw = Self::data_raw(runtime.table(), id);

    // SAFETY: We hold `&mut` on the runtime so no `&`-references can be active.
    // Also, we don't access any other data from the table while `r` is active.
    let data = unsafe { &mut *data_raw };

    assert_ne!(
        data.durabilities[field_index],
        Durability::NEVER_CHANGE,
        "never-changing inputs cannot be mutated"
    );

    data.revisions[field_index] = runtime.current_revision();

    let field_durability = &mut data.durabilities[field_index];
    if *field_durability != Durability::MIN {
        runtime.report_tracked_write(*field_durability);
    }
    *field_durability = durability.unwrap_or(*field_durability);

    setter(&mut data.fields)
}

data.fields 保存值，data.revisions 按字段保存最近写入的修订。durability 写入报告使用字段原来的等级，再采用 setter 指定的新等级，确保原先按旧等级验证的消费者也能发现这次写入。NEVER_CHANGE 字段在此前会被拒绝修改。

把首次查询完成的修订记作 R_old，这次写入后的修订记作 R_new。setter 刚完成时，核心记录的关系如下：

这张表表示写入与查询之间的状态关系，省略了具体 ID 和附加字段。setter 只更新输入，运行时没有立即执行全部消费者。应用再次请求 compile 时，才需要验证当前请求会使用的旧记录。

4.2 字段写入与结果变化

输入字段的 ingredient 用最近写入的修订回答变化检查：

unsafe fn maybe_changed_after(
    &self,
    zalsa: &Zalsa,
    _db: crate::database::RawDatabase<'_>,
    input: Id,
    revision: Revision,
) -> VerifyResult {
    let value = <IngredientImpl<C>>::data(zalsa, input);
    VerifyResult::changed_if(value.revisions[self.field_index] > revision)
}

传入的 revision 是消费者的验证基准，self.field_index 选择正在验证的具体字段。解析查询曾读取 SourceProgram.text，而文本的 R_new 写入发生在它上次验证之后，所以这个字段会报告变化。

这层记录只判断字段是否被写入，不比较文本的新旧内容。再次写入同一份文本也会推进 revision，更新字段标记；解析查询可能因此执行，之后才能比较新旧解析结果。应用已经知道文本相同时，可以在调用 setter 之前省去冗余写入。

字段之间的变化标记各自保存。一个输入对象若还有未被某项查询读取的字段，修改该字段不会改变已读字段的标记。对于这次 calc 修改，解析查询读到的是整个文本字段，所以必须处理这次写入；函数之间能否分别复用，要等解析重建字段之后再判断。

5. 如何证明旧结果仍然有效

应用再次调用 compile(db, source_program)，入口找到的是原来的查询 key。此时旧 memo 还在，但它只在 R_old 下确认过有效。运行时需要检查旧依赖在新修订中是否仍能支持这份结果。

compile 上次执行时先读取解析结果，再调用类型检查。这两个查询分别保存了自己的依赖：解析依赖文本，类型检查依赖 Program.statements 和各项子检查，函数检查继续依赖自己读取的字段。因此，验证 compile 并不要求先执行它的函数体；运行时可以先沿这些旧记录检查。

5.1 fetch 与浅验证

fetch 的职责是取得有效的返回值。它调用 refresh_memo，先尝试 fetch_hot，再按需进入 fetch_cold。热路径要求 memo 存在且 value 没有被淘汰，并尝试只使用 header 中的修订信息完成验证。

Header 的两个修订字段承担不同职责：

shallow_verify_memo 先比较 verified_at 与当前 revision。同一修订内已经验证过的普通最终结果，可以继续复用。跨修订时，运行时再检查 durability：若对应等级的 last_changed_revision 没有超过旧 verified_at，就能排除该查询所读输入发生相关写入。

Durability 的依据来自第二部分第 3 节的活动查询记录：查询取所读依赖中的最低等级。Runtime 为各等级维护保守的写入上界；HIGH 写入会更新 HIGH 及更低等级的上界，LOW 写入不会更新 HIGH 的上界。一个只读 HIGH 数据的查询，在只有 LOW 数据被写入时可以免去逐边验证。HIGH 仍然允许修改，写入会使这项快捷判断失效。

本例文本使用通常的 LOW 等级。LOW 的上界是当前 revision，所以 R_new 的写入不能用等级信息直接排除，查询需要进入更具体的验证。

冷路径先取得这项 key 的处理权，再重新读取 memo。等待期间其他线程可能已经完成计算，因此取得处理权不等于必须执行函数。fetch_cold 的选择由旧 memo 是否有值、验证能否通过共同决定：

fn fetch_cold<'db>(
    &'db self,
    zalsa: &'db Zalsa,
    zalsa_local: &'db ZalsaLocal,
    db: &'db C::DbView,
    id: Id,
    memo_ingredient_index: MemoIngredientIndex,
) -> Option<&'db Memo<C>> {
    let database_key_index = self.database_key_index(id);
    // Try to claim this query: if someone else has claimed it already,
    // go back and start again.
    let claim_guard = match self
        .sync_table
        .try_claim(zalsa, zalsa_local, id, Reentrancy::Allow)
    {
        ClaimResult::Claimed(guard) => guard,
        ClaimResult::Running(blocked_on) => {
            let _ = blocked_on.block_on(zalsa);
            return None;
        }
        ClaimResult::Cycle { .. } => {
            return Some(self.fetch_cold_cycle(
                zalsa,
                zalsa_local,
                db,
                id,
                database_key_index,
                memo_ingredient_index,
            ));
        }
    };

    // Now that we've claimed the item, check again to see if there's a "hot" value.
    let opt_old_memo = self.get_memo_from_table_for(zalsa, id, memo_ingredient_index);

    if let Some(old_memo) = opt_old_memo
        && old_memo.value.is_some()
        && old_memo.header.verify_memo(
            db.into(),
            &claim_guard,
            C::CYCLE_STRATEGY,
            #[cfg(feature = "detailed-trace")]
            true,
        )
    {
        // SAFETY: memo is present in memo_map and we have verified that it is
        // still valid for the current revision.
        return unsafe { Some(self.extend_memo_lifetime(old_memo)) };
    }

    self.execute(db, claim_guard, opt_old_memo)
}

前面的 try_claim 分支处理执行权，后半段才判断能否复用旧 memo。只有旧值存在且验证通过，函数才提前返回它；否则最后调用 self.execute。结果被淘汰时，header 可能仍然有效，但 fetch 要交付实际值，仍需重建结果。仅查询“某项依赖是否变化”的接口可以采用另一条路径，第三部分第 2 节会说明它如何利用保留下来的 header。

5.2 深验证与实际消费者

MemoHeader::deep_verify_memo 先区分依赖来源。普通 Derived 记录通过检查后，读出父 memo 自己的旧 verified_at，将它作为验证基准；全部依赖未变时，才把父 memo 标记为当前修订有效：

fn deep_verify_memo(
    &self,
    db: crate::database::RawDatabase<'_>,
    claim_guard: &ClaimGuard<'_>,
    cycle_recovery_strategy: CycleRecoveryStrategy,
    #[cfg(feature = "detailed-trace")] has_value: bool,
) -> VerifyResult {
    let zalsa = claim_guard.zalsa();
    let database_key_index = claim_guard.database_key_index();

    match self.origin() {
        QueryOriginRef::Derived(edges) => {
            #[cfg(feature = "detailed-trace")]
            crate::tracing::debug!(
                "{database_key_index:?}: deep_verify_memo(old_memo = {old_memo:#?})",
                old_memo = self.tracing_debug(has_value)
            );

            let is_provisional = self.may_be_provisional();
            if is_provisional {
                return VerifyResult::changed();
            }
            if cycle_recovery_strategy == CycleRecoveryStrategy::Panic
                && self.was_cycle_participant()
            {
                return VerifyResult::changed();
            }

            let verified_at = self.verified_at.load();

            let result = deep_verify_edges(
                db,
                zalsa,
                &self.revisions,
                verified_at,
                edges,
                database_key_index,
            );

            if result.is_unchanged() {
                self.mark_as_verified(zalsa, database_key_index);
            }

            result
        }

        QueryOriginRef::Assigned(_) => {
            VerifyResult::changed()
        }
        QueryOriginRef::DerivedUntracked(_) => {
            VerifyResult::changed()
        }
    }
}

这里的 AtomicRevision 通过 load() 得到 Revision。验证比较的是父查询上次确认有效之后的变化，不能在遍历前就把它更新到当前修订。每条输入边通过自己的 DatabaseKeyIndex 找到 ingredient，调用变化检查：

fn deep_verify_edges(
    db: crate::database::RawDatabase,
    zalsa: &Zalsa,
    #[allow(unused)] old_revisions: &QueryRevisions,
    old_verified_at: Revision,
    edges: QueryEdges<'_>,
    database_key_index: DatabaseKeyIndex,
) -> VerifyResult {
    #[cfg(feature = "accumulator")]
    let mut inputs = InputAccumulatedValues::Empty;

    for edge in edges {
        match edge.kind() {
            QueryEdgeKind::Input => {
                let dependency_index = edge.key();
                let input_result = dependency_index.maybe_changed_after(
                    db, zalsa, old_verified_at,
                );

                match input_result {
                    VerifyResult::Changed => {
                        return VerifyResult::changed();
                    }
                    #[cfg(feature = "accumulator")]
                    VerifyResult::Unchanged { accumulated } => {
                        inputs |= accumulated;
                    }
                    #[cfg(not(feature = "accumulator"))]
                    VerifyResult::Unchanged { .. } => {}
                }
            }
            QueryEdgeKind::Output => {
                let dependency_index = edge.key();
                dependency_index.mark_validated_output(zalsa, database_key_index);
            }
        }
    }
    let result = VerifyResult::unchanged_with_accumulated(
        #[cfg(feature = "accumulator")]
        inputs,
    );

    #[cfg(feature = "accumulator")]
    old_revisions.accumulated_inputs.store(inputs);

    result
}

old_verified_at 是正在验证的父 memo 的旧基准。对于文本字段，检查直接比较字段标记；对于解析等子查询，检查可能先验证或执行子查询，取得它当前的变化结论。

旧边按照首次读取的顺序验证。一旦输入边报告变化，遍历立即结束，由查询重新执行并收集当前依赖。对动态分支而言，条件已经变化时，后来读取的旧分支不应继续作为当前计算的依据。遇到输出边时，运行时会及时将相应输出标记有效，因为后面的输入查询可能读取它。

下面把这条控制流程展开。箭头表示验证的推进顺序；只有输入边会要求依赖给出变化结论：

flowchart TD
    B["读旧 verified_at"] --> N["按原顺序取下一条旧边"]
    N --> K{"还有边？"}
    K -->|没有| R["更新 verified_at<br/>复用旧 memo"]
    K -->|有| T{"边的种类"}
    T -->|输出| O["标记输出有效"]
    O --> N
    T -->|输入| V["以旧基准验证输入"]
    V --> C{"依赖变化？"}
    C -->|没有| N
    C -->|有| E["立即结束旧边验证"]
    E --> X["重算父查询<br/>记录当前依赖"]

动态分支可以说明为什么输入变化后立即结束。假设旧执行先读取条件，再读取 A；条件的新值选择了 B，就应当重新执行、记录 B，不能继续验证旧 A 并把它当成本轮输入：

flowchart TD
    Old["旧 memo：先读条件，再读 A"] --> Check["首先验证条件"]
    Check --> Change["条件结果由 true 变为 false"]
    Change --> Stop["结束旧边验证，不再验证旧 A"]
    Stop --> Run["重新执行：读条件，再读 B"]
    Run --> New["新 memo：条件与 B 成为直接输入"]

全部依赖通过验证时，运行时把旧 memo 的 verified_at 更新到当前 revision，复用返回值和现有输入边。它没有执行该函数体，但可能已经验证甚至重算了内层查询。包含未跟踪读取的旧记录则不能凭这些边排除变化，深验证会保守报告变化。

对子查询的检查还需要等待它给出当前结论。maybe_changed_after 可以先验证或执行子查询，再将新 memo 的 changed_at 与父查询传入的旧基准比较。普通最终结果的标记没有超过基准，就返回 Unchanged；标记超过基准或结果仍可能临时，则报告变化。因此，依赖的函数执行过，父查询仍有可能通过验证。

fetch 实际将值交给正在执行的父查询时，还会报告读取，使父查询保留这条直接依赖。旧记录的验证与新执行中的依赖收集分别完成各自的工作。

回到这次 calc 请求，检查首先从 compile 的旧边进入解析查询，再进入文本字段。文本写入发生在旧基准之后，所以解析 memo 无法通过验证，需要重新计算。此时只能确定解析必须执行，外层的 compile 仍在等待解析查询的变化结论，不能直接判定所有检查都要重做。

解析完成以后，外层还需要验证类型检查查询。它记录的输入包括 Program.statements、函数检查和名称查找。double 的检查读取自己的 args、body；quadruple 的检查读取自己的字段，并通过 find_function 确认被调用的名称存在。后者没有读取 double.body。这些不同的读取，决定了后续验证需要分别检查什么。

如果重建对象能够沿用身份，旧字段和查询记录就仍然可以被定位；身份或某条实际依赖变化，则需要进一步处理。接下来先完成解析重算，查看新结果怎样得到变化标记，再继续这次尚未完成的外层验证。对象匹配的实现留到第二部分第 7 节展开。

6. 重算后怎样截断变化并发布结果

解析查询读过的文本已经写入，它需要执行用户函数。普通执行分支通过 push_query 创建活动记录，再将它和旧 header 交给第二部分第 1 节的 execute_query。

旧 header 可提供派生对象的身份记录，帮助解析器重建对象；本次输入依赖则由新的读取收集。用户函数返回后，活动帧弹出，QueryCompletion 将输入、输出边及修订信息组成完成记录。运行时此时同时拥有新返回值、当前执行记录和可用于比较的旧 memo。

活动记录先把所读依赖的 changed_at 取最大值，得到新结果的候选变化标记。对解析查询而言，新读取的文本携带这次写入的标记。候选值表示依赖中的变化，但函数输出仍需单独比较：如果解析成功匹配到同一个 Program，返回的 Program 值可能相等；如果重新执行类型检查，返回值则仍然是 ()。

这些相等各有范围。Program 值相等只表示解析返回相同对象 ID，不表示 double.body 没变；() 相等也不表示诊断没变。前者由字段依赖继续检查，后者由受管理的诊断记录另行维护。Salsa 可以保留某项主返回值的变化标记，同时更新本次执行产生的其他记录。

运行时通过 backdate_if_appropriate 比较新返回值与旧 memo 中的值：

pub(super) fn backdate_if_appropriate<'db>(
    &self,
    old_memo: &'db Memo<C>,
    index: DatabaseKeyIndex,
    revisions: &mut QueryRevisions,
    value: &C::Output<'db>,
) {
    if old_memo.header.can_backdate(revisions)
        && old_memo
            .value()
            .is_some_and(|old_value| C::values_equal(old_value, value))
    {
        old_memo.header.backdate(index, revisions);
    }
}

C::values_equal 来自查询配置，默认比较新旧返回值；no_eq 的比较恒为 false。比较需要旧 memo 中仍然有值。can_backdate 还要求新记录没有未处理的循环头、旧 memo 不是临时结果，并且新 durability 不低于旧 durability。依赖等级降低会影响消费者以后能否使用快速验证，所以不能仅凭返回值相等保留旧传播结论。

检查通过后，MemoHeader::backdate 将新记录的 revisions.changed_at 设为旧 header 的 self.revisions.changed_at。运行时保留的是旧结果向消费者报告的变化标记，数据库 revision 继续前进，新 memo 的 verified_at 仍然设为当前修订，本次执行收集的依赖也继续保存。

calc 的返回值涉及对象身份和辅助诊断。为了单独观察这项回填如何减少外层计算，下面使用一个只返回整数、布尔值和字符串的小例子。输入有文本和路径两个字段：

#[salsa::input]
struct Source {
    #[returns(deref)]
    text: String,
    path: String,
}

三个查询分别解析整数、判断奇偶性、生成报告；签名中的 Database 是 Salsa 的数据库接口：

#[salsa::tracked(returns(copy))]
fn parsed(db: &dyn Database, source: Source) -> i64 {
    source
        .text(db)
        .trim()
        .parse()
        .expect("demo input is an integer")
}

#[salsa::tracked(returns(copy))]
fn is_even(db: &dyn Database, source: Source) -> bool {
    parsed(db, source) % 2 == 0
}

#[salsa::tracked(returns(clone))]
fn report(db: &dyn Database, source: Source) -> String {
    if is_even(db, source) {
        "even"
    } else {
        "odd"
    }
    .to_owned()
}

这条链的直接依赖是 report → is_even → parsed → Source.text，没有查询读取 path。设文本为 "11"，首次请求完成所在的修订为 R1，普通 LOW 查询且 memo 值保留时，会形成以下记录：

表中用查询名称代指对应的 key；R1、R2 表示这个独立例子的相对修订。

文本写为 "13" 后记作 R2。再次请求报告，验证沿旧边找到文本字段的写入，解析查询重新计算出 13。整数改变，所以新解析 memo 的 verified_at 和 changed_at 都为 R2。

奇偶查询随后需要执行。它读取刚更新的解析 memo；缓存命中也会报告这次读取，在活动记录中加入指向 parsed 的边，并汇总 R2 的变化标记。新的布尔值仍然是 false，本例满足 backdating 条件，所以候选 changed_at = R2 被回填为 R1，新 memo 的 verified_at 则是 R2。

报告查询的旧验证基准是 R1，依赖的奇偶结果仍携带 R1 变化标记。它因此通过深验证，保留 "odd"，只把 verified_at 更新为 R2，不执行报告函数体。奇偶查询和报告查询最终都有 verified_at = R2、changed_at = R1，但前者执行并比较了结果，后者只完成验证。

继续写成 "14"，记作 R3，整数变为 14、布尔值变为 true、报告变为 "even"，三个返回值都变化，三个查询都执行。这一轮验证报告时使用的旧基准是 R2，而不是报告的旧 changed_at = R1：上一轮已经验证有效的记录，应从上次验证所在的修订检查后续变化。

改变输入，逐步观察验证、执行与传播停止的位置。点开节点可以对照值和修订标记：

回到 calc，解析结果的 Program 对象 ID 相同，可以保留解析查询的主值变化标记，但本次执行中的字段和输出仍要更新。完成这些维护并安装新 memo 之后，外层验证才能继续使用解析查询的当前记录。

6.1 新依赖、输出与 memo 发布

回填 changed_at 之后，运行时仍然使用本次执行的完成记录。查询若切换分支但仍返回同一个值，新的输入边必须指向本次实际读取的分支；否则，下一次修改新分支就会漏掉变化。结果相等允许保留变化标记，不允许继续使用失效的旧依赖。

本次执行产生的对象和普通输出也需要维护。execute 在 backdating 之后调用 diff_outputs：普通输出边取旧输出减去本次仍然产生的输出，将剩余部分报告为过期；tracked 对象使用另存的身份记录，完成记录中的 stale_tracked_structs 进入相应清理路径。这些对象不作为普通直接输出边保存。

对于 calc，解析器需要保存本轮再次产生的 Program、Function 等对象，并处理不再产生的旧对象。例如删除一个声明时，旧函数不能继续作为有效解析产物留下；第二部分第 7 节具体说明身份匹配、字段更新与清理的关系。

诊断也必须反映本轮检查的状态。修复 double 后，函数检查仍返回 ()，但旧的未声明变量诊断不能继续被应用收集。应用在 compile 后请求 compile::compile::accumulated::<Diagnostic>，会读取当前查询及相关子查询的诊断记录；它不是根据主返回值 () 是否相等决定诊断是否相同。前一个 compile 是模块名，后一个是查询名。Accumulator 的保存和收集协议在第三部分第 2.2 节展开。

收尾完成后，execute 调用 Memo::new，将当前值、当前 revision 和本次修订记录组合为新 memo，再由 insert_memo 安装到对应槽位。

Memo::new 以当前 revision 初始化 verified_at；completed_query.revisions 保存本次依赖、durability，以及可能回填过的 changed_at。insert_memo 替换对应槽位的记录，旧 memo 在仍可能被借用的期间暂存，直到后续修订安全地释放。

现在继续第二部分第 5 节暂停的外层验证。先沿用相关对象成功匹配、语句列表和 quadruple 所读字段与名称查找结果保持有效的情形：

外层函数体可以不执行，内层解析和 double 检查仍然完成了更新。复用的依据是每项查询自己的输入记录，更新的范围则包括主值、字段和辅助输出。对象匹配失败或其他读取变化时，上表对应的复用条件不再成立，运行时会按实际记录继续处理。

解析结果当前指向哪些对象，仍取决于重建期间的身份匹配。下一节继续检查解析器如何使用旧身份记录，以及何时需要新的 ID。

修复函数体和修改函数名称会影响不同的记录。下面对照两次修改中的对象身份、字段、检查与诊断：

7. 派生对象的身份与生命周期

修改输入之后，解析器再次调用 Program::new、Function::new，构造本轮的分析产物。前面的验证过程能否找到旧类型检查 memo，有一个前提：用于查询参数的对象能够保留原来的 ID。如果每次构造都分配新 ID，即使某个函数没有改变，它的类型检查也会成为另一个查询实例。

因此，重新解析需要做两件不同的工作：识别本轮对象对应上次的哪个对象，更新这些对象的字段。下面继续用 double 的修复，查看源码怎样完成这两件事。

Salsa 用三种数据模型处理不同来源的对象：

其中，tracked struct 需要同时保存对象的身份和属性；interned 则将完整内容作为去重依据。两者都使用对象 ID 定位数据库中的数据，但匹配对象的规则不同。

7.1 Tracked struct

calc 中的 Function 定义如下：

#[salsa::tracked(debug)]
pub struct Function<'db> {
    #[returns(copy)]
    pub name: FunctionId<'db>,

    #[returns(copy)]
    name_span: Span<'db>,

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

    #[tracked]
    pub body: Expression<'db>,
}

未标记 #[tracked] 的字段参与身份匹配，因此这里的身份字段是 name 和 name_span；args 与 body 是 tracked 属性，可以在对象继续使用原 ID 时更新。returns(copy)、returns(deref) 控制 getter 的返回方式，与字段是否参与身份无关。

#[salsa::tracked(debug)]
pub struct Span<'db> {
    #[tracked]
    #[returns(copy)]
    pub start: usize,
    #[tracked]
    #[returns(copy)]
    pub end: usize,
}

这里的 Span 也值得展开：它的 start、end 都是 tracked 属性，没有身份字段。同一创建查询中的 Span 按出现序号匹配，所以位置坐标可以更新，Span 对象标识仍然延续。名称位置的坐标变化因此不等于 name_span 这个身份字段一定变化；但创建顺序改变可能影响匹配。

类型检查查询取得 Function 对象标识后，读取 args 和 body，形成对这些字段的依赖。解析器下一次执行时，如果匹配到原来的函数对象，就可以保留对象标识、更新函数体。类型检查查询仍然能通过原对象标识定位到旧 memo，但对 body 的验证会发现内容变化，进而执行新的检查。对象匹配与字段依赖分别完成了查询定位和内容验证。

Tracked 对象由查询创建，匹配范围也限定在创建它的查询实例内。首次解析创建的 double、quadruple，各自的身份记录保存在解析 memo 中。再次执行同一个解析查询之前，旧记录被带入新的活动帧；解析器调用 Function::new 时，便可以尝试从这些记录中找到对应对象。输入依赖仍然由本轮读取重新收集，不是沿用上次的输入列表。

这组身份记录归创建查询所有。下图沿同一个解析 key 展示它如何延续到下一次执行，以及没有再次产生的对象怎样退出：

flowchart TD
    O["旧解析 memo<br/>保存 creator 的对象身份记录"] --> S["重新执行同一解析 key<br/>旧身份记录进入活动帧"]
    S --> N["Function::new<br/>类型 · 身份字段哈希 · 区分序号"]
    N --> M{"有旧身份记录<br/>且能够更新？"}
    M -->|是| U["复用匹配对象<br/>通常保留 ID · 更新属性"]
    M -->|否| A["分配新对象<br/>保存新身份记录"]
    U --> C["完成本轮对象产生集"]
    A --> C
    C --> D["旧对象本轮未再产生<br/>stale 清理相关数据"]

这里的身份 key 用于查找旧 ID；能否更新还要检查当前对象状态，slot 复用也可能产生新 generation。它不同于 Interned 对完整内容的相等比较。new_struct 的完整分支如下：

pub fn new_struct<'db>(
    &'db self,
    zalsa: &'db Zalsa,
    zalsa_local: &'db ZalsaLocal,
    mut fields: C::Fields<'db>,
) -> C::Struct<'db> {
    let identity_hash = IdentityHash {
        ingredient_index: self.ingredient_index,
        hash: crate::hash::hash(&C::untracked_fields(&fields)),
    };

    let (current_deps, disambiguator) = zalsa_local.disambiguate(identity_hash);

    let identity = Identity {
        hash: identity_hash.hash,
        ingredient_index: identity_hash.ingredient_index,
        disambiguator,
    };

    if let Some(id) = zalsa_local.tracked_struct_id(&identity) {
        // The struct already exists in the intern map.
        crate::tracing::trace!(
            "Reuse tracked struct {id:?}",
            id = self.database_key_index(id)
        );

        // SAFETY: The `id` was present in the interned map, so the value must be initialized.
        let update_result = unsafe { self.update(zalsa, id, &current_deps, fields) };

        fields = match update_result {
            // Overwrite the previous ID if we are reusing the old slot with new fields.
            Ok(updated_id) if updated_id != id => {
                zalsa_local.store_tracked_struct_id(identity, updated_id);
                return FromId::from_id(updated_id);
            }

            // The id has not changed.
            Ok(id) => return FromId::from_id(id),

            // Failed to perform the update, we are forced to allocate a new slot.
            Err(fields) => fields,
        };
    }

    // We failed to perform the update, or this is a new tracked struct, so allocate a new entry
    // in the struct map.
    let id = self.allocate(zalsa, zalsa_local, &current_deps, fields);
    crate::tracing::trace!(
        "Allocated new tracked struct {key:?}",
        key = self.database_key_index(id)
    );
    zalsa_local.store_tracked_struct_id(identity, id);
    FromId::from_id(id)
}

ingredient_index 区分 tracked struct 的类型，hash 来自未标记的身份字段，disambiguator 区分本次创建过程中同类哈希的多次出现。运行时用这组信息查找当前查询的身份记录，找到后尝试更新字段并复用 ID；没有匹配对象，或原存储位置不能更新时，才分配新的对象。

更新过程还会比较实际字段值。Tracked 属性只有在新旧值不等时才更新对应字段的变化标记；身份字段也会进行相等比较，避免将哈希碰撞当成同一对象。若匹配到的存储位置实际属于不同身份，运行时会清理旧 memo、递增 ID 的 generation，将其作为新的身份处理。

把这些规则应用到修复后的解析结果，可以看到身份与内容分别怎样参与后续计算。下表沿用相关对象成功匹配、原有声明结构和顺序保留的情形：

尤其需要注意 Program.statements：函数声明项保存的是 Function 对象标识，没有把 body 直接内嵌进向量。double.body 更新，并不自动改变语句列表的值。函数检查通过自己的字段依赖发现这项变化，而不是要求解析查询先返回一个不同的 Program ID。

quadruple 的检查虽然遇到对 double 的调用，当前检查器只通过 find_function 判断这个名称是否存在，不读取 double.body。只要它自己的字段和名称查找结果仍然有效，旧检查就可以复用。源程序中的调用关系和增量运行时中的读取关系，在这里有明确的区别。

对象没有匹配成功时，后续查询会使用新 ID，原查询的缓存就未必能继续定位。名称变化、创建顺序变化及身份字段的选择，都可能导致这种情况；不能仅凭函数文本看起来没改，断言其检查必然被跳过。匹配也限定在创建查询内，不会将不同查询产生的同内容对象自动合并。其他分析器需要根据声明所属模块、名称及重复声明等规则选择身份字段。

创建查询执行结束后，运行时区分本轮再次产生的对象和没有再次产生的旧对象。后者作为 stale output 被移除，并清理相关数据。例如，源文件中删除了一个函数，解析查询本轮不再创建它，对应的派生对象就会进入这条清理路径。

7.2 Interned

calc 的 FunctionId 保存名称文本。两处调用都写了 double，它们可以共用一份名称内容。这里的去重范围是同一个数据库中的 FunctionId interner；VariableId 有自己的 interner，不会因为文本相同就与 FunctionId 共用身份。

intern_id 先计算字段内容的哈希，再到相应分片查找。哈希用于选择候选，value_eq 仍要比较实际字段。对于只有 text 一个字段的 FunctionId，两次完整相等的 double 返回同一个 ID；twice 的内容不同，取得另一个身份。

flowchart TD
    A["第一次<br/>text = double"] --> Q
    B["第二次<br/>text = double"] --> Q
    C["新名称<br/>text = twice"] --> Q
    Q["FunctionId interner<br/>哈希定位 · 字段相等比较"]
    Q -->|double| D["Id A<br/>保存 double"]
    Q -->|twice| E["Id B<br/>保存 twice"]

如果 double 已经驻留，第二次调用直接返回已有 ID，不再保存另一份相同字符串。这个身份对应的字段不可修改；将名称改成 twice，需要驻留新的内容。

没有找到相等内容时，运行时可以分配新 slot，也可以复用过期 slot。后者只适用于启用回收、活跃修订记录已足够，且候选为 LOW durability 的情形。是否过期比较的是该 interner 记录的活跃修订窗口，不是数据库写入次数。当前修订已经验证的值不能复用，较高 durability 的值不进入候选 LRU。

flowchart TD
    N["新内容未命中"] --> C
    C{"有可复用候选？<br/>LOW · 已过期<br/>本修订未验证"}
    C -->|无| A["分配新 slot"]
    C -->|有| M["清理旧 memo<br/>移除旧内容索引"]
    M --> G["写入新内容<br/>generation：g → g+1"]
    G --> P["重新索引并发布<br/>新 Id：(slot, g+1)"]

运行时先清理旧 memo 和旧内容索引，再写入新字段，并以增加了 generation 的新 ID 建立索引。slot 相同，ID 也已经不同，旧身份不会被当成新内容。generation 无法继续增加的 slot 不再复用；若以后重新驻留旧内容，也不保证找回原 ID。

字段 getter 返回数据库借用期间的字段引用。运行时在暴露可复用值之前检查它已经在当前修订验证；验证会保护该 slot，使本修订中的后续驻留不能覆盖它。图中的 slot 表示存储槽位，不能据此推断精确地址或跨修订稳定的 ID。

不可变字段通常无需逐字段记录变化依赖；可回收的 interned 身份仍要参与依赖验证，防止缓存沿用已经被复用的旧身份。字段借用还受 'db 生命周期约束：借用正在使用时，外部不能取得可变数据库访问去修改输入。

经过这次修改，输入文本、派生对象字段、查询返回值和诊断已经分别更新；未受影响的查询则保留有效记录。实际运行还需要保证这些记录能够被多个请求共享，memo 替换不会破坏借用，输入写入也不会与旧修订的查询交错。接下来的工程实现围绕这些约束展开。

三、运行时设计与取舍

1. 并行查询与并发协调

多个请求可以在时间上重叠，称为并发；不同线程同时执行计算，则形成并行。Salsa 允许应用把数据库对象交给不同线程请求查询，协调这些请求使用的共享数据。一次普通查询调用不会自动把子查询分派给线程池：应用决定哪些工作并行、创建多少工作线程，Salsa 管理缓存、执行权和等待关系。

1.1 应用发起并行，数据库共享结果

数据库 clone 共享输入和 memo，每个实例又保留自己的活动查询栈。这样，线程 A 的解析读取不会被记到线程 B 的活动查询中：

flowchart TD
    A["线程 A · Db A"] -->|独有| LA["ZalsaLocal A<br/>活动栈 · 局部取消"]
    B["线程 B · Db B"] -->|独有| LB["ZalsaLocal B<br/>活动栈 · 局部取消"]
    A -->|Arc 共享| Z["同一个 Zalsa"]
    B -->|Arc 共享| Z
    Z --> I["Ingredients"]
    Z --> R["共享 Runtime"]
    R --> T["Table · memo<br/>修订信息 · 线程等待图"]

Storage::clone 没有复制整份缓存。共享持有的是 handle，新建的是局部执行状态：

impl<Db: Database> Clone for Storage<Db> {
    fn clone(&self) -> Self {
        Self {
            handle: self.handle.clone(),
            zalsa_local: ZalsaLocal::new(),
        }
    }
}

Database trait 要求 Send，数据库对象可以移交给另一线程。常规 Storage 含有 RefCell 等局部状态，并不是可直接让多个线程共用同一 &Db 的 Sync 对象；通常让各工作线程拥有自己的 clone。

下面是 tests/parallel/memo_table_first_insert.rs 的完整用例。两个查询种类不同，却读取同一个输入。A 先发送信号 1，然后等待 B 的信号 2；这要求 B 也进入函数体，才能让 A 继续。线程由测试中的 thread::spawn 创建：

use crate::sync::thread;
use crate::{Knobs, KnobsDatabase};

#[salsa::input]
struct Input {
    #[returns(copy)]
    value: u32,
}

#[salsa::tracked(returns(copy))]
fn query_a(db: &dyn KnobsDatabase, input: Input) -> u32 {
    db.signal(1);
    db.wait_for(2);
    input.value(db)
}

#[salsa::tracked(returns(copy))]
fn query_b(db: &dyn KnobsDatabase, input: Input) -> u32 {
    db.wait_for(1);
    db.signal(2);
    input.value(db)
}

#[test_log::test]
fn concurrent_first_insert() {
    crate::sync::check(|| {
        let db_a = Knobs::default();
        let input = Input::new(&db_a, 42);
        let db_b = db_a.clone();

        let a = thread::spawn(move || query_a(&db_a, input));
        let b = thread::spawn(move || query_b(&db_b, input));

        assert_eq!(a.join().unwrap(), 42);
        assert_eq!(b.join().unwrap(), 42);
    });
}

Knobs 是测试套件提供的数据库，signal、wait_for 用于控制交握；这段代码展示真实的并行调用方式，不能当作 calc 的现有多线程入口。两个独立断言要求结果都为 42，并不提供加速比。共享表、interner 等仍需要同步，不同 key 可以并行执行，也仍可能在这些资源上短暂竞争。

1.2 同一 key 的执行权与等待

两个线程也可能请求同一项计算。热路径已取得有效缓存时，可以直接返回；需要进入冷路径验证或执行时，SyncTable::try_claim 协调这个 key。Claimed 给当前线程一个 ClaimGuard；Running 表示已有处理者；Cycle 表示继续等待会形成循环。

同步表使用分片锁登记归属。普通 ClaimGuard 保存 key 和所属分片，不持有整段用户计算期间的分片锁，因此它不会把其他 key 的函数体全部串行化。下面只画同一普通 key 尚无有效结果、A 先认领且正常完成的情形：

sequenceDiagram
    participant A as 线程 A
    participant S as 共享 memo / 执行权
    participant B as 线程 B
    A->>S: 请求 Q · 取得 claim
    B->>S: 请求同一 Q
    S-->>B: 已有处理者 · 检查等待环
    Note over B: 登记等待 · 释放同步锁
    A->>A: 验证或执行查询
    A->>S: 确认旧 memo 有效 / 安装新 memo
    A->>S: 释放 claim · 通知等待者
    S-->>B: 等待结束
    B->>S: 返回 fetch 循环 · 重读并验证 memo
    S-->>B: 取得当前有效结果

等待结束后，fetch_cold 返回 None，外层请求循环重新探测共享 memo；取得 claim 的线程也会再次读取和验证 memo，因为其他线程可能在它取得处理权前更新过结果。等待通知不代替缓存验证，线程之间也没有直接传递用户返回值。

安装记录通过原子指针发布，旧 memo 进入前面介绍的暂存区，仍可被已有借用使用。ClaimGuard 用 RAII 释放执行权并通知等待者；owner panic 会传播失败，局部取消则允许等待者重新请求。循环处理中还可能移交 claim，因此“一项 key 永远只执行一次”并不是这里的保证。

1.3 等待环与查询循环

如果 A 持有查询 QA，等待 B 正在处理的 QB，而 B 又请求 QA，直接阻塞会使双方互相等待。Runtime 在新增等待边前，检查对方是否已经沿等待路径依赖当前线程：

flowchart TD
    A["线程 A<br/>正在处理 QA"] -->|请求 QB · 等待 B| B["线程 B<br/>正在处理 QB"]
    B -.->|请求 QA · 将要等待 A| A
    B --> C["Runtime 检查反向路径<br/>发现等待环"]
    C --> D["返回 Cycle<br/>按查询配置处理"]

这两条边表示线程等待，区别于 memo 中“查询读取哪些输入”的依赖边。完整的 Runtime::block 在同线程重入或发现反向路径时返回 Cycle；无环时返回用于后续登记和阻塞的 Running：

    pub(crate) fn block<'a>(
        &'a self,
        database_key: DatabaseKeyIndex,
        other_id: ThreadId,
        query_mutex_guard: SyncGuard<'a>,
    ) -> BlockResult<'a> {
        let thread_id = thread::current().id();
        // Cycle in the same thread.
        if thread_id == other_id {
            return BlockResult::Cycle;
        }

        let dg = self.dependency_graph.lock();

        if dg.depends_on(other_id, thread_id) {
            crate::tracing::debug!(
                "block_on: cycle detected for {database_key:?} in thread {thread_id:?} on {other_id:?}"
            );
            return BlockResult::Cycle;
        }

        BlockResult::Running(Running(Box::new(BlockedOnInner {
            dg,
            query_mutex_guard,
            database_key,
            other_id,
            thread_id,
        })))
    }

普通查询默认对循环 panic；只有显式配置了 fallback 或固定点规则，才进入对应恢复过程。跨线程固定点还可能转移查询的处理归属，让参与者继续协同迭代。发现环本身不意味着业务结果已经收敛；第 2.3 节再看 provisional 怎样成为 final。

1.4 输入写入与协作取消

输入 setter 要求 &mut Db，但它只独占当前数据库实例，其他 clone 仍然持有共享存储和旧修订的借用。写入必须先结束这些访问，再推进修订：

sequenceDiagram
    participant W as 写入线程
    participant S as 共享 Storage
    participant R as 其他工作线程
    W->>S: setter 进入 zalsa_mut
    S->>S: 设置 pending write
    Note over W,S: 等待其他 handle 全部释放
    R->>S: 到达取消检查点
    S-->>R: PendingWrite · unwind
    R->>R: 清理活动帧和执行权
    R->>S: 应用释放数据库 handle
    S-->>W: clone 数量为 1
    W->>S: 取得独占 Zalsa
    W->>S: 推进 revision · 写入字段

图中的工作线程主动到达检查点，运行时并不在任意指令处抢占线程。查询入口会检查取消；长时间只做本地运算的循环，可以调用 db.unwind_if_revision_cancelled() 及时响应。应用还要结束这些工作并释放各自数据库对象：查询已经返回，或只保留一个空闲 clone，仍然不足以让写入者取得独占访问。

cancel_others 等待的是共享 handle 数量。取消标记由 guard 管理；其他 handle 全部 drop 后退出等待，才可通过 Arc::get_mut 取得唯一可变访问。普通 setter 随后进入新修订并更新字段：

    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"
        );
        {
            let _cancellation_flag = CancellationFlagGuard::new(&self.handle.zalsa_impl);

            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();
        // Increment the cancellation count only after cancelled workers have dropped their
        // handles. Otherwise, a worker unwinding from cancellation could insert a provisional
        // memo with the new cancellation count.
        let overflow = zalsa.runtime_mut().bump_cancellation_count();
        if overflow {
            zalsa.new_revision();
        }
        zalsa
    }

这里不能在查询体内部调用独占取消路径，否则会等到自己仍持有的执行状态，形成死锁。独立的 CancellationToken 只取消某个 ZalsaLocal，与 setter 所需的全局取消、全部 handle 释放和写入边界不同。检查点的间隔、应用结束工作及释放 clone 的时机，共同影响写入等待时间。

2. 缓存、辅助输出与循环

前面使用的查询都有完整缓存值，返回值也已经确定。Salsa 还支持回收缓存中的大对象、保存查询产生的诊断，以及处理带有业务恢复规则的循环。这些功能分别改变结果的存储形式、输出形式和有效状态。

2.1 LRU

LRU 用于限制某个查询保留的结果值数量。例如，中间查询返回一个大对象，上层只从中得到一个小结果；大对象近期没有直接被请求，上层结果却仍然留在缓存中。这时可以回收中间结果值，同时保留上层验证它所需的信息。

Memo 将主返回值 value 与 header 分开保存。LRU 的实际淘汰操作如下：

pub(super) fn evict_value_from_memo_for(
    table: MemoTableWithTypesMut<'_>,
    memo_ingredient_index: MemoIngredientIndex,
) {
    let map = |memo: &mut Memo<C>| {
        if memo.header.can_evict_value() {
            // Set the memo value to `None`.
            memo.value = None;
        }
    };

    table.map_memo(memo_ingredient_index, map)
}

它只清除结果值，header 中的依赖、变化标记和验证信息仍然存在。上层通过 maybe_changed_after 验证中间查询时，如果依赖没有变化，就能继续复用上层 memo，无需重建已被回收的大对象。应用真正请求中间结果时，fetch 发现 value 缺失，才需要重新执行该查询。

同一个只有 header 的 memo，在两种请求下有不同用途。左侧的验证只需要知道是否变化；右侧的直接请求必须交出实际结果值：

flowchart TD
    A["中间查询 memo<br/>header · Some 大值"] -->|LRU 淘汰主值| B["header 保留<br/>value = None"]
    B --> V["上层 maybe_changed_after<br/>只验证变化"]
    B --> F["应用 fetch 中间查询<br/>需要实际值"]
    V -->|依赖仍有效| U["复用上层结果<br/>无需重建中间大值"]
    F --> R["值缺失<br/>执行查询 · 重建大值"]

这个操作只适用于可重建的查询结果。来源为普通 Derived 的 memo 可以淘汰值，其他查询指定的输出或带 untracked inputs 的结果不能按同一方式处理。LRU 超限处理在新修订开始等时机执行，配置的容量也只针对相关结果值，不是整个数据库的严格内存上限。

2.2 Accumulator

calc 的类型检查查询返回 ()，检查过程中发现的错误则通过 Diagnostic accumulator 收集。查询调用 Diagnostic.accumulate(db) 时，诊断归属于当前活动查询；应用通过 compile::compile::accumulated::<Diagnostic> 取得该查询及其相关子查询的诊断。

这类输出不能用主返回值的相等判断代替。下面的例子中，File.content 是文件的文本输入，Log 是累积错误的类型，LogDatabase 是查询使用的数据库接口。解析查询返回一个整数，解析失败时同时产生一条错误：

#[salsa::tracked(returns(copy))]
fn parse(db: &dyn LogDatabase, input: File) -> u32 {
    let value: Result<u32, _> = input.content(db).parse();

    match value {
        Ok(value) => value,
        Err(error) => {
            Log(error.to_string()).accumulate(db);
            0
        }
    }
}

输入为 "0" 时，主值是 0，没有诊断；改为 "a" 后，主值仍是 0，却多了一条解析错误。主返回值可以被 backdate，诊断仍然需要反映这次执行的新状态。

accumulated API 先 fetch 主查询，确保它的状态已更新，再沿当前 memo 依赖图遍历，收集各查询保存的累积值。遍历按查询 key 去重，所以同一个子查询被多次依赖，不会因此重复收集；两个不同查询产生相同错误文本，仍然可以得到两条诊断。收集顺序来自查询依赖与各查询保存的累积值，而不是全局日志的实时发生顺序。

pub fn accumulated_by<'db, A>(&self, db: &'db C::DbView, key: Id) -> Vec<&'db A>
where
    A: accumulator::Accumulator,
{
    let (zalsa, zalsa_local) = db.zalsas();

    zalsa_local.report_untracked_read(zalsa.current_revision());

    let Some(accumulator) = <accumulator::IngredientImpl<A>>::from_zalsa(zalsa) else {
        return vec![];
    };
    let mut output = vec![];

    self.fetch(db, zalsa, zalsa_local, key);

    let db_key = self.database_key_index(key);
    let mut visited: FxHashSet<DatabaseKeyIndex> = FxHashSet::default();
    let mut stack: Vec<DatabaseKeyIndex> = vec![db_key];

    while let Some(k) = stack.pop() {
        let ingredient = zalsa.lookup_ingredient(k.ingredient_index());

        let Some(function) = ingredient.as_function() else {
            continue;
        };

        if !visited.insert(k) {
            continue;
        }

        let (accumulated_map, input) =
            unsafe { ingredient.accumulated(db.into(), k.key_index()) };
        if let Some(accumulated_map) = accumulated_map {
            accumulated_map.extend_with_accumulated(accumulator.index(), &mut output);
        }
        if input.is_empty() {
            continue;
        }

        let Some(origin) = function
            .memo(zalsa, k.key_index())
            .map(|memo| memo.header().origin())
        else {
            continue;
        };

        if let QueryOriginRef::Derived(edges) | QueryOriginRef::DerivedUntracked(edges) = origin
        {
            stack.reserve(edges.len());
        }

        stack.extend(origin.inputs().rev().filter(|input| {
            zalsa
                .lookup_ingredient(input.ingredient_index())
                .as_function()
                .is_some()
        }));

        visited.reserve(stack.len());
    }

    output
}