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 TrackedStructValue 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 TrackedStructValue instance for a given id. The TrackedStructValue 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 TrackedStructValue storing its data

The struct and field ingredients share access to a hashmap that maps each field id to a value struct:

#[derive(Debug)]
struct TrackedStructValue<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 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,

    /// 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 {
    /// The id type used to define instances of this struct.
    /// The [`TrackedStructIngredient`][] contains the interner
    /// that will create the id values.
    type Id: InternedId;

    /// A (possibly empty) tuple of the fields for this struct.
    type Fields;

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

    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 an existing value revision array `revisions`,
    /// given the tuple of the old values (`old_value`)
    /// and the tuple of the values (`new_value`).
    /// If a value has changed, then its element is
    /// updated to `current_revision`.
    fn update_revisions(
        current_revision: Revision,
        old_value: &Self::Fields,
        new_value: &Self::Fields,
        revisions: &mut Self::Revisions,
    );
}