The Mun backend makes extensive use of
Salsa to perform on-demand, incremental
salsa lets you define your program as a set of queries. Every
query is used like a function
K -> V that maps from some key
K to a value of
V. Changing the input
K also invalidates the result of computing
K -> V.
However, if the result
V does not change after changing
K the invalidation
is not propagated to computations that use
V as an input. This enables Mun to
cache a lot of computations between compilations, enabling
very fast rebuilding on incremental changes.
Queries are grouped together in so-called databases defined as traits. Database traits can have super traits that enable them to build upon other queries.
This design is heavily inspired by Rust Analyzer.
SourceDatabase provides queries and inputs that form the basis of all
compilation because it contains the original source text.
SourceRoots which are groupings of files.
SourceRoots define the hierarchy of files relative to a certain root. For the
system it's not interesting where the files come from and how they are actually
organized on disk.
SourceRoots provide an abstraction over the filesystem that
provides just enough information for the backend to function.
Another relevant query is the
line_index query which provides line and column
information for characters in a source file. This is used for instance when
emitting human-readable diagnostic messages with line and column numbers.
AstDatabase provides syntax tree transformations on top of the source
parse function returns the
Concrete Syntax Tree (CST)
of a file provided by the
mun_syntax crate. Any errors related to parsing are
stored in the tree itself.
As an example of where Salsa helps Mun achieve faster incremental compilation:
changing a single character in a file will also change the CST which in turn
will invalidate a lot of computations. However, most changes occur within blocks
(like functions or structs). To not invalidate everything in the changed file,
another query transforms the CST to an
AstIdMap which assigns ids to all
top-level items in a file. This enables referring to those ids in later stages of compilation which will change much less often.
InternDatase links certain locations in the syntax tree to ids. For
instance, it associates a function syntax node with a
FunctionId. This id
is then used everywhere in code to refer to the specific function instance. The
same happens for other items like structs. The purpose of this interning is
again to allow better incremental compilation for queries that only need to
refer to certain constructs without having to refer to the volatile syntax tree
DefDatabase provides definitions extracted from the syntax trees. It
provides desugared or lowered versions of language constructs that enable other
queries to query specific information for these constructs. Extracting this data
again enables faster incremental compilation because if the extracted data does
not change dependent queries also will not change.
HirDatabase resolves all types and names from the definitions. It also
performs type inferencing. The resulting High-Level Representation (HIR) is the
input for the LLVM Intermediate Representation (LLVM IR). The HIR data
structures can also contain errors, but only if there are no errors present will
generating IR be valid.
CodeGenDatabase provides queries to construct assemblies from
groups of files. Assemblies are the final product of the Mun compiler. They are
the binaries that can be executed by the runtime. This stage is where Salsa
really shines; only if something actually changed in the HIR will an assembly be
The language server uses the same backend as the compiler. Whereas the compiler
creates assemblies the language server queries the different databases to
provide a user with code intelligence. It also uses the exact same diagnostics
paths as the compiler, which means there is never a mismatch between the
compiler and the language server - and vice versa. If compiling your code results in an error it will also be immediately visible in your IDE.