Tracked structs

Tracked structs are stored in a special way to reduce their costs.

Tracked structs are created via a new operation.

The tracked struct and tracked field ingredients

For a single tracked struct we create multiple ingredients. The tracked struct ingredient is the ingredient created first. It creates new instances of the struct and assigns their ids. The corresponding ValueStruct data is stored in Salsa's paged table.

For each #[tracked] field, we create a tracked field ingredient that moderates access to a particular field. All of these ingredients use the same paged table to access the ValueStruct instance for a given id. The ValueStruct contains both the field values but also the revisions when they last changed value.

Each tracked struct has an id

This begins by creating a database-local salsa::Id for the tracked struct. The ID contains a table index and a generation used when slots are reused. Its identity is derived from a combination of

the currently executing query;
a u64 hash of the fields not marked #[tracked];
a disambiguator that makes this hash unique within the current query. i.e., when a query starts executing, it creates an empty map, and the first time a tracked struct with a given hash is created, it gets disambiguator 0. The next one will be given 1, etc.

Each tracked struct has a `ValueStruct` storing its data

The struct and field ingredients use the paged table to find the value struct for a given id:

pub struct Value<C>
where
    C: Configuration,
{
    /// The revision when this tracked struct was last updated.
    /// This field also acts as a kind of "lock" over the `value` field. Once it is equal
    /// to `Some(current_revision)`, the fields are locked and
    /// cannot change further. This makes it safe to give out `&`-references
    /// so long as they do not live longer than the current revision
    /// (which is assured by tying their lifetime to the lifetime of an `&`-ref
    /// to the database).
    ///
    /// The struct is updated from an older revision `R0` to the current revision `R1`
    /// when the struct is first accessed in `R1`, whether that be because the original
    /// query re-created the struct (i.e., by user calling `Struct::new`) or because
    /// the struct was read from. (Structs may not be recreated in the new revision if
    /// the inputs to the query have not changed.)
    ///
    /// When re-creating the struct, the field is temporarily set to `None`.
    /// This is signal that there is an active `&mut` modifying the other fields:
    /// even reading from those fields in that situation would create UB.
    /// This `None` value should never be observable by users unless they have
    /// leaked a reference across threads somehow.
    updated_at: OptionalAtomicRevision,

    /// The durability minimum durability of all inputs consumed
    /// by the creator query prior to creating this tracked struct.
    /// If any of those inputs changes, then the creator query may
    /// create this struct with different values.
    durability: Durability,

    /// The revision information for each field: when did this field last change.
    /// When tracked structs are re-created, this revision may be updated to the
    /// current revision if the value is different.
    revisions: C::Revisions,

    /// Fields of this tracked struct. They can change across revisions,
    /// but they do not change within a particular revision.
    ///
    /// TODO: Consider whether we need a more explicit aliasing barrier or whether
    /// this should be restructured (e.g., with a nested struct for `fields` + `memos`)
    /// to make the aliasing guarantees more obvious. See PR #741 for prior discussion.
    fields: C::Fields<'static>,

    /// Memo table storing the results of query functions etc.
    /*unsafe */
    memos: MemoTable,
}

The value struct stores the values of the fields but also the revisions when that field last changed. Each time the struct is recreated in a new revision, the old and new values for its fields are compared and changed field revisions are updated.

The macro generates the tracked struct `Configuration`

The "configuration" for a tracked struct defines not only the types of the fields, but also various important operations such as extracting the hashable id fields and updating the "revisions" to track when a field last changed:

/// Trait that defines the key properties of a tracked struct.
///
/// Implemented by the `#[salsa::tracked]` macro when applied
/// to a struct.
///
/// # Safety
///
/// For every lifetime `'db`, `Fields<'db>` must be safe for Salsa to retain
/// as `Fields<'static>` and later expose with the lifetime of a database
/// borrow. Both types must have identical layouts and validity invariants.
pub unsafe trait Configuration: Sized + 'static {
    const LOCATION: crate::ingredient::Location;

    /// The debug name of the tracked struct.
    const DEBUG_NAME: &'static str;

    /// The debug names of any tracked fields.
    const TRACKED_FIELD_NAMES: &'static [&'static str];

    /// The relative indices of any tracked fields.
    const TRACKED_FIELD_INDICES: &'static [usize];

    /// Whether this struct should be persisted with the database.
    const PERSIST: bool;

    /// A (possibly empty) tuple of the fields for this struct.
    type Fields<'db>: Send + Sync;

    /// A array of [`AtomicRevision`][] values, one per each of the tracked value fields.
    /// When a struct is re-recreated in a new revision, the corresponding
    /// entries for each field are updated to the new revision if their
    /// values have changed (or if the field is marked as `#[no_eq]`).
    #[cfg(feature = "persistence")]
    type Revisions: Send
        + Sync
        + Index<usize, Output = AtomicRevision>
        + plumbing::serde::Serialize
        + for<'de> plumbing::serde::Deserialize<'de>;

    #[cfg(not(feature = "persistence"))]
    type Revisions: Send + Sync + Index<usize, Output = AtomicRevision>;

    type Struct<'db>: Copy + FromId + AsId;

    fn untracked_fields(fields: &Self::Fields<'_>) -> impl Hash;

    /// Create a new value revision array where each element is set to `current_revision`.
    fn new_revisions(current_revision: Revision) -> Self::Revisions;

    /// Update the field data and, if the value has changed,
    /// the appropriate entry in the `revisions` array (tracked fields only).
    ///
    /// Returns `true` if any identity field changed and the struct should be
    /// considered re-created.
    ///
    fn update_fields<'db>(
        current_revision: Revision,
        revisions: &Self::Revisions,
        old_fields: &mut Self::Fields<'db>,
        new_fields: Self::Fields<'db>,
    ) -> bool;

    /// Returns the size of any heap allocations in the output value, in bytes.
    fn heap_size(_value: &Self::Fields<'_>) -> Option<usize> {
        None
    }

    /// Serialize the fields using `serde`.
    ///
    /// Panics if the value is not persistable, i.e. `Configuration::PERSIST` is `false`.
    fn serialize<S>(value: &Self::Fields<'_>, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: plumbing::serde::Serializer;

    /// Deserialize the fields using `serde`.
    ///
    /// Panics if the value is not persistable, i.e. `Configuration::PERSIST` is `false`.
    fn deserialize<'de, D>(deserializer: D) -> Result<Self::Fields<'static>, D::Error>
    where
        D: plumbing::serde::Deserializer<'de>;
}

Salsa

Tracked structs

The tracked struct and tracked field ingredients

Each tracked struct has an id

Each tracked struct has a ValueStruct storing its data

The macro generates the tracked struct Configuration

Each tracked struct has a `ValueStruct` storing its data

The macro generates the tracked struct `Configuration`