Salsa Concepts: Queries, Databases, and Query Groups

It's helpful to think about this as a graph with nodes. Each derived value has a dependency on other values, which could themselves be either base or derived. Base values don't have a dependency. ```ignore I <- A <- C ... | J <- B <--+ ``` When an input `I` changes, the derived value `A` could change. The derived value `B`, which does not depend on `I`, `A`, or any value derived from `A` or `I`, is not subject to change. Therefore, Salsa can reuse the computation done for `B` in the past, without having to compute it again. The computation could also terminate early. Keeping the same graph as before, say that input `I` has changed in some way (and input `J` hasn't), but when computing `A` again, it's found that `A` hasn't changed from the previous computation. This leads to an "early termination", because there's no need to check if `C` needs to change, since both `C` direct inputs, `A` and `B`, haven't changed. ## Key Salsa concepts ### Query A query is some value that Salsa can access in the course of computation. Each query can have a number of keys (from 0 to many), and all queries have a result, akin to functions. `0-key` queries are called "input" queries. ### Database The database is basically the context for the entire computation, it's meant to store Salsa's internal state, all intermediate values for each query, and anything else that the computation might need. The database must know all the queries the library is going to do before it can be built, but they don't need to be specified in the same place. After the database is formed, it can be accessed with queries that are very similar to functions. Since each query's result is stored in the database, when a query is invoked `N`-times, it will return `N`-**cloned** results, without having to recompute the query (unless the input has changed in such a way that it warrants recomputation). For each input query (`0-key`), a "set" method is generated, allowing the user to change the output of such query, and trigger previous memoized values to be potentially invalidated. ### Query Groups A query group is a set of queries which have been defined together as a unit. The database is formed by combining query groups. Query groups are akin to "Salsa modules". A set of queries in a query group are just a set of methods in a trait. To create a query group a trait annotated with a specific attribute (`#[salsa::query_group(...)]`) has to be created. An argument must also be provided to said attribute as it will be used by Salsa to create a `struct` to be used later when the database is created. Example input query group: ```rust,ignore /// This attribute will process this tree, produce this tree as output, and produce /// a bunch of intermediate stuff that Salsa also uses. One of these things is a /// "StorageStruct", whose name we have specified in the attribute. /// /// This query group is a bunch of **input** queries, that do not rely on any /// derived input.

This section explains key Salsa concepts: Queries (values accessed during computation with keys and results), Databases (contexts storing internal state and intermediate values), and Query Groups (sets of queries defined as a unit, like Salsa modules). Queries function similarly to functions, returning cloned results from the database unless recomputation is needed. Input queries have "set" methods for changing outputs and triggering invalidation. Query groups are defined using a trait annotated with `#[salsa::query_group(...)]`.