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