How would you design a compiler upfront to be both a compiler and a LSP server?

Question

For most modern programming languages, an LSP (Language Server Protocol) server needs to be developed, which requires reusing/rewriting some of the existing code that is already used by the compiler. So, how can a compiler be designed to accommodate this need from the start?

Credit to gavinhoward for the idea on Area 51.

Answer 1

That said, after deciding that LSP would essentially be required for my language, I had to figure this out. Here is my list of factors.

Performance

A user expects an LSP server to respond after every keypress. Typing 120 words a minute means that, with five characters per word and one space, they type 12 characters per second. Let's round that down to 10.

This means your server has to respond within 100 milliseconds.

That's a tall order for a compiler.

This is the biggest reason that compiler-based LSP servers don't really happen; making batch-based compilers fast enough to work that fast is hard.

Why? Because LSP is an entirely different use case than compilation. Compilation is batch; LSP is interactive. Compilation is all-at-once; LSP is incremental.

This mismatch is fundamental.

Of course, the compiler doesn't have to do everything it normally does for LSP; it just has to parse and validate. So it is possible, but it's hard.

Often, based on the design of the language, it makes more sense to have a separate program anyway.

Which brings me to...

Language Design

Language design matters a lot.

If your compiler is multi-pass, that's going to hurt in several ways.

First, it's hard to implement incremental compilation in a multi-pass compiler. I tried. My language design changed because of this.

Second, multiple passes means more time taken.

Third, multiple passes means that information is most likely not local.

How to Do It

So let's assume that you are unwilling to change your language design for LSP. What do you do?

Easy: don't do it.

I suggest you actually plan on writing an LSP server that is separate from the compiler. Really. Just plan on it. Their use cases are completely different and require different architectures in most cases.

Save yourself the pain and just write two different programs.

(Edit: Of course, you could still do the 20% effort upfront to get the compiler 80% of the way there and then share code between them. But that work does have to happen upfront.)

But if you plan on changing your language design like I did, here's what to do:

• Make your language single-pass.
• Make sure your compiler can continue after parse errors. This means having a way to recover. Usually, this means looking for the next semicolon or right brace and start again from there.
• Make sure your compiler can generate semantic information, such as labeling what is a function, what is a type, etc.
• Make sure your compiler stores location and span information for every token.
• Make it possible for each compilation unit to be standalone and not depend on other compilation units. Yes, this is what C/C++ did better than everyone else. (This has the benefit of preventing your compiler from becoming a build system and making it easier to build in parallel.)
• Don't require header files; that's slow. Your compiler should be able to take in that information some other way because in LSP mode, it should store that information and use it as-is without touching disk.
• If you can make it possible to restart parsing from random spots, do it. For example, if you can store the order in which the functions were defined, then your server could figure out what functions came before the location of a change, delete them, and reparse from the change.

Answer 2

Gavin's answer makes a lot of great points, and I don't disagree with them. Furthermore, I'm going to risk repeating some of his closing advice, but I hope I included at least some context that makes the answer worthwhile to read.

If you end up deciding you want to marry your compiler to the LSP, or if you even just want to make your compiler amenable to being used in editor/IDE tooling, then I would take a look at some of the design and implementation of rust-analyzer. While it isn't actually a compiler itself, it implements a Rust frontend that is both incremental and resilient. These traits are important because when used in conjunction with an editor we always want our tooling to respond as quickly and as completely as possible, as opposed to failing to check/format/build later code for the sole reason of an earlier, unrelated piece of code not being well-formed.

rust-analyzer's dev docs on syntax describe some of the design that make it very resilient for parsing. One of the rust-analyzer maintainers has recently blogged about resilient parser implementations. The same maintainer has also worked on an incremental computation framework for Rust called salsa, which could be interesting to look at. Here is a blog post on query-based compiler architectures that makes reference to both salsa and using a compiler in language server tooling.

Answer 3

One thing you can do to save a lot of time on LSP re-parsing and re-compiling your code on frequent changes: use a parser with memoisation. Packrat, for example, or any other similar approach. This way it'll be very easy to invalidate the parsed region affected by an edit and then reparse the entire unit, whatever it is - your parser should know the boundaries of your units, be it a module, a class, a function, an entire file, etc.

Likewise, you can run further lowering, typing passes, etc., only on things that changed and that depend on what you've changed.

It can all be easily made a part of your compiler, because why would you write two different parsers anyway? A side effect of having syntax highlighting, type hints, pretty-printing and all that as a side effect of compilation is that you can add formatted literate code generation to the compiler.