docs/dev/architecture.md

   1 # Architecture
   2
   3 This document describes the 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 See also the [guide](./guide.md), which walks through a particular snapshot of
   8 rust-analyzer code base.
   9
  10 Yet another resource is this playlist with videos about various parts of the
  11 analyzer:
  12
  13 https://www.youtube.com/playlist?list=PL85XCvVPmGQho7MZkdW-wtPtuJcFpzycE
  14
  15 Note that the guide and videos are pretty dated, this document should be in
  16 generally fresher.
  17
  18 ## The Big Picture
  19
  20 ![](https://user-images.githubusercontent.com/1711539/50114578-e8a34280-0255-11e9-902c-7cfc70747966.png)
  21
  22 On the highest level, rust-analyzer is a thing which accepts input source code
  23 from the client and produces a structured semantic model of the code.
  24
  25 More specifically, input data consists of a set of test files (`(PathBuf,
  26 String)` pairs) and information about project structure, captured in the so
  27 called `CrateGraph`. The crate graph specifies which files are crate roots,
  28 which cfg flags are specified for each crate and what dependencies exist between
  29 the crates. The analyzer keeps all this input data in memory and never does any
  30 IO. Because the input data are source code, which typically measures in tens of
  31 megabytes at most, keeping everything in memory is OK.
  32
  33 A "structured semantic model" is basically an object-oriented representation of
  34 modules, functions and types which appear in the source code. This representation
  35 is fully "resolved": all expressions have types, all references are bound to
  36 declarations, etc.
  37
  38 The client can submit a small delta of input data (typically, a change to a
  39 single file) and get a fresh code model which accounts for changes.
  40
  41 The underlying engine makes sure that model is computed lazily (on-demand) and
  42 can be quickly updated for small modifications.
  43
  44
  45 ## Code generation
  46
  47 Some of the components of this repository are generated through automatic
  48 processes. `cargo xtask codegen` runs all generation tasks. Generated code is
  49 committed to the git repository.
  50
  51 In particular, `cargo xtask codegen` generates:
  52
  53 1. [`syntax_kind/generated`](https://github.com/rust-analyzer/rust-analyzer/blob/a0be39296d2925972cacd9fbf8b5fb258fad6947/crates/ra_parser/src/syntax_kind/generated.rs)
  54   -- the set of terminals and non-terminals of rust grammar.
  55
  56 2. [`ast/generated`](https://github.com/rust-analyzer/rust-analyzer/blob/a0be39296d2925972cacd9fbf8b5fb258fad6947/crates/ra_syntax/src/ast/generated.rs)
  57   -- AST data structure.
  58
  59 3. [`doc_tests/generated`](https://github.com/rust-analyzer/rust-analyzer/blob/a0be39296d2925972cacd9fbf8b5fb258fad6947/crates/assists/src/doc_tests/generated.rs),
  60   [`test_data/parser/inline`](https://github.com/rust-analyzer/rust-analyzer/tree/a0be39296d2925972cacd9fbf8b5fb258fad6947/crates/ra_syntax/test_data/parser/inline)
  61   -- tests for assists and the parser.
  62
  63 The source for 1 and 2 is in [`ast_src.rs`](https://github.com/rust-analyzer/rust-analyzer/blob/a0be39296d2925972cacd9fbf8b5fb258fad6947/xtask/src/ast_src.rs).
  64
  65 ## Code Walk-Through
  66
  67 ### `crates/ra_syntax`, `crates/parser`
  68
  69 Rust syntax tree structure and parser. See
  70 [RFC](https://github.com/rust-lang/rfcs/pull/2256) and [./syntax.md](./syntax.md) for some design notes.
  71
  72 - [rowan](https://github.com/rust-analyzer/rowan) library is used for constructing syntax trees.
  73 - `grammar` module is the actual parser. It is a hand-written recursive descent parser, which
  74   produces a sequence of events like "start node X", "finish node Y". It works similarly to [kotlin's parser](https://github.com/JetBrains/kotlin/blob/4d951de616b20feca92f3e9cc9679b2de9e65195/compiler/frontend/src/org/jetbrains/kotlin/parsing/KotlinParsing.java),
  75   which is a good source of 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)
  76   is what we use for the definition of the Rust language.
  77 - `TreeSink` and `TokenSource` traits bridge the tree-agnostic parser from `grammar` with `rowan` trees.
  78 - `ast` provides a type safe API on top of the raw `rowan` tree.
  79 - `ast_src` description of the grammar, which is used to generate `syntax_kinds`
  80   and `ast` modules, using `cargo xtask codegen` command.
  81
  82 Tests for ra_syntax are mostly data-driven: `test_data/parser` contains subdirectories with a bunch of `.rs`
  83 (test vectors) and `.txt` files with corresponding syntax trees. During testing, we check
  84 `.rs` against `.txt`. If the `.txt` file is missing, it is created (this is how you update
  85 tests). Additionally, running `cargo xtask codegen` will walk the grammar module and collect
  86 all `// test test_name` comments into files inside `test_data/parser/inline` directory.
  87
  88 Note
  89 [`api_walkthrough`](https://github.com/rust-analyzer/rust-analyzer/blob/2fb6af89eb794f775de60b82afe56b6f986c2a40/crates/ra_syntax/src/lib.rs#L190-L348)
  90 in particular: it shows off various methods of working with syntax tree.
  91
  92 See [#93](https://github.com/rust-analyzer/rust-analyzer/pull/93) for an example PR which
  93 fixes a bug in the grammar.
  94
  95 ### `crates/base_db`
  96
  97 We use the [salsa](https://github.com/salsa-rs/salsa) crate for incremental and
  98 on-demand computation. Roughly, you can think of salsa as a key-value store, but
  99 it also can compute derived values using specified functions. The `base_db` crate
 100 provides basic infrastructure for interacting with salsa. Crucially, it
 101 defines most of the "input" queries: facts supplied by the client of the
 102 analyzer. Reading the docs of the `base_db::input` module should be useful:
 103 everything else is strictly derived from those inputs.
 104
 105 ### `crates/hir*` crates
 106
 107 HIR provides high-level "object oriented" access to Rust code.
 108
 109 The principal difference between HIR and syntax trees is that HIR is bound to a
 110 particular crate instance. That is, it has cfg flags and features applied. So,
 111 the relation between syntax and HIR is many-to-one. The `source_binder` module
 112 is responsible for guessing a HIR for a particular source position.
 113
 114 Underneath, HIR works on top of salsa, using a `HirDatabase` trait.
 115
 116 `hir_xxx` crates have a strong ECS flavor, in that they work with raw ids and
 117 directly query the database.
 118
 119 The top-level `hir` façade crate wraps ids into a more OO-flavored API.
 120
 121 ### `crates/ide`
 122
 123 A stateful library for analyzing many Rust files as they change. `AnalysisHost`
 124 is a mutable entity (clojure's atom) which holds the current state, incorporates
 125 changes and hands out `Analysis` --- an immutable and consistent snapshot of
 126 the world state at a point in time, which actually powers analysis.
 127
 128 One interesting aspect of analysis is its support for cancellation. When a
 129 change is applied to `AnalysisHost`, first all currently active snapshots are
 130 canceled. Only after all snapshots are dropped the change actually affects the
 131 database.
 132
 133 APIs in this crate are IDE centric: they take text offsets as input and produce
 134 offsets and strings as output. This works on top of rich code model powered by
 135 `hir`.
 136
 137 ### `crates/rust-analyzer`
 138
 139 An LSP implementation which wraps `ide` into a language server protocol.
 140
 141 ### `crates/vfs`
 142
 143 Although `hir` and `ide` don't do any IO, we need to be able to read
 144 files from disk at the end of the day. This is what `vfs` does. It also
 145 manages overlays: "dirty" files in the editor, whose "true" contents is
 146 different from data on disk.
 147
 148 ## Testing Infrastructure
 149
 150 Rust Analyzer has three interesting [systems
 151 boundaries](https://www.tedinski.com/2018/04/10/making-tests-a-positive-influence-on-design.html)
 152 to concentrate tests on.
 153
 154 The outermost boundary is the `rust-analyzer` crate, which defines an LSP
 155 interface in terms of stdio. We do integration testing of this component, by
 156 feeding it with a stream of LSP requests and checking responses. These tests are
 157 known as "heavy", because they interact with Cargo and read real files from
 158 disk. For this reason, we try to avoid writing too many tests on this boundary:
 159 in a statically typed language, it's hard to make an error in the protocol
 160 itself if messages are themselves typed.
 161
 162 The middle, and most important, boundary is `ide`. Unlike
 163 `rust-analyzer`, which exposes API, `ide` uses Rust API and is intended to
 164 use by various tools. Typical test creates an `AnalysisHost`, calls some
 165 `Analysis` functions and compares the results against expectation.
 166
 167 The innermost and most elaborate boundary is `hir`. It has a much richer
 168 vocabulary of types than `ide`, but the basic testing setup is the same: we
 169 create a database, run some queries, assert result.
 170
 171 For comparisons, we use the `expect` crate for snapshot testing.
 172
 173 To test various analysis corner cases and avoid forgetting about old tests, we
 174 use so-called marks. See the `marks` module in the `test_utils` crate for more.