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

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)， 它放在结构体字段上时含义也基本相同。）