I'm a bit surprised we never carry forward the query's dependencies that ended up in a cycle. The query only depends on the cycle_result's dependencies. This seems wrong to me as it means the query will only re-run if a dependency read in cycle_result changes but not if a dependency changes that was read before hitting the cycle.

We also don't carry forward the active query's durability, whether it has untracked reads, accumulated values, ...

For example, if you have something like this:

#[salsa::input]
struct Input {
    value1: i32,
	value2: i32
}

#[salsa::tracked(cycle_result=cycle_result)]
fn has_cycle(db: &dyn Database, input: Input) -> i32 {
	let value = input.value1(db);
	if value == 0 {
	    has_cycle(db, input)		
	} else {
		value
	}
}

fn cycle_result(db: &dyn Database, _id: salsa::Id, input: Input) -> i32 {
    input.value2(db)
}

This query will depend only on value2, not value1.

We would also need to re-run the query if it turns out that the durability, changed at, or any other metadata field of the completed query differs from the metadata of the inserted fallback immediate memo, to ensure the metadata correctly propagates back to queries that have read the fallback immediate memo.

The first part could be fixed by using the metadata from the completed query put preserving the value from the fallback immediate memo.

The second issue would require running a second iteration (or multiple?)

I think I funnily just ran into a bug with rust-analyzer that could be explained by some of this (because it did involve a cycle that I caued in code by accident replacing type T = Complex<Type, ...> with type T = T, undoing that did not seem to have refreshed dependent use sites correctly).

Haha, that's funny

I'm starting to believe that today's fixpoint handling is sufficient to support fallback immedate but proper and with good test coverage. The only downsides are that it requires 2 executions instead of one, that Value must be Clone, and it requires a somewhat useless C::value_equals call. But these should be pretty insubstantial in the grand scheme of things.

All it really comes down to is that fallback immediate is a cycle recovery function that always returns the previous value and discards the new value. Returning the previous value guarantees that the cycle converges immediately. However, this requires that Value is Clone because the recovery function only gets a borrowed previous value.

Not only eliminates this any non-determinism, it also simplifies Salsa a good deal and comes with much better test coverage.

@Veykril would a Clone requirement be okay for r-a?

Actually, it doesn't even require an extra iteration. The query converges immediately unless the query metadata (durability, changed at etc) changed. Which is precisely what we want.

The only extra overhead is an extra clone and eq call, which in my view, doesn't justify the added complexity of maintaining both modes

Given we use this cycle handling variant only for actual invalid inputs / user errors the cloning is probably irrelevant for us here, so sounds reasonable.

How can this happen?

Using the example from above (and assuming bug 1 is fixed). Let's say value1 has a low durability and value2 has a high durability.

The fallback value has high durability because it only reads value2. Any query that now reads has_cycle before its execution completes sees that it has durability high and inherits the durability (unless it reads other direct or transitive inputs).

However, has_cycle should have a durability of low because it reads value1. Updating the durability on the memo that we insert isn't enough because we also need to update the durability on the queries that read has_cycle.

I recently added the low_durability_cycle_enter_from_different_head test which captures this problematic for fixpoint iteration

Okay, there's one difference between the two. FallbackImmediate uses the fallback value for all queries marked with cycle_result that participate in the same cycle (but not normal queries that participate in the same cycle. That's fine because they can never be called from a query outside the cycle).

With fixpoint, only the cycle heads use the fallback value. Other heads that participate in the cycle but don't form a cycle of their own compute their value as usual.

This behavior is tested by cycle_a_t1_b_t2_fallback.rs:

• FallbackImmediate: Both query_a and query_b return their fallback value
• Fixpoint based "fallback immediate": query_a computes it's result as normal (returning FALLBACK_B | OFFSET_A) and only query_b returns the fallback value

Is this distinction important for r-a?

I don't think that's true? I believe FallbackImmediate should also use the fallback value only for the head.

If it is true, then I'm not sure it should be true...

I'm not sure why the behavior is as it is but my impression is that it uses the fallback value for all queries with a cycle_result attribute

This is because of the code here