]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //! Code for projecting associated types out of trait references. |
2 | ||
1a4d82fc | 3 | use super::PredicateObligation; |
1a4d82fc | 4 | |
f9f354fc XL |
5 | use crate::infer::InferCtxtUndoLogs; |
6 | ||
7 | use rustc_data_structures::{ | |
8 | snapshot_map::{self, SnapshotMapRef, SnapshotMapStorage}, | |
9 | undo_log::Rollback, | |
10 | }; | |
ba9703b0 | 11 | use rustc_middle::ty::{self, Ty}; |
74b04a01 | 12 | |
a2a8927a | 13 | pub use rustc_middle::traits::{EvaluationResult, Reveal}; |
1a4d82fc | 14 | |
f9f354fc XL |
15 | pub(crate) type UndoLog<'tcx> = |
16 | snapshot_map::UndoLog<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>; | |
17 | ||
1a4d82fc JJ |
18 | #[derive(Clone)] |
19 | pub struct MismatchedProjectionTypes<'tcx> { | |
dfeec247 | 20 | pub err: ty::error::TypeError<'tcx>, |
1a4d82fc JJ |
21 | } |
22 | ||
064997fb | 23 | #[derive(Clone, TypeFoldable, TypeVisitable)] |
dfeec247 | 24 | pub struct Normalized<'tcx, T> { |
1a4d82fc JJ |
25 | pub value: T, |
26 | pub obligations: Vec<PredicateObligation<'tcx>>, | |
27 | } | |
28 | ||
29 | pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>; | |
30 | ||
dfeec247 XL |
31 | impl<'tcx, T> Normalized<'tcx, T> { |
32 | pub fn with<U>(self, value: U) -> Normalized<'tcx, U> { | |
74b04a01 | 33 | Normalized { value, obligations: self.obligations } |
1a4d82fc JJ |
34 | } |
35 | } | |
36 | ||
3157f602 XL |
37 | // # Cache |
38 | ||
0bf4aa26 | 39 | /// The projection cache. Unlike the standard caches, this can include |
9fa01778 | 40 | /// infcx-dependent type variables, therefore we have to roll the |
0bf4aa26 XL |
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. | |
3b2f2976 XL |
44 | /// |
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). | |
49 | /// | |
50 | /// Entries in the projection cache might contain inference variables | |
9fa01778 | 51 | /// that will be resolved by obligations on the projection cache entry (e.g., |
3b2f2976 | 52 | /// when a type parameter in the associated type is constrained through |
9fa01778 | 53 | /// an "RFC 447" projection on the impl). |
3b2f2976 XL |
54 | /// |
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, | |
0731742a | 58 | /// users that don't wait for a fixed point (e.g., trait evaluation) have to |
3b2f2976 XL |
59 | /// resolve the obligations themselves to make sure the projected result is |
60 | /// ok and avoid issues like #43132. | |
61 | /// | |
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. | |
9fa01778 XL |
65 | // |
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. | |
f9f354fc XL |
68 | pub struct ProjectionCache<'a, 'tcx> { |
69 | map: &'a mut SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>, | |
70 | undo_log: &'a mut InferCtxtUndoLogs<'tcx>, | |
71 | } | |
72 | ||
5099ac24 | 73 | #[derive(Clone, Default)] |
f9f354fc XL |
74 | pub struct ProjectionCacheStorage<'tcx> { |
75 | map: SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>, | |
3b2f2976 XL |
76 | } |
77 | ||
78 | #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] | |
79 | pub struct ProjectionCacheKey<'tcx> { | |
9c376795 | 80 | ty: ty::AliasTy<'tcx>, |
3b2f2976 XL |
81 | } |
82 | ||
a2a8927a | 83 | impl<'tcx> ProjectionCacheKey<'tcx> { |
9c376795 | 84 | pub fn new(ty: ty::AliasTy<'tcx>) -> Self { |
ba9703b0 | 85 | Self { ty } |
3b2f2976 | 86 | } |
3157f602 XL |
87 | } |
88 | ||
89 | #[derive(Clone, Debug)] | |
ba9703b0 | 90 | pub enum ProjectionCacheEntry<'tcx> { |
3157f602 XL |
91 | InProgress, |
92 | Ambiguous, | |
b9856134 | 93 | Recur, |
3157f602 | 94 | Error, |
a2a8927a | 95 | NormalizedTy { |
5099ac24 | 96 | ty: Normalized<'tcx, ty::Term<'tcx>>, |
a2a8927a XL |
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. | |
107 | /// | |
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. | |
120 | /// | |
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 | |
125 | /// paragraph). | |
126 | /// This ensures that we do not lose any regions | |
127 | /// constraints that arise from processing the | |
128 | /// sub-obligations. | |
129 | complete: Option<EvaluationResult>, | |
130 | }, | |
3157f602 XL |
131 | } |
132 | ||
f9f354fc XL |
133 | impl<'tcx> ProjectionCacheStorage<'tcx> { |
134 | #[inline] | |
135 | pub(crate) fn with_log<'a>( | |
136 | &'a mut self, | |
137 | undo_log: &'a mut InferCtxtUndoLogs<'tcx>, | |
138 | ) -> ProjectionCache<'a, 'tcx> { | |
139 | ProjectionCache { map: &mut self.map, undo_log } | |
3157f602 | 140 | } |
f9f354fc | 141 | } |
3157f602 | 142 | |
f9f354fc XL |
143 | impl<'tcx> ProjectionCache<'_, 'tcx> { |
144 | #[inline] | |
145 | fn map( | |
146 | &mut self, | |
147 | ) -> SnapshotMapRef< | |
148 | '_, | |
149 | ProjectionCacheKey<'tcx>, | |
150 | ProjectionCacheEntry<'tcx>, | |
151 | InferCtxtUndoLogs<'tcx>, | |
152 | > { | |
153 | self.map.with_log(self.undo_log) | |
c30ab7b3 SL |
154 | } |
155 | ||
f9f354fc XL |
156 | pub fn clear(&mut self) { |
157 | self.map().clear(); | |
3157f602 XL |
158 | } |
159 | ||
160 | /// Try to start normalize `key`; returns an error if | |
3b2f2976 | 161 | /// normalization already occurred (this error corresponds to a |
3157f602 | 162 | /// cache hit, so it's actually a good thing). |
ba9703b0 | 163 | pub fn try_start( |
dfeec247 XL |
164 | &mut self, |
165 | key: ProjectionCacheKey<'tcx>, | |
166 | ) -> Result<(), ProjectionCacheEntry<'tcx>> { | |
f9f354fc XL |
167 | let mut map = self.map(); |
168 | if let Some(entry) = map.get(&key) { | |
c30ab7b3 | 169 | return Err(entry.clone()); |
3157f602 XL |
170 | } |
171 | ||
f9f354fc | 172 | map.insert(key, ProjectionCacheEntry::InProgress); |
3157f602 XL |
173 | Ok(()) |
174 | } | |
175 | ||
ea8adc8c | 176 | /// Indicates that `key` was normalized to `value`. |
5099ac24 FG |
177 | pub fn insert_term( |
178 | &mut self, | |
179 | key: ProjectionCacheKey<'tcx>, | |
180 | value: Normalized<'tcx, ty::Term<'tcx>>, | |
181 | ) { | |
dfeec247 XL |
182 | debug!( |
183 | "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}", | |
184 | key, value | |
185 | ); | |
b9856134 XL |
186 | let mut map = self.map(); |
187 | if let Some(ProjectionCacheEntry::Recur) = map.get(&key) { | |
188 | debug!("Not overwriting Recur"); | |
189 | return; | |
190 | } | |
a2a8927a XL |
191 | let fresh_key = |
192 | map.insert(key, ProjectionCacheEntry::NormalizedTy { ty: value, complete: None }); | |
3157f602 XL |
193 | assert!(!fresh_key, "never started projecting `{:?}`", key); |
194 | } | |
195 | ||
a2a8927a XL |
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) { | |
9c376795 | 203 | Some(ProjectionCacheEntry::NormalizedTy { ty, complete: _ }) => { |
a2a8927a XL |
204 | info!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty); |
205 | let mut ty = ty.clone(); | |
04454e1e | 206 | if result.must_apply_considering_regions() { |
a2a8927a XL |
207 | ty.obligations = vec![]; |
208 | } | |
209 | map.insert(key, ProjectionCacheEntry::NormalizedTy { ty, complete: Some(result) }); | |
210 | } | |
211 | ref value => { | |
212 | // Type inference could "strand behind" old cache entries. Leave | |
213 | // them alone for now. | |
214 | info!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value); | |
215 | } | |
216 | }; | |
217 | } | |
218 | ||
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, | |
222 | _ => None, | |
223 | }) | |
224 | } | |
225 | ||
3157f602 XL |
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 | |
229 | /// be different). | |
ba9703b0 | 230 | pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) { |
f9f354fc | 231 | let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous); |
3157f602 XL |
232 | assert!(!fresh, "never started projecting `{:?}`", key); |
233 | } | |
234 | ||
b9856134 XL |
235 | /// Indicates that while trying to normalize `key`, `key` was required to |
236 | /// be normalized again. Selection or evaluation should eventually report | |
237 | /// an error here. | |
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); | |
241 | } | |
242 | ||
3157f602 XL |
243 | /// Indicates that trying to normalize `key` resulted in |
244 | /// error. | |
ba9703b0 | 245 | pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) { |
f9f354fc | 246 | let fresh = self.map().insert(key, ProjectionCacheEntry::Error); |
3157f602 XL |
247 | assert!(!fresh, "never started projecting `{:?}`", key); |
248 | } | |
249 | } | |
f9f354fc XL |
250 | |
251 | impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> { | |
252 | fn reverse(&mut self, undo: UndoLog<'tcx>) { | |
253 | self.map.reverse(undo); | |
254 | } | |
255 | } |