ARCHITECTURE.md

   1 # Architecture
   2
   3 This document describes high-level architecture of rust-analyzer.
   4 If you want to familiarize yourself with the code base, you are just
   5 in the right place!
   6
   7 ## The Big Picture
   8
   9 ![](https://user-images.githubusercontent.com/1711539/50114578-e8a34280-0255-11e9-902c-7cfc70747966.png)
  10
  11 On the highest level, rust-analyzer is a thing which accepts input source code
  12 from the client and produces a structured semantic model of the code.
  13
  14 More specifically, input data consists of a set of test files (`(PathBuf,
  15 String)` pairs) and an information about project structure, the so called
  16 `CrateGraph`. Crate graph specifies which files are crate roots, which cfg flags
  17 are specified for each crate (TODO: actually implement this) and what are
  18 dependencies between the crate. The analyzer keeps all these input data in
  19 memory and never does any IO. Because the input data is source code, which
  20 typically measures in tens of megabytes at most, keeping all input data in
  21 memory is OK.
  22
  23 A "structured semantic model" is basically an object-oriented representations of
  24 modules, functions and types which appear in the source code. This representation
  25 is fully "resolved": all expressions have types, all references are bound to
  26 declarations, etc.
  27
  28 The client can submit a small delta of input data (typically, a change to a
  29 single file) and get a fresh code model which accounts for changes.
  30
  31 Underlying engine makes sure that model is computed lazily (on-demand) and can
  32 be quickly updated for small modifications.
  33
  34
  35 ## Code generation
  36
  37 Some of the components of this repository are generated through automatic
  38 processes. These are outlined below:
  39
  40 - `gen-syntax`: The kinds of tokens are reused in several places, so a generator
  41   is used. We use tera templates to generate the files listed below, based on
  42   the grammar described in [grammar.ron]:
  43   - [ast/generated.rs][ast generated] in `ra_syntax` based on
  44     [ast/generated.tera.rs][ast source]
  45   - [syntax_kinds/generated.rs][syntax_kinds generated] in `ra_syntax` based on
  46     [syntax_kinds/generated.tera.rs][syntax_kinds source]
  47
  48 [tera]: https://tera.netlify.com/
  49 [grammar.ron]: ./crates/ra_syntax/src/grammar.ron
  50 [ast generated]: ./crates/ra_syntax/src/ast/generated.rs
  51 [ast source]: ./crates/ra_syntax/src/ast/generated.rs.tera
  52 [syntax_kinds generated]: ./crates/ra_syntax/src/syntax_kinds/generated.rs
  53 [syntax_kinds source]: ./crates/ra_syntax/src/syntax_kinds/generated.rs.tera
  54
  55
  56 ## Code Walk-Through
  57
  58 ### `crates/ra_syntax`
  59
  60 Rust syntax tree structure and parser. See
  61 [RFC](https://github.com/rust-lang/rfcs/pull/2256) for some design
  62 notes.
  63
  64 - [rowan](https://github.com/rust-analyzer/rowan) library is used for constructing syntax trees.
  65 - `grammar` module is the actual parser. It is a hand-written recursive descent parsers, which
  66   produces a sequence of events like "start node X", "finish not Y". It works similarly to  [kotlin parser](https://github.com/JetBrains/kotlin/blob/4d951de616b20feca92f3e9cc9679b2de9e65195/compiler/frontend/src/org/jetbrains/kotlin/parsing/KotlinParsing.java),
  67   which is a good source for inspiration for dealing with syntax errors and incomplete input. Original [libsyntax parser](https://github.com/rust-lang/rust/blob/6b99adeb11313197f409b4f7c4083c2ceca8a4fe/src/libsyntax/parse/parser.rs)
  68   is what we use for the definition of the Rust language.
  69 - `parser_api/parser_impl` bridges the tree-agnostic parser from `grammar` with `rowan` trees.
  70   This is the thing that turns a flat list of events into a tree (see `EventProcessor`)
  71 - `ast` a type safe API on top of the raw `rowan` tree.
  72 - `grammar.ron` RON description of the grammar, which is used to
  73   generate `syntax_kinds` and `ast` modules, using `cargo gen-syntax` command.
  74 - `algo`: generic tree algorithms, including `walk` for O(1) stack
  75   space tree traversal (this is cool) and `visit` for type-driven
  76   visiting the nodes (this is double plus cool, if you understand how
  77   `Visitor` works, you understand rust-analyzer).
  78
  79 Test for ra_syntax are mostly data-driven: `tests/data/parser` contains a bunch of `.rs`
  80 (test vectors) and `.txt` files with corresponding syntax trees. During testing, we check
  81 `.rs` against `.txt`. If the `.txt` file is missing, it is created (this is how you update
  82 tests). Additionally, running `cargo gen-tests` will walk the grammar module and collect
  83 all `//test test_name` comments into files inside `tests/data` directory.
  84
  85 See [#93](https://github.com/rust-analyzer/rust-analyzer/pull/93) for an example PR which
  86 fixes a bug in the grammar.
  87
  88 ### `crates/ra_db`
  89
  90 We use [salsa][https://github.com/salsa-rs/salsa] crate for incremental and
  91 on-demand computation. Roughly, you can think of salsa as a key-value store, but
  92 it also can compute derived values using specified functions. The `ra_db` crate
  93 provides a basic infrastructure for interracting with salsa. Crucially, it
  94 defines most of the "input" queries: facts supplied by the client of the analyzer.
  95
  96 ### `crates/ra_hir`
  97
  98 HIR provides a high-level "object oriented" acess to Rust code.
  99
 100 The principal difference between HIR and syntax trees is that HIR is bound to a
 101 particular crate instance. That is, it has cfg flags and features applied (in
 102 theory, in practice this is to be implemented). So, there relation between
 103 syntax and HIR is many-to-one. The `source_binder` modules is responsible for
 104 guessing a hir for a particular source position.
 105
 106 Underneath, hir works on top of salsa, using a `HirDatabase` trait.
 107
 108 ### `crates/ra_analysis`
 109
 110 A stateful library for analyzing many Rust files as they change.
 111 `AnalysisHost` is a mutable entity (clojure's atom) which holds
 112 current state, incorporates changes and handles out `Analysis` --- an
 113 immutable consistent snapshot of world state at a point in time, which
 114 actually powers analysis.
 115
 116 One interesting aspect of analysis is its support for cancellation. When a change
 117 is applied to `AnalysisHost`, first all currently active snapshots are
 118 cancelled. Only after all snapshots are dropped the change actually affects the
 119 database.
 120
 121 ### `crates/ra_lsp_server`
 122
 123 An LSP implementation which uses `ra_analysis` for managing state and
 124 `ra_editor` for actually doing useful stuff.
 125
 126 See [#79](https://github.com/rust-analyzer/rust-analyzer/pull/79/) as an
 127 example of PR which adds a new feature to `ra_editor` and exposes it
 128 to `ra_lsp_server`.
 129
 130 ### `crates/ra_editor`
 131
 132 All IDE features which can be implemented if you only have access to a
 133 single file. `ra_editor` could be used to enhance editing of Rust code
 134 without the need to fiddle with build-systems, file
 135 synchronization and such.
 136
 137 In a sense, `ra_editor` is just a bunch of pure functions which take a
 138 syntax tree as an input.
 139
 140 The tests for `ra_editor` are `#[cfg(test)] mod tests` unit-tests spread
 141 throughout its modules.
 142
 143 ### `crates/gen_lsp_server`
 144
 145 A language server scaffold, exposing a synchronous crossbeam-channel based API.
 146 This crate handles protocol handshaking and parsing messages, while you
 147 control the message dispatch loop yourself.
 148
 149 Run with `RUST_LOG=sync_lsp_server=debug` to see all the messages.
 150
 151 ### `crates/ra_cli`
 152
 153 A CLI interface to rust-analyzer.
 154
 155 ### `crate/tools`
 156
 157 Custom Cargo tasks used to develop rust-analyzer:
 158
 159 - `cargo gen-syntax` -- generate `ast` and `syntax_kinds`
 160 - `cargo gen-tests` -- collect inline tests from grammar
 161 - `cargo install-code` -- build and install VS Code extension and server
 162
 163 ### `editors/code`
 164
 165 VS Code plugin
 166
 167
 168 ## Common workflows
 169
 170 To try out VS Code extensions, run `cargo install-code`.  This installs both the
 171 `ra_lsp_server` binary and VS Code extension. To install only the binary, use
 172 `cargo install --path crates/ra_lsp_server --force`
 173
 174 To see logs from the language server, set `RUST_LOG=info` env variable. To see
 175 all communication between the server and the client, use
 176 `RUST_LOG=gen_lsp_server=debug` (will print quite a bit of stuff).
 177
 178 To run tests, just `cargo test`.
 179
 180 To work on VS Code extension, launch code inside `editors/code` and use `F5` to
 181 launch/debug. To automatically apply formatter and linter suggestions, use `npm
 182 run fix`.
 183