This PR is...kind of long. It reshapes the core logic of salsa to fix various bugs in cycle handling and generally simplify how we handle cross-thread coordination.
Best read commit by commit: every commit passes all tests, afaik.
The core bug I was taking aim at was the fact that, when you invoke
maybe_changed_since, you can sometimes wind up detecting a cycle without having pushed some of the relevant queries onto the stack. This is now fixed.
From a user's POV, ~~nothing changes from this PR~~, there are only minimal changes to the public interface. The biggest one is that recover functions now get a
&salsa::Cycle which has methods for accessing the participants; the other is that queries that are participating in cycle fallback will use unwinding to avoid executing past the point where the cycle is discovered. Otherwise, things work the same as before:
- If you encounter a cycle and all participant queries are marked with
#[salsa::recover], then they will take on the recovery value. (At the moment, they continue executing after the cycle is observed, but their final result is ignored; I plan to change this in a follow-up PR, or maybe some future commit to this PR.)
- If you encounter a cycle and some or all participants are NOT marked with
#[salsa::recover], then the code panics. This is treated like any other panic, cancelling all other work.
Along the way, I made... a few... other changes:
- Cross-thread handling is simplified. When we block on another thread, it no longer sends us a final result. Instead, it just gets re-awoken and then it retries the original request. This is helpful when you encounter cycles in
read, but it's also more compatible with some of the directions I have in mind.
- Cycle detection is simplified and more centrally coordinated. Previously, when a cycle was detected, we would mark all the participants on the current thread, but then we would mark other threads 'lazilly'. Now, threads move ownership of their stack into the shared dep graph when they block, so that we can mark all the stack frames at once. This also means less cloning on blocking, so it should be mildly more efficient.
- The code is DRY-er, since
maybe_changed_since has been re-implemented in terms of the same core building blocks as
probe and friends). I originally tried to unify them, but I realized that they behave somewhat differently from one another and both of them make sense. (In particular, we want to be able to free values with the LRU cache while still checking if they are up to date.)
Ah, I realize now that I had planned to write a bunch of docs in the salsa book before I landed this. Well, I'm going to open the PR anyway, as I've let this branch go far too long.