compiler/rustc_infer/src/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     Recur,
  94     Error,
  95     NormalizedTy(NormalizedTy<'tcx>),
  96 }
  97
  98 impl<'tcx> ProjectionCacheStorage<'tcx> {
  99     #[inline]
 100     pub(crate) fn with_log<'a>(
 101         &'a mut self,
 102         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 103     ) -> ProjectionCache<'a, 'tcx> {
 104         ProjectionCache { map: &mut self.map, undo_log }
 105     }
 106 }
 107
 108 impl<'tcx> ProjectionCache<'_, 'tcx> {
 109     #[inline]
 110     fn map(
 111         &mut self,
 112     ) -> SnapshotMapRef<
 113         '_,
 114         ProjectionCacheKey<'tcx>,
 115         ProjectionCacheEntry<'tcx>,
 116         InferCtxtUndoLogs<'tcx>,
 117     > {
 118         self.map.with_log(self.undo_log)
 119     }
 120
 121     pub fn clear(&mut self) {
 122         self.map().clear();
 123     }
 124
 125     /// Try to start normalize `key`; returns an error if
 126     /// normalization already occurred (this error corresponds to a
 127     /// cache hit, so it's actually a good thing).
 128     pub fn try_start(
 129         &mut self,
 130         key: ProjectionCacheKey<'tcx>,
 131     ) -> Result<(), ProjectionCacheEntry<'tcx>> {
 132         let mut map = self.map();
 133         if let Some(entry) = map.get(&key) {
 134             return Err(entry.clone());
 135         }
 136
 137         map.insert(key, ProjectionCacheEntry::InProgress);
 138         Ok(())
 139     }
 140
 141     /// Indicates that `key` was normalized to `value`.
 142     pub fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: NormalizedTy<'tcx>) {
 143         debug!(
 144             "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
 145             key, value
 146         );
 147         let mut map = self.map();
 148         if let Some(ProjectionCacheEntry::Recur) = map.get(&key) {
 149             debug!("Not overwriting Recur");
 150             return;
 151         }
 152         let fresh_key = map.insert(key, ProjectionCacheEntry::NormalizedTy(value));
 153         assert!(!fresh_key, "never started projecting `{:?}`", key);
 154     }
 155
 156     /// Indicates that trying to normalize `key` resulted in
 157     /// ambiguity. No point in trying it again then until we gain more
 158     /// type information (in which case, the "fully resolved" key will
 159     /// be different).
 160     pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) {
 161         let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous);
 162         assert!(!fresh, "never started projecting `{:?}`", key);
 163     }
 164
 165     /// Indicates that while trying to normalize `key`, `key` was required to
 166     /// be normalized again. Selection or evaluation should eventually report
 167     /// an error here.
 168     pub fn recur(&mut self, key: ProjectionCacheKey<'tcx>) {
 169         let fresh = self.map().insert(key, ProjectionCacheEntry::Recur);
 170         assert!(!fresh, "never started projecting `{:?}`", key);
 171     }
 172
 173     /// Indicates that trying to normalize `key` resulted in
 174     /// error.
 175     pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) {
 176         let fresh = self.map().insert(key, ProjectionCacheEntry::Error);
 177         assert!(!fresh, "never started projecting `{:?}`", key);
 178     }
 179 }
 180
 181 impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> {
 182     fn reverse(&mut self, undo: UndoLog<'tcx>) {
 183         self.map.reverse(undo);
 184     }
 185 }