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 offers methods to create new instances of the struct and therefore has unique access to the interner and hashtables used to create the struct id. It also shares access to a hashtable that stores the ValueStruct that contains the field data.

For each field, we create a tracked field ingredient that moderates access to a particular field. All of these ingredients use that same shared hashtable 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 a globally unique id

This will begin by creating a globally unique, 32-bit id for the tracked struct. It is created by interning a combination of

the currently executing query;
a u64 hash of the #[id] fields;
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 share access to a hashmap that maps each field id to a value struct:

#[derive(Debug)]
pub struct Value<C>
where
    C: Configuration,
{
    /// 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 when this tracked struct was last updated.
    /// This field also acts as a kind of "lock". 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: AtomicCell<Option<Revision>>,

    /// Fields of this tracked struct. They can change across revisions,
    /// but they do not change within a particular revision.
    fields: C::Fields<'static>,

    /// 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,

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

    /// Sync table storing the results of query functions etc.
    syncs: SyncTable,
}

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 a new revision is created.

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.
pub trait Configuration: Sized + 'static {
    const DEBUG_NAME: &'static str;
    const FIELD_DEBUG_NAMES: &'static [&'static str];

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

    /// A array of [`Revision`][] values, one per each of the 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]`).
    type Revisions: Send + Sync + DerefMut<Target = [Revision]>;

    type Struct<'db>: Copy;

    /// Create an end-user struct from the underlying raw pointer.
    ///
    /// This call is an "end-step" to the tracked struct lookup/creation
    /// process in a given revision: it occurs only when the struct is newly
    /// created or, if a struct is being reused, after we have updated its
    /// fields (or confirmed it is green and no updates are required).
    fn struct_from_id<'db>(id: Id) -> Self::Struct<'db>;

    /// Deref the struct to yield the underlying id.
    fn deref_struct(s: Self::Struct<'_>) -> Id;

    fn id_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.
    ///
    /// # Safety
    ///
    /// Requires the same conditions as the `maybe_update`
    /// method on [the `Update` trait](`crate::update::Update`).
    ///
    /// In short, requires that `old_fields` be a pointer into
    /// storage from a previous revision.
    /// It must meet its validity invariant.
    /// Owned content must meet safety invariant.
    /// `*mut` here is not strictly needed;
    /// it is used to signal that the content
    /// is not guaranteed to recursively meet
    /// its safety invariant and
    /// hence this must be dereferenced with caution.
    ///
    /// Ensures that `old_fields` is fully updated and valid
    /// after it returns and that `revisions` has been updated
    /// for any field that changed.
    unsafe fn update_fields<'db>(
        current_revision: Revision,
        revisions: &mut Self::Revisions,
        old_fields: *mut Self::Fields<'db>,
        new_fields: Self::Fields<'db>,
    );
}

Salsa

Tracked structs

The tracked struct and tracked field ingredients

Each tracked struct has a globally unique 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`