salsa-rs/salsa

A query function is a user-provided function executed by Salsa to compute the value of a [derived query].

When writing query functions, keep the following assumptions in mind:

• Purity: Salsa assumes all query functions are 'pure' functions of their dependencies. If a function relies on state not tracked by Salsa, you must explicitly report an [untracked read].
• Side-effects: Salsa assumes functions have no important side-effects (e.g., sending network messages where the result must be observed).
• Re-execution: Because of these assumptions, Salsa only re-executes functions when it needs their return value and their dependencies have changed.

Salsa uses the "red-green" algorithm to manage incremental computation. The database tracks a single revision number that increments every time an input is set.

When a #[salsa::tracked] function is invoked, Salsa tracks its dependencies and the revisions in which those dependencies last changed. If a function is called again in a newer revision, Salsa checks if any inputs have changed. If they have, the function re-executes; otherwise, it returns a cached value.

Backdating is an optimization where, if a tracked function's inputs change but its output remains identical (e.g., adding a comment to source code that doesn't change the AST), Salsa "backdates" the result to avoid unnecessary re-computation of downstream dependencies.

In Salsa, backdating is a mechanism used to optimize incremental computation. It occurs when a value computed in a specific revision $R$ is marked as having last changed in an earlier revision.

This happens when Salsa compares an existing memo $M$ with a new computation. If the dependencies of $M$ have changed, but the result of the query function remains identical to the previous value, Salsa 'backdates' the change to the earlier revision where the value actually became stable. This prevents unnecessary downstream invalidations of functions that depend on this value.

In Salsa, a memo is considered verified in a specific revision $R$ if the system has confirmed that its value is still up-to-date. This means that re-executing the associated query function is guaranteed to produce the same result.

To optimize performance, each memo tracks the revision in which it was last verified. This allows Salsa to skip redundant checks during fetch and maybe changed after operations by determining if dependencies have changed since the last verification.

A derived query is a query whose value is determined by the result of a user-provided query function.

Key characteristics:

• The query function is executed to compute the result.
• Unlike input queries, the results of derived queries can always be recomputed by re-executing the associated query function whenever needed.

To build a database with Salsa, you embed the salsa::Storage struct into your application. The Storage struct is composed of two primary components:

1. The Query Store: This is the generated storage struct specific to your database definition.
2. The salsa::Runtime: This manages query coordination and tracking.

By combining these, Storage acts as the central container for both your data and the metadata required to track dependencies.

Salsa operates by defining a program as a set of queries. A query acts as a function mapping a key of type K to a value of type V. There are two primary types of queries:

• Inputs: These are the base inputs to your system. They can be changed at any time.
• Functions: These are pure functions (no side effects) that transform inputs into other values. Results are memoized, and Salsa intelligently recomputes only what is necessary when inputs change.

Salsa uses the fetch operation to compute query values, prioritizing the reuse of memoized results. There are three primary types of queries that determine how values are retrieved or computed:

1. Input queries: These are the simplest form of query; they directly load a result from a table.
2. Interned queries: These map an input to a hashmap to find an existing integer identifier. If the input is not found, a new integer is created.
3. Derived queries: These involve complex logic where a value is computed based on other dependencies. Salsa optimizes these by checking if existing memoized values are still valid based on dependency changes and durability checks.

In Salsa, a memo is a data structure that tracks the execution state of a [query function] for a specific [query] Q. It is used to optimize performance by avoiding redundant computations.

A memo typically stores:

• The returned value from the query function (though some queries may not cache values, or values may be dropped due to [LRU] collection).
• The revision in which the memo was last [verified].
• The changed at revision (the revision when the memo's value last changed, which may be [backdated]).
• The minimum durability of the memo's [dependencies].
• The complete set of [dependencies], or a marker indicating an [untracked dependency].

Even when a memo does not store a result value, it remains useful for tracking [dependency] information to determine if dependent queries need to be re-executed.