Building a Gradual Type Checker for Lua

If you’ve ever wondered how rust-analyzer can respond in milliseconds while you type, the answer is Salsa. Salsa is the incremental computation framework that powers rust-analyzer’s query system, and this tutorial teaches it from the ground up by building something real: a gradual type checker for Lua.

We’ll use lex_lua to turn Lua source text into tokens, analisar to turn those tokens into an AST, and salsa to make the whole thing incremental. When a file changes, we only re-check what’s affected. No prior Salsa or type-theory experience is needed, but you should be comfortable with Rust. We build from zero.

Why Salsa?

Imagine you’re building a language server. Every time the user types a character, you need to re-check their code. The naive approach — re-parse every file, re-infer every type, re-emit every diagnostic — works fine for a ten-line script. It falls apart for a real project with hundreds of files and thousands of functions. You can’t afford to redo everything on every keystroke.

Salsa is the answer to that problem. It’s an incremental computation framework: you write your logic as pure functions called queries, and Salsa takes care of caching the results and only re-running queries whose inputs actually changed. Change one file, and Salsa skips every query that doesn’t depend on it. The caching is automatic. You don’t write cache invalidation logic. Salsa infers the dependency graph from what your queries actually read, so the graph is always correct and can never get out of sync with the code.

That’s the core value, but Salsa also handles the harder edges. Recursive queries that would loop forever are caught and reported as cycles. Diagnostics — errors, warnings — flow through a separate channel called accumulators, so reporting a type error doesn’t poison the query graph and prevent other checks from running.

This is the same architecture that makes rust-analyzer fast, and by the end of this tutorial, you’ll understand how it works because you’ll have built one yourself.

What You’ll Build

Seventeen chapters, one type checker. By the end, you’ll have:

• A Salsa-powered incremental type checker that re-checks only what changed
• Support for LuaCATS annotations (---@type, ---@param, ---@return, ---@generic)
• Union types (number|string), generic functions (identity(x: T): T), and recursive types (Node|nil)
• Type narrowing (type(x) == "number" makes x a number inside the if)
• Cross-file type checking with require() — edit one file, invalidate only its dependents
• A language server that responds incrementally as you type

Each feature builds on the ones before it. Salsa’s incrementality makes them all fast; the type system catches what would otherwise be runtime errors.

A Note on Code Structure

Each chapter is a standalone Rust crate — it compiles and runs independently. This means the AST types (Statement, Expression, BinOp, UnaryOp), the parser conversion functions (convert_stmt, convert_expr), the type environment (TypeEnv), and the type inference logic (infer_type) are repeated across chapters with incremental additions.

In production code, you’d extract these into a shared library crate. For a tutorial, the duplication is intentional: each chapter is self-contained, so you can jump to any chapter and have the full context without chasing imports across crates. The tradeoff is that fixes to shared code need to be applied in each chapter — but that’s a small price for the readability win.

Version Note

This tutorial uses Salsa 0.26. Salsa’s API changed significantly between the “Salsa 2022” era (0.12 and below) and the current 0.20+ line — the #[salsa::input], #[salsa::tracked], and #[salsa::accumulator] macros, the Database trait, and the query system are all different. If you’re coming from an older Salsa tutorial, you’ll need to re-learn the API. The concepts (incremental computation, dependency tracking, cycle detection) are the same. The syntax is not.

If Salsa has released a newer version by the time you read this, the concepts should still apply, but macro names, trait signatures, and generated method names may differ. Check the Salsa docs for the current API.

License

MIT