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 ValueStruct<C>
where
    C: Configuration,
{
    /// Index of the struct ingredient.
    struct_ingredient_index: IngredientIndex,

    /// The id of this struct in the ingredient.
    id: Id,

    /// The key used to create the id.
    key: KeyStruct,

    /// 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 entity was most recently created.
    /// Typically the current revision.
    /// Used to detect "leaks" outside of the salsa system -- i.e.,
    /// access to tracked structs that have not (yet?) been created in the
    /// current revision. This should be impossible within salsa queries
    /// but it can happen through "leaks" like thread-local data or storing
    /// values outside of the root salsa query.
    created_at: 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,
}

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 {
    /// A (possibly empty) tuple of the fields for this struct.
    type Fields<'db>;

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

    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).
    ///
    /// # Safety
    ///
    /// Requires that `ptr` represents a "confirmed" value in this revision,
    /// which means that it will remain valid and immutable for the remainder of this
    /// revision, represented by the lifetime `'db`.
    unsafe fn struct_from_raw<'db>(ptr: NonNull<ValueStruct<Self>>) -> Self::Struct<'db>;

    /// Deref the struct to yield the underlying value struct.
    /// Since we are still part of the `'db` lifetime in which the struct was created,
    /// this deref is safe, and the value-struct fields are immutable and verified.
    fn deref_struct(s: Self::Struct<'_>) -> &ValueStruct<Self>;

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

    /// Access the revision of a given value field.
    /// `field_index` will be between 0 and the number of value fields.
    fn revision(revisions: &Self::Revisions, field_index: u32) -> Revision;

    /// 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>,
    );
}