Chapter 8: Cycle Detection — What Happens When Queries Form a Loop

Two Lua functions. One calls the other. The other calls the first.

Let’s find out.

The Problem

Imagine two Lua functions that reference each other:

local function f(x) return g(x + 1) end
local function g(x) return f(x - 1) end

If infer_type(f) calls infer_type(g) which calls infer_type(f) — that’s a cycle. Without protection, this loop runs forever. The stack overflows. Your language server hangs.

Salsa catches this. Let’s see how.

A Minimal Cycle

#![allow(unused)]
fn main() {
// A tracked function that calls itself — a direct cycle.
// (SourceFile is a Salsa input struct defined in Ch1.)
#[salsa::tracked]
fn direct_cycle(db: &dyn salsa::Database, source: SourceFile) -> i32 {
    direct_cycle(db, source)
}
}

When you call direct_cycle(db, file), Salsa notices that direct_cycle is already on the call stack. Instead of re-entering the function, it panics with a cycle error.

This is deliberate. Salsa’s contract is: tracked functions are pure functions of their inputs. A cycle violates that contract — the result depends on itself. There’s no correct answer, so Salsa stops.

You might wonder why Salsa doesn’t return a Result type instead of panicking. The reason is the function signature: #[salsa::tracked] functions return Type, not Result<Type, CycleError>. Changing the return type would force every caller to handle the error, even in the common (acyclic) case. Panicking is Salsa’s way of saying “this shouldn’t happen in normal code” — and the recovery mechanisms below are how you opt in to handling it when it does.

What the Panic Looks Like

thread 'main' panicked at 'dependency graph cycle when querying \
  infer_type(Id { value: 42 }), set cycle_fn/cycle_initial to fixpoint iterate.
Query stack:
  [infer_type(Id { value: 42 }),
   infer_type(Id { value: 17 })]',
  .../salsa-0.26.2/src/function/fetch.rs:178:5

The panic message tells you which query cycled and shows the query stack — the chain of calls that led to the cycle. The message also suggests using cycle_fn or cycle_initial (the fixpoint iteration approach) if you want to handle cycles instead of panicking. For a type checker, cycle_result is usually simpler — it returns a fallback value immediately, no iteration needed.

Handling Cycles Gracefully

Panicking is fine for a tutorial. For a real language server, it’s not — you don’t want the entire process to crash because one file has mutually recursive functions.

Salsa provides two ways to handle cycles without panicking:

1. catch_unwind and fallible wrappers

The simplest way to handle cycles without crashing is to wrap the query call in std::panic::catch_unwind. Salsa panics on cycles, and catch_unwind lets you catch that panic and recover:

#![allow(unused)]
fn main() {
use std::panic::{catch_unwind, AssertUnwindSafe};

fn safe_type_check(db: &Database, source: SourceFile) -> Vec<Diagnostic> {
    // AssertUnwindSafe tells the compiler "I accept that this closure
    // may observe inconsistent state after a panic." It's needed because
    // catch_unwind requires the closure to be UnwindSafe, and closures
    // that capture &Database aren't automatically UnwindSafe — the
    // compiler can't prove the database is still consistent after a
    // panic. In practice, Salsa's cycle panics don't corrupt state
    // (they abort the query before it writes anything), so this is safe.
    let result = catch_unwind(AssertUnwindSafe(|| {
        type_check(db, source)
    }));
    match result {
        Ok(diagnostics) => diagnostics,
        Err(panic_payload) => {
            // Salsa cycles panic with a string message like
            // "dependency graph cycle when querying infer_type(...)"
            if let Some(msg) = panic_payload.downcast_ref::<&str>() {
                vec![Diagnostic::error(format!("cycle: {msg}"))]
            } else if let Some(msg) = panic_payload.downcast_ref::<String>() {
                vec![Diagnostic::error(format!("cycle: {msg}"))]
            } else {
                vec![Diagnostic::error("unknown cycle".to_string())]
            }
        }
    }
}
}

Now instead of crashing, a cycle produces a diagnostic: error: dependency graph cycle when querying infer_type(...). The language server stays alive. The user sees the error in their editor and can fix the mutual recursion.

This approach — wrap the top-level query and convert the panic into a user-visible error — works reliably across Salsa versions. It’s not elegant, but it handles cycles without restructuring your queries. You might wonder why you’d use catch_unwind instead of the built-in cycle_result approach below. The tradeoff: catch_unwind is universal (wrap any query) but blunt (you get a string error message, not a typed fallback). cycle_result is precise (each query defines its own typed fallback) but per-query (you opt in for each tracked function individually). For a small project, catch_unwind is quick to add. For a production type checker, cycle_result is the better long-term choice.

If your project uses panic = "abort" (common in release builds for performance and binary size), catch_unwind won’t work — there’s nothing to catch. Use the cycle recovery function approach below instead.

2. Cycle recovery with cycle_result

Salsa also provides a built-in way to handle cycles without panicking. When a cycle is detected, instead of panicking, Salsa calls your recovery function and uses its return value to break the cycle.

The idea: a tracked function can specify what to return if it’s part of a cycle. For a type checker, the sensible fallback is Type::Error — “I couldn’t infer this type because of a cycle.”

In Salsa 0.26, the attribute is cycle_result. It takes the name of a function that Salsa calls when the tracked function is part of a cycle:

#![allow(unused)]
fn main() {
#[salsa::tracked(cycle_result = infer_type_fallback)]
fn infer_type(db: &dyn Db, def: Definition) -> Type {
    match def.kind {
        DefKind::Function => {
            // Walk the function body, inferring types for each expression.
            // If the body calls another function, we look up its Definition
            // and call infer_type recursively. That recursive call is
            // where cycles happen.
            //
            // (Ch5's infer_type works on expressions. A definition-level
            // type checker would walk the function's body here, calling
            // infer_type for each referenced Definition. The details
            // aren't important — what matters is that infer_type can
            // call itself on a different Definition, and that's the
            // cycle we need to recover from.)
            todo!("walk function body, inferring types")
        }
        DefKind::Variable => {
            // Infer the type of the variable's initializer expression.
            todo!("infer variable type")
        }
        DefKind::Parameter => {
            // Parameters get their types from the function signature
            // or from explicit annotations (Ch10).
            Type::Dynamic
        }
    }
}

/// Fallback function: called when infer_type is part of a cycle.
///
/// Instead of panicking, we return Type::Error. Salsa propagates
/// this back through the cycle — every query that was waiting on
/// infer_type gets Error, and computation continues.
///
/// The `id` parameter identifies which query instance hit the cycle.
/// The `def` parameter is the tracked function's other input —
/// in this case, the Definition being inferred. The fallback
/// signature is (db, id, ...other_inputs), matching the tracked
/// function's parameters after db.
///
/// Note: the fallback receives `&dyn salsa::Database`, not `&dyn Db`.
/// The tracked function uses your custom `Db` trait, but the fallback
/// runs outside the normal query context — Salsa doesn't give it
/// access to your custom database methods. This restriction is
/// deliberate: the fallback runs during cycle recovery, where the
/// interrupted query's intermediate state is inconsistent. If the
/// fallback could call other tracked functions, it might trigger more
/// cycles or read stale data. Restricting it to the base `Database`
/// trait prevents that. Since the fallback's job is to return a fixed
/// value (Type::Error), it doesn't need custom methods anyway.
fn infer_type_fallback(
    _db: &dyn salsa::Database,
    _id: salsa::Id,
    _def: Definition,
) -> Type {
    Type::Error
}
}

When infer_type hits a cycle — say f calls g and g calls f — Salsa notices that infer_type for f’s Definition is already on the stack. Instead of panicking, it calls infer_type_fallback, which returns Type::Error. That Error propagates: infer_type for g’s Definition gets Error for f’s type, so it also returns Error. The cycle is broken, and the rest of the type checker continues.

-- What the user wrote:
local function f(x) return g(x + 1) end
local function g(x) return f(x - 1) end

-- What happens internally:
--   infer_type(Definition for f)        -- simplified: the tracked struct for f
--     → calls infer_type(Definition for g)
--       → calls infer_type(Definition for f)  ← CYCLE!
--       → infer_type_fallback returns Type::Error
--     → f's return type is Error
--   → g's return type is Error
--
-- Both functions get Type::Error. The type checker continues.
-- A diagnostic is reported: "cannot infer type of `f`: cyclic dependency"
--
-- Note: "Definition for f" is pseudocode — Definition is a Salsa tracked
-- struct, not an enum variant. You can't write Definition::f in Rust.
-- The real code would use Definition::new(db, f_name, ...) to create the
-- instance, then pass that instance to infer_type.

The cycle_result approach uses the FallbackImmediate strategy — when a cycle is detected, Salsa immediately returns the fallback value. This is the right choice for a type checker: there’s no “correct” type for a cyclic function, so returning Type::Error immediately is the sensible behavior.

Salsa also supports fixpoint iteration via the cycle_fn and cycle_initial attributes. This is useful for dataflow-style analysis where you want to iterate until the values converge. A type checker doesn’t need this — Type::Error is the only sensible answer for a cycle — but if you’re building something like a constant propagation analysis, check the Salsa docs for the cycle_fn API.

The cycle recovery API has changed across Salsa versions. The concept is stable — define a fallback, return it on cycles, keep running — but the attribute name and function signature may differ. Check the Salsa docs for your version.

Why Cycles Happen in Type Checkers

Cycles show up in real type checkers more often than you’d expect:

Our tutorial doesn’t hit these because:

• infer_type doesn’t look up function definitions from a global table (Ch5 checks expressions in isolation)
• parse is per-file (no cross-file dependencies)
• We don’t resolve require() (Ch9 adds cross-file resolution)

But a real type checker will hit cycles. When you add cross-file resolution, you’ll need cycle handling.

The Architectural Fix: Break the Loop

The best way to handle cycles is to structure your queries so they don’t form loops. This means making the dependency graph explicit:

SourceFile (input)
    ↓
parse() → LuaAst (tracked function)
    ↓
top_level_names() → Vec<String> (tracked function)
    ↓
FuncDef (tracked struct, one per function)
    ↓
infer_return_type() → Type (tracked function, depends on FuncDef, not SourceFile)

The key: infer_return_type depends on FuncDef (a tracked struct), not on SourceFile (an input). When you edit the source, parse re-runs and produces new FuncDefs. Salsa creates new tracked struct instances for changed functions, and only re-runs infer_return_type for those.

Why does this help with cycles? Because the dependency graph goes one direction: SourceFile → parse → FuncDef → infer_return_type. There’s no arrow going back up. Mutual recursion between functions becomes infer_return_type(FuncDef for f) → infer_return_type(FuncDef for g) → infer_return_type(FuncDef for f) — a cycle at the entity level, which Salsa can detect and recover from. Without the FuncDef layer, you’d have type_check(SourceFile A) → type_check(SourceFile B) → type_check(SourceFile A) — a cycle at the file level, which invalidates entire files instead of individual functions.

The granularity matters. The FuncDef tracked struct is the entity boundary — the point where “something changed” becomes specific enough to handle without pulling the whole file back into the cycle.

This is the tracked-struct granularity we discussed in Ch4. It’s not only about performance — it’s about making the dependency graph acyclic by design.

What We’re Simplifying

Recovery function signatures. The cycle_result attribute and the exact signature of the fallback function (db, id, ...other_inputs) are specific to Salsa 0.26. The fallback receives the database, the query’s Salsa ID, and any other input parameters the tracked function takes (after the db parameter). Other versions may use different attribute names (like cycle_fn or cycle_initial) and different signatures (some include &salsa::Cycle for diagnostic access). The concept — define a function that returns a fallback value — is stable. The syntax may not match your version exactly. Check the Salsa docs for the current API.

try_ query variants. Some Salsa versions have explored query methods that return Result instead of panicking on cycles (e.g., try_get_{field} on tracked structs). As of Salsa 0.26, these don’t exist in the public API — catch_unwind and cycle_result are the two available approaches. If a future version adds try_ variants, they’d offer fine-grained cycle handling without wrapping every call in catch_unwind.

Cycle interaction with incremental recomputation. When Salsa invalidates a query that was part of a cycle, the recovery function runs again on the next access. The details — does it re-run the whole cycle, or only the recovered query? — depend on the version. For production use, test your recovery behavior after edits, not only on first run.

For a real implementation, read the Salsa book and the rust-analyzer source — rust-analyzer is the largest real-world Salsa user and handles cycles extensively.

Next: Chapter 9: Cross-File Analysis — We’ve been type-checking one file at a time. Real Lua projects span multiple files with require. We’ll extend our type checker to handle cross-file dependencies — resolving types from imported modules, tracking which files depend on which, and invalidating only what changed when a dependency updates.