Why building a Rust LSP is hard · Rust Glancer

A long, long time ago, mighty matklad used to write great posts about how Rust tooling works. Those were great times, but alas, the last rust-analyzer blog post dates 2023 I am no matklad, but I'm building Rust Glancer, an experimental Rust LSP, for quite a while now. It's probably the most interesting and ambitious project I've worked on, and I want to share some things I've learned while working on it. This will be a (hopefully coherent) story about how Rust LSPs work, from the perspective of both rust-analyzer and Rust Glancer: how things that seem easy turn out to be hard, things that seem hard turn out to be even harder, and things I didn't expect to exist at all somehow do. Obviously, a single blog post can't cover everything, this will be a very technical but still architectural overview rather than a deep dive into any particular topic brought up along the way. Those will come as separate posts, granted I won't be lazy. Otherwise, be ready for many anecdotal chapters that have one thing in common: building an LSP means having to produce useful answers from partial information. Disclaimer: I am no expert in building LSPs, and the purpose of this post is to make readers interested in internals and caveats of LSPs rather than give an unambiguous and formal design overview. I intentionally try not to use compiler jargon, and use approximate phrasing in many places to focus on the overall meaning rather than precision. There are plenty of links in the post to more detailed/precise sources, and I recommend checking them out! Also, I have read a lot of rust-analyzer code before and during preparation of this post, but I'm no rust-analyzer maintainer; if I got some things wrong -- sorry. Where does an LSP start? LSP server has two opposite ends: the server that implements the Language Server Protocol (as in, "there is this thing I can send requests to and receive well-formed responses") and the actual state that we want to serve (as in, "the sent queries actually do what they need to do and operate over some kind of indexed state"). The first seems to be a solved problem, right? Especially given that tower-lsp-server exists. Welp, not really. Let's start there, and then we will gradually get to indexing once we actually need it. The LSP begins with a client sending an initialize request which requires you to initialize the LSP (huh). Before you respond, client won't do anything. Once you do, it sends an initialized notification, and all is good, and LSP communication starts. The problem is: when do you respond to this request? Once the server starts, you have nothing. You don't know anything about the project, and only when you receive this request you will know what's the codebase we're talking about. And in order to actually answer any queries, we need to "index™" it. We don't know what indexing means yet, but it's certainly a lot of work. Do we block until we've indexed everything? Then users will enjoy 10-20-50-100 seconds of waiting with editor being nearly useless. Not an option. Do we start right away? But then what do we answer to the imminent first query about the currently open file? Won't that cause us to block there instead? How to avoid the scary "we need to index everything" problem? And this reveals the first huge difference between the compiler and LSP. Compiler has a rather binary definition of done: the binary (sorry) is either compiled or not. Technically, compiled shared libraries and other build artifacts are usable as well, but in practice you will be annoyed if compiler compiles 715 out of 716 crates in your workspace and then stops. LSP is different: we can provide useful results almost immediately. We don't need complete information at the first millisecond, we need to send something useful to users as soon as possible. We only need to decide what we count as "something useful". The answer to the original question is: we need to do the least amount of useful work that will make processing queries possible. Thus both rust-analyzer and Rust Glancer just validate the provided config and respond. rust-analyzer schedules workspace discovery to start after the response, while Rust Glancer will remain passive until the first query hits. Once the handshake is finished, the real deal starts: you get your first actual queries. In most cases, these likely will be textDocument/didOpen, textDocument/inlayHint, and textDocument/documentSymbol. If the user is eager and you're unlucky, there might even be textDocument/didChange in between these. And the complexity explodes. First, fun fact: LSP as a protocol doesn't want you to think about the filesystem. There is no filesystem, there are just documents and edits. Which makes sense: often times, the document is not saved, so you can't know its contents. Except it doesn't. In most languages, analysis of a single file (or a set of open files) in isolation stops being useful fairly quickly. Enter hell: LSP assumes that it's the source of truth, but you still need to access the filesystem yourself, and do it in a synchronized way. To make it more fun, edits can happen outside of the editor, and the client might not be very faithful in notifying you about such events. And that's why we need a virtual file system, and "source generations", e.g. identifiers of the state of source code at the time of currently executed request. If we will try to naively combine filesystem access and LSP notifications, it will turn the whole project into a never-ending race condition. Instead we load the project sources to memory, declare it a VFS, and try our best to apply any changes on top of this loaded state, and each time we change the state, we update the source generation, which lets us have consistent internal state (and cancel in-flight queries as they get invalidated). "What in-flight queries?", I hear you ask. And that's the second fun fact. Executing an LSP query might entail a suprising amount of work, and not all queries made equal. Looking for references for a symbol is a fairly non-trivial task, while hover is typically cheap. Therefore doing one query at a time is not an option, you need to execute read queries in parallel. And whenever something changes state, the currently running queries will be doing now useless work against now outdated state. Your job is to create a loop which separates mutating and non-mutating queries, lets read requests run in parallel, and cancel work once state changes. And also, if you're unlucky to use async, serialize incoming messages to make sure that your didOpen and didChange don't come in the reverse order which could be a hell of an issue to debug (I wonder why I needed to make this remark). Third and final fun fact is that LSP authors actually considered that you might not be ready, so they gave you useful instruments to deal with that, such as workspace/inlayHint/refresh server request. With such a powerful tool, you can say "oops, try again now pls" and send the actual response even if initially you sent nothing. The problem is that not everything can be refreshed. Document symbols can't; if you don't send them right away, they will be stale until client itself decides that it's time to ask again. Which means that for some queries you might need to get creative. But we've got distracted. Client waits for inlay hints and document symbols. And we still haven't indexed a single thing. What do we do? Server, at your service Lucky us: to answer document symbols, we truly have to index a single thing. The currently open file. And this is actually a perfect example of LSP being useful very fast. All you need to do to answer this request is parse the file. An AST (or rather CST, but we'll get to that) will already tell you which structures, traits, functions, methods, etc you have. You can even do that as a part of the request on demand. textDocument/hover over a Bar in fn foo(a: Bar) {} is a bit trickier: it requires semantic analysis, at least in some form. You need to know where does the thing under the cursor comes from. For that to exist, you need to understand which items (structs, methods, you get it) are available in the scope. To do that, you need definition maps: resolved "what can be seen from where" maps for each crate and module. And to get definition maps, you need an extra layer of lowering. You could still work on AST/CST level, but it won't be convenient. Likely you want to have an item tree, your own representation of items defined in each file. So you need to parse each file -> build an item tree from AST/CST -> resolve modules and build a definition map -> check what's visible under the cursor -> find it through defmaps -> extract documentation for the resolved item -> show it. If you are wondering what does "under the cursor" mean, treat yourself with something savoury for a great question, we'll get to back later. For now, it's quite a bit of extra work, but still fairly manageable. Inlay hints are significantly trickier (as well as hovering inside of a body, e.g. on a local variable). They appear inside of bodies. In fn foo() { let a = bar(); } we can say that fn foo is an item declaration, while { let a = bar(); } is a real scary part body. Note that in the semantic model described above we didn't care about bodies at all. Not only that, but for good inlay hints we need no less than type inference. And for now I will refuse to elaborate. But if you think that it ends here, behold the final boss of the LSP: textDocument/references. For inlay hints, you need to analyze bodies in one file. For references, you hit an innocent option+shift+F12 on a function definition in VS Code (or any other editor that for some reason has the same keybinding), and the poor server must find all uses of that function in all discoverable places across the workspace graph. Think Option. We're talking quickly going through thousands of bodies where we need to distinguish this exact Option from any other item named Option. And