april 2018 trait resolution regression #60010
Comments
pnkfelix
changed the title
jonas-schievink
added
A-traits
|
This change in behavior might be a bugfix. I'm still trying to understand the further narrowed-down test case, where it seems like one of the crucial details is the handling of use std::panic::RefUnwindSafe;
trait Database { type Storage; }
trait HasQueryGroup { }
trait Query<DB> { type Data; }
trait SourceDatabase { fn parse(&self) { loop { } } }
struct ParseQuery;
struct RootDatabase { _runtime: Runtime<RootDatabase>, }
struct Runtime<DB: Database> { _storage: Box<DB::Storage> }
struct SalsaStorage { _parse: <ParseQuery as Query<RootDatabase>>::Data, }
impl Database for RootDatabase { type Storage = SalsaStorage; }
impl HasQueryGroup for RootDatabase {}
impl<DB> Query<DB> for ParseQuery where DB: SourceDatabase, DB: Database { type Data = RootDatabase; }
impl<T> SourceDatabase for T where T: RefUnwindSafe, T: HasQueryGroup {}
pub(crate) fn goto_implementation(db: &RootDatabase) -> u32 { db.parse(); loop { } }
fn main() { } |
|
(note in particular that in this example, we have a blanket implementation of (But I'm not yet sure whether Update: okay, |
|
For reference, here is the log of changes between the two relevant nightlies. (I just transcribed this directly from #58291 (comment) )
|
|
Okay I have now confirmed that this was injected by #48995 |
|
my current theory is that this is arising due to some interaction between inductive and co-inductive reasoning. In particular, if you focus in on the impl<T> SourceDatabase for T
where
T: RefUnwindSafe, // [1]
T: HasQueryGroup, // [2]
{}commenting out either line [1] or line [2] above from the original code will cause the whole source input to be acccepted. It is only when both are presented as preconditions on the blanket impl of I extended the that is, it thinks the attempt to prove And that last bit, struct SalsaStorage { _parse: <ParseQuery as Query<RootDatabase>>::Data, }
// ...
impl<DB> Query<DB> for ParseQuery where DB: SourceDatabase { type Data = RootDatabase; }so we now see why the compiler might reason that it has to prove But for some reason we don't hit the above problem if we remove the |
|
@pnkfelix I haven't had time to deeply look yet, but a few notes about induction/co-induction in general: In short, a cycle in trait resolution is only considered "true" if all the traits involved are co-inductive (i.e., auto-traits). So if you have But if you have In this case, then, I expect that cycle to be "non-true", because What I'm not sure about 100% is why the behavior changed here and whether the cycle ought to arise. |
|
Also curious: If you do There are two distinct systems for trait evaluation (the "evaluate" code and the "confirm" code) which, I suppose, are disagreeing here. Digging a bit more. |
…tion, r=<try> forego caching for all participants in cycles, apart from root node This is a targeted fix for #60010, which uncovered a pretty bad failure of our caching strategy in the face of coinductive cycles. The problem is explained in the comment in the PR on the new field, `in_cycle`, but I'll reproduce it here: > Starts out as false -- if, during evaluation, we encounter a > cycle, then we will set this flag to true for all participants > in the cycle (apart from the "head" node). These participants > will then forego caching their results. This is not the most > efficient solution, but it addresses #60010. The problem we > are trying to prevent: > > - If you have `A: AutoTrait` requires `B: AutoTrait` and `C: NonAutoTrait` > - `B: AutoTrait` requires `A: AutoTrait` (coinductive cycle, ok) > - `C: NonAutoTrait` requires `A: AutoTrait` (non-coinductive cycle, not ok) > > you don't want to cache that `B: AutoTrait` or `A: AutoTrait` > is `EvaluatedToOk`; this is because they were only considered > ok on the premise that if `A: AutoTrait` held, but we indeed > encountered a problem (later on) with `A: AutoTrait. So we > currently set a flag on the stack node for `B: AutoTrait` (as > well as the second instance of `A: AutoTrait`) to supress > caching. > > This is a simple, targeted fix. The correct fix requires > deeper changes, but would permit more caching: we could > basically defer caching until we have fully evaluated the > tree, and then cache the entire tree at once. I'm not sure what the impact of this fix will be in terms of existing crates or performance: we were accepting incorrect code before, so there will perhaps be some regressions, and we are now caching less. As the comment above notes, we could do a lot better than this fix, but that would involve more invasive rewrites. I thought it best to start with something simple. r? @pnkfelix -- but let's do crater/perf run cc @arielb1
…r-investigation, r=pnkfelix forego caching for all participants in cycles, apart from root node This is a targeted fix for rust-lang#60010, which uncovered a pretty bad failure of our caching strategy in the face of coinductive cycles. The problem is explained in the comment in the PR on the new field, `in_cycle`, but I'll reproduce it here: > Starts out as false -- if, during evaluation, we encounter a > cycle, then we will set this flag to true for all participants > in the cycle (apart from the "head" node). These participants > will then forego caching their results. This is not the most > efficient solution, but it addresses rust-lang#60010. The problem we > are trying to prevent: > > - If you have `A: AutoTrait` requires `B: AutoTrait` and `C: NonAutoTrait` > - `B: AutoTrait` requires `A: AutoTrait` (coinductive cycle, ok) > - `C: NonAutoTrait` requires `A: AutoTrait` (non-coinductive cycle, not ok) > > you don't want to cache that `B: AutoTrait` or `A: AutoTrait` > is `EvaluatedToOk`; this is because they were only considered > ok on the premise that if `A: AutoTrait` held, but we indeed > encountered a problem (later on) with `A: AutoTrait. So we > currently set a flag on the stack node for `B: AutoTrait` (as > well as the second instance of `A: AutoTrait`) to supress > caching. > > This is a simple, targeted fix. The correct fix requires > deeper changes, but would permit more caching: we could > basically defer caching until we have fully evaluated the > tree, and then cache the entire tree at once. I'm not sure what the impact of this fix will be in terms of existing crates or performance: we were accepting incorrect code before, so there will perhaps be some regressions, and we are now caching less. As the comment above notes, we could do a lot better than this fix, but that would involve more invasive rewrites. I thought it best to start with something simple. r? @pnkfelix -- but let's do crater/perf run cc @arielb1
|
I believe this is resolved by PR #60444, in the sense that we now issue: and furthermore, we do so independently of whatever the function body of Closing as fixed. |
(spawned off of #58291)
Reduced example (play):
original code:
https://gist.github.com/dc3f0f8568ca093d9750653578bb8026
The text was updated successfully, but these errors were encountered: