Struct rustc_trait_selection::traits::select::ProvisionalEvaluationCache

pub(in traits::select) struct ProvisionalEvaluationCache<'tcx> {
    dfn: Cell<usize>,
    reached_depth: Cell<usize>,
    map: RefCell<FxHashMap<PolyTraitRef<'tcx>, ProvisionalEvaluation>>,
}

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

reached_depth: Cell<usize>

Stores the "coldest" depth (bottom of stack) reached by any of the evaluation entries. The idea here is that all things in the provisional cache are always dependent on something that is colder in the stack: therefore, if we add a new entry that is dependent on something colder still, we have to modify the depth for all entries at once.

Example:

Imagine we have a stack A B C D E (with E being the top of the stack). We cache something with depth 2, which means that it was dependent on C. Then we pop E but go on and process a new node F: A B C D F. Now F adds something to the cache with depth 1, meaning it is dependent on B. Our original cache entry is also dependent on B, because there is a path from E to C and then from C to F and from F to B.

map: RefCell<FxHashMap<PolyTraitRef<'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 dependices 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.

Implementations

impl<'tcx> ProvisionalEvaluationCache<'tcx>

pub(in traits::select) fn next_dfn(
    &self
) -> usize

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

pub(in traits::select) fn get_provisional(
    &self,
    fresh_trait_ref: PolyTraitRef<'tcx>
) -> Option<EvaluationResult>

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 self.current_reached_depth() and above.

pub(in traits::select) fn current_reached_depth(
    &self
) -> usize

Current value of the reached_depth counter -- all the provisional cache entries are dependent on the item at this depth.

pub(in traits::select) fn insert_provisional(
    &self,
    from_dfn: usize,
    reached_depth: usize,
    fresh_trait_ref: PolyTraitRef<'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_ref and resulted in result.

pub(in traits::select) 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.

pub(in traits::select) fn on_completion(
    &self,
    depth: usize,
    op: impl FnMut(PolyTraitRef<'tcx>, EvaluationResult)
)

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). The callback op will be invoked for each provisional entry that we can now confirm.

Trait Implementations

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

pub fn default() -> Self

Returns the "default value" for a type.