]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //! Code for projecting associated types out of trait references. |
2 | ||
1a4d82fc | 3 | use super::PredicateObligation; |
1a4d82fc | 4 | |
3157f602 | 5 | use rustc_data_structures::snapshot_map::{Snapshot, SnapshotMap}; |
ba9703b0 XL |
6 | use rustc_middle::ty::fold::TypeFoldable; |
7 | use rustc_middle::ty::{self, Ty}; | |
74b04a01 | 8 | |
ba9703b0 | 9 | pub use rustc_middle::traits::Reveal; |
1a4d82fc JJ |
10 | |
11 | #[derive(Clone)] | |
12 | pub struct MismatchedProjectionTypes<'tcx> { | |
dfeec247 | 13 | pub err: ty::error::TypeError<'tcx>, |
1a4d82fc JJ |
14 | } |
15 | ||
60c5eb7d | 16 | #[derive(Clone, TypeFoldable)] |
dfeec247 | 17 | pub struct Normalized<'tcx, T> { |
1a4d82fc JJ |
18 | pub value: T, |
19 | pub obligations: Vec<PredicateObligation<'tcx>>, | |
20 | } | |
21 | ||
22 | pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>; | |
23 | ||
dfeec247 XL |
24 | impl<'tcx, T> Normalized<'tcx, T> { |
25 | pub fn with<U>(self, value: U) -> Normalized<'tcx, U> { | |
74b04a01 | 26 | Normalized { value, obligations: self.obligations } |
1a4d82fc JJ |
27 | } |
28 | } | |
29 | ||
3157f602 XL |
30 | // # Cache |
31 | ||
0bf4aa26 | 32 | /// The projection cache. Unlike the standard caches, this can include |
9fa01778 | 33 | /// infcx-dependent type variables, therefore we have to roll the |
0bf4aa26 XL |
34 | /// cache back each time we roll a snapshot back, to avoid assumptions |
35 | /// on yet-unresolved inference variables. Types with placeholder | |
36 | /// regions also have to be removed when the respective snapshot ends. | |
3b2f2976 XL |
37 | /// |
38 | /// Because of that, projection cache entries can be "stranded" and left | |
39 | /// inaccessible when type variables inside the key are resolved. We make no | |
40 | /// attempt to recover or remove "stranded" entries, but rather let them be | |
41 | /// (for the lifetime of the infcx). | |
42 | /// | |
43 | /// Entries in the projection cache might contain inference variables | |
9fa01778 | 44 | /// that will be resolved by obligations on the projection cache entry (e.g., |
3b2f2976 | 45 | /// when a type parameter in the associated type is constrained through |
9fa01778 | 46 | /// an "RFC 447" projection on the impl). |
3b2f2976 XL |
47 | /// |
48 | /// When working with a fulfillment context, the derived obligations of each | |
49 | /// projection cache entry will be registered on the fulfillcx, so any users | |
50 | /// that can wait for a fulfillcx fixed point need not care about this. However, | |
0731742a | 51 | /// users that don't wait for a fixed point (e.g., trait evaluation) have to |
3b2f2976 XL |
52 | /// resolve the obligations themselves to make sure the projected result is |
53 | /// ok and avoid issues like #43132. | |
54 | /// | |
55 | /// If that is done, after evaluation the obligations, it is a good idea to | |
56 | /// call `ProjectionCache::complete` to make sure the obligations won't be | |
57 | /// re-evaluated and avoid an exponential worst-case. | |
9fa01778 XL |
58 | // |
59 | // FIXME: we probably also want some sort of cross-infcx cache here to | |
60 | // reduce the amount of duplication. Let's see what we get with the Chalk reforms. | |
0bf4aa26 | 61 | #[derive(Default)] |
3157f602 | 62 | pub struct ProjectionCache<'tcx> { |
3b2f2976 XL |
63 | map: SnapshotMap<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>, |
64 | } | |
65 | ||
66 | #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] | |
67 | pub struct ProjectionCacheKey<'tcx> { | |
dfeec247 | 68 | ty: ty::ProjectionTy<'tcx>, |
3b2f2976 XL |
69 | } |
70 | ||
ba9703b0 XL |
71 | impl ProjectionCacheKey<'tcx> { |
72 | pub fn new(ty: ty::ProjectionTy<'tcx>) -> Self { | |
73 | Self { ty } | |
3b2f2976 | 74 | } |
3157f602 XL |
75 | } |
76 | ||
77 | #[derive(Clone, Debug)] | |
ba9703b0 | 78 | pub enum ProjectionCacheEntry<'tcx> { |
3157f602 XL |
79 | InProgress, |
80 | Ambiguous, | |
81 | Error, | |
3b2f2976 | 82 | NormalizedTy(NormalizedTy<'tcx>), |
3157f602 XL |
83 | } |
84 | ||
0731742a | 85 | // N.B., intentionally not Clone |
3157f602 | 86 | pub struct ProjectionCacheSnapshot { |
3b2f2976 | 87 | snapshot: Snapshot, |
3157f602 XL |
88 | } |
89 | ||
90 | impl<'tcx> ProjectionCache<'tcx> { | |
0531ce1d XL |
91 | pub fn clear(&mut self) { |
92 | self.map.clear(); | |
93 | } | |
94 | ||
3157f602 XL |
95 | pub fn snapshot(&mut self) -> ProjectionCacheSnapshot { |
96 | ProjectionCacheSnapshot { snapshot: self.map.snapshot() } | |
97 | } | |
98 | ||
99 | pub fn rollback_to(&mut self, snapshot: ProjectionCacheSnapshot) { | |
a1dfa0c6 | 100 | self.map.rollback_to(snapshot.snapshot); |
3157f602 XL |
101 | } |
102 | ||
0bf4aa26 | 103 | pub fn rollback_placeholder(&mut self, snapshot: &ProjectionCacheSnapshot) { |
a1dfa0c6 | 104 | self.map.partial_rollback(&snapshot.snapshot, &|k| k.ty.has_re_placeholders()); |
c30ab7b3 SL |
105 | } |
106 | ||
a1dfa0c6 XL |
107 | pub fn commit(&mut self, snapshot: ProjectionCacheSnapshot) { |
108 | self.map.commit(snapshot.snapshot); | |
3157f602 XL |
109 | } |
110 | ||
111 | /// Try to start normalize `key`; returns an error if | |
3b2f2976 | 112 | /// normalization already occurred (this error corresponds to a |
3157f602 | 113 | /// cache hit, so it's actually a good thing). |
ba9703b0 | 114 | pub fn try_start( |
dfeec247 XL |
115 | &mut self, |
116 | key: ProjectionCacheKey<'tcx>, | |
117 | ) -> Result<(), ProjectionCacheEntry<'tcx>> { | |
c30ab7b3 SL |
118 | if let Some(entry) = self.map.get(&key) { |
119 | return Err(entry.clone()); | |
3157f602 XL |
120 | } |
121 | ||
122 | self.map.insert(key, ProjectionCacheEntry::InProgress); | |
123 | Ok(()) | |
124 | } | |
125 | ||
ea8adc8c | 126 | /// Indicates that `key` was normalized to `value`. |
ba9703b0 | 127 | pub fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: NormalizedTy<'tcx>) { |
dfeec247 XL |
128 | debug!( |
129 | "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}", | |
130 | key, value | |
131 | ); | |
ea8adc8c | 132 | let fresh_key = self.map.insert(key, ProjectionCacheEntry::NormalizedTy(value)); |
3157f602 XL |
133 | assert!(!fresh_key, "never started projecting `{:?}`", key); |
134 | } | |
135 | ||
3b2f2976 XL |
136 | /// Mark the relevant projection cache key as having its derived obligations |
137 | /// complete, so they won't have to be re-computed (this is OK to do in a | |
138 | /// snapshot - if the snapshot is rolled back, the obligations will be | |
139 | /// marked as incomplete again). | |
140 | pub fn complete(&mut self, key: ProjectionCacheKey<'tcx>) { | |
141 | let ty = match self.map.get(&key) { | |
142 | Some(&ProjectionCacheEntry::NormalizedTy(ref ty)) => { | |
dfeec247 | 143 | debug!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty); |
3b2f2976 XL |
144 | ty.value |
145 | } | |
146 | ref value => { | |
147 | // Type inference could "strand behind" old cache entries. Leave | |
148 | // them alone for now. | |
dfeec247 XL |
149 | debug!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value); |
150 | return; | |
3b2f2976 XL |
151 | } |
152 | }; | |
153 | ||
dfeec247 XL |
154 | self.map.insert( |
155 | key, | |
156 | ProjectionCacheEntry::NormalizedTy(Normalized { value: ty, obligations: vec![] }), | |
157 | ); | |
3b2f2976 XL |
158 | } |
159 | ||
94b46f34 XL |
160 | /// A specialized version of `complete` for when the key's value is known |
161 | /// to be a NormalizedTy. | |
162 | pub fn complete_normalized(&mut self, key: ProjectionCacheKey<'tcx>, ty: &NormalizedTy<'tcx>) { | |
163 | // We want to insert `ty` with no obligations. If the existing value | |
a1dfa0c6 XL |
164 | // already has no obligations (as is common) we don't insert anything. |
165 | if !ty.obligations.is_empty() { | |
dfeec247 XL |
166 | self.map.insert( |
167 | key, | |
168 | ProjectionCacheEntry::NormalizedTy(Normalized { | |
169 | value: ty.value, | |
170 | obligations: vec![], | |
171 | }), | |
172 | ); | |
94b46f34 XL |
173 | } |
174 | } | |
175 | ||
3157f602 XL |
176 | /// Indicates that trying to normalize `key` resulted in |
177 | /// ambiguity. No point in trying it again then until we gain more | |
178 | /// type information (in which case, the "fully resolved" key will | |
179 | /// be different). | |
ba9703b0 | 180 | pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) { |
3157f602 XL |
181 | let fresh = self.map.insert(key, ProjectionCacheEntry::Ambiguous); |
182 | assert!(!fresh, "never started projecting `{:?}`", key); | |
183 | } | |
184 | ||
185 | /// Indicates that trying to normalize `key` resulted in | |
186 | /// error. | |
ba9703b0 | 187 | pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) { |
3157f602 XL |
188 | let fresh = self.map.insert(key, ProjectionCacheEntry::Error); |
189 | assert!(!fresh, "never started projecting `{:?}`", key); | |
190 | } | |
191 | } |