Building a Gradual Type Checker for Lua
A hands-on tutorial that teaches Salsa (the incremental computation framework) by building a gradual type checker for Lua, powered by the analisar parser and lex_lua lexer.
Who Is This For?
- Rust developers curious about Salsa and incremental computation
- People who want to understand how rust-analyzer's query system works under the hood
- Anyone interested in type checking, gradual typing, or Lua tooling
You should be comfortable with Rust. No prior Salsa or type-theory experience needed — we build from zero.
The Stack
| Crate | Role | Version |
|---|---|---|
lex_lua | Lua lexer — tokens, spans, comments | 0.2 |
analisar | Lua parser — AST from tokens | 0.4 |
salsa | Incremental query framework | 0.26 |
Chapters
-
Hello Salsa: Inputs and Tracked Functions — Your first Salsa database, input structs,
#[salsa::tracked], and the revision model. -
Parsing Lua with Analisar — Wire analisar into Salsa. Source text → AST, incrementally.
-
Interned Symbols and Name Resolution —
#[salsa::interned]for variable/function names. Building a symbol table. -
Tracked Structs: The Typed AST —
#[salsa::tracked]on structs. Converting analisar's AST into a Salsa-aware typed IR. -
Type Inference: The Core Query — The big one. A
#[salsa::tracked]function that walks the AST and assigns types. Incrementality in action. -
Diagnostics as Accumulators —
#[salsa::accumulator]for errors and warnings without poisoning the query graph. -
Putting It Together: The Language Server — Wire everything into a simple LSP. Watch Salsa skip work on keystrokes.
Running the Code
Each chapter has a src/ directory with runnable code. From the repo root:
cargo run --bin ch01
cargo run --bin ch02
# etc.
Why Salsa?
Salsa solves a real problem: when you're building a tool that re-runs on every keystroke (IDE, linter, type checker), you can't afford to recompute everything. Salsa gives you:
- Automatic caching — tracked functions memoize their results
- Incremental invalidation — when an input changes, only affected queries re-run
- Cycle detection — recursive queries that would loop forever are caught
- Accumulators — side-channels for diagnostics that don't break the query graph
You'll learn all of these by building something real, not by reading docs in a vacuum.
License
MIT