struct ProvisionalEvaluationCache<'tcx> {
dfn: Cell<usize>,
map: RefCell<FxIndexMap<PolyTraitPredicate<'tcx>, ProvisionalEvaluation>>,
wf_args: RefCell<Vec<(GenericArg<'tcx>, usize)>>,
}
Expand description
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<FxIndexMap<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
whereD
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 onB
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 forF
.
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§
source§impl<'tcx> ProvisionalEvaluationCache<'tcx>
impl<'tcx> ProvisionalEvaluationCache<'tcx>
sourcefn get_provisional(
&self,
fresh_trait_pred: PolyTraitPredicate<'tcx>,
) -> Option<ProvisionalEvaluation>
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).
sourcefn insert_provisional(
&self,
from_dfn: usize,
reached_depth: usize,
fresh_trait_pred: PolyTraitPredicate<'tcx>,
result: EvaluationResult,
)
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
.
sourcefn on_failure(&self, dfn: usize)
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.
sourcefn on_completion(&self, dfn: usize)
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§
Auto Trait Implementations§
impl<'tcx> !Freeze for ProvisionalEvaluationCache<'tcx>
impl<'tcx> !RefUnwindSafe for ProvisionalEvaluationCache<'tcx>
impl<'tcx> Send for ProvisionalEvaluationCache<'tcx>
impl<'tcx> !Sync for ProvisionalEvaluationCache<'tcx>
impl<'tcx> Unpin for ProvisionalEvaluationCache<'tcx>
impl<'tcx> !UnwindSafe for ProvisionalEvaluationCache<'tcx>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T, R> CollectAndApply<T, R> for T
impl<T, R> CollectAndApply<T, R> for T
source§impl<T> Filterable for T
impl<T> Filterable for T
source§fn filterable(
self,
filter_name: &'static str,
) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>
fn filterable( self, filter_name: &'static str, ) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>
source§impl<T> Instrument for T
impl<T> Instrument for T
source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T> IntoEither for T
impl<T> IntoEither for T
source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§impl<P> IntoQueryParam<P> for P
impl<P> IntoQueryParam<P> for P
fn into_query_param(self) -> P
source§impl<T> MaybeResult<T> for T
impl<T> MaybeResult<T> for T
source§impl<I, T, U> Upcast<I, U> for Twhere
U: UpcastFrom<I, T>,
impl<I, T, U> Upcast<I, U> for Twhere
U: UpcastFrom<I, T>,
source§impl<I, T> UpcastFrom<I, T> for T
impl<I, T> UpcastFrom<I, T> for T
fn upcast_from(from: T, _tcx: I) -> T
source§impl<Tcx, T> Value<Tcx> for Twhere
Tcx: DepContext,
impl<Tcx, T> Value<Tcx> for Twhere
Tcx: DepContext,
default fn from_cycle_error( tcx: Tcx, cycle_error: &CycleError, _guar: ErrorGuaranteed, ) -> T
source§impl<T> WithSubscriber for T
impl<T> WithSubscriber for T
source§fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
source§fn with_current_subscriber(self) -> WithDispatch<Self>
fn with_current_subscriber(self) -> WithDispatch<Self>
impl<'a, T> Captures<'a> for Twhere
T: ?Sized,
impl<T> ErasedDestructor for Twhere
T: 'static,
impl<T> MaybeSendSync for T
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: 104 bytes