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<'tcx, 'a> {
  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     pub(crate) fn with_log<'a>(
  99         &'a mut self,
 100         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 101     ) -> ProjectionCache<'tcx, 'a> {
 102         ProjectionCache { map: &mut self.map, undo_log }
 103     }
 104 }
 105
 106 impl<'tcx> ProjectionCache<'tcx, '_> {
 107     fn map(
 108         &mut self,
 109     ) -> SnapshotMapRef<
 110         '_,
 111         ProjectionCacheKey<'tcx>,
 112         ProjectionCacheEntry<'tcx>,
 113         InferCtxtUndoLogs<'tcx>,
 114     > {
 115         self.map.with_log(self.undo_log)
 116     }
 117
 118     pub fn clear(&mut self) {
 119         self.map().clear();
 120     }
 121
 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).
 125     pub fn try_start(
 126         &mut self,
 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());
 132         }
 133
 134         map.insert(key, ProjectionCacheEntry::InProgress);
 135         Ok(())
 136     }
 137
 138     /// Indicates that `key` was normalized to `value`.
 139     pub fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: NormalizedTy<'tcx>) {
 140         debug!(
 141             "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
 142             key, value
 143         );
 144         let fresh_key = self.map().insert(key, ProjectionCacheEntry::NormalizedTy(value));
 145         assert!(!fresh_key, "never started projecting `{:?}`", key);
 146     }
 147
 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);
 157                 ty.value
 158             }
 159             ref value => {
 160                 // Type inference could "strand behind" old cache entries. Leave
 161                 // them alone for now.
 162                 debug!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value);
 163                 return;
 164             }
 165         };
 166
 167         map.insert(
 168             key,
 169             ProjectionCacheEntry::NormalizedTy(Normalized { value: ty, obligations: vec![] }),
 170         );
 171     }
 172
 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() {
 179             self.map().insert(
 180                 key,
 181                 ProjectionCacheEntry::NormalizedTy(Normalized {
 182                     value: ty.value,
 183                     obligations: vec![],
 184                 }),
 185             );
 186         }
 187     }
 188
 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
 192     /// be different).
 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);
 196     }
 197
 198     /// Indicates that trying to normalize `key` resulted in
 199     /// error.
 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);
 203     }
 204 }
 205
 206 impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> {
 207     fn reverse(&mut self, undo: UndoLog<'tcx>) {
 208         self.map.reverse(undo);
 209     }
 210 }