Cycle recovery #6
Comments
|
One option is to walk the stack whenever we encounter a cycle and mark all the participants in some way. We could then avoid caching their return values. Or, even more extreme, we could ignore their results altogether and just propagate back dummy return values. (That is, the query can finish executing as normal, but its return value is ignoring, and some kind of default or cycle value is propagated back. Obviously this is related to the idea of terminating unwanted queries early.) To just skip caching would be relatively easy. Each active query would carry some If we wanted to propagate back errors, we have to extend the system slightly to know what value to return. You could imagine this working like so: in order to recover from a cycle, a query must have a defined return value like I'm a bit concerned that having to "opt in" to cycle handling will error prone, though. Perhaps just "no cache" is a better starting point. |
|
Here's the bit of IntelliJ that deals with this issue: https://github.com/JetBrains/intellij-community/blob/9d69a9c4245956ce063b20b1bf99165422dfefc2/platform/util/src/com/intellij/openapi/util/RecursionManager.java#L17-L37 (RecursionManager is what you get when you mix FP and OOP) |
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
892: Type aliases r=matklad a=flodiebold This implements type aliases (i.e. `type` definitions). There's just one snag: handling recursion. E.g. `type Foo = Foo` makes type inference panic with a query cycle. I think the best way to handle this would be if Salsa provided the ability to catch cycle errors? It seems that there's some work underway to support this [here](salsa-rs/salsa#6) and [here](salsa-rs/salsa#147). Should we wait for this? I don't see a good way to handle this without help from Salsa. Co-authored-by: Florian Diebold <flodiebold@gmail.com>
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
- adopt the new `Durability` API proposed in [RFC salsa-rs#6] - Adopt `AtomicU64` for `runtimeId` (salsa-rs#182) - use `ptr::eq` and `ptr::hash` for readability - upgrade parking lot - remove needless clone [RFC salsa-rs#6]: salsa-rs/salsa-rfcs#6
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
Quickest POC I could create to get some potentially cyclic queries to not panic and instead return a result I could act on. (gluon's module importing need to error on cycles). ``` // Causes `db.query()` to actually return `Result<V, CycleError>` fn query(&self, key: K, key2: K2) -> V; ``` A proper implementation of this would likely return `Result<V, CycleError<(K, K2)>>` or maybe larger changes are needed. cc salsa-rs#6
|
Is there an approach to this we can use today? Thank you |
|
We've got this |
So handling cycles has traditionally been a thorny issue. Right now the code panics in the event of a cycle. We probably want this to stay an option, but it's probably not the best choice long term — particularly since it often happens that the order of queries is determined by user input (and hence that cycles are somewhat out of our control).
This issue is focused on the case where a cycle represents an error. I'm going to open a sister issue to focus on the case of "succesful cyclic computations".
One challenge with cycles is that they can easily lead to non-determinism. For example, imagine that we return a
Result— if that is not faithfully propagated up the entire cycle, that implies thatfoo.query().get(K)could sometimes yieldOk(the root call) and other times yieldErr(the cyclic call). This somewhat invalidates all the memoized results in the middle, since they are dependent upon theErrresult. But if we had executed things in another order, things might have turned out differently. This is undesirable. It's particularly bad if we cache such results.The text was updated successfully, but these errors were encountered: