Caching and Cycle Handling in the New Trait Solver

# Caching in the new trait solver Caching results of the trait solver is necessary for performance. We have to make sure that it is sound. Caching is handled by the [`SearchGraph`] ## The global cache At its core, the cache is fairly straightforward. When evaluating a goal, we check whether it's in the global cache. If so, we reuse that entry. If not, we compute the goal and then store its result in the cache. To handle incremental compilation the computation of a goal happens inside of [`DepGraph::with_anon_task`][`with_anon_task`] which creates a new `DepNode` which depends on all queries used inside of this computation. When accessing the global cache we then read this `DepNode`, manually adding a dependency edge to all the queries used: [source][wdn]. ### Dealing with overflow Hitting the recursion limit is not fatal in the new trait solver but instead simply causes it to return ambiguity: [source][overflow]. Whether we hit the recursion limit can therefore change the result without resulting in a compilation failure. This means we must consider the remaining available depth when accessing a cache result. We do this by storing more information in the cache entry. For goals whose evaluation did not reach the recursion limit, we simply store its reached depth: [source][req-depth]. These results can freely be used as long as the current `available_depth` is higher than its `reached_depth`: [source][req-depth-ck]. We then update the reached depth of the current goal to make sure that whether we've used the global cache entry is not observable: [source][update-depth]. For goals which reach the recursion limit we currently only use the cached result if the available depth *exactly matches* the depth of the entry. The cache entry for each goal therefore contains a separate result for each remaining depth: [source][rem-depth].[^1] ## Handling cycles The trait solver has to support cycles. These cycles are either inductive or coinductive, depending on the participating goals. See the [chapter on coinduction] for more details. We distinguish between the cycle heads and the cycle root: a stack entry is a cycle head if it recursively accessed. The *root* is the deepest goal on the stack which is involved in any cycle. Given the following dependency tree, `A` and `B` are both cycle heads, while only `A` is a root. ```mermaid graph TB A --> B

This section describes the caching mechanism used in the new trait solver for performance, focusing on its soundness and implementation via the `SearchGraph`. It details the global cache's structure, including handling incremental compilation with `DepGraph`, managing recursion limits by storing depth information, and addressing cycles by distinguishing between cycle heads and roots. The aim is to efficiently reuse computed results while ensuring accurate and consistent behavior, especially in the presence of recursion and depth constraints.