Struct rustc_trait_selection::traits::select::ProvisionalEvaluationCache

struct ProvisionalEvaluationCache<'tcx> {
    dfn: Cell<usize>,
    map: RefCell<FxHashMap<PolyTraitPredicate<'tcx>, ProvisionalEvaluation>>,
    wf_args: RefCell<Vec<(GenericArg<'tcx>, usize)>>,
}

The “provisional evaluation cache” is used to store intermediate cache results when solving auto traits. Auto traits are unusual in that they can support cycles. So, for example, a “proof tree” like this would be ok:

• Foo<T>: Send :-
  • Bar<T>: Send :-
    • Foo<T>: Send – cycle, but ok
  • Baz<T>: Send

Here, to prove Foo<T>: Send, we have to prove Bar<T>: Send and Baz<T>: Send. Proving Bar<T>: Send in turn required Foo<T>: Send. For non-auto traits, this cycle would be an error, but for auto traits (because they are coinductive) it is considered ok.

However, there is a complication: at the point where we have “proven” Bar<T>: Send, we have in fact only proven it provisionally. In particular, we proved that Bar<T>: Send under the assumption that Foo<T>: Send. But what if we later find out this assumption is wrong? Specifically, we could encounter some kind of error proving Baz<T>: Send. In that case, Bar<T>: Send didn’t turn out to be true.

In Issue #60010, we found a bug in rustc where it would cache these intermediate results. This was fixed in #60444 by disabling all caching for things involved in a cycle – in our example, that would mean we don’t cache that Bar<T>: Send. But this led to large slowdowns.

Specifically, imagine this scenario, where proving Baz<T>: Send first requires proving Bar<T>: Send (which is true:

• Foo<T>: Send :-
  • Bar<T>: Send :-
    • Foo<T>: Send – cycle, but ok
  • Baz<T>: Send
    • Bar<T>: Send – would be nice for this to be a cache hit!
    • *const T: Send – but what if we later encounter an error?

The provisional evaluation cache resolves this issue. It stores cache results that we’ve proven but which were involved in a cycle in some way. We track the minimal stack depth (i.e., the farthest from the top of the stack) that we are dependent on. The idea is that the cache results within are all valid – so long as none of the nodes in between the current node and the node at that minimum depth result in an error (in which case the cached results are just thrown away).

During evaluation, we consult this provisional cache and rely on it. Accessing a cached value is considered equivalent to accessing a result at reached_depth, so it marks the current solution as provisional as well. If an error is encountered, we toss out any provisional results added from the subtree that encountered the error. When we pop the node at reached_depth from the stack, we can commit all the things that remain in the provisional cache.

Fields

dfn: Cell<usize>

next “depth first number” to issue – just a counter

map: RefCell<FxHashMap<PolyTraitPredicate<'tcx>, ProvisionalEvaluation>>

Map from cache key to the provisionally evaluated thing. The cache entries contain the result but also the DFN in which they were added. The DFN is used to clear out values on failure.

Imagine we have a stack like:

• A B C and we add a cache for the result of C (DFN 2)
• Then we have a stack A B D where D has DFN 3
• We try to solve D by evaluating E: A B D E (DFN 4)
• E generates various cache entries which have cyclic dependencies on B
  • A B D E F and so forth
  • the DFN of F for example would be 5
• then we determine that E is in error – we will then clear all cache values whose DFN is >= 4 – in this case, that means the cached value for F.

wf_args: RefCell<Vec<(GenericArg<'tcx>, usize)>>

The stack of args that we assume to be true because a WF(arg) predicate is on the stack above (and because of wellformedness is coinductive). In an “ideal” world, this would share a stack with trait predicates in TraitObligationStack. However, trait predicates are much hotter than WellFormed predicates, and it’s very likely that the additional matches will have a perf effect. The value here is the well-formed GenericArg and the depth of the trait predicate above that well-formed predicate.

Implementations

impl<'tcx> ProvisionalEvaluationCache<'tcx>

fn next_dfn(&self) -> usize

Get the next DFN in sequence (basically a counter).

fn get_provisional(
    &self,
    fresh_trait_pred: PolyTraitPredicate<'tcx>
) -> Option<ProvisionalEvaluation>

Check the provisional cache for any result for fresh_trait_ref. If there is a hit, then you must consider it an access to the stack slots at depth reached_depth (from the returned value).

fn insert_provisional(
    &self,
    from_dfn: usize,
    reached_depth: usize,
    fresh_trait_pred: PolyTraitPredicate<'tcx>,
    result: EvaluationResult
)

Insert a provisional result into the cache. The result came from the node with the given DFN. It accessed a minimum depth of reached_depth to compute. It evaluated fresh_trait_pred and resulted in result.

fn on_failure(&self, dfn: usize)

Invoked when the node with dfn dfn does not get a successful result. This will clear out any provisional cache entries that were added since dfn was created. This is because the provisional entries are things which must assume that the things on the stack at the time of their creation succeeded – since the failing node is presently at the top of the stack, these provisional entries must either depend on it or some ancestor of it.

fn on_completion(&self, dfn: usize)

Invoked when the node at depth depth completed without depending on anything higher in the stack (if that completion was a failure, then on_failure should have been invoked already).

Note that we may still have provisional cache items remaining in the cache when this is done. For example, if there is a cycle:

• A depends on…
  • B depends on A
  • C depends on…
    • D depends on C
  • …

Then as we complete the C node we will have a provisional cache with results for A, B, C, and D. This method would clear out the C and D results, but leave A and B provisional.

This is determined based on the DFN: we remove any provisional results created since dfn started (e.g., in our example, dfn would be 2, representing the C node, and hence we would remove the result for D, which has DFN 3, but not the results for A and B, which have DFNs 0 and 1 respectively).

Note that we do not attempt to cache these cycle participants in the evaluation cache. Doing so would require carefully computing the correct DepNode to store in the cache entry: cycle participants may implicitly depend on query results related to other participants in the cycle, due to our logic which examines the evaluation stack.

We used to try to perform this caching, but it lead to multiple incremental compilation ICEs (see #92987 and #96319), and was very hard to understand. Fortunately, removing the caching didn’t seem to have a performance impact in practice.

Trait Implementations

impl<'tcx> Default for ProvisionalEvaluationCache<'tcx>

fn default() -> Self

Returns the “default value” for a type.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference’s “Type Layout” chapter for details on type layout guarantees.

Size: 80 bytes