]> git.lizzy.rs Git - rust.git/blob - src/tools/rust-analyzer/docs/dev/guide.md
Rollup merge of #105109 - rcvalle:rust-kcfi, r=bjorn3
[rust.git] / src / tools / rust-analyzer / docs / dev / guide.md
1 # Guide to rust-analyzer
2
3 ## About the guide
4
5 This guide describes the current state of rust-analyzer as of 2019-01-20 (git
6 tag [guide-2019-01]). Its purpose is to document various problems and
7 architectural solutions related to the problem of building IDE-first compiler
8 for Rust. There is a video version of this guide as well:
9 https://youtu.be/ANKBNiSWyfc.
10
11 [guide-2019-01]: https://github.com/rust-lang/rust-analyzer/tree/guide-2019-01
12
13 ## The big picture
14
15 On the highest possible level, rust-analyzer is a stateful component. A client may
16 apply changes to the analyzer (new contents of `foo.rs` file is "fn main() {}")
17 and it may ask semantic questions about the current state (what is the
18 definition of the identifier with offset 92 in file `bar.rs`?). Two important
19 properties hold:
20
21 * Analyzer does not do any I/O. It starts in an empty state and all input data is
22   provided via `apply_change` API.
23
24 * Only queries about the current state are supported. One can, of course,
25   simulate undo and redo by keeping a log of changes and inverse changes respectively.
26
27 ## IDE API
28
29 To see the bigger picture of how the IDE features work, let's take a look at the [`AnalysisHost`] and
30 [`Analysis`] pair of types. `AnalysisHost` has three methods:
31
32 * `default()` for creating an empty analysis instance
33 * `apply_change(&mut self)` to make changes (this is how you get from an empty
34   state to something interesting)
35 * `analysis(&self)` to get an instance of `Analysis`
36
37 `Analysis` has a ton of methods for IDEs, like `goto_definition`, or
38 `completions`. Both inputs and outputs of `Analysis`' methods are formulated in
39 terms of files and offsets, and **not** in terms of Rust concepts like structs,
40 traits, etc. The "typed" API with Rust specific types is slightly lower in the
41 stack, we'll talk about it later.
42
43 [`AnalysisHost`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/lib.rs#L265-L284
44 [`Analysis`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/lib.rs#L291-L478
45
46 The reason for this separation of `Analysis` and `AnalysisHost` is that we want to apply
47 changes "uniquely", but we might also want to fork an `Analysis` and send it to
48 another thread for background processing. That is, there is only a single
49 `AnalysisHost`, but there may be several (equivalent) `Analysis`.
50
51 Note that all of the `Analysis` API return `Cancellable<T>`. This is required to
52 be responsive in an IDE setting. Sometimes a long-running query is being computed
53 and the user types something in the editor and asks for completion. In this
54 case, we cancel the long-running computation (so it returns `Err(Cancelled)`),
55 apply the change and execute request for completion. We never use stale data to
56 answer requests. Under the cover, `AnalysisHost` "remembers" all outstanding
57 `Analysis` instances. The `AnalysisHost::apply_change` method cancels all
58 `Analysis`es, blocks until all of them are `Dropped` and then applies changes
59 in-place. This may be familiar to Rustaceans who use read-write locks for interior
60 mutability.
61
62 Next, let's talk about what the inputs to the `Analysis` are, precisely.
63
64 ## Inputs
65
66 rust-analyzer never does any I/O itself, all inputs get passed explicitly via
67 the `AnalysisHost::apply_change` method, which accepts a single argument, a
68 `Change`. [`Change`] is a builder for a single change
69 "transaction", so it suffices to study its methods to understand all of the
70 input data.
71
72 [`Change`]: https://github.com/rust-lang/rust-analyzer/blob/master/crates/base_db/src/change.rs#L14-L89
73
74 The `(add|change|remove)_file` methods control the set of the input files, where
75 each file has an integer id (`FileId`, picked by the client), text (`String`)
76 and a filesystem path. Paths are tricky; they'll be explained below, in source roots
77 section, together with the `add_root` method. The `add_library` method allows us to add a
78 group of files which are assumed to rarely change. It's mostly an optimization
79 and does not change the fundamental picture.
80
81 The `set_crate_graph` method allows us to control how the input files are partitioned
82 into compilation units -- crates. It also controls (in theory, not implemented
83 yet) `cfg` flags. `CrateGraph` is a directed acyclic graph of crates. Each crate
84 has a root `FileId`, a set of active `cfg` flags and a set of dependencies. Each
85 dependency is a pair of a crate and a name. It is possible to have two crates
86 with the same root `FileId` but different `cfg`-flags/dependencies. This model
87 is lower than Cargo's model of packages: each Cargo package consists of several
88 targets, each of which is a separate crate (or several crates, if you try
89 different feature combinations).
90
91 Procedural macros are inputs as well, roughly modeled as a crate with a bunch of
92 additional black box `dyn Fn(TokenStream) -> TokenStream` functions.
93
94 Soon we'll talk how we build an LSP server on top of `Analysis`, but first,
95 let's deal with that paths issue.
96
97 ## Source roots (a.k.a. "Filesystems are horrible")
98
99 This is a non-essential section, feel free to skip.
100
101 The previous section said that the filesystem path is an attribute of a file,
102 but this is not the whole truth. Making it an absolute `PathBuf` will be bad for
103 several reasons. First, filesystems are full of (platform-dependent) edge cases:
104
105 * It's hard (requires a syscall) to decide if two paths are equivalent.
106 * Some filesystems are case-sensitive (e.g. macOS).
107 * Paths are not necessarily UTF-8.
108 * Symlinks can form cycles.
109
110 Second, this might hurt the reproducibility and hermeticity of builds. In theory,
111 moving a project from `/foo/bar/my-project` to `/spam/eggs/my-project` should
112 not change a bit in the output. However, if the absolute path is a part of the
113 input, it is at least in theory observable, and *could* affect the output.
114
115 Yet another problem is that we really *really* want to avoid doing I/O, but with
116 Rust the set of "input" files is not necessarily known up-front. In theory, you
117 can have `#[path="/dev/random"] mod foo;`.
118
119 To solve (or explicitly refuse to solve) these problems rust-analyzer uses the
120 concept of a "source root". Roughly speaking, source roots are the contents of a
121 directory on a file systems, like `/home/matklad/projects/rustraytracer/**.rs`.
122
123 More precisely, all files (`FileId`s) are partitioned into disjoint
124 `SourceRoot`s. Each file has a relative UTF-8 path within the `SourceRoot`.
125 `SourceRoot` has an identity (integer ID). Crucially, the root path of the
126 source root itself is unknown to the analyzer: A client is supposed to maintain a
127 mapping between `SourceRoot` IDs (which are assigned by the client) and actual
128 `PathBuf`s. `SourceRoot`s give a sane tree model of the file system to the
129 analyzer.
130
131 Note that `mod`, `#[path]` and `include!()` can only reference files from the
132 same source root. It is of course possible to explicitly add extra files to
133 the source root, even `/dev/random`.
134
135 ## Language Server Protocol
136
137 Now let's see how the `Analysis` API is exposed via the JSON RPC based language server protocol. The
138 hard part here is managing changes (which can come either from the file system
139 or from the editor) and concurrency (we want to spawn background jobs for things
140 like syntax highlighting). We use the event loop pattern to manage the zoo, and
141 the loop is the [`main_loop_inner`] function. The [`main_loop`] does a one-time
142 initialization and tearing down of the resources.
143
144 [`main_loop`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L51-L110
145 [`main_loop_inner`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L156-L258
146
147
148 Let's walk through a typical analyzer session!
149
150 First, we need to figure out what to analyze. To do this, we run `cargo
151 metadata` to learn about Cargo packages for current workspace and dependencies,
152 and we run `rustc --print sysroot` and scan the "sysroot" (the directory containing the current Rust toolchain's files) to learn about crates like
153 `std`. Currently we load this configuration once at the start of the server, but
154 it should be possible to dynamically reconfigure it later without restart.
155
156 [main_loop.rs#L62-L70](https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L62-L70)
157
158 The [`ProjectModel`] we get after this step is very Cargo and sysroot specific,
159 it needs to be lowered to get the input in the form of `Change`. This
160 happens in [`ServerWorldState::new`] method. Specifically
161
162 * Create a `SourceRoot` for each Cargo package and sysroot.
163 * Schedule a filesystem scan of the roots.
164 * Create an analyzer's `Crate` for each Cargo **target** and sysroot crate.
165 * Setup dependencies between the crates.
166
167 [`ProjectModel`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/project_model.rs#L16-L20
168 [`ServerWorldState::new`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L38-L160
169
170 The results of the scan (which may take a while) will be processed in the body
171 of the main loop, just like any other change. Here's where we handle:
172
173 * [File system changes](https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L194)
174 * [Changes from the editor](https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L377)
175
176 After a single loop's turn, we group the changes into one `Change` and
177 [apply] it. This always happens on the main thread and blocks the loop.
178
179 [apply]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L216
180
181 To handle requests, like ["goto definition"], we create an instance of the
182 `Analysis` and [`schedule`] the task (which consumes `Analysis`) on the
183 threadpool. [The task] calls the corresponding `Analysis` method, while
184 massaging the types into the LSP representation. Keep in mind that if we are
185 executing "goto definition" on the threadpool and a new change comes in, the
186 task will be canceled as soon as the main loop calls `apply_change` on the
187 `AnalysisHost`.
188
189 ["goto definition"]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/server_world.rs#L216
190 [`schedule`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L426-L455
191 [The task]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop/handlers.rs#L205-L223
192
193 This concludes the overview of the analyzer's programing *interface*. Next, let's
194 dig into the implementation!
195
196 ## Salsa
197
198 The most straightforward way to implement an "apply change, get analysis, repeat"
199 API would be to maintain the input state and to compute all possible analysis
200 information from scratch after every change. This works, but scales poorly with
201 the size of the project. To make this fast, we need to take advantage of the
202 fact that most of the changes are small, and that analysis results are unlikely
203 to change significantly between invocations.
204
205 To do this we use [salsa]: a framework for incremental on-demand computation.
206 You can skip the rest of the section if you are familiar with `rustc`'s red-green
207 algorithm (which is used for incremental compilation).
208
209 [salsa]: https://github.com/salsa-rs/salsa
210
211 It's better to refer to salsa's docs to learn about it. Here's a small excerpt:
212
213 The key idea of salsa is that you define your program as a set of queries. Every
214 query is used like a function `K -> V` that maps from some key of type `K` to a value
215 of type `V`. Queries come in two basic varieties:
216
217 * **Inputs**: the base inputs to your system. You can change these whenever you
218   like.
219
220 * **Functions**: pure functions (no side effects) that transform your inputs
221   into other values. The results of queries are memoized to avoid recomputing
222   them a lot. When you make changes to the inputs, we'll figure out (fairly
223   intelligently) when we can re-use these memoized values and when we have to
224   recompute them.
225
226 For further discussion, its important to understand one bit of "fairly
227 intelligently". Suppose we have two functions, `f1` and `f2`, and one input,
228 `z`. We call `f1(X)` which in turn calls `f2(Y)` which inspects `i(Z)`. `i(Z)`
229 returns some value `V1`, `f2` uses that and returns `R1`, `f1` uses that and
230 returns `O`. Now, let's change `i` at `Z` to `V2` from `V1` and try to compute
231 `f1(X)` again. Because `f1(X)` (transitively) depends on `i(Z)`, we can't just
232 reuse its value as is. However, if `f2(Y)` is *still* equal to `R1` (despite
233 `i`'s change), we, in fact, *can* reuse `O` as result of `f1(X)`. And that's how
234 salsa works: it recomputes results in *reverse* order, starting from inputs and
235 progressing towards outputs, stopping as soon as it sees an intermediate value
236 that hasn't changed. If this sounds confusing to you, don't worry: it is
237 confusing. This illustration by @killercup might help:
238
239 <img alt="step 1" src="https://user-images.githubusercontent.com/1711539/51460907-c5484780-1d6d-11e9-9cd2-d6f62bd746e0.png" width="50%">
240
241 <img alt="step 2" src="https://user-images.githubusercontent.com/1711539/51460915-c9746500-1d6d-11e9-9a77-27d33a0c51b5.png" width="50%">
242
243 <img alt="step 3" src="https://user-images.githubusercontent.com/1711539/51460920-cda08280-1d6d-11e9-8d96-a782aa57a4d4.png" width="50%">
244
245 <img alt="step 4" src="https://user-images.githubusercontent.com/1711539/51460927-d1340980-1d6d-11e9-851e-13c149d5c406.png" width="50%">
246
247 ## Salsa Input Queries
248
249 All analyzer information is stored in a salsa database. `Analysis` and
250 `AnalysisHost` types are newtype wrappers for [`RootDatabase`] -- a salsa
251 database.
252
253 [`RootDatabase`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/db.rs#L88-L134
254
255 Salsa input queries are defined in [`FilesDatabase`] (which is a part of
256 `RootDatabase`). They closely mirror the familiar `Change` structure:
257 indeed, what `apply_change` does is it sets the values of input queries.
258
259 [`FilesDatabase`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/base_db/src/input.rs#L150-L174
260
261 ## From text to semantic model
262
263 The bulk of the rust-analyzer is transforming input text into a semantic model of
264 Rust code: a web of entities like modules, structs, functions and traits.
265
266 An important fact to realize is that (unlike most other languages like C# or
267 Java) there is not a one-to-one mapping between the source code and the semantic model. A
268 single function definition in the source code might result in several semantic
269 functions: for example, the same source file might get included as a module in
270 several crates or a single crate might be present in the compilation DAG
271 several times, with different sets of `cfg`s enabled. The IDE-specific task of
272 mapping source code into a semantic model is inherently imprecise for
273 this reason and gets handled by the [`source_binder`].
274
275 [`source_binder`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/hir/src/source_binder.rs
276
277 The semantic interface is declared in the [`code_model_api`] module. Each entity is
278 identified by an integer ID and has a bunch of methods which take a salsa database
279 as an argument and returns other entities (which are also IDs). Internally, these
280 methods invoke various queries on the database to build the model on demand.
281 Here's [the list of queries].
282
283 [`code_model_api`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/hir/src/code_model_api.rs
284 [the list of queries]: https://github.com/rust-lang/rust-analyzer/blob/7e84440e25e19529e4ff8a66e521d1b06349c6ec/crates/hir/src/db.rs#L20-L106
285
286 The first step of building the model is parsing the source code.
287
288 ## Syntax trees
289
290 An important property of the Rust language is that each file can be parsed in
291 isolation. Unlike, say, `C++`, an `include` can't change the meaning of the
292 syntax. For this reason, rust-analyzer can build a syntax tree for each "source
293 file", which could then be reused by several semantic models if this file
294 happens to be a part of several crates.
295
296 The representation of syntax trees that rust-analyzer uses is similar to that of `Roslyn`
297 and Swift's new [libsyntax]. Swift's docs give an excellent overview of the
298 approach, so I skip this part here and instead outline the main characteristics
299 of the syntax trees:
300
301 * Syntax trees are fully lossless. Converting **any** text to a syntax tree and
302   back is a total identity function. All whitespace and comments are explicitly
303   represented in the tree.
304
305 * Syntax nodes have generic `(next|previous)_sibling`, `parent`,
306   `(first|last)_child` functions. You can get from any one node to any other
307   node in the file using only these functions.
308
309 * Syntax nodes know their range (start offset and length) in the file.
310
311 * Syntax nodes share the ownership of their syntax tree: if you keep a reference
312   to a single function, the whole enclosing file is alive.
313
314 * Syntax trees are immutable and the cost of replacing the subtree is
315   proportional to the depth of the subtree. Read Swift's docs to learn how
316   immutable + parent pointers + cheap modification is possible.
317
318 * Syntax trees are build on best-effort basis. All accessor methods return
319   `Option`s. The tree for `fn foo` will contain a function declaration with
320   `None` for parameter list and body.
321
322 * Syntax trees do not know the file they are built from, they only know about
323   the text.
324
325 The implementation is based on the generic [rowan] crate on top of which a
326 [rust-specific] AST is generated.
327
328 [libsyntax]: https://github.com/apple/swift/tree/5e2c815edfd758f9b1309ce07bfc01c4bc20ec23/lib/Syntax
329 [rowan]: https://github.com/rust-analyzer/rowan/tree/100a36dc820eb393b74abe0d20ddf99077b61f88
330 [rust-specific]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_syntax/src/ast/generated.rs
331
332 The next step in constructing the semantic model is ...
333
334 ## Building a Module Tree
335
336 The algorithm for building a tree of modules is to start with a crate root
337 (remember, each `Crate` from a `CrateGraph` has a `FileId`), collect all `mod`
338 declarations and recursively process child modules. This is handled by the
339 [`module_tree_query`], with two slight variations.
340
341 [`module_tree_query`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/module_tree.rs#L115-L133
342
343 First, rust-analyzer builds a module tree for all crates in a source root
344 simultaneously. The main reason for this is historical (`module_tree` predates
345 `CrateGraph`), but this approach also enables accounting for files which are not
346 part of any crate. That is, if you create a file but do not include it as a
347 submodule anywhere, you still get semantic completion, and you get a warning
348 about a free-floating module (the actual warning is not implemented yet).
349
350 The second difference is that `module_tree_query` does not *directly* depend on
351 the "parse" query (which is confusingly called `source_file`). Why would calling
352 the parse directly be bad? Suppose the user changes the file slightly, by adding
353 an insignificant whitespace. Adding whitespace changes the parse tree (because
354 it includes whitespace), and that means recomputing the whole module tree.
355
356 We deal with this problem by introducing an intermediate [`submodules_query`].
357 This query processes the syntax tree and extracts a set of declared submodule
358 names. Now, changing the whitespace results in `submodules_query` being
359 re-executed for a *single* module, but because the result of this query stays
360 the same, we don't have to re-execute [`module_tree_query`]. In fact, we only
361 need to re-execute it when we add/remove new files or when we change mod
362 declarations.
363
364 [`submodules_query`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/module_tree.rs#L41
365
366 We store the resulting modules in a `Vec`-based indexed arena. The indices in
367 the arena becomes module IDs. And this brings us to the next topic:
368 assigning IDs in the general case.
369
370 ## Location Interner pattern
371
372 One way to assign IDs is how we've dealt with modules: Collect all items into a
373 single array in some specific order and use the index in the array as an ID. The
374 main drawback of this approach is that these IDs are not stable: Adding a new item can
375 shift the IDs of all other items. This works for modules, because adding a module is
376 a comparatively rare operation, but would be less convenient for, for example,
377 functions.
378
379 Another solution here is positional IDs: We can identify a function as "the
380 function with name `foo` in a ModuleId(92) module". Such locations are stable:
381 adding a new function to the module (unless it is also named `foo`) does not
382 change the location. However, such "ID" types ceases to be a `Copy`able integer and in
383 general can become pretty large if we account for nesting (for example: "third parameter of
384 the `foo` function of the `bar` `impl` in the `baz` module").
385
386 [`LocationInterner`] allows us to combine the benefits of positional and numeric
387 IDs. It is a bidirectional append-only map between locations and consecutive
388 integers which can "intern" a location and return an integer ID back. The salsa
389 database we use includes a couple of [interners]. How to "garbage collect"
390 unused locations is an open question.
391
392 [`LocationInterner`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_db/src/loc2id.rs#L65-L71
393 [interners]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/db.rs#L22-L23
394
395 For example, we use `LocationInterner` to assign IDs to definitions of functions,
396 structs, enums, etc. The location, [`DefLoc`] contains two bits of information:
397
398 * the ID of the module which contains the definition,
399 * the ID of the specific item in the modules source code.
400
401 We "could" use a text offset for the location of a particular item, but that would play
402 badly with salsa: offsets change after edits. So, as a rule of thumb, we avoid
403 using offsets, text ranges or syntax trees as keys and values for queries. What
404 we do instead is we store "index" of the item among all of the items of a file
405 (so, a positional based ID, but localized to a single file).
406
407 [`DefLoc`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/ids.rs#L129-L139
408
409 One thing we've glossed over for the time being is support for macros. We have
410 only proof of concept handling of macros at the moment, but they are extremely
411 interesting from an "assigning IDs" perspective.
412
413 ## Macros and recursive locations
414
415 The tricky bit about macros is that they effectively create new source files.
416 While we can use `FileId`s to refer to original files, we can't just assign them
417 willy-nilly to the pseudo files of macro expansion. Instead, we use a special
418 ID, [`HirFileId`] to refer to either a usual file or a macro-generated file:
419
420 ```rust
421 enum HirFileId {
422     FileId(FileId),
423     Macro(MacroCallId),
424 }
425 ```
426
427 `MacroCallId` is an interned ID that specifies a particular macro invocation.
428 Its `MacroCallLoc` contains:
429
430 * `ModuleId` of the containing module
431 * `HirFileId` of the containing file or pseudo file
432 * an index of this particular macro invocation in this file (positional id
433   again).
434
435 Note how `HirFileId` is defined in terms of `MacroCallLoc` which is defined in
436 terms of `HirFileId`! This does not recur infinitely though: any chain of
437 `HirFileId`s bottoms out in `HirFileId::FileId`, that is, some source file
438 actually written by the user.
439
440 [`HirFileId`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/ids.rs#L31-L93
441
442 Now that we understand how to identify a definition, in a source or in a
443 macro-generated file, we can discuss name resolution a bit.
444
445 ## Name resolution
446
447 Name resolution faces the same problem as the module tree: if we look at the
448 syntax tree directly, we'll have to recompute name resolution after every
449 modification. The solution to the problem is the same: We [lower] the source code of
450 each module into a position-independent representation which does not change if
451 we modify bodies of the items. After that we [loop] resolving all imports until
452 we've reached a fixed point.
453
454 [lower]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/nameres/lower.rs#L113-L147
455 [loop]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/nameres.rs#L186-L196
456 And, given all our preparation with IDs and a position-independent representation,
457 it is satisfying to [test] that typing inside function body does not invalidate
458 name resolution results.
459
460 [test]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/nameres/tests.rs#L376
461
462 An interesting fact about name resolution is that it "erases" all of the
463 intermediate paths from the imports: in the end, we know which items are defined
464 and which items are imported in each module, but, if the import was `use
465 foo::bar::baz`, we deliberately forget what modules `foo` and `bar` resolve to.
466
467 To serve "goto definition" requests on intermediate segments we need this info
468 in the IDE, however. Luckily, we need it only for a tiny fraction of imports, so we just ask
469 the module explicitly, "What does the path `foo::bar` resolve to?". This is a
470 general pattern: we try to compute the minimal possible amount of information
471 during analysis while allowing IDE to ask for additional specific bits.
472
473 Name resolution is also a good place to introduce another salsa pattern used
474 throughout the analyzer:
475
476 ## Source Map pattern
477
478 Due to an obscure edge case in completion, IDE needs to know the syntax node of
479 a use statement which imported the given completion candidate. We can't just
480 store the syntax node as a part of name resolution: this will break
481 incrementality, due to the fact that syntax changes after every file
482 modification.
483
484 We solve this problem during the lowering step of name resolution. The lowering
485 query actually produces a *pair* of outputs: `LoweredModule` and [`SourceMap`].
486 The `LoweredModule` module contains [imports], but in a position-independent form.
487 The `SourceMap` contains a mapping from position-independent imports to
488 (position-dependent) syntax nodes.
489
490 The result of this basic lowering query changes after every modification. But
491 there's an intermediate [projection query] which returns only the first
492 position-independent part of the lowering. The result of this query is stable.
493 Naturally, name resolution [uses] this stable projection query.
494
495 [imports]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/nameres/lower.rs#L52-L59
496 [`SourceMap`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/nameres/lower.rs#L52-L59
497 [projection query]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/nameres/lower.rs#L97-L103
498 [uses]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/query_definitions.rs#L49
499
500 ## Type inference
501
502 First of all, implementation of type inference in rust-analyzer was spearheaded
503 by [@flodiebold]. [#327] was an awesome Christmas present, thank you, Florian!
504
505 Type inference runs on per-function granularity and uses the patterns we've
506 discussed previously.
507
508 First, we [lower the AST] of a function body into a position-independent
509 representation. In this representation, each expression is assigned a
510 [positional ID]. Alongside the lowered expression, [a source map] is produced,
511 which maps between expression ids and original syntax. This lowering step also
512 deals with "incomplete" source trees by replacing missing expressions by an
513 explicit `Missing` expression.
514
515 Given the lowered body of the function, we can now run [type inference] and
516 construct a mapping from `ExprId`s to types.
517
518 [@flodiebold]: https://github.com/flodiebold
519 [#327]: https://github.com/rust-lang/rust-analyzer/pull/327
520 [lower the AST]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/expr.rs
521 [positional ID]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/expr.rs#L13-L15
522 [a source map]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/expr.rs#L41-L44
523 [type inference]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_hir/src/ty.rs#L1208-L1223
524
525 ## Tying it all together: completion
526
527 To conclude the overview of the rust-analyzer, let's trace the request for
528 (type-inference powered!) code completion!
529
530 We start by [receiving a message] from the language client. We decode the
531 message as a request for completion and [schedule it on the threadpool]. This is
532 the place where we [catch] canceled errors if, immediately after completion, the
533 client sends some modification.
534
535 In [the handler], we deserialize LSP requests into rust-analyzer specific data
536 types (by converting a file url into a numeric `FileId`), [ask analysis for
537 completion] and serialize results into the LSP.
538
539 The [completion implementation] is finally the place where we start doing the actual
540 work. The first step is to collect the `CompletionContext` -- a struct which
541 describes the cursor position in terms of Rust syntax and semantics. For
542 example, `function_syntax: Option<&'a ast::FnDef>` stores a reference to
543 the enclosing function *syntax*, while `function: Option<hir::Function>` is the
544 `Def` for this function.
545
546 To construct the context, we first do an ["IntelliJ Trick"]: we insert a dummy
547 identifier at the cursor's position and parse this modified file, to get a
548 reasonably looking syntax tree. Then we do a bunch of "classification" routines
549 to figure out the context. For example, we [find an ancestor `fn` node] and we get a
550 [semantic model] for it (using the lossy `source_binder` infrastructure).
551
552 The second step is to run a [series of independent completion routines]. Let's
553 take a closer look at [`complete_dot`], which completes fields and methods in
554 `foo.bar|`. First we extract a semantic function and a syntactic receiver
555 expression out of the `Context`. Then we run type-inference for this single
556 function and map our syntactic expression to `ExprId`. Using the ID, we figure
557 out the type of the receiver expression. Then we add all fields & methods from
558 the type to completion.
559
560 [receiving a message]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L203
561 [schedule it on the threadpool]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L428
562 [catch]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_lsp_server/src/main_loop.rs#L436-L442
563 [the handler]: https://salsa.zulipchat.com/#narrow/stream/181542-rfcs.2Fsalsa-query-group/topic/design.20next.20steps
564 [ask analysis for completion]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ide_api/src/lib.rs#L439-L444
565 [ask analysis for completion]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/lib.rs#L439-L444
566 [completion implementation]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion.rs#L46-L62
567 [`CompletionContext`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion/completion_context.rs#L14-L37
568 ["IntelliJ Trick"]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion/completion_context.rs#L72-L75
569 [find an ancestor `fn` node]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion/completion_context.rs#L116-L120
570 [semantic model]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion/completion_context.rs#L123
571 [series of independent completion routines]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion.rs#L52-L59
572 [`complete_dot`]: https://github.com/rust-lang/rust-analyzer/blob/guide-2019-01/crates/ra_ide_api/src/completion/complete_dot.rs#L6-L22