Chapter 4: Tracked Structs — Entity Identity in Salsa

Learn #[salsa::tracked] on structs: giving AST nodes stable identity that survives edits.

What You'll Learn

  • What tracked structs are and why they matter
  • The difference between "data" and "identity"
  • How tracked structs enable fine-grained incrementality
  • The pattern used in rust-analyzer's IR

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. In a plain AST, they're just data. If you change add's body, how does Salsa know that mul is unaffected?

Answer: it can't — not with plain data. Both functions are part of the same LuaAst struct. If anything in the AST changes, the whole LuaAst is considered different, and every query that depends on it re-runs.

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 a Tracked Struct

#![allow(unused)]
fn main() {
#[salsa::tracked(debug)]
pub struct FuncDef<'db> {
    pub name: FuncName<'db>,      // interned name (from ch03)
    pub param_count: u32,          // tracked field
    #[returns(ref)]
    pub body_text: String,         // the body as text
}
}

#[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
  • Fields can be queried independently (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: two Symbol("print") instances are the same symbol
  • Tracked: two FuncDef instances with identical fields are different function definitions

Step 2: 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 3: Per-Field Dependencies

Tracked structs have another superpower: field-level dependency tracking. When a tracked function reads func.param_count(db), Salsa records a dependency on that specific field. If you change func.body_text() but not func.param_count(), queries that only read param_count return their cached values.

#![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 = /* count operators in body */;
    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.

Step 4: The Wrapper/Data Pattern

In practice, you often see this pattern in Salsa projects:

  1. Tracked struct — provides identity ("which function is this?")
  2. Plain data inside — provides content ("what's in this function?")

This is what rust-analyzer does. Each function, struct, enum, and impl in the Rust source becomes a tracked struct. The content (the AST, the type, the body) is stored as plain data inside the struct.

For our tutorial, we're keeping it simpler: FuncDef is a tracked struct with a few fields. In a production system, you'd have tracked structs for every named entity, and the AST nodes would reference them by ID rather than by string.

Running

cargo run --bin ch04-tracked-structs

Key Takeaways

  1. Tracked structs have identity. Unlike plain data, each instance has a Salsa ID. Two FuncDef instances with the same content are still different entities.

  2. Fields can be tracked independently. Change only the body? Queries that read param_count don't re-run. This is fine-grained incrementality.

  3. The wrapper/data pattern. Tracked struct (identity) + plain data (content). This separates "which thing" from "what's in the thing."

  4. Lifetime 'db. Tracked structs can't outlive the database. This prevents stale references after mutations.

  5. Why not tracked structs for the entire AST? You can, and rust-analyzer does. But it adds complexity: every node type needs a tracked struct definition, helper functions need lifetime annotations, and the Update trait must be implemented for all inner types. For this tutorial, we use tracked structs for key entities (functions) and plain data for the AST content.

What's 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.