src/librustc_infer/traits/project.rs

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