milc – A Minimal Incremental Lazy Cache

• Minimal: Doesn’t do a lot, should be easy to understand and modify.
• Incremental: Cache entries depend on other entries, and are only updated when an input changes.
• Lazy: Derived values are only updated on demand, so edits are very cheap.
• Cache: It caches things. 😐

This is a minimal implementation of the Salsa incremental caching algorithm, aiming for ease of understanding, more so than performance or a rich feature set.

It stemmed from my struggles when learning Salsa, which seemed fairly complicated to set up, required an intrusive set of proc-macros to generate the cachable types, required cached values to be Clone, and moreover didn’t allow for re-use of cached values. Since I wanted to cache tree-sitter parsers (which aren’t Clone and really want to be reused), this seemed like a good enough excuse to roll my own.

So this library was born in an attempt to understand why Salsa was designed the way it was, and in the processs either grow more comfortable with it, or end up with just enough of a re-implementation to be useful.

As such, consider this not so much a turnkey solution for a wide variety of incremental caching needs, but more as a starting point for your own fork or rewrite.

Usage

• Implement the Input trait for inputs.
• Implement the Query trait for derived values.
• Instantiate a Db implementation (currently only InMemory exists).
• set(...)/compute(...)/... your inputs.
• get(...) your queries.

usemilc::{Db,InMemory,Input,Query};// The query type. Must be `Clone` and `Hash`.
#[derive(Clone, Hash, Copy, Debug)]struct Even;implInput<u8>forEven{}implQuery<bool>forEven{fn value(&self,db: &implDb)-> bool {letn: u8 =*self.get(db);n%2==0}}letdb=&mutInMemory::new();// Set new input value
Even.set(db,2);letnumber: u8 =*Even.get(db);letis_even: bool =*Even.get(db);assert!(number==2&&is_even);// Re-use previous input to compute the next
Even.compute(db,|n: u8|n+1);letnumber: u8 =*Even.get(db);letis_even: bool =*Even.get(db);assert!(number==3&&!is_even);

Prior Art

• Salsa is the most direct inspiration. Basically does everything better than we do, but requires your cached data to be Clone and forces you to use its own macro-generated types.
• Comemo seems very easy to use, for good or ill. There’s no explicit cache instance to pass around, it all happens in the background. It also seems to let you freely mutate tracked types as you’re accesing them. Both of those factors didn’t quite sit right with me; I prefer Salsa’s mental model of an explicit cache instance and strict separation between mutation and access.
• Adapton, which seems more of an academic endeavor. It’s just a lot.