Jars and ingredients

⚠️ IN-PROGRESS VERSION OF SALSA. ⚠️

This page describes the unreleased "Salsa 2022" version, which is a major departure from older versions of salsa. The code here works but is only available on github and from the salsa-2022 crate.

This page covers how data is organized in salsa and how links between salsa items (e.g., dependency tracking) works.

Salsa items and ingredients

A salsa item is some item annotated with a salsa annotation that can be included in a jar. For example, a tracked function is a salsa item:


#![allow(unused)]
fn main() {
#[salsa::tracked]
fn foo(db: &dyn Db, input: MyInput) { }
}

...and so is a salsa input...


#![allow(unused)]
fn main() {
#[salsa::input]
struct MyInput { }
}

...or a tracked struct:


#![allow(unused)]
fn main() {
#[salsa::tracked]
struct MyStruct { }
}

Each salsa item needs certain bits of data at runtime to operate. These bits of data are called ingredients. Most salsa items generate a single ingredient, but sometimes they make more than one. For example, a tracked function generates a FunctionIngredient. A tracked struct however generates several ingredients, one for the struct itself (a TrackedStructIngredient, and one FunctionIngredient for each value field.

Ingredients define the core logic of salsa

Most of the interesting salsa code lives in these ingredients. For example, when you create a new tracked struct, the method TrackedStruct::new_struct is invoked; it is responsible for determining the tracked struct's id. Similarly, when you call a tracked function, that is translated into a call to TrackedFunction::fetch, which decides whether there is a valid memoized value to return, or whether the function must be executed.

Ingredient interfaces are not stable or subject to semver

Interfaces are not meant to be directly used by salsa users. The salsa macros generate code that invokes the ingredients. The APIs may change in arbitrary ways across salsa versions, as the macros are kept in sync.

The Ingredient trait

Each ingredient implements the Ingredient<DB> trait, which defines generic operations supported by any kind of ingredient. For example, the method maybe_changed_after can be used to check whether some particular piece of data stored in the ingredient may have changed since a given revision:

We'll see below that each database DB is able to take an IngredientIndex and use that to get a &dyn Ingredient<DB> for the corresponding ingredient. This allows the database to perform generic operations on a numbered ingredient without knowing exactly what the type of that ingredient is.

Jars are a collection of ingredients

When you declare a salsa jar, you list out each of the salsa items that are included in that jar:

#[salsa::jar]
struct Jar(
    foo,
    MyInput,
    MyStruct
);

This expands to a struct like so:


#![allow(unused)]
fn main() {
struct Jar(
    <foo as IngredientsFor>::Ingredient,
    <MyInput as IngredientsFor>::Ingredient,
    <MyStruct as IngredientsFor>::Ingredient,
)
}

The IngredientsFor trait is used to define the ingredients needed by some salsa item, such as the tracked function foo or the tracked struct MyInput. Each salsa item defines a type I, so that <I as IngredientsFor>::Ingredient gives the ingredients needed by I.

Database is a tuple of jars

Salsa's database storage ultimately boils down to a tuple of jar structs, where each jar struct (as we just saw) itself contains the ingredients for the salsa items within that jar. The database can thus be thought of as a list of ingredients, although that list is organized into a 2-level hierarchy.

The reason for this 2-level hierarchy is that it permits separate compilation and privacy. The crate that lists the jars doens't have to know the contents of the jar to embed the jar struct in the database. And some of the types that appear in the jar may be private to another struct.

The HasJars trait and the Jars type

Each salsa database implements the HasJars trait, generated by the salsa::db procedural macro. The HarJars trait, among other things, defines a Jars associated type that maps to a tuple of the jars in the trait.

For example, given a database like this...

#[salsa::db(Jar1, ..., JarN)]
struct MyDatabase {
    storage: salsa::Storage<Self>
}

...the salsa::db macro would generate a HasJars impl that (among other things) contains type Jars = (Jar1, ..., JarN):

        impl salsa::storage::HasJars for #db {
            type Jars = (#(#jar_paths,)*);

In turn, the salsa::Storage<DB> type ultimately contains a struct Shared that embeds DB::Jars, thus embedding all the data for each jar.

Ingredient indices

During initialization, each ingredient in the database is assigned a unique index called the IngredientIndex. This is a 32-bit number that identifies a particular ingredient from a particular jar.

Routes

In addition to an index, each ingredient in the database also has a corresponding route. A route is a closure that, given a reference to the DB::Jars tuple, returns a &dyn Ingredient<DB> reference. The route table allows us to go from the IngredientIndex for a particular ingredient to its &dyn Ingredient<DB> trait object. The route table is created while the database is being initialized, as described shortly.

Database keys and dependency keys

A DatabaseKeyIndex identifies a specific value stored in some specific ingredient. It combines an IngredientIndex with a key_index, which is a salsa::Id:

/// An "active" database key index represents a database key index
/// that is actively executing. In that case, the `key_index` cannot be
/// None.
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct DatabaseKeyIndex {
    pub(crate) ingredient_index: IngredientIndex,
    pub(crate) key_index: Id,
}

A DependencyIndex is similar, but the key_index is optional. This is used when we sometimes wish to refer to the ingredient as a whole, and not any specific value within the ingredient.

These kinds of indices are used to store connetions between ingredients. For example, each memoized value has to track its inputs. Those inputs are stored as dependency indices. We can then do things like ask, "did this input change since revision R?" by

  • using the ingredient index to find the route and get a &dyn Ingredient<DB>
  • and then invoking the maybe_changed_since method on that trait object.

HasJarsDyn

There is one catch in the above setup. We need the database to be dyn-safe, and we also need to be able to define the database trait and so forth without knowing the final database type to enable separate compilation. Traits like Ingredient<DB> require knowing the full DB type. If we had one function ingredient directly invoke a method on Ingredient<DB>, that would imply that it has to be fully generic and only instantiated at the final crate, when the full database type is available.

We solve this via the HasJarsDyn trait. The HasJarsDyn trait exports method that combine the "find ingredient, invoking method" steps into one method:

/// Dyn friendly subset of HasJars
pub trait HasJarsDyn {
    fn runtime(&self) -> &Runtime;

    fn maybe_changed_after(&self, input: DependencyIndex, revision: Revision) -> bool;

    fn cycle_recovery_strategy(&self, input: IngredientIndex) -> CycleRecoveryStrategy;

    fn origin(&self, input: DatabaseKeyIndex) -> Option<QueryOrigin>;

    fn mark_validated_output(&self, executor: DatabaseKeyIndex, output: DependencyIndex);

    /// Invoked when `executor` used to output `stale_output` but no longer does.
    /// This method routes that into a call to the [`remove_stale_output`](`crate::ingredient::Ingredient::remove_stale_output`)
    /// method on the ingredient for `stale_output`.
    fn remove_stale_output(&self, executor: DatabaseKeyIndex, stale_output: DependencyIndex);

    /// Informs `ingredient` that the salsa struct with id `id` has been deleted.
    /// This means that `id` will not be used in this revision and hence
    /// any memoized values keyed by that struct can be discarded.
    ///
    /// In order to receive this callback, `ingredient` must have registered itself
    /// as a dependent function using
    /// [`SalsaStructInDb::register_dependent_fn`](`crate::salsa_struct::SalsaStructInDb::register_dependent_fn`).
    fn salsa_struct_deleted(&self, ingredient: IngredientIndex, id: Id);
}

So, technically, to check if an input has changed, an ingredient:

  • Invokes HasJarsDyn::maybe_changed_after on the dyn Database
  • The impl for this method (generated by #[salsa::db]):
    • gets the route for the ingredient from the ingredient index
    • uses the route to get a &dyn Ingredient
    • invokes maybe_changed_after on that ingredient

Initializing the database

The last thing to dicsuss is how the database is initialized. The Default implementation for Storage<DB> does the work:

impl<DB> Default for Storage<DB>
where
    DB: HasJars,
{
    fn default() -> Self {
        let mut routes = Routes::new();
        let jars = DB::create_jars(&mut routes);
        Self {
            shared: Arc::new(Shared {
                jars,
                cvar: Default::default(),
            }),
            routes: Arc::new(routes),
            runtime: Runtime::default(),
        }
    }
}

First, it creates an empty Routes instance. Then it invokes the DB::create_jars method. The implementation of this method is defined by the #[salsa::db] macro; it simply invokes the Jar::create_jar method on each of the jars:

            fn create_jars(routes: &mut salsa::routes::Routes<Self>) -> Self::Jars {
                (
                    (
                        <#jar_paths as salsa::jar::Jar>::create_jar(routes),
                    )*
                )
            }

This implementation for create_jar is geneated by the #[salsa::jar] macro, and simply walks over the representative type for each salsa item and ask it to create its ingredients

    quote! {
        impl<'salsa_db> salsa::jar::Jar<'salsa_db> for #jar_struct {
            type DynDb = dyn #jar_trait + 'salsa_db;

            fn create_jar<DB>(routes: &mut salsa::routes::Routes<DB>) -> Self
            where
                DB: salsa::storage::JarFromJars<Self> + salsa::storage::DbWithJar<Self>,
            {
                (
                    let #field_var_names = <#field_tys as salsa::storage::IngredientsFor>::create_ingredients(routes);
                )*
                Self(#(#field_var_names),*)
            }
        }
    }

The code to create the ingredients for any particular item is generated by their associated macros (e.g., #[salsa::tracked], #[salsa::input]), but it always follows a particular structure. To create an ingredient, we first invoke Routes::push which creates the routes to that ingredient and assigns it an IngredientIndex. We can then invoke (e.g.) FunctionIngredient::new to create the structure. The routes to an ingredient are defined as closures that, given the DB::Jars, can find the data for a particular ingredient.