architecture.md - rls - Git at Google

 # Rust Language Server (RLS) - Architecture

 ## Preface
 In addition to the document below, an architecture overview can be found at @nrc's blog post [How the RLS works](https://www.ncameron.org/blog/how-the-rls-works/) (2017). While some bits have changed, the gist of it stays the same.

 Here we aim to explain in-depth how RLS obtains the underlying data to drive its indexing features as the context for the upcoming IDE planning and discussion at the 2019 Rust All-Hands.

 Also the [rust-analyzer](https://github.com/rust-analyzer/rust-analyzer/blob/1d53f695f0408f47c5cce5cefa471eb0e86b0db7/docs/dev/guide.md) guide is a great resource as it covers a lot of common ground.

 ## High-level overview

 At the time of writing, at the highest level RLS compiles your package/workspace (similar to `cargo check`) and reuses resulting internal data structures of the Rust compiler to power its indexing features.

 When initialized, (unless overriden by custom build command) RLS `cargo check`s the current project and collects inter-crate [1] dependency graph along with exact crate compilation invocations, which is used later to run the compiler again itself (but in-process).

 In-process compilation runs return populated internal data structures (`rls_data::Analysis`), which are further lowered and cross-referenced to expose a low-level indexing API (`rls_analysis::Analysis`) to finally be consumed by the Rust Language Server in order to answer relevant LSP [2] queries.

 The main reason we execute the compilation in-process is to optimize the
 latency - we pass the resulting data structures in-memory. For dependencies that
 don't change often (non-primary/path dependencies) we perform the compilation out of process
 once, where we dump and cache the resulting data into a JSON file, which only needs to be read once at the start of indexing.

 [1] *crate* is a single unit of compilation as compiled by `rustc`. For example, Cargo package with bin+lib has *two* crates (sometimes called *targets* by Cargo).

 [2] [*Language Server Protocol*](https://microsoft.github.io/language-server-protocol/specification) is a language-agnostic JSON-RPC protocol which serves to expose common language "smartness" operations via standardized interface, regardless of the IDE/editor used.

 ## Information flow (in-depth)
 The current flow is as follows:
 ```
 rustc -> rustc_save_analysis -> rls_data -> rls_analysis -> rls
 ```

 ### [rustc_save_analysis](https://github.com/rust-lang/rust/tree/master/compiler/rustc_save_analysis)

 The Rust compiler includes the [`rustc_save_analysis`](https://github.com/rust-lang/rust/tree/master/compiler/rustc_save_analysis) crate, which allows to dump the knowledge about the currently compiled crate. The main entry point is [`process_crate`](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L978), which walks the post-macro-expansion AST and [saves](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L1011) the collected knowledge either by [dumping to a JSON file](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L953-L965) or by [calling back with resulting data structure](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L967-L976).

 ### [rls_data](https://github.com/rust-lang/rls/tree/master/rls-data)

 As mentioned previously, the returned data structure is [`rls_data::Analysis`](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-data/src/lib.rs#L11-L26) inside the [`rls_data`](https://github.com/rust-lang/rls/tree/master/rls-data) crate:

 ```rust
 /// Basically a type alias, we refer to nodes with HIR ids.
 /// All of the below nodes are either identified by or refer to those IDs.
 type Id = rustc::hir::def_id::DefId;

 pub struct Analysis {
     ...
     /// Contains rustc invocation producing this save-analysis data. Currently
     /// used to support RLS in custom build system context, namely Buck).
     pub compilation: Option<CompilationOptions>,
     /// Path to current crate root file and current crate `GlobalCrateId`. Also
     /// includes externally referred crates' `GlobalCrateId` and their local
     /// `CrateNum` index as stored by rustc from this crate compilation PoV.
     pub prelude: Option<CratePreludeData>,
     /// Nodes of use tree forests, incl. relation, span, optional alias value
     /// and kind (extern crate, simple use or glob).
     pub imports: Vec<Import>,
     /// Main data nodes. Roughly correspond to post-expansion AST nodes, incl.
     /// span, qualified name, relations, optional signature (if a function),
     /// docs and attributes.
     pub defs: Vec<Def>,
     /// Nodes for `impl` items, incl. kind (inherent, trait impl, ...), span,
     /// children ids, docs, attributes and signature.
     pub impls: Vec<Impl>,
     /// Span which refers an `Id` of function/module/type/variable kind.
     pub refs: Vec<Ref>,
     /// Contains callsite and callee span along with macro qualified name.
     pub macro_refs: Vec<MacroRef>,
     /// Impl/SuperTrait relation between `Id`s with an associated span.
     pub relations: Vec<Relation>,
 }
 ```

 ### [rls_analysis](https://github.com/rust-lang/rls/tree/master/rls-analysis)

 This [crate](https://github.com/rust-lang/rls/tree/master/rls-analysis) is responsible for loading and stitching multiple of
 the `rls_data::Analysis` data structures into a single, coherent interface.

 Whereas `rls_data` format can be considered an implementation detail that might
 change, this crate aims to provide a 'stable' API.

 Another reason behind that is that each of those structures contains data centric
 to the crate that was being compiled - this [lowering](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-analysis/src/lowering.rs#L161)
 cross-references the data
 and indexes it, resulting in a database spanning multiple crates that can be
 queried like 'across known crates, find all references to a definition at a
 given span' or similarly.

 We are capable of updating the index with new crate data. Whenever we encounter
 a new crate, we [record and translate](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-analysis/src/lowering.rs#L122-L144)
 the crate id into our database-wide crate id mapping.

 However, if data for an already lowered crate is loaded again, we simply
 replace the definitions for a given crate and re-index.

 One interesting edge case is when we lower data for crates having the same name, such
 as binary and `#[cfg(test)]`-compiled version of it. We need to ensure we lower a given definition
 [only once](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-analysis/src/lowering.rs#L271-L276)
 , even if it technically is repeated across multiple crates.

 ### rls

 With all the data lowering logic in place, all we have to do is actually fetch
 the data - that happens inside the RLS.

 In general, apart from being an LSP server, the RLS is also concerned with
 build orchestration, and coordination of other components, such as

 * Racer for autocompletion
 * Cargo for project layout detection and initial build coordination
 * internal virtual file system (VFS) for handling in-memory text buffers,
 * rls-analysis serving as our knowledge database
 * Clippy performing additional lints
 * Rustfmt driving our formatting capabilities

 After doing initial compilation with Cargo, we cache a subgraph of the inter-crate
 dependency graph along with compilation invocations and input files for the
 crates we're interested in (inside the [primary or path-based packages](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/cargo.rs#L358-L363))
 which we later rerun manually.

 In our case Cargo is configured to use a separate target directory
 (`$target-dir/rls`) so the analysis does not interfere with regular builds.

 We hijack the Cargo build process not only to record the build orchestration
 data mentioned above but also to inject additional compiler flags forcing the compiler
 to dump the JSON save-analysis files for each dependency. This serves as an
 optimization so that we don't have to re-check dependencies in a fresh run.

 Because RLS aims to provide a truthful view of the compilation and to maintain
 parity with regular `cargo check` flow, our Cargo runs also run `build.rs` and
 proc macros initially and when needed (e.g. by modifying a file causing
 `build.rs` to be rerun).

 ## Build scheduling

 On every relevant file change we [mark files as dirty](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/notifications.rs#L113) and schedule a normal build.

 We currently discern two [build priorities](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/mod.rs#L114-L124):

 * Normal
 * Cargo

 The latter is scheduled whenever a change happened that can impact entire
 project. This includes:

 * [initial build](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/mod.rs#L328)
 * [configuration change](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/notifications.rs#L116)
 (can potentially build different set of packages)
 * [Cargo.toml change](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/notifications.rs#L264)
 (ditto)
 * [build directory](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/mod.rs#L468-L472) changed
 * [modified file](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/cargo_plan.rs#L350-L354) in a package we didn't build
 * [build.rs](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/cargo_plan.rs#L359-L360) modification

 On a normal build, we map from dirty files to dirty crates, sort those
 topologically and run rustc in-process for each crate ourselves.
 With each compilation in-process we directly
 [receive `rls_data::Analysis`](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/rustc.rs#L293-L305)
 in a callback,
 [mark corresponding files as built](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/mod.rs#L478-L490)
 and finally
 [update our analysis database](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/post_build.rs#L180-L184)
 with currently built data for each rebuilt crate.

 If there are still files that are modified after we scheduled a build (user kept
 typing), we don't mark it as done yet and schedule a regular build again).
 It's worth noting that we squash builds whenever user happened to type before
 a build kicked off (we buffer build requests not to waste work on something we
 might potentially invalidate).

 ## I/O

 As mentioned previously, we run Cargo using a separate target directory so we
 do the same kind of work that Cargo does, in addition to also saving
 JSON save-analysis files for our non-path dependencies.

 ### VFS

 To allow running analysis on unsaved in-memory text buffers, we use the
 [`rls-vfs`](https://github.com/rust-lang/rls/tree/master/rls-vfs)
 crate to act as our virtual file system.

 The Rust compiler supports using custom file providers via [`FileLoader`](https://github.com/rust-lang/rust/blame/f19851069efd6ee1fe899a469f08ad2d66e76050/compiler/rustc_span/src/source_map.rs#L98-L105) trait, which [we use](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/rustc.rs#L355-L367).

 It delegates to the real file system
 whenever there are no buffered changes to a file but serves the unsaved buffers [from the VFS](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/rustc.rs#L54) otherwise.
	# Rust Language Server (RLS) - Architecture

	## Preface
	In addition to the document below, an architecture overview can be found at @nrc's blog post [How the RLS works](https://www.ncameron.org/blog/how-the-rls-works/) (2017). While some bits have changed, the gist of it stays the same.

	Here we aim to explain in-depth how RLS obtains the underlying data to drive its indexing features as the context for the upcoming IDE planning and discussion at the 2019 Rust All-Hands.

	Also the [rust-analyzer](https://github.com/rust-analyzer/rust-analyzer/blob/1d53f695f0408f47c5cce5cefa471eb0e86b0db7/docs/dev/guide.md) guide is a great resource as it covers a lot of common ground.

	## High-level overview

	At the time of writing, at the highest level RLS compiles your package/workspace (similar to `cargo check`) and reuses resulting internal data structures of the Rust compiler to power its indexing features.

	When initialized, (unless overriden by custom build command) RLS `cargo check`s the current project and collects inter-crate [1] dependency graph along with exact crate compilation invocations, which is used later to run the compiler again itself (but in-process).

	In-process compilation runs return populated internal data structures (`rls_data::Analysis`), which are further lowered and cross-referenced to expose a low-level indexing API (`rls_analysis::Analysis`) to finally be consumed by the Rust Language Server in order to answer relevant LSP [2] queries.

	The main reason we execute the compilation in-process is to optimize the
	latency - we pass the resulting data structures in-memory. For dependencies that
	don't change often (non-primary/path dependencies) we perform the compilation out of process
	once, where we dump and cache the resulting data into a JSON file, which only needs to be read once at the start of indexing.

	[1] crate is a single unit of compilation as compiled by `rustc`. For example, Cargo package with bin+lib has two crates (sometimes called targets by Cargo).

	[2] [Language Server Protocol](https://microsoft.github.io/language-server-protocol/specification) is a language-agnostic JSON-RPC protocol which serves to expose common language "smartness" operations via standardized interface, regardless of the IDE/editor used.

	## Information flow (in-depth)
	The current flow is as follows:
	```
	rustc -> rustc_save_analysis -> rls_data -> rls_analysis -> rls
	```

	### [rustc_save_analysis](https://github.com/rust-lang/rust/tree/master/compiler/rustc_save_analysis)

	The Rust compiler includes the [`rustc_save_analysis`](https://github.com/rust-lang/rust/tree/master/compiler/rustc_save_analysis) crate, which allows to dump the knowledge about the currently compiled crate. The main entry point is [`process_crate`](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L978), which walks the post-macro-expansion AST and [saves](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L1011) the collected knowledge either by [dumping to a JSON file](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L953-L965) or by [calling back with resulting data structure](https://github.com/rust-lang/rust/blob/e08d5693609a659e45025b8ea4dbd9efa342fa68/compiler/rustc_save_analysis/src/lib.rs#L967-L976).

	### [rls_data](https://github.com/rust-lang/rls/tree/master/rls-data)

	As mentioned previously, the returned data structure is [`rls_data::Analysis`](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-data/src/lib.rs#L11-L26) inside the [`rls_data`](https://github.com/rust-lang/rls/tree/master/rls-data) crate:

	```rust
	/// Basically a type alias, we refer to nodes with HIR ids.
	/// All of the below nodes are either identified by or refer to those IDs.
	type Id = rustc::hir::def_id::DefId;

	pub struct Analysis {
	...
	/// Contains rustc invocation producing this save-analysis data. Currently
	/// used to support RLS in custom build system context, namely Buck).
	pub compilation: Option<CompilationOptions>,
	/// Path to current crate root file and current crate `GlobalCrateId`. Also
	/// includes externally referred crates' `GlobalCrateId` and their local
	/// `CrateNum` index as stored by rustc from this crate compilation PoV.
	pub prelude: Option<CratePreludeData>,
	/// Nodes of use tree forests, incl. relation, span, optional alias value
	/// and kind (extern crate, simple use or glob).
	pub imports: Vec<Import>,
	/// Main data nodes. Roughly correspond to post-expansion AST nodes, incl.
	/// span, qualified name, relations, optional signature (if a function),
	/// docs and attributes.
	pub defs: Vec<Def>,
	/// Nodes for `impl` items, incl. kind (inherent, trait impl, ...), span,
	/// children ids, docs, attributes and signature.
	pub impls: Vec<Impl>,
	/// Span which refers an `Id` of function/module/type/variable kind.
	pub refs: Vec<Ref>,
	/// Contains callsite and callee span along with macro qualified name.
	pub macro_refs: Vec<MacroRef>,
	/// Impl/SuperTrait relation between `Id`s with an associated span.
	pub relations: Vec<Relation>,
	}
	```

	### [rls_analysis](https://github.com/rust-lang/rls/tree/master/rls-analysis)

	This [crate](https://github.com/rust-lang/rls/tree/master/rls-analysis) is responsible for loading and stitching multiple of
	the `rls_data::Analysis` data structures into a single, coherent interface.

	Whereas `rls_data` format can be considered an implementation detail that might
	change, this crate aims to provide a 'stable' API.

	Another reason behind that is that each of those structures contains data centric
	to the crate that was being compiled - this [lowering](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-analysis/src/lowering.rs#L161)
	cross-references the data
	and indexes it, resulting in a database spanning multiple crates that can be
	queried like 'across known crates, find all references to a definition at a
	given span' or similarly.

	We are capable of updating the index with new crate data. Whenever we encounter
	a new crate, we [record and translate](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-analysis/src/lowering.rs#L122-L144)
	the crate id into our database-wide crate id mapping.

	However, if data for an already lowered crate is loaded again, we simply
	replace the definitions for a given crate and re-index.

	One interesting edge case is when we lower data for crates having the same name, such
	as binary and `#[cfg(test)]`-compiled version of it. We need to ensure we lower a given definition
	[only once](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls-analysis/src/lowering.rs#L271-L276)
	, even if it technically is repeated across multiple crates.

	### rls

	With all the data lowering logic in place, all we have to do is actually fetch
	the data - that happens inside the RLS.

	In general, apart from being an LSP server, the RLS is also concerned with
	build orchestration, and coordination of other components, such as

	* Racer for autocompletion
	* Cargo for project layout detection and initial build coordination
	* internal virtual file system (VFS) for handling in-memory text buffers,
	* rls-analysis serving as our knowledge database
	* Clippy performing additional lints
	* Rustfmt driving our formatting capabilities

	After doing initial compilation with Cargo, we cache a subgraph of the inter-crate
	dependency graph along with compilation invocations and input files for the
	crates we're interested in (inside the [primary or path-based packages](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/cargo.rs#L358-L363))
	which we later rerun manually.

	In our case Cargo is configured to use a separate target directory
	(`$target-dir/rls`) so the analysis does not interfere with regular builds.

	We hijack the Cargo build process not only to record the build orchestration
	data mentioned above but also to inject additional compiler flags forcing the compiler
	to dump the JSON save-analysis files for each dependency. This serves as an
	optimization so that we don't have to re-check dependencies in a fresh run.

	Because RLS aims to provide a truthful view of the compilation and to maintain
	parity with regular `cargo check` flow, our Cargo runs also run `build.rs` and
	proc macros initially and when needed (e.g. by modifying a file causing
	`build.rs` to be rerun).

	## Build scheduling

	On every relevant file change we [mark files as dirty](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/notifications.rs#L113) and schedule a normal build.

	We currently discern two [build priorities](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/mod.rs#L114-L124):

	* Normal
	* Cargo

	The latter is scheduled whenever a change happened that can impact entire
	project. This includes:

	* [initial build](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/mod.rs#L328)
	* [configuration change](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/notifications.rs#L116)
	(can potentially build different set of packages)
	* [Cargo.toml change](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/notifications.rs#L264)
	(ditto)
	* [build directory](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/mod.rs#L468-L472) changed
	* [modified file](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/cargo_plan.rs#L350-L354) in a package we didn't build
	* [build.rs](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/cargo_plan.rs#L359-L360) modification

	On a normal build, we map from dirty files to dirty crates, sort those
	topologically and run rustc in-process for each crate ourselves.
	With each compilation in-process we directly
	[receive `rls_data::Analysis`](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/rustc.rs#L293-L305)
	in a callback,
	[mark corresponding files as built](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/mod.rs#L478-L490)
	and finally
	[update our analysis database](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/actions/post_build.rs#L180-L184)
	with currently built data for each rebuilt crate.

	If there are still files that are modified after we scheduled a build (user kept
	typing), we don't mark it as done yet and schedule a regular build again).
	It's worth noting that we squash builds whenever user happened to type before
	a build kicked off (we buffer build requests not to waste work on something we
	might potentially invalidate).

	## I/O

	As mentioned previously, we run Cargo using a separate target directory so we
	do the same kind of work that Cargo does, in addition to also saving
	JSON save-analysis files for our non-path dependencies.

	### VFS

	To allow running analysis on unsaved in-memory text buffers, we use the
	[`rls-vfs`](https://github.com/rust-lang/rls/tree/master/rls-vfs)
	crate to act as our virtual file system.

	The Rust compiler supports using custom file providers via [`FileLoader`](https://github.com/rust-lang/rust/blame/f19851069efd6ee1fe899a469f08ad2d66e76050/compiler/rustc_span/src/source_map.rs#L98-L105) trait, which [we use](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/rustc.rs#L355-L367).

	It delegates to the real file system
	whenever there are no buffered changes to a file but serves the unsaved buffers [from the VFS](https://github.com/rust-lang/rls/blob/3df74381f37617ec800537c11fb0c3130f5f3616/rls/src/build/rustc.rs#L54) otherwise.