Module search_graph

The search graph is responsible for caching and cycle detection in the trait solver. Making sure that caching doesn’t result in soundness bugs or unstable query results is very challenging and makes this one of the most-involved self-contained components of the compiler.

We added fuzzing support to test its correctness. The fuzzers used to verify the current implementation can be found in https://github.com/lcnr/search_graph_fuzz.

This is just a quick overview of the general design, please check out the relevant rustc-dev-guide chapter for more details. Caching is split between a global cache and the per-cycle provisional_cache. The global cache has to be completely unobservable, while the per-cycle cache may impact behavior as long as the resulting behavior is still correct.

Structs

GlobalCache

PathsToNested

Tracks how nested goals have been accessed. This is necessary to disable global cache entries if computing them would otherwise result in a cycle or access a provisional cache entry.

SearchGraph

Enums

AllPathsToHeadCoinductive

For each goal we track whether the paths from this goal to its cycle heads are coinductive.

PathKind

In the initial iteration of a cycle, we do not yet have a provisional result. In the case we return an initial provisional result depending on the kind of cycle.

UsageKind

The kinds of cycles a cycle head was involved in.

Traits

Cx

The search graph does not simply use Interner directly to enable its fuzzing without having to stub the rest of the interner. We don’t make this a super trait of Interner as users of the shared type library shouldn’t have to care about Input and Result as they are implementation details of the search graph.

Delegate