Problem

A foundational assumption of deep_verify_memo is that it walks query dependencies in execution order (as seen by the query being validated). This PR fixes a bug related to cyclic queries where this invariant was violated because of how Salsa tracks dependencies:

• Salsa only stores the DatabaseKeyIndex but not the IterationCount when adding a read dependency. The result is that Salsa adds a single dependency even if a query reads a x_1 and x_2 where _i signifies the iteration.
• We only store the last memo, making it impossible to retrieve a query's dependencies in iteration i.

The result is that deep_verify_edges verifies dependencies before the structs on which the query results are stored, which is unsound.

Here an example where this happened before (this is a new test case):

#[salsa::tracked(cycle_initial=cycle_initial)]
fn query_a<'db>(db: &'db dyn salsa::Database) -> Interned<'db> {
    let interned = query_b(db);
    let value = interned.value(db);

    if value < 10 {
        Interned::new(db, value + 1)
    } else {
        interned
    }
}

#[salsa::tracked]
fn query_b<'db>(db: &'db dyn Database) -> Interned<'db> {
    let interned = query_a(db);
    query_x(db, interned);
    interned
}

#[salsa::tracked]
fn query_x<'db>(_db: &'db dyn Database, _i: Interned<'db>) {}

fn cycle_initial(db: &dyn Database, _id: Id) -> Interned<'_> {
    Interned::new(db, 0)
}

#[salsa::interned]
struct Interned {
    value: u32,
}

Collected input/outputs by query:

• query_a
  • query_b
  • Interned::new(1)

    ---

  • Interned::new(2)

    ---

  • Interned::new(3)

    ---

  • ...
  • Interned::new(10)
• query_b
  • Interned::new(0)
  • query_a
  • query_x(Interned(0))

    ---

  • query_x(Interned(1))

    ---

  • query_x(Interned(2))

    ---

  • ...
  • query_x(Interned(10))
• query_x: Not important

Traversal order in maybe_changed_after:

1. query_a
   1. query_b
      1. Interned::new(0)
      2. query_a (returns unchanged, fixpoint initial)
      3. query_x(0)
      4. query_x(1)
      5. query_x(2)
      6. query_x(...)
      7. query_x(10)
      8. Interned::new(1)
   2. Interned::new(2)
   3. Interned::new(...)
   4. Interned::new(10)

Note how Salsa verifies query_x(1), and query_x(...) before verifying that the interned values haven't changed.

The issue is that Salsa sees a dependency on query_b (without any iteration!), but it then doesn't just validate the dependencies of query_b in iteration 0, it validates all its dependencies, even if they are from later iterations. Only once that's done does salsa verify the remaining dependencies from query_a, even though they were created before some of the dependencies that were just verified as part of query_b.

Solution

This PR flattens the dependencies of all queries with cycle handling that participate in a cycle after each execution (each iteration) so that the cycle head depends only on inputs, tracked structs, interned values, and finalized queries. This ensures that the query's dependencies form a tree, not a graph (no cycles).

Not only does this fix the bug mentioned above, but it also greatly simplifies maybe_changed_after, as it no longer needs to handle cyclic dependencies. This allows us to remove almost all fixpoint-related code from maybe_changed_after (and friends).

Downsides

There are a few downsides to this approach:

• It inherently breaks accumulated values. Collecting the accumulated values requires walking the query's dependency tree. This is fundamentally at odds with this new approach because we intentionally trim the dependency tree. I didn't consider this a blocker because trimming dependency trees (specifically by flattening) is something that we want to introduce in other parts of Salsa, to reduce memory usage (Flatten query dependencies #909). The other reason is that accumulated values were already "broken," in the sense that they returned too many values when a cycle head depended on the accumulating function in some iterations but not all, but the result would contain the accumulated values from all iterations.
• Flattening the dependencies for each cycle head participating in a cycle isn't cheap, as the benchmarks show. I initially worked on a version that only required the outermost cycle head's dependencies. This implementation only regressed performance by 8-9%. However, it required a much more complicated design because deep_verify_memo for a nested head needed to delegate to the outermost cycle head. This, in turn, required tracking more state to verify if the outermost cycle head is still "the same" as when the inner head was executed (a cycle finalized in the field), and it's also much more difficult to reason about in general. It also didn't work 😆 Specifically, it didn't correctly handle the case where an inner cycle converges before its outer cycle. The issue is that the inner cycle counted on the outer most cycle to do the dependency flattening. But the inner cycle now suddenly needs to know its own flattened dependencies across all previous iterations. We could probably make this approach work, but it would require that the inner cycle walks its dependencies from the previous iteration, and replaces its dependency on the outer-most query with its flattened dependencies. However, it's not clear to me how to detect the outer-most cycle without storing it in the Memo. Ultimately, this didn't seem worthwhile, given there's no meaningful performance regression on ty (one benchmark shows a 1% regression)
• The memory overhead can be substantial for large cycles if they have many dependencies, because most dependencies are duplicated across all heads participating in the same cycle. It would be nice if there were some structural sharing to reduce the overhead, but I consider this a follow-up. I also think that there are much bigger opportunities in Salsa to reduce memory usage (immortal durability, within the same revision LRU).

Alternative solutions

I still think the ideal is for Salsa to store multiple memos for queries participating in fixpoint, and for the iteration count to be part of the QueryEdge. This would remove much of the special casing required for fixpoint iteration and fit more naturally into Salsa's overall design. It probably would also set the foundation for speculative execution, where an iteration is "one speculative execution", but we could use other keys.

I decided not to explore this further because there are some big open questions, where it was unclear to me how to resolve them in the limited time I had available:

• How can we store multiple memos?
• Should the iteration count be part of the DatabaseKeyIndex or separate? I think it must be a single key; the caller of fetch doesn't know what the "latest" iteration of a given query is. But it always wants the most recent value.
• How can we include the iteration count in the QueryEdge without increasing its size?
• How does locking work? Validating different iterations of the same query in maybe_changed_after shouldn't result in a cycle, but acquiring the lock for the key without an iteration should.

How to support diff_outputs?

I don't think there's an open issue for it, but our fixpoint handling is prone to removing outputs and tracked structs too early for queries participating in a cycle. Salsa diffs the outputs immediately after completing an iteration. However, some outputs (including tracked structs) might only have been created in later iterations. Salsa deleting them in the first iteration is overly aggressive (and it used to be unsound #980). To fix this, it would be very helpful if there were a hook to finalize all cycle participants, rather than our current lazy validation.

My initial approach to this PR used eager validation, but that didn't handle the case where a nested cycle converges before the outer cycle. So I switched to flattening all cycle head dependencies; however, that also means that walking the dependency tree during finalization no longer contains the full dependency tree, making eager finalization impossible (or we'd have to retain the query dependencies in a different way). But I think there's still a solution to this problem, but we have to defer diff_outputs to the next revision.

I don't have this fully figured out but my thinking is along these lines:

• Store the old-memo's revision metadata on the memo when completing the first iteration and carry that information forward across all later iterations.
• When completing a query, check if this is the initial iteration and the old_memo has prev_revision_metadata set. If so, diff the prev_revision_metadata with the old_memo.input_outputs and delete any no-longer-created outputs.

Notes for reviewer

This hopefully fixes #1023

For some more context, see the write up in https://hackmd.io/XCIIyYjlQkuVg33THEr4iQ

This PR is based on top of #1063 because it removes the need to special-case fallback-immediate.