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::{EvaluationResult, 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, TypeVisitable)]
  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(Clone, 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::AliasTy<'tcx>,
  81 }
  82
  83 impl<'tcx> ProjectionCacheKey<'tcx> {
  84     pub fn new(ty: ty::AliasTy<'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 {
  96         ty: Normalized<'tcx, ty::Term<'tcx>>,
  97         /// If we were able to successfully evaluate the
  98         /// corresponding cache entry key during predicate
  99         /// evaluation, then this field stores the final
 100         /// result obtained from evaluating all of the projection
 101         /// sub-obligations. During evaluation, we will skip
 102         /// evaluating the cached sub-obligations in `ty`
 103         /// if this field is set. Evaluation only
 104         /// cares about the final result, so we don't
 105         /// care about any region constraint side-effects
 106         /// produced by evaluating the sub-boligations.
 107         ///
 108         /// Additionally, we will clear out the sub-obligations
 109         /// entirely if we ever evaluate the cache entry (along
 110         /// with all its sub obligations) to `EvaluatedToOk`.
 111         /// This affects all users of the cache, not just evaluation.
 112         /// Since a result of `EvaluatedToOk` means that there were
 113         /// no region obligations that need to be tracked, it's
 114         /// fine to forget about the sub-obligations - they
 115         /// don't provide any additional information. However,
 116         /// we do *not* discard any obligations when we see
 117         /// `EvaluatedToOkModuloRegions` - we don't know
 118         /// which sub-obligations may introduce region constraints,
 119         /// so we keep them all to be safe.
 120         ///
 121         /// When we are not performing evaluation
 122         /// (e.g. in `FulfillmentContext`), we ignore this field,
 123         /// and always re-process the cached sub-obligations
 124         /// (which may have been cleared out - see the above
 125         /// paragraph).
 126         /// This ensures that we do not lose any regions
 127         /// constraints that arise from processing the
 128         /// sub-obligations.
 129         complete: Option<EvaluationResult>,
 130     },
 131 }
 132
 133 impl<'tcx> ProjectionCacheStorage<'tcx> {
 134     #[inline]
 135     pub(crate) fn with_log<'a>(
 136         &'a mut self,
 137         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 138     ) -> ProjectionCache<'a, 'tcx> {
 139         ProjectionCache { map: &mut self.map, undo_log }
 140     }
 141 }
 142
 143 impl<'tcx> ProjectionCache<'_, 'tcx> {
 144     #[inline]
 145     fn map(
 146         &mut self,
 147     ) -> SnapshotMapRef<
 148         '_,
 149         ProjectionCacheKey<'tcx>,
 150         ProjectionCacheEntry<'tcx>,
 151         InferCtxtUndoLogs<'tcx>,
 152     > {
 153         self.map.with_log(self.undo_log)
 154     }
 155
 156     pub fn clear(&mut self) {
 157         self.map().clear();
 158     }
 159
 160     /// Try to start normalize `key`; returns an error if
 161     /// normalization already occurred (this error corresponds to a
 162     /// cache hit, so it's actually a good thing).
 163     pub fn try_start(
 164         &mut self,
 165         key: ProjectionCacheKey<'tcx>,
 166     ) -> Result<(), ProjectionCacheEntry<'tcx>> {
 167         let mut map = self.map();
 168         if let Some(entry) = map.get(&key) {
 169             return Err(entry.clone());
 170         }
 171
 172         map.insert(key, ProjectionCacheEntry::InProgress);
 173         Ok(())
 174     }
 175
 176     /// Indicates that `key` was normalized to `value`.
 177     pub fn insert_term(
 178         &mut self,
 179         key: ProjectionCacheKey<'tcx>,
 180         value: Normalized<'tcx, ty::Term<'tcx>>,
 181     ) {
 182         debug!(
 183             "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
 184             key, value
 185         );
 186         let mut map = self.map();
 187         if let Some(ProjectionCacheEntry::Recur) = map.get(&key) {
 188             debug!("Not overwriting Recur");
 189             return;
 190         }
 191         let fresh_key =
 192             map.insert(key, ProjectionCacheEntry::NormalizedTy { ty: value, complete: None });
 193         assert!(!fresh_key, "never started projecting `{:?}`", key);
 194     }
 195
 196     /// Mark the relevant projection cache key as having its derived obligations
 197     /// complete, so they won't have to be re-computed (this is OK to do in a
 198     /// snapshot - if the snapshot is rolled back, the obligations will be
 199     /// marked as incomplete again).
 200     pub fn complete(&mut self, key: ProjectionCacheKey<'tcx>, result: EvaluationResult) {
 201         let mut map = self.map();
 202         match map.get(&key) {
 203             Some(ProjectionCacheEntry::NormalizedTy { ty, complete: _ }) => {
 204                 info!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty);
 205                 let mut ty = ty.clone();
 206                 if result.must_apply_considering_regions() {
 207                     ty.obligations = vec![];
 208                 }
 209                 map.insert(key, ProjectionCacheEntry::NormalizedTy { ty, complete: Some(result) });
 210             }
 211             ref value => {
 212                 // Type inference could "strand behind" old cache entries. Leave
 213                 // them alone for now.
 214                 info!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value);
 215             }
 216         };
 217     }
 218
 219     pub fn is_complete(&mut self, key: ProjectionCacheKey<'tcx>) -> Option<EvaluationResult> {
 220         self.map().get(&key).and_then(|res| match res {
 221             ProjectionCacheEntry::NormalizedTy { ty: _, complete } => *complete,
 222             _ => None,
 223         })
 224     }
 225
 226     /// Indicates that trying to normalize `key` resulted in
 227     /// ambiguity. No point in trying it again then until we gain more
 228     /// type information (in which case, the "fully resolved" key will
 229     /// be different).
 230     pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) {
 231         let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous);
 232         assert!(!fresh, "never started projecting `{:?}`", key);
 233     }
 234
 235     /// Indicates that while trying to normalize `key`, `key` was required to
 236     /// be normalized again. Selection or evaluation should eventually report
 237     /// an error here.
 238     pub fn recur(&mut self, key: ProjectionCacheKey<'tcx>) {
 239         let fresh = self.map().insert(key, ProjectionCacheEntry::Recur);
 240         assert!(!fresh, "never started projecting `{:?}`", key);
 241     }
 242
 243     /// Indicates that trying to normalize `key` resulted in
 244     /// error.
 245     pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) {
 246         let fresh = self.map().insert(key, ProjectionCacheEntry::Error);
 247         assert!(!fresh, "never started projecting `{:?}`", key);
 248     }
 249 }
 250
 251 impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> {
 252     fn reverse(&mut self, undo: UndoLog<'tcx>) {
 253         self.map.reverse(undo);
 254     }
 255 }