designing a query system | arya dradjicaFrom the start of this year, I have slowly been going about designing a query system for Krabby. It took five months of sitting still and thinking really hard, but I believe I have a clear grasp of the design now. I’m going to explain why Krabby needs a query system (because I thought it wouldn’t for a while), the special features I wanted, and how everything fits together.<br>precursor: the push-based architecture<br>My original vision for Krabby was a push-based architecture where tasks “push” their outputs to later tasks that need them. I thought this would have a lower overhead than a “pull-based” query system. And this felt feasible because (particularly in the earlier stages of compilation) the dependencies between tasks can be known upfront. The compiler could execute many independent tasks of the same type in an easily parallelized fashion.<br>This greatly influenced the design of my name resolution algorithm. My idea was to (often pre-emptively) parse Rust source files from the target crate’s src/ folder and inject their results into a global database of Rust items. The database would also store pending references to as-yet-undiscovered items, and when those items got added, the references would be resolved.<br>I was quite happy with this design for a while, but as I got into the weeds of the implementation back in December, I realized the design had some important flaws.<br>Because the global database tracked pending references, it was basically a specialized query system — I hadn’t escaped that complexity.

Because it was lazy, it wouldn’t make good use of the CPU cache: items could be added (and thus inserted in the cache) much earlier than their first use. An eager approach, where items are looked up when they are first needed, would improve the use of the cache.

Unbalanced dependency graphs (containing long chains of tasks that must be done serially) would not be handled efficiently. The architecture is unable to identify tasks which are heavily depended upon, and does not control when they are executed. They might be executed very late in compilation, and cause a single CPU to keep working after everything else is done. In contrast, a pull-based approach would add an element of demand-driven prioritization.

A pull-based approach can target a different goal (e.g. cargo check vs. cargo build vs. identifying a particular Rust item) easily. This is crucial for making Krabby usable for LSPs, where user-initiated actions (e.g. find all references to foo()) should be evaluated as quickly as possible, with minimal unrelated work.

This stopped my name resolution implementation work in its tracks. I began designing the query system at the very start of 2026, and (excluding a two-month tangent to write housekeeping), it’s been my primary focus. Let me tell you: designing a query system is a lot of work!!<br>my wish list<br>I am perpetually saddened by the fact that codebases are fundamentally limited by their historic design choices. The way a program is architected specializes it, and sets it down a path it cannot be shaken from easily. I keep seeing features and optimizations blocked by years-old decisions that never considered their possibility. It’s just the way things are, but I find it heartbreaking.<br>With all my projects, but Krabby in particular, I try to explore the design space as thoroughly as I can—to look five, maybe ten steps ahead. I try to design things to elegantly allow for all the possibilities I can foresee. This is fallible, of course, but I find solace in knowing I tried. That’s my excuse for writing a seven-thousand-word blog post.<br>Here’s the list of interesting features I thought of for Krabby’s query system. I’m mostly focusing on the ways it departs from rustc’s query system and salsa. I’m not going to try implementing all of these features immediately, but I have tried to integrate their needs in my design.<br>Concurrency : The query system should operate across multiple threads and efficiently distribute tasks (which are fine-grained units of work) between them. It needs to handle contention (different threads trying to compute the same data) and detect cycles across threads.<br>This isn’t a unique feature, but I think it has the biggest effect on the design. rustc’s frontend already supports concurrency (it has been in development for a while, but it is now tested as part of CI). I hope to embrace parallelism even more with Krabby, treating it as a requirement from day one and letting it shape the rest of the design.<br>The housekeeping crate was an important step towards concurrency. It provides an essential ingredient for building high-performance concurrent data structures: a safe way to deallocate resources shared between threads. While other implementations of this exist, housekeeping provides some additional features (and, I hope, better performance). I plan to write up its design sometime.

Asynchrony : Tasks should be able to pause and resume. This...