Expand description
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§
- Global
Cache - Paths
ToNested - 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.
- Search
Graph
Enums§
- AllPaths
ToHead Coinductive - For each goal we track whether the paths from this goal to its cycle heads are coinductive.
- Path
Kind - 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.
- Usage
Kind - 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 ofInterner
as users of the shared type library shouldn’t have to care aboutInput
andResult
as they are implementation details of the search graph. - Delegate