src/librustc_infer/traits/project.rs

   1 //! Code for projecting associated types out of trait references.
   2
   3 use super::PredicateObligation;
   4
   5 use crate::infer::InferCtxtUndoLogs;
   6
   7 use rustc_data_structures::{
   8     snapshot_map::{self, SnapshotMapRef, SnapshotMapStorage},
   9     undo_log::Rollback,
  10 };
  11 use rustc_middle::ty::{self, Ty};
  12
  13 pub use rustc_middle::traits::Reveal;
  14
  15 pub(crate) type UndoLog<'tcx> =
  16     snapshot_map::UndoLog<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>;
  17
  18 #[derive(Clone)]
  19 pub struct MismatchedProjectionTypes<'tcx> {
  20     pub err: ty::error::TypeError<'tcx>,
  21 }
  22
  23 #[derive(Clone, TypeFoldable)]
  24 pub struct Normalized<'tcx, T> {
  25     pub value: T,
  26     pub obligations: Vec<PredicateObligation<'tcx>>,
  27 }
  28
  29 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
  30
  31 impl<'tcx, T> Normalized<'tcx, T> {
  32     pub fn with<U>(self, value: U) -> Normalized<'tcx, U> {
  33         Normalized { value, obligations: self.obligations }
  34     }
  35 }
  36
  37 // # Cache
  38
  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.
  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
  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).
  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,
  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.
  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.
  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.
  68 pub struct ProjectionCache<'a, 'tcx> {
  69     map: &'a mut SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>,
  70     undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
  71 }
  72
  73 #[derive(Default)]
  74 pub struct ProjectionCacheStorage<'tcx> {
  75     map: SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>,
  76 }
  77
  78 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  79 pub struct ProjectionCacheKey<'tcx> {
  80     ty: ty::ProjectionTy<'tcx>,
  81 }
  82
  83 impl ProjectionCacheKey<'tcx> {
  84     pub fn new(ty: ty::ProjectionTy<'tcx>) -> Self {
  85         Self { ty }
  86     }
  87 }
  88
  89 #[derive(Clone, Debug)]
  90 pub enum ProjectionCacheEntry<'tcx> {
  91     InProgress,
  92     Ambiguous,
  93     Error,
  94     NormalizedTy(NormalizedTy<'tcx>),
  95 }
  96
  97 impl<'tcx> ProjectionCacheStorage<'tcx> {
  98     #[inline]
  99     pub(crate) fn with_log<'a>(
 100         &'a mut self,
 101         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 102     ) -> ProjectionCache<'a, 'tcx> {
 103         ProjectionCache { map: &mut self.map, undo_log }
 104     }
 105 }
 106
 107 impl<'tcx> ProjectionCache<'_, 'tcx> {
 108     #[inline]
 109     fn map(
 110         &mut self,
 111     ) -> SnapshotMapRef<
 112         '_,
 113         ProjectionCacheKey<'tcx>,
 114         ProjectionCacheEntry<'tcx>,
 115         InferCtxtUndoLogs<'tcx>,
 116     > {
 117         self.map.with_log(self.undo_log)
 118     }
 119
 120     pub fn clear(&mut self) {
 121         self.map().clear();
 122     }
 123
 124     /// Try to start normalize `key`; returns an error if
 125     /// normalization already occurred (this error corresponds to a
 126     /// cache hit, so it's actually a good thing).
 127     pub fn try_start(
 128         &mut self,
 129         key: ProjectionCacheKey<'tcx>,
 130     ) -> Result<(), ProjectionCacheEntry<'tcx>> {
 131         let mut map = self.map();
 132         if let Some(entry) = map.get(&key) {
 133             return Err(entry.clone());
 134         }
 135
 136         map.insert(key, ProjectionCacheEntry::InProgress);
 137         Ok(())
 138     }
 139
 140     /// Indicates that `key` was normalized to `value`.
 141     pub fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: NormalizedTy<'tcx>) {
 142         debug!(
 143             "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
 144             key, value
 145         );
 146         let fresh_key = self.map().insert(key, ProjectionCacheEntry::NormalizedTy(value));
 147         assert!(!fresh_key, "never started projecting `{:?}`", key);
 148     }
 149
 150     /// Mark the relevant projection cache key as having its derived obligations
 151     /// complete, so they won't have to be re-computed (this is OK to do in a
 152     /// snapshot - if the snapshot is rolled back, the obligations will be
 153     /// marked as incomplete again).
 154     pub fn complete(&mut self, key: ProjectionCacheKey<'tcx>) {
 155         let mut map = self.map();
 156         let ty = match map.get(&key) {
 157             Some(&ProjectionCacheEntry::NormalizedTy(ref ty)) => {
 158                 debug!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty);
 159                 ty.value
 160             }
 161             ref value => {
 162                 // Type inference could "strand behind" old cache entries. Leave
 163                 // them alone for now.
 164                 debug!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value);
 165                 return;
 166             }
 167         };
 168
 169         map.insert(
 170             key,
 171             ProjectionCacheEntry::NormalizedTy(Normalized { value: ty, obligations: vec![] }),
 172         );
 173     }
 174
 175     /// A specialized version of `complete` for when the key's value is known
 176     /// to be a NormalizedTy.
 177     pub fn complete_normalized(&mut self, key: ProjectionCacheKey<'tcx>, ty: &NormalizedTy<'tcx>) {
 178         // We want to insert `ty` with no obligations. If the existing value
 179         // already has no obligations (as is common) we don't insert anything.
 180         if !ty.obligations.is_empty() {
 181             self.map().insert(
 182                 key,
 183                 ProjectionCacheEntry::NormalizedTy(Normalized {
 184                     value: ty.value,
 185                     obligations: vec![],
 186                 }),
 187             );
 188         }
 189     }
 190
 191     /// Indicates that trying to normalize `key` resulted in
 192     /// ambiguity. No point in trying it again then until we gain more
 193     /// type information (in which case, the "fully resolved" key will
 194     /// be different).
 195     pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) {
 196         let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous);
 197         assert!(!fresh, "never started projecting `{:?}`", key);
 198     }
 199
 200     /// Indicates that trying to normalize `key` resulted in
 201     /// error.
 202     pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) {
 203         let fresh = self.map().insert(key, ProjectionCacheEntry::Error);
 204         assert!(!fresh, "never started projecting `{:?}`", key);
 205     }
 206 }
 207
 208 impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> {
 209     fn reverse(&mut self, undo: UndoLog<'tcx>) {
 210         self.map.reverse(undo);
 211     }
 212 }