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

0 files changed, 0 insertions, 0 deletions