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::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)]
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>,
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::ProjectionTy<'tcx>,
83 impl ProjectionCacheKey<'tcx> {
84 pub fn new(ty: ty::ProjectionTy<'tcx>) -> Self {
89 #[derive(Clone, Debug)]
90 pub enum ProjectionCacheEntry<'tcx> {
94 NormalizedTy(NormalizedTy<'tcx>),
97 impl<'tcx> ProjectionCacheStorage<'tcx> {
98 pub(crate) fn with_log<'a>(
100 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
101 ) -> ProjectionCache<'a, 'tcx> {
102 ProjectionCache { map: &mut self.map, undo_log }
106 impl<'tcx> ProjectionCache<'_, 'tcx> {
111 ProjectionCacheKey<'tcx>,
112 ProjectionCacheEntry<'tcx>,
113 InferCtxtUndoLogs<'tcx>,
115 self.map.with_log(self.undo_log)
118 pub fn clear(&mut self) {
122 /// Try to start normalize `key`; returns an error if
123 /// normalization already occurred (this error corresponds to a
124 /// cache hit, so it's actually a good thing).
127 key: ProjectionCacheKey<'tcx>,
128 ) -> Result<(), ProjectionCacheEntry<'tcx>> {
129 let mut map = self.map();
130 if let Some(entry) = map.get(&key) {
131 return Err(entry.clone());
134 map.insert(key, ProjectionCacheEntry::InProgress);
138 /// Indicates that `key` was normalized to `value`.
139 pub fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: NormalizedTy<'tcx>) {
141 "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
144 let fresh_key = self.map().insert(key, ProjectionCacheEntry::NormalizedTy(value));
145 assert!(!fresh_key, "never started projecting `{:?}`", key);
148 /// Mark the relevant projection cache key as having its derived obligations
149 /// complete, so they won't have to be re-computed (this is OK to do in a
150 /// snapshot - if the snapshot is rolled back, the obligations will be
151 /// marked as incomplete again).
152 pub fn complete(&mut self, key: ProjectionCacheKey<'tcx>) {
153 let mut map = self.map();
154 let ty = match map.get(&key) {
155 Some(&ProjectionCacheEntry::NormalizedTy(ref ty)) => {
156 debug!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty);
160 // Type inference could "strand behind" old cache entries. Leave
161 // them alone for now.
162 debug!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value);
169 ProjectionCacheEntry::NormalizedTy(Normalized { value: ty, obligations: vec![] }),
173 /// A specialized version of `complete` for when the key's value is known
174 /// to be a NormalizedTy.
175 pub fn complete_normalized(&mut self, key: ProjectionCacheKey<'tcx>, ty: &NormalizedTy<'tcx>) {
176 // We want to insert `ty` with no obligations. If the existing value
177 // already has no obligations (as is common) we don't insert anything.
178 if !ty.obligations.is_empty() {
181 ProjectionCacheEntry::NormalizedTy(Normalized {
189 /// Indicates that trying to normalize `key` resulted in
190 /// ambiguity. No point in trying it again then until we gain more
191 /// type information (in which case, the "fully resolved" key will
193 pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) {
194 let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous);
195 assert!(!fresh, "never started projecting `{:?}`", key);
198 /// Indicates that trying to normalize `key` resulted in
200 pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) {
201 let fresh = self.map().insert(key, ProjectionCacheEntry::Error);
202 assert!(!fresh, "never started projecting `{:?}`", key);
206 impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> {
207 fn reverse(&mut self, undo: UndoLog<'tcx>) {
208 self.map.reverse(undo);