Chapter 4: Tracked Structs — Entity Identity in Salsa

You have two functions in a file. You change one of them. Salsa should re-run only the queries that depend on that function — not every query in the file. But with the AST as a single input, Salsa can’t tell which function changed. The whole LuaAst is one blob: touch any part, and every query that depends on it re-runs.

The fix: each function needs its own identity in Salsa’s database. Not “part of the AST” — a separate entity with a stable ID that survives edits to other functions. That’s what tracked structs give you.

This chapter switches from whole-file parsing (the analisar crate from Chapters 2–3) to extracting individual function definitions by hand. The parsing is intentionally simple — string splitting, no nested parentheses. The point isn’t the parser, it’s the Salsa pattern: once you understand how tracked structs give functions identity, you could swap in a real parser that produces FuncDefs. (You can use analisar with tracked structs — you’d parse the whole file, then decompose the AST into individual FuncDef instances in a tracked query. The hand-rolled parser here is a simplification that keeps the focus on Salsa’s identity model, not on AST traversal.)

The Problem: Plain Data Has No Identity

Consider two Lua functions:

function add(a, b) return a + b end
function mul(a, b) return a * b end

Both have the same shape — two parameters, a body that’s a binary operation. But they’re different functions. Change add’s body, and mul shouldn’t be affected. With plain data, it is — both functions live in the same LuaAst struct, so any change invalidates everything.

You need identity. Each function needs a stable ID that survives edits to other functions. That’s what tracked structs give you.

Step 1: Define an Interned Function Name

Chapter 3 defined Symbol — a generic interned string. Here we need something more specific: an interned name that represents a function name. Same pattern, different purpose:

#![allow(unused)]
fn main() {
#[salsa::interned(debug)]
pub struct FuncName<'db> {
    #[returns(ref)]
    pub text: String,
}
}

Why not reuse Symbol? You could — in a small project, one interned string type is fine. But as a codebase grows, separate interned types act like newtypes: they prevent you from accidentally passing a variable name where a function name is expected. The type system catches the mistake. FuncName and Symbol have the same structure, but they’re not interchangeable — and that’s the point.

Step 2: Define a Tracked Struct

#![allow(unused)]
fn main() {
#[salsa::tracked(debug)]
pub struct FuncDef<'db> {
    pub name: FuncName<'db>,      // interned name (defined above)
    #[tracked]
    pub param_count: u32,          // tracked field — per-field dependencies
    #[tracked]
    #[returns(ref)]
    pub body_text: String,         // tracked field — per-field dependencies
}
}

#[salsa::tracked] on a struct makes it database-resident. Each instance gets a unique Salsa ID, it’s stored in the database (not on the stack), it has a lifetime 'db tying it to the database, and fields can be queried independently for fine-grained dependencies.

This is different from #[salsa::interned]. Interned structs are deduplicated by content — same fields, same ID. Tracked structs have unique IDs even if their fields are identical. Think of it as the difference between a value type and a reference type: Interned means two Symbol("print") instances are the same symbol; Tracked means two FuncDef instances with identical fields are different function definitions.

Step 3: Identity vs Content

Here’s the key distinction:

┌─────────────────────────────────────┐
│  Plain data:                        │
│  Two {name: "add", params: 2}       │
│  → Equal by value                   │
│  → No way to tell them apart        │
├─────────────────────────────────────┤
│  Tracked struct:                    │
│  Two FuncDef {name: "add", ...}     │
│  → Different IDs                    │
│  → "Which function?" matters        │
└─────────────────────────────────────┘

When you change add’s body, you create a new FuncDef with a new ID. Salsa sees: “function #1 changed.” Queries that depended on function #2 (mul) aren’t invalidated because function #2’s ID is unchanged.

Step 4: Per-Field Dependencies

Tracked structs can track dependencies at the field level — but only if you opt in. By default, Salsa tracks dependencies at the struct level: reading func.param_count(db) tells Salsa you depend on func, not on param_count specifically. To get per-field tracking, mark the field with #[tracked]:

#![allow(unused)]
fn main() {
#[salsa::tracked(debug)]
pub struct FuncDef<'db> {
    pub name: FuncName<'db>,      // untracked (default)
    #[tracked]
    pub param_count: u32,          // tracked — dependency on this field only
    #[tracked]
    #[returns(ref)]
    pub body_text: String,         // tracked — dependency on this field only
}
}

With #[tracked] on the fields, Salsa records a dependency on that specific field when you read it. If you change body_text but not param_count, queries that only read param_count return their cached values.

To see this in action, we’ll introduce a second query. func_signature reads only name and param_count — it doesn’t care about the body:

#![allow(unused)]
fn main() {
#[salsa::tracked]
pub fn func_signature(db: &dyn salsa::Database, func: FuncDef<'_>) -> String {
    let name = func.name(db).text(db);
    let param_count = func.param_count(db);
    let params: Vec<String> = (0..param_count).map(|i| format!("p{}", i)).collect();
    format!("function {}({})", name, params.join(", "))
}
}

func_complexity reads both param_count and body_text — a change to either field invalidates it:

#![allow(unused)]
fn main() {
#[salsa::tracked]
pub fn func_complexity(db: &dyn salsa::Database, func: FuncDef<'_>) -> u32 {
    let body = func.body_text(db);     // depends on body_text
    let ops: u32 = ['+', '-', '*', '/', '.', '=']
        .iter()
        .map(|c| body.chars().filter(|&ch| ch == *c).count() as u32)
        .sum();
    ops + func.param_count(db)          // depends on param_count
}
}

If you change only the body text, func_complexity re-runs (it depends on body_text). But if you added a query that only reads param_count, it would return its cached value. The per-field benefit shows up across different queries — not within a single query that reads both fields.

Without #[tracked], all fields are “untracked” — Salsa still stores them and you can read them, but the dependency is on the entire struct. Change any untracked field, and the struct is considered re-created, invalidating all queries that depend on it. For our FuncDef, adding #[tracked] is the right call: the whole point is fine-grained incrementality, and we want queries that only read param_count to stay cached when the body changes.

Step 5: The Wrapper/Data Pattern

There’s a design tension in our FuncDef. Its param_count and body_text fields are tracked with #[tracked] — Salsa records per-field dependencies, and changing one field doesn’t invalidate queries that only read the other. The name field is untracked — it’s part of the struct’s identity, not a tracked data field. Changing the name effectively creates a new function.

But sometimes you want identity to stay stable even when content changes. Rust-analyzer does this. Each function in the source code gets a tracked struct with an ID that doesn’t change when the body is edited — because the body isn’t a field of the tracked struct at all. It’s a separate tracked query.

The pattern looks like this:

1. Tracked struct — identity only. No mutable fields. “Which function is this?”
2. Tracked function — content. Takes the tracked struct as input, returns the data. “What’s in this function?”

#![allow(unused)]
fn main() {
// Identity — stable even when content changes
#[salsa::tracked]
pub struct Func {
    pub name: FuncName<'db>,  // the one field that *is* identity
    // no body, no param_count — those are content
}

// Content — a separate query
#[salsa::tracked]
pub fn func_data(db: &dyn salsa::Database, func: Func<'_>) -> FuncData {
    // look up the body, parameters, etc.
}
}

Our tutorial uses the simpler approach: FuncDef puts content directly in the tracked struct. This is easier to understand and fine for a small project. In a production system with hundreds of entities, the wrapper/data pattern pays off: it keeps identities stable across edits, which means fewer cache invalidations and faster incremental updates.

Step 6: Parsing Functions from Source

Before we can see tracked structs in action, we need to create some. That means parsing source text into FuncDef instances.

We’re switching from the analisar parser (Chapters 2–3) to a hand-rolled string-splitting approach. Why? Because analisar gives us the entire AST at once — a single LuaAst. But FuncDef is per-function. We need to produce individual tracked structs, not one big bag of data.

Here’s the implementation:

#![allow(unused)]
fn main() {
#[salsa::tracked]
pub fn parse_functions(db: &dyn salsa::Database, source: SourceFile) -> Vec<FuncDef<'_>> {
    let text = source.text(db);
    let mut functions = Vec::new();

    for line in text.lines() {
        let line = line.trim();
        if let Some(rest) = line.strip_prefix("function ") {
            // Parse: function name(p1, p2, ...) body end
            //
            // Simplification: this breaks on nested parentheses in
            // the body (e.g., `return g(x)` — the first `)` closes
            // `g(`, not the parameter list). For demonstrating tracked
            // structs, this is fine. A real implementation would use
            // analisar from ch02.
            if let Some(paren_pos) = rest.find('(') {
                let name = &rest[..paren_pos];
                let after_paren = &rest[paren_pos + 1..];
                if let Some(close_paren) = after_paren.find(')') {
                    let params_str = &after_paren[..close_paren];
                    let param_count = if params_str.is_empty() {
                        0
                    } else {
                        params_str.split(',').count() as u32
                    };
                    // Everything after ) until 'end' is the body
                    let body_start = paren_pos + 1 + close_paren + 1;
                    let body = if body_start < rest.len() {
                        rest[body_start..].trim().trim_end_matches("end").trim().to_string()
                    } else {
                        String::new()
                    };

                    let func_name = FuncName::new(db, name.to_string());
                    let func = FuncDef::new(db, func_name, param_count, body);
                    functions.push(func);
                }
            }
        }
    }

    functions
}
}

A few things to notice. FuncName::new(db, ...) interns each function name — if two functions are named add, they share the same FuncName ID. FuncDef::new(db, ...) creates a tracked struct, and each call produces a new ID even if the fields are identical. The return type is Vec<FuncDef<'_>> — a collection of tracked structs. Salsa sees this query as depending on the SourceFile input. When the source changes, the whole parse_functions result is invalidated.

The parser is deliberately fragile. It won’t handle nested parentheses, multiline functions, or comments. That’s intentional — the point is the Salsa pattern, not parsing. A production type checker would use analisar (or any proper Lua parser) and convert its AST into tracked structs.

Step 7: Seeing It in Action

Let’s make this concrete. Say we have two functions:

function add(a, b) return a + b end
function mul(a, b) return a * b end

When we first run the type checker:

1. parse_functions runs → produces two FuncDef instances: function #1 (add) and function #2 (mul)
2. func_signature and func_complexity run for each → results cached per FuncDef ID

Now we edit add’s body to return a .. b (string concatenation instead of addition):

Edit: add's body changed from "a + b" to "a .. b"

What happens:

1. parse_functions re-runs → new source, so it produces FuncDef instances for the updated code
2. add’s FuncDef keeps the same ID — identity is keyed by the untracked fields (fields without #[tracked]), and add’s name didn’t change. But Salsa compares the old and new field values: body_text changed, so that field’s revision updates. name and param_count didn’t change, so their revisions stay the same.
3. mul’s FuncDef also keeps the same ID — and none of its fields changed, so all field revisions stay the same
4. func_complexity(mul) → cached result returned instantly — mul’s FuncDef has the same ID and no fields changed, so all cached queries are still valid
5. func_complexity(add) → re-runs because it reads body_text, and that field’s revision changed → new complexity value
6. func_signature(mul) → cached — it only reads name and param_count, neither of which changed
7. func_signature(add) → also cached! add‘s body_text revision changed, but func_signature doesn’t read body_text — it only depends on name and param_count, and neither of those fields’ revisions changed

Step 7 is the per-field tracking payoff. add was “touched” by the re-parse, but func_signature is insulated because it never read the field that changed. Without #[tracked] on the fields, changing any field of add’s FuncDef would invalidate func_signature — even though it doesn’t use the changed field.

The key moment is step 2. With plain data, changing any part of the AST would invalidate everything. With tracked structs, add keeps its identity (same name = same entity), and Salsa tracks which fields actually changed. Queries that depend on unchanged fields never need to re-run.

This is the difference between “per-file incrementality” (Chapters 2–3: the whole file re-checks) and “per-entity incrementality” (this chapter: only the changed function re-checks). Tracked structs are what make per-entity incrementality possible.

Running

cargo run --bin ch04-tracked-structs

Next: Chapter 5: Type Inference — The heart of the tutorial. We’ll implement type inference as a Salsa tracked query and see incrementality in action. This is where everything comes together.