处理循环

默认情况下，当 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 的查询在参与循环时也会使用它们的回退值。这是为了确保查询结果不依赖于查询的执行顺序（详情）。