1 //! Code for projecting associated types out of trait references.
3 use super::PredicateObligation;
5 use crate::infer::InferCtxtUndoLogs;
7 use rustc_data_structures::{
8 snapshot_map::{self, SnapshotMapRef, SnapshotMapStorage},
11 use rustc_middle::ty::{self, Ty};
13 pub use rustc_middle::traits::{EvaluationResult, Reveal};
15 pub(crate) type UndoLog<'tcx> =
16 snapshot_map::UndoLog<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>;
19 pub struct MismatchedProjectionTypes<'tcx> {
20 pub err: ty::error::TypeError<'tcx>,
23 #[derive(Clone, TypeFoldable, TypeVisitable)]
24 pub struct Normalized<'tcx, T> {
26 pub obligations: Vec<PredicateObligation<'tcx>>,
29 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
31 impl<'tcx, T> Normalized<'tcx, T> {
32 pub fn with<U>(self, value: U) -> Normalized<'tcx, U> {
33 Normalized { value, obligations: self.obligations }
39 /// The projection cache. Unlike the standard caches, this can include
40 /// infcx-dependent type variables, therefore we have to roll the
41 /// cache back each time we roll a snapshot back, to avoid assumptions
42 /// on yet-unresolved inference variables. Types with placeholder
43 /// regions also have to be removed when the respective snapshot ends.
45 /// Because of that, projection cache entries can be "stranded" and left
46 /// inaccessible when type variables inside the key are resolved. We make no
47 /// attempt to recover or remove "stranded" entries, but rather let them be
48 /// (for the lifetime of the infcx).
50 /// Entries in the projection cache might contain inference variables
51 /// that will be resolved by obligations on the projection cache entry (e.g.,
52 /// when a type parameter in the associated type is constrained through
53 /// an "RFC 447" projection on the impl).
55 /// When working with a fulfillment context, the derived obligations of each
56 /// projection cache entry will be registered on the fulfillcx, so any users
57 /// that can wait for a fulfillcx fixed point need not care about this. However,
58 /// users that don't wait for a fixed point (e.g., trait evaluation) have to
59 /// resolve the obligations themselves to make sure the projected result is
60 /// ok and avoid issues like #43132.
62 /// If that is done, after evaluation the obligations, it is a good idea to
63 /// call `ProjectionCache::complete` to make sure the obligations won't be
64 /// re-evaluated and avoid an exponential worst-case.
66 // FIXME: we probably also want some sort of cross-infcx cache here to
67 // reduce the amount of duplication. Let's see what we get with the Chalk reforms.
68 pub struct ProjectionCache<'a, 'tcx> {
69 map: &'a mut SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>,
70 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
73 #[derive(Clone, Default)]
74 pub struct ProjectionCacheStorage<'tcx> {
75 map: SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>,
78 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
79 pub struct ProjectionCacheKey<'tcx> {
80 ty: ty::AliasTy<'tcx>,
83 impl<'tcx> ProjectionCacheKey<'tcx> {
84 pub fn new(ty: ty::AliasTy<'tcx>) -> Self {
89 #[derive(Clone, Debug)]
90 pub enum ProjectionCacheEntry<'tcx> {
96 ty: Normalized<'tcx, ty::Term<'tcx>>,
97 /// If we were able to successfully evaluate the
98 /// corresponding cache entry key during predicate
99 /// evaluation, then this field stores the final
100 /// result obtained from evaluating all of the projection
101 /// sub-obligations. During evaluation, we will skip
102 /// evaluating the cached sub-obligations in `ty`
103 /// if this field is set. Evaluation only
104 /// cares about the final result, so we don't
105 /// care about any region constraint side-effects
106 /// produced by evaluating the sub-boligations.
108 /// Additionally, we will clear out the sub-obligations
109 /// entirely if we ever evaluate the cache entry (along
110 /// with all its sub obligations) to `EvaluatedToOk`.
111 /// This affects all users of the cache, not just evaluation.
112 /// Since a result of `EvaluatedToOk` means that there were
113 /// no region obligations that need to be tracked, it's
114 /// fine to forget about the sub-obligations - they
115 /// don't provide any additional information. However,
116 /// we do *not* discard any obligations when we see
117 /// `EvaluatedToOkModuloRegions` - we don't know
118 /// which sub-obligations may introduce region constraints,
119 /// so we keep them all to be safe.
121 /// When we are not performing evaluation
122 /// (e.g. in `FulfillmentContext`), we ignore this field,
123 /// and always re-process the cached sub-obligations
124 /// (which may have been cleared out - see the above
126 /// This ensures that we do not lose any regions
127 /// constraints that arise from processing the
129 complete: Option<EvaluationResult>,
133 impl<'tcx> ProjectionCacheStorage<'tcx> {
135 pub(crate) fn with_log<'a>(
137 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
138 ) -> ProjectionCache<'a, 'tcx> {
139 ProjectionCache { map: &mut self.map, undo_log }
143 impl<'tcx> ProjectionCache<'_, 'tcx> {
149 ProjectionCacheKey<'tcx>,
150 ProjectionCacheEntry<'tcx>,
151 InferCtxtUndoLogs<'tcx>,
153 self.map.with_log(self.undo_log)
156 pub fn clear(&mut self) {
160 /// Try to start normalize `key`; returns an error if
161 /// normalization already occurred (this error corresponds to a
162 /// cache hit, so it's actually a good thing).
165 key: ProjectionCacheKey<'tcx>,
166 ) -> Result<(), ProjectionCacheEntry<'tcx>> {
167 let mut map = self.map();
168 if let Some(entry) = map.get(&key) {
169 return Err(entry.clone());
172 map.insert(key, ProjectionCacheEntry::InProgress);
176 /// Indicates that `key` was normalized to `value`.
179 key: ProjectionCacheKey<'tcx>,
180 value: Normalized<'tcx, ty::Term<'tcx>>,
183 "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
186 let mut map = self.map();
187 if let Some(ProjectionCacheEntry::Recur) = map.get(&key) {
188 debug!("Not overwriting Recur");
192 map.insert(key, ProjectionCacheEntry::NormalizedTy { ty: value, complete: None });
193 assert!(!fresh_key, "never started projecting `{:?}`", key);
196 /// Mark the relevant projection cache key as having its derived obligations
197 /// complete, so they won't have to be re-computed (this is OK to do in a
198 /// snapshot - if the snapshot is rolled back, the obligations will be
199 /// marked as incomplete again).
200 pub fn complete(&mut self, key: ProjectionCacheKey<'tcx>, result: EvaluationResult) {
201 let mut map = self.map();
202 match map.get(&key) {
203 Some(ProjectionCacheEntry::NormalizedTy { ty, complete: _ }) => {
204 info!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty);
205 let mut ty = ty.clone();
206 if result.must_apply_considering_regions() {
207 ty.obligations = vec![];
209 map.insert(key, ProjectionCacheEntry::NormalizedTy { ty, complete: Some(result) });
212 // Type inference could "strand behind" old cache entries. Leave
213 // them alone for now.
214 info!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value);
219 pub fn is_complete(&mut self, key: ProjectionCacheKey<'tcx>) -> Option<EvaluationResult> {
220 self.map().get(&key).and_then(|res| match res {
221 ProjectionCacheEntry::NormalizedTy { ty: _, complete } => *complete,
226 /// Indicates that trying to normalize `key` resulted in
227 /// ambiguity. No point in trying it again then until we gain more
228 /// type information (in which case, the "fully resolved" key will
230 pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) {
231 let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous);
232 assert!(!fresh, "never started projecting `{:?}`", key);
235 /// Indicates that while trying to normalize `key`, `key` was required to
236 /// be normalized again. Selection or evaluation should eventually report
238 pub fn recur(&mut self, key: ProjectionCacheKey<'tcx>) {
239 let fresh = self.map().insert(key, ProjectionCacheEntry::Recur);
240 assert!(!fresh, "never started projecting `{:?}`", key);
243 /// Indicates that trying to normalize `key` resulted in
245 pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) {
246 let fresh = self.map().insert(key, ProjectionCacheEntry::Error);
247 assert!(!fresh, "never started projecting `{:?}`", key);
251 impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> {
252 fn reverse(&mut self, undo: UndoLog<'tcx>) {
253 self.map.reverse(undo);