# How Salsa works
<!-- toc -->
This chapter is based on the explanation given by Niko Matsakis in this
[video](https://www.youtube.com/watch?v=_muY4HjSqVw) about
[Salsa](https://github.com/salsa-rs/salsa). To find out more you may
want to watch [Salsa In More
Depth](https://www.youtube.com/watch?v=i_IhACacPRY), also by Niko
Matsakis.
> As of <!-- date-check --> November 2022, although Salsa is inspired by (among
> other things) rustc's query system, it is not used directly in rustc. It
> _is_ used in [chalk], an implementation of Rust's trait system, and
> extensively in [`rust-analyzer`], the official implementation of the language
> server protocol for Rust, but there are no medium or long-term concrete
> plans to integrate it into the compiler.
## What is Salsa?
Salsa is a library for incremental recomputation. This means it allows reusing
computations that were already done in the past to increase the efficiency
of future computations.
The objectives of Salsa are:
* Provide that functionality in an automatic way, so reusing old computations
is done automatically by the library.
* Doing so in a "sound", or "correct", way, therefore leading to the same
results as if it had been done from scratch.
Salsa's actual model is much richer, allowing many kinds of inputs and many different outputs.
For example, integrating Salsa with an IDE could mean that
the inputs could be manifests (`Cargo.toml`, `rust-toolchain.toml`), entire
source files (`foo.rs`), snippets and so on. The outputs of such an integration
could range from a binary executable, to lints, types (for example, if a user
selects a certain variable and wishes to see its type), completions, etc.
## How does it work?
The first thing that Salsa has to do is identify the "base inputs" that
are not something computed but given as input.
Then Salsa has to also identify intermediate, "derived" values, which are
something that the library produces, but, for each derived value there's a
"pure" function that computes the derived value.
For example, there might be a function `ast(x: Path) -> AST`. The produced
Abstract Syntax Tree (`AST`) isn't a final value, it's an intermediate value
that the library would use for the computation.
This means that when you try to compute with the library, Salsa is going to
compute various derived values, and eventually read the input and produce the
result for the asked computation.
In the course of computing, Salsa tracks which inputs were accessed and which
values are derived. This information is used to determine what's going to
happen when the inputs change: are the derived values still valid?
This doesn't necessarily mean that each computation downstream from the input
is going to be checked, which could be costly. Salsa only needs to check each
downstream computation until it finds one that isn't changed. At that point, it
won't check other derived computations since they wouldn't need to change.
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