<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>docs/dev/guide.md - fork/rust-analyzer @ 2022-06-27</title>
<meta name="description" content="docs/dev/guide.md in fork/rust-analyzer at 2022-06-27.">
<meta property="og:title" content="docs/dev/guide.md - fork/rust-analyzer @ 2022-06-27">
<meta property="og:description" content="docs/dev/guide.md in fork/rust-analyzer at 2022-06-27.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="2022-06-27" data-tip="b74e96f509baf0be70281c55f14cb18fefbc6b22">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>fork/rust-analyzer</h1>
</div>
<pre class="clone">git clone https://git.julia.blue/fork/rust-analyzer</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">bors[bot]</span><span class="commit-message" data-commit="9ca81edb7ce2e301234e3dafd7ecc35d398db603">Merge #9703</span><span class="snapshot-sha sha" data-commit="9ca81edb7ce2e301234e3dafd7ecc35d398db603">9ca81edb7c</span><time datetime="2021-07-26T22:23:35+00:00" title="2021-07-26 22:23:35 +0000">2021-07-26</time></p>
<header class="topbar"><details class="switcher"><summary>2022-06-27</summary><div class="menu"><strong>branches</strong><a href="/fork/rust-analyzer/ref/master/">master</a><strong>tags</strong><a href="/fork/rust-analyzer/ref/2022-06-13/">2022-06-13</a><a href="/fork/rust-analyzer/ref/2022-06-20/">2022-06-20</a><a class="current" href="/fork/rust-analyzer/ref/2022-06-27/">2022-06-27</a><a href="/fork/rust-analyzer/ref/2022-07-04/">2022-07-04</a><a href="/fork/rust-analyzer/ref/2022-07-11/">2022-07-11</a><a href="/fork/rust-analyzer/ref/2022-07-18/">2022-07-18</a><a href="/fork/rust-analyzer/ref/2022-07-25/">2022-07-25</a><a href="/fork/rust-analyzer/ref/nightly/">nightly</a><a class="all" href="/fork/rust-analyzer/refs">all refs →</a></div></details><nav class="crumbs"><a href="/fork/rust-analyzer/">rust-analyzer</a> / <a href="/fork/rust-analyzer/ref/2022-06-27/tree/docs/">docs</a> / <a href="/fork/rust-analyzer/ref/2022-06-27/tree/docs/dev/">dev</a> / <span class="cur">guide.md</span></nav>
<span class="view-stats"><span>31.4 KiB</span><span>573 lines</span></span><span class="actions"><a class="raw" href="/fork/rust-analyzer/raw/650fbfc89f36c534e13ebccbf1131c08607ac168/docs/dev/guide.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><h1>Guide to rust-analyzer</h1>
<h2>About the guide</h2>
<p>This guide describes the current state of rust-analyzer as of 2019-01-20 (git
tag <a href="https://github.com/rust-analyzer/rust-analyzer/tree/guide-2019-01">guide-2019-01</a>). Its purpose is to document various problems and
architectural solutions related to the problem of building IDE-first compiler
for Rust. There is a video version of this guide as well:
https://youtu.be/ANKBNiSWyfc.</p>
<h2>The big picture</h2>
<p>On the highest possible level, rust-analyzer is a stateful component. A client may
apply changes to the analyzer (new contents of <code>foo.rs</code> file is "fn main() {}")
and it may ask semantic questions about the current state (what is the
definition of the identifier with offset 92 in file <code>bar.rs</code>?). Two important
properties hold:</p>
<ul>
<li>
<p>Analyzer does not do any I/O. It starts in an empty state and all input data is
provided via <code>apply_change</code> API.</p>
</li>
<li>
<p>Only queries about the current state are supported. One can, of course,
simulate undo and redo by keeping a log of changes and inverse changes respectively.</p>
</li>
</ul>
<h2>IDE API</h2>
<p>To see the bigger picture of how the IDE features work, let's take a look at the <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L265-L284"><code>AnalysisHost</code></a> and
<a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L291-L478"><code>Analysis</code></a> pair of types. <code>AnalysisHost</code> has three methods:</p>
<ul>
<li><code>default()</code> for creating an empty analysis instance</li>
<li><code>apply_change(&amp;mut self)</code> to make changes (this is how you get from an empty
state to something interesting)</li>
<li><code>analysis(&amp;self)</code> to get an instance of <code>Analysis</code></li>
</ul>
<p><code>Analysis</code> has a ton of methods for IDEs, like <code>goto_definition</code>, or
<code>completions</code>. Both inputs and outputs of <code>Analysis</code>' methods are formulated in
terms of files and offsets, and <strong>not</strong> in terms of Rust concepts like structs,
traits, etc. The "typed" API with Rust specific types is slightly lower in the
stack, we'll talk about it later.</p>
<p>The reason for this separation of <code>Analysis</code> and <code>AnalysisHost</code> is that we want to apply
changes "uniquely", but we might also want to fork an <code>Analysis</code> and send it to
another thread for background processing. That is, there is only a single
<code>AnalysisHost</code>, but there may be several (equivalent) <code>Analysis</code>.</p>
<p>Note that all of the <code>Analysis</code> API return <code>Cancellable&lt;T&gt;</code>. This is required to
be responsive in an IDE setting. Sometimes a long-running query is being computed
and the user types something in the editor and asks for completion. In this
case, we cancel the long-running computation (so it returns <code>Err(Cancelled)</code>),
apply the change and execute request for completion. We never use stale data to
answer requests. Under the cover, <code>AnalysisHost</code> "remembers" all outstanding
<code>Analysis</code> instances. The <code>AnalysisHost::apply_change</code> method cancels all
<code>Analysis</code>es, blocks until all of them are <code>Dropped</code> and then applies changes
in-place. This may be familiar to Rustaceans who use read-write locks for interior
mutability.</p>
<p>Next, let's talk about what the inputs to the <code>Analysis</code> are, precisely.</p>
<h2>Inputs</h2>
<p>Rust Analyzer never does any I/O itself, all inputs get passed explicitly via
the <code>AnalysisHost::apply_change</code> method, which accepts a single argument, a
<code>Change</code>. <a href="https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/base_db/src/change.rs#L14-L89"><code>Change</code></a> is a builder for a single change
"transaction", so it suffices to study its methods to understand all of the
input data.</p>
<p>The <code>(add|change|remove)_file</code> methods control the set of the input files, where
each file has an integer id (<code>FileId</code>, picked by the client), text (<code>String</code>)
and a filesystem path. Paths are tricky; they'll be explained below, in source roots
section, together with the <code>add_root</code> method. The <code>add_library</code> method allows us to add a
group of files which are assumed to rarely change. It's mostly an optimization
and does not change the fundamental picture.</p>
<p>The <code>set_crate_graph</code> method allows us to control how the input files are partitioned
into compilation units -- crates. It also controls (in theory, not implemented
yet) <code>cfg</code> flags. <code>CrateGraph</code> is a directed acyclic graph of crates. Each crate
has a root <code>FileId</code>, a set of active <code>cfg</code> flags and a set of dependencies. Each
dependency is a pair of a crate and a name. It is possible to have two crates
with the same root <code>FileId</code> but different <code>cfg</code>-flags/dependencies. This model
is lower than Cargo's model of packages: each Cargo package consists of several
targets, each of which is a separate crate (or several crates, if you try
different feature combinations).</p>
<p>Procedural macros should become inputs as well, but currently they are not
supported. Procedural macro will be a black box <code>Box&lt;dyn Fn(TokenStream) -&gt; TokenStream&gt;</code>
function, and will be inserted into the crate graph just like dependencies.</p>
<p>Soon we'll talk how we build an LSP server on top of <code>Analysis</code>, but first,
let's deal with that paths issue.</p>
<h2>Source roots (a.k.a. "Filesystems are horrible")</h2>
<p>This is a non-essential section, feel free to skip.</p>
<p>The previous section said that the filesystem path is an attribute of a file,
but this is not the whole truth. Making it an absolute <code>PathBuf</code> will be bad for
several reasons. First, filesystems are full of (platform-dependent) edge cases:</p>
<ul>
<li>It's hard (requires a syscall) to decide if two paths are equivalent.</li>
<li>Some filesystems are case-sensitive (e.g. macOS).</li>
<li>Paths are not necessarily UTF-8.</li>
<li>Symlinks can form cycles.</li>
</ul>
<p>Second, this might hurt the reproducibility and hermeticity of builds. In theory,
moving a project from <code>/foo/bar/my-project</code> to <code>/spam/eggs/my-project</code> should
not change a bit in the output. However, if the absolute path is a part of the
input, it is at least in theory observable, and <em>could</em> affect the output.</p>
<p>Yet another problem is that we really <em>really</em> want to avoid doing I/O, but with
Rust the set of "input" files is not necessarily known up-front. In theory, you
can have <code>#[path="/dev/random"] mod foo;</code>.</p>
<p>To solve (or explicitly refuse to solve) these problems rust-analyzer uses the
concept of a "source root". Roughly speaking, source roots are the contents of a
directory on a file systems, like <code>/home/matklad/projects/rustraytracer/**.rs</code>.</p>
<p>More precisely, all files (<code>FileId</code>s) are partitioned into disjoint
<code>SourceRoot</code>s. Each file has a relative UTF-8 path within the <code>SourceRoot</code>.
<code>SourceRoot</code> has an identity (integer ID). Crucially, the root path of the
source root itself is unknown to the analyzer: A client is supposed to maintain a
mapping between <code>SourceRoot</code> IDs (which are assigned by the client) and actual
<code>PathBuf</code>s. <code>SourceRoot</code>s give a sane tree model of the file system to the
analyzer.</p>
<p>Note that <code>mod</code>, <code>#[path]</code> and <code>include!()</code> can only reference files from the
same source root. It is of course possible to explicitly add extra files to
the source root, even <code>/dev/random</code>.</p>
<h2>Language Server Protocol</h2>
<p>Now let's see how the <code>Analysis</code> API is exposed via the JSON RPC based language server protocol. The
hard part here is managing changes (which can come either from the file system
or from the editor) and concurrency (we want to spawn background jobs for things
like syntax highlighting). We use the event loop pattern to manage the zoo, and
the loop is the <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L156-L258"><code>main_loop_inner</code></a> function. The <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L51-L110"><code>main_loop</code></a> does a one-time
initialization and tearing down of the resources.</p>
<p>Let's walk through a typical analyzer session!</p>
<p>First, we need to figure out what to analyze. To do this, we run <code>cargo metadata</code> to learn about Cargo packages for current workspace and dependencies,
and we run <code>rustc --print sysroot</code> and scan the "sysroot" (the directory containing the current Rust toolchain's files) to learn about crates like
<code>std</code>. Currently we load this configuration once at the start of the server, but
it should be possible to dynamically reconfigure it later without restart.</p>
<p><a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L62-L70">main_loop.rs#L62-L70</a></p>
<p>The <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/project_model.rs#L16-L20"><code>ProjectModel</code></a> we get after this step is very Cargo and sysroot specific,
it needs to be lowered to get the input in the form of <code>Change</code>. This
happens in <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L38-L160"><code>ServerWorldState::new</code></a> method. Specifically</p>
<ul>
<li>Create a <code>SourceRoot</code> for each Cargo package and sysroot.</li>
<li>Schedule a filesystem scan of the roots.</li>
<li>Create an analyzer's <code>Crate</code> for each Cargo <strong>target</strong> and sysroot crate.</li>
<li>Setup dependencies between the crates.</li>
</ul>
<p>The results of the scan (which may take a while) will be processed in the body
of the main loop, just like any other change. Here's where we handle:</p>
<ul>
<li><a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L194">File system changes</a></li>
<li><a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L377">Changes from the editor</a></li>
</ul>
<p>After a single loop's turn, we group the changes into one <code>Change</code> and
<a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L216">apply</a> it. This always happens on the main thread and blocks the loop.</p>
<p>To handle requests, like <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L216">"goto definition"</a>, we create an instance of the
<code>Analysis</code> and <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L426-L455"><code>schedule</code></a> the task (which consumes <code>Analysis</code>) on the
threadpool. <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop/handlers.rs#L205-L223">The task</a> calls the corresponding <code>Analysis</code> method, while
massaging the types into the LSP representation. Keep in mind that if we are
executing "goto definition" on the threadpool and a new change comes in, the
task will be canceled as soon as the main loop calls <code>apply_change</code> on the
<code>AnalysisHost</code>.</p>
<p>This concludes the overview of the analyzer's programing <em>interface</em>. Next, let's
dig into the implementation!</p>
<h2>Salsa</h2>
<p>The most straightforward way to implement an "apply change, get analysis, repeat"
API would be to maintain the input state and to compute all possible analysis
information from scratch after every change. This works, but scales poorly with
the size of the project. To make this fast, we need to take advantage of the
fact that most of the changes are small, and that analysis results are unlikely
to change significantly between invocations.</p>
<p>To do this we use <a href="https://github.com/salsa-rs/salsa">salsa</a>: a framework for incremental on-demand computation.
You can skip the rest of the section if you are familiar with <code>rustc</code>'s red-green
algorithm (which is used for incremental compilation).</p>
<p>It's better to refer to salsa's docs to learn about it. Here's a small excerpt:</p>
<p>The key idea of salsa is that you define your program as a set of queries. Every
query is used like a function <code>K -&gt; V</code> that maps from some key of type <code>K</code> to a value
of type <code>V</code>. Queries come in two basic varieties:</p>
<ul>
<li>
<p><strong>Inputs</strong>: the base inputs to your system. You can change these whenever you
like.</p>
</li>
<li>
<p><strong>Functions</strong>: pure functions (no side effects) that transform your inputs
into other values. The results of queries are memoized to avoid recomputing
them a lot. When you make changes to the inputs, we'll figure out (fairly
intelligently) when we can re-use these memoized values and when we have to
recompute them.</p>
</li>
</ul>
<p>For further discussion, its important to understand one bit of "fairly
intelligently". Suppose we have two functions, <code>f1</code> and <code>f2</code>, and one input,
<code>z</code>. We call <code>f1(X)</code> which in turn calls <code>f2(Y)</code> which inspects <code>i(Z)</code>. <code>i(Z)</code>
returns some value <code>V1</code>, <code>f2</code> uses that and returns <code>R1</code>, <code>f1</code> uses that and
returns <code>O</code>. Now, let's change <code>i</code> at <code>Z</code> to <code>V2</code> from <code>V1</code> and try to compute
<code>f1(X)</code> again. Because <code>f1(X)</code> (transitively) depends on <code>i(Z)</code>, we can't just
reuse its value as is. However, if <code>f2(Y)</code> is <em>still</em> equal to <code>R1</code> (despite
<code>i</code>'s change), we, in fact, <em>can</em> reuse <code>O</code> as result of <code>f1(X)</code>. And that's how
salsa works: it recomputes results in <em>reverse</em> order, starting from inputs and
progressing towards outputs, stopping as soon as it sees an intermediate value
that hasn't changed. If this sounds confusing to you, don't worry: it is
confusing. This illustration by @killercup might help:</p>
&lt;img alt="step 1" src="https://user-images.githubusercontent.com/1711539/51460907-c5484780-1d6d-11e9-9cd2-d6f62bd746e0.png" width="50%"&gt;
&lt;img alt="step 2" src="https://user-images.githubusercontent.com/1711539/51460915-c9746500-1d6d-11e9-9a77-27d33a0c51b5.png" width="50%"&gt;
&lt;img alt="step 3" src="https://user-images.githubusercontent.com/1711539/51460920-cda08280-1d6d-11e9-8d96-a782aa57a4d4.png" width="50%"&gt;
&lt;img alt="step 4" src="https://user-images.githubusercontent.com/1711539/51460927-d1340980-1d6d-11e9-851e-13c149d5c406.png" width="50%"&gt;
<h2>Salsa Input Queries</h2>
<p>All analyzer information is stored in a salsa database. <code>Analysis</code> and
<code>AnalysisHost</code> types are newtype wrappers for <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/db.rs#L88-L134"><code>RootDatabase</code></a> -- a salsa
database.</p>
<p>Salsa input queries are defined in <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/base_db/src/input.rs#L150-L174"><code>FilesDatabase</code></a> (which is a part of
<code>RootDatabase</code>). They closely mirror the familiar <code>Change</code> structure:
indeed, what <code>apply_change</code> does is it sets the values of input queries.</p>
<h2>From text to semantic model</h2>
<p>The bulk of the rust-analyzer is transforming input text into a semantic model of
Rust code: a web of entities like modules, structs, functions and traits.</p>
<p>An important fact to realize is that (unlike most other languages like C# or
Java) there is not a one-to-one mapping between the source code and the semantic model. A
single function definition in the source code might result in several semantic
functions: for example, the same source file might get included as a module in
several crates or a single crate might be present in the compilation DAG
several times, with different sets of <code>cfg</code>s enabled. The IDE-specific task of
mapping source code into a semantic model is inherently imprecise for
this reason and gets handled by the <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/source_binder.rs"><code>source_binder</code></a>.</p>
<p>The semantic interface is declared in the <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/code_model_api.rs"><code>code_model_api</code></a> module. Each entity is
identified by an integer ID and has a bunch of methods which take a salsa database
as an argument and returns other entities (which are also IDs). Internally, these
methods invoke various queries on the database to build the model on demand.
Here's <a href="https://github.com/rust-analyzer/rust-analyzer/blob/7e84440e25e19529e4ff8a66e521d1b06349c6ec/crates/hir/src/db.rs#L20-L106">the list of queries</a>.</p>
<p>The first step of building the model is parsing the source code.</p>
<h2>Syntax trees</h2>
<p>An important property of the Rust language is that each file can be parsed in
isolation. Unlike, say, <code>C++</code>, an <code>include</code> can't change the meaning of the
syntax. For this reason, rust-analyzer can build a syntax tree for each "source
file", which could then be reused by several semantic models if this file
happens to be a part of several crates.</p>
<p>The representation of syntax trees that rust-analyzer uses is similar to that of <code>Roslyn</code>
and Swift's new <a href="https://github.com/apple/swift/tree/5e2c815edfd758f9b1309ce07bfc01c4bc20ec23/lib/Syntax">libsyntax</a>. Swift's docs give an excellent overview of the
approach, so I skip this part here and instead outline the main characteristics
of the syntax trees:</p>
<ul>
<li>
<p>Syntax trees are fully lossless. Converting <strong>any</strong> text to a syntax tree and
back is a total identity function. All whitespace and comments are explicitly
represented in the tree.</p>
</li>
<li>
<p>Syntax nodes have generic <code>(next|previous)_sibling</code>, <code>parent</code>,
<code>(first|last)_child</code> functions. You can get from any one node to any other
node in the file using only these functions.</p>
</li>
<li>
<p>Syntax nodes know their range (start offset and length) in the file.</p>
</li>
<li>
<p>Syntax nodes share the ownership of their syntax tree: if you keep a reference
to a single function, the whole enclosing file is alive.</p>
</li>
<li>
<p>Syntax trees are immutable and the cost of replacing the subtree is
proportional to the depth of the subtree. Read Swift's docs to learn how
immutable + parent pointers + cheap modification is possible.</p>
</li>
<li>
<p>Syntax trees are build on best-effort basis. All accessor methods return
<code>Option</code>s. The tree for <code>fn foo</code> will contain a function declaration with
<code>None</code> for parameter list and body.</p>
</li>
<li>
<p>Syntax trees do not know the file they are built from, they only know about
the text.</p>
</li>
</ul>
<p>The implementation is based on the generic <a href="https://github.com/rust-analyzer/rowan/tree/100a36dc820eb393b74abe0d20ddf99077b61f88">rowan</a> crate on top of which a
<a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_syntax/src/ast/generated.rs">rust-specific</a> AST is generated.</p>
<p>The next step in constructing the semantic model is ...</p>
<h2>Building a Module Tree</h2>
<p>The algorithm for building a tree of modules is to start with a crate root
(remember, each <code>Crate</code> from a <code>CrateGraph</code> has a <code>FileId</code>), collect all <code>mod</code>
declarations and recursively process child modules. This is handled by the
<a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/module_tree.rs#L116-L123"><code>module_tree_query</code></a>, with two slight variations.</p>
<p>First, rust-analyzer builds a module tree for all crates in a source root
simultaneously. The main reason for this is historical (<code>module_tree</code> predates
<code>CrateGraph</code>), but this approach also enables accounting for files which are not
part of any crate. That is, if you create a file but do not include it as a
submodule anywhere, you still get semantic completion, and you get a warning
about a free-floating module (the actual warning is not implemented yet).</p>
<p>The second difference is that <code>module_tree_query</code> does not <em>directly</em> depend on
the "parse" query (which is confusingly called <code>source_file</code>). Why would calling
the parse directly be bad? Suppose the user changes the file slightly, by adding
an insignificant whitespace. Adding whitespace changes the parse tree (because
it includes whitespace), and that means recomputing the whole module tree.</p>
<p>We deal with this problem by introducing an intermediate <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/module_tree.rs#L41"><code>submodules_query</code></a>.
This query processes the syntax tree and extracts a set of declared submodule
names. Now, changing the whitespace results in <code>submodules_query</code> being
re-executed for a <em>single</em> module, but because the result of this query stays
the same, we don't have to re-execute <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/module_tree.rs#L116-L123"><code>module_tree_query</code></a>. In fact, we only
need to re-execute it when we add/remove new files or when we change mod
declarations.</p>
<p>We store the resulting modules in a <code>Vec</code>-based indexed arena. The indices in
the arena becomes module IDs. And this brings us to the next topic:
assigning IDs in the general case.</p>
<h2>Location Interner pattern</h2>
<p>One way to assign IDs is how we've dealt with modules: Collect all items into a
single array in some specific order and use the index in the array as an ID. The
main drawback of this approach is that these IDs are not stable: Adding a new item can
shift the IDs of all other items. This works for modules, because adding a module is
a comparatively rare operation, but would be less convenient for, for example,
functions.</p>
<p>Another solution here is positional IDs: We can identify a function as "the
function with name <code>foo</code> in a ModuleId(92) module". Such locations are stable:
adding a new function to the module (unless it is also named <code>foo</code>) does not
change the location. However, such "ID" types ceases to be a <code>Copy</code>able integer and in
general can become pretty large if we account for nesting (for example: "third parameter of
the <code>foo</code> function of the <code>bar</code> <code>impl</code> in the <code>baz</code> module").</p>
<p><a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/base_db/src/loc2id.rs#L65-L71"><code>LocationInterner</code></a> allows us to combine the benefits of positional and numeric
IDs. It is a bidirectional append-only map between locations and consecutive
integers which can "intern" a location and return an integer ID back. The salsa
database we use includes a couple of <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/db.rs#L22-L23">interners</a>. How to "garbage collect"
unused locations is an open question.</p>
<p>For example, we use <code>LocationInterner</code> to assign IDs to definitions of functions,
structs, enums, etc. The location, <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/ids.rs#L127-L139"><code>DefLoc</code></a> contains two bits of information:</p>
<ul>
<li>the ID of the module which contains the definition,</li>
<li>the ID of the specific item in the modules source code.</li>
</ul>
<p>We "could" use a text offset for the location of a particular item, but that would play
badly with salsa: offsets change after edits. So, as a rule of thumb, we avoid
using offsets, text ranges or syntax trees as keys and values for queries. What
we do instead is we store "index" of the item among all of the items of a file
(so, a positional based ID, but localized to a single file).</p>
<p>One thing we've glossed over for the time being is support for macros. We have
only proof of concept handling of macros at the moment, but they are extremely
interesting from an "assigning IDs" perspective.</p>
<h2>Macros and recursive locations</h2>
<p>The tricky bit about macros is that they effectively create new source files.
While we can use <code>FileId</code>s to refer to original files, we can't just assign them
willy-nilly to the pseudo files of macro expansion. Instead, we use a special
ID, <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/ids.rs#L18-L125"><code>HirFileId</code></a> to refer to either a usual file or a macro-generated file:</p>
<pre class="language-rust"><a-k>enum</a-k> <a-t>HirFileId</a-t> <a-p>{</a-p>
    <a-cr>FileId</a-cr><a-p>(</a-p><a-t>FileId</a-t><a-p>),</a-p>
    <a-cr>Macro</a-cr><a-p>(</a-p><a-t>MacroCallId</a-t><a-p>),</a-p>
<a-p>}</a-p></pre>
<p><code>MacroCallId</code> is an interned ID that specifies a particular macro invocation.
Its <code>MacroCallLoc</code> contains:</p>
<ul>
<li><code>ModuleId</code> of the containing module</li>
<li><code>HirFileId</code> of the containing file or pseudo file</li>
<li>an index of this particular macro invocation in this file (positional id
again).</li>
</ul>
<p>Note how <code>HirFileId</code> is defined in terms of <code>MacroCallLoc</code> which is defined in
terms of <code>HirFileId</code>! This does not recur infinitely though: any chain of
<code>HirFileId</code>s bottoms out in <code>HirFileId::FileId</code>, that is, some source file
actually written by the user.</p>
<p>Now that we understand how to identify a definition, in a source or in a
macro-generated file, we can discuss name resolution a bit.</p>
<h2>Name resolution</h2>
<p>Name resolution faces the same problem as the module tree: if we look at the
syntax tree directly, we'll have to recompute name resolution after every
modification. The solution to the problem is the same: We <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L113-L117">lower</a> the source code of
each module into a position-independent representation which does not change if
we modify bodies of the items. After that we <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres.rs#L186-L196">loop</a> resolving all imports until
we've reached a fixed point.</p>
<p>And, given all our preparation with IDs and a position-independent representation,
it is satisfying to <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/tests.rs#L376">test</a> that typing inside function body does not invalidate
name resolution results.</p>
<p>An interesting fact about name resolution is that it "erases" all of the
intermediate paths from the imports: in the end, we know which items are defined
and which items are imported in each module, but, if the import was <code>use foo::bar::baz</code>, we deliberately forget what modules <code>foo</code> and <code>bar</code> resolve to.</p>
<p>To serve "goto definition" requests on intermediate segments we need this info
in the IDE, however. Luckily, we need it only for a tiny fraction of imports, so we just ask
the module explicitly, "What does the path <code>foo::bar</code> resolve to?". This is a
general pattern: we try to compute the minimal possible amount of information
during analysis while allowing IDE to ask for additional specific bits.</p>
<p>Name resolution is also a good place to introduce another salsa pattern used
throughout the analyzer:</p>
<h2>Source Map pattern</h2>
<p>Due to an obscure edge case in completion, IDE needs to know the syntax node of
a use statement which imported the given completion candidate. We can't just
store the syntax node as a part of name resolution: this will break
incrementality, due to the fact that syntax changes after every file
modification.</p>
<p>We solve this problem during the lowering step of name resolution. The lowering
query actually produces a <em>pair</em> of outputs: <code>LoweredModule</code> and <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L52-L59"><code>SourceMap</code></a>.
The <code>LoweredModule</code> module contains <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L52-L59">imports</a>, but in a position-independent form.
The <code>SourceMap</code> contains a mapping from position-independent imports to
(position-dependent) syntax nodes.</p>
<p>The result of this basic lowering query changes after every modification. But
there's an intermediate <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L97-L103">projection query</a> which returns only the first
position-independent part of the lowering. The result of this query is stable.
Naturally, name resolution <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/query_definitions.rs#L49">uses</a> this stable projection query.</p>
<h2>Type inference</h2>
<p>First of all, implementation of type inference in rust-analyzer was spearheaded
by <a href="https://github.com/flodiebold">@flodiebold</a>. <a href="https://github.com/rust-analyzer/rust-analyzer/pull/327">#327</a> was an awesome Christmas present, thank you, Florian!</p>
<p>Type inference runs on per-function granularity and uses the patterns we've
discussed previously.</p>
<p>First, we <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/expr.rs">lower the AST</a> of a function body into a position-independent
representation. In this representation, each expression is assigned a
<a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/expr.rs#L13-L15">positional ID</a>. Alongside the lowered expression, <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/expr.rs#L41-L44">a source map</a> is produced,
which maps between expression ids and original syntax. This lowering step also
deals with "incomplete" source trees by replacing missing expressions by an
explicit <code>Missing</code> expression.</p>
<p>Given the lowered body of the function, we can now run <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/ty.rs#L1208-L1223">type inference</a> and
construct a mapping from <code>ExprId</code>s to types.</p>
<h2>Tying it all together: completion</h2>
<p>To conclude the overview of the rust-analyzer, let's trace the request for
(type-inference powered!) code completion!</p>
<p>We start by <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L203">receiving a message</a> from the language client. We decode the
message as a request for completion and <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L428">schedule it on the threadpool</a>. This is
the place where we <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L436-L442">catch</a> canceled errors if, immediately after completion, the
client sends some modification.</p>
<p>In <a href="https://salsa.zulipchat.com/#narrow/stream/181542-rfcs.2Fsalsa-query-group/topic/design.20next.20steps">the handler</a>, we deserialize LSP requests into rust-analyzer specific data
types (by converting a file url into a numeric <code>FileId</code>), <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L439-L444">ask analysis for
completion</a> and serialize results into the LSP.</p>
<p>The <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion.rs#L46-L62">completion implementation</a> is finally the place where we start doing the actual
work. The first step is to collect the <code>CompletionContext</code> -- a struct which
describes the cursor position in terms of Rust syntax and semantics. For
example, <code>function_syntax: Option&lt;&amp;'a ast::FnDef&gt;</code> stores a reference to
the enclosing function <em>syntax</em>, while <code>function: Option&lt;hir::Function&gt;</code> is the
<code>Def</code> for this function.</p>
<p>To construct the context, we first do an <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L72-L75">"IntelliJ Trick"</a>: we insert a dummy
identifier at the cursor's position and parse this modified file, to get a
reasonably looking syntax tree. Then we do a bunch of "classification" routines
to figure out the context. For example, we <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L116-L120">find an ancestor <code>fn</code> node</a> and we get a
<a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L123">semantic model</a> for it (using the lossy <code>source_binder</code> infrastructure).</p>
<p>The second step is to run a <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion.rs#L52-L59">series of independent completion routines</a>. Let's
take a closer look at <a href="https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/complete_dot.rs#L6-L22"><code>complete_dot</code></a>, which completes fields and methods in
<code>foo.bar|</code>. First we extract a semantic function and a syntactic receiver
expression out of the <code>Context</code>. Then we run type-inference for this single
function and map our syntactic expression to <code>ExprId</code>. Using the ID, we figure
out the type of the receiver expression. Then we add all fields &amp; methods from
the type to completion.</p>
</section><div class="code-panel"><pre class="code src language-markdown"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text"><a-p>#</a-p> <a-tt>Guide to rust-analyzer</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text"><a-p>##</a-p> <a-tt>About the guide</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text">This guide describes the current state of rust-analyzer as of 2019-01-20 (git</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text">tag [guide-2019-01]). Its purpose is to document various problems and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text">architectural solutions related to the problem of building IDE-first compiler</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text">for Rust. There is a video version of this guide as well:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text">https://youtu.be/ANKBNiSWyfc.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text"><a-tu>[guide-2019-01]</a-tu>: <a-tu>https://github.com/rust-analyzer/rust-analyzer/tree/guide-2019-01</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text"><a-p>##</a-p> <a-tt>The big picture</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text">On the highest possible level, rust-analyzer is a stateful component. A client may</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text">apply changes to the analyzer (new contents of `foo.rs` file is &quot;fn main() {}&quot;)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text">and it may ask semantic questions about the current state (what is the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text">definition of the identifier with offset 92 in file `bar.rs`?). Two important</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text">properties hold:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text"><a-p>* </a-p>Analyzer does not do any I/O. It starts in an empty state and all input data is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text"><a-p>  </a-p>provided via `apply_change` API.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text"><a-p>* Only queries about the current state are supported. One can, of course,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text"><a-p>  simulate undo and redo by keeping a log of changes and inverse changes respectively.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L27" href="#L27">27</a><span class="code-text"><a-p>## </a-p><a-tt>IDE API</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L28" href="#L28">28</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text"><a-p>To see the bigger picture of how the IDE features work, let&#39;s take a look at the [`AnalysisHost`] and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L30" href="#L30">30</a><span class="code-text"><a-p>[`Analysis`] pair of types. `AnalysisHost` has three methods:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L31" href="#L31">31</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L32" href="#L32">32</a><span class="code-text"><a-p>* `default()` for creating an empty analysis instance</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L33" href="#L33">33</a><span class="code-text"><a-p>* `apply_change(&amp;mut self)` to make changes (this is how you get from an empty</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L34" href="#L34">34</a><span class="code-text"><a-p>  state to something interesting)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L35" href="#L35">35</a><span class="code-text"><a-p>* `analysis(&amp;self)` to get an instance of `Analysis`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L36" href="#L36">36</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L37" href="#L37">37</a><span class="code-text"><a-p>`Analysis` has a ton of methods for IDEs, like `goto_definition`, or</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L38" href="#L38">38</a><span class="code-text"><a-p>`completions`. Both inputs and outputs of `Analysis`&#39; methods are formulated in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L39" href="#L39">39</a><span class="code-text"><a-p>terms of files and offsets, and **not** in terms of Rust concepts like structs,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L40" href="#L40">40</a><span class="code-text"><a-p>traits, etc. The &quot;typed&quot; API with Rust specific types is slightly lower in the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L41" href="#L41">41</a><span class="code-text"><a-p>stack, we&#39;ll talk about it later.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L42" href="#L42">42</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L43" href="#L43">43</a><span class="code-text"><a-tu>[`AnalysisHost`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L265-L284</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L44" href="#L44">44</a><span class="code-text"><a-tu>[`Analysis`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L291-L478</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L45" href="#L45">45</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L46" href="#L46">46</a><span class="code-text"><a-p>The reason for this separation of `Analysis` and `AnalysisHost` is that we want to apply</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L47" href="#L47">47</a><span class="code-text"><a-p>changes &quot;uniquely&quot;, but we might also want to fork an `Analysis` and send it to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L48" href="#L48">48</a><span class="code-text"><a-p>another thread for background processing. That is, there is only a single</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L49" href="#L49">49</a><span class="code-text"><a-p>`AnalysisHost`, but there may be several (equivalent) `Analysis`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L50" href="#L50">50</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L51" href="#L51">51</a><span class="code-text"><a-p>Note that all of the `Analysis` API return `Cancellable&lt;T&gt;`. This is required to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L52" href="#L52">52</a><span class="code-text"><a-p>be responsive in an IDE setting. Sometimes a long-running query is being computed</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L53" href="#L53">53</a><span class="code-text"><a-p>and the user types something in the editor and asks for completion. In this</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L54" href="#L54">54</a><span class="code-text"><a-p>case, we cancel the long-running computation (so it returns `Err(Cancelled)`),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L55" href="#L55">55</a><span class="code-text"><a-p>apply the change and execute request for completion. We never use stale data to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L56" href="#L56">56</a><span class="code-text"><a-p>answer requests. Under the cover, `AnalysisHost` &quot;remembers&quot; all outstanding</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L57" href="#L57">57</a><span class="code-text"><a-p>`Analysis` instances. The `AnalysisHost::apply_change` method cancels all</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L58" href="#L58">58</a><span class="code-text"><a-p>`Analysis`es, blocks until all of them are `Dropped` and then applies changes</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L59" href="#L59">59</a><span class="code-text"><a-p>in-place. This may be familiar to Rustaceans who use read-write locks for interior</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L60" href="#L60">60</a><span class="code-text"><a-p>mutability.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L61" href="#L61">61</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L62" href="#L62">62</a><span class="code-text"><a-p>Next, let&#39;s talk about what the inputs to the `Analysis` are, precisely.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L63" href="#L63">63</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L64" href="#L64">64</a><span class="code-text"><a-p>## </a-p><a-tt>Inputs</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L65" href="#L65">65</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L66" href="#L66">66</a><span class="code-text"><a-p>Rust Analyzer never does any I/O itself, all inputs get passed explicitly via</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L67" href="#L67">67</a><span class="code-text"><a-p>the `AnalysisHost::apply_change` method, which accepts a single argument, a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L68" href="#L68">68</a><span class="code-text"><a-p>`Change`. [`Change`] is a builder for a single change</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L69" href="#L69">69</a><span class="code-text"><a-p>&quot;transaction&quot;, so it suffices to study its methods to understand all of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L70" href="#L70">70</a><span class="code-text"><a-p>input data.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L71" href="#L71">71</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L72" href="#L72">72</a><span class="code-text"><a-tu>[`Change`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/base_db/src/change.rs#L14-L89</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L73" href="#L73">73</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L74" href="#L74">74</a><span class="code-text"><a-p>The `(add|change|remove)_file` methods control the set of the input files, where</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L75" href="#L75">75</a><span class="code-text"><a-p>each file has an integer id (`FileId`, picked by the client), text (`String`)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L76" href="#L76">76</a><span class="code-text"><a-p>and a filesystem path. Paths are tricky; they&#39;ll be explained below, in source roots</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L77" href="#L77">77</a><span class="code-text"><a-p>section, together with the `add_root` method. The `add_library` method allows us to add a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L78" href="#L78">78</a><span class="code-text"><a-p>group of files which are assumed to rarely change. It&#39;s mostly an optimization</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L79" href="#L79">79</a><span class="code-text"><a-p>and does not change the fundamental picture.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L80" href="#L80">80</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L81" href="#L81">81</a><span class="code-text"><a-p>The `set_crate_graph` method allows us to control how the input files are partitioned</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L82" href="#L82">82</a><span class="code-text"><a-p>into compilation units -- crates. It also controls (in theory, not implemented</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L83" href="#L83">83</a><span class="code-text"><a-p>yet) `cfg` flags. `CrateGraph` is a directed acyclic graph of crates. Each crate</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L84" href="#L84">84</a><span class="code-text"><a-p>has a root `FileId`, a set of active `cfg` flags and a set of dependencies. Each</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L85" href="#L85">85</a><span class="code-text"><a-p>dependency is a pair of a crate and a name. It is possible to have two crates</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L86" href="#L86">86</a><span class="code-text"><a-p>with the same root `FileId` but different `cfg`-flags/dependencies. This model</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L87" href="#L87">87</a><span class="code-text"><a-p>is lower than Cargo&#39;s model of packages: each Cargo package consists of several</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L88" href="#L88">88</a><span class="code-text"><a-p>targets, each of which is a separate crate (or several crates, if you try</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L89" href="#L89">89</a><span class="code-text"><a-p>different feature combinations).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L90" href="#L90">90</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L91" href="#L91">91</a><span class="code-text"><a-p>Procedural macros should become inputs as well, but currently they are not</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L92" href="#L92">92</a><span class="code-text"><a-p>supported. Procedural macro will be a black box `Box&lt;dyn Fn(TokenStream) -&gt; TokenStream&gt;`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L93" href="#L93">93</a><span class="code-text"><a-p>function, and will be inserted into the crate graph just like dependencies.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L94" href="#L94">94</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L95" href="#L95">95</a><span class="code-text"><a-p>Soon we&#39;ll talk how we build an LSP server on top of `Analysis`, but first,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L96" href="#L96">96</a><span class="code-text"><a-p>let&#39;s deal with that paths issue.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L97" href="#L97">97</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L98" href="#L98">98</a><span class="code-text"><a-p>## </a-p><a-tt>Source roots (a.k.a. &quot;Filesystems are horrible&quot;)</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L99" href="#L99">99</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L100" href="#L100">100</a><span class="code-text"><a-p>This is a non-essential section, feel free to skip.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L101" href="#L101">101</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L102" href="#L102">102</a><span class="code-text"><a-p>The previous section said that the filesystem path is an attribute of a file,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L103" href="#L103">103</a><span class="code-text"><a-p>but this is not the whole truth. Making it an absolute `PathBuf` will be bad for</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L104" href="#L104">104</a><span class="code-text"><a-p>several reasons. First, filesystems are full of (platform-dependent) edge cases:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L105" href="#L105">105</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L106" href="#L106">106</a><span class="code-text"><a-p>* It&#39;s hard (requires a syscall) to decide if two paths are equivalent.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L107" href="#L107">107</a><span class="code-text"><a-p>* Some filesystems are case-sensitive (e.g. macOS).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L108" href="#L108">108</a><span class="code-text"><a-p>* Paths are not necessarily UTF-8.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L109" href="#L109">109</a><span class="code-text"><a-p>* Symlinks can form cycles.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L110" href="#L110">110</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L111" href="#L111">111</a><span class="code-text"><a-p>Second, this might hurt the reproducibility and hermeticity of builds. In theory,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L112" href="#L112">112</a><span class="code-text"><a-p>moving a project from `/foo/bar/my-project` to `/spam/eggs/my-project` should</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L113" href="#L113">113</a><span class="code-text"><a-p>not change a bit in the output. However, if the absolute path is a part of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L114" href="#L114">114</a><span class="code-text"><a-p>input, it is at least in theory observable, and *could* affect the output.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L115" href="#L115">115</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L116" href="#L116">116</a><span class="code-text"><a-p>Yet another problem is that we really *really* want to avoid doing I/O, but with</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L117" href="#L117">117</a><span class="code-text"><a-p>Rust the set of &quot;input&quot; files is not necessarily known up-front. In theory, you</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L118" href="#L118">118</a><span class="code-text"><a-p>can have `#[path=&quot;/dev/random&quot;] mod foo;`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L119" href="#L119">119</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L120" href="#L120">120</a><span class="code-text"><a-p>To solve (or explicitly refuse to solve) these problems rust-analyzer uses the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L121" href="#L121">121</a><span class="code-text"><a-p>concept of a &quot;source root&quot;. Roughly speaking, source roots are the contents of a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L122" href="#L122">122</a><span class="code-text"><a-p>directory on a file systems, like `/home/matklad/projects/rustraytracer/**.rs`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L123" href="#L123">123</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L124" href="#L124">124</a><span class="code-text"><a-p>More precisely, all files (`FileId`s) are partitioned into disjoint</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L125" href="#L125">125</a><span class="code-text"><a-p>`SourceRoot`s. Each file has a relative UTF-8 path within the `SourceRoot`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L126" href="#L126">126</a><span class="code-text"><a-p>`SourceRoot` has an identity (integer ID). Crucially, the root path of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L127" href="#L127">127</a><span class="code-text"><a-p>source root itself is unknown to the analyzer: A client is supposed to maintain a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L128" href="#L128">128</a><span class="code-text"><a-p>mapping between `SourceRoot` IDs (which are assigned by the client) and actual</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L129" href="#L129">129</a><span class="code-text"><a-p>`PathBuf`s. `SourceRoot`s give a sane tree model of the file system to the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L130" href="#L130">130</a><span class="code-text"><a-p>analyzer.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L131" href="#L131">131</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L132" href="#L132">132</a><span class="code-text"><a-p>Note that `mod`, `#[path]` and `include!()` can only reference files from the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L133" href="#L133">133</a><span class="code-text"><a-p>same source root. It is of course possible to explicitly add extra files to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L134" href="#L134">134</a><span class="code-text"><a-p>the source root, even `/dev/random`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L135" href="#L135">135</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L136" href="#L136">136</a><span class="code-text"><a-p>## </a-p><a-tt>Language Server Protocol</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L137" href="#L137">137</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L138" href="#L138">138</a><span class="code-text"><a-p>Now let&#39;s see how the `Analysis` API is exposed via the JSON RPC based language server protocol. The</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L139" href="#L139">139</a><span class="code-text"><a-p>hard part here is managing changes (which can come either from the file system</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L140" href="#L140">140</a><span class="code-text"><a-p>or from the editor) and concurrency (we want to spawn background jobs for things</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L141" href="#L141">141</a><span class="code-text"><a-p>like syntax highlighting). We use the event loop pattern to manage the zoo, and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L142" href="#L142">142</a><span class="code-text"><a-p>the loop is the [`main_loop_inner`] function. The [`main_loop`] does a one-time</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L143" href="#L143">143</a><span class="code-text"><a-p>initialization and tearing down of the resources.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L144" href="#L144">144</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L145" href="#L145">145</a><span class="code-text"><a-tu>[`main_loop`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L51-L110</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L146" href="#L146">146</a><span class="code-text"><a-tu>[`main_loop_inner`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L156-L258</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L147" href="#L147">147</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L148" href="#L148">148</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L149" href="#L149">149</a><span class="code-text"><a-p>Let&#39;s walk through a typical analyzer session!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L150" href="#L150">150</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L151" href="#L151">151</a><span class="code-text"><a-p>First, we need to figure out what to analyze. To do this, we run `cargo</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L152" href="#L152">152</a><span class="code-text"><a-p>metadata` to learn about Cargo packages for current workspace and dependencies,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L153" href="#L153">153</a><span class="code-text"><a-p>and we run `rustc --print sysroot` and scan the &quot;sysroot&quot; (the directory containing the current Rust toolchain&#39;s files) to learn about crates like</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L154" href="#L154">154</a><span class="code-text"><a-p>`std`. Currently we load this configuration once at the start of the server, but</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L155" href="#L155">155</a><span class="code-text"><a-p>it should be possible to dynamically reconfigure it later without restart.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L156" href="#L156">156</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L157" href="#L157">157</a><span class="code-text"><a-p>[main_loop.rs#L62-L70](https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L62-L70)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L158" href="#L158">158</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L159" href="#L159">159</a><span class="code-text"><a-p>The [`ProjectModel`] we get after this step is very Cargo and sysroot specific,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L160" href="#L160">160</a><span class="code-text"><a-p>it needs to be lowered to get the input in the form of `Change`. This</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L161" href="#L161">161</a><span class="code-text"><a-p>happens in [`ServerWorldState::new`] method. Specifically</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L162" href="#L162">162</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L163" href="#L163">163</a><span class="code-text"><a-p>* Create a `SourceRoot` for each Cargo package and sysroot.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L164" href="#L164">164</a><span class="code-text"><a-p>* Schedule a filesystem scan of the roots.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L165" href="#L165">165</a><span class="code-text"><a-p>* Create an analyzer&#39;s `Crate` for each Cargo **target** and sysroot crate.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L166" href="#L166">166</a><span class="code-text"><a-p>* Setup dependencies between the crates.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L167" href="#L167">167</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L168" href="#L168">168</a><span class="code-text"><a-tu>[`ProjectModel`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/project_model.rs#L16-L20</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L169" href="#L169">169</a><span class="code-text"><a-tu>[`ServerWorldState::new`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L38-L160</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L170" href="#L170">170</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L171" href="#L171">171</a><span class="code-text"><a-p>The results of the scan (which may take a while) will be processed in the body</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L172" href="#L172">172</a><span class="code-text"><a-p>of the main loop, just like any other change. Here&#39;s where we handle:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L173" href="#L173">173</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L174" href="#L174">174</a><span class="code-text"><a-p>* [File system changes](https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L194)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L175" href="#L175">175</a><span class="code-text"><a-p>* [Changes from the editor](https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L377)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L176" href="#L176">176</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L177" href="#L177">177</a><span class="code-text"><a-p>After a single loop&#39;s turn, we group the changes into one `Change` and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L178" href="#L178">178</a><span class="code-text"><a-p>[apply] it. This always happens on the main thread and blocks the loop.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L179" href="#L179">179</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L180" href="#L180">180</a><span class="code-text"><a-tu>[apply]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L216</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L181" href="#L181">181</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L182" href="#L182">182</a><span class="code-text"><a-p>To handle requests, like [&quot;goto definition&quot;], we create an instance of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L183" href="#L183">183</a><span class="code-text"><a-p>`Analysis` and [`schedule`] the task (which consumes `Analysis`) on the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L184" href="#L184">184</a><span class="code-text"><a-p>threadpool. [The task] calls the corresponding `Analysis` method, while</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L185" href="#L185">185</a><span class="code-text"><a-p>massaging the types into the LSP representation. Keep in mind that if we are</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L186" href="#L186">186</a><span class="code-text"><a-p>executing &quot;goto definition&quot; on the threadpool and a new change comes in, the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L187" href="#L187">187</a><span class="code-text"><a-p>task will be canceled as soon as the main loop calls `apply_change` on the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L188" href="#L188">188</a><span class="code-text"><a-p>`AnalysisHost`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L189" href="#L189">189</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L190" href="#L190">190</a><span class="code-text"><a-tu>[&quot;goto definition&quot;]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L216</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L191" href="#L191">191</a><span class="code-text"><a-tu>[`schedule`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L426-L455</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L192" href="#L192">192</a><span class="code-text"><a-tu>[The task]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop/handlers.rs#L205-L223</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L193" href="#L193">193</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L194" href="#L194">194</a><span class="code-text"><a-p>This concludes the overview of the analyzer&#39;s programing *interface*. Next, let&#39;s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L195" href="#L195">195</a><span class="code-text"><a-p>dig into the implementation!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L196" href="#L196">196</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L197" href="#L197">197</a><span class="code-text"><a-p>## </a-p><a-tt>Salsa</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L198" href="#L198">198</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L199" href="#L199">199</a><span class="code-text"><a-p>The most straightforward way to implement an &quot;apply change, get analysis, repeat&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L200" href="#L200">200</a><span class="code-text"><a-p>API would be to maintain the input state and to compute all possible analysis</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L201" href="#L201">201</a><span class="code-text"><a-p>information from scratch after every change. This works, but scales poorly with</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L202" href="#L202">202</a><span class="code-text"><a-p>the size of the project. To make this fast, we need to take advantage of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L203" href="#L203">203</a><span class="code-text"><a-p>fact that most of the changes are small, and that analysis results are unlikely</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L204" href="#L204">204</a><span class="code-text"><a-p>to change significantly between invocations.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L205" href="#L205">205</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L206" href="#L206">206</a><span class="code-text"><a-p>To do this we use [salsa]: a framework for incremental on-demand computation.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L207" href="#L207">207</a><span class="code-text"><a-p>You can skip the rest of the section if you are familiar with `rustc`&#39;s red-green</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L208" href="#L208">208</a><span class="code-text"><a-p>algorithm (which is used for incremental compilation).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L209" href="#L209">209</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L210" href="#L210">210</a><span class="code-text"><a-tu>[salsa]</a-tu><a-p>: </a-p><a-tu>https://github.com/salsa-rs/salsa</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L211" href="#L211">211</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L212" href="#L212">212</a><span class="code-text"><a-p>It&#39;s better to refer to salsa&#39;s docs to learn about it. Here&#39;s a small excerpt:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L213" href="#L213">213</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L214" href="#L214">214</a><span class="code-text"><a-p>The key idea of salsa is that you define your program as a set of queries. Every</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L215" href="#L215">215</a><span class="code-text"><a-p>query is used like a function `K -&gt; V` that maps from some key of type `K` to a value</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L216" href="#L216">216</a><span class="code-text"><a-p>of type `V`. Queries come in two basic varieties:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L217" href="#L217">217</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L218" href="#L218">218</a><span class="code-text"><a-p>* **Inputs**: the base inputs to your system. You can change these whenever you</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L219" href="#L219">219</a><span class="code-text"><a-p>  like.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L220" href="#L220">220</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L221" href="#L221">221</a><span class="code-text"><a-p>* **Functions**: pure functions (no side effects) that transform your inputs</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L222" href="#L222">222</a><span class="code-text"><a-p>  into other values. The results of queries are memoized to avoid recomputing</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L223" href="#L223">223</a><span class="code-text"><a-p>  them a lot. When you make changes to the inputs, we&#39;ll figure out (fairly</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L224" href="#L224">224</a><span class="code-text"><a-p>  intelligently) when we can re-use these memoized values and when we have to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L225" href="#L225">225</a><span class="code-text"><a-p>  recompute them.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L226" href="#L226">226</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L227" href="#L227">227</a><span class="code-text"><a-p>For further discussion, its important to understand one bit of &quot;fairly</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L228" href="#L228">228</a><span class="code-text"><a-p>intelligently&quot;. Suppose we have two functions, `f1` and `f2`, and one input,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L229" href="#L229">229</a><span class="code-text"><a-p>`z`. We call `f1(X)` which in turn calls `f2(Y)` which inspects `i(Z)`. `i(Z)`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L230" href="#L230">230</a><span class="code-text"><a-p>returns some value `V1`, `f2` uses that and returns `R1`, `f1` uses that and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L231" href="#L231">231</a><span class="code-text"><a-p>returns `O`. Now, let&#39;s change `i` at `Z` to `V2` from `V1` and try to compute</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L232" href="#L232">232</a><span class="code-text"><a-p>`f1(X)` again. Because `f1(X)` (transitively) depends on `i(Z)`, we can&#39;t just</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L233" href="#L233">233</a><span class="code-text"><a-p>reuse its value as is. However, if `f2(Y)` is *still* equal to `R1` (despite</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L234" href="#L234">234</a><span class="code-text"><a-p>`i`&#39;s change), we, in fact, *can* reuse `O` as result of `f1(X)`. And that&#39;s how</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L235" href="#L235">235</a><span class="code-text"><a-p>salsa works: it recomputes results in *reverse* order, starting from inputs and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L236" href="#L236">236</a><span class="code-text"><a-p>progressing towards outputs, stopping as soon as it sees an intermediate value</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L237" href="#L237">237</a><span class="code-text"><a-p>that hasn&#39;t changed. If this sounds confusing to you, don&#39;t worry: it is</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L238" href="#L238">238</a><span class="code-text"><a-p>confusing. This illustration by @killercup might help:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L239" href="#L239">239</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L240" href="#L240">240</a><span class="code-text"><a-p>&lt;</a-p><a-tg>img</a-tg><a-p> </a-p><a-at>alt</a-at><a-p>=&quot;</a-p><a-s>step 1</a-s><a-p>&quot; </a-p><a-at>src</a-at><a-p>=&quot;</a-p><a-s>https://user-images.githubusercontent.com/1711539/51460907-c5484780-1d6d-11e9-9cd2-d6f62bd746e0.png</a-s><a-p>&quot; </a-p><a-at>width</a-at><a-p>=&quot;</a-p><a-s>50%</a-s><a-p>&quot;&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L241" href="#L241">241</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L242" href="#L242">242</a><span class="code-text"><a-p>&lt;</a-p><a-tg>img</a-tg><a-p> </a-p><a-at>alt</a-at><a-p>=&quot;</a-p><a-s>step 2</a-s><a-p>&quot; </a-p><a-at>src</a-at><a-p>=&quot;</a-p><a-s>https://user-images.githubusercontent.com/1711539/51460915-c9746500-1d6d-11e9-9a77-27d33a0c51b5.png</a-s><a-p>&quot; </a-p><a-at>width</a-at><a-p>=&quot;</a-p><a-s>50%</a-s><a-p>&quot;&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L243" href="#L243">243</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L244" href="#L244">244</a><span class="code-text"><a-p>&lt;</a-p><a-tg>img</a-tg><a-p> </a-p><a-at>alt</a-at><a-p>=&quot;</a-p><a-s>step 3</a-s><a-p>&quot; </a-p><a-at>src</a-at><a-p>=&quot;</a-p><a-s>https://user-images.githubusercontent.com/1711539/51460920-cda08280-1d6d-11e9-8d96-a782aa57a4d4.png</a-s><a-p>&quot; </a-p><a-at>width</a-at><a-p>=&quot;</a-p><a-s>50%</a-s><a-p>&quot;&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L245" href="#L245">245</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L246" href="#L246">246</a><span class="code-text"><a-p>&lt;</a-p><a-tg>img</a-tg><a-p> </a-p><a-at>alt</a-at><a-p>=&quot;</a-p><a-s>step 4</a-s><a-p>&quot; </a-p><a-at>src</a-at><a-p>=&quot;</a-p><a-s>https://user-images.githubusercontent.com/1711539/51460927-d1340980-1d6d-11e9-851e-13c149d5c406.png</a-s><a-p>&quot; </a-p><a-at>width</a-at><a-p>=&quot;</a-p><a-s>50%</a-s><a-p>&quot;&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L247" href="#L247">247</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L248" href="#L248">248</a><span class="code-text"><a-p>## </a-p><a-tt>Salsa Input Queries</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L249" href="#L249">249</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L250" href="#L250">250</a><span class="code-text"><a-p>All analyzer information is stored in a salsa database. `Analysis` and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L251" href="#L251">251</a><span class="code-text"><a-p>`AnalysisHost` types are newtype wrappers for [`RootDatabase`] -- a salsa</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L252" href="#L252">252</a><span class="code-text"><a-p>database.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L253" href="#L253">253</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L254" href="#L254">254</a><span class="code-text"><a-tu>[`RootDatabase`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/db.rs#L88-L134</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L255" href="#L255">255</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L256" href="#L256">256</a><span class="code-text"><a-p>Salsa input queries are defined in [`FilesDatabase`] (which is a part of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L257" href="#L257">257</a><span class="code-text"><a-p>`RootDatabase`). They closely mirror the familiar `Change` structure:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L258" href="#L258">258</a><span class="code-text"><a-p>indeed, what `apply_change` does is it sets the values of input queries.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L259" href="#L259">259</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L260" href="#L260">260</a><span class="code-text"><a-tu>[`FilesDatabase`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/base_db/src/input.rs#L150-L174</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L261" href="#L261">261</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L262" href="#L262">262</a><span class="code-text"><a-p>## </a-p><a-tt>From text to semantic model</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L263" href="#L263">263</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L264" href="#L264">264</a><span class="code-text"><a-p>The bulk of the rust-analyzer is transforming input text into a semantic model of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L265" href="#L265">265</a><span class="code-text"><a-p>Rust code: a web of entities like modules, structs, functions and traits.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L266" href="#L266">266</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L267" href="#L267">267</a><span class="code-text"><a-p>An important fact to realize is that (unlike most other languages like C# or</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L268" href="#L268">268</a><span class="code-text"><a-p>Java) there is not a one-to-one mapping between the source code and the semantic model. A</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L269" href="#L269">269</a><span class="code-text"><a-p>single function definition in the source code might result in several semantic</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L270" href="#L270">270</a><span class="code-text"><a-p>functions: for example, the same source file might get included as a module in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L271" href="#L271">271</a><span class="code-text"><a-p>several crates or a single crate might be present in the compilation DAG</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L272" href="#L272">272</a><span class="code-text"><a-p>several times, with different sets of `cfg`s enabled. The IDE-specific task of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L273" href="#L273">273</a><span class="code-text"><a-p>mapping source code into a semantic model is inherently imprecise for</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L274" href="#L274">274</a><span class="code-text"><a-p>this reason and gets handled by the [`source_binder`].</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L275" href="#L275">275</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L276" href="#L276">276</a><span class="code-text"><a-tu>[`source_binder`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/source_binder.rs</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L277" href="#L277">277</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L278" href="#L278">278</a><span class="code-text"><a-p>The semantic interface is declared in the [`code_model_api`] module. Each entity is</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L279" href="#L279">279</a><span class="code-text"><a-p>identified by an integer ID and has a bunch of methods which take a salsa database</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L280" href="#L280">280</a><span class="code-text"><a-p>as an argument and returns other entities (which are also IDs). Internally, these</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L281" href="#L281">281</a><span class="code-text"><a-p>methods invoke various queries on the database to build the model on demand.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L282" href="#L282">282</a><span class="code-text"><a-p>Here&#39;s [the list of queries].</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L283" href="#L283">283</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L284" href="#L284">284</a><span class="code-text"><a-tu>[`code_model_api`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/code_model_api.rs</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L285" href="#L285">285</a><span class="code-text"><a-tu>[the list of queries]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/7e84440e25e19529e4ff8a66e521d1b06349c6ec/crates/hir/src/db.rs#L20-L106</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L286" href="#L286">286</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L287" href="#L287">287</a><span class="code-text"><a-p>The first step of building the model is parsing the source code.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L288" href="#L288">288</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L289" href="#L289">289</a><span class="code-text"><a-p>## </a-p><a-tt>Syntax trees</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L290" href="#L290">290</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L291" href="#L291">291</a><span class="code-text"><a-p>An important property of the Rust language is that each file can be parsed in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L292" href="#L292">292</a><span class="code-text"><a-p>isolation. Unlike, say, `C++`, an `include` can&#39;t change the meaning of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L293" href="#L293">293</a><span class="code-text"><a-p>syntax. For this reason, rust-analyzer can build a syntax tree for each &quot;source</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L294" href="#L294">294</a><span class="code-text"><a-p>file&quot;, which could then be reused by several semantic models if this file</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L295" href="#L295">295</a><span class="code-text"><a-p>happens to be a part of several crates.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L296" href="#L296">296</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L297" href="#L297">297</a><span class="code-text"><a-p>The representation of syntax trees that rust-analyzer uses is similar to that of `Roslyn`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L298" href="#L298">298</a><span class="code-text"><a-p>and Swift&#39;s new [libsyntax]. Swift&#39;s docs give an excellent overview of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L299" href="#L299">299</a><span class="code-text"><a-p>approach, so I skip this part here and instead outline the main characteristics</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L300" href="#L300">300</a><span class="code-text"><a-p>of the syntax trees:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L301" href="#L301">301</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L302" href="#L302">302</a><span class="code-text"><a-p>* Syntax trees are fully lossless. Converting **any** text to a syntax tree and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L303" href="#L303">303</a><span class="code-text"><a-p>  back is a total identity function. All whitespace and comments are explicitly</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L304" href="#L304">304</a><span class="code-text"><a-p>  represented in the tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L305" href="#L305">305</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L306" href="#L306">306</a><span class="code-text"><a-p>* Syntax nodes have generic `(next|previous)_sibling`, `parent`,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L307" href="#L307">307</a><span class="code-text"><a-p>  `(first|last)_child` functions. You can get from any one node to any other</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L308" href="#L308">308</a><span class="code-text"><a-p>  node in the file using only these functions.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L309" href="#L309">309</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L310" href="#L310">310</a><span class="code-text"><a-p>* Syntax nodes know their range (start offset and length) in the file.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L311" href="#L311">311</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L312" href="#L312">312</a><span class="code-text"><a-p>* Syntax nodes share the ownership of their syntax tree: if you keep a reference</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L313" href="#L313">313</a><span class="code-text"><a-p>  to a single function, the whole enclosing file is alive.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L314" href="#L314">314</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L315" href="#L315">315</a><span class="code-text"><a-p>* Syntax trees are immutable and the cost of replacing the subtree is</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L316" href="#L316">316</a><span class="code-text"><a-p>  proportional to the depth of the subtree. Read Swift&#39;s docs to learn how</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L317" href="#L317">317</a><span class="code-text"><a-p>  immutable + parent pointers + cheap modification is possible.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L318" href="#L318">318</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L319" href="#L319">319</a><span class="code-text"><a-p>* Syntax trees are build on best-effort basis. All accessor methods return</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L320" href="#L320">320</a><span class="code-text"><a-p>  `Option`s. The tree for `fn foo` will contain a function declaration with</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L321" href="#L321">321</a><span class="code-text"><a-p>  `None` for parameter list and body.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L322" href="#L322">322</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L323" href="#L323">323</a><span class="code-text"><a-p>* Syntax trees do not know the file they are built from, they only know about</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L324" href="#L324">324</a><span class="code-text"><a-p>  the text.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L325" href="#L325">325</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L326" href="#L326">326</a><span class="code-text"><a-p>The implementation is based on the generic [rowan] crate on top of which a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L327" href="#L327">327</a><span class="code-text"><a-p>[rust-specific] AST is generated.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L328" href="#L328">328</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L329" href="#L329">329</a><span class="code-text"><a-tu>[libsyntax]</a-tu><a-p>: </a-p><a-tu>https://github.com/apple/swift/tree/5e2c815edfd758f9b1309ce07bfc01c4bc20ec23/lib/Syntax</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L330" href="#L330">330</a><span class="code-text"><a-tu>[rowan]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rowan/tree/100a36dc820eb393b74abe0d20ddf99077b61f88</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L331" href="#L331">331</a><span class="code-text"><a-tu>[rust-specific]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_syntax/src/ast/generated.rs</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L332" href="#L332">332</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L333" href="#L333">333</a><span class="code-text"><a-p>The next step in constructing the semantic model is ...</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L334" href="#L334">334</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L335" href="#L335">335</a><span class="code-text"><a-p>## </a-p><a-tt>Building a Module Tree</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L336" href="#L336">336</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L337" href="#L337">337</a><span class="code-text"><a-p>The algorithm for building a tree of modules is to start with a crate root</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L338" href="#L338">338</a><span class="code-text"><a-p>(remember, each `Crate` from a `CrateGraph` has a `FileId`), collect all `mod`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L339" href="#L339">339</a><span class="code-text"><a-p>declarations and recursively process child modules. This is handled by the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L340" href="#L340">340</a><span class="code-text"><a-p>[`module_tree_query`], with two slight variations.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L341" href="#L341">341</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L342" href="#L342">342</a><span class="code-text"><a-tu>[`module_tree_query`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/module_tree.rs#L116-L123</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L343" href="#L343">343</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L344" href="#L344">344</a><span class="code-text"><a-p>First, rust-analyzer builds a module tree for all crates in a source root</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L345" href="#L345">345</a><span class="code-text"><a-p>simultaneously. The main reason for this is historical (`module_tree` predates</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L346" href="#L346">346</a><span class="code-text"><a-p>`CrateGraph`), but this approach also enables accounting for files which are not</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L347" href="#L347">347</a><span class="code-text"><a-p>part of any crate. That is, if you create a file but do not include it as a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L348" href="#L348">348</a><span class="code-text"><a-p>submodule anywhere, you still get semantic completion, and you get a warning</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L349" href="#L349">349</a><span class="code-text"><a-p>about a free-floating module (the actual warning is not implemented yet).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L350" href="#L350">350</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L351" href="#L351">351</a><span class="code-text"><a-p>The second difference is that `module_tree_query` does not *directly* depend on</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L352" href="#L352">352</a><span class="code-text"><a-p>the &quot;parse&quot; query (which is confusingly called `source_file`). Why would calling</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L353" href="#L353">353</a><span class="code-text"><a-p>the parse directly be bad? Suppose the user changes the file slightly, by adding</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L354" href="#L354">354</a><span class="code-text"><a-p>an insignificant whitespace. Adding whitespace changes the parse tree (because</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L355" href="#L355">355</a><span class="code-text"><a-p>it includes whitespace), and that means recomputing the whole module tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L356" href="#L356">356</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L357" href="#L357">357</a><span class="code-text"><a-p>We deal with this problem by introducing an intermediate [`submodules_query`].</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L358" href="#L358">358</a><span class="code-text"><a-p>This query processes the syntax tree and extracts a set of declared submodule</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L359" href="#L359">359</a><span class="code-text"><a-p>names. Now, changing the whitespace results in `submodules_query` being</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L360" href="#L360">360</a><span class="code-text"><a-p>re-executed for a *single* module, but because the result of this query stays</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L361" href="#L361">361</a><span class="code-text"><a-p>the same, we don&#39;t have to re-execute [`module_tree_query`]. In fact, we only</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L362" href="#L362">362</a><span class="code-text"><a-p>need to re-execute it when we add/remove new files or when we change mod</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L363" href="#L363">363</a><span class="code-text"><a-p>declarations.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L364" href="#L364">364</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L365" href="#L365">365</a><span class="code-text"><a-tu>[`submodules_query`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/module_tree.rs#L41</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L366" href="#L366">366</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L367" href="#L367">367</a><span class="code-text"><a-p>We store the resulting modules in a `Vec`-based indexed arena. The indices in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L368" href="#L368">368</a><span class="code-text"><a-p>the arena becomes module IDs. And this brings us to the next topic:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L369" href="#L369">369</a><span class="code-text"><a-p>assigning IDs in the general case.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L370" href="#L370">370</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L371" href="#L371">371</a><span class="code-text"><a-p>## </a-p><a-tt>Location Interner pattern</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L372" href="#L372">372</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L373" href="#L373">373</a><span class="code-text"><a-p>One way to assign IDs is how we&#39;ve dealt with modules: Collect all items into a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L374" href="#L374">374</a><span class="code-text"><a-p>single array in some specific order and use the index in the array as an ID. The</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L375" href="#L375">375</a><span class="code-text"><a-p>main drawback of this approach is that these IDs are not stable: Adding a new item can</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L376" href="#L376">376</a><span class="code-text"><a-p>shift the IDs of all other items. This works for modules, because adding a module is</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L377" href="#L377">377</a><span class="code-text"><a-p>a comparatively rare operation, but would be less convenient for, for example,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L378" href="#L378">378</a><span class="code-text"><a-p>functions.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L379" href="#L379">379</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L380" href="#L380">380</a><span class="code-text"><a-p>Another solution here is positional IDs: We can identify a function as &quot;the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L381" href="#L381">381</a><span class="code-text"><a-p>function with name `foo` in a ModuleId(92) module&quot;. Such locations are stable:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L382" href="#L382">382</a><span class="code-text"><a-p>adding a new function to the module (unless it is also named `foo`) does not</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L383" href="#L383">383</a><span class="code-text"><a-p>change the location. However, such &quot;ID&quot; types ceases to be a `Copy`able integer and in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L384" href="#L384">384</a><span class="code-text"><a-p>general can become pretty large if we account for nesting (for example: &quot;third parameter of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L385" href="#L385">385</a><span class="code-text"><a-p>the `foo` function of the `bar` `impl` in the `baz` module&quot;).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L386" href="#L386">386</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L387" href="#L387">387</a><span class="code-text"><a-p>[`LocationInterner`] allows us to combine the benefits of positional and numeric</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L388" href="#L388">388</a><span class="code-text"><a-p>IDs. It is a bidirectional append-only map between locations and consecutive</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L389" href="#L389">389</a><span class="code-text"><a-p>integers which can &quot;intern&quot; a location and return an integer ID back. The salsa</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L390" href="#L390">390</a><span class="code-text"><a-p>database we use includes a couple of [interners]. How to &quot;garbage collect&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L391" href="#L391">391</a><span class="code-text"><a-p>unused locations is an open question.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L392" href="#L392">392</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L393" href="#L393">393</a><span class="code-text"><a-tu>[`LocationInterner`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/base_db/src/loc2id.rs#L65-L71</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L394" href="#L394">394</a><span class="code-text"><a-tu>[interners]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/db.rs#L22-L23</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L395" href="#L395">395</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L396" href="#L396">396</a><span class="code-text"><a-p>For example, we use `LocationInterner` to assign IDs to definitions of functions,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L397" href="#L397">397</a><span class="code-text"><a-p>structs, enums, etc. The location, [`DefLoc`] contains two bits of information:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L398" href="#L398">398</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L399" href="#L399">399</a><span class="code-text"><a-p>* the ID of the module which contains the definition,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L400" href="#L400">400</a><span class="code-text"><a-p>* the ID of the specific item in the modules source code.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L401" href="#L401">401</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L402" href="#L402">402</a><span class="code-text"><a-p>We &quot;could&quot; use a text offset for the location of a particular item, but that would play</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L403" href="#L403">403</a><span class="code-text"><a-p>badly with salsa: offsets change after edits. So, as a rule of thumb, we avoid</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L404" href="#L404">404</a><span class="code-text"><a-p>using offsets, text ranges or syntax trees as keys and values for queries. What</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L405" href="#L405">405</a><span class="code-text"><a-p>we do instead is we store &quot;index&quot; of the item among all of the items of a file</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L406" href="#L406">406</a><span class="code-text"><a-p>(so, a positional based ID, but localized to a single file).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L407" href="#L407">407</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L408" href="#L408">408</a><span class="code-text"><a-tu>[`DefLoc`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/ids.rs#L127-L139</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L409" href="#L409">409</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L410" href="#L410">410</a><span class="code-text"><a-p>One thing we&#39;ve glossed over for the time being is support for macros. We have</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L411" href="#L411">411</a><span class="code-text"><a-p>only proof of concept handling of macros at the moment, but they are extremely</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L412" href="#L412">412</a><span class="code-text"><a-p>interesting from an &quot;assigning IDs&quot; perspective.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L413" href="#L413">413</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L414" href="#L414">414</a><span class="code-text"><a-p>## </a-p><a-tt>Macros and recursive locations</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L415" href="#L415">415</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L416" href="#L416">416</a><span class="code-text"><a-p>The tricky bit about macros is that they effectively create new source files.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L417" href="#L417">417</a><span class="code-text"><a-p>While we can use `FileId`s to refer to original files, we can&#39;t just assign them</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L418" href="#L418">418</a><span class="code-text"><a-p>willy-nilly to the pseudo files of macro expansion. Instead, we use a special</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L419" href="#L419">419</a><span class="code-text"><a-p>ID, [`HirFileId`] to refer to either a usual file or a macro-generated file:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L420" href="#L420">420</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L421" href="#L421">421</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L422" href="#L422">422</a><span class="code-text"><a-p>enum </a-p><a-t>HirFileId</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L423" href="#L423">423</a><span class="code-text"><a-p>    </a-p><a-cr>FileId</a-cr><a-p>(</a-p><a-t>FileId</a-t><a-p>),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L424" href="#L424">424</a><span class="code-text"><a-p>    </a-p><a-cr>Macro</a-cr><a-p>(</a-p><a-t>MacroCallId</a-t><a-p>),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L425" href="#L425">425</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L426" href="#L426">426</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L427" href="#L427">427</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L428" href="#L428">428</a><span class="code-text"><a-p>`MacroCallId` is an interned ID that specifies a particular macro invocation.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L429" href="#L429">429</a><span class="code-text"><a-p>Its `MacroCallLoc` contains:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L430" href="#L430">430</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L431" href="#L431">431</a><span class="code-text"><a-p>* `ModuleId` of the containing module</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L432" href="#L432">432</a><span class="code-text"><a-p>* `HirFileId` of the containing file or pseudo file</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L433" href="#L433">433</a><span class="code-text"><a-p>* an index of this particular macro invocation in this file (positional id</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L434" href="#L434">434</a><span class="code-text"><a-p>  again).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L435" href="#L435">435</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L436" href="#L436">436</a><span class="code-text"><a-p>Note how `HirFileId` is defined in terms of `MacroCallLoc` which is defined in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L437" href="#L437">437</a><span class="code-text"><a-p>terms of `HirFileId`! This does not recur infinitely though: any chain of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L438" href="#L438">438</a><span class="code-text"><a-p>`HirFileId`s bottoms out in `HirFileId::FileId`, that is, some source file</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L439" href="#L439">439</a><span class="code-text"><a-p>actually written by the user.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L440" href="#L440">440</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L441" href="#L441">441</a><span class="code-text"><a-tu>[`HirFileId`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/ids.rs#L18-L125</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L442" href="#L442">442</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L443" href="#L443">443</a><span class="code-text"><a-p>Now that we understand how to identify a definition, in a source or in a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L444" href="#L444">444</a><span class="code-text"><a-p>macro-generated file, we can discuss name resolution a bit.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L445" href="#L445">445</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L446" href="#L446">446</a><span class="code-text"><a-p>## </a-p><a-tt>Name resolution</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L447" href="#L447">447</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L448" href="#L448">448</a><span class="code-text"><a-p>Name resolution faces the same problem as the module tree: if we look at the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L449" href="#L449">449</a><span class="code-text"><a-p>syntax tree directly, we&#39;ll have to recompute name resolution after every</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L450" href="#L450">450</a><span class="code-text"><a-p>modification. The solution to the problem is the same: We [lower] the source code of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L451" href="#L451">451</a><span class="code-text"><a-p>each module into a position-independent representation which does not change if</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L452" href="#L452">452</a><span class="code-text"><a-p>we modify bodies of the items. After that we [loop] resolving all imports until</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L453" href="#L453">453</a><span class="code-text"><a-p>we&#39;ve reached a fixed point.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L454" href="#L454">454</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L455" href="#L455">455</a><span class="code-text"><a-tu>[lower]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L113-L117</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L456" href="#L456">456</a><span class="code-text"><a-tu>[loop]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres.rs#L186-L196</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L457" href="#L457">457</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L458" href="#L458">458</a><span class="code-text"><a-p>And, given all our preparation with IDs and a position-independent representation,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L459" href="#L459">459</a><span class="code-text"><a-p>it is satisfying to [test] that typing inside function body does not invalidate</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L460" href="#L460">460</a><span class="code-text"><a-p>name resolution results.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L461" href="#L461">461</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L462" href="#L462">462</a><span class="code-text"><a-tu>[test]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/tests.rs#L376</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L463" href="#L463">463</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L464" href="#L464">464</a><span class="code-text"><a-p>An interesting fact about name resolution is that it &quot;erases&quot; all of the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L465" href="#L465">465</a><span class="code-text"><a-p>intermediate paths from the imports: in the end, we know which items are defined</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L466" href="#L466">466</a><span class="code-text"><a-p>and which items are imported in each module, but, if the import was `use</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L467" href="#L467">467</a><span class="code-text"><a-p>foo::bar::baz`, we deliberately forget what modules `foo` and `bar` resolve to.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L468" href="#L468">468</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L469" href="#L469">469</a><span class="code-text"><a-p>To serve &quot;goto definition&quot; requests on intermediate segments we need this info</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L470" href="#L470">470</a><span class="code-text"><a-p>in the IDE, however. Luckily, we need it only for a tiny fraction of imports, so we just ask</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L471" href="#L471">471</a><span class="code-text"><a-p>the module explicitly, &quot;What does the path `foo::bar` resolve to?&quot;. This is a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L472" href="#L472">472</a><span class="code-text"><a-p>general pattern: we try to compute the minimal possible amount of information</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L473" href="#L473">473</a><span class="code-text"><a-p>during analysis while allowing IDE to ask for additional specific bits.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L474" href="#L474">474</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L475" href="#L475">475</a><span class="code-text"><a-p>Name resolution is also a good place to introduce another salsa pattern used</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L476" href="#L476">476</a><span class="code-text"><a-p>throughout the analyzer:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L477" href="#L477">477</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L478" href="#L478">478</a><span class="code-text"><a-p>## </a-p><a-tt>Source Map pattern</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L479" href="#L479">479</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L480" href="#L480">480</a><span class="code-text"><a-p>Due to an obscure edge case in completion, IDE needs to know the syntax node of</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L481" href="#L481">481</a><span class="code-text"><a-p>a use statement which imported the given completion candidate. We can&#39;t just</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L482" href="#L482">482</a><span class="code-text"><a-p>store the syntax node as a part of name resolution: this will break</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L483" href="#L483">483</a><span class="code-text"><a-p>incrementality, due to the fact that syntax changes after every file</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L484" href="#L484">484</a><span class="code-text"><a-p>modification.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L485" href="#L485">485</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L486" href="#L486">486</a><span class="code-text"><a-p>We solve this problem during the lowering step of name resolution. The lowering</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L487" href="#L487">487</a><span class="code-text"><a-p>query actually produces a *pair* of outputs: `LoweredModule` and [`SourceMap`].</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L488" href="#L488">488</a><span class="code-text"><a-p>The `LoweredModule` module contains [imports], but in a position-independent form.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L489" href="#L489">489</a><span class="code-text"><a-p>The `SourceMap` contains a mapping from position-independent imports to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L490" href="#L490">490</a><span class="code-text"><a-p>(position-dependent) syntax nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L491" href="#L491">491</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L492" href="#L492">492</a><span class="code-text"><a-p>The result of this basic lowering query changes after every modification. But</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L493" href="#L493">493</a><span class="code-text"><a-p>there&#39;s an intermediate [projection query] which returns only the first</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L494" href="#L494">494</a><span class="code-text"><a-p>position-independent part of the lowering. The result of this query is stable.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L495" href="#L495">495</a><span class="code-text"><a-p>Naturally, name resolution [uses] this stable projection query.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L496" href="#L496">496</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L497" href="#L497">497</a><span class="code-text"><a-tu>[imports]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L52-L59</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L498" href="#L498">498</a><span class="code-text"><a-tu>[`SourceMap`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L52-L59</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L499" href="#L499">499</a><span class="code-text"><a-tu>[projection query]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/nameres/lower.rs#L97-L103</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L500" href="#L500">500</a><span class="code-text"><a-tu>[uses]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/query_definitions.rs#L49</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L501" href="#L501">501</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L502" href="#L502">502</a><span class="code-text"><a-p>## </a-p><a-tt>Type inference</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L503" href="#L503">503</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L504" href="#L504">504</a><span class="code-text"><a-p>First of all, implementation of type inference in rust-analyzer was spearheaded</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L505" href="#L505">505</a><span class="code-text"><a-p>by [@flodiebold]. [#327] was an awesome Christmas present, thank you, Florian!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L506" href="#L506">506</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L507" href="#L507">507</a><span class="code-text"><a-p>Type inference runs on per-function granularity and uses the patterns we&#39;ve</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L508" href="#L508">508</a><span class="code-text"><a-p>discussed previously.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L509" href="#L509">509</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L510" href="#L510">510</a><span class="code-text"><a-p>First, we [lower the AST] of a function body into a position-independent</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L511" href="#L511">511</a><span class="code-text"><a-p>representation. In this representation, each expression is assigned a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L512" href="#L512">512</a><span class="code-text"><a-p>[positional ID]. Alongside the lowered expression, [a source map] is produced,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L513" href="#L513">513</a><span class="code-text"><a-p>which maps between expression ids and original syntax. This lowering step also</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L514" href="#L514">514</a><span class="code-text"><a-p>deals with &quot;incomplete&quot; source trees by replacing missing expressions by an</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L515" href="#L515">515</a><span class="code-text"><a-p>explicit `Missing` expression.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L516" href="#L516">516</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L517" href="#L517">517</a><span class="code-text"><a-p>Given the lowered body of the function, we can now run [type inference] and</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L518" href="#L518">518</a><span class="code-text"><a-p>construct a mapping from `ExprId`s to types.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L519" href="#L519">519</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L520" href="#L520">520</a><span class="code-text"><a-tu>[@flodiebold]</a-tu><a-p>: </a-p><a-tu>https://github.com/flodiebold</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L521" href="#L521">521</a><span class="code-text"><a-tu>[#327]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/pull/327</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L522" href="#L522">522</a><span class="code-text"><a-tu>[lower the AST]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/expr.rs</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L523" href="#L523">523</a><span class="code-text"><a-tu>[positional ID]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/expr.rs#L13-L15</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L524" href="#L524">524</a><span class="code-text"><a-tu>[a source map]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/expr.rs#L41-L44</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L525" href="#L525">525</a><span class="code-text"><a-tu>[type inference]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/hir/src/ty.rs#L1208-L1223</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L526" href="#L526">526</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L527" href="#L527">527</a><span class="code-text"><a-p>## </a-p><a-tt>Tying it all together: completion</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L528" href="#L528">528</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L529" href="#L529">529</a><span class="code-text"><a-p>To conclude the overview of the rust-analyzer, let&#39;s trace the request for</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L530" href="#L530">530</a><span class="code-text"><a-p>(type-inference powered!) code completion!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L531" href="#L531">531</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L532" href="#L532">532</a><span class="code-text"><a-p>We start by [receiving a message] from the language client. We decode the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L533" href="#L533">533</a><span class="code-text"><a-p>message as a request for completion and [schedule it on the threadpool]. This is</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L534" href="#L534">534</a><span class="code-text"><a-p>the place where we [catch] canceled errors if, immediately after completion, the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L535" href="#L535">535</a><span class="code-text"><a-p>client sends some modification.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L536" href="#L536">536</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L537" href="#L537">537</a><span class="code-text"><a-p>In [the handler], we deserialize LSP requests into rust-analyzer specific data</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L538" href="#L538">538</a><span class="code-text"><a-p>types (by converting a file url into a numeric `FileId`), [ask analysis for</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L539" href="#L539">539</a><span class="code-text"><a-p>completion] and serialize results into the LSP.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L540" href="#L540">540</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L541" href="#L541">541</a><span class="code-text"><a-p>The [completion implementation] is finally the place where we start doing the actual</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L542" href="#L542">542</a><span class="code-text"><a-p>work. The first step is to collect the `CompletionContext` -- a struct which</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L543" href="#L543">543</a><span class="code-text"><a-p>describes the cursor position in terms of Rust syntax and semantics. For</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L544" href="#L544">544</a><span class="code-text"><a-p>example, `function_syntax: Option&lt;&amp;&#39;a ast::FnDef&gt;` stores a reference to</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L545" href="#L545">545</a><span class="code-text"><a-p>the enclosing function *syntax*, while `function: Option&lt;hir::Function&gt;` is the</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L546" href="#L546">546</a><span class="code-text"><a-p>`Def` for this function.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L547" href="#L547">547</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L548" href="#L548">548</a><span class="code-text"><a-p>To construct the context, we first do an [&quot;IntelliJ Trick&quot;]: we insert a dummy</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L549" href="#L549">549</a><span class="code-text"><a-p>identifier at the cursor&#39;s position and parse this modified file, to get a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L550" href="#L550">550</a><span class="code-text"><a-p>reasonably looking syntax tree. Then we do a bunch of &quot;classification&quot; routines</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L551" href="#L551">551</a><span class="code-text"><a-p>to figure out the context. For example, we [find an ancestor `fn` node] and we get a</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L552" href="#L552">552</a><span class="code-text"><a-p>[semantic model] for it (using the lossy `source_binder` infrastructure).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L553" href="#L553">553</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L554" href="#L554">554</a><span class="code-text"><a-p>The second step is to run a [series of independent completion routines]. Let&#39;s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L555" href="#L555">555</a><span class="code-text"><a-p>take a closer look at [`complete_dot`], which completes fields and methods in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L556" href="#L556">556</a><span class="code-text"><a-p>`foo.bar|`. First we extract a semantic function and a syntactic receiver</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L557" href="#L557">557</a><span class="code-text"><a-p>expression out of the `Context`. Then we run type-inference for this single</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L558" href="#L558">558</a><span class="code-text"><a-p>function and map our syntactic expression to `ExprId`. Using the ID, we figure</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L559" href="#L559">559</a><span class="code-text"><a-p>out the type of the receiver expression. Then we add all fields &amp; methods from</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L560" href="#L560">560</a><span class="code-text"><a-p>the type to completion.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L561" href="#L561">561</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L562" href="#L562">562</a><span class="code-text"><a-tu>[receiving a message]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L203</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L563" href="#L563">563</a><span class="code-text"><a-tu>[schedule it on the threadpool]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L428</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L564" href="#L564">564</a><span class="code-text"><a-tu>[catch]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L436-L442</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L565" href="#L565">565</a><span class="code-text"><a-tu>[the handler]</a-tu><a-p>: </a-p><a-tu>https://salsa.zulipchat.com/#narrow/stream/181542-rfcs.2Fsalsa-query-group/topic/design.20next.20steps</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L566" href="#L566">566</a><span class="code-text"><a-tu>[ask analysis for completion]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L439-L444</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L567" href="#L567">567</a><span class="code-text"><a-tu>[completion implementation]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion.rs#L46-L62</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L568" href="#L568">568</a><span class="code-text"><a-tu>[`CompletionContext`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L14-L37</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L569" href="#L569">569</a><span class="code-text"><a-tu>[&quot;IntelliJ Trick&quot;]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L72-L75</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L570" href="#L570">570</a><span class="code-text"><a-tu>[find an ancestor `fn` node]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L116-L120</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L571" href="#L571">571</a><span class="code-text"><a-tu>[semantic model]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/completion_context.rs#L123</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L572" href="#L572">572</a><span class="code-text"><a-tu>[series of independent completion routines]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion.rs#L52-L59</a-tu></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L573" href="#L573">573</a><span class="code-text"><a-tu>[`complete_dot`]</a-tu><a-p>: </a-p><a-tu>https://github.com/rust-analyzer/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/completion/complete_dot.rs#L6-L22</a-tu></span></span></pre></div></div>
</main>
</body>
</html>
