The "red-green" algorithm

This page explains the basic salsa incremental algorithm. The algorithm is called the "red-green" algorithm, which is where the name salsa comes from.

Database revisions

The salsa database always tracks a single revision. Each time you set an input, the revision is incremented. So we start in revision R1, but when a set method is called, we will go to R2, then R3, and so on. For each input, we also track the revision in which it was last changed.

Basic rule: when inputs change, re-execute!

When you invoke a tracked function, in addition to storing the value that was returned, we also track what other tracked functions it depends on, and the revisions when their value last changed. When you invoke the function again, if the database is in a new revision, then we check whether any of the inputs to this function have changed in that new revision. If not, we can just return our cached value. But if the inputs have changed (or may have changed), we will re-execute the function to find the most up-to-date answer.

Here is a simple example, where the parse_module function invokes the module_text function:

#![allow(unused)]
fn main() {
#[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(ref)]
fn module_text(db: &dyn Db, module: Module) -> String {
    panic!("text for module `{module:?}` not set")
}
}

If we invoke parse_module twice, but change the module text in between, then we will have to re-execute parse_module:

#![allow(unused)]
fn main() {
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!
}

Backdating: sometimes we can be smarter

Often, though, tracked functions don't depend directly on the inputs. Instead, they'll depend on some other tracked function. For example, perhaps we have a type_check function that reads the AST:

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

If the module text is changed, we saw that we have to re-execute parse_module, but there are many changes to the source text that still produce the same AST. For example, suppose we simply add a comment? In that case, if type_check is called again, we will:

• First re-execute parse_module, since its input changed.
• We will then compare the resulting AST. If it's the same as last time, we can backdate the result, meaning that we say that, even though the inputs changed, the output didn't.

Durability: an optimization

As an optimization, salsa includes the concept of durability. When you set the value of a tracked function, you can also set it with a given durability:

#![allow(unused)]
fn main() {
module_text::set_with_durability(
    db,
    module,
    "fn foo() { }".to_string(),
    salsa::Durability::HIGH
);
}

For each durability, we track the revision in which some input with that durability changed. If a tracked function depends (transitively) only on high durability inputs, and you change a low durability input, then we can very easily determine that the tracked function result is still valid, avoiding the need to traverse the input edges one by one.

An example: if compiling a Rust program, you might mark the inputs from crates.io as high durability inputs, since they are unlikely to change. The current workspace could be marked as low durability.