Use query-based compiler architecture

[michaelmesser]

• [x] I have read CONTRIBUTING.md.
• [x] I have checked that there is no existing PR/issue about my proposal.

Summary

A query-based compiler architecture would allow for efficient incremental type checking. Rust-analyzer and Sixty use this approach.

Query-based compilers are structured as follows:

• Queries are pure functions that depend on other queries or inputs
• Dependencies of queries are recorded at runtime
• Use a cached value if a query was already computed and the dependencies have not changed

Motivation

A query-based compiler architecture would provide the following benefits:

• Only recompute what is needed
• Accurate incremental computation since all dependencies are recorded at runtime
• Whole project instead of just one file (switching files has no cost)
• Easier to reason about because everything is a pure function
• Significantly easier to parallelize since everything is pure
• Better Idris API (useful to LSP)

The proposal

I believe an implementation would be similar to how rust-analyzer and sixty are implemented.

• Rust-analyzer with Salsa

  • Responsive Compilers Video
  • Three Architectures for a Responsive IDE
  • Salsa Flowgraph Image
    • Video
  • Rust Analyzer Repo
  • Salsa Repo

• Sixty with Rock

  • Query-based Compilers Blog
  • Query-based Compiler Architectures Video
  • Rock Repo
  • Sixty Repo

Alternatives considered

• No incremental computation
  • Far too slow
• Attempt to manage incremental computation by hand
  • Difficult and error prone

Conclusion

A query-based architecture would significantly improve the editor experience on large projects. Unfortunately, rearchitecting the compiler would be a huge and difficult change to implement.

[ohad]

I think the IDE protocol can be used to this effect. The protocol requests can be recorded with dependencies and their responses cached, and a simple compiler state flag can indicate whether the state has changed. If the flag isn't set, we can satisfy a new response from its cavhed answer.

In the future, we can improve the dependency analysis for finer grained change tracking. So working on the IDE protocol can be a shortcut to query based compiler.

This kind of architecture can even be a layer between the client and server, in an external project.

[michaelmesser]

@ohad I think you are describing something significantly different that what I am describing. Can you point to a project that does what you describe so I can better understand?

[ohad]

It's possible that the implementation is significantly different, but since this proposes a major overhaul of the compiler, I think the IDE protocol is a viable alternative that should be considered if it delivers comparable functionality.