Rollup merge of #60444 - nikomatsakis:issue-60010-cycle-error-investigation, r=pnkfelix

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

2 files changed, 91 insertions, 0 deletions

diff --git a/src/test/ui/traits/cycle-cache-err-60010.rs b/src/test/ui/traits/cycle-cache-err-60010.rs
new file mode 100644
index 00000000000..45aa1b3c522
--- /dev/null
+++ b/src/test/ui/traits/cycle-cache-err-60010.rs
@@ -0,0 +1,71 @@
+// Test that we properly detect the cycle amongst the traits
+// here and report an error.
+
+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, //~ ERROR overflow
+}
+
+impl Database for RootDatabase { //~ ERROR overflow
+    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 {
+    // This is not satisfied:
+    //
+    // - `RootDatabase: SourceDatabase`
+    //   - requires `RootDatabase: RefUnwindSafe` + `RootDatabase: HasQueryGroup`
+    // - `RootDatabase: RefUnwindSafe`
+    //   - requires `Runtime<RootDatabase>: RefUnwindSafe`
+    // - `Runtime<RootDatabase>: RefUnwindSafe`
+    //   - requires `DB::Storage: RefUnwindSafe` (`SalsaStorage: RefUnwindSafe`)
+    // - `SalsaStorage: RefUnwindSafe`
+    //    - requires `<ParseQuery as Query<RootDatabase>>::Data: RefUnwindSafe`,
+    //      which means `ParseQuery: Query<RootDatabase>`
+    // - `ParseQuery: Query<RootDatabase>`
+    //    - requires `RootDatabase: SourceDatabase`,
+    // - `RootDatabase: SourceDatabase` is already on the stack, so we have a
+    //   cycle with non-coinductive participants
+    //
+    // we used to fail to report an error here because we got the
+    // caching wrong.
+    SourceDatabase::parse(db);
+    22
+}
+
+fn main() {}
diff --git a/src/test/ui/traits/cycle-cache-err-60010.stderr b/src/test/ui/traits/cycle-cache-err-60010.stderr
new file mode 100644
index 00000000000..9192f7ba2e3
--- /dev/null
+++ b/src/test/ui/traits/cycle-cache-err-60010.stderr
@@ -0,0 +1,20 @@
+error[E0275]: overflow evaluating the requirement `RootDatabase: SourceDatabase`
+  --> $DIR/cycle-cache-err-60010.rs:27:5
+   |
+LL |     _parse: <ParseQuery as Query<RootDatabase>>::Data,
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `Query<RootDatabase>` for `ParseQuery`
+
+error[E0275]: overflow evaluating the requirement `RootDatabase: SourceDatabase`
+  --> $DIR/cycle-cache-err-60010.rs:30:6
+   |
+LL | impl Database for RootDatabase {
+   |      ^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `Query<RootDatabase>` for `ParseQuery`
+   = note: required because it appears within the type `SalsaStorage`
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0275`.