Three Architectures for a Responsive IDE

Three Architectures for a Responsive IDE

@matklad, Jul 20, 2020

rust-analyzer is a new "IDE backend" for the Rust programming language.<br>Support rust-analyzer on Open Collective.

In this post, we’ll learn how to make a snappy IDE, in three different ways :-)<br>It was inspired by this excellent article about using datalog for semantic analysis: https://petevilter.me/post/datalog-typechecking/<br>The post describes only the highest-level architecture.<br>There’s much more to implementing a full-blown IDE.

Specifically, we’ll look at the backbone infrastructure of an IDE which serves two goals:

Quickly accepting new edits to source files.

Providing type information about currently opened files for highlighting, completion, etc.

Map Reduce

The first architecture is reminiscent of the map-reduce paradigm.<br>The idea is to split analysis into relatively simple indexing phase, and a separate full analysis phase.

The core constraint of indexing is that it runs on a per-file basis.<br>The indexer takes the text of a single file, parses it, and spits out some data about the file.<br>The indexer can’t touch other files.

Full analysis can read other files, and it leverages information from the index to save work.

This all sounds way too abstract, so let’s look at a specific example — Java.<br>In Java, each file starts with a package declaration.<br>The indexer concatenates the name of the package with a class name to get a fully-qualified name (FQN).<br>It also collects the set of methods declared in the class, the list of superclasses and interfaces, etc.

Per-file data is merged into an index which maps FQNs to classes.<br>Note that constructing this mapping is an embarrassingly parallel task — all files are parsed independently.<br>Moreover, this map is cheap to update.<br>When a file change arrives, this file’s contribution from the index is removed, the text of the file is changed and the indexer runs on the new text and adds the new contributions.<br>The amount of work to do is proportional to the number of changed files, and is independent from the total number of files.

Let’s see how FQN index can be used to quickly provide completion.

10<br>11<br>12<br>13<br>14<br>15<br>16<br>17<br>18<br>19<br>20<br>21<br>22<br>23<br>24<br>25<br>26<br>// File ./mypackage/Foo.java<br>package mypackage;

import java.util.*;

public class Foo {<br>public static Bar f() {<br>return new Bar();

// File ./mypackage/Bar.java<br>package mypackage;

public class Bar {<br>public void g() {}

// File ./Main.java<br>import mypackage.Foo;

public class Main {<br>public static void main(String[] args) {<br>Foo.f().

The user has just typed Foo.f()., and we need to figure out that the type of receiver expression is Bar, and suggest g as a completion.

First, as the file Main.java is modified, we run the indexer on this single file.<br>Nothing has changed (the file still contains the class Main with a static main method), so we don’t need to update the FQN index.

Next, we need to resolve the name Foo.<br>We parse the file, notice an import and look up mypackage.Foo in the FQN index.<br>In the index, we also find that Foo has a static method f, so we resolve the call as well.<br>The index also stores the return type of f, but, and this is crucial, it stores it as a string "Bar", and not as a direct reference to the class Bar.

The reason for that is import java.util.* in Foo.java.<br>Bar can refer either to java.util.Bar or to mypackage.Bar.<br>The indexer doesn’t know which one, because it can look only at the text of Foo.java.<br>In other words, while the index does store the return types of methods, it stores them in an unresolved form.

The next step is to resolve the identifier Bar in the context of Foo.java.<br>This uses the FQN index, and lands in the class mypackage.Bar.<br>There the desired method g is found.

Altogether, only three files were touched during completion.<br>The FQN index allowed us to completely ignore all the other files in the project.

One problem with the approach described thus far is that resolving types from the index requires a non-trivial amount of work.<br>This work might be duplicated if, for example, Foo.f is called several times.<br>The fix is to add a cache.<br>Name resolution results are memoized, so that the cost is paid only once.<br>The cache is blown away completely on any change — with an index, reconstructing the cache is not that costly.

To sum up, the first approach works like this:

Each file is being indexed, independently and in parallel, producing a "stub" — a set of visible top-level declarations, with unresolved types.

All stubs are merged into a single index data structure.

Name resolution and type inference work primarily off the stubs.

Name resolution is lazy (we only resolve a type from the stub when we need it) and memoized (each type is resolved only once).

The caches are completely invalidated on every change

The index is updated incrementally:

if the edit doesn’t change the file’s stub, no change to the index is required.

otherwise, old keys are removed and new keys are...