mirror of
https://github.com/salsa-rs/salsa.git
synced 2025-02-02 09:46:06 +00:00
497 lines
35 KiB
HTML
497 lines
35 KiB
HTML
<!DOCTYPE HTML>
|
|
<html lang="en" class="sidebar-visible no-js light">
|
|
<head>
|
|
<!-- Book generated using mdBook -->
|
|
<meta charset="UTF-8">
|
|
<title>Overview - Salsa</title>
|
|
|
|
|
|
<!-- Custom HTML head -->
|
|
|
|
|
|
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
|
|
<meta name="description" content="">
|
|
<meta name="viewport" content="width=device-width, initial-scale=1">
|
|
<meta name="theme-color" content="#ffffff" />
|
|
|
|
<link rel="icon" href="favicon.svg">
|
|
<link rel="shortcut icon" href="favicon.png">
|
|
<link rel="stylesheet" href="css/variables.css">
|
|
<link rel="stylesheet" href="css/general.css">
|
|
<link rel="stylesheet" href="css/chrome.css">
|
|
<link rel="stylesheet" href="css/print.css" media="print">
|
|
|
|
<!-- Fonts -->
|
|
<link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
|
|
<link rel="stylesheet" href="fonts/fonts.css">
|
|
|
|
<!-- Highlight.js Stylesheets -->
|
|
<link rel="stylesheet" href="highlight.css">
|
|
<link rel="stylesheet" href="tomorrow-night.css">
|
|
<link rel="stylesheet" href="ayu-highlight.css">
|
|
|
|
<!-- Custom theme stylesheets -->
|
|
<link rel="stylesheet" href="mermaid.css">
|
|
|
|
</head>
|
|
<body>
|
|
<!-- Provide site root to javascript -->
|
|
<script type="text/javascript">
|
|
var path_to_root = "";
|
|
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
|
|
</script>
|
|
|
|
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
|
<script type="text/javascript">
|
|
try {
|
|
var theme = localStorage.getItem('mdbook-theme');
|
|
var sidebar = localStorage.getItem('mdbook-sidebar');
|
|
|
|
if (theme.startsWith('"') && theme.endsWith('"')) {
|
|
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
|
}
|
|
|
|
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
|
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
|
}
|
|
} catch (e) { }
|
|
</script>
|
|
|
|
<!-- Set the theme before any content is loaded, prevents flash -->
|
|
<script type="text/javascript">
|
|
var theme;
|
|
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
|
if (theme === null || theme === undefined) { theme = default_theme; }
|
|
var html = document.querySelector('html');
|
|
html.classList.remove('no-js')
|
|
html.classList.remove('light')
|
|
html.classList.add(theme);
|
|
html.classList.add('js');
|
|
</script>
|
|
|
|
<!-- Hide / unhide sidebar before it is displayed -->
|
|
<script type="text/javascript">
|
|
var html = document.querySelector('html');
|
|
var sidebar = 'hidden';
|
|
if (document.body.clientWidth >= 1080) {
|
|
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
|
sidebar = sidebar || 'visible';
|
|
}
|
|
html.classList.remove('sidebar-visible');
|
|
html.classList.add("sidebar-" + sidebar);
|
|
</script>
|
|
|
|
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
|
<div class="sidebar-scrollbox">
|
|
<ol class="chapter"><li class="chapter-item expanded "><a href="about_salsa.html"><strong aria-hidden="true">1.</strong> About salsa</a></li><li class="chapter-item expanded affix "><li class="part-title">How to use Salsa</li><li class="chapter-item expanded "><a href="overview.html" class="active"><strong aria-hidden="true">2.</strong> Overview</a></li><li class="chapter-item expanded "><a href="tutorial.html"><strong aria-hidden="true">3.</strong> Tutorial: calc language</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="tutorial/structure.html"><strong aria-hidden="true">3.1.</strong> Basic structure</a></li><li class="chapter-item expanded "><a href="tutorial/jar.html"><strong aria-hidden="true">3.2.</strong> Jars and databases</a></li><li class="chapter-item expanded "><a href="tutorial/db.html"><strong aria-hidden="true">3.3.</strong> Defining the database struct</a></li><li class="chapter-item expanded "><a href="tutorial/ir.html"><strong aria-hidden="true">3.4.</strong> Defining the IR: the various "salsa structs"</a></li><li class="chapter-item expanded "><a href="tutorial/parser.html"><strong aria-hidden="true">3.5.</strong> Defining the parser: memoized functions and inputs</a></li><li class="chapter-item expanded "><a href="tutorial/accumulators.html"><strong aria-hidden="true">3.6.</strong> Defining the parser: reporting errors</a></li><li class="chapter-item expanded "><a href="tutorial/debug.html"><strong aria-hidden="true">3.7.</strong> Defining the parser: debug impls and testing</a></li><li class="chapter-item expanded "><a href="tutorial/checker.html"><strong aria-hidden="true">3.8.</strong> Defining the checker</a></li><li class="chapter-item expanded "><a href="tutorial/interpreter.html"><strong aria-hidden="true">3.9.</strong> Defining the interpreter</a></li></ol></li><li class="chapter-item expanded "><a href="reference.html"><strong aria-hidden="true">4.</strong> Reference</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="reference/durability.html"><strong aria-hidden="true">4.1.</strong> Durability</a></li><li class="chapter-item expanded "><a href="reference/algorithm.html"><strong aria-hidden="true">4.2.</strong> Algorithm</a></li></ol></li><li class="chapter-item expanded "><a href="common_patterns.html"><strong aria-hidden="true">5.</strong> Common patterns</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="common_patterns/on_demand_inputs.html"><strong aria-hidden="true">5.1.</strong> On-demand (Lazy) inputs</a></li></ol></li><li class="chapter-item expanded "><a href="tuning.html"><strong aria-hidden="true">6.</strong> Tuning</a></li><li class="chapter-item expanded "><a href="cycles.html"><strong aria-hidden="true">7.</strong> Cycle handling</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="cycles/fallback.html"><strong aria-hidden="true">7.1.</strong> Recovering via fallback</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">How Salsa works internally</li><li class="chapter-item expanded "><a href="how_salsa_works.html"><strong aria-hidden="true">8.</strong> How Salsa works</a></li><li class="chapter-item expanded "><a href="videos.html"><strong aria-hidden="true">9.</strong> Videos</a></li><li class="chapter-item expanded "><a href="plumbing.html"><strong aria-hidden="true">10.</strong> Plumbing</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="plumbing/jars_and_ingredients.html"><strong aria-hidden="true">10.1.</strong> Jars and ingredients</a></li><li class="chapter-item expanded "><a href="plumbing/database_and_runtime.html"><strong aria-hidden="true">10.2.</strong> Databases and runtime</a></li><li class="chapter-item expanded "><a href="plumbing/db_lifetime.html"><strong aria-hidden="true">10.3.</strong> The db lifetime on tracked/interned structs</a></li><li class="chapter-item expanded "><a href="plumbing/tracked_structs.html"><strong aria-hidden="true">10.4.</strong> Tracked structures</a></li><li class="chapter-item expanded "><a href="plumbing/query_ops.html"><strong aria-hidden="true">10.5.</strong> Query operations</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="plumbing/maybe_changed_after.html"><strong aria-hidden="true">10.5.1.</strong> maybe changed after</a></li><li class="chapter-item expanded "><a href="plumbing/fetch.html"><strong aria-hidden="true">10.5.2.</strong> Fetch</a></li><li class="chapter-item expanded "><a href="plumbing/derived_flowchart.html"><strong aria-hidden="true">10.5.3.</strong> Derived queries flowchart</a></li><li class="chapter-item expanded "><a href="plumbing/cycles.html"><strong aria-hidden="true">10.5.4.</strong> Cycle handling</a></li></ol></li><li class="chapter-item expanded "><a href="plumbing/terminology.html"><strong aria-hidden="true">10.6.</strong> Terminology</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="plumbing/terminology/backdate.html"><strong aria-hidden="true">10.6.1.</strong> Backdate</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/changed_at.html"><strong aria-hidden="true">10.6.2.</strong> Changed at</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/dependency.html"><strong aria-hidden="true">10.6.3.</strong> Dependency</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/derived_query.html"><strong aria-hidden="true">10.6.4.</strong> Derived query</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/durability.html"><strong aria-hidden="true">10.6.5.</strong> Durability</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/input_query.html"><strong aria-hidden="true">10.6.6.</strong> Input query</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/ingredient.html"><strong aria-hidden="true">10.6.7.</strong> Ingredient</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/LRU.html"><strong aria-hidden="true">10.6.8.</strong> LRU</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/memo.html"><strong aria-hidden="true">10.6.9.</strong> Memo</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/query.html"><strong aria-hidden="true">10.6.10.</strong> Query</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/query_function.html"><strong aria-hidden="true">10.6.11.</strong> Query function</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/revision.html"><strong aria-hidden="true">10.6.12.</strong> Revision</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/salsa_item.html"><strong aria-hidden="true">10.6.13.</strong> Salsa item</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/salsa_struct.html"><strong aria-hidden="true">10.6.14.</strong> Salsa struct</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/untracked.html"><strong aria-hidden="true">10.6.15.</strong> Untracked dependency</a></li><li class="chapter-item expanded "><a href="plumbing/terminology/verified.html"><strong aria-hidden="true">10.6.16.</strong> Verified</a></li></ol></li></ol></li><li class="chapter-item expanded "><li class="part-title">Appendices</li><li class="chapter-item expanded "><a href="meta.html"><strong aria-hidden="true">11.</strong> Meta: about the book itself</a></li></ol> </div>
|
|
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
|
|
</nav>
|
|
|
|
<div id="page-wrapper" class="page-wrapper">
|
|
|
|
<div class="page">
|
|
|
|
<div id="menu-bar-hover-placeholder"></div>
|
|
<div id="menu-bar" class="menu-bar sticky bordered">
|
|
<div class="left-buttons">
|
|
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
|
<i class="fa fa-bars"></i>
|
|
</button>
|
|
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
|
<i class="fa fa-paint-brush"></i>
|
|
</button>
|
|
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
|
<li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
|
</ul>
|
|
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
|
<i class="fa fa-search"></i>
|
|
</button>
|
|
</div>
|
|
|
|
<h1 class="menu-title">Salsa</h1>
|
|
|
|
<div class="right-buttons">
|
|
<a href="print.html" title="Print this book" aria-label="Print this book">
|
|
<i id="print-button" class="fa fa-print"></i>
|
|
</a>
|
|
|
|
</div>
|
|
</div>
|
|
|
|
<div id="search-wrapper" class="hidden">
|
|
<form id="searchbar-outer" class="searchbar-outer">
|
|
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
|
</form>
|
|
<div id="searchresults-outer" class="searchresults-outer hidden">
|
|
<div id="searchresults-header" class="searchresults-header"></div>
|
|
<ul id="searchresults">
|
|
</ul>
|
|
</div>
|
|
</div>
|
|
|
|
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
|
<script type="text/javascript">
|
|
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
|
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
|
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
|
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
|
});
|
|
</script>
|
|
|
|
<div id="content" class="content">
|
|
<main>
|
|
<h1 id="salsa-overview"><a class="header" href="#salsa-overview">Salsa overview</a></h1>
|
|
<p>This page contains a brief overview of the pieces of a Salsa program.
|
|
For a more detailed look, check out the <a href="./tutorial.html">tutorial</a>, which walks through the creation of an entire project end-to-end.</p>
|
|
<h2 id="goal-of-salsa"><a class="header" href="#goal-of-salsa">Goal of Salsa</a></h2>
|
|
<p>The goal of Salsa is to support efficient <strong>incremental recomputation</strong>.
|
|
Salsa is used in rust-analyzer, for example, to help it recompile your program quickly as you type.</p>
|
|
<p>The basic idea of a Salsa program is like this:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>let mut input = ...;
|
|
loop {
|
|
let output = your_program(&input);
|
|
modify(&mut input);
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>You start out with an input that has some value.
|
|
You invoke your program to get back a result.
|
|
Some time later, you modify the input and invoke your program again.
|
|
<strong>Our goal is to make this second call faster by re-using some of the results from the first call.</strong></p>
|
|
<p>In reality, of course, you can have many inputs and "your program" may be many different methods and functions defined on those inputs.
|
|
But this picture still conveys a few important concepts:</p>
|
|
<ul>
|
|
<li>Salsa separates out the "incremental computation" (the function <code>your_program</code>) from some outer loop that is defining the inputs.</li>
|
|
<li>Salsa gives you the tools to define <code>your_program</code>.</li>
|
|
<li>Salsa assumes that <code>your_program</code> is a purely deterministic function of its inputs, or else this whole setup makes no sense.</li>
|
|
<li>The mutation of inputs always happens outside of <code>your_program</code>, as part of this master loop.</li>
|
|
</ul>
|
|
<h2 id="database"><a class="header" href="#database">Database</a></h2>
|
|
<p>Each time you run your program, Salsa remembers the values of each computation in a <strong>database</strong>.
|
|
When the inputs change, it consults this database to look for values that can be reused.
|
|
The database is also used to implement interning (making a canonical version of a value that can be copied around and cheaply compared for equality) and other convenient Salsa features.</p>
|
|
<h2 id="inputs"><a class="header" href="#inputs">Inputs</a></h2>
|
|
<p>Every Salsa program begins with an <strong>input</strong>.
|
|
Inputs are special structs that define the starting point of your program.
|
|
Everything else in your program is ultimately a deterministic function of these inputs.</p>
|
|
<p>For example, in a compiler, there might be an input defining the contents of a file on disk:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::input]
|
|
pub struct ProgramFile {
|
|
pub path: PathBuf,
|
|
pub contents: String,
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>You create an input by using the <code>new</code> method.
|
|
Because the values of input fields are stored in the database, you also give an <code>&</code>-reference to the database:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>let file: ProgramFile = ProgramFile::new(
|
|
&db,
|
|
PathBuf::from("some_path.txt"),
|
|
String::from("fn foo() { }"),
|
|
);
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Mutable access is not needed since creating a new input cannot affect existing tracked data in the database.</p>
|
|
<h3 id="salsa-structs-are-just-integers"><a class="header" href="#salsa-structs-are-just-integers">Salsa structs are just integers</a></h3>
|
|
<p>The <code>ProgramFile</code> struct generated by the <code>salsa::input</code> macro doesn't actually store any data. It's just a newtyped integer id:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>// Generated by the `#[salsa::input]` macro:
|
|
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
|
|
pub struct ProgramFile(salsa::Id);
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>This means that, when you have a <code>ProgramFile</code>, you can easily copy it around and put it wherever you like.
|
|
To actually read any of its fields, however, you will need to use the database and a getter method.</p>
|
|
<h3 id="reading-fields-and-return_ref"><a class="header" href="#reading-fields-and-return_ref">Reading fields and <code>return_ref</code></a></h3>
|
|
<p>You can access the value of an input's fields by using the getter method.
|
|
As this is only reading the field, it just needs a <code>&</code>-reference to the database:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>let contents: String = file.contents(&db);
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Invoking the accessor clones the value from the database.
|
|
Sometimes this is not what you want, so you can annotate fields with <code>#[return_ref]</code> to indicate that they should return a reference into the database instead:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::input]
|
|
pub struct ProgramFile {
|
|
pub path: PathBuf,
|
|
#[return_ref]
|
|
pub contents: String,
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Now <code>file.contents(&db)</code> will return an <code>&String</code>.</p>
|
|
<p>You can also use the <code>data</code> method to access the entire struct:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>file.data(&db)
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<h3 id="writing-input-fields"><a class="header" href="#writing-input-fields">Writing input fields</a></h3>
|
|
<p>Finally, you can also modify the value of an input field by using the setter method.
|
|
Since this is modifying the input, and potentially invalidating data derived from it,
|
|
the setter takes an <code>&mut</code>-reference to the database:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>file.set_contents(&mut db).to(String::from("fn foo() { /* add a comment */ }"));
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Note that the setter method <code>set_contents</code> returns a "builder".
|
|
This gives the ability to set the <a href="./reference/durability.html">durability</a> and other advanced concepts.</p>
|
|
<h2 id="tracked-functions"><a class="header" href="#tracked-functions">Tracked functions</a></h2>
|
|
<p>Once you've defined your inputs, the next thing to define are <strong>tracked functions</strong>:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked]
|
|
fn parse_file(db: &dyn crate::Db, file: ProgramFile) -> Ast {
|
|
let contents: &str = file.contents(db);
|
|
...
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>When you call a tracked function, Salsa will track which inputs it accesses (in this example, <code>file.contents(db)</code>).
|
|
It will also memoize the return value (the <code>Ast</code>, in this case).
|
|
If you call a tracked function twice, Salsa checks if the inputs have changed; if not, it can return the memoized value.
|
|
The algorithm Salsa uses to decide when a tracked function needs to be re-executed is called the <a href="./reference/algorithm.html">red-green algorithm</a>, and it's where the name Salsa comes from.</p>
|
|
<p>Tracked functions have to follow a particular structure:</p>
|
|
<ul>
|
|
<li>They must take a <code>&</code>-reference to the database as their first argument.
|
|
<ul>
|
|
<li>Note that because this is an <code>&</code>-reference, it is not possible to modify inputs during a tracked function!</li>
|
|
</ul>
|
|
</li>
|
|
<li>They must take a "Salsa struct" as the second argument -- in our example, this is an input struct, but there are other kinds of Salsa structs we'll describe shortly.</li>
|
|
<li>They <em>can</em> take additional arguments, but it's faster and better if they don't.</li>
|
|
</ul>
|
|
<p>Tracked functions can return any clone-able type. A clone is required since, when the value is cached, the result will be cloned out of the database. Tracked functions can also be annotated with <code>#[return_ref]</code> if you would prefer to return a reference into the database instead (if <code>parse_file</code> were so annotated, then callers would actually get back an <code>&Ast</code>, for example).</p>
|
|
<h2 id="tracked-structs"><a class="header" href="#tracked-structs">Tracked structs</a></h2>
|
|
<p><strong>Tracked structs</strong> are intermediate structs created during your computation.
|
|
Like inputs, their fields are stored inside the database, and the struct itself just wraps an id.
|
|
Unlike inputs, they can only be created inside a tracked function, and their fields can never change once they are created (until the next revision, at least).
|
|
Getter methods are provided to read the fields, but there are no setter methods.
|
|
Example:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked]
|
|
struct Ast<'db> {
|
|
#[return_ref]
|
|
top_level_items: Vec<Item>,
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Just as with an input, new values are created by invoking <code>Ast::new</code>.
|
|
Unlike with an input, the <code>new</code> for a tracked struct only requires a <code>&</code>-reference to the database:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked]
|
|
fn parse_file(db: &dyn crate::Db, file: ProgramFile) -> Ast {
|
|
let contents: &str = file.contents(db);
|
|
let parser = Parser::new(contents);
|
|
let mut top_level_items = vec![];
|
|
while let Some(item) = parser.parse_top_level_item() {
|
|
top_level_items.push(item);
|
|
}
|
|
Ast::new(db, top_level_items) // <-- create an Ast!
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<h3 id="id-fields"><a class="header" href="#id-fields"><code>#[id]</code> fields</a></h3>
|
|
<p>When a tracked function is re-executed because its inputs have changed, the tracked structs it creates in the new execution are matched against those from the old execution, and the values of their fields are compared.
|
|
If the field values have not changed, then other tracked functions that only read those fields will not be re-executed.</p>
|
|
<p>Normally, tracked structs are matched up by the order in which they are created.
|
|
For example, the first <code>Ast</code> that is created by <code>parse_file</code> in the old execution will be matched against the first <code>Ast</code> created by <code>parse_file</code> in the new execution.
|
|
In our example, <code>parse_file</code> only ever creates a single <code>Ast</code>, so this works great.
|
|
Sometimes, however, it doesn't work so well.
|
|
For example, imagine that we had a tracked struct for items in the file:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked]
|
|
struct Item {
|
|
name: Word, // we'll define Word in a second!
|
|
...
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Maybe our parser first creates an <code>Item</code> with the name <code>foo</code> and then later a second <code>Item</code> with the name <code>bar</code>.
|
|
Then the user changes the input to reorder the functions.
|
|
Although we are still creating the same number of items, we are now creating them in the reverse order, so the naive algorithm will match up the <em>old</em> <code>foo</code> struct with the new <code>bar</code> struct.
|
|
This will look to Salsa as though the <code>foo</code> function was renamed to <code>bar</code> and the <code>bar</code> function was renamed to <code>foo</code>.
|
|
We'll still get the right result, but we might do more recomputation than we needed to do if we understood that they were just reordered.</p>
|
|
<p>To address this, you can tag fields in a tracked struct as <code>#[id]</code>. These fields are then used to "match up" struct instances across executions:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked]
|
|
struct Item {
|
|
#[id]
|
|
name: Word, // we'll define Word in a second!
|
|
...
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<h3 id="specify-the-result-of-tracked-functions-for-particular-structs"><a class="header" href="#specify-the-result-of-tracked-functions-for-particular-structs">Specify the result of tracked functions for particular structs</a></h3>
|
|
<p>Sometimes it is useful to define a tracked function but specify its value for some particular struct specially.
|
|
For example, maybe the default way to compute the representation for a function is to read the AST, but you also have some built-in functions in your language and you want to hard-code their results.
|
|
This can also be used to simulate a field that is initialized after the tracked struct is created.</p>
|
|
<p>To support this use case, you can use the <code>specify</code> method associated with tracked functions.
|
|
To enable this method, you need to add the <code>specify</code> flag to the function to alert users that its value may sometimes be specified externally.</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked(specify)] // <-- specify flag required
|
|
fn representation(db: &dyn crate::Db, item: Item) -> Representation {
|
|
// read the user's input AST by default
|
|
let ast = ast(db, item);
|
|
// ...
|
|
}
|
|
|
|
fn create_builtin_item(db: &dyn crate::Db) -> Item {
|
|
let i = Item::new(db, ...);
|
|
let r = hardcoded_representation();
|
|
representation::specify(db, i, r); // <-- use the method!
|
|
i
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Specifying is only possible for tracked functions that take a single tracked struct as an argument (besides the database).</p>
|
|
<h2 id="interned-structs"><a class="header" href="#interned-structs">Interned structs</a></h2>
|
|
<p>The final kind of Salsa struct are <strong>interned structs</strong>.
|
|
Interned structs are useful for quick equality comparison.
|
|
They are commonly used to represent strings or other primitive values.</p>
|
|
<p>Most compilers, for example, will define a type to represent a user identifier:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::interned]
|
|
struct Word {
|
|
#[return_ref]
|
|
pub text: String,
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>As with input and tracked structs, the <code>Word</code> struct itself is just a newtyped integer, and the actual data is stored in the database.</p>
|
|
<p>You can create a new interned struct using <code>new</code>, just like with input and tracked structs:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>let w1 = Word::new(db, "foo".to_string());
|
|
let w2 = Word::new(db, "bar".to_string());
|
|
let w3 = Word::new(db, "foo".to_string());
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>When you create two interned structs with the same field values, you are guaranteed to get back the same integer id. So here, we know that <code>assert_eq!(w1, w3)</code> is true and <code>assert_ne!(w1, w2)</code>.</p>
|
|
<p>You can access the fields of an interned struct using a getter, like <code>word.text(db)</code>. These getters respect the <code>#[return_ref]</code> annotation. Like tracked structs, the fields of interned structs are immutable.</p>
|
|
<h2 id="accumulators"><a class="header" href="#accumulators">Accumulators</a></h2>
|
|
<p>The final Salsa concept are <strong>accumulators</strong>. Accumulators are a way to report errors or other "side channel" information that is separate from the main return value of your function.</p>
|
|
<p>To create an accumulator, you declare a type as an <em>accumulator</em>:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::accumulator]
|
|
pub struct Diagnostics(String);
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>It must be a newtype of something, like <code>String</code>. Now, during a tracked function's execution, you can push those values:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>Diagnostics::push(db, "some_string".to_string())
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Then later, from outside the execution, you can ask for the set of diagnostics that were accumulated by some particular tracked function. For example, imagine that we have a type-checker and, during type-checking, it reports some diagnostics:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>#[salsa::tracked]
|
|
fn type_check(db: &dyn Db, item: Item) {
|
|
// ...
|
|
Diagnostics::push(db, "some error message".to_string())
|
|
// ...
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>we can then later invoke the associated <code>accumulated</code> function to get all the <code>String</code> values that were pushed:</p>
|
|
<pre><pre class="playground"><code class="language-rust">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>let v: Vec<String> = type_check::accumulated::<Diagnostics>(db);
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
|
|
</main>
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
<!-- Mobile navigation buttons -->
|
|
<a rel="prev" href="about_salsa.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next" href="tutorial.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
|
|
<div style="clear: both"></div>
|
|
</nav>
|
|
</div>
|
|
</div>
|
|
|
|
<nav class="nav-wide-wrapper" aria-label="Page navigation">
|
|
<a rel="prev" href="about_salsa.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next" href="tutorial.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
</nav>
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
<script type="text/javascript">
|
|
window.playground_copyable = true;
|
|
</script>
|
|
|
|
|
|
<script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="searcher.js" type="text/javascript" charset="utf-8"></script>
|
|
|
|
<script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="highlight.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="book.js" type="text/javascript" charset="utf-8"></script>
|
|
|
|
<!-- Custom JS scripts -->
|
|
<script type="text/javascript" src="mermaid.min.js"></script>
|
|
<script type="text/javascript" src="mermaid-init.js"></script>
|
|
|
|
|
|
</body>
|
|
</html>
|